Составители:
Рубрика:
101
Ниже шапки матрицы идут строки, которые образуют матрицу условий. В них
записываются коэффициенты при неизвестных из симплексных уравнений (3.2). Этих
строк в матрице должно быть ровно столько, сколько в данной задаче ограничений. Это
хорошо видно на табл. 3.1, в которой показан пример заполнения первой симплексной
таблицы применительно к условию общей формулировки стандартной задачи линейного
программирования на максимум, при ограничениях — неравенствах со знаками ≤ и
положительными числами b
1
,..., b
m
.
Последнюю строку таблицы называют оценочной (или дополнительной). В нее
заносятся двойственные оценки
∆
j
,
которые непосредственно не вытекают из ранее
сформулированного условия задачи, а рассчитываются по определенной формуле,
которая будет рассмотрена несколько ниже. Оптимальность программы определяется по
знакам чисел ∆
1
, ∆
2
,…, ∆
j
,…,∆
n
оценочной строки. Кроме того, по числам ∆
j
,- можно
установить, за счет чего может' быть улучшена программа, если она не оптимальная.
Далее рассмотрим таблицу по столбцам. Столбцы, находящиеся слева от матрицы
условий, имеют существенное значение и элементы их входят в условия задачи (в первой
таблице) или получаются в процессе решения задачи (во второй и последующих таблицах) .
Столбцы, стоящие справа от матрицы условий, являются вспомогательными и служат для
определения направления продолжения расчетов и средства для ведения контроля за
правильностью вычислений.
Сначала следует заполнить второй столбец таблицы (P
0
). В него записываются
наименования базисных неизвестных, связанных с единичным базисом. Напомним, что все
неизвестные, входящие в задачу линейного программирования, подразделяются на базисные и
свободные (см. гл. 2). Последние в любой программе (опорном решении) всегда равны
нулю. Число базисных неизвестных обычно совпадает с числом ограничительных
уравнений, которые входят в программу (план). В первой симплексной таблице в столбце
P
0
указываются наименования всех дополнительных неизвестных [в случае стандартной
задачи (1-10) при неотрицательных b
i
], которые являются базисными неизвестными
исходной программы.
В первый (слева) столбец С
0
записываются коэффициенты c
i
целевой функции,
которые соответствуют базисным неизвестным, вошедшим в исходную программу
(записанным в столбце P
0
).
Следующий, третий по счету, столбец — столбец В в первой симплексной таблице—
заполняется значениями базисных неизвестных x
j
, входящих в начальную программу. В
случае стандартной задачи значения базисных неизвестных начальной программы
представляют собой совокупность неотрицательных свободных членов ограничительной
системы, поэтому для такой задачи столбец В заполняется неотрицательными числами
b
1
,b
2
,…, b
т
. Во второй и последующих симплексных таблицах в процессе итеративного
(повторяющегося) расчета числа столбца В постепенно преобразуются в искомое
оптимальное решение, т. е. характеризуют величину базисных неизвестных, входящих в
оптимальную программу; поэтому этот столбец и называют итоговым.
На пересечении итогового столбца и оценочной строки находится клетка, в
которой указывается значение целевой функции F
k
, соответствующее данному этапу
решения (данной k-й итерации).
Далее идут столбцы, которые представляют векторы условий. Количество этих
столбцов равно числу всех неизвестных в канонической задаче. Эти столбцы в первой
симплексной таблице заполняются коэффициентами при неизвестных в ограничительных
уравнениях. Сначала располагаются столбцы коэффициентов при основных неизвестных,
а далее столбцы коэффициентов при дополнительных неизвестных.
Страницы
- « первая
- ‹ предыдущая
- …
- 99
- 100
- 101
- 102
- 103
- …
- следующая ›
- последняя »
