Решение транспортной задачи линейного программирования
Автор: Юлия Будникова • Ноябрь 22, 2020 • Практическая работа • 996 Слов (4 Страниц) • 427 Просмотры
Министерство образования и науки РФ
Федеральное государственное бюджетное образовательное учреждение высшего образования
Юго-западный государственный университет
Кафедра информационной безопасности
Теория игр и исследование операций
Практическая работа №3:
«Решение транспортной задачи линейного программирования».
Вариант №1
Выполнила:
студентка, группы ИБ-01м Будникова Ю.А.
Проверил:
Профессор, к. ф.-м. н Добрица В.П.
Курск 2020
Цель занятия:
1. Освоить методы формирования начального опорного решения транспортной задачи линейного программирования
2. Освоить методы оптимизации начального опорного решения транспортной задачи.
3. Ознакомиться с методами численного решения транспортной задачи с помощью надстройки “Поиск решения” в среде MS Excel
Поставщики товара – оптовые коммерческие предприятия [pic 1] имеют запасы товаров соответственно в количестве [pic 2] ед. и розничные торговые предприятия [pic 3] - подали заявки на закупку товаров в объемах соответственно: [pic 4] Тарифы перевозок единицы груза с каждого из пунктов поставки в соответствующие пункты потребления заданы в виде матрицы [pic 5]
Найти такой план перевозок груза от поставщиков к потребителям, чтобы совокупные затраты на перевозку были минимальными.
[pic 6] [pic 7] [pic 8].
[pic 9]
Для начала установим тип транспортной задачи. Для этого проверим сумму запасов и потребностей. . .[pic 10][pic 11]
А это значит, что задача открытая. Мы имеем запасов больше, значит добавим фиктивного потребителя с запросом равным избытку запасов. Для этого добавим новый столбец в таблицу.[pic 12]
Таблица 1
[pic 13] | 125 | 75 | 200 | 220 | 175 | 5 |
[pic 14] | ||||||
22 | 23 | 21 | 11 | 8 | 3 | 0 |
188 | 7 | 17 | 5 | 2 | 4 | 0 |
210 | 2 | 16 | 8 | 4 | 3 | 0 |
380 | 3 | 9 | 21 | 8 | 4 | 0 |
Для каждой строки и столбца таблицы 1 найдем разности между двумя минимальными величинами издержек и поместим их в отдельные ячейки Так, например, в строке А1 минимальные величины издержек 8 и 3, разность между ними равна 5. Точно так же для столбца В1 минимальные величины издержек 2 и 3, разность между ними равна 1.
Таблица 2
[pic 15] | 125 | 75 0 | 200 | 220 | 175 | 5 | Разность |
[pic 16] | |||||||
22 | 23 | 21 | 11 | 8 | 3 | 0 | 5 |
188 | 7 | 17 | 5 | 2 | 4 | 0 | 2 |
210 | 2 | 16 | 8 | 4 | 3 | 0 | 1 |
380 305 | 3 | 9 (75) | 21 | 8 | 4 | 0 | 1 |
Разность | 1 | 7 | 3 | 2 | 0 | 0 |
Вычислив разности, видим, что наибольшая из них соответствует столбцу В2, и строке А1. В этом столбце минимальные издержки соответствуют клетке, находящейся на пересечении столбца В2 и строки А4 – 9 ед. В эту клетку и занесем значение потребности клиента В2 – 75 ед. Исключим из рассмотрения столбец В2, а запасы производителя А1 будем считать равными 380 – 75 = 305 ед.
...