ВУЗ:
Составители:
122
Итерация 1. с
2
=min(с
1
,с
2
)=-3<0,
следовательно, переменная х
2
будет
базисной. Для определения
зисной переменной найдем отноше-
ние
2i
i
a
b
для всех i:
2
1
2
;1
1
1
22
2
12
1
====
a
b
a
b
.
Минимально первое из них,
поэтому a
12
x
2
– р-член. Новая кано-
ническая форма будет тогда иметь
вид
⎪
⎩
⎪
⎨
⎧
=−+−
=+−
=++−
.334
,12
,1
31
431
321
zxx
xxx
xxx
Итерация 2. Новое базисное допустимое решение:
х
1
= х
3
= 0; х
2
= х
4
= 1; z = -3.
Значение целевой функции уменьшилось. Решение соответствует точке В.
Т.к. с
1
= min(с
1
, с
3
) = -4 < 0, то переменная х
1
будет базисной. Только
одно отношение
2i
i
a
b
> 0 – это при i = 2, поэтому р-член a
21
x
1
= 2x
1
. Перемен-
ная х
4
будет внебазисной. Новая каноническая форма
⎪
⎩
⎪
⎨
⎧
=−+
=+−
=++
.zxx
,/x/x/x
,/x/x/x
5 2
212121
232121
43
431
432
Это соответствует базисному решению
х
1
=0,5; х
2
=1,5; х
3
=х
4
=0; z=-5.
Значение целевой функции еще более уменьшилось. Решение соответ-
ствует точке С. Эта точка является решением задачи линейного программи-
рования, т.к. все c
j
> 0.
Таким образом, были рассмотрены основы обычного симплексного ме-
тода решения задач ЛП. На практике чаще используются его модификации.
7.7.4. Модифицированный симплекс-метод
Процедура обычного симплекс-метода требует большого числа итера-
ций. На каждом цикле вычислений появляются ошибки округления, которые
накапливаются. В результате оптимальное решение не будет верным. Поэто-
Рис. 7.11. Графическое решение
п
р
име
р
а 7.17
Страницы
- « первая
- ‹ предыдущая
- …
- 120
- 121
- 122
- 123
- 124
- …
- следующая ›
- последняя »
