Нахождение оптимального решения

Пример нахождения опорного плана

Поставщики	Потребители и их спрос	Мощность поставщиков

F=14 x₁₁ + 28 x₁₂ + 21 x₁₃ + 28 x₁₄ + 10 x₂₁ + 17 x ₂₂ + 15 x₂₃ + 24 x₂₄ + 14 x₃₁ + 30 x₃₂ +25 x₃₃ + 21 x₃₄

Первоначальный план получен по методу северо-западного угла. Задача сбалансированная (закрытая).

Таблица 1

Стоимость перевозок по данному плану составляет: 1681:

F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 =1681

С помощью методов построения первоначального опорного плана можно получить вырожденный или невырожденный опор­ный план. Построенный план транспортной задачи как задачи линейного программирования можно было бы довести до оптимального с помощью симплексного метода. Однако из-за громоздкости симплексных таблиц, со­держащих тп неизвестных, и большого объема вычислительных работ для получения оптимального плана используют более простые методы. Наиболее часто применяются метод потенциалов (модифицированный распредели­тельный метод) и метод дифференциальных рент.

Метод потенциалов. Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).

Алгоритм нахождения решения транспортной задачи этим методом основан на соотношении между прямой и двойственной задачами.

Дата добавления: 2014-11-29