Chương 7
Quy Hoạch Nguyên –
Quy Hoạch Động
2
C7. Quy Hoạch Nguyên – Quy Hoạch Động
1. Quy Hoạch Nguyên
2. Quy Hoạch Động
3
1. Quy Hoạch Nguyên
1.1. Giới thiệu BT quy hoạch nguyên

Xét BT QHTT ở dạng chuẩn
∑
=
=
n
1j
jj
xcMin Z
n , 2, 1,j0x
m , 2, 1,i0 bxa
j
n
1j
ijij
=∀≥
=∀≥=
∑
=
:RB


.

VĐ: người ngày phải lựa chọn sao cho giá trị của các mặt hàng mang
theo là tối đa trong điều kiện giới hạn trọng lượng mang theo là K.

Giả sử Biến QĐ của BT
∑
=
=
n
1j
jj
xcMax Z



=
chọn được khôngj mặt hàng nếu0
chọn được j mặt hàng nếu1
x
j10x
Kxa
j
n
1j
jj
∀=
<
∑
=

i
(x) ≤ 0; i = 1, 2, …, m và chỉ có k RB thỏa mãn.
Sử dụng m biến nguyên 0-1 y
i
; i = 1, 2, …, m và m số dương đủ
lớn M
i
; i = 1, 2, …, m.
m1,2, ,i1 0y
kmy yy
m1,2, ,iyM(x)g
i
m21
iii
==
−=+++
=≤
hoaëc
7
1. Quy Hoạch Nguyên (tt4)
VD 7.3: BT lập thứ tự công việc (Sequencing Problem)

Giả sử Thời gian để hoàn thành công việc i là p
i
và Thời điểm mà ở đó công
việc i được bắt đầu là t
i
.

So sánh giữa 2 công việc i và j, có 2 TH

hoaëc=
≥−+−
≥−+
8
1. Quy Hoạch Nguyên (tt5)
VD 7.4: BT thiết lập kho (Warehouse Problem)
y
i
= 1 nếu kho được thiết lập tại địa điểm i, nếu không thì y
i
= 0; i = 1,2,…,m.
f
i
: Chi phí thiết lập kho hàng tại địa điểm i.
x
ij
: Lượng hàng vận chuyển từ kho tại địa điểm i đến điểm tiêu thụ j; j = 1,2,…,n.
c
ij
: Chi phí vận chuyển 1 đơn vị hàng hóa từ kho hàng tại điểm i đến điểm j.
d
j
: Nhu cầu của điểm tiêu thụ j.
s
i
: Khả năng cung cấp của kho hàng được thiết lập tại địa điểm i.
i1hay 0y
ji,0x
jdx
iysx

VD 7.5: BT người giao hàng (Traveling Salesman Problem)
Người giao hàng phải giao hàng cho n địa điểm C
1
, C
2
,…, C
n
hàng ngày. Bắt đầu
từ C
1
và phải quay trở lại đây sau khi làm xong công việc. C
ij
là khoảng cách
giữa 2 điểm giao hàng i và j.
BT: Người giao hàng phải lựa chọn đường đi như thế nào để tổng quảng đường
là ngắn nhất.
n2,3, ,inguyênhay 0u
ji,1hay 0x
ji n;2,3, ,ji,1-nnxuu
j1x
i1x
i
ij
ijji
n
1i
ij
n
1j
ij

n
1i
ij
n
1j
ij
=∀≥
∀=
≠=−≤+−
∀=
∀=
∑
∑
∑∑
=
=
= =
nguyeânvaø
hoaëc
:RB
xcMin
n
1i
n
1j
ijij
11
1. Quy Hoạch Nguyên (tt8)
1.3. Phương pháp giải BT quy hoạch nguyên
VD 7.6: Xét BT QHTT

= 5; x
2
= 3).
12
1. Quy Hoạch Nguyên (tt9)
1.3. Phương pháp giải BT quy hoạch nguyên

Giải BT quy hoạch nguyên khá phức tạp vì tùy
thuộc vào Bản chất BT (thuần túy, hỗn hợp hay 0-
1), Số lượng các biến nguyên và Cấu trúc đặc thù.

Có 2 pp giải BT quy hoạch nguyên:
•
Giải thuật mặt cắt (Cutting Plane Algorithm)
•
Giải thuật phân nhánh và chặn (Branch and Bound
Algorithm).
13
2. Quy Hoạch Động

BT quy hoạch động là 1 dạng BT tối ưu hóa, mà trong đó việc tìm ra
giải pháp tối ưu của BT được thực hiện thông qua việc tìm nghiệm tối
ưu của 1 chuỗi các BT con có liên quan đến BT ban đầu.

Quy hoạch động là 1 pp giải quyết tối ưu theo từng giai đoạn, thích
hợp với các QĐ theo tuần tự thời gian hoặc không gian.

BT quy hoạch động cho biết Nghiệm tối ưu theo từng giai đoạn.
Việc liên kết các giai đoạn của BT quy hoạch động được thực hiện
thông qua phép đệ quy. Tùy thuộc vào Bản chất của BT mà phương


Giả sử
•
f
i
: Thời gian di chuyển nhỏ nhất từ nút i đến nút 9.
•
t
ij
: Thời gian di chuyển trên cung (i, j).

Trên cung (i, j) bất kỳ,
Do vậy:

Đường đi ngắn nhất từ i đến 9, buộc phải qua 1 nút
nào đó, nên
9i}f{t minf
jij
j
i
≠+≤
9i}f{t minf
jij
j
i
≠+=
j 9;iftf
jiji
∀≠+≤
16

7
= 7 + 3 = 10
1 94 8
2
3 6
5 7
1
2
6
3
12
7
4
4
3
7
7
15
15
10
3
15
015
107
min
ft
ft
minf
969
868

3
12
7
4
4
3
7
7
15
15
10
3
17
154
143
min
ft
ft
minf
636
434
3
=






+













+
+
+
+
=
















+
+
=
19
172
201
min
ft
ft
minf
313
212
1
=






+
+
=






iij
i
j
≠+≤
1j}f{t minf
iij
i
j
≠+=
i 1;jftf
iijj
∀≠+≤
19
2. Quy Hoạch Động (tt3)
Giải BT bằng đệ quy xuôi dòng
f
1
= 0
f
2
= t
12
+ f
1
= 1 + 0 = 1
f
3
= t
13
+ f

224
4
=






+
+
=






+
+
=
9
54
112
min
ft
ft
minf
445
225

557
447
7
=






+
+
=






+
+
=
12
67
57
min
ft
ft
minf
668

889
779
669
9
=










+
+
+
=










+






+
+
=
1 94 8
2
3 6
5 7
1
2
6
3
12
7
4
4
3
7
7
15
15
10
3
END
21