1636661695

7

1. WPROWADZENIE

na podzbiorze zbioru Rⁿ ograniczonym pewnymi nierównościami oraz równaniami liniowymi. Czasami ciało M będziemy zastępować pierścieniem Z i będziemy wtedy mówić o programowaniu całkowitoliczbowym.

Wiele praktycznych problemów występujących w ekonomii oraz badaniach operacyjnych może być sformułowanych w postaci zagadnienia programowania liniowego (m.in. zagadnienie transportowe, problem plecakowy). W trakcie wykładu omawiamy tego typu problemy.

Notatki zawierają także część Dodatek, w której umieszczono fakty pozwalające lepiej zrozumieć treść wykładu.

Przykład 1.1. Załóżmy, że pewna firma produkuje dwa rodzaje zapałek: grillowe (długie) i normalne (krótkie). Zysk z każdego pudła zapałek grillowych wynosi 300 EUR, a z każdego pudła zapałek normalnych wynosi 200 EUR. Firma posiada jedną maszynę robiącą długie lub krótkie zapałki. Maszyna ta może wyprodukować w jednym roku maksymalnie 900 000 pudeł zapałek długich lub krótkich. Do produkcji zapałek firma potrzebuje drewna oraz pudeł. Do otrzymania jednego pudła zapałek grillowych potrzeba 3 m³ drewna, natomiast do otrzymania jednego pudła zapałek normalnych potrzeba 1 m³ drewna. Firma posiada 1 800 000 m³ drewna na rok następny, ponadto nasza firma ma 700 000 pudeł na zapałki grillowe oraz 600 000 pudeł na zapałki normalne.

Naszym celem jest zmaksymalizowanie zysków firmy w roku następnym, przy czym zakładamy, że firma może sprzedać wszystko co wyprodukuje. Zapiszmy powyższy problem za pomocą nierówności. Niech x\ oraz X2 oznaczają odpowiednio ilość pudeł (x 100 000) zapałek długich oraz ilość pudeł (x 100 000) zapałek krótkich wyprodukowanych w roku następnym. Zysk z jednego pudła zapałek długich wynosi 300 EUR (3x100 EUR), zatem zysk z X\ pudeł zapałek długich wynosi 3xi (stu euro jednostek). Podobnie zysk z X2 pudeł zapałek krótkich wynosi 2^2 (stu euro jednostek). Przy formułowaniu naszego zagadnienia musimy wziąć pod uwagę następujące ograniczenia:

•    wydajność maszyny jest ograniczona przez 9 (x 100 000) pudeł na rok, czyli X\ + X2 < 9;

•    ograniczenie związane z ilością drewna, to 3xi + X2 < 18;

•    ograniczenie związane z ilością dostępnych pudeł, to X\ <7,X2< 6;

•    ograniczenie związane z sensownością rozważań, to X\ >0, X2 >0.