Bài giảng Chương 1: Bài toán quy hoạch rời rạc

ến 
nay phương pháp này với nhiều cải tiến khác nhau vẫn là công cụ chủ yếu để giải quyết 
bài toán đề ra. 
 2.7. Bài toán với chi phí cố định 
 Xét bài toán tối ưu có dạng sau: 
n
j 1 2
j=1
min f(x)= f ( ) : ( , ,..., )j nx x x x x D
 = ∈  ∑ 
trong đó nD R+⊂ là một tập lồi đóng và: 
Bùi Thế Tâm I.6 Quy hoạch rời rạc 
0
( ) ( 1,2,..., )
0 0
+ >= = =
j j j j
j j
j
d c x khi x
f x j n
khi x
Giả thiết 0jd > với mọi 1, 2,...,j n= . Các số jd thường được hiểu là các chi phí cố 
định cần thiết để đưa phương thức sản xuất j vào hoạt động, nó không phụ thuộc vào 
cường độ sử dụng của phương thức này ( )jx . 
 Giả sử đã biết jp là cận trên của biến ( )jx , tức là: 
{ }jax x : , 1, 2,...,jp m x D j n≥ ∈ = 
Khi đó ta có thể đưa bài toán trên về bài toán tương đương với nó dạng: 
{ }
1
( ) min
,0 , 0,1 , 1, 2,...,
n
j j j j
j
j j j j
c x d y
x D x p y y j n
=
+ →
∈ ≤ ≤ ∈ =
∑
 2.8. Bài toán với ràng buộc dạng lựa chọn 
 Cho hai hàm số ( )g x và ( )h x bị chặn trên trên tập hợp D . Nếu ta đòi hỏi phải có 
hoặc ( ) 0g x ≤ hoặc ( ) 0h x ≤ với mọi x D∈ , thì điều này có thể diễn đạt bằng cách đưa 
thêm vào một biến số nhận giá trị 0-1. Ký hiệu gu và hu là các cận trên của hàm ( )g x 
và ( )h x trên tập D ( ( ) gg x u≤ , ( ) hh x u≤ , x D∀ ∈ ). Khi đó điều kiện trên sẽ được thoả 
mãn khi và chỉ khi: 
{ }
( )
( ) (1 )
0,1
g
h
g x u
h x u
δ
δ
δ
≤ ≤ − ∈
 Ví dụ 1. Điều kiện bù trong quy hoạch toàn phương 
1
0
n
j j
j
x y
=
=∑ (với 0, 0, 1,2,...,j jx y j n≥ ≥ = ) 
có thể thay thế bằng n cặp ràng buộc dạng lựa chọn: 
0jx ≤ hay 0, 1,2,...,jy j n≤ = (với 0, 0, 1, 2,...,j jx y j n≥ ≥ = ). 
 Giả sử đã biết cận trên jp của biến jx và cận trên jq của biến jy . Khi đó bằng 
cách đưa vào các biến jz nhận giá trị 0-1, ta có thể đưa n cặp ràng buộc dạng lựa chọn 
nói trên về dạng: 
{ }, (1 ), 0,1j j j j j j jx p z y q z z≤ ≤ − ∈ (với 0, 0, 1, 2,...,j jx y j n≥ ≥ = ). 
 Ví dụ 2. Khi quyết định phương thức sản xuất sản phẩm mới ta thường gặp tình 
huống sau: hoặc là không sản xuất sản phẩm j ( jx =0), hoặc là nếu chấp nhận sản xuất 
nó thì phải sản xuất với số lượng không ít hơn jd ( j jx d≥ ), với jd là số lượng sản 
phẩm loại j tối thiểu cần sản xuất để bù lại được các chi phí cần bỏ ra khi đưa phương 
Bùi Thế Tâm I.7 Quy hoạch rời rạc 
thức sản xuất sản phẩm mới này vào hoạt động (khi đó mới có lãi). Tức là ta gặp ràng 
buộc dạng lựa chọn: 
0 0j j jd x hay x− ≤ ≤ 
Giả sử đã biết cận trên jp của biến jx trong bài toán trên. Khi đó ta đưa vào biến 0-1 
1iy = nếu chấp nhận sản xuất sản phẩm j , và bằng 0 nếu ngược lại. Ta có thể đưa ràng 
buộc dạng lựa chọn nói trên về hệ ràng buộc tương đương sau: 
{ }, 0,1j j j j j jd y x p y y≤ ≤ ∈ 
 2.9. Bài toán pha cắt nguyên vật liệu 
 Trong thực tế ta thường phải cắt những vật liệu dài (thanh thép, gỗ, ống nước) 
thành những đoạn nhỏ có độ dài cho trước với số lượng nhất định để sử dụng. Nên cắt 
như thế nào để đỡ lãng phí vật liệu nhất. 
 Ví dụ. Một công trường xây dựng có những thanh thép dài 6m, cần cắt thành 40 
đoạn dài 2,5m và 60 đoạn dài 1,6m, nên như thế nào để đỡ lãng phí vật liệu nhất. 
 Ta có 3 cách cắt như sau: 
Mẫu 1: 2 đoạn 2,5m, thừa 1 m. 
Mẫu 2: 1 đoạn 2,5m và 2 đoạn 1,6n, thừa 0,3m. 
Mẫu 3: 3 đoạn 1,6m, thừa 1,2m. 
Gọi 1 2 3, ,x x x là số thanh cần cắt theo mẫu 1, 2, 3 tương ứng, ta có bài toán quy hoạch 
rời rạc sau: 
1 2 3
1 2
2 3
1 2 3
0.3 1.2 min
2 40
2 3 60
0 , ,
x x x
x x
x x
x x x Z
+ + →
+ =
+ =
≤ ∈
 Tổng quát, ký hiệu: ija là số đoạn loại i thu được khi cắt theo mẫu j , ib là số 
đoạn loại i cần có, jc là dẻo thừa khi cắt theo mẫu j , jx là số thanh thép cắt theo mẫu 
j . Ta được bài toán quy hoạch rời rạc: 
1
1
min
, 1, 2,...,
0 , 1, 2,...,
n
j j
j
n
ij j i
j
j
c x
a x b i m
x Z j n
=
=
→
= =
≤ ∈ =
∑
∑ 
 2.10. Bài toán sản xuất đầu tư 
 Trong thực tế, tất cả các nhà đầu tư vào sản xuất đều gặp bài toán : có m loại tài 
nguyên cần dùng để sản xuất ra n loại sản phẩm. Các tài nguyên này có thể bị tiêu hao 
trong quá trình sản xuất hoặc được tăng thêm nhờ thực hiện một trong p dự án đầu tư 
phát triển sản xuất. 
Bùi Thế Tâm I.8 Quy hoạch rời rạc 
 Cho biết: 
jx là số lượng sản phẩm loại j được sản xuất. 
jc lợi nhuận thu được nếu một sản phẩm loại j được sản xuất. 
0b là tổng số tiền nhà đầu tư có thể đem ra để đầu tư vào sản xuất (thực hiện các 
dự án). 
ib là lượng tài nguyên i hiện có trước khi thực hiện các đầu tư. 
ija là số tài nguyên i cần để sản xuất ra một sản phẩm j . 
kd là chi phí cần cho loại dự án đầu tư k . 
ikg là lượng tài nguyên i được tăng thêm nếu dự án đầu tư k được thực hiện. 
 Ta đưa vào một biến 0-1: ky =1 nếu dự án được dùng, và bằng 0 nếu trái lại. 
 Dạng toán học của bài toán là: 
{ }
1
0
1
1 1
ax
, 1, 2,...,
0 , 1, 2, ,
0,1 , 1, 2, ,
n
j j
j
p
k k
k
pn
ij j i ik k
j k
j
k
c x m
d y b
a x b g y i m
x Z j n
y k p
=
=
= =
→
≤
≤ + =
≤ ∈ =
∈ =
∑
∑
∑ ∑
 2.11. Bài toán chọn địa điểm đặt nhà máy 
 Đây cũng là một bài toán đầu tư, nhưng phức tạp hơn so với bài toán sản xuất - 
đầu tư. Cái khó không phải chỉ vì các chi phí đầu tư được tính đến mà còn vì có các chi 
phí khác phụ thuộc vào địa điểm đặt nhà máy, cụ thể là chi phí vận chuyển. Cũng còn 
một khó khăn nữa, đó là chi phí đầu tư trả một lần, còn chi phí vận chuyển thì xuất hiện 
thường xuyên. Để làm cho chi phí này có thể so sánh được với nhau thì phải xét thêm 
các chi phí vận chuyển trong các thời kỳ khác nhau, tất nhiên là quy đổi so với thời kỳ 
đầu. Nói một cách khác, cần thêm vào một hệ số nhân thích hợp đối với các chi phí vận 
chuyển. 
Ta ký hiệu: 
P là số địa điểm thích hợp đặt nhà máy. 
N là số các nhà máy khác nhau có thể xây dựng ( N P≤ ), mỗi địa điểm đặt nhiều 
nhất là một nhà máy. 
M là số các vật phẩm khác nhau được sản xuất hay tiêu dùng. 
isa là lượng vật phẩm i được sản xuất (nếu is 0a > ), hay tiêu dùng (nếu is 0a < ) ở 
nhà máy s ( 1, 2,..., ; 1,2,...,i M s N= = ) 
Bùi Thế Tâm I.9 Quy hoạch rời rạc 
ib là nhu cầu về vật phẩm i do các nhà máy sản xuất (nếu 0ib > ), hay do các nhà 
máy tiêu dùng (nếu 0ib < ). 
psd là chi phí lắp đặt nhà máy s tại địa điểm ( 1, 2,..., )p p P= . 
pqc là chi phí vận chuyển một đơn vị hàng giữa các địa điểm p và q . 
stf là lượng hàng cần vận chuyển (trong một thời kỳ) từ nhà máy s tới nhà máy 
t . 
λ là hệ số chuyển đổi làm cho chi phí vận chuyển so sánh được với chi phí đầu 
tư. 
psx là biến xác định vị trí, nhận giá trị 1 hay 0 tuỳ thuộc vào nhà máy s có đặt tại 
vị trí p hay không. 
Bài toán đặt ra là cần xác định địa điểm đặt các nhà máy sao cho tổng chi phí xây 
dựng và vận chuyển hàng là nhỏ nhất. Ta đi đến bài toán quy hoạch nguyên phi tuyến: 
{ }
1 1 1 1 1 1
1 1
1
min
, 1,2,...,
1, 1, 2,...,
0,1 , 1, 2,..., ; 1,2,...,
P N P P N N
ps ps pq st ps qt
p s p q s t
P N
is ps i
p s
N
ps
s
ps
d x c f x x
a x b i M
x p P
x p P s N
λ
= = = = = =
= =
=
+ →
≥ =
≤ =
∈ = =
∑∑ ∑∑∑∑
∑∑
∑
 2.12. Tìm tập ổn định trên đồ thị 
 Cho đồ thị G , có n đỉnh, E là tập các cạnh của đồ thị. Tìm tập đỉnh có nhiều 
phần tử nhất trên đồ thị sao cho không có hai đỉnh nào kề nhau. 
 Ta thêm vào một biến 0-1: jx =1 nếu đỉnh j được chọn, và bằng 0 nếu trái lại. 
Dạng toán học của bài toán là: 
{ }
1
ax
1 ( , )
0,1 , 1, 2, ,
n
j
j
i j
j
x m
x x i j E
x j n
=
→
+ ≤ ∀ ∈
∈ =
∑
 Nếu đỉnh j có trọng số jc >0 thì ta có bài toán tìm tập ổn định có trọng số lớn 
nhất: 
{ }
1
ax
1 ( , )
0,1 , 1, 2,
n
j j
j
i j
j
c x m
x x i j E
x j n
=
→
+ ≤ ∀ ∈
∈ =
∑
Bùi Thế Tâm I.10 Quy hoạch rời rạc 
 2.13. Bài toán tìm sắc tố 
 Tìm số màu tối thiểu để tô mọi đỉnh của đồ thị sao cho hai đỉnh kề nhau có màu 
khác nhau. Giả sử đồ thị ( , )G V E= , V là tập n đỉnh, E là tập m cạnh. Cần tối đa n 
màu nếu đồ thị có n đỉnh. Đặt hai biến 
ky =1 nếu màu k được dùng, và bằng 0 nếu trái lại. 
jkx =1 nếu đỉnh j được tô màu k , và bằng 0 nếu trái lại. 
 Dạng toán học của bài toán là: 
{ }
1
1
min
1, 1,2,...,
, ( , ) , 1, 2, ,
, 0,1 , , 1,2, ,
n
k
k
n
jk
k
ik jk k
k jk
y
x j n
x x y i j E k n
y x k j n
=
=
→
= =
+ ≤ ∀ ∈ =
∈ =
∑
∑
trong đó, ràng buộc thứ nhất biểu thị mỗi đỉnh chỉ được tô bằng một màu, ràng buộc thứ 
hai biểu thị hai đỉnh kề nhau không được tô cùng một màu. 
 2.14. Bài toán tìm chỉ số màu 
 Hãy tìm số màu tối thiểu để tô mọi cạnh của đồ thị G sao cho hai cạnh kề nhau 
không được tô cùng màu. Giả sử đồ thị G có n đỉnh, m cạnh, E là tập các cạnh của 
đồ thị. Tối đa cần dùng m màu để tô m cạnh. Ký hiệu 
ky =1 nếu màu k được dùng, và bằng 0 nếu trái lại. 
jkx =1 nếu cạnh j được tô màu k , và bằng 0 nếu trái lại. 
ija =1 nếu đỉnh i là mút cuối của cạnh j và bằng 0 nếu trái lại. 
 Dạng toán học của bài toán là: 
{ }
1
1
1
min
1, 1,2,...,
, 1, 2,..., ; 1, 2,...,
, 0,1 , , 1,2, ,
m
k
k
m
jk
k
m
ij jk k
j
k jk
y
x j m
a x y k m i n
y x j k m
=
=
=
→
= =
≤ = =
∈ =
∑
∑
∑
trong đó, ràng buộc thứ nhất biểu thị mỗi cạnh chỉ tô một màu, ràng buộc thứ hai biểu 
thị không tô cùng một màu các cạnh có chung một đỉnh. 
 2.15. Bài toán phủ đỉnh 
 Cho đồ thị ( , )G V E= , V là tập n đỉnh, E là tập m cạnh. Tìm số đỉnh ít nhất của 
đồ thị G sao cho mỗi cạnh có ít nhất một đầu mút đã được chọn. 
Bùi Thế Tâm I.11 Quy hoạch rời rạc 
 Ứng dụng: tìm cách đặt các trạm quan sát (hoặc cửa hàng, trạm điện thoại, trung 
tâm dịch vụ) tại các ngã ba, ngã tưsao cho quan sát được mọi tuyến đường trong khu 
phố với số trạm ít nhất. 
 Ta đưa vào một biến 0-1 là jx =1 nếu đỉnh j được chọn, và bằng 0 nếu trái lại. 
Dạng toán học của bài toán: 
{ }
1
min
1, ( , )
0,1 ; 1,2,...,
n
j
j
i j
j
x
x x i j E
x j n
=
→
+ ≥ ∀ ∈
∈ =
∑
 2.16. Bài toán phủ cạnh 
 Cho đồ thị ( , )G V E= , V là tập n đỉnh, E là tập m cạnh. Tìm số cạnh ít nhất của 
đồ thị G sao cho mỗi đỉnh thuộc V đều là đầu mút của ít nhất một cạnh đã chọn