Đề tài Thuật toán đơn hình (simplex method) để giải bài toán quy hoạch tuyến tính

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. Cuối cùng, em xin bày tỏ lòng biết ơn sâu sắc nhất đối với thày giáo hướng dẫn Thạc sỹ Vũ Tiến Việt, người đã tận tình chỉ bảo, giúp đỡ em trong quá trình hoàn thành khoá luận này. Em cũng xin chân thành cảm ơn sự giúp đỡ nhiệt tình của các thầy cô trong khoa Toán - Tin, Học viện An ninh Nhân dân. Chương I. Bài toán quy hoạch tuyến tính Trong việc nghiên cứu các bài toán tối ưu nói chung, giải tích lồi giữ một vai trò rất quan trọng. Nó được sử dụng làm cơ sở toán học trong việc xây dựng các thuật toán. Quy hoạch tuyến tính là một trong những lớp bài toán tối ưu được nghiên cứu trọng vẹn cả về phương diện lý thuyết lẫn thực hành, Bài toán vận tải là một dạng đặc biệt của QHTT. Do đó chương này nhằm giới thiệu một số khái niệm và kiến thức cơ bản về giải tích lồi và QHTT. 1.1 Một số khái niệm về giải tích lồi 1.1.1 Không gian Euclude Một vector n chiều trên trường số thực là một bộ được sắp thứ tự gồm n số thực x=(x1, x2, ..., xn). Các xi, i =1, ..., n gọi là các thành phần hay toạ độ của vector. Ví dụ x=(4,5,10,20). Hai vectơ x và y gọi là bằng nhau x=y, nếu xi=yi, "i =1, ..., n. Xét hai phép toán trên các vector: Phép cộng: x+y=(x1+y1, x2+y2, ..., xn+yn) Phép nhân: ax=(ax1, ax2, ..., axn), "a ẻ R Khi đó tập hợp tất cả các vector n chiều trong đó xác định phép cộng các vector, nhân một số thực với vector như trên tạo thành không gian tuyến tính n chiều trên trường số thực R, ký hiệu Rn. Các vector x(i) ẻRn, i =1, ..., m được gọi là độc lập tuyến tính nếu: Nếu: với ít nhất một ai ạ 0 thì x gọi là tổ hợp tuyến tính của các x(i), i =1, ..., m. Hơn nữa nếu ai > 0, i =1, ..., m và thì x gọi là tổ hợp lồi của các x(i), i =1, ..., m. Trong Rn có n vector độc lập tuyến tính lập thành cơ sở của nó. Giả sử e(1), e(2), ..., e(n) là một cơ sở của Rn thì bất kỳ một vector x ẻ Rn đều là tổ hợp tuyến tính của các vector e(1), e(2), ..., e(n). Ta gọi tích vô hướng của hai vector x=(x1, x2, ..., xn) và y=(y1, y2, ..., yn), ký hiệu, , là một số bằng. Tích vô hướng là một dạng song tuyến tính, đối xứng, không âm, tức là: = . "x,y ẻ Rn =+. "x(1), x(2), y ẻ Rn = l. "x,y ẻ Rn ³ 0, "xẻ Rn dấu bằng xẩy ra khi và chỉ khi x= 0. Độ dài của vector x=(x1, x2, ..., xn) là một số xác định bởi. Khoảng cách giữa hai vector x và y là một số xác định bởi: Không gian vector trong đó có tích vô hướng và khoảng cách như trên gọi là không gian Euclude. 1.1.2 Tập compact Dãy {x(k) }èRn k=1, 2, ... được gọi là có giới hạn x(0) khi k đ Ơ và viết k đ Ơ lim x(k) = x(0), nếu Hình cầu tâm a bán kính r là tập S={xẻRn :ẵx-aẵÊ r }. Hình cầu này tạo nên r- lân cận của điểm a, hay gọi là lân cận của a. * Nếu tập AèRn chứa cùng với điểm x một lân cận của nó thì x gọi là điểm trong của A. Nếu trong lân cận bất kỳ của x ẻ A có các điểm của A và các điểm không thuộc A thì x gọi là điểm biên của tập hợp A. * Một tập AèRn gọi là giới nội nếu nó được chứa trong một hình cầu tâm O nào đó, tức là tồn tại số r đủ lớn sao cho với mọi xẻA,ẵxẵÊ r. Một dãy {x(k)} hội tụ thì bao giờ cũng giới nội. * Một tập hợp GèRn được gọi là mở nếu với mọi xẻG đều tồn tại một hình cầu tâm x nằm gọn trong G. Một tập FèRn được gọi là đóng nếu với mọi dãy hội tụ{x(k)}è F ta đều có: Một tập chứa mọi điểm biên của nó là tập đóng. * Tập C được gọi là tập Compact nếu từ mọi dãy vô hạn {x(k)} thuộc C đều có thể trích ra một dãy con {x(ki)} hội tụ tới phần tử thuộc C. Tập C là Compact khi và chỉ khi C đóng và giới nội. Tập Compact M của tập đóng C cũng đóng trong C. Tập con đóng M của tập Compact cũng Compact. Hàm f(x) liên tục trên tập Compact C thì sẽ đạt cực trị trên tập ấy. 1.1.3 Tập lồi Cho hai điểm a, b ẻRn. Ta gọi đường thẳng qua a, b là tập điểm có dạng xẻRn : x = la + (1-l)b, l ẻ R. Đoạn thẳng nối hai điểm a, b là tập lồi các điểm có dạng xẻRn :x = lx + (1-l)y, 0 Ê l Ê 1 * Một tập MèRn được gọi là một đa tạp affine nếu với hai điểm bất kỳ x, y ẻM thì toàn bộ đường thẳng đi qua hai điểm đó cũng thuộc M. Tức là lx + (1-l)y ẻM : "x,y ẻM, " lẻR. * Một siêu phẳng trong không gian Rn là tập hợp tất cả các điểm x=(x1, x2, ..., xn) ẻRn thỏa mãn phương trình tuyến tính a1x1+ a2x2+ ... + anxn = a trong đó a1, a2, ..., an , a ẻR * Tập hợp các điểm x=(x1, x2, ..., xn) ẻRn thoản mãn bất phương trình tuyến tính a1x1+ a2x2+ ... + anxn Ê a được gọi là nửa không gian đóng. * Nửa không gian được cho bởi a1x1+ a2x2+ ... + anxn < a được gọi là nửa không gian mở. * Tập XèRn được gọi là tập lồi nếu cùng với việc chứa hai điểm x, y nó chứa cả đoạn thẳng chứa hai điểm ấy, tức là chứa tất cả các điểm có dạng: lx + (1-l)y, 0 Ê l Ê 1 Ví dụ về các tập lồi: Không gian Euclide, các nửa không gian, mặt phẳng, nửa mặt phẳng, hình chữ nhật, hình vuông, hình elip, hình hộp, hình cầu ... * Một tập hợp là giao của một số hữu hạn các nửa không gian đóng được gọi là tập lồi đa diện. Mệnh đề: Giao của hai tập lồi là một tập lồi. Hệ quả 1. Giao của một số bất kỳ tập hợp lồi là tập lồi. Hệ quả 2. Miền chứa nghiệm của một hệ bất phương trình tuyến tính dạng. là một tập lồi (đa diện lồi). Một tập lồi đa diện giới nội gọi là một đa diện. Giao của tất cả các tập lồi chứa tập X gọi là bao lồi của nó, ký hiệu [X] 1.1.4 Hàm lồi * Một hàm số f(x) xác định trên tập lồi C è Rn được gọi là hàm lồi trên C, nếu với mọi x, y ẻC và 0 Ê l Ê 1 ta có f(lx + (1-l)y) Ê lf(x) + (1-l)f(y). * Hàm f(x) được gọi là hàm lồi chặt nếu với mọi x, y ẻC và 0 Ê l Ê 1 ta có. f(lx + (1-l)y) < lf(x) + (1-l)f(y). * Hàm f(x) được gọi là hàm lõm (lõm chặt) nếu - f(x) là hàm lồi (lồi chặt) * Hàm f(x) xác định trên C đạt cực tiểu tuyệt đối tại x* ẻC nếu f(x*) Ê f(x):" xẻC * Hàm f(x) đạt cực tiểu địa phương tại x* ẻ C nếu tồn tại lân cận mở U của x* sao cho f(x*) Ê f(x):" xẻC ầU Mệnh đề 1: Bất kỳ điểm cực tiểu địa phương nào của hàm lồi trên tập lồi cũng là điểm cực tiểu tuyệt đối. Hệ quả: Bất kỳ điểm cực đại địa phương nào của hàm lõm cũng là cực đại tuyệt đối. Mệnh đề 2: Cực đại của một hàm lồi (nếu có) trên một tập lồi có điểm cực biên bao giờ cũng đạt tại một điểm cực biên. 1.2 Bài toán Quy hoạch tuyến tính QHTT bắt nguồn từ những nghiên cứu của nhà toán học Nga nổi tiếng, Viện sỹ L.V. Kantorovich trong một loạt các công trình về bài toán kế hoạch hoá sản xuất, công bố năm 1938. Năm 1947 nhà toán học Mỹ G.B. Dantzig đã nghiên cứu và đề xuất phương pháp đơn hình (Simplex method) để giải bài toán QHTT. Năm 1952 phương pháp đơn hình đã được chạy trên máy tính điện tử của Mỹ. 1.2.1 Bài toán quy hoạch tuyến tính Bài toán tổng quát. Để nhất quán lập luận ta xét bài toán tìm cực đại, sau đó ta xét cách chuyển bài toán tìm cực tiểu sang tìm cực đại. Bài toán tổng quát của QHTT có dạng: Ký hiệu: A=(aij)mxn là ma trận với các phần tử aij (1.1) gọi là hàm mục tiêu, (1.2) là các rằng buộc. Nếu gặp bài toán Min, tức là Thì giữ nguyên ràng buộc và đưa về bài toán Max bằng cách Nếu bài toán Max có phương án tối ưu là x* thì bài toán min cũng có phương án là x* và fmin=-`fmax Thật vậy, vì x* là phương án tối ưu của bài toán Max nên ta có: Chứng tỏ x* là phương án tối ưu của bài toán Min và Dạng chuẩn và dạng chính tắc. Người ta thường xét bài toán quy hoạch tuyến tính dưới hai dạng sau: -Dạng chuẩn: -Dạng chính tắc: Đưa bài toán QHTT về dạng chuẩn hoặc dạng chính tắc. Bất kỳ QHTT nào cũng có thể đưa về một trong hai dạng chuẩn hoặc chính tắc nhờ các phép biến đổi tuyến tính sau: i) Một ràng buộc Có thể đưa về ràng buộc bằng cách nhân hai vế với (-1) và viết lại ii) Một ràng buộc đẳng thức có thể thay bằng hai ràng buộc bất đẳng thức: iii) Một biến xj không bị ràng buộc dấu có thể thay thế bởi hiệu của hai biến không âm bằng cách đặt: iv) Một ràng buộc bất đẳng thức Có thể đưa về ràng buộc đẳng thức bằng cách đưa vào biến phụ yi ³ 0: Về nguyên tắc, áp dụng nhiều lần các phép biến đổi (i), (ii) và (iii) ta có thể đưa một bài toán QHTT bất kỳ về dạng chuẩn, sau đó áp dụng nhiều lần phép biến đổi (iv) ta sẽ đưa nó về dạng chính tắc. Giải bài toán QHTT bằng phương pháp hình học. Xét bài toán QHTT dưới dạng chuẩn với hai biến số: Từ ý nghĩa hình học ta biết rằng mỗi bất phương trình tuyến tính ai1x1+ai2x2 Ê bi xác định một nửa mặt phẳng. Như vậy miền ràng buộc D được xác định như là giao của một nửa mặt phẳng và sẽ là một đa giác lồi trên mặt phẳng. Phương trình c1x1+c2x2=a khi a thay đổi sẽ xác định trên mặt phẳng các đường thẳng song song với nhau mà ta sẽ gọi là các đường mức (với giá trị mức a). Mỗi điểm ẻD sẽ nằm trên một đường mức với mức Bài toán đặt ra có thể phát biểu theo ngôn ngữ hình học như sau: trong số các đường mức cắt tập D, hãy tìm đường mức với gía trị lớn nhất. Nếu dịch chuyển song song các đường mức theo hướng vector pháp tuyến của chúng thì giá trị mức sẽ tăng, nếu dịch chuyển theo hướng ngược lại thì giá trị mức sẽ giảm. Vì vậy để giải bài toán đặt ra, ta có thể tiến hành như sau. Bắt đầu từ một đường mức cắt D, ta dịch chuyển song song các đường mức theo hướng vector pháp tuyến (c1,c2) cho đến khi việc dịch chuyển tiếp theo làm cho đường mức không còn cắt D nữa thì dừng. Điểm của D (có thể nhiều điểm) nằm trên đường mức cuối cùng này sẽ là lời giải tối ưu cần tìm, còn giá trị của hàm mục tiêu tại đó chính là giá trị tối ưu của bài toán. Ví dụ: Xét bài toán: f(x)= 4x1+5x2đmax Xét đường mức: 4x1+5x2=10. Đường mức này đi qua hai điểm (0,2) và (2.5,0). Ta có x*=(3,2), fmax=22 và x* là một đỉnh của D. Qua phương pháp hình học ta thấy rằng: - Nếu quy hoạch tuyến tính có phương án tối ưu thì có ít nhất một đỉnh là tối ưu. Sở dĩ nói ít nhất vì có trường hợp đường mức ở vị trí giới hạn trùng với một cạnh của D thì tất cả các điểm trên cạnh này là phương án tối ưu, trong đó có hai đỉnh. - Nếu miền ràng buộc D giới nội và khác rỗng thì chắc chắn có phương án tối ưu. - Nếu miền ràng buộc không giới nội nhưng hàm mục tiêu bị chặn trên ở trên miền ràng buộc thì cũng chắc chắn có phương án tối ưu. 1.2.2 Một số tính chất chung Mệnh đề 1: Tập hợp tất cả các phương án của một bài toán QHTT là tập lồi. Tập lồi D các phương án của một bài toán QHTT xác định bởi toàn bộ các ràng buộc (1.2) và (1.3). Tập D có thể là rỗng, hoặc là một đa diện lồi hoặc là một tập lồi đa diện không giới nội. Nếu D là một đa diện lồi thì bài toán có phương án, hơn nữa giá trị tối ưu của hàm mục tiêu trên đa diện lồi là hữu hạn và việc tìm phương án tối ưu đưa đến việc chọn các điểm của đa diện D có số đỉnh (điểm cực biên hay phương án cực biên) hữu hạn. Mệnh đề 2: Hàm mục tiêu của bài toán QHTT sẽ đạt Max tại điểm cực biên của tập D. Nếu hàm mục tiêu không chỉ nhận Max tại một điểm cực biên của tập lồi D mà tại nhiều điểm cực biên thì nó sẽ đạt giá trị cực đại tại những điểm là tổ hợp lồi của các điểm đó. Ký hiệu Aj, j=1, ..., n là các vector cột của ma trận A. Khi ấy hệ ràng buộc Ax =b có thể viết: x1A1 + x2A2 + ... + xnAn = b (1.4) Mệnh đề 3: Nếu các vector A1, A2, ..., Ak là độc lập tuyến tính và thoả mãn x1A1+x2A2+...+xnAn=b trong đó xj > 0, j=1,...k thì điểm x=(x1,x2,...,xk,0,...,0) là điểm cực biên của tập lồi đa diện D. Mệnh đề 4: Nếu x =(x1,x2,...,xn) là điểm cực biên của tập lồi đa diện D thì các vector Aj trong biểu diễn (1.4) ứng với các thành phần xj > 0 lập thành hệ độc lập tuyến tính. Vì ma trận A có m dòng nên từ đây suy ra rằng điểm cực biên không có quá m thành phần dương. Các mệnh đề 3 và mệnh đề 4 có thể gộp lại thành một mệnh đề sau: Mệnh đề 5: Để x =(x1,x2...,xn) là phương án cực biên của QHTT dưới dạng chính tắc thì cần và đủ là các vector cột Aj của ma trận A ứng với các thành phần xj > 0 là độc lập tuyến tính. 1.2.3 Phương pháp đơn hình giải bài toán QHTT Cơ sở của phương pháp này đươc G.B. Dantzig công bố năm 1947 có tên gọi là phương pháp đơn hình. Sở dĩ có tên gọi như vậy là vì những bài toán đầu tiên được giải bằng phương pháp đó có các ràng buộc dạng: Mà tập hợp các điểm xẻRn thoả mãn các ràng buộc trên là một đơn hình trong không gian n chiều. Đường lối chung và cơ sở của thuật toán. i) Đường lối chung. Phương pháp đơn hình dựa trên hai nhận xét sau: nếu bài toán QHTT có phương án tối ưu, đa diện lồi D có một số hữu hạn đỉnh. Như vậy phải tồn tại thuật toán hữu hạn. Thuật toán gồm hai giai đoạn: Giai đoạn 1: Tìm một phương án cực biên (một đỉnh). Giai đoạn 2: Kiểm tra điều kiện tối ưu đối phương án tìm được ở giai đoạn 1. Nếu điểu kiện tối ưu được thoả mãn thì phương án đó là tối ưu. Nếu không, ta chuyển sang phương án cực biên mới sao cho cải tiến giá trị hàm mục tiêu. Tiếp theo lại kiểm tra điều kiện tối ưu đối với phương án mới. Người ta thực hiện một dãy các thủ tục như vậy cho đến khi nhận được phương án tối ưu, hoặc đến tình huống bài toán không có phương án tối ưu. ii) Cơ sở của thuật toán. Xét bài toán QHTT dưới dạng chính tắc: đ max (1.6) Ax = b (1.7) x ³ 0 (1.8) Trong đó A là ma trận kích thước mxn và giả sử rằng hạng của ma trận A là m (điều này không làm mất tính tổng quát). x là một vector. Giả sử x là một phương án cực biên nào đó. Ta ký hiệu: J* = {j| xj > 0} (1.9) Vì các vector Aj, jẻJ* là độc lập tuyến tính nên |J*| Ê m (|J*| là số số phần tử xj >0). * Phương án cực biên x được gọi là không thoái hoá nếu | J* |= m, thoái hoá nếu |J*| < m. Ta chọn một hệ thống m vector độc lập tuyến tính {Aj, j ẻ J}sao cho J ấ J*. Hệ thống đó gọi là cơ sở của x, các vector {Aj, j ẻ J} và các biến {xj, j ẻ J} được gọi là các vector và các biến cơ sở tương ứng. Các vector và các biến Aj, xj, jẽ J gọi là các vector và các biến phi cơ sở tương ứng. Nếu x không thoái hoá thì tồn tại một cơ sở duy nhất, đó là J=J*. Mỗi vector Ak phi cơ sở có thế biểu diễn dưới dạng tổ hợp tuyến tính của các vector cơ sở: Trong đó các hệ số zjk được xác định duy nhất bởi việc giải hệ phương trình: Bài toán QHTT được gọi là không thoái hoá nếu tất cả các phương án cực biên của nó đều không thoái hoá. Giả sử bài toán không thoái hoá và ta đã tìm được một phương án cực biên x=(x1, x2,...xm, 0,...0) và cơ sở của nó A1,, A2,...Am. Đối với phương án cực biên này ta có: với giá trị của hàm mục tiêu: Ta tính các đại lượng sau: Kí hiệu: Định lý 1.1: (Tiêu chuẩn tối ưu). Nếu đối với phương án cực biên x=(x1,x2,...,xm,0...0) các điều kiện sau được thỏa mãn thì x* là phương án tối ưu. Chú ý: Trong (1.10) nếu Aj là một vector cơ sở, khi đó tồn tại chỉ một hệ số zjj=1, tất cả các hệ số khác đều bằng 0 và ta có: và trong thực hành để kiểm tra điều kiện tối ưu của phương pháp cực biên x ta chỉ cần kiểm tra Dk ³ 0, "kẽJ (1.18) Người ta có thể chứng minh rằng nếu bài toán không thoái hoá thì (1.16) cũng là điều kiện cần của tối ưu. Định lý 1.2: Nếu tồn tại một chỉ số k sao cho Dk Z0. Công thức tìm phương án x’: Nhân (1.10) với q nào đó ta có: Lấy (1.12) trừ đi (1.19) từng vế ta có: Nếu các hệ số của các vector Aj, j=1,.....,m và Ak trong (1.20) không âm, khi đó ta có một phương án mới x’ mà đối với nó hàm mục tiêu f có giá trị Trong (1.12) tất cả các biến xj, j=1,...,m đều dương. Vì vậy có thể tìm được q > 0 sao cho Nếu đối với chỉ số k mà Dk 0, jẻJ thì giá trị q lớn nhất còn thoả mãn (1.22) có thể xác định bởi hệ thức : Nếu ta thay q trong (1.20) và (1.21) bởi qo thì thành phần thứ r sẽ bằng 0: xr- qozrk=0. Như vậy ta nhận được phương án mới x’ với cơ sở Aj, jẻJ\ {r}ẩ{k}=J’. Nếu zjk Ê 0, "jẻ J thì tất cả các thành phần xj- q zjk trong (1.22) sẽ không âm "q >0, nghĩa là ta luôn có phương án "q >0, nhưng từ (1.21) ta dễ thấy giá trị hàm mục tiêu tiến tới +Ơ khi q tiến tới +Ơ. Trong thực hành Dantzig đã chứng minh rằng các bước lặp sẽ giảm đáng kể nếu ta thay vector As thoả mãn: và khi đó vector Ar được xác định theo công thức: Ta có phương án cực biên mới x’ mà các thành phần của nó có dạng: nếu j ạ r nếu j=r và cơ sở của nó là Trên cơ sở lý thuyết đã nhận được, ta chuyển sang xét thuật toán đơn hình. Thuật toán đơn hình Giả sử ta đã đưa QHTT về dạng chính tắc: cx=Zđ max Ax=b x³0 Bước 1: Xây dựng bảng đơn hình xuất phát. Tìm một phương án cực biên xuất phát x và cơ sở của nó Aj, jẻJ. Xác định các số zjk bởi hệ phương trình: Đối với mỗi k ẽ J , tính các ước lượng: Còn với jẻJ thì Dj = 0. Tính giá trị hàm mục tiêu Bước 2: Kiểm tra tối ưu. Nếu Dk ³ 0, "k ẽ J thì x là phương án tối ưu, dừng thuật toán. Trái lại, chuyển sang bước 3. Bước 3: Tìm vector đưa vào cơ sở. Có hai khả năng xảy ra: Tồn tại kẽJ sao cho Dk< 0 và zjk Ê 0, "jẻJ thì bài toán QHTT không có lời giải tối ưu (Z không bị chặn trên). Dừng thuật toán. Đối với mỗi kẽJ sao cho Dk 0. Khi đó chọn chỉ số s theo tiêu chuẩn: Đưa vector As vào cơ sở. Bước 4: Tìm vector loại khỏi cơ sở. Xác định Và đưa vector Ar ra khỏi cơ sở. Bước 5: Chuyển sang phương án cực biên mới và cơ sở mới. Cơ sở mới là {Aj,j ẻJ’} với J’= J\{r} ẩ z{s}. Phương án cực biên mới x’ được tính theo (1.26), khai triển của các véc tơ Ak theo các cơ sở mới được tính theo công thức (1.28). Quay lên bước 2. Chú ý. Đối với bài toán min thì tiêu chuẩn tối ưu là DkÊ 0 ("k) và vector As được chọn đưa vào cơ sở theo công thức: Công thức đổi cơ sở và bảng đơn hình. Ta xét các công thức chuyển từ phương án cực biên x với cơ sở J sang phương án cực biên x’ với cơ sở J’. Ta đã có công thức (1.26) để tính các thành phần của x’. Bây giờ ta thiết lập công thức tính các số z’jk. Ta có: Mặt khác Thay biểu thức của Ar vào ta được: Đây là công thức biểu diễn Ak qua cơ sở mới J’ =J\{r}ẩ{s}. Bởi vậy ta có: nếu jạr nếu j=r Sau khi có z’jk ta tính: Để dễ tính toán, trong mỗi bước lặp ta thiết lập bảng đơn hình (xem bảng 1.1). Nếu tất cả các số trong dòng cuối (trừ hàm mục tiêu f) đều không âm, nghĩa là Dk³0 "k, khi đó x là phương án tối ưu. Bảng 1.1 cj Cơ sở Ph án c1 ... cj ... cr ... cm... ck... cs ... cn Aa... Aj... Ar... Am...Ak... As... An c1 ... cj ... cr ... cm A1... Aj ... Ar... Am x1 ... xj ... xr ... xm 1 ... 0 ... 0 ... 0 0 ... 1 ... 0 ... 0 0 ... 0 ... 1 ... 0 0 ... 0 ... 0 ... 1 z1k ... zjk ... zrk ... zmk z1s ... zjs ... zrs... zms z1n ... zjn ... zrn... zmn f 0... 0... 0... 0 ... Dk ... Ds... Dn Nếu dòng cuối (không kể f ) có những số âm thì xem thử có cột nào cắt dòng cuối ở một số âm mà mọi số trong cột đó đều âm hay không. Nếu có cột nào như thế thì bài toán không có phương án tối ưu. Nếu trái lại thì chọn cột sao cho Rồi chọn ( trong số các dòng cắt cột s ở những số dương ) dòng r sao cho: Cột s gọi là cột quay. Vector Ar được đưa vào cơ sở. Dòng r gọi là dòng quay. Vector Ar bị đưa ra khỏi cơ sở. Phần tử zrs > 0 là giao của cột quay và dòng quay gọi là phần tử chính của phép quay. Các phần tử zjs, j ạ r gọi là phần tử quay. Các công thức (1.26), (1.29) gọi là các công thức đổi cơ sở. Bảng đơn hình mới suy được từ bảng cũ bằng cách thay cr, Ar trong dòng quay bằng cs, As. Sau đó thực hiện các phép biến đổi dưới đây: i) Chia mỗi phần tử ở dòng quay cho phần tử chính được số 1 ở vị trí của zrs cũ. Kết quả thu được là dòng chính. ii) Lấy mỗi dòng khác trừ đi tích của dòng chính nhân với phần tử quay tương ứng được số 0 ở mọi vị trí còn lại của cột quay. Dòng mới = dòng cũ tương ứng - dòng chính x phần tử quay Lưu ý rằng sau phép quay thì ở vị trí Ds ta thu được số 0 vì lúc này As trở thành vector đơn vị cơ sở, nghĩa là ta đã làm mất số âm nhỏ nhất ở dòng cuối của bảng cũ. Toàn thể phép biến đổi trên gọi là phép quay xung quanh phần tử chính zrs. Sau khi thực hiện phép quay ta có một phương án mới và một cơ sở mới. Nếu chưa đạt yêu cầ nghĩa là còn Dk <1 thì ta lại tiếp tục quá trình. Chú ý: Trong bảng đơn hình ở bảng 1.1, không giảm tổng quát ta coi các vector cơ sở được đánh số A1, A2, ..., Am, nghĩa là J = {1,2, ..., m}. 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 Có m địa điểm A1, A2, ..., An cùng sản xuất một loại hàng hóa với các lượng hàng tương ứng là a1, a2, ..., an. Có n nơi tiêu thụ loại hàng hóa đó B1, B2, ..., Bn với các yêu cầu tương ứng là b1, b2, ..., bn. Để đơn giản ta sẽ gọi Ai là điểm phát i, i=1, ..., m Bj là điểm thu j, j=1, ..., n Hàng có thể chở từ một điểm phát bất kỳ (i) đến một điểm thu bất kỳ (j) Ký hiệu: cij - chi phí chuyên chở một đơn vị hàng từ điểm phát (i) đến điểm thu (j). xij - lượng hàng chuyên chở từ (i) đến (j). Bài toán đặt ra là: xác định những đại lượng xij cho mọi con đường (i,j) sao cho tổng chi phí chuyên chở là nhỏ nhất với giả thiết là: Tức là lượng hàng phát ra bằng đúng lượng hàng yêu cầu ở các điểm thu (điều kiện cân bằng thu phát). Dạng toán học của BTVT là: Hệ rằng buộc (2.2), (2.3) có m + n phương trình, m x n ẩn, tuy nhiên do (I) nên bất kỳ phương trình nào trong m + n phương trình cũng là hệ quả của các phương trình còn lại và có thể bỏ đi. Thật vậy, hệ rằng buộc có thể viết dạng (2.5). Giả sử ta cộng các phương trình từ thứ (m+1) tới thứ (m+n) rồi trừ đi tổng các phương trình từ thứ (2) tới thứ (m) thì ta được phương trình thứ (1). Do đó số phương trình cực đại của hệ (2.2), (2.3) không quá m + n-1. Ký hiệu ma trận của hệ (2.5) là A. X = (x11, x12, ..., xij, ..., xmn) - Vector cột mxn thành phần. C = (c11, c12, ..., cij, ..., cmn) - Vector hàng mxn thành phần. P = (a1, a2, ..., am, b1, b2, ..., bn) - Vector cột vế phải. Ta đưa BTVT về dạng. Ta gọi Pij là cột của ma trận A ứng với biến xij. Vector này có 2 thành phần bằng 1 tại dòng thứ i và dòng thứ m+j còn các thành phần khác bằng 0. Định nghĩa 1: Vector X thỏa mãn (2.7), (2.8) được gọi là một phương án của BTVT. Một phương án đạt cực tiểu (2.6) gọi là phương án tối ưu. Một phương án X gọi là phương án cơ sở nếu vector cột Pij của ma trận A tương ứng với các xij > 0 là độc lập tuyến tính. Định lý 2.1: BTVT luôn có phương án tối ưu. Chứng minh: 1) Trước hết ta chứng minh BTVT luôn có phương án. 2) Sau đó chứng minh rằng miền rằng buộc giới nội. a) Đặt : Ta thấy: Lập thành một phương án, vì rằng xij ³ 0 b) Vì các hệ số trong (2.2), (2.3) và các đại lượng ai, bj không âm và hữu hạn nên mọi xij đều bị chặn trên. Thực vậy xij không thể lớn hơn các số tương ứng ai, bj. Vì vậy miền rằng buộc là khác rỗng và giới nội (đa diện lồi). Đa diện này có 1 số hữu hạn đỉnh. Theo thuật toán đơn hình, xuất phát từ một phương án cực biên, sau một số hữu hạn bước ta phải đi tới một phương án cực biên tối ưu. Định nghĩa 2: - Một ô (i,j) mà xij gọi là ô sử dụng. - Tập các ô sau được gọi là một dây truyền trong T (i1,j1), (i1,j2), (i2,j2), (i2,j3), ..., (is,js+1) (2.9) hoặc: (i1,j1), (i2,j1), (i2,j2), (i3,j2), ..., (is+1,js) (2.10) Mỗi cặp ô liền nhau trong dây truyền được xếp trong một hàng hoặc trong một cột. Dây truyền được gọi là kín hay là một chu trình nếu: js+1 = j1 hoặc is+1 = i1 Gọi G là tập hợp các ô sử dụng: G = {(i,j) | xij > 0 } |G| Ê m+n-1 - Một phương án X của BTVT đã cho được gọi là không thoái hóa nếu |G| = m+n-1 Ngược lại là thoái hóa nếu |G| Ê m+n-1 - Nếu một tập hợp con thực sự của G lập thành chu trình thì ta có một chu trình con của G. Định lý 2.2: Hệ thống vector Pij của BTVT là độc lập tuyến tính khi và chỉ khi các ô tương ứng với các vector của hệ thống không tạo thành chu trình. Chứng minh: Cần. Ký hiệu Pij = { Pij ẵ (i,j) ẻ G}. Giả sử Pij là hệ độc lập tuyến tính, ta phải chứng minh G không lập thành chu trình. Bằng phản chứng, nếu có một chu trình tạo nên bởi các ô tương ứng với một số vector của hệ Pij thì nó có dạng: (i1,j1), (i1,j2), (i2,j2), (i2,j3), ..., (is,js+1) với js+1 = js khi đó rõ ràng: Pi1,j1 - Pi1j2 + Pi2j2 - ... - Pisjs - Pisj1 = 0 tức là hệ Pij phụ thuộc tuyến tính, mâu thuẫn với giả thiết. Đủ: Giả sử G không lập thành chu trình. Ta phải chứng minh hệ Pij là độc lập tuyến tính. Bằng phản chứng, giả sử hệ Pij là phụ thuộc tuyến tính. Mỗi vector Pij có dạng: (a1, ..., ai, ..., am, am+1, ..., am+j, ..., am+n) với thành phần ai = am+j = 1 còn các tọa độ khác bằng 0. Nếu hệ Pij phụ thuộc tuyến tính, tức là có một tổ hợp tuyến tính của các vector Pij bằng 0. Điều đó có nghĩa là trong thành phần của tổ hợp này ngoài vector dạng Pi1j1, phải có các vector Pi1jk và vector Piej1. Nhưng điều đó chứng tỏ rằng các ô {(i,j)} tương ứng với hệ thống Pij lập thành chu trình. Điều này trái với giả thiết. Vậy hệ Pij là độc lập tuyến tính. Hệ quả: Vector X là phương án cực biên khi và chỉ khi tập các ô sử dụng tương ứng không lập thành chu trình. Chứng minh: Coi BTVT là một QHTT thì X là phương án cực biên khi và chỉ khi các vector Pij ứng với xij > 0 là độc lập tuyến tính, theo định lý 2.2 thì điều đó xẩy ra khi và chỉ khi tập các ô sử dụng tương ứng không lập thành chu trình. Định lý 2.3: Giả sử X là một phương án của BTVT và tập G của nó lập thành chu trình, thế thì bao giờ cũng có thể điều chỉnh được X để chuyển sang một phương án mới X’ không xấu hơn mà tập G’ không lập thành chu trình. Chứng minh: Giả sử K là một chu trình nào đó của G ta phân ra trong K tập các ô chẵn K+ và tập các ô lẻ K- (xen kẽ nhau). Không giảm tổng quát có thể coi: (nếu không ta quy ước lại các ô chẵn và lẻ trên K) Ký hiệu: q = min{xijẵ(i,j) ẻ K- } (2.12) Ta chuyển X đ X’ như sau: Rõ ràng X’ vẫn còn là phương án của BTVT vì rằng: Vì mỗi hàng hay cột chỉ chứa 2 ô sử dụng nên q và (-q) triệt tiêu nhau. Hàm mục tiêu không tăng vì Do phép biến đổi (2.13) và q xác định bởi (2.12), sẽ có một ô thuộc K- trước đây xij > 0 bây giờ x’ij = 0. Ta loại ô đó ra khỏi G’ do đó khỏi K và phá được chu trình K. Nếu còn chu trình nào khác ta lại phá bằng cách tương tự. Vì vậy ta luôn có thể giả thiết rằng phương án đang xét có các ô sử dụng không lập thành chu trình. Hệ quả: Mọi phương án X đều có thể chuyển về phương án cức biên X’ không xấu hơn X. 2.1.2 Cách tìm phương án xuất phát Phương pháp góc tây bắc. Lập bảng T, ta ghi số liệu vào bảng đó, luôn xuất phát từ ô ở góc trên, bên trái. bj ai b1 ... bj ... bn a1 xịj ... ai ... am Ta bắt đầu phân phối vào ô (1,1) lượng hàng: x11 = min(a1, b1) - Nếu x11 = a1 thì ta xóa hàng 1. Lập bảng mới có b’1 = b1 - x11. Tiếp tục quá trình, bắt đầu từ ô (2,1). - Nếu x11 = b1 thì ta xóa cột 1. Lập bảng mới có a’1 = a1 - x11. Tiếp tục quá trình, bắt đầu từ ô (1,2). Một lần phân phối như vậy ta được một tải lượng xij > 0 và bỏ bớt đi được một hàng (hoặc cột) của bảng T. Bảng mới cuối cùng chỉ còn lại một ô (m, n) và do cân bằng thu phát nên cực tiể đạt cả ở hàng, cả ở cột sau khi phân phối lượng còn lại. Do đó ta xóa cả cột n và hàng m đi. Tổng số hàng và cột là m + n mỗi lần phân phối bỏ đi được 1 hàng (hoặc cột), lần cuối cùng bỏ cả cột n và hàng m, nên phương án thu được có không quá m + n - 1 ô sử dụng, không lập thành chu trình, tức là có phương án cực biên. Phương pháp cước phí tối thiểu trong toàn bảng. Quá trình biến đổi và phân phối hoàn toàn giống như phương pháp trên chỉ khác là trong mỗi bước ta không chọn ô ở góc tây bắc mà chọn ô có cước phí nhỏ nhất trong toàn bảng. Phương pháp cực tiểu cước phí theo hàng. Bắt đầu từ hàng 1: Giả sử c1s = min cik, k = 1, ..., n Phân phối xis = min(a1, bs). Nếu x1s = a1 thì xóa dòng 1 rồi tiếp tục quá trình từ dòng 2, b’s = bs - x1s. Nếu x1s = bs thì xóa cột s rồi tiếp tục quá trình, và lấy a’1 = a1 - x1s. Phương pháp cực tiể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ê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ó. 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. Tài liệu tham khảo 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. 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. 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. 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. 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 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. Fijménez, JL Verdegay - Uncertain Solid Transportion Problem Fuzzy Sets and system. 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. Gass S.I. Linear programming. Fifth Edition, New York 1985. Một số sách giới thiệu ngôn ngữ Lập trình C. 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