Programowanie liniowe
Programowanie liniowe
całkowitoliczbowe
całkowitoliczbowe
T.Trzaskalik
Wprowadzenie
do badań operacyjnych
z komputerem
Zaokrąglanie rozwiązań (1)
Zaokrąglanie rozwiązań (1)
Przykład 2.1
Przykład 2.1
Zadanie wyjściowe
Zadanie wyjściowe
x2
f(x1, x2) = 21x1 + 11x2 max
7x1 + 4x2 d" 13
x1, x2 e" 0
B
x1, x2 - całkowite
Zadanie zrelaksowane
Zadanie zrelaksowane
f(x1, x2) = 21x1 + 11x2 max
O x1
A (13/7, 0)
7x1 + 4x2 d" 13
x1, x2 e" 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 2
Zaokrąglanie rozwiązań (2)
Zaokrąglanie rozwiązań (2)
Porównanie wartościfunkcji kryterium
Porównanie wartościfunkcji kryterium
x2
(0, 3)
(0, 2)
(1, 1)
(0, 1)
(0, 0) (1, 0) x1
f(0, 0) = 0, f(0, 1) = 11, f(0, 2) = 22,
f(0, 3) = 33, f(1, 0) = 21, f(1, 1) = 32,
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 3
Zadanie czyste (1)
Zadanie czyste (1)
Przykład 2.2
Przykład 2.2
Zadanie wyjściowe
Zadanie wyjściowe
f(x1, x2) = x1 + x2 max
x2
x1 + 2x2 d" 32
18x1 + 3x2 d" 224
A (10 2/3, 10 2/3)
A (10 2/3, 10 2/3)
x1, x2 e" 0
10
x1, x2 - całkowite
Zadanie zrelaksowane
Zadanie zrelaksowane
f(x1, x2) = x1 + x2 max
O
x1
x1 + 2x2 d" 32
10
18x1 + 3x2 d" 224
x1, x2 e" 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 4
Zadanie czyste (2)
Zadanie czyste (2)
Podział względem x1
Podział względem x1
Zadanie 1
Zadanie 1
f(x1, x2) = x1 + x2 max
x1 + 2x2 d" 32
18x1 + 3x2 d" 224
x1, x2 e" 0
10 11 x1
10 2/3
Zadanie 2 Zadanie 3
Zadanie 2 Zadanie 3

x1 + x2 max x1 + x2 max
d" d"
x1 +2x2 32 x1 +2x2 32
d" d"
18x1 +3x2 224 18x1 +3x2 224
d" d" e"
0 x1 10 x1 11
e" e"
x1, x2 0 x1, x2 0
x1, x2  całkowite
x1, x2  całkowite
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 5
Zadanie czyste (3)
Zadanie czyste (3)
Zbiory rozwiązań dopuszczalnych zadań 2 i 3
Zbiory rozwiązań dopuszczalnych zadań 2 i 3
x2
B
Zadanie 2
Zadanie 2
C
Zadanie 3
Zadanie 3
O x1
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 6
Zadanie czyste (4)
Zadanie czyste (4)
Zbiory rozwiązań dopuszczalnych zadań 2 i 3
Zbiory rozwiązań dopuszczalnych zadań 2 i 3
x2 x2
B (10, 11)
C (11, 8 2/3)
O O
x1 x1
Zadanie 3
Zadanie 3
Zadanie 2
Zadanie 2
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 7
Zadanie czyste (5)
Zadanie czyste (5)
Podział względem x2
Podział względem x2
x2 Zadanie 3
Zadanie 3
x1 + x2 max
x1 + 2x2 d" 32
18x1 + 3x2 d" 224
Zadanie 1
Zadanie 1
x2 e" 11
11
f(x1, x2) = x1 + x2 max
x1, x2 e" 0
10 2/3
x1 + 2x2 d" 32
Zadanie 2
Zadanie 2
18x1 + 3x2 d" 224
10
x1 + x2 max
x1, x2 e" 0
x1 + 2x2 d" 32
18x1 + 3x2 d" 224
0 d" x2 d" 10
x1, x2 e" 0
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 8
Zadanie czyste (6)
Zadanie czyste (6)
Zbiory rozwiązań dopuszczalnych zadań 2 i 3
Zbiory rozwiązań dopuszczalnych zadań 2 i 3
x2
Zadanie 3
Zadanie 3
11 E
10 D
Zadanie 2
Zadanie 2
x1
O C
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 9
Zadanie czyste (7)
Zadanie czyste (7)
Rozwiązania zadań 2 i 3
Rozwiązania zadań 2 i 3
x2
x2
E (10, 11)
D (10 7/9, 10)
O O
x1 x1
Zadanie 3
Zadanie 3
Zadanie 2
Zadanie 2
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 10
Zadanie mieszane (1)
Zadanie mieszane (1)
Geometryczna interpretacja zbioru rozwiązań dopuszczalnych
Geometryczna interpretacja zbioru rozwiązań dopuszczalnych
x2
f(x1, x2) = x1 + x2 max
x1 + 2x2 d" 32
18x1 + 3x2 d" 224
x1, x2 e" 0
x1 - całkowite
O
x1
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 11
Zadanie mieszane (2)
Zadanie mieszane (2)
Geometryczna interpretacja zbioru rozwiązań dopuszczalnych (c.d.)
Geometryczna interpretacja zbioru rozwiązań dopuszczalnych (c.d.)
x2
f(x1, x2) = x1 + x2 max
x1 + 2x2 d" 32
18x1 + 3x2 d" 224
x1, x2 e" 0
x2 - całkowite
O
x1
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 12
Zadanie mieszane (3)
Zadanie mieszane (3)
Przykład 2.3
Przykład 2.3
Zadanie wyjściowe Zadanie zrelaksowane
Zadanie wyjściowe Zadanie zrelaksowane
3x1 + 3x2 + 13x3 max 3x1 + 3x2 + 13x3 max
 3x1 + 6x2 + 7x3 d" 8  3x1 + 6x2 + 7x3 d" 8
6x1  3x2 + 7x3 d" 8 6x1  3x2 + 7x3 d" 8
x1 e" 0 x1 e" 0
0 d" x2 d" 5 0 d" x2 d" 5
0 d" x3 d" 5 0 d" x3 d" 5
x2, x3 - całkowite Rozwiązanie
RozwiÄ…zanie
x1 = 2,667, x2 = 2,667, x3 = 0
fopt = 16
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 13
Zadanie mieszane (4)
Zadanie mieszane (4)
Iteracja 1
Iteracja 1
Lista rozpatrywanych zadań: 1
Lista rozpatrywanych zadań:
Zadania usuwane z listy: -
Zadania usuwane z listy:
Lista zadań po modyfikacji: 1
Lista zadań po modyfikacji:
Zadania wybrane do podziału: 1
Zadania wybrane do podziału:
RozwiÄ…zanie zadania 1: x1 = 2,667, x2 = 2,667, x3 = 0
RozwiÄ…zanie zadania 1:
Podział względem zmiennej: x2
Podział względem zmiennej:
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 14
Zadanie mieszane (5)
Zadanie mieszane (5)
Iteracja 1 (c.d.)
Iteracja 1 (c.d.)
Zadanie 1
Zadanie 1
3x1 + 3x2 + 13x3 max
 3x1 + 6x2 + 7x3 d" 8
6x1  3x2 + 7x3 d" 8
x1 e" 0 0 d" x2 d" 5 0 d" x3 d" 5
2 2,667 3
0 5 x2
Zadanie 2 Zadanie 3
Zadanie 2 Zadanie 3
3x1 + 3x2 + 13x3 max 3x1 + 3x2 + 13x3 max
 3x1 + 6x2 + 7x3 d" 8  3x1 + 6x2 + 7x3 d" 8
6x1  3x2 + 7x3 d" 8 6x1  3x2 + 7x3 d" 8
x1 e" 0 0 d" x2 d" 2 0 d" x3 d" 5 x1 e" 0 3 d" x2 d" 5 0 d" x3 d" 5
RozwiÄ…zanie
RozwiÄ…zanie
Zadanie sprzeczne
Zadanie sprzeczne
x1 = 2, x2 = 2, x3 = 0,286 fopt = 15,714
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 15
Zadanie mieszane (6)
Zadanie mieszane (6)
Iteracja 2
Iteracja 2
Lista rozpatrywanych zadań: 1, 2, 3
Lista rozpatrywanych zadań:
Zadania usuwane z listy: 1 (podzielone), 3 (sprzeczne)
Zadania usuwane z listy:
Lista zadań po modyfikacji: 2
Lista zadań po modyfikacji:
Zadania wybrane do podziału: 2
Zadania wybrane do podziału:
RozwiÄ…zanie zadania 2: x1 = 2, x2 = 2, x3 = 0,286
RozwiÄ…zanie zadania 2:
Podział względem zmiennej: x3
Podział względem zmiennej:
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 16
Zadanie mieszane (7)
Zadanie mieszane (7)
Iteracja 2 (c.d.)
Iteracja 2 (c.d.)
Zadanie 2
Zadanie 2
3x1 + 3x2 + 13x3 max
 3x1 + 6x2 + 7x3 d" 8
0 1 5 x3
6x1  3x2 + 7x3 d" 8
0,286
x1 e" 0 0 d" x2 d" 2 0 d" x3 d" 5
Zadanie 5
Zadanie 5
Zadanie 4
Zadanie 4
3x1 + 3x2 + 13x3 max
3x1 + 3x2 + 13x3 max
 3x1 + 6x2 + 7x3 d" 8
 3x1 + 6x2 + 7x3 d" 8
6x1  3x2 + 7x3 d" 8
6x1  3x2 + 7x3 d" 8
x1 e" 0 0 d" x2 d" 2 1 d" x3 d" 5
x1 e" 0 0 d" x2 d" 2 0 d" x3 d" 0
RozwiÄ…zanie RozwiÄ…zanie
RozwiÄ…zanie RozwiÄ…zanie
x1 = 2,33, x2 = 2, x3 = 0 x1 = 0,33, x2 = 0,33, x3 = 1
fopt = 13 fopt = 15
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 17
Zadanie mieszane (8)
Zadanie mieszane (8)
Iteracja 3
Iteracja 3
Lista rozpatrywanych zadań: 2, 4, 5
Lista rozpatrywanych zadań:
Zadania usuwane z listy: 2 (podzielone),
Zadania usuwane z listy:
Lista zadań po modyfikacji: 4, 5
Lista zadań po modyfikacji:
Zadania wybrane do podziału: 5
Zadania wybrane do podziału:
RozwiÄ…zanie zadania 2: x1 = 0,33, x2 = 0,33, x3 = 1
RozwiÄ…zanie zadania 2:
Podział względem zmiennej: x2
Podział względem zmiennej:
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 18
Zadanie mieszane (9)
Zadanie mieszane (9)
Iteracja 3 (c.d.)
Iteracja 3 (c.d.)
Zadanie 5
Zadanie 5
3x1 + 3x2 + 13x3 max
 3x1 + 6x2 + 7x3 d" 8
0 1 x2
2
6x1  3x2 + 7x3 d" 8
0,333
x1 e" 0 0 d" x2 d" 2 1 d" x3 d" 5
Zadanie 7
Zadanie 7
Zadanie 6
Zadanie 6
3x1 + 3x2 + 13x3 max
3x1 + 3x2 + 13x3 max
 3x1 + 6x2 + 7x3 d" 8
 3x1 + 6x2 + 7x3 d" 8
6x1  3x2 + 7x3 d" 8
6x1  3x2 + 7x3 d" 8
x1 e" 0 1 d" x2 d" 2 1 d" x3 d" 5
x1 e" 0 0 d" x2 d" 0 1 d" x3 d" 5
RozwiÄ…zanie Zadanie sprzeczne
RozwiÄ…zanie Zadanie sprzeczne
x1 = 0, x2 = 0, x3 = 1,143
fopt = 14,857
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 19
Zadanie mieszane (10)
Zadanie mieszane (10)
Iteracja 4
Iteracja 4
Lista rozpatrywanych zadań: 4, 5, 6, 7
Lista rozpatrywanych zadań:
Zadania usuwane z listy: 5 (podzielone), 7 (sprzeczne)
Zadania usuwane z listy:
Lista zadań po modyfikacji: 4, 6
Lista zadań po modyfikacji:
Zadania wybrane do podziału: 6
Zadania wybrane do podziału:
RozwiÄ…zanie zadania 6: x1 = 0, x2 = 0, x3 = 1,143
RozwiÄ…zanie zadania 6:
Podział względem zmiennej: x3
Podział względem zmiennej:
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 20
Zadanie mieszane (11)
Zadanie mieszane (11)
Iteracja 4 (c.d.)
Iteracja 4 (c.d.)
Zadanie 6
Zadanie 6
1 2
3x1 + 3x2 + 13x3 max
 3x1 + 6x2 + 7x3 d" 8
5 x3
1,143
6x1  3x2 + 7x3 d" 8
x1 e" 0 0 d" x2 d" 0 1 d" x3 d" 5
Zadanie 9
Zadanie 9
Zadanie 8
Zadanie 8
3x1 + 3x2 + 13x3 max
3x1 + 3x2 + 13x3 max
 3x1 + 6x2 + 7x3 d" 8
 3x1 + 6x2 + 7x3 d" 8
6x1  3x2 + 7x3 d" 8
6x1  3x2 + 7x3 d" 8
x1 e" 0 1 d" x2 d" 2 2 d" x3 d" 5
x1 e" 0 0 d" x2 d" 0 1 d" x3 d" 1
RozwiÄ…zanie Zadanie sprzeczne
RozwiÄ…zanie Zadanie sprzeczne
x1 = 0,167, x2 = 0, x3 = 1
fopt = 13,5
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 21
Zadanie mieszane (12)
Zadanie mieszane (12)
Iteracja 5
Iteracja 5
Lista rozpatrywanych zadań: 4, 6, 8, 9
Lista rozpatrywanych zadań:
Zadania usuwane z listy: 6 (podzielone), 9 (sprzeczne)
Zadania usuwane z listy:
4 (fopt(4) = 13 < fopt(8) = 13,5)
Lista zadań po modyfikacji:
Lista zadań po modyfikacji: 8
x1 = 0,167, x2 = 0, x3 = 1
RozwiÄ…zanie zadania 8:
RozwiÄ…zanie zadania 8:
Spełnione warunki całkowitoliczbowości. Rozwiązanie to jest
rozwiązaniem optymalnym zadania wyjściowego.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 22
Zadanie mieszane (13)
Zadanie mieszane (13)
Zestawienie rozwiązywanych zadań
Zestawienie rozwiązywanych zadań
Optymalna Nowo-
Zakresy zmienności Rozwiązanie optymalne
Numer
wartość generowane
zadania
x2 x3 x1 x2 x3
funkcji celu zadania
1 [0, 5] [0, 5] 2,667 2,667 0 16 2, 3
2 [0, 2] [0, 5] 2 2 0,286 15,714 4, 5
3 [3, 5] [0, 5] Zadanie sprzeczne
4 [0, 2] [0, 0] 2,333 2 0 13
5 [0, 2] [1, 5] 0,333 0,333 1 15 6,7
6 [0, 0] [1, 5] 0 0 1,143 14,857 8,9
7 [1, 2] [1, 5] Zadanie sprzeczne
8 [0, 0] [1, 1] 0,167 0 1 13,5
9 [1, 2] [2, 5] Zadanie sprzeczne
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 23
Reguły postępowania w metodzie podziału i ograniczeń
Reguły postępowania w metodzie podziału i ograniczeń
1. Porządkowanie listy zadań zrelaksowanych.
1.
2. Sprawdzenie kryterium optymalności i w przypadku
2.
jego spełnienia zakończenie obliczeń.
3. Wybór zadania do podziału.
3.
4. Wybór zmiennej, względem której dokonamy podziału.
4.
5. Podział zadania, rozwiązanie nowo utworzonych zadań i
5.
umieszczenie ich na liście zadań zrelaksowanych.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 24
Równanie cięcia (1)
Równanie cięcia (1)
Przykład 2.4
Przykład 2.4
x1 + x2 max x1 + x2 max
x1 + 2x2 + x3 = 32
x1 + 2x2 d" 32
18x1 + 3x2 + x4 = 224
18x1 + 3x2 d" 224
x1, x2 e" 0 x1, x2, x3, x4 e" 0
x1, x2 - całkowite
cx max 1 1 0 0
b
Baza x1 x2 x3 x4
x2 1 0 1 0,5455 -0,0303 10,6667
x1 1 1 0 -0,0909 0,0606 10,6667
x1 1 1 0 -0,0909
0,0606 10,6667
cj  zj 0 0 -0,4545 -0,0303 21,3333
x1  0,0909x3 + 0,0606x4 = 10,6667
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 25
Równanie cięcia (2)
Równanie cięcia (2)
Wyprowadzenie wzoru
Wyprowadzenie wzoru
[-0,0909] d" -0,0909 [-0,0909]x3 d" -0,0909x3
[0,0606] d" 0,0606 [0,0606]x4 d" 0,0606x4
[-0,0909]x3 + [0,0606]x4 d" -0,0909x3 + 0,0606x4
x1 + [ 0,0909]x3 + [0,0606]x4 d" x1  0,0909x3 + 0,0606x4 = 10,6667
x1 + [-0,0909]x3 + [0,0606]x4 d" 10,6667
x1 + [-0,0909]x3 + [0,0606]x4 d" [10,6667]
x1 + [-0,0909]x3 + [0,0606]x4 + x5 = [10,6667]
([-0,0909] + 0,0909)x3 + ([0,0606]  0,0606)x4 + x5 = [10,6667]  10,6667
-0,9091x3  0,0606x4 + x5 = -0,6667
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 26
Równanie cięcia (3)
Równanie cięcia (3)
Rozszerzenie tablicy simpleksowej
Rozszerzenie tablicy simpleksowej
0
cx max 1 1 0 0 0
b
x4
Baza x1 x2 x3 x4 x5
x2 1 0 1 0,5455 -0,0303 0 10,6667
-0,0303
0,0606
x1 1 1 0 -0,0909 0,0606 0 10,6667
x5 0 0 0 -0,9091 -0,0606 1 -0,6667
x5 0 0 0 -0,9091 -0,0606 1 -0,6667
-0,0606
cj  zj 0 0 -0,4545 -0,0303 0 21,3333
-0,0303
Dualna metoda simpleks
Dualna metoda simpleks
cx max 1 1 0 0 0
b
Baza x1 x2 x3 x4 x5
x2 1 0 1 1 0 -0,5 11
x1 1 1 0 -1 0 1 10
x4 1 0 0 15 1 -16 11
cj  zj 0 0 0 0  0,5 21
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 27
Równanie cięcia (4)
Równanie cięcia (4)
Interpretacja geometryczna
Interpretacja geometryczna
 0,9091x3  0,0606x4 + x5 =  0,6667
10 2 2
- x3 - x4 + x5 = -
11 33 3
10 2 2
- x3 - x4 d" -
11 33 3
x3 = 32  x1  2x2
x4 = 224  18x1  3x2
10 2 2
- (32 - x1 - 2x2) - (224 -18x1 - 3x2) d" -
11 33 3
x1 + x2 d" 21
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 28
Równanie cięcia (5)
Równanie cięcia (5)
Interpretacja geometryczna (c.d.)
Interpretacja geometryczna (c.d.)
C2
x2
C1 C3
C2(10,11)
B
10,67
C1(10,10) C3(11,11)
10,67 x1
O
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 29
Reguły postępowania w metodzie cięć
Reguły postępowania w metodzie cięć
1. RozwiÄ…zanie zadania zrelaksowanego.
1.
2. Wybór równania wykorzystywanego do
2.
konstrukcji równania cięcia (wiersz i).
3. Konstrukcja równania cięcia:
3.
( - aij xij + xn+1 = [bi ] - bi
[aij ] )
"
zmienne niebazowe
4. Przejście do nowej bazy dopuszczalnej.
4.
5. Zakończenie postępowania.
5.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 30
Modernizacja parku maszynowego (1)
Modernizacja parku maszynowego (1)
Przykład 2.5
Przykład 2.5
Produkty Maksymalny
Czas pracy
1 2 3 czas pracy
Maszyna 1 1 3 2 30
Maszyna 2 2 2 6 20
Zysk jednostkowy 1 2 3
Zwiększenie
Maszyna Wariant Koszt
czasu pracy
1 7 45
1
2 16 70
1 10 28
2
2 30 80
A
ączny koszt modernizacji nie może przekroczyć 125.
Należy dokonać takiej modernizacji maszyn, by zmaksymalizować zysk
przy zwiększonych możliwościach produkcyjnych.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 31
Modernizacja parku maszynowego (2)
Modernizacja parku maszynowego (2)
Cel
Cel
Celem jest dokonanie takiej modernizacji maszyn, by zmaksymalizować zysk
otrzymany z wytworzenia produktów P1, P2, P3.
Zmienne decyzyjne
Zmienne decyzyjne
x1  planowany rozmiar produkcji wyrobu P1,
x2  planowany rozmiar produkcji wyrobu P2,
x3  planowany rozmiar produkcji wyrobu P3,
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 32
Modernizacja parku maszynowego (3)
Modernizacja parku maszynowego (3)
Zmienne dodatkowe
Zmienne dodatkowe
1, jeżeli czas pracy maszyny 1 zostanie zwiększony o 7 jednostek
Å„Å‚
x4 =
òÅ‚
ół0, w przeciwnym wypadku
1, jeżeli czas pracy maszyny 1 zostanie zwiększony o 16 jednostek
Å„Å‚
x5 =
òÅ‚
ół0, w przeciwnym wypadku
1, jeżeli czas pracy maszyny 2 zostanie zwiększony o 10 jednostek
Å„Å‚
x6 =
òÅ‚
ół0, w przeciwnym wypadku
1, jeżeli czas pracy maszyny 2 zostanie zwiększony o 30 jednostek
Å„Å‚
x7 =
òÅ‚
ół0, w przeciwnym wypadku
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 33
Modernizacja parku maszynowego (4)
Modernizacja parku maszynowego (4)
Funkcja celu
Funkcja celu
f(x1, x2, x3) = x1 + 2x2 + 3x3
Warunki ograniczajÄ…ce
Warunki ograniczajÄ…ce
ograniczenie zwiÄ…zane z czasem pracy maszyny 1:
x1 + 3x2 + 2x3 d" 30 + 7x4 + 16x5
ograniczenie zwiÄ…zane z czasem pracy maszyny 2:
2x1 + 2x2 + 6x3 d" 20 + 10x6 + 30x7
warunek budżetowy:
45x4 + 70x5 + 28x6 + 80x7 d" 125
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 34
Modernizacja parku maszynowego (5)
Modernizacja parku maszynowego (5)
Warunki ograniczajÄ…ce (c.d.)
Warunki ograniczajÄ…ce (c.d.)
Warunki określające możliwość jednoczesnej realizacji wariantów:
dla maszyny 1:
x4 + x5 d" 1
dla maszyny 2:
x6 + x7 d" 1
warunki nieujemności:
x1, x2, x3 e" 0
warunki dodatkowe:
x4, x5, x6, x7 " {0, 1}
RozwiÄ…zanie optymalne
RozwiÄ…zanie optymalne
x1 = 0, x2 = 8,7, x3 = 5,43, x4 = 1, x5 = 0, x6 = 0, x7 = 1
Wartość funkcji celu jest równa 33,71
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 35
Plan wydawniczy (1)
Plan wydawniczy (1)
Przykład 2.6
Przykład 2.6
Przedmiot Rodzaj skryptu Prognoza sprzedaży
ZarzÄ…dzanie nowe wydanie 2500
Matematyka wznowienie 3000
Statystyka nowe wydanie 2000
Statystyka matematyczna nowe wydanie 1500
Statystyka opisowa wznowienie 1500
Finanse nowe wydanie 1800
Rachunkowość nowe wydanie 3000
Rachunkowość II wznowienie 3500
Angielski nowe wydanie 5000
Francuski nowe wydanie 3500
Nad skryptami mogą pracować redaktorzy:
Jerzy480 godzin,
Krystyna 320 godzin,
Maria 350 godzin.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 36
Plan wydawniczy (2)
Plan wydawniczy (2)
Przykład 2.6 (c.d.)
Przykład 2.6 (c.d.)
Skrypt Jerzy Krystyna Maria
ZarzÄ…dzanie 220 300 -
Matematyka 130 190 -
Statystyka 190 150 210
Statystyka matematyczna 160 - 190
Statystyka opisowa 90 - 120
Finanse - 220 100
Rachunkowość - - 200
Rachunkowość II - - 180
Angielski 300 - 240
Francuski - 400 310
Wydane zostanÄ…:
- co najwyżej dwa skrypty ze statystyki,
- co najwyżej jeden skrypt z rachunkowości,
- matematyka lub zarzÄ…dzanie,
Należy określić najlepszy plan wydawniczy.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 37
Plan wydawniczy (3)
Plan wydawniczy (3)
Cel
Cel
Ustalenie planu wydawniczego, który maksymalizuje łączną, planowaną
wielkość sprzedaży
Zmienne decyzyjne
Zmienne decyzyjne
Zmienna Opis zmiennej Wartość
x1 wydanie ZarzÄ…dzanie {0, 1}
skryptu:
x2 Matematyka {0, 1}
x3 Statystyka {0, 1}
x4 Statystyka matematyczna {0, 1}
x5 Statystyka opisowa {0, 1}
x6 Finanse {0, 1}
x7 Rachunkowość {0, 1}
x8 Rachunkowość II {0, 1}
x9 Angielski {0, 1}
x10 Francuski {0, 1}
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 38
Plan wydawniczy (4)
Plan wydawniczy (4)
Funkcja celu
Funkcja celu
25x1 + 30x2 + 20x3+ 15x4+ 15x5+ 18x6+ 30x7+ 35x8+ 50x9+ 35x10 max
Warunki ograniczajÄ…ce
Warunki ograniczajÄ…ce
Jerzy - co najwyżej 480 godzin:
220x1 + 130x2 + 190x3 + 160x4 + 90x5 + 300x9 d" 480
Krystyna - co najwyżej 320 godzin:
300x1 + 190x2 + 150x3 + 220x6 + 400x10 d" 320
Maria - co najwyżej 350 godzin:
210x3 + 190x4 + 120x5 + 100x6 + 200x7 + 180x8 + 240x9 + 310x10 d" 350
Nie więcej niż dwa skrypty ze statystyki:
x3 + x4 + x5 d" 2
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 39
Plan wydawniczy (5)
Plan wydawniczy (5)
Warunki ograniczajÄ…ce (c.d.)
Warunki ograniczajÄ…ce (c.d.)
W planie nie może się znalez
ć więcej niż jeden skrypt z rachunkowości:
x7 + x8 d" 1
W planie musi siÄ™ znalez
ć skrypt z zarządzania lub matematyki:
x1 + x2 = 1
Dodatkowe warunki na zmienne decyzyjne:
x1, x2, x3, x4, x5, x6, x7, x8, x9, x10 " {0, 1}
RozwiÄ…zanie optymalne
RozwiÄ…zanie optymalne
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
RozwiÄ…zanie 1
0 1 0 0 1 0 0 1 0 0
x1 x2 x3 x4 x5 x6 x7 x8 x9 x10
RozwiÄ…zanie 2
0 1 0 0 0 0 0 0 1 0
Optymalna wartość funkcji celu wynosi 80.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 40
Relokalizacja komisariatów policji (1)
Relokalizacja komisariatów policji (1)
Przykład 2.7
Przykład 2.7
Proponowana lokalizacja Rejony
A 1, 5, 7
B 1, 2, 5, 7
C 1, 3, 5
D 2, 4, 5
E 3, 4, 6
F 4, 5, 6
G 1, 5, 6, 7
Należy znalez
ć najmniejszą liczbę zrelokalizowanych komisariatów
pokrywających swym zasięgiem wszystkie siedem rejonów.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 41
Relokalizacja komisariatów policji (2)
Relokalizacja komisariatów policji (2)
Cel
Cel
Określenie najmniejszej liczby relokalizowanych komisariatów, aby każdy
rejon był pod opieką przynajmniej jednego komisariatu.
Zmienne decyzyjne
Zmienne decyzyjne
Zmienna Opis zmiennej Wartość
x1 A {0, 1}
x2 B {0, 1}
Proponowa-
x3 C {0, 1}
na
x4 D {0, 1}
lokalizacja
x5 E {0, 1}
komisariatu:
x6 F {0, 1}
x7 G {0, 1}
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 42
Relokalizacja komisariatów policji (3)
Relokalizacja komisariatów policji (3)
Funkcja celu
Funkcja celu
x1 + x2 + x3+ x4+ x5+ x6+ x7 min
Warunki ograniczajÄ…ce
Warunki ograniczajÄ…ce
Rejon 1:
x1 + x2 + x3 + x7 e" 1
Rejon 2:
x2 + x4 e" 1
Rejon 3:
x3 + x5 e" 1
Rejon 4:
x4 + x5 + x6 e" 1
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 43
Relokalizacja komisariatów policji (4)
Relokalizacja komisariatów policji (4)
Warunki ograniczajÄ…ce (c.d.)
Warunki ograniczajÄ…ce (c.d.)
Rejon 5:
x1 + x2 + x3 + x4 + x5 + x7 e" 1
Rejon 6:
x1 + x2 + x7 e" 1
Dodatkowe warunki na zmienne decyzyjne:
x1, x2, x3, x4, x5, x6, x7 " {0, 1}
RozwiÄ…zanie optymalne
RozwiÄ…zanie optymalne
x1 x2 x3 x4 x5 x6 x7
0 1 0 0 1 0 0
Optymalna wartość funkcji celu wynosi 2.
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 44
Podsumowanie
Podsumowanie
SÅ‚owa kluczowe
" Rozwiązanie całkowitoliczbowe
" Założenie podzielności
" Warunki całkowitoliczbowości
" Czyste zadanie programowania całkowitoliczbowego
" Mieszane zadanie programowania całkowitoliczbowego
" Relaksacja zadania
" Metoda zaokrągleń
" Metoda podziału i ograniczeń
" Metoda cięć
" Zmienne binarne
Pora na relaks
Pora na relaks
T.Trzaskalik: Wprowadzenie do badań operacyjnych z komputerem 2/ 45