Khóa luận Tối ưu hoá Bài toán vận tải mở rộng

hóa vì ẵGẵ = m + n - 1 = 6 Tìm các thế vị: u1 = 0 ị v2 = c12 - u1 = 2 - 0 = 2 u2 = c22 - v2 = 3 - 2 = 1 v1 = c21 - u2 = 1 - 1 = 0 v3 = c23 - u1 = 8 - 1 = 7 u3 = c33 - v3 = 9 - 7 = 2 v4 = c34 - u3 = 7 - 2 = 5 Bước 3. Tính các ước lượng D11 = u1 + v1 - c11 = 0 + 0 - 4 = -4 < 0 D13 = u1 + v3 - c13 = 0 + 7 - 10 = -3< 0 D14 = u1 + v4 - c14 = 0 + 5 - 6 = -1 < 0 D24 = u2 + v4 - c24 = 1 + 5 - 12 = -6 < 0 D31 = u3 + v1 - c31 = 2 + 2 - 5 = -1 < 0 D32 = u1 + v1 - c11 = 2 + 2 - 3 = 1 > 0 Bước 4. Di*j* = D32 = 1 > 0 ta ghép ô (3,2) vào với G ta được chu trình: K: (2,2), (2,3), (3,3), (3,2) lẻ chẵn lẻ chẵn Bước 5. Phá vỡ chu trình với q = min{xij (i,j)ẻK-} = 5 Ta có bảng mới (Bảng 2.2), Phương án X’. bj ai 30 25 40 25 20 4 20 2 10 6 45 30 1 3 15 8 12 55 5 5 3 25 9 25 7 Lần lặp 2: Bước 2. ẵGẵ = 6 Tìm các thế vị: u1 = 0 ị v2 = c12 - u1 = 2 - 0 = 2 u3 = c32 - v2 = 3 - 2 = 1 v3 = c33 - u3 = 9 - 1 = 8 u2 = c23 - v3 = 8 - 8 = 0 v1 = c21 - u2 = 1 - 0 = 1 v4 = c34 - u3 = 7 - 1 = 6 Bước 3. Tính các ước lượng D11 = u1 + v1 - c11 = 0 + 1 - 4 = -3 < 0 D13 = u1 + v3 - c13 = 0 + 8 - 10 = -2 < 0 D14 = u1 + v4 - c14 = 0 + 6 - 6 = 0 D22 = u2 + v2 - c22 = 0 + 2 - 3 = -1 < 0 D24 = u2 + v4 - c24 = 0 + 6 - 12 = -6 < 0 D31 = u3 + v1 - c31 = 1 + 1 - 5 = -3 < 0 Ta có phương án tối ưu là: x12 = 20, x21 = 30, x23 = 15, x32 = 5, x33 = 25, x34 = 25. fmin = 20.2 + 30.1 + 15.8 + 5.3 + 25.9 + 25.7 = 605 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 Một loạt sản phẩm đồng đều được vận chuyển từ một trong m nguồn phát tới một trong n nguồn thu. Các nguồn phát có thể là các nơi sản xuất, các kho hàng, hoặc các điểm cung cấp được đặc trưng bởi lượng hàng phát ai,, i=1..,m. Nguồn thu là các nơi tiêu thụ, hoặc các nơi có nhu cầu được đặc trưng bởi mức độ yêu cầu bj, j=1,...,n. Đặt ek, k=1,...,l là số lượng sản phẩm có thể vận chuyển được bởi một trong l phương án khác nhau hay các phương tiện vận chuyển khác nhau. cijk ³ 0 là chi phí vận chuyển một đơn vị sản phẩm từ trạm phát i tới trạm thu j bằng phương tiện k. Mục đích đặt ra của bài toán là cần xác định tất cả các lượng sản phẩm xiịk được vận chuyển từ tất cả các nguồn phát i tới tất cả các nguồn thu j bởi mỗi phương thức vận chuyển k để cho tổng chi phí vận chuyển là nhỏ nhất. Về mô hình toán học bài toán STP được phát biểu như sau: Xác định các số xijk ³ 0 thoả hàm mục tiêu và các ràng buộc sau: Với các ràng buộc: Ta có nhận xét mô hình của bài toán STP là dạng tổng quát của mô hình bài toán vận tải hai chỉ số thông thường TP (Transport Problem) nếu chúng ta chỉ nghiên cứu trong một phương thức vận chuyển duy nhất (l=1). 2.2.2 Một số định nghĩa cơ bản i) Một bộ giá trị {xijk} i=1, ..., m, j=1, ..., n, k=1, ..., l thoả mãn các ràng buộc được gọi là một phương án của bài toán. ii) Một phương án mà hệ thống các véc tơ hệ số ứng với các toạ độ dương độc lập tuyến tính gọi là 1 phương án tựa (phương án cực biên). iii) Một phương án tựa mà số các toạ độ dương đúng bằng hạng của ma trận hệ số gọi là một phương án tựa không suy biến. iv) Một phương án làm cực tiểu hàm chi phí được gọi là một phương án tối ưu. v) Ta gọi một tập hợp các ô (i,j,k) tạo thành một vòng nếu các véc tơ hệ số Pijk tương ứng là phụ thuộc tuyến tính, nhưng nếu bớt đi một véc tơ thì chúng trở thành độc lập tuyến tính. Các ô (i,j,k) đó gọi là đỉnh của vòng. vi) Một tập hợp các ô (i,j,k) không tạo thành vòng nếu các véc tơ hệ số Pijk tương ứng là độc lập tuyến tính. vii) Nếu các ô (i,j,k) tạo thành một vòng thì các véc tơ hệ số Pijk thoả mãn hệ thức ồaijk pijk=0 (i,j,k) ẻ vòng viii) Đối với một phương án x ={xijk, i=1, ..., m, j=1, ..., n, k=1, ..., l} ta gọi ô (i,j,k) là ô chọn nếu xijk tương ứng >0, là ô loại nếu xijk tương ứng =0 Chú ý: Một phương án x={xijk} là phương án tựa khi và chỉ khi các ô của phương án này không tạo thành vòng. - Một ô (i0,j0,k0) được loại khỏi vòng khi và chỉ khi ai0j0k0= 0 trong hệ ồPijk aiịk=0. 2.2.3 Điều kiện để bài toán có phương án Định lý: Điều kiện cần và đủ để bài toán có phương án là: Chứng minh: Nếu bài toán đã có phương án {xijk} i=1, ..., m, j=1, ..., n, k=1, ..., l thì ta có: ị điều kiện cần Nếu có thì: Lấy: Cố định chỉ số i=i0 Tương tự như vậy ị đpcm Số phương trình đôc lập tuyến tính của bài toán là m+ n+ l- 2 2.2.4 Xây dựng phương án xuất phát Trong bài toán này ta sử dụng phương pháp góc Tây Bắc. Ta bắt đầu phân phối vào ô (1,1,1) lượng sản phẩm: x111= min {a1,b1,e1} Không mất tính tổng giá sử x111= a1 Ghi số 0 vào các ô(i, j, k)mà Pijk tương ứng có toạ độ bằng 1 ở cùng hàng với a1(với số min). Tính lượng hàng còn lại: a1= a1- a1, b1=b1-a1, e1=e1-a1 Bước tiếp theo ta xét ô kề với ô (1,1,1) mà trị số của biến chưa xác định trị số. Bước tổng quát: xijk=min {ai,bj,ek}. 2.2.5 Thuật toán *Xây dựng phương án xuất phát như trên Đặt T= {i, j, k): xijk là biến cơ sở (xijk>0)}, khi đó T gồm đúng (m+n+l-2) ô *Tính các thế vị: Tìm hệ thống số ui, thoả mãn ui+ vj+ wk= cijk Với mọi (i, j, k)ẻ T Do số phương trình là (m+n+l-2) có m+n+l ẩn do đó đặt u1= 0, v1=0 *Kiểm tra tối ưu: Nếu Dijk=( ui+ vj+ wk)- cijk Ê 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: Drst =max {Dijk : (i,j,k) ẻT } >0 Tìm các hệ số: yijk 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) bj cijk 7 4 13 13 ai 3 7 4 10 11 4 7 5 15 10 16 8 10 20 11 3 5 16 22 1 11 1 1 9 2 9 4 4 7 13 10 14 20 1 12 7 18 4 10 Ta có phương án xuất phát: x111=6, x112=1, x122=4, x222=0, x232=11, x233=2, x243=3, x343=10 *Lần lặp1: Ta có thế vị u= (0, -6, -5), v= (0, 3, 13, 20), w= (3, 4, -5) Bảng delta là: bj 7 4 13 13 ai 0 -1 12 13 11 0 0 12 9 -15 -18 0 5 -23 -11 7 12 16 -24 0 0 17 -12 -17 0 0 -6 -3 4 5 10 -15 -18 11 7 -27 -5 -1 0 Ta có h=3 và các giá trị của x tương ứng là: x111=6, x112=4, x222=0, x232=8, x233=5, x242=5, x343=10 *Lần lặp 2: u= (0, -6, 12), v= (0, 3, 13, 3), w=(3, 4, -5) Bảng delta 2 : bj 7 4 13 13 ai 0 -1 12 -4 11 0 0 12 -8 -15 -18 0 -12 -23 -11 7 -15 16 -24 0 0 0 -12 -17 0 -17 11 14 21 5 10 2 -1 28* 7 -10 -8 16 0 Ta có h = 4 và x111=6, x112= 1, x122= 4, x222= 0,x223= 9, x242= 7, x332= 4, x343= 6 *Lần lặp 3: u = (0, -6, -2), v = (0, 3, -1, 3), w= (3, 4, 9) Bảng delta 3: bj 7 4 13 13 ai 0 -1 -2 -4 11 0 0 -2 -8 -15 -4 -0 2* -23 -11 -7 -5 16 -24 0 -14 0 2 -3 0 -3 -3 +0 -7 -9 10 -12 -15 0 -7 -10 -23 2 0 Ta có h = 4 và x111= 6, x112=1, x143= 4,x222=4, x233=7, x242=5, x332=6, x343 =4 *Lần lặp 4: u=(0, -4, 0), v=(0, 1,-3, 1), w=(3, 4, 9) Bảng delta 4: bj 7 4 13 13 ai 0 -3 -4 -6 11 0 -2 -4 -10 -1 -6 -2 0 -21 -11 -7 -5 16 -22 0 -14 0 4* -3 0 -3 -1 +0 -7 -9 10 -10 -15 0 -7 -8 -8 2 0 Ta có h=1 và x111= x143=5, x213=1, x222=4, x233=6, x242=5, x332=7, x343=3 *Lần lặp 5: u = (0, -4, 0), v = (0, 5, 1, 5), w = (3, 0, 5) Bảng delta 5: bj 7 4 13 13 ai 0 1 -0 -2 11 -4 -2 -4 -10 -1 -6 -2 0 -21 -7 -3 -1 16 -26 0 -14 0 0 -3 0 -3 -1 4* -3 -5 10 -14 -15 0 -7 -12 -8 2 0 Ta có h=2 và x111= 4, x143=7, x213=3, x222=2, x233=5, x242=6, x321=2, x343=8 *Lần lặp 6: u = (0, -5.33, -2.67) v = (0, 3.67, 1, 3.67), w = (3, 2.67, 6.33) Bảng delta 6 bj 7 4 13 13 ai 0 -0.33 -0 -3.33 11 -1.33 -0.67 -1.33 -8.67 -3.67 -6 -0.67 0 -22.33 -9.67 -4.33 -3.67 16 -24.67 0 -12.67 0 0 -4.33 0 -4.33 -3.67 0 -5.67 -9 10 -14 -16.33 0 -8.33 -13.33 -10.67 0.67* -2.67 Ta có h=6 và x111= 6, x143=5, x213=1, x222=4, x233=3, x242=8, x321=4, x333=6 *Lần lặp 7: u = (0, -6, -4), v =(0,3,1,3), w=(3,4,7) bj 7 4 13 13 ai 0 -1 -0 -4 11 -0 -0 -0 -8 -3 -6 -0 0 -23 -11 -5 -5 16 -24 0 -12 0 0 5 0 -5 -5 -2 -7 1 10 -14 -17 0 -9 -14 -12 0 -4 Nhìn vào bảng delta 7, ta thấy các giá trị đều nhỏ hơn hoặc bằng 0, do đó ta có phương án tối ưu là: x111= 6, x143=5, x213=1, x222=4, x233=3, x242=8, x321=4, x333=6 Giá trị của hàm mục tiêu tương ứng với phương án tối ưu trên là 115. 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 Bài toán vận tải ba chỉ số có hạn chế khả năng thông qua được phát biểu tương tự như bài toán không hạn chế khả năng thông qua nhưng có thêm lượng hạn chế dijk ở mỗi ô. Về mô hình toán học bài toán được phát biểu như sau: Với các ràng buộc: 2.3.2 Điều kiện để bài toán có phương án Điều kiện cần nhưng không đủ để bài toán là giải được là: 2.3.3 Thuật toán Ta có thể giải tương tự như trong quy hoặc tuyến tính với các biến bị chặn trên. Nội dung: Xây dựng phương án cực biên xuất phát xijk thoả mãn các rằng buộc. Đặt T={(i,j,k): xijjk là cơ sở}. Phân loại các ô không thuộc T thành hai loại T0= {(i,j,k) ẽT : xijk = 0} và Td = {(i,j,k) ẽT : xijk = 0} Tính các thế vị: Tìm hệ thống số ui (i=1, ..., m), vj, (j=1, ..., n) và wk (k=1, ..., l) thoả mãn ui + vj + wk = cijk với mọi (i,j,k) ẻT. Kiểm tra điều kiện tối ưu: Tính c’ijk = cijk - (ui + vj + wk) với mọi (i,j,k) ẻ T ẩ T0 và c’ijk = ui + vj + wk - cijk với mọi (i,j,k)ẻ Td. Nếu c’ijk ³ 0 với mọi ô (i,j,k) thì dừng: bài toán đã giải song. Nếu trái 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 c’rst = min{ c’ijk : (i,j,k) ẽ T} < 0 Tìm các hệ số yijk với (i,j,k) ẻ T thoả mãn trong đó Pijk là vector điều kiện của bài toán. nếu nếu Xác định hắng số biến đổi: h = min(h1, h2) với Điều chỉnh phương án: nếu nếu 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 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 3.4.1 có thể viết lại như sau: 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: ai1 = ai2 , 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 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: Bảng 2.4: Chi phí trong bài toán phụ: k c111 ... c11l c111 ... c11l M ... ... ... ... ... ... ... c1n1 ... c1nl c1n1 ... c1nl M c111 ... c11l c111 ... c11l M ... ... ... ... ... ... ... c1n1 ... c1nl c1n1 ... c1nl M M ... M M ... M M i = 1 ... k 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 ... ... ... ... ... ... ... c1n1 ... c1nl c1n1 ... c1nl M c111 ... c11l c111 ... c11l 0 ... ... ... ... ... ... ... c1n1 ... 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 ... ... ... ... ... ... ... 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 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 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 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. 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 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. và 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 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à: 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ử 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. Đặ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. 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ó. Tác giả rất mong được sự đóng góp ý kiến quý báu của các thầy cô giáo và các bạn để khoá luận hoàn thiện hơn. Tài liệu tham khảo Quy hoạch toán học - PGS.TS Bùi Minh Trí - Nhà xuất bản Khoa học kỹ thuật Hà Nội 2001. Các phương pháp tối ưu hoá - PGS.TS Bùi Thế Tâm, GS.TS Trần Vũ Thiệu - Nhà xuất bản giao thông vận tải 1998. Các bài toán vận tải nhiều chỉ số - Phạm Xuân Ninh - Luận án tiến sỹ 1978. Một số khoá luận tốt nghiệp Trường đại học Bách khoa Hà Nội 2002. 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]; typedef int vtvong[MAX1][MAX2][MAX3]; typedef float vtm[MAX1]; typedef float vtn[MAX2]; typedef float 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; } 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); 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]); } 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; } 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]; 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; } } } } } } } 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; 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; 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; 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); 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; 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]); } 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; }//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]; 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]; 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]; 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) { 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. Bài toán vận tải hai chỉ số. Kich thuoc vectoro: m:=3 n:=1 l:=4 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: *****************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.00 GIA TRI CUA HAM MUC TIEU LA: 610.00 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:=3 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 x[2,4,2]= 8.00 x[3,3,2]= 4.00 x[3,3,3]= 6.00 GIA TRI CUA HAM MUC TIEU LA: 115.00 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:=3 CAC 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 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.00 GIA TRI CUA HAM MUC TIEU LA: 125.00 Bài toán vận tải 3 chỉ số khoảng. Kich thuoc vec to: m:=3 n:=3 l:=3 CAC 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********************* 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 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.00 GIA TRI CUA HAM MUC TIEU LA: 803.00