Составители:
Рубрика:
110
В ключевом столбце в иных примерах (и последующих итерациях нашего примера)
могут быть элементы отрицательные и равные нулю. При делении элементов итогового
столбца на отрицательные элементы получился бы выпуск отрицательного количества
продукции, а при делении на нулевые элементы — выпуск сколь угодно большого
количества продукции. Иными словами, эти ресурсы (или продукция) не лимитируют
выпуск продукции, подлежащей вводу в программу. Следовательно, соответствующие
этим ресурсам неизвестные не должны исключаться из базисных неизвестных.
Отсюда следует важное правило:
при выборе ключевой строки
не принимаются во
внимание строки, на пересечении которых с ключевым столбцом находятся нулевые или
отрицательные элементы.
В табл. 3.2 ключевой столбец и ключевая строка выделены специальной
штриховкой. Элемент, находящийся на пересечении ключевого столбца и ключевой
строки, называют
ключевым элементом
(в литературе ключевые столбец, строку и
элемент называют также по-другому — разрешающие, ведущие, направляющие,
генеральные и др.).
Итак, ключевой столбец — это такой, который соответствует продукции (иначе
базисной неизвестной), включаемой в данный момент (на данной итерации) в программу.
Ключевая строка соответствует ресурсам (или продукции), которые в данный момент (на
данной итерации) из программы исключаются.
Процесс решения задачи как раз и заключается в том, что поочередно заменяются
ресурсы (или продукция в ряде случаев), входящие в программу, выпуском более
выгодной продукции, причем на каждой итерации ресурсы (или менее выгодная
продукция) одного вида полностью исключаются из программы, а на освободившееся
место включается другая продукция, которая в предыдущей программе отсутствовала.
Выполняя такую замену при переходе от одной программы к другой, следует
иметь в виду, что при этом изменяются числовые значения всех элементов таблицы.
Следовательно, элементы табл. 3.2 должны быть преобразованы так, чтобы они
соответствовали новому варианту плана, новой программе. В этом преобразовании
важную роль играет ключевой элемент. Однако это подробно будет изложено ниже, а
сейчас следует вычислить элементы столбцов
∑
и
α
, которые остались незаполненными.
В столбец
∑
(в дальнейшем его будем называть
контрольным столбцом)
в первой
симплексной таблице записываются суммы элементов матрицы по строкам, начиная от
столбца
В
и кончая столбцом
x
п+т
(в данном примере столбцом
x
7
).
Элементы столбца
α
для каждой строки рассчитываются путем деления элемента
этой строки, стоящего в ключевом столбце, на ключевой элемент. Эти элементы
выполняют чисто вспомогательную роль при преобразовании матрицы. В нашем примере
можно было бы обойтись без них, однако в более сложных задачах наличие элементов
α
позволит несколько упростить технику расчетов при преобразовании матрицы.
Следующий этап (итерация) в решении задачи заключается в составлении новой
программы и преобразовании элементов старой матрицы с тем, чтобы они
соответствовали новой программе. Преобразованные элементы будем записывать в
табл. 3.3.
Прежде всего в столбец
P
1
записываются базисные неизвестные, входящие в
новую программу (в нашем примере — старые
x
5
,
х
6
,
х
7
,
вместо
x
4
—
x
3
)
,
а в столбец
с
0
—
соответствующие коэффициенты
с
3
,
с
5
,
с
6
и
c
7
целевой функции.
Преобразование старой матрицы начинают с пересчета элементов
ключевой
строки. Если разделить все ее элементы на ключевой элемент, то получившиеся в
результате элементы будут соответствовать новому варианту плана, новой программе.
Эти показатели записываются в строку с вновь введенной базисной неизвестной
х
3
.
Эту
строку называют
главной
строкой. Так, разделив элемент
b
1
=1500 в прежней
Страницы
- « первая
- ‹ предыдущая
- …
- 108
- 109
- 110
- 111
- 112
- …
- следующая ›
- последняя »
