Составители:
Рубрика:
115
3.2. Симплексный метод в решении задач с условием
в виде уравнений и неравенств со знаком
≥
≥≥
≥
(метод искусственного базиса)
В предыдущем параграфе нами рассмотрен основной алгоритм симплексного метода
для решения так называемой стандартной задачи линейного программирования на
максимум целевой функции
∑
=
=
n
j
jj
xcF
1
,
условие которой было представлено в виде
неравенств
∑
=
=≤
n
j
ijij
mibx
1
),...,2,1(
α
с положительными свободными членами. Исходные
неравенства нами были преобразованы в уравнения путем ввода дополнительных
неотрицательных неизвестных (
x
n+1
,…,
х
п+т
).
Дополнительные неизвестные входили в
симплексные уравнения со знаком плюс, и в единичной подматрице на главной диагонали мы
имели элементы, равные единице. Это позволило нам получить исходную программу.
В целом ряде экономических задач исходные ограничительные условия могут быть
представлены в виде уравнений
∑
=
==
n
j
ijij
mibx
1
),,...,2,1(
α
или неравенств
∑
=
=≥
n
j
ijij
mibx
1
),,...,2,1(
α
или, наконец, ограничительные условия могут быть смешанными в виде уравнений и
неравенств с любыми знаками:
{ }
∑
=
=≥=≤
n
j
ijij
mibx
1
).,...,2,1(,,
α
Предположим, дано условие задачи в виде системы линейных уравнений:
=+++
=+−+
=−+−
7
,632
,22
4321
4321
4321
xxxx
xxxx
xxxx
(3.12)
и требования минимизации целевой функции
F
(
x
)=2
x
1
+
x
2
-
x
3
-
x
4
(3.13)
при неотрицательных переменных
x
1
,
x
2
,
x
3
и
x
4
или то же в общем развернутом виде:
=+++
=+++
mnmnmm
nn
bxaxaxa
bxaxaxa
...
...............................................
,...
2211
11212111
(3.14)
при
bi
≥
0,
i
=l, 2, . . .,
m
и при
x
j
≥
0,
j
=1,2,…,
n
и минимизации целевой функции
F
=
c
1
x
1
+
c
2
x
2
+…+
c
n
x
n
. (3.15)
Как в числовом примере, так и в общей формулировке задачи нет таких
переменных
x
j
,
которые бы входили с коэффициентом + 1 один раз в какое-либо одно
уравнение системы.
Следовательно, нет и явной исходной программы.
Страницы
- « первая
- ‹ предыдущая
- …
- 113
- 114
- 115
- 116
- 117
- …
- следующая ›
- последняя »
