Прогнозирование устойчивости. Жигулин Г.П - 124 стр.

UptoLike

ВУЗ: 

Университет ИТМО | Санкт-Петербург

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

Рубрика: 

126
Первые три метода являются универсальными, остальные же
предназначены для определенных классов задач.
Рассмотрим более подробно универсальный метод – метод
последовательного улучшения решения.
6.3.1. Метод последовательного улучшения решения
(симплекс-метод)
Основы метода были сформулированы в 1947 г. Данцигом под названием
симплексного метода (simplex (лат.) – простой).
Идея метода содержит три существенных момента:
1. указывается способ вычисления исходного (опорного) решения;
2. устанавливается признак, который позволяет проверить, является
ли выбранное решение оптимальным;
3. дается способ перехода от выбранного неоптимального решения к
другому, более близкому к
искомому оптимальному решению.
Допустим, в задаче ЛП имеется
n – переменных и m – независимых
линейных ограничений. Причем
kmn
=
−
. Выберем k -переменных в качестве
свободных в порядке возрастания, т.е.
k
xxx ,,,
21
Κ
, а остальные m – базисных
переменных (
nkk
xxx ,,,
21
Κ
++
) выразим, как и ранее, через свободные. Получим:
⎪
⎪
⎭
⎪
⎪
⎬
⎫
++++=
++++=
++++=
+++++
+++++
.
.........................
,
,
2211
2,222,211,22
1,122,111,11
nknknnn
kkkkkkk
kkkkkkk
xxxx
xxxx
xxxx
βααα
βααα
βααα
Κ
Κ
Κ
(6.51.)
Из предыдущих выводов известно, что оптимальное решение (если оно
существует) достигается в одной из опорных точек (вершин ОДР), где по
крайней мере
mnk −= переменных равны нулю.
Положим, в качестве первого шага решения, что все свободные
переменные равны нулю:
0;;0;0
21
=
=
=
k
xxx
Κ
.
(6.52.)
Подставляя (6.52.) в (6.51.), имеем
nnkkkk
xxx
β
β
β
=
=
=
++++
;;;
2211
Κ
.
(6.53.)
Решение (6.53.) может быть допустимо, если все свободные члены
nkk
β
β
β
;;;
21
Κ
++
– неотрицательны и тогда будем иметь опорное решение.
Проверяем, будет ли это решение оптимальным. Для этого подставляем
(6.52.) в минимизированную линейную функцию
L , выраженную через
свободные переменные
k
xxx ,,,
21
Κ .

Страницы