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