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:

1. budowa modelu matematycznego postawionego zadania,

2. rozwiązanie modelu,

3. 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ą :

1. sposób graficzny,

2. algorytm simpleks,

3. algorytm transportowy.

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

Należą do nich :

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

2. sformułowanie kryterium działalności oraz znalezienia jego matematycznej postaci ,

3. 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 :

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

2. 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:

wyroby surowce	A	B	zasoby 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
0 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