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 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.
Đề tài: 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: vận tải ba chỉ số (solid transport problem), vận tải ba chỉ số khoảng (interval solid transport problem) giới thiệu một số bài vận tải số
80 trang |
Chia sẻ: lvcdongnoi | Lượt xem: 5406 | Lượt tải: 1
Bạn đang xem trước 20 trang tài liệ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 vận tải ba chỉ số (solid transport problem), vận tải ba chỉ số khoảng (interval solid transport problem), để xem tài liệu hoàn chỉnh bạn click vào nút DOWNLOAD ở trên
jk PyP =∑
∈),,(
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
Nếu h = h1 thì T’ = T. Nếu trái lại, gọi (e,f,g) là ô tại đó h2 đạt min, khi đó
T’ = T \ {(e,f,g)}∪{(r,s,t)}
- Quay trở lại bước tính các thế vị.
2.3.4 Ví dụ
Giải bài toán vận tải ba chỉ số có hạn chế khả năng thông qua như sau:
m=3, n=4, l=3.
a = (7, 7, 16), b = (1, 12, 9, 8), e = (3, 5, 22)
bj
cijk 1 12 9 8
ai
5 11 9 3
7 17 15 10 13
9 6 10 7
11 8 7 8
7 25 1 1 4
31 2 20 4
15 45 6 25
16 21 8 3 15
13 7 9 2
Ma trận có khả năng thông qua là:
1 3 2 1
1 5 2 1
1 5 2 1
1 3 3 2
1 5 4 2
1 5 4 2
1 3 2 3
1 3 4 5
1 3 2 6
Sử dụng chương trình tính toán ta có kết quả tính toán như sau:
bj
7 4 13 13
{ }
∈−
∈
=
∈−
∪∉
=
drst
rst
ijkijk
ijk
ijk
Ttsrhx
Ttsrh
x
Tkjihyx
tsrTkjix
x
),,(
),,(
),,(
),,(),,(
0'
'
nế
nế
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
ai
1
11
1 5
16 1
5 1
2
10 4
2 2 6
Gía trị của hàm mục tiêu là 125
2.4 Bài toán vận tải ba chỉ số khoảng(Interval Solid Transpotion Problem)
2.4.1 Phát biểu bài toán(ISTP)
Bài toán ISTP được phát biểu như sau:
Với các rằng buộc:
Trong đó: Ai = [ai1, ai2 ], i=1, ..., m; Bj = [bj1, bj2 ], j=1, ..., n, Ek = [ek1, ek2 ],
e=1, ..., l là các khoảng giá trị tương ứng lượng cung cấp, lượng nhu câu, khả
năng vận chuyển.
Quan hệ “= 1” được định nghĩa như sau:
Do đó, w = 1[a,b] khi và chỉ khi w và bài toán (2.22) có thể viết lại như sau:
∑∑∑
= = =
m
i
n
j
l
k
ijkijk xcMin
1 1 1
)22.2(
,,,0
,1,
,1,
,1,
1 1
1 1
1 1
1
1
1
∀≥
==
==
==
∑∑
∑∑
∑∑
= =
= =
= =
kjix
lkEx
njBx
miAx
ijk
m
i
l
j k
ijk
m
i
l
k
jijk
n
j
l
k
iijk
[ ] [ ] zwbazw defba =∈∃→←= :,1 ,
∑∑∑
= = =
m
i
n
j
l
k
ijkijk xcMin
1 1 1
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
Với các rằng buộc:
Bài toán ISTP có thể thực hiện được khi và chỉ khi A ∩ B ∩ C ≠∅ trong
đó.
Nhận xét: Bài toán ISTP là bài toán tổng quát hoá của bài toán STP với
điều kiện:
ai
1
= ai
2
, i=1, ..., m, bj1 = bj2 , j=1, ..., n, el1 = el2 , k=1, ..., l
2.4.2 Thuật toán
Giải bài toán ISTP thông qua việc đưa sang bài toán phụ STP bằng cách
thêm nguồn phát, thu, phương tiện vận tải phù hợp.
Theo cách đó bài toán m nguồn phát, n nguồn thu, l phương thức vận
chuyển được chuyển sang bài toán phụ STP như được trình bày trong Bảng 2.3,
và Bảng 2.4, mà có thể giải có hiệu quả cho bài toán chuẩn.
Bài toán phụ trong trường hợp này bao gồm 2m +1, nguồn phát, 2n +1
nguồn thu và 2l +1 phương thức vận chuyển. Trong số đó có 1 nguồn phát, 1
nguồn thu và 1 phương thức vận chuyển được gọi là “giả”. Chi phí trong bài
toán phụ được thể hiện ở Bảng 2.3.
Trong bài toán phụ, m rằng buộc đầu tiên ứng với mức độ cung cấp nhỏ
nhất của nguồn phát và chi phí vận chuyển tương ứng tới nguồn thu. Sau đó là m
rằng buộc biểu diễn lượng hàng cung cấp của các nguồn thêm vào nhưng không
cần thiết, do đó chi phí vận chuyển tương ứng tới nguồn thu giả bằng phương
thức vận chuyển giả nhận giá trị 0. Rằng buộc cuối thể hiện nguồn phát giả.
Tương tự, n rằng buộc đầu tiên ứng với lượng nhu cầu nhỏ nhất của các
nguồn thu và chi phí vận chuyển tương ứng từ nguồn phát giả với phương thức
)23.2(
,,,0
,1,
,1,
,1,
1 1
1 1
1 1
∀≥
=∈
=∈
=∈
∑∑
∑∑
∑∑
= =
= =
= =
kjix
lkEx
njBx
miAx
ijk
m
i
l
j
kijk
m
i
l
k
jijk
n
j
l
k
iijk
==
==
== ∑∑∑∑∑∑∑∑∑
=========
l
k
k
l
k
i
l
k
k
n
j
i
n
j
i
n
j
j
m
i
i
m
i
i
m
i
i eebbaa EEBBAA
1
2
1
1
11
2
1
1
11
2
1
1
1
,,,,,
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
vận chuyển giả nhận giá trị M, n rằng buộc tiếp theo thể hiện lượng yêu cầu của
nguồn phát giả bằng phương thức vận chuyển giả nhận giá trị 0. Rằng buộc tiếp
theo biểu thị nguồn thu giả.
Tiếp tục như vậy, l rằng buộc tương ứng khả năng vận chuyển nhỏ nhất, chi
phí vận chuyển từ nguồn phát giả tới nguồn thu giả nhận giá trị M, tiếp theo l
rằng buộc thể hiện khả năng vận chuyển khả năng vận chuyển của phương thức
vận chuyển thêm vào nhưng không cần thiết, do đó chi phí vận chuyển từ nguồn
phát giả đến nguồn thu giả nhận giá trị 0. Rằng buộc cuối cùng thể hiện phương
thức vận chuyển giả. Số lượng của nguồn phát giả, nguồn thu giả, phương thức
vận chuyển giả được cố định phần còn lại để bài toán được cân bằng.
Cuối cùng nghiệm x’ijk , i=1, ..., 2m +1, j=1, ..., 2n +1, k=1, ..., 2l +1 của
bài toán STP cần chuyển sang nghiệm xijk , i=1, ..., m, j=1, ..., n, k=1, ..., l của
bài toán ISTP như sau:
xijk = x’ijk + x’(m+i)jk + x’i(n+j)k + x’ij(l+k) + x’(m+i)(n+j)k + x’(m+i)j(l+k) + x’i(n+j)(l+k)
i=1, ..., m, j=1, ..., n, k=1, ..., l
Bảng 2.3: Bài toán phụ của bài toán ISTP:
với các rằng buộc:
∑∑∑
+
=
+
=
+
=
12
1
12
1
12
1
'
m
i
n
i
l
k
ijkijk xcMin
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
Bảng 2.4: Chi phí trong bài toán phụ:
k
c111 ... c11l c111 ... c11l M
... ... ... ... ... ... ...
c1≤ ... c1nl c1n1 ... c1nl M
c111 ... c11l c111 ... c11l M
... ... ... ... ... ... ...
c1≤ ... c1nl c1n1 ... c1nl M
M ... M M ... M M
i = 1
...
k
∑∑ ∑∑∑
∑∑
∑∑
∑∑ ∑∑∑
∑∑
∑∑
∑∑∑∑
∑∑
∑∑
+
=
+
= ===
+
+
=
+
=
−−
+
=
+
=
+
=
+
= ===
+
+
=
+
=
−−
+
=
+
=
==
+
=
+
=
+
+
=
+
=
−−
+
=
+
=
−−+=
+=−=
==
−+−=
+=−=
==
−+−=
+=−=
==
12
1
12
1 1
1
1
12
1
2'
)12(
12
1
12
1
12'
12
1
12
1
1
'
12
1
12
1 1
12
1
1
1
2
'
)12(
12
1
12
1
12'
12
1
12
1
1'
1
12
1
12
12
1
12
1
'
)12(
12
1
12
1
12'
12
1
12
1
1'
)(
2,1,
,1,
)(
2,1,
,1,
)()(
2,1,
,1,
m
i
n
j
l
k
k
n
j
jj
m
i
ilij
m
i
n
j
lklkijk
m
i
n
j
kijk
n
j
l
k
l
k
kk
n
j
j
m
i
ikni
m
i
l
k
njnjijk
m
i
l
k
jijk
l
k
kk
n
j
jj
n
j
l
k
jkm
n
j
l
k
mimiijk
n
j
l
k
iijk
ebba
ee
e
eeba
bb
b
eebb
aa
a
x
llkx
lkx
x
nnjx
njx
x
mmix
mix
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
cm11 ... cm1l cm11 ... cm1l M
... ... ... ... ... ... ...
cmn1 ... cmnl cmn1 ... cmnl M
cm11 ... cm1l cm11 ... cm1l M
... ... ... ... ... ... ...
ccn1 ... cmnl cmn1 ... cmnl M
M ... M M ... M M
i = m
k
c111 ... c11l c111 ... c11l M
... ... ... ... ... ... ...
c1≤ ... c1nl c1n1 ... c1nl M
c111 ... c11l c111 ... c11l 0
... ... ... ... ... ... ...
c1≤ ... c1nl c1n1 ... c1nl 0
M ... M 0 ... 0 0
i = m +1
...
k
cm11 ... cm1l cm11 ... cm1l M
... ... ... ... ... ... ...
cmn1 ... cmnl cmn1 ... cmnl M
cm11 ... cm1l cm11 ... cm1l 0
... ... ... ... ... ... ...
ccn1 ... cmnl cmn1 ... cmnl 0
M ... M 0 ... 0 0
i = 2m
k
M
... M M ... M M
... ... ... ... ... ... ...
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
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: A1 = [29, 41], A2 = [8, 23], A3 = [16, 50]
Lượng nhu cầu: B1 = [8, 17], B2 = [14, 19], B3 = [23, 32]
Lượng phương tiện vận chuyển: E1 = [26, 41], E2 = [7, 42], E3 = [4, 30]
Chi phí:
k k k
41 71 84 84 42 46 8 12 34
73 97 87 71 53 88 49 70 3
16 7 20 84 42 95 50 26 49
i =1 i =2 i =3
Bài toán này có thể thực hiện được khi:
A ∩ B ∩ E = [53, 114] ∩ [37, 113] ∩ [53, 68] ≠ ∅
Bài toán có thể chuyển về bài toán phụ (7x7x7) STP sau:
Lượng cung cấp: a = (29, 8, 16, 12, 15, 34, 99)
Lượng nhu cầu: b = (8, 14, 23, 9, 5, 9, 145)
Lượng phương tiện vận chuyển: e = (26, 7, 4, 15, 35, 26, 100)
Chi phí vận chuyển:
k
41 71 84 41 71 84 M
73 97 87 73 97 87 M
16 7 20 16 7 20 M
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
41 71 84 41 71 84 M
73 97 87 73 97 87 M
16 7 20 16 7 20 M
M M M M M M M
i =1
k
84 42 46 84 42 46 M
71 53 88 71 53 88 M
84 42 95 84 42 95 M
84 42 46 84 42 46 M
71 53 88 71 53 88 M
84 42 95 84 42 95 M
M M M M M M M
i =2
k
8 12 34 8 12 34 M
49 70 3 49 70 3 M
50 26 49 50 26 49 M
8 12 34 8 12 34 M
49 70 3 49 70 3 M
50 26 49 50 26 49 M
M M M M M M M
i =3
k
41 71 84 41 71 84 M
73 97 87 73 97 87 M
16 7 20 16 7 20 M
41 71 84 41 71 84 0
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
73 97 87 73 97 87 0
16 7 20 16 7 20 0
M M M 0 0 0 0
i =4
k
84 42 46 84 42 46 M
71 53 88 71 53 88 M
84 42 95 84 42 95 M
84 42 46 84 42 46 0
71 53 88 71 53 88 0
84 42 95 84 42 95 0
M M M 0 0 0 0
i =5
k
8 12 34 8 12 34 M
49 70 3 49 70 3 M
50 26 49 50 26 49 M
8 12 34 8 12 34 0
49 70 3 49 70 3 0
50 26 49 50 26 49 0
0 0 0 0 0 0 0
i =6
k
M M M M M M M
M M M M M M M
M M M M M M M
M M M 0 0 0 0
M M M 0 0 0 0
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
M M M 0 0 0 0
M M M 0 0 0 0
i =7
Sau khi chuyển về bài toán STP, ta có kết quả sau: Nghiệm của bài toán
phụ STP là:
x[1,3,1] = 14.00, x[1,3,2] = 6.00, x[1,6,5] = 9.00, x[2,1,5] = 2.00, x[2,3,5] =
3.00, x[2,4,2] = 1.00, x[2,4,5] = 2.00, x[2,3,6] = 10.00, x[4,7,4] = 12.00,
x[5,5,7] = 3.00, x[5,7,5] = 12.00, x[6,2,3] = 4.00, x[6,4,1] = 6.00, x[6,7,4] =
3.00, x[6,7,5] = 5.00, x[6,7,6] = 16.00, x[7,5,5] = 2.00, x[7,7,7] = 97.00
Nghiệm của bài toán ISTP tương ứng là:
xISTP[1,3,1] = 14.00, xISTP[1,3,2] = 15.00, xISTP[2,1,2] = 5.00,
xISTP[2,3,2] = 3.00, xISTP[3,1,1] = 12.00, xISTP[3,2,3] = 14.00,
Giá trị hàm mục tiêu đạt được là: 803.
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
CHƯƠNG 3. GIỚI THIỆU MỘT SỐ BÀI TOÁN VẬN TẢI MỞ RỘNG
3.1 Bài toán sản xuất - vận tải
3.1.1 Phát biểu bài toán
Có một loại sản phẩm nào đó dự kiến được sản xuất ở m địa điểm A1, A2,
..., An. Biết rằng nếu địa điểm Ai sản xuất xi đơn vị sản phẩm thì tốn chi phí là
fi(xi). Sản phẩn sản xuất ra cần được vận chuyển tới n địa điểm tiêu thụ B1, B2,
..., Bn với nhu cầu tương ứng là b1, b2, ..., bn. Chi phí vận chuyển một đơn vị sản
phẩm từ địa điểm Ai tới địa điểm Bj được biết trước là cij. Cần lập một phương
án sản xuất và vận chuyển với tổng chi phí sản xuất và vận chuyển nhỏ nhất đảm
bảo thoả mãn nhu cầu của các nơi tiêu dùng bằng những sản phẩm làm ra được
ở tất cả các nơi sản xuất.
Ký hiều xi là khối lượng sản phẩm được sản xuất tại địa điểm Ai và xij là
khối lượng sản phẩm được chuyển từ địa điểm Ai đến Bj. Khi ấy dạng toán học
của bài toán sản xuất - vận tải là cực tiểu hàm chi phí.
với các điều kiện sau:
với
Chú ý: fi là hàm lõm, nghĩa là quy mô sản xuất càng mở rộng thì chi phí
sản xuất trên một đơn vị sản phẩm càng giảm.
3.1.2.Phương pháp giải .
Hàm mục tiêu của bài toán gồm hai thành phần: phần phi tuyến lõm (ứng
với chi phí sản xuất) và phần tuyến tính (ứng với chi phí vận chuyển). Vì số biến
Minxcxf
m
i
n
j
ijij
m
i
ii →+∑∑∑
= == 1 11
)(
∑
∑
∑
∑
=
=
=
=
=
=≤≤=∈=
==≥
==
==
n
j
j
m
i
ii
T
m
ij
m
i
jij
n
j
iij
bS
xSxxXxxx
njmix
njbx
mixx
1
1
1
1
1
0:),...,(
,1,,1,0
,1,
,1,
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
phi tuyến xi (m biến) tương đối nhỏ so với số biến tuyến tính xij (m.n biến), nên
để giải bài toán sử dụng kỹ thuật phân dã.
Tạm thời cố định các biến xi (mức sản xuất) ta có bài toán vận tải thông
thường, giải bài toán này ta thu được phương án vận chuyển tốt nhất ứng với
mức sản xuất đã chọn. Tiếp đó, ta kiểm tra xem các xi hiện có đã phải là tốt hay
chưa; nếu chưa, ta sẽ tìm cách chọn (nhờ giải một bài toán phi tuyến phụ) mức
sản xuất mới tốt hơn và lại giải bài toán vận tải ứng với mức sản xuất mới này,
.... Sau một số hữu hạn bước lặp ta sẽ thu được lời giải của bài toán.
Ký hiệu:
t, t là giá trị nhỏ nhất và lớn nhất của phần chi phí vận chuyển trong hàm
mục tiêu.
Giải bài toán quy hoạch sau đây để tìm mức sản xuất ban đầu:
Ký hiệu (t0,x(0)) là lời giải của bài toán (Q0). Đặt k=0
Bước lặp k ≥ 0. Giải bài toán vận tải:
ta thu được lời giải {xij(k) }và các thế vị tương ứng {ui(k), vj(k) }.
1) Nếu , dừng thuật toán: {xi(k), xij(k)} là lời giải của bài
toán
∑∑ == ijjjijjj cbtcbt maxmin v
tttXx
txfQ ii
≤≤∈
→+∑
,
min)()( 0
njmix
njbx
mixx
xc
ij
j
m
i
ij
k
i
n
j
ij
m
i
n
j
ijij
,1,,1,0
,1,
,1,
min
1
)(
1
1 1
==≥
==
==
→
∑
∑
∑∑
=
=
= =
k
m
i
n
j
k
ijijk txcl ≤=∑∑
= =1 1
)(
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
2) Nếu trái lại, ta có:
Ta đưa thêm vào bài toán phụ (Qk) một rằng buộc mới:
từ bất đẳng thức trước đó cho ta thấy x(k) vi phạm rằng buộc mới này và
nhận được bài toán mới (Qk+1)
Giải bài toán này, ta thu được lời giải (tk+1, x(k+1)). Chuyển sang bước lặp
mới k+1.
Chú ý: Các bài toán phụ (Qk) là bài toán tìm cực tiểu của một hàm lõm với
các rằng buộc tuyến tính, trong đó bài toán sau chỉ khác bài toán trước bởi một
rằng buộc mới thêm vào.
3.2 Bài toán vận tải đa mục tiêu
3.2.1 Phát biểu bài toán
Chi phí và thời gian tương xứng được xét trong bài toán vận tải hai mục
tiêu. Giả sử rằng với mỗi ô (i,j) có vài lựa chọn một cặp gồm chi phí cho một
đơn vị vận chuyển và thời gian vận chuyển. Mục đích là để liệt kê tất cả các
nghiệm hữu hiệu (không trội) trong việc làm cực tiểu tổng chi phí vận chuyển và
khoảng thời gian vận chuyển. Phương pháp tham số vận chuyển được sử dụng
cho mỗi ô (i,j) gồm tập các lựa chọn (cij, tij) tạo ra mối quan hệ tuyến tính giữa
cij và tij. Bài toán đối với cij trở thành từng bước đối với tij cho tất cả hoặc một số
ô (i,j) như là một trường hợp đặc biệt.
Lớp các bài toán vận tải thông thường là:
∑∑
= =
→
m
i
n
j
ijij xc
1 1
min
k
n
j
j
k
j
m
i
k
j
k
ik tbvxul >+= ∑∑
== 1
)(
1
)()(
0
1
)(
1
)()( ≤++− ∑∑
==
n
j
j
k
j
m
i
k
j
k
i bvxut
ksbvxut
tttXx
MintxfQ
n
j
j
s
j
m
i
s
j
s
i
m
i
iik
,0,0
,
)()(
1
)(
1
)()(
1
1
=≤++−
≤≤∈
→+
∑∑
∑
==
=
+
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
Ngoài ra, thời gian vận chuyển cũng rất quan trọng, đặc biệt là trong
trường hợp chất lượng sản phẩm có thể bị suy giảm hoặc có yêu cầu về thời gian
đối với hàng hoá đó. Giả sử tij là thời gian yêu cầu vận chuyển từ điểm phát i tới
điểm thu j. Chúng ta coi thời gian vận chuyển là không phụ thuộc vào tổng số
hàng hoá được vận chuyển và vận chuyển bấy kỳ từ điểm phát nào tới bất kỳ
điểm thu nào đều bắt đầu tại một thời điểm là 0.
Ngoài mục đích cực tiểu cước phí, bài toán còn phải đòi hỏi giảm thời gian
vận chuyển trong suốt quá trình vận chuyển. Gọi thời gian này là “khoảng thời
gian vận chuyển”. Về toán học tương xứng với bài toán:
Đôi khi cũng có sự tương xứng giữa thời gian vận chuyển và chi phí vận
chuyển trên một đơn vị hàng hoá cij, như trong trường hợp tij cũng là biến quyết
định. Bài toán này xét cực tiểu vector (khoảng thời gian vận chuyển, tổng chi
phí vận chuyển) trên tất cả các điểm hữu hiệu tij và xij. Mục đích của bài toán là
tìm tất cả những điểm hữu hiệu.
3.2.2 Lập phương trình toán học
Gọi cij(t) là chi phí trên một đơn vị hàng hoá vận chuyển từ nguồn phát i tới
nguồn thu j khi t là thời gian vận chuyển tương ứng với cặp điểm đó. Giả sử
)1.3(
;0,
,1;,1,0
,1,
,1,
1 1
1
1
=>
==≥
==
==
∑ ∑
∑
∑
= =
=
=
m
i
n
j
jiji
ij
m
i
jij
n
j
iij
baba
njmix
njbx
miax
)2.3(
)0:( ≥ijxij
ijtMaxMinimise
)3.3(
:
:
)(
>+
≤≤+
=
ijijijij
ijijijij
ij
stdsp
strdtp
tc
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
rằng đối với mỗi ô (i,j) cho quan hệ tuyến tính cij(t) như sau:
Trong đó pij, dij, sij và rij là hằng số, 0 ≤ rij ≤ sij.
Nhận xét:
Đối với mỗi ô (i,j): pij ≥ 0 thì cij(t) là các hằng số hoặc là giảm một cách
tuyến tính khi t tăng từ rij đến sij.
Ta không thể vận chuyển hàng từ điểm phát i tới điểm thu j trong suốt thời
gian nhỏ hơn rij.
Lập phương trình toán học:
với tij ≥ rij ∀(i,j) và cij(t) cho bởi (3.2)
Đặt
T = {(t11, ..., t1n, ..., t21, ..., t2n, ..., tm1, ...,tmn): tij ≥ rij∀ (i,j)}
Bài toán được viết lại như sau:
Đặt trên các ô (t,x) ∈ T x
K.
Tập Z được gọi là không gian chuẩn của bài toán.
Nghiệm của bài toán P là liệt kê tất cả những điểm hữu hiệu thuộc Z và tìm
sự tương ứng của nó trên T x K.
3.2.3 Trường hợp rời rạc
Trường hợp rời rạc của bài toán. Bài toán vận tải có nhiều phương thức vận
chuyển khác nhau như vận chuyển bằng đường sắt, đường không, ... đối với mỗi
cặp điểm bất kỳ. Mỗi phương thức vận chuyển bao hàm thời gian vận chuyển và
chi phí vận chuyển trên một đơn vị hàng hoá.
Giả sử uij là số các phương thức vận chuyển từ nguồn phát i tới nguồn thu j.
Gọi k là một trong các phương thức vận chuyển đó, khi đó ta có thời gian vận
chuyển là tijk và chi phí vận chuyển trên một đơn vị hàng hoá là cij.
{ }
∑∑
= =
>
m
i
n
j
ijijijij
xji
xtctMaxMin
ij 1 10:),(
)(,
{ } ∑∑
= =
>
==
m
i
n
j
ijijijij
xji
xtcztMaxz
ij 1 1
20:),(1
)(,
( )
∀≥=== ∑∑
==
),(0;::...,,...,,...,,...,,...,,
11
1221111 jixbxaxxxxxxxK ij
n
j
jij
m
i
iijmnmnn
)(),( 21),( PzzMinKxt ∈
{ }
=== ∑∑
= =
>
m
i
n
j
ijijijij
xji
xtcztMaxzzzZ
ij 1 1
20:),(121
)(,:),(
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
Đặt Gij là tập hợp các phương thức vận chuyển, tức là Gij = {1, 2, ..., uij}
tương ứng với ô (i,j).
Nếu (tijh, cijh) < (tijk, cijk) với h, k ∈ Gij thì ta nói k là phương thức vận
chuyển trội.
Trong ngữ cảnh của bài toán cực tiểu vector khoảng thời gian vận chuyển
và tổng chi phí vận chuyển thì việc làm trội các phương thức vận chuyển không
liên quan đến nhau. Bởi vậy không mất tính tổng quát ta không làm trội các
phương thức vận chuyển với bất kỳ ô (i,j). Bài toán được viết như sau:
với các rằng buộc:
Giải bài toán sẽ liệt kê được tất cả các nghiệm hữu hiệu.
{ }
∑∑∑
= = ∈
>
m
i
n
j
ijkijk
Gk
ijk
xkji
xctMaxMin
ij
ijk 1 10:),,(
,
∀>
==
==
∑ ∑
∑ ∑
= ∈
= ∈
jix
njbx
miax
ijk
m
i Gk
jijk
n
j Gk
iijk
ij
ij
,,0
,1,
,1,
1
1
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
KẾT LUẬN
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ú.
Trong nghành công an có rất nhiều bài toán có thể đưa về BTVT hoặc
chuyển hoá thành một trong những lớp của BTVT. Như bài toán phân việc (một
dạng đặc biệt của BTVT hai chỉ số). Nội dung như sau: Có n người và n công
việc, để giao cho người i thực hiện công việc j cần một chi phí cij. Vấn đề là cần
phân cho người nào làm việc gì sao cho tổng chi phí là nhỏ nhất, và bài toán sản
xuất - vận tải (đã nêu ở Chương 3). Bài toán này có thể áp dụng tính phương án
tối ưu trong việc sản xuất - vận chuyển để cấp phát quân trang giữa các nhà máy
may của Bộ và các đơn vị cần được cấp phát quân trang ...
Nếu đi hết tất cả các vấn đề của Lý thuyết BTVT thì đó là một khối lượng
kiến thức rất khổng lồ, các vấn đề ứng dụng của BTVT cũng rất nhiều, rất phong
phú và đa dạng. Tuy nhiên, thời gian và khuôn khổ của khoá luận, nên những
kết quả đạt được vẫn chưa đầy đủ và có thể có sai sót. Khoá luận mới dừng lại
trên mô hình lý thuyết, chưa có những chứng minh bằng số liệu thực tế. Mặc dù
vậy, kết quả đạt được cũng đã phần nào góp phần làm sáng tỏ những tính chất
cơ bản của BTVT và các ứng dụng của nó.
Rất mong được sự đóng góp ý kiến quý báu của các thầy cô giáo, các bạn
và người sử dụng để khoá luận hoàn thiện hơn.
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
TÀI LIỆU THAM KHẢO
1. PGS.TS Bùi Minh Trí - Quy hoạch toán học - Nhà xuất bản Khoa học kỹ
thuật Hà Nội 2001.
2. 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.
3. 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.
4. 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.
5. 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
6. 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.
7. Fijménez, JL Verdegay - Uncertain Solid Transportion Problem Fuzzy Sets
and system.
8. 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.
9. Gass S.I. Linear programming. Fifth Edition, New York 1985.
10. Một số sách giới thiệu ngôn ngữ Lập trình C.
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
PHỤ LỤC
Phụ lục 1. Module giải bài toán vận tải 3 chỉ số không hạn chế khả năng
thông qua.
#define MAX1 10
#define MAX2 10
#define MAX3 10
#define MAX 30
#define epsilon 0.00001
//==================================================================
==
//==================================================================
==
typedef float vt[MAX1][MAX2][MAX3];
typedefint vtvong[MAX1][MAX2][MAX3];
typedeffloat vtm[MAX1];
typedeffloat vtn[MAX2];
typedeffloat vtl[MAX3];
typedef float mtran[MAX][MAX];
typedef float vto[MAX];
//==================================================================
==
//==================================================================
==
void Nhap(vt c,vtm a,vtn b,vtl e)
{
int i,j,k;
float tg,tonga,tongb,tonge;
Nhap:
cprintf("\r\nVao kich thuoc vec to:");
cprintf("\r\n m:=");cscanf("%d",&m);
cprintf("\r\n n:=");cscanf("%d",&n);
cprintf("\r\n l:=");cscanf("%d",&l);
tonga=0; tongb=0; tonge=0;
cprintf("\r\n");
for(i=1;i<=m;i++)
{
cprintf(" a[%d]:=",i);
cscanf("%f",&tg);
cprintf("\r\n");
a[i]=tg;
tonga=tonga+tg;
}
cprintf("\r\n");
for(j=1;j<=n;j++)
{
cprintf(" b[%d]:=",j);
cscanf("%f",&tg);
cprintf("\r\n");
b[j]=tg;
tongb=tongb+tg;
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
}
cprintf("\r\n");
for(k=1;k<=l;k++)
{
cprintf(" e[%d]:=",k);
cscanf("%f",&tg);
cprintf("\r\n");
e[k]=tg;
tonge=tonge+tg;
}
cprintf("\r\n");
if(tonga!=tongb||tonga!=tonge||tongb!=tonge)
{
cprintf("BAI TOAN KHONG CO NGHIEM ! BAN NHAP LAI !");
goto Nhap;
}
cprintf("\r\n");
for (i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
for (k=1;k<=l;k++)
{
cprintf(" c[%d,%d,%d]:=",i,j,k);
cscanf("%f",&tg);
c[i][j][k]=tg;
cprintf("\r\n");
}
cprintf("\r\n");
}
}
//==================================================================
==
//==================================================================
==
void Taofile(vt c,vtm a,vtn b, vtl e)
{
int i,j,k;
FILE *fp;
float *pc;
pc=(float*)c;
char tenfile[67];
lamlai:
cprintf("\r\n VAO TEN FILE DE LUU BT STP:");
cscanf("%s",&tenfile);
fp=fopen(tenfile,"wb");
if(fp==NULL)
{
cprintf("\r\n Loi mo tep !");
goto lamlai;
}
Nhap(c,a,b,e);
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
Sua(m,n,l,c,a,b,e);
fwrite(&m,sizeof(int),1,fp);
fwrite(&n,sizeof(int),1,fp);
fwrite(&l,sizeof(int),1,fp);
/* Ghi cac phan tu cua ma tran*/
for (i=1;i<=m;i++)
for(j=1;j<=n;j++)
for (k=1;k<=l;k++)
{
fwrite((pc+i*MAX2*MAX3+j*MAX3+k),sizeof(float),1,fp);
}
for(i=1;i<=m;i++)
fwrite(&a[i],sizeof(float),1,fp);
for(j=1;j<=n;j++)
fwrite(&b[j],sizeof(float),1,fp);
for(k=1;k<=l;k++)
fwrite(&e[k],sizeof(float),1,fp);
fclose(fp);
}
//==================================================================
==
//==================================================================
==
void Ghifile(vt c,vtm a,vtn b, vtl e,vt x)
{
int i,j,k;
FILE *fp;
char tenfile[67];
lamlai:
cprintf("\r\n VAO TEN FILE DE LUU KET QUA BT STP:");
cscanf("%s",&tenfile);
fp=fopen(tenfile,"wt");
if(fp==NULL)
{
cprintf("\r\n Loi mo tep !");
goto lamlai;
}
fprintf(fp,"\nVao kich thuoc vec to:");
fprintf(fp,"\n m:=%d",m);
fprintf(fp,"\n n:=%d",n);
fprintf(fp,"\n l:=%d",l);
fprintf(fp,"\r\nCAC VEC TO DU LIEU CUA BAI TOAN LA:\n\r");
for(i=1;i<=m;i++)
{
fprintf(fp,"a[%d]:=%8.2f ",i,a[i]);
}
fprintf(fp,"\n");
for(j=1;j<=n;j++)
{
fprintf(fp,"b[%d]:=%8.2f ",j,b[j]);
}
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
fprintf(fp,"\n");
for(k=1;k<=l;k++)
{
fprintf(fp,"e[%d]:=%8.2f ",k,e[k]);
}
fprintf(fp,"\nMA TRAN CHI PHI CUA BAI TOAN LA\n:");
for(i=1;i<=m;i++)
{
fprintf(fp,"*****************%d*********************\n",i);
for(j=1;j<=n;j++)
{
for(k=1;k<=l;k++)
{
fprintf(fp,"%8.2f",c[i][j][k]);
}
fprintf(fp,"\n");
}
}
fprintf(fp,"\nNGHIEM CUA BAI TOAN STP LA:\n");
for(i=1;i<=m;i++)
for (j=1;j<=n;j++)
for(k=1;k<=l;k++)
if (x[i][j][k]>epsilon)
fprintf(fp,"\n x[%d,%d,%d]=%8.2f",i,j,k,x[i][j][k]);
fprintf(fp,"\r\nGIA TRI CUA HAM MUC TIEU LA:%8.2f",muctieu);
fclose(fp);
}
//==================================================================
==
//==================================================================
==
void Docfile(vt c,vtm a,vtn b,vtl e)
{
int i,j,k;
FILE *fp;
float *pc;
pc=(float*)c;
char tenfile[67];
lamlai1:
cprintf("\r\n ");
cprintf(" Vao ten file de doc chuoi so lieu ra:");
cscanf("%s",&tenfile);
fp=fopen(tenfile,"rb");
if(fp==NULL)
{
cprintf("\r\n Tep khong ton tai !");
getch();
goto lamlai1;
}
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
fread(&m,sizeof(int),1,fp);
fread(&n,sizeof(int),1,fp);
fread(&l,sizeof(int),1,fp);
/* Doc cac phan tu */
for (i=1;i<=m;i++)
for(j=1;j<=n;j++)
for (k=1;k<=l;k++)
{
fread((pc+i*MAX2*MAX3+j*MAX3+k),sizeof(float),1,fp);
}
for(i=1;i<=m;i++)
fread(&a[i],sizeof(float),1,fp);
for(j=1;j<=n;j++)
fread(&b[j],sizeof(float),1,fp);
for(k=1;k<=l;k++)
fread(&e[k],sizeof(float),1,fp);
fclose(fp);
cprintf("\r\n DU LIEU CUA BAI TOAN STP DOC DUOC LA:");
Hienthi(m,n,l,c,a,b,e);
}
//==================================================================
==
//==================================================================
==
void PA_DAU(int m,int n,int l,vtm a,vtn b,vtl e,vt x,vtvong Dvong)
{
vtm a11;vtn b11;vtl e11;
int i,j,k,i1,j1,k1,i0,j0,k0;
for(i=1;i<=m;i++) a11[i]=a[i];
for(j=1;j<=n;j++) b11[j]=b[j];
for(k=1;k<=l;k++) e11[k]=e[k];
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
for(k=1;k<=l;k++)
{
x[i][j][k]=-1;
Dvong[i][j][k]=0;
}
}
for(i=1;i<=m;i++)
{
for(j=1;j<=n;j++)
{
for(k=1;k<=l;k++)
{
if (x[i][j][k]<0)
{
if (a11[i]<=b11[j] &&a11[i]<=e11[k])
{
x[i][j][k]=a11[i];
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
Dvong[i][j][k]=1;
b11[j]=b11[j]-a11[i];
e11[k]=e11[k]-a11[i];
a11[i]=0;
i0=i;
for(j1=1;j1<=n;j1++)
{
for(k1=1;k1<=l;k1++)
{
if(x[i0][j1][k1]<0)
x[i0][j1][k1]=0;
}
}
}
if (b11[j]<a11[i] && b11[j]<=e11[k])
{
x[i][j][k]=b11[j];
Dvong[i][j][k]=1;
a11[i]=a11[i]-b11[j];
e11[k]=e11[k]-b11[j];
b11[j]=0;
j0=j;
for(i1=1;i1<=m;i1++)
{
for(k1=1;k1<=l;k1++)
{
if(x[i1][j0][k1]<0)
x[i1][j0][k1]=0;
}
}
}
if (e11[k]<b11[j] && e11[k]<a11[i])
{
x[i][j][k]=e11[k];
Dvong[i][j][k]=1;
b11[j]=b11[j]-e11[k];
a11[i]=a11[i]-e11[k];
e11[k]=0;
k0=k;
for(i1=1;i1<=m;i1++)
{
for(j1=1;j1<=n;j1++)
{
if( x[i1][j1][k0]<0)
x[i1][j1][k0]=0;
}
}
}
}
}
}
}
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
cprintf("\r\n PHUONG AN DAU TIEN LA:\r\n");
for(i=1;i<=m;i++)
{
for (j=1;j<=n;j++)
{
for(k=1;k<=l;k++)
{
if (x[i][j][k]>0||Dvong[i][j][k]==1)
{
cprintf("\r\n x[%d,%d,%d]=%8.2f",i,j,k,x[i][j][k]);
}
}
}
}
getch();
}
//==================================================================
==//================================================================
====
void Householder(int m0,int n0,vto b1,mtran a1,vto x1)
{
int i,j,k;
float s,sb,alpha,beta,gama,gamab,tg;
vto v;
for(k=1;k<=n0;k++)
{
s=0;
for(i=k;i<=m0;i++)
{
v[i]=a1[i][k];
s=s+v[i]*v[i];
}
alpha=sqrt(s);
tg=a1[k][k];
if(tg>0)
{
alpha=-alpha;
}
beta=s-tg*alpha;
tg=tg-alpha;
v[k]=tg;
//thuc hien Hc doi voicac cot con lai cua ma tran a
for (j=k;j<=n0;j++)
{
s=0;
for(i=k;i<=m0;i++)
{
s=s+v[i]*a1[i][j];
}
gama=s/beta;
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
for(i=k;i<=m0;i++)
{
a1[i][j]=a1[i][j]-gama*v[i];
}
}
sb=0;
for(i=k;i<=m0;i++)
{
sb=sb+v[i]*b1[i];
}
gamab=sb/beta;
for(i=k;i<=m0;i++)
{
b1[i]=b1[i]-gamab*v[i];
}
}//for k
//Tinh nghiem
x1[n0]=b1[n0]/a1[n0][n0];
for(i=n0-1;i>=1;i--)
{
s=0;
for(j=i+1;j<=n0;j++)
{
s=s+a1[i][j]*x1[j];
}
x1[i]=(b1[i]-s)/a1[i][i];
}
}
//==================================================================
==
//==================================================================
==
void THE_VI(vt c,vtvong Dvong,int m,int n,int l,vt delta)
{
int i,j,k,i1,j1,mnl;
mtran atv;
vto btv,xtv;
vtm u;vtn v;vtl w;
float tg;
mnl=m+n+l;
//Ghep cac the vi
for(i1=1;i1<=mnl-2;i1++)
for(j1=1;j1<=mnl-2;j1++)
atv[i1][j1]=0;
i1=0;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
for (k=1;k<=l;k++)
if(Dvong[i][j][k]==1)
{
i1=i1+1;
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
if(i!=1) atv[i1][i-1]=1;
if(j!=1) atv[i1][m+j-2]=1;
atv[i1][m+n+k-2]=1;
btv[i1]=c[i][j][k];
}
Householder(mnl-2,mnl-2,btv,atv,xtv);
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++)
for (j=1;j<=n;j++)
for(k=1;k<=l;k++) y[i][j][k]=0;
for(j1=1;j1<=mnl-2;j1++)
for(i1=1;i1<=mnl;i1++)
a1[i1][j1]=0;
j1=0;
for(i=1;i<=m;i++)
for (j=1;j<=n;j++)
for(k=1;k<=l;k++)
if(Dvong[i][j][k]==1)
{
j1=j1+1;
a1[i][j1]=1;
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
a1[m+j][j1]=1;
a1[m+n+k][j1]=1;
}
for(i=1;i<=mnl;i++)
b1[i]=0;
b1[r]=1;
b1[s+m]=1;
b1[m+n+t]=1;
for(i=1;i<=mnl;i++)
{
for(j=1;j<=mnl-2;j++)
{
ah[i][j]=a1[i][j];
}
}
for(i=1;i<=mnl;i++)
bh[i]=b1[i];
Householder(mnl,mnl-2,bh,ah,x1);
j1=0;
for(i=1;i<=m;i++)
for (j=1;j<=n;j++)
for(k=1;k<=l;k++)
if(Dvong[i][j][k]==1)
{
j1=j1+1;
if(a1[i][j1]==1&&a1[m+j][j1]==1&&a1[m+n+k][j1]==1)
y[i][j][k]=x1[j1];
}
}
//==================================================================
==
//==================================================================
==
void GIAI(int m,int n,int l,vtm a,vtn b,vtl e, vt c,vt x)
{
int i,j,k,r,s,t,e0,f0,g0;
int lanlap;
float max,min,h;
vtvong Dvong;
vt delta,y,x1;
PA_DAU(m,n,l,a,b,e,x1,Dvong);
lanlap=0;
while(1)
{
lanlap=lanlap+1;
THE_VI(c,Dvong,m,n,l,delta);
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
max=delta[1][1][1];
r=1;s=1;t=1;
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
for(k=1;k<=l;k++)
if(delta[i][j][k]>max)
{
max=delta[i][j][k];
r=i;
s=j;
t=k;
}
if(max<=epsilon) goto Dung;
if(lanlap>100)
{
cprintf("BAI TOAN CHUA CHO NGHIEM TOI UU VONG LAP LON");
goto Dung;
}
Tim_y(r,s,t,Dvong,y);
// Xac dinh hang so bien doi
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
for(k=1;k<=l;k++)
if(y[i][j][k]>epsilon&&Dvong[i][j][k]==1)
{
min=x1[i][j][k]/y[i][j][k];
h=min;
e0=i;
f0=j;
g0=k;
}
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
for(k=1;k<=l;k++)
if(y[i][j][k]>epsilon &&Dvong[i][j][k]==1)
{
min=x1[i][j][k]/y[i][j][k];
if(min<h)
{
h=min;
e0=i;
f0=j;
g0=k;
}
}
// Dieu chinh phuong an
for(i=1;i<=m;i++)
for(j=1;j<=n;j++)
for(k=1;k<=l;k++)
if(Dvong[i][j][k]==1) x1[i][j][k]=x1[i][j][k]-h*y[i][j][k];
x1[r][s][t]=h;
Dvong[r][s][t]=1;
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
Dvong[e0][f0][g0]=0;
}//while
Dung:
for(i=1;i<=m;i++)
for (j=1;j<=n;j++)
for(k=1;k<=l;k++)
x[i][j][k]=x1[i][j][k];
cprintf("\r\n SO LAN LAP LA:%d",lanlap);
cprintf("\r\nNGHIEM CUA BAI TOAN STP LA:\n");
for(i=1;i<=m;i++)
{
for (j=1;j<=n;j++)
{
for(k=1;k<=l;k++)
{
if (x[i][j][k]>epsilon)
{
printf("\n x[%d,%d,%d]=%8.2f",i,j,k,x[i][j][k]);
getch();
}
}
}
}
}
Phụ lục 2. Module giải bài toán vận tải 3 chỉ số khoảng.
void ISTPphu(vtm a,vtn b,vtl e,vt c)
{
int i,j,k;
float M,tg,tgb21,tge21,tga2,tgb1,tge1;
m=2*m1+1;
n=2*n1+1;
l=2*l1+1;
//CHUYEN DOI VOI CAC RANG BUOC
tgb21=0;tge21=0;
tga2=0;tgb1=0;tge1=0;
for(i=1;i<=m1;i++)
a[i]=A1[i];
for(i=m1+1;i<=2*m1;i++)
{
tg=A2[i-m1]-A1[i-m1];
a[i]=tg;
}
for(j=1;j<=n1;j++)
{
tgb21=tgb21+(B2[j]-B1[j]);
}
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
for(k=1;k<=l1;k++)
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++)
{
for(j=1;j<=n1;j++)
{
for(k=1;k<=l1;k++)
c[i][j][k]=c1[i][j][k];
for(k=l1+1;k<=2*l1;k++)
c[i][j][k]=c1[i][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][j-n1][k];
for(k=l1+1;k<=2*l1;k++)
c[i][j][k]=c1[i][j-n1][k-l1];
c[i][j][l]=M;
}
for(k=1;k<=l;k++)
c[i][n][k]=M;
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
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++)
{
for(k=1;k<=l1;k++)
c[m][j][k]=M;
for(k=l1+1;k<=l;k++)
c[m][j][k]=0;
}
}
//==================================================================
==
//==================================================================
==
void ChuyenNghiem(int m1,int n1,int l1, vt x,vt xISTP)
{
int i,j,k;
float tg;
for(i=1;i<=m1;i++)
for(j=1;j<=n1;j++)
for(k=1;k<=l1;k++)
{
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];
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
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);
gz=100000;
//Nhap1(m,n,l,a,b,e,c,d);
nt=ml*nl*ll;
mt=ml*nl*ll+ml+ll+nl;
m1t=ml*nl*ll+ml+ll;
m2t=nl;
count=0;
mft=mt+1;
nft=nt+1;
mnt=mt+nt;
n1t=m1t+1;
n2t=m1t+m2t;
for(i=1;i<=mft;i++)
for(j=1;j<=nft;j++)
s[i][j]=0;
int k;
for(i=1;i<=ml;i++)
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];
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
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;
r=s[mft][j];
}
}
//Kiem tra dieu kien toi uu
if(r<=ep)
{goto Dung;
}
// Tim dong xoay
lt=0;
te=10E+20;
for(i=1;i<=mt;i++)
{ if(s[i][kt]>ep)
{r=s[i][nft]/s[i][kt];
if(r<te)
{ lt=i;
te=r;
}
}
}
if(lt==0)
{cprintf("Ham muc tieu khong bi chan");
goto Dung;
}
//Bien doi bang don hinh
r=1/s[lt][kt];
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
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:
int i1,j1,k1;
for(i1=1;i1<=ml;i1++)
for(j1=1;j1<=nl;j1++)
for(k1=1;k1<=ll;k1++)
xl[i1][j1][k1]=0;
for(j=1;j<=nt+2*mt-m1t;j++)
{ for(i=1;i<=mt;i++)
if(cs[nt+i]==j)
{ for(i1=1;i1<=ml;i1++)
for(j1=1;j1<=nl;j1++)
for(k1=1;k1<=ll;k1++)
{ h=(i1-1)*nl*ll+(j1-1)*ll+k1;
if(h==j) xl[i1][j1][k1]=s[i][nt+1];
}
}
}
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)
{
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
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:
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:
*****************1*********************
4.00 2.00 10.00 6.00
*****************2*********************
1.00 3.00 8.00 12.00
*****************3*********************
5.00 4.00 9.00 7.00
NGHIEM CUA BAI TOAN STP LA:
x[1,1,2]= 20.00
x[2,1,1]= 30.00
x[2,1,2]= 5.00
x[2,1,3]= 10.00
x[3,1,3]= 30.00
x[3,1,4]= 25.00GIA TRI CUA HAM MUC TIEU LA: 610.00
2. Bài toán vận tải 3 chỉ số không hạn chế khả năng thông qua.
Kich thuoc vec to:
m:=3
n:=4
l:=3CAC 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*********************
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
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
x[2,4,2]= 8.00
x[3,3,2]= 4.00
x[3,3,3]= 6.00GIA TRI CUA HAM MUC TIEU LA: 115.00
3. Bài toán vận tải 3 chỉ số có hạn chế khả năng thông qua.
Kich thuoc vec to:
m:=3
n:=4
l:=3CAC VEC TO DU LIEU CUA BAI TOAN LA:
a[1]:= 7.00 a[2]:= 7.00 a[3]:= 16.00
b[1]:= 1.00 b[2]:= 12.00 b[3]:= 9.00 b[4]:= 8.00
e[1]:= 3.00 e[2]:= 5.00 e[3]:= 22.00
MA TRAN CHI PHI CUA BAI TOAN LA
:*****************1*********************
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
45.00 8.00 7.00
6.00 3.00 9.00
25.00 15.00 2.00
MA TRAN HAN CHE CUA BAI TOAN LA
:*****************1*********************
1.00 1.00 1.00
3.00 5.00 5.00
2.00 2.00 2.00
1.00 1.00 1.00
*****************2*********************
1.00 1.00 1.00
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
3.00 5.00 5.00
3.00 4.00 4.00
2.00 2.00 2.00
*****************3*********************
1.00 1.00 1.00
3.00 3.00 3.00
2.00 4.00 2.00
3.00 5.00 6.00
NGHIEM CUA BAI TOAN STPL LA:
x[1,1,3]= 1.00
x[1,2,3]= 5.00
x[1,4,1]= 1.00
x[2,2,3]= 5.00
x[2,3,2]= 1.00
x[2,4,3]= 1.00
x[3,2,3]= 2.00
x[3,3,1]= 2.00
x[3,3,2]= 4.00
x[3,3,3]= 2.00
x[3,4,3]= 6.00GIA TRI CUA HAM MUC TIEU LA: 125.00
4. Bài toán vận tải 3 chỉ số khoảng.
Kich thuoc vec to:
m:=3
n:=3
l:=3CAC VEC TO DU LIEU CUA BAI TOAN ISTP LA:
a[1]:=[ 29.00 8.2f]a[2]:=[ 8.00 8.2f]a[3]:=[ 16.00 8.2f]
b[1]:=[ 8.00 8.2f]b[2]:=[ 14.00 8.2f]b[3]:=[ 23.00 8.2f]
e[1]:=[ 26.00 8.2f]e[2]:=[ 7.00 8.2f]e[3]:=[ 4.00 8.2f]
MA TRAN CHI PHI CUA BAI TOAN ISTP LA
:*****************1*********************
41.00 71.00 84.00
73.00 97.00 87.00
16.00 7.00 20.00
*****************2*********************
84.00 42.00 46.00
71.00 53.00 88.00
84.00 42.00 95.00
*****************3*********************
8.00 12.00 34.00
49.00 70.00 3.00
50.00 26.00 49.00
CAC VEC TO DU LIEU CUA BAI TOAN PHU STP LA:
a[1]:= 29.00 a[2]:= 8.00 a[3]:= 16.00 a[4]:= 12.00 a[5]:= 15.00
a[6]:= 34.00 a[7]:= 99.00
b[1]:= 8.00 b[2]:= 14.00 b[3]:= 23.00 b[4]:= 9.00 b[5]:= 5.00
b[6]:= 9.00 b[7]:= 145.00
e[1]:= 26.00 e[2]:= 7.00 e[3]:= 4.00 e[4]:= 15.00 e[5]:= 35.00 e[6]:=
26.00 e[7]:= 100.00
MA TRAN CHI PHI CUA BAI TOAN PHU STP LA
:*****************1*********************
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
41.00 71.00 84.00 41.00 71.00 84.00 100.00
73.00 97.00 87.00 73.00 97.00 87.00 100.00
16.00 7.00 20.00 16.00 7.00 20.00 100.00
41.00 71.00 84.00 41.00 71.00 84.00 100.00
73.00 97.00 87.00 73.00 97.00 87.00 100.00
16.00 7.00 20.00 16.00 7.00 20.00 100.00
100.00 100.00 100.00 100.00 100.00 100.00 100.00
*****************2*********************
84.00 42.00 46.00 84.00 42.00 46.00 100.00
71.00 53.00 88.00 71.00 53.00 88.00 100.00
84.00 42.00 95.00 84.00 42.00 95.00 100.00
84.00 42.00 46.00 84.00 42.00 46.00 100.00
71.00 53.00 88.00 71.00 53.00 88.00 100.00
84.00 42.00 95.00 84.00 42.00 95.00 100.00
100.00 100.00 100.00 100.00 100.00 100.00 100.00
*****************3*********************
8.00 12.00 34.00 8.00 12.00 34.00 100.00
49.00 70.00 3.00 49.00 70.00 3.00 100.00
50.00 26.00 49.00 50.00 26.00 49.00 100.00
8.00 12.00 34.00 8.00 12.00 34.00 100.00
49.00 70.00 3.00 49.00 70.00 3.00 100.00
50.00 26.00 49.00 50.00 26.00 49.00 100.00
100.00 100.00 100.00 100.00 100.00 100.00 100.00
*****************4*********************
41.00 71.00 84.00 41.00 71.00 84.00 100.00
73.00 97.00 87.00 73.00 97.00 87.00 100.00
16.00 7.00 20.00 16.00 7.00 20.00 100.00
41.00 71.00 84.00 41.00 71.00 84.00 0.00
73.00 97.00 87.00 73.00 97.00 87.00 0.00
16.00 7.00 20.00 16.00 7.00 20.00 0.00
100.00 100.00 100.00 0.00 0.00 0.00 0.00
*****************5*********************
84.00 42.00 46.00 84.00 42.00 46.00 100.00
71.00 53.00 88.00 71.00 53.00 88.00 100.00
84.00 42.00 95.00 84.00 42.00 95.00 100.00
84.00 42.00 46.00 84.00 42.00 46.00 0.00
71.00 53.00 88.00 71.00 53.00 88.00 0.00
84.00 42.00 95.00 84.00 42.00 95.00 0.00
100.00 100.00 100.00 0.00 0.00 0.00 0.00
*****************6*********************
8.00 12.00 34.00 8.00 12.00 34.00 100.00
49.00 70.00 3.00 49.00 70.00 3.00 100.00
50.00 26.00 49.00 50.00 26.00 49.00 100.00
8.00 12.00 34.00 8.00 12.00 34.00 0.00
49.00 70.00 3.00 49.00 70.00 3.00 0.00
50.00 26.00 49.00 50.00 26.00 49.00 0.00
100.00 100.00 100.00 0.00 0.00 0.00 0.00
*****************7*********************
100.00 100.00 100.00 100.00 100.00 100.00 100.00
100.00 100.00 100.00 100.00 100.00 100.00 100.00
100.00 100.00 100.00 100.00 100.00 100.00 100.00
100.00 100.00 100.00 0.00 0.00 0.00 0.00
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
100.00 100.00 100.00 0.00 0.00 0.00 0.00
100.00 100.00 100.00 0.00 0.00 0.00 0.00
100.00 100.00 100.00 0.00 0.00 0.00 0.00
NGHIEM CUA BAI TOAN PHU STP LA:
x[1,3,1]= 14.00
x[1,3,2]= 6.00
x[1,6,5]= 9.00
x[2,1,5]= 2.00
x[2,3,5]= 3.00
x[2,4,2]= 1.00
x[2,4,5]= 2.00
x[3,1,1]= 6.00
x[3,2,6]= 10.00
x[4,7,4]= 12.00
x[5,5,7]= 3.00
x[5,7,5]= 12.00
x[6,2,3]= 4.00
x[6,4,1]= 6.00
x[6,7,4]= 3.00
x[6,7,5]= 5.00
x[6,7,6]= 16.00
x[7,5,5]= 2.00
x[7,7,7]= 97.00
NGHIEM CUA BAI TOAN ISTP LA:
xISTP[1,3,1]= 14.00
xISTP[1,3,2]= 15.00
xISTP[2,1,2]= 5.00
xISTP[2,3,2]= 3.00
xISTP[3,1,1]= 12.00
xISTP[3,2,3]= 14.00GIA TRI CUA HAM MUC TIEU LA: 803.00
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
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: Bài toán
vận tải ba chỉ số (solid transport problem), 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
MỤC LỤC
LỜI MỞ ĐẦU
CHƯƠNG I. BÀI TOÁN QUY HOẠCH TUYẾN TÍNH
1.1 Một số khái niệm về giải tích lồi
1.1.1 Không gian Euclude
1.1.2 Tập compact
1.1.3 Tập lồi
1.1.4 Hàm lồi
1.2 Bài toán Quy hoạch tuyến tính
1.2.1 Bài toán quy hoạch tuyến tính
1.2.2 Một số tính chất chung
1.2.3 Phương pháp đơn hình giải bài toán QHTT
CHƯƠNG 2. BÀI TOÁN VẬN TẢI VÀ BÀI TOÁN VẬN TẢI MỞ RỘNG
2.1 Bài toán vận tải hai chỉ số
2.1.1 Phát biểu bài toán và tính chất
2.1.2 Cách tìm phương án xuất phát
2.1.3 Thuật toán
2.1.4 Ví dụ
2.2 Bài toán vận tải ba chỉ số(Solid Transpotion Problem)
2.2.1 Phát biểu bài toán
2.2.2 Một số định nghĩa cơ bản
2.2.3 Điều kiện để bài toán có phương án
2.2.4 Xây dựng phương án xuất phát
2.2.5 Thuật toán
2.2.6 Ví dụ
2.3 Bài toán vận tải ba chỉ số có hạn chế khả năng thông qua
2.3.1 Phát biểu bài toán
2.3.2 Điều kiện để bài toán có phương án
2.3.3 Thuật toán
2.3.4 Ví dụ
2.4 Bài toán vận tải ba chỉ số khoảng(Interval Solid Transpotion Problem)
2.4.1 Phát biểu bài toán(ISTP)
2.4.2 Thuật toán
2.4.3 Ví dụ
CHƯƠNG 3. GIỚI THIỆU MỘT SỐ BÀI TOÁN VẬN TẢI MỞ RỘNG
3.1 Bài toán sản xuất - vận tải
3.1.1 Phát biểu bài toán
3.1.2 Phương pháp giải
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
K
IL
O
BO
O
K
S.
CO
M
3.2 Bài toán vận tải đa mục tiêu
3.2.1 Phát biểu bài toán
3.2.2 Lập phương trình toán học
3.2.3 Trường hợp rời rạc
KẾT LUẬN
TÀI LIỆU THAM KHẢO
PHỤ LỤC
Phụ lục 1. Module giải bài toán vận tải 3 chỉ số không hạn chế khả năng thông
qua.
Phụ lục 2. Module giải bài toán vận tải 3 chỉ số khoảng.
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.
Phụ lục 4. Kêt quả chương trình.
1. Bài toán vận tải hai chỉ số.
2. Bài toán vận tải 3 chỉ số không hạn chế khả năng thông qua.
3. Bài toán vận tải 3 chỉ số có hạn chế khả năng thông qua.
4. Bài toán vận tải 3 chỉ số khoảng.
THÖ VIEÄN ÑIEÄN TÖÛ TRÖÏC TUYEÁN
Các file đính kèm theo tài liệu này:
- 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- vận tải ba chỉ số (solid transport problem), vận tải ba chỉ số khoảng (interval solid .pdf