ВУЗ:
Составители:
21
нуля. Однако при возрастании свободной переменной некоторые из базисных
переменных будут уменьшаться. Поскольку отрицательные значения
переменных недопус тимы, то в качестве новой свободной переменной следует
принять ту из базисных переменных, которая раньше других обращается в
ноль.
Пр и пользовании табличным методом удобно ввести специальную форму
записи уравнений и целевой функции. Обозначим через
(
)
m,1ix
i
=
′
базисные
переменные, а через
(
)
mn,1jx
j
−=
′′
свободные переменные. Выразив целевую
функцию и базисные переменные через свободные переменные, сформулируем
задачу линейного программирования в следующем виде: максимизировать
∑
′′
⋅−=−=
′
−
=
mn
1j
jjoo
xcaqq
при условии
(
)
∑
≥
′′
≥
′
=
′′
⋅−=
′
−
=
mn
1j
jijijioi
.0x;0x;m,1ixaax
Пр и тако й форме записи задача может быть представлена матрицей
коэффициентов при свободных переменных, представленной в табл. 3.
Таблица 3
Матрица коэффициентов при свободных переменных
0
1
x
′′
−
2
x
′′
−
…
mn
x
−
′′
−
q´ a
00
a
01
a
02
… a
0(n-m )
1
x
′
a
10
a
11
a
12
… a
1(n-m )
… … … … … …
m
x
′
a
m0
a
m1
a
m2
… a
m(n-m)
По виду коэффициентов матрицы (см. табл. 3) легко судить, является ли
найденное базисное решение допус тимым и, если оно допус тимо, то будет ли
оно оптимальным. Действительно, замечая, что столбец коэффициентов
a
i0
(i ≠ 0) предс тавляет собой базисное решение, соответс твующее базису
,x...,,x
m1
′′
а строчка коэффициентов a
0j
(j ≠ 0) представляет собой взятые с
обратным знаком коэффициенты при свободных переменных, приходим к
выводу, что базисное решение, соответс твующее базису ,x...,,x
m1
′′
допустимо,
если a
i0
≥ 0. Если, кроме того, a
0j
≥ 0, то это базисное решение является
оптимальным. Очевидно также, что при оптимальном базисном решении
коэффициент а
00
дает значение
max
q
′
.
Следовательно, решение задачи линейного программирования табл ичным
методом заключается в нахождении на первом этапе какого-либо допустимого
Страницы
- « первая
- ‹ предыдущая
- …
- 20
- 21
- 22
- 23
- 24
- …
- следующая ›
- последняя »
