Альтернативные решения с отклонением целевой функции от эк­стремума.

Не всегда имеется возможность выполнить дополнительные условия, сохранив оптимальность решения. Пусть, например, за­дано дополнительное условие 2500 < *бз ^ 3200. Клетка (6, 3) в таб-

лице 118 уже занята. Если мы увеличим в ней ресурс в соответ­ствии с дополнительным условием (то есть увеличим *бз)> то по­лучим уже неоптимальное решение. Для этого строим цикл с уг­лами в клетках (6, 3), (6, 4), (2, 4) и (2, 3), помечаем их последова­тельно знаками «+» и «—», начиная с клетки (6, 3). Максимально возможный перемещаемый ресурс в построенном цикле ^хтт⁼ Ю80. Следует ли переместить ресурс, равный именно 1080 (дополнительное условие при этом будет выполнено)? Ответ бу­дет отрицательным. Чем больший ресурс мы переместим, тем сильнее нарушим оптимальность плана (тем больше возрастет целевая функция по сравнению с минимумом). Изменение целе­вой функции легко подсчитать:

А^ = Ах(ЕС, -Хф, ₍₁₆₂₄₎

где Ах— перемещаемый ресурс; 2С„, ЕС., —суммы значений коэффициентов

_ (+) (-),

Су, стоящих в клетках, помеченных знаками «+» и «—» соответственно.

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

^г' = Зпт + ^Л^= ^{125 2}99 + 380 (33, 0 - 15, 1) = = 125 299 + 6802 = 132 101 руб.

При этом в клетках цикла ресурсы изменятся следующим об­разом:

х₂₃: 1080 -> 700; х₂₄: 0 -> 380; х₆₃: 2120 -» 2500; х₆₄: 2000 -» 1620.

Заметим, что ранее свободная клетка (2, 4) стала занятой и об­щее число занятых клеток превысило (т + п — 1). Полученное ре­шение неоптимально, но (!) оно ближе к оптимальному, чем если бы мы, стараясь сохранить число занятых клеток равным (т +п — 1), перемещали ресурс Дх= 1080.

Действуя по аналогичной схеме, можно не только увеличи вать, но и уменьшать ресурс в занятой клетке (например, для учета ограничений типа Ху< Л) или занимать ранее свободную клетку, получая новые неоптимальные, но полезные на практике решения.

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

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

Рассмотрим более подробно случай, когда необходимость корректировки решения вызвана дополнительным условием типа х, -*, *< Д где /3 —заданная константа. Как уже отмечалось, такие условия не учитываются при постановке задачи (см. п. 15.3).

Пусть, например, в полученном решении (см. табл. 118) не­обходимо учесть условие х₃₁ < 100. В принципе в данном случае можно воспользоваться описанной выше процедурой. Однако в связи с тем что для удовлетворения дополнительного условия из клетки (3, 1) необходимо удалить весьма большой ресурс — 6700, превышающий ресурс в любой другой занятой клетке, преобразовать имеющееся оптимальное решение с помощью одного цикла нельзя. Необходимо построение нескольких цик­лов, что значительно усложняет задачу, особенно в таблицах больших размеров. Кроме того, поскольку допустимое преоб­разование решения с помощью циклов, очевидно, не един­ственное, в любом случае остается открытым вопрос о наилуч­шей корректировке оптимального решения. В связи с этим ре­комендуется следующая универсальная процедура учета до­полнительных условий типа х,»^ < 2), обеспечивающая наи­лучшую корректировку решения (с точки зрения наименьшего отклонения целевой функции от оптимального значения). Она включает следующие шаги:

1) решение задачи без учета дополнительного условия;

2) анализ полученного решения; если выполняется ограниче­ние х, *, * < Б, процедура заканчивается, в противном случае осу­ществляется переход к третьему шагу;

3) замена условия х^* < 1> на условие х, *, * = 2), блокировка
клетки (/*, /), соответствующее изменение величин А_? и Я, * (см.
п. 15.3) и решение новой задачи. Полученное решение и будет
наилучшей корректировкой исходного оптимального плана с
учетом условия х, *у* < Ь.

Очевидно, что нецелесообразно сразу переходить к шагу 3, так как до выполнения первого шага неясно, выгодно ли в клетке (/*, у'*) размещать ресурс, равный 2). Для примера проведем коррек­тировку решения задачи 16.2, представленного в таблице 118, с учетом ограничения х_3[ < 100. Результаты представлены в табли­це 119.

119. Решение задачи 16.2 с учетом ограничения х₃| ^ 100 (2Г= 130 299 руб.)

16.7. АНАЛИЗ ОПТИМАЛЬНЫХ РЕШЕНИЙ НА ОСНОВЕ ЭКОНОМИЧЕСКОЙ ИНТЕРПРЕТАЦИИ ПОТЕНЦИАЛОВ

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

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

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

Отмеченные свойства потенциалов позволяют анализировать и более сложные ситуации, когда относительно небольшие изме­нения объема производства А, и В^ происходят у несвязанных поставщика и потребителя, то есть когда клетка (/, у) свободна. Проиллюстрируем сказанное на конкретном примере (Ларчен-ко Е. Г. Вычислительная техника и экономико-математические методы в землеустройстве. — М: Недра, 1978. — С. 257).

Задача 16.3. Пусть имеются три поставщика и четыре потре­бителя однородного груза. Количество грузов у поставщиков — Л, -(/= 1,..., 3), спрос потребителей —Д(/'= 1,..., 4), стоимость транспортировки груза — Су, руб. за 1 т. Требуется определить та­кой план перевозки грузов, при котором транспортные расходы были бы минимальны.

Оптимальный план приведен в таблице 120. Рассмотрим те­перь такую задачу: если необходимо сократить потребление про­дукции, то в каком конкретно пункте целесообразно это сделать и у какого поставщика необходимо уменьшить запас продукции?

120. Оптимальное решение задачи 16.3

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

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

Аналогично, если необходимо увеличить объем потребления, то целесообразно взять потребителя с наименьшим потенциа­лом, а поставщика — с наибольшим. В рассматриваемом примере это 1-й потребитель и 1-й поставщик. Тогда разность (Ру-а,) бу­дет минимальной и, следовательно, целевая функция возрастет в наименьшей степени. Рассмотренное правило говорит только о том, как следует менять объемы продукции у поставщиков и по­требителей. Однако пока неясно, как должны измениться ресур­сы в занятых клетках, то есть неизвестно, как изменится само оптимальное решение при условии сохранения его структуры (расположения занятых клеток).

Рассмотрим, например, случай увеличения объема продукции на единицу. Как отмечалось, в этом случае целесообразно увели­чить мощности 1-го потребителя и 1-го поставщика. Однако в полученном оптимальном решении они непосредственно между собой не связаны — клетка (1, 1) свободна (см. табл. 120), иначе говоря, маршрут от первого поставщика к первому потребителю не используется. На первый взгляд это парадоксально, но дело в том, что разность (Ру-а,), на основе анализа которой мы выбра­ли поставщика и потребителя, характеризует решение в целом, а не только клетку (1, 1). Значит, нужно так изменить решение, чтобы, во-первых, расположение занятых клеток не изменилось, а во-вторых, чтобы при измененных значениях А_{ и В_х выполня­лись все граничные условия. Проделаем это следующим образом.

Потребитель 1 в оптимальном плане получает груз от постав­щика 3; все остальные поставщики оказываются для него менее выгодными. Увеличив потребление В_{ на единицу, следует при­нять х₃₁ = 15 + 1 = 16. Но поскольку мощность поставщика 3 не менялась, то для сохранения баланса следует уменьшить и объем поставок, которые он делает потребителю 4, то есть положить х₃4 = 6 - 1 = 5. Наконец, чтобы 4-м потребителем было получено требуемое количество груза, необходимо добавить единицу к по­ставкам от 1-го поставщика к 4-му потребителю, то есть поло­жить х₁₄ =1 + 1=2. Таким образом, несмотря на отсутствие пря­мой связи между 1-м поставщиком и 1-м потребителем (клетка (1, 1) свободна), увеличение потребления В_{ произошло именно из-за увеличения запаса А\.

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

пример, увеличить, а затем после увеличения соответствующих величин А, и В; получаем на ЭВМ новое решение задачи. В этом случае польза от анализа потенциалов заключается в том, что мы сразу находим поставщика и потребителя, у которых необходимо увеличить объем продукции. Поиск же «наугад» может потребо­вать очень много итераций.

Обратим еще раз внимание на то, что изменение величин 4 и В_} не изменило структуру оптимального решения, а значит, и не изменило потенциалы. Именно это свойство устойчивости по­тенциалов позволяет использовать их в качестве показателей экономической эффективности. Однако необходимо помнить об относительности такой устойчивости: потенциалы изменятся, если изменения исходных данных потребуют включения в план ранее свободных клеток и исключения ранее занятых. Так, если бы в рассмотренном примере необходимо было увеличить общий объем продукции более чем на 6 единиц (например, на 7), то, действуя по рассмотренной выше схеме, мы при изменении по­ставки х₃4 получили бы х₃4 ⁼ 6 —7 = —1, что, очевидно, недопус­тимо. Таким образом, в рассмотренном примере анализ потен­циалов дает разумный результат только при приращениях про­дукции, меньших или равных 6. Именно в этом смысле мы гово­рили выше о полезности анализа потенциалов при относительно небольших изменениях общего объема продукции.

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

Пример 1. Пусть во 2-м хозяйстве объем производства свеклы увеличился на 1000 т. В каком хозяйстве следует уменьшить ее производство при условии, что общий объем поставок свеклы должен сохраниться и мощности заводов не меняются?

В данном случае А$=А₂ + 1000=4400. Необходимо найти такой

номер /, что 4'=4--1000 и при этом соответствующее изменение значения целевой функции будет минимальным: Д2= (2' — -2)^ тт. Используя формулу (15.8) для расчета целевой функ­ции через потенциалы, получим

А2^, = 1000(-а₂ + а_/).

Следовательно, для минимизации М необходимо выбрать / таким, чтобы значение а, - было наименьшим. Это значит, что объем производства свеклы необходимо уменьшить на 1000 т в 9-м хозяйстве (см. табл. 118).

В таблице 121 представлено оптимальное решение, соответ­ствующее указанному изменению объемов производства свеклы

во 2-м и 9-м хозяйствах. Поскольку расположение занятых кле­ток не изменилось (и соответственно не изменились потенциа­лы), можно сделать вывод о правомерности использования ана­лиза потенциалов для решения данной задачи.

121. Оптимальное решение задачи 16.2 с дополнительным условием (пример 1)*

*Звездочкой помечены значения х«, отличающиеся от аналогичных значений п табл. 118. ^р, = 122 399 руб.

Пример 2. Пусть требуется увеличить общий объем переработ ки свеклы на 300 т. Это разрешается сделать за счет увеличения ее производства только в одном хозяйстве и соответствующего увеличения объема переработки на одном заводе. Какие коп к ретно хозяйство и завод следует выбрать?

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

Д2'=300(р_/-а_; ).

Следовательно, для минимизации Л2Г необходимо выбрать } та­ким, чтобы значение (3, - было наименьшим, а / — таким, чтобы зна­чение ос, - было наибольшим, то есть увеличить на 300 т производ­ство в 6-м хозяйстве и переработку на 1-м заводе (см. табл. 118).

Пример 3. Пусть на 3-м заводе объем переработки свеклы уменьшается на 400 т, но общий объем переработки (и производ­ства) свеклы должен сохраниться. Разрешается увеличить объем переработки свеклы на одном заводе, уменьшить объем произ­водства в одном хозяйстве и увеличить его также в одном хозяй­стве. Какие конкретно хозяйства и завод следует выбрать?

В этом примере, если выбрать у'-й завод (объем переработки увеличивается на 400 т), /_ге хозяйство (объем производства воз­растает на 400 т) и /2" ^е хозяйство (объем производства уменьша­ется на 400 т), то целевая функция по сравнению со значением, соответствующим исходному оптимальному решению, изменит­ся на

Л7= 400(|З_у- рз) + 400(-а, -₁ + а_/? ).

Следовательно, для минимизации Д2 необходимо выбрать ] та­ким, чтобы значение (3, - было наименьшим, /\ — чтобы значение а_{; 1} было наибольшим, /₂ — чтобы значение а_д было наименьшим. В данном случае объем производства свеклы необходимо увели­чить на 400 т в 6-м хозяйстве, уменьшить на 400 т в 9-м хозяйстве и увеличить объем переработки на 400 т на 1-м заводе (см. табл. 118).

Анализ решений, полученных в рассмотренных примерах, подтвердил правомерность использования потенциалов в постав­ленных задачах.

Контрольные вопросы и задания

1. Назовите основные блоки информации, содержащиеся в последней (опти­мальной) симплекс-таблице.

2. Что характеризуют: основные переменные, попавшие в базис последней сим­плекс-таблицы? Не попавшие в базис? Остаточные переменные, попавшие в базис? 11е попавшие в базис? Избыточные переменные, попавшие в базис? Не попавшие в базис?

3. Что характеризуют коэффициенты замещения симплекс-таблицы?

4. Что означает выражение «ввести в оптимальный план небазисную перемен­ную»?

5. Каким образом меняется решение задачи линейного программирования при ииедении в план небазисной переменной? Приведите соответствующие расчетные формулы.

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

7. Какому изменению ресурса соответствует введение в оптимальный план по-пожительного значения остаточной переменной? Отрицательного значения?

8. Какому изменению планового задания соответствует введение в оптималь­ный план положительного значения избыточной переменной? Отрицательного ■ шачения?

9. В каких случаях может оказаться необходимой корректировка оптимального
плана задачи линейного программирования?

10. Перечислите основные действия при введении в оптимальный план неба­зисной основной переменной.

11. Как определить пределы допустимых значений вводимой в оптимальный план небазисной основной переменной?

12. Перечислите основные действия при введении в оптимальный план неба­зисной остаточной переменной.

13. Как следует поступать, если в оптимальный план требуется ввести значение небазисной основной переменной, выходящее за пределы интервала допустимых значений?

14. Как определить пределы допустимых значений вводимой в оптимальный план небазисной остаточной переменной?

15. Укажите основные действия при введении в оптимальный план небазисной избыточной переменной.

16. Как определить пределы допустимых значений вводимой в оптимальный план небазисной избыточной переменной?

17. Что такое двойственные оценки оптимального плана?

18. Дайте экономическую интерпретацию двойственной оценки, соответствую­щей небазисной остаточной переменной; небазисной избыточной переменной; не­базисной основной переменной.

19. Каков смысл термина «скрытые цены»?

20. Как будут меняться элементы индексной строки оптимальной симплекс-таблицы при изменении коэффициента в целевой функции при базисной перемен­ной?

21. Как оценить пределы изменения коэффициента в целевой функции при ба­зисной переменной, если поставлено условие сохранения структуры (состава ба­зисных переменных) оптимального плана?

22. Как будут меняться элементы индексной строки оптимальной симплекс-таблицы при изменении коэффициента в целевой функции при небазисной пере­менной?

23. Как оценить пределы изменения коэффициента в целевой функции при не­базисной переменной, если поставлено условие сохранения структуры (состава ба­зисных переменных) оптимального плана?

24. При каком изменении коэффициента при небазисной переменной в целе­вой функции соответствующая неэффективная отрасль станет эффективной?

25. Назовите основные виды корректировок решения транспортной задачи.

26. Что называется альтернативным оптимальным решением транспортной за­дачи?

27. По каким параметрам оптимальной транспортной таблицы можно судить о наличии альтернативных оптимальных решений?

28. Как с помощью циклов можно найти альтернативные оптимальные реше­ния?

29. В каких случаях может возникнуть необходимость в определении альтерна­тивных неоптимальных решений?

30. Каким образом с помощью циклов можно построить альтернативное не­оптимальное решение для соблюдения ограничения вида х„< И!

31. Опишите универсальный способ наилучшего преобразования оптимального решения при введении дополнительного ограничения вида ху< й.

32. Приведите формулу для расчета целевой функции транспортной задачи че­рез потенциалы поставщиков и потребителей. Какова экономическая интерпрета­ция потенциалов, согласующаяся с этой формулой?

33. Если /-й поставщик и у'-й потребитель связаны, то есть в оптимальной транспортной таблице клетка (/, ]) занята, как изменится оптимальное решение и значение целевой функции в случае одновременного увеличения (уменьшения) ве­личин А₍ и В₁ на единицу ресурса?

34. Какие виды задач по корректировке оптимального решения можно решать, используя экономическую интерпретацию потенциалов, если необходимы измене­ния несвязанных величин Л, - и В/!

Глава 17

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

17.1. ИСПОЛЬЗОВАНИЕ СОКРАЩЕННЫХ СИМПЛЕКС-ТАБЛИЦ

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

Рассмотрим в качестве примера задачу по оптимальной транс­формации угодий в хозяйстве. Ее постановка, математическая формулировка и методика вычисления коэффициентов рассмот­рены в главе 23.

Задача 17.1. В хозяйстве возникла необходимость определить наиболее целесообразный способ трансформации 592, 8 га паст­бищ и 6, 6 га болот. Учитывая природные особенности и каче­ственные характеристики участков, 54, 8 га пастбища можно трансформировать в пашню, а остальные улучшить; болота могут быть переведены либо в сенокосы, либо в пастбища.

Введем переменные: х_{ — площадь пастбищ, трансформируе­мая в пашню; х₂ — подлежащих улучшению; х₃ — площадь болот, осушаемая гончарным дренажем, переводимая в пастбище; х₄ — осушаемая открытой сетью каналов, переводимая в сенокос. Ис­ходные данные для составления плана трансформации приведе­ны в таблице 122.