Транспортная задача. Тема Линейное программирование. Транспортная задача. Метод потенциалов. Задание

• Название: Тема Линейное программирование. Транспортная задача. Метод потенциалов. Задание
• Анкор: Транспортная задача
• Дата: 28.02.2023
• Размер: 74.55 Kb.
• Имя файла: Transportnaja_zadacha_metod_potencialovВ7.docx
• Тип: Решение; #960063

Тема: Линейное программирование. Транспортная задача. Метод потенциалов.

Задание: составить оптимальный план распределения поставок. Начальный базисный план перевозок можно сделать любым известным способом. Стоимость перевозки единицы груза, а также потребности и наличие груза даны в таблице.

Поставщики/ Потребители	95	150	85	80
115	17	11	9	12
90	12	18	8	16
205	10	15	14	7

Решение

Методом минимального элемента составляем начальный план перевозок.

Так как (минимальный элемент), то в него помещаем 80, оставшиеся ячейки в четвертом столбце будут пустыми так как весь груз на данном объекте распределен. В ячейку помещаем 85, а в ячейку помещаем 5, так как другие ячейки строки 2 не могут быть заполнены.

В ячейку помещаем 115, так как в этой ячейке находится минимальная стоимость из всех оставшихся. На данном объекте осталось 30 единиц груза, его помещаем в ячейку , так как это последний оставшийся потребитель, который готов приобрести последний оставшийся груз.

Поставщики/ Потребители	95	150	85	80
115	17	11 115	9	12
90	12	18 5	8 85	16
205	10 95	15 30	14	7 80

Для каждой заполненной клетки записываем уравнение потенциалов:

, где u_i – номер строки, а v_j- номер столбца

Решая систему уравнений получаем:



Составим разности потенциалов для свободных клеток:













Так как , то опорное решение не является оптимальным и его можно улучшить, перейдя от одного опорного решения к другому.

Для свободной клетки (2;1), имеющей положительную оценку ( ) строится цикл.

У вершин со знаком (-) выбираем минимальный груз, он равен 5. Его прибавляем к грузам, стоящих у положительных вершин, и отнимаем от грузов, стоящих у отрицательных вершин.

После перераспределения груза в пределах цикла имеем следующую транспортную таблицу. Транспортная таблица не является окончательной, поэтому выполняем дальнейшие расчёты.

Поставщики/ Потребители	95	150	85	80
115	17	11 115	9	12
90	12 5	18	8 85	16
205	10 90	15 35	14	7 80

Для каждой заполненной клетки записываем уравнение потенциалов:

, где u_i – номер строки, а v_j- номер столбца

Решая систему уравнений получаем:



Составляем разности потенциалов для свободных клеток:













Получили, что все оценки свободных клеток отрицательные, следовательно, найденное решение оптимальное. Найденный план оптимальный.



Стоимость перевозок равна:





Ответ:

Стоимость перевозок равна: F= .