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

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

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

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

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

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

Прямая задача ЛП в стандартной форме записывается следующим образом:

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

Заметим, что в состав n переменных включаются также избыточные и остаточные переменные.

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

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

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

 

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

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

3. в дв. зад. число нетривиальных ограничений в точности равно числу переменных в пр. зад. Вектор правых частей нетривиальных ограничений дв. зад. совпадает с вектором с коэффициентов целевой функции пр. зад. Матрица ограничений дв. зад. = транспонированной матрице ограничений пр. зад. 1-е ограничение дв. зад. соответствует переменной х₁, 2e-х₂ и т.д. Знак переменных х переходит в знак двойственных ограничений, т.е. если х₁≥0, то в 1ом ограничении дв. зад. знак ≥, если х₁≤0, то знак ≤, если х₁ , то знак =.

 

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

f(x)=c₁x₁+c₂x₂+…+c_nx_n → max g(y)=b₁y₁+b₂y₂+…+b_ny_n → min

 

 

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

 

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

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

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

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

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

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

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

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

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

Прямая задача ЛП в стандартной форме записывается следующим образом:

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

Заметим, что в состав n переменных включаются также избыточные и остаточные переменные.

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

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

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

 

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

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

3. в дв. зад. число нетривиальных ограничений в точности равно числу переменных в пр. зад. Вектор правых частей нетривиальных ограничений дв. зад. совпадает с вектором с коэффициентов целевой функции пр. зад. Матрица ограничений дв. зад. = транспонированной матрице ограничений пр. зад. 1-е ограничение дв. зад. соответствует переменной х₁, 2e-х₂ и т.д. Знак переменных х переходит в знак двойственных ограничений, т.е. если х₁≥0, то в 1ом ограничении дв. зад. знак ≥, если х₁≤0, то знак ≤, если х₁ , то знак =.

 

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

f(x)=c₁x₁+c₂x₂+…+c_nx_n → max g(y)=b₁y₁+b₂y₂+…+b_ny_n → min

 

 

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

 

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

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

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

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

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

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

Док-во:

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

Ах≤b

x≥0

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

А^Ty≥c

y≥0

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