Giáo trình Toán kinh tế

BỘ CÔNG THƯƠNG
TRƯỜNG CAO ĐẲNG CÔNG NGHIỆP & XÂY DỰNG

BÀI GIẢNG MÔN HỌC
TOÁN KINH TẾ
Dùng cho hệ: Cao đẳng chuyên nghiệp
Chuyên ngành:
(Lưu hành nội bộ)
Người biên soạn: Phạm Ngọc Thế
Người phản biện: Nguyễn Thị Thu Hà
Uông Bí, năm 2010
1lêi më ®Çu
§Ó ®¸p øng kÞp thêi cho nhu cÇu vÒ tµi liÖu gi¶ng d¹y còng nh­ häc tËp
cña tr­êng Bé m«n kÕ to¸n ®· tæ chøc biªn so¹n gi¸o tr×nh "To¸n Kinh tÕ”
Trong khi biªn so¹n, c¸c gi¸o viªn ®· tiÕp thu nghiªm tóc nh÷ng ®ãng
gãp cña ng­êi ®äc vÒ nh÷ng ®iÓm cÇn chØnh lý vµ bæ sung ®¶m b¶o tÝnh c¬ b¶n,
hiÖn ®¹i, chÝnh x¸c, khoa häc vµ cËp nhËt ®­îc nhiÒu th«ng tin, nh÷ng thay ®æi
Gi¸o tr×nh "To¸n kinh tÕ" lµ tµi liÖu gi¶ng d¹y cho chuyªn ngµnh h¹ch
to¸n kÕ to¸n cña tr­êng Cao ®¼ng C«ng nghiÖp vµ X©y dùng ®ång thêi gi¸o tr×nh
lµ tµi liÖu tèt cho c¸c b¹n ®äc quan t©m kh¸c.
Gi¸o tr×nh lµ nÒn t¶ng cÇn cã ®Ó tiÕp tôc häc c¸c chuyªn ngµnh nh­ kÕ
to¸n tµi chÝnh, kÕ to¸n hµnh chÝnh sù nghiÖp vµ kÕ to¸n qu¶n trÞ, kiÓm to¸n,...
Mong r»ng gi¸o tr×nh sÏ lµ tµi liÖu h÷u Ých trong c«ng t¸c gi¶ng d¹y vµ
nghiªn cøu cña häc sinh trong vµ ngoµi tr­êng. Tuy nhiªn trong qu¸ tr×nh biªn
so¹n vµ xuÊt b¶n kh«ng tr¸nh khái nh÷ng sai sãt, rÊt mong ng­êi ®äc ®ãng gãp ý
kiÕn ®Ó hoµn thiÖn h¬n cho lÇn xuÊt b¶n sau.
Tæ bé m«n kÕ to¸n.
2Ch­¬ng më ®Çu : Bæ tóc kiÕn thøc ®¹i sè tuyÕn tÝnh
I.Véc tơ n chiều và các phép tính
1 - Các khái niệm
2 - Tổ hợp tuyến tính
33- Hệ vectơ phụ thuộc tuyến tính và độc lập tuyến tính
 Suy ra hệ đã cho độc lập tuyến tính
 Trong không gian Rn , một hệ vectơ độc lập tuyến tính có không quá n
vectơ và một hệ vectơ có nhiều hơn n vectơ thì phụ thuộc tuyến tính.
II.Ma trËn vµ c¸c phÐp tÝnh
1.Các khái niệm
+ Khái niệm về ma trận: Ma trận là bảng gồm mxn số thực được sắp sếp thành
m hàng và n cột là một ma trận cấp mxn.
Ký hiệu ma trận cấp mxn la (A)mxn=(aij)mxn, trong đó aij là phần tử tổng
quát của ma trận A.
+ Ma trận không
+ Ma trận tam giác
+ Ma trận đường chéo
+ Ma trận vuông
4+ Ma trận đơn vị
+ Ma trận chuyển vị
2.Các phép tính
Cho các ma trận A = (aij)mxn và ma trận B = (bij)mxn
+ Hai ma trận bằng nhau: Hai ma trận A và B được gọi là hai ma trận bằng
nhau nếu các phần tử tương ứng của hai ma trận bàng nhau nghĩa la aij = bij.
+ Phép cộng hai ma trận: Tổng hai ma trận A và B được gọi là hai ma trận C
trong đó các phần tử của nó bằng tổng tương ứng các phần tử tương ứng của hai
ma trận nghĩa là cij = aij + bij.
+ Tích ma trận với số b: Tích của ma trận A với một số b nào đó là một ma
trận bA cùng cấp trong đó các phần tử của nó bằng tương ứng các phần tử của
ma trân A sau khi nhân nên b lần..
+ Phép nhân hai ma trận: Tích ma trận A=(aij)mxn với ma trận B= (bij)nxp là
ma trận C = (cij)mxp trong đó các phần tử của nó bằng tổng tương ứng của các
phần tử hàng i ma trận A nhân các phần tử cột i ma trận B.
3.Hạng của ma trận
Người ta gọi hạng của của hệ véc tơ cột của A là hạng của ma trận A ký hiệu
là r hoặc rank(A). Như vậy hạng của ma trận A cung là hạng của hệ véc tơ dòng.
Tính chất : Rank(A) ≤ Min(m,n)
Các phép biến đổắô cấp, đồng nhất không làm thay đổi hạng của ma trận
4.Ma trận nghịch đảo
Cho Ma trận là ma trận vuông cấp n và Rank(A) = n thì bao giờ cũng tồn tại
ma trận A-1 sao cho A.A-1=E (Ma trận đơn vị ) thì A-1 được goi là ma trân nghịch
đảo của ma trận A.
Cách tính ma trận nghịch đảo:
Để tính được ma trận nghịch đảo A-1 ta viết ma trận mở rộng (A/E) sau đó
thực hiện phép biến đổi sơ cấp sao cho ma trận mở rộng trên chuyển trành (A/A-
1) thì A-1 là ma trận nghịch đảo cần tìm.
III.HÖ ph­¬ng tr×nh tuyÕn tÝnh
5Hệ phương trình tuyến tính :
Khái niệm: Hệ phương trình tuyến tính tổng quát là hệ có m phương trình và
n ẩn số .
Có thể giải hệ phương trình tuyến tính bằng nhiều phương pháp khác nhau (
thế , khử , định thức ... ) . Phương pháp thế được thể hiện bằng cách thực hiện
phép quay . Ðể ứng dụng thêm trong việc giải bài toán Qui hoạch tuyến tính sau
này, ta giải hệ phương trình bằng phép quay biến dạng.
6
7
8
9Ch­¬ng i: bai to¸n quy ho¹ch tuyÕn tÝnh ph­¬ng ph¸p
®¬n h×nh
I .Bµi to¸n quy ho¹ch tuyÕn tÝnh tæng qu¸t vµ c¸c d¹ng ®Æc biÒt
1- Bài toán quy hoạch tuyến tính tổng quát
C¸c kh i¸ niÖm:
Có thể tạm định nghĩa 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 mà hàm mục tiêu (vấn đề được quan tâm) và các ràng buộc
(điều kiện của bài toán) đều là hàm và các phương trình hoặc bất phương trình
tuyến tính. Đây chỉ là một định nghĩa mơ hồ, bài toán quy hoạch tuyến tính sẽ
được xác định rõ ràng hơn thông qua các ví dụ .
Các bước nghiên cứu và ứng dụng một bài toán quy hoạch tuyến tính điển
hình là như sau :
- Xác định vấn đề cần giải quyết, thu thập dữ liệu.
- Lập mô hình toán học.
- Xây dựng các thuật toán để giải bài toán đã mô hình hoá bằng ngôn ngữ
thuận lợi cho việc lập trình cho máy tính.
- Tính toán thử và điều chỉnh mô hình nếu cần.
- Áp dụng giải các bài toán thực tế.
Hay nói gọn hơn:
Bài toán quy hoạch tuyến tính tổng quát là bài toán đi tìm cực trị (cực tiểu
hoặc cực đại) của một hàm tuyến tính xác định trên tập hợp nghiệm của một hệ
thống hỗn hợp các phương trình và bất phương trình tuyến tính.Bài toán được mô
tả dưới dạng toán học như sau :
F(x) = j
n
j
j xc
 1
 min (max)
j
n
j
ijxa
 1
= bi (i I 1)
j
n
j
ijxa
 1
 ( ) bi (i I 2)
Trong đó f(x) gọi là hàm mục tiêu ,mỗi phương trình hoặc bất phương trình
tuyến tính gọi là một ràng buộc.
-Phương án
Véctơ x thoả mãn mọi ràng buộc của một bài toán gọi là một phương án.
-Phương án x thoả mãn ràng buộc i với dấu " = " , nghĩa là : j
n
j
ijxa
 1
= bi , thì
ràng buộc i gọi là " chặt " đối với phương án x , hoặc phương án x thoả mãn chặt
ràng buộc i .
- Phương án x thoả mãn ràng buộc i với dấu bất đẳng thức thực sự ,nghĩa là
j
n
j
ijxa
 1
 ( ) bi thì ràng buộc i gọi là " lỏng " đối với phương án x ,hoặc phương
án x thoả mãn lỏng ràng buộc i.
-Phương án cực biên
10
Một phương án thoả mãn chặt n ràng buộc độc lập tuyến tính, gọi là phương
án cực biên . Một phương án cực biên thoả mãn chặt đúng n ràng buộc gọi là
phương án cực biên không suy biến, thoả mãn chặt hơn n ràng buộc gọi là
phương án cực biên suy biến .
-Phương án tối ưu
Một phương án mà tại đó hàm mục tiêu đạt chỉ số cực tiểu (cực đại ) gọi là
phương án tối ưu (tốt nhất )
-Bài toán giải được và không giải được
Bài toán có ít nhất một phương án tối ưu gọi là bài toán giải được .Bài toán
không có phương án hoặc có phương án nhưng trị số hàm mục tiêu không bị
chặn dưới (trên ) - cũng có nghĩa là giảm ( tăng ) vô hạn - trên tập phương án gọi
là không giải được .
Cơ sở của phương án cực biên
 Gọi m véctơ [A j ] độc lập tuyến tính bao hàm hệ thống các véctơ tương ứng
với các thành phần dương của phương án cực biên là cơ sở của phương án cực
biên ấy .Ký hiệu một cách quy ước cơ sở là J . Các đặc trưng của một cơ sở j : | J
|= m ,trong đó| J | là số phần tử của j ; { A Jjj : } độc lập tuyến tính ,{ A Jjj : }
}.0:{A  jj x
-Phương án cực biên không suy biến chỉ có một cơ sở duy nhất ,đó là các
véctơ tương ứng với các thành phần dương.
-Phương án cực biên suy biến có nhiều cơ sở khác nhau,phần chung của chúng
là các véctơ tương ứng với các thành phần dương.
)( Jjx j gọi là thành phần cơ sở ;
2.Các dạng đặc biệt
Bài toán dạng chính tắc
Bài toán dạng đặc biệt có một hệ phương trình ràng buộc và mọi biến số đều
không âm như sau :
F(x) = j
n
j
j xc
 1
 min (max)
j
n
j
ijxa
 1
= bi (i = 1 )m
Xj )1(0 nj  
Ký hiệu A = [ a ij ]mn gọi là ma trận điều kiện của bài toán;
Aj - véctơ cột j của ma trận A- gọi là véctơ điều kiện ;b-véctơ vế phải của hệ phương trình ràng buộc .
11
-Bài toán chính tắc còn có thể viết dưới dạng :
F(x) = j
n
j
j xc
 1
 min (max)
bAx j
n
j j
 
 1
X );1(0 njj  
F(x)=(c,x) min( max)
Ax=b
x .0 
- Cách đưa một bài toán về dạng chính tắc
Ðịnh lí 1 . Mọi bài toán quy hoạch tuyến tính đều có thể quy về bài toán dạng
chính tắc tương đương theo nghĩa trị tối ưu của hàm mục tiêu trong hai bài toán
là trùng nhau và từ phương án tối ưu của bài toán này suy ra phương án tối ưu
của bài toán kia .
Chứng minh
Trước hết , ta chứng tỏ rằng bài toán Qui hoạch tuyến tính tổng quát có thể
đưa về dạng chính tắc
Người ta có thể biến đổi bài toán quy hoạch tuyến tính dạng tổng quát thành
bài toán quy hoạch tuyến tính dạng chính tắc nhờ các quy tắc sau đây :
• Nếu gặp ràng buộc i có dạng ≤ thì người ta cộng thêm vào vế trái của ràng
buộc một biến phụ xn+i≥ 0 để được dấu = ..
• Nếu gặp ràng buộc i có dạng ≥ thì người ta trừ vào vế trái của ràng buộc
một biến phụ xn+i ≥ 0 để được dấu = .
Các biến phụ chỉ là những đại lượng giúp ta biến các ràng buộc dạng bất đẳng
thức thành đẳng thức, nó phải không ảnh hưởng gì đến hàm mục tiêu nên không
xuất hiện trong hàm mục tiêu.
• Nếu biến xj≤ 0 thì ta đặt xj= -x’j với x’j≥ 0 rồi thay vào bài toán.
• Nếu biến xj là tuỳ ý thì ta đặt xj = xjj -x’jj , các xjj đều ≥ 0 rồi thay vào bài
toán.
• Trong trường hợp trong số các ràng buộc có dòng mà vế phải của dòng đó là
giá trị âm thì đổi dấu cả hai vế để được vế phải là một giá trị không âm.
12
Dựa vào các phép biến đổi trên mà người ta có thể nói rằng bài toán quy
hoạch tuyến tính chính tắc là bài toán quy hoạch tuyến tính mà trong đó các
ràng buộc chỉ có dấu = , vế phải và các biến số đều không âm.
13
Ðịnh lí 1 cho thấy rằng chỉ cần xây dựng thuật toán giải cho bài toán Qui
hoạch tuyến tính dạng chính tắc ( hoặc chuẩn tắc ) và từ đó có thể giải được bài
toán Qui hoạch tuyến tính tổng quát.
b) Bài toán dạng chuẩn: là bài toán QHTT có dạng
-Bài toán dạng chính tắc đặc biệt thể hiện ở :bi )1(0 mi  ,mỗi phương trình
có một biến với hệ số bằng 1 và không có mặt ở các phương trình khác.Có thể
mô tả dưới dạng :
F(x)= j
n
j
j xc
 1
 min (max)
x1 +a1m+1xm+1+ a1m+2xm+2 + ........+ a1nxn=b1
 x2 + a2m+1xm+1+ a2m+2xm+2+ ........+ a2nxn=b2
.....................................................
 xm + amm+1xm+1+ amm+2xm+2+ ........+ amnxn=bm
)1(0 njx j  
Bài toán Qui hoạch tuyến tính dạng chuẩn tắc có tất cả điều kiện ràng buộc là
bất phương trình và tất cả các ẩn số đều không âm :
14
II.C¸c tÝnh chÊt chung
1.Sù tån t¹i ph­¬ng ¸n cùc biªn
-Nếu bài toán có phương án và hạng của ma trận hệ ràng buộc n thì bài toán
có phương án cực biên .
-Nếu bài toán dạng chính tắc có phương án thì chắc chắn có phương án cực
biên vì hạng của ma trận hệ ràng buộc luôn bằng n.
Định lý 1.
Tập D các phương án của bài toán QHTT chính tắc là một tập lồi.
Định lý 2.
Nếu tập D các phương án của bài toán QHTT chíng tắc không rỗng và bị
chặn, thì D là một đa diện lồi.
• Định lý có thể chứng minh bằng phương pháp quy nạp theo số biến của
bài toán. Để chứng minh D là một đa diện lồi, ta chỉ cần chứng tỏ rằng, trong D
có một số hữu hạn các phương án, mà mỗi phương án thuộc D đều là tổ hợp lồi
của các phương án trong D.
Định lý 3. Nếu bài toán QHTT chính tắc có lời giải và tập D các phương án
của nó là một đa diện lồi, thì có ít nhất một điểm cực biên của D là phương án tối
ưu.
Định lý 4. Nếu bài toán QHTT chính tắc có lời giải, thì tồn tại ít nhất 1 điểm
cực biên của tập D các phương án là phương án tối ưu (gọi là phương án cực biên
tối ưu).
• Định lý này làm cơ sở lý luận cho phương pháp giải bài toán. Nhờ nó đáng
lẽ phải phải tìm phương án tối ưu trong tập vô số phương án, ta chỉ cần tìm trong
tập hữu hạn các phương án cực biên.
Tuy vậy, không loại trừ có những phương án tối ưu không phải là điểm cực
biên, thể hiện ở định lý sau:
Định lý 5. Nếu bài toán QHTT chính tắc có x1 , x2 , ... , xk là những phương
án cực biên tối ưu, thì mọi tổ hợp lồi của chúng cũng là phương án tối ưu.
Nếu tập các phương án của một quy hoạch tuyến tính chính tắc không rỗng thì
quy hoạch tuyến tính đó có ít nhất một phương án cực biên.
Bổ đề
15
Nếu x là một phương án tối ưu của quy hoạch tuyến tính.
x1, x2 là các phương án của quy hoạch tuyến tính.
x là tổ hợp lồi thực sự của x1, x2
thì x1, x2 cũng là phương án tối ưu của quy hoạch tuyến tính.
Nếu tập các phương án của một quy hoạch tuyến tính không rỗng và là một đa
diện lồi thì quy hoạch tuyến tính đó sẽ có ít nhất một phương án cực biên là
phương án tối ưu
2.Sù tån t¹i ph­¬ng ¸n tèi ­u
-Nếu bài toán có phương án và trị số hàm mục tiêu bị chặn dưới (trên) trên tập
hợp phương án thì bài toán có phương án tối ưu ( giải được).
-Nếu bài toán có phương án cực biên và giải được thì phải có phương án cực
biên tối ưu .Do đó nếu bài toán dạng chính tắc giải được thì phải có phương án
cực biên tối ưu.
-Nếu bài toán có hơn một phương án tối ưu thì sẽ có vô số phương án tối ưu .
3.TÝnh h÷u h¹n cña sè ph­¬ng ¸n cùc biªn
-Số phương án cực biên của mọi bài toán quy hoạch tuyến tính đều hữu hạn.
Điều kiện cần và đủ để x0 là phương án cực biên ( điểm cực biên của S) là các
cột Aj ứng với >0 là độc lập tuyến tính.
Số phương án cực biên của một quy hoạch tuyến tính chính tắc là hữu hạn. Số
thành phần > 0 của một phương án cực biên tối đa là bằng m.
Khi số thành phần > 0 của một phương án cực biên bằng đúng m thì phương
án đó được gọi là một phương án cơ sở.
NX: Tập hợp các phương án D của bài toán Qui hoạch tuyến tính thường là vô
hạn, tuy nhiên số phương án cực biên là hữu hạn. Ðịnh lí 5 cho thấy rằng chỉ cần
tìm nghiệm trong các điểm cực biên (hữu hạn) của D , suy ra tính hữu hạn của
thuật toán đơn hình sau này.
III.Ph­¬ng ph¸p ®¬n h×nh gi¶i bµi to¸n quy ho¹ch tuyÕn tÝnh
1.Néi dung cña ph­¬ng ph¸p
-Nội dung của phương pháp
16
Xuất phát từ một phương án cực biên của bài toán dạng chính tắc, tìm cách
đánh giá nó ,nếu chưa tối ưu thì tìm cách chuyển sang một phương án cực biên
khác tốt hơn .Vì số phương án cực biên là hữu hạn nên sau một số hữu hạn bước
hoặc sẽ kết luận bài toán không giải được vì trị số hàm mục tiêu không bị chặn
trên tập phương án hoặc sẽ tìm được phương án cực biên tối ưu .
Có một số phương pháp khác nhau để giải bài toán Qui hoạch tuyến tính :
phương pháp hình học , phương pháp phân tích sự biến động của hàm mục tiêu
và phương pháp đơn hình .
 Trong một số trường hợp , dựa vào sự phân tích các hệ số của hàm mục
tiêu f , có thể chỉ ra được sự tăng lên hoặc giảm xuống của một số ẩn số theo
hướng có lợi cho hàm mục tiêu từ đó suy ra phương tối ưu . Tất nhiên , phương
pháp này không phải khi nào cũng sử dụng hiệu quả .
Ở thời điểm hiện nay , máy tính cá nhân được sử dụng phổ biến cũng
như có nhiều chương trình hoặc phần mềm lập cho máy tính để giải bài toán Qui
hoạch tuyến tính nên việc xây dựng một phương pháp vạn năng cho tất cả các bài
toán Qui hoạch tuyến tính cần thiết . Ðó chính là phương pháp đơn hình và
phương pháp đơn hình mở rộng được trình bày ở mục sau . Sử dụng phương
pháp đơn hình.
 Có nhiều hình thức trình bày cơ sở lý thuyết cho phương pháp đơn hình
: ma trận, cơ sở của không gian vectơ và tọa độ vectơ .. . Mặc dù vậy , phần tính
toán thực hành đều giống nhau . Ðịnh lí 1 cho thấy rằng chỉ cần xây dựng thuật
toán giải cho bài toán Qui hoạch tuyến tính dạng chính tắc ( hoặc chuẩn tắc ) thì
mọi bài toán tổng quát xem như giải được. Mặt khác , từ Ðịnh líï 5 và hệ quả của
nó suy ra rằng chỉ cần tìm phương án tối ưu trong các phương án cực biên ( hữu
hạn ) . Phương pháp ( thuật toán ) đơn hình được xây dựng để tìm nghiệm cực
biên của  ... n hình ta sẽ được một phương án cực biên tối ưu
khác của bài toán M .Vì 0A nằm trong cơ sở nên bỏ hàng và cột ứng với x0 sẽ
được bản đơn hình ứng với cơ sở tối ưu của bài toán xuất phát .Tuy nhiên trường
hợp này sẽ không xảy ra nếu khi thực hiện thuật toán ta luôn ưu tiên đưa vectơ
0A vào cơ sở khi nó ứng với 0 .
- Đặc điểm tính toán khi giải bài toán M
Vì thành phần cơ sở của giả phương án phụ thuộc M nên trong bảng đơn
hình cột phương án chia làm hai : Một cột ghi phần phụ thuộc M ,một cột ghi hệ
số của M trong thành phần cơ sở .Khi hệ số của M khác 0 thì dấu của nó chính là
46
dấu của thành phần cơ sở .Chú ý rằng cột hệ số của M hoàn toàn trùng với cột
0, 00 cx ,nên 0 trùng với hệ số của M trong yf
Vì vậy để đơn giản trong bảng có thể dùng chính cột này làm cột x0.
47
Ch­¬ng III: Bµi to¸n vËn t¶i
I.Néi dung vµ ®Æc ®iÓm
1.Néi dung kinh tÕ vµ d¹ng to¸n häc
Nội dung bài toán.
Giả sử trên một khu vực địa lý ,tại một thời điểm nhất định có m nơi sản xuất (
kho) một loại hàng hoá thuần nhất .Ký hiệu nơi sản xuất i là Ai và gọi là trạmphát Ai mi  1 ; lượng hàng hiện có ở Ai là ai .Đồng thời có n nơi tiêu thụ loại
hàng hoá đó .Ký hiệu nơi tiêu thụ j là Bj và gọi là trạm thu 1jB j n  ; yêu cầu
của trạm thu Bj là bj .Để thuận tiện từ đây ta sẽ gọi ai và bj là yêu cầu của cáctrạm phát và thu .Chi phí vận chuyển một đơn vị hàng hóa từ trạm phát Ai tới
trạm thu Bj là cij 1 , 1i m j n   .Lập phương án vận chuyển đáp ứng đầy đủ yêu
cầu của các trạm thu bằng tát cả các hàng hóa có ở cấc trạm phát với tổng chi phí
vận chuyển là nhỏ nhất .
. Hãy lập kế hoạch vận chuyển từ mỗi điểm phát đến mỗi điểm thu bao
nhiêu hàng để :
- Các điểm phát đều phát hết hàng
- Các điểm thu đều nhận đủ hàng
- Tổng cước phí phải trả là ít nhất
 Gọi xij là lượng hàng chuyển từ điểm phát Ai đến điểm thu Bj , xij ≥ 0 . Vì
tổng lượng hàng phát đi từ mỗi điểm phát Ai đến mọi điểm thu Bj bằng lượng
hàng phát từ Ai nên :
Dạng toán học
Gọi xij là lượng hàng vận chuyển từ trạm phát Ai tới trạm thu Bj .Mô hình bàicó dạng :
ij ij
1 1
ij
1
ij ij
1
min
1
1 , ,
n m
j i
n
i
j
m
j
i
f x c x
x a i m
x b j n x o i j
 
  



48
Bài toán trên gọi là bài toán vận tải cổ điển hay bài toán dạng đóng .Rõ ràng
bài toán chỉ có nghĩa khi
1 1
m n
i j
i j
a b
   ,với điều kiện này bài toán gọi là cân bằng
thu phát .
Bài toán không cân bằng thu phát có 2 dạng và gọi chúng là bài toán dạng
mở .
a)
1 1
m n
i j
i j
a b
  
 ij ij
1 1
min
n m
j i
f x c x
 
 ij
1
1
n
i
j
x a i m
 
 ij ij
1
1 , 0 ,
m
j
i
x b j n x i j
  
b)
1 1
m n
i j
i j
a b
  
 ij ij
1 1
min
n m
j i
f x c x
 
ij
1
ij ij
1
1
1 , 0 ,
n
i
j
m
j
i
x a i m
x b j n x i j
 
  


2.C¸c ®Æc ®iÓm
Tính chất chung của bài toán vận tải đóng
-Đó là bài toán dạng chính tắc .Trong hệ m+ n phương trình ràng buộc chỉ có
m+n-1 phương trình độc lập tuyến tính , do đó một phương án cực biên có tối đa
m+n-1 thành phần dương .
- Các vecto điều kiện Aij tương ứng với biến xij có thành phần I và thànhphần m+j bằng 1 ,các thành phần còn lại đều bằng 0.
-Bài toán cân bằng thu phát luôn giải được .
3.M« t¶ bµi to¸n d­íi d¹ng b¶ng
Bài toán vận tải dạng bảng
Xây dựng một bản gồm m hàng và n cột ;mỗi hàng dặc trwung cho một trạm
phát ,mỗi cột đặc trưng cho một trạm thu .Tương ứng với mỗi hàng hoặc cột ghi
yêu cầu của trạm phát hoặc trạm thu .
49
-Phương pháp chi phí nhỏ nhất ( đường gần ):luôn ưu tiên phân phối cho ô
có cij nhỏ nhất trong bảng .-Phương pháp Fogels : Luôn ưu tiên phân phối cho ô có cij nhỏ nhất nằm trên
hàng hoặc cột có hiệu số giữa chi phí nhỏ nhì và nhỏ nhất và lớn nhất .
Ta đưa bài toán vào một bảng gọi là bảng vận tải.
Bảng gồm (m+1) hàng và (n+1) cột, cột 1 ghi tên và lượng hàng ở các điểm phát
(Ai và ai). Hàng 1 ghi tên và lượng hàng ở các điểm thu (Bj và bj), ô còn lại trong
mỗi ô góc trên bên trái ghi cước phí cij, góc dưới bên phải ghi lượng hàng xij.
• Các khái niệm về bài toán dạng bảng:
• Ô chọn: Là ô có lượng hàng xij ≥0, còn gọi là ô sử dụng, khoanh tròn xij lại.
• Ô loại: Là ô không có hàng, tức xij=0, ta để trống ô đó.
• Dây chuyền: là một đoạn thẳng hay một dãy liên tiếp các đoạn thẳng gấp khúc
mà hai đầu mút là hai ô chỉ nằm trên cùng một hàng hoặc một cột với một ô chọn
khác thuộc dây truyền của bảng vận tải.
• Chu trình: Là dây chuyền khép kín
Như vậy một hàng hoặc một cột mà chu trình đi qua thì chỉ đi qua hai ô và số ô.
Do đó số ô ít nhất của một chu trình là 4.
• Ma trận X = (xi j)m.n thỏa mãn hệ (2) - (4) được gọi là một phương án của
bài toán.
• Phương án: X = (xi j)m.n thỏa mãn được gọi là phương án cực biên của
bài toán vận tải nếu tập hợp các ô tương ứng với các thành phần dương của nó
không tạo thành chu trình.
• Phương án X = (xi j)m.n được gọi là phương án cực biên không suy biến nếu
số ô chọn của nó đúng bằng m+n+1.
• Phương án X = (xi j)m.n được gọi là phương án cực biên suy biến nếu số ô
chọn của nó nhỏ thua m+n+1.
• Một phương án thoả mãn yêu cầu (1) được gọi là phương án tối ưu (nghiệm) của
bài toán, ký hiệu là Xopt.
 Cho bài toán vận tải dạng bảng kích thước m x n. Một tập hợp các ô có thứ
tự được gọi là một dây chuyền nếu:
50
• Hai ô liên tiếp cùng dòng hoặc cùng cột.
• Ba ô liên tiếp không cùng dòng hoặc cùng cột.
 Một dây chuyền khép kín, nghĩa là ô cuối cùng dòng hoặc cùng cột
với ô đầu tiên được gọi là một chu trình.
Chú ý rằng mệnh đề ngược lại của Ðịnh lí 3 không đúng. Số m+n-1 chỉ là dấu
hiệu cần nhưng không phải là điều kiện đủ để xét tập hợp các ô có chứa chu trình
hay không.
Hệ quả Một phương án cực biên có không quá m+n-1 ô chọn hay một
phương án có từ m+n ô chọn trở lên thì không phải là phương án cực biên .
 Mệnh đề ngược lại không đúng . Số ô chọn không quá m+n-1 chỉ là dấu hiệu
cần nhưng không đủ để xét một phương án có phải là cực biên hay không .
II.X©y dùng ph­¬ng ¸ n cùc biªn
Bài toán vận tải là bài toán Qui hoạch tuyến tính dạng chính tắc nên có thể
giải bằng phương pháp đơn hình ( Chương I ) .Tuy nhiên , bài toán vận tải
thường có số ẩn rất lớn ( mxn ) và có cấu trúc đặc biệt : ma trận các hệ số hầu hết
bằng 0 ,do đó , chúng ta sẽ không giải bài toán theo phương pháp đơn hình đã
biết mà xây dựng một phương pháp giải đơn giản hơn , đó là phương pháp
(thuật toán ) phân phối .
Có 3 phương pháp xây dựng phương án cực biên thường sử dụng là phương
pháp góc .
Nội dung chính của phương pháp phân phối gồm các bước như sau :
1.Nguyªn t¾c ph©n phèi tèi ®a(TL)
Lây ô(i,j) bất kỳ và phân phối lượng hàng xij = min(ai,bj) sẽ có ba trường hợp xẩy ra như
sau.
Trường hợp 1: xij = ai nghĩa là trạm phát Ai đã hết hàng, loại bỏ hàng i đồng thời sửa lại
nhu cầu của trạm thu Bj lượng hàng mới là b’j = bj- ai.
Trường hợp 2: xij = bj nghĩa là trạm thu Bi đã hết hàng, loại bỏ cột j đồng thời sửa lại nhu
cầu của trạm phát Aj lượng hàng mới là a’j = ai – bj
Trường hợp 3: xij = ai = bj nghĩa là trạm phát Ai đã hết hàng và trạm thu Bj đã thoả mãn
nhu cầu loại bỏ hàng i và cột J
51
Quá trình cứ tiếp tục như vậy cho đến khi toàn bộ lượng hàng ở các tram phát phân phối
hết và các trạm thu thoả mãn nhu cầu về hàng hoá.
2.C¸c ph­¬ng ph¸p x©y dùng ph­¬ng ¸ n cùc biªn
a. Phương pháp tìm phương án cực biên xuất phát.
Để xây dựng một phương án cực biên xuất phát người ta thường sử dụng
một trong ba phương pháp sau:
• Phương pháp góc Tây-Bắc.
Phương pháp góc tây bắc gồm những bước sau:
Bước 1. Chọn ô nằm ở dòng 1, cột 1 của bảng
vận tải. Bước 2. Phân lượng hàng h = min{a1, b1}
vào ô(1,1)
Bước 3. Đánh dấu hàng (cột), theo đó lượng hàng ở trạm phát (trạm thu) tương
ứng đã hết
(đã đủ).
Bước 4. Quay trở về bước 1 thực hiện công việc ở những ô còn lại.
• Phương pháp min- cước.
Nội dung phương pháp min cước gồm các bước sau đây.
Bước 1. Chọn ô có cước phí thấp nhất để phân hàng giả sử là
ô (i,j). Bước 2. Phân lượng hàng h = min {ai, bj} vào ô(i,j)
Bước 3. Đánh dấu các ô thuộc hàng i, hoặc cột j nếu trạm phát Ai đã phát hết
hàng, hoặc trạm thu Bj đã nhận đủ hàng.
Bước 4. Quay trở lại bước 1 thực hiện công việc ở những ô còn lại.
• Phương pháp xấp xỉ Phoghel.
• Định nghĩa. Độ lệch của hàng (cột) là hiệu số giữa ô có cước phí thấp thứ nhì
trừ đi ô có cước phí thấp thứ nhất của hàng (cột) đó.
Nội dung của phương pháp Phoghen gồm các bước sau:
Bước 1. Chọn hàng hoặc cột có độ chênh lệchlớnnhất
52
Bước 2. Chọn ô có cước phí thấp nhất thuộc hàng (cột) có độ chênh lệch lớn
nhất, giả sử ô(i,j).
Bước 3. Phân lượng hàng h = min{ai, bj} vào ô(i,j)
Bước 4. Đánh dấu các ô thuộc hàng (cột), theo đó trạm phát Ai đã phát hết
hàng hoặc trạm
thu Bj đã nhận đủ hàng, quay trở về từ bước 1 tiếp tục thực hiện thuật toán.
Phương pháp góc Tây - Bắc
- Phân phối tối đa vào ô góc Tây - Bắc của bảng ( góc trên bên trái ) .
- Tính lại lượng hàng ở dòng và cột vừa tham gia phân phối . Tạm thời loại dòng
hoặc cột có lượng hàng còn lại bằng 0 ra khỏi quá trình phân phối . Quay lại bước ở trên
và tiếp tục phân phối cho đến hết .
Các số ai được viết ở cột đầu tiên , các số bj được viết ở dòng đầu tiên . Các
dòng và cột này không tính vào kích thước bài toán . Ma trận cước phí [ ci j ]
đưọc viết nhỏ hơn ở phía dưới mỗi ô .
Phương pháp ưu tiên cước phí nhỏ nhất
- Phân phối tối đa vào ô có cước phí nhỏ nhất của toàn bảng .
- Tính lại lượng hàng ở dòng và cột vừa tham gia phân phối . Tạm thời loại dòng
hoặc cột có lượng hàng còn lại bằng 0 ra khỏi quá trình phân phối . Quay lại bước - ở
trên và tiếp tục phân phối cho đến hết . - Phương pháp xấp xỉ Fogen
- Tính độ lệch của các dòng [ cột ] bằng hiệu số giữa cước phí nhỏ thứ nhì và
cước phí nhỏ nhất trong dòng [ cột ] đó .
- Xác định ô trũng : ô có cước phí nhỏ nhất ở trên dòng và cột cùng có độ
lệch lớn nhất . Phân phối tối đa vào ô trũng nếu có và chuyển sang bước tiếp
theo.
- Phân phối tối đa vào ô có cước phí nhỏ nhất ở trên dòng [ cột ] có độ lệch
lớn nhất .
- Tính lại lượng hàng trên dòng và cột vừa phân phối . Loại bỏ dòng hoặc cột
có lượng hàng bằng 0 khỏi quá trình phân phối . Quay lại bước và tiếp tục quá
trình cho đến hết .
 Phương án thu được theo nguyên tắc phân phối tối đa là phương án cực
biên .
53
III.Ph­¬ng ph¸p thÕ vÞ gi¶i bµi to¸n vËn t¶i
1.Tiªu chuÈn tèi ­u
Tiêu chuẩn tối ưu :
Điều kiện cần và đủ để phương án ij{x }x của bài toán vận tải tối ưu là tồn
tại một hệ thống số i{u }jv thỏa mãn :
a) ij ( , )j iv u c i j 
b) ijj iv u c nếu xij>0
Các số ui,vj trong tiêu chuẩn tối ưu và trong các tính toán sẽ gặp được gọi làcác thế vị hàng và cột .
3. ThuËt to¸n cña ph­¬ng ph¸p thÕ vÞ
Thuật toán của phương pháp thế vị
Giả sử đã biết một phương án cực biên với tập ô cơ sở S tương ứng .Thuật
toán gồm các bước sau :
Bước 1: Tìm phương án cực biên xuất phát X0= (xij )m..xn
 Sử dụng một trong 3 phương pháp đã trình bầy ở trên để tìm phương án cực
biên xuất phát
(nếu phương án tìm được là phương án suy biến thì ta phải bổ xung ô chọn
không để được phương án không suy biến, ô chọn có vai trò như các ô chọn khác).
Bước 2: Kiểm tra tính tối ưu của phương án.
• Xây dựng hệ thống thế vị.
1)Xây dựng hệ thống thế vị {ui,vj}Lấy một hàng I bất kì và cho nó một thế vị u ,tùy ý .Các thế vị còn lại được
xác định theo quy tắc :
-Nếu hàng I đã có ui và (I,j) S thì thế vị của cột j được tính bởi :Vj=ui+cij-Nếu cột j đã có vj và (I,j) S thì thế vị của hàng I được tính bởi :
Ui=vj-cijQuá trình tiếp tục cho tới khi xác định được toàn bộ hệ thống thế vị .
2) Kiểm tra tiêu chuẩn tối ưu
-Các ô cơ sở (I,j) S ,hiển nhiên thỏa mãn điều kiện b vì vậy chỉ cần kiểm tra
điều kiện a đối với các ô phi cơ sở (I,j) S .
-Nếu vj-ui cij, ,i j S thì phương án tương ứng tối ưu .
54
-Nếu tồn tại một ô Sji , mà vj - ui > cij thì phương án không tối ưu .Các ô
có vj - ui > cij gọi là các ô vi phạm ,tính ijijij cuv đối với các ô vi phạm
,như vậy 0 ij
3) Điều chỉnh phương án
-Giả sử rkij
ij
max
0
.Ô (r,k) được lấp làm ô điều chỉnh .Tìm vòng tạo bởi ô
điều chỉnh với các ô cơ sở .Trên vòng đánh dấu lẻ chẵn các ô với ô điều chỉnh
(r,k) là ô lẻ .Ký hiệu vi,vc tương ứng là tập ô lẻ ,chẵn trên vòng .Xác định q=min
xij, cVji , .Thực hiện phép biến đổi biến số trên vòng :
cij
iij
ij
ij
Vjiqx
Vjiqx
Vjix
x
,
,,
,,
-Thực chất phép biến đổi trên là tăng q cho ô lẻ và giảm q ở ô chẵn .
-Kết quả của quá trình biến đổi ta được phương án cực biên mới x' tốt
hơn x : rkqxfxf .' sau điều chỉnh ô điều chỉnh thành ô cơ sở ,ô ứng
với q sẽ trở thành phi cơ sở.
3.Tr­êng hîp suy biÕn
- Trường hợp bài toán suy biến thì q có thể bằng 0.Khi q=0 ta vẫn thực hiện
thuật toán một cách bình thường ,nghĩa là ô ứng với q vẫn bị loại khỏi tập ô cơ sở
.Tuy nhiên kết quả của quá trình điều chỉnh chỉ chuyển sang một tập ô cơ sở khác
của cùng một phương án cực biên suy biến .
- Dấu hiệu xuất hiện phương án cực biên suy biến là q đạt tại nhiều ô .Khi
đó ta sẽ loại một trong những ô ứng với q ra khỏi tập ô cơ sở theo quy tắc ngẫu
nhiên ,các ô còn lại ứng với q vẫn giữ trong tập ô cơ sở với tư cách ô bổ sung.
IV.Bµi to¸n kh«ng c©n b»ng thu ph¸t
1.Ph¸t lín h¬n thu
Trường hợp  
m
i
n
j
jba
1 1
1 ta đưa về bài toán cân bằng thu phát bằng cách thêm
vào một trạm thu giả Bn+1 với yêu cầu  
m
i
n
j
jn bab
1 1
11 ,đồng thời ci.n+1=0
)( j .Lượng hàng lấy từ trạm phát A1 cung cấp cho trạm thu giả Bn+1 nghĩa là
lượng hàng được giữ lại ở trạm phát A1
P.hương pháp giải
• Giải bài toán vận tải cung lớn hơn cầu:
55
Ta thêm vào bài toàn một trạm thu giả Bn+1 với lượng hàng thu là:
Cước phí từ trạm phát giả Am+1 đến các trạm thu Bj là cm+1,j = 0 (j = ,1 n ).
Khi đó bài toán đã cho trở về bài toán cung bằng cầu mà ta đã biết cách giải.
Chú ý: - Khi giải bài toán trên, nếu sử dụng phương pháp min- cước tìm
phương án cực biên xuất phát ta ưu tiên phân phối hàng tối đa vào ô có cựớc phí
dương nhỏ nhất trước rồi mới mới đến ô có cước phí bằng không.
• Giá trị hàm mục tiêu: f (Xopt) = f ( X opt) = fmin.
2.Ph¸t it h¬n thu
-Trường hợp  
m
i
n
j
ji ba
1 1
.Ta đưa về bài toán cân bằng thu phát bằng cách
thêm vào một trạm phát giả Am+1 với yêu cầu am+1= 
n
j
m
i
ij ab
1 1
,đồng thời
)(0 jc ijm  .Lượng hàng lấy từ trạm phát giả Am+1 cung cấp cho trạm thu Bj
,nghĩa là lượng yêu cầu của trạm thu Bj không được thoả mãn .
hàng.
Phương pháp giải
• Giải bài toán vận tải cung lớn hơn cầu:
Ta thêm vào bài toàn một trạm thu giả Bn+1 với lượng hàng thu là:
Cước phí từ trạm phát giả Am+1 đến các trạm thu Bj là cm+1,j = 0 (j = ,1 n ).
Khi đó bài toán đã cho trở về bài toán cung bằng cầu mà ta đã biết cách giải.
Chú ý: - Khi giải bài toán trên, nếu sử dụng phương pháp min- cước tìm
phương án cực biên xuất phát ta ưu tiên phân phối hàng tối đa vào ô có cựớc phí
dương nhỏ nhất trước rồi mới mới đến ô có cước phí bằng không.
• Giá trị hàm mục tiêu: fmin.
Thùc hµnh gi¶i bµi to¸n QHTT trªn m¸y tÝnh
56
tµi liÖu tham kh¶o
1. To¸n kinh tÕ - §¹i häc Má ®Þa chÊt.
2. To¸n kinh tÕ - Häc viÖn Tµi chÝnh Hµ Néi.
3. Trần Tóc - Quy ho¹ch tuyÕn tÝnh §¹i häc Kinh tÕ quèc d©n -Hµ Néi 1998
4. Bµi gi¶ng gi¶i c¸c bµi to¸n tèi ­u vµ thèng kª trªn Excel- PGS.TS Bïi ThÕ
T©m - Phßng tèi ­u vµ ®iÒu khiÓn viÖn to¸n häc ViÖt Nam.
5. Hoàng Tuþ - Lý thuyết quy hoạch Tập I nhà xuất bản khoa học hà nội -
1968.