Рассмотрим каноническую ЗЛП
, (5.1)
(5.2)
где . Будем предполагать, что и система уравнений (5.2) совместна и имеет бесконечное множество решений.
Для начала работы по симплекс-методу требуется, чтобы система ограничений (5.2) была приведена к допустимому виду. Это означает, что какие-то переменных выражены через остальные переменных, причем свободные члены в полученной системе неотрицательны. Предположим для определенности, что система ограничений имеет вид
(5.3)
где (базисные переменные) выражены через (свободные переменные), причем .
Так как переменные выражены через , то соответствующим образом необходимо изменить целевую функцию (5.1). Подставляя в (5.1) вместо выражения, определяемые правыми частями системы (5.3), получим следующий вид целевой функции:
(5.4)
(целевая функция зависит от свободных переменных ).
Определение 5.1. ЗЛП (5.3) – (5.4) называется задачей линейного программирования допустимого вида.
Обозначим через множество базисных переменных, через множество свободных переменных. Построим начальное опорное (базисное) решение системы ЗЛП (5.3) – (5.4), положив значения свободных переменных равными нулю:
. (5.5)
Заметим, что значение целевой функции на базисном решении (5.5):
.
Возникает вопрос: можно ли уменьшить значение целевой функции? При решении ЗЛП симплекс-методом возникают три случая.
Случай 1. Предположим, что в целевой функции (5.4) ЗЛП допустимого вида все коэффициенты при свободных переменных неотрицательны. Заметим, что при любом допустимом решении
,
являющимся решением системы (5.3):
причем среди чисел есть хотя бы одно, отличное от нуля, получим, что значение целевой функции (5.4) не меньше, чем значение целевой функции на базисном решении (5.5):
.
Таким образом, наименьшее значение целевой функции (5.4) достигается на базисном решении (5.5) и равно . Получаем теорему.
Теорема 5.1 (случай оптимальности базисного решения ЗЛП). Если в целевой функции (5.4) ЗЛП допустимого вида все коэффициенты при свободных переменных неотрицательны, то базисное решение (5.5) является оптимальным, .
Пример 5.1. Найти оптимальное решениеЗЛП допустимого вида
, .
Решение. В данном случае , , базисное решение . В целевой функции все коэффициенты при свободных переменных положительны (). Согласно теореме 5.1 базисное решение , полученное при нулевых значениях свободных переменных (), является оптимальным, причем . Итак,
, .
Случай 2. Предположим, что в целевой функции (5.4) ЗЛП допустимого вида среди коэффициентов при свободных переменных существует отрицательный коэффициент, а в системе ограничений (5.3) все коэффициенты при этой же свободной переменной неотрицательны. Пусть для определенности при свободной переменной в целевой функции коэффициент , а в системе ограничений (5.3):
.
Построим допустимое решение , ,
(5.6)
На этом допустимом решении значение целевой функции имеет вид
.
Заметим, что с неограниченным увеличением значения свободной переменной () целевая функция неограниченно уменьшается (). В данном случае задача не имеет оптимального решения (целевая функция не имеет наименьшего значения).
Теорема 5.2 (случай отсутствия оптимального решения ЗЛП). Если в целевой функции (5.4) ЗЛП допустимого вида среди коэффициентов при свободных переменных существует отрицательный коэффициент, а в системе ограничений (5.3) все коэффициенты при этой свободной переменной неотрицательны, то ЗЛП не имеет оптимального решения в силу неограниченности целевой функции этой задачи.
Пример 5.2. Доказать, чтоЗЛП не имеет оптимального решения
, ,
Решение. В данном случае , , базисное решение . В целевой функции при свободной переменной отрицательный коэффициент (), а в системе ограничений при этой же переменной все неотрицательные коэффициенты (1>0, 3>0). Согласно теореме 5.2 ЗЛП не имеет оптимального решения.
Случай 3. Пусть в целевой функции (5.4) ЗЛП допустимого вида среди коэффициентов при свободных переменных существует отрицательный коэффициент (пусть для определенности ) и в системе ограничений (5.3) при этой же свободной переменной также существует по крайней мере один отрицательный коэффициент.
Возникают два случая.
Случай 3.1. Пусть в системе ограничений (5.3) среди коэффициентов только один отрицательный. Предположим для определенности . Построим допустимое решение
,
где и компоненты удовлетворяют системе (5.6).
На этом допустимом решении значение целевой функции равно
.
Уменьшение целевой функции можно достичь за счет увеличения значения свободной переменной . Так как , то при увеличении значения свободной переменной значения базисных переменных увеличиваются. Заметим, что увеличение значения свободной переменной приводит к уменьшению значения базисной переменной (), и при
базисная переменная обратится в нуль:
.
Обращение в нуль базисной переменной при означает, что необходимо изменить базис переменных. А именно, переменную вывести из базиса переменных, а переменную ввести в базис (обозначаем это так ). При этом число будем называть разрешающим элементом.
Случай 3.2. Пусть в системе ограничений (5.3) среди коэффициентов существуют по крайней мере два отрицательных. Пусть для определенности (при этом ).
Построим допустимое решение , где и компоненты определяются из системы
На этом допустимом решении значение целевой функции равно
.
Так как , то при увеличении значения свободной переменной значения базисных переменных увеличиваются. Заметим, что увеличение значения свободной переменной приводит к уменьшению значений базисных переменных (так как ). Составим вспомогательное число
.
При увеличении значения свободной переменной от 0 до обязательно какая-то из базисных переменных обратится в нуль. Предположим для определенности, что . Тогда при значении базисная переменная обратится в нуль. Как и в случае 3.1, это означает, что происходит смена базиса переменных: выходит из базиса переменных, а входит в базис (). При этом, как и в случае 3.1, число называют разрешающим элементом.
Обобщая сказанное в случае 3, необходимо переменную вывести из базиса переменных, а ввести в базис переменных. Для этого необходимо из системы ограничений (5.3) выразить переменную через переменную . Получим новую систему ограничений
(5.7)
где обязательно . При этом соответствующим образом изменится и целевая функция
, (5.8)
причем .
Получили новую ЗЛП допустимого вида с системой ограничений (5.7) и целевой функцией (5.8). В этой задаче , . Составим базисное решение, положив нулевыми значения свободных переменных:
.
Заметим, что значение целевой функции на базисном решении
,
то есть в результате смены базиса переменных значение целевой функции уменьшилось на значение .