ВУЗ:
Составители:
80
L = - x
1
+ x
1
– 1 + 0,5x
1
+ x
4
–1 = 0,5x
1
+ x
4
– 2,
L′ = 0,5x
1
+ x
4
.
5.5. Симплекс-метод решения задачи линейного программирования
5.5.1. Аналитическое введение в симплексный метод
Симплексный метод был разработан известным американским ма-
тематиком Дж. Данцигом и в настоящее время стал универсальным ме-
тодом линейного программирования. Алгоритм метода состоит из ряда
шагов.
I. При решении задачи симплексным методом необходимо систе-
му уравнений линейных ограничений привести к виду, когда какие-либо
r переменных (базисные) выражены через остальные свободные пере-
менные, причем свободные члены этих выражений должны быть неот-
рицательными.
Пусть для определенности x
1
, x
2
, …, x
r
выражены через ос-
тальные переменные x
r+1
, x
r+2
, x
r+3
, …, x
n
.
Система ограничений принимает вид
⎪
⎪
⎭
⎪
⎪
⎬
⎫
+++=
+++=
+++=
++
++
++
,...
...............................................
;...
;...
''
1
'
1,
'
2
'
21
'
1,22
'
1
'
11
'
1,11
вxaxах
вxaxах
вxaxах
rnrnrrrr
nnrr
nnrr
(5.14)
где .0 ..., ,0 ,0
''
2
'
1
≥≥≥
ввв
r
Базис (x
1
, x
2
, …, x
r
) обозначим через Б. Пусть все небазисные пе-
ременные равны нулю:
x
r+1
= x
r+2
=…, x
n
=0.
Найдем из системы (5.14) значения базисных переменных:
. ..., , ,
'
1
'
2
1
'
1
вх
в
х
в
х
rr
=
==
В результате получаем базисное решение (
ввв
r
''
2
'
1
..., , , ), соответст-
вующее базису Б.
Целевая функция (минимизируемая линейная функция) F (x
1
, x
2
,
…, x
n
) также выражается через небазисные переменные
....
'
1
'
1
xCxCC
F
nnrro
+++=
++
Страницы
- « первая
- ‹ предыдущая
- …
- 78
- 79
- 80
- 81
- 82
- …
- следующая ›
- последняя »
