Составители:
Рубрика:
146
2-я итерация
0
x
4
6
2
4
0
1
0
-1
0
12
3
/
2
1
0
x
5
3
-3
6
0
0
1
-2
0
5
1/2
3/2
3
xз
0
1
-2
1
0
0
1
0
1
-
-1/2
0 x
7
0 -2 0 0 0 -1 1 2 0 -
0
2
-8
0
0
0
3
0
-3
-
-2
3
-
я итерация
0 x
4
6 0 0 1 0 0 -1 10 3/2 -
0
x
5
3
0
0
0
0
1
-1/2
-3/2
2
∞
0
3
xз
0
0
0
1
0
0
1/2
1/2
2
-
0
2
x
2
0
-1/2
1
0
0
0
-1/4
1/4
1/2
-
-1/8
0
-2
0
0
0
0
1
2
1
-
-1/2
4
-
я итерация
1
x
1
3/2
0
x
5
3
3
x
3
0
2
x
2
3/4
3 0
0
0
1/2
0
1
3/2
6
Эта задача имеет очевидную вырожденную исходную программу x
1
=0, х
2
=0, х
3
=0,
x
4
=6, x
5
=3, х
6
=0, х
7
=0, связанную с единичной подматрицей. Здесь две базисных
неизвестных х
6
и х
7
равны нулю. Составим симплексную табл. (3.10) и проведем
последующие итерации.
Несмотря на явную вырожденность предложенной задачи (все программы
вырожденные), применение обычного алгоритма симплексного метода привело очень
быстро к оптимальному решению x
l
=
3
/2,
x
2
=
3
/4,
x
3
= 0,
x
4
=0,
x
5
= 3,
x
6
= 0,
x
7
=0.
При этом только
на последней итерации получилось приращение целевой функции. На
всех предыдущих итерациях значение целевой функции оставалось неизменным нулевым
исходным значением.
3.5. Обнаружение неразрешимости задачи
линейного программирования
Неразрешимость задачи линейного программирования может происходить по двум
причинам: либо задача не имеет ни одной программы (опорного решения), либо целевая
функция условиями задачи не ограничена.
В первом случае неразрешимость задачи обнаруживается тем, что в процессе
решения М-задачи будет получено ее оптимальное решение еще до того, как будут
выведены из базисных все искусственные переменные. При этом из оставшихся
искусственных базисных переменных y
i
хотя бы одна будет отлична от нуля. Это значит,
4
4
Страницы
- « первая
- ‹ предыдущая
- …
- 144
- 145
- 146
- 147
- 148
- …
- следующая ›
- последняя »
