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

МПУ состоит в последователь­ном выполнении идентичных шагов (опишем вычислительные процедуры одного шага). К началу очередного шага пусть имеются некоторое ДБМ К и отвечающий ему допустимый вектор х (K) = (х₁, х₂,..., х_п). Над этими исходными данными выполняются следующие процедуры:

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

Зная базисные векторы и допустимый базисный вектор =(х₁, х₂,..., х_m, 0,…,0), решаем систему линейных уравнений:

Эта система имеет единственное решение , т.к. К – это базисное множество.

 

 

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

II. Проверка двойственной допустимости ДБМ К. Для найденного вектора у (К) вычисляются величины и проверяются неравенства , .

1. Находим величины

При этом возможны два случая:

а) . Это означает, что базисное множество К является одновременно допустимым и двойственно допустимым базисным множеством. Тогда (потеореме: если базисное множество К является одновременно допустимым и двойственно допустимым базисным множеством, то отвечающие ему векторы и оптимальные соответственно в задачах А и А*) векторы х (К) и у (К) оптимальны для соответствующих задач и . На этом процесс заканчивается с выдачей искомых оптимальных векторов.

б) условие а) нарушается, т.е. К не является двойственно допустимым и вектор не допустимый в задаче А*. Надо найти и перейти к выполнению следующей процедуры.

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

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

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

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

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

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

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

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

.

 

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

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

 

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

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

K' = (K\ (k* }) { j₀ }.

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

 

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

х (К') = ()

по формулам

, k K' \ { j₀ }, .

При этом

.

 

 

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

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

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

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

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

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

 

				…	n
				…
				…
				…
…	…	…	…	…	…	…
m				…
				…

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

Номер шага
k*

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

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

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

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

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

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

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

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

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

Шаг

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

y (K)=(0,0)

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

, .

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

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

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

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

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

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

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

Т.к. , К ⁺ ={3}

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

 

 

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

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

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

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

 

,

k K' \ { j₀ },

.

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

 

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

 

2 шаг

…………………