Линейно програмиране и оптимизация - трудни задачи с решения

Решение:
За всяко [tex]a[/tex] началото на координатната система удовлетворява всички ограничения, затова допустимото множество [tex]D[/tex] никога не е празно; въпросът е само дали [tex]z[/tex] е ограничена отгоре в [tex]D[/tex].
Случай [tex]a\gt 0[/tex]. От [tex]x_1+ax_2\le 3[/tex] и [tex]x_1, x_2\ge 0[/tex] получаваме
[tex]0\le x_1\le 3,\qquad 0\le x_2\le\frac{3}{a}[/tex]
следователно [tex]D[/tex] е ограничен затворен многоъгълник и линейната функция достига максимума си в него (във връх). Всъщност при [tex]x_1\le 3[/tex] първите две ограничения са изпълнени автоматично ([tex]x_1-2x_2\le 3\lt 4[/tex], [tex]x_1-x_2\le 3\lt 6[/tex]), така че [tex]D[/tex] е триъгълникът с върхове [tex]\left(0 ; 0\right)[/tex], [tex]\left(3 ; 0\right)[/tex], [tex]\left(0 ; \frac{3}{a}\right)[/tex] и
[tex]z_{\max}=\max\left\{6 ; \frac{3}{a}\right\}[/tex]
Случай [tex]a\le 0[/tex]. Всяка точка [tex]\left(0 ; t\right)[/tex] с [tex]t\ge 0[/tex] е допустима, защото
[tex]-2t\le 4,\qquad -t\le 6,\qquad at\le 0\le 3[/tex]
Геометрично цялата положителна полуос [tex]Ox_2[/tex] лежи в [tex]D[/tex], а по нея [tex]z\left(0 ; t\right)=t\to+\infty[/tex], така че [tex]z[/tex] няма максимум. (Това включва и [tex]a=0[/tex], когато третото ограничение е просто [tex]x_1\le 3[/tex].)
Задачата има решение точно при [tex]a\in\left(0 ; +\infty\right)[/tex].

Решение:
Всяка от променливите [tex]x_1, x_4, x_6[/tex] участва с коефициент [tex]1[/tex] в точно едно уравнение, затова началното базисно допустимо решение е [tex]x_1=7[/tex], [tex]x_4=12[/tex], [tex]x_6=10[/tex], останалите променливи са [tex]0[/tex], при [tex]F=14{,}76[/tex]. Базисните променливи имат нулева цена, затова относителните оценки на свободните променливи са коефициентите им в [tex]F[/tex]:
[tex]\Delta_2=1,\qquad \Delta_3=-3,\qquad \Delta_5=-2[/tex]
При минимизация отрицателна оценка означава, че [tex]F[/tex] може още да намалява. Итерация [tex]1[/tex]: в базиса влиза [tex]x_3[/tex] (най-отрицателна оценка). Отношенията за положителните елементи в нейния стълб са [tex]\frac{12}{4}=3[/tex] (ред [tex]2[/tex]) и [tex]\frac{10}{3}[/tex] (ред [tex]3[/tex]); минимумът е в ред [tex]2[/tex], затова от базиса излиза [tex]x_4[/tex]. След преобразуването:
[tex]x_3=3+\frac{1}{2}x_2-\frac{1}{4}x_4,\quad x_1=10-\frac{5}{2}x_2-\frac{1}{4}x_4-2x_5,\quad x_6=1+\frac{5}{2}x_2+\frac{3}{4}x_4-8x_5[/tex]
[tex]F=5{,}76-\frac{1}{2}x_2+\frac{3}{4}x_4-2x_5[/tex]
Итерация [tex]2[/tex]: влиза [tex]x_5[/tex] (оценка [tex]-2[/tex]); отношенията са [tex]\frac{10}{2}=5[/tex] и [tex]\frac{1}{8}[/tex], затова излиза [tex]x_6[/tex]:
[tex]x_5=\frac{1}{8}+\frac{5}{16}x_2+\frac{3}{32}x_4-\frac{1}{8}x_6,\quad x_1=\frac{39}{4}-\frac{25}{8}x_2-\frac{7}{16}x_4+\frac{1}{4}x_6[/tex]
[tex]F=5{,}51-\frac{9}{8}x_2+\frac{9}{16}x_4+\frac{1}{4}x_6[/tex]
Итерация [tex]3[/tex]: влиза [tex]x_2[/tex] (оценка [tex]-\frac{9}{8}[/tex]). В изразите за [tex]x_3[/tex] и [tex]x_5[/tex] коефициентът пред [tex]x_2[/tex] е положителен, така че нарастването на [tex]x_2[/tex] не ги прави отрицателни; само редът на [tex]x_1[/tex] ограничава [tex]x_2[/tex], затова излиза [tex]x_1[/tex]:
[tex]x_2=\frac{78}{25}-\frac{8}{25}x_1-\frac{7}{50}x_4+\frac{2}{25}x_6,\qquad F=2+\frac{9}{25}x_1+\frac{18}{25}x_4+\frac{4}{25}x_6[/tex]
Сега всички оценки са неотрицателни, затова решението е оптимално: [tex]x_1=x_4=x_6=0[/tex] и
[tex]x_2=\frac{78}{25}=3{,}12,\quad x_3=3+\frac{1}{2}\cdot 3{,}12=4{,}56,\quad x_5=\frac{1}{8}+\frac{5}{16}\cdot 3{,}12=1{,}1[/tex]
Проверка: [tex]3{,}12-3\cdot 4{,}56-2\cdot 1{,}1+14{,}76=2[/tex], а левите страни на трите ограничения са равни на [tex]7[/tex], [tex]12[/tex], [tex]10[/tex]. Минималните разходи са [tex]F_{\min}=2[/tex].

Решение:
Всяка от променливите [tex]x_1, x_2, x_3, x_5[/tex] участва само в едно уравнение, затова ги изразяваме чрез [tex]x_4[/tex] и [tex]x_6[/tex]:
[tex]x_1=13-3x_6,\quad x_2=18+x_4-2x_6,\quad x_3=3+2x_4-x_6,\quad x_5=12+3x_4-x_6[/tex]
Заместваме в [tex]z[/tex]:
[tex]z=5\left(13-3x_6\right)+\left(18+x_4-2x_6\right)+2\left(3+2x_4-x_6\right)+4x_4+3\left(12+3x_4-x_6\right)+20x_6=125+18x_4-2x_6[/tex]
При [tex]x_4=x_6=0[/tex] получаваме допустима точка със [tex]z=125[/tex], но [tex]z[/tex] още намалява, когато [tex]x_6[/tex] расте. Нарастването на [tex]x_6[/tex] се ограничава от [tex]x_3=3+2x_4-x_6\ge 0[/tex], т.е. [tex]x_6\le 3+2x_4[/tex]. Следователно в допустимото множество, като използваме [tex]x_4\ge 0[/tex],
[tex]z=125+18x_4-2x_6\ge 125+18x_4-2\left(3+2x_4\right)=119+14x_4\ge 119[/tex]
Равенство се достига само при [tex]x_4=0[/tex] и [tex]x_6=3[/tex]; тогава [tex]x_1=4[/tex], [tex]x_2=12[/tex], [tex]x_3=0[/tex], [tex]x_5=9[/tex] са неотрицателни, следователно точката [tex]\left(4 ; 12 ; 0 ; 0 ; 9 ; 3\right)[/tex] е допустима и
[tex]z=20+12+0+0+27+60=119[/tex]
Най-малката стойност е [tex]119[/tex].

Решение:
Наличността е [tex]20+10+15=45[/tex] тона, а потребностите са [tex]15+20+15+10=60[/tex] тона, следователно задачата е небалансирана (открита). Добавяме фиктивен склад [tex]A_4[/tex] с [tex]15[/tex] тона и нулеви разходи; това, което той „доставя“, е неудовлетвореното търсене. Нека [tex]x_{ij}[/tex] е количеството (в тонове), превозено от [tex]A_i[/tex] до [tex]B_j[/tex].
Методът на минималния елемент (първо клетките на [tex]A_4[/tex] с нулеви разходи, след това най-евтините реални клетки) дава началния план и разходите по него:
[tex]x_{41}=15,\ x_{12}=20,\ x_{24}=10,\ x_{33}=15,\qquad z=20\cdot 1+10\cdot 2+15\cdot 5=115[/tex]
По цикъла [tex](A_2B_3)^{+},\ (A_2B_4)^{-},\ (A_3B_4)^{+},\ (A_3B_3)^{-}[/tex] разходите се изменят с [tex]3-2+3-5=-1[/tex] на тон, а по него могат да се преместят [tex]\theta=\min(10; 15)=10[/tex] тона. Новият план ([tex]B_1[/tex] остава незадоволен) и разходите по него:
[tex]x_{12}=20,\ x_{23}=10,\ x_{33}=5,\ x_{34}=10,\qquad z=20\cdot 1+10\cdot 3+5\cdot 5+10\cdot 3=105[/tex]
Проверка за оптималност с потенциали: вземаме [tex]u_1=2,\ u_2=3,\ u_3=5,\ u_4=0[/tex] и [tex]v_1=0,\ v_2=-1,\ v_3=0,\ v_4=-2[/tex]. Тогава [tex]u_i+v_j=c_{ij}[/tex] във всяка заета клетка, а всички оценки [tex]c_{ij}-u_i-v_j[/tex] (по редове, последният ред е за [tex]A_4[/tex]) са неотрицателни:
[tex]\begin{bmatrix}0&0&2&6\\1&4&0&1\\1&0&0&0\\0&1&0&2\end{bmatrix}[/tex]
Следователно за всеки допустим план (цялата наличност е превозена, [tex]B_j[/tex] получава [tex]r_j[/tex] тона, не повече от нужното), тъй като [tex]c_{ij}\ge u_i+v_j[/tex] при [tex]i=1,2,3[/tex], имаме
[tex]\sum_{i,j} c_{ij}x_{ij}\ge\sum_{i,j}(u_i+v_j)x_{ij}=2\cdot 20+3\cdot 10+5\cdot 15-r_2-2r_4\ge 145-20-2\cdot 10=105[/tex]
защото [tex]r_2\le 20[/tex] и [tex]r_4\le 10[/tex]. Значи няма по-евтин план и минималните общи разходи са [tex]105[/tex] евро.

Решение:
Това е задача за назначенията; прилагаме унгарския метод. Изваждането на константа от цял ред или стълб променя общото време на всяко разпределение с една и съща константа, защото всяко разпределение използва точно по един елемент от всеки ред и от всеки стълб.
Изваждаме минимумите по редове [tex]64, 52, 56, 60[/tex] (сума [tex]232[/tex]), а след това минимумите по стълбове [tex]2, 0, 6, 0[/tex] на новата матрица (сума [tex]8[/tex]):
[tex]\begin{bmatrix}6&16&11&0\\3&0&6&2\\2&0&8&12\\2&0&7&10\end{bmatrix}\ \to\ \begin{bmatrix}4&16&5&0\\1&0&0&2\\0&0&2&12\\0&0&1&10\end{bmatrix}[/tex]
Всички елементи са неотрицателни, затова всяко разпределение изисква поне [tex]232+8=240[/tex] минути. Има четири независими нули: работник [tex]1[/tex] на машина [tex]D[/tex], работник [tex]2[/tex] на [tex]C[/tex], работник [tex]3[/tex] на [tex]A[/tex], работник [tex]4[/tex] на [tex]B[/tex]. Това разпределение достига долната граница:
[tex]64+58+58+60=240[/tex]
(Друго оптимално разпределение е [tex]1\to D,\ 2\to C,\ 3\to B,\ 4\to A[/tex] с [tex]64+58+56+62=240[/tex].) Минималното общо време е [tex]240[/tex] минути.