Т.4.4.1 (о допустимых решениях прямой и двойственной задач)

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

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

Если Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru - некоторый исходный математический объект (модель), то двойственный объект Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru , вообще говоря, выступает как некий внешний по отношению к Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru объект ''наблюдения'' за Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru . Двойственность в зависимости от ее конкретного содержания, определяемого конкретной математической дисциплиной (алгебра, функциональный анализ, выпуклый анализ, теория оптимального управления и т.д.), несет в себе следы специфики соответствующей дисциплины. Но именно это обстоятельство и превращает двойственность в математике в здание хотя в определенном смысле и единой, но гармонически организованной и насыщенной архитектуры.

Содержание двойственности в линейном программировании состоит в сопоставлении исходной задаче C другой задачи Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru , формируемой поопределенным правилам и называемой двойственной. Эти задачи связаны математически содержательными соотношениями, позволяющими, например, получить оценки критериальной эффективности всех параметров, формирующих задачу C; свести решение оптимизационной задачи к решению некоторой системы неравенств; сформировать в изящной форме условия оптимальности; оценить скорость сходимости итерационных процессов для задачи C и т.д.

Если задача МП (или ЛП) - результат моделирования конкретной экономической (производственной) ситуации, то двойственность и та информация, которую двойственность порождает, позволяют провести глубокий анализ моделируемой ситуации (моделируемого объекта), выявить узкие места, тенденции динамики объекта, выразив эти факторы в количественной форме. Затакого рода анализом закрепился термин - экономико-математический анализ. Профессионально сделанные пакеты прикладных программ (ППП), решающие задачи МП или ЛП, обычно выдают в форме удобных распечаток всю совокупность информации, необходимую для экономико-математического анализа. Это дает экономистам хорошие возможности для оценки состояния экономических (или производственных) систем и идентификации параметров управления.

Прямая задача ЛП в стандартной форме записывается следующим образом:
Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru
при ограничениях:
Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru
Заметим, что в состав n переменных включаются также избыточные и остаточные переменные.

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


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


Двойственная задача получается путем симметричного структурного преобразования условий прямой задачи в соответствии со следующими правилами:

1. число переменных в дв. зад. = числу нетривиальных ограничений пр. зад., при этом 1я двойственная переменная y1 соответствует 1му ограничению пр. зад, у2 соответствует 2-му ограничению пр.зад. и т.д. Если в 1ом ограничении пр. зад. знак ≤, то у1≥0, если знак ≥, то у1≤0, если знак =, то у1 Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru (знак у противоположен знаку соответствующего ограничения).

2. целевая функция дв. зад. всегда min. При этом g (y)=byàmin, где у- вектор переменных дв. зад, b- вектор правых частей ограничений пр. зад.

3. в дв. зад. число нетривиальных ограничений в точности равно числу переменных в пр. зад. Вектор правых частей нетривиальных ограничений дв. зад. совпадает с вектором скоэффициентов целевой функции пр. зад. Матрица ограничений дв. зад. = транспонированной матрице ограничений пр. зад. 1-е ограничение дв. зад. соответствует переменной х1, 2e-х2 и т.д. Знак переменных х переходит в знак двойственных ограничений, т.е. если х1≥0, то в 1ом ограничении дв. зад. знак ≥, если х1≤0, то знак ≤, если х1 Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru , то знак =.

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

f(x)=c1x1+c2x2+…+cnxn → max g(y)=b1y1+b2y2+…+bnyn → min

Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru

xi≤0 (i=1,2….m)

Из указанных правил построения двойственной задачи следует, что она имеет m переменных (y1, y2, …, ym) и n ограничений (соответствующих n переменным прямой задачи x1, x2, …, xn).
Рассмотрим теперь, как формируются остальные условия двойственной задачи: направление оптимизации, ограничения и знаки двойственных переменных. Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru

Если решать прямую задачу очень сложно, то проще решить двойственную задачу. И имея оптимальную симплекс-таблицу двойственной задачи можно получить оптимальную симплекс-таблицу прямой задачи, не решая её.

Пример 1.(у Ани)

ОСНОВНЫЕ ТЕОРЕМЫ ДВОЙСТВЕННОСТИ

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

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

Если Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru - некоторый исходный математический объект (модель), то двойственный объект Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru , вообще говоря, выступает как некий внешний по отношению к Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru объект ''наблюдения'' за Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru . Двойственность в зависимости от ее конкретного содержания, определяемого конкретной математической дисциплиной (алгебра, функциональный анализ, выпуклый анализ, теория оптимального управления и т.д.), несет в себе следы специфики соответствующей дисциплины. Но именно это обстоятельство и превращает двойственность в математике в здание хотя в определенном смысле и единой, но гармонически организованной и насыщенной архитектуры.

Содержание двойственности в линейном программировании состоит в сопоставлении исходной задаче C другой задачи Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru , формируемой поопределенным правилам и называемой двойственной. Эти задачи связаны математически содержательными соотношениями, позволяющими, например, получить оценки критериальной эффективности всех параметров, формирующих задачу C; свести решение оптимизационной задачи к решению некоторой системы неравенств; сформировать в изящной форме условия оптимальности; оценить скорость сходимости итерационных процессов для задачи C и т.д.

Если задача МП (или ЛП) - результат моделирования конкретной экономической (производственной) ситуации, то двойственность и та информация, которую двойственность порождает, позволяют провести глубокий анализ моделируемой ситуации (моделируемого объекта), выявить узкие места, тенденции динамики объекта, выразив эти факторы в количественной форме. Затакого рода анализом закрепился термин - экономико-математический анализ. Профессионально сделанные пакеты прикладных программ (ППП), решающие задачи МП или ЛП, обычно выдают в форме удобных распечаток всю совокупность информации, необходимую для экономико-математического анализа. Это дает экономистам хорошие возможности для оценки состояния экономических (или производственных) систем и идентификации параметров управления.

Прямая задача ЛП в стандартной форме записывается следующим образом:
Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru
при ограничениях:
Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru
Заметим, что в состав n переменных включаются также избыточные и остаточные переменные.

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


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


Двойственная задача получается путем симметричного структурного преобразования условий прямой задачи в соответствии со следующими правилами:

1. число переменных в дв. зад. = числу нетривиальных ограничений пр. зад., при этом 1я двойственная переменная y1 соответствует 1му ограничению пр. зад, у2 соответствует 2-му ограничению пр.зад. и т.д. Если в 1ом ограничении пр. зад. знак ≤, то у1≥0, если знак ≥, то у1≤0, если знак =, то у1 Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru (знак у противоположен знаку соответствующего ограничения).

2. целевая функция дв. зад. всегда min. При этом g (y)=byàmin, где у- вектор переменных дв. зад, b- вектор правых частей ограничений пр. зад.

3. в дв. зад. число нетривиальных ограничений в точности равно числу переменных в пр. зад. Вектор правых частей нетривиальных ограничений дв. зад. совпадает с вектором скоэффициентов целевой функции пр. зад. Матрица ограничений дв. зад. = транспонированной матрице ограничений пр. зад. 1-е ограничение дв. зад. соответствует переменной х1, 2e-х2 и т.д. Знак переменных х переходит в знак двойственных ограничений, т.е. если х1≥0, то в 1ом ограничении дв. зад. знак ≥, если х1≤0, то знак ≤, если х1 Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru , то знак =.

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

f(x)=c1x1+c2x2+…+cnxn → max g(y)=b1y1+b2y2+…+bnyn → min

Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru

xi≤0 (i=1,2….m)

Из указанных правил построения двойственной задачи следует, что она имеет m переменных (y1, y2, …, ym) и n ограничений (соответствующих n переменным прямой задачи x1, x2, …, xn).
Рассмотрим теперь, как формируются остальные условия двойственной задачи: направление оптимизации, ограничения и знаки двойственных переменных. Т.4.4.1 (о допустимых решениях прямой и двойственной задач) - student2.ru

Если решать прямую задачу очень сложно, то проще решить двойственную задачу. И имея оптимальную симплекс-таблицу двойственной задачи можно получить оптимальную симплекс-таблицу прямой задачи, не решая её.

Пример 1.(у Ани)

ОСНОВНЫЕ ТЕОРЕМЫ ДВОЙСТВЕННОСТИ

Т.4.4.1 (о допустимых решениях прямой и двойственной задач)

Если х – любое допустимое решение пр. зад., а у – любое допустимое решение дв. зад., то f (x)≤g (y).

Док-во:

х– допустимое решение пр. зад., значит х удовлетворяет ограничениям пр. зад.

Ах≤b

x≥0

y –допустимое решение дв. зад., значитyудовлетворяет ограничениям дв.зад.

АTy≥c

y≥0

f(x)=cx≤(ATy)x=(Ax)y≤by=g(y)( Непосредственной проверкой, т.е. вычислением левой и правой частей устанавливаем равенство (Ах)у= х (АTу))

Наши рекомендации