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


Мы поможем в написании ваших работ!



ЗНАЕТЕ ЛИ ВЫ?

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



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

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

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

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

 

 

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

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

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

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

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

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

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

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

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

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

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

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

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

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

.

 

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

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

 

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

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

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

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

 

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

х (К') = ()

по формулам

, k K' \ { j0 }, .

При этом

.

 

 

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

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

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

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

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

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

 

      n  
 
 
 
m
   

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

Номер шага
k*  

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

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

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

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

Векторы α3, α4 – линейно независимы, базисное множество 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* }) { j0 } K' ={2,4}

 

,

k K' \ { j0 },

.

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

 

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

 

2 шаг

…………………



Поделиться:


Последнее изменение этой страницы: 2016-04-26; просмотров: 519; Нарушение авторского права страницы; Мы поможем в написании вашей работы!

infopedia.su Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Обратная связь - 54.159.186.146 (0.024 с.)