Примеры построения двойственных задач

Задача 3.1. Построить двойственную задачу к заданной модели линейного программирования.

Исходная задача:

max Z = 3 x₁ + x₂ + 2 x₃

x₁ + 3 x₂ + 5 x₃ 9

2 x₁ + 2 x₂ + x₃ 5

x_1, x_2, x₃ ³0.

Двойственная задача имеет вид:

min f = 9 y₁ + 5 y₂

y₁ + 2 y₂ ³ 3

3 y₁ + 2 y₂ ³ 1

5 y₁ + y₂ ³ 2

y₁ ³0, y₂ ³ 0.

Задача 3.2. Построить двойственную задачу к модели линейного программирования:

max Z = 2 x₁ + x₂ + 3 x₃

-x₁ + 3 x₂ - 5 x₃ = 12

2 x₁ - 2 x₂ + 4 x₃ = 4

3 x₁ + x₂ + x₃ = 18

x_1, x_2, x₃ ³0.

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

min f = 12 y₁ + 24 y₂ + 18 y₃

-y₁ + 2 y₂ + 3 y₃ ³ 2

3 y₁ - y₂ + y₃ ³ 1

-5 y₁ + 4 y₂ + y₃ ³ 3.

Задача 3.3. Построить двойственную модель к задаче 2.2. Выписать ее решение из оптимальной симплекс-таблицы задачи 2.2.

Исходная задача имеет вид:

max Z = 25 x₁ + 50 x₂ + 40 x₃

25 x₁ + 50 x₂ ³ 21000

40 x₃ ³ 12000

x₁ + x₂ + x₃ 1000

10 x₁ + x₂ +25 x₃ 15760

x_1, x_2, x₃ ³0.

В результате решения данной задачи была получена следующая симплекс-таблица:

Таблица 3.2 – Оптимальная симплекс-таблица исходной задачи

Базис	B	X1	X2	X3	X4	X5	X6	X7
X2						0.02
X3						-0.03
X4						1.25
X7						0.60	-1
M+1						0.25

Оптимальный план исходной задачи:

, , , ,

, ,

.

Перейдем к построению двойственной задачи. Предварительно приведем два первых ограничения к неравенствам со знаком « ». Для этого умножим левые и правые их части на «-1».

max Z = 25 x₁ + 50 x₂ + 40 x₃

-25 x₁ – 50 x₂ -21000

-40 x₃ -12000

x₁ + x₂ + x₃ 1000

10 x₁ + x₂ +25 x₃ 15760.

x_1, x_2, x₃ ³0.

Двойственная задача будет иметь вид:

min f = -21000 y₁ -12000 y₂ + 1000 y₃ + 15760 y₄

-25 y₁ + 0 y₂ + y₃ + 10 y₄ ³ 25

-50 y₁ + 0 y₂ + y₃ + y₄ ³ 50

0 y₁ -40 y₂ + y₃ + 25 y₄ ³ 40

y₁, y₂, y₃, y₄ ³ 0.

Согласно первой теореме двойственности если прямая задача имеет оптимальное решение, то и двойственная задача также будет иметь решение. Оптимальный план двойственной задачи расположен в строке «M+1» таблицы 3.2:

, , ,

, , , ,

.

Дата добавления: 2014-11-18