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

ớ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