Bài giảng Toán tài chính - Chương 5B: Quy hoạch tuyến tính hai biến

QUY HOẠCH 
TUYẾN TÍNH
HAI BIẾN + 
CHƯƠNG
5B
VÍ DỤ 1
Một xí nghiệp cần sản xuất 3 loại bánh: bánh đậu xanh, 
bánh thập cẩm và bánh dẻo. Lượng nguyên liệu đường, 
đậu cho một bánh mỗi loại, lượng dự trữ nguyên liệu, 
tiền lãi cho một bánh mỗi loại được cho trong bảng sau: 
Hãy lập mô hình bài toán tìm số lượng mỗi loại bánh cần 
sản xuất sao cho không bị động về nguyên liệu mà lãi đạt 
được cao nhất.
VÍ DỤ 1
Gọi x1,x2,x3 lần lượt là số bánh đậu xanh, bánh thập
cẩm, bánh dẻo cần phải sản xuất.
Điều kiện: xj ≥ 0  = 1,2,3
Tiền lãi thu được (ngàn đồng)
Lượng đường sử dụng và điều kiện:
Lượng đậu sử dụng và điều kiện:
 1 2 3 1 2 3, , 3 2 2,5f x f x x x x x x 
1 2 30,04 0,06 0,05 500x x x 
1 30,07 0,02 300x x 
VÍ DỤ 1
Vậy ta có mô hình bài toán:
Đây là bài toán quy hoạch tuyến tính 3 biến, tìm giá trị
lớn nhất của hàm mục tiêu.
1 2 3 1 2 3
1 2 3
1 3
, , 3 2 2,5 max
0,04 0,06 0,05 500
0,07 0,02 300
0 1,2,3j
f x f x x x x x x
x x x
x x
x j
VÍ DỤ 2
Giả sử yêu cầu tối thiểu mỗi ngày về các chất dinh dưỡng 
đạm, đường, khoáng cho một loại gia súc tương ứng là 90g, 
130g, 10g. Cho biết hàm lượng các chất dinh dưỡng trên có 
trong 1g thức ăn A, B, C và giá mua 1kg thức ăn mỗi loại được 
cho trong bảng sau:
Hãy lập mô hình toán học của bài toán xác định khối lượng 
thức ăn mỗi loại phải mua để tổng số tiền chi cho mua thức 
ăn ít nhất nhưng đáp ứng được nhu cầu dinh dưỡng mỗi 
ngày.
VÍ DỤ 3
Một cơ sở sản xuất đồ gỗ dự định sản xuất ba loại sản phẩm là 
bàn, ghế và tủ. Định mức sử dụng lao động, chi phí sản xuất và giá 
bán mỗi sản phẩm mỗi loại ước tính trong bảng sau:
Hãy lập mô hình toán học của bài toán xác định số sản phẩm mỗi 
loại cần phải sản xuất sao cho không bị động trong sản xuất và 
tổng doanh thu đạt được cao nhất, biết rằng cơ sở có số lao động 
tương đương với 500 ngày công, số tiền dành cho chi phí sản xuất 
là 40 triệu đồng và số bàn, ghế phải theo tỉ lệ 1/6.
VÍ DỤ 4
Một trại cưa các khúc gỗ thành các tấm ván. Có hai loại
ván: ván thành phẩm và ván sử dụng trong xây dựng. Giả
sử, đối với:
Ván thành phẩm cần 2 giờ để cưa và 5 giờ để bào 10m 
ván
Ván xây dựng cần 3 giờ để cưa và 3 giờ để bào 10m ván
Máy cưa làm việc tối đa 8 giờ trong ngày và máy bào làm
việc tối đa 15 giờ trong ngày. Nếu lợi nhuận của 10m ván
thành phẩm là 120 (ngàn đồng) và lợi nhuận của 10m ván
xây dựng là 100 (ngàn đồng). Trong ngày, trại cưa phải
cưa bao nhiêu ván mỗi loại để lợi nhuận lớn nhất.
BÀI TOÁN QHTT TỔNG QUÁT
(1) Hàm f(x) gọi là hàm mục tiêu
(2) là hệ ràng buộc chính
(3) là hệ ràng buộc dấu
(2) Và (3) gọi chung là hệ ràng buộc của bài toán
1 1 2 2
1 1 2 2
1 ...
2 ... 1,2,..,
0
3 0 1,2,...,
min (max)n n
i i in n i
j
f x c x c x c x
a x a x a x b i m
x j n
tuy y
DẠNG MA TRẬN CỦA BÀI TOÁN QHTT
Xét bài toán QHTT dạng:
 1 1 2 2
11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
...
...
...
..........................................
...
0
min (max)n n
n n
n n
m m mn n m
j
f x c x c x c x
a x a x a x b
a x a x a x b
a x a x a x b
x
DẠNG MA TRẬN CỦA BÀI TOÁN QHTT
Đặt:
Ta có dạng ma trận của bài toán QHTT:
11 12 1 1 1 1
21 22 2 2 2 2
1 2
...
...
... ... .......................
...
n
n
m n nm m mn
a a a b x c
a a a b x c
A b x c
b x ca a a
 min max
0
Tf c x
Ax b
x
BÀI TOÁN DẠNG CHÍNH TẮC:
n
j j
j 1
n
ij j
j 1
j
f x c x min (max)
a x b (i 1,m)
x 0 (j 1,n)
i


Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài
toán dạng chính tắc tương đương theo nghĩa trị tối ưu
của hàm mục tiêu trong hai bài toán là trùng nhau và từ
phương án tối ưu của bài toán này suy ra phương án tối
ưu của bài toán kia
• Các ràng buộc
chính đều là
phương trình
• Các ẩn đều
không âm
BÀI TOÁN DẠNG CHUẨN TẮC
1 2
1 0 0
0 1 0
... ... ...
0 0 1
me e e
n
j j
j 1
n
ij j
j 1
j
f x c x min (max)
a x b (i 1,m)
x 0 (j 1,n)
i


• Các hệ số tự do bi
không âm (bi ≥ 0)
• Trong ma trận hệ số
có đủ m vecto cột
đơn vị: e1, e2,,em
VÍ DỤ 5
Bài toán sau có dạng chính tắc:
1 2 3
1 2 3
1 2 3
1 2
1 2 3
260 120 600 max
2 3 500
100 40 250 40000
6
, , 0
x x x
x x x
x x x
x x
x x x
VÍ DỤ 6
Xét bài toán QHTT sau:
Bài toán trên có dạng chính tắc hay chuẩn tắc
1 2 3 4
1 4 5
1 3 6
1 2 3 4
2 4 6 max
12
12 3
6
0 1,2,...,6j
f x x x x x
x x x
x x x
x x x x
x j
VÍ DỤ 6
Ma trận hệ số tự do:
12
3
6
b
• Ma trận hệ số A:
1 0 0 1 1 0
12 0 1 0 0 1
1 1 1 1 0 0
A
1e 2e3e
• Ẩn cơ bản thứ nhất là x5.
• Ẩn cơ bản thứ 2 là x6.
• Ẩn cơ bản thứ 3 là x2.
CÁC LOẠI PHƯƠNG ÁN
Định nghĩa. Vec tơ  ∈  thỏa tất cả các ràng buộc của
bài toán quy hoạch tuyến tính được gọi là phương án
chấp nhận được.
Định nghĩa. Phương án chấp nhận được làm cho hàm
mục tiêu có giá trị lớn nhất (nếu là bài toán max) hay nhỏ
nhất (nếu là bài toán min) thì được gọi là phương án tối
ưu (PATU).
VÍ DỤ 7
Cho bài toán QHTT:
Trong các phương án sau phương án nào là phương án
chấp nhận được.
 1 2
1 2
1 2
1 2
120 100 max
2 3 8
5 3 15
0, 0
f x x x
x x
x x
x x
1 2 3 4
1 2 1 2
2 2 3 1
u u u u
PHƯƠNG ÁN CƠ BẢN
Trong bài toán chính tắc. Xét phương án
Hệ vectơ liên kết với phương án
Trong đó Aj là vec tơ cột thứ j trong ma trận hệ số Amn
Định nghĩa. Phương án cơ bản nếu hệ vecto liên kết với
phương án độc lập tuyến tính
Ẩn xj gọi là cơ bản nếu  > 0
 1 2, ,..., nx x x x 
 | 0j jA A x 
PACB TRONG BÀI TOÁN CHUẨN TẮC
Cho ẩn cơ bản thứ k bằng hệ số tự do thứ k, còn các ẩn không 
cơ bản bằng 0, nghĩa là:
Ta được một phương án cơ bản x = (0,6,0,0,12,3) . 
Phương án này không suy biến vì có đủ 3 thành phần dương. 
Đây là phương án cơ bản ban đầu của bài toán. 
Tổng quát, trong bài toán QHTT dạng chuẩn bất kì, khi cho ẩn 
cơ bản thứ k bằng hệ số tự do thứ k ( k = 1,2,,m ), còn các ẩn 
không cơ bản bằng 0, ta được phương án cơ bản ban đầu của 
bài toán. Nếu sắp xếp lại ta có dạng sau.
1 2 3 4 5 60; 6; 0; 0; 12; 3x x x x x x 
 0 1 2, ,..., ,0,0,...,0mx b b b 
ĐƯA BÀI TOÁN VỀ DẠNG CHÍNH TẮC
Bước 1. Kiểm tra ràng buộc chính
1 1 2 2 ...i i in n ia x a x a x b 
• Ràng buộc dạng nhỏ hơn:
•
• Ta cộng thêm ẩn phụ:
• Ràng buộc dạng lớn hơn:
• Ta trừ đi ẩn phụ:
1 1 2 2 ...i i in n n k ia x a x a x x b 
1 1 2 2 ...i i in n ia x a x a x b 
1 1 2 2 ...i i in n n k ia x a x a x x b 
ĐƯA BÀI TOÁN VỀ DẠNG CHÍNH TẮC
Bước 2. Kiểm tra điều kiện dấu các ẩn số
Nếu có ẩn dạng: ta đổi biến:
Nếu ẩn xi có dấu tùy ý ta đổi biến:
Chú ý:
Các ẩn mới và các ẩn phụ đều không âm.
Hệ số của các ẩn phụ trong hàm mục tiêu là 0.
Khi tìm được PATU của bài toán dạng chính tắc ta chỉ cần 
tính giá trị của các ẩn ban đầu và bỏ đi các ẩn phụ thì sẽ 
được PATU của bài toán dạng tổng quát đã cho.
0ix 
i i ix x x 
i ix x 
VÍ DỤ 8
Đưa bài toán sau về dạng chính tắc:
 1 2 3
1 2 3
1 3
1 2 3
1 2
2 4 min
4 6 3 12
7 3
2 3 5 6
0, 0
f x x x x
x x x
x x
x x x
x x
VÍ DỤ 8
Đáp án:
1 2 3 3
1 2 3 3 4
1 3 3 5
1 2 3 3
1 2 3 3
4 5
2 4 min
4 6 3 12
7 3
2 3 5 6
0, 0, 0, 0
0, 0
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
PHƯƠNG PHÁP HÌNH HỌC (ĐỒ THỊ)
Sinh viên tham khảo thêm lý thuyết sách
College Mathematics for Busines – Raymond A. Barnett
Chương 5 phần Linear Programing
Chỉ dùng cho bài toán quy hoạch tuyến tính 2 biến
PHƯƠNG PHÁP ĐỒ THỊ
Xét bài toán quy hoach tuyến tính :
2
1
2
1
min maxj j
j
ij j i
j
f x c x
a x b


PHƯƠNG PHÁP ĐỒ THỊ
Biểu diễn các ràng buộc lên đồ thị Oxy.
Xác định phần được giới hạn bởi các ràng buộc là tập 
phương án.
Xác định các điểm cực biên (đỉnh) của tập phương án 
thỏa mãn các ràng buộc.
Xác định giá trị của hàm mục tiêu tại các điểm cực 
biên.
So sánh và suy ra phương án tối ưu 
VÍ DỤ 9. BÀI TOÁN KẾ HOẠCH SẢN XUẤT
Một nhà sản xuất lều sử dụng trên các vùng núi có 2 dòng sản
phẩm: tiêu chuẩn và thám hiểm. 
Mỗi lều tiêu chuẩn yêu cầu 1 giờ công lao động từ bộ phận cắt
và 3 giờ công từ bộ phận lắp ráp.
Mỗi lều thám hiểm đòi hỏi 2 giờ công lao động từ bộ phận cắt
và 4 giờ làm việc từ bộ phận lắp ráp. 
Số giờ lao động tối đa có sẵn mỗi ngày trong các phòng cắt và
lắp ráp lần lượt là 32 và 84. 
Nếu công ty thu được mức lợi nhuận $50 cho mỗi lều tiêu
chuẩn và 80$ cho mỗi lều thám hiểm, thì mỗi ngày nên sản
xuất bao nhiêu lều mỗi loại để tối đa hóa tổng lợi nhuận hàng
ngày (giả sử rằng tất cả các lều có thể được bán)?
MÔ HÌNH BÀI TOÁN
Gọi x, y lần lượt là số lều tiêu chuẩn và thám hiểm
 , 50 80 max
0,
32
0
2
3 4 84
x
f x y
y
x
x y P
x y
y
TẬP PHƯƠNG ÁN
•Ta có thể tính toán được lợi nhuận tại từng điểm nằm
trong miền khả thi (feasible region) hay tập phương án
•Tại (x,y)=(12,10) ta có P=1400
•Tại (x,y)=(23,2) ta có P=1310
2 32
3 4 8
0, 0
4
x
x
y
x
y
y
ĐƯỜNG ĐẲNG LỢI
Gán cho P một giá trị cố định và vẽ đồ thị P=50x+80y trên
hệ trục tọa độ Oxy ta có được một đường thẳng. Đường
này có tên là constant profit line hay đường đẳng lợi.
Mọi điểm thuộc tập phương án và nằm trên đường này
đều cho ta một kế hoạch sản xuất và có cùng lợi ích P như
nhau. 
Với mỗi giá trị khác nhau của P ta có một đường đẳng lợi
khác song song với đường đẳng lợi còn lại, vì có chung hệ
số góc. 
Để thuận tiện ta đưa phương trình đường đẳng lợi về
dạng:
5
50 80
8 80
P
P x y y x
ĐƯỜNG ĐẲNG LỢI
Lợi nhuận lớn nhất sẽ nằm tại điểm mà đường đẳng lợi xa nhất so 
với gốc tọa độ nhưng vẫn còn nằm trong miền khả năng. 
Trong ví dụ này thì nó chính là điểm (20,6)
Profit max: P=20.50+6.80=1480
Nhận xét. PATU nằm tại các điểm góc (corner points) của tập
phương án
max max
5
8 80
P
y x
P y
VÍ DỤ 10
Đối với tập phương án như hình vẽ
(A) Cho P = x + y. Vẽ đồ thị các
đường đẳng lợi thông qua các điểm
(5, 5) và (10, 10). Đặt đường thẳng
dọc theo đường có lợi nhuận nhỏ
hơn và trượt theo hướng tăng lợi
nhuận, mà không làm thay đổi độ
dốc của nó. Giá trị tối đa của P là
bao nhiêu? Giá trị tối đa này xảy ra ở 
đâu?
(B) Lặp câu (A) cho P = x + 10y.
(C) Lặp câu (A) cho P = 10x + y
CÁC ĐỊNH LÝ
Định lý 1. Nếu bài toán quy hoạch tuyến tính có PATU thì PATU 
là một trong các PACB của tập phương án.
Định lý 2. (Về sự tồn tại phương án tối ưu)
A) Nếu tập phương án của bài toán QHTT bị chặn thì cả bài
toán min và max đều có PATU
B) Nếu tập phương án không bị chặn và các hệ số của hàm
mục tiêu đều dương thì bài toán min có PATU nhưng bài toán
max không có PATU
C) Nếu tập phương án của bài toán rỗng thì cả bài toán min và
max đều không có PATU
TÌM PATU BẰNG PP ĐỒ THỊ
VÍ DỤ 11A
Z max = 28
Z min = 15
VÍ DỤ 11B
Z min = 160
Không có max
VÍ DỤ 12
Giải bài toán QHTT sau:
1 2 1 2
1 2
1 2
1 2
1 2
, min
2 2 1
2 2
5 3
0, 0
f x x x x
x x
x x
x x
x x
VÍ DỤ 13
Biểu diễn đồ thị các bất đẳng thức lên
hệ trục tọa độ ta được miền các
phương án là hình ngũ giác ABCDE. 
Các điểm có tọa độ như sau A(0,0); 
B(0,2); C(1,4); D(4,1); E(2,0) là các
điểm cực biên. lần lượt thay các cực
biên vào hàm mục tiêu ta có f(A) = 0; 
f(B) = 2; f(C) = 3; f(D) = -3; f(E) = -2. 
Vậy phương án tối ưu x*=(4,1) tại đó
hàm mục tiêu đạt giá trị Min
D
C
A
B
E
VÍ DỤ 14
Một xí nghiệp đóng tàu đánh cá cần đóng 2 loại tàu 100 
mã lực và 50 mã lực. Trong xí nghiệp có 3 loại thợ chính
quyết định sản lượng kế hoạch. Thợ rèn có 2000 công, 
thợ sắt có 3000 công, thợ mộc có 1500 công. Định mức
lao động của mỗi loại tàu được cho trong bản:
Hỏi xí nghiệp nên đóng tàu mỗi loại bao nhiêu để đạt
tổng số mã lực cao nhất?
100 mã lực 50 mã lực
Thợ sắt (3000)
Thợ rèn (2000)
Thợ mộc 
(1500)
150
120
80
70
50
40
VÍ DỤ 14
Gọi x1, x2 lần lượt là số tàu 100 mã lực và 50 mã lực cần
đóng
Ta cần tìm x1, x2 sao cho: f(x)=100x1+50x2 max
Điều kiện:
0x,0x
1500x40x80
2000x50x120
3000x70x150
21
21
21
21
VÍ DỤ 15
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, 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 9 
giờ máy cán, 5 giờ máy tiện, 3 giờ máy mài; 1 đơn vị sản
phẩm B cần 3 giờ máy cán, 4 giờ máy tiện; 1 đơn vị sản
phẩm C cần 5 giờ máy cán. 3 giờ máy tiện, 2 giờ máy mài. 
Mỗi sản phẩm A trị giá 48 ngàn đồng, mỗi sản phẩm B trị
giá 16 ngàn đồng, mỗi sản phẩm C trị giá 27 ngàn đồng.
Vấn đề đặt ra là xí nghiệp cấn chế tạo bao nhiêu đơn vị
sản phẩm mỗi loại để tổng giá trị sản phẩm xí nghiệp thu
được là lớn nhất, với điều kiện không dùng quá số giờ
hiện có của mỗi loại máy.
VÍ DỤ 16
Một xí nghiệp điện cơ sản xuất quạt điện các loại. Cần cắt
từ một tấm tôn các cánh quạt điện theo 3 kiểu A, B, C. Có
6 mẫu cắt khác nhau theo bảng sau:
Kiểu cánh quạt
Mẫu cắt
1 2 3 4 5 6
A
B
C
2
0
0
1
1
0
1
0
1
0
2
0
0
1
2
0
0
3
PHƯƠNG PHÁP ĐƠN HÌNH
Simplex method
Xuất phát từ một PACB đầu tiên, tìm cách đánh giá
PACB ấy, nếu nó chưa tối ưu thì tìm cách chuyển sang 
một PACB mới tốt hơn.
Quá trình được lặp lại vì số PACB là hữu hạn nên sau
một số hữu hạn bước 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 hoặc sẽ tìm
được phương án tối ưu. 
Do nhà toán học George Benard Danzig đưa ra năm
1947
PHƯƠNG PHÁP ĐƠN HÌNH
1) Tìm một phương án cực biên (phương án cơ bản)
2) Xét xem PACB này đã là PATU hay chưa. Nếu đã tối ưu
thì kết thúc. Ngược lại chuyển sang bước 3.
3) Tìm phương án cực biên liền kề tốt hơn PACB đang xét
4) Quay về bước 2.
VÍ DỤ 17
Xét bài toán dạng chuẩn tắc
Ta có:
0
5
432
min232
421
321
4321
jx
xxx
xxx
xxxxxf
5
4
1011
0132
BA
VÍ DỤ 17
Ẩn cơ bản: x3, x4
Phương án cơ bản: x1=x2=0; x3=4; x4=5
Ta có:
5
4
1011
0132
BA
 25,4,0,0 00 xfx
 4321 232 xxxxxf 
0
5
324
0
5
432
214
213
421
321
jj x
xxx
xxx
x
xxx
xxx
VÍ DỤ 17
Ta đánh giá f(x) như sau:
Bài toán min nên với
Ta chưa đánh giá được giá trị nhỏ nhất của f
 2211021
212121
4321
932
5232432
232
xxxfxxxf
xxxxxxxf
xxxxxf
 21 932 xxxf 
 Axxxf 21 932
VÍ DỤ 17
Thử chọn x1, x4 làm ẩn cơ bản. Cho x2, x3=0 ta có
Phương án cơ bản:
Ta có: 
3
2
5
42
4
1
41
1
x
x
xx
x
 3,0,0,20 x
0
2
1
2
5
3
2
1
2
3
2
0
5
432
324
321
421
321
j
j x
xxx
xxx
x
xxx
xxx
VÍ DỤ 17
Ta đánh giá f(x) như sau:
Dễ thấy:
Vậy phương án tối ưu:
 32
4321
2
3
2
9
4
232
xxxf
xxxxxf
 4 xf
 3,0,0,2* x
CHÚ Ý
Tổng quát ta có:
Với x0 là phương án cơ bản
+ Nếu bài toán min thì ta cần Delta dương
+ Nếu bài toán max thì ta cần Delta âm
Trong PP đơn hình phía sau thì Delta trong bảng đơn hình
ngược dấu với Delta ở đây.
  kk xxfxf 0
Ẩn không cơ bản 0 kx
PHƯƠNG PHÁP ĐƠN HÌNH
BẢNG ĐƠN HÌNH

n
1
jijij cacΔ
i
 Cách tính Delta một cột:
 Lấy hệ số cột ngoài cùng bên trái bảng
 Nhân với hệ số cột cần tính
 Trừ đi giá trị trên đầu cột cần tính
 Cách tính giá trị f(x):
 Lấy cột hệ số nhân cột P. Án
 
n
1
iibcf
i
x
DẤU HIỆU VỀ PHƯƠNG ÁN TỐI ƯU
1. Nếu ∆k ≤ 0 thì x
0 là phương án tối ưu.
2. Nếu tồn tại một ∆k > 0 mà ajk ≤ 0 thì bài toán không có
phương án tối ưu.
3. Nếu tất cả ∆k > 0 và tồn tại ajk > 0 thì ta có thể tìm
được phương án tốt hơn trong trường hợp bài toán
không suy biến.
CÁC BƯỚC THỰC HIỆN
CÁC BƯỚC THỰC HIỆN
Nhớ phép biến đổi sơ cấp
trên dòng đối với ma trận. 
Tương tự như khi đi tìm hạng
của ma trận khi biến đổi về
dạng bậc thang.
VÍ DỤ 18
36
60
52
100103
010324
001342
bA
VÍ DỤ 18
Hệ số Ẩn cơ
bản
PA X1
5
X2
4
X3
5
X4
2
X5
1
X6
3
36
60
52
100103
010324
001342
bA
 654321 32545 xxxxxxxf 
VÍ DỤ 18
Hệ số
Ẩn cơ
bản
PA
x1 x2 x3 x4 x5 x6
5 4 5 2 1 3
2 x4 52 2 4 3 1 1 0
1 x5 60 4 2 3 0 1 0
3 x6 36 3 0 1 0 0 1
36
60
52
100103
010324
001342
bA
 654321 32545 xxxxxxxf 
VÍ DỤ 18
Hệ số Ẩn cơ
bản
PA X1
5
X2
4
X3
5
X4
2
X5
1
X6
3
2 X4 52 2 4 3 1 1 0
1 X5 60 4 2 3 0 1 0
3 x6 36 3 0 1 0 0 1
272 12 6 7 0 0 0
 654321 32545 xxxxxxxf 
64
0
2
4
3
1
2
2 
 272
36
60
52
3
1
2
0 
 xf
VÍ DỤ 18
Hệ số Ẩn cơ
bản
PA X1
5
X2
4
X3
5
X4
2
X5
1
X6
3
2 X4 52 2 4 3 1 1 0
1 X5 60 4 2 3 0 1 0
3 x6 36 3 0 1 0 0 1
272 12 6 7 0 0 0
36
60
52
100103
010324
001342
bA
 654321 32545 xxxxxxxf 
125
3
4
2
3
1
2
1 
 64
0
2
4
3
1
2
1 
ĐÁNH GIÁ
Hệ số Ẩn cơ
bản
PA X1
5
X2
4
X3
5
X4
2
X5
1
X6
3
2 X4 52 2 4 3 1 1 0
1 X5 60 4 2 3 0 1 0
3 x6 36 3 0 1 0 0 1
272 12 6 7 0 0 0
Giá trị lớn nhất nằm ở cột x1
123:36
154:60
162:52
Giá trị nhỏ nhất nằm ở hàng x6
Vậy đưa biến x1 vào thay cho biến x6
BẢNG MỚI
Hệ số Ẩn cơ
bản
PA X1
5
X2
4
X3
5
X4
2
X5
1
X6
3
2 X4 52 2 4 3 1 0 0
1 X5 60 4 2 3 0 1 0
3 x6 36 3 0 1 0 0 1
272 12 6 7 0 0 0
2 X4 28 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
128 0 6 3 0 0 -4
Chia hàng mới để có hệ số 1 tại vị trí xoay
Biến đổi trên dòng để các hàng còn lại là 0
Tính lại các giá trị Delta và giá trị f(x0)
BẢNG MỚI
Hệ số Ẩn cơ
bản
PA X1
5
X2
4
X3
5
X4
2
X5
1
X6
3
2 X4 28 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
128 0 6 3 0 0 -4
2 X4 4 0 0 -1 1 -2 2
4 X2 6 0 1 5/6 0 1/2 -2/3
5 x1 12 1 0 1/3 0 0 1/3
92 0 0 -2 0 -3 0
Đưa biến x2 vào thay biến x5
PATU: x0=(12,6,0,4,0,0) f min = 92
PHƯƠNG PHÁP ĐƠN HÌNH – CHÚ Ý
1) Đối với bài toán có hàm f(x) max thì có thể chuyển về
giải bài toán với hàm g(x) = −f(x) min (Chú ý là fmax = −gmin)
hoặc cũng có thể giải trực tiếp với dấu hiệu tối ưu là k ≥ 0, 
dấu hiệu để điều chỉnh phương án là k < 0, còn các yếu tố
khác của thuật toán không đổi.
2) Chọn vectơ đưa vào cơ sở ứng với max

 là với hy vọng làm
trị số hàm mục tiêu giảm nhiều nhất sau mỗi bước biến đổi, 
tuy nhiên vectơ đưa vào cơ sở thực sự làm trị số hàm mục tiêu
giảm nhiều nhất phải ứng với max


.   nhưng trên nguyên
tắc thì đưa bất kỳ vectơ nào ứng với k > 0 vào cơ sở cũng cải
tiến được phương án.
PHƯƠNG PHÁP ĐƠN HÌNH – CHÚ Ý
3) Trường hợp bài toán suy biến thì θ0 có thể bằng 0, khi θ0
= 0 vẫn thực hiện thuật toán một cách bình thường, nghĩa
là vectơ ứng với θ0 vẫn bị loại khỏi cơ sở. 
Dấu hiệu xuất hiện phương án cực biên suy biến là θ0
đạt tại nhiều chỉ số, khi đó vectơ loại khỏi cơ sở được
chọn trong số những vectơ ứng với θ0 theo quy tắc ngẫu
nhiên.
PHƯƠNG PHÁP ĐƠN HÌNH – CHÚ Ý
Khi áp dụng thuật toán cần lưu ý hai trường hợp:
Phương án cực biên x0 có cơ sở J0 là cơ sở đơn vị, lúc đó ma trận hệ
số phân tích của [ A | b] theo cơ sở đơn vị là chính nó nên ta có thể
lập ngay được bảng đơn hình. Bài toán dạng chuẩn là bài toán cho
ngay một phương án cực biên với cơ sở là đơn vị, nên từ bài toán ta 
có thể lập được bảng đơn hình ứng với phương án cực biên ấy.
Nếu J0 không phải là cơ sở đơn vị thì để lập bảng đơn hình trước
hết cần phải tìm ma trận hệ số phân tích theo J0. Để làm điều này ta 
viết ma trận mở rộng [A | b] sau đó thực hiện các phép biến đổi sơ
cấp trên các hàng của ma trận, biến đổi sao cho các vectơ cơ sở trở
thành các vectơ đơn vị khác nhau. Khi đó ma trận mở rộng sẽ trở
thành ma trận hệ số phân tích. 
VÍ DỤ 19
Cho bài toán:
Chứng tỏ rằng vecto x0 = (8, 0, 0, 0) là phương án cực
biên.
Dùng vectơ trên giải bài toán theo phương pháp đơn
hình
 1 2 3 42 6 8 5 minf x x x x x 
1 2 3 4
1 2 3 4
1 2 3 4
2 3 8
2 5 2
4 7 8 2 20
0 1,2,3,4j
x x x x
x x x x
x x x x
x j
VÍ DỤ 19
Dễ thấy rằng x0 thỏa mãn mọi ràng buộc của bài toán, 
các ràng buộc là độc lập tuyến tính, vậy x0 là phương
án cực biên không suy biến.
Trước hết phải đưa bài toán về dạng chính tắc. 
1 2 3 4
1 2 3 4
1 2 3 4 5
1 2 3 4 6
2 6 8 5 min
2 3 8
2 5 2
4 7 8 2 20
0 1,2,3,4,5,6j
f x x x x x
x x x x
x x x x x
x x x x x
x j
VÍ DỤ 19
Từ x0 suy ra phương án cực biên không suy biến của
bài toán dạng chính tắc: x= (8, 0, 0, 0, 18, 12) với cơ
sở là J0 = {A1, A5, A6} không phải là cơ sở đơn vị.
Vì vậy để lập được bảng đơn hình ứng với phương án
cực biên x ta phải tìm ma trận hệ số phân tích của
ma trận điều kiện của bài toán dạng chính tắc qua cơ
sở J0 . 
Chú ý rằng vế phải của ma trận hệ số phân tích phải
trùng với các thành phần cơ sở của phương án cực
biên.
VÍ DỤ 19
Quá trình biến đổi trên ma trận như sau:
Dựa trên ma trận hệ số phân tích ta lập bảng đơn hình.
12
18
8
102
013
001
410
550
321
20
8
8
102
015
001
874
112
321
Ta có 3 = 4 > 0, nhưng aj3 < 0 (j J), bài toán không có
phương án tối ưu.
Hệ số Ẩn cơ
bản
PA X1
-2
X2
-6
X3
8
X4
-5
X5
0
X6
0
-2 X1 8 1 2 -3 1 0 0
0 X5 18 0 5 -5 -3 1 0
0 x6 12 0 1 -4 2 0 1
-16 0 2 -2 3 0 0
-2 X1 2 1 3/2 -1 0 0 -1/2
0 X5 36 0 13/2 -11 0 1 3/2
-5 x4 6 0 1/2 -2 1 0 1/2
-34 0 1/2 4 0 0 -3/2
 1 2 3 42 6 8 5 minf x x x x x 
VÍ DỤ 20. BÀI TOÁN ĐẶT ẨN PHỤ
Giải bài toán sau bằng phương pháp đơn hình
Với hệ ràng buộc:
 1 2 3 4
1
2 3 min
2
f x x x x x 
1 2 3 4
2 3 4
2 3 4
1
18
2
4 8 8
2 2 3 20
0 1,2,3,4j
x x x x
x x x
x x x
x j
VÍ DỤ 20. BÀI TOÁN ĐẶT ẨN PHỤ
Trước hết đưa bài toán về dạng chính tắc bằng cách cộng vào
ràng buộc (2) và (3) hai biến phụ x5 và x6. Ta có:
Với hệ ràng buộc mới:
 1 2 3 4
1
2 3 min
2
f x x x x x 
1 2 3 4
2 3 4 5
2 3 4 6
1
18
2
4 8 8
2 2 3 20
0 1,2,3,4,5,6j
x x x x
x x x x
x x x x
x j
Phương án tương ứng là tối ưu: x0 = (0, 0, 16, 4, 40, 
0) 
Giá trị tối ưu của hàm mục tiêu là: f = –18.
VÍ DỤ 21. BÀI TOÁN ĐẶT ẨN PHỤ
Đây là bài
toán dạng
chuẩn tắc 
phương
pháp đơn
hình
BÀI TOÁN ẨN GIẢ
QUAN HỆ HAI BÀI TOÁN
 Nếu bài toán M vô nghiệm thì bài toán ban đầu vô
nghiệm.
 Nếu bài toán M có nghiệm (x1,x2,,xn,0,,0) thì
(x1,x2,,xn) là nghiệm bài toán ban đầu
 Nếu bài toán M có nghiệm (x1,x2,,xn,xn+1,,xn+m) và có ít
nhất 1 trong các ẩn giả >0 thì bài toán ban đầu vô nghiệm
 Thuận lợi: có thể xây dựng ngay phương án cơ bản ban 
đầu thông qua đặt các ẩn giả.
VÍ DỤ 22.
VÍ DỤ 22.
Ta có bài toán.
Đây là bài toán dạng chuẩn tắc nên ta có thể áp dụng
ngay phương pháp đơn hình để giải.
 min2 76321 MxMxxxxxf