Симплекс-метод

1. Симплекс-метод

2.

Теорема 1 Пусть исходная задача решается на минимум, тогда
если для некоторого опорного решения все z-оценки j ( j 1, n)
неположительные, то
оптимальным.
такое
опорное
решение
является
Теорема 2 Если исходная задача решается на максимум, то в
случае, когда все j ( j 1, n) – неотрицательные, получаем
оптимальное решение исходной задачи.

3.

Теорема 3 Если опорный план ЗЛП не вырожден и k 0
такое, что в k-ом столбце системы ограничений есть хотя бы
одно положительное число, т.е. не все aik 0 , то существует
такое опорное решение x ' , что z ( x' ) z ( x), где x – исходное
опорное.
Теорема 4 Если опорное решение ЗЛП не вырождено и k 0
и в k-ом столбце системы ограничений нет ни одного
положительного числа, т.е. все a ik 0, то целевая функция
не ограничена на ОДР.

4.

Структура симплекс таблицы
...
C
m 1
...
A
2
...
A Am 1
m
...
1
0
...
0
a
1, m 1
...
a
1, n
0
1
...
0
a
2, m 1
...
a
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
...
0
0
...
1
a
m, m 1
...
0
0
...
0
...
C
1
C
A
1
x C1 b
1
1
x C b
2 2 2
...
...
...
...
X
Б
C
Б A0
x
C bm
m
m
0
k
2
m
C
m 1
C
n
A
n
a
2, n
m, n
n

5.

Методы контроля:
1. Z-оценки при базисных переменных равны нулю 0 i (1,m);
i
2. Значения правой части всегда неотрицательны b 0
j
j (1,n);
3. Значение целевой функции на каждом шаге не ухудшается.
Зацикливание
Зацикливание может возникать при наличии вырожденного
опорного решения. Выражается в том, что значение целевой
функции на следующем шаге не меняется.

6.

Пример:
3x 5x 7 x min
1
3
5
2 x1 x2 3x4 x6 10
2 1 0 3 0 1 0 10
2 x x 3x 10
3
x
2
x
x
8
1
2
4
1
3
7
3 0 2
0 0 0 1 8
3x 2 x 8
3
1
7 x1 x3 7 x4 x5 12
7 0 1 7 1 0 0 12
7 x x 7 x x 12
3
4 5
1
x 0 j (1,7)
j
x 0 j (1,5)
j
Составим симплекс-таблицу:
x
2
x
7
x
5
-3
0
-5
0
7
0
0
0
10
2
1
0
-3
0
-1
0
0
8
3
0
2
0
0
0
1
7
12
7
0
1
-7
1
0
0
84
52
0
12
-49
0
0
0

7.

Найдем в каждом столбце с положительной z-оценкой
min
b
i :
a
ik
для первого столбца:
для второго столбца:
10
2
5
10
0
-
8
3
2,666667
8
2
4
12
7
1,714286
12
1
12
1,71 – минимальное
4 – минимальное
Теперь получившиеся значения умножаем на соответствующую zоценку:
1,714286 * 52 = 89,
14, 4 * 12 = 48.
Т.о. новый разрешающий элемент -
a13