Правило выявления неограниченности решения следующее. Если на какой-либо симплекс-итерации коэффициенты в ограничениях для какой-нибудь небазисной переменной будут неположительными, значит, пространство решений не ограничено в направлении возрастания этой переменной. Кроме того, если коэффициент этой переменной в z-строке отрицателен, когда рассматривается задача максимизации, или положителен в задаче минимизации, целевая функция также не ограничена.

УПРАЖНЕНИЯ 3.5.3

1. В задаче из примера 3.5.3 с помощью программы TORA покажите, что применение симплекс-метода, когда согласно условию оптимальности вычисления начинаются с переменной л:, в качестве вводимой, обязательно приведет к неограниченному решению.

2. Дана следующая задача ЛП.

Максимизировать z = 20л:, + 10x2 + х3 при выполнении условий

Зх, - Зх, + 5*3 < 50, лс, + х3< 10, хх-х2 + 4х3 < 20, х х2, х3>0.

a) Рассмотрев ограничения, определите направление (по оси х х2 илих3), в котором пространство допустимых решений не ограничено.

b) Без дополнительных вычислений сделайте заключение относительно оптимального значения целевой функции.

3. В некоторых плохо построенных моделях ЛП пространство допустимых решений может быть неограниченным даже тогда, когда задача имеет конечное (ограниченное) оптимальное решение. Такое может случиться, если при построении ограничений допущены ошибки. В больших задачах иногда трудно визуально определить, является ли пространство допустимых решений ограниченным. Разработайте процедуру определения неограниченности про-

странства решений.

3.5.4. Отсутствие допустимых решений

Если ограничения задачи ЛП несовместны (т.е. они не могут выполняться одновременно), то задача не имеет допустимых решений. Такая ситуация не может возникнуть, если все неравенства, составляющие систему ограничений, имеют тип < с неотрицательными правыми частями, так как в этом случае дополнительные переменные могут составить допустимое решение. Для других типов ограничений используются искусственные переменные. И хотя в оптимальном решении все искусственные переменные в силу штрафов равны нулю, такой исход возможен только тогда, когда задача имеет непустое пространство допустимых решений. В противном случае в оптимальном решении будет присутствовать хотя бы одна положительная искусственная переменная.

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

Пример 3.5.4. Отсутствие допустимых решений

Рассмотрим следующую задачу.

Максимизировать z = За-, + 2а2

при выполнении условий

2а, + а2<2, За, + 4х3> 12, а а2>0.

Результат применения симплекс-метода представлен в следующей таблице.

Данные из этой таблицы показывают, что в точке оптимума искусственная переменная R имеет положительное значение (= 4), что свидетельствует об отсутствии допустимого решения. На рис. 3.13 графически представлена ситуация данной задачи. Алгоритм симплекс-метода, допуская положительные значения искусственной переменной, по существу, превращает неравенство За, + 4х3>12 в За, + 4а3 < 12. (Объясните, почему так происходит.) В результате получаем то, что можно назвать псевдооптимальным решением.

Рис. 3.13. Отсутствие допустимых решений в примере 3.5.4

Литература

УПРАЖНЕНИЯ 3.5.4

1. Компания производит изделия трех типов Tl, Т2 и ТЗ. На их изготовление расходуется материал Ml и М2 согласно данным следующей таблицы.

Ежедневно можно использовать не более 1000 единиц материала Ml и 1200 единиц материала М2. Отдел маркетинга настаивает, чтобы суммарное ежедневное производство изделий составляло не менее 500 единиц. Может ли производство удовлетворить это требование? Если ответ отрицательный, помогите компании составить наиболее выгодную структуру производства изделий. 2. Дана следующая задача ЛП.

Максимизировать z = Зхг + 2х2 + Зх3

при ограничениях

2хх + х2 + х3<2, Зх, + 4х2 + 2х3 > 8, xv х2, х3>0.

Используя М-метод в программе TORA, покажите, что оптимальное решение этой задачи содержит искусственную базисную переменную, значение этой переменной равно нулю. Имеет ли задача допустимое оптимальное решение?

ЛИТЕРАТУРА

1. Bazaraa М., Jarvis J., Sherali М. Linear Programming and Network Flows, 2nd ed., Wiley, New York, 1990.

2. Dantzig G. Linear Programming and Extensions, Princeton University Press, Princeton, N.J., 1963. (Русский перевод: Данциг Дж. Линейное программирование, его применение и обобщение. - М.: Прогресс, 1966.)

3. Dantzig G., Thapa М. Linear Programming 1: Introdution, Springer, New York, 1997.

4. Nering E., Tucker A. Linear Programming and Related Problems, Academic Press, Boston, 1992.

5. Schrage L. Optimization Modeling with LINGO, LINGO Systems, Inc., Chicago, 1999.

6. Taha H. Linear Programming, Chapter II-1 in Handbook of Operations Research, J. Moder and S. Elmaghraby (eds.), Van Nostrand Reinhold, New York, 1978. (Русский перевод: Исследование операций: в 2-х томах. Под ред. Дж. Моудера, С. Элмаграби. - М.: Мир, 1981.)