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

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


 

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

33758. Договор дарения 16.24 KB
  Договор дарения. Договор дарения договор по которому одна сторона даритель безвозмездно передает или обязуется передать другой стороне одаряемому вещь в собственность либо имущественное право требование к себе или третьему лицу либо освобождает или обязуется освободить ее от имущественной обязанности перед собой или третьим лицом. Разновидностью договора дарения является пожертвование дарение сделанное в отношении неопределенного круга лиц в общеполезных целях. Договор дарения может быть как консенсуальным так и...
33759. Договор ренты (понятие, виды) 14.34 KB
  Договор ренты понятие виды. По договору ренты одна сторона получатель ренты передает другой стороне плательщику ренты в собственность имущество а плательщик ренты обязуется в обмен на полученное имущество периодически выплачивать получателю определенную денежную сумму либо предоставить средства на его содержание в иной форме. Виды договора ренты: постоянная рента; пожизненная рента; пожизненное содержание с иждивением. Эти виды договора ренты имеют ряд общих признаков но различаются: формой предоставления содержания...
33760. Исполнение, новация и другие способы прекращения обязательств 17.24 KB
  Наиболее частым и нормальным способом прекращения обязательства является его исполнение Однако это имеет место если произведенное исполнение является надлежащим т. соответствует всем условиям самого обязательства и требованиям законодательства установленным для данного вида обязательств. Факт исполнения обязательства во взаимоотношениях предпринимателей обычно подтверждается составлением двустороннего акта приемки. Возможно частичное исполнение обязательства по предмету или сроку и тогда обязательство в соответствующей части...
33761. Понятие, значение и виды договоров 15.69 KB
  Понятие значение и виды договоров. Договор это соглашение двух или нескольких лиц об установлении изменении или прекращении гражданских прав и обязанностей. Значение договоров: договор одно из оснований возникновения гражданских прав и обязанностей; часто под договором понимается не просто юридический факт а само правоотношение возникающее из соглашения сторон; договор основной способ оформления отношений участников гражданского оборота; договоры опосрвдуют движение объектов гражданских прав от одних субъектов к...
33762. Содержание и форма договора 15.1 KB
  Содержание и форма договора. Содержание договора составляет совокупность согласованных сторонами условий. Среди условий договора необходимо выделять существенные условия. Существенными являются условия о предмете договора условия которые названы в законе или иных правовых актах как существенные или необходимые для договоров данного вида а также все те условия относительно которых по заявлению одной из сторон должно быть достигнуто соглашение ч.
33763. Основные и предварительные договоры. Договор присоединения 15.35 KB
  Основные и предварительные договоры. Договор присоединения. Основной договор непосредственно порождает права и обязанности сторон связанные с перемещением материальных благ: передачей имущества выполнением работ оказанием услуг и т. Предварительный договор это соглашение сторон о заключении основного договора в будущем.
33764. Свободные и обязательные договоры. Характеристика публичного договора 15.02 KB
  Заключение же обязательных договоров как это следует из самого их названия является обязательным для одной или обеих сторон. Обязательным участником публичного договора является коммерческая организация. При отсутствии хотя бы одного из указанных признаков договор не является публичным и рассматривается как свободный договор. Так если предприятие розничной торговли заключает с гражданином договор куплипродажи канцелярских товаров которыми торгует это предприятие то данный договор является публичным.
33765. Способы и порядок заключения гражданско-правовых договоров. Момент заключения договора 15.89 KB
  Способы и порядок заключения гражданскоправовых договоров. Момент заключения договора. Договор считается заключенным если между сторонами достигнуто соглашение по всем существенным условиям договора. Понуждение к заключению договора не допускается за исключением случаев когда обязанность заключить договор предусмотрена ГК законом или добровольно принятым обязательством.
33766. Заключение договора в обязательном порядке 15.54 KB
  Заключение договора в обязательном порядке. Указанный порядок применяется в тех случаях когда заключение договора является обязательным для одной из сторон в силу закона т. Заинтересованная в заключении договора сторона для которой его заключение не является обязательным направляет другой стороне для которой заключение договора обязательно проект договора. Сторона для которой заключение договора является обязательным должна в течение 30 дней со дня получения оферты рассмотреть ее и направить другой стороне: либо извещение об...