Linearno programiranje i optimizacija - zadaci sa rešenjima

Rešenje:
Neka su [tex]x_1\ge 0[/tex] i [tex]x_2\ge 0[/tex] količine proizvoda [tex]P_1[/tex] i [tex]P_2[/tex] u smeši. Treba minimizovati cenu [tex]Z[/tex] pri ograničenjima:
[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]
Svako ograničenje određuje poluravan iznad odgovarajuće granične prave, pa je dopustivi skup neograničen. Njegova temena su presečne tačke uzastopnih graničnih pravih:
[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]
Svaka od ovih tačaka zadovoljava sva ograničenja (npr. u [tex]B[/tex]: [tex]x_1+2x_2=11\ge 8[/tex]). Iako je skup neograničen, koeficijenti funkcije [tex]Z[/tex] su pozitivni, pa je [tex]Z\ge 0[/tex] ograničena odozdo i njen minimum se dostiže u temenu:
[tex]Z(A)=20,\quad Z(B)=13,\quad Z(C)=16,\quad Z(D)=24[/tex]
Provera bez crteža: za svaku dopustivu tačku važi
[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]
Najjeftinija smeša ([tex]x_1=1[/tex], [tex]x_2=5[/tex]) košta [tex]13[/tex] evra.

Rešenje:
Dopustivi skup [tex]D[/tex] je konveksan poliedar; on je neprazan (sadrži koordinatni početak) i ograničen (jer je [tex]0\le x_i\le 1[/tex]). Linearna funkcija je neprekidna, pa na povezanom kompaktnom skupu [tex]D[/tex] uzima tačno sve vrednosti iz zatvorenog intervala [tex]\left[z_{\min} ; z_{\max}\right][/tex].
Pošto je [tex]x_1, x_2, x_3\ge 0[/tex], važi [tex]z\le 0[/tex], a u dopustivoj tački [tex]\left(0 ; 0 ; 0\right)[/tex] je [tex]z=0[/tex]:
[tex]z_{\max}=0[/tex]
Iz trećeg ograničenja sledi [tex]z=-\left(x_1+x_2+x_3\right)\ge -1[/tex]. Tačka [tex]\left(1 ; 0 ; 0\right)[/tex] je dopustiva ([tex]3\le 6[/tex], [tex]1\le 6[/tex], [tex]1\le 1[/tex]) i u njoj je [tex]z=-1[/tex]:
[tex]z_{\min}=-1[/tex]
(Prva dva ograničenja su zapravo suvišna: [tex]3x_1+3x_2+x_3\le 3\left(x_1+x_2+x_3\right)\le 3\lt 6[/tex] i slično [tex]x_1+x_2+3x_3\le 3\lt 6[/tex].) Skup vrednosti je [tex]\left[-1 ; 0\right][/tex].

Rešenje:
Pri ceni [tex]x[/tex] firma prodaje [tex]d(x)=400-10x[/tex] proizvoda, što ima smisla za [tex]0\le x\le 40[/tex]. Profit je prihod umanjen za ukupne troškove:
[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]
Izvod je jednak nuli za [tex]x=25\in\left[0 ; 40\right][/tex], a pošto je [tex]P''(x)=-20\lt 0[/tex] (parabola je okrenuta nadole), ta kritična tačka je globalni maksimum:
[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]
Najveći profit je [tex]250[/tex] evra (pri ceni od [tex]25[/tex] evra po komadu).