Решение прямой задачи представлено следующими симплекс-таблицами: бп icon

Решение прямой задачи представлено следующими симплекс-таблицами: бп




Скачати 142.95 Kb.
НазваРешение прямой задачи представлено следующими симплекс-таблицами: бп
Дата20.09.2012
Розмір142.95 Kb.
ТипРешение

2.7. Получение оптимального решения двойственной задачи с помощью симплекс-таблиц прямой задачи


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

Найти такие х1 и х2, которые удоволетворяют следующим условиям:

mах L=2х1+3х2;

x1+2х2\<8;

x1\<1;

x12>/0.

Прямая задача в стандартной имеет вид:

mах L=2х1 +3х2;

x1+2х23=8;

x14=1;

x1234 >/0

Двойственная задача:

min L=8у12;

у12 >/2;

1 >/ 3; (у1 >/ 3/2);

у1>/0;

у2>/0.

Решим с помощью симплекс-метода по отдельности обе задачи.

Решение прямой задачи представлено следующими симплекс-таблицами:

БП

x1

x2

x3

X4

Решение

x3

1

2

1

0

8

x4

1

0

0

1

1

L

-2

-3

0

0

0





































х2

1/2

1

1/2

0

4

х4

1

0

0

1

1

L

-1/2

0

3/2

0

12





































х2

0

1

1/2

-1/2

7/2

х1

1

0

0

1

1

L

0

0

3\2

1/2

25/2



Решение прямой задачи : х1=1; х2=7/2; mах L=25/2.

Поскольку в двойственной задаче имеются ограничения вида>/ , то для её решения используем М-метод:

mіn L=8у12+МR1+MR2;

y123+R1=2;

14+R2=3;

у1234,R1,R2>/ 0.

Так как:

R1=2-у123;

R2=3-2у14,

То после подстановки R1 и R2 в целевую функцию, двойственная задача будет иметь вид:
^

min L=(8-3M) y1+(1-M) y2+My3+My4+5M;


y1+y2-y3+R1=2;

2y1-y4+R2=3;

y1234, R1, R2>/ 0.

Решение двойственной задачи представлено следующими симплекс-таблицами:

БП

y1

y2

y3

y4

R1

R2

Решение

R1

1

1

-1

0

1

0

2

R2

2

0

0

-1

0

1

3

L

8+3M

-1+M

-M

-M

0

0

5M

























R1

0

1

-1

1/2

1

-1/2

1/2

y1

1

0

0

-1/2

0

1/2

3/2

L

0

-1+M

-M

-4+1/2M

0

4-3/2M

12+1/2М

























y2

0

1

-1

1/2

1

-1/2

1/2

y1

1

0

0

-1/2

0

1\2

3/2

L

0

0

-1

-3 1/2

1-M

3 1/2-M

25/2


Решение двойственной задачи: у1=3/2; у2=1/2; mіn L=12 ½.

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

Правило:

Коэффициент при Разности между левой и правой

начальной базисной = частями ограничения двойственной

переменной в оптимальном задачи, ассоциированного с данной

L-уравнении прямой задачи начальной базисной переменной.


Используем данное правило к рассмотренной выше задаче:

Начальные базисные переменные прямой задачи- это х3, х4. Коэффи-

циенты при этих начальных базисных переменных в оптимальном L - уравнении прямой задачи равны, соответственно, 3/2, 1/2.

Ограничения двойственной задачи, ассоциированые с данными началь-ными базисными переменными имеют вид:

y1>/ 0;

у2>/ 0.

Разности между левой и правой частями этих ограничений равны, соответственно,

у1-0 и у2-0.

Используя сформулированное правило, получаем:

3/2=у1;

1/2=у2.

Это же решение следует и из оптимальной симплекс-таблицы двой-ственной задачи.

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

Начальными базисными переменными двойственной задачи есть R1и R2. Коэффициенты при начальных базисных переменных в оптимальном L - уравнении равны, соответственно, 1-М и 3 ½-М.

Ограничение прямой задачи, ассоциированные с данными начальными переменными, имеют вид:

Х1 \
х2 \
Разности между левыми и правыми частями этих ограничений равны, соответственно,

х1-М;

х2-М.

Используя сформулированное правило, получаем:

1-М=х1-М;

3 ½-М=х2-М.

Откуда, х1=1; х2=3 ½.

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

Следовательно, необходимо решать только ту задачу (прямую или двойственную), для которой трудоёмкость вычислений меньше.

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

Анализ и сопоставление результатов, полученных при решении прямой и двойственных задач позволяет сформулировать два интересных вывода:

  1. Оптимальные значения целевых функций прямой и двойственных задач совпадают:

_

mах L=min L.

2. В задаче максимизации целевая функция последовательно увеличивается от начального значения до оптимального. В задаче минимизации целевая функция последовательно уменьшается от начального значения до оптимального ( рис. 2.6.).

Допустимые, но не оптимальные Допустимые решения двойственной

значения прямой задачи. задачи.

|_________________________ |____________________________________|

| Недопустимые значения двойствен- | Недопустимые значения прямой задачи, но “луч- |

ной задачи шие“, нежели её оптимальное решение

_

Начальное мах L=min L Начальное

значение допустимое опти- значение

целевой мальное решение целевой

функции прямой и двойствен- функции

в задаче ной задач в задаче

максими- миними-

зации зации

Рис. 2.6.

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

Очевидно также, что чем меньше интервал между начальными значениями целевых функций прямой и обратной задачей, тем ближе допустимые значения переменных к их оптимальным значениям. Это может быть использовано для проверки удачности выбранных начальных допустимых решений. Кроме того, неоптимальному по допустимому решению одной задачи соответствует недопустимое, но “лучшее” чем оптимальное значение другой задачи.”Лучшее” понимается в том смысле, что значение целевой функции для этой задачи будет лучше, чем для оптимального допустимого решения.

Эти выводы, позволили разработать двойственный симплекс-метод решения задач ЛП, при исспользовании которого сначала находят недопустимое, но “лучшее”, чем оптимальное решение (при обычном симплекс-методе сначала находят допустимое, не неоптимальное решение).


^ 2.8. Двойственный симплекс- метод


Рассмотрим двойственный симплекс-метод на следующем примере.

Найти такие х1 и х2 , которые обеспечивают:

min L=3х12, при ограничениях:

1+4х2>/ 25;

х1 \<3;

х1>/ 0; х2>/ 0.

Введя лишь дополнительные переменные (искусственные переменные вводить не будем), получаем следующую задачу ЛП:

min L=3x1+x2;

-5x1-4x2+x3=-25;

х14=3;

х1, х2, х3, х4>0.

Приравнивая переменные х1 и х2 нулю , получаем начальную симплекс-таблицу вида:

БП

х1

х2

х3

х4

Решение

х3

-5

-4

1

0

-25

х4

1

0

0

1

3

L

-3

-1

0

0

0


ведущий столбец


Начальная симплекс-таблица соответствует оптимальному

( коэффициенты в L - уравнении для небазисных переменных отрица-тельны) по недопустимому ( х3 = -25 не являются неотрицательной ) решению.

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

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

Алгоритм двойственного симплекс-метода приведен на рис.2.7.



1. Приведение к задаче с ограничениями вида равенств, путём введения только дополнительных переменных.

Для исходных ограничений >/, правые части равенств делают отрицательными .





2. Нахождение начального недопусти- мого (дополнительные переменные для ограничений >/ 0 оказываются отрицательными), но оптимального значения.




3. Проверка

Решение Да решения на допусти-

найдено мость (условие допусти-

мости)


нет



4. Переход к соседней оптимальной вершине, в которой значение целевой функции ухудшается (условие оптимальности).




Рис. 2.7


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

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

После выбора исключаемой из базиса переменной (ведущей строки) и включаемой в базис (ведущего столбца) осуществляется обычная для симплекс-метода операция преобразования строк симплекс-таблицы.

Для рассматриваемого примера условие допустимости не выполняется для базисной переменной х33=-25), что и определяет ведущую строку.

В качестве включаемой базис переменной выбирается х2, так как для этой переменной отношение коэффициента L-уравнения (-1) к соответствующему коэффициенту ведущей строке (-4) является наименьшим (1/4). Для небазисной переменной х1 это отношение равно 3/5.Последующее преобразование строк приводит к новой симплекс-таблице:

БП

х1

х2

х3

х4

Решение

х2

5/4

1

-1/4

0

25/4

х4

1

0

0

1

3

L

-1 3/4

0

-1/4

0

25/4


Новое решение является оптимальным (коэффициенты в L-уравнений для небазисных переменных х1 и х3 отрицательны) и допустимым (все переменные неотрицательны). Итак, решением данной задачи является:

х1=0; х2=25/4; min L=25/4.

Применение двойственного симплекс-метода особенно эффективно при анализе моделей на чувствительность, в частности, в тех случаях, когда после получения оптимального решения в условие задачи вводится новое ограничение. Если для предыдущего оптимального решения новое ограничение не выполняется,то полученное решение оптимальное, но недопустимое. Применяя двойственный симплекс-метод находим новое оптимальное решение путём пошагового уменьшения «степени недопустимости решений».

Схожі:

Решение прямой задачи представлено следующими симплекс-таблицами: бп iconРешение прямой задачи представлено следующими симплекс-таблицами: бп
Получение оптимального решения двойственной задачи с помощью симплекс-таблиц прямой задачи
Решение прямой задачи представлено следующими симплекс-таблицами: бп iconРешение по методу Денавита Хартенберга было очень громоздким и потому решили его упростить. Как известно, решение прямой задачи намного проще решения обратной, потому очертим метод решения только обратной задачи
Украине внедряются разные типы роботов и станков. Это позволяет предприятиям уменьшить процентное соотношение брака продукции и увеличить...
Решение прямой задачи представлено следующими симплекс-таблицами: бп icon3 Формулировка задачи
Транспортная задача представляет собой задачу лп, которую можно решать симплекс-методом. Однако специфическая структура условий задачи...
Решение прямой задачи представлено следующими симплекс-таблицами: бп icon3 Формулировка задачи
Транспортная задача представляет собой задачу лп, которую можно решать симплекс-методом. Однако специфическая структура условий задачи...
Решение прямой задачи представлено следующими симплекс-таблицами: бп icon3 Формулировка задачи
Транспортная задача представляет собой задачу лп, которую можно решать симплекс-методом. Однако специфическая структура условий задачи...
Решение прямой задачи представлено следующими симплекс-таблицами: бп icon3 Формулировка задачи
Транспортная задача представляет собой задачу лп, которую можно решать симплекс-методом. Однако специфическая структура условий задачи...
Решение прямой задачи представлено следующими симплекс-таблицами: бп icon3 Формулировка задачи
Транспортная задача представляет собой задачу лп, которую можно решать симплекс-методом. Однако специфическая структура условий задачи...
Решение прямой задачи представлено следующими симплекс-таблицами: бп icon3 Формулировка задачи
Транспортная задача представляет собой задачу лп, которую можно решать симплекс-методом. Однако специфическая структура условий задачи...
Решение прямой задачи представлено следующими симплекс-таблицами: бп icon2 Двойственная задача линейного программирования Двойственная задача
Между прямой и двойственной задачами существуют тесная взаимосвязь. Фактически оптимальное решение одной из задач непосредственно...
Решение прямой задачи представлено следующими симплекс-таблицами: бп icon2 Двойственная задача линейного программирования Двойственная задача
Между прямой и двойственной задачами существует тесная взаимосвязь. Фактически оптимальное решение одной из задач непосредственно...
Додайте кнопку на своєму сайті:
Документи


База даних захищена авторським правом ©zavantag.com 2000-2013
При копіюванні матеріалу обов'язкове зазначення активного посилання відкритою для індексації.
звернутися до адміністрації
Документи