Programowanie 

całkowitoliczbowe

- 

metoda podziału i  

ograniczeń

opk

1

2

Przykład:

Zakład produkuje wyroby W

1

 i W

2

.

Wśród materiałów które zostaną użyte w produkcji 
są 2 limitowane. Limity te wynoszą m

1

=48 a dla 

materiału drugiego m

2

=56 jednostek. 

Aby wyprodukować jednostkę wyrobu W

1

 potrzeba 8 

jednostek materiału m

1

 i 7 jednostek materiału m

2

.

Aby wyprodukować jednostkę wyrobu W

2

 potrzeba 6 

jednostek materiału m

1

 i 7 jednostek materiału m

2

.

Wyroby W

1

 i W

2

 są niezbędne do produkcji 

urządzenia U. 
Jedno urządzenie U wymaga 4 jednostek wyrobu W

1

 

i 3 jednostek wyrobu W

2

.

Produkcja będzie opłacalna jeżeli zakład sprzeda 
wyroby W

1

 i W

2

 potrzebne do wytworzenia co 

najmniej 12 jednostek urządzenia U.
Wiedząc, że cena wyrobu W

1

 będzie wynosić 7 a 

cena wyrobu W

2

 6 określ wielkość produkcji 

maksymalizującej zysk ze sprzedaży.

Model matematyczny:

FC: Z(x

1

, x

2

)=7x

1

+6x

2

→MAX

O: a)  8x

1

 + 6x

2

 ≤ 48

b)  x

1

 + x

2

 ≤ 7

c) 4x

1

 + 3x

2

 ≥12

WB:  x

1

 ≥ 0,  x

2

 ≥ 0

x

1

є C

Metoda podziału i ograniczeń

3

Szukamy rozwiązania nie uwzględniając 

warunku całoliczbowości

 

4

Z(x

1

, x

2

)=7x

1

+6x

2

→MAX

a)  8x

1

 + 6x

2

 ≤ 48

b)  x

1

 + x

2

 ≤ 7

c) 4x

1

 + 3x

2

 ≥12

  x

1

 ≥ 0,  x

2

 ≥ 0

Rozwiązanie: 
x

1

=3,40

x

2

=2,75 z(x

1

, x

2

) 

= 40,3

Zadanie umieszczamy na liście zadań:

5

Nr 

zadani

a

Wartość 

FC

Czy spełnione są 

warunki 

całkowitoliczbowo

ści

Numer zadań, na które 

zadanie zostało 

podzielone

1

40,3

Nie

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:

                x

2

є [0,2]               x

2

є [3, ∞)

                x

2

 ≤ 2

 

     x

2

 ≥ 3

Numer zadań umieszczony na liście 

zadań

Na podstawie otrzymanych przedziałów budujemy dwa zadania:

6

Zadanie 2:

Z(x

1

, x

2

)=7x

1

+6x

2

→MAX

a)  8x

1

 + 6x

2

 ≤ 48

b)  x

1

 + x

2

 ≤ 7

c) 4x

1

 + 3x

2

 ≥12

           d) x

2

 ≤ 2

    x

1

 ≥ 0,  x

2

 ≥ 0

Zadanie 3:

Z(x

1

, x

2

)=7x

1

+6x

2

→MAX

a)  8x

1

 + 6x

2

 ≤ 48

b)  x

1

 + x

2

 ≤ 7

c) 4x

1

 + 3x

2

 ≥12

           d) x

2

 ≥ 3

    x

1

 ≥ 0,  x

2

 ≥ 0

Nr 

zadani

a

Wartość 

FC

Czy spełnione są 

warunki 

całkowitoliczbowo

ści

Numer zadań, na które 

zadanie zostało 

podzielone

1

40,3

Nie

2

3

Dla zadania 3:
maksimum w punkcie 

G(17/5,2)

wartość funkcji celu 

Z(17/5,2) 

= 40 1/3 

Dla zadania 3:
Maksimum w punkcie  G(3,4)
Wartość funkcji celu 

Z(3,4) = 40 

7

8

Lista zadań wygląda teraz tak:

Nr 

zadani

a

Wartość 

FC

Czy spełnione są 

warunki 

całkowitoliczbow

ości

Numer zadań, na które 

zadanie zostało 

podzielone

1

40,3

Nie

2

3

2

40 1/3

Tak

3

40

Tak

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.

9

Lista zadań wygląda teraz tak:

Nr 

zadani

a

Wartość 

FC

Czy spełnione są 

warunki 

całkowitoliczbowo

ści

Numer zadań, na które 

zadanie zostało 

podzielone

2

40,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.

Dla zadania 2:
Maksimum w punkcie  C (17/5, 2)
Wartośc funkcji celu 

Z (17/5, 2) = 40 1/3

10

Model matematyczny:
FC: Z(x

1

, x

2

)=7x

1

+6x

2

→MAX

O: a)  8x

1

 + 6x

2

 ≤ 48

b)  x

1

 + x

2

 ≤ 7

c) 4x

1

 + 3x

2

 ≥12

WB:  x

1

 ≥ 0,  x

2

 ≥ 0

x

1

є C 

x

2

є C

Rozwiązujemy zadanie metodą podziału 
i    ograniczeń,  przy  czym  wielkość 
produkcji  obydwóch  wyrobów  musi  być 
określona liczbą całkowitą 

11

Szukamy rozwiązania nie 
uwzględniając warunku 
całoliczbowości 

Zadanie 1

Z(x

1

, x

2

)=7x

1

+6x

2

→MAX

a)  8x

1

 + 6x

2

 ≤ 48

b)  x

1

 + x

2

 ≤ 7

c) 4x

1

 + 3x

2

 ≥12

  x

1

 ≥ 0,  x

2

 ≥ 0

Rozwiązanie: 

x

1

=3,40 x

2

=2,75 z(x

1

, x

2

) = 40,3

Zadanie umieszczamy na liście zadań:

12

Nr 

zadani

a

Wartość 

FC

Czy spełnione są 

warunki 

całkowitoliczbowoś

ci

Numer zadań, na które 

zadanie zostało 

podzielone

1

40,3

Nie

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:
x

1

 ≤ 3

x

1

 ≥ 4

Na podstawie otrzymanych przedziałów 

budujemy dwa zadania:

13

Zadanie 2:
Z(x

1

, x

2

)=7x

1

+6x

2

→MAX

a)  8x

1

 + 6x

2

 ≤ 48

b)  x

1

 + x

2

 ≤ 7

c) 4x

1

 + 3x

2

 ≥12

          d) x

1

 ≤ 3

  x

1

 ≥ 0,  x

2

 ≥ 0

Rozwiązanie zadania 2:

x

1

=3  x

2

=3,17  Z(x

1

,x

2

)=40,2

Zadanie 3:
Z(x

1

, x

2

)=7x

1

+6x

2

→MAX

a)  8x

1

 + 6x

2

 ≤ 48

b)  x

1

 + x

2

 ≤ 7

c) 4x

1

 + 3x

2

 ≥12

          d) x

1

≥ 4

  x

1

 ≥ 0,  x

2

 ≥ 0

Rozwiązanie zadania 3:

x

1

=4  x

2

=2, Z(x

1

,x

2

)=40

14

Lista zadań wygląda teraz tak:

Nr 

zadan

ia

Wartość 

FC

Czy spełnione są 

warunki 

całkowitoliczbo

wości

Numer zadań, na które 

zadanie zostało 

podzielone

1

40,3

Nie

2

3

2

40,2

Nie

3

40

Tak

Porządkowanie listy zadań
Z listy usuwamy:
Zadanie 1 bo zostało już podzielone
Zadanie 2  - nie spełnia warunków 
całkowitoliczbowości, ale ma większą wartość funkcji 
celu niż zadanie 2.
Zadanie 3 spełnia wszystkie warunki 
całkowitoliczbowości.

15

Lista zadań wygląda teraz tak:

Nr 

zadan

ia

Wartość 

FC

Czy spełnione są 

warunki 

całkowitoliczbo

wości

Numer zadań, na które 

zadanie zostało 

podzielone

2

40,2

Nie

3

40

Tak

Zadanie 2 musi zostać podzielone
Rozwiązanie Zadanie 2

 x

1

=3  x

2

=3,17

Ponieważ zmienna x2 nie spełnia warunków 
całkowitoliczbowości dokonujemy podziału ze 
względu na ta zmienną  

Na podstawie otrzymanych przedziałów 

budujemy dwa zadania:

16

Zadanie 4:

Z(x

1

, 

x

2

)=7x

1

+6x

2

→MAX

a)  8x

1

 + 6x

2

 ≤ 48

b)  x

1

 + x

2

 ≤ 7

c) 4x

1

 + 3x

2

 ≥12

          d) x

1

≥ 4 

          e) x

2

 ≤ 3

  x

1

 ≥ 0,  x

2

 ≥ 0

Rozwiązanie zadania 4:

x

1

=3  x

2

=3   

Z(x

1

,x

2

)=39

  

Zadanie 5:

Z(x

1

, 

x

2

)=7x

1

+6x

2

→MAX

a)  8x

1

 + 6x

2

 ≤ 

48

b)  x

1

 + x

2

 ≤ 7

c) 4x

1

 + 3x

2

 ≥12

          d) x

1

≥ 4

          e) x

2

≥ 4

  x

1

 ≥ 0,  x

2

 ≥ 0

Rozwiązanie zadania 

5:
Zadanie jest 

sprzeczne

17

Lista zadań wygląda teraz tak:

Nr 

zadani

a

Wartość 

FC

Czy spełnione są 

warunki 

całkowitoliczbowo

ści

Numer zadań, na które 

zadanie zostało 

podzielone

2

40,2

Nie

4

5

3

40

Tak

4

39

Tak

5

Zadanie sprzeczne

Zadanie 2 musi zostać podzielone.
Zadanie 3 spełnia wszystkie warunki 
całkowitoliczbowości.
Zadanie 4 warunki całkowitoliczbowości zostały 
spełnione, ale wartość funkcji celu jest mniejsza niż w 
zadaniu 3.

18

Lista zadań wygląda teraz tak:

Nr 

zadani

a

Wartość 

FC

Czy spełnione są 

warunki 

całkowitoliczbowo

ści

Numer zadań, na które 

zadanie zostało 

podzielone

3

40

Tak

Na  liście  pozostaje  tylko  jedno 
zadanie.
Ponieważ 

spełnia 

ono 

wszystkie 

warunki  całkowitoliczbowości,  to  jego 
rozwiązanie 

jest 

rozwiązaniem 

optymalnym zadania pierwotnego .

x

1

=4  x

2

=2, Z(x

1

,x

2

)=40