ВУЗ:
Составители:
Таблица 1
С
1
С
2
... С
m
С
m + 1
... С
k
... C
n
C
б
Базис
плана
План
X
P
1
P
2
...
P
m
P
m + 1
...
P
k
... P
n
C
1
P
4
B
1
1 0 … 0 Z
1, m + 1
... Z
1k
... Z
1n
C
2
P
5
B
2
0 1 … 0 Z
2, m + 1
... Z
2k
... Z
2n
… …
… … … … … ... ... … ... ...
C
m
P
m
B
m
0 0 … 1 Z
m, m + 1
... Z
mk
... Z
mn
Z
k
Z
1
Z
2
... Z
m
Z
m + 1
... Z
k
... Z
n
∆
k
F(X) = 0
∆
1
∆
2
... ∆
m
∆
m + 1
... ∆
k
... ∆
n
В первом столбце таблицы C
б
записывают коэффициенты целевой функции (С
1
, С
2
, …, С
m
) при базисных перемен-
ных (в базис входят только векторы, образующие единичную подматрицу, как в нашем случае P
1
/ P
m
). Во втором столбце
(Базис плана) должны находиться базисные векторы данного опорного плана, а в третьем столбце (План Х) – правая часть
ограничений задачи (базисные компоненты плана). Таким образом, перемножая элементы первого столбца таблицы со
столбцом «План Х» и суммируя эти произведения, мы получаем значение целевой функции (ячейка –
()
mm
BCBCBCXF +++= ...
2211
).
Первая строка симплексной таблицы содержит коэффициенты линейной функции нашей задачи и остается неизмен-
ной на протяжении всего решения (С
1
, С
2
, …, С
n
).
В центральной части таблицы записывают коэффициенты при неизвестных в ограничениях исходной задачи (Z
11
, …,
Z
1n
, …, Z
m1
, …, Z
mn
). При этом следует заметить, что коэффициенты при базисных переменных в ограничениях задачи
составляют единичную подматрицу.
Строку Z
k
рассчитывают по формуле
∑
=
=
m
j
jkjk
ZCZ
1
. (3)
Строку ∆
k
рассчитывают по формуле
kkk
CZ
−
=
∆
. (4)
Известно, что при переходе к новому опорному плану X(Θ), в котором k-я компонента равна Θ > 0 (станет базисной),
значение целевой функции изменится и будет равно:
()()
(
)
k
XFXF ∆Θ−=Θ
0
. (5)
Выводы относительно данного опорного плана делают на основании содержимого последней строки таблицы по
следующим критериям.
Критерий 1 (критерий оптимальности). Если все ∆
k
≥ 0 , то выбранный план для задачи максимизации является оп-
тимальным (для задачи на минимум признак оптимальности – неположительность всех ∆
k
).
Критерий 2. Если обнаруживается некоторое ∆
k
< 0 (для задачи минимизации ∆
k
> 0) и хотя бы одно из значений
Z
jk
> 0, то переход к новому опорному плану увеличит (уменьшит) значение целевой функции. При этом в базис будет
вводиться новый вектор, выбор которого определяется по критерию максимального по модулю произведения Θ∆
k
. Если к
тому же учесть, что число положительных (базисных) компонент опорного плана должно оставаться равным m, то одну
из m базисных компонент исходного плана обращаем в нуль выбором:
jk
j
Z
X
0
min=Θ , (6)
где
0
j
X – компоненты опорного плана; Z
jk
– коэффициенты при k-й переменной в ограничениях задачи.
Критерий 3. Если обнаруживается некоторое ∆
k
< 0, но все Z
jk
≤ 0, то линейная форма задачи не ограничена по
максимуму (неограниченность по минимуму устанавливается аналогично при ∆
k
> 0 и всех Z
jk
≤ 0).
Переход к очередной симплексной таблице сводится к тому, чтобы выразить
X
k
из уравнения, соответствующего
минимуму для Θ, и исключить из остальных уравнений (в итоге получаем единичный вектор при новой базисной компо-
ненте и тем самым сохраняется единичная подматрица при базисных векторах):
1.
Строку, соответствующую вектору, выводимому из базиса (главная строка), делим на коэффициент (главный
элемент), находящийся на пересечении этой строки и столбца, соответствующего вектору, вводимому в базис (главный
столбец).
2.
От всех остальных строк вычитаем преобразованную главную строку, умноженную на элемент, находящийся на
пересечении искомой строки и главного столбца.
Получив новую симплексную таблицу для улучшенного опорного плана, действуем по той же схеме, т.е. проверяем
новый план на оптимальность и при необходимости переходим к очередному опорному плану. Этот процесс продолжаем
до тех пор, пока найденный опорный план не окажется оптимальным.
Итак, нахождение оптимального плана симплексным методом включает следующие этапы:
1.
Находят опорный план.
2.
Составляют симплекс-таблицу.
Страницы
- « первая
- ‹ предыдущая
- …
- 10
- 11
- 12
- 13
- 14
- …
- следующая ›
- последняя »
