Giáo trình Quy hoạch tuyến tính

1 UBND TỈNH QUẢNG NGÃI
TRƯỜNG ĐẠI HỌC PHẠM VĂN ĐỒNG
BÀI GIẢNG
 QUY HOẠCH 
 TUYẾN TÍNH 
 Biên soạn : ThS. PHAN BÁ TRÌNH
Quaûng Ngaõi, Thaùng 5 - 2014
2LỜI NÓI ĐẦU
 Quy hoạch tuyến tính là lĩnh vực toán học nghiên cứu các bài toán tối ưu trên hữu
hạn biến mà hàm mục tiêu và các ràng buộc đều là hàm số và các phương trình hoặc 
bất phương trình tuyến tính.
 Khi Dantzig công bố phương pháp đơn hình để giải các bài toán lập kế hoạch cho 
không quân Mỹ năm 1947 là xuất phát từ yêu cầu về quản lý và cũng từ đó các dạng
bài toán khác nhau đều tìm cách đưa về quy hoạch tuyến tính và dùng phương pháp 
đơn hình để giải. Người ta cũng dùng quy hoạch tuyến tính để phân tích các mô
hình lý thuyết kinh tế cổ điển của Walras được đề xuất từ năm 1874 một cách hoàn 
chỉnh.
 Các nhà toán học như Kantorovich và Koopmans là những nhà toán học có nhiều 
công trình nghiên cứu và ứng dụng quy hoạch tuyến tính thành công nhất trong lĩnh
vực kinh tế mà chúng ta thường gọi là toán kinh tế. Năm 1975, Kantorovich và
Koopmans được giải thưởng Nobel về khoa học kinh tế. 
 Quy hoạch tuyến tính là môn học bắt buộc đối với các trường thuộc khối ngành
khoa học tự nhiên, kinh tế, sư phạm
Bài giảng Quy hoạch tuyến tính dành cho sinh viên các lớp thuộc ngành sư phạm 
Toán, ngành kinh tế,
 Nội dung “ Bài giảng Quy hoạch tuyến tính” gồm 5 chương:
 Chương 1. Bài toán quy hoạch tuyến tính
 Chương 2. Tính chất của tập phương án và tập phương án tối ưu của bài toán quy 
 hoạch tuyến tính
 Chương 3. Phương pháp đơn hình và các thuật toán của nó
 Chương 4. Bài toán đối ngẫu, thuật toán đơn hình đối ngẫu
 Chương 5. Bài toán vận tải, thuật toán thế vị
 Bài giảng đã trình bày những nội dung căn bản nhất của quy hoạch tuyến tính như
cấu trúc đa dạng của bài toán và cách chuyển đổi sang cấu trúc chính tắc, chuẩn tắc
của bài toán quy hoạch tuyến tính, cấu trúc bài toán đối ngẫu, các phương pháp giải
3bài toán quy hoạch tuyến tínhĐặc biệt, sau mỗi chương có phần bài tập rất phong 
phú để củng cố kiến thức và rèn luyện kỹ năng tính toán.
 Bài giảng đã giới thiệu các ví dụ minh hoạ, những bài toán ứng dụng trong nhiều 
lĩnh vực khác nhau sẽ giúp ích cho các bạn sinh viên các nhà quản lý, các nhà kinh 
tế
 Chúng tôi hy vọng rằng “Bài giảng Quy hoạch tuyến tính” là một tài liệu học tập 
bổ ích cho sinh viên và là nguồn tư liệu phong phú cho quý Thầy, Cô giáo tham 
khảo, nghiên cứu. 
 Là lần viết đầu tiên, nên chắc chắn bài giảng còn nhiều thiếu sót. Chúng tôi hết
sức chân thành cảm ơn sự góp ý, nhận xét của bạn đọc về nhiều phương diện để bài
giảng ngày càng được tốt hơn.
 Mọi góp ý xin gửi về:
 Phan Bá Trình, Khoa Cơ bản - Trường Đại học Phạm Văn Đồng.
 Email: pbtrinh@pdu.edu.vn
4Chương 1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
1.1. Một vài bài toán thực tế
1.1.1. Xây dựng mô hình toán học cho một số vấn đề thực tế
Các bước thực hiện để lập mô hình toán học cho vấn đề thực tế
Bước 1. Tìm kiếm thông tin gốc
Đây là quá trình thu thập các số liệu kinh tế - kỹ thuật. Bước này khá quan trọng 
vì tất cả các bước sau dựa vào các số liệu này để tính toán. Nó quyết định tính chính 
xác của kết quả thu được. Mỗi bài toán kinh tế cụ thể đòi hỏi các thông tin gốc khác 
nhau.
Bước 2. Xử lý số liệu
Bước này có thể chia thành hai giai đoạn
i) Lập mô hình bài toán
Từ những số liệu và các yêu cầu về kinh tế - kỹ thuật, ta chuyển thành mô hình 
toán học. Đòi hỏi ở bước này là phải thiết lập chính xác và đầy đủ các điều kiện của 
bài toán.
ii) Lựa chọn thuật toán thích hợp và giải bài toán
Đây là quá trình tính toán trên mô hình toán dựa vào các thành tựu và toán học 
đã có.
Kết quả ở bước này chính là lời giải cơ bản để đưa ra giải pháp tối ưu về mặt 
kinh tế. Vì vậy đây là bước quan trọng.
Bước 3. Thông tin kết quả
Thực chất của bước này là sự diễn giải các thông tin về mặt toán học thành các
thông tin về mặt kinh tế. Nghĩa là, dựa vào các kết quả tính toán đã có để những nhà 
làm chính sách đưa ra các quyết định kinh tế.
1.1.2. Một vài bài toán thực tế
1.1.2.1. Bài toán lập kế hoạch sản xuất
Bài toán tổng quát:
Trong một chu kì sản xuất một doanh nghiệp sử dụng m loại nhân tố sản xuất 
khác nhau để sản xuất ra n loại sản phẩm khác nhau E1, E2, , En. 
5Tiềm năng về các nhân tố sản xuất này của doanh nghiệp là có hạn cho bởi vec 
tơ b = (b1, b2, , bm). 
Biết rằng để sản xuất ra một đơn vị sản phẩm Ej njj ,1:  cần chi phí hết aij
đơn vị nhân tố sản xuất thứ i mii ,1:  lợi nhuận khi bán sản phẩm được cho bởi 
vectơ c = (c1, c2, ..., cn). Đặt: nmijaA . 
Vậy doanh nghiệp cần phải lập kế hoạch sản xuất bao nhiêu để không bị động 
về tiềm năng các nhân tố sản xuất và thu được lợi nhuận lớn nhất. 
Phân tích: 
Gọi x1, x2 ,, xn lần lượt là số sản phẩm E1, E2 ,, En (trong kế hoạch cần sản 
xuất)
Theo đề bài ta có mô hình toán học như sau:
Tìm x = (x1, x2, , xn) thỏa mãn: 
f(x) = c1x1 + c2x2 +  + cnxn max (1) 
a11x1 + a12x2 + + a1nxn b1
a21x1 + a22x2 + + a2nxn b2 (2)
.
am1x1 + am2x2 +  + amnxn bm
xj 0 njj ,1:  (3)
hay ta viết gọn dưới dạng ma trận 
f(x) = cTx max (1/)
Ax b (2/)
x 0 (3/)
Ví dụ 1:
Một công ty phần mềm chuyên sản xuất 2 loại phần mềm A và B. Với đội ngũ 
gồm 6 thạc sỹ và 8 kỹ sư tin học. 
Biết rằng: Để sản xuất hoàn thành 1 phần mềm A cần 2 thạc sỹ và 1 kỹ sư, để 
sản xuất hoàn thành 1 phần mềm B cần 1 thạc sĩ và 3 kỹ sư. Qua tiếp thị trên thị 
trường được biết nhu cầu cực đại của cả 2 phần mềm. Giá bán ra cho một loại phần 
mềm A là 2000USD và cho một loại phần mềm B là: 3000USD. 
6Hãy lập kế hoạch sản xuất cho mỗi tháng để thỏa mãn yêu cầu thị trường, 
không bị động về đội ngũ, doanh thu đem về cho công ty lớn nhất. 
Giải:
Gọi x1, x2 lần lượt là số lượng phần mềm A và B cần sản xuất. 
Theo để bài ta có mô hình toán học: 
Tìm x = (x1, x2): 
f(x) = 2x1 + 3x2 max (Đơn vị tính: 1.000USD) (1)
83
62
21
21
xx
xx
 (2)
x1 0; x2 0 (3)
1.1.2.2. Bài toán vận tải 
Bài toán:
Ta cần vận chuyển một loại mặt hàng nào đó (Chẳng hạn: máy tính, linh kiện 
điện từ, gạo, gỗ, xi măng, xăng dầu,) gồm có m trạm phát hàng A1, A2, , Am
với lượng hàng yêu cầu phát đi tương ứng là a1, a2, , am đơn vị hàng, n trạm thu 
hàng B1, B2, , Bn với lượng hàng yêu cầu chuyển đến tương ứng là b1, b2, , bn
đơn vị hàng và ma trận cước phí vận chuyển (Chi phí vận chuyển một đơn vị hàng)
 c11 c12  c1n
 c21 c22  c2n
 C = . viết gọn là: 
nmij
cC
.
 .
 cm1 cm2  cmn
Ở đây cij njmiji ,1 ;,1:,  : là cước phí vận chuyển cho mỗi đơn vị hàng 
hóa được chuyển từ trạm phát Ai đến trạm thu Bj. 
Bài toán đặt ra với điều kiện 
1 1
m n
i j
i j
a b
   (*)
(*) gọi là điều kiện cân bằng thu phát tức là: Tổng lượng hàng phát đáp ứng đầy 
đủ cho tổng lượng hàng thu (cung bằng cầu). Hãy lập kế hoạch vận chuyển hàng 
sao cho: 
- Các trạm phát (cung) hết lượng hàng hiện có.
7- Các trạm thu (cầu) nhận đủ lượng hàng yêu cầu.
- Tổng chi phí vận chuyển nhỏ nhất.
Phân tich:
Gọi xij njmiji ,1 ;,1:,  : là lượng hàng vận chuyển từ Ai đến Bj
Thấy rằng xij 0; njmiji ,1 ;,1:,  trong đó xij > 0 khi Ai phát hàng cho 
Bj; còn xij = 0 khi Ai không phát hàng cho Bj. Khi đó mô hình của bài toán nói trên 
là: Tìm một ma trận phân phối và vận chuyển hàng:
x11 x12  x1n
x21 x22  x2n
 X = . viết gọn 
nmij
xX
.
 .
xm1 xm2  xmn
thỏa mãn các điều kiện sau: 
 f(x) = 
1 1
m n
ij ij
i j
c x
 min (tổng chi phí vận chuyển bé nhất) (1)
i
n
j
ij ax 
 1
(tổng lượng hàng phát đi từ trạm Ai) mii ,1:  ; 
j
m
i
ij bx 
 1
(tổng lượng hàng chuyển đến trạm Bj) njj ,1:  .
 xij 0; njmiji ,1 ;,1:,  (3)
Ví dụ 2:
Ta cần vận chuyển máy tính từ 2 công ty (trạm phát): P1, P2 đến 3 nơi tiêu thụ (trạm 
thu) T1, T2 và T3. Số lượng máy tính ở mỗi công ty cần chuyển, nhu cầu máy tính tại 
các nơi tiêu thụ cũng như cước phí vận chuyển cho mỗi máy tính được chuyển từ 
công ty Pi đến nơi tiêu thụ Tj 3,1 ;2,1:,  jiji được cho trong bảng sau: 
T1: 15 (máy) T2: 20 (máy) T3: 25 (máy)
P1: 20 (máy) 5 (nghìn đồng) 7 (nghìn đồng) 2 (nghìn đồng)
P2: 40 (máy) 4 (nghìn đồng) 4 (nghìn đồng) 6 (nghìn đồng)
Hãy lập kế hoạch vận chuyển như thế nào để:
(2)
Cước phí
Công ty
Trạm thu
8- Các công ty phải phân phối hết số máy tính hiện có.
- Các nơi tiêu thụ nhận đủ số máy theo nhu cầu.
- Tổng cước phí vận chuyển là thấp nhất.
Giải:
Gọi xij là số máy tính sẽ vận chuyển từ công ty (Pi) đến nơi tiêu thụ (Tj) 
 njmiji ,1 ;,1:, 
Với điều kiện: xij 0 njmiji ,1 ;,1:,  .
Số máy tính vận chuyển từ P1 đến 3 nơi tiêu thụ là: 
x11 + x12 + x13
Số máy tính vận chuyển từ P2 đến 3 nơi tiêu thụ là: 
x21 + x22 + x23
Số máy tính vận chuyển đến tiêu thụ T1 từ 2 công ty là: 
x11 + x21
Tổng số máy tính vận chuyển đến tiêu thụ T2 từ 2 công ty là: 
x12 + x22
Tổng số máy tính vận chuyển đến tiêu thụ T3 từ 2 công ty là: 
x13 + x23
Tổng cước phí phải chi trả là: (Tổng này càng nhỏ càng tốt) 
5x11 + 7x12 + 2x13 + 4x21 + 3x22 + 6x23
Theo đề bài ta có mô hình toán học của bài toán là: 
Tìm x = (xij) 3,1 ;2,1:,  jiji thỏa mãn: 
f(x) = 5x11 + 7x12 + 2x13 + 4x21 + 3x22 + 6x23 min (1)
x11 + x12 + x13 = 20
x21 + x22 + x23 = 40
x11 + x21 = 15 (2)
x12 + x22 = 20
x13 + x23 = 25
xij 0 3,1 ;2,1:,  jiji . (3)
9Ma trận hệ số 
1 0 0 1 0 0
0 1 0 0 1 0
0 0 1 0 0 1
1 1 1 0 0 0
0 0 0 1 1 1
A ; 
25
20
15
40
20
B ;
11 12 13
21 22 23
 x x
 x x
x
X
x
Ở đây thay vì viết x = (x11, x12, x13, x21, x22, x23) ta viết thành ma trận như trên đề 
mỗi hàng ứng với một trạm phát và mỗi cột ứng với một trạm thu cho dễ hình dung. 
1.1.2.3. Bài toán khẩu phần thức ăn
Bài toán:
Giả sử ta đã biết được nhu cầu tối thiểu hằng ngày về các chất dinh dưỡng 
(đường, đạm, béo, khoáng...) cần cho một loại đối tượng nào đó (trẻ con, người lớn, 
heo, gà,...). 
Để cung cấp các chất dinh dưỡng này hiện có một số thức ăn có thể mua được 
trên thị trường và cũng biết tỉ lệ các chất dinh dưỡng trong mỗi loại thức ăn cũng 
như giá cả của chúng.
Vấn đề đặt ra là cần xác định số lượng thức ăn mỗi loại trong khẩu phần thức ăn 
hàng ngày sao cho vừa đảm bảo cung cấp đủ chất dinh dưỡng đồng thời giá thành là 
rẻ nhất.
Bài toán khẩu phần thức ăn là một bài toán cụ thể nhưng mô hình của nó có thể 
dùng cho các bài toán khác. 
Thực chất đây là bài toán hỗn hợp nhiều thành phần để đạt được yêu cầu nào đó 
về chất lượng sản phẩm, đồng thời có giá thành rẻ nhất. 
Có thể áp dụng mô hình này cho các ngành như luyện kim, hoá chất,...
Phân tích:
Ký hiệu: n là số loại thức ăn.
 m là số loại dinh dưỡng cần cho khẩu phần.
 aij là hàm lượng chất dinh dưỡng i có trong một đơn vị thức ăn j
 njmiji ,1 ;,1:,  .
 bi là số đơn vị chất dinh dưỡng i cần cho 1 khẩu phần thức ăn 
 mii ,1: 
10
 cj là đơn giá 1 đơn vị thức ăn j njj ,1:  .
 xj là số lượng thức ăn j cần mua cho 1 khẩu phần thức ăn njj ,1:  .
Hàm mục tiêu là: nn xcxcxcxf ...2211 .
Bài toán có thể phát biểu như sau:
Xác định các giá trị x1, x2, , xn sao cho hàm mục tiêu f đạt giá trị nhỏ nhất 
đồng thời đảm bảo yêu cầu dinh dưỡng cho mỗi khẩu phần thức ăn.
Mô hình toán học của bài toán là:
 min...2211 nn xcxcxcxf (1)
mnmnmm
nn
nn
bxaxaxa
bxaxaxa
bxaxaxa
...
................................................
...
...
2211
22222121
11212111
(2)
0...;;0 ;0 21 nxxx (3)
Ví dụ 3:
Có 3 loại thức ăn I, II, III dùng trong chăn nuôi. Các chất dinh dưỡng cơ bản là 
chất đạm, chất béo và Albumin. Mức độ yêu cầu các chất dinh dưỡng trong một 
ngày, hàm lượng các chất dinh dưỡng trong mỗi loại thức ăn và giá cả của chúng 
cho ở bảng sau:
 Thức ăn
Dinh dưỡng
I II III
 Đạm 0,5 10 0,4 20
 Béo 3,0 0,5 0,7 10
 Albumin 0,3 0,8 2,0 15
0,8 1,5 3,0
 Yêu cầu
Đơn giá
Các số liệu được hiểu như sau:
Một đơn vị thức ăn loại I có 0,5 đơn vị chất đạm, 3 đơn vị chất béo và 0,3 đơn 
vị Albumin.
11
Mỗi đơn vị thức ăn loại I; II; III lần lượt có giá trị tương ứng là: 0,8; 1,5 và 3,0 
đơn vị tiền.
Yêu cầu tối thiểu của chất đạm là 20 đơn vị, của chất béo là 10 đơn vị và của 
Albumin là 15 đơn vị.
Xác định số liệu để ghi vào bảng trên là công việc của các nhà kinh tế, chuyên 
môn, không thuộc phạm vi quy hoạch tuyến tính.
Nhiệm vụ đặt ra là: cần xác định số liệu thức ăn mỗi loại sao cho đảm bảo yêu 
cầu về dinh dưỡng, đồng thời giá thành khẩu phần thức ăn là nhỏ nhất.
Ta cần thành lập mô hình của bài toán này:
Gọi x1, x2, x3 lần lượt là số lượng thức ăn loại I, II, III cần mua. Đây là những 
số cần tìm.
Hàm mục tiêu sẽ là:
 min35,18,0 321 xxxxf (1)
Hệ ràng buộc là:
152 8,03,0
107,05,03 
204,010 5,0
321
321
321
xxx
xxx
xxx
(2)
0 ;0 ;0 321 xxx . (3)
Điều kiện (3) có được là vì số lượng thức ăn không thể âm.
Nhiệm vụ của bài toán là tìm bộ giá trị (x1, x2, x3) thoả mãn các ràng buộc (2), 
(3) và sao cho hàm mục tiêu f(x) đạt giá trị nhỏ nhất.
Nhận định chung:
Qua các ví dụ được trình bày ở phần trên, ta thấy rằng trong nhiều lĩnh vực khác 
nhau có những yêu cầu khác nhau trong việc đề ra các quyết định định lượng nhằm 
tối ưu hóa sản xuất. Nhưng những yêu cầu này có thể được diễn giải thành mô hình 
toán học và tổng quát hóa như sau: 
(1) Điều kiện tối ưu hóa: Đòi hỏi thỏa mãn yêu cầu về mặt kinh tế bao gồm 2 
trường hợp cực đại hóa hoặc cực tiểu hóa. 
12
(2) Điều kiện ràng buộc: Bao gồm một hệ gồm các phương trình họăc bất 
phương trình bậc nhất. Hệ thống các ràng buộc này xuất phát từ những đòi hỏi cần 
được thỏa mãn về mặt kỹ thuật. 
(3) Điều kiện về dấu: Xuất phát từ yêu cầu thực tiển là các quyết định đỏi hỏi 
không âm. 
Các cách biểu diễn của bài toán quy hoạch tuyến tính như sau: 
Tìm x = (x1, x2, , xn) R
n thỏa mãn: 
 f(x) = x1c1 + x2c2 +  + xncn min/ (max) (1) 
a11x1 + a12x2 + + a1nxn   b1
a21x1 + a22x2 +  + a2nxn   b2
 (2)
am1x1 + am2x2 +  + amnxn   bm
xj 0 njj ,1:  (3) 
Hay viết gọn: 
 Tìm x = (x1, x2, , xn) với xj R njj ,1:  thỏa mãn: 
f(x) = 
1
n
j j
j
c x
 min/ (max) (1) 
1
n
ij j
j
a x
   ; mii ,1:  (2)
xj 0; njj ,1:  (3) 
Dạng ma trận của bài toán:
Gọi 
nmij
aA
.
 ; c = (c1 c2  cn)
T, 
x = (x1 x2  xn)
T, 
b = (b1 b2  bm)
T.
Khi đó: Bài toán quan hệ tuyến tính tổng quát có thể viết: 
f(x) = cTx min/ (max) (1/) 
Ax   b (2/)
x 0 (3/) 
13
Trong đó các aij, bj và các cj đều đã biết, còn xj njj ,1:  là các ẩn số
 njmiji ,1 ;,1:,  . 
1.2. Các dạng bài toán quy hoạch tuyến tính
1.2.1. Bài toán quy hoạch tuyến tính tổng quát
Bài toán quy hoạch tuyến tính tổng quát được định nghĩa như sau:
 (max)min/...2211 nn xcxcxcxf (1)
 
 
m1,i:i 
 ...2211 ininii bxaxaxa
(2)
  0 jx hoặc tuỳ ý njj ,1:  (3)
(Ký hiệu:   nghĩa là lấy một trong 3 dấu trong ngoặc;
   nghĩa là lấy một trong 2 dấu trong ngoặc).
- Hàm f gọi là hàm mục tiêu của bài toán
- Phương án của bài toán là vectơ nxxxx ...,,, 21 thoả mãn ràng buộc (2) và 
(3). Ký hiệu S là tập tất cả các phương án của bài toán.
- Phương án tối ưu của bài toán là **2*1* ...,,, nxxxx làm cho hàm mục tiêu f đạt 
giá trị nhỏ nhất đối với bài toán min và lớn nhất đối với bài toán max, tức là phương 
án thoả mãn điều kiện (1). Ký hiệu S* là tập tất cả các phương án tối ưu của bài 
toán.
- Trị tối ưu của bài toán là: **22
*
11
*
... nn xcxcxcxf 
trong đó **2*1* ...,,, nxxxx là phương án tối ưu.
- Hai bài toán quy hoạch tuyến tính gọi là tương đương nếu chúng có cùng tập 
phương án và tập phương án tối ưu.
G ...  lớn nhất để bố trí trước, ở bài toán này đối với công nhân 6 ta chọn 
công việc thứ 6 vì có năng suất làm việc c66= 138% là lớn nhất. Tương tự ta chọn 
cho các công nhân khác.
Phương án cho trên bảng cũng là phương án tối ưu của bài toán.
1
1
1
1
1
1
107
5.5.3. Bài toán vận tải có ô cấm
5.5.3.1. Nội dung phương pháp 
Trong thực tế cũng thường xảy ra trường hợp:
Hàng từ trạm phát Ah mh 1 không thể chở đến trạm thu Bk nk 1 có
nhiều lý do khác nhau, chẳng hạn từ trạm phát Ah đến trạm thu Bk không có đường 
đi hoặc trạm thu Bk không có nhu cầu về hàng hoá của trạm phát Ah. 
Ô (h, k) gọi là ô cấm. Vì vậy ta có bài toán vận tải có ô cấm.
Để giải bài toán vận tải có ô cấm ta thực hiện như sau:
- Gán cho các ô cấm (h, k) hệ số chi phí Chk = M, với M là một số rất lớn .
- Giải bằng phương pháp thế vị một cách bình thường.
Lưu ý
Khi xét tiêu chuẩn tối ưu, biểu thức ijjiij cvu sẽ dương (âm) nếu chứa M 
với dấu dương (âm).
5.5.3.2. Ví dụ 
Giải bài toán vận tải có ô cấm sau:
 Bj
Ai
b1
45
b2
100
b3
50
b4
60
a1
70
M
16 15 11
a2
100
10
17 9 M
a3
85
12
14 10 13
Giải. 
Mục đích của chúng ta là phân phối sao cho chi phí đạt giá trị nhỏ nhất (min) 
cho nên chi phí cho các ô cấm sẽ được gán là M > 0, rất lớn.
Sử dụng phương pháp chi phí nhỏ nhất để tìm phương án cơ bản ban đầu, ta 
được:
108
 Bj
Ai
b1
45
b2
100
b3
50
b4
60
a1
70
M
16
 10
15 11
 60
a2
100
10
 45
17
 5
9
 50
M
a3
85
12
14
 85
10 13
Phương án cơ bản ban đầu:
0 0 85 0
0 50 5 45
60 0 10 0
0X .
Số ô chọn của X0 là 6 = 3 + 4 -1, nên X0 không suy biến. 
Hàng 2 và cột 2 cùng có số ô chọn nhiều nhất. 
Ở đây chúng ta chọn hàng 2, nên ta gán u2 = 0, sau đó tính các thế vị còn lại 
như bảng sau:
 Bj
Ai
b1
45
b2
100
b3
50
b4
60
ui
a1
70
M
 9-M 
16
 10
15
 -7
11
 60
-1
a2
100
10
 45
17
 5
9
 50
M
 12-M
0
a3
85
12
 -5
14
 85
10
 -4
13
 -4
-3
vj 10 17 9 12
Với hệ thống thế vị vừa tìm được, chúng ta tiến hành tính các hệ số ước lượng.
109
Từ bảng trên ta có: do M > 0, rất lớn nên jiij ,,0  . Do đó phương án đang 
xét là phương án tối ưu của bài toán.
Vậy phương án tối ưu của bài toán là:
0 0 85 0
0 50 5 45
60 0 10 0
*X
và trị tối ưu là: 2995* Xf .
5.5.4. Bài toán xe không 
5.5.4.1. Nội dung phương pháp
Đối với các doanh nghiệp kinh doanh vận tải thì việc bố trí các xe chạy theo các 
tuyến là rất quan trọng. Cần bố trí sao cho tổng số tấn - km xe chạy không là nhỏ 
nhất.
Ở trên ta xét bài toán phân phối hàng hoá từ các trạm phát Ai đến các trạm thu 
Bj. Giải bài toán này ta mới biết lượng xij trong phương án tối ưu là bao nhiêu (tấn), 
nhưng ta chưa bố trí được các xe tải đi theo các tuyến này như thế nào cho hợp lý 
(trên quan điểm của xí nghiệp vận tải) để cho xe ít phải chạy không hàng (tức tổng 
số tấn - km xe chạy không là nhỏ nhất).
Bài toán đặt ra như sau:
Có những loại hàng khác nhau cần chở từ một số trạm này đến một số trạm 
khác. Lượng hàng cần vận chuyển và hệ thống đường sá nối liền các trạm đã biết. 
Cần xác định hành trình của các xe sao cho tổng số tấn - km là nhỏ nhất. 
Gọi một T - km xe không là số đo của một xe có trọng tải 1 tấn chạy không 
hàng trên đoạn đường 1 km.
Chú ý rằng trạm thu hàng lúc này trở thành trạm phát xe không và trạm phát 
hàng trở thành trạm thu xe không. Có bao nhiêu xe chở hàng đến trạm thu thì có bấy 
nhiêu xe không trả về các trạm phát nên bài toán bao giờ cũng cân bằng thu phát.
Như vậy bài toán hoàn toàn tương tự như bài toán phân phối hàng, chỉ cần đổi 
vai trò trạm thu thành trạm phát và ngược lại. Các thuật giải đều như cũ.
Chú ý rằng ở đây những đoạn đường chở hàng là hoàn toàn xác định, số lượng 
hàng phải chở cũng như vậy nên không có vấn đề giảm tổng số T-km xe chạy có 
110
hàng, mà chỉ có khả năng xác định hành trình của các xe sao cho tổng số T-km xe 
không là nhỏ nhất.
Ký hiệu:   là tuyến xe chạy có tải; 
là tuyến xe chạy không có tải .
 [ xi j ] : khối lượng hàng phải vận chuyển;
 ( xi j ) : ứng với phương án tối ưu của bài toán xe không.
Nếu trong một ô có 2 số: [ xi j ] và ( xi j ), ta chọn số nhỏ nhất (đó là số tấn trọng 
tải xe cần điều động).
Sau khi giải bài toán có phương án vận chuyển với tổng số T-km xe không là 
nhỏ nhất. Sau đó ta còn phải bố trí cụ thể hành trình chi tiết cho từng xe.
 5.5.4.2. Ví dụ 
Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây:
Nơi cấp hàng Loại hàng Trọng tải xe (tấn) Nơi nhận hàng
A1 Sắt
40
20
35
B1
B3
B4
A2 Xi măng
10
15
40
B1
B2
B4
A3 Gạch
30
40
B2
B3
Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng:
3 2 5 4
6 1 4 3
1 4 3 2
.
Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với 
tổng số tấn x km xe chạy không tải là ít nhất.
Giải.
Giả thiết các xe có thể chở được tất cả loại hàng trên.
111
A1: 40 + 20 + 35 = 95; 
A2: 10 + 15 + 40 = 65 ; 
A3: 30 + 40 = 70; 
B1: 40 + 10 = 50;
B2: 15 + 30 = 45; 
B3: 20 + 40 = 60;
B4: 35 + 40 = 75.
a) Thực hiện phương pháp thế vị giải bài toán thu phát xe không:
 Phát
Thu 50 45 60 75 ui
95
2
 20 
3
4 1
 75
u1 = 0
65
3
 5
4
1
 60
6
u2 = 1
70
4
 25
5
 45
2 3
u3 = 2
vj v1 = 2 v2 = 3 v3 = 0 v4 = 1
 jiCvu ijjiij ,;0 .
Nên phương án tối ưu là: 
0 0 45 25
0 60 0 5 
75 0 0 20
*X
và trị tối ưu là: 515*min Xf .
b) Kết hợp với kế hoạch vận chuyển, ta có bảng:
[40]
 (20)
[20] [35]
 (75)
[10]
 (5)
[15]
 (60)
[40]
 (25)
[30]
 (45)
[40]
112
Trên bảng ta có 4 ô vừa có ô tròn, vừa có ô vuông là: (1,1); (1,4); (2,1); (3,2) 
tương ứng ta có 4 tuyến điều động:
TABA 20:111 
TABA 35:141 
TABA 5:212 
TABA 30:323 .
Sau khi giảm lượng chênh lệch giữa ô tròn và ô vuông giữa, ta có bảng mới:
[20]
[20]
 (40)
[5]
[15]
 (60)
[40]
 (25)
 (15)
[40]
TABABA 20:14231 
[20]
 (20)
[5]
[15]
 (40)
[20]
 (25)
 (15)
[40]
TABABA 5:23312 
[20]
 (20)
[15]
 (35)
[20]
 (20)
 (15)
[35]
 TABABA 15:23322 
113
[20]
 (20)
[15]
 (20)
[20]
 (20)
[20]
 TABABABA 20:1423311 .
Tóm lại: TABA 20:111 
TABA 35:141 
TABA 5:212 
TABA 30:323 
 TABABA 5:23312 
 TABABA 15:23322 
 TABABABA 20:1423311 .
114
Bài tập chương 5.
 BÀI TOÁN VẬN TẢI, THUẬT TOÁN THẾ VỊ
Bài 1. 
Giải bài toán vận tải
30 40 50 60
 30 5 4 6 4
 40
4 3 5 3
 110
2 2 1 7
Bài 2. 
Giải bài toán vận tải
110 40 30
60
7 3 4
50
1 5 6
40
2 3 4
30
2 4 5
Bài 3. 
Giải bài toán vận tải
104 22 40 118
31
1 4 2 2
50
3 4 2 4
75
4 3 2 3
128
2 4 4 4
Bài 4. 
Giải bài toán vận tải 
cij
A
B
cij
A
B
cij
A
B
115
60 25 15 20
30
4 3 2 1
40
2 8 6 5
50
3 5 7 9
Bài 5. 
Giải bài toán vận tải
60 60 80 50
100
5 4 6 2
20
3 1 4 7
130
4 5 6 3
Bài 6. 
Giải bài toán vận tải tìm max:
 Bj
Ai
b1
76
b2
62
b3
88
b4
45
b5
40
a1
79
10
19 15 6 7
a2
102
13
11 8 7 4
a3
70
12
17 10 5 3
a4
60
12 18 18 9 10
cij
A
B
cij
A
B
116
Bài 7.
Giải bài toán vận tải có ô cấm sau:
 Bj
Ai
b1
70
b2
80
b3
40
b4
30
a1
100
M
30 45 M
a2
80
55
40 30 50
a3
40
50
35 35 45
Bài 8.
Giải bài toán vận tải có ô cấm sau:
 Bj
Ai
b1
50
b2
80
b3
35
b4
65
a1
55
7
11 14 101
a2
115
10
M 9 M
a3
60
12
10 11 14
Bài 9. Giải bài toán vận tải có ô cấm sau:
 Bj
Ai
b1
140
b2
155
b3
170
a1
110
5
7 10
a2
125
8
5 9
a3
120
12
6 11
a4
135
9 8 13
Với điều kiện trạm a2 và trạm a4 phát hết hàng.
117
Bài 10.
Giải bài toán vận tải có ô cấm sau:
 Bj
Ai
b1
45
b2
55
b3
40
b4
75
a1
70
5
6 6 8
a2
65
4
5 8 7
a3
55
3
4 7 3
 Với điều kiện trạm b1 và trạm b3 thu đủ hàng.
Bài 11.
Giải bài toán không cân bằng thu phát sau:
Bj
Ai
b1
25
b2
35
b3
60
b4
30
a1
20
2
3 1 4
a2
40
4
5 3 2
a3
60
1
2 7 6
Bài 12.
Giải bài toán không cân bằng thu phát sau:
 Bj
Ai
b1
20
b2
30
b3
45
b4
50
a1
40
5
8 6 11
a2
30
6
7 7 12
a3
55
8
8 9 10
118
Bài 13.
Giải bài toán không cân bằng thu phát sau:
 Bj
Ai
b1
50
b2
35
b3
65
b4
75
a1
90
2
3 1 4
a2
75
4
5 3 2
a3
80
1
2 7 6
Bài 14.
Giải bài toán không cân bằng thu phát sau:
 Bj
Ai
b1
50
b2
70
b3
75
a1
40
12
14 25
a2
65
26
17 13
a3
45
15
18 19
a4
60
16 23 22
Bài 15.
Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây:
Nơi cấp hàng Loại hàng Trọng tải xe (tấn) Nơi nhận hàng
A1 Đường
50
20
B1
B4
A2 Đậu
45
5
30
B2
B3
B4
A3 Hạt điều
35
55
B1
B3
Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng:
5 2 5 4
3 1 4 3
2 4 3 2
.
119
Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với 
tổng số tấn x km xe chạy không tải là ít nhất.
Bài 16.
Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây:
Nơi cấp hàng Loại hàng Trọng tải xe (tấn) Nơi nhận hàng
A1 Gạo
30
40
50
B1
B2
B3
A2 Đường
75
55
B3
B4
A3 Sữa
20
50
15
B1
B2
B4
Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng:
2 4 1 3
3 5 2 1
4 1 3 6
.
Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với 
tổng số tấn x km xe chạy không tải là ít nhất.
Bài 17.
Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây:
Nơi cấp hàng Loại hàng Trọng tải xe (tấn) Nơi nhận hàng
A1 Gạo
50
30
B2
B4
A2 Mì
25
40
B1
B3
A3 Đường
10
15
B1
B2
Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng:
60 50 60 30
40 60 30 40
30 70 50 20
.
120
Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với 
tổng số tấn x km xe chạy không tải là ít nhất.
Bài 18.
Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây:
Nơi cấp hàng Loại hàng Số lượng (tấn) Nơi nhận hàng
A1 Cam
50
20
B1
B2
A2 Bưởi
10
40
B1
B3
A3 Sầu riêng
50
30
B4
B2
Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng:
50 20 40 50
20 10 30 40
50 40 20 30
.
Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với 
tổng số tấn x km xe chạy không tải là ít nhất.
Bài 19.
Một xí nghiệp vận tải thực hiện kế hoạch vận tải sau đây:
Nơi cấp hàng Loại hàng Trọng tải xe (tấn) Nơi nhận hàng
A1 Gạo
100
50
B1
B2
A2 Bắp
10
50
B1
B3
A3 Bột mì
100
80
B4
B2
Ma trận khoảng cách từ nơi cấp hàng đến nơi nhận hàng:
60 50 65 30
45 65 30 40
35 70 55 25
.
Yêu cầu lập kế hoạch điều động xe sao cho thực hiện được kế hoạch vận tải với 
tổng số tấn x km xe chạy không tải là ít nhất.
121
TÀI LIỆU THAM KHẢO
[1] Trần Đình Ánh (2007), Bài tập Quy hoạch tuyến tính, NXB Giáo dục, Hà Nội. 
[2] Phí Mạnh Ban (1998), Quy hoạch tuyến tính, NXB Giáo dục, Hà Nội. 
[3] Trần Quốc Chiến (2007), Giáo trình quy hoạch tuyến tính, Đại học Đà 
Nẵng, (Lưu hành nội bộ).. 
[4] Võ Văn Tuấn Dũng (2007), Giáo trình quy hoạch tuyến tính, NXB Thống kê. 
[5] Hoàng Đức Hải -Vũ Thị Bích Liên - Trần Gia Tùng (2000), Giáo trình Toán 
kinh tế , NXB Giáo dục, Hà Nội.
[6] Đặng Hấn (1995), Quy hoạch tuyến tính (Lý thuyết & Bài tập có lời giải), 
Trường ĐH Kinh tế Tp Hồ Chí Minh, (Lưu hành nội bộ).
[7] Nguyễn Đức Hiền (2009), Giáo trình quy hoạch tuyến tính, NXB Thông tin 
và truyền thông, Hà nội. 
[8] Lê Khánh Luận (2006), Lý thuyết-Bài tập-Bài giải Quy hoạch tuyến tính tối 
ưu hóa, NXB Lao động. 
[9] Nguyễn Đức Nghĩa (1996),Tối ưu hóa (Quy hoạch tuyến tính và rời rạc), 
NXB Giáo dục, Hà Nội.
[10] Lê Văn Phi (2004), Quy hoạch tuyến tính và ứng dụng trong kinh tế, NXB 
Giáo dục, Hà Nội. 
[11] Nguyễn Xuân Thủy (1995), Bài tập Quy hoạch tuyến tính, NXB Giáo dục, 
Hà Nội.
[12] Trần Túc (2001), Bài tập quy hoạch tuyến tính, NXB Khoa học Kỹ thuật.
[13] Hoàng Tụy (1967), Lý thuyết quy hoạch, NXB Giáo dục, Hà Nội.
[14] G.Dantzig (1963), Linear programming and extensions, Jersey.
[15] Kuzexov A.B., Cholod N.I., Koxtevich L.X. (1978), Hướng dẫn giải bài 
toán quy hoạch tuyến tính, NXB Đại học (Tiếng Nga). Minsk.
[16] Achmanov S. (1984), Programmation Linéeire. Edition Mir. Moscou. 
[17] Gass S.I. (1969), Linear Programming – Methols and Applications. 
McGraw-Hill Book Co. New York. 
122
MỤC LỤC
Lời nói đầu  2
Chương 1. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH... 4
1.1. Một vài bài toán thực tế 4
1.1.1. Xây dựng mô hình toán học cho một số vấn đề thực tế 4
1.1.2. Một vài bài toán thực tế.. 4
1.2. Các dạng bài toán quy hoạch tuyến tính 13
1.2.1. Bài toán quy hoạch tuyến tính tổng quát..... 13
1.2.2. Bài toán quy hoạch tuyến tính dạng chuẩn tắc 15
1.2.3. Bài toán quy hoạch tuyến tính dạng chính tắc  16
1.3. Phương pháp hình học giải bài toán quy hoạch tuyến tính hai biến . 18
1.3.1. Nội dung phương pháp...... 18
1.3.2. Các ví dụ............ 19
Bài tập chương 1.. 23 
Chương 2. TÍNH CHẤT CỦA TẬP PHƯƠNG ÁN VÀ TẬP PHƯƠNG 
 ÁN TỐI ƯU CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 27
2.1. Tập hợp lồi... 27
2.1.1. Tổ hợp lồi.. 27
2.1.2. Tập hợp lồi 27
2.1.3. Điểm cực biên của một tập hợp lồi.. 28
2.1.4. Bao lồi . 28
2.1.5. Đa diện lồi và tập lồi đa diện 29
2.2. Tính chất của tập phương án và tập phương án tối ưu của bài toán quy 
hoạch tuyến tính.. 30
2.2.1. Định lý 1 (Tính lồi của tập phương án). 30
2.2.2. Định lý 2 (Sự tồn tại lời giải của bài toán quy hoạch tuyến tính). 30
2.2.3. Định lý 3  31
2.3. Tính chất của bài toán quy hoạch tuyến tính dạng chính tắc.. 31
2.3.1. Định lý 1 (Tính chất đặc trưng của phương án cực biên) . 31
2.3.2. Hệ quả 1. .. 33
123
2.3.3. Hệ quả 2  33
2.3.4. Định lý 2 35
2.3.5. Định lý 3 35
Bài tập chương 2. 36
Chương 3. PHƯƠNG PHÁP ĐƠN HÌNH 
 VÀ CÁC THUẬT TOÁN CỦA NÓ .. 37 
3.1. Cơ sở lý luận của phương pháp đơn hình 37
3.1.1. Định nghĩa 37
3.1. 2. Các tính chất cơ bản 38
3.2. Công thức đổi cơ sở 40
3.2.1. Phép biến đổi Jordan  40
3.2.2. Giải hệ phương trình tuyến tính  41
3.2.3. Phương pháp tìm phương án . 44
3.3. Thuật toán đơn hình gốc 47
3.3.1. Thuật toán đơn hình giải bài toán quy hoạch tuyến tính.. 47
3.3.2. Các ví dụ 49
3.4. Thuật toán đơn hình với cơ sở giả. 53
3.4.1. Nội dung phương pháp  53
3.4.2. Ví dụ  54
Bài tập chương 3. 57
Chương 4 BÀI TOÁN ĐỐI NGẪU, 
 THUẬT TOÁN ĐƠN HÌNH ĐỐI NGẪU 59
4.1. Bài toán đối ngẫu. 59
4.1.1. Định nghĩa. 59
4.1.2. Mối quan hệ giữa bài toán gốc và bài toán đối ngẫu. 62
4.1.3. Tìm phương án tối ưu của bài toán đối ngẫu  63
4.2. Thuật toán đơn hình đối ngẫu.. 66
4.2.1. Nội dung thuật toán đơn hình đối ngẫu . 66
4.2.2. Thuật toán đơn hình đối ngẫu.. 68
4.2.3. Ứng dụng. 72
124
4.3. Ý nghĩa của bài toán đối ngẫu. 74
4.3.1. Ý nghĩa toán học... 74
4.3.2. Ý nghĩa kinh tế.. 77
Bài tập chương 4.. 79
Chương 5. BÀI TOÁN VẬN TẢI, THUẬT TOÁN THẾ VỊ .. 82
5.1. Một số tính chất của bài toán vận tải... 82
5.1.1. Thành lập bài toán .. 82
5.1. 2. Một số định nghĩa khác... 83
5.1. 3. Các tính chất. 84
5.2. Một số phương pháp xây dựng phương án cực biên ban đầu.. 86
5.2.1. Phương pháp góc Tây Bắc .. 86
5.2.2. Phương pháp chi phí nhỏ nhất .. 87
5.2.3. Phương pháp Foghen . 89
5.3. Thuật toán thế vị  90
5.3.1. Nội dung thuật toán thế vị  90
5.3.2. Ví dụ . 91
5.4. Bài toán vận tải suy biến . 96
5.4.1. Khái niệm về bài toán vận tải suy biến  96
5.4.2. Ví dụ . 96
5.5. Một số bài toán quy về bài toán vận tải chính tắc. 99
5.5.1. Bài toán vận tải không cân bằng thu phát.. 99
5.5.2. Bài toán vận tải tìm max. 105
5.5.3. Bài toán vận tải có ô cấm.. 107
5.5.4. Bài toán xe không ..... 109
Bài tập chương 5 114
Tài liệu tham khảo .. 121
Mục lục  122