Bài toán vận tải ba chỉ số khoảng

iểu cước phí theo cột. Tương tự như phương pháp trên, nhưng xuất phát từ cột thứ 1. Dùng các phương pháp trên để tìm phương án xuất phát, trong một số lớn các trường hợp, số bước lặp dẫn tới nghiệm giảm đi khá nhiều, nhất là khi giải BTVT mà số điểm phát và thu rất lớn. 2.1.3 Thuật toán Tiêu chuẩn tối ưu Định lý 2.4: Phương án X của BTVT là tối ưu Û $ các số ui, i = 1, ..., m và vj, j = 1, ..., n sao cho: ui + vj Ê cij "(i,j)ẻT (2.14) ui + vj = cij , nếu xij > 0 (2.15) Các số ui, vj gọi là các thế vị ứng với các điểm phát và thu i,j. Chứng minh: Đủ: Giả sử các số ui, vj thỏa mãn (2.14), (2.15). Ta phải chứng minh phương án X = (xij)mxn tương ứng là tối ưu. Muốn vậy, phải chứng minh: Ê " X’ = (xij)mxn (2.16) Mặt khác do (2.14), (2.15) tức là: ui + vj < cij với xij = 0 ui + vj = cij với xij > 0 Nên ta có: (xij > 0 ) Từ (2.17) và (2.18) ta có (2.16). Cần: Xét bài toán đối ngẫu của BTVT . Giả sử (T) có phương án tối ưu `x ị theo định lý đỗi ngẫu bài toán (T’) có lời giải `z = (`u1, ...,`um,`v1, ...,`vn) tức là $`z. Vì`z là phương án tối ưu, tức cũng là phương án: `u + `v Ê cij "(i,j) Mặt khác theo định lý về độ lệch bù `X,`Z là tối ưu Û = 0 = 0 Nếu`xij > 0 thì PijZ = cij hay`u +`v Ê cij Thuật toán. Bước 1: Tìm phương án xuất phát theo 1 trong 4 phương án đễ giới thiệu phần trước. Bước 2: Kiểm tra phương án: Nếu các ô sử dụng lập thành chu trình thì ta sử dụng định lý (2.3) để phá chu trình, chuyển phương án xuất phát về phương án cực biên. Xác định hệ thống các thế vị ui, vj theo định lý 2.4 (công thức 2.15). Vì giả thiết bài toán không thoái hóa nên tập G = {(i,j) | xij >0} có đúng m +n -1 ô, do đó có m +n - 1 phương trình. ui + vj = cij , xij > 0 (2.19) Để xác định m + n ẩn ui (i=1, ..., m), vj (j=1, ..., n). Như vậy sẽ có một ui hoặc một vj được xác định tùy ý và m + n -1 ẩn còn lại sẽ xác định duy nhất từ m + n -1 phương trình. Quy tắc: Đầu tiên cho ui0 = 0 (i0 thường là dòng đầu tiên hoặc là dòng chứa 1 ô sử dụng). Sau đó xác định vj = cij - ui0 cho những cột cắt dòng i0 ở một ô sử dụng. Bằng quy tắc đó ta xác định được ui và vj cho mọi dòng và cột. Với mọi ô (i,j) ẻG ta xác định các ước lượng sau đây: Dij sau đây: Dij = (ui + vj) - cij Nếu Dij Ê 0, "(i,j) thì phương án đã cho là tối ưu. Nếu Dij > 0 với ít nhất 1 ô (i,j) thì phương án đã cho chưa tối ưu, ta có thể điều chỉnh để hạ nữa hàm mục tiêu. Bước 3: Điều chỉnh phương án. Giả sử ô vi phạm tiêu chuẩn tối ưu là (i,j) tức là Di*j* >0 (nếu có nhiều ô vi phạm ta chọn ô ứng với max Dij với hy vọng hàm mục tiêu giảm nhanh nhất). Ô (i*,j*) ẻG. Bây giờ ta thêm ô (i*,j*) vào tập G. Khi đó tất cả m + n ô sử dụng. Ô (i*,j*) sẽ lập với các ô của G một chu trình K duy nhất. Coi ô (i*,j*) là ô chẵn, tức là (i*,j*) ẻK+. Ta điều chỉnh phương án X để nhận được phương án X’ mà tập G’ không lập thành chu trình ta loại khỏi chu trình 1 ô sử dụng ứng với cực tiểu của (4.1), giả sử là ô (is,js) (Điều chỉnh theo công thức(2.13)). Đặt xi*j* = xisjs = q > 0 Do đó ô (i*,j*) trở thành ô sử dụng. G’ = G \ (is,js) ẩ (i*,j*) vẫn gồm m + n -1 không lập thành chu trình. Ta xác định hệ thống thế vị mới ứng với phương án X’ và G’ và tiếp tục quá trình cho đến khi nào xẩy ra tình huống Dij Ê 0, "(i,j) ị lúc đó ta nhận được phương án tối ưu. Nếu bài toán không thoái hóa thì sau một số hữu hạn bước ta sẽ đi đến lời giải. Chú ý: Nếu số ô sử dụng N < m +n - 1 thì thêm (m +n -1) - N ô mới với xij =0 sao cho không tạo thành chu trình. 2.1.4 Ví dụ Ví dụ: Giải BTVT với các số liệu cho trong bảng sau (Bảng 2.1): bj ai 30 25 40 25 20 4 20 2 10 6 45 30 1 5 3 10 8 12 55 5 3 30 9 25 7 Kiểm tra điều kiện cân bằng thu phát: Lần lặp 1: Bước 1. Tìm phương án xuất phát bằng phương pháp cực tiểu cước phí trong toàn bảng. Ta được phương án cực biên X (Bảng 2.1). Bước 2. Phương án X không thoái 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 vector 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 vector hệ số Pijk tương ứng là phụ thuộc tuyến tính, nhưng nếu bớt đi một vector 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 vector 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 vector 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 (2.22) 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 ... ... ... ... ... ... ... c1Ê ... c1nl c1n1 ... c1nl M c111 ... c11l c111 ... c11l M ... ... ... ... ... ... ... c1Ê ... 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 ... ... ... ... ... ... ... 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 ... ... ... ... ... ... ... 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