ВУЗ:
Составители:
83
5.5.2. Табличный алгоритм замены базисных переменных
Процедура «переразрешения» системы уравнений-ограничений
ОЗЛП относительно новых базисных переменных может быть сущест-
венно упрощена, если ее формализовать и свести к заполнению стан-
дартных таблиц по определенной системе правил – алгоритму.
Рассмотрим систему четырех уравнений-ограничений:
⎪
⎪
⎭
⎪
⎪
⎬
⎫
+++=
+++=
+++=
+++=
вхахах
а
у
вхахаха
у
вхахаха
у
вхахаха
у
4343242141
4
3333232131
3
2323222121
2
1313212111
1
,
,
,
с тремя свободными переменными х
1
, х
2
, х
3
:
min Z = C
o
– C
1
x
1
- C
2
x
2
- C
3
x
3
.
Чтобы алгоритм был проще и легче запоминался, целесообразно пред-
варительно несколько преобразовать систему уравнений, представив их
правые части как разности между свободными членами и суммой ос-
тальных:
⎪
⎪
⎭
⎪
⎪
⎬
⎫
⋅−⋅−⋅−−=
⋅−⋅−⋅−−=
⋅−⋅−⋅−−=
⋅−⋅−⋅−−=
).(
),(
),(
),(
3432421414
4
3332321312
3
3232221212
2
3132121111
1
хахахав
у
хахахав
у
хахахав
у
хахахав
у
(5.16)
Обозначим а
11
=
α
11
, -а
12
=
α
12
, …, тогда получим стандартную форму
записи линейного программирования:
).(min
).(
),(
),(
),(
332211
3432421414
4
3332321313
3
3232221212
2
3132121111
1
xCxCxCC
Z
ххxв
у
ххxв
у
ххxв
у
ххxв
у
o
++−=
⎪
⎪
⎭
⎪
⎪
⎬
⎫
⋅
α
+⋅
α
+⋅
α
+−=
⋅
α
+⋅
α
+⋅
α
+−=
⋅
α
+⋅
α
+⋅
α
+−=
⋅
α
+⋅
α
+⋅
α
+−=
(5.17)
Очевидно, вместо того, чтобы полностью записывать уравнения
(5.17), можно ограничиться заполнением стандартной табл. 5.1. Здесь
ячейки стандартной таблицы, образуемые от пересечения строк (у
1
, у
2
,
Страницы
- « первая
- ‹ предыдущая
- …
- 81
- 82
- 83
- 84
- 85
- …
- следующая ›
- последняя »
