Sbírka matematických úloh

Problém betonu

Úloha číslo: 3251

• Varianta 1

  Zformulujte úlohu lineárního programování pro maximalizaci zisku, kde odbytové ceny po odečtení nákladů jsou 300 eularů za kubík směsi B1 a 400 ER za kubík směsi B2. Graficky znázorněte prostor přípustných řešení a určete optimální řešení.

• Řešení

  Podmínky dané surovinami S1, S2 a S3 včetně nezápornosti proměnných jsou: \[\begin{eqnarray*} 0.2 x + 0.4 y & \le & 80 \\ 0.15 x + 0.1 y & \le & 30 \\ 0.3 x + 0.1 y & \le & 50 \\ x,y & \ge & 0 \end{eqnarray*}\] Účelová fukce je \(\max(300x+400y)\). Hledáme řešení které nabývá tohoto maxima vzhledem k uvedeným podmínkám.
  Zakreslíme jednotlivé poloroviny – přímka S1 prochází např. body \((0{,}200)\) a \((200{,}100)\), S2 \((100{,}150)\) a \((200{,}0)\), S3 \((100, 200)\) a \((150{,}50)\). Výsledný mnohoúhelník znázorňující všechna přípustná řešení je vybarven šedě. Z obrázku vidíme, že optimální řešení je v průniku S1 a S2, neboli bod \((100{,}150)\), neboť právě tímto bodem prochází přímka se směrnicí \(-\frac{3}{4}\) (naznačená čárkovaně) tak, že celý mnohoúhelník leží pod ní (t.j. ostatní přípustná řeení mají hodnotu účelové funkce nižší.)

  

• Varianta 2

  Stejnou metodou vyřešte pozměněný příklad, kde cílem neni maximalizace zisku, ale minimalizace nákladů. Přitom jsou známy náklady na výrobu jednoho kubíku směsi B1 (35 ER) a směsi B2 (25 ER).

• Výsledek

  Cílová funkce \(\min(35x+25y)\) má optimální řešení \((0{,}0)\).

• Varianta 3

  K předchozí variantě doplňte ještě požadavek na minimální objem výroby směsi B1 (125 kubíků za den) a směsi B2 (50 kubíků za den).

• Řešení

  Podmínky \(x,y\ge 0 \) nahradíme \(x\ge 125, y\ge 50\) a dostaneme optimální řešení \((125{,}50)\).

  

• Varianta 4

  Nyní minimalizujte náklady jako v třetí varaintě za předpokladu, že denní zisk bude přesně 70.000 ER.

• Řešení

  Spolu s podmínkou \(300x+400y=70.000\) dostaneme jednodimenzionální prostor přípustných řešení – úsečku ležící na přímce Z, jež prochází např. body \((100{,}100)\) a \((0{,}175)\), což dává optimum v průniku přímek Z a \(x=125\) čili \((125, 81.25)\).

  

• Varianta 5

  Cílem je opět maximalizace zisku (jako v první variantě), přitom ale dodržte podmínky na minimální objem výroby (třetí varianta).

• Řešení

  Nyní optimum nalezneme v průniku přímky S2 s \(x=125\) čili \((125{,}112.5)\).

• Varianta 6

  Opět maximalizujte zisk, ale minimální velikost objemu má být 150 kubíků směsi B1 a 75 kubíků směsi B2.

• Řešení

  Poloprostory \(x \ge 150, y \ge 75\) a \( 0.3 x + 0.1 y \le 50\) nemají společný neprázdný průnik, jak vidno z obrázku, čili úloha nemá žádné přípustné řeení.

  

• Varianta 7

  Převeďte poslední variantu na úlohu LP ve tvaru s minimalizací a rovností.

• Řešení

  Musíme změnit maximalizaci na mimimalizaci a převést nerovnosti s uitím pomocných poměnných na rovnosti následovně: \[\begin{eqnarray*} \min (-300x-400y) \\ 0.2 x + 0.4 y + z_1 & = & 80 \\ 0.15 x + 0.1 y + z_2 & = & 30 \\ 0.3 x + 0.1 y + z_3 & = & 50 \\ x - z_4 & = & 150 \\ y - z_5 & = & 75 \\ x,y,z_1,z_2,z_3,z_4,z_5 & \ge & 0 \end{eqnarray*}\] Takové zadání LP však u nelze snadno řešit grafickou metodou.