Полный текст:
Тема
4.2. Задачи линейного программирования
1755. Для
откорма животных употребляют два вида кормов; стоимость 1 кг корма ? вида – 5 ден.
ед., а корма ?? – 2 ден. ед. В каждом килограмме корма ? вида содержится 5 ед.
питательного вещества А, 2,5 ед. питательного вещества Б и 1 ед. питательного
вещества В, а в каждом килограмме корма ?? вида соответственно 3, 3 и 1,3 ед.
Какое количество корма каждого вида необходимо расходовать ежедневно, чтобы
затраты на откорм были минимальными, если суточный рацион предусматривает
питательных единиц типа А не менее 225 ед., типа Б – не менее 150 ед. и типа в
– не менее 80 ед.?
Решение
Занесем исходные данные в таблицу
Питательное вещество
Необходимый минимум питательных веществ
Число единиц питательных веществ в 1 кг корма
?
??
А
225
5
3
Б
150
2,5
3
В
80
1
1,3
Составим
экономико – математическую модель задачи.
Обозначим
- количество кормов ?
и ??, входящих в дневной рацион. Тогда этот рацион будет включать единиц питательного вещества А, единиц вещества Б и единиц питательного
вещества В. Так как содержание питательных веществ А, Б, В в рационе должно
быть не менее соответственно 225, 150 и 80 единиц, то получим систему
неравенств:
(*)
Кроме того,
переменные . (**)
Общая стоимость
рациона составит (в ден. ед)
(***)
Итак, экономико – математическая
модель задачи: составить дневной рацион , удовлетворяющий системе (*) и условию (**), при котором
функция (***) принимает минимальное значение.
При компьютерной
реализации данной задачи получаем следующее решение:
, F=150
ден.ед.
Решение
закончено.
Тема
4.3. Задачи транспортного типа.
1764. В
резерве трех железнодорожных станций А, В и С находятся соответственно 60, 80 и
100 вагонов. Составить оптимальный план перегона этих вагонов к четырем пунктам
погрузки хлебе, если пункту № 1 необходимо 40 вагонов, № 2 – 60 вагонов, № 3 –
80 вагонов и № 4 – 60 вагонов. Стоимости перегонов одного вагона со станции А в
указанные пункты соответственно равны 1, 2, 3, 4 ден. ед., со станции В – 4, 3,
2, 0 ден. ед. и со станции С – 0, 2, 2, 1 ден. ед.
Решение
1. Проверяем сбалансированность
модели ТЗ. Суммарный резерв вагонов на трех железнодорожных станциях составляет
вагонов; суммарная потребность четырех пунктов погрузки хлеба
в вагонах равна вагонов. Таким образом, модель ТЗ является сбалансированной
(закрытой).
2. Заносим исходные данные в
распределительную таблицу.
Пункты погрузки
Запасы
станции
1
2
3
4
60
4
3
2
0
80
0
2
2
1
100
потребности
40
60
80
60
3. Строим опорный план методом
«минимального элемента». Находим количество вагонов, которые следует отправить
по данному маршруту. Находим клетку с минимальным тарифом; это клетка (2;4), в
которую заносим максимально возможное количество вагонов
вагонов.
Затем мысленно вычеркиваем (закрываем) столбец. Из оставшихся клеток таблицы находим клетку с минимальным
тарифом; это – клетка (3;1), в которую вновь вносим максимально возможное
количество вагонов
вагонов.
Закрываем столбец . Из оставшихся клеток наименьший тариф имеет клетка (1;2), в
которую заносим
вагонов.
Закрываем столбец . ,
Начальный опорный план построен.
Посчитаем стоимость перегонов вагонов по этому плану.
ден. ед.
4. Проверяем начальный опорный
план на вырожденность. Для этого считаем число загруженных клеток таблицы; оно
равно 5. Согласно требованиям, предъявляемым к опорному плану, число
загруженных клеток должно быть равно 4+3-1=6. Таким образом, заключаем, что
начальный опорный план вырожден.
Введем нулевую постановку в клетку, имеющую наименьший
тариф, такая клетка становиться условно занятой – (1;1).
5. Строим систему уравнений для
определения потенциалов поставщиков и потребителей, используя только
загруженные клетки таблицы:
Пункты погрузки
Запасы
станции
1
2
3
4
60
0
4
3
2
0
80
-1
0
2
2
1
100
-1
потребности
40
60
80
60
1
2
3
1
При этом потенциал полагаем
равным нулю. В результате решения системы уравнений методом последовательного
исключения неизвестных находим значения потенциалов:
6. Находим косвенные тарифы
незагруженных клеток таблицы
7. Находим оценки незагруженных
клеток таблицы:
Поскольку все оценки свободных клеток неположительные, то
начальный опорный план является оптимальным планом перегона вагонов с трех
железнодорожных станций в четыре пункта погрузки хлеба:
.
Это означает, что с
первой станции следует перегнать 60 вагонов во второй пункт, со второй станции
следует перегнать 20 вагонов в третий пункт и 60 вагонов в четвертый пункт, и с
третьей станции следует перегнать 40 вагонов в первый пункт и 60 – в третий.
Суммарная минимальная стоимость перегона равна 280 ден. ед
Решение закончено.