Методы оптимальных решений

Задача 1.6. 

В условии каждой задачи дается функция цели ЗЛП и система линейных ограничений, определяющих множество допустимых планов. Указано, является ли она задачей на максимум или минимум. Построить ее каноническую форму.

[pic 1]

[pic 2]

Решение. Каноническая форма задачи характеризуется следующими тремя признаками: 1) однородная система ограничений в виде системы уравнений; 2) однородные условия неотрицательности, распространяющиеся на все переменные, участвующие в задаче, 3) максимизация линейной функции. В данной задаче нарушены все три признака.

Начнем с преобразования смешанной системы ограничений в систему уравнений. Это преобразование выполняется путем введения неотрицательных "балансовых" переменных (x7) в левые части неравенств со знаками "плюс" или "минус" в зависимости от знака неравенства. В результате система условий запишется в следующем виде:

[pic 3]

Перейдем к преобразованию условий неотрицательности. Неравенствами [pic 4] не охвачены переменные x1, x2, x4, x6, которые будем называть "произвольными". Для приведения задачи к однородным условиям неотрицательности можно воспользоваться специальным приемом. Этот прием приводит к увеличению числа переменных в задаче. Суть его заключается в том, что вместо каждой произвольной переменной x2, x4, x5, x6, вводятся две неотрицательные переменные из равенств

[pic 5],

где [pic 6]. В результате получаем задачу, содержащую не 8, а 12 переменных.

Мы пришли к следующей задаче линейного программирования с ограничениями в виде системы уравнений и однородными условиями неотрицательности: минимизировать линейную функцию

[pic 7]при условиях

[pic 8]Наконец, переход к задаче максимизации линейной функции осуществляется путем введения новой функции [pic 9] из равенства

[pic 10].

Задача 2.6

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

Решение.

[pic 11]

[pic 12]

[pic 13]

Следуя общим правила, выберем в качестве базисных переменных x3, x4, x5. Тогда [pic 14], [pic 15] — свободные переменные. Положим свободные переменные [pic 16] x1=0, x2=0, базисное решение [pic 17](0; 0; 1; 1; 1). Данное базисное решение является допустимым, так как все базисные переменные положительны. Исключим базисные переменные в выражении для целевой функции, получим: [pic 18]

Составим симплекс-таблицу, соответствующую угловой точке [pic 19]

Среди элементов нижней строки таблицы есть отрицательные.  Значит, [pic 20]не является решением задачи.