Двойственный симплекс-метод

1.

Двойственный симплекс-метод
C ( х) 5 x1 7 x 2 min
4 x1 3 x 2 21
x1 3
x2 2
x1 , x 2 0
Приведем к каноническому виду, введя дополнительные
переменные х3, х4, х5 0.

2.

C1 ( х) 5 x1 7 x2 max
4 x1 3 x2 x3 21
x x 3
1 4
х 2 х5 2
x j 0,
j 1,5
Умножим второе и третье структурное ограничение на (-1)
C1 ( х) 5 x1 7 x 2 max
4 x1 3 x 2 x3 21
x1 x 4 3
x 2 x5 2
x j 0,
j 1,5

3.

Векторы А3, А4, А5 образуют единичный базис этой ЗЛП.
Частным решением будет вектор х0 = (0; 0; 21; -3; -2).
Опр. Решение системы линейных уравнений
x 0 ( x10 , x 20 ,..., x n0 ) , соответствующее базису А ,
называется псевдопланом или почти
допустимым базисным решением (ПДБР), если
все двойственные оценки неотрицательны
( j , j 1, n), а среди координат плана существует,
по крайней мере, одна отрицательная координата
(x0k < 0, k ).
Здесь ik : xik 0,
k 1, l , l m .

4.

Чаще всего псевдоплан появляется в задачах, в которых:
1. Ограничения имеют вид Ах b.
2. Коэффициенты целевой функции сj 0, j 1, n
и при этом C(х) min.
3. В ЗЛП вводится существенное или активное
ограничение, т.е. такое ограничение, которое изменяет
оптимальный план в первоначально заданном
множестве допустимых планов.

5.

Теорема. Признак оптимальности псевдоплана.
Пусть х* = (х*1 ,…, х*n) – псевдоплан, в котором
x *j 0,
j 1, n , тогда х* – оптимальный план.
Доказательство. Так как х* псевдоплан, то ему
соответствует некоторый базис. Поскольку по условию
теоремы x *j 0,
j 1, n , то х* – БДП.
Из определения псевдоплана следует, что j 0,
При
этом
попадаем
в
условия
теоремы
j 1, n.
«Признак
оптимальности БДП». Таким образом, х* – оптимальный
план.

6.

Алгоритм двойственного симплекс-метода
(с, х) max
Aх b
х 0
(1)
Мы имеем систему ограничений вида:
xk akj x j xk 0 , k
(2)
j
В (2) все координаты x0k не определены по знаку. При этом в
ЗЛП (2) все оценки
j 0,
j 1, n
.

7.

Правило 1. Определение номера вектора, выводимого из
базиса.
Из базиса выводится вектор Ar , у которого номер r
определяется из соотношения:
min xk 0 xr 0 0 или
k
max xk 0 xr 0
xk 0 0

8.

Правило 2. Определение номера вектора, вводимого в
базис.
Номер вектора s, вводимого в базис, выбирается из
отношений двойственных оценок к отрицательным
элементам r-ой строки симплекс-таблицы:
j
min
a rj 0
a
rj
s
a
rs
или
Ведущим элементом будет
j
s
max
0
a rj 0 a
a
rj
rs
ars
.

9.

С помощью фрагмента симплекс-таблицы, запишем
формулы пересчета ее элементов.
Таблица.
Фрагмент симплекс-таблицы

10.

Компоненты нового псевдоплана определяются согласно (3).
x kнов
xr 0
а ks ,
xk 0
а rs
xr 0
,
а rs
0,
k s,
k
(3)
k s
k
Другие элементы симплексной таблицы вычисляются по
формулам:
а rj
нов
а ks ,
а kj а kj
а rs
а rj
нов
а kj
,
а rs
нов
а
rs
k s,
k s,
j 1, n,
j 1, n
1, r s
0, r s
j s
(4)

11.

Двойственные оценки:
нов
j
j
аrj
аrs
s
(5)
Значение целевой функции на новом псевдоплане:
C(х
нов
хr 0
) C(х )
s
а rs
0
(6)

12.

Теорема 10.
Применение правил 1 и 2, а также формул (3) (6)
обеспечивает:
1) переход к новому псевдоплану, т. е. гарантируется
а) j 0,
j 1, n
б) новый псевдоплан хнов есть базисный план.
2) Значение целевой функции на новом псевдоплане не
больше, чем значение целевой функции на предыдущем
псевдоплане, т.е. С(хнов) С(х0).

13.

П р и м е р 15.
Приведем ЗЛП к каноническому виду
Базисный план х0 = (0; 0; 0; -16; -4) есть псевдоплан

14.

Строим симплекс-таблицу и решаем задачу.
Получен оптимальный план х* = (0; 0; 8; 0; 44)
Значение целевой функции C1(х*) = -8
Значение целевой функции исходной задачи C(х*) = 8.

15.

Признак отсутствия допустимых планов
Теорема. Признак неразрешимости ЗЛП в двойственном
симплекс-методе.
Пусть в ЗЛП (1) имеется псевдоплан х* = (x1*, …, xr*, …, xn*)
такой, что r-я координата меньше нуля, а все элементы r-й
строки симплексной таблицы неотрицательны, тогда ЗЛП
неразрешима.
Более короткая формулировка теоремы:
Если существует псевдоплан х* = (x1*,…, xr*,…, xn*) такой,
что xr * < 0, а элементы а rj 0, j =1, n , то мн-во D = .

16.

П р и м е р.
Выполнив эквивалентные преобразования получаем:
Составим симплексную таблицу:

17.

Таблица.
Из теоремы следует вывод, что задача не разрешима.
Область допустимых планов есть пустое множество (D = ).
Это легко можно проиллюстрировать графически.

18.

Рис. Графическая иллюстрация отсутствия
множества допустимых планов в ЗЛП

19.

Решение ЗЛП с дополнительным активным ограничением
Допустим, что ЗЛП (1) имеет оптимальный план
x * ( x1* ,..., x n* )
Известен носитель оптимального плана
* i1 , i2 ,..., im и *j 0,
j 1, n
Последней итерации симплексной таблицы соответствует
система уравнений
xk akj x j xk 0 , k *
j
Координаты оптимального плана х*
*
xk 0 , k
*
xk
0 , k
(7)

20.

Добавим к исходной ЗЛП (1) дополнительное активное или,
как еще говорят, существенное ограничение вида:
n
a
j 1
m 1, j
x j bm 1
(8)
Введем в неравенство (8) дополнительную переменную
x n+1 0.
n
a
j 1
a
k *
m 1, k
m 1, j
x j xn 1 bm 1
(9)
xk am 1, j x j xn 1 bm 1
j
(10)

21.

Выразим xk из (7) и подставим в уравнение
(10). Получим уравнение (11).
a
k *
m 1,k
(xk 0 akj x j ) am 1, j x j xn 1 bm 1
j
j
(11)

22.

Выделим и сгруппируем свободные переменные, а
постоянные члены перенесем в правую часть уравнения (11):
xn 1 (am 1, j
j
a
m 1,k
akj ) x j bm 1
k *
a
m 1,k
xk 0
(12)
k *
Обозначим xm 1, 0 bm 1
a
m 1, k
xk 0 , тогда дополнительная
k *
переменная xn+1 = xm+1,0. Запишем (12) в (m+1) строку
симплекс-таблицы. Появляется новый единичный
базисный вектор An+1.
За счет дополнительного ограничения (12) получили новую
ЗЛП, в которой имеется псевдоплан
x нов
x*
x
m 1, 0

23.

Действительно, n новых двойственных оценок равны
прежним двойственным оценкам, а оценка n+1 = 0, как
оценка базисного вектора An+1. Кроме того, xm+1,0 0,
так как
bm 1
a
k
*
m 1,k
xk 0
в силу предположения, что
дополнительное ограничение активное.
Имея псевдоплан, можно продолжать решение ЗЛП
двойственным симплекс-методом.

24.

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

25.

(l1) и (l2) обозначения прямых линий, ограничивающих
соответствующие полуплоскости.

26.

Решение производственной задачи

27.

Получен оптимальный план х* = (4; 0; 8; 0)
Издержки составят С(х*) = 20 ден. ед.
Теперь обстоятельства изменились. Заказчик потребовал
изготовить не менее 6 штук изделий А. Появляется новое
активное ограничение х1 6 (обозначим соответствующую
прямую l3).
Вводим дополнительную переменную х5 0

28.

Выразим х1 из второго уравнения и подставим
в третье уравнение. Тогда
Применяя алгоритм двойственного симплекс-
метода, получаем оптимальный план
х1* = (6; 0; 6; 2; 0), С(х1*) = 30 ден. ед.
Геометрическая иллюстрация решения данной
задачи показана на рис.

29.

Иллюстрация решения задачи