 |
Общие правила составления двойственных задач
|
|
|
|
При составлении двойственных задач используют следующие правила.
Правило 1. Во всех ограничениях исходной задачи свободные члены должны находиться в правой части, а члены с неизвестными — в левой.
Правило 2. Ограничения-неравенства исходной задачи должны быть записаны так, чтобы знаки неравенств у них были направлены в одну сторону.
Правило 3. Если знаки неравенств в ограничениях исходной задачи «≤», то целевая функция F (X)= c 0 + c 1 x 1 + с 2 х 2+... + спхп должна максимизироваться, а если «≥», то минимизироваться.
Правило 4. Каждому ограничению исходной задачи соответствует неизвестное в двойственной задаче; при этом неизвестное, отвечающее ограничению-неравенству, должно удовлетворять условию неотрицательности, а неизвестное, отвечающее ограничению-равенству, может быть любого знака.
Правило 5. Целевая функция двойственной задачи имеет вид
Z (Y) = c 0 + b 1 y 1 +... + bmym, где c 0 ―свободный член целевой функции F (X)исходной задачи; b 1,..., bт — свободные члены в ограничениях исходной задачи, при этом bi ― свободный член именно того ограничения, которому соответствует неизвестная yi; y 1, у 2 ,..., ут — неизвестные в двойственной задаче.
Правило 6. Целевая функция Z (Y)двойственной задачи должна оптимизироваться противоположным по сравнению с F (X)образом, т.е. если F (X) → max, то Z (Y) → min, и если F (X)→min, то Z (Y)→ max.
Правило 7. Каждому неизвестному xj, j= 1, 2,..., п исходной задачи соответствует ограничение в двойственной задаче. Совокупность этих п ограничений (вместе с условиями неотрицательности неизвестных yi,соответствующих ограничениям-неравенствам исходной задачи) образует систему ограничений двойственной задачи. Все ограничения двойственной задачи имеют вид неравенств, свободные члены которых находятся в правых частях, а члены с неизвестными y 1, y 2,..., ут — в левых. Все знаки неравенств имеют вид «≥», если Z (Y)→min, и «≤», если Z (Y)→max.
|
|
|
Коэффициенты, с которыми неизвестные y 1, y 2,..., ут входят в ограничение, соответствующее неизвестному хj, совпадают с коэффициентами при этом неизвестном хj в ограничениях исходной задачи, а именно: коэффициент при yi совпадает с тем коэффициентом при хj, с которым хj входит в ограничение исходной задачи, соответствующее неизвестному уi.
Пример 5. Составить задачу, двойственную к данной
F (X) = х 1+ 4 х 2 + 3 х 3 → min,
Решение. Умножим первое ограничение-неравенство на -1. Задача примет вид исходной задачи симметричной пары двойственных задач:
F (X) = х 1+ 4 х 2 + 3 х 3 → min,
Умножим правые части ограничений на соответствующие переменные двойственной задачи и сложим их, получим целевую функции*
Z (Y)= - 10 у 1 + 6 у 2 + 12 у 3→ max.
Функция Z (Y)максимизируется, так как целевая функций исходной задачи минимизируется.
Умножаем коэффициенты при х 1 на соответствующие переменные двойственной задачи и складываем их: - 1 у 1 + 2 у 2+1 у 3.Данная сумма меньше или равна коэффициенту при х 1в целевой функции:
- 1 у 1 + 2 у 2+1 у 3≤1.
Неравенство имеет вид «≤», потому что целевая функция двойственной задачи максимизируется. Аналогично составляются еще два ограничения двойственной задачи (соответствуют переменным х 2, х 3):
- 1 у 1-1 у 2 + 2 у 3≤4,
-1 у 1 + 3 у 3 ≤3.
Все переменные двойственной задачи удовлетворяют условию неотрицательности, потому что все ограничения исходной задачи неравенства.
Окончательно двойственная задача имеет вид
Z (Y)= - 10 у 1 + 6 у 2 + 12 у 3→ max,
Пример 6. Составить задачу, двойственную к данной
F (X) = х 1- х 2 - 2 х 3+3 х 4 → min,
Решение. Данная задача имеет вид исходной задачи второй несимметричной пары двойственных задач. Запишем двойственную задачу
|
|
|
Z (Y)= 7 у 1 + 10 у 2→ max,
Переменные у 1, у 2могут не удовлетворять условию неотрицательности, так как они соответствуют ограничениям-равенствам исходной задачи.
Пример 7. Составить задачу, двойственную к данной
F (X) = 3- 2 х 1 + х 3 → min,
Решение. Используем общие правила составления двойственных задач. Умножим ограничения-неравенства на -1, так как в задаче на минимум они должны иметь вид «≥» (см. правило 3). Исходная задача запишется в виде
F (X) = 3- 2 х 1 + х 3 → min,
Составим двойственную задачу: Z (Y)=3 - 3 у 1 + 5 у 2- 8 у 3+ 6 у 4 → max,
Неизвестная у 4,соответствующая ограничению-равенству, может быть любого знака (см. правило 4).
|
|
|
