АвтоАвтоматизацияАрхитектураАстрономияАудитБиологияБухгалтерияВоенное делоГенетикаГеографияГеологияГосударствоДомДругоеЖурналистика и СМИИзобретательствоИностранные языкиИнформатикаИскусствоИсторияКомпьютерыКулинарияКультураЛексикологияЛитератураЛогикаМаркетингМатематикаМашиностроениеМедицинаМенеджментМеталлы и СваркаМеханикаМузыкаНаселениеОбразованиеОхрана безопасности жизниОхрана ТрудаПедагогикаПолитикаПравоПриборостроениеПрограммированиеПроизводствоПромышленностьПсихологияРадиоРегилияСвязьСоциологияСпортСтандартизацияСтроительствоТехнологииТорговляТуризмФизикаФизиологияФилософияФинансыХимияХозяйствоЦеннообразованиеЧерчениеЭкологияЭконометрикаЭкономикаЭлектроникаЮриспунденкция

Описание второго алгоритма симплекс-метода

Читайте также:
  1. I Классификация кривых второго порядка
  2. I.2.4. Алгоритм симплекс-метода.
  3. IDL-описаниеи библиотека типа
  4. II. ОПИСАНИЕ МАССОВОЙ ДУШИ У ЛЕБОНА
  5. V2: ДЕ 6 - Линейные отображения. Определители второго порядка
  6. XI. Описание заболевания
  7. Алгоритм симплекс-метода
  8. Алгоритм симплекс-метода.
  9. Анализ основных конкурентов (схема и описание)
  10. Аналитическое выравнивание по параболе второго порядка
  11. Аналитическое описание движения
  12. Античное историческое сознание и историописание

Опишем алгоритм применительно к решению ЗЛП, записанной в канонической форме с односторонними ограничениями:

Пусть известен начальный опорный план с базисом , т.е. - базисные компоненты, - небазисные компоненты.

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

Вычисления удобно выполнять, используя две симплекс-таблицы:


Основная таблица
P t
 
     
Вспомогательная таблица
 
 
 
 
 

 

Порядок вычислений по второму алгоритму

1. Найти обратную матрицу и заполнить её элементами столбцы , основной симплекс-таблицы.

2. Вычислить значение линейной формы как скалярное произведение столбцов и основной таблицы. Результат занести в -ю строку столбца основной симплекс-таблицы.

3. Вычислить значения элементов вектора-строки по формуле , как скалярное произведение столбцов и основной симплекс-таблицы. Полученными значениями заполнить -ю строку основной симплекс-таблицы.

4. Найти значения оценок векторов условий относительно базиса по формуле , , как произведение вектора-строки основной таблицы на соответствующий столбец вспомогательной таблицы минус соответствующий коэффициент линейной формы, записанный в -ой строке вспомогательной таблицы. Полученные значения занести в строку вспомогательной таблицы с номером, соответствующим номеру выполняемой итерации.

5. Проверить оптимальность опорного плана.

· Если все оценки неотрицательные (), то - оптимальный опорный план и, тогда, в столбце основной симплекс-таблицы записано решение ЗЛП, а именно, значения базисных компонент оптимального опорного плана и соответствующее ему максимальное значение линейной формы. На этом процесс решения ЗЛП завершается.

· Если среди оценок найдутся отрицательные (), то для построения нового опорного плана необходимо найти вектор, который будет вводиться в базис. Он определяется по номеру наименьшей отрицательной оценки и, таким образом, устанавливается разрешающий столбец .

6. Вычислить коэффициенты разложения вектора по базису , используя формулу , как произведение -ой строки обратной матрицы из основной таблицы на столбец вспомогательной таблицы. Полученные значения занести в столбец основной симплекс-таблицы.

7. Определить вектор, выводимый из базиса. Для этого необходимо заполнить столбец основной таблицы значениями путем деления элементов столбца основной таблицы на соответствующие им по номеру элементы столбца основной таблицы.

· Если все , то исходная задача неразрешима в силу неограниченности сверху линейной формы . На этом процесс решения ЗЛП завершается.

· Если , то необходимо выбрать . Пусть им оказался элемент с номером , т.е. . Тогда соответствующий этому индексу вектор должен выводиться из базиса. Элемент является «разрешающим». На этом нулевая итерация завершена и надлежит приступить к выполнению следующей итерации.

8. Для заполнения новой основной таблицы вычислить по рекуррентным формулам новые значения параметров итерации.

· Заполнить -тую строку новой основной таблицы элементами , , получающимися делением соответствующих элементов () -той строки старой основной таблицы на разрешающий элемент , т.е. по формулам .

· Все остальные -тые строки главной части новой основной симплекс-таблицы получить как результат вычитания из -той строки старой основной симплекс-таблицы -той строки новой симплекс-таблицы, умноженной на соответствующий -тый элемент разрешающего столбца старой основной симплекс-таблицы, т.е. в соответствии с рекуррентными формулами . По аналогичным формулам могут быть вычислены также и элементы -й строки: .

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

Решение М -задачи

Весь процесс решения исходной задачи (2.15) – (2.16) приведен в таблицах 2.3 и2.4.

Заполнение таблиц происходит в соответствии с описанным выше алгоритмом.

Таблица 2.3

Основная симплекс-таблица

0 итерация

N P B t
                12 3/4
                8 14/15
                6 5/8
              1 2/3
m+1 - - -50М       -30М-48 -

 

 

1 итерация

N P B t
    44 1/3       -2/15 -2/5 +
            -1   +
    79 1/3       -8/15 -1 3/5 +
    1 2/3       1/30 3/5 2 7/9
m+1 - -         1 3/5 -27 1/5 -

2 итерация

N P B t
    45 4/9       -1/9 1/9  
            -1    
    83 7/9       -4/9 4/9 188 1/2
    2 7/9       1/18 -1/18 +
m+1 - - 155 5/9       3 1/9 -3 1/9 -

 

3 итерация

N P B t
    24 1/2     -1/4      
    29 1/2     -2 1/4      
    188 1/2     2 1/4 -1    
    13 1/4     1/8      
m+1 - -             -

Вспомогательная симплекс-таблица Таблица 2.4

N B
                     
                     
                     
                  -1  
m+1 С                 -M
  -22M-30 -14M-25 -18M-56 -30M-48       M  
  5 1/5 -2 3/5 -27 1/5         -1 3/5 1 3/5+M
  38 4/9 18 5/9   45 1/3       -3 1/9 3 1/9+M
                  M

 

Решение М-задачи получено за 4 итерации. Оптимальный план её представляет вектор и . В оптимальном плане М-задачи искусственная переменная , поэтому вектор - решение исходной задачи (2.15), (2.16) и .

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


1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 |

Поиск по сайту:



Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав. Студалл.Орг (0.009 сек.)