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

(транспортные расходы минимальны). Выполняются ли условия потенциальности для плана Х' - неизвестно, но каждой клетке (i, j) макета 8, исходя из потенциальности плана Х, соответствует неравенство vj - ui £ aij или, наоборот, aij ≥ vj - ui. Возьмем из каждой клетки макета соответствующий х'ij, умножим его на левую и правую части последнего неравенства и сложим. Получим неравенство <

p>.

Двойную сумму в правой части обозначим для краткости буквой S:

,

ее можно переписать в виде разности двух двойных сумм:

.

Преобразуем эти суммы следующим образом. Первая из них в развернутом виде дает

или

.

Аналогично вторую двойную сумму можно записать так:

.

Тогда равенство запишется в иной форме:

.

Но есть сумма компонент плана по j-му столбцу, она

равна потребности j-ro пункта назначения

.

Аналогично есть сумма компонент плана, взятая по i-й строке, она равна запасам в i-м пункте отправления

.

Эти равенства сумм компонент по строке и столбцу соответственно запасам и потребностям будут выполняться для любого допустимого плана, в том числе и для взятого в самом начале плана Х (xij):

Поэтому для любых допустимых планов будем иметь

и в написанном выше равенстве суммы x¢ij можно заменить соответствующими суммами xij:

Теперь вернемся к форме записи

.

В плане Х (xij) по условию его потенциальности для каждой положительной компоненты xij> 0 выполняется равенство vj - ui = aij.

Остальные компоненты плана равны нулю, и соответствующие слагаемые в сумме обратятся в нули. Поэтому полученная сумма будет равна

.

Подставляя в

,

приходим к неравенству

или zmin ≥ zX. Иными словами, транспортные расходы по плану Х меньше или равны минимальным расходам. Но меньше минимальных они быть не могут, остается только равенство zX = zmin План Х доставляет минимальные издержки, т.е. он оптимален, что и требовалось доказать.

Таким образом, если план потенциален, то он оптимален. Это и является тем критерием, по которому судят об оптимальности плана.

Справедливо и обратное положение: если план оптимален, то он о6язательно потенциален. Это условие (необходимость) принимается без доказательства. [5]

10. Особенности решения транспортных задач с неправильным балансом

Может случиться, что в рассматриваемых пунктах запасы не равны потребностям: или запасы превосходят потребности, или же запасы не обеспечивают потребностей.

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

Для решения задачи поступаем следующим образом.

Первый случай. .

В математическую модель транспортной задачи введем фиктивный (l+l) - й пункт назначения. Для этого в матрице задачи предусмотрим один столбец, для которого потребность будет равна излишку груза:

,

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

min

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

Второй случай.

Если запасов не хватает для удовлетворения потребностей, т.е. , то вводим фиктивный (k+1) - й пункт отправления, которому приписываем запас груза, равный

,

тарифы на доставку грузов из этого фиктивного склада опять, полагаем нулевыми. В матрице добавится одна строка. На функционале это не отразится, а система ограничений задачи станет совместной, т.е. станет возможным отыскание оптимального плана на минимум стоимости перевозок. [5]

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

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

11.1 Предварительный шаг

Этот шаг включает следующих три этапа.

1. Находим допустимый ациклический план.

2. Составляем систему чисел - потенциалов пунктов отправления и пунктов назначения.

3. Анализируем систему на потенциальность. Если она потенциальна (т.е. план потенциален), то найденный план оптимален. Если система не потенциальна, приступаем к общему шагу.

Первый этап: нахождение допустимого ациклического плана способом северо-западного угла.

Невзирая на тарифы, начинаем составление плана с заполнения левой верхней клетки (1,1) (с северо-западного угла).

Смотрим на запасы M1 и потребности N1. Если M1 < N1, то в клетку (1,1) вписываем Ml (т.е. отдаем пункту назначения весь запас груза из первого пункта отправления - случай в таблице). Если N1 < M1, то в клетку (1,1) записываем N1, т.е. покрываем всю потребность первого пункта назначения за счет первого пункта отправления.

 Скачать реферат