Табличная форма представления транспортной модели

Для формализованного изложения методов решения транс­портной задачи сформулируем основные понятия, родственные введенным для общей задачи линейного программирования.

Допустимым решением транспортной задачи называется такая совокупность значений величин Ху, /= \,..., т, ]= \,..., п, для кото­рой выполняются все ограничения. Допустимое решение, при котором целевая функция достигает минимума (максимума), на­зывается оптимальным. Среди допустимых решений выделяют оазисные, в которых не более (т+п— I) величин Ху отличаются от нуля, а остальные строго равны нулю. Наличие таких реше­ний—общее свойство задач линейного программирования; ко-мичество ненулевых переменных в базисном решении не может превышать числа независимых ограничений. В данном случае в идаче имеется (т + п) ограничений типа (15.2), (15.3), но с уче­том балансового условия (15.4) независимых ограничений оста­ется только (т+п—1). Следовательно, в базисном решении транспортной задачи должно быть не более (т+п— 1) ненуле-пых переменных. Как и в общей задаче линейного программиро-

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

В матричном представлении задачи (табл. 84) клетки, в кото­рых величины Хц отличны от нуля, называют занятыми, а все ос­тальные — свободными. Таким образом, любое базисное решение содержит не более (т +п— 1) занятых клеток. Если число заня­тых клеток (К_зш) в точности равно (т +п— 1), решение называ­ется невырожденным, в противном случае — вырожденным. По­скольку в рассматриваемом ниже алгоритме мы будем опериро­вать только базисными решениями, то в ходе решения для конт­роля необходимо рассчитывать величину К_зш. Если ^зан > (^{т + п} — 1)> ^то решение на очередной итерации найдено неверно и необходимо искать ошибку. В вырожденном решении некоторые базисные переменные равны нулю; соответствующие им клетки заполняются нулями и считаются условно занятыми.

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

В отличие от первого опорного плана симплекс-метода, име­ющего чисто условный характер, распределительный метод пред­полагает составление реального опорного плана; методы его на­хождения очень важны. Чем ближе опорный план к оптимально­му, тем меньше итераций необходимо будет произвести для дос­тижения оптимального решения, тем меньше затраты времени и выше точность вычислений.

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

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