Мегаобучалка Главная | О нас | Обратная связь  


Особенности алгоритма метода искусственного базиса




Алгоритм метода искусственного базиса имеет следующие особенности:

1. Ввиду того, что начальное опорное решение расширенной задачи содержит искусственные переменные, входящие в целевую функцию с коэффициентом –M (в задаче на максимум) или +M (в задаче на минимум), оценки разложений векторов условий состоят из двух слагаемых и , одно из которых не зависит от M , а другое зависит от M. Так как M сколь угодно велико по сравнению с единицей >>1), то на первом этапе расчета для нахождения векторов, вводимых в базис, используется только слагаемые оценок .

2. Векторы, соответствующие искусственным переменным, которые выводятся из базиса опорного решения, исключаются из рассмотрения.

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

4. Переход от решения расширенной задачи к решению исходной задачи осуществляется с использованием доказанных выше теорем 3.2.-3.4.

И

Р е ш е н и е. Составляем расширенную задачу. В левые части уравнений системы ограничений вводим неотрицательные искусственные переменные с коэффициентом +1 (всегда). Удобно справа от уравнений записать вводимые искусственные переменные. В первое уравнение вводим переменную , во второе – переменную . Данная задача – задача на нахождение максимума, поэтому и в целевую функцию вводятся с коэффициентом –M. Получаем:

 

Задача имеет начальное опорное решение с базисом . Вычисляем оценки векторов условий по базису опорного решения и значение целевой функции на опорном решении:

 

 

 

Записываем исходные данные в симплексную таблицу (табл. 3.1.1). При этом оценки и для удобства вычислений записываем в две строки: в первую – слагаемые , не зависящие от M, во вторую – слагаемые , зависящие от M. Значения удобно указывать без M, имея в виду, однако, что оно там присутствует.

 

Таблица 3.1.1

 

3 2 -8 -M -M

Б
-M -M           -7 -2      
-3 -2 -1
-12 -5 -4 -5

 

Начальное опорное решение не является оптимальным, так как в задаче на максимум имеются отрицательные оценки (см. теорему 3.1). Выбираем номер вектора , вводимого в базис опорного решения, и вектора , выводимого из базиса. Для этого вычисляем приращения целевой функции при введении в базис каждого из векторов с отрицательной оценкой и находим максимум этого приращения. При этом слагаемыми оценок (без M) пренебрегаем до тех пор, пока хотя бы одно слагаемое (с M) отлично от нуля. В связи с этим со слагаемыми оценок может отсутствовать в таблице до тех пор, пока присутствует строка . Находим:

при k=3.

В столбце « » (см. табл. 3.1.1) за разрешающий элемент выбираем коэффициент 1 во второй строке и выполняем преобразование Жордана.

Вектор , выводимый из базиса, исключаем из рассмотрения (вычеркиваем). Получаем опорное решение с базисом (табл. 3.1.2). Решение не является оптимальным, так как имеется отрицательная оценка

 

 

Таблица 3.1.2

 

Б
    -M         -5     -1       -2           -
-1 -1  
-2 -1  

 

 

 

 

В столбце « » единственный положительный элемент принимаем за разрешающий и переходим к новому опорному решению с базисом (табл.3.1.3).

 

 

Таблица 3.1.3

 

Б
-8     -5 -8   -1 -1          
-10    

 

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

О т в е т: при

 




Читайте также:
Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы...
Как выбрать специалиста по управлению гостиницей: Понятно, что управление гостиницей невозможно без специальных знаний. Соответственно, важна квалификация...
Почему человек чувствует себя несчастным?: Для начала определим, что такое несчастье. Несчастьем мы будем считать психологическое состояние...



©2015-2020 megaobuchalka.ru Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. (360)

Почему 1285321 студент выбрали МегаОбучалку...

Система поиска информации

Мобильная версия сайта

Удобная навигация

Нет шокирующей рекламы



(0.004 сек.)