Programowanie
całkowitoliczbowe
Programowanie całkowitoliczbowe (1)
1. Model optymalizacyjny:
F(x) = F(x
1
,x
2
) = 4x
1
+ 3x
2
→
max
2x
1
+ 3x
2
≤
6
4x
1
+ 2x
2
≤
8
x
1
≥
0 x
2
≥
0
x
1
, x
2
∈
C
Programowanie całkowitoliczbowe (2)
x
2
x
1
1
2
3
1
2
3
4
G[3,4]
R*[1,5; 1]
F*(x
1
,x
2
) = 9
Programowanie całkowitoliczbowe - przykład
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
x
2
≥
0
x
3
≥
0
x
1
, x
2
, x
3
∈
C
Programowanie całkowitoliczbowe - przykład
Zadanie Z
1/-
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
100
x
2
≥
0
oraz x
2
≤
100
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
3,11
0
100
x
2
2,89
0
100
x
3
0
0
100
Z
max
18
×
×
Lista zada
ń
do podziału:
Z
1/-
;
(18)
Programowanie całkowitoliczbowe - przykład
Zadanie Z
2/1
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
3
x
2
≥
0
oraz x
2
≤
100
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
3
0
3
x
2
2,78
0
100
x
3
0,05
0
100
Z
max
17,95
×
×
Lista zada
ń
do podziału:
Z
2/1
;
(17,95)
Zadanie Z
3/1
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
4
oraz x
1
≤
100
x
2
≥
0
oraz x
2
≤
100
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
Zadanie
4
100
x
2
sprz.
0
100
x
3
0
100
Z
max
---
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
4/2
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
3
x
2
≥
0
oraz x
2
≤
2
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
2,22
0
3
x
2
2
0
2
x
3
0,38
0
100
Z
max
17,61
×
×
Lista zada
ń
do podziału:
Z
4/2
;
(17,61)
Zadanie Z
5/2
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
3
x
2
≥
3
oraz x
2
≤
100
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
Zadanie
0
3
x
2
sprz.
3
100
x
3
0
100
Z
max
---
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
6/4
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
2
x
2
≥
0
oraz x
2
≤
2
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
2
0
2
x
2
1,78
0
2
x
3
0,47
0
100
Z
max
17,52
×
×
Lista zada
ń
do podziału:
Z
6/4
;
(17,52)
Zadanie Z
7/4
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
3
oraz x
1
≤
3
x
2
≥
0
oraz x
2
≤
2
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
Zadanie
3
3
x
2
sprz.
0
2
x
3
0
100
Z
max
---
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
10/8
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
1
x
2
≥
0
oraz x
2
≤
1
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
1
0
1
x
2
0,78
0
1
x
3
0,90
0
100
Z
max
17,09
×
×
Lista zada
ń
do podziału:
Z
9/6
; Z
10/8
; Z
11/8
→
Z
10/8
(15,71) (17,09) (10,85)
Zadanie Z
11/8
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
2
oraz x
1
≤
2
x
2
≥
0
oraz x
2
≤
1
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
2
2
2
x
2
1
0
1
x
3
0,14
0
100
Z
max
10,85
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
8/6
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
2
x
2
≥
0
oraz x
2
≤
1
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
1,22
0
2
x
2
1
0
1
x
3
0,81
0
100
Z
max
17,19
×
×
Lista zada
ń
do podziału:
Z
8/6
; Z
9/6
→
Z
8/6
(17,52) (15,71)
Zadanie Z
9/6
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
2
x
2
≥
2
oraz x
2
≤
2
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
2
0
2
x
2
2
2
2
x
3
0,28
0
100
Z
max
15,71
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
12/10
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
1
x
2
≥
0
oraz x
2
≤
0
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
0,22
0
1
x
2
0
0
0
x
3
1,23
0
100
Z
max
16,76
×
×
Lista zada
ń
do podziału:
Z
9/6
; Z
11/8
; Z
12/10
; Z
13/10
→
Z
12/10
(15,71) (10,85) (16,76) (15,28)
Zadanie Z
13/10
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
1
x
2
≥
1
oraz x
2
≤
1
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
1
0
1
x
2
1
1
1
x
3
0,71
0
100
Z
max
15,28
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
14/12
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
0
x
2
≥
0
oraz x
2
≤
0
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
0
0
0
x
2
0
0
0
x
3
1,14
0
100
Z
max
14,85
×
×
Lista zada
ń
do podziału:
Z
9/6
; Z
11/8
; Z
13/10
; Z
14/12
; Z
15/12
→
Z
9/6
(15,71) (10,85) (15,28) (14,85) (10,43)
Zadanie Z
15/12
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
1
oraz x
1
≤
1
x
2
≥
0
oraz x
2
≤
0
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
1
1
1
x
2
0
0
0
x
3
0,57
0
100
Z
max
10,43
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
9/6
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
2
x
2
≥
2
oraz x
2
≤
2
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
2
0
2
x
2
2
2
2
x
3
0,28
0
100
Z
max
15,71
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
16/9
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
2
x
2
≥
2
oraz x
2
≤
2
x
3
≥
0
oraz x
3
≤
0
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
2
0
2
x
2
2
2
2
x
3
0
0
0
Z
max
12
×
×
Lista zada
ń
do podziału:
Z
13/10
; Z
14/12
;
Z
16/9
→
Z
13/10
(15,28) (14,85)
(12)
Zadanie Z
17/9
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
2
x
2
≥
2
oraz x
2
≤
2
x
3
≥
1
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
Zadanie
0
2
x
2
sprz.
2
2
x
3
1
100
Z
max
---
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
13/10
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
1
x
2
≥
1
oraz x
2
≤
1
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
1
0
1
x
2
1
1
1
x
3
0,71
0
100
Z
max
15,28
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
18/13
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
1
x
2
≥
1
oraz x
2
≤
1
x
3
≥
0
oraz x
3
≤
0
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
1
0
1
x
2
1
1
1
x
3
0
0
0
Z
max
6
×
×
Lista zada
ń
do podziału:
Z
14/12
;
Z
16/9
;
Z
18/13
→
Z
14/12
(14,85)
(12) (6)
Zadanie Z
19/13
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
1
x
2
≥
1
oraz x
2
≤
1
x
3
≥
1
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
Zadanie
0
1
x
2
sprz.
1
1
x
3
1
100
Z
max
---
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
14/12
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
0
x
2
≥
0
oraz x
2
≤
0
x
3
≥
0
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
0
0
0
x
2
0
0
0
x
3
1,14
0
100
Z
max
14,85
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
20/14
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
1
x
2
≥
1
oraz x
2
≤
1
x
3
≥
0
oraz x
3
≤
1
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
0
0
1
x
2
0
1
1
x
3
1
0
1
Z
max
13
×
×
Lista zada
ń
do podziału:
Z
16/9
;
Z
18/13
;
Z
18/13
(12) (6) (13)
Zadanie Z
21/14
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
1
x
2
≥
1
oraz x
2
≤
1
x
3
≥
2
oraz x
3
≤
100
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
Zadanie
0
1
x
2
sprz.
1
1
x
3
2
100
Z
max
---
×
×
Programowanie całkowitoliczbowe - przykład
Zadanie Z
20/14
F(x) = F(x
1
,x
2
) = 3x
1
+ 3x
2
+ 13x
3
→
max
-3x
1
+ 6x
2
+ 7x
3
≤
8
6x
1
- 3x
2
+ 7x
3
≤
10
x
1
≥
0
oraz x
1
≤
1
x
2
≥
1
oraz x
2
≤
1
x
3
≥
0
oraz x
3
≤
1
x
1
, x
2
, x
3
∈
C
Z
1/-
R*
Granice
x
1
0
0
1
x
2
0
1
1
x
3
1
0
1
Z
max
13
×
×
Z
1/-
(18)
Z
2/1
(17,95)
Z
3/1
(sprz.)
Z
4/2
(17,61)
Z
5/2
(aprz.)
Z
6/4
(17,52)
Z
7/4
(sprz.)
Z
8/6
(17,19)
Z
9/6
(15,71)
Z
10/8
(17,09)
Z
11/8
(10,85)
Z
12/10
(16,76)
Z
13/10
(15,28)
Z
14/12
(14,85)
Z
15/12
(10,43)
Z
20/14
(13)
Z
21/14
(sprz.)
Z
16/9
(12)
Z
17/9
(sprz.)
Z
18/10
(6)
Z
19/10
(sprz.)
x
1
x
1
x
2
x
2
x
2
x
2
x
1
x
1
x
1
x
1
x
3
x
3
x
2
x
2
x
1
x
1
x
3
x
3
x
3
x
3