Двойственный симплекс-метод Приведем к каноническому виду, введя дополнительные

х4, х5  0.

этой ЗЛП. Частным решением будет вектор х0 =

(0; 0; 21; -3; -2).

Здесь

.

Ах  b.
Коэффициенты целевой функции сj  0,

и при этом C(х)  min.
В ЗЛП вводится существенное или активное ограничение, т.е. такое ограничение, которое изменяет оптимальный план в первоначально заданном множестве допустимых планов.

– псевдоплан, в котором
, тогда х* – оптимальный план.
Доказательство.

Так как х* псевдоплан, то ему соответствует некоторый базис. Поскольку по условию теоремы

, то х* – БДП.

Из определения псевдоплана следует, что

При этом попадаем в условия теоремы «Признак оптимальности БДП». Таким образом, х* – оптимальный план.

.

координаты x0k не определены по знаку. При этом в ЗЛП

(2) все оценки

.

базиса.

Из базиса выводится вектор Ar , у которого номер r определяется из соотношения:

базис.

Номер вектора s, вводимого в базис, выбирается из отношений двойственных оценок к отрицательным элементам r-ой строки симплекс-таблицы:

Ведущим элементом будет

.

симплекс-таблицы

по формулам:
(4)

 (6) обеспечивает:
1) переход к новому псевдоплану, т. е.

гарантируется

а)

б) новый псевдоплан хнов есть базисный план.
2) Значение целевой функции на новом псевдоплане не больше, чем значение целевой функции на предыдущем псевдоплане, т.е. С(хнов)  С(х0).

каноническому виду
Базисный план х0 = (0; 0; 0; -16;

-4) есть псевдоплан

0; 8; 0; 44)
Значение целевой функции C1(х*) =

-8
Значение целевой функции исходной задачи C(х*) = 8.

симплекс-методе.
Пусть в ЗЛП (1) имеется псевдоплан х* = (x1*, …,

xr*, …, xn*) такой, что r-я координата меньше нуля, а все элементы r-й строки симплексной таблицы неотрицательны, тогда ЗЛП неразрешима.

симплексную таблицу:

разрешима. Область допустимых планов есть пустое множество (D = ).

Это легко можно проиллюстрировать графически.

имеет оптимальный план
Известен носитель оптимального плана
Последней итерации симплексной

таблицы соответствует система уравнений

(7)

Координаты оптимального плана х*

говорят, существенное ограничение вида:
(8)
Введем в неравенство (8) дополнительную переменную
x

n+1  0.

(9)

(10)

в уравнение (10). Получим уравнение (11).


(11)

правую часть уравнения (11):
(12)
Обозначим
переменная xn+1 = xm+1,0. Запишем (12)

в (m+1) строку симплекс-таблицы. Появляется новый единичный базисный вектор An+1.

, тогда дополнительная

За счет дополнительного ограничения (12) получили новую ЗЛП, в которой имеется псевдоплан

прежним двойственным оценкам, а оценка n+1 = 0, как оценка

базисного вектора An+1. Кроме того, xm+1,0  0,
так как

в силу предположения, что

дополнительное ограничение активное.

Имея псевдоплан, можно продолжать решение ЗЛП двойственным симплекс-методом.

постоянного заказчика изделие А основной номенклатуры и изделие В второстепенной

номенклатуры. Издержки на производство одного изделия А равны 5 ден. ед., а изделия В – 1 ден. ед.
Заказчик требует как минимум на четыре единицы больше изделия А , чем изделия В. Производство одного изделия А дает единицу токсичных отходов, а изделия В – две единицы отходов. Общее количество токсичных отходов не должно превышать 12 единиц. Необходимо так организовать производство, чтобы минимизировать издержки.

составят С(х*) = 20 ден. ед.
Теперь обстоятельства изменились. Заказчик потребовал

изготовить не менее 6 штук изделий А. Появляется новое активное ограничение х1  6 (обозначим соответствующую прямую l3).

Вводим дополнительную переменную х5  0

(6; 0; 6; 2; 0), С(х1*) = 30 ден.

ед. Геометрическая иллюстрация решения данной задачи показана на рис.

Выразим х1 из второго уравнения и подставим
в третье уравнение. Тогда