Решение задач линейного программирования
Лекция 4
Рассмотрим симплексный метод на примере следующей задачи:
;
,
; (6)
;
;
, 
Решение. С помощью дополнительных неотрицательных переменных перейдем к системе уравнений вместо системы неравенств. Учитывая, что все неравенства имеют знак “ 
”. Дополнительные переменные входят со знаком плюс. Исходная система ограничений после указанных преобразований имеет следующий вид:
,
; (7)
;
;
Для нахождения первоначального базисного решения разобьем переменные на две группы: основные (базисные) и неосновные (небазисные). Легко видеть, что определитель 
при дополнительных переменных 
имеет следующий вид: 
и, следовательно, отличен от нуля. Исходя из этого переменные можно взять в качестве основных переменных на первом шаге решения задачи. При выборе основных переменных на первом шаге не обязательно составлять определитель и проверять равно ли нулю его значение. Можно воспользоваться следующим правилом.
В качестве основных переменных на первом шаге следует выбрать (если это возможно) такие 
переменных, каждая из которых входит только в одно из уравнений системы ограничений. В рассматриваемой ситуации дополнительные переменные удовлетворяют этому правилу.
Шаг 1. Основные переменные . Неосновные переменные 
. Выразим основные переменные через неосновные переменные:
;
; (8)
;
.
Положим неосновные переменные равными нулю, т.е. 
, получим базисное решение 
, которое является допустимым. Учитывая, что целевая функция, выраженная через неосновные переменные, имеет вид
,
легко понять, что ее значения при равны нулю и может быть увеличено за счет увеличения любой их неосновных переменных . Это можно сделать, если перейти к такому новому допустимому базисному решению, в котором эта переменная будет основной, т.е. будет принимать не нулевое, а положительное значение. При таком переходе одна из основных переменных перейдет в неосновные, а геометрически произойдет переход к соседней вершине многогранника, где значение целевой функции лучше.
|
|
В данном примере, учитывая, что в целевой функции коэффициенты при 
и 
положительны, в основные переменные можно переводить и и . Для определенности в основные переменные переведем ту переменную, коэффициент которой в целевой функции больше. В данном случае такой переменной является .
Поскольку необходимо сохранять допустимость решений, т.е. все переменные должны оставаться неотрицательными и, следовательно, необходимо выполнение следующих неравенств (при этом 
как неосновная переменная)
;
;
; (разрешающее уравнение)
.
Каждое уравнение системы (8), кроме последнего, определяет оценочное отношение – границу роста переменной , сохраняющую неотрицательность соответствующей переменной.
Очевидно, что сохранение неотрицательности возможно, если не нарушена ни одна из границ. Следовательно, в рассматриваемом случае
.
При 
переменная 
обращается в нуль и переходит в неосновные переменные. Уравнение, где достигается наибольшее возможное значение переменной, переводимой в основные (т.е. где оценка минимальна), называется разрешающим. В данном случае ‑ это третье уравнение.
Шаг 2. Основные переменные 
. Неосновные переменные 
.
На этом шаге из уравнений (8) выразим новые основные переменные, начиная с разрешающего уравнения (оно используется при выражении записи для )
|
|
;
;
;
.
Преобразуя систему, получим:
;
; (9)
;
.
Второе базисное решение 
является допустимым.
Выразим значение целевой функции, получим:
.
Далее, как легко видеть, значение 
не является максимальным, поскольку оно может быть улучшено за счет переменной 
, входящей в выражение для целевой функции с положительным коэффициентом. Как и ранее предположив, что правые части уравнений (9) неотрицательны (при этом 
как неосновная переменная):
;
;
;
.
получим, что наибольшее значение определяется из выражения
.
Второе уравнение является разрешающим, переменная 
переходит в неосновные.
Шаг 3. Основные переменные 
. Неосновные переменные 
.
Повторяя процедуру шага 2, выражаем новые основные переменные через неосновные, начиная с разрешающего уравнения. Проведя необходимые преобразования, получим
;
; (10)
;
.
Базисное решение 
соответствует вершине, у которой 
; . Выражаем линейную функцию через неосновные переменные:
;
.
Третье допустимое базисное решение не является оптимальным, так как при неосновной переменной 
в выражении для целевой функции через неосновные переменные содержится положительный коэффициент. Переводим в основную переменную. При определении наибольшего возможного значения для получаем, рассмотрев все четыре уравнения системы (10) при 
‑ любое;
;
;
.
.
Третье уравнение является разрешающим и переменная 
переходит в неосновные.
Шаг 4. Основные переменные 
. Неосновные переменные 
.
|
|
После преобразований получим
;
;
; (11)
.
Базисное решение 
.
Целевая функция, выраженная через неосновные переменные, имеет вид
.
Это выражение не содержит положительных коэффициентов при неосновных переменных, следовательно, улучшить решение нельзя и поэтому значение целевой функции 
максимальное.
На основе изучения рассмотренного примера критерий оптимальности решения при отыскании максимума целевой функции может быть сформулировано так: если в выражении целевой функции через неосновные переменные отсутствуют положительные коэффициенты при неосновных переменных, то решение оптимальною.
При решении задачи определения минимума целевой функции можно использовать один из следующих путей:
‑ если необходимо отыскать минимум 
, то решается задача максимизации функции 
, и это решение принимается за решение исходной задачи;
‑ на каждом шаге симплексного метода уменьшать целевую функцию за счет той неосновной переменной, которая входит в выражение целевой функции с отрицательным коэффициентом.
Рассмотрим симплексный метод решения следующей задачи на минимум.
.
; (12)
;
, 
.
Сведем данную задачу к каноническому виду, для чего введем положительные дополнительные переменные с отрицательным знаком, т.к. неравенства имеют вид 
.
Получим систему уравнений
;
.
Шаг 1. Выберем в качестве основных переменных переменные 
. Неосновные переменные 
.
Выразим основные переменные через неосновные переменные:
;
.
Первое базисное решение получим, приравняв нулю все неосновные переменные: 
. Учитывая, что все координаты неотрицательны, это решение допустимо Выразим линейную целевую функцию через неосновные переменные:
Значение 
не является оптимальным, так как функцию можно уменьшить за счет перевода в основные переменные любую из переменных 
, имеющих в выражении для отрицательные коэффициенты. Так как имеет больший по абсолютному значению коэффициент, то переводим в основные именно эту переменную.
Для нее наибольшее возможное значение определяется из соотношения 
. То есть первое уравнение становится разрешающим.
Следовательно, 
становится неосновной переменной, 
.
Шаг 2. Основные переменные 
. Неосновные переменные 
.