BADANIA OPERACYJNE
Badania operacyjne
„Badania operacyjne są sztuką dawania złych odpowiedzi na
„Badania operacyjne są sztuką dawania złych odpowiedzi na
te praktyczne pytania, na które inne metody dają odpowiedzi
jeszcze gorsze.”
T. Sayty
2
Standardowe zadanie
Standardowe zadanie
programowania liniowego
Standardowe zadanie programowania liniowego
Rozważamy proces, w którym zmiennymi są
x
1
, x
2
, ..., x
n
.
Proces poddany jest
m
ograniczeniom, zapisanymi w postaci:
p
y j
g
,
p
y
p
11 1
12
2
1
1
21 1
22
2
2
2
...
...
n
n
n
n
a x
a x
a x
b
a x
a x
a x
b
+
+ +
=
+
+ +
=
(1)
1 1
2
2
...
...
m
m
mn
n
m
a x
a x
a x
b
+
+ +
=
(1)
1 1
2
2
m
m
mn
n
m
a
ij
, b
i
– znane współczynniki
4
Standardowe zadanie programowania liniowego
Dopuszczamy jedynie nieujemne wartości
x
j
, czyli:
0
1 2
x
j
n
≥
=
(2)
0,
1, 2,...,
j
x
j
n
≥
=
Zakładamy również, że:
(2)
y
,
0,
1, 2,...,
i
b
i
m
≥
=
(3)
Z procesem jest związana funkcja
Z
:
1 1
2
2
...
n
n
Z
c x
c x
c x
=
+
+ +
(4)
c
j
, j = 1, 2, ...,n
– znane współczynniki
5
Standardowe zadanie programowania liniowego
Zagadnienie polega na maksymalizacji (minimalizacji) funkcji
Z
(wzór
(4)
) spełniającej ograniczenia
(1), (2), (3)
.
Z
(wzór
(4)
) spełniającej ograniczenia
(1), (2), (3)
.
Zapis:
1
FC :
MAX
n
j
j
j
Z
c x
=
=
→
∑
1
m
ij
j
i
j
a x
b
=
⎧
=
⎪
⎪
∑
(5)
1
O :
0,
1, 2,...,
j
j
x
j
n
=
⎪
⎪⎪
≥
=
⎨
⎪
(5)
0,
1, 2,...,
i
b
i
m
⎪
⎪
≥
=
⎪
⎪⎩
6
⎪⎩
Standardowe zadanie programowania liniowego
Zapis w postaci macierzowej:
T
FC
MAX
Z
(6)
T
FC :
MAX
Z
=
→
c x
=
⎧
⎪
Ax b
O :
0
0
⎪ ≥
⎨
⎪ ≥
⎩
x
b
⎩
11
12
1n
a
a
a
⎡
⎤
⎢
⎥
…
1
c
⎡ ⎤
⎢ ⎥
1
x
⎡ ⎤
⎢ ⎥
1
b
⎡ ⎤
⎢ ⎥
21
22
2n
a
a
a
⎢
⎥
⎢
⎥
=
⎢
⎥
⎢
⎥
A
…
…
…
…
2
c
⎢ ⎥
⎢ ⎥
=
⎢ ⎥
⎢ ⎥
c
2
x
⎢ ⎥
⎢ ⎥
=
⎢ ⎥
⎢ ⎥
x
2
b
⎢ ⎥
⎢ ⎥
=
⎢ ⎥
⎢ ⎥
b
1
2
m
m
mn
a
a
a
⎢
⎥
⎣
⎦
…
n
c
⎢ ⎥
⎣ ⎦
n
x
⎢ ⎥
⎣ ⎦
m
b
⎢ ⎥
⎣ ⎦
7
Standardowe zadanie programowania liniowego
* B d
h
d i i h
kt
h d i
* Bardzo powszechną w zagadnieniach praktycznych odmianą
ograniczeń są ograniczenia w postaci nierówności.
To też są zagadnienia programowania liniowego ale
To też są zagadnienia programowania liniowego ale
nie w postaci standardowej.
8
Standardowe zadanie programowania liniowego
Przykład 1.
Zakład zamierza rozpocząć produkcję wyrobów
W
1
i
W
2
. Wśród
a ad a e a o poc ąć p odu cję y obó
W
1
W
2
ś ód
środków produkcyjnych, które zostaną użyte w produkcji dwa są
limitowane. Limity te wynoszą: dla środka
S
1
63
jednostki, a dla
ś dk
d
k
b
d k
ć d
k
b
środka
S
2
64
jednostki. Aby wyprodukować jednostkę wyrobu
W
1
potrzeba
9
jednostek środka
S
1
i
8
jednostek środka
S
2
. Aby
wyprodukować jednostkę wyrobu
W
potrzeba
7
jednostek
S
i
8
wyprodukować jednostkę wyrobu
W
2
potrzeba
7
jednostek
S
1
i
8
jednostek
S
2
. Wyroby
W
1
i
W
2
są niezbędne do produkcji
urządzenia
U
. Jedno urządzenie
U
wymaga
3
jednostek wyrobu
ą
ą
y
g
j
y
W
1
i
2
jednostek wyrobu
W
2
. Produkcja będzie opłacalna, jeżeli
zakład sprzeda wyroby
W
1
i
W
2
potrzebne do wytworzenia co
j
i j
6
j d
t k
d
i
U
najmniej
6
jednostek urządzenia
U
.
Wiedząc, że cena wyrobu
W
1
będzie wynosić
6
, a cena wyrobu
W
5
określ wielkość produkcji maksymalizującej zysk ze
9
W
2
5
określ wielkość produkcji maksymalizującej zysk ze
sprzedaży.
Standardowe zadanie programowania liniowego
W
1
W
2
S
63
9
7
c
S
1
S
63
64
9
8
7
8
c
d
S
2
64
8
8
U
3
2
6
d
e
U
3
2
6
cena
6
5
e
cena
6
5
10
Standardowe zadanie programowania liniowego
Zmienne decyzyjne:
lk ść
d k
b
x
1
– wielkość produkcji wyrobu
W
1
x
2
– wielkość produkcji wyrobu
W
2
11
Standardowe zadanie programowania liniowego
Funkcja celu:
(
)
6
5
MAX
Z x x
x
x
=
+
→
Ograniczenia:
1
2
1
2
( ,
)
6
5
MAX
Z x x
x
x
=
+
→
Ograniczenia:
c
1
2
9
7
63
x
x
+
≤
d
8
8
64
x
x
+
≤
d
1
2
8
8
64
x
x
+
≤
e
1
2
3
2
6
x
x
+
≥
Warunki brzegowe:
1
2
0,
0
x
x
≥
≥
12
Standardowe zadanie programowania liniowego
Zadanie programowania liniowego:
FC:
1
2
1
2
( ,
)
6
5
MAX
Z x x
x
x
=
+
→
O
O:
c
1
2
9
7
63
x
x
+
≤
d
1
2
8
x
x
+
≤
e
3
2
6
x
x
+
≥
e
1
2
3
2
6
x
x
+
≥
WB:
1
2
0,
0
x
x
≥
≥
* Ograniczenia w postaci nierówności.
To nie jest standardowe zadanie programowania liniowego
To nie jest standardowe zadanie programowania liniowego
13
METODA
METODA
GEOMETRYCZNA
GEOMETRYCZNA
Metoda geometryczna
Zadanie programowania liniowego z dwoma zmiennymi
decyzyjnymi
można
rozwiązać
metodą
geometryczną
decyzyjnymi
można
rozwiązać
metodą
geometryczną
(szczegóły na laboratorium).
Na podstawie tej metody otrzymujemy zbiór punktów, a
następnie sprawdzamy w którym z nich wartość funkcji celu
następnie sprawdzamy, w którym z nich wartość funkcji celu
jest największa (lub najmniejsza).
15
Metoda geometryczna
Rozwiązanie dla zadania z Przykładu 1.:
A(2, 0)
B(7, 0)
(2, 0)
6 2 5 0 12
Z
= ⋅ + ⋅ =
(7, 0)
6 7 5 0
42
Z
= ⋅ + ⋅ =
C(3.5, 4.5)
(3.5, 4.5)
6 3.5 5 4.5
43.5
Z
= ⋅
+ ⋅
=
MAX
D(0,8)
E(0,3)
(0,8)
6 0 5 8
40
Z
= ⋅ + ⋅ =
(0, 3)
6 0 5 3 15
Z
= ⋅ + ⋅ =
E(0,3)
(0, 3)
6 0 5 3 15
Z
+
Odpowiedź:
Aby zysk był maksymalny, należy wyprodukować
3.5
jednostki
W
1
oraz
4.5
jednostki
W
2
.
16
ZADANIE DUALNE
Zadanie dualne
Przykład 2.
Zakład produkuje cztery wyroby
W
1
,
W
2
,
W
3
i
W
4
. Wśród
Zakład produkuje cztery wyroby
W
1
,
W
2
,
W
3
i
W
4
. Wśród
środków produkcyjnych, używanych w procesie wytwarzania
wyrobów dwa są limitowane. Limity te, oraz ilości środków
b
d
i
ól
h
bó
ł
potrzebne do wytworzenia poszczególnych wyrobów zostały
przedstawione w tabeli.
Znając jednostkowe ceny wyrobów, określić taki plan
Znając jednostkowe ceny wyrobów, określić taki plan
produkcji aby zysk był maksymalny.
18
Zadanie dualne
W
1
W
2
W
3
W
4
S
1
1
3
1
1
600
S
2
4
1
1
5
1200
cena
8
9
6
10
Zmienne decyzyjne:
x
i
– wielkość produkcji wyrobu
W
i
i = 1...4
19
Zadanie dualne
Model matematyczny:
FC:
(
)
8
9
6
10
MAX
Z x x x x
x
x
x
x
=
+
+
+
→
O:
1
2
3
4
1
2
3
4
( ,
,
,
)
8
9
6
10
MAX
Z x x x x
x
x
x
x
=
+
+
+
→
3
600
1
2
3
4
3
600
x
x
x
x
+
+ +
≤
1
2
3
4
4
5
1200
x
x
x
x
+ + +
≤
WB:
0
0
0
0
x
x
x
x
≥
≥
≥
≥
1
2
3
4
0,
0,
0,
0
x
x
x
x
≥
≥
≥
≥
20
Zadanie dualne
Zadanie pierwotne:
FC
T
FC:
O:
T
MAX
Z
=
→
c x
≤
Ax b
WB:
0
≥
x
Zadanie dualne:
FC:
O:
T
MIN
Z
=
→
b y
T
≥
A y c
O:
WB:
≥
A y c
0
≥
y
21
Zadanie dualne
Model matematyczny zadania dualnego:
FC:
FC:
O
1
2
1
2
( ,
)
600
1200
MIN
Z y y
y
y
=
+
→
O:
1
2
4
8
y
y
+
≥
1
2
3
9
y
y
+
≥
1
2
y
y
1
2
6
y
y
+
≥
1
2
5
10
y
y
+
≥
WB:
0
0
y
y
≥
≥
1
2
y
y
1
2
0,
0
y
y
≥
≥
22
Zadanie dualne
Interpretacja zadania dualnego
Konkurent postanawia wykupić zapasy środków produkcji od
producenta, i chce zminimalizować koszty materiałów (ma
kupić
600
jednostek
S
i
1200
jednostek
S
)
kupić
600
jednostek
S
1
i
1200
jednostek
S
2
).
Zmienne decyzyjne w zadaniu dualnym:
y
1
– cena jednostki środka produkcji
S
1
y
2
– cena jednostki środka produkcji
S
2
y
2
j
p
j
S
2
(
)
600
1200
MIN
Z
+
→
1
2
1
2
( ,
)
600
1200
MIN
Z y y
y
y
=
+
→
23
Zadanie dualne
Interpretacja zadania dualnego c. d.
Wyprodukowanie wyrobów wiąże się z kosztem środków
S
1
i
S
2
. Konkurent, aby zachęcić producenta do sprzedaży
materiałów musi mu zapłacić co najmniej tyle ile producent
materiałów musi mu zapłacić co najmniej tyle, ile producent
uzyskałby ze sprzedaży wyrobów, które produkuje.
1
2
4
8
y
y
+
≥
1
2
3
9
y
y
+
≥
1
2
6
y
y
+
≥
5
10
+
≥
1
2
5
10
y
y
+
≥
24
Zadanie dualne
Twierdzenie o dualności
Zadanie pierwotne ma rozwiązanie wtedy i tylko wtedy, gdy
zadanie dualne ma rozwiązanie, oraz:
(MAX)
(MIN)
Z
Z
=
wnioski:
1. Rozwiązując jedno z zadań, automatycznie
rozwiązujemy też drugie.
2. Twierdzenie
ma
duże znaczenie praktyczne,
p
y
,
ponieważ czasami łatwiej jest rozwiązać
zadanie dualne (mniej zmiennych).
25
Zadanie dualne
Na podstawie metody geometrycznej:
A(0,9)
(A)
10800
Z
=
B(3 / 2,9 / 2)
(B)
6300
Z
=
C(5,1)
D(10 0)
(C)
4200
Z
=
(D)
6000
Z
MIN
D(10, 0)
(D)
6000
Z
=
Aby koszt materiałów był najmniejszy i wynosił
4200
, konkurent
musi zapłacić za jednostkę
S
1
5
, a za jednostkę
S
2
1
.
26
Zadanie dualne
Na podstawie twierdzenia o dualności:
M k i
FC
d i
i
t
j t ó
i i
FC
Maksimum FC zadania pierwotnego jest równe minimum FC
zadania dualnego.
Zysk producenta wyniesie również
4200
y
p
y
Jakie jest rozwiązanie zadania pierwotnego?
Twierdzenie o równowadze.
27
Zadanie dualne
Twierdzenie o równowadze
Jeżeli
i
–ty warunek zadania pierwotnego (ZP) jest (chociaż w
jednym) optymalnym rozwiązaniu spełniony z nierównością
( t ) t
d
i d j
i
t
i
(d
l
)
(ostro), to odpowiadająca mu
i
–ta zmienna
y
i
w (dowolnym)
optymalnym rozwiązaniu zadania dualnego (ZD) przyjmuje
wartość zero.
a ość e o
Dla
zmiennej
x
i
>0
w
rozwiązaniu
optymalnym
ZP
odpowiadające jej
i
–te ograniczenie w ZD jest ograniczeniem
ó
ś
równościowym.
Twierdzenie jest również słuszne w przeciwną stronę.
28
Zadanie dualne
Rozwiązanie przykładu:
1
2
5
1
y
y
=
=
1
2
y
y
Sprawdzenie ograniczeń ZD:
1: 5 4 1 8
j
=
+ ⋅ >
2 : 3 5 1 9
j
=
⋅ + >
3
5 1
6
3 : 5 1
6
j
=
+ =
4 : 5 5 1 10
j
=
+ ⋅ =
Nierówności ostre dla
j = 1
i
j = 2
:
Dla rozwiązania optymalnego ZP
x
1
= 0
i
x
2
= 0
29
Zadanie dualne
Ponieważ:
1
2
5
0
1
0
y
y
= >
= >
O
i
i 1 i 2
ZP
i
i
i ó
ś i
i
Ograniczenia 1 i 2 w ZP są ograniczeniami równościowymi
(przy czym
x
1
= 0
,
x
2
= 0
):
3
4
3
4
600
5
1200
x
x
x
x
+
=
+
=
3
4
450
150
x
x
=
=
30
Zadanie dualne
Odpowiedź do zadania pierwotnego:
Aby zysk był maksymalny producent musi wyprodukować
450
Aby zysk był maksymalny, producent musi wyprodukować
450
jednostek
W
3
i
150
jednostek
W
4
. Zysk wyniesie
4200
.
31
Szczegółowe zasady
formułowania zadania dualnego
formułowania zadania dualnego
Szczegółowe zasady formułowania zadania dualnego
Zadanie pierwotne
Zadanie dualne
maksymalizacja
minimalizacja
maksymalizacja
minimalizacja
33
Szczegółowe zasady formułowania zadania dualnego
Zadanie pierwotne
Zadanie dualne
Ograniczenia
Zmienne
i
- te:
≥
0
y
≤
i
te:
≥
0
i
y
≤
≤
0
i
y
≥
i
- te:
=
dowolne
i
y
i
- te:
34
Szczegółowe zasady formułowania zadania dualnego
Zadanie pierwotne
Zadanie dualne
Zmienne
Ograniczenia
j
- te:
≥
0
x
≥
j
te:
≥
0
j
x
≥
≤
0
j
x
≤
=
dowolne
j
x
j
- te:
j
- te:
j
j
35
Szczegółowe zasady formułowania zadania dualnego
Przykład 3.
Dla podanego zadania pierwotnego zapisać zadanie dualne.
p
g
p
g
p
1
2
3
4
FC :
( )
2
3
MAX
Z
x
x
x
x
=
+
+ +
→
x
1
2
3
4
O :
2
3
20
2
3
50
x
x
x
x
+
−
+
=
+
+
≤
1
2
3
4
1
2
3
4
2
3
50
3
2
40
x
x
x
x
x
x
x
x
+
+
−
≤
− + +
≥
1
2
3
4
WB :
0
0
0
dowolne
x
x
x
x
≥
≥
≤
36
Szczegółowe zasady formułowania zadania dualnego
Zadanie dualne:
1
2
3
FC :
( )
20
50
40
MIN
Z
y
y
y
=
+
+
→
y
O :
1
2
3
2
3
2
y
y
y
+
+
≥
2
3
y
y
y
+
−
≥
1
2
3
2
3
y
y
y
+
≥
1
2
3
3
3
1
y
y
y
−
+
+
≤
2
1
y
y
y
+
1
2
3
2
1
y
y
y
−
+
=
WB :
1
dowolne
y
2
0
y
≥
3
0
y
≤
WB :
1
y
2
y
3
y
37
Na dzisiaj wystarczy
Na dzisiaj wystarczy...
38
Sprowadzenie modelu
do postaci bazowej
2
Sprowadzenie modelu do postaci bazowej
Przykład 4.
Model matematyczny z Przykładu 1. sprowadzić do postaci
bazowej.
3
Sprowadzenie modelu do postaci bazowej
1
2
9
7
63
x
x
+
≤
Ograniczenie
Aby otrzymać ograniczenie w postaci równania
wprowadzamy dodatkową zmienną do ograniczenia:
1
2
3
9
7
63
x
x
x
+
+ =
x
3
– zmienna bilansująca
Zmienna
x
3
określa ilość środka
S
1
jaki nie zostanie
wykorzystany w procesie produkcyjnym
4
Sprowadzenie modelu do postaci bazowej
1
2
3
9
7
63
x
x
x
+
+ =
3
1
2
63 9
7
x
x
x
=
−
−
Gdyby przyjąć:
x
1
=0
i
x
2
=0
:
3
63
0
x
=
≥
Zmienna
x
3
spełnia postulat nieujemności.
5
Sprowadzenie modelu do postaci bazowej
Ograniczenie
Aby otrzymać ograniczenie w postaci równania
wprowadzamy dodatkową zmienną do ograniczenia
(analogicznie jak dla pierwszego ograniczenia):
x
4
– zmienna bilansująca
Zmienna
x
4
określa ilość środka
S
2
jaki nie zostanie
wykorzystany w procesie produkcyjnym
1
2
8
x
x
+ ≤
1
2
4
8
x
x
x
+ + =
Dla
x
1
=0
i
x
2
=0
:
4
8
0
x
= ≥
6
Sprowadzenie modelu do postaci bazowej
Ograniczenie
Aby otrzymać ograniczenie w postaci równania
wprowadzamy dodatkową zmienną do ograniczenia:
x
5
– zmienna bilansująca
1
2
3
2
6
x
x
+
≥
1
2
5
3
2
6
x
x
x
+
− =
Dla
x
1
=0
i
x
2
=0
:
5
6
0
x
= − <
7
Sprowadzenie modelu do postaci bazowej
W postaci bazowej, w każdym ograniczeniu musi
znajdować się jedna zmienna, która po wyzerowaniu
wszystkich pozostałych zmiennych w ograniczeniu jest
nieujemna.
Wprowadzamy kolejną zmienną:
1
2
5
6
3
2
6
x
x
x
x
+
− + =
Dla
x
1
=0
,
x
2
=0
oraz
x
5
=0
:
6
6
0
x
= ≥
x
6
– zmienna sztuczna
8
Sprowadzenie modelu do postaci bazowej
Rozwiązanie zadania po wprowadzeniu zmiennej sztucznej
nie
jest
równoważne
z
rozwiązaniem
zadania
początkowego.
Byłoby równoważne tylko wtedy, gdyby w rozwiązaniu
optymalnym zmienna sztuczna miała wartość zero.
9
Sprowadzenie modelu do postaci bazowej
Aby zapewnić
x
6
=0
w rozwiązaniu optymalnym, każdą
zmienną sztuczną wprowadza się do funkcji celu.
Współczynnik przy zmiennej sztucznej w funkcji celu
dobiera się tak, aby niezerowa wartość tej zmiennej mocno
pogarszała wartość funkcji celu.
1
2
6
1
2
6
( ,
,
)
6
5
MAX
Z x x x
x
x
Mx
=
+
+
→
1000
M
= −
10
Sprowadzenie modelu do postaci bazowej
Czy zmienne bilansujące należy uwzględnić w funkcji celu?
Tak.
Z jakimi współczynnikami?
Wszystkie współczynniki przy zmiennych bilansujących w
funkcji celu są równe zero.
1
2
3
4
5
6
1
2
3
4
5
6
( ,
,
,
,
,
)
6
5
0
0
0
1000
MAX
Z x x x x x x
x
x
x
x
x
x
=
+
+
+
+
−
→
11
Sprowadzenie modelu do postaci bazowej
Postać bazowa zadania z Przykładu 1:
FC:
O:
WB:
1
2
3
1
2
4
1
2
5
6
9
7
63
8
3
2
6
x
x
x
x
x
x
x
x
x
x
+
+
=
+
+
=
+
− + =
1
2
3
4
5
6
0,
0,
0,
0,
0,
0
x
x
x
x
x
x
≥
≥
≥
≥
≥
≥
1
2
3
4
5
6
1
2
3
4
5
6
( ,
,
,
,
,
)
6
5
0
0
0
1000
MAX
Z x x x x x x
x
x
x
x
x
x
=
+
+
+
+
−
→
12
Sprowadzenie modelu do postaci bazowej
Sprowadzenie do postaci bazowej ograniczenia typu:
1
2
3
5
4
x
x
+
=
Wprowadzamy zmienną sztuczną:
1
2
3
3
5
4
x
x
x
+
+ =
Należy ją uwzględnić w funkcji celu w podany poprzednio
sposób, czyli tak, aby jej niezerowa wartość mocno
pogarszała wartość funkcji celu.
13
Sprowadzenie modelu do postaci bazowej
Postać bazowa:
Wszystkie ograniczenia w postaci równań
W każdym ograniczeniu znajduje się zmienna, która po
wyzerowaniu pozostałych zmiennych ma wartość
nieujemną
Współczynnik przy tej zmiennej ma wartość 1
Wprowadzone zmienne bilansujące wprowadza się do
funkcji celu z zerowymi współczynnikami
Wprowadzone zmienne sztuczne uwzględnia się w
funkcji celu ze współczynnikami mocno pogarszającymi
jej wartość
METODA SIMPLEX
15
Metoda simplex
Przykład 5.
Rozwiązać zadanie z Przykładu 1. metodą simplex.
16
Metoda simplex
Tablica simplex:
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
17
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
1
0 9 0 1 ( 1000) 3
z
= ⋅ + ⋅ + −
⋅
3000
= −
-3000
18
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
2
0 7
0 1 ( 1000) 2
z
= ⋅ + ⋅ + −
⋅
2000
= −
-3000 -2000
19
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
3
0 1 0 0 ( 1000) 0
z
= ⋅ + ⋅ + −
⋅
0
=
-3000 -2000
0
20
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
4
0 0 0 1 ( 1000) 0
z
= ⋅ + ⋅ + −
⋅
0
=
-3000 -2000
0
0
21
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
5
0 0 0 0 ( 1000) ( 1)
z
= ⋅ + ⋅ + −
⋅ −
1000
=
-3000 -2000
0
0
1000
22
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
6
0 0 0 0 ( 1000) 1
z
= ⋅ + ⋅ + −
⋅
1000
= −
-3000 -2000
0
0
1000 -1000
23
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
1
1
6 ( 3000)
c
z
− = − −
3006
=
-3000 -2000
0
0
1000 -1000
c
j
- z
j
3006
24
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
2
2
5 ( 2000)
c
z
− = − −
2005
=
-3000 -2000
0
0
1000 -1000
c
j
- z
j
3006
2005
25
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
3
3
0 0
c
z
− = −
0
=
-3000 -2000
0
0
1000 -1000
c
j
- z
j
3006
2005
0
26
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
4
4
0 0
c
z
− = −
0
=
-3000 -2000
0
0
1000 -1000
c
j
- z
j
3006
2005
0
0
27
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
5
5
0 1000
c
z
− = −
1000
= −
-3000 -2000
0
0
1000 -1000
c
j
- z
j
3006
2005
0
0
-1000
28
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
6
6
1000 ( 1000)
c
z
− = −
− −
0
=
-3000 -2000
0
0
1000 -1000
c
j
- z
j
3006
2005
0
0
-1000
0
29
Metoda simplex
j
j
c
z
−
- wskaźniki optymalności
Dla zmiennych bazowych wskaźniki optymalności zawsze
są równe 0.
30
Metoda simplex
Kryterium optymalności:
Rozwiązanie jest optymalne, jeżeli wartości wszystkich
wskaźników optymalności są niedodatnie.
Rozwiązanie w bazie
[x
3
, x
4
, x
6
]
nie jest rozwiązaniem optymalnym.
Należy przejść do następnej bazy
31
Metoda simplex
Kryterium wejścia do bazy:
Do bazy wchodzi zmienna, która ma największą wartość
wskaźnika optymalności.
Jeżeli
największa
wartość
wskaźnika
optymalności
odpowiada więcej niż jednaj zmiennej, wybieramy zmienną
o najniższym indeksie.
W przykładzie kryterium wejścia spełnia zmienna
x
1
.
32
Metoda simplex
Kryterium wyjścia z bazy:
Obliczamy ilorazy wyrazów wolnych (kolumna
b
i
) przez
elementy (tylko dodatnie) kolumny zmiennej wchodzącej do
bazy.
Bazę opuszcza ta zmienna, dla której obliczony iloraz jest
najmniejszy.
Jeżeli najmniejsza wartość ilorazu występuje dla więcej niż
jednej zmiennej, to jako zmienną opuszczającą bazę
można wybrać dowolną z nich.
33
Metoda simplex
3
: 63 / 9
7
x
=
4
: 8 /1 8
x
=
6
: 6 / 3
2
x
=
W przykładzie kryterium wyjścia spełnia zmienna
x
6
.
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
9
7
1
0
0
0
1
1
0
1
0
0
3
2
0
0
-1
1
63
8
6
b
i
x(B)
x
3
x
4
x
6
c(B)
0
0
-1000
z
j
-3000 -2000
0
0
1000 -1000
c
j
- z
j
3006
2005
0
0
-1000
0
34
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
0
1
1
0
3
-3
0
1/3
0
1
1/3
-1/3
1
2/3
0
0
-1/3
1/3
45
6
2
b
i
x(B)
x
3
x
4
x
1
c(B)
0
0
6
z
j
6
4
0
0
-2
2
c
j
- z
j
0
1
0
0
2
-1002
Rozwiązanie w bazie
[x
3
, x
4
, x
1
]
nie jest rozwiązaniem optymalnym.
35
Metoda simplex
Do bazy wchodzi zmienna:
x
5
Ilorazy:
3
: 45 / 3 15
x
=
4
: 6 /(1/ 3) 18
x
=
1
:
x
−
ujemny współczynnik – nie liczymy ilorazu
Z bazy wychodzi zmienna:
x
3
36
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
0
1/3
1/3
0
1
-1
0
2/9
-1/9
1
0
0
1
7/9
1/9
0
0
0
15
1
7
b
i
x(B)
x
5
x
4
x
1
c(B)
0
0
6
z
j
6
14/3
2/3
0
0
0
c
j
- z
j
0
1/3
-2/3
0
0
-1000
Rozwiązanie w bazie
[x
5
, x
4
, x
1
]
nie jest rozwiązaniem optymalnym.
37
Metoda simplex
Do bazy wchodzi zmienna:
x
2
Ilorazy:
5
: 15 /(1/ 3)
45
x
=
4
: 1/(2 / 9)
4.5
x
=
1
: 7 /(7 / 9)
9
x
=
Z bazy wychodzi zmienna:
x
4
38
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
0
0
1/2
-3/2
1
-1
0
1
-1/2
9/2
0
0
1
0
1/2
-7/2
0
0
27/2
9/2
7/2
b
i
x(B)
x
5
x
2
x
1
c(B)
0
5
6
z
j
6
5
1/2
3/2
0
0
c
j
- z
j
0
0
-1/2
-3/2
0
-1000
Rozwiązanie w bazie
[x
5
, x
2
, x
1
]
jest rozwiązaniem optymalnym.
39
Metoda simplex
c
T
x
→
MAX
6
5
0
0
0
-1000
x
1
x
2
x
3
x
4
x
5
x
6
0
0
1/2
-3/2
1
-1
0
1
-1/2
9/2
0
0
1
0
1/2
-7/2
0
0
27/2
9/2
7/2
b
i
x(B)
x
5
x
2
x
1
c(B)
0
5
6
z
j
6
5
1/2
3/2
0
0
c
j
- z
j
0
0
-1/2
-3/2
0
-1000
5
27 / 2
x
=
2
9 / 2
x
=
1
7 / 2
x
=
Zmienne bazowe:
Zmienne niebazowe:
3
0
x
=
4
0
x
=
6
0
x
=
40
Metoda simplex
Rozwiązanie:
1
2
3
4
5
6
3.5
4.5
0
0
13.5
0
x
x
x
x
x
x
=
=
=
=
=
=
Funkcja celu:
1
2
3
4
5
6
( ,
,
,
,
,
)
43.5
Z x x x x x x
=
Różnice w algorytmie
metody simplex na
MAX i MIN
42
Różnice w algorytmie metody simplex na MAX i MIN
Kryterium wejścia
MAX:
Zmienna z największą wartością wskaźnika optymalności
MIN:
Zmienna z najmniejszą wartością wskaźnika optymalności
43
Różnice w algorytmie metody simplex na MAX i MIN
Kryterium wyjścia
MAX:
Zmienna, dla której iloraz elementu z wektora wyrazów wolnych
przez współczynnik z kolumny zmiennej wchodzącej do bazy
ma najmniejszą wartość.
MIN:
Identycznie jak w zadaniu na MAX.
44
Różnice w algorytmie metody simplex na MAX i MIN
Rozwiązanie optymalne
MAX:
Wszystkie wskaźniki optymalności muszą być niedodatnie
MIN:
Wszystkie wskaźniki optymalności muszą być nieujemne.
Postępowanie, gdy zmienne
nie spełniają warunków
nieujemności
46
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
1
2
3
FC :
( )
3
6
4
MAX
Z
x
x
x
=
+
−
→
x
1
2
3
1
2
3
1
2
3
O : 3
5
2
6
2
3
7
12
4
6
3
5
x
x
x
x
x
x
x
x
x
−
−
≥ −
−
+
≥
+
−
=
1
2
3
WB :
0
0
x
x
R
x
≥
∈
≤
47
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
*
**
*
**
2
2
2
2
2
,
0,
0
x
x
x
x
x
= −
≥
≥
Zmienną x
2
zastępujemy różnicą dwóch zmiennych
nieujemnych:
x
2
∈
R
48
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
*
**
*
**
3
3
3
3
3
,
0,
0
x
x
x
x
x
= −
≥
≥
Zmienną x
3
zastępujemy różnicą dwóch zmiennych
nieujemnych:
x
3
≤
0
49
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
*
**
*
**
*
**
*
**
1
2
2
3
3
1
2
2
3
3
FC :
( ,
,
,
,
)
3
6(
) 4(
)
MAX
Z x x x
x x
x
x
x
x
x
=
+
−
−
−
→
*
**
*
**
1
2
2
3
3
*
**
*
**
1
2
2
3
3
*
**
*
**
1
2
2
3
3
O : 3
5(
) 2(
)
6
2
3(
) 7(
) 12
4
6(
) 3(
)
5
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
−
−
−
−
≥ −
−
−
+
−
≥
+
−
−
−
=
*
**
*
**
1
2
2
3
3
WB :
0
0
0
0
0
x
x
x
x
x
≥
≥
≥
≥
≥
50
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
1
2
3
4
5
1
2
3
4
5
ˆ ˆ ˆ ˆ ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
FC :
( ,
,
,
,
)
3
6
6
4
4
MAX
Z x x x x x
x
x
x
x
x
=
+
−
−
+
→
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
ˆ
ˆ
ˆ
ˆ
ˆ
O :
3
5
5
2
2
6
ˆ
ˆ
ˆ
ˆ
ˆ
2
3
3
7
7
12
ˆ
ˆ
ˆ
ˆ
ˆ
4
6
6
3
3
5
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
−
+
−
+
≥ −
−
+
+
−
≥
+
−
−
+
=
ˆ
WB :
0,
1, 2,3, 4,5
j
x
j
≥
=
Zmieniamy numery zmiennych:
51
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
1
2
3
4
5
1
2
3
4
5
ˆ ˆ ˆ ˆ ˆ
ˆ
ˆ
ˆ
ˆ
ˆ
FC :
( ,
,
,
,
)
3
6
6
4
4
MAX
Z x x x x x
x
x
x
x
x
=
+
−
−
+
→
1
2
3
4
5
1
2
3
4
5
1
2
3
4
5
ˆ
ˆ
ˆ
ˆ
ˆ
O :
3
5
5
2
2
6
ˆ
ˆ
ˆ
ˆ
ˆ
2
3
3
7
7
12
ˆ
ˆ
ˆ
ˆ
ˆ
4
6
6
3
3
5
x
x
x
x
x
x
x
x
x
x
x
x
x
x
x
−
+
−
+
−
≤
−
+
+
−
≥
+
−
−
+
=
ˆ
WB :
0,
1, 2,3, 4,5
j
x
j
≥
=
Ograniczenia, w których wyraz wolny jest wartością ujemną
mnożymy przez -1 (tutaj ograniczenie pierwsze):
52
Postępowanie, gdy zmienne nie spełniają warunków nieujemności
Dalsze postępowanie identyczne jak przy sprowadzaniu do
postaci bazowej.
Szczególne przypadki rozwiązań
54
Szczególne przypadki rozwiązań
Zadanie sprzeczne
1
2
1
2
1
2
1
2
1
2
( ,
)
6
5
MAX
8
3
2
6
,
0
Z x x
x
x
x
x
x
x
x x
=
+
→
+ ≥
+
≤
≥
1
2
3
4
5
1
2
4
1
2
3
4
1
2
5
1
2
3
4
5
( ,
,
,
,
)
6
5
1000
MAX
8
3
2
6
,
,
,
,
0
Z x x x x x
x
x
x
x
x
x
x
x
x
x
x x x x x
=
+
−
→
+ − + =
+
+ =
≥
W postaci bazowej:
55
Szczególne przypadki rozwiązań
56
Szczególne przypadki rozwiązań
Zadanie sprzeczne:
•
Nie ma rozwiązań dopuszczalnych
Objawy w metodzie simplex:
W rozwiązaniu optymalnym, zmienna sztuczna (w tym
przykładzie
x
4
) będzie miała wartość niezerową (czyli będzie
w bazie).
57
Szczególne przypadki rozwiązań
Alternatywne rozwiązania optymalne
1
2
1
2
1
2
1
2
1
2
( ,
)
2
2
MAX
8
3
2
6
,
0
Z x x
x
x
x
x
x
x
x x
=
+
→
+ ≤
+
≥
≥
1
2
3
4
5
1
2
5
1
2
3
1
2
4
5
1
2
3
4
5
( ,
,
,
,
)
2
2
1000
MAX
8
3
2
6
,
,
,
,
0
Z x x x x x
x
x
x
x
x
x
x
x
x
x
x x x x x
=
+
−
→
+ + =
+
− + =
≥
W postaci bazowej:
58
Szczególne przypadki rozwiązań
C(0,8) :
(0,8)
16
D(8, 0) :
(8, 0)
16
Z
Z
=
=
59
Szczególne przypadki rozwiązań
Alternatywne rozwiązania optymalne:
•
Każdy punkt odcinka
CD
jest rozwiązaniem optymalnym
– odpowiada alternatywnemu, optymalnemu rozwiązaniu
Objawy w metodzie simplex:
W rozwiązaniu optymalnym, zerowe wartości wskaźników
optymalności dla zmiennych niebazowych.
•
Może się zdarzyć, że zadanie ma nieskończenie wiele
rozwiązań optymalnych
Rozwiązania optymalne można zidentyfikować przechodząc do
kolejnych baz.
60
Szczególne przypadki rozwiązań
Nieograniczona funkcja celu
1
2
1
2
1
2
1
1
2
( ,
)
2
3
MAX
3
2
6
7
,
0
Z x x
x
x
x
x
x
x x
=
+
→
+
≥
≤
≥
1
2
3
4
5
1
2
4
1
2
3
4
1
5
1
2
3
4
5
( ,
,
,
,
)
2
3
1000
MAX
6
7
,
,
,
,
0
Z x x x x x
x
x
x
x
x
x
x
x
x
x x x x x
=
+
−
→
+ − + =
+ =
≥
W postaci bazowej:
61
Szczególne przypadki rozwiązań
62
Szczególne przypadki rozwiązań
•
Zbiór rozwiązań jest nieograniczony
Objawy w metodzie simplex:
W tablicy simplex kolumna zmiennej wchodzącej do bazy ma
wszystkie elementy niedodatnie.
•
Funkcja celu jest nieograniczona od góry
W tym zadaniu:
63
Szczególne przypadki rozwiązań
Czy funkcja celu może być nieograniczona od dołu?
Nie, ponieważ wymagana jest nieujemność zmiennych
Czy, pomimo tego że zbiór rozwiązań dopuszczalnych jest
nieograniczony może istnieć „dokładne” rozwiązanie optymalne?
Może, gdy zadanie jest zadaniem na MIN.
64
Szczególne przypadki rozwiązań
1
2
1
2
1
2
1
1
2
( ,
)
2
3
MIN
3
2
6
7
,
0
Z x x
x
x
x
x
x
x x
=
+
→
+
≥
≤
≥
A(2, 0) :
(2, 0)
4
B(0, 3) :
(0, 3)
9
C(7, 0) :
(7, 0)
14
Z
Z
Z
=
=
=
MIN
Z poprzedniego rysunku:
65
The Happy End
PROGRAMOWANIE
CAŁKOWITOLICZBOWE
METODA PODZIAŁU
I OGRANICZEŃ
3
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
W
2
musi
być określona liczbą całkowitą.
4
Metoda podziału i ograniczeń
Model matematyczny:
FC:
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
O:
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
WB:
1
2
0,
0
x
x
≥
≥
2
C
x
∈
5
Metoda podziału i ograniczeń
Szukamy rozwiązania nie uwzględniając warunku
całoliczbowości (patrz: metoda geometryczna lub simplex)
Zadanie 1.
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
1
2
0,
0
x
x
≥
≥
Rozwiązanie:
1
2
1
2
3.5
4.5 Z( , ) 43.5
x
x
x x
=
=
=
6
Metoda podziału i ograniczeń
Zadanie umieszczamy na liście zadań:
Numery zadań, na
które zadanie zostało
podzielone
Czy spełnione
są warunki
całkowitoliczbowości
Wartość
FC
Nr
zadania
Nie
1
43.5
7
Metoda podziału i ograniczeń
Zmienna
x
2
nie spełnia nałożonego na nią w zadaniu
głównym warunku
x
2
∈ C
.
Dokonujemy podziału:
Otrzymujemy dwa przedziały:
2
[0,4]
x
∈
2
[5, )
x
∈ ∞
2
5
x
≥
2
4
x
≤
8
Metoda podziału i ograniczeń
Na podstawie otrzymanych przedziałów budujemy dwa zadania:
Zadanie 2.
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
1
2
0,
0
x
x
≥
≥
2
4
x
≤
Zadanie 3.
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
1
2
0,
0
x
x
≥
≥
2
5
x
≥
9
Metoda podziału i ograniczeń
Numery zadań umieszczamy na liście zadań:
Numery zadań, na
które zadanie zostało
podzielone
Czy spełnione
są warunki
całkowitoliczbowości
Wartość
FC
Nr
zadania
Nie
1
43.5
2
3
10
Metoda podziału i ograniczeń
11
Metoda podziału i ograniczeń
Dla
Zadania 2:
Maksimum w punkcie:
35
C(
,4)
9
35
1
Z(
,4) 43
9
3
=
Wartość funkcji celu:
Dla
Zadania 3:
Maksimum w punkcie:
G(3,5)
Z(3,5) 43
=
Wartość funkcji celu:
12
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Numery zadań, na
które zadanie zostało
podzielone
Czy spełnione
są warunki
całkowitoliczbowości
Wartość
FC
Nr
zadania
Nie
1
43.5
2
3
2
1
43
3
Tak
Tak
3
43
13
Metoda podziału i ograniczeń
Porządkowanie listy zadań
Z listy usuwamy:
Zadanie 1.
- bo zostało już podzielone
Zadanie 3.
– spełnione są wszystkie warunki
całkowitoliczbowości, ale ma
mniejszą wartość funkcji celu
niż
Zadanie 2.
14
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Numery zadań, na
które zadanie zostało
podzielone
Czy spełnione
są warunki
całkowitoliczbowości
Wartość
FC
Nr
zadania
2
1
43
3
Tak
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.
15
Metoda podziału i ograniczeń
Przykład 7.
Rozwiązać zadanie z Przykładu 1. metodą podziału i
ograniczeń, przy czym wielkość produkcji obydwóch
wyrobów musi być określona liczbą całkowitą.
16
Metoda podziału i ograniczeń
Model matematyczny:
FC:
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
O:
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
WB:
1
2
0,
0
x
x
≥
≥
1
2
C,
C
x
x
∈
∈
17
Metoda podziału i ograniczeń
Szukamy rozwiązania nie uwzględniając warunku
całkowitoliczbowości
Zadanie 1.
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
1
2
0,
0
x
x
≥
≥
Rozwiązanie:
1
2
1
2
3.5
4.5 Z( , ) 43.5
x
x
x x
=
=
=
18
Metoda podziału i ograniczeń
Zadanie umieszczamy na liście zadań:
Numery zadań, na
które zadanie zostało
podzielone
Czy spełnione
są warunki
całkowitoliczbowości
Wartość
FC
Nr
zadania
Nie
1
43.5
19
Metoda podziału i ograniczeń
Ponieważ obydwie zmienne nie spełniają warunków
całkowitoliczbowości wybieramy, względem której z nich
dokonamy podziału.
Dokonujemy podziału względem
x
1
:
Otrzymujemy dwa przedziały:
1
4
x
≥
1
3
x
≤
20
Metoda podziału i ograniczeń
Na podstawie otrzymanych przedziałów budujemy dwa zadania:
Zadanie 2.
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
1
2
0,
0
x
x
≥
≥
1
3
x
≤
Zadanie 3.
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
1
2
0,
0
x
x
≥
≥
1
4
x
≥
21
Metoda podziału i ograniczeń
Rozwiązanie
Zadania 2:
Rozwiązanie
Zadania 3:
1
2
1
2
3
5 Z( , ) 43
x
x
x x
=
=
=
1
2
1
2
4
3.8 Z( , ) 43.2851
x
x
x x
=
=
=
22
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Numery zadań, na
które zadanie zostało
podzielone
Czy spełnione
są warunki
całkowitoliczbowości
Wartość
FC
Nr
zadania
Nie
1
43.5
2
3
2
Tak
Nie
3
43.2851
43
23
Metoda podziału i ograniczeń
Porządkowanie listy zadań
Z listy usuwamy:
Zadanie 1.
- bo zostało już podzielone
Zadanie 3.
– nie spełnia warunków całkowitoliczbowości,
ale ma większą wartość funkcji celu niż
Zadanie 2.
Na liście pozostaje:
Zadanie 2.
– spełnia wszystkie warunki całkowitoliczbowości
24
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Numery zadań, na
które zadanie zostało
podzielone
Czy spełnione
są warunki
całkowitoliczbowości
Wartość
FC
Nr
zadania
2
Tak
Nie
3
43.2851
43
Zadanie 3.
musi zostać podzielone
25
Metoda podziału i ograniczeń
Rozwiązanie
Zadania 3
:
1
2
4
3.8
x
x
=
=
Ponieważ zmienna
x
2
nie spełnia warunków
całkowitoliczbowości, dokonujemy podziału ze względu na
tą zmienną.
2
3.8
x
=
2
3
x
≤
2
4
x
≥
26
Metoda podziału i ograniczeń
Na podstawie otrzymanych przedziałów budujemy dwa zadania:
Zadanie 4.
Zadanie 5.
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
1
2
0,
0
x
x
≥
≥
1
4
x
≥
2
3
x
≤
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
1
2
0,
0
x
x
≥
≥
1
4
x
≥
2
4
x
≥
27
Metoda podziału i ograniczeń
Rozwiązanie
Zadania 4:
Rozwiązanie
Zadania 5:
1
2
1
2
4.66667
3 Z( , ) 43
x
x
x x
=
=
=
Zadanie jest sprzeczne
28
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Numery zadań, na
które zadanie zostało
podzielone
Czy spełnione
są warunki
całkowitoliczbowości
Wartość
FC
Nr
zadania
2
Tak
Nie
3
43.2851
43
4
5
4
43
Nie
5
Zadanie sprzeczne
29
Metoda podziału i ograniczeń
Porządkowanie listy zadań
Z listy usuwamy:
Zadanie 3.
- bo zostało już podzielone
Zadanie 4.
– nie spełnia warunków całkowitoliczbowości,
ale wartość funkcji celu jest taka sama jak
w
Zadaniu 2.
Na liście pozostaje:
Zadanie 2.
– spełnia wszystkie warunki całkowitoliczbowości
Zadanie 5.
- bo jest sprzeczne
30
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Numery zadań, na
które zadanie zostało
podzielone
Czy spełnione
są warunki
całkowitoliczbowości
Wartość
FC
Nr
zadania
2
Tak
43
4
43
Nie
Zadanie 4.
musi zostać podzielone
31
Metoda podziału i ograniczeń
Rozwiązanie
Zadania 4
:
1
2
4.66667
3
x
x
=
=
Ponieważ zmienna
x
1
nie spełnia warunków
całkowitoliczbowości, dokonujemy podziału ze względu na
tą zmienną.
1
4.66667
x
=
1
4
x
≤
1
5
x
≥
32
Metoda podziału i ograniczeń
Na podstawie otrzymanych przedziałów budujemy dwa zadania:
Zadanie 6.
Zadanie 7.
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
1
2
0,
0
x
x
≥
≥
1
4
x
≥
2
3
x
≤
1
4
x
≤
1
2
1
2
Z( , ) 6
5
MAX
x x
x
x
=
+
→
1
2
9
7
63
x
x
+
≤
1
2
8
x
x
+ ≤
1
2
3
2
6
x
x
+
≥
1
2
0,
0
x
x
≥
≥
1
4
x
≥
2
3
x
≤
1
5
x
≥
33
Metoda podziału i ograniczeń
Rozwiązanie
Zadania 6:
Rozwiązanie
Zadania 7:
1
2
1
2
4
3 Z( , ) 39
x
x
x x
=
=
=
1
2
1
2
5
2.57143 Z( , ) 42.85714
x
x
x x
=
=
=
34
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Numery zadań, na
które zadanie zostało
podzielone
Czy spełnione
są warunki
całkowitoliczbowości
Wartość
FC
Nr
zadania
2
Tak
43
4
43
Nie
6
39
Tak
7
42.85714
Nie
6
7
35
Metoda podziału i ograniczeń
Porządkowanie listy zadań
Z listy usuwamy:
Zadanie 4.
- bo zostało już podzielone
Zadanie 7.
– nie spełnia warunków całkowitoliczbowości,
a wartość funkcji celu jest mniejsza niż
w
Zadaniu 2.
Zadanie 6.
- warunki całkowitoliczbowości spełnione, ale
wartość funkcji celu jest mniejsza niż
w
Zadaniu 2.
36
Metoda podziału i ograniczeń
Lista zadań wygląda teraz tak:
Numery zadań, na
które zadanie zostało
podzielone
Czy spełnione
są warunki
całkowitoliczbowości
Wartość
FC
Nr
zadania
2
Tak
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.
Kiedy zadanie należy
usunąć z listy?
38
Kiedy zadanie należy usunąć z listy?
W przypadku problemu na MAX, zadanie usuwamy z listy gdy:
• jest sprzeczne
• zostało podzielone
• istnieje zadanie spełniające warunki
całkowitoliczbowości, o większej wartości funkcji celu
39
Kiedy zadanie należy usunąć z listy?
W przypadku problemu na MIN, w ostatnim punkcie
wymagane jest, aby funkcja celu miała mniejszą wartość
Kiedy zadanie należy podzielić?
41
Kiedy zadanie należy podzielić?
W przypadku problemu na MAX, zadanie zastaje podzielone
gdy:
• nie spełnia warunków całkowitoliczbowości, ale ma
największą wartość funkcji celu spośród zadań
znajdujących się na liście
W przypadku problemu na MIN, funkcja celu musi mieć
wartość najmniejszą
Dlaczego nie można rozwiązać
zadania bez warunków
całkowitoliczbowości, a później
zaokrąglić wyników?
43
Dlaczego nie można rozwiązać zadania bez warunków całkowitoliczbowości...
Przykład 8.
Przypomnienie:
Dla Przykładu 1. rozwiązaniem był punkt:
A(3.5,4.5)
Wartość funkcji celu w tym punkcie wynosiła:
1
2
( , ) 43.5
Z x x
=
44
Dlaczego nie można rozwiązać zadania bez warunków całkowitoliczbowości...
Zaokrąglenie obydwu wartości zmiennych:
W górę:
B(4,5)
W dół:
C(3,4)
45
Dlaczego nie można rozwiązać zadania bez warunków całkowitoliczbowości...
46
Dlaczego nie można rozwiązać zadania bez warunków całkowitoliczbowości...
Punkt:
B(4,5)
leży poza zbiorem rozwiązań dopuszczalnych
Punkt:
C(3,4)
leży w zbiorze rozwiązań dopuszczalnych
Wartość funkcji celu dla tego punktu:
1
2
Z( , ) 38
x x
=
Jest to mniejsza wartość FC, niż ta, którą uzyskano w
wyniku rozwiązania zadania z warunkami
całkowitoliczbowości.
Zadanie binarne
48
Zadanie binarne
Przykład 9.
Firma Ziutek Pizza chce otworzyć lokale w pewnym miasteczku.
Możliwe lokacje pizzerii oraz dzielnice jakie może obsłużyć
dany lokal podane są w tabeli.
Sformułować zadanie programowania całkowitoliczbowego,
które może zostać wykorzystane do znalezienia najmniejszej
liczby pizzerii pokrywających swoim zasięgiem wszystkie
dzielnice.
49
Zadanie binarne
Wygwizdów,
Mannhattan, Sikornik,
Narita
Ramblas
Mannhattan, Sikornik,
Montparnasse
Wall Street
Wygwizdów,
Mannhattan, Narita,
Montparnasse
Pola Elizejskie
Dzielnice
Możliwa lokalizacja
pizzerii
(ulice)
50
Zadanie binarne
Zmienne decyzyjne
Przyjmują tylko wartości 0 i 1.
Nazywane są zmiennymi zerojedynkowymi lub binarnymi
51
Zadanie binarne
Zmienna
x
1
:
Opisuje decyzję o ewentualnej lokalizacji pizzerii przy
ulicy Pola Elizejskie:
1
1
0
x
=
jeśli stwierdzona zostanie konieczność lokalizacji przy tej ulicy
jeżeli nie trzeba lokalizować pizzerii przy tej ulicy
52
Zadanie binarne
Zmienna
x
2
:
Opisuje decyzję o ewentualnej lokalizacji pizzerii przy
ulicy Wall Street:
2
1
0
x
=
jeśli stwierdzona zostanie konieczność lokalizacji przy tej ulicy
jeżeli nie trzeba lokalizować pizzerii przy tej ulicy
53
Zadanie binarne
Zmienna
x
3
:
Opisuje decyzję o ewentualnej lokalizacji pizzerii przy
ulicy Ramblas:
3
1
0
x
= ®
¯
jeśli stwierdzona zostanie konieczność lokalizacji przy tej ulicy
jeżeli nie trzeba lokalizować pizzerii przy tej ulicy
54
Zadanie binarne
Funkcja celu:
Minimalizujemy ilość pizzerii, czyli sumę wartości zmiennych
x
1
, x
2
, x
3
1
2
3
1
2
3
Z( , , )
MIN
x x x
x
x
x
= + + →
55
Zadanie binarne
Ograniczenia:
Dla każdej dzielnicy musi istnieć przynajmniej jedna pizzeria,
która będzie ją obsługiwać.
56
Zadanie binarne
Dzielnicę Wygwizdów może obsługiwać pizzeria przy ulicy
Pola Elizejskie lub Ramblas:
1
3
1
x
x
+ ≥
Dzielnicę Mannhattan może obsługiwać pizzeria przy ulicy
Pola Elizejskie, Wall Street lub Ramblas:
1
2
3
1
x
x
x
+ + ≥
Dzielnicę Sikornik może obsługiwać pizzeria przy ulicy
Wall Street lub Ramblas:
2
3
1
x
x
+ ≥
57
Zadanie binarne
Dzielnicę Narita może obsługiwać pizzeria przy ulicy Pola
Elizejskie lub Ramblas:
1
3
1
x
x
+ ≥
Dzielnicę Montparnasse może obsługiwać pizzeria przy ulicy
Pola Elizejskie lub Wall Street:
1
2
1
x
x
+ ≥
58
Zadanie binarne
Model matematyczny:
1
2
3
1
2
3
Z( , , )
MIN
x x x
x
x
x
= + + →
1
3
1
x
x
+ ≥
1
2
3
1
x
x
x
+ + ≥
2
3
1
x
x
+ ≥
1
3
1
x
x
+ ≥
1
2
1
x
x
+ ≥
{ }
1
2
3
, ,
0,1
x x x
∈
59
...a studenci żyli z tą wiedzą długo i szczęśliwie
ZAGADNIENIE
TRANSPORTOWE
(część 1)
Zadanie zbilansowane
3
Zadanie zbilansowane
Przykład 10.
Firma posiada zakłady wytwórcze w miastach
A
,
B
i
C
, oraz
centra dystrybucyjne w miastach
D
,
E
,
F
i
G
.
Możliwości produkcyjne zakładów wynoszą odpowiednio:
120
,
20
i
60
jednostek, natomiast zapotrzebowanie w
poszczególnych centrach dystrybucyjnych odpowiednio:
80
,
30
,
40
i
50
jednostek.
Jednostkowe koszty transportu przedstawione są w tabeli.
Określić taki plan przewozów, aby koszty dostaw z zakładów
wytwórczych do centrów dystrybucyjnych były minimalne.
4
Zadanie zbilansowane
G
F
E
D
C
11
3
2
9
B
2
4
6
4
A
2
8
3
5
Tabela kosztów jednostkowych:
dostawcy
odbiorcy
Model matematyczny
6
Model matematyczny
Produkcja zakładów (podaż):
120 20 60
+
+
200
=
Zapotrzebowanie w centrach dystrybucyjnych (popyt):
80 30 40 50
+
+
+
200
=
Produkcja = Zapotrzebowanie
lub
Podaż = Popyt
Zadanie jest zbilansowane
7
Model matematyczny
1
1
m
n
i
j
i
j
a
b
=
=
=
∑ ∑
gdzie:
a
i
– zasoby
i
– tego dostawcy
b
j
– zapotrzebowanie
j
– tego odbiorcy
m
– ilość dostawców
n
– ilość odbiorców
c
ij
– koszt transportu od
i
– tego dostawcy do
j
– tego odbiorcy
8
Model matematyczny
Zmienne decyzyjne
x
ij
– ilość towaru przewożonego od
i
– tego dostawcy do
j
– tego odbiorcy
i = 1...m
j = 1...n
m = 3 n = 4
np.
x
24
– ilość towaru przewożonego od drugiego dostawcy
(miasto
B
) do czwartego odbiorcy (miasto
G
).
9
Model matematyczny
Funkcja celu
11
12
13
14
21
22
23
24
31
32
33
34
Z( ,
,
,
,
,
,
,
,
,
,
,
)
x x x x x x x x x x x x
=
11
12
13
14
5
3
8
2
x
x
x
x
=
+
+
+
+
21
22
23
24
4
6
4
2
x
x
x
x
+
+
+
+
+
31
32
33
34
9
2
3
11
x
x
x
x
+
+
+
+
MIN
→
1
1
Z( )
MIN
m
n
ij
ij ij
i
j
x
c x
=
=
=
→
∑∑
10
Model matematyczny
Ograniczenia
Dostawcy:
11
12
13
14
:
120
x
x
x
x
+
+
+
=
A
21
22
23
24
:
20
x
x
x
x
+
+
+
=
B
31
32
33
34
:
60
x
x
x
x
+
+
+
=
C
1
1...
n
ij
i
j
x
a
i
m
=
=
=
∑
11
Model matematyczny
Ograniczenia c. d.
Odbiorcy:
11
21
31
:
80
x
x
x
+
+
=
D
12
22
32
:
30
x
x
x
+
+
=
E
13
23
33
:
40
x
x
x
+
+
=
F
14
24
34
:
50
x
x
x
+
+
=
G
1
1...
m
ij
j
i
x
b
j
n
=
=
=
∑
12
Model matematyczny
Warunki brzegowe
0
1...
1...
ij
x
i
m
j
n
≥
=
=
Pierwsze rozwiązanie
dopuszczalne
Metoda kąta
północno - zachodniego
15
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
(3,4)
(3,3)
(3,2)
(3,1)
(2,4)
(2,3)
(2,2)
(2,1)
(1,4)
(1,3)
(1,2)
(1,1)
(1,1)...(3,4)
- węzły
16
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Ilość węzłów bazowych:
1
m n
+ −
W przykładzie:
3 4 1 6
+ − =
17
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
min(120,80)
80
=
80
18
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
19
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
min(40,30)
30
=
30
20
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
21
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
min(10,40)
10
=
10
22
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
23
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
min(20,30)
20
=
20
24
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
20
0
10
0
25
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
20
0
10
0
min(60,10)
10
=
10
26
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
20
0
10
0
10
50
0
27
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
20
0
10
0
10
50
min(50,50)
50
=
50
0
28
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Tablica przewozów:
120
20
60
80
30
40
50
80
40
0
0
0
30
10
0
0
0
10
0
30
0
20
0
10
0
10
50
50
0
0
0
29
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
*
- węzły bazowe
Pierwsze rozwiązanie dopuszczalne:
11
12
13
14
21
22
23
24
31
32
33
34
80
30
10
0
0
0
20
0
0
0
10
50
x
x
x
x
x
x
x
x
x
x
x
x
=
=
=
=
=
=
=
=
=
=
=
=
FC : Z( ) 1230
ij
x
=
30
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Sprawdzenie optymalności rozwiązania
1
u
2
u
3
u
1
v
2
v
3
v
4
v
u
i
– zmienne związane z dostawcami
v
j
– zmienne związane z odbiorcami
31
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
ij
i
j
ij
e
u
v
c
= + +
Wskaźniki optymalności:
Dla węzłów bazowych:
0
ij
e
=
32
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
(1,1)
1
1
5 0
u
v
+ + =
(1,2)
1
2
3 0
u
v
+ + =
(1,3)
1
3
8 0
u
v
+ + =
(2,3)
2
3
4 0
u
v
+ + =
(3,3)
3
3
3 0
u
v
+ + =
(3,4)
3
4
11 0
u
v
+ + =
33
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Układ 6 równań z 7 niewiadomymi.
Układ ma nieskończenie wiele rozwiązań.
Aby go rozwiązać za jedną zmienną przyjmuje się dowolną
wartość.
34
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Przyjmujemy
u
1
= 0
z :
z :
z :
z :
z :
z :
1
5
v
= −
2
3
v
= −
3
8
v
= −
2
3
4
4
u
v
= − − =
3
3
3
5
u
v
= − − =
4
3
11
16
v
u
= − − = −
35
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Wskaźniki optymalności dla węzłów niebazowych:
(1,4)
14
1
4
14
14
e
u
v
c
= + +
= −
(2,1)
21
2
1
21
3
e
u
v
c
= + +
=
(2,2)
22
2
2
22
7
e
u
v
c
= + +
=
(2,4)
24
2
4
24
10
e
u
v
c
= + +
= −
(3,1)
31
3
1
31
9
e
u
v
c
= + +
=
(3,2)
32
3
2
32
4
e
u
v
c
= + +
=
36
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
0
0
4
9
-10
0
7
3
-14
0
0
0
*
*
*
*
*
*
Tablica wskaźników optymalności
37
Pierwsze rozwiązanie dopuszczalne – metoda kąta NW
Kryterium optymalności
Rozwiązanie jest optymalne, jeżeli wartości wszystkich
wskaźników optymalności są nieujemne
Rozwiązanie nie jest optymalne
Kolejne rozwiązania
39
Kolejne rozwiązania
Nowe rozwiązanie
wymiana jednego węzła w bazie
Kryterium wejścia
Do bazy wprowadzany jest węzeł, dla którego wskaźnik
optymalności ma wartość najmniejszą.
W przykładzie:
(1,4)
40
Kolejne rozwiązania
Określenie węzła usuwanego z bazy
Budowa tzw. cyklu
„Definicja cyklu”
W każdym wierszu i kolumnie do cyklu wchodzą dwa lub zero
węzłów.
Cykl składa się z półcyklu dodatniego i ujemnego.
41
Kolejne rozwiązania
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
Tablica przewozów
+
(1,4)
węzeł
wprowadzany
do bazy
Węzeł wprowadzany do bazy – półcykl dodatni
42
Kolejne rozwiązania
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
Tablica przewozów
+
–
(3,4)
drugi węzeł w czwartej kolumnie – półcykl ujemny
43
Kolejne rozwiązania
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
Tablica przewozów
+
–
(3,3)
drugi węzeł w trzecim wierszu – półcykl dodatni
+
44
Kolejne rozwiązania
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
Tablica przewozów
+
–
–
(1,3)
drugi węzeł w trzeciej kolumnie – półcykl ujemny
+
45
Kolejne rozwiązania
80
0
0
30
0
0
10
0
20
0
10
50
*
*
*
*
*
*
Tablica przewozów
+
–
–
Cykl składający się z czterech węzłów
+
46
Kolejne rozwiązania
Określamy minimum w półcyklu ujemnym:
min(10,50) 10
=
Minimum odpowiada węzłowi
(1,3)
Kryterium wyjścia
Z bazy usuwany jest węzeł z półcyklu ujemnego, dla którego
wartość przewozu jest najmniejsza.
47
Kolejne rozwiązania
10
*
Tablica przewozów – nowe rozwiązanie
48
Kolejne rozwiązania
10
*
Tablica przewozów – nowe rozwiązanie
0
49
Kolejne rozwiązania
10
*
Tablica przewozów – nowe rozwiązanie
0
40
*
50
Kolejne rozwiązania
10
*
Tablica przewozów – nowe rozwiązanie
0
40
*
20
*
51
Kolejne rozwiązania
10
*
Tablica przewozów – nowe rozwiązanie
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
FC : Z( ) 1090
ij
x
=
52
Kolejne rozwiązania
0
0
4
9
-10
0
7
3
-14
0
0
0
*
*
*
*
*
*
Tablica wskaźników optymalności z poprzedniego kroku
(1,1)
1
1
0 0
u
v
+ + =
Dla węzłów bazowych:
(1,2)
1
2
0 0
u
v
+ + =
(1,4)
1
4
14 0
u
v
+ − =
(2,3)
2
3
0 0
u
v
+ + =
(3,3)
3
3
0 0
u
v
+ + =
(3,4)
3
4
0 0
u
v
+ + =
53
Kolejne rozwiązania
Przyjmujemy
u
1
= 0
1
0
v
=
2
0
v
=
3
14
v
=
2
14
u
= −
3
14
u
= −
4
14
v
=
Otrzymujemy:
54
Kolejne rozwiązania
Nowe wskaźniki optymalności:
ij
i
j
ij
e
u
v
e
′ = + +
e
ij
– wskaźniki optymalności z poprzedniego kroku
55
Kolejne rozwiązania
0
0
-10
-5
-10
0
-7
-11
0
14
0
0
*
*
*
*
*
*
Nowe wskaźniki optymalności
Rozwiązanie nie jest optymalne
56
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
Węzeł wprowadzany do bazy:
(2,1)
+
57
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
(1,1)
drugi węzeł w pierwszej kolumnie – półcykl ujemny
+
–
58
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
(1,4)
drugi węzeł w pierwszym wierszu – półcykl dodatni
+
–
+
59
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
(3,4)
drugi węzeł w czwartej kolumnie – półcykl ujemny
+
–
+
–
60
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
(3,3)
drugi węzeł w trzecim wierszu – półcykl dodatni
+
–
+
–
+
61
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
(2,3)
drugi węzeł w drugim wierszu – półcykl ujemny
+
–
+
–
+
–
62
Kolejne rozwiązania
10
*
Tablica przewozów
0
40
*
20
*
80
0
0
30
0
0
20
0
*
*
*
Cykl składający się z sześciu węzłów
+
–
+
–
+
–
min(80,20,40) 20
=
(2,3)
usuwany z bazy
63
Kolejne rozwiązania
30
*
Tablica przewozów – nowe rozwiązanie
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
FC : Z( ) 870
ij
x
=
64
Kolejne rozwiązania
0
0
-10
-5
-10
0
-7
-11
0
14
0
0
*
*
*
*
*
*
Tablica wskaźników optymalności z poprzedniego kroku
(1,1)
1
1
0 0
u
v
+ + =
Dla węzłów bazowych:
(1,2)
1
2
0 0
u
v
+ + =
(1,4)
1
4
0 0
u
v
+ + =
(2,1)
2
1
11 0
u
v
+ − =
(3,3)
3
3
0 0
u
v
+ + =
(3,4)
3
4
0 0
u
v
+ + =
65
Kolejne rozwiązania
Przyjmujemy
u
1
= 0
1
0
v
=
2
0
v
=
3
0
v
=
2
11
u
=
3
0
u
=
4
0
v
=
Otrzymujemy:
66
Kolejne rozwiązania
0
0
-10
-5
1
11
4
0
0
14
0
0
*
*
*
*
*
*
Nowe wskaźniki optymalności
Rozwiązanie nie jest optymalne
67
Kolejne rozwiązania
30
*
Tablica przewozów
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
Węzeł wprowadzany do bazy:
(3,2)
+
68
Kolejne rozwiązania
30
*
Tablica przewozów
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
–
+
(1,2)
drugi węzeł w drugiej kolumnie – półcykl ujemny
69
Kolejne rozwiązania
30
*
Tablica przewozów
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
–
+
(1,4)
drugi węzeł w pierwszym wierszu – półcykl dodatni
+
70
Kolejne rozwiązania
30
*
Tablica przewozów
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
–
+
(3,4)
drugi węzeł w czwartej kolumnie – półcykl ujemny
–
+
71
Kolejne rozwiązania
30
*
Tablica przewozów
0
20
*
40
*
60
20
0
30
0
0
0
0
*
*
*
–
+
Cykl składający się z czterech węzłów
–
+
min(30,20) 20
=
(3,4)
usuwany z bazy
72
Kolejne rozwiązania
50
*
Tablica przewozów – nowe rozwiązanie
0
0
*
40
*
60
20
0
10
0
20
0
0
*
*
*
FC : Z( ) 670
ij
x
=
73
Kolejne rozwiązania
0
0
-10
-5
1
11
4
0
0
14
0
0
*
*
*
*
*
*
Tablica wskaźników optymalności z poprzedniego kroku
(1,1)
1
1
0 0
u
v
+ + =
Dla węzłów bazowych:
(1,2)
1
2
0 0
u
v
+ + =
(1,4)
1
4
0 0
u
v
+ + =
(2,1)
2
1
0 0
u
v
+ + =
(3,2)
3
2
10 0
u
v
+ − =
(3,3)
3
3
0 0
u
v
+ + =
74
Kolejne rozwiązania
Przyjmujemy
u
1
= 0
1
0
v
=
2
0
v
=
3
10
v
= −
2
0
u
=
3
10
u
=
4
0
v
=
Otrzymujemy:
75
Kolejne rozwiązania
10
0
0
5
1
1
4
0
0
4
0
0
*
*
*
*
*
*
Nowe wskaźniki optymalności
Rozwiązanie optymalne
76
Kolejne rozwiązania
11
12
13
14
21
22
23
24
31
32
33
34
60
10
0
50
20
0
0
0
0
20
40
0
x
x
x
x
x
x
x
x
x
x
x
x
=
=
=
=
=
=
=
=
=
=
=
=
FC : Z( ) 670
ij
x
=
Rozwiązanie optymalne
77
A jednak się skończyło!!!
Wyszukiwarka
Podobne podstrony:
MO 21 25, AB
MO 1 10, A,B0029
MO pytania przykladowe
mo all
MO 1 10, A,B0012
MO 1 10, A,B0009
MO 11 15, A,B0009
MO - sprawozdanie 2(1), Politechnika Poznańska, Mechatronika, SEMESTR I, Odlewnictwo
sciana MO
MO JM 02 JS 03
MO 16 20, A,B0001
MO 1 10, A,B0026
MO 26 30,AB0010
MO 1 10, A,B0013
MO 1 10, A,B0011
MO 24B
na sternika mo torowodnego EGZAMIN
więcej podobnych podstron