Составители:
Рубрика:
117
В матрицах систем уравнений такого вида не содержится единичной подматрицы,
в которой диагональные элементы были бы равны единице, а остальные — нулю. В них
содержатся подматрицы, соответствующие дополнительным неизвестным, с
диагональными элементами, равными — 1. Поэтому, если принять дополнительные
неизвестные в качестве базисных, то они окажутся отрицательными (х
1
= х
2
= х
3
= х
4
= x
5
= 0,
х
6
= — 500, х
7
= — 1000, х
8
= — 200, x
9
= — 400), т. е. не будут удовлетворять условиям
неотрицательности всех переменных. Следовательно, здесь мы не имеем явной
неотрицательной исходной программы.
Для решения задачи необходима единичная подматрица (с положительными
элементами). Чтобы получить ее, надо ввести еще одну группу неизвестных, число
которых равно числу исходных неравенств (или уравнений — в первом примере), по
одному такому неизвестному на каждое неравенство (или уравнение). Эти новые
неизвестные в отличие от дополнительных — уравновешивающих — называют
искусственными. В данной задаче обозначим их через y
1
, у
2
, у
3
, y
4
и введем их в левые части
уравнений со знаком плюс.
Симплексные уравнения исходных условий в окончательном виде, допускающем
перенесение коэффициентов при неизвестных непосредственно в первоначальную
симплекcную таблицу, будут
1
:
⋅++++
+−−−−⋅++++=
+⋅+++
+−−−−++++=
++++
+−−−⋅−⋅+⋅+++=
+++⋅+
+−−−⋅−+⋅+++=
.1000
100012010400
,0100
010010003200
,0010
0010012121000
,0001
000101100500
4321
987654321
4321
987654321
4321
987654321
4321
987654321
yyyy
xxxxxxxxx
yyyy
xxxxxxxxx
yyyy
xxxxxxxxx
yyyy
xxxxxxxxx
(3.24)
В этих уравнениях имеется единичная подматрица и все неизвестные считаются
неотрицательными. Дальнейшее решение задачи может быть выполнено двумя способами.
Рассмотрим их последовательно.
Первый способ заключается в отыскании какой-то программы (опорного плана)
основной задачи (3.16), (3.17) посредством решения вспомогательной задачи, которая
заключается в нахождении минимума целевой функции:
F’=y
1
+ y
2
+ y
3
+ y
4
=min (3.25)
или, в расширенном виде,
F’=0x
1
+0x
2
+0x
3
+0x
4
+0x
5
+0x
6
+0x
7
+0x
8
+0x
9
+1y
1
+1y
2
+1y
3
+1y
4
=min
Если получится минимум этой целевой функции, равный нулю (F' = 0), то в решении
этой вспомогательной задачи (3.24; 3.25) получится искомая программа исходной задачи (3.16;
3.17).
Последняя таблица вспомогательной задачи при F'=0 = min служит основой для
составления первоначальной симплексной таблицы для решения исходной задачи. С этой
целью надо из последней таблицы вспомогательной задачи отбросить столбцы,
соответствующие неизвестным у
1
, у
2
, y
3
и y
4
, затем изменить коэффициенты с
j
в первой
строке и столбце с
0
, заменив их соответствующими коэффициентами с
j
, из целевой функции
Страницы
- « первая
- ‹ предыдущая
- …
- 115
- 116
- 117
- 118
- 119
- …
- следующая ›
- последняя »
