Исходные данные к задаче 16.2

Хозяйство

Стоимость доставки свеклы на заводы, руб/т

Объемы производства

свеклы в хозяйствах, т

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

Представляет практический интерес поиск альтернативных оптимальных решений, то есть решений, отличающихся от при­веденного в таблице 118 значениями ху, но дающих то же (в дан­ном случае минимальное) значение целевой функции. Такие ре­шения могут понадобиться, например, при появлении новых, ра­нее не учтенных ограничений на объемы перевозок ресурса по отдельным маршрутам. Формальным признаком их наличия яв­ляется появление в матрице оптимального плана свободных кле­ток с оценками а, у= 0. В рассматриваемом примере таких клеток две: (1, 3) и (3, 2). Если построить замкнутый цикл (по правилам, рассмотренным в п. 15.2) и переместить ресурс из какой-либо за­нятой клетки в свободную клетку с оценкой, равной 0, мы также получим оптимальное решение.

Рассмотрим, например, клетку (1, 3). Если построить цикл с углами в клетках (1, 2), (1, 3), (2, 2), (2, 3) и переместить ресурс, равный 1080, то получим новое оптимальное решение, в котором клетка (1, 3) будет занята ресурсом х₁₃ = 1080, клетка (2, 3) станет свободной, а ресурсы в клетках (1, 2) и (2, 2) соответственно уменьшатся и увеличатся на 1080. При этом поскольку оценка свободной клетки равна 0, то в соответствии с формулой (15.7) изменение А2 целевой функции также равно 0, что и подтверж­дает оптимальность нового решения.

Отметим, что в данном случае по циклу можно переместить ресурс и меньший 1080. Полученное решение также будет опти­мальным, хотя число занятых клеток превысит т + п — 1 (то есть оно не будет базисным).

Таким образом, наличие даже одной свободной клетки с нуле­вой оценкой обеспечивает получение бесконечного числа опти­мальных решений (в рассмотренном примере за счет варьирова­ния перемещаемого ресурса в диапазоне [0, 1080]). Поскольку транспортные задачи представляют собой частный случай общих задач линейного программирования, можно сказать, что здесь реализуется ситуация, когда поверхность уровня целевой функ­ции параллельна одной из граней симплекса, сформированного системой ограничений транспортной задачи. Естественно, что наличие другой клетки с нулевой оценкой — клетки (3, 2) — обес­печивает получение еще одного множества оптимальных реше­ний задачи. Более того, можно показать, что допустимо одновре­менное преобразование полученного оптимального решения с использованием циклов, соответствующих всем свободным клет­кам с нулевыми оценками (при соблюдении требования неотри­цательности переменных).