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

^~^^_^ Потребители ^^"---^^ ресурса Источники ^~"--^^^ ресурса ^~~~\

1

2

3

п

Наличие ресурсов

1

хп

с„

х\г

Сп

Х\1

С,з

х\п

С|я

А

2

*21

с21

х21

С22

хгъ

с73

х2п

Сгп

Аг

т

хт\

Ст\

хт?

С„а

хтЪ

С„в

хтп

г

Ат

11отребности в >ссурсах

В\

Вг

в3

в„

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

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

309

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

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

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

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

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

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

Метод минимального (максимального) элемента.

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

310

стоят наименьшие величины Су. Тем самым достигается опреде­ленное приближение к оптимальному решению. Алгоритм метода сводится к следующему.

1. Из всех значений Су в матрице выбирают наименьшее.

1. В соответствующую клетку записывают значение Ху, равное наименьшей из соответствующих величин А,- и В/.

Хд=гят(А„ Ву).

3. Определяют новые значения величин А-, и В/.

А1 = А~Ху', Ву = Ву—Хд.

4. Если А-=0 и В^>0, то из таблицы вычеркивают соответству­ющую строку и далее с этой строкой не работают. Если 4^;>0и -б)=0, то вычеркивают соответствующий столбец. Если обе величины А\жВ'] равны нулю, то вычеркивают только (!) строку или только столбец (безразлично что). С оставшимся столбцом (строкой), имеющим нулевое значение В^(Л[), далее работают, как с нормальным столбцом (строкой).

4. Далее указанные операции повторяют до тех пор, пока в таб-мице все строки, кроме одной (или все столбцы, кроме одного), не окажутся вычеркнутыми. Оставшиеся ресурсы А-Щ) заносят в соответствующие клетки последней невычеркнутой строки (пос-нсднего невычеркнутого столбца). Полученное решение проверя­ют по числу занятых клеток. Кроме того, необходима проверка ог­раничений типа (15.2) и (15.3). Если ограничения выполняются, то по формуле (15.1) вычисляют значение целевой функции.

Если в ходе реализации приведенного алгоритма на каких-

и ибо шагах окажется, что одновременно Л/=0и.бу=0, получен­ное опорное решение будет вырожденным (некоторые из заня­тых клеток будут условно занятыми).

При решении задач на максимум приведенный алгоритм ме­няется только в первом шаге: вместо минимального значения Су находят максимальное и далее работают с соответствующей клет­кой. Рассмотрим конкретный пример.

Задача 15.5. В хозяйстве для обеспечения грубыми и сочными кормами 5 животноводческих ферм имеется 3 источника кормов: .' нолевых и 1 кормовой севооборот. Необходимо составить опти­мальный план закрепления источников кормов за фермами, ми­нимизирующий стоимость перевозки кормов. Исходные данные приведены в таблице 85.

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

311