Курсовая работа: Линейное программирование как метод оптимизации

5. Если переменная x_j исходной задачи (42) - (44) может принимать только лишь положительные значения, то j -е условие в системе (46) двойственной задачи (45) - (47) является неравенством вида “". Если же переменная x_j может принимать как положительные, так и отрицательные значения, то 1 - соотношение в системе представляет собой уравнение. Аналогичные связи имеют место между ограничениями (43) исходной задачи (42) - (44) и переменными двойственной задачи (45) - (47). Если i - соотношение в системе (43) исходной задачи является неравенством, то i -я переменная двойственной задачи . В противном случае переменная у_j может принимать как положительные, так и отрицательные значения.

Двойственные пары задач обычно подразделяют на симметричные и несимметричные. В симметричной паре двойственных задач ограничения (43) прямой задачи и соотношения (46) двойственной задачи являются неравенствами вида “". Таким образом, переменные обеих задач могут принимать только лишь неотрицательные значения.

Теорема двойственности.

Существующие зависимости между решениями прямой и двойственной задач характеризуются сформулированными ниже леммами и теоремами двойственности.

Лемма 1.

Если Х - некоторый план исходной задачи , a Y - произвольный план двойственной задачи , то значение целевой функции исходной задачи при плане Х всегда не превосходит значения целевой функции двойственной задачи при плане Y, т.е.

Лемма 2.

Если для некоторых планов X^* и Y^* задач , то X^* - оптимальный план исходной задачи, а Y^* - оптимальный план двойственной задачи.

Теорема 8

( первая теорема двойственности). Если одна из задач двойственной пары или , имеет оптимальный план, то и другая имеет оптимальный план и значения целевых функций задач при их оптимальных планах равны между собой, т.е.

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

Теорема 9

( вторая теорема двойственности).

План задачи и план задачи , являются оптимальными планами этих задач тогда и только тогда, когда для любого выполняется равенство

Геометрическая интерпретация двойственных задач. Если число переменных в прямой и двойственной задачах, образующих данную пару, равно двум, то, использ уя геометрическую интерпретацию задачи линейного программирования, можно легко найти решение данной пары задач. При этом имеет место один из следующих трех взаимно исключающих друг друга случаев:

1) обе задачи имеют планы;

2) планы имеет только одна задача;

3) для каждой задачи двойственной пары множество планов пусто.

а) Составить задачу двойственную к примеру 2.

б) Найти её решение любым методом.

в) Найти решение задачи 2, используя теорему двойственности.

а) Задача имеет вид:

1	1
1	2
1	3
2	1

f = 9X1 + 14X2 + 15 X3 + 10X4 → max

1	1	1	2
1	2	3	1

X1 + X2 + X3 + 2X4 ≤ 3

X1 + 2X2 + 3X3 + X4 ≤ 7

X1, X2, X3, X4 ≥ 0

Составим двойственную задачу по следующей схеме:

число переменных в дв. задаче равно числу ограничений в исходной, а число ограничений в дв. равно числу переменных в исходной;