Problém řezání plechu
Úloha číslo: 3261
Dílna má dodat 400 kusů součástky A, 600 ks součástky B a 2625 ks součástky C. Z jednoho kusu plechu lze vykrájet podle pěti schémat různá množství součástek, jak je udáno v následující tabulce: Jakým způsobem je možné vykrájet požadované množství součástek při minimální spotřebě materiálu?
\(\begin{array}{|l|ccccc|} \hline Sou. & Sch. 1 & Sch. 2 & Sch. 3 & Sch. 4 & Sch. 5\\ \hline A & 8 & 4 & – & – & – \\ B & 4 & 10 & 16 & 10 & – \\ C & 1 & 2 & 3 & 20 & 100 \\ \hline \end{array} \)
Varianta 1
Zformulujte primární i duální úlohu.
Řešení
Primární a duální problémy znějí:
\[\begin{eqnarray*} \min (x_1+x_2+x_3+x_4+x_5) \\ 8x_1 + 4 x_2 & = & 400 \\ 4x_1 + 10 x_2 + 16 x_3 + 10 x_4& = & 600 \\ x_1 + 2 x_2 + 3 x_3 + 20 x_4 + 100 x_5 & = & 2625 \\ x_1,x_2,x_3,x_4,x_5 & \ge & 0 \end{eqnarray*}\] \[\begin{eqnarray*} \max (600u_1+400u_2+2625u_3) \\ 8u_1 + 4u_2 + u_3 & \le & 1 \\ 4u_1 + 10u_2 + 2u_3 & \le & 1 \\ 16u_2 + 3u_3 & \le & 1 \\ 10u_2 + 20u_3 & \le & 1 \\ 100u_3 & \le & 1 \\ \end{eqnarray*}\]
Rovnostem odpovídá neomezená proměnná a podmínce nezápornosti proměnných odpovídá \(\ge\) nerovnost.
Varianta 2
Vyřešte primární úlohu simplexovou metodou.
Řešení
Řešení primární úlohu simplexovým algoritmem. Nejprve si tabulku upravíme tak, abychom si mohli vyjádřit bázické řešení: \[ \begin{array}{r|rrrrr|r} & 8 & 4 & 0 & 0 & 0 & 400 \\ & 4 & 10 & 16 & 10 & 0 & 600 \\ & 1 & 2 & 3 & 20 & 100 & 2625 \\ \hline & 2 & 1 & 0 & 0 & 0 & 100 \\ & 2 & 5 & 8 & 5 & 0 & 300 \\ & 1 & 2 & 3 & 20 & 100 & 2625 \\ \hline & 0 & -3 & -6 & -40 & -200 & -5150 \\ & 0 & 1 & 2 & -35 & -200 & -4950 \\ 1 & 1 & 2 & 3 & 20 & 100 & 2625 \\ \hline & 0 & 0 & 0 & -145 & -800 & -20000 \\ 2 & 0 & 1 & 2 & -35 & -200 & -4950 \\ 1 & 1 & 0 & -1 & 90 & 500 & 12525 \\ \hline 5 & 0 & 0 & 0 & 29/160 & 1 & 25 \\ 2 & 0 & 1 & 2 & 5/4 & 0 & 50 \\ 1 & 1 & 0 & -1 & -5/8 & 0 & 25 \\ \end{array} \]
Máme štěstí, bázické řešení je \((x_1,…,x_5)=(25{,}50,0{,}0,25)\). (Jinak bychom museli řešit pomocnou úlohu.) Pokračujeme s původní účelovou funkcí. Pozor řešíme minimalizační úlohu, takže sloupec pro pivot bude vybírán s opačným znaménkem!!!
\[ \begin{array}{r|rrrrr|r} 5 & 0 & 0 & 0 & 29/160 & 1 & 25 \\ 2 & 0 & 1 & 2 & 5/4 & 0 & 50 \\ 1 & 1 & 0 & -1 & -5/8 & 0 & 25 \\ \hline & 1 & 1 & 1 & 1 & 1 & 0 \\ \end{array} \]
\[ \begin{array}{r|rrrrr|r} 5 & 0 & 0 & 0 & 29/160 & 1 & 25 \\ 2 & 0 & 1 & 2 & 5/4 & 0 & 50 \\ 1 & 1 & 0 & -1 & -5/8 & 0 & 25 \\ \hline & 0 & 0 & 0 & 31/160 & 0 & -100 \\ \end{array} \]
Poslední řádek neobsahuje žádný záporný prvek, dosáhli jsme tedy optima. Bázickým optimálním řešením podle naší tabulky je \((x_1,…,x_5)=(25{,}50,0{,}0,25)\), lze ovšem zvolit i libovolné jiné z konvexního obalu bodů \((25{,}50,0{,}0,25)\) a \((50{,}0,25{,}0,25)\).
Varianta 3
Vyřešte duální úlohu simplexovou metodou.
Řešení
Řešení duální úlohy (všimněte si, že přípustné bázické řešení máme zadarmo):
\[ \begin{array}{r|rrrrrrrr|r} 4^* & 8 & 4 & 1 & 1 & 0 & 0 & 0 & 0 & 1 \\ 5 & 4 & 10 & 2 & 0 & 1 & 0 & 0 & 0 & 1 \\ 6 & 0 & 16 & 3 & 0 & 0 & 1 & 0 & 0 & 1 \\ 7 & 0 & 10 & 20 & 0 & 0 & 0 & 1 & 0 & 1 \\ 8 & 0 & 0 & 100 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline & 400^* & 600 & 2625 & 0 & 0 & 0 & 0 & 0 & 0 \\ \end{array} \]
\[ \begin{array}{r|rrrrrrrr|r} 1 & 1 & 1/2 & 1/8 & 1/8 & 0 & 0 & 0 & 0 & 1/8 \\ 5^* & 0 & 8 & 3/2 & -1/2 & 1 & 0 & 0 & 0 & 1/2 \\ 6 & 0 & 16 & 3 & 0 & 0 & 1 & 0 & 0 & 1 \\ 7 & 0 & 10 & 20 & 0 & 0 & 0 & 1 & 0 & 1 \\ 8 & 0 & 0 & 100 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline & 0 & 400 & 2575 & -50 & 0 & 0 & 0 & 0 & -50 \\ \end{array} \]
\[ \begin{array}{r|rrrrrrrr|r} 1 & 1 & 0 & 1/32 & 5/32 & -1/16 & 0 & 0 & 0 & 3/32 \\ 2 & 0 & 1 & 3/16 & -1/16 & 1/8 & 0 & 0 & 0 & 1/16 \\ 6 & 0 & 0 & 0 & 1 & -2 & 1 & 0 & 0 & 0 \\ 7 & 0 & 0 & 290/16 & 10/16 & -10/8 & 0 & 1 & 0 & 1/4 \\ 8^* & 0 & 0 & 100 & 0 & 0 & 0 & 0 & 1 & 1 \\ \hline & 0 & 0 & 2500 & -25 & -50 & 0 & 0 & 0 & -75 \\ \end{array} \]
\[ \begin{array}{r|rrrrrrrr|r} 1 & 1 & 0 & 0 & 5/32 & -1/16 & 0 & 0 & -1/3200 & 299/3200 \\ 2 & 0 & 1 & 0 & -1/16 & 1/8 & 0 & 0 & -3/1600 & 97/1600 \\ 6 & 0 & 0 & 0 & 1 & -2 & 1 & 0 & 0 & 0 \\ 7 & 0 & 0 & 0 & 10/16 & -10/8 & 0 & 1 & -29/160 & 31/160 \\ 3 & 0 & 0 & 1 & 0 & 0 & 0 & 0 & 1/100 & 1/100 \\ \hline & 0 & 0 & 0 & -25 & -50 & 0 & 0 & -25 & -100 \\ \end{array} \]
Máme řešení duální úlohy: \((u_1,…,u_3)=(\frac{299}{3200},\frac{97}{1600},\frac{1}{100})\) Odpovídající řešení primární úlohy v tomto případě nalezneme jako koeficienty účelové funkce u pomocných proměnných.
Všimněte si také, že nerovnosti nebázických proměnných \(x_3,x_4\) se v řešení neprojeví, t.j. duální řešení lze získat jako řešení soustavy (rovnic!) \[\begin{eqnarray*} 8u_1 + 4u_2 + u_3 & = & 1 \\ 4u_1 + 10u_2 + 2u_3 & = & 1 \\ 100u_3 & = & 1 \\ \end{eqnarray*}\]
