40105

Двойственный симплекс-метод, основные принципы, алгоритм. Случаи, когда удобно применять двойственный симплексный метод

Доклад

Менеджмент, консалтинг и предпринимательство

ДСМ ДСМ как и СМ называется методом последовательного улучшения оценок и применяется для решения задачи: исходным пунктом этого метода является выбор такого базиса . Таким образом основные принципы ДСМ заключаются в том чтобы: каждый раз выполнялось 2 значения целевой функции убывало. Для этого воспользуемся 2м принципом ДСМ. Чтобы обеспечить это надо выбрать так что: 6 Алгоритм ДСМ формулируется так: Выбираем базис и строим I симплекстаблицу Если все то решение оптимально иначе переход к 3.

Русский

2013-10-15

178 KB

14 чел.

18. Двойственный симплекс-метод, основные принципы, алгоритм. Случаи, когда удобно применять двойственный симплексный метод. (ДСМ)

ДСМ, как и СМ, называется методом последовательного улучшения оценок и применяется для решения задачи:

исходным пунктом этого метода является выбор такого базиса .

Предположим   (1)

и  (2)

Вектор X0, соответствующий АБ может быть недопустимым, так как среди его компонент могут быть отрицательные числа. Вектор X0 называется псевдорешением

Вектор  является допустимым решением двойственной задачи.

Для псевдорешения  можно записать

AX = B

X = A-1B

YTA = CT

YT = CTA-1

Согласно взаимосвязи между значениями целевых функций исходной и двойственной задач ( F(X)  Z(Y) ) для допустимого решения исходной задачи  и допустимого решения двойственной задачи  выполняется

Лемма. Для двух допустимых решений двойственной пары X = (x1, x2, …, xn) и Y = (y1, y2, …, ym) выполняется  F(X)  Z(Y)

ДОК-ВО: ЧТД

Таким образом, если поиск оптимального решения исходной задачи вести путем перехода от одного псевдорешения к другому, то при этом необходимо уменьшать значения целевой функции исходной задачи. Таким образом, основные принципы ДСМ заключаются в том, чтобы:

  1.  каждый раз выполнялось (2)
  2.  значения целевой функции убывало.

Определим выбор разрешающего элемента , удовлетворяющего вышеуказанным принципам. Согласно СМ можно записать:

(3)

Пусть . Вектор , тогда из (3)

Чтобы гарантировать выполнение этого неравенства для должно выполняться .  (4)

Пусть .

Для  условие (3) будет выполняться в силу (2) и (4).

Для  условие (3) представим в виде

, так как , то знак изменится.

надо выбрать из условия  (5)

Установим принцип выбора строки . Для этого воспользуемся 2-м принципом ДСМ. Учитываем

Значение . Чтобы обеспечить это  надо выбрать так, что:

(6)

Алгоритм ДСМ формулируется так:

  1.  Выбираем базис и строим I симплекс-таблицу
  2.  Если все , то решение оптимально, иначе переход к 3.
  3.  Находим строки, где . Если для некоторой выполняется , то система несовместна,

иначе выбирается  (для условности можно выбирать наименьшую отрицательную ).

  1.  Выбираем  j0 согласно (5). Разрешающий элемент
  2.  Строится новая симплекс-таблица и переходим к шагу 2.

В ДСМ, как и в СМ, возможно зацикливание в случае, когда   (7)

В этом случае F не изменит значения при переходе к новому базису. Если зацикливание произошло, то можно изменить номера i0 и j0, то есть изменить выбор разрешающего элемента и продолжить решение. Если (7) не возникает, то зацикливания нет и целевая функция периодически убывает. Если на i-ой итерации произошло убывание целевой функции, то предыдущее базисное решение на последующих итерациях не вычисляется, и за конечное число итераций прекратиться убывание целевой функции, найдено  оптимальное решение.

Случаи, когда удобно применять ДСМ

Применимость ДСМ на практике ограничена тем, что сложно выбрать базис (1), который обеспечивает условие (2).

Укажем случаи, когда выбор базиса не представляет труда.

1) пусть имеется следующая исходная задача:

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

Перейдем к дополнительным переменным:

В качестве базиса  выберем .

В силу того, что , то

Таким образом, задача подготовлена к применению ДСМ.

2) в некоторых практических задачах можно обнаружить, что найденное решение не отражает действительную ситуацию. Это происходит, когда при построении ЭММ не было учтено некоторое ограничение. Это ограничение должно быть добавлено, и задача должна быть решена заново с учетом этого ограничения. Если ограничение имеет вид неравенства, то удобнее применять ДСМ.

Предположим  – оптимальное решение исходной задачи на max, т.е. все .

Добавляем неравенство:

Вводим дополнительную переменную:

Составим расширенную матрицу полученной системы:

Обозначим строку i через .

Сделаем следующее преобразование последней строки матрицы A по следующей формуле:

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

Каждый столбец A есть вектор Aj, записанный в базисе

Таким образом,  – симплекс-таблица, построенная по методу дополнительных переменных. Надо записать в таблицу  Так как вектор  – базисный и , то  совпадают с оценками заключительной симплекс-таблицы задача готова к применению ДСМ, если при этом .


 

А также другие работы, которые могут Вас заинтересовать

53246. Природа й населення Стародавньої Греції 84.5 KB
  Населення Давньої Греції та довколішніх земель. У різних містах Греції зустрілися у славетному храмі бога Аполлона в місті Дельори яке знаходиться поблизу південного схилу гори Парнас. Населення Давньої Греції та довколишніх земель.
53247. Викторина «Древняя Греция». 6 класс 62 KB
  Вспомните миф и назовите море. Назовите имя героини. Персефона Назовите сына критского мастера построившего лабиринт. Назовите героя.
53248. Греция в ІІ – первой половине І тыс. до н.э 62 KB
  Цели урока: познакомить учащихся с гомеровским периодом в истории Греции; рассмотреть произведения Гомера Одиссея Илиада и дать характеристику этим произведениям как литературным памятникам и историческим источникам; показать причины и направления греческой колонизации; формировать умения и навыки работы в группах со словарем и хронологической таблицей; повышать уровень культурного развития учащихся Ожидаемые результаты: после этого урока учащиеся смогут: называть время гомеровского периода и периода греческой колонизации в...
53249. Греко-перські війни 49.5 KB
  А Марафонська битва; Б Битва при Фермопілах; В Сала мінська битва; Г Остаточна перемога греків та її значення; Перший Афінський морський союз. А Марафонська битва; 13 вересня 490 до н. Марафонська битва 20000 персів та 11000 греків під керівництвом Мільтіада → перемога греків → марафонський біг 42 км. Б Битва при Фермопілах; 481 створено військовооборонний союз Спарти та Афін.
53250. Греко-перські війни 2.01 MB
  А Марафонська битва. Б Битва при Фермопілах. В Саламінська битва. А Марафонська битва.
53251. Греко-перські війни 52 KB
  А Марафонська битва; Б битва при Фермопілах; В Саламінська битва; 3. А Марафонська битва. Марафонська битва Б Битва при Фермопілах. битва при Фермопілах.
53252. Музыкальная гостиная: «Гений норвежской музыкальной сказки - Эдвард Григ» 224 KB
  Ключевая компетенция способность личности мобилизовать свои знания умения а также способы выполнения действий необходимых для адаптации и продуктивной деятельности в различных профессиональных сообществах. развитие познавательного интереса у младших школьников и эмоционального отклика на шедевры музыкальной классики воспитания у учащихся ценностного отношения к мировой культуре в процессе восприятия и творческой интерпретации произведений мировой классики; обогащения знаний учащихся о музыке как о сфере ориентированной на...
53253. Управління системою громадянського виховання в загальноосвітньому навчальному закладі 313 KB
  ТЕОРЕТИЧНІ ОСНОВИ УПРАВЛІННЯ СИСТЕМОЮ ГРОМАДЯНСЬКОГО ВИХОВАННЯ В ЗАГАЛЬНООСВІТНЬОМУ НАВЧАЛЬНОМУ ЗАКЛАДІ. Сутнісна характеристика системи громадянського виховання. Шляхи реалізації системи громадянського виховання в загальноосвітньому навчальному закладі.
53254. Що означає бути громадянином своєї держави 45.5 KB
  Мета уроку: розкрити зміст понять громадянин громадянство громадянські якості громадянські почуття і почуття; пояснити що означає бути громадянином і відчувати приналежність до своєї держави; висловлювати власне судження про те як людина може бути корисною суспільству; наводити приклади вчинків якими вони зможуть принести користь суспільству. План змісту уроку Що означає бути громадянином своєї держави.Що означає бути громадянином і відчувати приналежність до своєї держави.