dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

1

PROGRAMOWANIE LINIOWE CAŁKOWITOLICZBOWE

Zadanie programowania liniowego w którym zmienne decyzyjne musz¸a przyjmować wartości całkowite nazywamy zadaniem programowania liniowego całkowi-toliczbowego (krótko PLC).

max(min)z = c1x1 + c2x2 + · · · + cnxn

[Funkcja celu]

a11x1 + a12x2 + · · · + a1nxn ≤ (≥, =)b1

[Ograniczenie 1]

. . .

am1x1 + am2x2 + · · · + amnxn ≤ (≥, =)bm [Ograniczenie m]

x1 ≥ 0, . . . , xr ≥ 0, r ≤ n

[Ograniczenia na znak]

xi − całkowite, i = 1, . . . , n1(n1 ≤ n).

Jeśli n1 = n, zagadnienie nazywamy czystym zagadnieniem programowania liniowego (PCL) natomiast, gdy n1 < n zagadnienie nazywamy mieszanym (MCL).

Przykład. Zagadnienie rozkroju. Klient zamówił w tartaku 100 desek o szerokości 2 cm, 150 desek o szerokości 3 cm i 80 desek o szerokości 4 cm. Wszystkie zamawiane przez klientów deski są tej samej długości l. Deski wycinane s¸a ze standardowych desek o długości l i szerokości 10 cm. W jaki sposób zrealizować zamówienie aby ilość ci¸etych desek standardowych była minimalna? Poniższa ta-bela pokazuje wszystkie możliwe sposoby poci¸ecia standardowej deski: Sposób Ilość 4 cm Ilość 3 cm Ilość 2 cm

1

2

0

1

2

1

2

0

3

1

1

1

4

1

0

3

5

0

3

0

6

0

2

2

7

0

1

3

8

0

0

5

Zmienne decyzyjne:

• xi - ilość desek ci¸eta i-tym sposobem i = 1, . . . , 8.

Model:

P8 x

i=1

i → min

2x1 + x2 + x3 + x4 ≥ 80

[Deski 4 cm]

2x2 + x3 + 3x5 + 2x6 + x7 ≥ 150

[Deski 3 cm]

x1 + x3 + 3x4 + 2x6 + 3x7 + 5x8 ≥ 100 [Deski 2 cm]

xi ≥ 0, xi − całkowite, i = 1, . . . , 8

dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

2

Zadanie w którym wszystkie zmienne decyzyjne musz¸a przyjmować wartość 0 lub 1 nazywamy zadaniem programowania 0-1.

max(min)z = c1x1 + c2x2 + · · · + cnxn

[Funkcja celu]

a11x1 + a12x2 + · · · + a1nxn ≤ (≥, =)b1

[Ograniczenie 1]

. . .

am1x1 + am2x2 + · · · + amnxn ≤ (≥, =)bm [Ograniczenie m]

xi ∈ {0, 1}, i = 1, . . . , n

Przykład. Zagadnienie plecakowe. W magazynie znajduje si¸e 7 paczek. Każda paczka ma określon¸a wag¸e i wartość podan¸a w poniższej tabeli:

Paczka Waga Wartość

1

5

8

2

2

3

3

7

10

4

1

1

5

6

9

6

8

11

7

2

2

Samochód ma ładowność 15 (czyli może zabrać ładunek o ł¸acznej wadze nie wi¸ekszej niż 15). Które paczki ma zabrać samochód aby zmaksymalizować wartość ładunku?

Zmienne decyzyjne:

• xi ∈ {0, 1}, xi = 1 jeżeli samochód zabiera i-t¸a paczk¸e i 0 w przeciwnym wypadku, i = 1, . . . , 7.

Model:

max z = 8x1 + 3x2 + 10x3 + x4 + 9x5 + 11x6 + 2x7

5x1 + 2x2 + 7x3 + x4 + 6x5 + 8x6 + 2x7 ≤ 15

[Ładowność samochodu]

xi ∈ {0, 1}, i = 1, . . . , 7

Rozpatrzmy dodatkowe ograniczenia:

• Należy zabrać paczk¸e 2 lub 5. Należy zamodelować alternatyw¸e x2 = 1 ∨

x5 = 1. Dodajemy ograniczenie:

x2 + x5 ≥ 1

• Nie wolno przewozić razem paczek 1 i 6. Należy zamodelować warunek

∼ (x1 = 1 ∧ x6 = 1) ≡ (x1 = 0 ∨ x6 = 0). Dodajemy ograniczenie:

x1 + x6 ≤ 1

dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

3

• Jeżeli zabieramy paczk¸e 3 to musimy zabrać również paczk¸e 4. Należy zamodelować implikacj¸e x3 = 1 ⇒ x4 = 1. Dodajemy ograniczenie:

x4 ≥ x3

Przykład. Zagadnienie stałych kosztów. Firma tekstylna SZYK zamierza produkować trzy produkty: W1, W2 i W3. Do produkcji tych wyrobów potrzebne są trzy rodzaje maszyn, które firma zamierza wynająć. Wynajęcie maszyn do produkcji wyrobów W1, W2 i W3 kosztyje tygodniowo odpowiednio 200, 150 i 100 zł.

Zmienne koszty produkcji szacuje się odpowiednio na 6, 4 i 8 zł. za sztukę a cena zbytu wynosi odpowiednio 12, 8 i 15 zł. za szt. Wyroby te produkuje się z mate-riału, którego tygodniowa dostawa nie przekracza 160 m2 a jednostkowe zużycie wynosi odpowiednio 4, 3 i 4 m2. Ponadto zdolności produkcyjne firmy ograni-cza zatrudnienie - dysponuje 150 roboczogodzinami tygodniowo. Pracochłonność wytwarzania jednej sztuki każdego wyrobu wynosi odpowiednio 3, 2 i 6 roboczogodzin. Firma chce opracować plan produkcji maksymalizujący zysk. Zmienne decyzyjne:

• xi - ilość produkowanego wyrobu Wi i = 1, 2, 3.

• yi ∈ {0, 1}, yi = 1 jeżeli produkuje się wyrób Wi i = 1, 2, 3 a 0 w przeciwnym wypadku.

Model: Funkcją celu jest zysk (Dochód - koszt zmienny - koszt wynajmu maszyn) max z = 12x1 + 8x2 + 15x3 − (6x1 + 4x2 + 8x3) − (200y1 + 150y2 + 100y3)

= 6x1 + 4x2 + 7x3 − 200y1 − 150y2 − 100y3

3x1 + 4x2 + 7x3 ≤ 150

4x1 + 3x2 + 4x3 ≤ 160

x1 ≤ M1y1( jeśli x1 > 0 to y1 = 1)

x2 ≤ M2y2( jeśli x2 > 0 to y2 = 1)

x3 ≤ M3y3( jeśli x3 > 0 to y3 = 1)

x1, x2, x3 ≥ 0 całkowite; y1, y2, y3 ∈ {0, 1}

Z ograniczeń mamy, że M1 = 40 , M2 = 53 i M3 = 25. Rozwiązanie optymalne to: zopt = 75, x3 = 25, y3 = 1.

Przykład. Zagadnienie lokalizacji.

Przykład. Zagadnienie pokrycia. W pewnym regionie znajduje si¸e sześć miast.

Czasy przejazdu mi¸edzy miastami (w minutach) podane s¸a w poniższej tabeli: Miasto 1

Miasto 2

Miasto 3

Miasto 4

Miasto 5

Miasto 6

Miasto 1

0

10

20

30

30

20

Miasto 2

0

25

35

20

10

Miasto 3

0

15

30

20

Miasto 4

0

15

25

Miasto 5

0

14

dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

4

W których miastach należy ulokować posterunki policji aby czas dojazdu do każ-

dego miasta był nie dłuższy niż 15 minut? Chcemy zminimalizować liczb¸e wybu-dowanych posterunków.

Posterunek w mieście

obsługuje miasta

1

1,2

2

1,2,6

3

3,4

4

3,4,5

5

4,5,6

6

2,5,6

Zmienne decyzyjne:

• xi ∈ {0, 1}, xi = 1 jeżeli budujemy posterunek w i-tym mieście i 0 w przeciwnym wypadku, i = 1, . . . , 6.

Model:

x1 + x2 + x3 + x4 + x5 + x6 → min

x1 + x2 ≥ 1

[Należy obsłużyć miasto 1]

x1 + x2 + x6 ≥ 1

[Należy obsłużyć miasto 2]

x3 + x4 ≥ 1

[Należy obsłużyć miasto 3]

x3 + x4 + x5 ≥ 1

[Należy obsłużyć miasto 4]

x4 + x5 + x6 ≥ 1

[Należy obsłużyć miasto 5]

x2 + x5 + x6 ≥ 1

[Należy obsłużyć miasto 6]

xi ∈ {0, 1}, i = 1, . . . , 6

dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

5

Przykład (zaawansowane modelowanie). Firma wytwarza 3 typy samochodów.

Dane s¸a nast¸epuj¸ace:

TYP 1

TYP 2

TYP 3

Zużycie stali (t/szt)

1.5

3

5

Wymagana praca (h/szt)

30

25

40

Zysk ($/szt.)

2000

3000

4000

Zapas stali wynosi 6000 t a dost¸epna praca wynosi 60 000 godzin. Chcemy zmaksymalizować zysk.

Zmienne decyzyjne:

• xi - liczba produkowanych samochodów i-tego typu, i = 1, . . . , 3.

Model:

2000x1 + 3000x2 + 4000x3 → max

1.5x1 + 3x2 + 5x3 ≤ 6000

[Zużycie stali]

30x1 + 25x2 + 40x3 ≤ 60000

[Zużycie pracy]

x1, x2, x2 ≥ 0 i całkowite

Rozpatrzmy nast¸epuj¸ace dodatkowe wymagania:

1. Produkcja mniej niż 1000 sztuk typu 1 jest nieopłacalna (należy produkować albo 0 albo co najmniej 1000 sztuk). Należy zamodelować alternatyw¸e x1 ≤

0 ∨ x1 ≥ 1000. Wprowadzamy zmienn¸a binarn¸a y1 ∈ {0, 1} i dodajemy dwa ograniczenia:

x1 ≤ M y1

1000 − x1 ≤ M (1 − y1)

gdzie M jest duż¸a liczb¸a. Jeżeli y1 = 0 to x1 ≤ 0. Jeżeli y1 = 1 to 1000 − x1 ≤ 0 czyli x1 ≥ 1000. W ten sposób jeden z dwóch warunków

musi być spełniony.

Uwaga: W ogólnym przypadku chcemy zamodelować alternatyw¸e

f (x1, . . . , xn) ≤ 0 ∨ g(x1, . . . , xn) ≤ 0

Chcemy aby przynajmniej jedno z dwóch ograniczeń było spełnione. Wy-

maganie to modelujemy wprowadzaj¸ac zmienn¸a binarn¸a y ∈ {0, 1} i zast¸epuj¸ac oryginalne ograniczenia ograniczeniami:

f (x1, . . . , xn) ≤ M y

(1.1)

g(x1, . . . , xn) ≤ M (1 − y)

gdzie M jest jak¸aś bardzo duż¸a liczb¸a.

dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

6

2. Jeżeli produkcja typu 3 przekroczy 500 szt. to produkcja typu 2 nie może przekroczyć 100 szt. Chcemy zamodelować implikacj¸e (x3 > 500) ⇒ (x2 ≤

100). Korzystamy z prawa logicznego (p ⇒ q) ≡ (∼ p ∨ q). St¸ad (x3 > 500) ⇒ (x2 ≤ 100) ≡ (x3 ≤ 500) ∨ (x2 ≤ 100) Wprowadzamy zmienn¸a

binarn¸a y2 ∈ {0, 1} i dodajemy ograniczenia (zgodnie z (1.1)):

x3 − 500 ≤ M y2

x2 − 100 ≤ M (1 − y2)

gdzie M jest jak¸aś bardzo duż¸a liczb¸a. Jeżeli x3 > 500 to aby spełnić pierw-sze ograniczeni musi zajść y2 = 1. Wówczas z drugiego ograniczenie otrzymujemy x2 ≤ 100. Jeżeli x3 ≤ 500 to y2 = 0 i wartość x2 może być dowolna.

Uwaga: W ogólnym przypadku chcemy zamodelować implikacj¸e

f (x1, . . . , xn) > 0 ⇒ g(x1, . . . , xn) ≤ 0.

Korzystamy z równoważnego warunku:

f (x1, . . . , xn) ≤ 0 ∨ g(x1, . . . , xn) ≤ 0.

i dodajemy ograniczenia zgodnie z (1.1). Jeżeli chcemy zamodelować implikacj¸e

f (x1, . . . , xn) > 0 ⇒ g(x1, . . . , xn) ≥ 0

to korzystamy z równoważnego warunku:

f (x1, . . . , xn) ≤ 0 ∨ −g(x1, . . . , xn) ≤ 0.

i dodajemy ograniczenia zgodnie z (1.1).

dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

7

ALGORYTM PODZIAŁU I OGRANICZEŃ

Naiwne metody rozwi¸azywania zadania PLC.

1. Pomiń warunki całkowitoliczbowości, rozwi¸aż problem algorytmem sympleks i zaokr¸aglij wynik. Rozpatrzmy przykład:

x2

3.5

3

2.5

2

1.5

1

0.5

0

0.5

1.0

1.5

2.0

x1

Problem posiada 6 rozwi¸azań dopuszczalnych. S¸a to punkty (0,0), (0,1), (0,2), (0,3), (1,0) i (1,1). Funkcja celu osi¸aga najwi¸eksz¸a wartość w punk-cie (0,3). Pomijaj¸ac warunki całkowitoliczbowości otrzymujemy optymalny punkt (13/7,0). Zaokr¸aglaj¸ac wynik w gór¸e otrzymujemy punkt (2,0), który jest niedopuszczalny. Zaokr¸aglaj¸ac wynik w dół otrzymujemy punkt (1, 0), który jest nieoptymalny.

2. Wygeneruj wszystkie rozwi¸azania dopuszczalne i wybierz najlepsze. Rozpatrzmy problem plecakowy:

P

max z =

n

c

i=1

ixi

Pn w

i=1

ixi ≤ W

xi ∈ {0, 1}, i = 1 . . . n

W problemie tym należy wygenerować i sprawdzić 2n rozwi¸azań. Załóżmy, że jedno rozwi¸azanie można sprawdzić w czasie 10−6 s. Wówczas dla n = 50

czas obliczeń wyniesie ok. 35 lat a dla n = 60 czas ten wyniesie ok. 36 558

lat. Algorytmy pełnego przegl¸adu s¸a wi¸ez bardzo nieefektywne.

Uwaga: Dla ogólnego zadania PLC nie jest znany efektywny algorytm (wszystkie znane algorytmy mog¸a działać bardzo długo dla pewnych niedużych problemów)

dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

8

Zadanie PL otrzymane z PLC przez usuni¸ecie warunków całkowitoliczbowości nazywamy relaksacj¸a PLC. Przykładowy problem i jego relaksacja: max z = 21x1 + 11x2

max z

7x

R = 21x1 + 11x2

1 + 4x2 ≤ 13

7x

x

1 + 4x2 ≤ 13

1, x2 ≥ 0

x

x

1, x2 ≥ 0

1, x2 całkowite

Wprowadzamy oznaczenia:

• z∗ - maksymalna wartość funkcji celu PLC

• z∗ - maksymalna wartość funkcji celu odpowiedniej relaksacji PLC.

R

Własność: Zachodzi zawsze warunek z∗ ≥ z∗, czyli relaksacja określa górne R

ograniczenie na wartość funkcji celu w PLC. Relaksacj¸e można rozwi¸azać algorytmem sympleks. Na poj¸eciu relaksacji opiera si¸e algorytm podziału i ograniczeń.

Przykład. Rozwi¸azać problem:

max z = 8x1 + 5x2

6x1 + 10x2 ≤ 45

9x1 + 5x2 ≤ 45

x1, x2 ≥ 0, x1, x2 całkowite

Zaczynamy od rozwi¸azania relaksacji (np. algorytmem sympleks albo metod¸a graficzn¸a). Otrzymujemy x1 = 3.75, x2 = 2.25, z∗ = 41.25.

R

x2

5

4

3

(3.75,2.25)

2

1

0

1

2

3

4

5

x1

Otrzymane rozwi¸azanie jest niedopuszczalne ponieważ zmienne s¸a niecałkowite.

Wybieramy zmienn¸a niecałkowit¸a z wi¸ekszym współczynnikiem funkcji celu czyli x1. Dokonujemy podziału zmiennej x1 i rozpatrujemy dwa podproblemy:

dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

9

x = 3.75, x = 2.25

0

1

2

z∗ = 41.25

R

x1 ≤ 3

x1 ≥ 4

x = 3, x = 2.7

x = 4

= 1

1

2

1

, x2

.8

1

2

z∗ = 37.5

z∗ = 41

R

R

5

4

3

(3,2.7)

2

(4,1.8)

1

1

2

0

1

2

3

4

5

Rozwi¸azania obu podproblemów s¸a niedopuszczalne (tzn. nie są całkowite). Wybieramy podproblem, dla którego relaksacja daje wi¸eksze górne oszacowaniem czyli podproblem 2. Zmienna x2 jest niecałkowita. Dokonujemy wi¸ec podziału x2

i tworzymy dwa podproblemy 3 i 4. Podproblem 4 jest sprzeczny - odpowiadaj¸acy mu wierzchołek zamykamy (nie dzielimy dalej).

x = 3.75, x = 2.25

0

1

2

z∗ = 41.25

R

x1 ≤ 3

x1 ≥ 4

x = 3, x = 2.7

x = 4

= 1

1

2

1

, x2

.8

1

2

z∗ = 37.5

z∗ = 41

R

R

x2 ≤ 1

x2 ≥ 2

x = 4.44, x = 1

3

1

2

4

model sprzeczny

z∗ = 40.55

R

Wybieramy otwarty podproblem z najwi¸ekszym górnym oszacowaniem, czyli podproblem 3. Zmienna x1 jest niecałkowita. Dokonujemy wi¸ec podziału x1 i tworzymy podproblemy 5 i 6. Rozwi¸azuj¸ac oba podproblemy otrzymujemy optymalne rozwi¸azania całkowite. Odpowiadaj¸ace im wierzchołki zamykamy. W tym momencie znamy dopuszczalne rozwi¸azanie x1 = 5, x2 = 0 o wartości funkcji celu równej 40. Musimy jeszcze zbadać otwarty podproblem 1. Ponieważ górne ograniczenie w tym podproblemie jest równe 37.5 < 40, to podproblem 1 nie może zawierać rozwi¸azania lepszego niż rozwi¸azanie x1 = 5, x2 = 0. Wierzchołek odpowiadaj¸acy podproblemowi 1 zamykamy. W tym momencie wszystkie wierzchołki s¸a zamlni¸ete i optymalnym rozwi¸azaniem jest x1 = 5, x2 = 0.

dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

10

x = 3.75, x = 2.25

0

1

2

z∗ = 41.25

R

x1 ≤ 3

x1 ≥ 4

x = 3, x = 2.7

x = 4

= 1

1

2

1

, x2

.8

1

2

z∗ = 37.5

z∗ = 41

R

R

x2 ≤ 1

x2 ≥ 2

x = 4.44, x = 1

3

1

2

4

model sprzeczny

z∗ = 40.55

R

x1 ≤ 4

x1 ≥ 5

x = 4, x = 1

x = 5, x = 0

5

1

2

6

1

2

z∗ = 37

z∗ = 40

R

R

Przykład. Rozwi¸azać problem:

max z = 2x1 + x2

5x1 + 2x2 ≤ 8

x1 + x2 ≤ 3

x1, x2 ≥ 0, x1 całkowite

Powyższy problem jest tzw. problemem mieszanym (tylko niektóre zmienne musz¸a być całkowite. Należy dzielić tylko zmienn¸a x1. Drzewo podziału i ograniczeń wygl¸ada nast¸epuj¸aco:

x = 2/3, x = 7/3

0

1

2

z∗ = 11

R

x1 ≥ 1

x1 ≤ 0

x = 0, x = 3

x = 1

= 3

1

, x2

/2

1

1

2

2

z∗ = 3

z∗ = 7/2

R

R

Optymalne rozwi¸azanie znajduje si¸e w wierzchołku 2. Jest to rozwi¸azanie x1 = 1, x2 = 3/2 o wartości funkcji celu z∗ = 7/2.

Wierzchołek (podproblem) k zamykamy jeżeli:

1. Rozwi¸azenie relaksacji w k jest dopuszczalne (odpowiednie zmienne s¸a cał-

kowite).

2. Relaksacja w k jest sprzeczna.

3. Znaleziono wcześniej rozwi¸azanie dopuszczalne dla którego wartość fukcji celu jest niemniejsza od z∗ w k.

R

dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

11

Algorytm podziału i ograniczeń dla problemu plecakowego

Rozpatrujemy nast¸epuj¸acy problem: P

max z =

n

c

i=1

ixi

Pn w

i=1

ixi ≤ W

xi ∈ {0, 1}, i = 1 . . . n

gdzie ci - cena i-tego przedmiotu, wi - waga i-tego przedmiotu, W - pojemność plecaka.

Przykład. Rozwi¸azać problem:

max z = 5x1 + 3x2 + 6x3 + 6x4 + 2x5

5x1 + 4x2 + 7x3 + 6x4 + 2x5 ≤ 15,

x1, .., x5 ∈ {0, 1}

Relaksacj¸a powyższego problemu jest nast¸epuj¸acy problem:

max zR = 5x1 + 3x2 + 6x3 + 6x4 + 2x5

5x1 + 4x2 + 7x3 + 6x4 + 2x5 ≤ 15,

0 ≤ xi ≤ 1, i = 1, . . . , 5

Relaksacj¸e rozwi¸azujemy za pomoc¸a nast¸epuj¸acego algorytmu zachłannego: i

ci

wi

ci/wi

1

5

5

1

2

3

4

3/4

3

6

7

6/7

4

6

6

1

5

2

2

1

Ładujemy przedmioty w kolejności ilorazów ci/wi zaczynaj¸ac od najwi¸ekszego.

Pocz¸atkowa wolna pojemność plecaka W = 15. Dodajemy cały przedmiot 1

(W = 10), dodajemy cały przedmiot 4 (W = 4), dodajemy cały przedmiot

5 (W = 2), dodajemy 2/7 przedmiotu 3 (W = 0). Otrzymujemy rozwi¸azanie x1 = 1, x2 = 0, x3 = 2/7, x4 = 1, x5 = 1 i z∗ = 145 . Rozwi¸azanie to jest R

7

niedopuszczalne. Wybieramy zmienn¸a niecałkowit¸a x3 i rozpatrujemy dwa podproblemy (dokonujemy podziału):

1. Ustawiamy x3 = 0 czyli rozpatrujemy relaksacj¸e bez przedmiotu 3.

max zR = 5x1 + 3x2 + 6x4 + 2x5

5x1 + 4x2 + 6x4 + 2x5 ≤ 15,

0 ≤ xi ≤ 1, i = 1, 2, 4, 5

Otrzymujemy rozwi¸azanie: x1 = 1, x2 = 1, x

2

3

= 0, x4 = 1, x5 = 1 i

z∗ = 141 .

R

2

dr inż. Adam Kasperski, M. Kulej Badania Operacyjne Wykład 4

12

2. Ustawiamy x3 = 1 czyli wkładamy przedmiot 3 do plecaka i pozostałe przedmioty dodajemy zachłannie.

max zR = 5x1 + 3x2 + 6 + 6x4 + 2x5

5x1 + 4x2 + 6x4 + 2x5 ≤ 8,

0 ≤ xi ≤ 1, i = 1, 2, 4, 5

Otrzymujemy rozwi¸azanie: x1 = 1, x2 = 0, x3 = 1, x4 = 1 , x

= 14.

2

5 = 0 i z∗

R

Oba podproblemy s¸a niedopuszczalne. Wybieramy podproblem o lepszym osza-cowaniu (relaksacji) czyli podproblem 1 i dzielimy dalej. Pełne drzewo podziału i ograniczeń pokazane jest na poniższym rysunku:

0

z∗ = 145

R

7

(1, 0, 2, 1, 1)

7

x3 = 0

x3 = 1

z∗ = 141

z∗ = 14

R

R

1

2

2

(1, 1, 0, 1, 1)

(1, 0, 1, 1, 0, )

2

2

x2 = 0

x2 = 1

x4 = 0

x4 = 1

z∗ = 13

z∗ = 14

z∗ = 133

z∗ = 14

R

4

R

3

R

4

R

5

6

(1, 0, 0, 1, 1)

(1, 1, 0, 1, 0)

(1, 1, 1, 0, 1)

(2, 0, 1, 1, 0)

4

5

Wierzchołki 5 i 6 zamykamy ponieważ w wierzchołku 4 znaleziono dopuszczalne rozwi¸azanie o wartości niemniejszej niż górne oszacowanie w 5 i 6. Optymalne rozwi¸azanie odczytujemy w wierzchołku 4, czyli zabieramy przedmioty 1, 2 i 4.