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

Решение:
Заготовки сверх заказа — это просто отходы, поэтому учитываем только заказанные заготовки. Их общая длина (в сантиметрах) равна
[tex]320\cdot 560+260\cdot 480+120\cdot 780=179200+124800+93600=397600[/tex]
Нижняя оценка. Так как [tex]2\cdot 320=640\gt 600[/tex], все [tex]560[/tex] заготовок по [tex]320[/tex] см находятся в [tex]560[/tex] разных профилях. В таком профиле остаётся [tex]280[/tex] см, куда помещается либо одна заготовка [tex]260[/tex] см и больше ничего (так как [tex]260+120\gt 280[/tex]), либо не более двух заготовок по [tex]120[/tex] см (так как [tex]3\cdot 120=360\gt 280[/tex]). Значит, профиль с заготовкой [tex]320[/tex] см содержит не более [tex]580[/tex] см заказанных заготовок, если в нём есть ещё и заготовка [tex]260[/tex] см, и не более [tex]560[/tex] см в противном случае.
Пусть [tex]k[/tex] — число профилей, содержащих одновременно заготовку [tex]320[/tex] см и заготовку [tex]260[/tex] см; тогда [tex]k\le 480[/tex]. Если использовано [tex]N[/tex] профилей, то общая длина заказанных заготовок не превосходит
[tex]580k+560(560-k)+600(N-560)=600N-40\cdot 560+20k\le 600N-22400+9600=600N-12800[/tex]
Она должна быть не меньше [tex]397600[/tex], поэтому
[tex]600N\ge 410400\Rightarrow N\ge 684[/tex]
Построение: раскраиваем [tex]480[/tex] профилей по схеме [tex]320+260[/tex] (отход по [tex]20[/tex] см), [tex]80[/tex] профилей по схеме [tex]320+120+120[/tex] (отход по [tex]40[/tex] см) и [tex]124[/tex] профиля по схеме [tex]5\cdot 120[/tex] (без отходов). Получаем [tex]480+80=560[/tex] заготовок по [tex]320[/tex] см, [tex]480[/tex] заготовок по [tex]260[/tex] см и [tex]2\cdot 80+5\cdot 124=780[/tex] заготовок по [tex]120[/tex] см, используя [tex]480+80+124=684[/tex] профиля; общий отход [tex]684\cdot 600-397600=12800[/tex] см — наименьший возможный. Наименьшее число стандартных профилей равно [tex]684[/tex].

Решение:
Из уравнения [tex]x_3=10-2x_1+x_2[/tex]; это целое число при целых [tex]x_1, x_2[/tex]. Подставляем в [tex]z[/tex]:
[tex]z=3x_1-5x_2+30-6x_1+3x_2=30-3x_1-2x_2[/tex]
Два ограничения-неравенства и условие [tex]x_3\ge 0[/tex] принимают вид:
[tex]x_1-2x_2+x_3\ge 3\Leftrightarrow 10-x_1-x_2\ge 3\Leftrightarrow x_1+x_2\le 7[/tex]
[tex]5x_1-4x_2+2x_3\ge 16\Leftrightarrow x_1-2x_2+20\ge 16\Leftrightarrow x_1-2x_2\ge -4[/tex]
[tex]x_3\ge 0\Leftrightarrow 2x_1-x_2\le 10[/tex]
Значит, нужно максимизировать [tex]w=3x_1+2x_2[/tex] (тогда [tex]z=30-w[/tex]) на целых точках с [tex]x_1, x_2\ge 0[/tex], удовлетворяющих этим трём ограничениям. Без условия целочисленности оптимум достигается в точке пересечения прямых [tex]x_1+x_2=7[/tex] и [tex]2x_1-x_2=10[/tex], т.е. в [tex]\left(\frac{17}{3}; \frac{4}{3}\right)[/tex] с [tex]w=\frac{59}{3}[/tex], а эта точка не целочисленная. Действительно, для любой допустимой точки
[tex]w=\frac{7}{3}(x_1+x_2)+\frac{1}{3}(2x_1-x_2)\le\frac{49}{3}+\frac{10}{3}=\frac{59}{3}\lt 20[/tex]
Так как в целых точках [tex]w[/tex] — целое число, [tex]w\le 19[/tex]. Точка [tex]x_1=5,\ x_2=2[/tex] даёт [tex]w=19[/tex] и удовлетворяет условиям [tex]5+2=7\le 7[/tex], [tex]5-4=1\ge -4[/tex], [tex]10-2=8\le 10[/tex]; тогда [tex]x_3=10-10+2=2[/tex]. Проверка в исходной задаче:
[tex]5-4+2=3\ge 3,\quad 25-8+4=21\ge 16,\quad 10-2+2=10,\quad z=15-10+6=11[/tex]
Минимум равен [tex]z_{\min}=30-19=11[/tex] и достигается в точке [tex](5; 2; 2)[/tex].

Решение:
При [tex]x[/tex] рейсах фирма получает прибыль
[tex]\pi(x)=100x-25x-0{,}01x^2=75x-0{,}01x^2[/tex]
При [tex]x_A[/tex] рейсах фирмы [tex]A[/tex] и [tex]x_B[/tex] рейсах фирмы [tex]B[/tex] максимизируем [tex]\Pi=\pi(x_A)+\pi(x_B)[/tex] при ограничениях [tex]x_A+2x_B\le 3000[/tex], [tex]x_A, x_B\ge 0[/tex]. Так как [tex]\pi'(x)=75-0{,}02x\gt 0[/tex] при [tex]x\lt 3750[/tex], а всегда [tex]x_A\le 3000[/tex], оставшиеся баллы можно было бы использовать на дополнительные рейсы фирмы [tex]A[/tex] и увеличить прибыль. Значит, в оптимуме используются все баллы: [tex]x_A=3000-2x_B[/tex], [tex]0\le x_B\le 1500[/tex], и для [tex]f(x_B)=\pi(3000-2x_B)+\pi(x_B)[/tex] получаем
[tex]f'(x_B)=-2\left(75-0{,}02(3000-2x_B)\right)+75-0{,}02x_B=45-0{,}1x_B[/tex]
Производная обращается в нуль при [tex]x_B=450[/tex], а [tex]f''=-0{,}1\lt 0[/tex], поэтому это максимум на отрезке; тогда [tex]x_A=3000-900=2100[/tex]. (Равносильно: условия Лагранжа [tex]75-0{,}02x_A=\lambda[/tex], [tex]75-0{,}02x_B=2\lambda[/tex] дают [tex]\lambda=33[/tex] евро — предельную ценность одного экобалла.) Прибыли равны
[tex]\pi(2100)=157500-44100=113400,\qquad \pi(450)=33750-2025=31725[/tex]
[tex]\Pi_{\max}=113400+31725=145125[/tex]
Для сравнения: без сотрудничества ([tex]x_A=1500[/tex], [tex]x_B=750[/tex]) общая прибыль равна [tex]90000+50625=140625[/tex], а при использовании только новых грузовиков ([tex]x_A=3000[/tex]) — [tex]135000[/tex]. Максимальная общая прибыль равна [tex]145125[/tex] евро.

Решение:
Вершины [tex]S[/tex] — это допустимые точки, в которых пересекаются три из шести граничных плоскостей с линейно независимыми нормалями. Решив все такие системы и оставив допустимые решения, получаем [tex]7[/tex] вершин:
[tex]O(0; 0; 0),\ \ (11; 0; 0),\ \ (0; 9; 0),\ \ (0; 0; 8),\ \ (4; 7; 0),\ \ (9; 0; 2),\ \ (0; 3; 8)[/tex]
Например, [tex]x+y+z=11[/tex], [tex]2x+3z=24[/tex] и [tex]y=0[/tex] дают [tex](9; 0; 2)[/tex], а точка [tex](12; 0; 0)[/tex], полученная из [tex]2x+3z=24[/tex], [tex]y=z=0[/tex], отбрасывается, так как [tex]12\gt 11[/tex]. Вершина [tex](0; 3; 8)[/tex] вырожденная: через неё проходят четыре плоскости, а именно [tex]x=0[/tex], [tex]x+y+z=11[/tex], [tex]2x+4y+3z=36[/tex] и [tex]2x+3z=24[/tex]. Каждая из шести плоскостей содержит грань со следующими вершинами:
[tex]x=0:\quad O,\ (0; 9; 0),\ (0; 3; 8),\ (0; 0; 8)[/tex]
[tex]y=0:\quad O,\ (11; 0; 0),\ (9; 0; 2),\ (0; 0; 8)[/tex]
[tex]z=0:\quad O,\ (11; 0; 0),\ (4; 7; 0),\ (0; 9; 0)[/tex]
[tex]x+y+z=11:\quad (11; 0; 0),\ (9; 0; 2),\ (0; 3; 8),\ (4; 7; 0)[/tex]
[tex]2x+4y+3z=36:\quad (0; 9; 0),\ (4; 7; 0),\ (0; 3; 8)[/tex]
[tex]2x+3z=24:\quad (0; 0; 8),\ (9; 0; 2),\ (0; 3; 8)[/tex]
Итак, четыре грани — четырёхугольники, а две — треугольники. Каждое ребро принадлежит ровно двум граням, поэтому
[tex]E=\frac{4\cdot 4+2\cdot 3}{2}=11[/tex]
Проверка по формуле Эйлера: [tex]V-E+F=7-11+6=2[/tex]. Также по степеням: вершина [tex](0; 3; 8)[/tex] соединена рёбрами с [tex]4[/tex] вершинами ([tex](0; 9; 0)[/tex], [tex](0; 0; 8)[/tex], [tex](9; 0; 2)[/tex], [tex](4; 7; 0)[/tex]), а каждая из остальных [tex]6[/tex] вершин — с [tex]3[/tex], поэтому [tex]E=\frac{4+6\cdot 3}{2}=11[/tex] (если считать, что все вершины имеют степень [tex]3[/tex], получилось бы невозможное [tex]\frac{21}{2}[/tex]). Многогранник имеет [tex]11[/tex] рёбер.