Составители:
Рубрика:
147
что в процессе решения М-задачи мы не достигнем программы (опорного решения)
исходной задачи, потому что таковой не существует или же вообще система уравнений
несовместна. А так как разрешимая задача линейного программирования, заданная в
канонической форме, всегда имеет хотя бы одну программу (опорное решение),
являющуюся оптимальной, то отсутствие программ указывает на ее неразрешимость.
Рассмотрим два небольших примера неразрешимых задач линейного
программирования (на две причины неразрешимости).
В отличие от всех уже рассмотренных нами задач в этих примерах примем
ограничительные условия смешанного типа:
{ } ( )
,,...,2,1,,
1
mibxa
i
n
j
jij
=≥≤
∑
=
чтобы читатель попутно освоил решение и этого типа задач.
Необходимо найти неотрицательные числа
x
1
≥
0 и,
x
2
≥
0
максимизирующие целевую
функцию
F=2x
1
+x
2
(3.77)
при условиях:
≤−
≥−
.23
,332
21
21
xx
xx
(3.78)
Путем введения дополнительных неотрицательных переменных x
3
, x
4
приводим
эту задачу к следующей эквивалентной каноничеcкой задаче.
Найти неотрицательные числа x
1
, x
2
, x
3
, x
4
, максимизирующие целевую функцию
F=2x
1
+x
2
+0x
3
+0x
4
(3.79)
при условиях:
=+−
=−−
.23
,332
421
321
xxx
xxx
(3.80)
Составляем условие эквивалентной М-задачи. Требуется найти
неотрицательные числа x
1
, x
2
, x
3
, x
4
, y
1
, максимизирующие целевую функцию
F
1
=2x
1
+1x
2
+0x
3
+0x
4
-My
1
, (3.81)
при условиях:
=+−
=+−−
.23
,332
421
1321
xxx
yxxx
(3.82)
Составим симплексную табл.3.11 (столбец для искусственной переменной y
1
в
таблицу не включаем) и проделаем последовательные итерации.
Исходная программа (y
1
= 3, x
4
=2, x
1
= 0, x
2
=0, x
3
= 0) оказалась не оптимальной. Для
улучшения плана проводим замещение базисной переменной x
4
свободной переменной x
1
,
поскольку в этом столбце отрицательная двойственная оценка.
Табл. 3.11
2
1
0
0
Со
P
0
B
x
1
x
2
x
3
x
4
∑
β
α
Страницы
- « первая
- ‹ предыдущая
- …
- 145
- 146
- 147
- 148
- 149
- …
- следующая ›
- последняя »
