Chương 4
Quy Hoạch Tuyến Tính
2
C4. Quy Hoạch Tuyến Tính
1. Giới thiệu về Bài toán QHTT
2. Phương pháp giải bài toán QHTT:
Phương pháp đồ thị
3. Giới thiệu phương pháp đơn hình
4. Giới thiệu cách giải bài toán QHTT và phi tuyến bằng phần
mềm Excel
3
1. Giới thiệu về Bài toán QHTT
Xác định x
1
, x
2
, …, x
n
sao cho:
Cực đại (hay Cực tiểu) hàm mục tiêu Z:
Z = z(x
1
, x
2
, …, x
n
)
Đồng thời thỏa mãn các ràng buộc R
j
:
R

Loại lều
Công đoạn Thường Chuyên
dụng
Giờ công sẵn
có
Cắt (giờ/cái) 1 2 32
Ráp (giờ/cái) 3 4 84
Lợi
nhuận/cái
$50 $80
5
1. Giới thiệu về Bài toán QHTT (tt2)

Dạng tổng quát:

Gọi x
j
là lượng sản phẩm j cần sản xuất, a
ij
là lượng nguyên liệu i cần để
sản xuất 1 đơn vị sản phẩm j.

Ràng buộc
Nguyên liệu
Sản phẩm
Lượng nguyên
liệu có sẵn
1 … j … n
1
…

m , 2, 1,i bxa
j
n
1j
ijij
=∀≥
=∀≤
∑
=
6
1. Giới thiệu về Bài toán QHTT (tt3)

Bài toán trộn sản phẩm/dinh dưỡng
Một người làm vườn muốn tạo một hỗn hợp phân bón từ
2 loại sản phẩm. Giá mua đơn vị, lượng dưỡng chất trong
mỗi đơn vị cho như sau:
Số đơn vị sp 1 và sp 2 cần mua là bao nhiêu?
Thành phần
Loại sản phẩm
Dưỡng chất
yêu cầu
Sản phẩm 1 Sản phẩm 2
Potat/đơn vị 2 1 14
Nitrat/đơn vị 1 1 12
Photphat/đơn vị 1 3 18
Giá mua/đơn vị $2 $4
7

Dạng tổng quát:


1
…
i
…
m
… a
ij
…
b
1
…
b
i
…
b
m
Chi phí mua/đơn vị
c
1
… c
j
… c
n
8
1. Giới thiệu về Bài toán QHTT (tt5)
Bài toán vận tải
Có 2 trạm phân phối chất đốt A và B cung cấp hàng cho 3 đại lý 1, 2
và 3. Tổng cung, tổng cầu và chi phí vận chuyển/mỗi đơn vị chất
đốt cho như sau:
Vận chuyển như thế nào để có tổng chi phí bé nhất?

…
i
…
m
… c
ij
…
s
1
…
s
i
…
s
m
Nhu cầu tối
thiểu
d
1
… d
j
… d
n
∑∑
= =
=
m
1i
n
1j

Trong đó

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 ≤.
∑
=
=
n
1j
jj
xcMax Z
n) , 2, 1,j( 0; xm) , 2, 1,i( ;bxa
j
n
1j
ijij
=∀≥=∀≤
∑
=
∑
=
=
n
1j
jj
xcMin Z
0b
i
≥
n) , 2, 1,j( 0; xm) , 2, 1,i( ;bxa
j

+ 4 x
2
≤ 84 (d2)
Nh.cầu lều c.dụng: x
2
≤ 12 (d3)
Biến: x
1
, x
2
≥ 0
Nghiệm khả dĩ?
Vùng khả dĩ?
12
2. PP giải Bài toán QHTT: PP đồ thị (tt2)
Lý thuyết nền tảng của bài toán QHTT (tt)
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ẽ 1 đườ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

1
= 32
3 x
1
+ 4 x
2
≤ 84 ==> 3 x
1
+ 4 x
2
+ s
2
= 84
x
2
≤ 12 x
2
+ s
3
= 12
x
1
, x
2
≥ 0 x
1
, x
2
, s
1

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ẽ
không khả
dĩ.
15
3. Giới thiệu phương pháp đơn hình (tt)
16
3. Giới thiệu phương pháp đơn hình (tt)
c. Các lời giải (nghiệm) cơ sở nằm trong niềm 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.
17
3. Giới thiệu phương pháp đơn hình (tt)
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:

1
= 32
3 x
1
+4 x
2
+s
2
=84
x
2
+ s
3
=12
– 50 x
1
–80 x
2
+Z =0
18
3. Giới thiệu phương pháp đơn hình (tt)
B2. Lập bảng đơn hình ban đầu
Nghiệm khả dĩ cơ sở là (0, 0, 32, 84, 12) và Z = 0
Biến cơ sở là s
1
, s
2
, s
3
.

x
2
s
1
s
2
s
3
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
20
3. Giới thiệu phương pháp đơn hình (tt)
B4. 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.
x
1
x
2
s
1
s
2
s
3

1
s
2
s
3
Z RHS
1* 0 1 0 -2 0 8
3 0 0 1 -4 0 36
0 1 0 0 1 0 12
-50 0 0 0 80 1 960
x
1
x
2
s
1
s
2
s
3
Z RHS
1 0 1 0 -2 0 8
0 0 -3 1 2* 0 12
0 1 0 0 1 0 12
0 0 50 0 -20 1 1360
R
2
= R
2
+ (-3) R

+ 20 R
2
*1/2
Nghiệm khả dĩ cơ sở mới (0, 12, 8, 36, 0) và Z = 960.
Nghiệm khả dĩ cơ sở mới (8, 12, 0, 12, 0) và Z = 1360.
22
3. Giới thiệu phương pháp đơn hình (tt)
x
1
x
2
s
1
s
2
s
3
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) và Z = 1480
23
3. Giới thiệu phương pháp đơn hình (tt)
3.3. Phương pháp đơn hình cho bài toán MAX với ràng
buộc ≤ và cả ≥ và =:
VD: Giải bài toán QHTT
Max Z = x

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 s
i
)
Với ràng buộc ≥, thêm biến trừ (-s
i
) và biến nhân tạo…
Với ràng buộc =, thêm biến nhân tạo (ký hiệu a
i
)
Cộng –Ma
i
vào hàm mục tiêu Z, trong đó M là hằng số rất lớn…
Tất cả s
i
, a
i
đều ≥ 0.
VD: Max Z = x
1
– x
2
+ 3 x
3
– Ma
1
– Ma
2
x
1

2
+Z= 0
x
1
, x
2
, x
3
, s
1
, s
2
, a
1
, a
2
≥0
25
3. Giới thiệu phương pháp đơn hình (tt)
B2. Lập bảng đơn hình sơ bộ và ban đầu
Bảng sơ bộ
Bảng ban đầu (sau khi loại M trong cột a
i
)
x
1
x
2
x
3

0 1 1 0 0 -1 1 0 10
-M-1 -M+1 -3-2M 0 0 M 0 1 -15M
Nghiệm khả dĩ cơ sở ban đầu (0, 0, 0, 20, 5, 0, 10), Z = -15M
R
3
– R
2
R
4
+ (3 + 2 M) R
2