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

Решение:
При любом [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_2[/tex] ограничивает только строка [tex]x_1[/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] минут.