3.3. Метод оптимального решения транспортной задачи

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

Рассмотрим решение транспортных задач методом потенциалов.

Теорема 2. Для того, чтобы транспортная задача имела оптимальное решение с системой чисели, называемых потенциалами необходимо и достаточно, чтобы выполнились два условия:

1. при условии, что , (3.5)

т.е. для занятых перевозками грузов клеток транспортной таблицы;

2. при условии, что , (3.6)

т.е. для незанятых клеток таблицы.

Потенциалы иявляются переменными двойственной транспортной задачи и означают плату за перевозку единицы груза в пунктах отправления поставщиками и в пунктах получения потребителями соответственно. Следовательно их сумма равна транспортному тарифу отi-го поставщика k-тому потребителю, т.е.

Условия (3.5) и (3.6) получены на основании второй теоремы двойственности.

При определении оценок для незанятых перевозками клеток транспортной таблицы условие (3.6) запишем в виде:

(3.7)

Значение является условием оптимальности опорного плана транспортной задачи. Если условие (6.7) не выполняется, т.е., то решение задачи не является оптимальным. Для его определения находят новый опорный план, перераспределяя соответствующий груз в незанятую точку с отрицательной оценкой.

Алгоритм решения транспортной задачи методом потенциалов:

1. Составление транспортной таблицы для соответствующего условия задачи.

2. Построение первоначального(исходного) решения(плана) способом минимальных тарифов( стоимостей) или способом «северо-западного угла».

3. Проверка опорности плана по условию . Если количество занятых клеток в транспортной таблице окажется меньше, чем, то включают нуль в одну из незанятых перевозками грузов клетку. Обычно выбирают клетку с наименьшим тарифом, при этом занятая нулем клетка не должна образовывать циклов с другими занятыми клетками таблицы.

4. Вычисление значения целевой функции по зависимости

(3.8)

5. Составление системы уравнений для потенциалов на основании условия (3.5). полученная система уравнений с m+n переменными является замкнутой. Для ее решения один из потенциалов принимают в качестве параметра и полагают произвольному значению, например, . В транспортную таблицу вводятся дополнительные строка и столбец для соответствующих значений потенциалов

6. Проводится оценка оптимальности (для не занятых клеток транспортной таблицы) составленного опорного плана согласно условию (6.7). Если хотя бы одна оценка не удовлетворяет этому условию, то решение не является оптимальным. Для определения оптимального плана строят новый опорный план.

7. Построение нового опорного плана. Если отрицательных оценок в полученном плане оказалось несколько, то из них выбирается наименьшая (наибольшая отрицательная по абсолютной величине). Клетку с этой оценкой называют перспективной в том смысле, что в нее включают определенную величину перевозимого груза. При заполнении груза в эту клетку следует изменить объемы перевозок грузов в других клетках транспортной таблицы, расположенных в так называемом цикле.

Циклом или замкнутым прямоугольным контуром в транспортной таблице для перспективной клетки называется последовательность отрезков(ломаная замкнутая линия), проведенных параллельно строкам и столбцам ,концы которых соединены в занятых клетках таблицы. Для каждой не занятой клетки транспортной таблицы можно построить единственный цикл.

8. Вершинам цикла присваиваются поочередности знаки «+» и «-», начиная с не занятой перспективной клетки. Величина перераспределяемого грузы выбирается наименьшая из чисел (поставок), расположенных в клетках (вершинах цикла) таблицы со знаком «-». Выбранная величина перераспределяется по циклу , прибавляя к соответствующим объемам грузов расположенных в клетках со знаком «+» и вычитая из объемов поставок для клеток таблицы со знаком «-»

9. Полученный новый план проверяется на опорность и оптимальность.

Если в оптимальном плане транспортной задачи оценка для не занятой клетки равна нулю, то задача имеет несколько оптимальных планов, но значение целевой функции (стоимость перевозки грузов) не изменится.

Значение целевой функции после перераспределения груза по циклу изменяется на величину∆Z=x_ik*S_ik,

Где ∆ Z- разность значений целевой функции двух планов;