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