40105

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

Доклад

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

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

Русский

2013-10-15

178 KB

18 чел.

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, записанный в базисе

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


 

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

30111. Менделизм 19.19 KB
  При скрещивании двух гомозиготных организмов относящихся к разным чистым линиям и отличающихся друг от друга по одной паре альтернативных признаков всё первое поколение гибридов F1 окажется единообразным и будет нести признак одного из родителей Этот закон также известен как закон доминирования признаков. Мендель же формулировал чистоту признака как отсутствие проявлений противоположных признаков у всех потомков в нескольких поколениях данной особи при самоопылении. Закон расщепления признаков: Закон расщепления или второй...
30112. Хромосомная теория наследственности (Т. X. Морган и др.) 18.08 KB
  Хромосомная теория наследственности Т. Доказано что количество наследственных признаков организма значительно превышает число хромосом гаплоидного набора. Так в гаплоидном наборе классического объекта генетических исследований мухидрозофилы есть только четыре хромосомы но число наследственных признаков и соответственно генов которые их определяют несомненно значительно больше. Это означает что в каждой хромосоме находится много генов.
30113. Генетика пола, Искусственная регуляция пола 42.68 KB
  Генетика пола Пол это совокупность признаков и свойств организма определяющих его участие в размножении. Пол особи может определяться: а до оплодотворения яйцеклетки сперматозоидом прогамное определение пола; б в момент оплодотворения сингамное определение пола; в после оплодотворения эпигамное определение пола. У морского кольчатого червя бонеллия определение пола происходит в процессе онтогенеза: если личинка садится на дно из нее развивается самка а если...
30114. Цитоплазматическое наследование 12.96 KB
  Цитоплазматическое наследование: Для того чтобы та или иная структура могла выполнять роль материального носителя наследственности и обеспечивать количественные закономерности наследования как уже было сказано она должна обладать тремя основными свойствами: выполнять жизненно важные функции в метаболизме клетки обладать способностью к самовоспроизведению точно распределяться в дочерние клетки при делении. Так центриоли участвуют в образовании веретена при делении клетки пластиды обеспечивают некоторые синтетические процессы митохондрии...
30115. Взаимодействие генов 14.76 KB
  Полное доминирование заключается в том что в гетерозиготе полученной при скрещивании представителей чистых линий различающихся по одной пара альтернативных признаков один из двух аллелей не проявляет своего действия. В фенотипе 3 частей проявился доминантный признак а у 1 части рецессивный. При неполном доминировании гибриды первого поколения имеют фенотип укладывающийся в рамки проявления признака между исходными родителями и никогда их не достигающий т. признак может быть любым но не как у представителей чистых линий: меньше...
30116. Инструментальные материалы. Упрочняющая обработка 220 KB
  Инструментальными являются материалы, основное назначение которых - оснащение рабочей части инструментов. К ним относятся инструментальные углеродистые, легированные и быстрорежущие стали, твердые сплавы, минералокерамика, сверхтвердые материалы.
30117. Генные мутации 33.8 KB
  Генные мутации. По последствиям генных мутаций их классифицируют на нейтральные регуляторные и динамические а также на миссенс и нонсенсмутации. Нейтральная мутации молчащая мутация мутация не имеет фенотипического выражения например в результате вырожденности генетического кода. Динамические мутации мутации обусловленные увеличением числа тринуклеотидных повторов в функционально значимых частях гена.
30118. Хромосомные мутации и геномные мутации 16.53 KB
  Хромосомные мутации и геномные мутации. Различают два основных типа хромосомных мутаций: численные хромосомные мутации и структурные хромосомные мутации. В свою очередь численные мутации делятся на анэуплоидии когда мутации выражаются в утрате или появлении дополнительной одной либо нескольких хромосом и полиплоидии когда увеличивается число гаплоидных наборов хромосом. Потерю одной из хромосом называют моносомией а возникновение дополнительной хромосомы у любой пары хромосом трисомией.
30119. Модификационная (фенотипическая) изменчивость 16.63 KB
  Характеристика: обратимость изменения исчезают при смене специфических условий окружающей среды спровоцировавших их групповой характер изменения в фенотипе не наследуются наследуется норма реакции генотипа статистическая закономерность вариационных рядов затрагивает фенотип при этом не затрагивая сам генотип.По размаху нормы реакции узкая более характерна для качественных признаков широкая более характерна для количественных признаков 3.По длительности: есть лишь у особи или группы особей которые подверглись влиянию...