Решение варианта 6 симплекс-методом Ответ:
x ∗ = ( 29 ; 2 ; 7 ; 18 ; 17 ) \boxed{x^*=(29;\ 2;\ 7;\ 18;\ 17)} x ∗ = ( 29 ; 2 ; 7 ; 18 ; 17 ) φ max = − 713 \boxed{\varphi_{\max}=-713} φ m a x = − 713 Решим задачу полностью по алгоритму из приложенного файла «Симплекс метод1»: с построением начального базисного плана (первая фаза), вычислением потенциалов
u u u , оценок
Δ j \Delta_j Δ j , направлений
l l l , шагов
θ \theta θ и проверкой оптимальности.
1. Условие задачи Требуется найти максимум целевой функции
φ = − 16 x 1 + 35 x 2 + 12 x 3 + 5 x 4 − 29 x 5 → max \varphi=-16x_1+35x_2+12x_3+5x_4-29x_5
\rightarrow\max φ = − 16 x 1 + 35 x 2 + 12 x 3 + 5 x 4 − 29 x 5 → max при ограничениях
{ x 2 + x 3 − 5 x 4 + 2 x 5 = − 47 , x 1 + x 2 + 3 x 3 + 4 x 4 − 2 x 5 = 90 , − 3 x 1 + 5 x 2 + x 3 + 2 x 4 − 5 x 5 = − 119. \begin{cases}
x_2+x_3-5x_4+2x_5=-47,\\
x_1+x_2+3x_3+4x_4-2x_5=90,\\
-3x_1+5x_2+x_3+2x_4-5x_5=-119.
\end{cases} ⎩ ⎨ ⎧ x 2 + x 3 − 5 x 4 + 2 x 5 = − 47 , x 1 + x 2 + 3 x 3 + 4 x 4 − 2 x 5 = 90 , − 3 x 1 + 5 x 2 + x 3 + 2 x 4 − 5 x 5 = − 119. 20 ≤ x 1 ≤ 29 , − 2 ≤ x 2 ≤ 11 , − 7 ≤ x 3 ≤ 7 , 17 ≤ x 4 ≤ 30 , 14 ≤ x 5 ≤ 25. \begin{aligned}
20&\le x_1\le29,\\
-2&\le x_2\le11,\\
-7&\le x_3\le7,\\
17&\le x_4\le30,\\
14&\le x_5\le25.
\end{aligned} 20 − 2 − 7 17 14 ≤ x 1 ≤ 29 , ≤ x 2 ≤ 11 , ≤ x 3 ≤ 7 , ≤ x 4 ≤ 30 , ≤ x 5 ≤ 25. Запишем задачу в канонической форме:
c T x → max , A x = b , d ∗ ≤ x ≤ d ∗ . c^Tx\rightarrow\max,\qquad Ax=b,\qquad d_*\le x\le d^*. c T x → max , A x = b , d ∗ ≤ x ≤ d ∗ . Здесь
A = ( 0 1 1 − 5 2 1 1 3 4 − 2 − 3 5 1 2 − 5 ) , A=
\begin{pmatrix}
0&1&1&-5&2\\
1&1&3&4&-2\\
-3&5&1&2&-5
\end{pmatrix}, A = 0 1 − 3 1 1 5 1 3 1 − 5 4 2 2 − 2 − 5 , b = ( − 47 90 − 119 ) , c = ( − 16 35 12 5 − 29 ) . b=\begin{pmatrix}-47\\90\\-119\end{pmatrix},
\qquad
c=\begin{pmatrix}-16\\35\\12\\5\\-29\end{pmatrix}. b = − 47 90 − 119 , c = − 16 35 12 5 − 29 . Число переменных
n = 5 n=5 n = 5 , число уравнений
m = 3 m=3 m = 3 . Следовательно, в базисе должны находиться три переменные, а две небазисные должны принимать граничные значения.
2. Формулы симплекс-метода из файла На страницах 1–2 файла приведён алгоритм для задачи с двусторонними ограничениями на переменные.
Потенциалы u = ( u 1 , u 2 , u 3 ) u=(u_1,u_2,u_3) u = ( u 1 , u 2 , u 3 ) вычисляются из системы
a j T u = c j , j ∈ J Б . a_j^Tu=c_j,\qquad j\in J_{\text{Б}}. a j T u = c j , j ∈ J Б . Оценки небазисных переменных:
Δ j = c j − a j T u \boxed{\Delta_j=c_j-a_j^Tu} Δ j = c j − a j T u Условия оптимальности:
{ Δ j ≤ 0 , x j = d ∗ j , Δ j ≥ 0 , x j = d j ∗ . \begin{cases}
\Delta_j\le0,&x_j=d_{*j},\\
\Delta_j\ge0,&x_j=d_j^*.
\end{cases} { Δ j ≤ 0 , Δ j ≥ 0 , x j = d ∗ j , x j = d j ∗ . Если условия нарушены, выбираем входящую переменную
x j 0 x_{j_0} x j 0 и определяем направление:
l j 0 = sign Δ j 0 , l_{j_0}=\operatorname{sign}\Delta_{j_0}, l j 0 = sign Δ j 0 , A Б l Б = − a j 0 sign Δ j 0 . A_{\text{Б}}l_{\text{Б}}
=-a_{j_0}\operatorname{sign}\Delta_{j_0}. A Б l Б = − a j 0 sign Δ j 0 . Допустимые шаги определяются формулами
θ j = { d j ∗ − x j l j , l j > 0 , d ∗ j − x j l j , l j < 0 , + ∞ , l j = 0. \theta_j=
\begin{cases}
\dfrac{d_j^*-x_j}{l_j},&l_j>0,\\[6pt]
\dfrac{d_{*j}-x_j}{l_j},&l_j<0,\\[6pt]
+\infty,&l_j=0.
\end{cases} θ j = ⎩ ⎨ ⎧ l j d j ∗ − x j , l j d ∗ j − x j , + ∞ , l j > 0 , l j < 0 , l j = 0. Выбираем наименьший допустимый шаг:
θ 0 = min θ j . \theta^0=\min\theta_j. θ 0 = min θ j . Новый план:
x ˉ = x + θ 0 l \boxed{\bar x=x+\theta^0l} x ˉ = x + θ 0 l Именно эти формулы будем использовать в каждой итерации.
3. Первая фаза симплекс-метода Согласно теории на страницах 2–3 файла, сначала необходимо получить допустимый базисный план. Для этого вводятся искусственные переменные.
3.1. Построение начального плана Возьмём значения переменных на границах:
x ~ = ( 29 ; − 2 ; 7 ; 17 ; 14 ) . \widetilde x=(29;-2;7;17;14). x = ( 29 ; − 2 ; 7 ; 17 ; 14 ) . Подставим в основные ограничения и вычислим вектор невязок:
ω = b − A x ~ . \omega=b-A\widetilde x. ω = b − A x . Первая невязка:
ω 1 = − 47 − ( − 2 + 7 − 5 ⋅ 17 + 2 ⋅ 14 ) = − 47 − ( − 52 ) = 5. \begin{aligned}
\omega_1
&=-47-(-2+7-5\cdot17+2\cdot14)\\
&=-47-(-52)=5.
\end{aligned} ω 1 = − 47 − ( − 2 + 7 − 5 ⋅ 17 + 2 ⋅ 14 ) = − 47 − ( − 52 ) = 5. Вторая невязка:
ω 2 = 90 − ( 29 − 2 + 3 ⋅ 7 + 4 ⋅ 17 − 2 ⋅ 14 ) = 90 − 88 = 2. \begin{aligned}
\omega_2
&=90-(29-2+3\cdot7+4\cdot17-2\cdot14)\\
&=90-88=2.
\end{aligned} ω 2 = 90 − ( 29 − 2 + 3 ⋅ 7 + 4 ⋅ 17 − 2 ⋅ 14 ) = 90 − 88 = 2. Третья невязка:
ω 3 = − 119 − ( − 3 ⋅ 29 + 5 ( − 2 ) + 7 + 2 ⋅ 17 − 5 ⋅ 14 ) = − 119 − ( − 126 ) = 7. \begin{aligned}
\omega_3
&=-119-(-3\cdot29+5(-2)+7\\
&\qquad+2\cdot17-5\cdot14)\\
&=-119-(-126)=7.
\end{aligned} ω 3 = − 119 − ( − 3 ⋅ 29 + 5 ( − 2 ) + 7 + 2 ⋅ 17 − 5 ⋅ 14 ) = − 119 − ( − 126 ) = 7. Таким образом,
ω = ( 5 ; 2 ; 7 ) \boxed{\omega=(5;2;7)} ω = ( 5 ; 2 ; 7 ) Все невязки положительные, поэтому введём искусственные переменные
x 6 , x 7 , x 8 x_6,x_7,x_8 x 6 , x 7 , x 8 со знаком «плюс».
3.2. Вспомогательная задача Целевая функция первой фазы:
F = − x 6 − x 7 − x 8 → max \boxed{F=-x_6-x_7-x_8\rightarrow\max} F = − x 6 − x 7 − x 8 → max Система ограничений:
{ x 2 + x 3 − 5 x 4 + 2 x 5 + x 6 = − 47 , x 1 + x 2 + 3 x 3 + 4 x 4 − 2 x 5 + x 7 = 90 , − 3 x 1 + 5 x 2 + x 3 + 2 x 4 − 5 x 5 + x 8 = − 119. \begin{cases}
x_2+x_3-5x_4+2x_5+x_6=-47,\\
x_1+x_2+3x_3+4x_4-2x_5+x_7=90,\\
-3x_1+5x_2+x_3+2x_4-5x_5+x_8=-119.
\end{cases} ⎩ ⎨ ⎧ x 2 + x 3 − 5 x 4 + 2 x 5 + x 6 = − 47 , x 1 + x 2 + 3 x 3 + 4 x 4 − 2 x 5 + x 7 = 90 , − 3 x 1 + 5 x 2 + x 3 + 2 x 4 − 5 x 5 + x 8 = − 119. Ограничения на исходные переменные остаются прежними, а на искусственные накладываем:
0 ≤ x 6 ≤ 5 , 0 ≤ x 7 ≤ 2 , 0 ≤ x 8 ≤ 7. 0\le x_6\le5,\quad
0\le x_7\le2,\quad
0\le x_8\le7. 0 ≤ x 6 ≤ 5 , 0 ≤ x 7 ≤ 2 , 0 ≤ x 8 ≤ 7. Начальный базисный план:
x ( 0 ) = ( 29 ; − 2 ; 7 ; 17 ; 14 ; 5 ; 2 ; 7 ) . x^{(0)}=(29;-2;7;17;14;5;2;7). x ( 0 ) = ( 29 ; − 2 ; 7 ; 17 ; 14 ; 5 ; 2 ; 7 ) . Базисные и небазисные индексы:
J Б ( 0 ) = { 6 , 7 , 8 } , J_{\text{Б}}^{(0)}=\{6,7,8\}, J Б ( 0 ) = { 6 , 7 , 8 } , J Н ( 0 ) = { 1 , 2 , 3 , 4 , 5 } . J_{\text{Н}}^{(0)}=\{1,2,3,4,5\}. J Н ( 0 ) = { 1 , 2 , 3 , 4 , 5 } . Начальное значение вспомогательной функции:
F ( 0 ) = − 5 − 2 − 7 = − 14 . F^{(0)}=-5-2-7=\boxed{-14}. F ( 0 ) = − 5 − 2 − 7 = − 14 . 4. Первая фаза. Итерация № 1 Шаг 1. Вычисляем потенциалы Так как в базисе находятся искусственные переменные
x 6 , x 7 , x 8 x_6,x_7,x_8 x 6 , x 7 , x 8 , имеющие единичные столбцы, получаем:
u 1 = − 1 , u 2 = − 1 , u 3 = − 1. u_1=-1,\qquad u_2=-1,\qquad u_3=-1. u 1 = − 1 , u 2 = − 1 , u 3 = − 1. u = ( − 1 ; − 1 ; − 1 ) \boxed{u=(-1;-1;-1)} u = ( − 1 ; − 1 ; − 1 ) Шаг 2. Вычисляем оценки Для небазисных переменных
c j = 0 c_j=0 c j = 0 .
Δ 1 = 0 − ( u 2 − 3 u 3 ) = − 2 , \Delta_1=0-(u_2-3u_3)=-2, Δ 1 = 0 − ( u 2 − 3 u 3 ) = − 2 , Δ 2 = 0 − ( u 1 + u 2 + 5 u 3 ) = 7 , \Delta_2=0-(u_1+u_2+5u_3)=7, Δ 2 = 0 − ( u 1 + u 2 + 5 u 3 ) = 7 , Δ 3 = 0 − ( u 1 + 3 u 2 + u 3 ) = 5 , \Delta_3=0-(u_1+3u_2+u_3)=5, Δ 3 = 0 − ( u 1 + 3 u 2 + u 3 ) = 5 , Δ 4 = 0 − ( − 5 u 1 + 4 u 2 + 2 u 3 ) = 1 , \Delta_4=0-(-5u_1+4u_2+2u_3)=1, Δ 4 = 0 − ( − 5 u 1 + 4 u 2 + 2 u 3 ) = 1 , Δ 5 = 0 − ( 2 u 1 − 2 u 2 − 5 u 3 ) = − 5. \Delta_5=0-(2u_1-2u_2-5u_3)=-5. Δ 5 = 0 − ( 2 u 1 − 2 u 2 − 5 u 3 ) = − 5. Получаем таблицу оценок:
Переменная Значение Оценка x 1 x_1 x 1 29 (верхняя) − 2 -2 − 2 x 2 x_2 x 2 −2 (нижняя) 7 7 7 x 3 x_3 x 3 7 (верхняя) 5 5 5 x 4 x_4 x 4 17 (нижняя) 1 1 1 x 5 x_5 x 5 14 (нижняя) − 5 -5 − 5
Условие оптимальности нарушено для
x 1 , x 2 , x 4 x_1,x_2,x_4 x 1 , x 2 , x 4 .
Выбираем
x 2 x_2 x 2 , поскольку
Δ 2 = 7 > 0 , x 2 = − 2. \Delta_2=7>0,\qquad x_2=-2. Δ 2 = 7 > 0 , x 2 = − 2. Следовательно,
j 0 = 2 , l 2 = 1. j_0=2,\qquad l_2=1. j 0 = 2 , l 2 = 1. Шаг 3. Находим направление l l l Из условия
A l = 0 Al=0 A l = 0 для расширенной системы:
{ l 2 + l 6 = 0 , l 2 + l 7 = 0 , 5 l 2 + l 8 = 0. \begin{cases}
l_2+l_6=0,\\
l_2+l_7=0,\\
5l_2+l_8=0.
\end{cases} ⎩ ⎨ ⎧ l 2 + l 6 = 0 , l 2 + l 7 = 0 , 5 l 2 + l 8 = 0. l 6 = − 1 , l 7 = − 1 , l 8 = − 5. l_6=-1,\qquad l_7=-1,\qquad l_8=-5. l 6 = − 1 , l 7 = − 1 , l 8 = − 5. Остальные компоненты равны нулю.
l = ( 0 ; 1 ; 0 ; 0 ; 0 ; − 1 ; − 1 ; − 5 ) \boxed{l=(0;1;0;0;0;-1;-1;-5)} l = ( 0 ; 1 ; 0 ; 0 ; 0 ; − 1 ; − 1 ; − 5 ) Шаг 4. Определяем шаг θ \theta θ Для входящей переменной
x 2 x_2 x 2 :
θ 2 = 11 − ( − 2 ) 1 = 13. \theta_2=\frac{11-(-2)}1=13. θ 2 = 1 11 − ( − 2 ) = 13. Для базисных переменных:
θ 6 = 0 − 5 − 1 = 5 , \theta_6=\frac{0-5}{-1}=5, θ 6 = − 1 0 − 5 = 5 , θ 7 = 0 − 2 − 1 = 2 , \theta_7=\frac{0-2}{-1}=2, θ 7 = − 1 0 − 2 = 2 , θ 8 = 0 − 7 − 5 = 7 5 . \theta_8=\frac{0-7}{-5}=\frac75. θ 8 = − 5 0 − 7 = 5 7 . Выбираем минимум:
θ 0 = min { 13 ; 5 ; 2 ; 7 5 } . \theta^0=\min\left\{13;5;2;\frac75\right\}. θ 0 = min { 13 ; 5 ; 2 ; 5 7 } . θ 0 = 7 5 \boxed{\theta^0=\frac75} θ 0 = 5 7 Минимум достигается на
x 8 x_8 x 8 . Значит,
x 8 x_8 x 8 выходит из базиса, а
x 2 x_2 x 2 входит.
Шаг 5. Строим новый план x ( 1 ) = x ( 0 ) + 7 5 l . x^{(1)}=x^{(0)}+\frac75l. x ( 1 ) = x ( 0 ) + 5 7 l . Вычисляем изменившиеся компоненты:
x 2 = − 2 + 7 5 = − 3 5 , x_2=-2+\frac75=-\frac35, x 2 = − 2 + 5 7 = − 5 3 , x 6 = 5 − 7 5 = 18 5 , x_6=5-\frac75=\frac{18}{5}, x 6 = 5 − 5 7 = 5 18 , x 7 = 2 − 7 5 = 3 5 , x_7=2-\frac75=\frac35, x 7 = 2 − 5 7 = 5 3 , x 8 = 7 − 5 ⋅ 7 5 = 0. x_8=7-5\cdot\frac75=0. x 8 = 7 − 5 ⋅ 5 7 = 0. Итак,
x ( 1 ) = ( 29 ; − 3 5 ; 7 ; 17 ; 14 ; 18 5 ; 3 5 ; 0 ) \boxed{
x^{(1)}=
\left(29;-\frac35;7;17;14;
\frac{18}{5};\frac35;0\right)
} x ( 1 ) = ( 29 ; − 5 3 ; 7 ; 17 ; 14 ; 5 18 ; 5 3 ; 0 ) Новый базис:
J Б ( 1 ) = { 6 , 7 , 2 } . J_{\text{Б}}^{(1)}=\{6,7,2\}. J Б ( 1 ) = { 6 , 7 , 2 } . Значение функции первой фазы:
F ( 1 ) = − 18 5 − 3 5 = − 21 5 . F^{(1)}
=-\frac{18}{5}-\frac35
=\boxed{-\frac{21}{5}}. F ( 1 ) = − 5 18 − 5 3 = − 5 21 . 5. Первая фаза. Итерация № 2 Шаг 1. Вычисляем потенциалы Теперь базис
J Б = { 6 , 7 , 2 } J_{\text{Б}}=\{6,7,2\} J Б = { 6 , 7 , 2 } .
Составим систему:
{ u 1 = − 1 , u 2 = − 1 , u 1 + u 2 + 5 u 3 = 0. \begin{cases}
u_1=-1,\\
u_2=-1,\\
u_1+u_2+5u_3=0.
\end{cases} ⎩ ⎨ ⎧ u 1 = − 1 , u 2 = − 1 , u 1 + u 2 + 5 u 3 = 0. Из третьего уравнения:
− 1 − 1 + 5 u 3 = 0 , -1-1+5u_3=0, − 1 − 1 + 5 u 3 = 0 , u 3 = 2 5 . u_3=\frac25. u 3 = 5 2 . Следовательно,
u = ( − 1 ; − 1 ; 2 5 ) \boxed{u=\left(-1;-1;\frac25\right)} u = ( − 1 ; − 1 ; 5 2 ) Шаг 2. Вычисляем оценки Небазисные индексы:
J Н = { 1 , 3 , 4 , 5 , 8 } . J_{\text{Н}}=\{1,3,4,5,8\}. J Н = { 1 , 3 , 4 , 5 , 8 } . Получаем:
Δ 1 = 0 − ( u 2 − 3 u 3 ) = 11 5 , Δ 3 = 0 − ( u 1 + 3 u 2 + u 3 ) = 18 5 , Δ 4 = 0 − ( − 5 u 1 + 4 u 2 + 2 u 3 ) = − 9 5 , Δ 5 = 0 − ( 2 u 1 − 2 u 2 − 5 u 3 ) = 2 , Δ 8 = − 1 − u 3 = − 7 5 . \begin{aligned}
\Delta_1&=0-(u_2-3u_3)=\frac{11}{5},\\
\Delta_3&=0-(u_1+3u_2+u_3)=\frac{18}{5},\\
\Delta_4&=0-(-5u_1+4u_2+2u_3)=-\frac95,\\
\Delta_5&=0-(2u_1-2u_2-5u_3)=2,\\
\Delta_8&=-1-u_3=-\frac75.
\end{aligned} Δ 1 Δ 3 Δ 4 Δ 5 Δ 8 = 0 − ( u 2 − 3 u 3 ) = 5 11 , = 0 − ( u 1 + 3 u 2 + u 3 ) = 5 18 , = 0 − ( − 5 u 1 + 4 u 2 + 2 u 3 ) = − 5 9 , = 0 − ( 2 u 1 − 2 u 2 − 5 u 3 ) = 2 , = − 1 − u 3 = − 5 7 . Условие оптимальности нарушено для
x 5 x_5 x 5 :
x 5 = 14 = d ∗ 5 , Δ 5 = 2 > 0. x_5=14=d_{*5},\qquad \Delta_5=2>0. x 5 = 14 = d ∗ 5 , Δ 5 = 2 > 0. Выбираем
j 0 = 5 , l 5 = 1. j_0=5,\qquad l_5=1. j 0 = 5 , l 5 = 1. Шаг 3. Находим направление Так как небазисные переменные, кроме
x 5 x_5 x 5 , не изменяются, получаем систему для базисных компонент:
{ l 2 + 2 l 5 + l 6 = 0 , l 2 − 2 l 5 + l 7 = 0 , 5 l 2 − 5 l 5 = 0. \begin{cases}
l_2+2l_5+l_6=0,\\
l_2-2l_5+l_7=0,\\
5l_2-5l_5=0.
\end{cases} ⎩ ⎨ ⎧ l 2 + 2 l 5 + l 6 = 0 , l 2 − 2 l 5 + l 7 = 0 , 5 l 2 − 5 l 5 = 0. Подставим
l 5 = 1 l_5=1 l 5 = 1 :
{ l 2 + 2 + l 6 = 0 , l 2 − 2 + l 7 = 0 , 5 l 2 − 5 = 0. \begin{cases}
l_2+2+l_6=0,\\
l_2-2+l_7=0,\\
5l_2-5=0.
\end{cases} ⎩ ⎨ ⎧ l 2 + 2 + l 6 = 0 , l 2 − 2 + l 7 = 0 , 5 l 2 − 5 = 0. Отсюда
l 2 = 1 , l 6 = − 3 , l 7 = 1. l_2=1,\qquad l_6=-3,\qquad l_7=1. l 2 = 1 , l 6 = − 3 , l 7 = 1. Полное направление:
l = ( 0 ; 1 ; 0 ; 0 ; 1 ; − 3 ; 1 ; 0 ) \boxed{l=(0;1;0;0;1;-3;1;0)} l = ( 0 ; 1 ; 0 ; 0 ; 1 ; − 3 ; 1 ; 0 ) Шаг 4. Вычисляем θ \theta θ θ 5 = 25 − 14 1 = 11. \theta_5=\frac{25-14}{1}=11. θ 5 = 1 25 − 14 = 11. θ 2 = 11 − ( − 3 / 5 ) 1 = 58 5 . \theta_2=
\frac{11-(-3/5)}{1}
=\frac{58}{5}. θ 2 = 1 11 − ( − 3/5 ) = 5 58 . θ 6 = 0 − 18 / 5 − 3 = 6 5 . \theta_6=
\frac{0-18/5}{-3}
=\frac65. θ 6 = − 3 0 − 18/5 = 5 6 . θ 7 = 2 − 3 / 5 1 = 7 5 . \theta_7=
\frac{2-3/5}{1}
=\frac75. θ 7 = 1 2 − 3/5 = 5 7 . Следовательно,
θ 0 = min { 11 ; 58 5 ; 6 5 ; 7 5 } . \theta^0=
\min\left\{11;\frac{58}{5};\frac65;\frac75\right\}. θ 0 = min { 11 ; 5 58 ; 5 6 ; 5 7 } . θ 0 = 6 5 \boxed{\theta^0=\frac65} θ 0 = 5 6 Минимум достигается на
x 6 x_6 x 6 . Поэтому из базиса выходит
x 6 x_6 x 6 , а входит
x 5 x_5 x 5 .
Шаг 5. Строим новый план x ( 2 ) = x ( 1 ) + 6 5 l . x^{(2)}=x^{(1)}+\frac65l. x ( 2 ) = x ( 1 ) + 5 6 l . Вычисляем:
x 2 = − 3 5 + 6 5 = 3 5 , x_2=-\frac35+\frac65=\frac35, x 2 = − 5 3 + 5 6 = 5 3 , x 5 = 14 + 6 5 = 76 5 , x_5=14+\frac65=\frac{76}{5}, x 5 = 14 + 5 6 = 5 76 , x 6 = 18 5 − 3 ⋅ 6 5 = 0 , x_6=\frac{18}{5}-3\cdot\frac65=0, x 6 = 5 18 − 3 ⋅ 5 6 = 0 , x 7 = 3 5 + 6 5 = 9 5 . x_7=\frac35+\frac65=\frac95. x 7 = 5 3 + 5 6 = 5 9 . Получаем
x ( 2 ) = ( 29 ; 3 5 ; 7 ; 17 ; 76 5 ; 0 ; 9 5 ; 0 ) \boxed{
x^{(2)}=
\left(29;\frac35;7;17;\frac{76}{5};
0;\frac95;0\right)
} x ( 2 ) = ( 29 ; 5 3 ; 7 ; 17 ; 5 76 ; 0 ; 5 9 ; 0 ) Новый базис:
J Б ( 2 ) = { 5 , 7 , 2 } . J_{\text{Б}}^{(2)}=\{5,7,2\}. J Б ( 2 ) = { 5 , 7 , 2 } . Значение функции:
F ( 2 ) = − 9 5 . F^{(2)}=-\frac95. F ( 2 ) = − 5 9 . 6. Первая фаза. Итерация № 3 Шаг 1. Вычисляем потенциалы Базис
J Б = { 5 , 7 , 2 } J_{\text{Б}}=\{5,7,2\} J Б = { 5 , 7 , 2 } .
Система для потенциалов:
{ 2 u 1 − 2 u 2 − 5 u 3 = 0 , u 2 = − 1 , u 1 + u 2 + 5 u 3 = 0. \begin{cases}
2u_1-2u_2-5u_3=0,\\
u_2=-1,\\
u_1+u_2+5u_3=0.
\end{cases} ⎩ ⎨ ⎧ 2 u 1 − 2 u 2 − 5 u 3 = 0 , u 2 = − 1 , u 1 + u 2 + 5 u 3 = 0. Подставим
u 2 = − 1 u_2=-1 u 2 = − 1 :
{ 2 u 1 + 2 − 5 u 3 = 0 , u 1 − 1 + 5 u 3 = 0. \begin{cases}
2u_1+2-5u_3=0,\\
u_1-1+5u_3=0.
\end{cases} { 2 u 1 + 2 − 5 u 3 = 0 , u 1 − 1 + 5 u 3 = 0. Из второго уравнения:
u 1 = 1 − 5 u 3 . u_1=1-5u_3. u 1 = 1 − 5 u 3 . Подставим в первое:
2 ( 1 − 5 u 3 ) + 2 − 5 u 3 = 0 , 2(1-5u_3)+2-5u_3=0, 2 ( 1 − 5 u 3 ) + 2 − 5 u 3 = 0 , 4 − 15 u 3 = 0 , 4-15u_3=0, 4 − 15 u 3 = 0 , u 3 = 4 15 . u_3=\frac4{15}. u 3 = 15 4 . Тогда
u 1 = 1 − 5 ⋅ 4 15 = − 1 3 . u_1=1-5\cdot\frac4{15}
=-\frac13. u 1 = 1 − 5 ⋅ 15 4 = − 3 1 . Итак,
u = ( − 1 3 ; − 1 ; 4 15 ) \boxed{
u=\left(-\frac13;-1;\frac4{15}\right)
} u = ( − 3 1 ; − 1 ; 15 4 ) Шаг 2. Вычисляем оценки Небазисные индексы:
J Н = { 1 , 3 , 4 , 6 , 8 } . J_{\text{Н}}=\{1,3,4,6,8\}. J Н = { 1 , 3 , 4 , 6 , 8 } . Оценки:
Δ 1 = 9 5 , \Delta_1=\frac95, Δ 1 = 5 9 , Δ 3 = 46 15 , \Delta_3=\frac{46}{15}, Δ 3 = 15 46 , Δ 4 = 9 5 , \Delta_4=\frac95, Δ 4 = 5 9 , Δ 6 = − 2 3 , \Delta_6=-\frac23, Δ 6 = − 3 2 , Δ 8 = − 19 15 . \Delta_8=-\frac{19}{15}. Δ 8 = − 15 19 . x 4 = 17 = d ∗ 4 , Δ 4 = 9 5 > 0. x_4=17=d_{*4},\qquad \Delta_4=\frac95>0. x 4 = 17 = d ∗ 4 , Δ 4 = 5 9 > 0. Условие оптимальности нарушено.
Выбираем
j 0 = 4 , l 4 = 1. j_0=4,\qquad l_4=1. j 0 = 4 , l 4 = 1. Шаг 3. Находим направление Для базисных переменных
x 5 , x 7 , x 2 x_5,x_7,x_2 x 5 , x 7 , x 2 получаем систему:
{ l 2 − 5 l 4 + 2 l 5 = 0 , l 2 + 4 l 4 − 2 l 5 + l 7 = 0 , 5 l 2 + 2 l 4 − 5 l 5 = 0. \begin{cases}
l_2-5l_4+2l_5=0,\\
l_2+4l_4-2l_5+l_7=0,\\
5l_2+2l_4-5l_5=0.
\end{cases} ⎩ ⎨ ⎧ l 2 − 5 l 4 + 2 l 5 = 0 , l 2 + 4 l 4 − 2 l 5 + l 7 = 0 , 5 l 2 + 2 l 4 − 5 l 5 = 0. Подставляем
l 4 = 1 l_4=1 l 4 = 1 :
{ l 2 − 5 + 2 l 5 = 0 , l 2 + 4 − 2 l 5 + l 7 = 0 , 5 l 2 + 2 − 5 l 5 = 0. \begin{cases}
l_2-5+2l_5=0,\\
l_2+4-2l_5+l_7=0,\\
5l_2+2-5l_5=0.
\end{cases} ⎩ ⎨ ⎧ l 2 − 5 + 2 l 5 = 0 , l 2 + 4 − 2 l 5 + l 7 = 0 , 5 l 2 + 2 − 5 l 5 = 0. Из третьего уравнения:
l 2 = l 5 − 2 5 . l_2=l_5-\frac25. l 2 = l 5 − 5 2 . Подставляем в первое:
l 5 − 2 5 − 5 + 2 l 5 = 0 , l_5-\frac25-5+2l_5=0, l 5 − 5 2 − 5 + 2 l 5 = 0 , 3 l 5 = 27 5 , 3l_5=\frac{27}{5}, 3 l 5 = 5 27 , l 5 = 9 5 . l_5=\frac95. l 5 = 5 9 . Тогда
l 2 = 9 5 − 2 5 = 7 5 , l_2=\frac95-\frac25=\frac75, l 2 = 5 9 − 5 2 = 5 7 , l 7 = − 7 5 − 4 + 2 ⋅ 9 5 = − 9 5 . l_7=-\frac75-4+2\cdot\frac95
=-\frac95. l 7 = − 5 7 − 4 + 2 ⋅ 5 9 = − 5 9 . Направление:
l = ( 0 ; 7 5 ; 0 ; 1 ; 9 5 ; 0 ; − 9 5 ; 0 ) \boxed{
l=\left(0;\frac75;0;1;\frac95;0;-\frac95;0\right)
} l = ( 0 ; 5 7 ; 0 ; 1 ; 5 9 ; 0 ; − 5 9 ; 0 ) Шаг 4. Находим допустимый шаг Для входящей переменной:
θ 4 = 30 − 17 1 = 13. \theta_4=\frac{30-17}{1}=13. θ 4 = 1 30 − 17 = 13. Для базисных переменных:
θ 2 = 11 − 3 / 5 7 / 5 = 52 7 , \theta_2=
\frac{11-3/5}{7/5}
=\frac{52}{7}, θ 2 = 7/5 11 − 3/5 = 7 52 , θ 5 = 25 − 76 / 5 9 / 5 = 49 9 , \theta_5=
\frac{25-76/5}{9/5}
=\frac{49}{9}, θ 5 = 9/5 25 − 76/5 = 9 49 , θ 7 = 0 − 9 / 5 − 9 / 5 = 1. \theta_7=
\frac{0-9/5}{-9/5}=1. θ 7 = − 9/5 0 − 9/5 = 1. Выбираем минимум:
θ 0 = min { 13 ; 52 7 ; 49 9 ; 1 } . \theta^0=
\min\left\{13;\frac{52}{7};\frac{49}{9};1\right\}. θ 0 = min { 13 ; 7 52 ; 9 49 ; 1 } . θ 0 = 1 \boxed{\theta^0=1} θ 0 = 1 Из базиса выходит
x 7 x_7 x 7 , а входит
x 4 x_4 x 4 .
Шаг 5. Новый план x ( 3 ) = x ( 2 ) + l . x^{(3)}=x^{(2)}+l. x ( 3 ) = x ( 2 ) + l . Вычисляем:
x 2 = 3 5 + 7 5 = 2 , x_2=\frac35+\frac75=2, x 2 = 5 3 + 5 7 = 2 , x 4 = 17 + 1 = 18 , x_4=17+1=18, x 4 = 17 + 1 = 18 , x 5 = 76 5 + 9 5 = 17 , x_5=\frac{76}{5}+\frac95=17, x 5 = 5 76 + 5 9 = 17 , x 7 = 9 5 − 9 5 = 0. x_7=\frac95-\frac95=0. x 7 = 5 9 − 5 9 = 0. Следовательно,
x ( 3 ) = ( 29 ; 2 ; 7 ; 18 ; 17 ; 0 ; 0 ; 0 ) \boxed{x^{(3)}=(29;2;7;18;17;0;0;0)} x ( 3 ) = ( 29 ; 2 ; 7 ; 18 ; 17 ; 0 ; 0 ; 0 ) Новый базис:
J Б = { 5 , 4 , 2 } \boxed{J_{\text{Б}}=\{5,4,2\}} J Б = { 5 , 4 , 2 } Значение вспомогательной функции:
F ( 3 ) = − 0 − 0 − 0 = 0 . F^{(3)}=-0-0-0=\boxed{0}. F ( 3 ) = − 0 − 0 − 0 = 0 . Первая фаза завершена.
Все искусственные переменные равны нулю:
x 6 = x 7 = x 8 = 0. x_6=x_7=x_8=0. x 6 = x 7 = x 8 = 0. Кроме того, искусственных переменных больше нет в базисе. Поэтому, согласно теории из файла, мы получили допустимый базисный план исходной задачи и можем перейти непосредственно ко второй фазе без буферной задачи.
7. Вторая фаза симплекс-метода Теперь возвращаемся к исходной целевой функции:
φ = − 16 x 1 + 35 x 2 + 12 x 3 + 5 x 4 − 29 x 5 → max . \varphi=-16x_1+35x_2+12x_3+5x_4-29x_5
\rightarrow\max. φ = − 16 x 1 + 35 x 2 + 12 x 3 + 5 x 4 − 29 x 5 → max . Начальный базисный план второй фазы:
x = ( 29 ; 2 ; 7 ; 18 ; 17 ) . x=(29;2;7;18;17). x = ( 29 ; 2 ; 7 ; 18 ; 17 ) . Базисные и небазисные индексы:
J Б = { 5 , 4 , 2 } , J_{\text{Б}}=\{5,4,2\}, J Б = { 5 , 4 , 2 } , J Н = { 1 , 3 } . J_{\text{Н}}=\{1,3\}. J Н = { 1 , 3 } . Шаг 1. Вычисляем потенциалы Для базисных переменных выполняются уравнения
a j T u = c j . a_j^Tu=c_j. a j T u = c j . При
j = 5 , 4 , 2 j=5,4,2 j = 5 , 4 , 2 получим:
{ 2 u 1 − 2 u 2 − 5 u 3 = − 29 , − 5 u 1 + 4 u 2 + 2 u 3 = 5 , u 1 + u 2 + 5 u 3 = 35. \begin{cases}
2u_1-2u_2-5u_3=-29,\\
-5u_1+4u_2+2u_3=5,\\
u_1+u_2+5u_3=35.
\end{cases} ⎩ ⎨ ⎧ 2 u 1 − 2 u 2 − 5 u 3 = − 29 , − 5 u 1 + 4 u 2 + 2 u 3 = 5 , u 1 + u 2 + 5 u 3 = 35. Решая эту систему, получаем:
u 1 = 7 3 , u 2 = 1 , u 3 = 19 3 \boxed{
u_1=\frac73,\quad
u_2=1,\quad
u_3=\frac{19}{3}
} u 1 = 3 7 , u 2 = 1 , u 3 = 3 19 Проверим:
2 ⋅ 7 3 − 2 − 5 ⋅ 19 3 = − 29 , 2\cdot\frac73-2-5\cdot\frac{19}{3}=-29, 2 ⋅ 3 7 − 2 − 5 ⋅ 3 19 = − 29 , − 5 ⋅ 7 3 + 4 + 2 ⋅ 19 3 = 5 , -5\cdot\frac73+4+2\cdot\frac{19}{3}=5, − 5 ⋅ 3 7 + 4 + 2 ⋅ 3 19 = 5 , 7 3 + 1 + 5 ⋅ 19 3 = 35. \frac73+1+5\cdot\frac{19}{3}=35. 3 7 + 1 + 5 ⋅ 3 19 = 35. Все три уравнения выполняются.
Шаг 2. Вычисляем небазисные оценки Небазисные переменные —
x 1 x_1 x 1 и
x 3 x_3 x 3 .
Δ 1 = c 1 − a 1 T u . \Delta_1=c_1-a_1^Tu. Δ 1 = c 1 − a 1 T u . Δ 1 = − 16 − ( u 2 − 3 u 3 ) . \Delta_1=-16-(u_2-3u_3). Δ 1 = − 16 − ( u 2 − 3 u 3 ) . Подставляем потенциалы:
Δ 1 = − 16 − ( 1 − 3 ⋅ 19 3 ) = − 16 − ( 1 − 19 ) = − 16 + 18 = 2. \begin{aligned}
\Delta_1
&=-16-\left(1-3\cdot\frac{19}{3}\right)\\
&=-16-(1-19)\\
&=-16+18=2.
\end{aligned} Δ 1 = − 16 − ( 1 − 3 ⋅ 3 19 ) = − 16 − ( 1 − 19 ) = − 16 + 18 = 2. Δ 1 = 2 \boxed{\Delta_1=2} Δ 1 = 2 Δ 3 = c 3 − a 3 T u , \Delta_3=c_3-a_3^Tu, Δ 3 = c 3 − a 3 T u , Δ 3 = 12 − ( u 1 + 3 u 2 + u 3 ) . \Delta_3=12-(u_1+3u_2+u_3). Δ 3 = 12 − ( u 1 + 3 u 2 + u 3 ) . Подставляем:
Δ 3 = 12 − ( 7 3 + 3 + 19 3 ) = 12 − 35 3 = 36 3 − 35 3 = 1 3 . \begin{aligned}
\Delta_3
&=12-\left(\frac73+3+\frac{19}{3}\right)\\
&=12-\frac{35}{3}\\
&=\frac{36}{3}-\frac{35}{3}\\
&=\frac13.
\end{aligned} Δ 3 = 12 − ( 3 7 + 3 + 3 19 ) = 12 − 3 35 = 3 36 − 3 35 = 3 1 . Δ 3 = 1 3 \boxed{\Delta_3=\frac13} Δ 3 = 3 1 Шаг 3. Проверяем условия оптимальности По теории из файла, для небазисных переменных, находящихся на верхней границе, должно выполняться условие
Δ j ≥ 0. \Delta_j\ge0. Δ j ≥ 0. Проверим:
Переменная Значение Оценка Условие x 1 x_1 x 1 29 = d 1 ∗ 29=d_1^* 29 = d 1 ∗ Δ 1 = 2 > 0 \Delta_1=2>0 Δ 1 = 2 > 0 Выполнено x 3 x_3 x 3 7 = d 3 ∗ 7=d_3^* 7 = d 3 ∗ Δ 3 = 1 3 > 0 \Delta_3=\frac13>0 Δ 3 = 3 1 > 0 Выполнено
Все условия оптимальности выполняются.
Следовательно, полученный базисный план оптимален. Дополнительных итераций второй фазы не требуется.
8. Вычисление максимума целевой функции Подставим найденные значения:
x 1 = 29 , x 2 = 2 , x 3 = 7 , x_1=29,\quad x_2=2,\quad x_3=7, x 1 = 29 , x 2 = 2 , x 3 = 7 , x 4 = 18 , x 5 = 17. x_4=18,\quad x_5=17. x 4 = 18 , x 5 = 17. Вычисляем:
φ max = − 16 ⋅ 29 + 35 ⋅ 2 + 12 ⋅ 7 + 5 ⋅ 18 − 29 ⋅ 17 = − 464 + 70 + 84 + 90 − 493 = − 713 . \begin{aligned}
\varphi_{\max}
&=-16\cdot29+35\cdot2+12\cdot7\\
&\quad+5\cdot18-29\cdot17\\
&=-464+70+84+90-493\\
&=\boxed{-713}.
\end{aligned} φ m a x = − 16 ⋅ 29 + 35 ⋅ 2 + 12 ⋅ 7 + 5 ⋅ 18 − 29 ⋅ 17 = − 464 + 70 + 84 + 90 − 493 = − 713 . 9. Проверка исходных ограничений Первое уравнение:
2 + 7 − 5 ⋅ 18 + 2 ⋅ 17 = 2 + 7 − 90 + 34 = − 47. 2+7-5\cdot18+2\cdot17
=2+7-90+34=-47. 2 + 7 − 5 ⋅ 18 + 2 ⋅ 17 = 2 + 7 − 90 + 34 = − 47. Второе уравнение:
29 + 2 + 3 ⋅ 7 + 4 ⋅ 18 − 2 ⋅ 17 29+2+3\cdot7+4\cdot18-2\cdot17 29 + 2 + 3 ⋅ 7 + 4 ⋅ 18 − 2 ⋅ 17 = 29 + 2 + 21 + 72 − 34 = 90. =29+2+21+72-34=90. = 29 + 2 + 21 + 72 − 34 = 90. Третье уравнение:
− 3 ⋅ 29 + 5 ⋅ 2 + 7 + 2 ⋅ 18 − 5 ⋅ 17 -3\cdot29+5\cdot2+7+2\cdot18-5\cdot17 − 3 ⋅ 29 + 5 ⋅ 2 + 7 + 2 ⋅ 18 − 5 ⋅ 17 = − 87 + 10 + 7 + 36 − 85 = − 119. =-87+10+7+36-85=-119. = − 87 + 10 + 7 + 36 − 85 = − 119. Все три равенства выполняются.
Проверим границы переменных:
20 ≤ 29 ≤ 29 , − 2 ≤ 2 ≤ 11 , − 7 ≤ 7 ≤ 7 , 17 ≤ 18 ≤ 30 , 14 ≤ 17 ≤ 25. \begin{aligned}
20&\le29\le29,\\
-2&\le2\le11,\\
-7&\le7\le7,\\
17&\le18\le30,\\
14&\le17\le25.
\end{aligned} 20 − 2 − 7 17 14 ≤ 29 ≤ 29 , ≤ 2 ≤ 11 , ≤ 7 ≤ 7 , ≤ 18 ≤ 30 , ≤ 17 ≤ 25. Все ограничения выполнены.
10. Итог решения За три итерации первой фазы получен допустимый базисный план исходной задачи:
x = ( 29 ; 2 ; 7 ; 18 ; 17 ) . x=(29;2;7;18;17). x = ( 29 ; 2 ; 7 ; 18 ; 17 ) . Во второй фазе вычислены потенциалы и небазисные оценки:
u = ( 7 3 ; 1 ; 19 3 ) , u=\left(\frac73;1;\frac{19}{3}\right), u = ( 3 7 ; 1 ; 3 19 ) , Δ 1 = 2 , Δ 3 = 1 3 . \Delta_1=2,\qquad \Delta_3=\frac13. Δ 1 = 2 , Δ 3 = 3 1 . Обе небазисные переменные находятся на верхних границах, а их оценки положительны. Поэтому выполнен критерий оптимальности из приложенного файла.
Окончательно:
x 1 ∗ = 29 , x 2 ∗ = 2 , x 3 ∗ = 7 , x 4 ∗ = 18 , x 5 ∗ = 17 , φ max = − 713. \boxed{
\begin{gathered}
x_1^*=29,\qquad x_2^*=2,\\
x_3^*=7,\qquad x_4^*=18,\\
x_5^*=17,\\[4pt]
\varphi_{\max}=-713.
\end{gathered}
} x 1 ∗ = 29 , x 2 ∗ = 2 , x 3 ∗ = 7 , x 4 ∗ = 18 , x 5 ∗ = 17 , φ m a x = − 713. Задача решена симплекс-методом полностью: выполнена первая фаза с тремя заменами базиса, получен допустимый план, проведена вторая фаза и доказана оптимальность найденного решения.
Text version Решение варианта 6 симплекс-методом
Ответ:
x ∗ = ( 29 ; 2 ; 7 ; 18 ; 17 ) \boxed{x^*=(29;\ 2;\ 7;\ 18;\ 17)} x ∗ = ( 29 ; 2 ; 7 ; 18 ; 17 ) φ max = − 713 \boxed{\varphi_{\max}=-713} φ m a x = − 713 Решим задачу полностью по алгоритму из приложенного файла «Симплекс метод1»: с построением начального базисного плана (первая фаза), вычислением потенциалов u u u Δ j \Delta_j Δ j l l l θ \theta θ
1. Условие задачи
Требуется найти максимум целевой функции
φ = − 16 x 1 + 35 x 2 + 12 x 3 + 5 x 4 − 29 x 5 → max \varphi=-16x_1+35x_2+12x_3+5x_4-29x_5
\rightarrow\max φ = − 16 x 1 + 35 x 2 + 12 x 3 + 5 x 4 − 29 x 5 → max при ограничениях
{ x 2 + x 3 − 5 x 4 + 2 x 5 = − 47 , x 1 + x 2 + 3 x 3 + 4 x 4 − 2 x 5 = 90 , − 3 x 1 + 5 x 2 + x 3 + 2 x 4 − 5 x 5 = − 119. \begin{cases}
x_2+x_3-5x_4+2x_5=-47,\\
x_1+x_2+3x_3+4x_4-2x_5=90,\\
-3x_1+5x_2+x_3+2x_4-5x_5=-119.
\end{cases} ⎩ ⎨ ⎧ x 2 + x 3 − 5 x 4 + 2 x 5 = − 47 , x 1 + x 2 + 3 x 3 + 4 x 4 − 2 x 5 = 90 , − 3 x 1 + 5 x 2 + x 3 + 2 x 4 − 5 x 5 = − 119. 20 ≤ x 1 ≤ 29 , − 2 ≤ x 2 ≤ 11 , − 7 ≤ x 3 ≤ 7 , 17 ≤ x 4 ≤ 30 , 14 ≤ x 5 ≤ 25. \begin{aligned}
20&\le x_1\le29,\\
-2&\le x_2\le11,\\
-7&\le x_3\le7,\\
17&\le x_4\le30,\\
14&\le x_5\le25.
\end{aligned} 20 − 2 − 7 17 14 ≤ x 1 ≤ 29 , ≤ x 2 ≤ 11 , ≤ x 3 ≤ 7 , ≤ x 4 ≤ 30 , ≤ x 5 ≤ 25. Запишем задачу в канонической форме:
c T x → max , A x = b , d ∗ ≤ x ≤ d ∗ . c^Tx\rightarrow\max,\qquad Ax=b,\qquad d_*\le x\le d^*. c T x → max , A x = b , d ∗ ≤ x ≤ d ∗ . Здесь
A = ( 0 1 1 − 5 2 1 1 3 4 − 2 − 3 5 1 2 − 5 ) , A=
\begin{pmatrix}
0&1&1&-5&2\\
1&1&3&4&-2\\
-3&5&1&2&-5
\end{pmatrix}, A = 0 1 − 3 1 1 5 1 3 1 − 5 4 2 2 − 2 − 5 , b = ( − 47 90 − 119 ) , c = ( − 16 35 12 5 − 29 ) . b=\begin{pmatrix}-47\\90\\-119\end{pmatrix},
\qquad
c=\begin{pmatrix}-16\\35\\12\\5\\-29\end{pmatrix}. b = − 47 90 − 119 , c = − 16 35 12 5 − 29 . Число переменных n = 5 n=5 n = 5 m = 3 m=3 m = 3
2. Формулы симплекс-метода из файла
На страницах 1–2 файла приведён алгоритм для задачи с двусторонними ограничениями на переменные.
Потенциалы u = ( u 1 , u 2 , u 3 ) u=(u_1,u_2,u_3) u = ( u 1 , u 2 , u 3 )
a j T u = c j , j ∈ J Б . a_j^Tu=c_j,\qquad j\in J_{\text{Б}}. a j T u = c j , j ∈ J Б . Оценки небазисных переменных:
Δ j = c j − a j T u \boxed{\Delta_j=c_j-a_j^Tu} Δ j = c j − a j T u Условия оптимальности:
{ Δ j ≤ 0 , x j = d ∗ j , Δ j ≥ 0 , x j = d j ∗ . \begin{cases}
\Delta_j\le0,&x_j=d_{*j},\\
\Delta_j\ge0,&x_j=d_j^*.
\end{cases} { Δ j ≤ 0 , Δ j ≥ 0 , x j = d ∗ j , x j = d j ∗ . Если условия нарушены, выбираем входящую переменную x j 0 x_{j_0} x j 0
l j 0 = sign Δ j 0 , l_{j_0}=\operatorname{sign}\Delta_{j_0}, l j 0 = sign Δ j 0 , A Б l Б = − a j 0 sign Δ j 0 . A_{\text{Б}}l_{\text{Б}}
=-a_{j_0}\operatorname{sign}\Delta_{j_0}. A Б l Б = − a j 0 sign Δ j 0 . Допустимые шаги определяются формулами
θ j = { d j ∗ − x j l j , l j > 0 , d ∗ j − x j l j , l j < 0 , + ∞ , l j = 0. \theta_j=
\begin{cases}
\dfrac{d_j^*-x_j}{l_j},&l_j>0,\\[6pt]
\dfrac{d_{*j}-x_j}{l_j},&l_j<0,\\[6pt]
+\infty,&l_j=0.
\end{cases} θ j = ⎩ ⎨ ⎧ l j d j ∗ − x j , l j d ∗ j − x j , + ∞ , l j > 0 , l j < 0 , l j = 0. Выбираем наименьший допустимый шаг:
θ 0 = min θ j . \theta^0=\min\theta_j. θ 0 = min θ j . Новый план:
x ˉ = x + θ 0 l \boxed{\bar x=x+\theta^0l} x ˉ = x + θ 0 l Именно эти формулы будем использовать в каждой итерации.
3. Первая фаза симплекс-метода
Согласно теории на страницах 2–3 файла, сначала необходимо получить допустимый базисный план. Для этого вводятся искусственные переменные.
3.1. Построение начального плана
Возьмём значения переменных на границах:
x ~ = ( 29 ; − 2 ; 7 ; 17 ; 14 ) . \widetilde x=(29;-2;7;17;14). x = ( 29 ; − 2 ; 7 ; 17 ; 14 ) . Подставим в основные ограничения и вычислим вектор невязок:
ω = b − A x ~ . \omega=b-A\widetilde x. ω = b − A x . Первая невязка:
ω 1 = − 47 − ( − 2 + 7 − 5 ⋅ 17 + 2 ⋅ 14 ) = − 47 − ( − 52 ) = 5. \begin{aligned}
\omega_1
&=-47-(-2+7-5\cdot17+2\cdot14)\\
&=-47-(-52)=5.
\end{aligned} ω 1 = − 47 − ( − 2 + 7 − 5 ⋅ 17 + 2 ⋅ 14 ) = − 47 − ( − 52 ) = 5. Вторая невязка:
ω 2 = 90 − ( 29 − 2 + 3 ⋅ 7 + 4 ⋅ 17 − 2 ⋅ 14 ) = 90 − 88 = 2. \begin{aligned}
\omega_2
&=90-(29-2+3\cdot7+4\cdot17-2\cdot14)\\
&=90-88=2.
\end{aligned} ω 2 = 90 − ( 29 − 2 + 3 ⋅ 7 + 4 ⋅ 17 − 2 ⋅ 14 ) = 90 − 88 = 2. Третья невязка:
ω 3 = − 119 − ( − 3 ⋅ 29 + 5 ( − 2 ) + 7 + 2 ⋅ 17 − 5 ⋅ 14 ) = − 119 − ( − 126 ) = 7. \begin{aligned}
\omega_3
&=-119-(-3\cdot29+5(-2)+7\\
&\qquad+2\cdot17-5\cdot14)\\
&=-119-(-126)=7.
\end{aligned} ω 3 = − 119 − ( − 3 ⋅ 29 + 5 ( − 2 ) + 7 + 2 ⋅ 17 − 5 ⋅ 14 ) = − 119 − ( − 126 ) = 7. Таким образом,
ω = ( 5 ; 2 ; 7 ) \boxed{\omega=(5;2;7)} ω = ( 5 ; 2 ; 7 ) Все невязки положительные, поэтому введём искусственные переменные x 6 , x 7 , x 8 x_6,x_7,x_8 x 6 , x 7 , x 8
3.2. Вспомогательная задача
Целевая функция первой фазы:
F = − x 6 − x 7 − x 8 → max \boxed{F=-x_6-x_7-x_8\rightarrow\max} F = − x 6 − x 7 − x 8 → max Система ограничений:
{ x 2 + x 3 − 5 x 4 + 2 x 5 + x 6 = − 47 , x 1 + x 2 + 3 x 3 + 4 x 4 − 2 x 5 + x 7 = 90 , − 3 x 1 + 5 x 2 + x 3 + 2 x 4 − 5 x 5 + x 8 = − 119. \begin{cases}
x_2+x_3-5x_4+2x_5+x_6=-47,\\
x_1+x_2+3x_3+4x_4-2x_5+x_7=90,\\
-3x_1+5x_2+x_3+2x_4-5x_5+x_8=-119.
\end{cases} ⎩ ⎨ ⎧ x 2 + x 3 − 5 x 4 + 2 x 5 + x 6 = − 47 , x 1 + x 2 + 3 x 3 + 4 x 4 − 2 x 5 + x 7 = 90 , − 3 x 1 + 5 x 2 + x 3 + 2 x 4 − 5 x 5 + x 8 = − 119. Ограничения на исходные переменные остаются прежними, а на искусственные накладываем:
0 ≤ x 6 ≤ 5 , 0 ≤ x 7 ≤ 2 , 0 ≤ x 8 ≤ 7. 0\le x_6\le5,\quad
0\le x_7\le2,\quad
0\le x_8\le7. 0 ≤ x 6 ≤ 5 , 0 ≤ x 7 ≤ 2 , 0 ≤ x 8 ≤ 7. Начальный базисный план:
x ( 0 ) = ( 29 ; − 2 ; 7 ; 17 ; 14 ; 5 ; 2 ; 7 ) . x^{(0)}=(29;-2;7;17;14;5;2;7). x ( 0 ) = ( 29 ; − 2 ; 7 ; 17 ; 14 ; 5 ; 2 ; 7 ) . Базисные и небазисные индексы:
J Б ( 0 ) = { 6 , 7 , 8 } , J_{\text{Б}}^{(0)}=\{6,7,8\}, J Б ( 0 ) = { 6 , 7 , 8 } , J Н ( 0 ) = { 1 , 2 , 3 , 4 , 5 } . J_{\text{Н}}^{(0)}=\{1,2,3,4,5\}. J Н ( 0 ) = { 1 , 2 , 3 , 4 , 5 } . Начальное значение вспомогательной функции:
F ( 0 ) = − 5 − 2 − 7 = − 14 . F^{(0)}=-5-2-7=\boxed{-14}. F ( 0 ) = − 5 − 2 − 7 = − 14 . 4. Первая фаза. Итерация № 1
Шаг 1. Вычисляем потенциалы
Так как в базисе находятся искусственные переменные x 6 , x 7 , x 8 x_6,x_7,x_8 x 6 , x 7 , x 8
u 1 = − 1 , u 2 = − 1 , u 3 = − 1. u_1=-1,\qquad u_2=-1,\qquad u_3=-1. u 1 = − 1 , u 2 = − 1 , u 3 = − 1. u = ( − 1 ; − 1 ; − 1 ) \boxed{u=(-1;-1;-1)} u = ( − 1 ; − 1 ; − 1 ) Шаг 2. Вычисляем оценки
Для небазисных переменных c j = 0 c_j=0 c j = 0
Δ 1 = 0 − ( u 2 − 3 u 3 ) = − 2 , \Delta_1=0-(u_2-3u_3)=-2, Δ 1 = 0 − ( u 2 − 3 u 3 ) = − 2 , Δ 2 = 0 − ( u 1 + u 2 + 5 u 3 ) = 7 , \Delta_2=0-(u_1+u_2+5u_3)=7, Δ 2 = 0 − ( u 1 + u 2 + 5 u 3 ) = 7 , Δ 3 = 0 − ( u 1 + 3 u 2 + u 3 ) = 5 , \Delta_3=0-(u_1+3u_2+u_3)=5, Δ 3 = 0 − ( u 1 + 3 u 2 + u 3 ) = 5 , Δ 4 = 0 − ( − 5 u 1 + 4 u 2 + 2 u 3 ) = 1 , \Delta_4=0-(-5u_1+4u_2+2u_3)=1, Δ 4 = 0 − ( − 5 u 1 + 4 u 2 + 2 u 3 ) = 1 , Δ 5 = 0 − ( 2 u 1 − 2 u 2 − 5 u 3 ) = − 5. \Delta_5=0-(2u_1-2u_2-5u_3)=-5. Δ 5 = 0 − ( 2 u 1 − 2 u 2 − 5 u 3 ) = − 5. Получаем таблицу оценок:
Переменная Значение Оценка x 1 x_1 x 1 29 (верхняя) − 2 -2 − 2 x 2 x_2 x 2 −2 (нижняя) 7 7 7 x 3 x_3 x 3 7 (верхняя) 5 5 5 x 4 x_4 x 4 17 (нижняя) 1 1 1 x 5 x_5 x 5 14 (нижняя) − 5 -5 − 5
Условие оптимальности нарушено для x 1 , x 2 , x 4 x_1,x_2,x_4 x 1 , x 2 , x 4
Выбираем x 2 x_2 x 2
Δ 2 = 7 > 0 , x 2 = − 2. \Delta_2=7>0,\qquad x_2=-2. Δ 2 = 7 > 0 , x 2 = − 2. Следовательно,
j 0 = 2 , l 2 = 1. j_0=2,\qquad l_2=1. j 0 = 2 , l 2 = 1. Шаг 3. Находим направление l l l
Из условия A l = 0 Al=0 A l = 0
{ l 2 + l 6 = 0 , l 2 + l 7 = 0 , 5 l 2 + l 8 = 0. \begin{cases}
l_2+l_6=0,\\
l_2+l_7=0,\\
5l_2+l_8=0.
\end{cases} ⎩ ⎨ ⎧ l 2 + l 6 = 0 , l 2 + l 7 = 0 , 5 l 2 + l 8 = 0. Так как l 2 = 1 l_2=1 l 2 = 1
l 6 = − 1 , l 7 = − 1 , l 8 = − 5. l_6=-1,\qquad l_7=-1,\qquad l_8=-5. l 6 = − 1 , l 7 = − 1 , l 8 = − 5. Остальные компоненты равны нулю.
l = ( 0 ; 1 ; 0 ; 0 ; 0 ; − 1 ; − 1 ; − 5 ) \boxed{l=(0;1;0;0;0;-1;-1;-5)} l = ( 0 ; 1 ; 0 ; 0 ; 0 ; − 1 ; − 1 ; − 5 ) Шаг 4. Определяем шаг θ \theta θ
Для входящей переменной x 2 x_2 x 2
θ 2 = 11 − ( − 2 ) 1 = 13. \theta_2=\frac{11-(-2)}1=13. θ 2 = 1 11 − ( − 2 ) = 13. Для базисных переменных:
θ 6 = 0 − 5 − 1 = 5 , \theta_6=\frac{0-5}{-1}=5, θ 6 = − 1 0 − 5 = 5 , θ 7 = 0 − 2 − 1 = 2 , \theta_7=\frac{0-2}{-1}=2, θ 7 = − 1 0 − 2 = 2 , θ 8 = 0 − 7 − 5 = 7 5 . \theta_8=\frac{0-7}{-5}=\frac75. θ 8 = − 5 0 − 7 = 5 7 . Выбираем минимум:
θ 0 = min { 13 ; 5 ; 2 ; 7 5 } . \theta^0=\min\left\{13;5;2;\frac75\right\}. θ 0 = min { 13 ; 5 ; 2 ; 5 7 } . θ 0 = 7 5 \boxed{\theta^0=\frac75} θ 0 = 5 7 Минимум достигается на x 8 x_8 x 8 x 8 x_8 x 8 x 2 x_2 x 2
Шаг 5. Строим новый план
x ( 1 ) = x ( 0 ) + 7 5 l . x^{(1)}=x^{(0)}+\frac75l. x ( 1 ) = x ( 0 ) + 5 7 l . Вычисляем изменившиеся компоненты:
x 2 = − 2 + 7 5 = − 3 5 , x_2=-2+\frac75=-\frac35, x 2 = − 2 + 5 7 = − 5 3 , x 6 = 5 − 7 5 = 18 5 , x_6=5-\frac75=\frac{18}{5}, x 6 = 5 − 5 7 = 5 18 , x 7 = 2 − 7 5 = 3 5 , x_7=2-\frac75=\frac35, x 7 = 2 − 5 7 = 5 3 , x 8 = 7 − 5 ⋅ 7 5 = 0. x_8=7-5\cdot\frac75=0. x 8 = 7 − 5 ⋅ 5 7 = 0. Итак,
x ( 1 ) = ( 29 ; − 3 5 ; 7 ; 17 ; 14 ; 18 5 ; 3 5 ; 0 ) \boxed{
x^{(1)}=
\left(29;-\frac35;7;17;14;
\frac{18}{5};\frac35;0\right)
} x ( 1 ) = ( 29 ; − 5 3 ; 7 ; 17 ; 14 ; 5 18 ; 5 3 ; 0 ) Новый базис:
J Б ( 1 ) = { 6 , 7 , 2 } . J_{\text{Б}}^{(1)}=\{6,7,2\}. J Б ( 1 ) = { 6 , 7 , 2 } . Значение функции первой фазы:
F ( 1 ) = − 18 5 − 3 5 = − 21 5 . F^{(1)}
=-\frac{18}{5}-\frac35
=\boxed{-\frac{21}{5}}. F ( 1 ) = − 5 18 − 5 3 = − 5 21 . 5. Первая фаза. Итерация № 2
Шаг 1. Вычисляем потенциалы
Теперь базис J Б = { 6 , 7 , 2 } J_{\text{Б}}=\{6,7,2\} J Б = { 6 , 7 , 2 }
Составим систему:
{ u 1 = − 1 , u 2 = − 1 , u 1 + u 2 + 5 u 3 = 0. \begin{cases}
u_1=-1,\\
u_2=-1,\\
u_1+u_2+5u_3=0.
\end{cases} ⎩ ⎨ ⎧ u 1 = − 1 , u 2 = − 1 , u 1 + u 2 + 5 u 3 = 0. Из третьего уравнения:
− 1 − 1 + 5 u 3 = 0 , -1-1+5u_3=0, − 1 − 1 + 5 u 3 = 0 , u 3 = 2 5 . u_3=\frac25. u 3 = 5 2 . Следовательно,
u = ( − 1 ; − 1 ; 2 5 ) \boxed{u=\left(-1;-1;\frac25\right)} u = ( − 1 ; − 1 ; 5 2 ) Шаг 2. Вычисляем оценки
Небазисные индексы:
J Н = { 1 , 3 , 4 , 5 , 8 } . J_{\text{Н}}=\{1,3,4,5,8\}. J Н = { 1 , 3 , 4 , 5 , 8 } . Получаем:
Δ 1 = 0 − ( u 2 − 3 u 3 ) = 11 5 , Δ 3 = 0 − ( u 1 + 3 u 2 + u 3 ) = 18 5 , Δ 4 = 0 − ( − 5 u 1 + 4 u 2 + 2 u 3 ) = − 9 5 , Δ 5 = 0 − ( 2 u 1 − 2 u 2 − 5 u 3 ) = 2 , Δ 8 = − 1 − u 3 = − 7 5 . \begin{aligned}
\Delta_1&=0-(u_2-3u_3)=\frac{11}{5},\\
\Delta_3&=0-(u_1+3u_2+u_3)=\frac{18}{5},\\
\Delta_4&=0-(-5u_1+4u_2+2u_3)=-\frac95,\\
\Delta_5&=0-(2u_1-2u_2-5u_3)=2,\\
\Delta_8&=-1-u_3=-\frac75.
\end{aligned} Δ 1 Δ 3 Δ 4 Δ 5 Δ 8 = 0 − ( u 2 − 3 u 3 ) = 5 11 , = 0 − ( u 1 + 3 u 2 + u 3 ) = 5 18 , = 0 − ( − 5 u 1 + 4 u 2 + 2 u 3 ) = − 5 9 , = 0 − ( 2 u 1 − 2 u 2 − 5 u 3 ) = 2 , = − 1 − u 3 = − 5 7 . Условие оптимальности нарушено для x 5 x_5 x 5
x 5 = 14 = d ∗ 5 , Δ 5 = 2 > 0. x_5=14=d_{*5},\qquad \Delta_5=2>0. x 5 = 14 = d ∗ 5 , Δ 5 = 2 > 0. Выбираем
j 0 = 5 , l 5 = 1. j_0=5,\qquad l_5=1. j 0 = 5 , l 5 = 1. Шаг 3. Находим направление
Так как небазисные переменные, кроме x 5 x_5 x 5
{ l 2 + 2 l 5 + l 6 = 0 , l 2 − 2 l 5 + l 7 = 0 , 5 l 2 − 5 l 5 = 0. \begin{cases}
l_2+2l_5+l_6=0,\\
l_2-2l_5+l_7=0,\\
5l_2-5l_5=0.
\end{cases} ⎩ ⎨ ⎧ l 2 + 2 l 5 + l 6 = 0 , l 2 − 2 l 5 + l 7 = 0 , 5 l 2 − 5 l 5 = 0. Подставим l 5 = 1 l_5=1 l 5 = 1
{ l 2 + 2 + l 6 = 0 , l 2 − 2 + l 7 = 0 , 5 l 2 − 5 = 0. \begin{cases}
l_2+2+l_6=0,\\
l_2-2+l_7=0,\\
5l_2-5=0.
\end{cases} ⎩ ⎨ ⎧ l 2 + 2 + l 6 = 0 , l 2 − 2 + l 7 = 0 , 5 l 2 − 5 = 0. Отсюда
l 2 = 1 , l 6 = − 3 , l 7 = 1. l_2=1,\qquad l_6=-3,\qquad l_7=1. l 2 = 1 , l 6 = − 3 , l 7 = 1. Полное направление:
l = ( 0 ; 1 ; 0 ; 0 ; 1 ; − 3 ; 1 ; 0 ) \boxed{l=(0;1;0;0;1;-3;1;0)} l = ( 0 ; 1 ; 0 ; 0 ; 1 ; − 3 ; 1 ; 0 ) Шаг 4. Вычисляем θ \theta θ
Для x 5 x_5 x 5
θ 5 = 25 − 14 1 = 11. \theta_5=\frac{25-14}{1}=11. θ 5 = 1 25 − 14 = 11. Для x 2 x_2 x 2
θ 2 = 11 − ( − 3 / 5 ) 1 = 58 5 . \theta_2=
\frac{11-(-3/5)}{1}
=\frac{58}{5}. θ 2 = 1 11 − ( − 3/5 ) = 5 58 . Для x 6 x_6 x 6
θ 6 = 0 − 18 / 5 − 3 = 6 5 . \theta_6=
\frac{0-18/5}{-3}
=\frac65. θ 6 = − 3 0 − 18/5 = 5 6 . Для x 7 x_7 x 7
θ 7 = 2 − 3 / 5 1 = 7 5 . \theta_7=
\frac{2-3/5}{1}
=\frac75. θ 7 = 1 2 − 3/5 = 5 7 . Следовательно,
θ 0 = min { 11 ; 58 5 ; 6 5 ; 7 5 } . \theta^0=
\min\left\{11;\frac{58}{5};\frac65;\frac75\right\}. θ 0 = min { 11 ; 5 58 ; 5 6 ; 5 7 } . θ 0 = 6 5 \boxed{\theta^0=\frac65} θ 0 = 5 6 Минимум достигается на x 6 x_6 x 6 x 6 x_6 x 6 x 5 x_5 x 5
Шаг 5. Строим новый план
x ( 2 ) = x ( 1 ) + 6 5 l . x^{(2)}=x^{(1)}+\frac65l. x ( 2 ) = x ( 1 ) + 5 6 l . Вычисляем:
x 2 = − 3 5 + 6 5 = 3 5 , x_2=-\frac35+\frac65=\frac35, x 2 = − 5 3 + 5 6 = 5 3 , x 5 = 14 + 6 5 = 76 5 , x_5=14+\frac65=\frac{76}{5}, x 5 = 14 + 5 6 = 5 76 , x 6 = 18 5 − 3 ⋅ 6 5 = 0 , x_6=\frac{18}{5}-3\cdot\frac65=0, x 6 = 5 18 − 3 ⋅ 5 6 = 0 , x 7 = 3 5 + 6 5 = 9 5 . x_7=\frac35+\frac65=\frac95. x 7 = 5 3 + 5 6 = 5 9 . Получаем
x ( 2 ) = ( 29 ; 3 5 ; 7 ; 17 ; 76 5 ; 0 ; 9 5 ; 0 ) \boxed{
x^{(2)}=
\left(29;\frac35;7;17;\frac{76}{5};
0;\frac95;0\right)
} x ( 2 ) = ( 29 ; 5 3 ; 7 ; 17 ; 5 76 ; 0 ; 5 9 ; 0 ) Новый базис:
J Б ( 2 ) = { 5 , 7 , 2 } . J_{\text{Б}}^{(2)}=\{5,7,2\}. J Б ( 2 ) = { 5 , 7 , 2 } . Значение функции:
F ( 2 ) = − 9 5 . F^{(2)}=-\frac95. F ( 2 ) = − 5 9 . 6. Первая фаза. Итерация № 3
Шаг 1. Вычисляем потенциалы
Базис J Б = { 5 , 7 , 2 } J_{\text{Б}}=\{5,7,2\} J Б = { 5 , 7 , 2 }
Система для потенциалов:
{ 2 u 1 − 2 u 2 − 5 u 3 = 0 , u 2 = − 1 , u 1 + u 2 + 5 u 3 = 0. \begin{cases}
2u_1-2u_2-5u_3=0,\\
u_2=-1,\\
u_1+u_2+5u_3=0.
\end{cases} ⎩ ⎨ ⎧ 2 u 1 − 2 u 2 − 5 u 3 = 0 , u 2 = − 1 , u 1 + u 2 + 5 u 3 = 0. Подставим u 2 = − 1 u_2=-1 u 2 = − 1
{ 2 u 1 + 2 − 5 u 3 = 0 , u 1 − 1 + 5 u 3 = 0. \begin{cases}
2u_1+2-5u_3=0,\\
u_1-1+5u_3=0.
\end{cases} { 2 u 1 + 2 − 5 u 3 = 0 , u 1 − 1 + 5 u 3 = 0. Из второго уравнения:
u 1 = 1 − 5 u 3 . u_1=1-5u_3. u 1 = 1 − 5 u 3 . Подставим в первое:
2 ( 1 − 5 u 3 ) + 2 − 5 u 3 = 0 , 2(1-5u_3)+2-5u_3=0, 2 ( 1 − 5 u 3 ) + 2 − 5 u 3 = 0 , 4 − 15 u 3 = 0 , 4-15u_3=0, 4 − 15 u 3 = 0 , u 3 = 4 15 . u_3=\frac4{15}. u 3 = 15 4 . Тогда
u 1 = 1 − 5 ⋅ 4 15 = − 1 3 . u_1=1-5\cdot\frac4{15}
=-\frac13. u 1 = 1 − 5 ⋅ 15 4 = − 3 1 . Итак,
u = ( − 1 3 ; − 1 ; 4 15 ) \boxed{
u=\left(-\frac13;-1;\frac4{15}\right)
} u = ( − 3 1 ; − 1 ; 15 4 ) Шаг 2. Вычисляем оценки
Небазисные индексы:
J Н = { 1 , 3 , 4 , 6 , 8 } . J_{\text{Н}}=\{1,3,4,6,8\}. J Н = { 1 , 3 , 4 , 6 , 8 } . Оценки:
Δ 1 = 9 5 , \Delta_1=\frac95, Δ 1 = 5 9 , Δ 3 = 46 15 , \Delta_3=\frac{46}{15}, Δ 3 = 15 46 , Δ 4 = 9 5 , \Delta_4=\frac95, Δ 4 = 5 9 , Δ 6 = − 2 3 , \Delta_6=-\frac23, Δ 6 = − 3 2 , Δ 8 = − 19 15 . \Delta_8=-\frac{19}{15}. Δ 8 = − 15 19 . Для x 4 x_4 x 4
x 4 = 17 = d ∗ 4 , Δ 4 = 9 5 > 0. x_4=17=d_{*4},\qquad \Delta_4=\frac95>0. x 4 = 17 = d ∗ 4 , Δ 4 = 5 9 > 0. Условие оптимальности нарушено.
Выбираем
j 0 = 4 , l 4 = 1. j_0=4,\qquad l_4=1. j 0 = 4 , l 4 = 1. Шаг 3. Находим направление
Для базисных переменных x 5 , x 7 , x 2 x_5,x_7,x_2 x 5 , x 7 , x 2
{ l 2 − 5 l 4 + 2 l 5 = 0 , l 2 + 4 l 4 − 2 l 5 + l 7 = 0 , 5 l 2 + 2 l 4 − 5 l 5 = 0. \begin{cases}
l_2-5l_4+2l_5=0,\\
l_2+4l_4-2l_5+l_7=0,\\
5l_2+2l_4-5l_5=0.
\end{cases} ⎩ ⎨ ⎧ l 2 − 5 l 4 + 2 l 5 = 0 , l 2 + 4 l 4 − 2 l 5 + l 7 = 0 , 5 l 2 + 2 l 4 − 5 l 5 = 0. Подставляем l 4 = 1 l_4=1 l 4 = 1
{ l 2 − 5 + 2 l 5 = 0 , l 2 + 4 − 2 l 5 + l 7 = 0 , 5 l 2 + 2 − 5 l 5 = 0. \begin{cases}
l_2-5+2l_5=0,\\
l_2+4-2l_5+l_7=0,\\
5l_2+2-5l_5=0.
\end{cases} ⎩ ⎨ ⎧ l 2 − 5 + 2 l 5 = 0 , l 2 + 4 − 2 l 5 + l 7 = 0 , 5 l 2 + 2 − 5 l 5 = 0. Из третьего уравнения:
l 2 = l 5 − 2 5 . l_2=l_5-\frac25. l 2 = l 5 − 5 2 . Подставляем в первое:
l 5 − 2 5 − 5 + 2 l 5 = 0 , l_5-\frac25-5+2l_5=0, l 5 − 5 2 − 5 + 2 l 5 = 0 , 3 l 5 = 27 5 , 3l_5=\frac{27}{5}, 3 l 5 = 5 27 , l 5 = 9 5 . l_5=\frac95. l 5 = 5 9 . Тогда
l 2 = 9 5 − 2 5 = 7 5 , l_2=\frac95-\frac25=\frac75, l 2 = 5 9 − 5 2 = 5 7 , l 7 = − 7 5 − 4 + 2 ⋅ 9 5 = − 9 5 . l_7=-\frac75-4+2\cdot\frac95
=-\frac95. l 7 = − 5 7 − 4 + 2 ⋅ 5 9 = − 5 9 . Направление:
l = ( 0 ; 7 5 ; 0 ; 1 ; 9 5 ; 0 ; − 9 5 ; 0 ) \boxed{
l=\left(0;\frac75;0;1;\frac95;0;-\frac95;0\right)
} l = ( 0 ; 5 7 ; 0 ; 1 ; 5 9 ; 0 ; − 5 9 ; 0 ) Шаг 4. Находим допустимый шаг
Для входящей переменной:
θ 4 = 30 − 17 1 = 13. \theta_4=\frac{30-17}{1}=13. θ 4 = 1 30 − 17 = 13. Для базисных переменных:
θ 2 = 11 − 3 / 5 7 / 5 = 52 7 , \theta_2=
\frac{11-3/5}{7/5}
=\frac{52}{7}, θ 2 = 7/5 11 − 3/5 = 7 52 , θ 5 = 25 − 76 / 5 9 / 5 = 49 9 , \theta_5=
\frac{25-76/5}{9/5}
=\frac{49}{9}, θ 5 = 9/5 25 − 76/5 = 9 49 , θ 7 = 0 − 9 / 5 − 9 / 5 = 1. \theta_7=
\frac{0-9/5}{-9/5}=1. θ 7 = − 9/5 0 − 9/5 = 1. Выбираем минимум:
θ 0 = min { 13 ; 52 7 ; 49 9 ; 1 } . \theta^0=
\min\left\{13;\frac{52}{7};\frac{49}{9};1\right\}. θ 0 = min { 13 ; 7 52 ; 9 49 ; 1 } . θ 0 = 1 \boxed{\theta^0=1} θ 0 = 1 Из базиса выходит x 7 x_7 x 7 x 4 x_4 x 4
Шаг 5. Новый план
x ( 3 ) = x ( 2 ) + l . x^{(3)}=x^{(2)}+l. x ( 3 ) = x ( 2 ) + l . Вычисляем:
x 2 = 3 5 + 7 5 = 2 , x_2=\frac35+\frac75=2, x 2 = 5 3 + 5 7 = 2 , x 4 = 17 + 1 = 18 , x_4=17+1=18, x 4 = 17 + 1 = 18 , x 5 = 76 5 + 9 5 = 17 , x_5=\frac{76}{5}+\frac95=17, x 5 = 5 76 + 5 9 = 17 , x 7 = 9 5 − 9 5 = 0. x_7=\frac95-\frac95=0. x 7 = 5 9 − 5 9 = 0. Следовательно,
x ( 3 ) = ( 29 ; 2 ; 7 ; 18 ; 17 ; 0 ; 0 ; 0 ) \boxed{x^{(3)}=(29;2;7;18;17;0;0;0)} x ( 3 ) = ( 29 ; 2 ; 7 ; 18 ; 17 ; 0 ; 0 ; 0 ) Новый базис:
J Б = { 5 , 4 , 2 } \boxed{J_{\text{Б}}=\{5,4,2\}} J Б = { 5 , 4 , 2 } Значение вспомогательной функции:
F ( 3 ) = − 0 − 0 − 0 = 0 . F^{(3)}=-0-0-0=\boxed{0}. F ( 3 ) = − 0 − 0 − 0 = 0 . Первая фаза завершена.
Все искусственные переменные равны нулю:
x 6 = x 7 = x 8 = 0. x_6=x_7=x_8=0. x 6 = x 7 = x 8 = 0. Кроме того, искусственных переменных больше нет в базисе. Поэтому, согласно теории из файла, мы получили допустимый базисный план исходной задачи и можем перейти непосредственно ко второй фазе без буферной задачи.
7. Вторая фаза симплекс-метода
Теперь возвращаемся к исходной целевой функции:
φ = − 16 x 1 + 35 x 2 + 12 x 3 + 5 x 4 − 29 x 5 → max . \varphi=-16x_1+35x_2+12x_3+5x_4-29x_5
\rightarrow\max. φ = − 16 x 1 + 35 x 2 + 12 x 3 + 5 x 4 − 29 x 5 → max . Начальный базисный план второй фазы:
x = ( 29 ; 2 ; 7 ; 18 ; 17 ) . x=(29;2;7;18;17). x = ( 29 ; 2 ; 7 ; 18 ; 17 ) . Базисные и небазисные индексы:
J Б = { 5 , 4 , 2 } , J_{\text{Б}}=\{5,4,2\}, J Б = { 5 , 4 , 2 } , J Н = { 1 , 3 } . J_{\text{Н}}=\{1,3\}. J Н = { 1 , 3 } . Шаг 1. Вычисляем потенциалы
Для базисных переменных выполняются уравнения
a j T u = c j . a_j^Tu=c_j. a j T u = c j . При j = 5 , 4 , 2 j=5,4,2 j = 5 , 4 , 2
{ 2 u 1 − 2 u 2 − 5 u 3 = − 29 , − 5 u 1 + 4 u 2 + 2 u 3 = 5 , u 1 + u 2 + 5 u 3 = 35. \begin{cases}
2u_1-2u_2-5u_3=-29,\\
-5u_1+4u_2+2u_3=5,\\
u_1+u_2+5u_3=35.
\end{cases} ⎩ ⎨ ⎧ 2 u 1 − 2 u 2 − 5 u 3 = − 29 , − 5 u 1 + 4 u 2 + 2 u 3 = 5 , u 1 + u 2 + 5 u 3 = 35. Решая эту систему, получаем:
u 1 = 7 3 , u 2 = 1 , u 3 = 19 3 \boxed{
u_1=\frac73,\quad
u_2=1,\quad
u_3=\frac{19}{3}
} u 1 = 3 7 , u 2 = 1 , u 3 = 3 19 Проверим:
2 ⋅ 7 3 − 2 − 5 ⋅ 19 3 = − 29 , 2\cdot\frac73-2-5\cdot\frac{19}{3}=-29, 2 ⋅ 3 7 − 2 − 5 ⋅ 3 19 = − 29 , − 5 ⋅ 7 3 + 4 + 2 ⋅ 19 3 = 5 , -5\cdot\frac73+4+2\cdot\frac{19}{3}=5, − 5 ⋅ 3 7 + 4 + 2 ⋅ 3 19 = 5 , 7 3 + 1 + 5 ⋅ 19 3 = 35. \frac73+1+5\cdot\frac{19}{3}=35. 3 7 + 1 + 5 ⋅ 3 19 = 35. Все три уравнения выполняются.
Шаг 2. Вычисляем небазисные оценки
Небазисные переменные — x 1 x_1 x 1 x 3 x_3 x 3
Оценка Δ 1 \Delta_1 Δ 1
Δ 1 = c 1 − a 1 T u . \Delta_1=c_1-a_1^Tu. Δ 1 = c 1 − a 1 T u . Δ 1 = − 16 − ( u 2 − 3 u 3 ) . \Delta_1=-16-(u_2-3u_3). Δ 1 = − 16 − ( u 2 − 3 u 3 ) . Подставляем потенциалы:
Δ 1 = − 16 − ( 1 − 3 ⋅ 19 3 ) = − 16 − ( 1 − 19 ) = − 16 + 18 = 2. \begin{aligned}
\Delta_1
&=-16-\left(1-3\cdot\frac{19}{3}\right)\\
&=-16-(1-19)\\
&=-16+18=2.
\end{aligned} Δ 1 = − 16 − ( 1 − 3 ⋅ 3 19 ) = − 16 − ( 1 − 19 ) = − 16 + 18 = 2. Δ 1 = 2 \boxed{\Delta_1=2} Δ 1 = 2 Оценка Δ 3 \Delta_3 Δ 3
Δ 3 = c 3 − a 3 T u , \Delta_3=c_3-a_3^Tu, Δ 3 = c 3 − a 3 T u , Δ 3 = 12 − ( u 1 + 3 u 2 + u 3 ) . \Delta_3=12-(u_1+3u_2+u_3). Δ 3 = 12 − ( u 1 + 3 u 2 + u 3 ) . Подставляем:
Δ 3 = 12 − ( 7 3 + 3 + 19 3 ) = 12 − 35 3 = 36 3 − 35 3 = 1 3 . \begin{aligned}
\Delta_3
&=12-\left(\frac73+3+\frac{19}{3}\right)\\
&=12-\frac{35}{3}\\
&=\frac{36}{3}-\frac{35}{3}\\
&=\frac13.
\end{aligned} Δ 3 = 12 − ( 3 7 + 3 + 3 19 ) = 12 − 3 35 = 3 36 − 3 35 = 3 1 . Δ 3 = 1 3 \boxed{\Delta_3=\frac13} Δ 3 = 3 1 Шаг 3. Проверяем условия оптимальности
По теории из файла, для небазисных переменных, находящихся на верхней границе, должно выполняться условие
Δ j ≥ 0. \Delta_j\ge0. Δ j ≥ 0. Проверим:
Переменная Значение Оценка Условие x 1 x_1 x 1 29 = d 1 ∗ 29=d_1^* 29 = d 1 ∗ Δ 1 = 2 > 0 \Delta_1=2>0 Δ 1 = 2 > 0 Выполнено x 3 x_3 x 3 7 = d 3 ∗ 7=d_3^* 7 = d 3 ∗ Δ 3 = 1 3 > 0 \Delta_3=\frac13>0 Δ 3 = 3 1 > 0 Выполнено
Все условия оптимальности выполняются.
Следовательно, полученный базисный план оптимален. Дополнительных итераций второй фазы не требуется.
8. Вычисление максимума целевой функции
Подставим найденные значения:
x 1 = 29 , x 2 = 2 , x 3 = 7 , x_1=29,\quad x_2=2,\quad x_3=7, x 1 = 29 , x 2 = 2 , x 3 = 7 , x 4 = 18 , x 5 = 17. x_4=18,\quad x_5=17. x 4 = 18 , x 5 = 17. Вычисляем:
φ max = − 16 ⋅ 29 + 35 ⋅ 2 + 12 ⋅ 7 + 5 ⋅ 18 − 29 ⋅ 17 = − 464 + 70 + 84 + 90 − 493 = − 713 . \begin{aligned}
\varphi_{\max}
&=-16\cdot29+35\cdot2+12\cdot7\\
&\quad+5\cdot18-29\cdot17\\
&=-464+70+84+90-493\\
&=\boxed{-713}.
\end{aligned} φ m a x = − 16 ⋅ 29 + 35 ⋅ 2 + 12 ⋅ 7 + 5 ⋅ 18 − 29 ⋅ 17 = − 464 + 70 + 84 + 90 − 493 = − 713 . 9. Проверка исходных ограничений
Первое уравнение:
2 + 7 − 5 ⋅ 18 + 2 ⋅ 17 = 2 + 7 − 90 + 34 = − 47. 2+7-5\cdot18+2\cdot17
=2+7-90+34=-47. 2 + 7 − 5 ⋅ 18 + 2 ⋅ 17 = 2 + 7 − 90 + 34 = − 47. Второе уравнение:
29 + 2 + 3 ⋅ 7 + 4 ⋅ 18 − 2 ⋅ 17 29+2+3\cdot7+4\cdot18-2\cdot17 29 + 2 + 3 ⋅ 7 + 4 ⋅ 18 − 2 ⋅ 17 = 29 + 2 + 21 + 72 − 34 = 90. =29+2+21+72-34=90. = 29 + 2 + 21 + 72 − 34 = 90. Третье уравнение:
− 3 ⋅ 29 + 5 ⋅ 2 + 7 + 2 ⋅ 18 − 5 ⋅ 17 -3\cdot29+5\cdot2+7+2\cdot18-5\cdot17 − 3 ⋅ 29 + 5 ⋅ 2 + 7 + 2 ⋅ 18 − 5 ⋅ 17 = − 87 + 10 + 7 + 36 − 85 = − 119. =-87+10+7+36-85=-119. = − 87 + 10 + 7 + 36 − 85 = − 119. Все три равенства выполняются.
Проверим границы переменных:
20 ≤ 29 ≤ 29 , − 2 ≤ 2 ≤ 11 , − 7 ≤ 7 ≤ 7 , 17 ≤ 18 ≤ 30 , 14 ≤ 17 ≤ 25. \begin{aligned}
20&\le29\le29,\\
-2&\le2\le11,\\
-7&\le7\le7,\\
17&\le18\le30,\\
14&\le17\le25.
\end{aligned} 20 − 2 − 7 17 14 ≤ 29 ≤ 29 , ≤ 2 ≤ 11 , ≤ 7 ≤ 7 , ≤ 18 ≤ 30 , ≤ 17 ≤ 25. Все ограничения выполнены.
10. Итог решения
За три итерации первой фазы получен допустимый базисный план исходной задачи:
x = ( 29 ; 2 ; 7 ; 18 ; 17 ) . x=(29;2;7;18;17). x = ( 29 ; 2 ; 7 ; 18 ; 17 ) . Во второй фазе вычислены потенциалы и небазисные оценки:
u = ( 7 3 ; 1 ; 19 3 ) , u=\left(\frac73;1;\frac{19}{3}\right), u = ( 3 7 ; 1 ; 3 19 ) , Δ 1 = 2 , Δ 3 = 1 3 . \Delta_1=2,\qquad \Delta_3=\frac13. Δ 1 = 2 , Δ 3 = 3 1 . Обе небазисные переменные находятся на верхних границах, а их оценки положительны. Поэтому выполнен критерий оптимальности из приложенного файла.
Окончательно:
x 1 ∗ = 29 , x 2 ∗ = 2 , x 3 ∗ = 7 , x 4 ∗ = 18 , x 5 ∗ = 17 , φ max = − 713. \boxed{
\begin{gathered}
x_1^*=29,\qquad x_2^*=2,\\
x_3^*=7,\qquad x_4^*=18,\\
x_5^*=17,\\[4pt]
\varphi_{\max}=-713.
\end{gathered}
} x 1 ∗ = 29 , x 2 ∗ = 2 , x 3 ∗ = 7 , x 4 ∗ = 18 , x 5 ∗ = 17 , φ m a x = − 713. Задача решена симплекс-методом полностью: выполнена первая фаза с тремя заменами базиса, получен допустимый план, проведена вторая фаза и доказана оптимальность найденного решения.
