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

Решение:
Парчетата, изрязани извън поръчката, са просто отпадък, затова броим само поръчаните парчета. Общата им дължина (в сантиметри) е
[tex]320\cdot 560+260\cdot 480+120\cdot 780=179200+124800+93600=397600[/tex]
Долна граница. Тъй като [tex]2\cdot 320=640\gt 600[/tex], парчетата от [tex]320[/tex] см (общо [tex]560[/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] ръба.