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

Rešenje:
Za svako [tex]a[/tex] koordinatni početak zadovoljava sva ograničenja, pa dopustivi skup [tex]D[/tex] nikada nije prazan; pitanje je samo da li je [tex]z[/tex] ograničena odozgo na [tex]D[/tex].
Slučaj [tex]a\gt 0[/tex]. Iz [tex]x_1+ax_2\le 3[/tex] i [tex]x_1, x_2\ge 0[/tex] dobijamo
[tex]0\le x_1\le 3,\qquad 0\le x_2\le\frac{3}{a}[/tex]
pa je [tex]D[/tex] ograničen zatvoren mnogougao i linearna funkcija na njemu dostiže maksimum (u temenu). Zapravo, za [tex]x_1\le 3[/tex] prva dva ograničenja su automatski ispunjena ([tex]x_1-2x_2\le 3\lt 4[/tex], [tex]x_1-x_2\le 3\lt 6[/tex]), tako da je [tex]D[/tex] trougao s temenima [tex]\left(0 ; 0\right)[/tex], [tex]\left(3 ; 0\right)[/tex], [tex]\left(0 ; \frac{3}{a}\right)[/tex] i
[tex]z_{\max}=\max\left\{6 ; \frac{3}{a}\right\}[/tex]
Slučaj [tex]a\le 0[/tex]. Svaka tačka [tex]\left(0 ; t\right)[/tex] sa [tex]t\ge 0[/tex] je dopustiva, jer je
[tex]-2t\le 4,\qquad -t\le 6,\qquad at\le 0\le 3[/tex]
Geometrijski, cela pozitivna poluosa [tex]Ox_2[/tex] leži u [tex]D[/tex], a duž nje je [tex]z\left(0 ; t\right)=t\to+\infty[/tex], pa [tex]z[/tex] nema maksimum. (To važi i za [tex]a=0[/tex], kada je treće ograničenje samo [tex]x_1\le 3[/tex].)
Zadatak ima rešenje tačno za [tex]a\in\left(0 ; +\infty\right)[/tex].

Rešenje:
Svaka od promenljivih [tex]x_1, x_4, x_6[/tex] javlja se sa koeficijentom [tex]1[/tex] u tačno jednoj jednačini, pa je početno bazno dopustivo rešenje [tex]x_1=7[/tex], [tex]x_4=12[/tex], [tex]x_6=10[/tex], ostale promenljive su [tex]0[/tex], uz [tex]F=14{,}76[/tex]. Bazne promenljive imaju nultu cenu, pa su relativne ocene slobodnih promenljivih njihovi koeficijenti u [tex]F[/tex]:
[tex]\Delta_2=1,\qquad \Delta_3=-3,\qquad \Delta_5=-2[/tex]
Kod minimizacije negativna ocena znači da [tex]F[/tex] još može da se smanji. Iteracija [tex]1[/tex]: u bazu ulazi [tex]x_3[/tex] (najnegativnija ocena). Količnici za pozitivne elemente njene kolone su [tex]\frac{12}{4}=3[/tex] (red [tex]2[/tex]) i [tex]\frac{10}{3}[/tex] (red [tex]3[/tex]); minimum je u redu [tex]2[/tex], pa iz baze izlazi [tex]x_4[/tex]. Posle transformacije:
[tex]x_3=3+\frac{1}{2}x_2-\frac{1}{4}x_4,\quad x_1=10-\frac{5}{2}x_2-\frac{1}{4}x_4-2x_5,\quad x_6=1+\frac{5}{2}x_2+\frac{3}{4}x_4-8x_5[/tex]
[tex]F=5{,}76-\frac{1}{2}x_2+\frac{3}{4}x_4-2x_5[/tex]
Iteracija [tex]2[/tex]: ulazi [tex]x_5[/tex] (ocena [tex]-2[/tex]); količnici su [tex]\frac{10}{2}=5[/tex] i [tex]\frac{1}{8}[/tex], pa izlazi [tex]x_6[/tex]:
[tex]x_5=\frac{1}{8}+\frac{5}{16}x_2+\frac{3}{32}x_4-\frac{1}{8}x_6,\quad x_1=\frac{39}{4}-\frac{25}{8}x_2-\frac{7}{16}x_4+\frac{1}{4}x_6[/tex]
[tex]F=5{,}51-\frac{9}{8}x_2+\frac{9}{16}x_4+\frac{1}{4}x_6[/tex]
Iteracija [tex]3[/tex]: ulazi [tex]x_2[/tex] (ocena [tex]-\frac{9}{8}[/tex]). U izrazima za [tex]x_3[/tex] i [tex]x_5[/tex] koeficijent uz [tex]x_2[/tex] je pozitivan, pa povećanje [tex]x_2[/tex] ne čini te promenljive negativnim; [tex]x_2[/tex] ograničava samo red promenljive [tex]x_1[/tex], pa izlazi [tex]x_1[/tex]:
[tex]x_2=\frac{78}{25}-\frac{8}{25}x_1-\frac{7}{50}x_4+\frac{2}{25}x_6,\qquad F=2+\frac{9}{25}x_1+\frac{18}{25}x_4+\frac{4}{25}x_6[/tex]
Sada su sve ocene nenegativne, pa je rešenje optimalno: [tex]x_1=x_4=x_6=0[/tex] i
[tex]x_2=\frac{78}{25}=3{,}12,\quad x_3=3+\frac{1}{2}\cdot 3{,}12=4{,}56,\quad x_5=\frac{1}{8}+\frac{5}{16}\cdot 3{,}12=1{,}1[/tex]
Provera: [tex]3{,}12-3\cdot 4{,}56-2\cdot 1{,}1+14{,}76=2[/tex], a leve strane tri ograničenja jednake su [tex]7[/tex], [tex]12[/tex], [tex]10[/tex]. Minimalni troškovi su [tex]F_{\min}=2[/tex].

Rešenje:
Svaka od promenljivih [tex]x_1, x_2, x_3, x_5[/tex] javlja se samo u jednoj jednačini, pa ih izražavamo preko [tex]x_4[/tex] i [tex]x_6[/tex]:
[tex]x_1=13-3x_6,\quad x_2=18+x_4-2x_6,\quad x_3=3+2x_4-x_6,\quad x_5=12+3x_4-x_6[/tex]
Zamenom u [tex]z[/tex] dobijamo:
[tex]z=5\left(13-3x_6\right)+\left(18+x_4-2x_6\right)+2\left(3+2x_4-x_6\right)+4x_4+3\left(12+3x_4-x_6\right)+20x_6=125+18x_4-2x_6[/tex]
Za [tex]x_4=x_6=0[/tex] dobijamo dopustivu tačku sa [tex]z=125[/tex], ali [tex]z[/tex] se i dalje smanjuje kada [tex]x_6[/tex] raste. Rast promenljive [tex]x_6[/tex] ograničen je uslovom [tex]x_3=3+2x_4-x_6\ge 0[/tex], tj. [tex]x_6\le 3+2x_4[/tex]. Zato na dopustivom skupu, koristeći [tex]x_4\ge 0[/tex], važi
[tex]z=125+18x_4-2x_6\ge 125+18x_4-2\left(3+2x_4\right)=119+14x_4\ge 119[/tex]
Jednakost važi samo za [tex]x_4=0[/tex] i [tex]x_6=3[/tex]; tada su [tex]x_1=4[/tex], [tex]x_2=12[/tex], [tex]x_3=0[/tex], [tex]x_5=9[/tex] nenegativni, pa je tačka [tex]\left(4 ; 12 ; 0 ; 0 ; 9 ; 3\right)[/tex] dopustiva i
[tex]z=20+12+0+0+27+60=119[/tex]
Najmanja vrednost je [tex]119[/tex].

Rešenje:
Ponuda iznosi [tex]20+10+15=45[/tex] tona, a potražnja [tex]15+20+15+10=60[/tex] tona, pa je problem neuravnotežen (otvoren). Dodajemo fiktivno skladište [tex]A_4[/tex] sa [tex]15[/tex] tona i nultim troškovima; ono što ono „isporučuje“ jeste nezadovoljena potražnja. Neka je [tex]x_{ij}[/tex] količina (u tonama) prevezena iz [tex]A_i[/tex] u [tex]B_j[/tex].
Metod minimalnog elementa (prvo polja skladišta [tex]A_4[/tex] sa nultim troškovima, zatim najjeftinija stvarna polja) daje početni plan i njegove troškove:
[tex]x_{41}=15,\ x_{12}=20,\ x_{24}=10,\ x_{33}=15,\qquad z=20\cdot 1+10\cdot 2+15\cdot 5=115[/tex]
Duž ciklusa [tex](A_2B_3)^{+},\ (A_2B_4)^{-},\ (A_3B_4)^{+},\ (A_3B_3)^{-}[/tex] troškovi se menjaju za [tex]3-2+3-5=-1[/tex] po toni, a duž njega može se premestiti [tex]\theta=\min(10; 15)=10[/tex] tona. Novi plan ([tex]B_1[/tex] ostaje bez isporuke) i njegovi troškovi:
[tex]x_{12}=20,\ x_{23}=10,\ x_{33}=5,\ x_{34}=10,\qquad z=20\cdot 1+10\cdot 3+5\cdot 5+10\cdot 3=105[/tex]
Proveravamo optimalnost metodom potencijala: uzmimo [tex]u_1=2,\ u_2=3,\ u_3=5,\ u_4=0[/tex] i [tex]v_1=0,\ v_2=-1,\ v_3=0,\ v_4=-2[/tex]. Tada je [tex]u_i+v_j=c_{ij}[/tex] u svakom zauzetom polju, a sve ocene [tex]c_{ij}-u_i-v_j[/tex] (po redovima, poslednji red je za [tex]A_4[/tex]) nenegativne su:
[tex]\begin{bmatrix}0&0&2&6\\1&4&0&1\\1&0&0&0\\0&1&0&2\end{bmatrix}[/tex]
Prema tome, za svaki dopustiv plan (sva ponuda je prevezena, [tex]B_j[/tex] dobija [tex]r_j[/tex] tona, ne više nego što mu je potrebno), pošto je [tex]c_{ij}\ge u_i+v_j[/tex] za [tex]i=1,2,3[/tex], važi
[tex]\sum_{i,j} c_{ij}x_{ij}\ge\sum_{i,j}(u_i+v_j)x_{ij}=2\cdot 20+3\cdot 10+5\cdot 15-r_2-2r_4\ge 145-20-2\cdot 10=105[/tex]
jer je [tex]r_2\le 20[/tex] i [tex]r_4\le 10[/tex]. Dakle, nijedan plan nije jeftiniji, pa minimalni ukupni troškovi iznose [tex]105[/tex] evra.

Rešenje:
Ovo je problem raspoređivanja (asignacije); primenjujemo mađarski metod. Oduzimanje konstante od celog reda ili cele kolone menja ukupno vreme svakog rasporeda za istu konstantu, jer svaki raspored koristi tačno po jedan element iz svakog reda i svake kolone.
Oduzimamo minimume po redovima [tex]64, 52, 56, 60[/tex] (zbir [tex]232[/tex]), a zatim minimume po kolonama [tex]2, 0, 6, 0[/tex] nove matrice (zbir [tex]8[/tex]):
[tex]\begin{bmatrix}6&16&11&0\\3&0&6&2\\2&0&8&12\\2&0&7&10\end{bmatrix}\ \to\ \begin{bmatrix}4&16&5&0\\1&0&0&2\\0&0&2&12\\0&0&1&10\end{bmatrix}[/tex]
Svi elementi su nenegativni, pa svaki raspored zahteva najmanje [tex]232+8=240[/tex] minuta. Postoje četiri nezavisne nule: radnik [tex]1[/tex] na mašini [tex]D[/tex], radnik [tex]2[/tex] na [tex]C[/tex], radnik [tex]3[/tex] na [tex]A[/tex], radnik [tex]4[/tex] na [tex]B[/tex]. Ovaj raspored dostiže donju granicu:
[tex]64+58+58+60=240[/tex]
(Drugi optimalni raspored je [tex]1\to D,\ 2\to C,\ 3\to B,\ 4\to A[/tex], sa [tex]64+58+56+62=240[/tex].) Minimalno ukupno vreme iznosi [tex]240[/tex] minuta.