BỘ GIÁO DỤC VÀ ĐÀO TẠO
TRƯỜNG ĐẠI HỌC NÔNG NGHIỆP HÀ NỘI
PGS. TS. NGUYỄN HẢI THANH

VẬN TRÙ HỌC
Giáo trình cho ngành Tin học và Công nghệ thông tin

Hà Nội − 2008


MỤC LỤC
Trang
LỜI NÓI ĐẦU
CHƯƠNG I. MỞ ĐẦU

7
9

1. Giới thiệu về Vận trù học / Khoa học quản lí

9

1.1. Vai trò của Vận trù học

9

1.2. Các bước áp dụng Vận trù học

10

1.3. Quá trình phát triển của Vận trù học

11

2. Các ứng dụng và phương pháp định lượng cơ bản của Vận trù học

12

2.1. Một số ứng dụng

12

2.2. Các phương pháp định lượng

14

2.3. Hệ thông tin quản lí
CHƯƠNG II. MỘT SỐ MÔ HÌNH VÀ PHƯƠNG PHÁP TỐI ƯU

14
16

1. Mô hình quy hoạch tuyến tính

16

1.1. Phát biểu mô hình quy hoạch tuyến tính

16

1.2. Phương pháp đơn hình giải BTQHTT dạng chính tắc


19

1.3. Phương pháp đơn hình hai pha giải BTQHTT
dạng tổng quát

23

1.4. Phương pháp cắt Gomory giải BTQHTT nguyên

29

1.5. Một số ứng dụng của phương pháp đơn hình

33
35

2. Mô hình quy hoạch tuyến tính đa mục tiêu
2.1. Các khái niệm cơ bản

35

2.2. Phương pháp tổng quát giải BTQHTT đa mục tiêu

37

2.3. Phương pháp thoả dụng mờ tương tác giải BTQHTT
đa mục tiêu

39


2.4. Một ứng dụng của mô hình quy hoạch tuyến tính đa mục tiêu

44
45

3. Mô hình tối ưu phi tuyến đơn và đa mục tiêu
3.1. Một số khái niệm cơ bản

45

3.2. Một số phương pháp giải bài toán tối ưu phi tuyến
đơn mục tiêu và ứng dụng

47

3.3. Một số phương pháp giải bài toán tối ưu phi tuyến
đa mục tiêu và ứng dụng

51

Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học



2


BÀI TẬP CHƯƠNG II
CHƯƠNG III. CÁC MÔ HÌNH MẠNG


54
57

1. Mô hình mạng vận tải

57

1.1. Phát biểu bài toán vận tải

57

1.2. Tạo phương án vận tải xuất phát

58

1.3. Phương pháp phân phối giải bài toán vận tải

60

1.4. Phương pháp phân phối cải biên giải bài toán vận tải

62

2. Mô hình mạng PERT

66

2.1. Các khái niệm cơ bản về PERT


66

2.2. Sơ đồ PERT với số liệu ngẫu nhiên

71

2.3. Điều chỉnh dự án khi kế hoạch một số hoạt động bị phá vỡ

73

2.4. Tính thời gian rút gọn tối ưu bằng phương pháp đơn hình

74

2.5. Áp dụng mạng PERT trong phân tích chi phí và
quản lí tài chính dự án

75

3. Một số mô hình mạng khác

77

3.1. Bài toán cây khung tối thiểu

77

3.2. Bài toán tìm đường đi ngắn nhất và quy hoạch động

79


3.3. Mô hình mạng trung chuyển hàng

86

3.4. Bài toán tìm luồng cực đại

88

BÀI TẬP CHƯƠNG III

90

CHƯƠNG IV. GIỚI THIỆU LÍ THUYẾT MÔ PHỎNG VÀ
MÔ HÌNH HÀNG CHỜ

96

1. Mục đích và các công cụ của mô phỏng

96

1.1. Khái niệm về mô phỏng ngẫu nhiên

96

1.2. Các công cụ chủ yếu của mô phỏng

97


1.3. Mô phỏng một số phân phối xác suất

98

2. Áp dụng mô phỏng ngẫu nhiên

101

2.1. Vai trò của phương pháp mô phỏng

101

2.2. Các bước cần tiến hành khi áp dụng mô phỏng

102

2.3. Một số ví dụ về áp dụng phương pháp mô phỏng

102

3. Một số vấn đề về mô hình hàng chờ
3.1. Một số yếu tố cơ bản của hệ thống hàng chờ

112
112


3.2. Các chỉ số cần khảo sát

115


3.3. Tính toán các chỉ số

116

3.4. Áp dụng mô phỏng cho một số hệ thống hàng chờ

118

BÀI TẬP CHƯƠNG IV

127

CHƯƠNG V. PHÂN TÍCH MARKOV VÀ ỨNG DỤNG

131

1. Các khái niệm cơ bản về xích Markov

131

1.1. Một số định nghĩa

131

1.2. Ma trận xác suất chuyển trạng thái và phân phối dừng

132

1.3. Các tính chất và định lí


137
138

2. Một số ứng dụng của phân tích Markov
2.1. Tìm cân bằng thị phần

138

2.2. Chính sách thay thế vật tư thiết bị

138

2.3. Phân tích Markov trong dự báo thất thu cho
các hợp đồng thực hiện trước

140

2.4. Tìm phân phối giới hạn cho một hệ thống kĩ thuật

142

2.5. Một ứng dụng của quá trình sinh−tử cho hệ thống hàngchờ

147
149

3. Mô phỏng xích Markov
3.1. Mô phỏng xích Markov thời gian rời rạc


149

3.2. Mô phỏng xích Markov thời gian liên tục

151

BÀI TẬP CHƯƠNG V

152

CHƯƠNG VI. MỘT SỐ MÔ HÌNH RA QUYẾT ĐỊNH VÀ ỨNG DỤNG

158

1. Ra quyết định trong môi trường bất định

158

1.1. Một số khái niệm cơ bản

158

1.2. Ra quyết định trong môi trường bất định nghiêm ngặt

160

1.3. Ra quyết định trong môi trường rủi ro

163
167


2. Phân tích quyết định Bayes
2.1. Phân tích quyết định Bayes dựa trên xác suất tiên nghiệm

167

2.2. Phân tích quyết định Bayes dựa trên xác suất hậu nghiệm

167

3. Cây quyết định và các bài toán quyết định nhiều giai đoạn

169

3.1. Bài toán quyết định nhiều giai đoạn

169

3.2. Phân tích Bayes sử dụng cây quyết định

171

4. Ra quyết định dựa trên tiêu chuẩn kì vọng thỏa dụng tối đa

174

Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học




4


4.1. Khái niệm hàm thỏa dụng

174

4.2. Tiêu chuẩn kì vọng thỏa dụng tối đa

175

5. Lí thuyết trò chơi và ứng dụng

179

5.1. Một số khái niệm cơ bản của lí thuyết trò chơi

179

5.2. Trò chơi hai người – tổng không với chiến lược thuần nhất

181

5.3. Trò chơi hai người – tổng không với chiến lược hỗn hợp

182

5.4. Lời giải bằng đồ thị cho các trò chơi cỡ 2×N hoặc M×2

186


5.5. Giới thiệu về trò chơi nhiều người

188

BÀI TẬP CHƯƠNG VI

190

CHƯƠNG VII. CÁC MÔ HÌNH QUẢN LÍ HÀNG DỰ TRỮ

193

1. Các khái niệm cơ bản

193

1.1. Các chức năng của việc dự trữ hàng

193

1.2. Hệ thống quản lí hàng dự trữ theo phân loại giá trị ABC

193

1.3. Mô hình quản lí hàng dự trữ tổng quát

194

2. Một số mô hình tất định trong quản lí hàng dự trữ


196

2.1. Mô hình tĩnh Wilson với một mặt hàng

196

2.2. Mô hình tĩnh một mặt hàng với dự trữ đệm

199

2.3. Mô hình tĩnh một mặt hàng với giá chiết khấu

200

2.4. Mô hình tĩnh nhiều mặt hàng với diện tích kho hạn chế

202

2.5. Mô hình động một mặt hàng N chu kì

204

3. Mô hình lập kế hoạch sản xuất N chu kì

207

3.1. Mô hình lập kế hoạch không cho phép nợ hàng

208


3.2. Mô hình lập kế hoạch cho phép nợ hàng

209

4. Một số mô hình xác suất trong quản lí hàng dự trữ

210

4.1. Mô hình xác suất với chế độ báo cáo theo dõi thường xuyên

210

4.2. Mô hình xác suất một chu kì

213

4.3. Mô hình xác suất nhiều chu kì

218

BÀI TẬP CHƯƠNG VII

224

PHẦN PHỤ LỤC

229

TÀI LIỆU THAM KHẢO


234


LỜI NÓI ĐẦU
Vận trù học (Operations Research) được xem là một công cụ định lượng nền tảng
của Khoa học quản lí mà trong đó các phương pháp và kĩ thuật của Toán học và các
công cụ tính toán, lưu trữ và xử lí dữ liệu của Tin học được áp dụng để mô hình hóa,
phân tích và tìm ra lời giải cho các bài toán quyết định, nhằm hỗ trợ bộ máy quản lí
đưa ra các quyết định hợp lí nhất. Trên thế giới việc nghiên cứu và ứng dụng Vận trù
học ngày càng phát triển sâu rộng với nhiều tạp chí chuyên ngành nổi tiếng, môn Vận
trù học được giảng dạy với thời lượng khá lớn bao gồm nhiều nội dung phong phú và
cấp thiết trong nhiều chương trình đào tạo đại học và cao học.
Hiện nay, những môn học trang bị kiến thức cơ sở về kinh tế - quản lí nói chung
và các phương pháp toán - tin ứng dụng trong mô hình hóa và phân tích các bài toán
quyết định nói riêng được đưa vào giảng dạy trong các chương trình đào tạo đại học
trong và ngoài nước. Đối với sinh viên các ngành Tin học, Công nghệ thông tin và
Toán - Tin ứng dụng, khối kiến thức về kinh tế - quản lí là thực sự cần thiết cho các
cương vị làm việc sau này, đặc biệt là cương vị CIO (Chief Information Officer Giám đốc Thông tin). Trong chương trình đào tạo ngành Tin học của Khoa Công
nghệ thông tin, Trường Đại học Nông nghiệp Hà Nội, khối kiến thức trên bao gồm Tối
ưu hóa, Phân tích số liệu, Quản trị học, Các phương pháp toán kinh tế và Vận trù
học. Giáo trình “Vận trù học” với thời lượng 60 tiết được biên soạn lần đầu nhằm
trước hết phục vụ việc dạy và học môn học này cho sinh viên năm thứ ba hoặc năm
thứ tư ngành Tin học. Hi vọng rằng, sau khi ra trường các kĩ sư Tin học sẽ áp dụng và
triển khai các phương pháp vận trù học được một cách rộng rãi với nhiều hiệu quả
thiết thực trong việc xây dựng các hệ thống thông tin quản lí và các phần mềm tính
toán cho các bài toán quản lí, quản trị kinh doanh và kinh tế - công nghệ khác.
Qua giáo trình này, sinh viên cần nắm được một số mô hình vận trù học cơ bản,
biết cách vận dụng các phương pháp và kĩ thuật toán học, các quy trình tính toán
khoa học thích hợp để phân tích và xử lí các mô hình đó. Các chủ đề trong giáo trình

bao gồm: Một số mô hình tối ưu (Optimization Model) như các mô hình quy hoạch
tuyến tính cũng như phi tuyến đơn và đa mục tiêu được đề cập tới trong Chương II.
Chương III giới thiệu về các mô hình mạng (Network Model) với các bài toán về mạng
vận tải, mạng PERT, về quy hoạch động áp dụng trong tìm đường đi ngắn nhất và bài
toán tìm luồng cực đại. Một số ứng dụng của mô hình hàng chờ (Waiting Line Model)
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học



6


và mô phỏng ngẫu nhiên (Stochastic Simulation) được trình bày trong Chương IV.
Chương V giới thiệu các khái niệm cơ bản và ứng dụng của xích Markov (Markov
Chain). Chương VI là các kiến thức cơ sở của lí thuyết quyết định (Decision Theory)
như các quy tắc ra quyết định trong các môi trường bất định và rủi ro, phân tích quyết
định Bayes, cây quyết định và lí thuyết trò chơi. Chương VII trình bày về mô hình
quản lí hàng dự trữ (Inventory Management Model), một vấn đề quan trọng phát sinh
trong quản lí tài nguyên và nguồn lực của các doanh nghiệp. Đây là các chủ đề chủ
yếu nhất của môn Vận trù học mà sinh viên các ngành Tin học, Công nghệ thông tin
và Toán - Tin ứng dụng tại các trường đại học nước ngoài bắt buộc phải học. Phần
bài tập sau từng chương giúp sinh viên củng cố các kiến thức đã học và thực hành áp
dụng các quy trình tính toán khoa học. Những sinh viên khá có thể tự học sâu thêm
bằng cách thu thập tài liệu liên quan qua nhiều nguồn, đặc biệt trên Internet và viết
các phần mềm nhỏ.
Giáo trình cũng có thể được lấy làm tài liệu tham khảo hay dạy và học các
phương pháp toán ứng dụng hay mô hình hóa cho các chuyên ngành như: Quản lí đất
đai, Kinh tế nông nghiệp, Cơ điện và một số chuyên ngành quản lí − kinh tế − công
nghệ khác ở bậc đại học hoặc cao học.
Một số tài liệu người học có thể tham khảo thêm là: Gillet B. E., Introduction to

Operations Research, McGraw Hill, New York, 1990; Taha H. A., Operations
Research, MacMillan Publishing Company, New York, 1989; Levin R. I., Rubin D. S.
and Stinson J. P., Quantitative approaches to management, McGraw Hill, New York,
1986; Phan Quốc Khánh, Vận trù học, Nxb Giáo dục, 2004; Tạp chí Ứng dụng Toán
học, Hội Ứng dụng Toán học Việt Nam, 2003 - 2007.
Trong quá trình biên soạn, tuy tác giả rất cố gắng nhưng có lẽ không tránh khỏi
sai sót. Tác giả xin chân thành cảm ơn các ý kiến đóng góp chỉnh sửa bản thảo bài
giảng môn học của các đồng nghiệp trong Khoa Công nghệ thông tin và sinh viên
ngành Tin học các khóa K47, K48, K49, K50 của Trường Đại học Nông nghiệp Hà
Nội và luôn mong muốn tiếp tục nhận được nhiều góp ý của các nhà khoa học, các
giảng viên và sinh viên để cho giáo trình được hoàn chỉnh hơn, chính xác hơn và sinh
động hơn.
Hà Nội, ngày 10 tháng 10 năm 2008
Tác giả


Chương I
MỞ ĐẦU
1. GIỚI THIỆU VỀ VẬN TRÙ HỌC VÀ KHOA HỌC QUẢN LÍ
1.1. Vai trò của Vận trù học
Vận trù học (Operations Research − OR) là ngành học nghiên cứu về các hoạt động
hợp lí. Việc tổ chức và tiến hành các hoạt động trong nhiều lĩnh vực như kinh tế, xã hội,
quốc phòng, kinh doanh, sản xuất, dịch vụ... đòi hỏi các nhà quản lí phải vận dụng một
cách thích hợp các điều kiện cho phép để trù tính và đưa ra các quyết định.
Đối với bộ máy quản lí các cấp trong các doanh nghiệp, tập đoàn, công ti..., ra quyết
định chính là trách nhiệm then chốt nhất. Quá trình ra quyết định được bắt đầu khi bộ
máy quản lí phát hiện một vấn đề nào đó cần quan tâm tới. Sau đó, cần xác định rõ vấn
đề, phát biểu mục tiêu phải hướng tới và các điều kiện hạn chế (còn gọi là các điều kiện
ràng buộc) cũng như tìm kiếm và đánh giá các phương án. Cuối cùng, phải chọn ra một
phương án hành động được coi là hợp lí hơn cả nhằm giải quyết vấn đề một cách tốt

nhất. Năng lực của bộ máy quản lí được thể hiện ở khả năng phát hiện vấn đề và giải
quyết bài toán quyết định phát sinh.
Một quá trình ra quyết định chính là một quá trình phân tích và tổng hợp thông tin,
có thể có hình thức định tính hay định lượng. Với cách tiếp cận định tính, người quản lí
có thể dựa vào các nhận định chủ quan và kinh nghiệm sẵn có của mình để đưa ra quyết
định. Trong một số trường hợp, cách tiếp cận này có tính “trực giác” nhưng cũng giúp
đưa ra được quyết định đủ tốt. Tuy nhiên, trong rất nhiều trường hợp khác, cách tiếp cận
định lượng sẽ có hiệu quả thật sự trong việc trợ giúp quá trình ra quyết định. Cách tiếp
cận định lượng thường được nhà quản lí thực hiện trong các trường hợp sau:
- Vấn đề đặt ra khá phức tạp bao gồm nhiều biến và do đó cần phải thiết lập mô
hình toán học và sử dụng các công cụ định lượng để tìm ra được phương án giải quyết.
- Các dữ liệu liên quan tới vấn đề cần khảo sát có dạng dữ liệu số và mục tiêu cần
hướng tới có tính chất định lượng, chẳng hạn như cần nâng cao hay hạ thấp một chỉ số
nào đấy.
- Vấn đề đặt ra có tính chất “lặp”, tức là quá trình giải quyết vấn đề có thể bao gồm
một số công đoạn/thủ tục lặp đi lặp lại nhiều lần và vì vậy, tiếp cận định lượng sẽ giúp
người quản lí tiết kiệm thời gian cũng như chi phí.
- Tiếp cận định lượng đã tỏ ra hữu hiệu trong một số tình huống tương tự hoặc khi
người quản lí đã có kinh nghiệm và thành công trong việc giải quyết các vấn đề tương
tự dựa trên tiếp cận định lượng.
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học



8


Có thể nói, Vận trù học là một công cụ định lượng nền tảng của Khoa học quản lí
(Management Science − MS), mà trong đó các phương pháp và kĩ thuật của Toán học
cũng như các công cụ tính toán, lưu trữ và xử lí dữ liệu của Tin học được áp dụng để

mô hình hóa, phân tích và tìm ra lời giải cho các bài toán quyết định, nhằm hỗ trợ bộ
máy quản lí đưa ra đưa ra được quyết định đúng đắn trong điều kiện nguồn lực và tài
nguyên hạn chế. Vì vậy, Vận trù học có một vai trò rất quan trọng trong việc thiết lập
các kế hoạch dài hạn, phát triển các chiến lược chủ đạo cũng như trong việc hỗ trợ các
hoạt động diễn ra hàng ngày trong nhiều lĩnh vực.
Vận trù học là một ngành học vừa có tính khoa học vừa có tính nghệ thuật. Với tư
cách là một khoa học, Vận trù học nghiên cứu và thiết lập các mô hình toán học của các
vấn đề phát sinh từ thực tế cũng như các phương pháp toán học/các thuật giải để giải
quyết mô hình đặt ra. Tuy nhiên, Vận trù học cũng là một nghệ thuật, vì rằng sự thành
công của quá trình ra quyết định phụ thuộc phần lớn vào tính sáng tạo và năng lực của
các nhà phân tích quyết định. Việc thu thập số liệu, thiết lập mô hình và triển khai
phương án tìm được trên thực tế phụ thuộc vào khả năng của chuyên gia hay nhóm
chuyên gia làm Vận trù học trong việc khai thác được thông tin xác thực cũng như xây
dựng được sự giao tiếp tin cậy với bộ máy quản lí.
1.2. Các bước áp dụng Vận trù học
Các bước cơ bản khi áp dụng Vận trù học để thiết lập và giải quyết một mô hình
phát sinh từ thực tế có thể được tóm lược như sau:
− Khảo sát thực tế và phát hiện vấn đề. Tại bước này, cần áp dụng và hoàn thiện
các kĩ năng như: biết lắng nghe, điều tra và khảo sát dữ liệu, biết phân tích các hoạt
động thực tế cũng như phân biệt được các yếu tố quan trọng với các chi tiết thứ yếu.
− Phân tích vấn đề và xây dựng mô hình. Trước hết cần xác định rõ mục tiêu
nghiên cứu và định dạng rõ bài toán phát sinh và phương án giải quyết, từ đó xác định
các yếu tố liên quan mà nhà quản lí có thể kiểm soát được. Nói cách khác, cần xác
định mục tiêu và các điều kiện hạn chế/điều kiện ràng buộc dưới dạng định tính. Sau
đó lựa chọn các biến quyết định và xây dựng mô hình toán học phù hợp, phản ánh
được thực tế khách quan.
− Thu thập số liệu đầu vào và xác định phương pháp giải quyết. Căn cứ mô hình đã
xây dựng được cần thu thập các số liệu đầu vào cần thiết, độ tin cậy của số liệu đầu vào
ảnh hưởng rất đáng kể tới kết quả đầu ra của mô hình. Với mô hình đã xây dựng được
cần tìm ra một phương pháp giải quyết thích hợp dựa trên các phương pháp đã biết hoặc

phát triển phương pháp mới.
− Xác định quy trình giải/thuật giải và chọn lựa phương án hợp lí. Có thể giải mô
hình bằng cách tính toán thông thường nhằm lựa chọn trong các phương án khả thi một
hoặc một số phương án hợp lí hơn cả. Đối với các mô hình lớn, gồm nhiều biến quyết
định và nhiều điều kiện ràng buộc cần lập trình và giải mô hình trên máy tính.


− Kiểm thử mô hình và đánh giá phương án tìm được. Trong trường hợp phương án
tìm được kéo theo các kết quả bất thường về mặt tính toán hoặc không phù hợp với thực
tế, cần kiểm tra và chỉnh sửa lại mô hình, rà soát lại các số liệu đầu vào cũng như các
bước tính toán hay chọn lựa phương án. Sau đó giải lại mô hình để tìm ra phương án
phù hợp hơn.
− Triển khai phương án tìm được trên thực tế. Trong toàn bộ quá trình ra quyết
định, chuyên gia Vận trù học cần quan hệ chặt chẽ với nhà quản lí, giải thích rõ ràng về
tác dụng của mô hình đã đặt ra. Để phương án cuối cùng được triển khai trên thực tế,
cần có báo cáo chi tiết giúp bộ máy quản lí hiểu rõ các hiệu quả thiết thực mà phương
án có thể mang lại. Tuy nhiên, cũng cần nêu rõ các điều kiện đảm bảo cần thiết cũng
như phân tích rõ các yếu tố lợi nhuận/chi phí/rủi ro của phương án.
1.3. Quá trình phát triển của Vận trù học
Những tiến bộ nhân loại đạt được trong vài thế kỉ vừa qua và trong giai đoạn hiện
tại có phần đóng góp quan trọng của các phương pháp khoa học trong việc giải quyết
các vấn đề kinh tế, xã hội. Phương pháp luận khoa học, trước đây thường được biết tới
trong các vấn đề của Khoa học tự nhiên, ngày nay ngày càng được ứng dụng rộng rãi
trong các lĩnh vực của Khoa học quản lí như: lập kế hoạch, tổ chức và kiểm soát các
hoạt động.
Từ hàng vài nghìn năm trước, các hoạt động chế tạo và lắp ráp tàu biển tại Venice
đã được tổ chức một cách khá khoa học. Vào cuối thế kỉ XIX, Frederick W. Taylor đã
giải quyết thành công bài toán quan trọng của Kĩ nghệ công nghiệp (Industrial
Engineering) lúc đó là chế tạo ra các loại xẻng để khai thác các loại quặng khác nhau
với năng suất cao nhất. Cũng vào thời gian này, Henry L. Gantt giải quyết thành công

bài toán lập tiến trình sản xuất (Production Scheduling) khi sản phẩm được chế tạo và
hoàn thiện qua nhiều công đoạn. Dần dần, các nhà quản lí mở rộng các bài toán trong
một số hoạt động kĩ nghệ công nghiệp sang các hoạt động khác của công ti như: khai
thác và sử dụng các nguồn nguyên liệu, thuê và phát triển nhân lực, chính sách tài
chính, bất động sản... Các nhà khoa học tự nhiên, xã hội cũng bắt đầu quan tâm tới các
bài toán quản lí và nhận thức được tầm quan trọng của việc giải quyết vấn đề một cách
hệ thống, tầm quan trọng của các nghiên cứu liên ngành bao gồm khoa học cơ bản, kĩ
nghệ và quản lí. Đó cũng là khởi nguồn của Khoa học quản lí.
Từ đầu thế kỉ XX, Vận trù học/Khoa học quản lí đã được áp dụng khá rộng rãi trong
nhiều lĩnh vực. Tại nước Anh vào năm 1914 - 1915 F. W. Lanchester đã xem xét các
hoạt động quân sự một cách định lượng khi đưa ra phương pháp đánh giá sức mạnh
quân sự thông qua số lượng bộ binh và hỏa lực. Còn tại Mĩ lúc đó, T. A. Edison nghiên
cứu và mô phỏng các hoạt động hợp lí của tàu chiến trong tấn công và tiêu diệt các tàu
ngầm. Vào năm 1917, nhà bác học người Đan Mạch A. K. Erlang cho công bố các công
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học

10




trình về các hoạt động hợp lí trong hệ dịch vụ điện thoại và bưu điện, có tên gọi tổng
quát là hệ thống hàng chờ (Waiting Line System). Năm 1915, Ford W. Harris công bố về
cách xác định dung lượng lô hàng tối ưu trong bài toán quản lí hàng dự trữ (Inventory
Management). Sau đó một loạt công trình được các tác giả khác tiếp tục công bố về các
mô hình kiểm soát hàng dự trữ. Các ứng dụng của lí thuyết xác suất trong kiểm định
chất lượng (Quality Control) cũng được đề cập tới trong các bài báo của Walter
Shewhart. Mô hình quy hoạch tuyến tính (Linear Programming) được giáo sư Đại học
Havard Wassily Leontieff áp dụng vào những năm 1930 để mô tả và phân tích toàn bộ
nền kinh tế Mĩ. Các ứng dụng của Vận trù học trong kinh doanh lần đầu tiên được

Horace C. Levinson phát triển trong giai đoạn 1920 - 1930 để nghiên cứu các mối quan
hệ giữa doanh thu và quảng cáo, giữa thu nhập và địa điểm sinh sống của người tiêu
dùng và các mặt hàng mua sắm. Sau năm 1945, Vận trù học tiếp tục được ứng dụng
ngày càng rộng rãi trong nhiều lĩnh vực. Rất nhiều bài toán quản lí được giải quyết bằng
phương pháp đơn hình (Simplex Method) do George B. Danzig đưa ra vào năm 1947.
Các mô hình mạng (Network Model) được phát triển lần đầu vào năm 1958 với sự trợ
giúp của công ti tư vấn Booz, Allen và Hamilton.
Tại Việt Nam, từ nhiều năm trước đây các hoạt động giảng dạy và nghiên cứu về
Vận trù học đã được tiến hành tại một số cơ sở đào tạo và nghiên cứu như Đại học Tổng
hợp Hà Nội, Viện Toán học, Viện Điều khiển kinh tế… Vận trù học được đưa vào ứng
dụng thành công trong một số lĩnh vực như giao thông, thủy lợi, sản xuất nông nghiệp và
công nghiệp, dịch vụ, quốc phòng, với các đóng góp của các giáo sư Hoàng Tụy, Trần Vũ
Thiệu, Nguyễn Đình Ngọc, Nguyễn Quý Hỷ. Được thành lập vào năm 2002, Tạp chí Ứng
dụng Toán học đã và đang công bố nhiều bài báo trong lĩnh vực Vận trù học.
Ngày nay, tại nhiều nước trên thế giới, các Hội Vận trù học và các Viện Khoa học
quản lí được thành lập, với nhiều tạp chí chuyên khảo nổi tiếng. Có thể giới thiệu ở đây
một số tạp chí quốc tế như: Operations Research, Management Science, A.I.E.E.
Transactions, C.O.R.S. Journal, Industrial Engineering, European Journal of
Operational Research, Asia-Pacific Journal of Operational Research, Decision
Sciences, Decision Support Systems.
2. CÁC ỨNG DỤNG VÀ PHƯƠNG PHÁP ĐỊNH LƯỢNG CƠ BẢN CỦA
VẬN TRÙ HỌC
2.1. Một số ứng dụng
Các ứng dụng cơ bản của Vận trù học có thể được phân loại theo các lĩnh vực
sau đây:
- Lập kế hoạch sử dụng các phương tiện, bao gồm: xác định quy mô và địa điểm
xây dựng xí nghiệp, lập kế hoạch cho bệnh viện, các hệ thống cung ứng dịch vụ quốc tế,
xác định số lượng phương tiện cần thiết, sắp xếp phương án vận chuyển, bố trí kho
hàng, phân công nhiệm vụ.



- Chế tạo, sản xuất: kiểm soát hàng dự trữ, cân bằng sản xuất và tiếp thị, lập tiến
trình sản xuất, đảm bảo ổn định sản xuất.
- Xây dựng: phân phối các dự trữ tài nguyên cho các dự án, xác định số thành viên
của các đội công tác, duy trì tiến trình công tác, lập tiến trình dự án.
- Đặt hàng, mua nguyên liệu: chuyển giao vật liệu, chính sách mua hàng và đặt lại
hàng tối ưu.
- Tiếp thị: xác định chi phí tiếp thị, thời điểm giới thiệu sản phẩm mới, chọn lựa
danh mục sản phẩm hỗn hợp.
- Tài chính: chính sách cổ tức, phân tích đầu tư và chọn lựa danh mục đầu tư.
- Kế toán: lập kế hoạch luồng tiền, chính sách tín dụng, lập kế hoạch cho chiến lược
kế toán nợ.
- Chính sách nhân lực: tuyển dụng nhân viên, lập kế hoạch nhân lực, lập tiến trình
bồi dưỡng cán bộ, cân bằng các kĩ năng.
- Nghiên cứu và phát triển: Kiểm soát các dự án nghiên cứu và phát triển, lập kế
hoạch phát triển sản phẩm mới.
Chúng ta hãy xem xét một cách chi tiết hơn vấn đề trên qua một vài ứng dụng điển
hình của Vận trù học/Khoa học quản lí như sau:
- Bài toán lập kế hoạch nhân lực. Một công ti cần thường xuyên duy trì 1000 nhân
viên, trong số đó có 70% nhân viên “cũ” (đã làm việc tại công ti từ một năm trở lên) và
30% nhân viên “mới” (làm việc dưới một năm). Theo các kết quả thống kê có được,
trong số nhân viên mới thông thường 50% bỏ việc trong vòng 4 tháng đầu, 20% bỏ việc
trong vòng 4 tháng tiếp theo, 10% bỏ việc trong 4 tháng kế tiếp và chỉ có 20 % không
bỏ việc trong năm đầu tiên vào làm việc. Trong số nhân viên cũ, thông thường hàng
năm có 30% bỏ việc (tức là khoảng 10% cho mỗi kì 4 tháng). Vậy công ti cần xác định
tỉ lệ tuyển nhân viên mới hàng năm như thế nào để: i) duy trì ổn định được lượng lao
động, ii) giảm lượng lao động hàng năm theo một tỉ lệ định trước, iii) tăng lượng lao
động hàng năm theo một tỉ lệ định trước.
- Bài toán phân công nhiệm vụ. Một nhóm 3 kĩ sư A, B và C được phân công hoàn
thành 3 nhiệm vụ 1, 2 và 3. Cần giao cho mỗi kĩ sư một nhiệm vụ sao cho tổng số ngày

công thực hiện 3 nhiệm vụ trên là thấp nhất, biết rằng kĩ sư A có thể hoàn thành các
nhiệm cụ 1, 2, 3 theo thứ tự trong vòng 2, 6 và 3 ngày, còn số ngày như vậy cho các kĩ
sư B và C là 8,4, 9 và 5, 7, 8. Bằng cách liệt kê các phương án phân công nhiệm vụ (có
tất cả 3! = 6 phương án phân công), có thể tìm được ngay phương án phân công tối ưu
là: phân công cho kĩ sư A nhiệm vụ 3, kĩ sư B nhiệm vụ 2 và kĩ sư C nhiệm vụ 1. Tuy
nhiên, nếu bài toán được mở rộng khi cần phân công 20 nhiệm vụ cho 20 kĩ sư thì
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học

12




phương pháp liệt kê (với tất cả là 20! ≈ 2,433×1018 phương án phân công) tỏ ra rất kém
tác dụng. Như vậy cần phải nghiên cứu một phương pháp khác để giải quyết bài toán
phân công nghiệm vụ tổng quát.
2.2. Các phương pháp định lượng
Các phương pháp định lượng cơ bản thường được sử dụng trong Vận trù học/Khoa
học quản lí bao gồm:
- Các phương pháp tối ưu giải mô hình quy hoạch tuyến tính và phi tuyến, quy
hoạch động và quy hoạch đa mục tiêu.
- Các kĩ thuật/thuật toán chuyên dụng giải các mô hình mạng như bài toán vận tải,
bài toán tìm đường đi ngắn nhất, mô hình mạng PERT, bài toán tìm luồng cực đại.
- Kĩ thuật mô phỏng giải các mô hình hàng chờ/dịch vụ công cộng.
- Phân tích Markov ứng dụng trong kinh doanh và quản lí.
- Các phương pháp chọn lựa quyết định dựa trên Lí thuyết quyết định và Lí thuyết
trò chơi.
- Các mô hình quản lí hàng dự trữ.
Do thời lượng có hạn, một số phương pháp khác của Vận trù học như các phương
pháp dự báo, hệ chuyên gia, khai phá dữ liệu và tri thức ... không được đề cập tới trong

giáo trình này.
2.3. Hệ thông tin quản lí
Các tiêu chuẩn về số liệu. Các phương pháp định lượng hay kĩ thuật tính toán được
đề cập trên đây thường đòi hỏi các số liệu đầu vào phải đảm bảo các tiêu chuẩn sau:
- Chính xác: số liệu phải không có sai sót.
- Chi phí hiệu quả: chi phí thu thập số liệu thấp hơn giá trị chúng có thể mang lại.
- Cập nhật: số liệu phản ánh đúng các điều kiện hiện tại.
- Tin cậy: số liệu phát sinh kết quả không có gì bất thường.
- Dễ sử dụng: số liệu có thể được sử dụng thân thiện mà không phải sửa đổi
gì thêm.
Các tiêu chuẩn trên đây có thể có tính chất “thỏa hiệp”, có nghĩa là nếu một tiêu
chuẩn nào đó trở nên tốt hơn thì cũng dẫn tới một tiêu chuẩn khác xấu đi. Chẳng hạn,
chi phí lấy số liệu thấp thường ảnh hưởng tới tính chính xác và độ tin cậy của số liệu.
Tuy nhiên, năm tiêu chuẩn này luôn là mục tiêu cần “cực đại hóa” khi thu thập số liệu.
Khái niệm hệ thông tin quản lí. Có thể coi hệ thông tin quản lí là một hệ thống các
số liệu/dữ liệu được thu thập, tổ chức, phân tích, xử lí và lưu trữ trên máy tính/mạng
máy tính dưới dạng thông tin hỗ trợ các quyết định quản lí. Để ứng dụng thành công các


phương pháp định lượng của Vận trù học, chúng ta luôn cần thiết lập được một hệ thông
tin quản lí đủ tốt nhằm cung cấp các số liệu cần thiết cho mô hình toán học của vấn đề
cần giải quyết. Rõ ràng rằng, các số liệu thô thu thập được trong bước khảo sát thực tế
và phát hiện vấn đề được biến đổi một cách thích hợp thành thông tin hỗ trợ ra quyết
định. Chẳng hạn, các số liệu thô về hệ số lợi nhuận của một loại sản phẩm được biến đổi
thành hệ số lợi nhuận (trung bình)/đơn vị sản phẩm, là một dạng thông tin hỗ trợ việc
lập kế hoạch sản xuất sản phẩm này.
Máy tính/mạng máy tính có rất nhiều điểm mạnh như: tính chính xác, tính nhất
quán, bộ nhớ lớn, xử lí được nhiều số liệu và phép toán phức tạp, làm việc theo các quy
tắc và chương trình định sẵn. Tuy nhiên, để thiết lập một hệ thông tin quản lí hiệu quả,
cần xác định được các dạng thông tin hỗ trợ cần thiết giúp phát huy tốt nhất các ưu điểm

suy luận sáng tạo và linh hoạt của người ra quyết định. Một hệ thông tin quản lí “nhiều
máy tính quá” thường dẫn đến phương án có tính cơ giới, sự phản ứng thiếu linh hoạt và
quyết định ở phạm vi hẹp. Trái lại, một hệ thông tin quản lí “nhiều tính người quá”
thường dẫn đến sự phản ứng chậm chạp và sự hạn chế trong việc sử dụng số liệu cũng
như khả năng tìm kiếm và đánh giá các phương án thay thế. Đây chính là các vấn đề cần
chú trọng khi các chuyên gia Vận trù học và Công nghệ thông tin cùng nhau xem xét và
xây dựng một hệ thông tin quản lí.
Hệ thông tin quản lí có thể được phân ra ba loại cơ bản: hệ thống cho đầu ra là
các kiểu báo cáo, hệ thống trả lời các truy vấn dạng “what - if” và hệ hỗ trợ ra quyết
định (Decision Support System - DSS). Các hệ hỗ trợ ra quyết định là loại hệ thông
tin quản lí hoàn thiện nhất cho phép tích hợp quá trình ra quyết định tương tác người
- máy tính với các cơ sở dữ liệu và các mô hình định lượng nhằm hỗ trợ trực tiếp
việc đưa ra quyết định.

Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học

14




Chương II
MỘT SỐ MÔ HÌNH VÀ PHƯƠNG PHÁP TỐI ƯU
1. MÔ HÌNH QUY HOẠCH TUYẾN TÍNH
1.1. Phát biểu mô hình quy hoạch tuyến tính
Với mục đích tìm hiểu bước đầu, xét mô hình toán học sau đây, còn gọi là mô hình
quy hoạch tuyến tính hay bài toán quy hoạch tuyến tính (BTQHTT), mà trong đó chúng
ta muốn tối ưu hóa (cực đại hóa hay cực tiểu hoá) hàm mục tiêu:
z = c1x1 + c2x2 + cnxn → Max (Min),
với các điều kiện ràng buộc:

a11x1 + a12x2 +... +a1nxn ≤ b1
a21x1 + a22x2 +... +a2nxn ≤ b2
...
am1x1 + am2x2 +... +amnxn ≤ bm
x1, x2,..., xn ≥ 0 (điều kiện không âm).
Trong trường hợp tổng quát, BTQHTT có thể bao gồm các ràng buộc dạng ≥, ≤
hoặc dạng =, các biến có thể có dấu ≥ 0, ≤ 0 hoặc dấu tùy ý.
Ví dụ 1: z = 8x1 + 6x2 → Max,
với các ràng buộc:
4x1 + 2x2 ≤ 60
2x1 + 4x2 ≤ 48
x1, x2 ≥ 0.
BTQHTT trên đây chính là một bài toán quyết định. Cần tìm các giá trị của các biến
quyết định x1, x2 để các ràng buộc được thoả mãn và hàm mục tiêu đạt giá trị lớn nhất.
Bài toán này có ý nghĩa kinh tế như sau: Giả sử một xí nghiệp sản xuất hai loại sản
phẩm I và II. Để sản xuất ra một đơn vị sản phẩm I cần có 4 đơn vị nguyên liệu loại A
và 2 đơn vị nguyên liệu loại B, các chỉ tiêu đó cho một đơn vị sản phẩm loại II là 2 và 4.
Lượng nguyên liệu dự trữ loại A và B hiện có là 60 và 48 (đơn vị). Bộ máy quản lí cần
đưa ra quyết định nên lựa chọn phương án sản xuất nào để triển khai nhằm đạt lợi nhuận
lớn nhất, biết lợi nhuận trên mỗi đơn vị sản phẩm bán ra là 8 và 6 (đơn vị tiền tệ) cho
các sản phẩm loại I và II.


Phương pháp đồ thị giải BTQHTT hai biến
Phương pháp đồ thị có ý nghĩa minh hoạ và giúp hiểu bản chất vấn đề.
Bước 1: Vẽ miền ràng buộc/miền các phương án khả thi, là tập hợp các phương án
khả thi (các phương án, nếu nói một cách ngắn gọn). Mỗi phương án được thể hiện qua bộ
số (x1, x2) còn gọi là véc tơ nghiệm, thoả mãn tất cả các ràng buộc đã có (xem hình II.1).
x2
30

4x1 + 2x2 = 60

1 A
8

B

2x1 + 4x2 = 48

4

C
O

3

6

15

24

x1

Hình II.1. Phương pháp đồ thị giải bài toán quy hoạch tuyến tính
− Trước hết chúng ta vẽ đồ thị 4x1 + 2x2 = 60 bằng cách xác định hai điểm trên đồ
thị: (0, 30) và (15, 0). Đồ thị trên là một đường thẳng chia mặt phẳng làm hai nửa mặt
phẳng: một phần gồm các điểm (x1, x2) thoả mãn 4x1 + 2x2 ≤ 60; một phần thoả mãn 4x1
+ 2x2 ≥ 60. Ta tìm được nửa mặt phẳng thoả mãn 4x1 + 2x2 ≤ 60.
− Tương tự, có thể vẽ đồ thị 2x1 + 4x2 = 48 bằng cách xác định hai điểm thuộc đồ

thị (0, 12) và (24, 0). Sau đó tìm nửa mặt phẳng thoả mãn 2x1 + 4x2 ≤ 48.
− Lúc này, giao của hai nửa mặt phẳng tìm được trên cho ta tập hợp các điểm (x1, x2)
thoả mãn hai ràng buộc đầu tiên. Tuy nhiên, để thoả mãn điều kiện không âm của các
biến, ta chỉ xét các điểm nằm trong góc phần tư thứ nhất. Vậy miền các phương án khả
thi là miền giới hạn bởi tứ giác OABC.
Bước 2: Trong miền (OABC) ta tìm điểm (x1, x2) sao cho z = 8x1 + 6x2 đạt giá trị
lớn nhất.
Cách 1: Dùng đường đồng mức. Tùy theo giá trị của x1, x2 mà z có mức giá trị khác
nhau.
− Vẽ đường đồng mức: 8x1 + 6x2 = c ở mức c = 24, (ta có thể chọn giá trị c bất kì,
nhưng chọn c = 24 là bội số chung của 6 và 8 để việc tìm toạ độ các điểm cắt hai trục toạ
độ thuận lợi hơn). Chúng ta dễ dàng tìm được hai điểm nằm trên đường đồng mức là (0,
4) và (3, 0). Các điểm nằm trên đường đồng mức này đều cho giá trị hàm mục tiêu z = 24.

Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học

16




− Tương tự, có thể vẽ đường đồng mức thứ hai: 8x1 + 6x2 = 48 đi qua hai điểm (0,
8) và (6, 0). Chúng ta nhận thấy, nếu tịnh tiến song song đường đồng mức lên trên theo
r
hướng của véc tơ pháp tuyến n (8, 6) thì giá trị của hàm mục tiêu z = 8x1 + 6x2 tăng lên.
Vậy giá trị z lớn nhất đạt được khi đường đồng mức đi qua điểm B(12, 6) (tìm được
x1 = 12, x2 = 6 bằng cách giải hệ phương trình 4x1 + 2x2 = 60 và 2x1 + 4x2 = 48).
Kết luận: Trong các phương án khả thi thì phương án tối ưu là (x1, x2) = (12, 6). Tại
phương án này, giá trị hàm mục tiêu là lớn nhất zmax = 8 × 12 + 6 × 6 = 132.
Nhận xét: Phương án tối ưu của bài toán trên (hay các BTQHTT khác, nếu có) luôn

đạt được tại một trong các đỉnh của miền phương án khả thi D (là một tập lồi đa diện
trong trường hợp BTQHTT tổng quát) hay còn gọi là các điểm cực biên (chính xác hơn,
miền điểm cực biên là điểm thuộc miền D, mà không thể tìm được một đoạn thẳng nào
cũng thuộc miền D nhận điểm đó là điểm trong). Nhận xét trên đây là một định lí toán
học đã được chứng minh một cách tổng quát trong các giáo trình môn học Tối ưu hoá.
Nói một cách hình ảnh, muốn đạt được phương án tối ưu cho các BTQHTT thì cần phải
“mạo hiểm” đi xét các điểm cực biên của miền phương án khả thi.
Cách 2: Từ nhận xét trên, để tìm phương án tối ưu ta chỉ cần so sánh giá trị của hàm
mục tiêu tại các điểm cực biên của miền phương án.
Tính giá trị z tại O(0, 0): z(0, 0) = 0; tại A(0, 12): z(0, 12) = 72; tại C(15,0): z(15, 0)
= 120; tại B(12, 6): z(12, 6) = 132 = Max{z(O), z(A), z(B), z(C)}. Vậy zmax = 132.
Nhận xét: Muốn tìm phương án tối ưu của BTQHTT ta xuất phát từ một điểm cực biên
nào đó, tìm cách cải thiện hàm mục tiêu bằng cách đi tới điểm cực biên kề nó. Tiếp tục như
vậy cho tới khi tìm được phương án tối ưu. Trong trường hợp BTQHTT có phương án tối
ưu thì quy trình giải này bao gồm hữu hạn bước (do số điểm cực biên là hữu hạn).
Sơ đồ khối

Bắt đầu

Nhập dữ liệu

Tìm điểm cực biên
xuất phát

Kiểm tra
điều kiện tối ưu

Sai

Đúng

In và lưu trữ kết quả

Dừng

Hình II.2. Sơ đồ khối giải BTQHTT

Tìm
điểm cực biên
kề tốt hơn


Đối với BTQHTT đang xét, quy trình giải được minh hoạ như sau:
O(0, 0)

→

A(0,12)

→

B(12,6) dừng

z=0

→

z = 72

→


z = 132

hoặc: O(0, 0)

→

C(15, 0)

→

B(12, 6) dừng

z=0

→

z = 120

→

z = 132.

Quy trình giải BTQHTT tổng quát có sơ đồ khối giản lược như trình bày trên hình
II.2. Trong sơ đồ trên, vì mục đích trình bày vấn đề đơn giản, chúng ta không đề cập tới
các trường hợp khi BTQHTT có miền phương án là tập rỗng (lúc đó ta không tìm được
phương án xuất phát) cũng như khi ta không tìm được điểm cực biên kề tốt hơn mặc dù
điều kiện tối ưu chưa thoả mãn (lúc đó tập các giá trị hàm mục tiêu z không bị chặn).
1.2. Phương pháp đơn hình giải BTQHTT dạng chính tắc
Đây là phương pháp số giải BTQHTT theo sơ đồ trên. Để giải ví dụ 1 trên đây,
trước hết chúng ta cần đưa BTQHTT về dạng chính tắc bằng cách thêm vào các biến bù

không âm x3 và x4 như sau:
z = 8x1 + 6x2 + 0x3 + 0x4 → Max
với các ràng buộc:
4x1 + 2x2 + x3 = 60
2x1 + 4x2 + x4 = 48
x1, x2, x3, x4 ≥ 0.
Một cách tổng quát, BTQHTT dạng chính tắc là bài toán với các biến không âm,
các ràng buộc với dấu “=”, hệ số vế phải của các ràng buộc không âm. Ngoài ra, mỗi
phương trình bắt buộc phải có một biến đứng độc lập với hệ số +1.
Để giải BTQHTT dạng chính tắc trên đây, cần lập một số bảng đơn hình như trình
bày trong bảng II.1. Trước hết, cần điền số liệu của bài toán đã cho vào bảng đơn hình
bước 1:
− Cột 1 là cột hệ số hàm mục tiêu ứng với các biến cơ sở đã chọn. Phương án xuất
phát có thể chọn là x1 = x2 = 0 (đây chính là điểm gốc toạ độ O(0, 0)), do đó x3 = 60, x4
= 48). Như vậy tại bước này chúng ta chưa bước vào sản xuất, nên trong phương án
chưa có đơn vị sản phẩm loại I hay II được sản xuất ra (chỉ “sản xuất” ra các lượng
nguyên liệu dư thừa, ta cũng nói là các “sản phẩm” loại III và IV) và giá trị hàm mục
tiêu z tạm thời bằng 0. Các biến bù có giá trị lớn hơn 0 có nghĩa là các nguyên liệu loại
tương ứng chưa được sử dụng hết. Ta gọi các biến x3 và x4 là các biến cơ sở vì chúng có
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học

18




giá trị lớn hơn 0 còn x1 và x2 là các biến ngoài cơ sở vì chúng có giá trị bằng 0. Với bài
toán có hai ràng buộc, tại mỗi bước chỉ có hai biến cơ sở.
− Cột 2 là cột các biến cơ sở. Trong cột 3 (cột phương án) cần ghi các giá trị của các
biến cơ sở đã chọn.

− Các cột tiếp theo là các cột hệ số trong các điều kiện ràng buộc tương ứng với các
biến x1, x2, x3 và x4 của bài toán đã cho.
Bảng II.1. Các bảng đơn hình giải BTQHTT
c1 = 8

c2 = 6

c3 = 0

c4 = 0

x1

x2

x3

x4

60
48

4
2

2
4

1
0


0
1

z0 = 0

z1 = 0

z2 = 0

z3 = 0

z4 = 0

Δ1 = 8

Δ2 = 6

Δ3 = 0

Δ4 = 0

15
18

1
0

1/2
3


1/4
−1/2

0
1

z0 = 120

z1 = 8

z2 = 4

z3 = 2

z4 = 0

Δ1 = 0

Δ2 = 2

Δ3 = −2

Δ4 = 0

12
6

1
0


0
1

1/3
−1/6

−1/6
1/3

z0 = 132

8

6

5/3

2/3

0

0

−5/3

−2/3

Hệ số hàm mục
tiêu cj


Biến cơ sở

Phương án

0
0

x3
x4
Hàng z

Hàng Δj = cj − zj
8
0

x1
x4
Hàng z

Hàng Δj = cj − zj
8
6

x1
x2
Hàng z

Hàng Δj = cj − zj


Phân tích bảng đơn hình bước 1
− Hệ số ứng với biến x1 trên hàng thứ nhất là a11 = 4 có nghĩa là tỉ lệ thay thế riêng
giữa một đơn vị sản phẩm loại I và một đơn vị sản phẩm loại III là 4 (giải thích: xét
phương trình/ràng buộc thứ nhất 4x1 + 2x2 + x3 = 60, x1 tăng một đơn vị thì x3 phải
giảm bốn đơn vị nếu giữ nguyên x2). Tương tự ta có thể giải thích được ý nghĩa của các
hệ số aij khác cho trên hàng 1 và hàng 2 trong bảng đơn hình bước 1.
− Chúng ta xét hàng z của bảng đơn hình. Để tính z1, cần áp dụng công thức z1 =
(cột hệ số của hàm mục tiêu) × (cột hệ số của biến x1) = 0×4 + 0×2 = (giá một đơn vị
sản phẩm loại III)×(tỉ lệ thay thế riêng loại I/loại III) + (giá một đơn vị sản phẩm loại
IV) × (tỉ lệ thay thế riêng loại I/loại IV) = tổng chi phí phải bỏ ra khi đưa thêm một đơn
vị sản phẩm loại I vào phương án sản xuất mới = 0. Các giá trị zj, với j = 1, 2, 3, 4, được
tính tương tự và chính là các chi phí khi đưa một thêm một đơn vị sản phẩm loại xj vào
phương án sản xuất mới. Còn z0 là giá trị của hàm mục tiêu đạt được tại phương án đang
xét: z0 = (cột hệ số của hàm mục tiêu)× (cột phương án) = 0×60 + 0×48 = 0.


− Trên hàng Δj cần ghi các giá trị Δj, j = 1, 2, 3, 4, tính theo công thức Δj = cj -zj = lợi
nhuận trên một đơn vị sản phẩm - chi phí trên một đơn vị sản phẩm. Vậy Δj là "lãi
biên"/một đơn vị sản phẩm khi đưa thêm một đơn vị sản phẩm loại j vào phương án sản
xuất mới. Nếu Δj > 0 thì hàm mục tiêu còn tăng được khi ta đưa thêm các đơn vị sản
phẩm loại j vào phương án sản xuất mới. Có thể chứng minh được Δj chính là đạo hàm
riêng ∂z/∂xj của hàm mục tiêu z theo biến xj. Như vậy, x1 tăng lên 1 thì z tăng lên 8 còn
x2 tăng lên 1 thì z tăng lên 6.
Do Δ1 và Δ2 đều dương nên vẫn còn khả năng cải thiện hàm mục tiêu khi chuyển
sang (hay “xoay sang”) một phương án cực biên kề tốt hơn (quay lại nhận xét ở phần
giải bài toán bằng phương pháp đồ thị: điểm cực biên kề của điểm (0, 0) có thể là A(0,
12) hay C(15, 0)).
Thủ tục xoay
Bước 1: Chọn cột xoay là cột có Δj > 0 tức là chọn biến xj làm biến cơ sở mới do xj
tăng kéo theo hàm mục tiêu tăng. Ở đây ta chọn đưa x1 vào (đánh dấu √ ở cột Δ1).

Bước 2: Chọn hàng xoay để xác định đưa biến nào ra khỏi số biến cơ sở (vì tại mỗi
bước số biến cơ sở là không thay đổi). Để chọn hàng xoay, ta thực hiện quy tắc “tỉ số
dương bé nhất" bằng cách lấy cột phương án (60, 48)T chia tương ứng cho cột xoay (4,
2)T để chọn tỉ số bé nhất. Một điều cần chú ý là ta chỉ xét các tỉ số có mẫu số dương.
Vì Min{60/4, 48/2} = 60/4 đạt được tại hàng đầu, nên ta đánh dấu √ vào hàng xoay
là hàng đầu (hàng tương ứng với biến x3). Do đó cần đưa x3 ra khỏi các biến cơ sở.
Bước 3: Chọn phần tử xoay nằm trên giao của hàng xoay và cột xoay.
Bước 4: Xoay sang bảng đơn hình mới, xác định các biến cơ sở mới để điền vào cột
biến cơ sở, đồng thời thay các giá trị trong cột hệ số hàm mục tiêu. Sau đó, tính lại các
phần tử của hàng xoay bằng cách lấy hàng xoay cũ chia cho phần tử xoay để có hàng
mới tương ứng.
Bước 5: Các phần tử còn lại của bảng đơn hình mới được tính theo quy tắc "hình
chữ nhật": (1)mới = (1)cũ - (2)cũ× (4)cũ/(3)cũ, trong đó (3) là đỉnh tương ứng với phần tử
xoay (xem hình II.3).
(2)

(3)

Chẳng hạn: (1)cũ = 4, 2(cũ) = 2
(3)cũ = phần tử xoay = 4, (4)cũ = 2 ⇒ (1)mới
2
= 4 − 2 × = 3.
4
(1)

(4)

Hình II.3. Quy tắc hình chữ nhật
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học


20




Giải thích: Các bước xoay trên đây chỉ là phép biến đổi tương đương hệ phương
trình

4x1 + 2x2 + x3 = 60 (a)
2x1 + 4x2 + x4 = 48 (b)
để có hệ
x1 + (1/2)x2 + (1/4)x3 = 15 (a’)
0x1 + 3x2 − (1/2)x3 + x4 = 18. (b’)
bằng cách lấy phương trình (a) chia cho 4 (phần tử xoay) để có (a’), rồi lấy (b) trừ
bớt
2 × (a)/4 để có (b’). Đây chính là nội dung của bước 4 và bước 5. Còn bước 3 sẽ đảm
bảo rằng giá trị của các biến cơ sở mới không âm (x1 = 15, x4 = 18).
Áp dụng thủ tục xoay cho các phần tử nằm trên hàng 1 và 2 của bảng đơn hình bước
1, sau đó tính các giá trị trên hàng zj và Δj tương tự như khi lập bảng đơn hình bước 1,
chúng ta sẽ nhận được bảng đơn hình bước 2.
Phân tích bảng đơn hình bước 2

Bảng bước 2 có thể được phân tích tương tự như bảng bước 1. Cần chú ý rằng lúc
này ta đang ở vị trí của điểm C(15, 0) vì x1 = 15 còn x2 = 0; giá trị của hàm mục tiêu là
z0 = 120 đã được cải thiện hơn so với bước 1. Ta thấy Δ2 = 2 > 0 nên còn có thể cải
thiện hàm mục tiêu bằng cách chọn biến x2 làm biến cơ sở mới. Thực hiện các bước
xoay sang phương án cực biên kề tốt hơn, chúng ta sẽ có bảng đơn hình bước 3.
Phân tích bảng đơn hình bước 3

Tại bảng đơn hình bước 3 ta thấy điều kiện tối ưu đã được thoả mãn (Δj ≤ 0

∀j=1, 2, 3, 4) nên không còn khả năng cải thiện phương án. Phương án tối ưu đã đạt
được tại x1 = 12, x2 = 6, x3 = 0, x4 = 0, tức là tại điểm cực biên B(12, 6) với giá trị zmax =
132.
Khung thuật toán đơn hình giải BTQHTT dạng chính tắc

Sau đây là khung thuật toán của phương pháp đơn hình được phát biểu cho
BTQHTT cực đại hóa dạng chính tắc.
Bước khởi tạo

- Tìm một phương án cực biên ban đầu.
- Tính Δj = cj - zj, ∀j = 1, n , trong đó n là số biến của bài toán đang xét.
Các bước lặp


Bước 1: Kiểm tra điều kiện tối ưu. Nếu điều kiện tối ưu Δj = cj - zj ≤ 0, ∀j = 1, n đã
được thoả mãn thì in/lưu trữ kết quả của bài toán và chuyển sang bước kết thúc.
Bước 2: Nếu tồn tại một chỉ số j sao cho Δj > 0 thì tiến hành thủ tục xoay gồm năm
bước đã biết, tính lại các Δj, ∀j = 1, n và quay lại bước 1 (Chú ý: Trong trường hợp ta
tìm được cột xoay mà không tìm được hàng xoay thì kết luận hàm mục tiêu không bị
chặn, in/lưu trữ kết quả của bài toán và chuyển sang bước kết thúc).
Bước kết thúc. Dừng.
Chú ý:

- Đối với các BTQHTT cần cực tiểu hóa hàm mục tiêu thì điều kiện tối ưu (hay tiêu
chuẩn dừng) là Δj ≥ 0 ∀j (nếu tồn tại j mà Δj ≤ 0 thì cần tiếp tục cải thiện hàm mục tiêu
bằng cách chọn cột j làm cột xoay...).
- Trong thực tiễn giải các BTQHTT dạng tổng quát có thể xảy ra trường hợp không
tìm được phương án xuất phát. Lúc này có thể kết luận mô hình đã thiết lập có các điều
kiện ràng buộc quá chặt chẽ, cần xem xét nới lỏng các điều kiện này.
- Trong trường hợp ta tìm được cột xoay mà không tìm được hàng xoay thì kết luận

hàm mục tiêu không bị chặn trên (đối với các BTQHTT dạng Max) hoặc không bị chặn
dưới (đối với các BTQHTT dạng Min). Khi đó dừng quá trình giải và kết luận mô hình
quy hoạch tuyến tính đã thiết lập không phù hợp với thực tế.
1.3. Phương pháp đơn hình hai pha giải BTQHTT dạng tổng quát
Đưa BTQHTT về dạng chính tắc
Ví dụ 1: (Trường hợp các ràng buộc đều có dấu ≤)

z = 8x1 + 6x2 → Max
với các ràng buộc:
⎧4x1 + 2x 2 ≤ 60
⎪
⎨2x1 + 4x 2 ≤ 48
⎪ x , x ≥ 0.
⎩ 1 2

Đưa BTQHTT về dạng chính tắc như đã biết bằng cách thêm hai biến bù (slack
variables) x3 và x4. Ta có BTQHTT dạng chính tắc là:
z = 8x1 + 6x2 + 0x3 + 0x4 → Max
⎧4x1 + 2x 2 + x 3 = 60
⎪
⎨2x1 + 4x 2 + x 4 = 48
⎪ x , x , x , x ≥ 0.
⎩ 1 2 3 4
Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học

22





Lúc này, trong hệ hai điều kiện ràng buộc đã có đủ hai biến đứng độc lập trong từng
phương trình với hệ số +1, nên đã có thể tìm được phương án cực biên xuất phát để bắt
đầu quá trình giải bài toán.
Ví dụ 2: (Trường hợp có biến không dương)

z = 8x1 − 6x2 → Max
với các ràng buộc:
⎧4x1 + 2x 2 + x 3 ≤ 60
⎪
⎨2x1 + 4x 2 + x 4 ≤ 48
⎪ x ≥ 0, x ≤ 0, x ≥ 0, x ≥ 0.
2
3
4
⎩ 1

Lúc này muốn giải bài toán bằng phương pháp đơn hình ta phải đổi biến x'2 = −x2.
Ta có BTQHTT với các biến đều không âm.
z = 8x1 + 6x'2 → Max
với các ràng buộc:
⎧4x1 − 2x '2 + x 3 ≤ 60
⎪
⎨2x1 − 4x '2 + x 4 ≤ 48
⎪ x , x ' , x , x ≥ 0.
⎩ 1 2 3 4

Ví dụ 3: (Trường hợp có biến với dấu tuỳ ý)

z = 8x1 + 6x2 → Max
với các ràng buộc:

⎧4x1 + 2x 2 ≤ 60
⎪
⎨2x1 + 4x 2 ≤ 48
⎪ x ≥ 0, x . có dấu tuỳ ý.
2
⎩ 1

Lúc này ta viết biến x2 dưới dạng x2 = x'2 − x''2 với
⎧ x '2 = max[0, x 2 ]
thì đảm bảo
⎨
⎩ x ''2 = max[0, − x 2 ]

⎧ x '2 ≥ 0
⎨
⎩ x ''2 ≥ 0.

Các ràng buộc sẽ là
⎧4x1 + 2x '2 − 2x ''2 + x 3 = 60
⎪
⎨2x1 + 4x '2 − 4x '2 + x 4 = 48
⎪ x , x ' , x '' , x , x ≥ 0.
⎩ 1 2 2 3 4

Bài toán với hàm mục tiêu là: z = 8x1 + 6x'2 − 6x''2 + 0x3 + 0x4 và các điều kiện ràng
buộc trên là BTQHTT dạng chính tắc.
Ví dụ 4: (Trường hợp có điều kiện ràng buộc với dấu ≥ hoặc dấu =)


z = 8x1 + 6x2 → Max

với các ràng buộc:
⎧4x1 + 2x 2 ≤ 60
⎪
(a) ⎨2x1 + 4x 2 ≥ 48
⎪ x ≥ 0, x ≥ 0.
2
⎩ 1

Ta thêm các biến bù x3 (slack variable) mang dấu “+”, x4 (surplus variable) mang
dấu “−” để có hệ điều kiện ràng buộc sau (lúc này hai ràng buộc đều có dấu =):
⎧4x1 + 2x 2 + x 3 = 60
⎪
(b) ⎨2x1 + 4x 2 − x 4 = 48
⎪ x , x , x , x ≥ 0.
⎩ 1 2 3 4

Phải thêm biến giả x5 (x5 gọi là lượng vi phạm của phương trình thứ hai) để được hệ
điều kiện ràng buộc
⎧4 x1 + 2 x2 + x3 = 60
⎪
(c) ⎨2 x1 + 4 x2 − x4 + x5 = 48
⎪ x , x , x , x , x ≥ 0.
⎩ 1 2 3 4 5

Lúc này, đã có đủ hai biến đứng độc lập trong từng phương trình với hệ số +1, nên
đã có thể tìm được phương án cực biên xuất phát để bắt đầu quá trình giải bài toán bằng
phương pháp đơn hình với hàm mục tiêu là z = 8x1 + 6x2 + 0x3 + 0x4 − Mx5 → Max,
trong đó M ≈ +∞ và biểu thức −Mx5 gọi là lượng phạt (đánh thuế). Bài toán đã được
đưa về dạng chính tắc. Lượng vi phạm x5 càng lớn thì hàm mục tiêu càng giảm, giá trị
của hàm mục tiêu chỉ có thể đạt Max khi x5 = 0.

Kết luận: Bao giờ cũng đưa được BTQHTT bất kì (các biến có dấu tuỳ ý, các ràng
buộc có thể ≤, ≥, =) về dạng chính tắc.
Phương pháp đơn hình mở rộng

Phương pháp đơn hình mở rộng còn gọi là phương pháp đánh thuế M được áp dụng
để để giải BTQHTT có biến giả.
Ví dụ 5: Sau khi thêm vào các biến bù và biến giả, BTQHTT trong ví dụ 4 được
đưa về dạng chính tắc (trong hàm mục tiêu tất cả các biến giả đều có hệ số là -M nên bài
toán được gọi là bài toán M).

Max z = 8x1 + 6x2 +0x3 + 0x4 − Mx5 (trong đó M ≈ +∞) với các ràng buộc

Trường Đại học Nông nghiệp Hà Nội – Giáo trình Vận trù học

24




⎧4x1 + 2x 2 + x 3 = 60
⎪
(c) ⎨2x1 + 4x 2 − x 4 + x 5 = 48
⎪ x , x , x , x , x ≥ 0.
⎩ 1 2 3 4 5

Cách 1: Có thể giải BTQHTT với các điều kiện ràng buộc (a) bằng phương pháp đồ
thị để nhận được kết quả: phương án tối ưu là (x1 = 0, x2 = 30) và zmax = 180.
Cách 2: Giải BTQHTT với các điều kiện ràng buộc (c) bằng cách lập bảng đơn hình
như thông thường nhưng chú ý hệ số M ≈ +∞ (xem bảng II.2).


Tại bảng đơn hình cuối cùng, ta thấy Δj ≤ 0 ∀j nên phương án tối ưu đã đạt được
với x2 = 30, x4 = 72, các xj khác = 0 và zMax = 180.
Chú ý:
− Khi một biến giả đã được đưa ra khỏi cơ sở thì không bao giờ quay lại nữa. Do đó
ta có thể xoá cột biến giả đó khỏi bảng đơn hình.
− Nếu dấu hiệu dừng xuất hiện (Δj ≤ 0 ∀j) nhưng vẫn còn biến giả với giá trị dương
trong số các biến cơ sở thì điều này chứng tỏ bài toán ban đầu không thể có phương án
khả thi (có thể chứng minh bằng phản chứng).
Bảng II.2. Các bảng đơn hình giải bài toán M
Hệ số hàm mục
tiêu

Biến cơ sở

Phương
án

8

6

0

0

−M

x1

x2


x3

x4

x5

x3
x5

60
48

4
2

2
4

1
0

0
−1

0
+1

z0 = −48M


z1 = −2M

z2 = −4M

z3 = 0

z4 = M

z5 = −M

Δ1 = 8+2M

Δ2 = 6+4M

Δ3 = 0

Δ4 = −M

Δ5 = 0

36
12

3
1/2

0
1

1

0

1/2
−1/4

−1/2
1/4

72

3

6

0

−3/2

3/2

5

0

0

3/2

−M − 3/2


72
30

6
2

0
1

2
1/2

1
0

−1
0

180

12

6

3

0

0


−4

0

−3

0

−M

0
−M
Hàng z
Hàng Δj
0
6

x3
x2
Hàng z
Hàng Δj

0
6

x4
x2
Hàng z
Hàng Δj


Phương pháp đơn hình hai pha

Với ví dụ trên (xem bảng II.2) ta thấy quá trình giải chia làm hai pha: pha 1 nhằm
giải bài toán M cho tới khi biến giả (x5) được đưa ra khỏi số biến cơ sở (lúc này có
phương án cực biên xuất phát cho bài toán (b)) và pha 2 nhằm tìm phương án tối ưu cho
bài toán (b).