7. Построение симплекс-таблицы. Достаточное условие оптимизации в задаче лп. Достаточное условие неразрешимости задачи лп.
Для
табличной реализации симплекс метода
величины
,
,
удобно представить в виде табл.:
Базис
( |
Св.
члены ( |
|
… |
|
… |
|
|
… |
|
|
|
1 |
|
0 |
|
0 |
|
|
|
|
|
0 |
|
1 |
|
0 |
|
|
|
|
|
0 |
|
0 |
|
1 |
|
|
|
|
Г(y) |
0 |
|
0 |
|
0 |
|
|
|
)
)
С
учетом сделанных преобразований исходную
задачу
,
можно переформулировать след. обр.:
найти максимум функции
, где
при ограничениях:
,
где
и неотрицательности.
Будем
искать некот. точку
,
в которой
не уменьшится по сравнению с найденным
знач. в точке y.
Выберем
некот. небазисную перем.
,
и будем подбирать для нее неотрицат.
значения. Остальные базисные перем.
,
,
.
Тогда соотношение
примет
вид:
,
а выражение целевой ф-ции
.
Достаточное условие оптимальности:
Т.:
Если
,
то план y
является оптимальным.
►Рассм.
произв. точку
и целев. ф-ю
◄
Достаточное условие неразрешимости:
Пусть
дост. усл. оптимальности не выполняется,
т.е.
и все величины
из выбранного значения k.
Т.:
Если при
,
,
то целевая функция неограниченно
возрастает. Т.е. ЗЛП неразрешаема.
8. Итерация симплекс-метода.
Пусть
такие номера i,
k:
и
.
В силу того, что
,
а
,
то знач. цел. ф-ции будет увел. Т.о.
выбирается s
(
)
такой, что
.
Эл.
наз. ведущим (разрешающим), i-ая
строка и k-ый
столбец – ведущими (разрешающими). В
качестве знач. перем.
.
Пост.
по ф-лам
следующ.обр.
,
,
,
,
,
…,
,
,
.
,
т.е. n-r
коорд. нулев.
Не равн. 0 коорд. имеют инд.: 1,...,s-1,s+1,…,
r,
k.
Рассм. лин. комб.
(*).
Покажем, что (*) может принимать знач. =0
только при усл., что все
.
Рассм.
,
тогда(*)предст.ввиде:
.
Последняя сумма предст. собой лин. комб.
ЛНЗ векторов
;
,
.
След-но, вектора стоящие при базисных
коорд. точк.
- ЛНЗ.
,
где
,
Выражая
из s-го
ур-ния
(**) знач.
перем.
и подставляя полученное выражение в
остальные ур-ния (**) получим зависимость
между базисными и небазисными коорд.
точк.
,
полученные соотношения представим в
виде симплекс-таблицы:
|
|
|
… |
|
… |
|
|
… |
|
… |
|
|
|
1 |
|
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
0 |
|
|
0 |
|
|
|
|
0 |
|
|
|
0 |
|
|
1 |
|
|
|
|
0 |
|
|
|
0 |
|
|
0 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
0 |
|
|
|
1 |
|
|
0 |
|
|
|
|
0 |
|
|
|
0 |
|
|
0 |
|
|
