2 Двойственная задача линейного программирования Двойственная задача icon

2 Двойственная задача линейного программирования Двойственная задача




Скачати 56.08 Kb.
Назва2 Двойственная задача линейного программирования Двойственная задача
Дата20.09.2012
Розмір56.08 Kb.
ТипЗадача

2.6. Двойственная задача линейного программирования


Двойственная задача – это вспомогательная задача линейного программирования, которая получается непосредственно из исходной, прямой задачи. Между прямой и двойственной задачами существуют тесная взаимосвязь. Фактически оптимальное решение одной из задач непосредственно ( без каких-либо дополнительных вычислений ) можно получить из оптимальной симплекс-таблицы другой таблицы.

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

max n

min L = ∑ cj•xj ,

j=1


при ограничениях n

∑ аij•хj = bi , i=1,2,…,m,

j=1

xj ≥0, j=1,2,…,n.

Необходимо отметить, что в состав переменных хj , j=1,n входят дополнительные переменные, которые необходимы были для написания ограничений в виде равенств. Для наглядности формулировки двойственной задачи, представим прямую задачу в виде схемы (рис. 2.5.)


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








Коэф. левых частей ограничений двойственной задачи

x1 x2 хj … xn

Правые части ограничений двойственной задачи

c1

с2



cj



cn




a11

a21

...

am1

a12

a22

...

am2









a1j

a2j

...

amj









a1n

a2n

...

amn

b1

b2



bm




y1

y2



ym

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




j-ограничение Коэффициенты целевой

двойственной задачи функции двойственной задачи

Рис.2.5


Из приведенной схемы видно, что двойственная задача получается из прямой в соответствии со следующими правилами:

  1. каждому ограничению прямой задачи соответствует переменная yj двойственной задачи;

  2. каждой переменной прямой задачи соответствует ограничение двойственной задачи;

  3. коэффициенты при переменной хj , фигурирующие в ограничениях прямой задачи, становятся коэффициентами левой части j-го ограничения двойственной задачи. Коэффициент cj, фигурирующий при той же переменной в целевой функции прямой задачи, становится постоянной правой части этого же ограничения двойственной задачи.

Другие правила получения двойственной задачи из прямой приведены в табл.2.2.


Табл.2.2.

Прямая задача

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

Целевая функция

Целевая функция

Ограничения

Переменные

Максимизация

Минимизация



Не ограничены в знаке

Минимизация

Максимизация



Не ограничены в знаке


Проиллюстрируем использование приведенных выше правил для построения двойственной задачи.

Пример 1. Прямая задача


мах L = 6х1 + 10х2 + х3 ;

1 + 4х2  3х3 ≤ 4 ;

х1 + 5х2 + 4х3 = 7;

х12 , х3 ≥ 0.


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


max L = 6х1 + 10х2 + х3 + 0 ∙ х4 ;

1 + 4х2  3х3 + х4 = 4 ;

х1 + 5х2 + 4х3 + 0 ∙ х4= 7;

х12 , х3 , х4 ≥ 0.


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


min Ĺ = 4y1 + 7y2 ;

2y1 + y2 ≥ 6;

4y1 + 5y2 ≥ 10;

-3y1 + 4y2 ≥ 1;

y1 + 0∙ y2 ≥ 0 (отсюда y1 ≥ 0);

y1 ,y2 не ограничены в знаке.

Заметим, что условие y1 ≥ 0 является более жестким, чем условие неограниченности y1 в знаке, поэтому в дальнейшем, условие «y1 не ограничено в знаке» убирается .

Пример 2. Прямая задача

min L = 4х1 + 5х2 ;

х1  3х2  3;

1 + 5х2 ≥ 1;

х12 ≥ 0.

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

min L = 4х1 + 5х2 + 0∙ х3 + 0∙ х4;

 х1 + 3х2 + х3 = 3;

1 + 5х2  х4 = 1;

х12 , х3 , х4 ≥ 0.

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


max Ĺ = 3y1 + y2 ;

y1 + 2y2  4;

3y1 + 5y2 5;

y1 + 0∙ y2  0 (y1  0) ;

0∙ y1  y2  0 (y2 ≥ 0);

y1 ,y2 не ограничены в знаке.

Два последних ограничения исключают условие неограниченности y1 и y2 в знаке.

Пример 3. Прямая задача


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

х1 + х2  6;

3х1 + 2х2 ≥ 5;

1 + 5х2 = 4;

х1 ≥ 0, х2 - не ограничен в знаке.


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

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

х1 + х2  х2 + х3 = 6;

3х1 + 2х2  2х2  х4 = 5;

1 + 5х2  5х2 = 4;

х1 , х2 , х2 ≥ 0.


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


min Ĺ = 6y1 + 5y2 + 4y3 ;

y1  3y2 + 4y3 ≥ 1;

y1 + 2y2 + 5y3 ≥ 3;

y1 + 2y2 + 5y3  3;

y1 ≥ 0;

y2  0.

y3 - не ограничен в знаке.

Схожі:

2 Двойственная задача линейного программирования Двойственная задача icon2 Двойственная задача линейного программирования Двойственная задача
Между прямой и двойственной задачами существует тесная взаимосвязь. Фактически оптимальное решение одной из задач непосредственно...
2 Двойственная задача линейного программирования Двойственная задача icon6 Задача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
2 Двойственная задача линейного программирования Двойственная задача icon6 Задача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
2 Двойственная задача линейного программирования Двойственная задача iconЗадача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
2 Двойственная задача линейного программирования Двойственная задача iconЗадача динамического программирования. Общий случай
Но в отличии от линейного программирования динамическое программирование не сводится к какой-либо стандартной вычислительной процедуре;...
2 Двойственная задача линейного программирования Двойственная задача iconЗадача прогноз задача ефект ставка -1 задача ефект ставка -2 задача опт портфель графіки
По акціях корпорацій виплачується дивіденд 5 г о на одну акцію. Продажна ціна акцій на фондовій біржі становила 100 г о
2 Двойственная задача линейного программирования Двойственная задача iconПлоская задача теории упругости
Плоская задача включает в себя плоскую деформацию и обобщенное плоское напряженное состояние
2 Двойственная задача линейного программирования Двойственная задача iconЗадача №2, 11 клас
Задача №2, 11 клас. Нехай маса мавпи m, а момент інерції барабана I. Коли мавпа рухається разом з барабаном, механічну енергію системи...
2 Двойственная задача линейного программирования Двойственная задача icon3. Транспортна задача лінійного програмування Формулювання задачі
Транспортна задача представляє собою задачу лп, котру можно вирішувати симплекс-методом. Але специфічна структура умов задачі дозволяє...
2 Двойственная задача линейного программирования Двойственная задача icon3. Транспортна задача лінійного програмування Формолювання задачі
Транспортна задача представляє собою задачу лп, котру можно вирішувати симплекс-методом. Але специфічна структура умов задачі дозволяє...
Додайте кнопку на своєму сайті:
Документи


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