ВУЗ:
Составители:
Рубрика:
10
вид
c
1
... c
l
... c
m
c
m+1
... c
n
x
0
b
0
c
0
x
1
... x
l
... x
m
x
m+1
... x
n
x
1
b
1
c
1
1 ... 0 ... 0 a
1 m+1
... a
1n
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x
l
b
l
c
l
0 ... 1 ... 0 a
lm+1
... a
ln
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
.
x
m
b
m
c
m
0 ... 0 ... 1 a
mm+1
... a
mn
(c, x
0
) 0 ... 0 ... 0 z
m+1
− c
m+1
... z
n
− c
n
Таблица составлена при условии, что первые m столбцов матрицы условий A, образующие базис,
являются единичными. Поэтому вектора x
j
коэффициентов размножения оставшихся векторов A
j
совпадают с ними и заполняют таблицу.
Фактически исходная таблица содержит все условия задачи, элемент z
j
− c
j
m +1– ой строки
есть разность между скалярным произведением вектора столбца c
0
на столбец x
j
и коэффициентом
линейной формы при ней.
Решение задачи ЛП заключается в последовательном преобразовании этой таблицы по вышеука-
занным формулам. Эти преобразования полностью соответствуют преобразованиям при решении
системы линейных алгебраических уравнений методом Гаусса:
Рассмотрим пример на применение симплекс-метода к задаче ЛП канонического вида, имеющей
единичный базис:
x
1
+x
2
+x
3
− min
x
1
−x4 −2x
6
=5
x
3
−2x
4
−5x
5
+6x
6
=5
x
j
≥ 0,j=1, 2, 3, 4, 5, 6
Легко видеть, что вектора A
1
,A
2
,A
3
образуют базис, которому отвечает опорный план x
0
=
(5, 3, 5, 0, 0, 0). Исходная таблица
bx
0
c
0
x
1
1
x
1
2
x
1
3
x
0
4
x
0
5
x
0
6
x
1
21100−10−2
x
2
310102−37
x
3
51001−2 −56
13000−1 −85
Вектор A
k
, вводимый в базис, определяется z
k
− c
k
= max{3, 5} = z
6
− c
6
=5. Значит столбец A
6
надо ввести в базис. Определим столбец A
l
, исключаемый из базиса, для этого находим
min
i
x
0
i
x
ik
= min{
3
1
,
5
6
} =
x
3
x
36
=
5
6
Значит вектор A
3
заменяется на вектор A
6
, а базисная переменная x
3
на x
6
. Ведущий элемент:
x
36
=6отмечен. Выполняем операцию исключения x
6
из первого и второго уравнения, а в третьем
— коэффициент при x
6
делаем равным единице. Следующая таблица имеет вид (Таблица 1):
c
0
x
1
1
x
2
2
x
1
3
x
0
4
x
0
5
x
0
6
x
1
40/61 102/6 −2/6 −10/60
x
1
13/61 01−1/610/6 −13/60
x
6
5/60001/6 −2/6 −5/61
58/60 0−5/68/6 −23/60
опорный план x
1
= (40/6, 13/6, 0, 0, 0, 5/6)
Теперь снова находим столбец, включаемый в новый базис. Среди всех z
j
− c
j
только z
4
− c
4
=8/11
положительно, следовательно, вектор вводится в базис. Вектор, исключаемый из базиса, находится
отыскиванием
min
x
2
x
24
,
x
6
x
64
= min
13
10
,
5
2
=
13
10
10
вид
c1 ... cl ... cm cm+1 ... cn
x0 b0 c0 x1 ... xl ... xm xm+1 ... xn
x1 b1 c1 1 ... 0 ... 0 a1 m+1 ... a1n
.. .. .. .. .. .. .. ..
. . . . . . . .
xl bl cl 0 ... 1 ... 0 al m+1 ... aln
.. .. .. .. .. .. .. ..
. . . . . . . .
xm bm cm 0 ... 0 ... 1 am m+1 ... amn
0
(c, x ) 0 ... 0 ... 0 zm+1 − cm+1 ... zn − cn
Таблица составлена при условии, что первые m столбцов матрицы условий A, образующие базис,
являются единичными. Поэтому вектора xj коэффициентов размножения оставшихся векторов Aj
совпадают с ними и заполняют таблицу.
Фактически исходная таблица содержит все условия задачи, элемент zj − cj m + 1 – ой строки
есть разность между скалярным произведением вектора столбца c0 на столбец xj и коэффициентом
линейной формы при ней.
Решение задачи ЛП заключается в последовательном преобразовании этой таблицы по вышеука-
занным формулам. Эти преобразования полностью соответствуют преобразованиям при решении
системы линейных алгебраических уравнений методом Гаусса:
Рассмотрим пример на применение симплекс-метода к задаче ЛП канонического вида, имеющей
единичный базис:
x1 +x2 +x3 − min
x1 −x4 −2x6 = 5
x3 −2x4 −5x5 +6x6 = 5
xj ≥ 0, j = 1, 2, 3, 4, 5, 6
Легко видеть, что вектора A1 , A2 , A3 образуют базис, которому отвечает опорный план x0 =
(5, 3, 5, 0, 0, 0). Исходная таблица
b x0 c0 x11 x12 x13 x04 x05 x06
x1 2 1 1 0 0 −1 0 −2
x2 3 1 0 1 0 2 −3 7
x3 5 1 0 0 1 −2 −5 6
13 0 0 0 −1 −8 5
Вектор Ak , вводимый в базис, определяется zk − ck = max{3, 5} = z6 − c6 = 5. Значит столбец A6
надо ввести в базис. Определим столбец Al , исключаемый из базиса, для этого находим
x0i 3 5 x3 5
min = min{ , } = =
i xik 1 6 x36 6
Значит вектор A3 заменяется на вектор A6 , а базисная переменная x3 на x6 . Ведущий элемент:
x36 = 6 отмечен. Выполняем операцию исключения x6 из первого и второго уравнения, а в третьем
— коэффициент при x6 делаем равным единице. Следующая таблица имеет вид (Таблица 1):
c0 x11 x22 x13 x04 x05 x06
x1 40/6 1 1 0 2/6 −2/6 −10/6 0
x1 13/6 1 0 1 −1/6 10/6 −13/6 0
x6 5/6 0 0 0 1/6 −2/6 −5/6 1
58/6 0 0 −5/6 8/6 −23/6 0
опорный план x1 = (40/6, 13/6, 0, 0, 0, 5/6)
Теперь снова находим столбец, включаемый в новый базис. Среди всех zj − cj только z4 − c4 = 8/11
положительно, следовательно, вектор вводится в базис. Вектор, исключаемый из базиса, находится
отыскиванием
x2 x6 13 5 13
min , = min , =
x24 x64 10 2 10
Страницы
- « первая
- ‹ предыдущая
- …
- 8
- 9
- 10
- 11
- 12
- …
- следующая ›
- последняя »
