Методы оптимизации (стр. 3 )

Для этого решаем систему уравнений . Матрица этой системы совпадает с транспонированной матрицей системы, решаемой на процедуре 1, поэтому она также имеет единственное решение. В результате определяем

IV. Определение . Проверяем выполнение неравенств , . При этом возможны два случая.

(а) Все коэффициенты gk неположительные. Тогда на основании следствия 1 векторы , опреде­ляемые в лемме 3, являются допустимыми в задаче А при всех , а линейная функ­ция на множестве таких векторов не ограничена сверху. Процесс на этом заканчи­вается с выдачей вектора х(К) и коэффициентов gk.

Метод последовательного улучшения допустимого вектора (МПУ)

IV. Определение (продолжение).

(б) Среди коэффициентов gk разложения имеются положительные. Тогда на основании следствие 2 векторы являются допустимыми в задаче А лишь при , где вычисляется по формуле:

.

При этом фиксируем элемент k* K*, на котором достигается равенство, затем переходим к последней процедуре.

Метод последовательного улучшения допустимого вектора (МПУ)

V. Подготовка информации к следующему шагу.

В ка­честве нового допустимого базисного множества принимаем

K' = (K\(k*}) {j0}.

Из базиса удаляется вектор , а вводится в базис вектор .

Вычисляем компоненты соответствующего вектора

х(К') = ( )

по формулам

, k K' \{j0}, .

При этом

.

Метод последовательного улучшения допустимого вектора (МПУ)

Замечание. В процедуре II, вообще говоря, нет не­обходимости вычислять для всех . Естественно, для каждой вычисленной величины сразу же проверить вы­полнение неравенства . Если это неравенство нару­шается, то имеет место случай б), т. е. К не является двойственно допустимым и вектор не допустимый в задаче А*, в качестве можно принять соответствующее . Однако ввиду того, что

должно быть не очень малым. По­этому при решении небольших задач обычно вычис­ляют все величины и в случае б) индекс выби­рается так, чтобы . При решении больших задач все уже не вычисляются, но с помощью специальных приемов добиваются того, чтобы для выбранного в случае б) величина мало отличалась от максималь­ного .

Метод последовательного улучшения допустимого вектора (МПУ)

При решении задач с помощью МПУ исходная информация и текущие данные обычно располагают в таблицах следующего вида:

Таблица 1. Исходная информация

	1	2	3	…	n
1				…
2				…
3				…
…	…	…	…	…	…	…
m				…
				…

Таблица 2. Текущие данные

Номер шага
k*

Пример решения задачи ЛП с помощью МПУ

Прямая задача А Двойственная задача А*

Найдем базис, базисное множество К, построим исходный допустимый вектор x(K)

	α1	α2	α3	α4	β	y
1	1	1	0	-2	y1
1	-3	0	1	-3	y2
сj	1	2	0	0

Векторы α3, α4 – линейно независимы, базисное множество K={3,4}.

- имеет единственное решение

Исходный допустимый вектор: x(K)=(0,0,2,3); m=2

Пример решения задачи ЛП с помощью МПУ

I. Определение вектора y(К).

1 шаг

Единственное решение имеет система: , K={3,4}.

y(K)=(0,0)

II. Проверка двойственной допустимости ДБМ К

, .

Проверим , ? Ясно, что

Вектор вводим в базис

Пример решения задачи ЛП с помощью МПУ

III. Вычисление коэффициентов разложения вектора по базисным векторам.

- разложение по базису

IV. Определение .

Определяем, какой вектор удалить из базиса.

Т. к. , К+ ={3}

Исключаем из базиса вектор

Пример решения задачи ЛП с помощью МПУ

V. Подготовка информации к следующему шагу.

В ка­честве нового допустимого базисного множества принимаем

K' = (K\(k*}) {j0} K' ={2,4}

,

k K' \{j0},

.

- допустимый вектор

(функция не ухудшилась)

2 шаг

…………………