ELEMENTY  PROGRAMOWANIA  LINIOWEGO.

     1.   PODSTAWOWE POJĘCIA I TWIERDZENIA

        Programowanie liniowe zajmuje się budową i rozwiązywaniem liniowych modeli decyzyjnych z określonym kryterium optymalności  .

       Ogólny zapis takiego modelu można przedstawić następująco:  wyznaczyć wartość największą albo najmniejszą  funkcji :

(1)                             

przy warunkach:

(2)                      

(3)                                .

Funkcję liniową      nazywamy   funkcją celu  bądź  funkcją kryterium.

      Zmienne     nazywamy zmiennymi decyzyjnymi  a wielkości  ,  j = 1, …,n,

  i = 1,…,m ,   j = 1,…,n ,   oraz   ,      nazywamy  parametrami  modelu.

Warunki  (2)  nazywamy warunkami ograniczającymi , zaś warunki (3)  -  warunkami brzegowymi .

        Występowanie warunków brzegowych na ogół jest związane z określonym charakterem zagadnień, np.  wielkość produkcji pewnego wyroby nie może być ujemna .

DEFINICJA 1.   Zbiór wszystkich układów liczb rzeczywistych     spełniający warunki  (2)  i  (3)   nazywamy  zbiorem rozwiązań dopuszczalnych  i oznaczamy go symbolem   X .

DEFINICJA 2.   Rozwiązaniem optymalnym  nazywamy te układy  ,

tzn. te rozwiązania dopuszczalne, dla których funkcja celu osiąga swoją wartość największą   ( najmniejszą )  .

     Ogólny schemat postępowania przy rozwiązywaniu zadań programowania liniowego jest następujący:

a)      budowa modelu matematycznego postawionego zadania,

b)     rozwiązanie modelu,

c)      weryfikacja i interpretacja otrzymanych wyników.

Opracowane metody rozwiązywania zadań programowania liniowego opierają się na następujących twierdzeniach:

TWIERDZENIE 1. 

Zbiór rozwiązań dopuszczalnych zadania programowania liniowego jest zbiorem domkniętym, wypukłym, o skończonej liczbie wierzchołków (niekoniecznie ograniczonym).

TWIERDZENIE 2.  

Funkcja liniowa określona na zbiorze domkniętym ograniczonym, wypukłym, o skończonej liczbie wierzchołków osiąga swoją wartość największą  ( najmniejszą )  na brzegu tego zbioru .

TWIERDZENIE 3.   ( Weierstrassa ) .

Funkcja liniowa określona na domkniętym zbiorze wypukłym, o skończonej liczbie wierzchołków osiąga swoją wartość największą  ( najmniejszą )  w wierzchołkach tego zbioru .

TWIERDZENIE  4. 

Jeżeli funkcja liniowa określona na zbiorze wypukłym , domkniętym o skończonej liczbie wierzchołków osiąga swoją wartość największą  ( najmniejszą ) w dwóch punktach wierzchołkowych, to tę wartość osiąga również  na odcinku łączącym te punkty.

Podstawowymi sposobami rozwiązywania zadań programowania liniowego są :

a)      sposób graficzny,

b)     algorytm simpleks,

c)      algorytm transportowy.

     Istnieją pewne ogólne zasady budowy modeli zadań programowania matematycznego.

Należą do nich :

a)      określenie wielkości, które będą  zmiennymi decyzyjnymi  modelu ,

b)     sformułowanie kryterium działalności oraz znalezienia jego matematycznej postaci ,

c)      uwzględniając treść i charakter zadania sformułowanie i zapisanie w postaci nierówności bądź równań warunków ograniczających naszą działalność .

2.      METODA  GRAFICZNA  ROZWIĄZYWANIA ZADAŃ PROGRAMOWANIA

            LINIOWEGO

    Jest to sposób otrzymania rozwiązania zadania programowania liniowego w przypadku, gdy w modelu występują tylko dwie zmienne decyzyjne, bądź dany model można sprowadzić do zadania o dwóch zmiennych decyzyjnych.

Idea metody graficznej jest następująca :

a)      wyznaczamy zbiór rozwiązań dopuszczalnych rozwiązując graficznie układ nierówności bądź równań ,

b)     znajdujemy  rozwiązanie optymalne, które zgodnie z twierdzeniem  3  i  4   , znajdować się będzie w którymś  z wierzchołków , bądź na brzegu zbioru rozwiązań dopuszczalnych.

PRZYKŁAD  1.

Pewien zakład produkuje dwa wyroby  A  i   B  .  Do produkcji tych wyrobów potrzebne są surowce    .  Nakłady surowców potrzebne do wyprodukowania jednostki każdego   z wyrobów  , zasoby surowców i zyski jednostkowe z sprzedaży tych wyrobów  podane są  w poniższej tabeli:

Należy ustalić plan produkcji zapewniający maksymalny zysk .

ROZWIĄZANIE

Zmiennymi decyzyjnymi w tym przypadku będą:

  -   planowana liczba jednostek wyrobu  A,

  -  planowana liczba jednostek wyrobu   B  ,        .

Funkcja celu :   zysk     .

Warunki ograniczające :

Warunki brzegowe :           .

Zbiorem rozwiązań dopuszczalnych tego modelu jest zbiór punktów  płaszczyzny spełniających warunki    oraz warunki brzegowe . Zauważmy , że na płaszczyźnie każdy

z tych warunków określa odpowiednią  półpłaszczyznę . Wobec tego znalezienie zbioru rozwiązań dopuszczalnych sprowadza się do graficznego rozwiązania układu

nierówności   ( * )  . Punkty będące wierzchołkami tego zbioru (wielokąta) wyznaczamy rozwiązując układy równań:

;        

oraz znajdując punkt przecięcia prostej z osią 0Y  i prostej     z osią 0X.                                                                       

                                  y                                                     Wierzchołki tego wielokąta to punkty: 

                   D(0,10)            C(2,9)                                          

                                                                B(4,6)

                                            X

                                                                         A(6,0)

                     O(0,0)                                                                              x                     

                                                     Rysunek  1.

Zapiszemy w tabeli  wartości  funkcji  celu dla poszczególnych punktów wierzchołkowych:

Jak widać, funkcja celu osiąga wartość największą równą  31  w punkcie  C ( 2,9 ) .

Zatem optymalny program produkcyjny jest następujący:

należy wyprodukować    2  jednostki wyrobu A  oraz  9  jednostek wyroby  B .

PRZYKŁAD 2.

Gospodarstwo rolne prowadzi hodowlę drobiu, stosując dwa produkty paszowe A i B . Dla właściwej hodowli zwierzęta powinny otrzymywać (na dobę) odpowiednie ilości potrzebnych składników odżywczych (witaminy,proteiny, itp.), które są podane w poniższej tabelce.

...