LỜI MỞ ĐẦU
Cùng với sự phát triển mạnh mẽ của khoa học kỹ thuật, các bài toán tối ưu
xuất hiện ngày càng nhiều và tính phức tạp của chúng ngày càng lớn. Phạm vi và
khả năng ứng dụng của các bài toán tối ưu cũng ngày càng đa dạng và phong phó.
Lớp bài toán tối ưu quan trọng được nghiên cứu đầu tiên và được ứng dụng
nhiều nhất là bài toán quy hoạch tuyến tính (linear programming). Đó là mô hình
toán học của một lớp rộng lớn các bài toán ứng dụng trong kinh tế và kỹ thuật. Do
đó cấu trúc của lớp bài toán quy hoạch tuyến tính có nhiều tính chất rất tốt về mặt
toán học, người ta đã tìm được các thuật giải rất hữu hiệu cho bài toán này. Năm
1947 nhà toán học Mỹ G.B. Dantzig đã nghiên cứu và đề xuất ra thuật toán đơn
hình (simplex method) để giải bài toán quy hoạch tuyến tính. Thuật toán đơn hình
được phát triển mạnh mẽ trong những năm sau đó và được xem là một phương
pháp kinh điển để giải các bài toán quy hoạch tuyến tính. Đây là một phương pháp
được sử dụng có thể nói là rộng rãi nhất. Có ba lý do chính:
Một là: Rất nhiều vấn đề thực tế, trong nhiều lĩnh vực khác nhau có thể đưa
về bài toán quy hoạch tuyến tính.
Hai là: Trong nhiều phương pháp giải các bài toán phi tuyến, bài toán tuyến
tính xuất hiện nh là một bài toán phụ cần phải giải trong nhiều bước lặp.
Ba là: Phương pháp đơn hình là phương pháp hiệu quả để giải bài toán quy
hoạch tuyến tính.
Ngày nay, bằng thuật toán đơn hình và các dạng cải biên của chúng, người ta
có thể giải rất nhanh các bài toán QHTT cỡ lớn.
Lớp các bài toán vận tải là trường hợp đặc biệt của quy hoạch tuyến tính, bởi
vậy có thể dùng các phương pháp của quy hoạch tuyến tính để giải. Tuy nhiên, do
tính chất đặc thù riêng của nó, người ta xây dựng các phương pháp giải riêng.
Thông thường khi nói đến bài toán vận tải ta thường liên hệ ngay đến bài toán
vận tải hai chỉ số, bởi đây là bài toán vận tải kinh điển có những phương pháp giải
hay. Bên cạnh đó, người ta còn xét mét sè các bài toán vận tải mở rộng như bài
Trang: 79

toán vận tải ba chỉ số, bài toán vận tải khoảng, bài toán vận tải đa mục tiêu và
rất nhiều bài toán khác, đó là các biến thể của bài toán vận tải kinh điển trên.
Trong khuôn khổ khoá luận này, em xem xét và nghiên cứu mét sè bài toán
mở rộng trong lớp các bài toán vận tải mở rộng đó. Đó là các bài toán: Bài toán
vận tải ba chỉ số (solid transport problem) không hạn chế và có hạn chế khả năng
thông qua, Bài toán vận tải ba chỉ số khoảng (interval solid transport problem)và
giới thiệu mét sè Bài toán vận tải đa mục tiêu.
Cuối cùng, em xin bày tỏ lòng biết ơn sâu sắc nhất đối với thày giáo hướng
dẫn Thạc sỹ Vò Tiến Việt, người đã tận tình chỉ bảo, giúp đỡ em trong quá trình
hoàn thành khoá luận này. Em còng xin chân thành cảm ơn sự giúp đỡ nhiệt tình
của các thầy cô trong khoa Toán - Tin, Học viện An ninh Nhân dân.














CHƯƠNG I. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
Trong việc nghiên cứu các bài toán tối ưu nói chung, giải tích lồi giữ mét vai
trò rất quan trọng. Nó được sử dụng làm cơ sở toán học trong việc xây dựng các
thuật toán.
Quy hoạch tuyến tính là mét trong những lớp bài toán tối ưu được nghiên cứu

trọng vẹn cả về phương diện lý thuyết lẫn thực hành, Bài toán vận tải là một dạng
Trang: 2

đặc biệt của QHTT. Do đó chương này nhằm giới thiệu mét sè khái niệm và
kiến thức cơ bản về giải tích lồi và QHTT.
1. 1 Một số khái niệm về giải tích lồi
1. 1. 1 Không gian Euclude
Mét vector n chiều trên trường số thực là mét bé được sắp thứ tự gồm n số
thực x = (x
1
, x
2
, , x
n
). Các x
i
, i =1, , n gọi là các thành phần hay toạ độ của
vector. Ví dụ x=(4,5,10,20).
Hai vectơ x và y gọi là bằng nhau x=y, nếu x
i
= y
i
, ∀i =1, , n.
Xét hai phép toán trên các vector:
Phép cộng: x + y = (x
1
+ y
1
, x
2

+ y
2
, , x
n
+ y
n
)
Phép nhân: αx=(αx
1
, αx
2
, , αx
n
), ∀α∈ R
Khi đó tập hợp tất cả các vector n chiều trong đó xác định phép cộng các
vector, nhân mét số thực với vector như trên tạo thành không gian tuyến tính n
chiều trên trường số thực R, ký hiệu R
n
.
Các vector x
(i)
∈R
n
, i =1, , m được gọi là độc lập tuyến tính nếu:
Nếu: với Ýt nhất mét α
i
≠ 0 thì x gọi là tổ hợp tuyến tính của các
x
(i)
, i =1, , m. Hơn nữa nếu α

i
> 0, i =1, , m và thì x gọi là tổ hợp lồi của
các x
(i)
, i =1, , m.
Trong R
n
có n vector độc lập tuyến tính lập thành cơ sở của nú.
Giả sử e
(1)
, e
(2)
, , e
(n)
là một cơ sở của R
n
thì bất kỳ mét vector x ∈ R
n
đều là tổ
hợp tuyến tính của các vector e
(1)
, e
(2)
, , e
(n)
. Ta gọi tích vô hướng của hai vector x =
(x
1
, x
2

, , x
n
) và y = (y
1
, y
2
, , y
n
), ký hiệu, <x,y>, là một số bằng.
Tích vô hướng là một dạng song tuyến tính, đối xứng, không âm, tức là:
Trang: 3

1. <x,y> = <y, x>. ∀x, y ∈ R
n
2. <x
(1)
+ x
(2)
, y >=< x
(1)
, y >+< x
(2)
, y>. ∀x
(1)
, x
(2)
, y ∈ R
n
3. <λx,y> = λ<x,y>. ∀x, y ∈ R
n

4. <x,x> ≥ 0, ∀x∈ R
n
dấu bằng xẩy ra khi và chỉ khi x= 0.
Độ dài của vector x = (x
1
, x
2
, , x
n
) là một số xác định bởi.
Khoảng cách giữa hai vector x và y là một số xác định bởi:
Không gian vector trong đó có tích vô hướng và khoảng cách nh trên gọi là
không gian Euclude.
1. 1. 2 Tập compact
Dóy {x
(k)
}⊂R
n
k=1, 2, được gọi là có giới hạn x
(0)
khi k →∞ và viết
lim x
(k)
= x
(0)
, nếu
Hình cầu tâm a bán kính ρ là tập S={x∈R
n
:x - a≤ρ}. Hình cầu này tạo
nên ρ- lân cận của điểm a, hay gọi là lân cận của a.

* Nếu tập A⊂R
n
chứa cùng với điểm x mét lân cận của nó thì x gọi là điểm
trong của A. Nếu trong lân cận bất kỳ của x ∈ A có các điểm của A và các điểm
không thuộc A thì x gọi là điểm biên của tập hợp A.
* Một tập A⊂R
n
gọi là giới nội nếu nó được chứa trong mét hình cầu tâm O
nào đó, tức là tồn tại sè ρ đủ lớn sao cho với mọi x∈A,x≤ρ. Một dóy {x
(k)
} hội tụ
thì bao giờ cũng giới nội.
* Một tập hợp G⊂R
n
được gọi là mở nếu với mọi x∈G đều tồn tại một hình
cầu tâm x nằm gọn trong G. Một tập F⊂R
n
được gọi là đóng nếu với mọi dãy hội
tụ{x
(k)
}⊂ F ta đều có:
Trang: 4

Một tập chứa mọi điểm biên của nú là tập đóng.
*Tập C được gọi là tập Compact nếu từ mọi dãy vô hạn {x
(k)
} thuộc C đều có
thể trích ra một dóy con {x
(ki)
} hội tụ tới phần tử thuộc C. Tập C là Compact khi và

chỉ khi C đóng và giới nội. Tập Compact M của tập đóng C còng đóng trong C.
Tập con đóng M của tập Compact còng Compact.
Hàm f(x) liên tục trên tập Compact C thì sẽ đạt cực trị trên tập Êy.
1. 1. 3 Tập lồi
Cho hai điểm a, b ∈R
n
. Ta gọi đường thẳng qua a, b là tập điểm có dạng
x∈R
n
: x = λa + (1-λ)b, λ∈ R.
Đoạn thẳng nối hai điểm a, b là tập lồi các điểm có dạng
x∈R
n
: x = λx + (1-λ)y, 0 ≤λ≤ 1
* Một tập M⊂R
n
được gọi là một đa tạp affine nếu với hai
điểm bất kỳ
x, y ∈M thì toàn bộ đường thẳng đi qua hai điểm đó cũng thuộc M.
Tức là λx + (1-λ)y ∈M : ∀x, y ∈M, ∀λ∈R.
* Một siêu phẳng trong không gian R
n
là tập hợp tất cả các
điểm
x = (x
1
, x
2
, , x
n

) ∈R
n
thỏa mãn phương trình tuyến tính
a
1
x
1
+ a
2
x
2
+ + a
n
x
n
= α trong đó a
1
, a
2
, , a
n
, α∈R
* Tập hợp các điểm x = (x
1
, x
2
, , x
n
) ∈R
n

thoản mãn bất phương trình tuyến
tính a
1
x
1
+ a
2
x
2
+ + a
n
x
n
≤α được gọi là nửa không gian đóng.
* Nửa không gian được cho bởi a
1
x
1
+ a
2
x
2
+ + a
n
x
n
< α được gọi là nửa
không gian mở.
* Tập X⊂R
n

được gọi là tập lồi nếu cùng với việc chứa hai điểm x, y nã chứa
cả đoạn thẳng chứa hai điểm Êy, tức là chứa tất cả các điểm có dạng:
λx + (1-λ)y, 0 ≤λ≤ 1
Ví dụ về các tập lồi: Không gian Euclide, các nửa không gian, mặt phẳng, nửa
mặt phẳng, hình chữ nhật, hình vuông, hình elip, hình hộp, hình cầu
Trang: 5

* Một tập hợp là giao của một số hữu hạn các nửa không gian đóng được gọi
là tập lồi đa diện.
Mệnh đề: Giao của hai tập lồi là một tập lồi.
Hệ quả 1. Giao của mét sè bất kỳ tập hợp lồi là tập lồi.
Hệ quả 2. Miền chứa nghiệm của một hệ bất phương trình tuyến tính dạng.
là một tập lồi (đa diện lồi). Mét tập lồi đa diện giới nội gọi là một đa diện.
Giao của tất cả các tập lồi chứa tập X gọi là bao lồi của nã, ký hiệu [X]
1. 1. 4 Hàm lồi
* Một hàm số f(x) xác định trên tập lồi C ⊂ R
n
được gọi là hàm lồi trên C, nếu
với mọi x, y ∈C và 0 ≤λ≤ 1 ta có f(λx + (1-λ)y) ≤λf(x) + (1-λ)f(y).
* Hàm f(x) được gọi là hàm lồi chặt nếu với mọi x, y ∈C và 0 ≤λ≤ 1 ta có.
f(λx + (1-λ)y) <λf(x) + (1-λ)f(y).
* Hàm f(x) được gọi là hàm lừm (lừm chặt) nếu - f(x) là hàm lồi (lồi chặt)
* Hàm f(x) xác định trên C đạt cực tiểu tuyệt đối tại x* ∈C
nếu
f(x
*
) ≤ f(x):∀ x∈C
* Hàm f(x) đạt cực tiểu địa phương tại x*∈ C nếu tồn tại lân cận mở U của x*
sao cho f(x*) ≤ f(x):∀ x∈C ∩U
Mệnh đề 1: Bất kỳ điểm cực tiểu địa phương nào của hàm lồi trên tập lồi cũng

là điểm cực tiểu tuyệt đối.
Hệ quả: Bất kỳ điểm cực đại địa phương nào của hàm lâm còng là cực đại
tuyệt đối.
Mệnh đề 2: Cực đại của một hàm lồi (nếu có) trên một tập lồi có điểm cực
biên bao giờ cũng đạt tại một điểm cực biên.
1. 2 Bài toán Quy hoạch tuyến tính
Trang: 6

QHTT bắt nguồn từ những nghiên cứu của nhà toán học Nga nổi tiếng, Viện
sỹ L.V. Kantorovich trong mét loạt các công trình về bài toán kế hoạch hoá sản
xuất, công bố năm 1938. Năm 1947 nhà toán học Mỹ G.B. Dantzig đã nghiên cứu
và đề xuất phương pháp đơn hình (Simplex method) để giải bài toán QHTT. Năm
1952 phương pháp đơn hình đã được chạy trên máy tính điện tử của Mỹ.
1. 2. 1 Bài toán quy hoạch tuyến tính
 Bài toán tổng quát.
Để nhất quán lập luận ta xét bài toán tìm cực đại, sau đó ta xét cách chuyển bài
toán tìm cực tiểu sang tìm cực đại. Bài toán tổng quát của QHTT có dạng:
Ký hiệu: A = (a
ij
)
mxn
là ma trận với các phần tử a
ij
(1.1) gọi là hàm mục tiêu, (1.2) là các rằng buộc.
Nếu gặp bài toán Min, tức là


Thì giữ nguyên ràng buộc và đưa về bài toán Max bằng
cách



Nếu bài toán Max có phương án tối ưu là x* thì bài toán min còng có phương
án là x* và f
min
=-

f
max
Thật vậy, vì x* là phương án tối ưu của bài toán Max nên ta có:



Chứng tỏ x* là phương án tối ưu của bài toán Min và


Người ta thường xét bài toán quy hoạch tuyến tính dưới hai dạng sau:
- Dạng chuẩn:





- Dạng chính tắc:





 Đưa bài toán QHTT về dạng chuẩn hoặc dạng chính tắc.
Bất kỳ QHTT nào cũng có thể đưa về mét trong hai dạng chuẩn hoặc chính

tắc nhờ các phép biến đổi tuyến tính sau:
i) Một ràng buộc


Có thể đưa về ràng buộc bằng cách nhân hai vế
với (-1) và viết lại
ii) Một ràng buộc đẳng thức


có thể thay bằng hai ràng buộc bất đẳng thức:
iii) Một biến x
j
không bị ràng buộc dấu có thể thay thế bởi hiệu của hai biến không
âm bằng cách đặt:
iv) Một ràng buộc bất đẳng thức

Trang: 8

Có thể đưa về ràng buộc đẳng thức bằng cách đưa vào biến phô y
i
≥ 0:


Về nguyên tắc, áp dụng nhiều lần các phép biến đổi (i), (ii) và (iii) ta có thể
đưa một bài toán QHTT bất kỳ về dạng chuẩn, sau đó áp dụng nhiều lần phép biến
đổi (iv) ta sẽ đưa nó về dạng chính tắc.
 Giải bài toán QHTT bằng phương pháp hình học.
Xét bài toán QHTT dưới dạng chuẩn với hai biến số:
Tõ ý nghĩa hình học ta biết rằng mỗi bất phương trình tuyến tính a
i1

x
1
+ a
i2
x
2
≤
b
i
xác
định một nửa mặt phẳng.
Nh vậy miền ràng buộc D được xác định nh là giao của
một nửa mặt phẳng và sẽ là một đa giác lồi trên mặt phẳng. Phương trình c
1
x
1
+
c
2
x
2
=
α
khi
α
thay đổi sẽ xác định trên mặt phẳng các đường thẳng song song với
nhau mà ta sẽ gọi là các đường mức (với giá trị mức
α
). Mỗi điểm ∈D sẽ
nằm trên một đường mức với mức

Bài toán đặt ra có thể phát biểu theo ngôn ngữ hình học như sau: trong số các
đường mức cắt tập D, hãy tìm đường mức với gía trị lớn nhất.
Nếu dịch chuyển song song các đường mức theo hướng vector
pháp tuyến của
chóng thì giá trị mức sẽ tăng, nếu dịch chuyển theo hướng ngược lại thì
giá trị mức sẽ giảm. Vì vậy để giải bài toán đặt ra, ta có thể tiến hành nh sau.
Bắt đầu từ mét đường mức cắt D, ta dịch chuyển song song các đường mức
theo hướng vector pháp tuyến (c
1
, c
2
) cho đến khi việc dịch chuyển tiếp theo làm
cho đường mức không còn cắt D nữa thì dừng. Điểm của D (có thể nhiều điểm)
nằm trên đường mức cuối cùng này sẽ là lời giải tối ưu cần tìm, còn giá trị của hàm
mục tiêu tại đó chính là giá trị tối ưu của bài toán.
Trang: 9

Ví dụ: Xét bài toán:
f(x)= 4x
1
+ 5x
2
→max
Xét đường mức: 4x
1
+ 5x
2
=10. Đường
mức này đi qua hai điểm (0,2) và (2.5,0). Ta có x*=(3,2), f
max

= 22







và x* là một đỉnh của D. Qua phương pháp hình học ta thấy rằng:
- Nếu quy hoạch tuyến tính có phương án tối ưu thì có Ýt nhất một đỉnh là tối
ưu. Sở dĩ nói Ýt nhất vì có trường hợp đường mức ở vị trí giới hạn trùng với một
cạnh của D thì tất cả các điểm trên cạnh này là phương án tối ưu, trong đó có hai
đỉnh.
- Nếu miền ràng buộc D giới nội và khác rỗng thì chắc chắn có phương án tối
ưu.
- Nếu miền ràng buộc không giới nội nhưng hàm mục tiêu bị chặn trên ở trên
miền ràng buộc thì cũng chắc chắn có phương án tối ưu.
1. 2. 2 Một số tính chất chung
Mệnh đề 1: Tập hợp tất cả các phương án của một bài toán QHTT là tập lồi.
Tập lồi D các phương án của một bài toán QHTT xác định bởi toàn bộ các
ràng buộc (1.2) và (1.3). Tập D có thể là rỗng, hoặc là một đa diện lồi hoặc là một
tập lồi đa diện không giới nội.
Nếu D là một đa diện lồi thì bài toán có phương án, hơn nữa giá trị tối ưu của
hàm mục tiêu trên đa diện lồi là hữu hạn và việc tìm phương án tối ưu đưa đến việc
Trang: 10

chọn các điểm của đa diện D có số đỉnh (điểm cực biên hay phương án cực
biên) hữu hạn.
Mệnh đề 2: Hàm mục tiêu của bài toán QHTT sẽ đạt Max tại điểm cực biên
của tập D. Nếu hàm mục tiêu không chỉ nhận Max tại một điểm cực biên của tập

lồi D mà tại nhiều điểm cực biên thì nó sẽ đạt giá trị cực đại tại những điểm là tổ
hợp lồi của các điểm đó.
Ký hiệu A
j
, j=1, , n là các vector cột của ma trận A.
Khi Êy hệ ràng buộc Ax = b có thể viết:
x
1
A
1
+ x
2
A
2
+ + x
n
A
n
=
b (1.4)

Mệnh đề 3: Nếu các vector A
1
, A
2
, , A
k
là độc lập tuyến tính và thoả mãn
x
1

A
1
+ x
2
A
2
+. . . + x
n
A
n
= b
trong đó x
j
>
0, j=1, . . . k thì điểm
x = (x
1
, x
2
, , x
k
,0, ,0)
là điểm cực biên của tập lồi đa diện D.
Mệnh đề 4: Nếu x = (x
1
, x
2
, , x
n
) là điểm cực biên của tập lồi đa diện D thì

các vector A
j
trong biểu diễn (1.4) ứng với các thành phần x
j
> 0 lập thành hệ độc
lập tuyến tính. Vì ma trận A có m dòng nên từ đây suy ra rằng điểm cực biên
không có quá m thành phần dương.
Các mệnh đề 3 và mệnh đề 4 có thể gộp lại thành một mệnh đề sau:
Mệnh đề 5: Để x = (x
1
, x
2
, x
n
) là phương án cực biên của QHTT dưới dạng
chính tắc thì cần và đủ là các vector cột A
j
của ma trận A ứng với các thành phần
x
j
> 0 là độc lập tuyến tính.
1. 2. 3 Phương pháp đơn hình giải bài toán QHTT
Cơ sở của
phương pháp này đươc G.B. Dantzig công bố năm 1947 có tên gọi là phương pháp
đơn hình. Sở dĩ có tên gọi nh vậy là vì những bài toán đầu tiên được giải bằng
phương pháp đó có các ràng buộc dạng:

và trong thực hành để kiểm tra điều kiện tối ưu của phương pháp cực biên x ta
chỉ cần kiểm tra
∆

k
≥ 0, ∀k∉J
(1. 18)
• Người ta có thể chứng minh rằng nếu bài toán không
thoái hoá thì (1.16) còng là điều kiện cần của tối ưu.
Định lý 1. 2: Nếu tồn tại một chỉ số k sao cho ∆
k
< 0 thì người ta có thể tìm
được Ýt nhất một phương án x’ mà đối với nã Z’ > Z
0
.
Công thức tìm phương án x’:
Nhân (1.10) với
θ
nào đó ta có:
Lấy (1.12) trừ đi (1.19) từng vế ta có:
Nếu các hệ số của các vector A
j
, j=1, , m và A
k
trong (1.20) không âm, khi đó ta
có một phương án mới x’ mà đối với nó hàm mục tiêu f có giá trị
Trong (1.12) tất cả các biến x
j
, j=1, , m đều dương. Vì vậy có thể tìm
được
θ
> 0 sao cho
Nếu đối với chỉ số k mà ∆
k

< 0, tồn tại z
jk
> 0, j∈J thì giá trị
θ
lớn nhất còn thoả mãn
(1.22) có thể xác định bởi hệ thức :


Nếu ta thay
θ
trong (1.20) và (1.21) bởi
θ
o
thì thành phần thứ r sẽ bằng 0:

Bài toán đặt ra là: xác định những đại lượng x
ij
cho mọi con đường (i,j) sao
cho tổng chi phí chuyên chở là nhỏ nhất với giả thiết là:
Tức là lượng hàng phát ra bằng đúng lượng hàng yêu cầu ở các điểm thu (điều
kiện cân bằng thu phát).
Dạng toán học của BTVT là:
Hệ rằng buộc (2.2), (2.3) có m + n phương trình, m x n Èn, tuy nhiên do (I)
nên bất kỳ phương trình nào trong m + n phương trình cũng là hệ quả của các
phương trình còn lại và có thể bỏ đi. Thật vậy, hệ rằng buộc có thể viết dạng (2. 5).
Giả sử ta cộng các phương trình từ thứ (m+1) tới thứ (m+n) rồi trừ đi tổng các
phương trình từ thứ (2) tới thứ (m) thì ta được phương trình thứ (1). Do đó số
phương trình cực đại của hệ (2.2), (2.3) không quá m + n-1.

- Nếu x

11
= b
1
thì ta xóa cột 1. Lập bảng mới có a’
1
= a
1
- x
11
. Tiếp tục quá trình,
bắt đầu từ ô (1,2).
Một lần phân phối như vậy ta được một tải lượng x
ij
> 0 và bá bít đi được một
hàng (hoặc cột) của bảng T. Bảng mới cuối cùng chỉ còn lại một ô (m, n) và do cân
bằng thu phát nên cực tiể đạt cả ở hàng, cả ở cột sau khi phân phối lượng còn lại.
Do đó ta xóa cả cột n và hàng m đi. Tổng số hàng và cột là m + n mỗi lần phân
phối bỏ đi được 1 hàng (hoặc cột), lần cuối cùng bỏ cả cột n và hàng m, nên
phương án thu được có không quá m + n - 1 ô sử dụng, không lập thành chu trình,
tức là có phương án cực biên.
 Phương pháp cước phí tối thiểu trong toàn bảng.
Quá trình biến đổi và phân phối hoàn toàn giống như phương pháp trên chỉ khác là
trong mỗi bước ta không chọn ô ở góc tây bắc mà chọn ô có cước phí nhỏ nhất
trong toàn bảng.
 Phương pháp cực tiểu cước phí theo hàng.
Bắt đầu từ hàng 1: Giả sử c
1s
= min c
ik
, k = 1, , n

Phân phối x
is
= min(a
1
, b
s
).
Nếu x
1s
= a
1
thì xóa dòng 1 rồi tiếp tục quá trình từ dòng 2, b’
s
= b
s
- x
1s
.

* Kiểm tra tối ưu: Nếu ∆
ijk
=( u
i
+ v
j
+ w
k
)- c
ijk
≤0 mọi ô (i,j,k)∈T thì dừng, bài

toán đã giải xong. Ngược lại chuyển sang bước điều chỉnh phương án.
* Điều chỉnh: Tìm ô (r,s,t) thoả mãn:
∆
rst
= max {∆
ijk
: (i,j,k) ∈T}>0
Tìm các hệ số: y
ijk
với (i,j,k) ∈T thoả
Xác định hằng số biến đổi:




T’=(T\ {e, f, g})u{(r, s, t)}
Quay trở lại bước thế vị
2. 2. 6 Ví dụ
Giải bài toán vận tải ba chỉ số không hạn chế khả năng thông qua cho bởi
bảng sau: m=3, n=4, l=3.
a=(11, 16,10), b=(7, 4, 13, 13), c=(6, 16, 15)


b
j
c
ijk
7 4 13 13
a
i


3 7 4 10





k
M

M M M M

M M M M M
M M 0 0 0

M M 0 0 0
M M 0 0 0
i = 2m + 1
2. 4. 3 Ví dụ
Xét bài toán (3x3x3) ISTP sau:
Lượng hàng cung cấp: A
1
= [29, 41], A
2
= [8, 23], A
3
= [16, 50]
Lượng nhu cầu: B
1
= [8, 17], B

2
= [14, 19], B
3
= [23, 32]
Lượng phương tiện vận chuyển: E
1
= [26, 41], E
2
= [7, 42], E
3
= [4, 30]
Chi phí:
k k kk
k k k
41
71 84
84 42 46
8 12 34
73 97 87 71 53 88 49 70 3

1. PGS. TS Bùi Thế Tâm, GS. TS Trần Vũ Thiệu - Các phương
pháp tối ưu hoá - Nhà xuất bản giao thông vận tải 1998.
2. Phạm Xuân Ninh - Luận án tiến sỹ - Các bài toán vận tải
nhiều chỉ số - 1978.
3. PGS. TS Bùi Minh Trí, PGS. TS Bùi Thế Tâm Giáo trình tối
ưu hoá - NXB Giáo thông vận tải - 1996.
4. Nguyễn Đức Nghĩa - Tối ưu hoá (Quy hoạch tuyến tính và
rời rạc) - NXB Giáo dục - 1997
5. Bùi Thế Tâm - Turbo Pascal (lý thuyết cơ bản, bài tập,
những chương trình mẫu trong khoa học kỹ thuật và kinh

doanh) - NXB Giao thông vận tải - 1995.
6. Fijmộnez, JL Verdegay - Uncertain Solid Transportion
Problem Fuzzy Sets and system.
7. V, Rajendra Prasad and K. P. K Nair Faculty of
Administration, University of New Brunswck
Fredricton, Canada. And Y.P. Aneja Faculty of
Administration, University of Windsor, Canada.
8. Gass S.I. Linear programming. Fifth Edition, New
York 1985.
9. Mét sè sách giới thiệu ngôn ngữ Lập trình C.





u[1]=0; v[1]=0;
for(i=2;i<=m;i++)
u[i]=xtv[i-1];
for(j=2;j<=n;j++)
v[j]=xtv[m+j-2];
for(k=1;k<=l;k++)
w[k]=xtv[m+n+k-2];
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
for (k=1;k<=l;k++)
if(Dvong[i][j][k]==1)
{
delta[i][j][k]=0;
}
else

{
tg=(u[i]+v[j]+w[k])-c[i][j][k];
delta[i][j][k]=tg;
}
}

//====================================================================
//====================================================================
void Tim_ y(int r, int s , int t, vtvong Dvong, vt y)
{
int i,j,k,i1,j1,mnl;
float s1;
mtran ah,a1;
vto bh,b1,x1;
mnl=m+n+l;
for(i=1;i<=m;i++)

tge21=tge21+(E2[k]-E1[k]);
tg=tgb21+tge21;
a[m]=tg;
for(j=1;j<=n1;j++)
b[j]=B1[j];
for(j=n1+1;j<=2*n1;j++)
{
tg=B2[j-n1]-B1[j-n1];
b[j]=tg;
}
for(i=1;i<=m1;i++)
tga2=tga2+A2[i];
for(j=1;j<=n1;j++)

tgb1=tgb1+B1[j];
tg=tga2-tgb1+tge21;
b[n]=tg;
for(k=1;k<=l1;k++)
e[k]=E1[k];
for(k=l1+1;k<=2*l1;k++)
{
tg=E2[k-l1]-E1[k-l1];
e[k]=tg;
}
for(k=1;k<=l1;k++)
tge1=tge1+E1[k];
tg=tga2+tgb21-tge1;
e[l]=tg;
/ / CHUYEN DOI VOI CAC CHI PHI
cprintf(" \r\nNhap chi phi ao (rat lon)M:=\r\n");
scanf("%f",&M);
for(i=1;i<=m1;i++)

c[i][n][k]=M;

}/ / for i
for(i=m1+1;i<=2*m1;i++)
{
for(j=1;j<=n1;j++)
{
for(k=1;k<=l1;k++)
c[i][j][k]=c1[i-m1][j][k];
for(k=l1+1;k<=2*l1;k++)
c[i][j][k]=c1[i-m1][j][k-l1];

c[i][j][l]=M;
}
for(j=n1+1;j<=2*n1;j++)
{
for(k=1;k<=l1;k++)
c[i][j][k]=c1[i-m1][j-n1][k];
for(k=l1+1;k<=2*l1;k++)
c[i][j][k]=c1[i-m1][j-n1][k-l1];
c[i][j][l]=0;
}
for(k=1;k<=l1;k++)
c[i][n][k]=M;
for(k=l1+1;k<=2*l1;k++)
c[i][n][k]=0;
}/ / for i
for(j=1;j<=n1;j++)
for(k=1;k<=n;k++)
c[m][j][k]=M;
for(j=n1+1;j<=n;j++)
{

tg=x[i][j][k]+x[m1+i][j][k]+x[i][j][l1+k]+x[i][j+n1][k]
+x[m1+i][n1+j][k]+x[m1+i][j][l1+k]+x[i][n1+j][l1+k];
xISTP[i][j][k]=tg;
}
cprintf(" \r\nNGHIEM CUA BAI TOAN ISTP LA:\r\n");
for(i=1;i<=m1;i++)
{
for (j=1;j<=n1;j++)
{

for(k=1;k<=l1;k++)
{
if (xISTP[i][j][k]>0)
{
cprintf(" \r\n x[%d,%d,%d]=%8.2f",i,j,k,xISTP[i][j][k]);
getch();
}
}
}
}
}

phụ lục 3. Module giải bài toán vận tải 3 chỉ số có hạn chế khả năng thông qua.
void RunL(int ml, int nl, int ll, vtm al, vtn bl, vtl el, vt cl, vt dl, vt xl)
{ int h;
char str[20];
float te,r,u,ep,gz;
int mt,nt, count;
arrT1 s;
arrT2 cs;
int i,j,nft,mft,mnt,n1t,m1t,kt,lt,lnt,lrt,n2t,m2t;
ep=float(0.0001);

for(j=1;j<=nl;j++)
for(k=1;k<=ll;k++)
{ h=(i-1)*ll*nl+(j-1)*ll+k;
s[mft][h]=cl[i][j][k];
s[i][h]=1; s[i][nft]=al[i];
s[ml+k][h]=1;s[ml+k][nft]=el[k];
s[ml+ll+h][h]=1;s[ml+ll+h][nft]=dl[i][j][k];

s[m1t+j][h]=1; s[m1t+j][nft]=bl[j];

}
s[mt+1][nt+1]=0;
for(i=1;i<=mnt;i++) cs[i]=i;
if(mt==m1t)
{ for(j=1;j<=nft;j++)
s[mft][j]=-s[mft][j];
}
else
{ for(j=1;j<=nft;j++)
{ r=0.0;
for(i=n1t;i<=mt;i++)
r=r+s[i][j];
s[mft][j]=gz*r-s[mft][j];
}
}
L1:
count=count+1;
// Tim cot xoay
kt=1;
r=s[mft][1];
for(j=2;j<=nt;j++)
{ if(s[mft][j]>r)
{ kt=j;

}
}
if(lt==0)
{cprintf(" Ham muc tieu khong bi chan");

goto Dung;
}
/ / Bien doi bang don hinh
r=1/s[lt][kt];
for(j=1;j<=nft;j++)
s[lt][j]=s[lt][j]*r;
for(i=1;i<=mft;i++)
{ if(i!=lt)
{ u=s[i][kt];
for(j=1;j<=nft;j++)
s[i][j]=s[i][j]-s[lt][j]*u;
}
s[i][kt]=-u*r;
}
s[lt][kt]=r;
// doi chi so cua bien co so va phi co so
lnt=lt+nt;
lrt=cs[lnt];
cs[lnt]=cs[kt];
cs[kt]=lrt;
if(lrt>=nt+n1t&&lrt<=nt+n2t)
{ cs[kt]=cs[kt]+mt-m1t;
for(i=1;i<=mft;i++)
s[i][kt]=-s[i][kt];
s[mft][kt]=s[mft][kt]-gz;
}
goto L1;
Dung:

mtieu=s[mt+1][nt+1];


cprintf(" \r\nNGHIEM CUA BAI TOAN STP LA:\n");
for(i=1;i<=ml;i++)
{
for (j=1;j<=nl;j++)
{
for(k=1;k<=ll;k++)
{
if (xl[i][j][k]>0)
{
printf(" \n x[%d,%d,%d]=%8.2f",i,j,k,xl[i][j][k]);
getch();
}
}
}
}
cprintf(" \n Gia tri ham muc tieu la: %8.2f",mtieu);
getch();
}

phụ lục 4. Kêt quả chương trình.
1. Bài toán vận tải hai chỉ số.
Kich thuoc vectoro:
m: = 3
n: = 1
l: = 4CAC VEC TO DU LIEU CUA BAI TOAN LA: CAC VEC TO
DU LIEU CUA BAI TOAN LA:
CAC VEC TO DU LIEU CUA BAI TOAN LA:
a[1]:= 20. 00 a[2]:= 45. 00 a[3]:= 55. 00
b[1]:= 120. 00

e[1]:= 30. 00 e[2]:= 25. 00 e[3]:= 40. 00 e[4]:= 25. 00
MA TRAN CHI PHI CUA BAI TOAN LA:

Kich thuoc vec to:
m: = 3
n: = 4
l: = 3CAC VEC TO DU LIEU CUA BAI TOAN LA: CAC VEC TO
DU LIEU CUA BAI TOAN LA:
CAC VEC TO DU LIEU CUA BAI TOAN LA:
a[1]:= 11. 00 a[2]:= 16. 00 a[3]:= 10. 00
b[1]:= 7. 00 b[2]:= 4. 00 b[3]:= 13. 00 b[4]:= 13. 00
e[1]:= 6. 00 e[2]:= 16. 00 e[3]:= 15. 00
MA TRAN CHI PHI CUA BAI TOAN LA:
*****************1*********************
3. 00 4. 00 10. 00
7. 00 7. 00 16. 00
4. 00 5. 00 8. 00
10. 00 15. 00 10. 00
*****************2*********************
20. 00 22. 00 1. 00
11. 00 1. 00 9. 00
3. 00 11. 00 2. 00
5. 00 1. 00 9. 00
*****************3*********************
4. 00 14. 00 17. 00
4. 00 20. 00 18. 00
7. 00 1. 00 4. 00
13. 00 12. 00 10. 00

NGHIEM CUA BAI TOAN STP LA:

x[1,1,1]= 6. 00
x[1,4,3]= 5. 00
x[2,1,3]= 1. 00
x[2,2,2]= 4. 00
x[2,3,3]= 3. 00

5. 00 17. 00 9. 00
11. 00 15. 00 6. 00
9. 00 10. 00 10. 00
3. 00 13. 00 7. 00
*****************2*********************
11. 00 25. 00 31. 00
8. 00 1. 00 2. 00
7. 00 1. 00 20. 00
8. 00 4. 00 4. 00
*****************3*********************
15. 00 21. 00 13. 00