Programowanie
całkowitoliczbowe
Gliwice
1
Metoda
podziału i ograniczeń
Gliwice
2
Metoda podziału i ograniczeń
Przykład 6
Rozwiązać zadanie z Przykładu 1 metodą podziału i ograniczeń,
przy czym wielkość produkcji wyrobu F2 musi być określona
liczbą całkowitą.
Gliwice
3
Metoda podziału i ograniczeń
Model matematyczny:
FC:
Z x1, x2 = 6x1 + 5x2 MAX
( )
O:
9x1 + 7x2 d" 63
1
x1 + x2 d" 8
2
3x1 + 2x2 e" 6
3
WB:
x1 e" 0, x2 e" 0
x2 "C
Gliwice
4
Metoda podziału i ograniczeń
Szukamy rozwiązania nie uwzględniając warunku
całoliczbowości (patrz metoda geometryczna lub simpleks)
Zadanie 1
Z x1, x2 = 6x1 + 5x2 MAX
( )
9x1 + 7x2 d" 63
1
x1 + x2 d" 8
2
3x1 + 2x2 e" 6
3
x1 e" 0, x2 e" 0
Rozwiązanie: x1 = 3.5, x2 = 4.5, Z(x1, x2) = 43.5
Gliwice
5
Metoda podziału i ograniczeń
Zadanie umieszczamy na liście zadań
Czy spełnione
Numery zadań, na
Nr Wartość
które zadanie zostało
są warunki
zadania FC
podzielone
całkowitoliczbowości
Gliwice
6
Metoda podziału i ograniczeń
Zmienna x2 nie spełnia nałożonego na nią w zadaniu
głównym warunku x2 " C
Dokonujemy podziału:
Otrzymujemy dwa przedziały:
Gliwice
7
Metoda podziału i ograniczeń
Na podstawie otrzymanych przedziałów budujemy dwa zadania:
Zadanie 2 Zadanie 3
Z x1, x2 = 6x1 + 5x2 MAX Z x1, x2 = 6x1 + 5x2 MAX
() ()
9x1 + 7x2 d" 63 9x1 + 7x2 d" 63
1 1
x1 + x2 d" 8 x1 + x2 d" 8
2 2
3x1 + 2x2 e" 6 3x1 + 2x2 e" 6
3 3
x2 d" 4 x2 e" 5
4 4
x1 e" 0, x2 e" 0 x1 e" 0, x2 e" 0
Gliwice
8
Metoda podziału i ograniczeń
Numery zadań umieszczamy na liście zadań:
Czy spełnione
Numery zadań, na
Nr Wartość
które zadanie zostało
są warunki
zadania FC
podzielone
całkowitoliczbowości
Gliwice
9
Metoda podziału i ograniczeń
x2
10
Zadanie 3
9
8
H
7
6
ZRD
F G
5
C
D
4
Zadanie 2
3
E
2
ZRD
1
1 2 3 4 5 6
A
B7 8 9 10 x1
Gliwice
10
Metoda podziału i ograniczeń
Dla Zadania 2
35
Maksimum w punkcie: C�# ,4ś#
ś# ź#
9
�# #
35 1
Z�# , 4ś# = 43
Wartość funkcji celu:
ś#ź#3
9
�# #
Dla Zadania 3
Maksimum w punkcie: G 3,5
( )
Z 3,5 = 43
( )
Wartość funkcji celu:
Gliwice
11
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Czy spełnione
Numery zadań, na
Nr Wartość
które zadanie zostało
są warunki
zadania FC
podzielone
całkowitoliczbowości
Gliwice
12
Metoda podziału i ograniczeń
Porządkowanie listy zadań:
Z listy usuwamy:
Gliwice
13
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Czy spełnione
Numery zadań, na
Nr Wartość
które zadanie zostało
są warunki
zadania FC
podzielone
całkowitoliczbowości
Na liście pozostało tylko jedno zadanie.
Ponieważ spełnia ono wszystkie warunki całkowitoliczbowości,
to jego rozwiązanie jest rozwiązaniem optymalnym zadania
pierwotnego.
Gliwice
14
Metoda podziału i ograniczeń
Przykład 7
Rozwiązać zadanie z Przykładu 1 metodą podziału i ograniczeń,
przy czym wielkość produkcji obydwu wyrobów musi być
określona liczbą całkowitą.
Gliwice
15
Metoda podziału i ograniczeń
Model matematyczny:
FC:
Z x1, x2 = 6x1 + 5x2 MAX
( )
O:
9x1 + 7x2 d" 63
1
x1 + x2 d" 8
2
3x1 + 2x2 e" 6
3
WB:
x1 e" 0, x2 e" 0
x1 "C, x2 "C
Gliwice
16
Metoda podziału i ograniczeń
Szukamy rozwiązania nie uwzględniając warunku
całoliczbowości (patrz metoda geometryczna lub simpleks)
Zadanie 1
Z x1, x2 = 6x1 + 5x2 MAX
( )
9x1 + 7x2 d" 63
1
x1 + x2 d" 8
2
3x1 + 2x2 e" 6
3
x1 e" 0, x2 e" 0
Rozwiązanie: x1 = 3.5, x2 = 4.5, Z(x1, x2) = 43.5
Gliwice
17
Metoda podziału i ograniczeń
Zadanie umieszczamy na liście zadań
Czy spełnione
Numery zadań, na
Nr Wartość
które zadanie zostało
są warunki
zadania FC
podzielone
całkowitoliczbowości
Gliwice
18
Metoda podziału i ograniczeń
Ponieważ obydwie zmienne nie spełniają warunków
całkowitoliczbowości, wybieramy zmienną, względem
której dokonamy podziału.
Dokonujemy podziału względem x1:
Otrzymujemy dwa przedziały:
Gliwice
19
Metoda podziału i ograniczeń
Na podstawie otrzymanych przedziałów budujemy dwa zadania:
Zadanie 2 Zadanie 3
Z x1, x2 = 6x1 + 5x2 MAX Z x1, x2 = 6x1 + 5x2 MAX
() ()
9x1 + 7x2 d" 63 9x1 + 7x2 d" 63
1 1
x1 + x2 d" 8 x1 + x2 d" 8
2 2
3x1 + 2x2 e" 6 3x1 + 2x2 e" 6
3 3
x1 d" 3 x1 e" 4
4 4
x1 e" 0, x2 e" 0 x1 e" 0, x2 e" 0
Gliwice
20
Metoda podziału i ograniczeń
Rozwiązanie Zadania 2
x1 = 3, x2 = 5, Z x1, x2 = 43
( )
Rozwiązanie Zadania 3
x1 = 4, x2 = 3.8, Z x1, x2 = 43.2851
( )
Gliwice
21
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Czy spełnione
Numery zadań, na
Nr Wartość
które zadanie zostało
są warunki
zadania FC
podzielone
całkowitoliczbowości
Gliwice
22
Metoda podziału i ograniczeń
Porządkowanie listy zadań:
Z listy usuwamy:
Na liście pozostaje:
Gliwice
23
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Czy spełnione
Numery zadań, na
Nr Wartość
które zadanie zostało
są warunki
zadania FC
podzielone
całkowitoliczbowości
Gliwice
24
Metoda podziału i ograniczeń
Rozwiązanie Zadania 3
x1 = 4 x2 = 3.8
Ponieważ zmienna x2 nie spełnia warunków
całkowitoliczbowości, dokonujemy podziału ze względu
na tą zmienną.
x2 = 3.8
Gliwice
25
Metoda podziału i ograniczeń
Na podstawie otrzymanych przedziałów budujemy dwa zadania:
Zadanie 4 Zadanie 5
Z x1, x2 = 6x1 + 5x2 MAX Z x1, x2 = 6x1 + 5x2 MAX
() ()
9x1 + 7x2 d" 63 9x1 + 7x2 d" 63
1 1
x1 + x2 d" 8 x1 + x2 d" 8
2 2
3x1 + 2x2 e" 6 3x1 + 2x2 e" 6
3 3
x1 e" 4 x1 e" 4
4 4
x2 d" 3 x2 e" 4
5 5
x1 e" 0, x2 e" 0 x1 e" 0, x2 e" 0
Gliwice
26
Metoda podziału i ograniczeń
Rozwiązanie Zadania 4
x1 = 4.66667, x2 = 3, Z x1, x2 = 43
()
Rozwiązanie Zadania 5
Zadanie jest sprzeczne
Gliwice
27
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Czy spełnione
Numery zadań, na
Nr Wartość
które zadanie zostało
są warunki
zadania FC
podzielone
całkowitoliczbowości
Gliwice
28
Metoda podziału i ograniczeń
Porządkowanie listy zadań:
Z listy usuwamy:
Na liście pozostaje:
Gliwice
29
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Czy spełnione
Numery zadań, na
Nr Wartość
które zadanie zostało
są warunki
zadania FC
podzielone
całkowitoliczbowości
Gliwice
30
Metoda podziału i ograniczeń
Rozwiązanie Zadania 4
x1 = 4.66667 x2 = 3
Ponieważ zmienna x1 nie spełnia warunków
całkowitoliczbowości, dokonujemy podziału ze względu
na tą zmienną.
x1 = 4.66667
Gliwice
31
Metoda podziału i ograniczeń
Na podstawie otrzymanych przedziałów budujemy dwa zadania:
Zadanie 6 Zadanie 7
Z x1, x2 = 6x1 + 5x2 MAX Z x1, x2 = 6x1 + 5x2 MAX
() ()
9x1 + 7x2 d" 63 9x1 + 7x2 d" 63
1 1
x1 + x2 d" 8 x1 + x2 d" 8
2 2
3x1 + 2x2 e" 6 3x1 + 2x2 e" 6
3 3
x1 e" 4 x1 e" 4
4 4
x2 d" 3 x2 d" 3
5 5
x1 d" 4 x1 e" 5
6 6
x1 e" 0, x2 e" 0 x1 e" 0, x2 e" 0
Gliwice
32
Metoda podziału i ograniczeń
Rozwiązanie Zadania 6
x1 = 4, x2 = 3, Z x1, x2 = 39
( )
Rozwiązanie Zadania 7
x1 = 5, x2 = 2.57143, Z x1, x2 = 42.85714
( )
Gliwice
33
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Czy spełnione
Numery zadań, na
Nr Wartość
które zadanie zostało
są warunki
zadania FC
podzielone
całkowitoliczbowości
Gliwice
34
Metoda podziału i ograniczeń
Porządkowanie listy zadań:
Z listy usuwamy:
Gliwice
35
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Czy spełnione
Numery zadań, na
Nr Wartość
które zadanie zostało
są warunki
zadania FC
podzielone
całkowitoliczbowości
x1 = 3, x2 = 5, Z x1, x2 = 43
( )
Na liście pozostało tylko jedno zadanie.
Ponieważ spełnia ono wszystkie warunki
całkowitoliczbowości, to jego rozwiązanie jest rozwiązaniem
optymalnym zadania pierwotnego.
Gliwice
36
Kiedy zadanie
należy usunąć z listy?
Gliwice
37
Kiedy zadanie należy usunąć z listy?
W przypadku problemu na MAX, zadanie usuwamy z listy gdy:



Gliwice
38
Kiedy zadanie należy usunąć z listy?
W przypadku problemu na MIN, zadanie usuwamy z listy gdy:



Gliwice
39
Kiedy zadanie
należy podzielić?
Gliwice
40
Kiedy zadanie należy usunąć z listy?
W przypadku problemu na MAX, zadanie zostaje podzielone gdy:

Gliwice
41
Dlaczego nie można rozwiązać
zadania bez warunków
całkowitoliczbowości, a póz
niej
zaokrąglić wyników?
Gliwice
42