Bài giảng Kỹ thuật ra quyết định kỹ sư - Chương 4: Qui hoạch tuyến tính

d1  dj  dn 
Gọi xij là lượng hàng vận chuyển từ i đến j. cij là chi phí vận 
chuyển một đơn vị hàng từ i đến j. 
Min Z = ∑∑
= =
m
1i
n
1j
ijijxc 
Ràng buộc (s.t) i
n
1j
ij sx ≤∑
=
 ∀i = 1, 2, , m 
 i
m
1i
ij dx ≥∑
=
 ∀j = 1, 2, , n 
 xij ≥ 0 ∀i = 1, 2, , m 
 ∀j = 1, 2, , n 
II. Lý thuyết nền tảng của bài toán QHTT: 
2.1. Dạng bài toán 
• Cực đại chuẩn (standard maximization problem) 
Max Z = ∑
=
n
1j
jjxc 
Ràng buộc (s.t) i
n
1j
jij bxa ≤∑
=
 ∀i = 1, 2, , m 
 xj ≥ 0 ∀j = 1, 2, , n 
Trong đó bi ≥ 0 
Chương 4 – Bài toán qui hoạch tuyến tính 5 GV. Nguyen Vu Quang 
• Cực tiểu chuẩn (standard minimization problem) 
Min Z = ∑
=
n
1j
jjxc 
Ràng buộc (s.t) i
n
1j
jij bxa ≥∑
=
 ∀i = 1, 2, , m 
 xj ≥ 0 ∀j = 1, 2, , n 
Trong đó bi ≥ 0 
• Bài toán cực đại (hay cực tiểu) với ràng buộc có dấu ≥ và 
cả dấu ≤ 
2.2. Nghiệm khả dĩ 
Nghiệm khả dĩ (feasible solution): một bộ giá trị các biến 
thỏa mãn các ràng buộc 
Vùng khả dĩ (feasible region): Tập tất cả các nghiệm khả dĩ 
Ví dụ: 
Max Z = 50x1 + 80x2 
Ràng buộc : 
 Tổng giờ cắt x1 + 2x2 ≤ 32 (d1) 
 Tổng giờ ráp 3x1 + 4x2 ≤ 84 (d2) 
 Nh.cầu lều C.dụng x2 ≤ 12 (d3) 
 Biến x1, x2 ≥ 0 
Nghiệm khả dĩ ? 
Vùng khả dĩ ? 
Chương 4 – Bài toán qui hoạch tuyến tính 6 GV. Nguyen Vu Quang 
2.3. Phương pháp đồ thị (cho bài toán có 2 biến) 
B1. Biểu diễn các ràng buộc trên mặt phẳng tọa độ và xác 
định vùng khả dĩ 
B2. Vẽ một đường thẳng có phương trùng với hàm mục 
tiêu Z. Di chuyển tịnh tiến đường thẳng này sao cho 
giá trị Z được cải thiện. Xác định giao điểm của đường 
thẳng với biên của vùng khả dĩ, đó là nghiệm tối ưu. 
Ghi chú: 
• Ràng buộc tích cực/ trói buộc (Binding constraint) 
• Ràng buộc không trói buộc 
• Nghiệm bài toán (nếu có) luôn là một điểm cực biên 
(đỉnh) của vùng khả dĩ 
12 
16 
32 
21 
28 
(20,6) 
(8,12) 
X2 
X1 
5 
8 
Z = 400 Z = 1480 
Chương 4 – Bài toán qui hoạch tuyến tính 7 GV. Nguyen Vu Quang 
III. Giới thiệu phương pháp đơn hình (simplex method) 
Không thể dùng phương pháp đồ thị nếu số biến > 3. 
⇒ Phương pháp đơn hình (thuật toán, giải bằng tay) 
3.1. Phương pháp đơn hình: 
Khái niệm biến bù, nghiệm khả dĩ cơ sở, biến cơ sở và biến 
không cơ sở: 
a. Để chuyển các ràng buộc (≤) thành các hệ phương trình 
(để ) ta dùng các biến bù: 
Ví dụ: Max Z = 50x1 + 80x2 
 S.t x1 + 2x2 ≤ 32 
 3x1 + 4x2 ≤ 84 
 x2 ≤ 12 
 x1, x2 ≥ 0 
======================================== 
 Max Z = 50x1 + 80x2 
 S.t x1 + 2x2 + s1 = 32 
 3x1 + 4x2 + s2 = 84 
 x2 + s3 = 12 
 x1, x2, s1, s2, s3 ≥ 0 
Giải hệ phương trình: m = 3 phương trình, n = 5 biến 
Có bao nhiêu lời giải? 
Chương 4 – Bài toán qui hoạch tuyến tính 8 GV. Nguyen Vu Quang 
b. Lời giải cơ sở: cho (n-m) biến có giá trị = 0 và giải các 
biến còn lại ⇒ số điểm cực 
Số lời giải cơ sở (basic solution) là : n! / [m!(n-m)!] 
Ví dụ: cho 2 biến có giá trị = 0 giải hệ 3 pt 3 ẩn sẽ có 10 lời 
giải cơ sở sau: 
X1 x2 s1 s2 s3 Điểm giao Khả dĩ? 
0 0 32 84 12 O Có 
0 16 0 20 -4 B 
0 21 -10 0 -9 C 
0 12 8 36 0 A Có 
32 0 0 -12 12 H 
28 0 4 0 12 G Có 
 0 0 
20 6 0 0 6 F Có 
8 12 0 12 0 D Có 
12 12 -4 0 0 E 
Lưu ý: lời giải tồn tại biến có giá trị âm sẽ là không khả dĩ 
12 
16 
32 
21 
28 
(20,6) 
(8,12) 
X2 
X1 
5 
8 
Z = 400 Z = 1480 
O 
A 
B 
C 
D 
E 
F
G
H
Chương 4 – Bài toán qui hoạch tuyến tính 9 GV. Nguyen Vu Quang 
c. Các lời giải (nghiệm) cơ sở nằm trong miền khả dĩ gọi là 
lời giải khả dĩ cơ sở (basic feasible solution) 
d. Trong nghiệm khả dĩ cơ sở, biến gán giá trị = 0 gọi là 
biến không cơ sở; các biến còn lại gọi là biến cơ sở. 
Giải thuật đơn hình (simplex method) 
Là phương pháp đại số lặp đi lặp lại để chuyển từ 1 lời giải 
khả dĩ cơ sở của bài toán sang 1 lời giải khả dĩ cơ sở khác 
và kiểm tra giá trị hàm mục tiêu cho đến khi đạt tối ưu. 
Về mặt hình học, điều này tương ứng với chuyển từ cực 
biên này sang cực biên khác của miền khả dĩ cho đến khi 
có lời giải tối ưu. 
3.2. Phương pháp đơn hình cho bài toán MAX với ràng 
buộc đều là ≤ và RHS dương: 
Ví dụ: Max Z = 50x1 + 80x2 
 S.t x1 + 2x2 ≤ 32 
 3x1 + 4x2 ≤ 84 
 x2 ≤ 12 
 x1, x2 ≥ 0 
Bước 1. Thêm biến bù (si): 
 x1 + 2x2 + s1 = 32 
 3x1 + 4x2 + s2 = 84 
 x2 + s3 = 12 
 - 50x1 - 80x2 + Z = 0 
Bước 2. Lập bảng đơn hình ban đầu: 
x1 x2 s1 s2 s3 Z RHS 
1 2 1 0 0 0 32 
3 4 0 1 0 0 84 
0 1 0 0 1 0 12 
-50 -80 0 0 0 1 0 
Nghiệm khả dĩ cơ sở là (0, 0, 32, 84, 12) *** Z = 0 
Biến cơ sở là s1, s2, s3 
Chương 4 – Bài toán qui hoạch tuyến tính 10 GV. Nguyen Vu Quang 
Bước 3. Xác định giá trị xoay 
+ Giao điểm của cột xoay và hàng xoay 
+ Cột xoay là cột có trị âm nhỏ nhất trong hàng dưới cùng 
+ Hàng xoay là hàng có tỷ số dịch chuyển nhỏ nhất 
+ Tỷ số dịch chuyển = RHS / giá trị dương trong cột xoay 
+ Nếu cột xoay không có giá trị dương ⇒ không có lời giải 
x1 x2 s1 s2 s3 Z RHS 
1 2 1 0 0 0 32 
3 4 0 1 0 0 84 
0 1 0 0 1 0 12 
-50 -80 0 0 0 1 0 
Bước 4. Thực hiện xoay cho đến khi hàng dưới không 
âm 
+ Chuyển giá trị xoay thành = 1 
+ Chuyển các giá trị khác trong cột xoay = 0 
x1 x2 s1 s2 s3 Z RHS 
1 2 1 0 0 0 32 R1 = R1 + (-2)R3
3 4 0 1 0 0 84 R2 = R2 + (-4)R3
0 1* 0 0 1 0 12 
-50 -80 0 0 0 1 0 R4 = R4 + 80R3
x1 x2 s1 s2 s3 Z RHS 
1* 0 1 0 -2 0 8 
3 0 0 1 -4 0 36 R2 = R2 + (-3)R1
0 1 0 0 1 0 12 
-50 0 0 0 80 1 960 R4 = R4 + 50R1
Nghiệm khả dĩ cơ sở mới (0, 12, 8, 36, 0) *** Z = 960 
x1 x2 s1 s2 s3 Z RHS 
1 0 1 0 -2 0 8 R1 = R1+2R2*1/2
0 0 -3 1 2* 0 12 R2 = R2*1/2
0 1 0 0 1 0 12 R3 = R3 + (-1)R2*1/2
0 0 50 0 -20 1 1360 R4 = R4 + 20R2*1/2
Nghiệm khả dĩ cơ sở mới (8, 12, 0, 12, 0) *** Z = 1360 
Chương 4 – Bài toán qui hoạch tuyến tính 11 GV. Nguyen Vu Quang 
x1 x2 s1 s2 s3 Z RHS 
1 0 -2 1 0 0 20 
0 0 -3/2 1/2 1 0 6 
0 1 3/2 -1/2 0 0 6 
0 0 20 10 0 1 1480 
Hàng dưới không âm, đạt tối ưu, nghiệm (20, 6, 0, 0, 6), Z=1480 
3.3. Phương pháp đơn hình cho bài toán MAX với ràng 
buộc ≤ và cả ≥ và =: 
Ví dụ: Giải bài toán QHTT 
Max Z = x1 – x2 + 3x3 
S.t: -x1 - x2 ≥ -20 
 x1 + x3 = 5 
 x2 + x3 ≥ 10 
 x1, x2, x3 ≥ 0 
Bước 1. Chuẩn hóa bài toán 
Làm cho tất cả giá trị RHS thành dương ; (nhân -1, đổi dấu) 
Với ràng buộc ≤, thêm biến bù (ký hiệu si) 
Với ràng buộc ≥, thêm biền trừ (-si) và biến nhân tạo 
Với ràng buộc =, thêm biến nhân tạo (ký hiệu ai) 
Cộng –Mai vào hàm mục tiêu Z, trong đó M là hằng số 
rất lớn 
Tất cả si, ai đều ≥ 0 
Ví dụ: 
Max Z = x1 – x2 + 3x3 – Ma1 – Ma2 
 x1 + x2 + s1 = 20 
 x1 + x3 + a1 = 5 
 x2 + x3 - s2 + a2 = 10 
 -x1 + x2 - 3x3 +Ma1 +Ma2 + Z = 0 
x1, x2, x3, s1, s2, a1, a2 ≥ 0 
Chương 4 – Bài toán qui hoạch tuyến tính 12 GV. Nguyen Vu Quang 
Bước 2. Lập bảng đơn hình sơ bộ và ban đầu 
Bảng sơ bộ 
x1 x2 x3 s1 a1 s2 a2 Z RHS 
1 1 0 1 0 0 0 0 20 
1 0 1 0 1 0 0 0 5 
0 1 1 0 0 -1 1 0 10 
-1 1 -3 0 M 0 M 1 0 
Bảng ban đầu (sau khi loại M trong cột ai) 
x1 x2 x3 s1 a1 s2 a2 Z RHS 
1 1 0 1 0 0 0 0 20 
1 0 1* 0 1 0 0 0 5 
0 1 1 0 0 -1 1 0 10 R3-R2 
-M-1 -M+1 -3-2M 0 0 M 0 1 -15M R4+(3+2M)R2 
Nghiệm khả dĩ cơ sở ban đầu (0, 0, 0, 20, 5, 0, 10), Z = -15M 
Bước 3. Thực hiện xoay đến khi hàng dưới không âm 
x1 X2 x3 s1 a1 s2 a2 Z RHS 
1 1 0 1 0 0 0 0 20 R1-R3 
1 0 1 0 1 0 0 0 5 
-1 1* 0 0 -1 -1 1 0 5 
M+2 -M+1 0 0 2M+3 M 0 1 -5M+15 R4+(M-1)R3 
Nghiệm khả dĩ cơ sở (0, 0, 5, 20, 0, 0, 5), Z = -5M+15 
x1 X2 x3 s1 a1 s2 a2 Z RHS 
2 0 0 1 1 1 -1 0 15 
1 0 1 0 1 0 0 0 5 
-1 1 0 0 -1 -1 1 0 5 
3 0 0 0 M+4 1 M-1 1 10 
Hàng dưới không âm, nghiệm khả dĩ (0, 5, 5, 15, 0, 0, 0) 
Vì các biến nhân tạo a1, a2 đều = 0, bài toán có nghiệm là: 
x1 = 0, x2 = 5, x3 = 5 và Max Z = 10 
(Nếu có một biến nhân tạo ≠ 0 thì bài toán sẽ không có nghiệm) 
Chương 4 – Bài toán qui hoạch tuyến tính 13 GV. Nguyen Vu Quang 
3.4. Phương pháp đơn hình cho bài toán MIN: 
Chuyển hàm mục tiêu Min Z = Σcjxj thành Max Z* = Σ(–cj)xj 
và giải như bài toán MAX 
Ví dụ: 
Min Z = 2x1 + 4x2 
 2x1 + x2 ≥ 14 
 x1 + x2 ≥ 12 
 x1 + 3x2 ≥ 18 
 x1, x2 ≥ 0 
⇒ 
Max Z* = – 2x1 – 4x2 
 2x1 + x2 ≥ 14 
 x1 + x2 ≥ 12 
 x1 + 3x2 ≥ 18 
 x1, x2 ≥ 0 
Bước 1. Chuẩn hóa bài toán (biến bù, trừ, nhân tạo) 
Max Z* = – 2x1 – 4x2 – Ma1 – Ma2 – Ma3 
 2x1 + x2 – s1 + a1 = 14 
 x1 + x2 – s2 + a2 = 12 
 x1 + 3x2 – s3 + a3 = 18 
 2x1 + 4x2 + Ma1 + Ma2 + Ma3 +Z = 0 
Bước 2. Lập bảng đơn hình sơ bộ và ban đầu 
Bảng sơ bộ 
x1 x2 s1 s2 s3 a1 a2 a3 Z RHS 
2 1 -1 0 0 1 0 0 0 14 
1 1 0 -1 0 0 1 0 0 12 
1 3 0 0 -1 0 0 1 0 18 
2 4 0 0 0 M M M 1 0 
Bảng ban đầu 
x1 x2 s1 s2 s3 a1 a2 a3 Z RHS 
2 1 -1 0 0 1 0 0 0 14 
1 1 0 -1 0 0 1 0 0 12 
1 3* 0 0 -1 0 0 1 0 18 
-4M+2 -5M+4 M M M 0 0 0 1 -44M
R1 = R1 - R3*1/3 
R2 = R2 - R3*1/3 
R3 = R3*1/3 
R4 = R4 – (-5M+4)R3*1/3 
Chương 4 – Bài toán qui hoạch tuyến tính 14 GV. Nguyen Vu Quang 
Bước 3. Thực hiện xoay đến khi hàng dưới không âm 
x1 x2 s1 s2 s3 a1 a2 a3 Z RHS 
5/3* 0 -1 0 1/3 1 0 -1/3 0 8 
2/3 0 0 -1 1/3 0 1 -1/3 0 6 
1/3 1 0 0 -1/3 0 0 1/3 0 6 
(-7M+2)/3 0 M M (-2M+4)/3 0 0 (5M-4)/3 1 -14M-24 
x1 x2 s1 s2 s3 a1 a2 a3 Z RHS 
1 0 -3/5 0 1/5 3/5 0 -1/5 0 24/5 
0 0 2/5* -1 1/5 -2/5 1 -1/5 0 14/5 
0 1 1/5 0 -2/3 -1/5 0 2/5 0 22/5 
0 0 (-2M+2)/5 M (-M+6)/5 (7M-2)/5 0 (6M-6)/5 1 (-14M-136)/5 
x1 x2 s1 s2 s3 a1 a2 a3 Z RHS 
1 0 0 -3/2 1/2 0 3/2 -1/2 0 9 
0 0 1 -5/2 1/2 -1 5/2 -1/2 0 7 
0 1 0 1/2 -1/2 0 -1/2 1/2 0 3 
0 0 0 1 1 M M-1 M-1 1 -30 
Hàng dưới không âm, nghiệm khả dĩ (9, 3, 7, 0, 0, 0, 0, 0) 
Vì các biến nhân tạo a1, a2, a3 đều = 0, bài toán có nghiệm là: 
x1 = 9, x2 = 3 và Max Z* = - 30 
Vậy bài toán gốc có Min Z = 30 
Chương 4 – Bài toán qui hoạch tuyến tính 15 GV. Nguyen Vu Quang 
IV. Giải bài toán QHTT bằng máy tính: 
Phương pháp đơn hình: 
• Khoa học toán 
• Hiểu rõ bản chất cách giải 
• Khó thực hiện 
• Càng khó khi bài toán có từ 5 đến hàng trăm biến 
Phần mềm máy tính: 
• Dựa vào thuật toán 
• Khả năng tính nhanh (hàng triệu phép thử / giây) 
• ABQM, QSB, LINDO, EXCEL 
Hướng dẫn sử dụng phần mềm ABQM và Excel: 
(Sinh viên xem tài liệu phát kèm theo bài giảng)