Составители:
Рубрика:
104
Во второй и последующих симплексных таблицах эти суммы пересчитываются по
правилам замещения, так же как и все другие элементы таблицы. Столбец
∑
называют
контрольным
,
так
как по его элементам проверяют правильность всех вычислений.
Последние два столбца (как и столбец
∑
) являются вспомогательными. Без них
можно было бы обойтись, рассматривая их формально, однако они способствуют
упорядочению и тем самым некоторому упрощению расчетов, а потому их также
рекомендуется заполнять. В столбец
β
записываются частные от деления элементов
итогового столбца
В
на элементы некоторого столбца
x
k
матрицы условий, который
выбирается по указанному ниже правилу. В столбец
α
заносятся коэффициенты для
пересчета строк матрицы при переходе от одной симплексной таблицы к другой.
Значение элементов столбца
∑
и столбца
α
известно из предыдущей главы.
Значение элементов столбца
β
также известно из последнего параграфа предыдущей
главы. По минимальному значению из положительных чисел
β
определяется базисная
неизвестная, которая должна быть выведена из базиса, чтобы получить новую лучшую
программу (опорные решения системы ограничений). Но нам пока неизвестно, какая
неизвестная из свободных должна войти в базисные для получения «лучшей» программы
(опорного решения). Рассмотрим этот вопрос.
В (2.10) было показано, что в конечных методах решения задач линейного
программирования, в частности в симплексном методе, осуществляется переход от одного
опорного решения к «лучшему» опорному решению, при котором получается большее
значение целевой функции в задаче максимизации, или меньшее значение в задаче
минимизации. Такой переход осуществляется до тех пор, пока мы не получим оптимальное
опорное решение, на котором целевая функция принимает наибольшее (или наименьшее)
значение. Установим, по какому признаку можно получить на следующей итерации «лучшее»
опорное решение.
Выше приведена общая форма симплексной таблицы (табл. 3.1), основным
содержанием которой является расширенная матрица системы с единичным базисом,
отвечающим данному опорному решению. Нижняя дополнительная строка таблицы,
называемая
оценочной,
рассчитана по формуле
∑
=−=∆
i
jijij
njcac
,...,2,1, (3.3)
где
c
j
—
коэффициенты целевой функции;
с
i
—
коэффициенты целевой функции при базисных неизвестных;
а
ij
—
элементы
j
-го столбца матрицы системы
Числа
∆
j
называются
двойственными оценками.
Мы рассматриваем невырожденную
задачу линейного программирования, в которой все числа
b
i
столбца
В
в любой симплексной
таблице положительны, т. е.
b
i
>0 при всех
i.
Значение целевой функции
∑
=
=
n
j
jj
xcF
1
на опорном решении:
,,...,,0,...,0,0
1121
mmnnn
bxbxxxx =====
++
которому отвечает табл. 3.1, равно:
.......
11112211
mmnssnssnssnnn
bcbcbcbcbcbcF
+++++−−+++
+++++++=
(3.4)
Допустим, что мы перешли к новому опорному решению с ключевым элементом
a
sk
>0,
при котором переменная
x
n+s
(
s ≤
m
) исключается из базисных (становится равной нулю), а
переменная
x
k
(
k≤n
) включается в базисные (становится положительной
x
k
=
'
s
b
>0).
Новое опорное решение будет
Страницы
- « первая
- ‹ предыдущая
- …
- 102
- 103
- 104
- 105
- 106
- …
- следующая ›
- последняя »
