Найти двойственные переменные с помощью комплементарности

Предмет: Математика
Раздел: Линейное программирование (прямая и двойственная задачи)

Дана задача линейного программирования:

F = x_1 \rightarrow \max

при условиях:

 \begin{cases} x_1 - 2x_2 \leq 0 \ - x_1 + x_2 \leq 1 \ x_1 + x_2 \leq 1 \ x_1 \geq 0, \quad x_2 \geq 0 \end{cases} 

Шаг 1. Построим двойственную задачу

Прямая задача (P) записана в канонической форме для максимизации. Её двойственная задача (D) будет задачей на минимизацию.

Обозначим переменные двойственной задачи как y_1, y_2, y_3 — по числу ограничений прямой задачи.

Целевая функция двойственной задачи:

Z = y_2 + y_3 \rightarrow \min

(правая часть ограничений прямой задачи: 0, 1, 1)

Ограничения двойственной задачи формируются по коэффициентам при x_1 и x_2 в прямой задаче:

 \begin{cases} y_1 - y_2 + y_3 \geq 1 \quad \text{(по } x_1 \text{)} \ -2y_1 + y_2 + y_3 \geq 0 \quad \text{(по } x_2 \text{)} \ y_1, y_2, y_3 \geq 0 \end{cases} 

Шаг 2. Решение прямой задачи графически или симплекс-методом

Рассмотрим систему ограничений:

 \begin{cases} x_1 - 2x_2 \leq 0 \quad \text{(1)} \ - x_1 + x_2 \leq 1 \quad \text{(2)} \ x_1 + x_2 \leq 1 \quad \text{(3)} \ x_1 \geq 0, \quad x_2 \geq 0 \quad \text{(4)} \end{cases} 

Построим допустимую область и найдём вершины пересечений:

1. Из (1): x_1 \leq 2x_2
2. Из (2): x_1 \geq x_2 - 1
3. Из (3): x_1 \leq 1 - x_2

Найдём точки пересечения:

• Пересечение (1) и (2):  \begin{cases} x_1 = 2x_2 \ x_1 = x_2 - 1 \end{cases} \Rightarrow 2x_2 = x_2 - 1 \Rightarrow x_2 = -1 \Rightarrow x_1 = -2  — не подходит (отрицательные значения)

• Пересечение (1) и (3):  \begin{cases} x_1 = 2x_2 \ x_1 = 1 - x_2 \end{cases} \Rightarrow 2x_2 = 1 - x_2 \Rightarrow 3x_2 = 1 \Rightarrow x_2 = \frac{1}{3}, x_1 = \frac{2}{3} 

• Пересечение (2) и (3):  \begin{cases} x_1 = x_2 - 1 \ x_1 = 1 - x_2 \end{cases} \Rightarrow x_2 - 1 = 1 - x_2 \Rightarrow 2x_2 = 2 \Rightarrow x_2 = 1, x_1 = 0 

• Пересечение (1) и оси: при x_2 = 0 \Rightarrow x_1 = 0

Проверим допустимые вершины:

1. (0, 0)
2. (0, 1)
3. (\frac{2}{3}, \frac{1}{3})

Подставим в целевую функцию F = x_1:

• F(0, 0) = 0
• F(0, 1) = 0
• F(\frac{2}{3}, \frac{1}{3}) = \frac{2}{3}

Оптимум достигается в точке (x_1 = \frac{2}{3}, x_2 = \frac{1}{3})

Шаг 3. Найдём двойственное решение

Используя теорему двойственности: если в прямой задаче оптимум F = \frac{2}{3}, то в двойственной Z = \frac{2}{3}.

Найдём двойственные переменные y_1, y_2, y_3 с помощью комплементарности:

Условия комплементарности:

• Если ограничение активно (выполнено как равенство), соответствующая двойственная переменная может быть ненулевой.
• Если неактивно — двойственная переменная = 0.

Проверим активные ограничения в точке (\frac{2}{3}, \frac{1}{3}):

1. x_1 - 2x_2 = \frac{2}{3} - \frac{2}{3} = 0 — активно → y_1 \neq 0
2. -x_1 + x_2 = -\frac{2}{3} + \frac{1}{3} = -\frac{1}{3} < 1 — не активно → y_2 = 0
3. x_1 + x_2 = \frac{2}{3} + \frac{1}{3} = 1 — активно → y_3 \neq 0

Система:

 \begin{cases} y_1 + y_3 = 1 \ -2y_1 + y_3 = 0 \end{cases} \Rightarrow \begin{cases} y_3 = 2y_1 \ y_1 + 2y_1 = 1 \Rightarrow 3y_1 = 1 \Rightarrow y_1 = \frac{1}{3}, y_3 = \frac{2}{3} \end{cases} 

Ответ:

• 3x_1 = 3 \cdot \frac{2}{3} = 2
• 3x_2 = 3 \cdot \frac{1}{3} = 1
• 3y_1 = 3 \cdot \frac{1}{3} = 1
• 3y_2 = 3 \cdot 0 = 0
• 3y_3 = 3 \cdot \frac{2}{3} = 2
• 3F = 3Z = 3 \cdot \frac{2}{3} = 2

✅ Заполненные поля:

• 3x_1 = 2
• 3x_2 = 1
• 3y_1 = 1
• 3y_2 = 0
• 3y_3 = 2
• 3F = 3Z = 2