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:
budowa modelu matematycznego postawionego zadania,
rozwiązanie modelu,
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ą :
sposób graficzny,
algorytm simpleks,
algorytm transportowy.
Istnieją pewne ogólne zasady budowy modeli zadań programowania matematycznego.
Należą do nich :
określenie wielkości, które będą zmiennymi decyzyjnymi modelu ,
sformułowanie kryterium działalności oraz znalezienia jego matematycznej postaci ,
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ść .
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 :
wyznaczamy zbiór rozwiązań dopuszczalnych rozwiązując graficznie układ nierówności bądź równań ,
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:
surowce |
A |
B |
surowców |
|
3 |
1 |
18 |
|
2 |
4 |
40 |
|
3 |
2 |
24 |
zyski jednostkowe |
2 |
3 |
|
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:
Punkt |
Współrzędne |
Wartość funkcji celu
|
|
|
x |
y |
|
A B C D |
0 6 4 2 0 |
0 0 6 9 10 |
0
2
|
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.
Przyjmują, że koszt jednostki produktu A jest równy 20 zł , a że koszt jednostki produktu B jest równy 40 zł, podać jaka struktura żywienia zapewni najmniejszy dobowy koszt hodowli.
Składniki odżywcze
|
Zawartość składników w produkcie
|
Minimalna ilość składnika
|
|
|
A |
B |
|
|
36 |
6 |
108 |
|
3 |
12 |
36 |
|
20 |
10 |
100 |
ROZWIĄZANIE
Zmiennymi decyzyjnymi w tym przypadku będą:
- planowana liczba jednostek paszy A,
- planowana liczba jednostek paszy B .
Funkcja celu : dobowy koszt hodowli:
.
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.
Wierzchołki tego zbioru:
.
Zapiszemy w tabeli wartości funkcji celu dla poszczególnych punktów wierzchołkowych:
Punkt |
Współrzędne |
Wartość funkcji celu
|
|
|
x |
y |
|
A B C D |
12 4 2 0 |
0 2 6 18 |
|
Jak widać, funkcja celu osiąga wartość najmniejszą równą 160 w punkcie
.
Zatem najmniejszy dobowy koszt hodowli zapewni kupno 4 jednostek paszy A oraz 2 jednostek paszy B.
Opracował: dr Franciszek Bogowski
5