Linearno programiranje i optimizacija - veoma teški zadaci sa rešenjima

Rešenje:
Komadi isečeni preko porudžbine su samo otpad, pa računamo samo poručene komade. Njihova ukupna dužina (u centimetrima) iznosi
[tex]320\cdot 560+260\cdot 480+120\cdot 780=179200+124800+93600=397600[/tex]
Donja granica. Pošto je [tex]2\cdot 320=640\gt 600[/tex], svih [tex]560[/tex] komada od [tex]320[/tex] cm nalazi se u [tex]560[/tex] različitih profila. U takvom profilu preostaje [tex]280[/tex] cm, u koje staje ili jedan komad od [tex]260[/tex] cm i ništa više (jer je [tex]260+120\gt 280[/tex]), ili najviše dva komada od [tex]120[/tex] cm (jer je [tex]3\cdot 120=360\gt 280[/tex]). Dakle, profil sa komadom od [tex]320[/tex] cm sadrži najviše [tex]580[/tex] cm poručenih komada ako sadrži i komad od [tex]260[/tex] cm, a najviše [tex]560[/tex] cm u suprotnom.
Neka je [tex]k[/tex] broj profila koji sadrže i komad od [tex]320[/tex] cm i komad od [tex]260[/tex] cm; tada je [tex]k\le 480[/tex]. Ako se upotrebi [tex]N[/tex] profila, ukupna dužina poručenih komada je najviše
[tex]580k+560(560-k)+600(N-560)=600N-40\cdot 560+20k\le 600N-22400+9600=600N-12800[/tex]
Ona mora biti najmanje [tex]397600[/tex], pa je
[tex]600N\ge 410400\Rightarrow N\ge 684[/tex]
Konstrukcija: [tex]480[/tex] profila sečemo kao [tex]320+260[/tex] (otpad po [tex]20[/tex] cm), [tex]80[/tex] profila kao [tex]320+120+120[/tex] (otpad po [tex]40[/tex] cm) i [tex]124[/tex] profila kao [tex]5\cdot 120[/tex] (bez otpada). Dobijamo [tex]480+80=560[/tex] komada od [tex]320[/tex] cm, [tex]480[/tex] komada od [tex]260[/tex] cm i [tex]2\cdot 80+5\cdot 124=780[/tex] komada od [tex]120[/tex] cm, uz upotrebu [tex]480+80+124=684[/tex] profila; ukupni otpad [tex]684\cdot 600-397600=12800[/tex] cm najmanji je mogući. Najmanji broj standardnih profila je [tex]684[/tex].

Rešenje:
Iz jednačine je [tex]x_3=10-2x_1+x_2[/tex], što je ceo broj kad su [tex]x_1, x_2[/tex] celi. Zamenom u [tex]z[/tex] dobijamo:
[tex]z=3x_1-5x_2+30-6x_1+3x_2=30-3x_1-2x_2[/tex]
Dva ograničenja u obliku nejednakosti i uslov [tex]x_3\ge 0[/tex] postaju:
[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]
Dakle, treba maksimizovati [tex]w=3x_1+2x_2[/tex] (tada je [tex]z=30-w[/tex]) na celobrojnim tačkama sa [tex]x_1, x_2\ge 0[/tex] koje zadovoljavaju ova tri ograničenja. Bez uslova celobrojnosti optimum se dostiže u preseku pravih [tex]x_1+x_2=7[/tex] i [tex]2x_1-x_2=10[/tex], tj. u tački [tex]\left(\frac{17}{3}; \frac{4}{3}\right)[/tex] sa [tex]w=\frac{59}{3}[/tex], koja nije celobrojna. Zaista, za svaku dopustivu tačku
[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]
Pošto je [tex]w[/tex] ceo broj u celobrojnim tačkama, [tex]w\le 19[/tex]. Tačka [tex]x_1=5,\ x_2=2[/tex] daje [tex]w=19[/tex] i zadovoljava [tex]5+2=7\le 7[/tex], [tex]5-4=1\ge -4[/tex], [tex]10-2=8\le 10[/tex]; tada je [tex]x_3=10-10+2=2[/tex]. Provera u polaznom problemu:
[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]
Minimum je [tex]z_{\min}=30-19=11[/tex] i dostiže se u tački [tex](5; 2; 2)[/tex].

Rešenje:
Za [tex]x[/tex] vožnji firma ostvaruje dobit
[tex]\pi(x)=100x-25x-0{,}01x^2=75x-0{,}01x^2[/tex]
Uz [tex]x_A[/tex] vožnji firme [tex]A[/tex] i [tex]x_B[/tex] vožnji firme [tex]B[/tex] maksimizujemo [tex]\Pi=\pi(x_A)+\pi(x_B)[/tex] uz ograničenja [tex]x_A+2x_B\le 3000[/tex], [tex]x_A, x_B\ge 0[/tex]. Pošto je [tex]\pi'(x)=75-0{,}02x\gt 0[/tex] za [tex]x\lt 3750[/tex], a uvek je [tex]x_A\le 3000[/tex], preostali poeni mogli bi se iskoristiti za dodatne vožnje firme [tex]A[/tex] uz veću dobit. Dakle, u optimumu se koriste svi poeni: [tex]x_A=3000-2x_B[/tex], [tex]0\le x_B\le 1500[/tex], i za [tex]f(x_B)=\pi(3000-2x_B)+\pi(x_B)[/tex] važi
[tex]f'(x_B)=-2\left(75-0{,}02(3000-2x_B)\right)+75-0{,}02x_B=45-0{,}1x_B[/tex]
Izvod se anulira za [tex]x_B=450[/tex], a [tex]f''=-0{,}1\lt 0[/tex], pa je to maksimum na intervalu; tada je [tex]x_A=3000-900=2100[/tex]. (Ekvivalentno: Lagranževi uslovi [tex]75-0{,}02x_A=\lambda[/tex], [tex]75-0{,}02x_B=2\lambda[/tex] daju [tex]\lambda=33[/tex] evra — graničnu vrednost jednog eko-poena.) Dobiti iznose
[tex]\pi(2100)=157500-44100=113400,\qquad \pi(450)=33750-2025=31725[/tex]
[tex]\Pi_{\max}=113400+31725=145125[/tex]
Poređenja radi, bez saradnje ([tex]x_A=1500[/tex], [tex]x_B=750[/tex]) ukupna dobit je [tex]90000+50625=140625[/tex], a samo sa novim kamionima ([tex]x_A=3000[/tex]) iznosi [tex]135000[/tex]. Maksimalna ukupna dobit iznosi [tex]145125[/tex] evra.

Rešenje:
Temena poliedra [tex]S[/tex] su dopustive tačke u kojima se seku tri od šest graničnih ravni sa linearno nezavisnim vektorima normala. Rešavanjem svih takvih sistema i zadržavanjem dopustivih rešenja dobijamo [tex]7[/tex] temena:
[tex]O(0; 0; 0),\ \ (11; 0; 0),\ \ (0; 9; 0),\ \ (0; 0; 8),\ \ (4; 7; 0),\ \ (9; 0; 2),\ \ (0; 3; 8)[/tex]
Na primer, [tex]x+y+z=11[/tex], [tex]2x+3z=24[/tex] i [tex]y=0[/tex] daju [tex](9; 0; 2)[/tex], dok se tačka [tex](12; 0; 0)[/tex], dobijena iz [tex]2x+3z=24[/tex], [tex]y=z=0[/tex], odbacuje, jer je [tex]12\gt 11[/tex]. Teme [tex](0; 3; 8)[/tex] je degenerisano: kroz njega prolaze četiri ravni, i to [tex]x=0[/tex], [tex]x+y+z=11[/tex], [tex]2x+4y+3z=36[/tex] i [tex]2x+3z=24[/tex]. Svaka od šest ravni sadrži stranu sa sledećim temenima:
[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]
Dakle, četiri strane su četvorouglovi, a dve su trouglovi. Svaka ivica pripada tačno dvema stranama, pa je
[tex]E=\frac{4\cdot 4+2\cdot 3}{2}=11[/tex]
Provera Ojlerovom formulom: [tex]V-E+F=7-11+6=2[/tex]. Takođe, po stepenima: teme [tex](0; 3; 8)[/tex] spojeno je ivicama sa [tex]4[/tex] temena ([tex](0; 9; 0)[/tex], [tex](0; 0; 8)[/tex], [tex](9; 0; 2)[/tex], [tex](4; 7; 0)[/tex]), a svako od ostalih [tex]6[/tex] temena sa [tex]3[/tex], pa je [tex]E=\frac{4+6\cdot 3}{2}=11[/tex] (pretpostavka da su sva temena stepena [tex]3[/tex] dala bi nemoguće [tex]\frac{21}{2}[/tex]). Poliedar ima [tex]11[/tex] ivica.