Giáo trình Toán kinh tế (Phần 1)

 UỶ BAN NHÂN DÂN TỈNH NGHỆ AN 
TRƢỜNG ĐẠI HỌC KINH TẾ 
GIÁO TRÌNH 
TOÁN KINH TẾ 
(Dùng cho hệ Đại học và Cao đẳng) 
Lƣu hành nội bộ 
Vinh, năm 2014 
 UỶ BAN NHÂN DÂN TỈNH NGHỆ AN 
TRƢỜNG ĐẠI HỌC KINH TẾ 
GIÁO TRÌNH 
TOÁN KINH TẾ 
(Dùng cho hệ Đại học và Cao đẳng) 
Lƣu hành nội bộ 
 Th.S Nguyễn Thị Hà (Chủ biên) 
 Th.S Trần Hà Lan 
Vinh, năm 2014 
 MỤC LỤC 
Chƣơng 1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ............................................................. - 2 - 
1. MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ......................................... - 2 - 
1.1. Bài toán lập kế hoạch sản xuất ............................................................................................ - 2 - 
1.2. Bài toán phân công lao động ............................................................................................... - 3 - 
1.3. Bài toán vận tải .................................................................................................................... - 4 - 
2. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH (QHTT) ............................................................. - 5 - 
2.1. Bài toán quy hoạch tuyến tính dạng tổng quát .................................................................... - 5 - 
2.2. Bài toán quy hoạch tuyến tính dạng chính tắc và chuẩn tắc ............................................... - 7 - 
2.3. Chuyển đổi dạng bài toán quy hoạch tuyến tính ................................................................. - 9 - 
3. THUẬT TOÁN ĐỒ THỊ GIẢI BÀI TOÁN QUY HOẠCH TUYẾN TÍNH HAI BIẾN .... - 11 - 
3.1. Nhận xét ............................................................................................................................ - 11 - 
3.2. Thuật toán đồ thị giải bài toán quy hoạch tuyến tính ........................................................ - 11 - 
4. MỘT SỐ YẾU TỐ HÌNH HỌC TRONG KHÔNG GIAN 
n¡ .......................................... - 14 - 
4.1. Tập hợp lồi ........................................................................................................................ - 14 - 
4.2. Tính chất của tập hợp lồi ................................................................................................... - 15 - 
5. TÍNH CHẤT CỦA BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ......................................... - 15 - 
5.1. Các giả thiết ban đầu ......................................................................................................... - 15 - 
5.2. Các tính chất cơ bản của bài toán quy hoạch tuyến tính ................................................... - 16 - 
6. PHƢƠNG PHÁP ĐƠN HÌNH ............................................................................................. - 25 - 
6.1. Cơ sở lý luận của phƣơng pháp đơn hình .......................................................................... - 25 - 
6.2. Công thức đổi tọa độ và bảng đơn hình ............................................................................ - 30 - 
6.3. Bài toán suy biến ............................................................................................................... - 35 - 
7. PHƢƠNG PHÁP TÌM PHƢƠNG ÁN CỰC BIÊN XUẤT PHÁT ..................................... - 37 - 
7.1. Bài toán giả tạo .................................................................................................................. - 37 - 
7.2. Mối quan hệ về phƣơng án tối ƣu của bài toán giả tạo và bài toán chính tắc tƣơng ứng .. - 39 - 
Chƣơng 2 .................................................................................................................................. - 42 - 
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU ........................................................ - 42 - 
1. KHÁI NIỆM BÀI TOÁN QHTT ĐỐI NGẪU .................................................................... - 42 - 
1.1. Bài toán quy hoạch tuyến tính đối ngẫu không đối xứng .................................................. - 42 - 
1.2. Quy tắc thành lập bài toán đối ngẫu .................................................................................. - 44 - 
LƢỢC ĐỒ TỔNG QUÁT ........................................................................................................ - 45 - 
Dạng 1. ..................................................................................................................................... - 45 - 
Dạng 2. ..................................................................................................................................... - 45 - 
1.3. Bài toán quy hoạch tuyến tính đối ngẫu đối xứng ............................................................. - 46 - 
2. CÁC ĐỊNH LÝ ĐỐI NGẪU ................................................................................................ - 48 - 
3. PHƢƠNG PHÁP ĐƠN HÌNH ĐỐI NGẪU ........................................................................ - 52 - 
3.1. Nội dung phƣơng pháp ...................................................................................................... - 52 - 
3.2. Thuật toán đơn hình đối ngẫu ............................................................................................ - 53 - 
Chƣơng 3 .................................................................................................................................. - 56 - 
BÀI TOÁN VẬN TẢI .............................................................................................................. - 56 - 
1. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BÀI TOÁN VẬN TẢI ................................... - 56 - 
1.1. Nội dung kinh tế và các dạng toán học của bài toán vận tải ............................................. - 56 - 
1.2. Mô hình bảng của bài toán vận tải .................................................................................... - 60 - 
1.3. Tính chất của bài toán vận tải cân bằng thu phát .............................................................. - 62 - 
2. THUẬT TOÁN THẾ VỊ GIẢI BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT ............. - 64 - 
2.1. Phƣơng pháp tìm phƣơng án cực biên xuất phát ............................................................... - 64 - 
2.2. Tiêu chuẩn tối ƣu cho một phƣơng án của bài toán vận tải cân bằng thu phát ................. - 68 - 
2.3. Phƣơng pháp cải tiến phƣơng án ....................................................................................... - 70 - 
 4. BÀI TOÁN PHÂN PHỐI ..................................................................................................... - 88 - 
4.1. Định nghĩa. ........................................................................................................................ - 88 - 
4.2. Phƣơng pháp giải ............................................................................................................... - 88 - 
5. BÀI TOÁN Ô CẤM ............................................................................................................. - 93 - 
CHƢƠNG 4. MỘT SỐ BÀI TOÁN ỨNG DỤNG BÀI ......................................................... - 97 - 
TOÁN QUY HOẠCH TUYẾN TÍNH ..................................................................................... - 97 - 
I. BÀI TOÁN SẢN XUẤT ĐỒNG BỘ ................................................................................... - 97 - 
1. CÁC KHÁI NIỆM VÀ TÍNH CHẤT CỦA BÀI TOÁN SẢN XUẤT ĐỒNG BỘ ............. - 97 - 
1.1. Nội dung kinh tế và mô hình toán học của bài toán sản xuất đồng bộ .............................. - 97 - 
1.2. Tính chất của bài toán sản xuất đồng bộ ......................................................................... - 101 - 
2. PHƢƠNG PHÁP NHÂN TỬ GIẢI BÀI TOÁN SẢN XUẤT ĐỒNG BỘ ....................... - 105 - 
2.1. Phƣơng pháp tìm phƣơng án cực biên suy rộng ban đầu ................................................ - 105 - 
2.2. Xây dựng hệ thống số kiểm tra và tiêu chuẩn tối ƣu ....................................................... - 108 - 
2.3. Điều chỉnh phƣơng án ..................................................................................................... - 109 - 
2.4. Thuật toán nhân tử giải bài toán sản xuất đồng bộ .......................................................... - 111 - 
II. BÀI TOÁN TRÒ CHƠI MA TRẬN ................................................................................. - 115 - 
1. MỘT SỐ KHÁI NIỆM MỞ ĐẦU...................................................................................... - 115 - 
1.1. Ví dụ về trò chơi ma trận ................................................................................................. - 115 - 
1.2. Bài toán trò chơi ma trận ................................................................................................. - 115 - 
1.3. Hàm thu hoạch của P ....................................................................................................... - 117 - 
2. ĐIỂM YÊN NGỰA VÀ CHIẾN LƢỢC TỐI ƢU ............................................................. - 118 - 
2.1. Điểm yên ngựa ................................................................................................................ - 118 - 
2.2. Chiến lƣợc tối ƣu ............................................................................................................. - 119 - 
2.3. Trò chơi đối xứng ............................................................................................................ - 120 - 
3. PHƢƠNG PHÁP TÌM CHIẾN LƢỢC TỐI ƢU CHO BÀI TOÁN TRÒ CHƠI MA TRẬN ..... - 
121 - 
3.1. Đƣa trò chơi ma trận về bài toán quy hoạch tuyến tính .................................................. - 121 - 
3.2. Phƣơng pháp tìm chiến lƣợc tối ƣu cho bài toán trò chơi ma trận .................................. - 123 - 
TÀI LIỆU THAM KHẢO ...................................................................................................... - 126 - 
- 1 - 
LỜI NÓI ĐẦU 
Toán học và kinh tế là hai lĩnh vực có mối quan hệ gắn bó với nhau. Kinh tế 
là nguồn cảm hứng cho toán học thực hiện khả năng tiềm năng của mình, còn toán 
học là công cụ giúp cho việc phân tích, giải quyết các vấn đề kinh tế một cách chặt 
chẽ, hợp lý và hiệu quả. Toán kinh tế là việc nghiên cứu để mô tả các vấn đề kinh 
tế dƣới dạng mô hình toán học thích hợp và từ góc độ toán học sẽ tìm ra lời giải 
cho mô hình đó, từ đó giúp các nhà kinh tế tìm ra các giải pháp tối ƣu cho bài toán 
kinh tế. 
Để đáp ứng nhu cầu giảng dạy và học tập môn Toán kinh tế cho sinh viên hệ 
đại học và cao đẳng, chúng tôi đã biên soạn cuốn giáo trình này. Giáo trình không 
đi sâu vào các vấn đề lý luận và các kỹ thuật toán học phức tạp mà chỉ tập trung 
trình bày những nội dung cơ bản và các thuật toán chính của lý thuyết tối ƣu tuyến 
tính. Nhằm giúp sinh viên rèn luyện kỹ năng trong giáo trình có đầy đủ các ví dụ 
cụ thể mô tả từng tình huống, hƣớng dẫn tỉ mỉ toàn bộ quá trình giải quyết vấn đề. 
Nội dung giáo trình gồm 4 chƣơng: 
 Chương 1. Bài toán quy hoạch tuyến tính 
 Chương 2. Bài toán quy hoạch tuyến tính đối ngẫu 
 Chương 3. Bài toán vận tải 
 Chương 4. Một số bài toán ứng dụng của bài toán quy hoạch tuyến 
tính 
 Mặc dù có nhiều cố gắng, nhƣng giáo trình này chắc chắn không tránh khỏi 
những thiếu sót. Chúng tôi rất mong đƣợc bạn đọc góp ý để cuốn sách ngày càng 
hoàn thiện. 
 Các tác giả 
- 2 - 
Chƣơng 1: BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 
1. MỘT SỐ VÍ DỤ VỀ BÀI TOÁN QUY HOẠCH TUYẾN TÍNH 
1.1. Bài toán lập kế hoạch sản xuất 
1.1.1. Nội dung bài toán 
Một cơ sở sản xuất có thể sản xuất đƣợc hai loại sản phẩm A và B, từ các 
nguyên liệu I, II, III. Chi phí từng loại nguyên liệu và tiền lãi của một đơn vị sản 
phẩm, cũng nhƣ dự trữ nguyên liệu cho trong Bảng 1.1. 
Bảng 1.1 
Nguyên liệu 
Sản phẩm 
I II III 
Lãi 
(đơn vị tiền) 
A 2 0 1 3 
B 1 1 0 5 
Dự trữ 8 4 3 
Hãy lập bài toán thể hiện kế hoạch sản xuất sao cho có tổng số lãi lớn nhất 
và phù hợp với điều kiện dự trữ nguyên liệu. 
1.1.2. Mô hình toán học của bài toán 
Gọi x1, x2 lần lƣợt là số sản phẩm A và B đƣợc sản xuất. Khi đó: 
Tổng số lãi là: 3x1 + 5x2 
Tổng số nguyên liệu I cần sử dụng là: 2x1 + x2 
Tổng số nguyên liệu II cần sử dụng là: x2 
Tổng số nguyên liệu III cần sử dụng là: x1 
Theo bài ra, ta có mô hình toán học: Tìm X(x1, x2) sao cho 
f(X) = 3x1 + 5x2 max 
- 3 - 
 với điều kiện 
1 2
2
1
j
2x x 8
 x 4
x 3
x 0, j 1,2
. 
1.2. Bài toán phân công lao động 
1.2.1. Nội dung bài toán 
Một phân xƣởng có 4 dây chuyền sản xuất khác nhau có thể sản xuất 3 loại 
sản phẩm. Lƣợng sản phẩm mỗi loại sản xuất ra đƣợc khi sử dụng một dây chuyền 
sản xuất mỗi loại trong một giờ và chi phí sản xuất ở dây chuyền đó sau một giờ 
hoạt động cùng với nhu cầu tối thiểu về các sản phẩm đƣợc cho bởi Bảng 1.2. 
Bảng 1.2 
Sản phẩm (SP) 
Dây chuyền sản xuất Nhu cầu 
tối thiểu I II III IV 
SP 1 2 3 1 1 1600 
SP 2 1 2 3 4 2200 
SP 3 3 1 4 5 2000 
Chi phí (1000đ) 10 5 13 16 
Hãy lập bài toán để bố trí thời gian cho các dây chuyền sản xuất sao cho 
thỏa mãn nhu cầu tối thiểu về các sản phẩm đồng thời tổng chi phí sản xuất thấp 
nhất. 
1.2.2. Mô hình toán học của bài toán 
Gọi xj là thời gian (giờ) áp dụng dây chuyền sản xuất thứ j (j = 4,1 ) khi đó: 
Tổng chi phí sản xuất là: 10x1 + 5x2 + 13x3 + 16x4 (1000đ) 
Tổng lƣợng sản phẩm 1 sản xuất ra là: 2x1 + 3x2 + x3 + x4 
Tổng lƣợng sản phẩm 2 sản xuất ra là: x1 + 2x2 + 3x3 + 4x4 
Tổng lƣợng sản phẩm 3 sản xuất ra là: 3x1 + x2 + 4x3 + 5x4 
Theo bài ra, ta có mô hình toán học: Tìm X(x1, x2, x3, x4) sao cho 
f(X) = 10x1 + 5x2 + 13x3 + 16x4 min 
- 4 - 
 với điều kiện 
1 2 3 4
1 2 3 4
1 2 3 4
j
2x 3x x x 1600
 x 2x 3x 4x 2200
3x x 4x 5x 2000
x 0, j 1,4
. 
1.3. Bài toán vận tải 
1.3.1. Nội dung bài toán 
Một đơn vị vận tải cần vận chuyển xi măng từ 3 kho K1, K2, K3 tới 4 công 
trƣờng xây dựng T1, T2, T3, T4. Cho biết lƣợng xi măng có ở mỗi kho, lƣợng xi 
măng cần ở mỗi công trƣờng và giá cƣớc vận chuyển (ngàn đồng) 1 tấn xi măng từ 
mỗi kho tới mỗi công trƣờng nhƣ Bảng 1.3. 
Bảng 1.3 
Kho xi măng 
Công trƣờng xây dựng 
T1: 130 tấn T2: 160 tấn T3: 120 tấn T4: 140 tấn 
K1: 170 tấn 20 18 22 25 
K2: 200 tấn 15 25 30 15 
K3: 180 tấn 45 30 40 35 
Hãy lập bài toán tìm kế hoạch vận chuyển xi măng từ các kho tới các công 
trƣờng sao cho tổng chi phí vận chuyển là nhỏ nhất và mọi kho đều phát hết lƣợng 
xi măng có, mọi công trƣờng nhận đủ lƣợng xi măng cần? 
1.3.2. Mô hình toán học của bài toán 
Gọi xij là lƣợng xi măng cần vận chuyển từ kho i (i = 1, 2, 3) tới công trƣờng 
j (j = 1, 2, 3, 4). Khi đó: 
Kho K1 phát hết lƣợng xi măng có: x11 + x12 + x13 + x14 = 170 
Kho K2 phát hết lƣợng xi măng có: x21 + x22 + x23 + x24 = 200 
Kho K3 phát hết lƣợng xi măng có: x31 + x32 + x33 + x34 = 180 
Công trƣờng T1 nhận đủ số xi măng cần: x11 + x21 + x31 = 130 
Công trƣờng T2 nhận đủ số xi măng cần: x12 + x22 + x32 = 160 
Công trƣờng T3 nhận đủ số xi măng cần: x13 + x23 + x33 = 120 
- 5 - 
Công trƣờng T4 nhận đủ số xi măng cần: x14 + x24 + x34 = 130 
Lƣợng hàng vận chuyển không âm: xij 0, i = 3,1 , j = 4,1 
Tổng chi phí vận chuyển: f(X) = 20x11 + 18x12 + 22x13 + 25x14 + 15x21 + 
25x22 + 30x23 + 15x24 + 45x31 + 30x32 + 40x33 + 35x34. 
Vậy mô hình toán học của bài toán là: Tìm X = [xij]3x4 sao cho f(X) min 
với X thỏa mãn các điều kiện trên. 
Tổng quát: Gọi m là số kho chứa hàng (điểm p ... iải của bài toán chính tắc hay bài toán giả tạo ta suy ra lời giải của 
bài toán đã cho. 
- 42 - 
Chƣơng 2 
BÀI TOÁN QUY HOẠCH TUYẾN TÍNH ĐỐI NGẪU 
Chƣơng này đề cập tới vấn đề đối ngẫu trong quy hoạch tuyến tính (QHTT). 
Đối ngẫu là một phƣơng pháp mà tƣơng ứng với mỗi bài toán quy hoạch tuyến tính 
đã cho (gọi là bài toán gốc) ta có thể thiết lập một bài toán quy hoạch tuyến tính 
khác (gọi là bài toán đối ngẫu) sao cho từ lời giải của bài toán này ta sẽ thu đƣợc 
thông tin về lời giải của bài toán kia. 
Sau đây, chúng tôi trình bày cách xây dựng bài toán đối ngẫu của một bài 
toán quy hoạch tuyến tính đã cho, nêu các định lý đối ngẫu cơ bản và phƣơng pháp 
đơn hình đối ngẫu. 
1. KHÁI NIỆM BÀI TOÁN QHTT ĐỐI NGẪU 
1.1. Bài toán quy hoạch tuyến tính đối ngẫu không đối xứng 
Cho bài toán QHTT dạng chính tắc (I): 
n
1 1 2 2 n n j j
j 1
f (X) c x c x ... c x c x min (2.1) 
với điều kiện
n
ij j i
j 1
j
a x b , i 1,m (2.2) 
x 0, j 1,n (2.3) 
Định nghĩa 2.1. Bài toán QHTT )I( sau 
m
1 1 2 2 m m i i
i 1
g(X) b y b y ... b y b y max (2.1)' 
 với điều kiện
m
ij i j
i 1
i
 a y c , j 1,n (2.2) '
y , i 1,mR
đƣợc gọi là bài toán QHTT đối ngẫu của bài toán gốc (I). 
Cặp bài toán (I) và bài toán )I( đƣợc gọi là cặp bài toán QHTT đối ngẫu 
không đối xứng. 
- 43 - 
Nhận xét: Phân tích cấu trúc của hai bài toán, ta có thể rút ra những nhận xét, đồng 
thời là những nguyên tắc thành lập bài toán đối ngẫu: 
(i) Nếu bài toán gốc tìm Min thì bài toán đối ngẫu tìm Max và hệ ràng buộc 
của bài toán đối ngẫu có dạng “ ”. 
 (ii) Số ràng buộc (không kể ràng buộc về dấu) trong bài toán này bằng số 
biến số trong bài toán kia, từ đó ta thấy tƣơng ứng với mỗi ràng buộc của bài toán 
này là một biến số của bài toán kia. 
(iii) Hệ số trong hàm mục tiêu của bài toán này là vế phải của hệ ràng buộc 
trong bài toán kia. 
(iv) Ma trận điều kiện trong hai bài toán là chuyển vị của nhau. 
(v) Các biến số trong bài toán đối ngẫu không có ràng buộc về dấu. 
Định nghĩa 2.2. Các cặp bất phƣơng trình sau 
m
j ij i j
i 1
x 0 và a y c , j 1,n . 
n
ij j i
j 1
a x b và yi R, m1,i . 
đƣợc gọi là các cặp điều kiện đối ngẫu. 
Ví dụ 2.1: Cho bài toán QHTT 
f(X) = 13x1 – 3x2 – 4x3 + 19x4 min 
 với điều kiện 
1 2 3 4
1 2 3 4
1 2 3 4
j
 2x x x 3x 44
x 2x 3x x 23
 3x x x 6x 96
x 0, j 1,4
Viết bài toán đối ngẫu cho bài toán này và chỉ ra các cặp điều kiện đối ngẫu. 
Giải: 
Do bài toán gốc tìm Min nên bài toán đối ngẫu tìm Max và bài toán gốc có 3 ràng 
buộc (không kể ràng buộc về dấu) nên bài toán đối ngẫu có số ẩn là 3. Hệ số hàm 
mục tiêu của bài toán đối ngẫu tƣơng ứng là vế phải hệ ràng buộc của bài toán 
gốc. 
- 44 - 
Do đó g(Y) = 44y1 + 23y2 + 96y3 max 
Các cặp điều kiện đối ngẫu: 
1 2 3 4 1
1 2 3 4 2
1 2 3 4 3
1 1 2 3
2 1 2 3
 2x x x 3x 44 và y
x 2x 3x x 23 và y
 3x x x 6x 96 và y
x 0 và 2y y 3y 13
x 0 và y 2y 3y
R
R
R
3 1 2 3
4 1 2 3
3
x 0 và y 3y 3y 4
x 0 và 3y y 6y 19
Ta có bài toán đối ngẫu: 
 g(Y) = 44y1 + 23y2 + 96y3 max 
với điều kiện
19
43
32
13
,
321
321
321
321
321
6yy 3y
3yyy
3yyy 
3yy 2y
yy,y R
Chú ý: Nếu bài toán gốc (I) đƣợc viết dƣới dạng ma trận 
 f(X) = CX min 
với điều kiện 
OX
BAX
thì bài toán đối ngẫu )I( có dạng: 
g(Y) = YB max 
với điều kiện YA C, 
trong đó O là ma trận không cấp n 1, Y = (y1 y2 ... ym) là ma trận hàng cấp 1 m. 
1.2. Quy tắc thành lập bài toán đối ngẫu 
Đối với bài toán bất kỳ để xác định bài toán đối ngẫu, trƣớc hết ta đƣa về bài 
toán dạng chính tắc, sau đó xây dựng bài toán đối ngẫu của bài toán này và gọi nó 
là bài toán đối ngẫu của bài toán đã cho. Việc làm trên khá phức tạp do đó chúng ta 
- 45 - 
có thể sử dụng các quy tắc nêu trong lƣợc đồ dƣới đây để trực tiếp viết bài toán đối 
ngẫu mà không cần phải thực hiện bƣớc biến đổi về dạng chính tắc. 
LƢỢC ĐỒ TỔNG QUÁT 
Dạng 1. 
Bài toán gốc: 
n
j j
j 1
f (X) c x min Bài toán đối ngẫu: 
m
i i
i 1
g(Y) b y max 
* Nếu xj 0 thì 
m
ij i j
i 1
a y c . 
* Nếu xj 0 thì 
m
ij i j
i 1
a y c . 
* Nếu xj không ràng buộc về dấu thì 
m
ij i j
i 1
a y c . 
* Nếu 
n
ij j i
j 1
a x b thì yi không ràng buộc về dấu. 
* Nếu 
n
ij j i
j 1
a x b thì yi 0. 
* Nếu 
n
ij j i
j 1
a x b thì yi 0. 
Dạng 2. 
Bài toán gốc: 
n
j j
j 1
f (X) c x max Bài toán đối ngẫu: 
m
i i
i 1
g(Y) b y min 
* Nếu xj 0 thì 
m
ij i j
i 1
a y c . 
* Nếu xj 0 thì 
m
ij i j
i 1
a y c . 
* Nếu xj không ràng buộc về dấu thì 
m
ij i j
i 1
a y c . 
* Nếu 
n
ij j i
j 1
a x b thì yi không ràng buộc về dấu. 
* Nếu 
n
ij j i
j 1
a x b thì yi 0. 
* Nếu 
n
ij j i
j 1
a x b thì yi 0. 
- 46 - 
Chú ý: Do tính đối xứng của cặp bài toán đối ngẫu nên khái niệm bài toán gốc và 
bài toán đối ngẫu chỉ mang tính tƣơng đối, nghĩa là nếu bài toán này là bài toán 
gốc thì bài toán kia là bài toán đối ngẫu và ngƣợc lại. 
Ví dụ 2.2: Viết bài toán đối ngẫu của bài toán sau: 
f(X) = - 4x1 + x2 + 5x3 + 3x5 min 
với điều kiện 
1 2 3 4 5
1 2 3 4 5
2 3 4 5
1 2 4 5
1 3 5
 3x 6x x 2x 4x 15
2x 3x 4x 5x x 8
 6x 3x 8x 4x 9
 3x 2x 3x x 24
x 0, x 0, x 0.
Giải: Bài toán đối ngẫu có dạng 
g(Y) = - 15y1 + 8y2 + 9y3 + 24y4 max 
với điều kiện 
1 2 4
1 2 3 4
1 2 3
1 2 3 4
 3y 2y 3y 4
6y 3y 6y 2y 1
 y 4y 3y 5
 2y 5y 8y 3y 0
1 2 3 4
1
2
4
4y y 4y y 3
 y 0
 y 0
 y 0
1.3. Bài toán quy hoạch tuyến tính đối ngẫu đối xứng 
Cho bài toán quy hoạch tuyến tính dạng chuẩn tắc (II) 
n
j j
j 1
f (X) c x min (2.4) 
 với điều kiện 
n
ij j i
j 1
j
a x b , i 1,m (2.5)
x 0, j 1,n (2.6)
Khi đó bài toán đối ngẫu của bài toán (II) là bài toán )II( 
- 47 - 
m
i i
i 1
g(Y) b y max (2.4)’ 
 với điều kiện 
m
ij i j
i 1
j
a y c , j 1,n (2.5)'
y 0, i 1,m (2.6)'
Định nghĩa 2.3. Cặp bài toán (II) và bài toán )II( đƣợc gọi là cặp bài toán đối 
ngẫu đối xứng. 
Dùng các ký hiệu ma trận ta có thể viết cặp bài toán QHTT đối ngẫu đối xứng trên 
nhƣ sau: 
 Bài toán gốc 
 min f (X) CX 
Với điều kiện 
n 1
AX B
X O
 Bài toán đối ngẫu 
 max g(Y) YB 
Với điều kiện 
1 m
YA C
Y O
Chú ý: Cặp bài toán QHTT đối ngẫu đối xứng trên có m + n cặp điều kiện đối 
ngẫu. 
Ví dụ 2.3: Tìm bài toán đối ngẫu của bài toán 
1 2 3f (X) 2x x x min 
 với điều kiện 
1 2 3
1 2 3
1 2 3
x 2x x 2
2x x 2x 5
x ,x ,x 0
Giải: Bài toán đối ngẫu là 
1 2g(Y) 2y 5y max 
 với điều kiện 
1 2
1 2
1 2
1 2
y 2y 2
2y y 1
y 2y 1
y ,y 0
- 48 - 
2. CÁC ĐỊNH LÝ ĐỐI NGẪU 
Ta có các định lý sau đây phản ánh mối quan hệ giữa bài toán gốc và bài 
toán đối ngẫu. Các chứng minh đƣợc thực hiện cho cặp bài toán đối ngẫu không 
đối xứng. Sự đúng đắn của các kết luận đối với cặp bài toán đối ngẫu tùy ý đƣợc 
suy ra từ nhận xét mọi cặp bài toán đối ngẫu có thể đƣa đƣợc về dạng cặp bài toán 
đối ngẫu không đối xứng. 
Xét cặp bài toán QHTT đối ngẫu không đối xứng 
Bài toán gốc (I) Bài toán đối ngẫu )I( 
 f (X) CX min 
 Với điều kiện 
n 1
AX B
X O
 g(Y) YB max 
 với điều kiện YA C 
Định lý 2.1. Giả sử X là phương án tùy ý của bài toán gốc (I), Y là phương án tùy 
ý của bài toán đối ngẫu )I( . Khi đó ta luôn có f(X) g(Y). 
Chứng minh: Giả sử X là phƣơng án tùy ý của bài toán (I), Y là phƣơng án tùy ý 
của bài toán )I( . 
f(X) = CX = 
n
j j
j 1
c x 
n m m n
ij i j ij j i
j 1 i 1 i 1 j 1
a y x a x y = 
m
i i
i 1
b y = YB = g(Y) 
Vậy f(X) g(Y). ■ 
Định lý 2.2. Nếu X* là phương án của bài toán (I), Y* là phương án của bài toán 
)I( thỏa mãn f(X*) = g(Y*) thì X* là phương án tối ưu của bài toán (I) và Y* là 
phương án tối ưu của bài toán đối ngẫu )I( . 
Chứng minh: Giả sử X là phƣơng án bất kỳ của bài toán (I), theo định lý 2.1 
chƣơng 2, ta có 
 f(X) g(Y*) = f(X*), X 
Suy ra min{f(X)} = f(X*). Do đó X* là phƣơng án tối ƣu của bài toán (I). 
Tƣơng tự, lấy Y là phƣơng án bất kỳ của bài toán )I( , ta có 
- 49 - 
 g(Y) f(X*) = g(Y*), Y 
Suy ra max{g(Y)} = g(Y*). Do đó Y* là phƣơng án tối ƣu của bài toán )I( . 
■ 
Hệ quả 2.1. Cặp bài toán đối ngẫu (I) và )I( có phương án tối ưu khi và chỉ khi 
chúng có phương án. 
Chứng minh: Điều kiện cần: Hiển nhiên. 
Điều kiện đủ: Giả sử X0, Y0 là cặp phƣơng án của bài toán (I), )I( . Để chứng minh 
bài toán (I) và )I( có phƣơng án tối ƣu, ta chứng minh hàm mục tiêu của chúng bị 
chặn. 
Thật vậy, lấy X là phƣơng án bất kỳ của bài toán (I), theo định lý 2.1 chƣơng 
2, ta có: 
 f(X) g(Y0), X 
Suy ra hàm mục tiêu f(X) bị chặn dƣới trong tập phƣơng án của bài toán gốc 
(I), theo định lý 1.7 chƣơng 1 thì bài toán gốc (I) phải có phƣơng án tối ƣu. 
Vẫn theo định lý 2.1 chƣơng 2, ta có 
g(Y) f(X0), Y. 
 Suy ra g(Y) bị chặn trên trong tập phƣơng án của bài toán )I( , theo định lý 
1.7 chƣơng 1, thì bài toán )I( phải có phƣơng án tối ƣu.■ 
Hệ quả 2.2. Nếu một trong hai bài toán (I) hoặc )I( có tập phương án khác 
nhưng không có phương án tối ưu thì bài toán kia có tập phương án là . 
Chứng minh: (Sinh viên tự chứng minh xem như bài tập) 
Định lý 2.3. (Định lý đối ngẫu thứ nhất) 
Nếu một trong hai bài toán của cặp bài toán đối ngẫu có phương án tối ưu 
thì bài toán kia cũng có phương án tối ưu, đồng thời 
min{f(X)} = max{g(Y)} 
Ta thừa nhận định lý vừa nêu. 
- 50 - 
Định lý 2.4. (Định lý lệch – bù hay định lý đối ngẫu thứ hai) 
 Cặp phương án X*, Y* tương ứng của cặp bài toán đối ngẫu là tối ưu khi và 
chỉ khi trong từng cặp điều kiện đối ngẫu, nếu điều kiện này thỏa mãn lỏng thì điều 
kiện kia thỏa mãn chặt. 
Áp dụng của các định lý đối ngẫu. 
1. Khảo sát sự tồn tại phương án, phương án tối ưu 
Ví dụ 1: Cho bài toán QHTT 
f(X) = 2x1 – x2 + 3x3 – 2x4 min 
 với điều kiện 
1 2
3 4
j
x x 15
 x x 8
x 0, j 1,4
Hãy viết bài toán đối ngẫu và chứng tỏ nó có phƣơng án tối ƣu? 
Giải: Bài toán đối ngẫu 
g(Y) = 15y1 + 8y2 max 
 với điều kiện 
1
1
2
2
y 2
y 1
 y 3
 y 2
Dễ dàng thấy rằng X(15, 8) và Y(1, 2) là các phƣơng án của cặp bài toán đối 
ngẫu. Theo hệ quả 1, suy ra bài toán có phƣơng án tối ƣu. 
Mặt khác, do hạng của hệ ràng buộc của bài toán đối ngẫu bằng 2 do đó nó 
có phƣơng án cực biên tối ƣu. 
2. Kiểm tra một phương án có tối ưu hay không. 
▪ Nếu biết cặp phƣơng án X*, Y* thì chỉ cần kiểm tra điều kiện f(X*) = 
f(Y*) 
▪ Nếu chỉ biết phƣơng án X* thì sử dụng định lý lệch bù tìm phƣơng án Y* 
của bài toán đối ngẫu. 
Ví dụ 2: Cho bài toán QHTT 
- 51 - 
1 2 3f X 2x 4x x max 
 với điều kiện 
1 2 4
1 2 3
2 4
j
 x 3x x 4
2x x x 3
 x 3x 3
x 0, j 1,4
a) Hãy chứng tỏ Xo(1, 1, 0, 0) là phƣơng án cực biên đồng thời tại = 0 nó 
cũng là phƣơng án tối ƣu. 
b)Tìm phƣơng án tối ƣu của bài toán đối ngẫu. Xác định để bài toán có vô số 
phƣơng án tối ƣu. 
Giải: a) Thử lại ta thấy ngay X0 là phƣơng án của bài toán đã cho. Mặt khác X0 
thỏa mãn chặt 4 ràng buộc độc lập, vậy nó là phƣơng án cực biên. 
Xét bài toán đối ngẫu 
1 2 34y 3y 3y min 
 với điều kiện 
1 2
1 2 3
2
1 3
3
 y 2y 2
3y y y 4
 y 
y 3y 0
 y 0
Áp dụng định lý lệch bù, ở đây x1, x2 > 0 và X0 thỏa mãn lỏng điều kiện thứ 
3 nên ta có hệ phƣơng trình 
1 2
1 2 3
3
 y 2y 2
3y y y 4
 y 0
 Y( 0,
5
2
,
5
6
) 
Thử lại ta thấy Y0 là phƣơng án của bài toán đối ngẫu. Vậy tại = 0, X0 là 
phƣơng án tối ƣu. 
- 52 - 
b) Rõ ràng tại = 0, Y0 cũng là phƣơng án tối ƣu của bài toán đối ngẫu. Không 
những thế, với mọi 
5
2
 thì Y0 cũng là phƣơng án của bài toán đối ngẫu. Do đó 
với mọi 
5
2
 ta có X0 là phƣơng án tối ƣu. 
Với < 
5
2
, Y0 thỏa mãn lỏng ràng buộc thứ 3, y1, y2 > 0, do đó phƣơng án 
tối ƣu X (nếu có) phải thỏa mãn: 
1 2 4
1 2 3
3
 x 3x x 4
2x x x 3
 x 0
Giải ra ta đƣợc X = 4 4 4
5 x 5 2x
, ,0,x
5 5
Để X là phƣơng án thì X phải thỏa mãn các điều kiện còn lại x1, x2, x4 0 và 
x2 – 3x4 3. Từ đó suy ra 
4
1 2
x
5 5
Vậy khi < 
5
2
 thì tập phƣơng án tối ƣu của bài toán gốc là 
X = 4 4 4
5 x 5 2x
, ,0,x
5 5
, với 4
1 2
x
5 5
. 
3. PHƢƠNG PHÁP ĐƠN HÌNH ĐỐI NGẪU 
3.1. Nội dung phƣơng pháp 
 Về thực chất, đây là phƣơng pháp đơn hình áp dụng vào bài toán đối ngẫu, 
nhƣng để tìm lời giải của bài toán gốc. Phƣơng pháp này do Lemke G. E. đề xuất 
năm 1954. 
 Phƣơng pháp đơn hình giải bài toán QHTT bắt đầu từ một phƣơng án cực 
biên xuất phát (nghiệm đúng AX = B và X 0) mà chƣa thỏa mãn tiêu chuẩn tối 
- 53 - 
ƣu. Sau mỗi bƣớc lặp ta tìm đƣợc một phƣơng án cực biên mới tốt hơn phƣơng án 
cũ và quá trình này tiếp tục cho đến khi tìm đƣợc một phƣơng án thỏa mãn tiêu 
chuẩn tối ƣu. 
 Phƣơng pháp đơn hình đối ngẫu, lại xuất phát từ một “giả phương án” 
(nghiệm đúng phƣơng trình AX = B) mà nó thỏa mãn tiêu chuẩn tối ƣu ( j 0) 
nhƣng không thỏa mãn X 0, nghĩa là bảng đơn hình ban đầu không có phần tử 
dƣơng trong dòng ƣớc lƣợng (dòng cuối) nhƣng lại có phần tử âm ở cột phƣơng án 
(vì thế có tên là cột giả phương án). Các bảng đơn hình đƣợc biến đổi sao cho luôn 
đảm bảo điều kiện tối ƣu và quá trình này tiếp diễn cho đến khi nhận đƣợc phƣơng 
án (không còn phần tử âm trong cột Giả phƣơng án). Phƣơng án đó đƣợc gọi là 
phƣơng án tối ƣu. 
3.2. Thuật toán đơn hình đối ngẫu 
Bước 1. Xuất phát từ hệ m vectơ độc lập tuyến tính có ma trận D = [Aj] với 
j J, |J| = m, sao cho mọi j 0, j = n,1 . 
Tìm giả phƣơng án X0 = (X*, 0), trong đó X* = C*D 
-1, với C* = i i Jc ; 
xj = 0, j J. 
 Bước 2. Kiểm tra xi 0, i J? 
 + Nếu có, thì X là phƣơng án tối ƣu. 
 + Nếu không, thì sang bƣớc 3. 
 Bước 3. Tại xi < 0, kiểm tra xij 0, j = n,1 ? 
 + Nếu có, bài toán không có phƣơng án tối ƣu. 
 + Nếu không, sang bƣớc 4. 
 Bước 4. Tồn tại xi < 0, tồn tại xij < 0. 
 Chọn i
x
l xx
i
0
min đƣa Al ra khỏi cơ sở. 
 Bước 5. Tìm phần tử trục xlk từ cách chọn: 
 0 = 
lj
j k
x 0
lj lk
min
x x
 đƣa Ak vào cơ sở mới. 
- 54 - 
 Bước 6. Xây dựng phƣơng án X1 bằng cách biến đổi bảng đơn hình nhƣ 
thƣờng lệ. 
 Gán X0 := X1, rồi trở lại bƣớc 2. 
Chú ý: Trong trƣờng hợp bài toán đối ngẫu suy biến thì có thể o = 0, khi o = 0 ta 
vẫn áp dụng thuật toán bình thƣờng, điều này làm nảy sinh khả năng xuất hiện hiện 
tƣợng xoay vòng. tuy nhiên, giống nhƣ phƣơng pháp đơn hình, trong thực tế tính 
toán ta dễ dàng thoát khỏi hiện tƣợng xoay vòng. 
 Dấu hiệu xuất hiện phƣơng án cực biên suy biến là o đạt tại nhiều chỉ số, 
khi đó các véc tơ ứng với o đều có thể đƣa vào cơ sở, vì vậy ta chọn véc tơ bất kỳ 
một cách ngẫu nhiên trong số chúng đƣa vào cơ sở mà không cần sử dụng quy tắc 
từ vựng. 
Ví dụ 2.6: Giải bài toán sau đây bằng phƣơng pháp đơn hình đối ngẫu 
1 2 3 4 5f (X) x x x x x min 
 với điều kiện 
1 3 4 5
1 4
1 2 4 5
j
2x x x 3x 6
 x x 3
4x x x 2x 5
x 0, j 1,5
Giải: Đƣa thêm ẩn phụ x6 0, ta có bài toán dạng chính tắc 
1 2 3 4 5f (X) x x x x x min 
 với điều kiện 
1 3 4 5
1 4 6
1 2 4 5
j
2x x x 3x 6
x x x 3
4x x x 2x 5
x 0, j 1,6
Nếu chọn cơ sở A3A6A2, ta đƣợc giả phƣơng án 
X0 = (0, 5, 6, 0, 0, -3) 
Ta có bảng đơn hình đối ngẫu: 
 Bảng 2.1 
- 55 - 
Bảng 
số 
Cơ sở 
Ai 
Hệ số 
ci 
Tọa 
độ xio 
1 -1 1 1 1 0 
A1 A2 A3 A4 A5 A6 
I 
A3 1 6 2 0 1 -1 3 0 
 A6 0 -3 -1 0 0 -1 0 1 
A2 -1 5 4 1 0 -1 2 0 
 f(X) = 1 -3 0 0 -1 0 0 
II 
A3 1 9 3 0 1 0 3 -1 
A4 1 3 1 0 0 1 0 -1 
A2 -1 8 5 1 0 0 2 -1 
 f(X) = 4 -2 0 0 0 0 -1 
Tại bảng II, có các phần tử trong cột giả phƣơng án đều không âm nên 
phƣơng án tối ƣu của bài toán là 
X(0, 8, 9, 3, 0) và fmin = 4.