Optymalizacja procesów technologicznych przy zastosowaniu programowania liniowego

Wstęp

Spośród różnych analitycznych metod stosowanych do rozwiązywania problemów optymalizacji procesów technologicznych do najefektowniejszych zaliczane jest programowanie liniowe (linear programming).

Zastosowanie programowania liniowego do optymalizacji procesów technologicznych

1. Modele transportowe

Problem transportowy w praktyce najogólniej określany jest jako problem optymalnej dystrybucji towarów. Rozwiązanie problemu transportowego daje odpowiedź na pytanie, jak przy najmniejszych kosztach zorganizować przewozy masy towarowej od dostawców do odbiorców. Z problemami transportowymi wiążą się również takie zagadnienia jak: transportowo-produkcyjne, lokalizacji obiektów, problem obsady, problem pustych przebiegów itd.

2. Problem mieszanek

W zagadnieniu optymalnego składu mieszaniny podejmujący decyzję pragnie określić jakie ilości surowców mineralnych należy użyć do przerobienia na gotowe do sprzedaży wyroby.

Programowanie liniowe

Problem programowania liniowego definiuje się w postaci :

przy ograniczeniach liniowych

oraz więzach nakładanych na na zmienne

gdzie:

x jest wektorem zmiennych optymalizowanych,

b jest wektorem współczynników liczbowych,

A jest macierzą,

v_lb , v_ub są wektorami ograniczającymi zakres zmiennych optymalizowanych.

Przy wystąpieniu ograniczeń równościowych powinny być one umieszczone w pierwszych wierszach macierzy A i wektora b.

Metody rozwiązywania zagadnienia programowania liniowego

Obecnie na rynku dostępne są różne pakiety programów komputerowych dzięki którym można o. Jednym z nich jest moduł Solver programu Excel.

Zadanie programowanie liniowego zawierające tylko dwie zmienne decyzyjne można prosto rozwiązać w sposób graficzny.

Przebieg ćwiczenia

Przykład 1

Problem

Należy znaleźć min -> -5x₁+4x₂-10x₃

przy ograniczeniach liniowych:

x₁+x₂=0

x₁ - x₂ +x₃ <= 30

x₁ - 2x₂ -5x₃ <= 50

3x₁-x₂ <= 10

oraz więzach nakładanych na zmienne

-10<= x₁ <=10,

-5<= x₂ <=15,

0<= x₃ <=5,

Rozwiązanie

1. Rozwiązanie problemu za pomocą SOLVER-a (programu narzędziowego pakietu Excel)

2. Należy przygotować arkusz w Excelu (poniżej), a następnie włączyć program Solver znajdujący się w pasku narzędziowym.

Po uruchomieniu Solvera należy:

3. Określić funkcję celu

- zaznaczyć odpowiednią komórkę w arkuszu (A4) z równaniem liniowym określającym minimum (maksimum),

- zaznaczyć w Solverze pole maksimum, minimum lub podać wartość którą to równanie ma spełniać.

4. Wypełnić pole określające które zmienne (komórki A2, B2,C2) mają być optymalizowane.

5. W następnym polu Solvera podać ograniczenia (komórki A8, A10, A12, A14) którym podlega optymalizowana funkcja.

6. Podać ograniczenia na zmienne:

A2>=A18, A2<=B18

B2>=A20, B2<=B20

C2>=A22, C2<=B22

7. Uruchomić przycisk równanie.

Przygotowany arkusz Excela dla przykładu 1

	A	B	C	D
1	x1	x2	x3
2	1	1	1
3	min-> -5*x1+4*x2-10*x3			funkcja celu
4	-5*A2+4*B2-10*C2
5
6	ograniczenia liniowe
7	x1+x2=0
8	A2+B2	0
9	x1-x2+x3<=30
10	A2-B2+C2	30
11	x1+2x2-5x3<=50
12	A2+2*B2-5*C2	50
13	3x1-x2<=10
14	3*A2-B2	10
15
16	więzy nakładane na zmienne
17	-10<=X1<=10
18	-10	10
19	-5<=X2<=15
20	-5	15
21	0<=x3<=5
22	0	5
23

Otrzymane wyniki obliczeń optymalizacyjnych

Zmienne optymalizowane
x1	x2	x3
2,5	-2,5	5
min -> -5*x1+4*x2-10*x3			Funkcja celu
-72,5
ograniczenia liniowe
x1+x2=0
0	0
x1-x2+x3<=30
10	30
x1+2x2-5x3<=50
-27,5	50
3x1-x2<=10
10	10
więzy nakładane na zmienne
-10<=X1<=10
-10	10
-5<=X2<=15
-5	15
0<=x3<5
0	5

Przykład 2

Dwa gatunki węgla A i B zawierają zanieczyszczenia fosforem i popiołem. W pewnym procesie przemysłowym potrzeba co najmniej 90 ton żeliwa zawierającego nie więcej niż 0.03% fosforu i nie więcej niż 4% popiołu. Procent zanieczyszczeń i ceny zakupu poszczególnych gatunków węgla (w jednostkach względnych) podaje tablica 1.

Tablica 1

Gatunek	Procentowe zawartości	zanieczyszczeń	Cena zakupu
Węgla	fosforu	popiołu	1 tony węgla (j. wzg)
A	0,02	3	500
B	0,05	5	400

Problem:

Jak zmieszać wymienione dwa gatunki węgla, aby uzyskać paliwo o możliwie najniższym koszcie, spełniające wyżej wymienione wymagania ?

Rozwiązanie:

Należy zbudować model matematyczny opisujący przedstawioną sytuację. Niech X₁ oznacza gatunek węgla A, a X₂ gatunek węgla B.

Pierwsze równanie dotyczy minimalnej ilości węgla (w tonach) potrzebnej w rozpatrywanym procesie przemysłowym:

X₁ + X₂ >= 90

Ograniczenia jakościowe są następujące:

0,02*X₁ + 0,05*X₂ <= 0,03*(X₁ + X₂ )

3*X₁ + 5*X₂ <= 4*(X₁ + X₂ )

Funkcja celu jest następująca:

F(X₁, X₂) = 500*X₁ + 400*X₂ --> min

W sytuacji gdy mamy do czynienia tylko z dwiema zmiennymi decyzyjnymi problem optymalizacji możemy rozwiązać metodą geometryczną.

Metoda geometryczna

Polega na wykreśleniu funkcji opisujących poszczególne zmienne na wykresie X1-0-X2. Otrzymamy w ten sposób obszar możliwych rozwiązań (rys.1). Tylko punkty przecięcia ograniczające poszczególne obszary mogą być rozwiązaniem zagadnienia.

W celu określenia minimum funkcji celu wartości współrzędnych poszczególnych punktów przecięcia wstawiamy do równania funkcji celu i obliczamy jej wartość. Wartość minimalna funkcji celu w jednym z punktów przecięcia określi poszukiwane wartości zmiennych decyzyjnych X₁, X₂.

Rys.1 Obszary ograniczeń

W naszym przykładzie obszar ograniczający to: ABCD

Punkty przecięcia to: A(60,30); B(90,18); C(120,0); D(90,0);

Funkcja celu w tych punktach ma wartość:

F(X_1A, X_2A) =42000 --> minimum

F(X_1B, X_2B) =52200

F(X_1C, X_2C) =60000

F(X_1D, X_2D) =45000

Rozwiązanie: X₁=60 ton, X₂=30 ton

Innym sposobem określenia punktu przecięcia wyznaczającego minimalną wartości funkcji celu jest wykreślenie tzw. linii śladowej.

Ślad tworzymy z funkcji minimalnej przyjmując jako minimalną - dowolną wartość liczbową (najprościej wielokrotność X1 i X2): np. 500X1+400X2=20000. Tworzymy prostą odcinkową (punkty X1=0,X2=50 ; X1=40, X2=0). Równolegle do tej prostej przesuwamy się do obszaru rozwiązań i pierwszy (zaczynając od początkowego obszaru rozwiązań-jak w przykładzie) lub ostatni (zaczynając od końcowego obszaru rozwiązań) punkt przecięcia (wierzchołek obszaru ograniczającego) jest rozwiązaniem. Dla naszego zadania jest to punkt A.

7

---