Х,*у* > Д

(15.18)

где /*, /* — некоторые фиксированные значения индексов /и у, Л —заданная кон-

станта.

При наличии такого ограничения данные о ресурсах /*-го по­ставщика и у*-го потребителя ресурса преобразовываются в транспортной таблице следующим образом:

4*=4*-А 5).=5, *-Д

где А\,, В'^ — новые значения объемов ресурса.

(15.19)

Очевидно, чтобы задача не теряла смысла, должны выпол­няться условия:

Я< Л, *; В< В_Г.

Помимо изменений транспортной таблицы в соответствии с (15.19) необходима проверка новых значений А-*мВ^*. Если /II* =0, то из транспортной таблицы вычеркивается г*-я строка.

Если 5у*=0, то вычеркивается у*-й столбец. При 4^г*=0и2у> =0 вычеркиваются /*-я строка и/*-й столбец.

Содержательно условия (15.18) и (15.19) означают, что /*-й по­ставщик гарантированно поставляет /*-му потребителю ресурс объема Э. Кроме того, если это будет выгодно с точки зрения до­стижения оптимального значения целевой функции, при Л/*> 0и5у*> 0 допускается превышение указанного объема. Одно­временно с операцией (15.19) необходимо «запомнить», что фак­тически в клетку (/'*, у*) уже помещен ресурс Д хотя формально этот факт в транспортной таблице отражать не нужно.

К ограничениям типа (15.18) относится первое ограничение из задачи 15.6 (его формализованная запись х₃з> 450).

Соответственно в транспортной таблице 96 необходимо про­вести следующие изменения:

4=4з-⁴⁵⁰⁼⁴⁵°; '^=^-450=600. (15.20)

После решения задачи и получения оптимального плана дан­ное число вносится в клетку, то есть прибавляется к значению х^з- Если в процессе решения х^=0, то х₃з = 0 + 450 и ограниче­ние выполняется по нижней границе. Если хзз> 0, то ограниче­ние принимает вид х₃₃ > 450.

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

Перейдем к рассмотрению дополнительных ограничений типа

х, у = 2). (15.21)

Первоначальные действия по учету таких ограничений анало­гичны действиям для случая ограничений вида х, у > Б. Тем са­мым в клетку (/*, /*) уже фактически будет помещен ресурс Д

Дальнейшие действия зависят от значений величин А[*иВ'^.

Если оказывается, что одна из величин А-*иВ'^* (или обе) равны нулю, алгоритм полностью подобен случаю х, у > В. Если же обе указанные величины оказались больше нуля, то дополнительно проводится изменение соответствующей стоимости транспорти­ровки С/у. При этом новое значение С, -*, * зависит от того, мини­мизируется целевая функция 2жш максимизируется.

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

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

Указанное изменение величины С, -*, * называется блокировкой оценки клетки (/*, /*). Практически вместо оценки клетки С, *, * ставится искусственная оценка М. При этом полагается, что М—> 0 при решении задачи на максимум и М—> °о при решении задачи на минимум. Такой прием, который также проводится до решения задачи, позволяет не только блокировать оценку, но и за счет приведения М к экстремальному значению не допустить попадания ресурса в блокированную клетку¹.

В рассматриваемом примере (задача 15.6) к ограничениям типа (15.21) относятся второе и третье, которые можно записать как х₂4=300; х₄₄ = 150. Соответственно в транспортной таблице (табл. 96) нужно провести следующие изменения (учтен тот факт, что изменение величины 5₄ должно проводиться дважды):

4=^-300=1000; Д^=Я₄-300=700; 4=Л4-¹⁵⁰=°; Щ=Щ~150=550.

Поскольку второе ограничение (х₂4 = 300) не привело к нуле­вым значениям величин 4^И^> необходима блокировка оценки клетки (2, 4). Для этого считают, что С₂₄ = М-> 0. Кроме того, по­скольку окончательное значение величины Л) равно нулю, чет­вертую строку следует вычеркнуть из таблицы.

Помимо рассмотренных выше ограничений на практике встречаются дополнительные ограничения типа

Х; *у*< 2) ИЛИ /)< Х_; *_у*< 1).

Таким, например, является четвертое ограничение из задачи 15.6.

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

1) если заданное ограничение х^< Б или 1> < х₍*_у*< 1> выпол­няется, полученное решение задачи принимается без изменений;

2) если ограничение х, у< 1) не выполняется, то по правилу

построения цикла величина Ах^ (х, '*_у*=х₍*у*-Дх₍*_у*=/)) переме­щается по циклу, приводя таким образом решение задачи к вы-

¹ Следует иметь в виду, что в ряде исключительных случаев прием блокировки оценки не срабатывает и в клетку попадают значения х,»у > 0. В таких случаях зада­ча с поставленным ограничением не имеет решения (система условий задачи несов­местна).

полнению условия х, '*у* = 1). Доводить оптимальный план до вида х/*у*< /) нецелесообразно, так как это приведет его с точки зре­ния изменения целевой функции к еще большему ухудшению.

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

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

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

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

1 2 3 4 Л,.

1 35 38 40 47

2 18 18 21 | 0 |

3 10 11 13 12

5 15 22 18 24

6 20 18 19 22
7 (фикт.) 0 0 00

В_] 2100 1700 I 600 || 550 [

550 1000 450 600 800 1550

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

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

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

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

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

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

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

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

99. Потенциалы и оценки для опорного решения задачи 15.6

ных переменных) изменится. Соответственно изменятся потен­циалы и оценки незанятых клеток (ср. табл. 99 и 100). Именно это обстоятельство делает преобразование решения при х_{т! п} = 0 необходимым шагом алгоритма потенциалов. Только после этого шага и проверки нового решения можно установить, достигнут оптимум или необходимо продолжить поиск. На практике часто оказывается, что после указанной приостановки изменения зна-

100. Оптимальная транспортная таблица задачи 15.6

чений целевой функции опять возобновляется «нормальная» ите­рационная процедура — целевая функция снова начинает возрас­тать (в задачах на максимум).

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