Bài giảng Tối ưu hóa trong thiết kế cơ khí - Chương 8: Quy hoạch tuyến tính (Linear Programming)

Trường Đại học Công nghiệp thành phố Hồ Chí Minh 
Khoa Công nghệ Cơ khí 
CHƯƠNG 08: 
QUY HOẠCH TUYẾN TÍNH 
(Linear Programming) 
Thời lượng: 3 tiết 
2 
Đặt vấn đề 
1. Quy hoạch tuyến tính (QHTT, 1930) là các bài toán tối ưu hóa mà 
ở đó hàm mục tiêu và toàn bộ các ràng buộc đều là hàm bậc 1 của 
các biến số. 
2. Các biểu thức ràng buộc có thể ở dạng đẳng thức (phương trình) 
hoặc bất đẳng thức (bất phương trình) tuyến tính. 
3. Các lĩnh vực ứng dụng của Quy hoạch tuyến tính: 
- Tối ưu hóa chế độ dinh dưỡng 
- Tối ưu hóa danh mục đầu tư 
- Bài toán sản xuất và vận chuyển 
- Bài toán viễn thông 
- Bài toán nhân viên bán dịch vụ du lịch 
- Trong kỹ thuật ngành cơ khí, thì QHTT giúp giải các bài toán thiết 
kế và sản xuất. Điển hình là các bài toán tối ưu hóa hình dạng 
(Shape Optimization), ví dụ như hình dáng khí động học của máy 
bay để giảm lực cản. Các ràng buộc có thể bao gồm hệ số nâng, 
độ dày tối đa tương đối, bán kính mũi, góc cạnh, v.v 
3 
Vấn đề 1 dẫn đến bài toán QHTT 
Trong các kết cấu khung thép, cần tính toán để tránh xuất hiện các 
“khớp dẻo”, là những điểm mà kết cấu có thể mất đi độ cứng và bị 
bẻ gãy dẻo như một khớp xoay. 
Khi mà số lượng các khớp dẻo tăng thì kết cấu sẽ có nguy cơ trở 
thành cơ cấu bị sụp gãy (a collapse mechanism). Để khắc phục vấn 
đề này, người ta cần phải làm tăng MÔMEN KHÁNG DẺO. 
Mômen kháng dẻo của một mặt cắt: 
d d cM Z   Zd – Môđun mặt cắt dẻo, σc – giới hạn chảy của vật liệu 
4 Ví dụ mômen kháng dẻo của mặt cắt dầm hình chữ nhật với chiều 
cao h, bề rộng b là: 
2
4
d c
bh
M 
  
Như vậy để tăng mô men kháng dẻo của mặt cắt thì hoặc là thay 
đổi vật liệu cứng hơn (làm tăng σc ), hoặc là tăng kích thước mặt cắt 
(b hoặc h hoặc cả 2). Nhưng điều này sẽ làm tăng khối lượng của 
kết cấu, tăng chi phí cho vật liệu. Chính vì vậy mà bài toán đặt ra là 
làm sao thiết kế được một kết cấu mà mômen kháng dẻo của nó đủ 
để giữ vững kết cấu không cho bị biến dạng dẻo, nhưng khối lượng 
của nó lại nhỏ nhất có thể. 
Kết cấu được cho là an toàn nếu khả năng hấp thụ năng lượng (thế 
năng đàn hồi U) của khung lớn hơn Công của ngoại lực (E) 
Thế năng biến dạng đàn hồi (U) sẽ được tính thông qua mômen 
kháng dẻo tại các điểm khớp dẻo. 
5 Vấn đề 1 dẫn đến bài toán QHTT 
Cho khung phẳng cấu tạo từ 2 cột 
và 1 dầm ngang chịu tải như hình. 
Tìm giá trị mômen khớp dẻo của 
cột (Mc) và dầm (Mb) để kết cấu đủ 
an toàn với khối lượng nhỏ nhất. 
P1=3 kN, P2=1 kN, h=8 m, l=10 m. 
 Có 4 khả năng khung biến dẻo 
1 1 24
4 c
E P P h
U M
  

    
Do có 4 khớp vị trí khớp 
dẻo của cột (Column) 
1 2
2 2 10
4 b
E P P l
U M
  

    
6 3 4
1 1 2 2 1 2 34
2 4c b
E P P Ph P l
U M M
   

    
1 1 24
2 2c b
E P P h
U M M
  

    
Hàm mục tiêu của bài toán: Cực tiểu hóa khối lượng khung gồm 
khối lượng của 2 cột và dầm ngang: 
 , 2 2 minc b b cf M M lM hM 
ρ – khối lượng riêng của khung theo 
chiều dài và mômen kháng dẻo 
Các ràng buộc xuất phát từ điều kiện U ≥ E ở 4 trường hợp: 
6
2.5
2 17
12
c
b
b c
b c
M
M
M M
M M
7 Gọi Mc=x1, Mb=x2, ta thu được mô hình toán: 
 1 2
1 2 1
2 1 2
3 1
4 2
20 16 min
2 17
12
6
2.5
f x x
g x x
g x x
g x
g x
x Bài toán QHTT 
Bài toán có 1 lời giải khi dùng phương pháp điều kiện KKT: 
min
0
6 16
; ; 216
6 4
0
f
* *
x λ
Các hàm ràng buộc gi có hạng tử 
bậc 0 ở bên kia dấu bất đẳng thức. 
Khác với việc trước đây đưa về 
dạng gi ≤0. 
8 
Vấn đề 2 dẫn đến bài toán QHTT 
Một xí nghiệp có thể sản xuất ra một loại sản phẩm theo 3 phương 
pháp khác nhau, k{ hiệu là PP1, PP2, PP3. Các loại nguyên liệu để sản 
xuất k{ hiệu là N1, N2, N3. Biết rằng số nguyên liệu hiện có, định 
mức tiêu hao các loại nguyên liệu và số lượng sản phẩm sản xuất ra 
trong một giờ theo các phương pháp cho ở bảng dưới: 
Nguyên 
liệu 
Số lượng 
hiện có (đv) 
Định mức tiêu hao trong một giờ 
PP1 PP2 PP3 
N1 250 4 5 3 
N2 350 2 4 1 
N3 450 3 6 4 
Sản lượng (đv/giờ) 10 12 9 
 Hãy tìm kế hoạch sản xuất tối ưu: 
Tìm số giờ sản xuất theo PP1, PP2, PP3 để tổng sản lượng do cả 3 
phương pháp sản xuất được lớn nhất có thể. 
9 
Vấn đề 2 dẫn đến bài toán QHTT 
Gọi x1, x2, x3 lần lượt là số giờ sản xuất theo PP1, PP2, PP3 tương ứng. 
Số nguyên liệu được sử dụng để sản xuất của 3 phương pháp là: 
- Nguyên liệu 1: 
- Nguyên liệu 2: 
- Nguyên liệu 3: 
1 2 34 5 3x x x 
1 2 32 4x x x 
1 2 33 6 4x x x 
Không vượt quá số lượng hiện có là 250 
Không vượt quá số lượng hiện có là 350 
Không vượt quá số lượng hiện có là 450 
Tổng sản lượng do 3 phương pháp sản xuất được là: 
1 2 310 12 9x x x 
Mô hình toán: 
1 2 3
1 1 2 3
2 1 2 3
3 1 2 3
10 12 9 max
4 5 3 250
2 4 350
3 6 4 450
0 1,2,3j
f x x x
g x x x
g x x x
g x x x
x j
Bài toán QHTT 
Các hàm ràng 
buộc gi có hạng tử 
bậc 0 ở bên kia 
dấu bất đẳng 
thức. Khác với 
việc trước đây 
đưa về dạng gi ≤0. 
10 
Vấn đề 3 dẫn đến bài toán QHTT 
Một xí nghiệp may mặc cần sản xuất 2000 chiếc quần và tối thiểu 
1000 cái áo. Về mặt l{ thuyết, mỗi 1 tấm vải có thể cắt ra được 1 số 
lượng quần và áo theo 6 cách khác nhau, như trong bảng dưới đây: 
Cách cắt Quần Áo 
1 90 35 
2 80 55 
3 70 70 
4 60 90 
5 120 0 
6 0 100 
Hãy tìm kế hoạch sản xuất tối ưu: 
Tìm số tấm vải cắt theo từng cách để sao cho tổng số vải sử dụng là 
ít nhất 
11 
Vấn đề 3 dẫn đến bài toán QHTT 
Gọi xj, (j=1..6) lần lượt là số tấm vải cắt theo cách thứ j, khi đó ta có: 
Do tổng số quần cần sản xuất là 2000 nên ta có phương trình: 
1 2 3 4 590 80 70 60 120 2000x x x x x 
Do tổng số áo cần sản xuất tối thiểu là 1000 nên ta có điều kiện: 
1 2 3 4 635 55 70 90 100 1000x x x x x 
Tổng số tấm vải cần sử dụng là: 
6
1
j
j
x

Mô hình toán: 
6
1
1 1 2 3 4 5
2 1 2 3 4 6
min
90 80 70 60 120 2000
35 55 70 90 100 1000
0, 1..6
j
j
j j
f x
g x x x x x
g x x x x x
x x j
x
N
12 
Vấn đề 4 dẫn đến bài toán QHTT 
Một nhà đầu tư có 70 tỉ đồng muốn đầu tư vào các loại hình sau: 
- Tiết kiệm không kz hạn với lãi suất 6.5% 
- Tiết kiệm có kz hạn với lãi suất 8.5% 
- Mua trái phiếu chính phủ với lãi suất 10% 
- Cho tư nhân vay với lãi suất 13% 
Thời gian đáo hạn được cho là như nhau. Các loại hình đầu tư này 
đều có rủi ro và do đó người đầu tư muốn làm theo các chỉ dẫn sau 
của nhà tư vấn: 
1. Không cho tư nhân vay quá 20% số vốn 
2. Số tiền mua trái phiếu không nên vượt quá tổng số tiền đầu tư 
vào 3 lĩnh vực kia 
3. Ít nhất 30% số tiền đầu tư phải thuộc tiết kiệm có kz hạn và trái 
phiếu 
4. Tỷ lệ tiền tiết kiệm không kz hạn trên tiền tiết kiệm có kz hạn 
không vượt quá 1/3 
Người này cần đầu tư mỗi khoản như thế nào với toàn bộ số tiền 
này để lợi nhuận thu được là tối đa? 
13 1) Xác định các biến số. Gọi: 
- x1 là số tiền gửi tiết kiệm không kz hạn 
- x2 là số tiền gửi tiết kiệm có kz hạn. 
- x3 là số tiền mua trái phiếu 
- x4 là số tiền cho tư nhân vay 
2) Xác định hàm mục tiêu: 
Tổng lợi nhuận người đó thu được: 
1 2 3 40.065 0.085 0.1 0.13x x x x 
3) Xác định các ràng buộc: 
[1]: 
[2]: 
[3]: 
[4]: 
[5]: 
4 14x tỷ 
3 1 2 4x x x x 
2 3 21x x tỷ 
1
2
1
3
x
x
1 2 3 4 70x x x x 
1 2 3 4
1 1
2 1 2 3 4
3 2 3
4 1 2
5 1 2 3 4
0.065 0.085 0.1 0.13 max
14
0
21
1
0
3
70
0, 1..4j j
f x x x x
g x
g x x x x
g x x
g x x
g x x x x
x x j
 N
Mô hình toán: 
14 
Vấn đề 5 dẫn đến bài toán QHTT 
Để nuôi một loại gia súc trong 24 giờ cần có khối lượng tối thiểu các 
chất tương ứng là: 
- 90 gr Protit 
- 130 gr Gluxit 
- 10 gr chất khoáng 
Tỷ lệ % theo khối lượng của các chất trên có trong 3 loại thức ăn A, 
B, C như sau: 
Thức ăn 
Chất dinh dưỡng 
Protit Gluxit Khoáng 
A 10 30 2 
B 20 40 1 
C 30 20 3 
 Giá 1 kg thức ăn A, B, C lần lượt là 3000 đ, 4000 đ, 5000 đ 
Xác định khối lượng (đơn vị gr) thức ăn A, B, C cần mua trong ngày 
sao cho tổng chi phí để mua các loại thức ăn là thấp nhất. 
15 1) Xác định các biến số. Gọi x1, x2, x3 lần lượt là số gram thức ăn A, 
B, C cần mua xj ≥ 0 (j=1..3) 
2) Xác định các ràng buộc: 
Lượng chất dinh dưỡng có trong toàn bộ khẩu phần thức ăn cần mua: 
- Proteit: 0.1 x1 + 0.2 x2 + 0.3 x3 tối thiểu là 90 gr 
- Gluxit: 0.3 x1 + 0.4 x2 + 0.2 x3 tối thiểu là 130 gr 
- Khoáng: 0.02 x1 + 0.01 x2 + 0.03 x3 tối thiểu là 10 gr 
3) Xác định hàm mục tiêu: Tổng chi phí cho khẩu phần thức ăn trong 
ngày là: 3 x1 + 4 x2 + 5 x3 (đồng) 
1 2 3
1 1 2 3
2 1 2 3
3 1 2 3
3 4 5 min
0.1 0.2 0.3 90
0.3 0.4 0.2 130
0.02 0.01 0.03 10
0 1..3j
f x x x
g x x x
g x x x
g x x x
x j
x
Mô hình toán: 
16 
Vấn đề 6 dẫn đến bài toán QHTT 
Tại sân bay Tân Sân Nhất có nhu cầu vận chuyển 
1200 hành khách và 120 tấn hàng bằng máy bay. Giả 
sử có 2 loại máy bay có thể sử dụng với khả năng 
vận chuyển của mỗi loại như sau: 
- Máy bay loại A: Mỗi máy bay có thể chở 150 hành 
khách và 20 tấn hàng với chi phí là 240 triệu đồng 
- Máy bay loại B: Mỗi máy bay có thể chở 180 hành 
khách và 16 tấn hàng với chi phí là 220 triệu đồng 
Hãy tìm phương án sử dụng số máy bay mỗi loại sao 
cho thỏa mãn yêu cầu vận chuyển với tổng chi phí là 
ít nhất. 
17 
1) Xác định các biến số. Gọi xj, (j=A, B) lần lượt là số lượng máy bay 
loại j cần sử dụng xj ≥ 0 (j=A, B), xj ϵ N (j=A, B) 
2) Xác định hàm mục tiêu: 
Tổng chi phí vận chuyển là: 240 xA + 220 xB (triệu đồng) 
3) Xác định các ràng buộc: 
- Tổng cộng 1200 hành khách cần phải chở: g1 = 150 xA + 180 xB = 1200 
- Tổng cộng 120 tấn hàng cần phải chở: g2 = 20 xA + 16 xB = 120 
1
2
240 220 min
150 180 1200
20 16 120
0, ,
A B
A B
A B
j j
f x x
g x x
g x x
x x j A B
x
N
Mô hình toán: 
18 Các dạng của bài toán QHTT 
Tìm 1 2, , , nx x x x sao cho: 
1
min max 1
n
j j
j
f c x
 x
Với điều kiện: 
  
1
1 1 2 2
1.. 2
0 1.. ; 0 1 .. ; 3
n
ij j i
j
j j
a x b i m
x j n x j n n n n

(1) là hàm mục tiêu 
(2) Có m phương trình/bất phương trình ràng buộc 
(3) Ràng buộc về dấu (đối với ẩn số) 
 Bài toán QHTT gọi là giải được nếu có ít nhất 1 phương án tối ưu 
19 Các dạng của bài toán QHTT 
Tìm 1 2, , , nx x x x sao cho: 
1
min max 1
n
j j
j
f c x
 x
Với điều kiện: 
  
1
1.. 4
0 1.. 5
n
ij j i
j
j
a x b i m
x j n

Bất kz bài toán QHTT tổng quát nào cũng đều có thể đưa về dạng 
chính tắc nhờ các phép biến đổi tương đương sau: 
20 
1
1
1
1 0
n
n
ij j n i
jij j i
j
n
a x x b
a x b
x


• Nếu ràng buộc có dạng ≥ 
thì trừ đi 1 ẩn phụ không 
âm 
 Khi đó thì hệ số của các ẩn phụ xn+1 trong hàm mục tiêu sẽ = 0 
• Nếu biến xj ≤ 0 được thay 
bằng: 
0
0
j j
j
j
x x
x
x
• Nếu biến xj không có ràng 
buộc về dấu thì được thay 
bằng hiệu của 2 biến 
không âm 
0
0
j j j
jj
j
x x x
xx
x
1
1
1
1 0
n
n
ij j n i
jij j i
j
n
a x x b
a x b
x


• Nếu ràng buộc có dạng ≤ 
thì cộng thêm 1 ẩn phụ 
không âm 
21 
 1 2 3
1 2 3
1 2 3
1 2 3
1 3
3 2 min
3 2 17
2 4 12
4 3 8 10
0; 0
f x x x
x x x
x x x
x x x
x x
x
3 3
3
3
2 2 2
2
2 2
0
0
0; 0
x x
x
x
x x x
x
x x
1 2 2 3
1 2 2 3 4
1 2 2 3
1 2 2 3 5
2
3 2 min
3 2 17
2 4 12
4 3 8 10
0 1,4,5 ; 0 2,3 ; 0j j
f x x x x
x x x x x
x x x x
x x x x x
x j x j x
x
1 2 3 4
1 2 3 4 5 6
1 2 3 4 5 6
1 2 3 4 5 6
3 3 2 min
3 2 0 17
2 4 4 0 0 12
4 3 3 8 0 10
0 1..6j
f x x x x
x x x x x x
x x x x x x
x x x x x x
x j
x
22 
Các dạng của bài toán QHTT 
Là trường hợp đặc biệt của bài toán dạng chính tắc. Khi ma trận hệ 
số của (4) chứa một ma trận đơn vị cấp m (có thể đưa về ma trận 
đơn vị bằng cách đổi chỗ các cột cho nhau) và bi ≥ 0 (i=1..m). 
Tìm 1 2, , , nx x x x sao cho: 
1
min max 1
n
j j
j
f c x
 x
Với điều kiện: 
  
,
1
1.. 6
0 1.. 7
0 1.. 5
n m
i i m k m k i
k
i
j
x a x b i m
b i m
x j n

23 
1, 1 1,
2, 1 2,
, 1 ,
1 0 0
0 1 0
0 0 1
m n
m n
m m m n
a a
a a
A
a a
 ,
1
6 1..
n m
i i i m k m k
k
x b a x i m
 
xi – ẩn cơ bản (i=1..m) 
xm+k – ẩn không cơ bản [k=1..(n-m)] 
• Một phương án mà các ẩn không cơ bản bằng 0 được gọi là 
phương án cơ bản (hay phương án cực biên) 
• Một phương án cơ bản có ít nhất 1 ẩn cơ bản bằng 0 gọi là phương 
án cơ bản suy biến 
• Một bài toán có ít nhất 1 phương án cơ bản suy biến gọi là bài toán 
suy biến 
24 
Ẩn cơ bản, phương án cơ bản 
2 5
1 2 3 4 3
1 2 3 4 5
1 2 3 4 5
min
0 0 2 1
0 3 0 3
0 2 0 2
0 1..5j
f x x
x x x x x
x x x x x
x x x x x
x j
x 
2 5
1 2 3
2 3 5
2 4 5
min
2 1
3 3
2 2
0 1..5j
f x x
x x x
x x x
x x x
x j
x
1 1 0 0 2 1
0 3 1 0 1 3
0 2 0 1 1 2
A
Ma trận hệ số 
Cột 1, 3, 4 tạo thành 
ma trận đơn vị cấp 3 
Các ẩn x1, 
x3, x4 lần 
lượt là các 
ẩn cơ bản 
của các ràng 
buộc 1, 2, 3 
1
0
3
2
0
0x
PA cơ bản 
ban đầu 
 0f 0x
25 
Mọi bài toán QHTT đều có thể đưa về dạng chính tắc tương ứng. Có 
1 vài tính chất quan trọng với bài toán dạng chính tắc như sau, giả 
thiết m ràng buộc độc lập tuyến tính và m<n: 
1) Tính chất 1: (Sự tồn tại phương án cơ bản PACB) 
Nếu bài toán có phương án thì có phương án cơ bản 
2) Tính chất 2: (Sự tồn tại phương án cơ bản tối ưu) 
Nếu bài toán có phương án tối ưu PATƯ thì có phương án cơ bản 
tối ưu PACBTƯ 
3) Tính chất 3: (Tính hữu hạn của số phương án cơ bản) 
Số phương án cơ bản khác nhau trong mỗi bài toán là hữu hạn 
4) Tính chất 4: (Sự tồn tại phương án tối ưu) 
Nếu bài toán có phương án và trị số hàm mục tiêu bị chặn dưới 
(trên) trên tập phương án khi f(x) min (max) thì bài toán có 
phương án tối ưu. 
26 Phương pháp hình học 
Trong trường hợp bài toán QHTT có 2 biến thì ta có thể giải bằng 
phương pháp hình học. Áp dụng các ứng dụng sau đây: 
1) Đường thẳng ax1 + bx2 = c chia mặt phẳng tọa độ thành 2 miền: 
Một miền là tập hợp tất cả các điểm M(x1,x2) thỏa mãn bất phương 
trình ax1 + bx2 > c , một miền là tập hợp tất cả các điểm M(x1,x2) thỏa 
mãn bất phương trình ax1 + bx2 < c. 
1x
2x
1 2ax bx c 
 1 2,M x x thỏa mãn 1 2ax bx c
 1 2,M x x
thỏa mãn 1 2ax bx c
27 Phương pháp hình học 
2) Họ đường thẳng cx1 + dx2 = m (m ϵ R) là tập hợp các đường thẳng 
song song với nhau mà ta gọi là đường đồng mức (tương ứng với giá 
trị mức m). Nếu ta di chuyển một đường thẳng trong họ (một đường 
đồng mức) đến một đường thẳng khác trong họ theo hướng của 
véctơ Gradient (c,d) thì giá trị tương ứng của m tăng, còn theo 
hướng ngược lại thì giá trị tương ứng của m giảm. 
1x
2x
1 2 4cx dx m 
 ,c d c
1 2 1cx dx m 
1 4m m 
Độ dốc (Hướng tăng 
mức giá trị m) 
28 
ax1 + bx2 = c
1 2
1 2 1
x x
ax bx c
c c
a b
1x
2x
1 2ax bx c 
c
a
c
b
29 Phương pháp hình học 
1) Vẽ các đường thẳng ràng buộc trong mặt phẳng tọa 
độ x1Ox2 
2) Xác định các nửa mặt phẳng hợp lệ 
3) Xác định miền lời giải đa giác hợp lệ 
4) Vẽ véc tơ Gradient (c,d) chỉ hướng tăng của hàm mục 
tiêu 
5) Dịch chuyển đường thẳng hàm mục tiêu theo hướng 
véctơ Gradient hoặc ngược lại đến các đỉnh ngoài 
cùng để tìm giá trị lớn nhất hoặc nhỏ nhất của hàm 
mục tiêu. 
6) Tính tọa độ các điểm cực trị và giá trị hàm mục tiêu 
trong điểm cực trị đó 
30 Phương pháp hình học 
 1 2
1 2
1 2
1
2
max
7
3
0 4
2 5
f x x
x x
x x
x
x
x
max
4
2
2f
maxx
2
5
31 Phương pháp hình học 
 1 2
1 2
1 2
1
2
2 2 min
2
1
1
2
1
4
f x x
x x
x x
x
x
x
min
min
1
2
1
4
3
2
f
x
32 Phương pháp hình học 
 1 2
1 2
1 2
1 2
1
2
3 4 max
3 4 18
3 3
2
0 5
0 6
f x x
x x
x x
x x
x
x
x
max
1
max
max max
2 1
max
26
2
7
9 3
2 4
18
x
x x
f
x
33 Phương pháp hình học 
 1 2
1 2
1 2
1 2
1
2
3 4 min
3 4 18
3 3
2
0 5
0 6
f x x
x x
x x
x x
x
x
x
min
1
min
min min
2 1
min
26
2
7
9 3
2 4
18
x
x x
f
x
34 Phương pháp hình học 
 1 2
1 2
1 2
1 2
1 2
max
4
1
3
2 3
2
, 0
f x x
x x
x x
x x
x x
x
max
1
max
max max
2 1
max
10
7
1
1
x
x x
f
x
35 Phương pháp hình học 
 1 2
1 2
1 2
1 2
1 2
3 min
24
1
1
3
3
2 9
2
, 0
f x x
x x
x x
x x
x x
x
min
1
min min min
2 1
min
2
3 3
3
x
x x
f
x
36 Phương pháp hình học 
 1 2
1 2
1 2
1 2
1 2
max
3 2 1
3
1
4
5
1
4
, 0
f x x
x x
x x
x x
x x
x
maxf 
37 Phương pháp hình học 
 1 2
1 2
1 2
1
2
2 min
3
1
5
4 6 3
0
1
2
f x x
x x
x x
x
x
x
minf 
38 Phương pháp hình học 
 1 2
1 2
1 2
1
2
max/ min
1
1
0 1
0
f x x
x x
x x
x
x
x
min/max
min/max
1
0
1f
x
39 Phương pháp hình học 
 1 2
1 2
1 2
1 2
1 2
max/ min
3 5 32
4 3 12
8
7
3
, 0
f x x
x x
x x
x x
x x
x
Không tồn tại miền hợp 
lệ (tập hợp rỗng). Vì thế 
hàm không có cực đại 
cũng như cực tiểu. 
40 Phương pháp đơn hình 
Theo các tính chất của bài toán QHTT, để tìm PATƯ 
của bài toán ta chỉ cần xét các PACB. 
Xuất phát từ một phương án cơ bản ban đầu x0 nào 
đó, tìm cách đánh giá nó. Nếu nó chưa phải là PATƯ 
thì tìm cách chuyển sang một PACB mới x1 tốt hơn. 
Quá trình này được lặp lại chừng nào còn có khả năng 
thực hiện sự di chuyển ấy. Vì số PACB là hữu hạn nên 
sau một số hữu hạn bước lặp hoặc sẽ thu được PATƯ 
của bài toán, hoặc sẽ kết luận bài toán không giải 
được vì hàm mục tiêu không bị chặn. 
 Vì cần xuất phát từ các PACB nên ta phải đưa bài 
toán về dạng chuẩn 
41 Phương pháp đơn hình 
Đầu tiên phải đưa bài toán về dạng chuẩn: 
Tìm 1 2, , , nx x x x sao cho: 
1
min max 1
n
j j
j
f c x
 x
Với điều kiện: 
,
1
1.. 6
0 1.. 7
0 1.. 5
n m
i i m k m k i
k
i
j
x a x b i m
b i m
x j n

 01 2
1
, , , ,0, ,0
m
m i i
in m
b b b f c b f
  
 
 
0 0x x
Phương án 
cơ bản 
42 
Xét 1 phương án x’ bất kz của bài toán: 
0
,
1 1 1 1 1 1
,
1 1 1 1
,
;
m k
n m n m m n m n m
j j i i m k m k i i i m k m k m k m k
j i k i k k
m n m m n m
i i i m k i m k m k m k m k
i k i k
f f
m k i m k
f C x C x C x C b a x C x
C b a C C x f f x
a
     
   
0
0
x
x
x x
1
m
i m k
i
C C 
  Δm+k – ước lượng của ẩn xm+k đối với PACB x0 
Do x’m+k ≥ 0 ɏ k nên nếu Δm+k ≤ 0 ɏ k thì f(x’)≥f(x
0) f(x0) là giá trị 
nhỏ nhất x0 là phương án tối ưu 
Dấu hiệu tối ưu: 
Nếu với một phương án cơ bản nào đó mà Δj ≤ 0 ɏ j thì đó
 là 
phương án tối ưu 
43 
Nếu với một phương án cơ bản nào đó tồn tại một Δj ≤ 0 mà aij ≤0 
ɏ i thì ta có thể tìm được một dãy phương án mà trên đó hàm 
mục tiêu giảm vô hạn, nghĩa là bài toán không có phương án tối 
ưu. 
Nếu với một phương án cơ bản nào đó mà mỗi Δj > 0 đều tồn tại 
ít nhất aij > 0 thì có thể tìm được một phương án cơ bản mới tốt 
hơn theo nghĩa giá trị hàm mục tiêu giảm 
44 
 01 2
1
, , , ,0, ,0
m
m i i
in m
b b b f c b f
  
 
 
0 0x xXuất phát từ phương án 
cơ bản 
Hệ số 
Ẩn 
CB 
PACB 
c1 c2  cr  cm cm+1  cs↓  cn 
x1 x2  xr  xm xm+1  xs  xn 
c1 x1 b1 1 0  0  0 a1,m+1  a1,s  a1,n 
c2 x2 b2 0 1  0  0 a2,m+1  a2,s  a2,n 
rc xr br 0 0  1  0 ar,m+1  ,r sa  ar,n 
cm xm bm 0 0  0  1 am,m+1  am,s  am,n 
 f(x) f(x
0
) 0 0  0  0 Δm+1  Δs  Δn 
1..j n 1..i m 
1
; 1 ..
m
j i ij j
i
c a c j m n
 
45 
1. Tính Δj [j=(m+1)..n] 
2. Kiểm tra tính tối ưu của phương án: 
• Nếu Δj ≤ 0 ɏ j=(m+1)..n thì phương án tương ứng là tối ưu Dừng 
• Nếu có ít nhất một Δj > 0 chuyển sang bước 3 
3. Kiểm tra tính không giải được của bài toán: 
• Nếu có một Δj > 0 mà toàn bộ aij ≤ 0 ɏ i=1..m, hay nói cách khác nếu 
mọi phần tử trên cột xj của bảng đều không dương thì bài toán 
không có phương án tối ưu vì hàm mục tiêu – vô cùng 
• Nếu với mỗi Δj > 0 đều có ít nhất một aij > 0 thì chuyển sang bước 4 
4. Chọn ẩn đi vào và xác định ẩn đi ra khỏi hệ cơ bản: 
• Chọn ẩn ứng với max Δj >0, giả sử max Δj = Δs>0 ẩn xs là ẩn đi vào 
• Chọn tất cả các ais>0 của ẩn xs, tính tất cả các tỉ lệ bi/ais, tìm 
min(bi/ais) giả sử = br/ars xr là ẩn đi ra ars là phần tử xoay 
5. Biến đổi bảng để thu được PACB mới tốt hơn: 
• Lập bảng mới, trong cột Ẩn cơ bản thay xr bởi xs, trong cột hệ số 
thay cr bởi cs. 
• (Tiếp)↓ 
46 
• Để thu được dòng xs trong bảng mới, ta chia dòng xr ở bảng cũ cho 
phần tử xoay ars (gồm br và arj, j=1..n đều cần chia cho ars). Đây sẽ là 
dòng chuẩn (trong bảng mới) 
• Để thu được bất kz dòng i nào trong số còn lại (trong bảng mới), 
i=1..m ta lấy dòng đó ở bảng cũ trừ đi dòng chuẩn sau khi đã nhân 
nó với phần tử ais (Phần tử ais nằm trên giao của cột xs với dòng 
đang xét ở bảng cũ). Kết quả thu được cho ta một phương án cơ 
bản mới với đầy đủ những tham số cần thiết cho trong bảng đơn 
hình tương ứng. 
• Quay lại bước 1 
47 
1. Nếu f(x) max thì có 2 cách xử l{: 
- Cách 1: Chuyển bài toán thành g(x) = -f(x) min, miền ràng 
buộc không thay đổi. Phương án tối ưu của bài toán g(x) là 
phương án tối ưu của bài toán f(x) nhưng fmax = -gmin 
- Cách 2: Giải trực tiếp bài toán f(x) max khi chỉ cần thay đổi 
tiêu chuẩn tối ưu là Δj ≥ 0 ɏ j=(m+1)..n và ẩn đi vào ứng với 
min Δj = Δs<0 
2. Nếu trong bảng đơn hình sau khi tìm được phương án tối ưu 
còn tồn tại Δi = 0 với xi là ẩn không cơ bản thì đó là dấu hiệu của 
bài toán tồn tại nhiều phương án tối ưu. 
Muốn tìm PACB tối ưu khác, ta chọn xi làm ẩn đi vào hệ ẩn cơ 
bản và áp dụng thuật toán đơn hình ta sẽ thu được PATƯ khác. 
*) Ẩn không cơ bản p là không phải ẩn cơ bản nhưng lại có Δp = 0 
48 
1 2 3 4 5 6 7
1 2 4 6 7 1 2 3 4 5 6 7
1 3 4 6 7
1 4 5 6
6 3 7 6 min
3
2 4 2 9 1 1 0 1 0 1 1 3
4 2 3 2 2 0 1 4 0 2 1 9
4 0 0 2 1 3 0 20 1..7j
f x x x x x x x
x x x x x x x x x x x x
x x x x x
x x x x
x j
x
Hệ 
số 
Ẩn 
CB 
PACB 
6 1 1 3 1 -7 6 
x1 x2 x3 x4 x5 x6 ↓ x7 
1 ← x2 3 -1 1 0 -1 0 1 1 
1 x3 9 -2 0 1 -4 0 2 -1 
1 x5 2 4 0 0 2 1 -3 0 
 f(x) f(x
0
)=14 -5 0 0 -6 0 7 6 
-7 x6 3 -1 1 0 -1 0 1 1 
1 x3 3 0 -2 1 -2 0 0 -3 
1 x5 11 1 3 0 -1 0 0 3 
 f(x) f(x
1
)=-7 2 -7 0 1 0 0 -13 
Do có một Δ4 = 1> 
0 mà toàn bộ ai4 ≤ 
0 ɏ i=1..3. 
 Không có PA 
tối ưu 
49 
1 2 3 4 5 6
1 2 3 4 1 2 3 4 5 6
1 2 3 5
1 3 6
5 4 5 2 3 min
2 4 3 152
4 2 3 60 2 4 3 1 0 0 152
3 36 4 2 3 0 1 0 60
3 0 1 0 0 1 360 1..6j
f x x x x x x
x x x x x x x x x x
x x x x
x x x
x j
x
PA tối ưu là: 
 min
min
12,6,0,104,0,0
292
T
f
x
Hệ 
số 
Ẩn 
CB 
PACB 
5 4 5 2 1 3 
x1↓ x2↓ x3 x4 x5 x6↓ 
2 x4 152 2 4 3 1 0 0 
1 x5 60 4 2 3 0 1 0 
3 ← x6 36 3 0 1 0 0 1 
 f(x) f(x
0
)=472 12 6 7 0 0 0 
2 x4 128 0 4 7/3 1 0 -2/3 
1 ← x5 12 0 2 5/3 0 1 -4/3 
5 x1 12 1 0 1/3 0 0 1/3 
 f(x) f(x
1
)=328 0 6 3 0 0 -4 
2 x4 104 0 0 -1 1 -2 2 
4 x2 6 0 1 5/6 0 0.5 -2/3 
5 ← x1 12 1 0 1/3 0 0 
1
3
 f(x) f(x
2
)=292 0 0 -2 0 -3 0 
*) Ẩn x6 không phải ẩn cơ bản 
nhưng lại có Δ6 = 0 
 Bài toán có lời giải không 
duy nhất. Ta thử tìm 1 lời giải 
khác bằng cách đưa x6 vào. 
50 
Hệ 
số 
Ẩn 
CB 
PACB 
5 4 5 2 1 3 
x1 x2 x3 x4 x5 x6 
2 x4 32 -6 0 -3 1 -2 0 
4 x2 30 2 1 1.5 0 0.5 0 
3 x6 36 3 0 1 0 0 1 
 f(x) f(x
3
)=292 0 0 -2 0 -3 0 
*) Ẩn x1 không phải ẩn cơ bản nhưng lại có Δ1 = 0 
 Bài toán có lời giải không duy nhất. 
 Ta có phương án tối ưu thứ 2 và có thể tiếp tục tìm phương án tối 
ưu thứ 3 nếu muốn 
51 
1 2 3 4
1 2 3 4
2 3 4
3 4
2 max
2 2
7 3 2
3 2 5
0 1..4j
f x x x x
x x x x
x x x
x x
x j
x
Dạng tổng quát 
Dạng chuẩn 
1 2 3 4
1 2 3 4 1 2 3 4 5 6
2 3 4 5
3 4 6
2 max
2 2
7 3 2 1 1 2 1 0 0 2
3 2 5 0 1 7 3 1 0 2
0 0 3 2 0 1 50 1..6j
f x x x x
x x x x x x x x x x
x x x x
x x x
x j
x
Giải trực tiếp bài toán f(x) 
max khi chỉ cần thay đổi tiêu 
chuẩn tối ưu là Δj ≥ 0 ɏ 
j=(m+1)..n và ẩn đi vào ứng 
với min Δj = Δs<0 
52 
Hệ 
số 
Ẩn 
CB 
PACB 
-2 -1 1 1 0 0 
x1 x2 x3↓ x4↓ x5 x6 
-2 ← x1 2 1 1 2 -1 0 0 
0 x5 2 0 -1 -7 3 1 0 
0 x6 5 0 0 -3 2 0 1 
 f(x) f(x
0
)=-4 0 -1 -5 1 0 0 
1 x3 1 0.5 0.5 1 -0.5 0 0 
0 x5 9 3.5 2.5 0 -0.5 1 0 
0 ← x6 8 1.5 1.5 0 0.5 0 1 
 f(x) f(x
1
)=1 2.5 1.5 0 -1.5 0 0 
1 x3 9 2 2 1 0 0 1 
0 x5 17 5 4 0 0 1 1 
1 x4 16 3 3 0 1 0 2 
 f(x) f(x
2
)=25 7 6 0 0 0 2 
PA tối ưu là: 
 max
max
0,0,9,16,17,0
25
T
f
x
53 
1 2 3
1 2 3
1 2 3
8 6 2 min
4 4 3 18
4 4 3 18
4 3 4 16
4 3 4 16
0 1..3j
f x x x
x x x
x x x
x j
x
Chuyển về dạng RREF 
1 2 3
25 5
1 0
4 2
0 1 7 2
x x x 
Hệ 
số 
Ẩn 
CB 
PACB 
-8 6 2 
x1 x2 x3 
-8 x1 5/2 1 0 25/4 
6 x2 2 0 1 -7 
 f(x) f(x
0
)=-8 0 0 -10 
PA tối ưu là: 
min
min
5
,2,0
2
8
T
f
 
 
 
x
54 
1 2 3
1 2 3 4
1 2 3
1 2 3
6 3 min
2 5 10
2 5 1 1 10
4 3 2 16
4 3 2 0 16
2 4 8
2 4 1 0 8
0 1..4j
f x x x
x x x x
x x x
x x x
x j
x Chuyển về dạng RREF 
1 2 3 4
1 0 0.5 0 4
0 1 0 0 0
0 0 0 1 2
x x x x 
Hệ 
số 
Ẩn 
CB 
PACB 
6 3 1 0 
x1 x2 x3↓ x4 
6 ← x1 4 1 0 12 0 
3 x2 0 0 1 0 0 
0 x4 2 0 0 0 1 
 f(x) f(x
0
)=24 0 0 2 0 
1 x3 8 2 0 1 0 
3 x2 0 0 1 0 0 
0 x4 2 0 0 0 1 
 f(x) f(x
1
)=8 -4 0 0 0 
PA tối ưu là: 
 min
min
0,0,8
8
T
f
x
55 
1 2 3
1 2 3
1 2 3
1 2 3
2 max
4 2 12
2 2 2 10
1
2 20
2
0 1..3j
f x x x
x x x
x x x
x x x
x j
x
Chuyển về dạng chính tắc 
1 2 3
1 2 3 4
1 2 3 5
1 2 3
2 max
4 2 12
2 2 2 10
1
2 20
2
0 1..5j
f x x x
x x x x
x x x x
x x x
x j
x
1 2 3 4 5
5 1 145
1 0 0
27 6 27
1 92
0 1 0 0
9 9
2 1 266
0 0 1
27 3 27
x x x x x 
Do x2, x4 ≥0 nên 
ràng buộc thứ 2 
là không thể đáp 
ứng. Bài toán 
không có PATƯ. 
56 
1. Vế phải bi ≥ 0 
2. Nếu không thỏa mãn điều kiện trên ta cần thiết hoán đổi các 
cột ẩn số để khi đưa về RREF được thỏa mãn 
1 2 4
1 2 3 4 5
1 2 3 4
1 2 3 4 5
2 2 28
5 3 2 31
2 2 2 16
0 1..5
2 2 0 1 0 28
1 5 3 2 1 31
2 2 2 1 0 16
j
x x x
x x x x x
x x x x
x j
x x x x x
A

1 2 3 4 5
4 5 3 2 1
4 5 3 2 1
3 1
211 0 0
4 10
2
1 1
70 1 0
4 10
2
1 1
10 0 1
2 5
1 0 0 2 2 28
2 1 3 5 1 31
1 0 2 2 2 16
1 0 0 2 2 28
0 1 0 15 5 105
0 0 1 2 0 6
x x x x x
x x x x x
A
x x x x x