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

Решение:
Нека [tex]x_1\ge 0[/tex] и [tex]x_2\ge 0[/tex] са количествата на [tex]P_1[/tex] и [tex]P_2[/tex] в сместа. Трябва да минимизираме цената [tex]Z[/tex] при ограниченията:
[tex]Z=3x_1+2x_2\to\min,\qquad 5x_1+x_2\ge 10,\quad x_1+x_2\ge 6,\quad x_1+2x_2\ge 8[/tex]
Всяко ограничение задава полуравнината над съответната гранична права, затова допустимото множество е неограничено. Върховете му са пресечните точки на последователните гранични прави:
[tex]x_1=0,\ 5x_1+x_2=10\Rightarrow A\left(0 ; 10\right)[/tex]
[tex]5x_1+x_2=10,\ x_1+x_2=6\Rightarrow 4x_1=4\Rightarrow B\left(1 ; 5\right)[/tex]
[tex]x_1+x_2=6,\ x_1+2x_2=8\Rightarrow x_2=2\Rightarrow C\left(4 ; 2\right)[/tex]
[tex]x_1+2x_2=8,\ x_2=0\Rightarrow D\left(8 ; 0\right)[/tex]
Всяка от тези точки удовлетворява всички ограничения (напр. в [tex]B[/tex]: [tex]x_1+2x_2=11\ge 8[/tex]). Въпреки че множеството е неограничено, коефициентите на [tex]Z[/tex] са положителни, затова [tex]Z\ge 0[/tex] е ограничена отдолу и минимумът ѝ се достига във връх:
[tex]Z(A)=20,\quad Z(B)=13,\quad Z(C)=16,\quad Z(D)=24[/tex]
Проверка без чертеж: за всяка допустима точка
[tex]3x_1+2x_2=\frac{1}{4}\left(5x_1+x_2\right)+\frac{7}{4}\left(x_1+x_2\right)\ge\frac{10}{4}+\frac{42}{4}=13[/tex]
Най-евтината смес ([tex]x_1=1[/tex], [tex]x_2=5[/tex]) струва [tex]13[/tex] евро.

Решение:
Допустимото множество [tex]D[/tex] е изпъкнал многостен; то е непразно (съдържа началото на координатната система) и ограничено (защото [tex]0\le x_i\le 1[/tex]). Линейната функция е непрекъсната, затова върху свързаното компактно множество [tex]D[/tex] тя приема точно всички стойности от затворения интервал [tex]\left[z_{\min} ; z_{\max}\right][/tex].
Тъй като [tex]x_1, x_2, x_3\ge 0[/tex], имаме [tex]z\le 0[/tex], а в допустимата точка [tex]\left(0 ; 0 ; 0\right)[/tex] е изпълнено [tex]z=0[/tex]:
[tex]z_{\max}=0[/tex]
От третото ограничение [tex]z=-\left(x_1+x_2+x_3\right)\ge -1[/tex]. Точката [tex]\left(1 ; 0 ; 0\right)[/tex] е допустима ([tex]3\le 6[/tex], [tex]1\le 6[/tex], [tex]1\le 1[/tex]) и в нея [tex]z=-1[/tex]:
[tex]z_{\min}=-1[/tex]
(Първите две ограничения всъщност са излишни: [tex]3x_1+3x_2+x_3\le 3\left(x_1+x_2+x_3\right)\le 3\lt 6[/tex] и аналогично [tex]x_1+x_2+3x_3\le 3\lt 6[/tex].) Множеството от стойности е [tex]\left[-1 ; 0\right][/tex].

Решение:
При цена [tex]x[/tex] фирмата продава [tex]d(x)=400-10x[/tex] изделия, което има смисъл при [tex]0\le x\le 40[/tex]. Печалбата е приходът минус общите разходи:
[tex]P(x)=x\left(400-10x\right)-10\left(400-10x\right)-2000=\left(x-10\right)\left(400-10x\right)-2000=-10x^2+500x-6000[/tex]
Производната се анулира при [tex]x=25\in\left[0 ; 40\right][/tex], а тъй като [tex]P''(x)=-20\lt 0[/tex] (клоните на параболата са насочени надолу), тази критична точка е глобален максимум:
[tex]P'(x)=-20x+500=0\Rightarrow x=25,\qquad d(25)=150[/tex]
[tex]P(25)=15\cdot 150-2000=2250-2000=250[/tex]
Максималната печалба е [tex]250[/tex] евро (при цена [tex]25[/tex] евро за изделие).