1LỜI NÓI ĐẦU

Sự tồn tại và vận động của các đối tượng trong quá trình phát triển kinh tế - xã hội
là hết sức phức tạp và đa dạng. Người ta có thể sử dụng nhiều phương pháp tiếp cận khác
nhau để nghiên cứu, phân tích lý giải sự tồn tại và vận động này, từ đó tìm cách tác động
đến các đối tượng và quá trình kinh tế nhằm mang lại lợ ích ngày càng lớn cho chính bản
thân xã hội loài người. Mỗi cách tiếp cận trong những điều kiện cụ thể có những ưu,
nhược điểm riêng. Phương pháp mô hình toán kinh tế là một trong những phương pháp
được xem là hiệu quả nhất trong nghiên cứu kinh tế - xã hội hiện nay. Đây là phương pháp
khai thác công cụ mạnh của toán học, kỹ thuật tinh toán, nhờ đó mà phương pháp mô hình
toán kinh tế cho phép giải quyết các bài toán với kích cỡ không hạn chế với độ phức tạp
mong muốn. Trong khuôn khổ môn học “ Toán kinh tế” dành cho chuyên ngành quản trị
kinh doanh bậc cao đẳng với thời lượng 2 tín chỉ, tập bài giảng này sẽ trang một số kỹ
năng cơ bản về mô hình hóa toán kinh tế và ứng dụng vào giải các bài toán kinh tế. Do
hạn chế về thời lượng giảng dạy, tập bài giảng này không thể đề cập sâu và chi tiết, cũng
như không đề cập đến nhiều nội dung khác thuộc lĩnh vực mô hình Toán kinh tế. Các nội
dung này người đọc có thể tìm đọc ở các tài liệu tham khảo đã liệt kê.
Tập bài giảng gồm 4 chương:
Chương I: Bài toán quy hoạch tuyến tính
Chương II: Phương pháp đơn hình
Chương III: Bài toán đối ngẫu
Chương IV: Bài toán vận tải.
Mặc dù tập bài giảng đã kế thừa nhiều tài liệu tôi cho rằng tập bài giảng vẫn
không thể tránh được những hạn chế nhất định. Tôi mong nhận được sự quan tâm của các
đồng nghiệp cũng như của tất cả bạn đọc nhằm tạo điều kiện cho tập bài giảng ngày càng
MỤC LỤC
3

Nội dung Trang

LỜI NÓI ĐẦU…………………………………………………………………

1
MỤC LỤC…………………………………………………………………………. 2
Chương 1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH……………………………….
4
1.1. MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QHTT…………………………………………….


2.1. PHƯƠNG PHÁP ĐƠN HÌNH GIẢI BÀI TOÁN QHTT DẠNG CHUẨN………

18
2.1.1. Thuật toán giải bài toán min………………………………………………. 18
2.1.2. Thuật toán giải bài toán max………………………………………………. 24
2.2. PHƯƠNG PHÁP ĐƠN HÌNH MỞ RỘNG GIẢI BÀI TOÁN QHTT DẠNG
CHÍNH TẮC……………………………………………………………………………

28
2.2.1. Phương pháp giải bài toán QHTT dạng chính tắc……………………… 28
2.2.2. So sánh các đại lượng trong bài toán QHTT dạng chính tắc……………. 28
BÀI TẬP CHƯƠNG 2……………………………………………………………………

35
Chương 3:
BÀI TOÁN ĐỐI NGẪU……………………………………………………
41
3.1. ĐỊNH NGHĨA BÀI TOÁN ĐỐI NGẪU……………………………………………

41
3.1.1. Định nghĩa bài toán đối ngẫu…
.………………………………………………
41
3.1.2. Cách xây dựng một bài toán đối ngẫu.
……………………………………….
41
3.2. QUAN HỆ GIỮA BÀI TOÁN GỐC VÀ BÀI TOÁN ĐỐI NGẪU………………

42
3.2.1. Cặp ràng buộc bài toán đối ngẫu.

53
4.1.1. Nội dung bài toán.
……………………………………………………………

53
4.1.2. Tính chất chung của bài toán.
………………………………………………

54
4.2. Phương pháp thế vị để giải bài toán.
……………………………………….

54
4.2.1. Phương pháp tìm phương án cực biên xuất phát.
…………………….

54
4.2.2. Phương pháp thế vị giải bài toán vận tải.
……………………………….

55
BÀI TẬP CHƯƠNG 4……………………………………………………………………
59


Bánh đậu
xanh
Bánh thập
cẩm
Bánh dẻo
Lượng dự
trữ
Đường 0,04 kg 0,06 kg 0,05 kg 500 kg
Đậu 0,07 kg 0 kg 0,02 kg 300 kg
Lãi 3 ngàn 2 ngàn 2,5 ngàn

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.
Giải.
Gọi x
1
, x
2
, x
3
lần lượt là số bánh đậu xanh, bánh thập cẩm và bánh dẻo cần sản
xuất. Điều kiện: x
j
≥ (j = 1,2,3). Khi đó
1. Tiền lãi thu được là: f(x) = f(x
1
, x
2
, x
3

2
, x
3
) = 3x
1
+ 2x
2
+ 2,5x
3
max.
Với điều kiện:


1 2 3
1 3
0 ,0 4 0 , 0 6 0 , 0 5 5 0 0 ;
0 ,0 7 0 , 0 2 3 0 0
x x x
x x
  
 

(3) x
j
≥ 0 (j = 1, 2, 3)
Ta nói đây là một bài toán qui hoạch tuyến tính 3 ẩn tìm max của hàm mục tiêu
f(x) = 3x
1
+ 2x
2

2km
x
12
3km
x
13
K2: 40T
4km
x
21
3km
x
22
1km
x
23

Hãy lập kế hoạch vận chuyển sao cho:
- Các kho giải phóng hết hàng;
- Các công trường nhận đủ vật liệu cần thiết;
- Tổng số T(tấn) x km phải thực hiện là nhỏ nhất.
Giải.
Gọi x
ij
là số tấn vật liệu sẽ vận chuyển từ kho K
j
đến công trường C
j
.
Điều kiện: x

= 20.
3. Tổng số tấn vật liệu được vận chuyển từ kho K
2
đến các công trường là x
21
+ x
22
+ x
23.

Để giải phóng hết vật liệu, ta phải có x
21
+ x
22
+ x
23
= 40.
4. Tổng số tấn vật liệu được vận chuyển về công trường C
1
là x
12
+ x
21
.
Để C
2
nhận đủ vật liệu, ta phải có x
11
+ x
21

(1) f(x) = 5x
11
+ 2x
12
+ 3x
13
+ 4x
21
+ 3x
22
+ x
23
min
Với điều kiện:
711 12 13
21 22 23
11 21
12 22
13 23
20;
40;

+ 3x
13
+ 4x
21
+ 3x
22
+ x
23
.
1.1.3. Bài toán phân công lao động
Một lớp học cần tổ chức lao động với hai loại công việc: xúc đất. Lao động của lớp
được chia làm 3 loại A, B, C, với số lượng lần lượt là 10, 20, 12. Năng suất của từng loại
lao động trên từng công việc cho trong bảng dưới đây:
Lao động

Công việc
A(10) B(20) C(12)
Xúc đất 6 5 4
Chuyển đất 4 3 2
Hãy tổ chức lao động sao cho có tổng năng suất lớn nhất.
Lập bài toán:
Gọi x
ij
là số lao động loại j làm công việc i (j = 1,2; x
ij
0, nguyên ). Khi đó, năng
suất lao động của công việc đào đất sẽ là:
6x
11
+ 5x

x x
x x
     


 


 


 


1.2. PHÂN LOẠI DẠNG BÀI TOÁN QHTT
1.2.1. Dạng tổng quát của bài toán QHTT
(1)
1
( ) m in( ax )
n
j j
j
f x c x m

 


Với điều kiện




 



 







(3) x
j
 0 (j  J
1
); x
j
≤ 0 (j  J
2
); x
j
tuỳ ý (j  J
3
);
Trong đó

3
=


1, 2, ,
n

- A = (a
ij
)
mxn
: Ma trận hệ số ràng buộc;
- B = (b
1
, b
2
, , b
m
): Véctơ các hệ số tự do;
- C = (c
1
, c
2
, , c
m
): Véctơ hệ số các ẩn trong hàm mục tiêu;
- x = (x
1
, x
2


 


ij
1
( 2 ) ( 1, )
n
j i
j
a x b i m

 


(3) 0 ( 1, )
j
x j n
 

Nhận xét: Bài toán QHTT dạng chính tắc là bài toán dạng tổng quát, trong đó.
- Các ràng buộc đều là phương trình;
- Các ẩn đều không âm
Ví dụ 1: Bài toán sau có dạng chính tắc:

1 2 3 4
(1) ( ) 2 4 6 min
f x x x x x
    


1.2.3. Dạng chuẩn của bài toán QHTT

1
(1) ( ) m in ( a x )
n
j j
j
f x c x m

 
ij
1
( 2 ) ( 1, )
n
j i
j
a x b i m

 
(3) 0 ( 1, )
j
x j n
 


     
  
     
     
     
     

Khi đó.
*Các ẩn ứng với các véctơ cột đơn vị được gọi là các ẩn cơ bản. Cụ thể ẩn ứng với
véctơ cột đơn vị e
k
là ẩn cơ bản thứ k.
*Một phương án mà các ẩn không cơ bản đều bằng 0 được gọi là một phương án cơ bản.
*Một phương án cơ bản có đủ m thành phần dương (nghĩa là mọi ẩn cơ bản đều
dương) đượi gọi là không suy biến. Ngược lại, một phương án cơ bản có ít hơn m thành
phần dương (nghĩa là có ít nhất một ẩn cơ bản bằng 0) được gọi là suy biến.
Ví dụ 2: Xét bài toán QHTT sau:

1 2 3 4 5 6
(1) ( ) 2 4 6 4 min
f x x x x x x x      1 4 5
1 3 6
1 2 3 4
12;
(2) 12 3;
6.
x x x

 

 
 
 
 

Có chứa đầy đủ 3 véctơ cột đơn vị e
1
(cột 5), e
2
(cột 6), e
3
(cột 2).
Do đó bài toán có dạng chuẩn, trong đó

10

*Ẩn cơ bản thứ 1 là x
5
.
*Ẩn cơ bản thứ 2 là x
6.

*Ẩn cơ bản thứ 3 là x
2.


i
a x b




ta đưa vào ẩn phụ x
n+i
 0 để biến về phương trình.

ij
1
n
j n i i
i
a x x b


 


2. Khi gặp ràng buộc dạng.
ij
1
n
i i
i
a x b



j
tuỳ ý, ta đổi biến x
j
=
'
j
x
-
''
j
x
với
'
j
x
 0;
''
j
x
 0.
Chú ý: 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.
Ví dụ 1: Biến đổi bài toán QHTT sau về dạng chính tắc:
11

f(x) = 3x
1

- Đưa vào ẩn phụ x
4
≥0 để biến bất phương trình 4x
1
– 6x
2
+ 5x
3
≤ 50 về phương
trình 4x
1
– 6x
2
+ 5x
3
+ x
4
= 50.
- Đưa vào ẩn phụ x
5
≥ 0 để biến bất phương trình 7x
1
+ x
3
≥ 30 về phương trình
7x
1
+ x
3
– x

f x f x x x x x x
   
max

' ' "
1 2 3 3 4
' "
1 3 3 5
' ' "
1 2 3 3
4 6 5( ) 50;
(2) 7 ( ) 30;
2 3 5( ) 25.
x x x x x
x x x x
x x x x

    

   


    
' ' ''
1 2 3 3 4 5
(3) 0; 0; 0; 0; 0; 0.
x x x x x x

1
, x
3
≥ 0.
1.3.2.Chuyển bài toán dạng chính tắc sang bài toán dạng chuẩn
Từ bài toán QHTT dạng chính tắc ta có thể xây dựng bài toán QHTT mở rộng có
dạng chuẩn như sau:
1. Khi gặp hệ số tự do b
i
< 0 ta đổi dấu hai vế của ràng buộc thứ i.
2. Khi ma trận hệ số ràng buộc A không chứa véctơ cột đơn vị thứ k là e
k
, ta đưa
vào ẩn giả x
n+k
 0 và cộng thêm ẩn giả x
n+k
vào vế trái của phương trình ràng buộc thứ k
để được phương trình ràng buộc mới:
12

1
n
kj j n k k
j
a x x b


1 2 3
4 6 5 50;
(2) 7 0;
2 3 5 25
x x x
x x x
x x x
  


  


   
(3) 0( 1, , 4)
j
x j
 

Giải: Bài toán trên đã có dạng chính tắc, trong đó vế phải của phương trình ràng
buộc thứ ba là -25 < 0. Đổi dấu hai vế của phương trình này ta được:
-2x
1
– 3x
2
+ 5x
3


 
 
 
 

Vì A còn thiếu 2 véctơ cột đơn vị là e
1
và e
3
nên bài toán có dạng chuẩn.
- Lập các ẩn giả x
5
 0, x
6
 0 và xây dựng bài toán mở rộng dạng chuẩn như sau:
(1).
1 2 3 4 5 6
( ) 3 2 2
f x x x x x Mx Mx
     
min.

1 2 3 5
1 3 4
1 2 3 6
4 6 5 50;
(2) 7 0;
2 3 5 25.
x x x x

6
max

1 2 3 5
1 3 4
1 2 3 6
4 6 5 50;
7 0;
2 3 5 25.
x x x x
x x x
x x x x
   


  


    


x
j
 0 (j = 1, , 6).
Ví dụ 2: Biến đổi bài toán QHTT sau về dạng chuẩn:
(1) f(x) = f(x
1
, x
2
, x

j
 0 (j = 1, ,4).
Giải.
Trước hết ta đưa bài toán về dạng chính tắc bằng cách đưa vào 2 ẩn phụ x
5
 0; x
6
 0:
(1) f(x) = f(x
1
, x
2
, x
3
) = 3x
1
+ 2x
2
+ 2x
3
+ x
4
min

2 3 5
3 4
1 2 3 6
9 15 50;
(2) 6 2 120;
3 5 45.


 


    


Ma trận hệ số ràng buộc là:

0 9 15 0 1 0 0
0 0 6 2 0 0 1
1 3 5 0 0 1 0
A

 
 
 
 
 
 
 

Vì A còn thiếu 1 véctơ cột đơn vị là e
2
nên bài toán chưa có dạng chuẩn.
- Lập ẩn giả x
7
 0 và xây dựng bài toán mở rộng dạng chuẩn như sau:

( )


  


    


x
j
 0 (j = 1, ,7).
1.3.3. Quan hệ giữa bài toán xuất phát và bài toán mở rộng.
a. Quan hệ giữa bài toán QHTT dạng tổng quát và bài toán dạng chính tắc.
- Sử dụng ẩn phụ. Ẩn phụ biến 1 bất phương trình thành 1 phương trình theo đúng
logic toán học.
- Các hệ số của ẩn phụ đều bằng 0 trong hàm mục tiêu.
b. Quan hệ giữa bài toán QHTT dạng chính tắc và bài toán dạng chuẩn.
- Sử dụng ẩn giả. Ẩn giả đưa vào một cách “giả tạo” cốt để ma trận có hệ số ràng
buộc có chứa đủ véctơ cột đơn vị, nó chỉ được cộng hình thức vào vế trái của phương trình
ràng buộc và tạo nên 1 phương trình ràng buộc mới.
- Ẩn giả sẽ tạo ra hàm mục tiêu mở rộng, hệ số của các ẩn giả đều = M (đối với bài
toán min), hoặc đều = -M (đối với bài toán max).
c. Mối quan hệ giữa bài toán xuất phát (A) và bài toán mở rộng B như sau:
(B) Vô nghiệm  (A) vô nghiệm
Mọi ẩn giả = 0  Bỏ các ẩn giả, được PATU của (A).
(B) Có nghiệm
Có ít nhất một ẩn giả > 0  (A) không có phương án
nào nên vô nghiệm

TÀI LIỆU THAM KHẢO


Bài 2:
Một xí nghiệp có thể sản xuất bốn loại mặt hàng xuất khẩu H1, H2, H3, H4. Để sản
xuất 4 loại mặt hàng này, xí nghiệp sử dụng hai loại nguyên liệu N1, N2. Số nguyên liệu
tối đa mà xí nghiệp huy động được tương ứng là 600kg và 800kg. Mức tiêu hao mỗi loại
nguyên liệu để sản xuất một mặt hàng và lợi nhuận thu được cho trong bảng sau:
Định mức tiêu hao nguyên liệu và lợi nhuận H1 H2 H3 H4
N1 0,5 0,2 0,3 0,4
N2 0,1 0,4 0,2 0,5
Lợi nhuận 0,8 0,3 0,5 0,4

Lập mô hình sao cho xí nghiệp sản xuất đạt lợi nhuận cao nhất?
Bài 3:
Một cơ sở dự định sản xuất tối đã trong một ngày 500 ổ bánh mì dài và 500 ổ bánh
mì tròn, muốn đạt lợi nhuận nhiều nhất, với những điều kiện như sau:
- Giá bán một ổ bánh mì dài làm từ 400g bột là 325 đồng, một ổ bánh mì tròn làm
từ 250g bột là 220 đồng.
- Số lượng bột được cung cấp tối đa trong ngày là 225kg với giá mỗi kg là 300 đồng.
- Lò nướng bánh cho phép nướng 75 ổ bánh mì dài hay 100 ổ bánh mì tròn trong
một giờ nhưng không thể nướng hai loại cùng một lúc. Lò nướng hoạt động tối đa 8 giờ
trong một ngày.
Hãy lập mô hình cho bài toán nêu trên?

Bài 4:
Ba xí nghiệp A, B, C cùng có thể sản xuất áo vét và quần. Khả năng sản xuất của
mỗi xí nghiệp như sau: Khi đầu tư 1000 USD vào xí nghiệp A thì thu được 35 áo vét và 45
16


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 7
Chuyên gia dinh dưỡng định thành lập một thực đơn gồm 2 loại thực phẩm chính A
và B. Cứ một (trăm gram):
17

 Thực phẩm A chứa 2 đơn vị chất béo, 1 đơn vị carbohydrate và 4 đơn vị protein.
 Thực phẩm B chứa 3 đơn vị chất béo, 3 đơn vị carbohydrate và 3 đơn vị protein.
Nếu một (trăm gram) thực phẩm A giá 20 (ngàn đồng) và một (trăm gram) thực
phẩm B giá 25 (ngàn đồng).
Hỏi nhà dinh dưỡng muốn thức ăn phải cung cấp ít nhất 18 đơn vị chất béo, 12 đơn
vị carbohydrate và 24 đơn vị protein thì cần bao nhiêu (trăm gram) thực phẩm mỗi loại để
có giá nhỏ nhất những vẫn cung cấp đủ dinh dưỡng?
Bài 8

Một nhà sản xuất có 2 nhà máy: Một nhà máy ở Vĩnh Phúc và một nhà máy ở Bình
Dương. Có 3 kho hàng phân phối sản phẩm đặt ở Hà Nội, TP. HCM và Cần Thơ. Nhà máy
ở Vinh phúc; Bình Dương, có khả nang cung cấp tối đa 100; 140 tấn mỗi tuần. Lượng cầu
của các kho ở Hà Nội, TP. HCM và Cần Thơ lần lượt từ 100; 60 và 80 tấn trở lên. Chi phí
vận chuyển (trăm ngàn) mỗi tấn cho như bảng bên dưới. Hỏi cần vận chuyển bao nhiêu tấn
hàng hóa từ nhà sản xuất đến các kho hàng ở Hà Nội, TP. HCM và ở Cần Thơ để chi phí
nhỏ nhất nhưng vẫn đáp ứng đủ nhu cầu?
Trạm phát
Trạm thu
Hà Nội



  


  





Bài 2: f(x) =
2x
1
–x
2
 max
Với điều kiện
1 2 3
1 2 3
1 2 3
1 2
2 2
2 2
4
, 0
x x x
x x x
x x x
x x

1 2
2 3 4
1 2 4
3 4
2 3
4 3
, , 0
x x x
x x
x x x
x x x
  


 


  





Bài 4: f(x) =
x
1
–2x
2
– x
3

Bài 5: f(x) =
-5x
1
–2x
2
– 10x
3
/3
 min

1 2 3
1 3 5
1 3
1 3
2 4 3 4 6
4 2 3 3 8
3 2 1
, 0
x x x
x x x
x x
x x
  


 


 




x
j
≥ 0 (j =
1,4
)
Bài 7: f(x) =
7x
1
+ 6x
2
– 12x
3
+ x
4
 max.
1 2 3 4
2 3 4
1 3 4
2 2 3 2 8
3 2 2 1
2 3 10
x x x x
x x x
x x x
   


   

2.1.1. Thuật toán giải bài toán min
1
(1) ( ) min
n
j j
j
f x c x

 


11 1 12 2 1 1
21 1 22 2 2 2
1 1 2 2
;
;
(2) .
n n
n n
m m mn n m
a x a x a x b
a x a x a x b
a x a x a x b
   


   

n
Hệ số
Ẩn cơ
bản
Phương
án
x
1
x
v
x
n

i
1
i
cr
i
cm
i
c

1
ia
1v

a
mv a
1n

a
rn

a
mn
*
ik

1 2
1 2

m
j i j i j i mj j
c a c a c a c
     
(j =
1,
n
)
= (cột Hệ số) (cột x
j
) - c
j

a
rv
20

Bước 2: Nhận định tính tối ưu.
1. Nếu
0
j

với mọi i = 1, ,m, thì bài toán min đang xét
vô nghiệm, nghĩa là không có phương án tối ưu nào.
3. Nếu hai trường hợp trên đều không xảy ra, nghĩa là tồn tại
0
v
 
, và với mọi j
mà
0
j
 
đều tồn tại i sao cho
ij
0
a

, thì sang bước 3.
Bước 3: Tìm ẩn đưa vào hệ ẩn cơ bản.
Trong tất cả các
0
j
 
, ta chọn
0
v
 
lớn nhất [Ta đánh dấu * cho
v

dương lớn

r
nhỏ nhất trong bảng]. Khi đó x
r
là ẩn ta sẽ đưa ra khỏi hệ ẩn cơ bản.
Bước 5: Tìm phần tử chốt.
Phần tử chốt là hệ số a
rv
ở cột v (cột chứa
*
v

), hàng r (hàng chứa
*
r

) [Ta đóng
khung phần tử chốt a
rv
].
Bước 6: Biến đổi bảng.
1. Trong cột ẩn cơ bản ta thay x
r
bằng x
v
. Trong cột hệ số ta thay c
r
bằng c
v
.
2. Dùng phép biến đổi h

c c v r
h h h
  

nghĩa là (hàng cuối mới) = (hàng cuối cũ) -
v

(hàng r mới).
21

Bước 7: Quay về bước 2.
Chú ý:
a. Trong bước 3, nếu có chiều
0
v
 
lớn nhất thì ta chỉ chọn một trong số đó để
đánh dấu * và xác định ẩn đưa vào tương ứng.
b. Trong bước 4, nếu có nhiều
r

thoả mãn
min : 0
k
r kv
kv
b

5
 min
1 2 4 5
2 3 4 5
2 5 6
6 2 9 3 2 ;
1 3
( 2 ) 2 3 0 ;
2 2
3 3 6 .
x x x x
x x x x
x x x
   



   


  



(3) x
j
 0 (j = 1, , 6)

1
;
- Ẩn cơ bản thứ 2 là x
3
;
- Ẩn cơ bản thứ 3 là x
6
;
Ta giải bài toán bằng phương pháp đơn hình.
Lập bảng đơn hình:
2 5 4 1 -5 0
Hệ số
Ẩn cơ
bản
Phương
án
x
1
x
2
x
3
x
4
x
5
x
6

i
f(x) 184 0 -9 0 -3 -7 0
f
0
= 2.32 + 4.30 + 0.36 = 184;
1 3 6
2
4
5
0;
2.( 6) 4.2 0.3 5 9;
2.( 2) 4.(1/ 2) 0.0 1 3;
2.( 9) 4.(3 / 2) 0.1 ( 5) 7
     
       
       
        

Trong bảng trên ta tấy
0
j
 
với mọi j = 1,2, ,6, nên bài toán min đang xét có
một phương án tối ưu là phương án cơ bản ban đầu x
0
định bởi:
1
3
6

23

Ví dụ 2: Giải bài toán QHTT sau:
(1) f(x) = f(x
1
, x
2
, x
3
) = 6x
1
+ x
2
+ x
3
+ x
5
– x
6
 min
1 2 4 6
1 3 6
1 4 5 6
15;
(2) 2 2 9;
4 2 3 2.
x x x x

4
+ x
5
– x
6
min

1 2 4 6
'
1 3 6
1 4 5 6
15;
(2 ) 2 2 9;
4 2 3 2.
x x x x
x x x
x x x x
    


   


   


(3) x
j
≥ 0 (j = 1, , 6).
Ma trận hệ số ràng buộc là:

;
Ta giải bài toán bằng phương pháp đơn hình.
Lập bảng đơn hình:
6 1 1 3 1 -7 Hệ
số
Ẩn cơ
bản
Phương
án
x
1
x
2
x
3
x
4
x
5
x
6

i


1
1
1
x
2

x
6
x
3
x
5

15
39
47
-1
-4
1
1
2
3
0
1
0
-1
-2
-1
0
0
1
1
0
0

f(x) -19 -2 -3 0 1 0 0


Bảng I: Ta tìm được:
f
0
= 1.15 + 1.9 + 1.2 = 26;

2 3 5
1
4
6
0;
1.( 1) 1.( 2) 1.4 6 5;
1.( 1) 1.0 1.2 3 2
1.1 1.( 2) 1( 3) ( 7) 3.
     
        
       
        

Trong bảng I ta thấy tồn tại
6
3 0
  
và trên cột tương ứng có a
13
=1>0 (a
23
=-2,
a
33

+ x
5
+ 4x
6
 min

2 3 4 5
2 4 5 6
1 4 5
2 2 3 6
(2) 3
4 2 5
x x x x
x x x x
x x x
   


   


  


(3) x
j
≥ 0 (j =
1,6
)
Giải

số
Ẩn cơ
bản
Phương
án
x
1
x
2
x
3
x
4
x
5
x
6

3
4
2
x
3
x
6
x
1
6
3
5

1
1
0
0
1

1/3
-4/3
1/3
-1/3
-2/3
2/3
-5/3
-16/3
1
0
0
0
1
0
f(x) 8 0 1/3*
-16/3
-56/3 0 0
-1 4 2

-2

-4
3/2

-1/2
2
0

1

0
f(x) 7 0 0
-11/2
-19
-1/2
0
3

2/3

Bảng II:
h
1
:=
1
1
3
h


h
2
:= h
2
-
1
3
h
1
:
h
3
:= h
3
+
1
4
:
3
h

h
c
:= h
c
-
1
:
3
c

1. Nếu
0
j
 
với mọi j = 1, ,n, thì phương án cơ bản ban đầu x
0
(là phương án có
thành phần thứ i
k
là
0
k
i
x
= b
k,
còn các thành phần khác bằng 0) là một phương án tối ưu
của bài toán max đang xét với f(x
0
) = f
0
.
2. Nếu tồn tại
0
v
 
sao cho a
iv
≤ 0 với mọi i = 1, ,m, thì bài toán max đang xét
vô nghiệm, nghĩa là không có phương án tối ưu nào.

1
, x
2
, x
3
) = 3x
1
+ 8x
2
+ 5x
3
 max

1 2
1 3
1 2 3
3 4;
(2) 2 7;
3 2 12.
x x
x x
x x x
 


 


  
