Двойственная задача линейного программирования
Пусть требуется решить задачу линейного программирования.
max( =6u1+12 u2+u3)
| (8.22)
| при условии
u1£-5;
u2£0;
u3£0;
-3 u1+0,1 u2+2 u3£-30;
2 u1+3 u2- u3£6;
ui – любое.
| (8.23)
| Как решать? И, прежде всего в условиях, когда переменные принимают произвольные значения? Одним из путей является введение дополнительных переменных vj, vn+j ≥0, j=1,…, n для замены исходных переменных uj = vj - vn+j и представления задачи к виду СЗЛП. Кроме того, требуется ввести новые переменные для преобразования неравенств в равенства Размерность задачи, а следовательно, и длительность расчетов резко возрастают.
Другим подходом является решение исходной ЗЛП через так называемую двойственную задачу линейного программирования (ДЗЛП).
Двойственностьв математическом программировании (МП), как и вообще в математике, играет фундаментальную роль. Она выступает в качестве краеугольного камня соответствующих теорий, порождает арсенал конструктивных средств анализа математических моделей, построения эффективных алгоритмов решения задач и формальной оценки этой эффективности.
Если - некоторый исходный математический объект (модель), то двойственный объект , вообще говоря, выступает как некий внешний по отношению к объект ''наблюдения'' за . Содержание двойственности в МП состоит в сопоставлении исходной задаче другой задачи , формируемой по определенным правилам и называемой двойственной. Эти задачи связаны математически содержательными соотношениями, позволяющими, например, получить оценки критериальной эффективности всех параметров, формирующих основную задачу; свести решение основной оптимизационной задачи к решению некоторой системы неравенств; сформировать в изящной форме условия оптимальности и т.д.
Если задача МП (или ЛП) - результат моделирования конкретной экономической (производственной) ситуации, то двойственность и та информация, которую двойственность порождает, позволяют провести глубокий анализ (экономико-математический анализ) моделируемого объекта, выявить узкие места, тенденции динамики объекта, выразив эти факторы в количественной форме. Профессионально сделанные пакеты прикладных программ, решающие задачи МП или ЛП, обычно выдают в форме удобных распечаток всю совокупность информации, необходимую для экономико-математического анализа.
Теорема о двойственности: Каждой ЗЛП можно сопоставить точно одну двойственную ей (ДЗЛП) и решение одной из задач определяет решение другой.
Исходная ЗЛП является двойственной по отношению к ДЗЛП, т.е. понятие двойственности является симметричным
Структуру двойственной задачи линейного программирования лучше всего видеть на примере симметричной ДЗЛП.
| ЗЛП
| ДЗЛП
| Функционал
| Min( )
| Max( )
| Ограничения
| ≥ (m уравнений)
| ; (n уравнений)
| Переменные
| ³0 (n переменных)
| (m переменных)
|
В ЗЛП столько переменных, сколько неравенств среди ограничений в ДЗЛП и столько ограничений, сколько переменных в ДЗЛП, каждому ограничению одной задачи соответствует переменная другой. Сравнивая структуры нетрудно видеть, что вектора и поменялись местами. Матрица А в системе ограничений транспонировалась, знаки неравенств поменялись на противоположные, а функция min() преобразовалась в max().
В более общем виде, при наличии ограничений типа «равенство» связь задач задается следующим образом:
| ЗЛП
| ДЗЛП
| Функционал
| Min( )
| Max
| Ограничения
| ..(k уравнений)
; (m уравнений)
| ; (n уравнений)
; (r уравнений)
| Переменные
| ³0 (n переменных)
– любое (r переменных)
| ³0 (k переменных)
- любое (m переменных)
| Структурную взаимосвязь переменных и ограничений можно представить в не совсем строгом, но понятном для восприятия виде. Исходная ЗЛП может быть представлена следующей матричной структурой:
|
|
| | |
|
| ³0
| - любое
| | |
| Размерность
| n
| r
|
| Θ
|
| k
| A11
| A12
|
| ≥
|
| m
| A21
| A22
|
| =
|
| Транспонированием структуры относительно матрицы ограничений и заменой переменных получаем структуру двойственной задачи ЛП.
|
|
| | |
|
|
| - любое
| | |
| Размерность
| k
| m
|
| Θ
|
| n
| At11
| At21
|
| ≤
|
| r
| At12
| At22
|
| =
|
| Согласно теореме двойственности если разрешима одна задача, то разрешима и другая; оптимальные значения целевых функций при этом одинаковы
=
Для получения решения исходной задачи ЛП при известном решении двойственной необходимо принять во внимание, что если j-я компонента вектора переменных ДЗЛПне равна нулю, тоj-е уравнение системы ограничений основной ЗЛП обращается встрогое равенство, (ЗЛП является двойственной по отношению к ДЗЛП). Как правило, полученная система уравнений является достаточной для определения решения основной ЗЛП. Дополнительными (если это потребуется) к полученной системе уравнений являются уравнения
; ,
которые и отражают описанные выше соотношения: ограничение - равенство (скобка равна нулю) – соответствующая двойственная переменная не равна нулю и наоборот, а также равенство оптимальных целевых функций основной и двойственной задач ЛП .
Важные частные случаи
Z2 = 0 ; U1 = 0
| СЗЛП
| ДЗЛП
| Функционал
| Min
| Max
| Ограничения
| ; (m уравнений)
| (n уравнений)
| Переменные
| (n переменных)
| - любое (m переменных)
|
= 0 ; = 0 - представленная выше симметричная структура двойственности
= 0 ; = 0
| ЗЛП
| ДЗЛП
| Функционал
| Min
| Max
| Ограничения
| (k уравнений)
| ; (r уравнений)
| Переменные
| – любое (r переменных)
| ³0 (k переменных)
| Замечание: ДЗЛП имеет вид СЗЛП, поскольку процедура максимизации легко, умножением целевой функции на (-1), преобразуется в минимизацию.
Теоремы двойственности
· Если рассмотреть задачу, двойственную к двойственной задаче, то снова придем к исходной задаче.
· Если в одной из задач допустимая область пуста, то в другой целевая функция не ограничена снизу (при минимизации) или сверху (при максимизации)
· Если первичная задача имеет допустимую точку Х, а двойственная - допустимую точку U, то обе задачи разрешимы и G(U)≤ max G= min Q≤Q(Z)
· Если для двух допустимых значений G(U)= Q(Z), то U и Z - оптимальные решения,
Не нашли, что искали? Воспользуйтесь поиском по сайту:
©2015 - 2024 stydopedia.ru Все материалы защищены законодательством РФ.
|