Компьютерное моделирование задач оптимизации. Мироновский Л.А - 31 стр.

UptoLike

ВУЗ: 

СПб ГУАП | Санкт-Петербург

Составители: 

Рубрика: 

31
решить путем полного перебора всех базисов, но их число может быть
весьма велико (число сочетаний из n элементов по m).
Алгоритм симплексметода состоит из следующих пяти шагов.
Шаг 0. Выбирается начальный базисный набор. Путем линейного
комбинирования уравнений (2), целевая функция и ограничения
равенства преобразуются к диагональной форме относительно базис
ных переменных так, чтобы каждая базисная переменная входила
только в одно уравнение и не входила в целевую функцию. Результат
записывается в форме так называемой симплекстаблицы. В ее пер
вую строку записывают коэффициенты c
i
целевой функции, а в ос
тальные строки – коэффициенты a
ij
ограничений задачи. В первый
столбец симплекстаблицы записывают коэффициенты b
i
– свобод
ные члены ограничений.
В частности, следующая таблица диагонализирована относитель
но базиса из первых m переменных (x
1
, x
2
, …, x
m
):
x
1
x
2
...
x
m
x
m
1+
...
x
n
сизаБ
b
i
\ c
i
00 ...0
c
m 1+
...
c
n
x
1
b
1
10 ...0
a
,1 m 1+
...
a
,1 n
x
2
b
2
01 ...0
a
,2 m 1+
...
a
,2 n
...........................
x
m
b
m
00 ...1
a
m,m 1+
...
a
n,m
Слева от таблицы записаны текущие базисные переменные (x
1
,
..., x
m
), а сверху приведен набор всех переменных задачи.
Шаг 1. Проверяется, все ли коэффициенты c
i
положительны. Если
это так, то таблица соответствует оптимальному решению.
Шаг 2. Если среди коэффициентов c
i
есть отрицательные, то выби
рается столбец с минимальным c
i
. Такой столбец и соответствующая
ему переменная называются ведущими. При увеличении этой пере
менной критерий уменьшается наиболее быстро.
Шаг 3. Выбирается ведущая строка, соответствующая той из базис
ных переменных, которая будет убывать меньше других. Это та пере
менная, для которой a
i,вед
>0 и отношение b
i
/a
i,вед
минимально. Если
таких переменных нет (все a
i,вед
£0), то задача неразрешима.
После выбора ведущих строки и столбца, происходит смена бази
са, при этом переменная ведущей строки исключается из него (умень

Страницы