Vypracovane-zkouskove-otazky - teorie

Základní typy omezujících podmínek:

• kapacitní „ ≤ “ → vymezují maximální množství vyčerpání zdrojů

• požadavkové „ ≥ “→ vymezují potřebu zajistit alespoň dané množství zdroje.

• určení „ = “→vyjadřují nutnost dosažení stanoveného výstupu

• Účelová (kriteriální) funkce

Vyjádřena jako skalární součin jednotkových cen proměnných a jejich hodnot. Představuje cíl řešení problému, jelikož oceňuje kvalitu jednotlivých kombinací procesu. Kvalita každého procesu je tedy ohodnocena cenovým koeficientem.

Základní typy účelových funkcí:

• minimalizační; Z (MIN)

• maximalizační. Z (MAX)

• Podmínky nezápornosti - Požadujeme pro všechny proměnné. Zajišťují praktickou aplikovatelnost řešení.

5) Uveďte a stručně charakterizujte dva základní způsoby grafického řešení modelů lineárního programování. Za jakých podmínek je možné je použít?

Prostor řešení:

• Proměnné – osy souřadnic y

• Omezující podmínky

  • kapacitní, požadavkové – poloroviny (zvolením libovolného bodu, který neleží na hraniční přímce, zjištění zda jeho souřadnice vyhovují dané omezující podmínce

  • určení – přímky (spojnice dvou bodů, kterými přímka prochází)

• Podmínky nezápornosti – 1. kvadrant

• Účelová funkce – mapa spojnic kombinací proměnných (x1,x2) s vhodnou konstantou za Z, kterou si zvolíme ve stejných jednotkách účelové funkce, poté nalezneme takovou její rovnoběžku, aby byla co nejdále od počátku souřadnic (maximalizace) nebo nejblíže (minimalizace), ale bude mít s množinou přípustných řešení společný alespoň jeden bod.

• Můžeme použít, pokud máme nejvýše dvě rozhodovací proměnné

• libovolný počet omezujících podmínek

• nakonec dosadíme do rovnic, abychom zjistili hodnoty proměnných a hodnotu účelové funkce

Prostor požadavků:

• Podmínka použití: model musí být v rovnicovém tvaru

• Realizujeme pomocí tzv.doplňkových proměnných takto:

• kapacitní podmínky (<=)- přičteme hodnotu doplňkové proměnné k levé straně OP (+d)

• požadavkové podmínky(>=)- od levé strany OP hodnotu doplňkové proměnné odečteme(-d)

• podmínky určení (=)- rovnice, žádná transformace není potřeba

• doplňkové proměnné

• přebírají jednotku omezující podmínky

• jejich hodnota se interpretuje jako „rezerva“, která zbývá do úplného vyčerpání omezující podmínky typu <=, nebo jako „překročení požadavku“ v omezující podmínce typu >=

• neovlivňují ÚF, vždy jim přiřazujeme nulovou sazbu;

• rovněž musí být nezáporné

• libovolný počet rozhodovacích proměnných

• nejvýše dvě omezující podmínky

• Bázi přípustného řešení zde tvoří dvojice proměnných, pomocí jejichž nezáporné lineární kombinace dokážeme vyjádřit vektor požadavků (pokud spojnice koncových vektorů ai a aj protne vektor požadavků v prvním kvadrantu, proměnné xi a xj tvoří přípustnou bázi úlohy.

• Před zakreslením je důležité zjistit ocenění jednotlivých proměnných v účelové funkci, tedy všechny koeficienty vydělíme jejich cenou. Avšak doplňkové proměnné nemůžeme dělit nulovou sazbou, ale dělíme je limitně (nějakou velmi malou hodnotou blížící se nule).

• V grafu vedeme rovnoběžky od rozhodovacích proměnných do +nekonečna a –nekonečna, řešením je taková rovnoběžka doplňkových proměnných, která protne vektor požadavků nejdále od počátku (minimalizace) a nejblíže od počátku (maximalizace)