Двойственные задачи ИТ
Найдите значения переменных и значения целевых функций основной задачи (Задача 1) и двойственной задачи (Задача 2). 
- Задача 1:
$$max f(X)=2x_1+x_2+5x_3$$;
$$\left\{\begin{array}{lr} x_1+2x_2+x_3\leq50, \\ 2x_1+4x_2+5x_3\leq80, \\ x_1+x_3\leq10; \end{array}\right.$$
$$x_i \geq0$$, $$i=\overline{1; 3}$$.
Оптимальное решение Задачи 1 (Таблица 7):
- Пара симметричных двойственных задач.
Задача 1:
$$maxf(X)=\sum_{i=1}^{n}c_ix_i$$;
$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$, $$j=\overline {1, m}$$;
$$x_i\geq 0$$, $$i=\overline{1, n}$$.
Задача 2:
$$minf(Y)=\sum_{j=1}^{m}b_jy_j$$;
$$\sum_{j=1}^{m}a_{ij}y_j\geq c_i$$, $$i=\overline{1, n}$$;
$$y_{j}\geq 0$$, $$j=\overline {1, m}$$. - Соответствие между переменными двойственных задач:
- Значения переменных $$y_i$$ равны оценкам переменных $$x_i$$:
$$y_1=\Delta_{n+1}$$, $$y_2=\Delta_{n+2}$$, …, $$y_{m+1}=\Delta_1$$, …, $$y_{m+n}=\Delta_n$$.
- Приведем модель Задачи 1 к каноническому виду:
$$max f(X)=2x_1+x_2+5x_3+0x_4+0x_5+0x_6$$;
$$\left\{\begin{array}{lr} x_1+2x_2+x_3+x_4=50, \\ 2x_1+4x_2+5x_3+x_5=80, \\ x_1+x_3+x_6=10; \end{array}\right.$$
$$x_i \geq0$$, $$i=\overline{1; 6}$$. - Основные переменные Задачи 1: $$x_1$$, $$x_2$$, $$x_3$$.
Дополнительные переменные Задачи 1: $$x_4$$, $$x_5$$, $$x_6$$.
Основные переменные двойственной задачи (Задачи 2): $$y_4$$, $$y_5$$, $$y_6$$.
Дополнительные переменные двойственной задачи (Задачи 2): $$y_1$$, $$y_2$$, $$y_3$$. - Найдем значения целевых функций (Таблица 8):
$$\Delta_0=0\cdot 25+1\cdot 7,5+5\cdot 10=57,5$$.
Найдем оценки переменных Задачи 1 (Таблица 8):
$$\Delta_2=\Delta_3=\Delta_4=0$$; $$\Delta_1=0\cdot 1,5+1\cdot (-0,75)+5\cdot 1-2=2,25$$; $$\Delta_5=0\cdot (-0,5)+1\cdot 0,25+5\cdot 1-2=0,25$$; $$\Delta_6=0\cdot 1,5+1\cdot (-1,25)+5\cdot 1-0=3,75$$.
- Найдем значения переменных двойственных задач.
Значения основных переменных Задачи 1:
$$x_1=0$$ (не в базисе), $$x_2=7,5$$ (в базисе), $$x_3=10$$ (в базисе).
Значения дополнительных переменные Задачи 1:
$$x_4=25$$ (в базисе), $$x_5=0$$ (не в базисе), $$x_6=0$$ (в базисе).
Значения основных переменных Задачи 2:
$$y_1=\Delta_4=0$$, $$y_2=\Delta_5=0,25$$, $$y_3=\Delta_6=3,75$$.
Значения дополнительных переменных Задачи 2:
$$y_4=\Delta_1=2,25$$, $$y_5=\Delta_2=0$$, $$y_6=\Delta_3=0$$. - Запишем решения двойственных задач.
Решение Задачи 1: $$X^*=(0; 7,5; 10; 25; 0; 0)$$, $$f(X^*)=57,5$$.
Решение Задачи 2: $$Y^*=(0; 0,25; 3,75; 2,25; 0; 0)$$, $$f(Y^*)=57,5$$.
- Оценка целевой функции:
$$\Delta_0=\sum_{k}C_{Bk} \cdot A_{0k}$$. - Оценки переменных:
$$\Delta_i=\sum_{k}C_{Bk} \cdot A_{ik}-c_i$$. - Оценки базисных переменных всегда равны нулю.
- Оптимальные значения целевых функций двойственных задач совпадают.
Выберите несколько вариантов ответов
Составьте задачу, двойственную к задаче:
- $$maxf(X)=3x_1+5x_2$$;
$$\left\{\begin{array}{lr} x_1-5x_2\leq1, \\ 5x_1+x_2\leq4, \\ 6x_1+x_2\leq7; \end{array}\right.$$
$$x_1\geq0$$, $$x_2\geq0$$.
Математическая модель основной задачи (Таблица 1)
- План: $$X=(x_1; x_2; . . . ; x_n)$$.
- Целевая функция:
$$max f(X)=c_1x_1+c_2x_2+…+c_nx_n$$. - Система ограничений:
$$\begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n\leq b_1, \\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n\leq b_2, \\ … \\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n\leq b_m. \end{cases}$$ - Условия неотрицательности переменных:
$$x_i\geq 0$$, $$i=\overline{1, n}$$.
- План: $$X=(y_1; y_2; . . . ; y_m)$$.
- Целевая функция:
$$min f(Y)=b_1y_1+b_2y_2+…+b_my_m$$. - Система ограничений:
$$\begin{cases} a_{11}y_1+a_{21}y_2+…+a_{m1}y_m\geq c_1, \\ a_{12}y_1+a_{22}y_2+…+a_{m2}y_m\geq c_2, \\ … \\ a_{1n}y_1+a_{2n}y_2+…+a_{mn}y_m\geq c_n. \end{cases}$$ - Условия неотрицательности переменных:
$$y_j\geq 0$$, $$j=\overline{1, m}$$.
- Основная задача:
$$maxf(X)=3x_1+5x_2$$;
$$\left\{\begin{array}{lr} x_1-5x_2\leq1, \\ 5x_1+x_2\leq4, \\ 6x_1+x_2\leq7; \end{array}\right.$$
$$x_1\geq0$$, $$x_2\geq0$$. - Составим таблицу данных и введем новые переменные $$y_1$$, $$y_2$$, …, $$y_m$$ (Таблица 2):
- Составим двойственную задачу:
$$minf(Y)=y_1+4y_2+7y_3$$;
$$\left\{\begin{array}{lr} y_1+5y_2+6y_3\geq3, \\ -5y_1+y_2+y_3\geq5; \end{array}\right.$$
$$y_j\geq0$$, $$j=\overline{1; 3}$$.
Переменные $$y_1$$, $$y_2$$, …, $$y_m$$ называют оценками ресурсов и устанавливают исходя из того, что:
- 1) общая стоимость ресурсов должна быть минимизирована;
2) в случае продажи ресурса выручка должна быть не меньше стоимости продукции при организации производства.
Выберите несколько вариантов ответов
Составьте задачу, двойственную к задаче:
- $$minf(X)=x_1+7x_2$$;
$$\left\{\begin{array}{lr} x_1+4x_2\geq3, \\ 6x_1-x_2\geq8; \end{array}\right.$$
$$x_i\geq0$$, $$i=\overline{1; 2}$$.
Пара симметричных двойственных задач (Таблица 1)
Задача 1
- План: $$X=(x_1; x_2; . . . ; x_n)$$.
- Целевая функция: $$min f(X)=c_1x_1+c_2x_2+…+c_nx_n$$.
- Система ограничений:
$$\begin{cases} a_{11}x_1+a_{12}x_2+…+a_{1n}x_n\geq b_1, \\ a_{21}x_1+a_{22}x_2+…+a_{2n}x_n\geq b_2, \\ … \\ a_{m1}x_1+a_{m2}x_2+…+a_{mn}x_n\geq b_m. \end{cases}$$ - Условия неотрицательности переменных: $$x_i\geq 0$$, $$i=\overline{1, n}$$.
- План: $$X=(y_1; y_2; . . . ; y_m)$$.
- Целевая функция: $$max f(Y)=b_1y_1+b_2y_2+…+b_my_m$$.
- Система ограничений:
$$\begin{cases} a_{11}y_1+a_{21}y_2+…+a_{m1}y_m\leq c_1, \\ a_{12}y_1+a_{22}y_2+…+a_{m2}y_m\leq c_2, \\ … \\ a_{1n}y_1+a_{2n}y_2+…+a_{mn}y_m\leq c_n. \end{cases}$$ - Условия неотрицательности переменных: $$y_j\geq 0$$, $$j=\overline{1, m}$$.
- Основная задача:
$$minf(X)=x_1+7x_2$$;
$$\left\{\begin{array}{lr} x_1+4x_2\geq3, \\ 6x_1-x_2\geq8; \end{array}\right.$$
$$x_i\geq0$$, $$i=\overline{1; 2}$$. - Составим таблицу данных (Таблица 3):
- Двойственная задача:
$$maxf(Y)=3y_1+8y_2$$;
$$\left\{\begin{array}{lr} y_1+6y_2\leq1, \\ 4y_1-y_2\leq7; \end{array}\right.$$
$$y_j\geq0$$, $$j=\overline{1; 2}$$.
- Если одна из двойственных задач имеет оптимальное решение, то и другая задача имеет оптимальное решение.
- Оптимальные значения целевых функций совпадают.
Выберите несколько вариантов ответов
Решите симплексным методом задачу:
- $$minf(X)=4x_1+x_2$$;
$$\left\{\begin{array}{lr} 2x_1+x_2\geq3, \\ 4x_1+x_2\geq4; \end{array}\right. $$
$$x_1\geq0$$, $$x_2\geq0$$.
- Пара симметричных двойственных задач
Задача 1:
$$maxf(X)=\sum_{i=1}^{n}c_ix_i$$;
$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$, $$j=\overline {1,m}$$;
$$x_i\geq 0$$, $$i=\overline{1,n}$$.
Задача 2:
$$minf(Y)=\sum_{j=1}^{m}b_jy_j$$;
$$\sum_{j=1}^{m}a_{ij}y_j\geq c_i$$, $$i=\overline{1,n}$$;
$$y_{j}\geq 0$$, $$j=\overline {1,m}$$. - Соответствие между переменными двойственных задач:
- Значения переменных $$y_i$$ равны оценкам переменных $$x_i$$:
$$y_1=\Delta_{n+1}$$, $$y_2=\Delta_{n+2}$$, …, $$y_{m+1}=\Delta_1$$, …, $$y_{m+n}=\Delta_n$$.
- Составим двойственную задачу:
$$maxf(Y)=3y_1+4y_2$$;
$$\left\{\begin{array}{lr} 2y_1+4y_2\leq4,\\ y_1+y_2\leq1; \end{array}\right.$$
$$y_j\geq0$$, $$j=\overline{1;2}$$. - Приведем математическую модель задачи к предпочтительному виду:
$$maxf(Y)=3y_1+4y_2$$;
$$\left\{\begin{array}{lr} 2y_1+4y_2+\underline{y_3}=4,\\ y_1+y_2+\underline{y_4}=1; \end{array}\right.$$
$$y_j\geq0$$, $$j=\overline{1;4}$$.
Базисные переменные: $$y_3=4$$, $$y_4=1$$.
Свободные переменные: $$y_1=0$$, $$y_2=0$$. - Составим симплексную таблицу и выполним симплексные преобразования (Таблица 6):
Поскольку все оценки переменных неотрицательные, то опорный план первой итерации оптимальный. - Найдем значения двойственных переменных:
$$x_1=\Delta_3=0$$, $$x_2=\Delta_4=4$$, $$x_3=\Delta_1=1$$, $$x_4=\Delta_2=0$$. - Запишем решение двойственной задачи: $$X^*=(0;4;1;0)$$; $$f(X^*)=4$$.
- Таблица для составления математической модели двойственной задачи:
- Данную задачу можно решать иначе.
Канонический вид:
$$minf(X)=4x_1+x_2+0 \cdot x_3+ 0 \cdot x_4$$;
$$\left\{\begin{array}{lr} 2x_1+x_2-x_3=3, \\ 4x_1+x_2-x_4=4. \end{array}\right.$$
Предпочтительный вид:
$$minf(X)=4x_1+x_2+0 \cdot x_3+ 0 \cdot x_4+M\omega_1+M\omega_2$$;
$$\left\{\begin{array}{lr} 2x_1+x_2-x_3+\underline{\omega_1}=3, \\ 4x_1+x_2-x_4+\underline{\omega_2}=4; \end{array}\right.$$
$$x_1 \geq0$$, $$i=\overline{1; 4}$$; $$\omega_1 \geq0$$, $$\omega_2 \geq0$$. - Дальше решаем $$M$$-задачу.
Выберите несколько вариантов ответов
Решите задачу, двойственную к задаче:
- $$maxf(X)=x_1+5x_2+2x_3$$;
$$\left\{\begin{array}{lr} 3x_1+x_2\leq5, \\ x_2+2x_3\leq1; \end{array}\right.$$
$$x_i \geq0$$, $$i=\overline{1; 3}$$.
- Пара симметричных двойственных задач
Задача 1:
$$maxf(X)=\sum_{i=1}^{n}c_ix_i$$;
$$\sum_{i=1}^{n}a_{ji}x_i\leq b_j$$, $$j=\overline {1, m}$$;
$$x_i\geq 0$$, $$i=\overline{1, n}$$.
Задача 2:
$$minf(Y)=\sum_{j=1}^{m}b_jy_j$$;
$$\sum_{j=1}^{m}a_{ij}y_j\geq c_i$$, $$i=\overline{1, n}$$;
$$y_{j}\geq 0$$, $$j=\overline {1, m}$$. - Соответствие между переменными двойственных задач:
- Значения переменных $$y_j$$ равны оценкам переменных $$x_i$$:
$$y_1=\Delta_{n+1}$$, $$y_2=\Delta_{n+2}$$, ..., $$y_{m+1}=\Delta_1$$, ..., $$y_{m+n}=\Delta_n$$.
- Приведем математическую модель задачи к каноническому виду:
$$maxf(X)=x_1+5x_2+2x_3$$;
$$\left\{\begin{array}{lr} 3x_1+x_2+\underline{x_4}=5,\\ x_2+2x_3+\underline{x_5}=1; \end{array}\right.$$
$$x_i \geq0$$, $$i=\overline{1;5}$$.
Базисные переменные: $$x_4=5$$, $$x_5=1$$.
Свободные переменные: $$x_1=0$$, $$x_2=0$$, $$x_3=0$$. - Составим симплексную таблицу и выполним симплексные преобразования (Таблица 4):
- Найдем значения переменных двойственной задачи:
$$y_1=\Delta_4=\frac{1}{3}$$, $$y_2=\Delta_5=4\frac{2}{3}$$, $$y_3=\Delta_1=0$$, $$y_4=\Delta_2=0$$, $$y_5=\Delta_3=7\frac{1}{3}$$. - Запишем решение двойственной задачи:
$$Y^*=\left (\frac{1}{3};4\frac{2}{3};0;0;7\frac{1}{3}\right )$$, $$f(Y^*)=6\frac{1}{3}$$.
Соответствие между переменными двойственных задач устанавливается по правилу:
- 1) основным переменным первой задачи соответствуют дополнительные переменные второй задачи;
2) дополнительным переменным первой задачи соответствуют основные переменные второй задачи.
Выберите несколько вариантов ответов