Критерий оптимальности решения:
Если в целевой функции, выраженной через неосновные переменные, нет положительных коэффициентов, то найденное решение оптимально и расчеты заканчиваются.
В противном случае целевую функцию можно увеличить за счет перевода любой неосновной переменной, входящей в целевую функцию с положительным коэффициентом, в состав основных переменных.
Для этого:
а) основные переменные выражаем через неосновные;
б) положив неосновные переменные равными нулю, находим базисное решение и проверяем его на допустимость (все основные переменные должны быть неотрицательными);
в) выражаем целевую функцию через неосновные переменные и проверяем базисное решение на оптимальность. Если критерий оптимальности не выполняется, то переводим любою неосновную переменную, входящую в целевую функцию с положительным коэффициентом, в состав основных переменных. При этом одна из основных переменных переводится в состав неосновных.
Для сохранения неотрицательности всех переменных задачи должно выполняться ограничение на максимум переменной, переводимой в состав основных:
. (4)
Уравнение, где выполняется условие (4), называется разрешающим и определяет основную переменную, которую надо перевести в неосновные.
г) Определяем новый состав основных и неосновных переменных.
Затем повторяются пункты а, б, в и г 2-го этапа при новых основных переменных до тех пор, пока не выполнится условие оптимальности решения.
Пример 2. Использование симплекс-метода рассмотрим на примере решения задачи об оптимальном плане мебельного цеха.
Решение
Приведем ЗЛП к каноническому виду: обратим систему ограничений – неравенств в систему равенств, вводя в каждое неравенство соответствующую неотрицательную переменную:
Все дополнительные переменные введены со знаком «+», т.к. рассматриваемые неравенства имеют знак «≤».
1-й этап. В соответствии с вышеизложенным правилом нахождения исходного допустимого базисного решения разобьем переменные на две группы - основные и неосновные:
основные переменные – х3, х4, х5;
неосновные переменные – х1, х2.
2-й этап. Последовательно повторяем пункты а, б, в и г 2-го этапа, пока не получим оптимальное решение.
Шаг 1
а) Выражаем основные переменные через неосновные:
б) Положив неосновные переменные равными нулю, получим первое базисное решение:
Х1=(0;0;8;20;5),
которое оказалось допустимым, т.к. все его координаты положительны.
в) Выражаем целевую функцию через неосновные переменные и проверяем базисное решение на оптимальность:
F1 = x1 + 2x2.
Т.к. критерий оптимальности не выполняется, то переводим любою неосновную переменную, например, x2, входящую в целевую функцию с положительным коэффициентом, в состав основных переменных (переходим к новой угловой точке многоугольника решений). При этом одна из основных переменных переводится в состав неосновных.
Чтобы новое базисное решение, с одной стороны, по крайней мере, не ухудшало значение целевой функции, а с другой – было бы допустимым, необходимо определить:
· максимум переменной х2, вошедшей в новый состав основных переменных;
· какая переменная из «бывших» основных должна перейти в состав неосновных переменных при переходе от старого базисного решения к новому.
Для определения максимум переменной х2, при котором каждая из «старых» основных переменных остается неотрицательной, должны выполняться неравенства:
Каждое из неравенств этой системы определяет возможные границы изменения переменной х2. В частности, из последнего неравенства системы следует, что переводимая переменная может возрастать неограниченно. Очевидно, допустимость нового базисного решения будет обеспечена, если будут выполнены все ограничения системы:
х2 = min{8;5;∞} = 5.
При х2 = 5 переменная х4 обращается в нуль и переходит в состав неосновных. Второе уравнение, где достигается наибольшее возможное значение переменной х2, называется разрешающим.
г) Определяем новый состав основных и неосновных переменных:
основные переменные – х2, х3, х5;
неосновные переменные – х1, х4.
Далее переходим к шагу 2.
Шаг 2
а) Выражаем основные переменные через неосновные, воспользовавшись соотношением из разрешеющего уравнения:
б) Положив неосновные переменные равными нулю, получим второе базисное решение:
Х2=(0;5;3;0;5).
Х2 допустимо, т.к. все его координаты положительны.
в) Выражаем целевую функцию через неосновные переменные и проверяем базисное решение на оптимальность:
F2 = 10 + 1/2x1 -1/2x4.
Критерий оптимальности не выполняется, переходим к следующему базисному решению, переведя переменную х1 в состав основных. Для этого определим допустимое значение x1 и разрешающее уравнение:
х1 = min{20;4;5} =4.
При х1 = 4 переменная х3 обращается в нуль и переходит в состав неосновных. Второе уравнение, где достигается наибольшее возможное значение переменной х1, будет разрешающим.
г) Определяем новый состав основных и неосновных переменных:
основные переменные – х1, х2, х5;
неосновные переменные – х3, х4.
Далее переходим к шагу 3.
Шаг 3
а) Выражаем основные переменные через неосновные, воспользовавшись соотношением из разрешеющего уравнения:
б) Положив неосновные переменные равными нулю, получим третье базисное решение:
Х3=(4;4;0;0;1).
Х3 допустимо, т.к. все его координаты положительны.
в) Выражаем целевую функцию через неосновные переменные и проверяем базисное решение на оптимальность:
F3 = 12 – 2/3x3 -1/3x4.
Критерий оптимальности выполняется, найденное решение Х3=(4;4;0;0;1) оптимально, при этом целевая функция F3 = 12.
Заметим, что значение дополнительной переменной х5=1 в оптимальном решении означает: при оптимальном плане третий ресурс Р3 расходуется неполностью, его остаток равен х5=1.
Замечание 1. Если критерий оптимальности выполнен, а в выражении целевой функции отсутствует какая-либо неосновная переменная, то задача имеет неединственное оптимальное решение.
Замечание 2. Если на каком-либо шаге во всех уравнениях системы получаются бесконечные оценочные отношения переменной, которая переводится в основные, то задача не имеет конечного оптимума.
Таким образом, если система ограничений непротиворечива, то выполнение конечного числа последовательных шагов симплекс – метода либо приводит к нахождению оптимального решения задачи, которое может быть неединственным, либо к установлению факта отсутствия конечного оптимума целевой функции.