VIỆN KHOA HỌC VÀ CÔNG NGHỆ VIỆT NAM
VIỆN TOÁN HỌC





PGS.TS. BÙI THẾ TÂM









QUY HOẠCH RỜI RẠC


BÀI GIẢNG CAO HỌC

HÀ NỘI 10-2008


Bùi Thế Tâm i Quy hoạch rời rạc


LỜI NÓI ĐẦU
Tài liệu này là các Bài giảng của môn Quy hoạch rời rạc thuộc Trung tâm đào tạo
sau đại học, Viện Toán học, Viện Khoa học và Công nghệ Việt nam trong các năm
2006, 2007 và 2008. Đây là tài liệu đầu tiên được viết bằng tiếng Việt trình bày một
cách hệ thống về Quy hoạch rời rạc với cơ sở lý thuyết chặt chẽ, chứng minh tính hữu
hạn của các thuật toán Gomory, hơn nữa còn đưa ra chương trình nguồn viết bằng C cho
các thuật toán.
Kiến thức chuẩn bị để tiếp thu giáo trình này là lý thuyết căn bản về quy hoạch
tuyến tính và phương pháp đơn hình [9], lập trình bằng ngôn ngữ C++ [11], bảng tính
điện tử Microsoft Excel [12].
Tài liệu gồm bảy chương. Chương 1 trình bày các bài toán phát sinh trong thực
tiễn dẫn đến các bài toán quy hoạch rời rạc, phát biểu bài toán quy hoạch rời rạc tổng
quát. Các bài tập ở cuối chương 1 có thể dùng lệnh Solver trong Microsoft Excel để
giải, hướng dẫn lệnh này cho trong tài liệu [12] hoặc[13].
Trong Chương 2 nêu những khái niệm cơ bản về quy hoạch tuyến tính, phương

pháp đơn hình bình thường, phương pháp đơn hình đối ngẫu từ vựng và chương trình
máy tính viết bằng C++, và khái niệm về bài toán quy hoạch tuyến tính nguyên.
Chương 3 trình bày tư tưởng phương pháp cắt, thuật toán Gomory thứ nhất và
chứng minh sự hội tụ của nó (tài liệu gốc trong [1], [2]), chương trình máy tính của
thuật toán Gomory thứ nhất.
Chương 4 xét hai thuật toán: thuật toán Gomory thứ hai dùng để giải bài toán quy
hoạch tuyến tính nguyên bộ phận [3], thuật toán Dalton - Llewellyn dùng để giải bài
toán quy hoạch tuyến tính với các biến nhận giá trị rời rạc [4], chương trình máy tính
của hai thuật toán này.
Chương 5 trình bày thuật toán Gomory thứ ba nhằm xây dựng các lát cắt đảm bảo
tất cả các Bảng đơn hình ở mỗi bước đều có tất cả các phần tử là nguyên [5], [6],
chương trình máy tính của thuật toán Gomory thứ ba.
Chương 6 trình bày tư tưởng của phương pháp nhánh cận, phương pháp Land
A.H và Doig A.G giải bài toán qui hoạch nguyên [7], phương pháp Little J.D, Murty
K.G, Sweeney D.W và Karen C giải bài toán người du lịch [8].
Các tài liệu gốc [1]-[8] được A.A. Korbut, Iu. Iu. Phinkenstein trình bày lại trong
cuốn sách [10]. Năm chương trình bằng ngôn ngữ C trong tài liệu này về Phương pháp
đơn ngẫu từ vựng, ba thuật toán Gomory, thuật toán Dalton đều do chính tác giả lập.
Bạn đọc quan tâm tới lập trình bằng Pascal cho các bài toán tối ưu của Quy hoạch tuyến
tính, Quy hoạch phi tuyến và Quy hoạch rời rạc có thể tham khảo tài liệu [14].
Các trường Đại học, các cơ sở đào tạo có nhu cầu giảng dạy môn này, hoặc hướng
dẫn giảng viên để giảng dạy môn này, hoặc bạn đọc muốn góp ý về giáo trình này xin
vui lòng liên hệ với tác giả theo địa chỉ: Bùi Thế Tâm, Viện Toán học, Viện Khoa học
và Công nghệ Việt Nam, 18 Hoàng Quốc Việt, Cầu giấy, Hà nội ; địa chỉ email:



Hà Nội, ngày 4 tháng10 năm 2008
Bùi Thế Tâm ii Quy hoạch rời rạc



TÀI LIỆU THAM KHẢO
1. Gomory R.E. An algorithm for integer solutions to linear programs. Recent
Advances Math. Program. New York - San Francisco - Toronto - London, McGraw-Hill
Book Co., Inc., 1963, 269-302.
2. Gomory R.E. Outline of an algorithm for integer solution to linear programs.
Bull. Amer. Math. Soc., 1958, 64, N5, 275-278.
3. Gomory R.E. An algorithm for the mixed integer problem. Rand. Corp., P-
1885, Santa Monica, California, February 22, 1960.
4. Dalton R.E, Llewellyn R.W. An extension of the Gomory mixed-integer
algorithm to mixed-discrete variable. Manag. Sci., 1966, 12, N7, 562-575.
5. Gomory R.E. An all-integer integer programming algorithm. IBM Research
Center, 1960, January, Research Report RC-189.
6. Gomory R.E. An all-integer integer programming algorithm. In "Industrial
scheduling", Englewood Cliffs, New Jersey, Prentice Hall, 1963, ch. 13.
7. Land A.H, Doig A.G. An automatic method of solving discrete programming
problems. Econometrica, 1960, 28, N3, 497-520.
8. Little J.D.C,Murty K.G, Sweeney D.W, Karel C. An algorithm for the traveling
salesman problem. Operat. Res., 1963, 11, N6, 972-989.
9. Bùi Thế Tâm, Trần Vũ Thiệu. Các phương pháp tối ưu hóa. NXB GTVT, 1998,
408 trang
10. A.A. Korbut, Iu. Iu. Phinkenstein. Quy hoạch rời rạc (tiếng Nga). NXB Khoa
học, Mascva, 1969, 368 trang
11. Bùi Thế Tâm. Ngôn ngữ C và lập trình hướng đối tượng. NXB GTVT, 2006,
240 trang.
12. Bùi Thế Tâm. Giáo trình Windows 2000, Word 2000, Excel 2000, Powerpoint
2000. NXB GTVT, 2002.
13. Bùi Thế Tâm. Giải các bài toán tối ưu và thống kê trên Microsoft Exel. Công
bố trên
, phần Công nghệ thông tin, 2007.

14. Bùi Thế Tâm. Turbo Pascal: lý thuyết cơ bản, bài tập, những chương trình
mẫu trong khoa học kỹ thuật và kinh tế. NXB GTVT, 1993, 460 trang.

VÀI NÉT VỀ TÁC GIẢ
B.T. Tâm sinh năm 1948 tại Hiệp Hoà, Bắc Giang; hiện làm việc tại Phòng Tối ưu
và Điều khiển thuộc Viện Toán học, Viện Khoa học và Công nghệ Việt nam; bảo vệ
Tiến sỹ tháng 5/1978 tại Viện Hàn lâm Khoa học Liên xô; nhận học hàm Phó giáo sư
tháng 7/1996.
Bùi Thế Tâm iii Quy hoạch rời rạc

MỤC LỤC
Chương 1. Bài toán quy hoạch rời rạc I.1
1. Định nghĩa bài toán I.1
2. Các bài toán thực tế dẫn đến bài toán quy hoạch rời rạc I.2
Chương 2. Những khái niệm mở đầu II.1
1. Những khái niệm cơ bản về quy hoạch tuyến tính II.1
2. So sánh theo nghĩa từ vựng II.3
3. Bảng đơn hình, các phương án và giả phương án II.4
4. Phương pháp đơn hình II.5
5. Phương pháp đơn hình đối ngẫu từ vựng II.6
6. Bài toán quy hoạch tuyến tính nguyên II.16
Chương 3. Thuật toán Gomory thứ nhất III.1
1. Tư tưởng phương pháp cắt III.1
2. Thuật toán Gomory thứ nhất III.5
3. Tính hữu hạn của thuật toán Gomory thứ nhất III.9
4. Giải ví dụ số III.11
5. Chương trình máy tính III.15
Bài tập III.23
Chương 4. Thuật toán Gomory thứ hai IV.1
1. Lược đồ logic của thuật toán IV.1

2. Thuật toán Gomory thứ hai IV.2
3. Thuật toán Dalton và Llewellyn IV.20
Bìa tập IV.33
Chương 5. Thuật toán Gomory thứ ba V.1
1. Ảnh hưởng sai số làm tròn và tư tưởng của thuật toán Gomory thứ ba V.1
2. Xây dựng lát cắt đúng nguyên, thuật toán Gomory thứ ba V.3
3. Chương trình máy tính V.13
Bài tập V.22
Chương 6. Thuật toán nhánh và cận VI.1
1. Tư tưởng của phương pháp nhánh và cận VI.1
2. Phương pháp Land và Doig giải bài toán quy hoạch nguyên VI.3
3. Phương pháp nhánh cận giải bài toán người du lịch VI.6
Bài tập VI.19

Bùi Thế Tâm I.1 Quy hoạch rời rạc

Chương 1
BÀI TOÁN QUY HOẠCH RỜI RẠC

1. ĐỊNH NGHĨA BÀI TOÁN QUY HOẠCH RỜI RẠC
Trong các bài toán quy hoạch tuyến tính, các biến số có thể nhận những giá trị
thực không âm. Tuy nhiên, trong thực tiễn thường gặp các bài toán mà các biến số chỉ
có thể nhận một số hữu hạn hay đếm được giá trị, thường là các giá trị nguyên. Chẳng
hạn sẽ là vô nghĩa khi đưa ra câu trả lời: cần sản xuất nửa cái bàn hay cần thuê 2,7 cái ô
tô để vận chuyển hàng hoá…Trong một số bài toán, chẳng hạn bài toán vận tải với các
lượng hàng cung và cầu là các số nguyên, song nhiều bài toán khác thì không phải như
vậy. Vì thế trong chương này sẽ đề cập đến nội dung và phương pháp giải các bài toán
tối ưu trên lưới các điểm nguyên hay trên các tập rời rạc, gọi tắt là bài toán quy hoạch
rời rạc hay bài toán quy hoạch nguyên.
Bài toán quy hoạch rời rạc có dạng sau:

Tìm cực đại của hàm
(, )
f
xy
phụ thuộc hai nhóm biến x và y với các ràng buộc
có dạng:
( , ) 0, 1,2, ,
i
g
xy i m x D
≤
=∈
trong đó,
12 12
( , , , ), ( , , , ), 0, 0
pq
xxx x yyy yp q==>≥
,
D là tập hữu hạn các véc tơ
p - chiều, còn
,
i
f
g
là những hàm cho trước của
n
biến số (
npq
=
+

).
Nếu ,
i
f
g là các hàm tuyến tính và
D
là lưới các điểm nguyên, thì ta có bài toán
quy hoạch nguyên tuyến tính, còn nếu
D là tập các véc tơ
p
thành phần 0 hay 1 thì ta
có bài toán quy hoạch nguyên
01
−
.
Nếu
0q =
, nghĩa là chỉ có các biến rời rạc
12
, , ,
p
x
xx
thì bài toán được gọi là bài
toán
quy hoạch nguyên hoàn toàn. Còn nếu
0q >
thì bài toán được gọi là bài toán
nguyên bộ phận
.

Chú ý
Sở dĩ bài toán quy hoạch rời rạc còn được gọi là bài toán quy hoạch nguyên là vì
bất kỳ bài toán với các biến số chỉ nhận một số hữu hạn giá trị cho trước, đều có thể quy
về bài toán trong đó các biến chỉ nhận các giá trị nguyên. Ví dụ, giả sử biến
x
biểu thị
quy mô công suất của nhà máy điện cần xây dựng chỉ có thể lấy một trong các giá trị
cho trước
12
, , ,
k
aa a (các quy mô công suất tiêu chuẩn). Khi đó bằng cách đặt:
11 2 2

kk
x
au au a u
=
+++,
với
{
}
12
1, 0;1 , 1,2 ,
kj
uu u u j k+++= ∈ =
thì biến rời rạc
x
có thể được thay thế bởi một số biến
j

u chỉ nhận giá trị 0 hay 1, gọi
tắt là biến
01−
hay biến Boolean.

Bùi Thế Tâm I.2 Quy hoạch rời rạc

Tương tự, nếu
{
}
0,1,2, ,
x
k∈
thì ta có thể viết
{
}
12
, 0;1 , 1, 2 ,
kj
x
uu uu j k=+++ ∈ =
nghĩa là bất kỳ bài toán với các biến nguyên bị chặn tuỳ ý, đều có thể quy về bài toán
với các biến
01−
. Điều này cho thấy bài toán quy hoạch nguyên
01−
giữ vai trò quan
trọng trong quy hoạch rời rạc.
2. CÁC BÀI TOÁN THỰC TẾ DẪN TỚI QUY HOẠCH RỜI RẠC
2.1. Bài toán vận tải

Có m kho hàng (điểm phát) chứa một loại hàng hoá, lượng hàng ở kho
i
là
i
a
và
n
nơi tiêu thụ (điểm thu), nhu cầu ở nơi thu là
j
b ,
ij
c là chi phí vận chuyển một đơn vị
hàng từ điểm phát
i đến điểm thu j . Xác định các lượng hàng vận chuyển
ij
x
từ các
điểm phát
i
tới các điểm thu j sao cho tổng chi phí là nhỏ nhất và nhu cầu các điểm
thu được thoả mãn.
Dạng toán học của bài toán là:
ij ij
ij
ij
1
ij
1
ij
11

min
, 1,2, ,
, 1,2, ,
0
.
n
i
j
m
j
i
mn
ij
ij
cx
x
ai m
x
bj n
x
ab
=
=
==
→
==
==
≥
=
∑

∑
∑
∑∑

Nếu các
i
a và
j
b
là nguyên thì đa diện lồi xác định bởi các ràng buộc của bài
toán có mọi đỉnh đều là nguyên. Do đó ta có thể dùng phương pháp đơn hình để giải bài
toán quy hoạch tuyến tính này, lời giải cuối cùng nhận được sẽ là một phương án
nguyên.
Ví dụ. Xét bài toán vận tải có 3 điểm phát và 4 điểm thu với ma trận chi phí như
sau:
2143
6052, (10,25,15), (5,15,20,10)
1482
ij ij
cab


===




Đáp số: trị tối ưu hàm mục tiêu là 115, phương án vận chuyển tối ưu là: x[1,3]=10,
x[2,2]=15, x[2,3]=10, x[3,1]=5, x[3,4]=10
2.2. Bài toán phân việc

Bùi Thế Tâm I.3 Quy hoạch rời rạc

Có n đơn vị sản xuất cần sản xuất n loại sản phẩm,
ij
c
là chi phí cho đơn vị
i
sản
xuất sản phẩm
j
. Hãy phân công mỗi đơn vị sản xuất một sản phẩm để tổng chi phí là
nhỏ nhất.
Dạng toán học của bài toán là:
{}
n
ij ij
1j=1
ij
1
ij
1
ij
min
1, 1,2, ,
1, 1,2, ,
0;1
n
i
n
j

m
i
cx
x
in
x
jn
x
=
=
=
→
==
==
∈
∑∑
∑
∑


Ví dụ có 4 đơn vị sản xuất 4 loại sản phẩm với ma trận chi phí sau:
100000 4000000 800000 550000
200000 3500000 750000 500000
400000 2000000 700000 400000
300000 5000000 600000 450000
Đáp số: trị tối ưu hàm mục tiêu là 3200000 đồng, phương án tối ưu là:
x[1,1]=x[2,4]=x[3,2]=x[4,3]=1.
2.3. Bài toán cái túi
Có một cái túi chứa được nhiều nhất một trọng lượng là b , có n đồ vật cần mang,
đồ vật

j
nặng
j
a
, giá trị của nó là
j
c
. Bài toán đặt ra là cho những đồ vật nào vào túi
để tổng giá trị của nó lớn nhất. Ký hiệu
j
x
là số đồ vật
j
được đưa vào túi. Dạng toán
học của bài toán là:
n
jj
j=1
j
1
jj
max
0,
n
j
j
cx
ax b
x
xZ

=
→
≤
≥∈
∑
∑

Ví dụ. Có một cái túi chứa được nhiều nhất là 62 kg, có 10 đồ vật cần mang
{}
123 4 5678910
123 4567 8910
30 19 13 38 20 6 8 19 10 11 ax
15 12 9 27 15 5 8 20 12 15 62
0,1 , 1,2, ,10
j
x
xxx xxxxxxm
xxxxxxx xxx
xj
+++++++++ →
+++++++++ ≤
∈=

Đáp số: trị tối ưu hàm mục tiêu là 95, phương án tối ưu là (1,1,0,1,0,0,1,0,0,0)
2.4. Bài toán xếp hàng lên tầu
Bùi Thế Tâm I.4 Quy hoạch rời rạc

Một tầu chở hàng có trọng tải T và thể tích
K
, tầu chở n loại hàng, hàng loại j

có số lượng là
j
s
, có trọng lượng là
j
a
, thể tích
j
b
và giá trị sử dụng là
j
c
. Bài toán đặt
ra là cần xác định số lượng hàng loại j cần xếp lên tàu
j
x
để tổng giá trị hàng hoá trên
tầu là lớn nhất.
Dạng toán học của bài toán là:
{}
n
jj
j=1
j
1
j
1
j
max
0,1,2, , , 1, 2, ,

n
j
j
n
j
j
j
cx
ax T
bx K
x
sj n
=
=
→
≤
≤
∈=
∑
∑
∑

Ở đây, không giảm tính tổng quát của bài toán ta có thể giả sử các hệ số ,,,,
jjj
TKa b c
(với mọi j ) đều là các số dương.
2.5. Bài toán xếp hàng vào các công ten nơ rỗng cùng loại
Có n loại hàng hoá cần được xếp lên các công ten nơ rỗng như nhau với tải trọng
của mỗi công ten nơ là
T và dung lượng là

K
. Hàng hoá loại j có trọng lượng
j
a
,
khối lượng
j
b
và số lượng cần vận chuyển là
j
s
(
1,2, ,
j
n
=
). Hãy tìm cách xếp tất cả
số hàng hoá này lên công ten nơ sao cho dùng ít công ten nơ nhất?
Giả sử ta đã biết được
m là số công ten nơ tối đa cần thiết để chở hết số hàng hoá
trên. Chẳng hạn, số
m có thể tìm theo cách: xếp dần các đồ vật lên công ten nơ theo thứ
tự tuỳ ý, cái nọ tiếp cái kia, cho đến khi trọng lượng hay dung tích của công ten nơ đã
dùng hết. Tiếp đó sử dụng công ten nơ tiếp theo…
Gọi
ij
x
là số đồ vật j được chở trên công ten nơ i ,
i
y là biến nhận giá trị 0 hay 1

tuỳ theo có dùng công ten nơ
i hay không.
Dạng toán học của bài toán là:
{}
{}
1
ij
1
ij
1
ij
1
ij
min
, 1, 2, ,
, 1, 2, ,
, 1,2, ,
0,1,2, , , 1, 2, , , 1, 2, ,
0,1 1,2, ,
m
i
i
n
ji
j
n
ji
j
m
j

i
j
i
y
ax Ty i m
bx Ky i m
xs j n
x
si mj n
yim
=
=
=
=
→
≤=
≤=
==
∈==
∈=
∑
∑
∑
∑


Bùi Thế Tâm I.5 Quy hoạch rời rạc

Hai nhóm ràng buộc đầu biểu thị yêu cầu không chuyên chở quá tải trọng và dung
lượng của mỗi công ten nơ được sử dụng ( 1

i
y
=
), còn công ten nơ không sử dụng
(0
i
y = ) cần phải rỗng. Nhóm ràng buộc thứ ba biểu thị mọi đồ vật cần được xếp vào
các công ten nơ.
2.6. Bài toán người du lịch
Cho đồ thị (, ),GVE= V là tập n đỉnh, E là tập n cạnh. Gọi
ij
c là độ dài của
cung nối từ đỉnh i đến đỉnh j, có thể
ij ji
cc
≠
và
ii
c
=
∞
với mọi
i
. Một chu trình
Hamilton là một chu trình sơ cấp mà nó tương đương với việc xuất phát từ một đỉnh bất
kỳ cho trước, đi qua mọi đỉnh khác đúng một lần và trở lại đỉnh xuất phát. Tổng khoảng
cách trên các cạnh trong hành trình đó là độ dài của hành trình đó. Mục tiêu của bài toán
người du lịch là tìm chu trình Hamilton có độ dài ngắn nhất.
Đặt
ij

1x = nếu cung (, )ij đượ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à:
{}
n
ij ij
1j=1
ij
1
ij
1
ij
ij
min
1, 1,2, ,
1, 1,2, ,
0;1 , , 1, 2, ,
1, 2 i j n
n
i
n
j
m
i
ij
cx
xi n
xj n
xijn
uu nx n
=

=
=
→
==
==
∈=
−
+≤− ≤≠≤
∑∑
∑
∑

trong đó
i
u nhận giá trị nguyên hay thực.
Hai tập ràng buộc đầu biểu thị mỗi thành phố được thăm đúng một lần. Ràng buộc
cuối đưa vào để mỗi hành trình của bài toán chỉ chứa duy nhất một chu trình.
Bài toán người du lịch là một bài toán rất quen thuộc và nổi tiếng trong tối ưu rời
rạc. Tuy số phương án của bài toán là hữu hạn (bằng
!n đối với bài toán có n thành
phố) nhưng với
n
cỡ hàng ngàn trở lên thì số phương án này cực kỳ lớn, vì thế cách
duyệt toàn bộ là không thể thực hiện được, mặc dầu có sự trợ giúp của các máy tính cực
mạnh. Little J.D, Murty K.G, Sweeney D.W và Karel C 1963 là những người đầu tiên
sử dụng thành công phương pháp nhánh cận để giải bài toán người du lịch và cho đế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
j12
j=1
min f(x)= f ( ) : ( , , , )
jn
x
xxx x D

=∈


∑

trong đó
n
DR
+
⊂ 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, , )
00
+>


==

=



jjj j
jj
j
dcx khix
f
xjn
khi x

Giả thiết 0
j
d > với mọi 1,2, ,
j
n= . Các số
j
d 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
()
j
x
.
Giả sử đã biết
j
p là cận trên của biến ( )
j
x
, tức là:

{
}
j
ax x : , 1,2, ,
j
p
mxDj 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
jj j j
j
jjjj
cx dy
x
Dxpyy 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à ()hx bị chặn trên trên tập hợp D . Nếu ta đòi hỏi phải có
hoặc
() 0gx≤ hoặc () 0hx ≤ 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
g
u và
h
u là các cận trên của hàm ( )
g
x
và ( )hx trên tập D (()
g
g
xu≤ ,()
h
hx u
≤
,
x
D
∀
∈ ). Khi đó điều kiện trên sẽ được thoả
mãn khi và chỉ khi:
{}
()
() (1 )
0,1
g
h

gx u
hx u
δ
δ
δ
≤


≤
−


∈


Ví dụ 1. Điều kiện bù trong quy hoạch toàn phương
1
0
n
jj
j
xy
=
=
∑
(với 0, 0, 1,2, ,
jj
x
yj n≥≥= )
có thể thay thế bằng

n cặp ràng buộc dạng lựa chọn:
0
j
x ≤ hay 0, 1, 2, ,
j
yj n≤= (với 0, 0, 1, 2, ,
jj
x
yj n≥≥= ).
Giả sử đã biết cận trên
j
p
của biến
j
x
và cận trên
j
q
của biến
j
y
. Khi đó bằng
cách đưa vào các biến
j
z
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,1
jjjjj jj
xpzyq zz≤≤−∈ (với
0, 0, 1, 2, ,
jj
x
yj 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 (
j
x
=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
j
d (
jj
x
d≥ ), với
j
d 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:
00
jj j
dx hayx

−
≤≤

Giả sử đã biết cận trên
j
p
của biến
j
x
trong bài toán trên. Khi đó ta đưa vào biến 0-1
1
i
y = 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,1
jj j jj j
dy x py 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

123
,,
x
xx 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:
123
12
23
123
0.3 1.2 min
240
2360
0,,
xxx
xx
xx
xxx Z
+
+→
+=
+=
≤∈

Tổng quát, ký hiệu:
ij
a là số đoạn loại i thu được khi cắt theo mẫu j ,
i
b là số
đoạn loại
i

cần có,
j
c là dẻo thừa khi cắt theo mẫu j ,
j
x
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
jj
j
n
ij j i
j
j
cx
ax b i m
x
Zj 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:
j
x
là số lượng sản phẩm loại j được sản xuất.
j
c
lợi nhuận thu được nếu một sản phẩm loại j được sản xuất.
0
b
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).
i
b
là lượng tài nguyên
i
hiện có trước khi thực hiện các đầu tư.
ij
a là số tài nguyên i cần để sản xuất ra một sản phẩm j .
k

d là chi phí cần cho loại dự án đầu tư
k
.
ik
g
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:
k
y =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
11
ax
, 1, 2, ,
0,1,2,,
0,1 , 1, 2, ,
n
jj
j
p
kk
k
p
n
ij j i ik k
jk
j

k
cx m
dy b
ax b g y i m
xZ j n
ykp
=
=
==
→
≤
≤+ =
≤∈ =
∈=
∑
∑
∑∑
…
…

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 (
NP
≤
), 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.
is
a 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, ,iMsN==)
Bùi Thế Tâm I.9 Quy hoạch rời rạc

i
b
là nhu cầu về vật phẩm
i
do các nhà máy sản xuất (nếu
0
i
b >
), hay do các nhà

máy tiêu dùng (nếu 0
i
b < ).
p
s
d là chi phí lắp đặt nhà máy
s
tại địa điểm ( 1, 2, , )
p
pP
=
.
p
q
c
là chi phí vận chuyển một đơn vị hàng giữa các địa điểm
p
và
q
.
s
t
f
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ư.

p
s
x
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:
{}
11 1111
11
1
min
, 1, 2, ,
1, 1, 2, ,
0,1 , 1, 2, , ; 1,2, ,
PN PPNN
ps ps pq st ps qt
ps pqs t
PN
is ps i
ps
N
ps
s
ps
dx c fxx

ax b i M
xp P
xpPsN
λ
== ====
==
=
+→
≥=
≤=
∈= =
∑∑ ∑∑∑∑
∑∑
∑

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:
j
x
=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
ij
j
xm
x
xijE
x
jn
=
→
+≤ ∀ ∈
∈=
∑
…

Nếu đỉnh
j
có trọng số
j
c >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
jj

j
ij
j
cx m
x
xijE
x
jn
=
→
+≤ ∀ ∈
∈=
∑
…

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ị (, )
GVE
=
, 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
k
y
=1 nếu màu
k
được dùng, và bằng 0 nếu trái lại.
jk

x
=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
kjk
y
xj n
x
xy ijEk n
yx kj 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
k
y =1 nếu màu
k
được dùng, và bằng 0 nếu trái lại.
jk
x
=1 nếu cạnh j được tô màu k , và bằng 0 nếu trái lại.
ij
a
=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
kjk
y
xj m
ax y k m i n
yx jk 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ị
(, )GVE=
, 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à
j
x
=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
ij
j
x
x
xijE
x
jn
=
→
+
≥∀ ∈
∈=
∑

2.16. Bài toán phủ cạnh
Cho đồ thị (, )GVE= ,
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.
Ứng dụng:
- Có một pháo đài với các tháp canh ở cuối mỗi hành lang, một lính gác ở hành
lang có thể quan sát được cả hai tháp canh ở hai đầu hành lang. Hãy tìm số lính canh ít

nhất để quan sát được mọi tháp canh của pháo đài (chính là số hành lang ít nhất để phủ
được hết các tháp canh).
- Có một viện bảo tàng gồm nhiều gian trưng bày, giữa các gian có các cửa thông
nhau, một người đứng ở cửa giữa hai gian có thể quan sát được cả hai gian. Hãy tìm
cách bố trí người canh gác ở các cửa sao cho gian nào cũng có người canh và số người
canh là ít nhất (mỗi gian là một đỉnh, mỗi cửa là một cạnh).
Ta đưa các ký hiệu:
ij
a =1 nếu đỉnh i là một trong các đầu mút của cạnh j và
bằng 0 nếu trái lại,
j
x
=1 nếu cạ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
1
min
1, 1,2, ,
0,1 ; 1, 2, ,
m
j
j
m
ij j
j
j
x
ax i n
x

jm
=
=
→
≥=
∈=
∑
∑

2.17. Bài toán ghép cặp trên đồ thị
Cho đồ thị (, )GVE= , V là tập n đỉnh, E là tập m cạnh. Tìm tập cạnh lớn nhất
(nhiều cạnh nhất) sao cho hai cạnh bất kỳ không chung đỉnh. Ta đưa vào các ký hiệu:
ij
a =1 nếu đỉnh i là một trong các đầu mút của cạnh j , và bằng 0 nếu trái lại.
j
x
=1 nếu cạ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à:
Bùi Thế Tâm I.12 Quy hoạch rời rạc

{}
1
1
1, 1,2, ,
0,1 ; 1, 2, ,
m
j
j
m
ij j

j
j
xmax
ax i n
x
jm
=
=
→
≤=
∈=
∑
∑

Nếu mỗi cạnh có gắn một trọng số
0
j
c ≥ thì có thể xét bài toán tìm ghép cặp với
tổng trọng số lớn nhất
1
max
m
jj
j
cx
=
⇒
∑

Ví dụ . Có

p
người và q việc,
p
khác q . Mỗi người được đào tạo để làm ít nhất
một việc. Hãy sắp xếp mỗi người làm một việc phù hợp với khả năng chuyên môn của
họ. Khi đó ta có đồ thị hai phần như sau:
Người 1 Việc 1
Người 2 Việc 2



Người
p
Việc q
p đỉnh ứng với người, q đỉnh ứng với việc. Nếu người
i
có khả năng làm việc j thì ta
vẽ cạnh
(, )ij. Tìm ghép cặp lớn nhất trong đồ thị này.
2.18. Bài toán phân công theo ca kíp
Phòng cảnh sát Quận có số tuyến cần được tuần tra theo thời gian cho trong bảng





Giả thiết mỗi tuyến tuần tra chỉ cần một viên cảnh sát, mỗi cảnh sát đi làm theo ca
8 tiếng liên tục. Hãy xác định số nhân viên cảnh sát tối thiểu để hoàn thành nhiệm vụ.
Gọi
1

x
là số cảnh sát đi làm vào lúc 22 giờ tối,
2
x
là số cảnh sát đi làm vào lúc 02 giờ
Thời gian Yêu cầu số tuyến tuần tra
22 giờ tối đến 02 giờ sáng 13
02 giờ sáng đến 06 giờ sáng 01
06 giờ sáng đến 10 giờ sang 07
10 giờ sáng đến 14 giờ chiều 06
14 giờ chiều đến 18 giờ chiều 06
18 giờ chiều đến 22 giờ tối 17
Bùi Thế Tâm I.13 Quy hoạch rời rạc

sáng, …,
6
x
là số cảnh sát đi làm vào lúc 18 giờ chiều. Khi đó dạng toán học của bài
toán là:
6
1
12
23
34
45
56
16
1
7
6

6
17
13
0 , 1, 2, 3, 4,5,6.
j
j
j
xmin
xx
xx
xx
xx
xx
xx
xZj
=
→
+≥
+≥
+≥
+≥
+≥
+≥
≤∈ =
∑

2.19. Bài toán tìm luồng cực đại trên đồ thị có hướng
Ta xét bài toán cụ thể: cho đồ thị có hướng gồm 6 đỉnh, nếu từ đỉnh u tới đỉnh v
có đường vận chuyển thì ta vẽ một cung j , lượng hàng vận chuyển trên cung này là
j

x
,
khả năng vận chuyển tối đa trên cung này là
j
q
. Tìm lượng hàng lớn nhất có thể vận
chuyển từ đỉnh 1 đến đỉnh 6.






Từ đồ thị trên ta có thể viết bài toán dưới dạng:
12
145
237
34 6
78
12 568
0 , 1, 2, 3, 4, 5, 6, 7,8
jj
xx max
xxx
xxx
xx x
xx
xx xxx
xqj
+

→
=+
=+
+=
=
+=++
≤≤ =


j
x
nguyên với j = 1, 2, 3, 4, 5, 6, 7, 8
Trong trường hợp véc tơ q = (4, 2, 4, 4, 1, 2, 2, 2) ta được đáp số là: lượng hàng tối đa
có thể vận chuyển là 5, phương án tối ưu là x = (3, 2, 0, 2, 1, 2, 2, 2).
3
1
5
4
2
6
2
x

1
x

4
x

3

x

5
x

6
x

7
x

8
x

Bùi Thế Tâm I.14 Quy hoạch rời rạc


BÀI TẬP
Dùng Microsoft Excel để giải các bài toán quy hoạch tuyến tính nguyên sau.
1. Một xưởng mộc sản xuất ba loại ghế tựa khác nhau A, B, C. Mỗi loại ghế cần
trải qua các thao tác: đánh bóng, đánh màu và đánh véc ni. Ngoài ra ghế loại C cần thêm
thao tác bọc nệm ghế. Biết thời gian cần thiết để thực hiện mỗi thao tác đối với từng loại
ghế: ghế loại A cần 1h đánh bóng, 0.5 giờ đánh màu, 0.7 giờ đánh véc ni và tiền lãi là
100 ngàn đồng; ghế loại B cần 1.2h đánh bóng, 0.5 giờ đánh màu, 0.7 giờ đánh véc ni
và tiền lãi là 130 ngàn đồng; ghế loại C cần 0.7h đánh bóng, 0.3 giờ đánh màu, 0.3 giờ
đánh véc ni, 0.7 giờ bọc nệm và tiền lãi là 80 ngàn đồng. Thời gian hiện có dành cho
việc đánh bóng là 600 giờ/ tháng, đánh màu là 300 giờ, đánh véc ni là 300 giờ, bọc nệm
là 140 giờ. Hỏi nên sản xuất bao nhiêu ghế mỗi loại để thu được nhiều lãi nhất.
2. Một xưởng sản xuất dự định mua hai loại máy để in hình vẽ trên vải. Máy A có
thể in 100 m/phút và chiếm 50 mét vuông diện tích sàn, còn máy B có thể in 200 m/phút

và chiếm 140 mét vuông diện tích sàn. Xưởng cần in ít nhất 600 m/phút và có diện tích
sàn để đặt máy in tối đa là 350 mét vuông. Mỗi máy A giá 22 triệu đồng và mối máy B
giá 42 triệu đồng. Hỏi cần mua bao nhiêu máy in mỗi loại sao cho tốn ít chi phí nhất.
3. Một doanh nghiệp có trong tay 10 dự án sẽ được lựa chọn để thực hiện vào năm
sau. Do hạn chế về nhân lực và tài chính nên không thể thực hiện tất cả các dự án. Để
lựa chọn, mỗi dự án được gán một trọng số biểu thị giá trị của việc thực hiện dự án đó,
các dự án từ 1 đến 10 có các trọng số tương ứng là: 70, 50, 60, 20, 10, 20, 30, 450, 10,
40. Chi phí về nhân lực của các dự án từ 1 đến 10 tương ứng là: 250, 195, 200, 70, 30,
40, 100, 170, 40, 120 người / tuần. Chi phí về tài chính của các dự án từ 1 đến 10 tương
ứng là : 400, 300, 350, 100, 70, 70, 250, 250, 100, 200 triệu đồng. Chủ doanh nghiệp
hiện có nguồn nhân lực 1000 người/tuần và 1500tiệu đồng để thực hiện các dự án. Cần
chọn thực hiện những dự án nào để thu được tổng giá trị lớn nhất.
4. Một xí nghiệp dùng 3 máy M1, M2, M3 để sản xuất một loại sản phẩm gồm 3
chi tiết C1, C2, C3 (mỗi bộ sản phẩm gồm một chi tiết mỗi loại). Mỗi ngày máy M1 có
thể sản xuất 8 chi tiết C1 hoặc 3 chi tiết C2 hoặc 12 chi tiết C3; máy M2 có thể sản xuất
12 chi tiết C1 hoặc 16 chi tiết C3 (máy M2 không sản xuất chi tiết C2), máy M3 có thể
sản xuất 6 chi tiết C1 hoặc 3 chi tiết C2 hoặc 6 chi tiết C3. Hãy xác định tỷ lệ thời gian
trong ngày để mỗi máy sản xuất từng chi tiết sao cho xí nghiệp đạt được số bộ sản phẩm
là nhiều nhất ?
5. Một xưởng làm cửa sắt có những thanh thép dài 12 m, cần cắt thành 8 đoạn dài
4m, 5 đoạn dài 5m và 3 đoạn dài 7m. Có 5 mẫu cắt sau. Mẫu 1: 3 đoạn dài 4m, không
thừa. Mẫu 2: 1 đoạn 4m, 1 đoạn 5m, thừa 3m. Mẫu 3: 1 đoạn 4m, 1 đoạn 7m, thừa 1m.
Mẫu 4: 2 đoạn 5m, thừa 2m. Mẫu 5: 1 đoạn 5m, 1 đoạn 7m, không thừa. Cần dùng
những mẫu cắt nào để tiết kiệm nhất.

6. Một xí nghiệp có thể sử dụng tối đa 510 giờ máy cán, 360 giờ máy tiện và 150
giờ máy mài để chế tạo 3 loại sản phẩm A, B, C. Để chế tạo một đơn vị sản phẩm A cần
9h máy cán, 5h máy tiện, 3h máy mài. Để chế tạo một đơn vị sản phẩm B cần 3h máy
cán, 4h máy tiện. Để chế tạo một đơn vị sản phẩm C cần 5h máy cán, 3h máy tiện, 2h
máy mài. Sản phẩm A trị giá 48 ngàn đồng. Sản phẩm B trị giá 16 ngàn đồng. Sản phẩm

C trị giá 27 ngàn đồng. Xí nghiệp cần chế tạo bao nhiêu sản phẩm mỗi loại để tổng giá
trị lớn nhất.
Bùi Thế Tâm I.15 Quy hoạch rời rạc

7. Một nhà sản xuất đồ gỗ sản xuất 3 loại bàn: loại truyền thống x1, loại cận đại
x2, loại hiện đại x3. Loại x1 có lợi nhuận là 36$, cần 2 h để tạo hình, 3 h để đánh bóng.
Loại x2 có lợi nhuận là 28$, cần 2 h để tạo hình, 2 h để đánh bóng. Loại x3 có lợi nhuận
là 32$, cần 4 h để tạo hình, 1 h để đánh bóng. Xác định phương án sản xuất để cực đại
hóa lợi nhuận nếu nhà sản xuất có 60 h để tạo hình và 80 h để đánh bóng.
8. Tìm phương án vận tải có chi phí nhỏ nhất. Khả năng các nơi phát hàng P1, P2,
P3 tương ứng là 80, 110, 120 tấn hàng. Nhu cầu các nơi tiêu thụ T1, T2, T3 tương ứng
là 100, 120, 900 tấn. Ma trân chi phí từ nơi phát tới nơi thu là ($ / tấn hàng hóa):
200 600 300
C = 400 200 700
500 800 300
9. Bài toán vận tải: khả năng phát A = (65, 95, 85, 55), nhu cầu B = (55, 50, 80 ,
50 ,65).
9 20 7 14 8
C = 12 15 19 13 8
11 27 17 23 19
14 11 13 7 10
10. Tìm tập đỉnh có nhiều phần tử nhất trên đồ thị sau sao cho không có hai đỉnh
nào kề nhau

1 3 2 10


6 4 5 9



7 8
11. 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
1 2


4 3
12. Tìm số màu tối thiểu để tô các cạnh của đồ thị sau sao cho hai cạnh kề nhau có
màu khác nhau
1

4

2 3
Bùi Thế Tâm I.16 Quy hoạch rời rạc

13. Tìm số đỉnh ít nhất trong đồ thị sau sao cho mỗi cạnh có ít nhất một đầu mút
được chọn.
5 7

4 6

3 2 1

14. Hãy bố trí số người gác tối thiểu cho khu bảo tàng có sơ đồ sau.


2 3 4



1 6 5




15. Tìm ghép cặp với tổng trọng số lớn nhất của đồ thị sau. Trọng số của các cạnh
(1,5), (1,6), (1,7), (2,5), (2,7), (3,6), (3,8), (4,6), (4,7), (4,8) lần lượt là: 5, 8, 2, 3, 4, 9, 6,
7, 2, 4.
1 5

2 6

3 7

4 8
Người Việc

Bùi Thế Tâm II.1 Quy hoạch rời rạc

Chương 2
NHỮNG KHÁI NIỆM MỞ ĐẦU
Trong chương này sẽ trình bày những khái niệm cơ bản về quy hoạch tuyến tính,
phương pháp đơn hình bình thường, phương pháp đơn hình đối ngẫu từ vựng, và khái
niệm về bài toán quy hoạch tuyến tính nguyên.
1. NHỮNG KHÁI NIỆM CƠ BẢN VỀ QUY HOẠCH TUYẾN TÍNH
1.1.
Bài toán qui hoạch tuyến tính là bài toán có dạng:

0
1

1
1
ax (1)
, 1, 2, , (2)
,1, , (3)
0, 1, , (4)
n
jj
j
n
ij j i
j
n
ij j i
j
j
xcxm
ax b i l
ax b i l m
xjn
=
=
=
=→
==
≤=+
≥=
∑
∑
∑


y Miền xác định: tập hợp các véc tơ x thoả mãn (2) và (4)
y Phương án bài toán: véc tơ x thoả mãn (2) và (4)
y Nếu (x
1
,…,x
n
) là phương án của bài toán,
0
1
n
jj
j
x
cx
=
=
∑
thì
X

= (x
0
,x
1
,…,x
n
) gọi
là phương án mở rộng của bài toán (1) – (4).
y Phương án

*
X làm cực đại (1) gọi là phương án tối ưu. Phương án mở rộng
*
X

gọi

là phương án tối ưu mở rộng nếu X
*
là phương án tối ưu .
y Kí hiệu:
L - miền xác định của bài toán (1)-(4)
(, )LC – kí hiệu bài toán qui hoạch tuyến tính (1) - (4)
(, )XLC – phương án tối ưu của bài toán (1) - (4)
(, )XLC

- phương án tối ưu mở rộng của bài toán (1) - (4)
C
L

là tập hợp các phương án tối ưu của bài toán ( , )LC
y Bài toán qui hoạch tuyến tính gọi là giải được nếu tồn tại phương án tối ưu.




Bùi Thế Tâm II.2 Quy hoạch rời rạc


1.2.

Dạng chính tắc của bài toán qui hoạch tuyến tính


0
1
1
ax
, 1, 2 , ,
0, 1,2, ,
n
jj
j
n
ij j i
j
j
xcxm
ax b i m
xj n
=
=
=→
==
≥=
∑
∑

y Gọi
1
2

.
.
j
j
j
mj
a
a
A
a





=





là véc tơ điều kiện thứ j của bài toán (5)-(7)

1
2
.
.
.
B=
m

b
b
b







là véc tơ ràng buộc của bài toán (5)-(7).
y Phương án X của bài toán (5)-(7) gọi là tựa nếu các véc tơ điều kiện ứng với
các thành phần dương của nó là độc lập tuyến tính.
y Cơ sở của phương án tựa X là tập hợp |0}
j
{A
j
x > . Các thành phần của
phương án tựa ứng với các véc tơ cơ sở gọi là các thành phần cơ sở (các biến tương ứng
gọi là biến cơ sở), các thành phần còn lại gọi là các thành phần phi cơ sở (các biến
tương ứng gọi là biến phi cơ sở).
y Nếu
1
( , , )
n
Xx x=
phương án tựa của bài toán quy hoạch tuyến tính,
1
( , , )
jjk

A
A
là cơ sở của phương án tựa,
{
}
1
, ,
k
B
jj=
,
{
}
1, , \NnB=
thì hàm mục
tiêu
01
, , ,
n
x
xx có thể biểu diễn qua các biến phi cơ sở:
0i j
( ), 0,1, ,
ii j
jN
x
xxxi n
∈
=+ − =
∑


Kí hiệu Q
n
={0,1,…,n}
B
0
=B∪{0}, N
0
=N∪{0}
Bảng đơn hình
0
,
ij n
iQ j N
Tx
∈∈
= gọi là bảng đơn hình đầy đủ.
y Phương án tựa bài toán (5) - (7) gọi là không suy biến nếu số ràng buộc của hệ
(6) - (7) mà phương án thỏa mãn với dấu bằng bằng đúng n (các ràng buộc này là độc
lập tuyến tính). Phương án tựa là suy biến nếu số ràng buộc mà phương án tựa thỏa mãn
chặt là lớn hơn n.
(5)
(6)
(7)
Bùi Thế Tâm II.3 Quy hoạch rời rạc

Phương án tựa X của bài toán (5) - (7) là không suy biến nếu các thành phần cơ sở
của nó là dương. Cơ sở của phương án tựa không suy biến xác định duy nhất. Ứng với
phương án tựa suy biến có nhiều cơ sở.
y Tiêu chuẩn tối ưu: để cho phương án mở rộng

'' '
01
' ( , , , )
n
Xxxx=

là tối ưu điều
kiện cần và đủ là tồn tại cơ sở B sao cho
'
i j
0
( ), 0,1, ,
0,
ii j
jN
j
x
xxxi n
xjN
∈
=+ − =
≥∈
∑

y Giả sử ràng buộc (6) của bài toán (5) - (7) viết ở dạng:
0i j
( ), 0,1 ,
ii j
jN
x

xxxi n
∈
=+ − =
∑
.
Bảng đơn hình tương ứng
0
,
ij
n
iQ j N
Tx
∈∈
=
,
210200
11
1
, , , ) ( , , , ),
( , , , ) ( , , , ).
1
0
X=(x
x
nn
n
njjn
j
xx xx x
Xxx cxxx

=
=
==
∑


Nếu x
i0
≥ 0 (i = 1, 2, . . ., n) thì bảng đơn hình T gọi là chấp nhận được, véc tơ X
là phương án tựa của bài toán quy hoạch tuyến tính.
Nếu x
0j
≥ 0 , j∈N thì bảng đơn hình T là chuẩn (đối ngẫu chấp nhận được), véc tơ
X gọi là giả phương án, X

gọi là giả phương án mở rộng

2. SO SÁNH THEO NGHĨA TỪ VỰNG


2.1. Véc tơ
12
( , , , )
n
Xxx x= gọi là dương từ vựng X>0 nếu X≠(0,…,0) và thành
phần đầu tiên khác 0 là dương.
y Véc tơ X gọi là không âm từ vựng X ≥ 0 nếu X>0 hay X=0
y Véc tơ X gọi là lớn hơn từ vựng véc tơ Y (ký hiệu X > Y) nếu X – Y >0
y Véc tơ X ≥ Y (không nhỏ hơn từ vựng) nếu X – Y ≥0
y X gọi là âm từ vựng (ký hiệu là X < 0) nếu –X >0

y Tương tự ta có các định nghĩa X ≤ 0, X < Y, X ≤ Y.
2.2. Phương án X
*
(phương án mở rộng
*
X

) của bài toán (5)- (7) gọi là phương
án tối ưu từ vựng (phương án
l - tối ưu) nếu đối với mọi phương án mở rộng X

ta có
*** *
01 01
( , , , ) ( , , , )
nn
XxxxXxxx=≥=

.
Định lý 1. Nếu tập hợp các phương án tối ưu của bài toán (5) - (7) khác rỗng và
bị chặn thì tồn tại phương án tối ưu từ vựng X
*

Định lý 2. Nếu X
*
phương án tối ưu từ vựng của bài toán (5)-(7) thì X
*
là
phương án tựa.
Bùi Thế Tâm II.4 Quy hoạch rời rạc


Bảng đơn hình
0
,
ij
n
iQ j N
Tx
∈∈
=

gọi là chuẩn từ vựng (hay là
l
- chuẩn) nếu

0
1
.
.
.
j
j
j
nj
x
x
R
x






=





> 0 , ∀j∈N


Định lý 3. Để cho phương án tựa X
*
của bài toán (5) – (7) là
l
- tối ưu, điều kiện
cần và đủ là tồn tại cơ sở B sao cho bảng đơn hình
0
,
ij
n
iQ j N
Tx
∈∈
= là l - chuẩn.
Giả phương án X (giả phương án mở rộng
X

) của bài toán (5) – (7) gọi là dương

từ vựng nếu bảng đơn hình tương ứng là
l
- chuẩn, nói gọn lại là
l
- giả phương án (
l
-
giả phương án mở rộng).

3. BẢNG ĐƠN HÌNH, PHƯƠNG ÁN, GIẢ PHƯƠNG ÁN
Phép biến đổi cơ bản của bảng đơn hình: đưa x
k
ra khỏi cơ sở, đưa x
l
vào cơ sở.
Phần tử x
kl
gọi là phần tử quay
Giả sử
0
,
ij
n
iQ jN
Tx
∈∈
=

,
cơ sở là B, N=

{
}
1, , \ , , , 0
kl
nBlN kB x
∈
∈≠
.
Gọi
{
}
(
)
{
}
*
\NNkl=∪
, các biến x
0
, x
1
, , x
n
có thể biểu diễn qua các biến
*
N và ta được bảng
0
*
*
,

*
ij
n
iQ jN
Tx
∈∈
=
và cơ sở mới
{
}
(
)
{
}
*
\
B
Bl k=∪ .
Gọi
j
R
là cột của T,
*
j
R
là cột của
*
T , ta có công thức tính lại như sau
*
*

l
k
kl
kj
jj l
kl
R
R
x
x
R
RR
x

=−




=−



hay viết ở dạng toạ độ
{} { }
*
*
, 0,1, 2, , .
, ( \ ) 0 , 0,1, ,
il

ik
kl
kj
ij ij il
kl
x
xi n
x
x
x
xxjNl i n
x

=− =




=− ∀∈ ∪ =




{
}
(
)
{
}
\0jNl∀∈ ∪

Bùi Thế Tâm II.5 Quy hoạch rời rạc

4. PHƯƠNG PHÁP ĐƠN HÌNH
4.1. Thuật toán
Phương pháp đơn hình cho phép xây dựng dãy hữu hạn các phương án tựa X
0
, X
1
,
…, X
k
, trong đó X
k
là phương án tối ưu của bài toán (5) - (7). Hàm mục tiêu x
0 =
x
0
(X
r
)
không giảm khi r tăng. Ứng với mỗi phương án tựa X
r
có T
r
, B
r
, N
r
. Quá trình giải gồm
bước lặp xuất phát (xây dựng phương án tựa xuất phát X

0
) và dãy các bước lặp tổng
quát.
Bước lặp tổng quát r ≥ 0 có phương án X
r
, tương ứng với nó có bảng đơn hình T
r
và các tập B
r
, N
r
. Kiểm tra bảng T
r
có là chuẩn không (tức là
0
0
jr
x
jN≥∀∈). Nếu
đúng thì X
r
là tối ưu, nếu không thì xác định
l
x
đưa vào cơ sở theo công thức :
{
}
00
min |
ljr

x
xjN=∈
Đưa biến
k
x
ra khỏi cơ sở theo tiêu chuẩn
00
min | 1,2, , ; 0
ki
il
kl il
xx
inx
xx


=
=>




Nếu không có x
il
(i = 1, 2, , n) dương thì bài toán không giải được, hàm mục
tiêu tiến ra dương vô cùng.
Tính X
r+1
, T
r+1

, B
r+1
, N
r+1
theo các công thức ở tiết 3.
4.2. Cách tính phương án xuất phát
Giải bài toán phụ ứng với bài toán (5) – (7) có b
i
≥ 0 ( i=1, ,m) :
12
1
1
( , , ) max
, 1, 2, ,
0, 1, 2, ,
nm
nm j
jn
n
ij j n i i
j
j
fxx x x
ax x b i m
xj nm
+
+
=+
+
=

=− ⇒
+= =
≥= +
∑
∑

Bài toán này có phương án tựa
11
( , , ) (0,0, ,0, , , )
m
nm
n
x
xbb
+
=
 
.
Dùng phương pháp đơn hình giải bài toán phụ, nếu
** *
12
( , , ) 0
nm
fx x x
+
=
thì
*
0
ni

x
+
= (i = 1, , m) và véc tơ
** *
12
( , , )
n
x
xx là phương án tựa phải tìm X
0
.
Nếu
*
f
< 0 thì bài toán (5) – (7) không giải được (không có phương án chấp nhận
được).
Ví dụ. Giải bài toán sau: