Вопрос20

МЕТОДЫ ОПРЕДЕЛЕНИЯ ОПОРНОГО ПЛАНА В РАСПРЕДЕЛИТЕЛЬНЫХ ЗАДАЧАХ

Нетрудно заметить, что задача (15.1—15.5) является частным случаем общей задачи линейного программирования и в принци­пе ее можно было бы решать симплекс-методом. Однако специ­фический вид транспортной модели (ограничения только типа «=», все коэффициенты при неизвестных в левых частях ограни­чений равны 1 или 0) позволил разработать для транспортных моделей более быстродействующую модификацию симплекс-ме­тода. При изучении и применении этого метода полезно исполь­зовать стандартное табличное представление транспортной мо­дели, в котором отражается вся исходная информация задачи (табл. 84).

представления транспортной модели

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

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

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

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

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

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

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

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

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

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

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

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

2. В соответствующую клетку записывают значение ху, равное наименьшей из соответствующих величин Л( и В/.

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

4. Если Af~0nBj>0, то из таблицы вычеркивают соответству­ющую строку и далее с этой строкой не работают. Если Д->0 и Bj=0, то вычеркивают соответствующий столбец. Если обе

величины А- и Щ равны нулю, то вычеркивают только (!) строку или только столбец (безрахчично что). С оставшимся столбцом (строкой), имеющим нулевое значение В}{А{), далее работают, как с нормальным столбцом (строкой).

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

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

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

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

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

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

полнению условия Xj»j*-D. Доводить оптимальный план до вида

x'j*j*<D нецелесообразно, так как это приведет его с точки зре­ния изменения целевой функции к еще большему ухудшению.

Аналогичным образом рассматривается ограничение D<x,»j*<D. При его невыполнении по циклу перемещается такое значение Ах,-**, которое наносит наименьший вред оптимальности задачи;

3) если значение Дх,-*^, перемешаемое по циклу, попадая в вер­шины с отрицательными знаками, нарушает условие неотрица­тельности переменных (*,■,>0), то данная задача при поставлен­ных условиях не имеет решения.

С учетом всех необходимых изменений исходная транспортная таблица задачи 15.6 примет вид, представленный в таблице 97.

97. Исходная транспортная таблица задачи 15.6, в которой учтены требование сбалансированности задачи и первые три дополнительных условия*

'Величины, изменившиеся в результате учета дополнительных ограничений, обведены. Кроме того, в результате учета 3-го ограничения вычеркнута 4-я строка таблицы и с учетом требования сбалансированности в таблицу введена строка с фиктивным источником ресурса. Предполагается, что в клетки (2,4), (3,3) и (4,4) уже внесены ресурсы, равные 300, 450 и 150 соответственно.

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

Вырожденные решения транспортной задачи.

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

Рассмотрим начальную транспортную таблицу задачи 15.6 (табл. 97). Применяя метод аппроксимации, найдем соответству­ющее опорное решение (табл. 98).

На первом шаге реализации данного метода была заполнена клетка (1,4). При этом ресурсы А\ и й4 согласно пятому шагу ме­тода аппроксимации уменьшатся до нуля. После этого четвертый столбец был вычеркнут, а первая строка с нулевым значением ре­сурса А] сохранена. На следующем шаге этот нулевой ресурс за­полнил клетку (1,3) — появилась условно занятая клетка, что и определило вырожденность опорного решения.

Обратим внимание на следующее обстоятельство. В принципе на первом шаге можно было бы вычеркнуть не только четвертый столбец, но и первую строку. Последующая процедура метода аппроксимации все равно дала бы допустимое решение задачи. Однако число занятых клеток в этом допустимом решении было бы меньше (т + п— 1), что не позволяет применить метод потен­циалов. Чтобы довести число занятых клеток до (т + л - 1), при­шлось бы некую подходящую (обеспечивающую в дальнейшем по­строение необходимых циклов) клетку объявить условно заня­той, то есть заполнить нулем. При этом пришлось бы руковод­ствоваться двумя правилами: 1) за условно занятую клетку надо принимать ту, которая не образовывает с другими занятыми клетками замкнутых многоугольников; 2) условно занятой мож­но объявлять только ту клетку, которая впоследствии, попадая в цикл, находилась бы в положительной вершине многоугольника. В противном случае при перемещении поставок по циклу и улуч­шении плана может нарушиться условие неотрицательности пе­ременных (x,j>0). Выполнение этих правил является довольно сложной процедурой даже для сравнительно простых транспорт­ных таблиц, а в больших таблицах вообще нереально. Именно это обстоятельство делает практически полезным тот алгоритм метода аппроксимации (так же, как и метода минимального эле­мента), который был изложен ранее. Этот алгоритм автомати­чески находит подходящую условно занятую клетку, он же легко

реализуется на ЭВМ.

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