Đề tài Phương án Tây- Bắc, Voghel, min cước và một số bài tập thực hành

Qui Hoạch Tuyến Tính Đề tài: Phương án Tây- Bắc, Voghel, min cước và một số bài tập thực hành Để tìm phương án cực biên ban đầu của bài toán vận tải. Chúng ta cần biết thế nào là bài toán vận tải và một số khái niệm của nó. Định nghĩa bài toán vận tải Xí nghiệp cần vận chuyển hàng hóa từ m kho (điểm phát) PI,i=1,2,…,m đến nơi tiêu thụ (điểm thu) Tj, j= 1,2,…,n. lượng hàng có ở mỗi kho Pi, là ai, i=1,2,…,m. lượng hàng cần ở mỗi nơi tiêu thụ Tjlà bj, j=1,2,…,n. chi phí vận chuyển một đơn vị hàng từ kho PI đến nơi tiêu thụ Tj là cij, i=1,2,…,m, j=1,2,…,n. cho biết tổng lượng hàng ở các kho bằng tổng lượng hàng cần tiêu thụ. Hãy lập kế hoạch vận chuyển hàng hóa sao cho chi phí là nhỏ nhất và đảm bảo yêu cầu thu phát Mô hình toán học của bài toán Tìm x = (x11,x12,…,xmn) sao cho f(x) =cij →min xij=ai, i=1,2,…,m.xij=bj, j=1,2,…,n.xij ≥0, i=1,2,…,m, j=1,2,…,n. Trong đó ai= bj (điều kiện cân bằng thu phát) Lưu ý: bài toán vận tải cân bằng thu phát luôn có phương án tối ưu và ta cũng có thể giải bằng phương pháp đơn hình. Ta trình bày dưới dạng bảng vận tải như sau: Thu Phát b1 b2 … bn a1 c11 X11 … c1n X1n a2 c21 X21 c22 X22 … c2n X2n … … … … … am Cm1 Xm1 cm2 Xm2 … cmn Xmn Một số khái niệm Xét bảng vận tải m × n ô chọn là ô (I,j) nằm trên dòng I, cột j mà lượng hàng xij>0, ô loại là ô (I,j) mà xij= 0. x x x x x x Dây chuyền là một tập hợp các ô chọn sao cho không có quá 2 ô liên tiếp nằm trên cùng một dòng hoặc cột. x x x x x x dây chuyền không là dây chuyền Chu trình là một dây chuyền khép kín. Số các ô trong một chu trình là số chẵn. số các ô tối đa trong bảng không tạo thành chu trình là m + n – 1. Với m + n – 1 không tạo thành chu trình ta có thể bổ sung thêm một ô bất kì để có ít nhất một chu trình. x x x x x x x x x x x x x x x x Một số chu trình thường gặp Ma trận cước phí là ma trận (cij) với cij là cước phí vận chuyển một đơn vị hàng từ Pi đến Tj. Phương án cực biên là phương án có số ô chọn tối đa không tạo thành chu trình là m + n – 1, nếu số ô này bằng đúng m + n – 1 ta có phương án cực biên không suy biến, ngược lại ta có phương án cực biên suy biến. Trường hợp suy biến ta có thể bổ sung thêm một số “ô chọn 0” để có m + n – 1 ô không tạo thành chu trình. CHƯƠNG 2 TÌM PHƯƠNG ÁN CỰC BIÊN BAN ĐẦU Một số phương pháp tìm phương án cực biên ban đầu 1 Phương pháp góc tây bắc Quy trình: Xác định ô ở góc tây bắc (hướng tây bắc theo nghĩa bản đồ) trên bảng bài toán vận tải. Ưu tiên phân phối lượng hành nhiều nhất vào ô ở góc tây bắc. Loại bỏ dòng hay cột đã phân phối đủ hàng. Tiếp tục quá trình trên cho đến khi phân phối hết hàng. 2 Phương pháp “min” cước Quy trình: Tìm ô có cước phí bé nhất. Phân phối lượng hành tối đa có thể vào ô đó. Loại bỏ dòng hay cột đã phân phối đủ hành. Tiếp tục quá trình cho đến khi phân phối hết hàng. 3 Phương pháp Voghel Quy trình: Tính số cước phí của hai ô có cước phí bé nhất trên các dòng và cột. Trên dòng hay cột có hiệu số lớn nhất tìm ô có cước phí bé nhất. Loại bỏ dòng hay cột đã phân phối đủ hàng. Tính lại hệ số cước phí trên dòng hay cột. Tiếp tục quá trình cho đến khi phân phối hết hàng. CHƯƠNG 3 BÀI TẬP THỰC HÀNH 3.1 Tìm phương án cực biên ban đầu bằng phương pháp Tây Bắc Bai 1a j i 50 80 70 75 4(50) 7 12 65 5 8 15 60 6 7 3 j i 80 70 25 7(25) 12 65 8 15 60 7 3 j i 55 70 65 8(55) 15 60 7 3 j i 70 10 15(10) 60 3 j i 70 60 3(60) j i 50 80 70 75 4(50) 7(25) 12 65 5 8(55) 15(10) 60 6 7 3(60) Vậy phương án cực biên ban đầu là 5000010001, f=1145 Bài 2a j i 50 20 30 60 6(50) 1 2 40 5 4 3 j i 20 30 10 1(10) 2 40 4 3 j i 10 30 40 4(10) 3 j i 30 30 3(30) j i 50 20 30 60 6(50) 1(10) 2 40 5 4(10) 3(30) Vậy phương án cực biên ban đầu là 5010001030, f= 440 Bài 3a j i 45 55 60 70 5(45) 2 3 90 2 1 4 j i 55 60 25 2(25) 3 90 1 4 j i 30 60 90 1(30) 4 j i 60 60 4(60) j i 45 55 60 70 5(45) 2(25) 3 90 2 1(30) 4(60) Vậy phương án cực biên ban đầu là 4525003060, f=545 Bài 4a j i 45 55 60 80 30 70 5(45) 2 3 6 10 90 2 1 4 9 4 50 6 5 5 8 6 60 1 12 13 7 7 j i 55 60 80 30 25 2(25) 3 6 10 90 1 4 9 4 50 5 5 8 6 60 12 13 7 7 j i 30 60 80 30 90 1(30) 4 9 4 50 5 5 8 6 60 12 13 7 7 j i 60 80 30 60 4(60) 9 4 50 5 8 6 60 13 7 7 j i 80 30 50 8(50) 6 60 7 7 j i 30 30 60 7(30) 7 j i 30 30 7(30) j i 45 55 60 80 30 70 5(45) 2(25) 3 6 10 90 2 1(30) 4(60) 9 4 50 6 5 5 8(50) 6 60 1 12 13 7(30) 7(30) Vậy phương án cực biên ban đầu là 452500003060000005000003030, f= 1365 Bài 5a j i 60 60 50 80 100 60 80 70 → j i 60 50 80 40 40 80 70 → j i 20 50 80 80 20 70 → j i 50 80 60 50 70 → j i 80 10 10 70 70 → f = 1780 Vậy phương án cực biên ban đầu là 6040020000050101070 Bài 6a j i 120 144 156 180 150 225 120 175 230 120 → j i 144 156 180 150 105 105 175 230 120 → j i 39 156 180 150 175 39 230 120 → j i 156 180 150 136 136 230 120 → j i 20 180 150 230 20 120 → j i 180 150 210 180 120 → j i 150 30 30 120 120 → f = 16 813 Vậy phương án cực biên ban đầu là 12003910501360000001200200180300120 Bai 7a phương pháp gốc tây bắc 130 140 120 160 180 20 18 22 25 170 15 25 30 15 200 45 30 40 35 Giải j i 130 140 120 160 180 20(130) 18 22 25 170 15 25 30 15 200 45 30 40 35 j i 140 120 160 50 18(50) 22 25 170 25 30 15 200 30 40 35 j i 90 120 160 170 25(90) 30 15 200 30 40 35 j i 120 160 80 30(80) 15 200 40 35 j i 40 160 200 40(40) 35 j i 160 160 35(160) Do đó ta có bảng sau: j i 130 140 120 160 180 20(130) 18(50) 22 25 170 15 25(90) 30(80) 15 200 45 30 40(40) 35(160) Vậy phương án cực biên ban đầu là 130 50 0 0 0 90 80 0 0 0 40 160 Và f= 15350 Bài 8a phương pháp gốc tây bắc 50 70 60 80 110 7 11 8 13 100 21 17 12 10 50 8 18 13 16 Giải j i 50 70 60 80 110 7(50) 11 8 13 100 21 17 12 10 50 8 18 13 16 j i 70 60 80 60 11(60) 8 13 100 17 12 10 50 18 13 16 j i 70 60 80 100 17(10) 12 10 50 18 13 16 j i 60 80 90 12(60) 10 50 13 16 j i 80 30 10(30) 50 16 j i 50 50 16(50) Do đó ta có bảng sau: j i 50 70 60 80 110 7(50) 11(60) 8 13 100 21 17(10) 12(12) 10(30) 50 8 18 13 16(50) Vậy phương án cực biên ban đầu là 50 60 0 0 0 10 60 30 0 0 0 50 Và f= 3000 Bài 9a phương pháp min cước 1 1 1 1 1 32 18 32 16 1 22 14 12 16 1 24 30 26 24 1 26 30 28 20 Giải j i 1 1 1 1 1 32(1) 18 32 16 1 22 14 12 16 1 24 30 26 24 1 26 30 28 20 j i 1 1 1 1 14(1) 12 16 1 30 26 24 1 30 28 20 j i 1 1 1 26(1) 24 1 28 20 j i 1 1 20(1) Do đó ta có bảng sau: j i 1 1 1 1 1 32(1) 18 32 16 1 22 14(1) 12 16 1 24 30 26(1) 24 1 26 30 28 20(1) Vậy phương án cực biên ban đầu là 1 0 0 0 0 1 0 0 0 0 1 0 0 0 0 1 Và f= 92 Bài 10a j i 30 60 50 40 45 30 80 55 → j i 60 50 40 15 15 80 55 → j i 45 50 40 80 45 55 → j i 50 40 35 35 55 → j i 15 40 55 15 40 → f = 845 Vậy phương án cực biên ban đầu là 301504500003501540 Bài 11a j i 50 80 70 75 50 65 60 → j i 80 70 25 25 65 60 → j i 55 70 65 55 60 → j i 70 10 10 60 60 → f = 1145 Vậy phương án cực biên ban đầu là 50250055100060 Bài 12a j i 5 9 9 7 10 5 12 8 → j i 9 9 7 5 5 12 8 → j i 4 9 7 12 4 8 → j i 9 7 8 8 8 → j i 1 7 8 1 7 → f = 146 Vậy phương án cực biên ban đầu là 550400008017 3.2 Tìm phương án cực biên ban đầu bằng phương pháp “min” cước Bài 1b j i 50 80 70 75 4 7 12 65 5 8 15 60 6 7 3(60) j i 50 80 10 75 4(50) 7 12 65 5 8 15 j i 80 10 25 7(25) 12 65 8 15 j i 55 10 65 8(55) 15 j i 10 10 15(10) j i 50 80 70 75 4(50) 7(25) 12 65 5 8(55) 15 60 6 7 3(60) Vậy phương án cực biên ban đầu là 50250055100060, f= 995 Bai 2b j i 50 20 30 60 6 1(20) 2 40 5 4 3 j i 50 30 40 6 2(30) 40 5 3 j i 50 10 6 40 5(40) j i 10 10 6(10) j i 50 20 30 60 6(10) 1(20) 2(30) 40 5(40) 4 3 Vậy phương án cực biên ban đầu là 1020304000, f= 340 Bài 3b j i 45 55 60 70 5 2 3 90 2 1(55) 4 j i 45 60 70 5 3 35 2(35) 4 j i 10 60 70 5 3(60) j i 10 10 5(10) j i 45 55 60 70 5(10) 2 3(60) 90 2(35) 1(55) 4 Vậy phương án cực biên ban đầu là 1006035550, f= 355 Bài 4b j i 45 55 60 80 30 70 5 2 3 6 10 90 2 1 4 9 4 50 6 5 5 8 6 60 1(45) 12 13 7 7 j i 55 60 80 30 70 2 3 6 10 90 1(55) 4 9 4 50 5 5 8 6 15 12 13 7 7 j i 60 80 30 70 3(60) 6 10 35 4 9 4 50 5 8 6 15 13 7 7 j i 80 30 10 6 10 35 9 4(30) 50 8 6 15 7 7 j i 80 10 6(10) 5 9 50 8 15 7 j i 70 5 9 50 8 15 7(15) j i 55 5 9 50 8(50) j i 5 5 9(5) j i 45 55 60 80 30 70 5 2 3(60) 6(10) 10 90 2 1(55) 4 9(5) 4(30) 50 6 5 5 8(50) 6 60 1(45) 12 13 7(15) 7 Vậy phương án cực biên ban đầu là 006010005505300005004500150, f= 1010 Bài 5b j i 60 60 50 80 100 8 5 9 7 80 4 2 (60) 5 8 70 3 8 10 9 → j i 60 50 80 100 8 9 7 20 4 5 8 70 3 (60) 10 9 → j i 50 80 100 9 7 20 5 (20) 8 10 10 9 → j i 30 80 100 9 7 (80) 10 10 9 → j i 30 20 9 (20) 10 10 (10) → f = 1240 Vậy phương án cực biên ban đầu là 0006060020802001010 Bài 6b j i 120 144 156 180 150 225 14 21 12 23 34 175 24 19 17 32 15 230 22 11 34 16 27 120 10 (120) 25 14 27 36 → j i 144 156 180 150 225 21 12 23 34 175 19 17 32 15 230 11 (144) 34 16 27 → j i 156 180 150 225 12 (156) 23 34 175 17 32 15 86 34 16 27 → j i 180 150 69 23 34 175 32 15 (150) 86 16 27 j i 180 69 23 25 32 86 16 (86) → j i 94 69 23 (69) 25 32 (25) → f = 10 669 Vậy phương án cực biên ban đầu là 0015669000025150014408601200000 Bài 7b phương pháp min cước 130 140 120 160 180 20 18 22 25 170 15 25 30 15 200 45 30 40 35 Giải j i 130 140 120 160 180 20 18 22 25 170 15(130) 25 30 15 200 45 30 40 35 j i 140 120 160 180 18 22 25 40 25 30 15(40) 200 30 40 35 j i 140 120 120 180 18(140) 22 25 200 30 40 35 j i 120 120 40 22(40) 25 200 40 35 j i 80 120 200 40 35(120) j i 80 80 40(80) Do đó ta có j i 130 140 120 160 180 20 18(140) 22(40) 25 170 15(130) 25 30 15(40) 200 45 30 40(80) 35(120) Vậy phương án cực biên ban đầu là 0 140 40 0 130 0 0 40 0 0 80 120 Và f= 13350 Bài 8b phương pháp min cước 50 70 60 80 110 7 11 8 13 100 21 17 12 10 50 8 18 13 16 Giải j i 50 70 60 80 110 7(50) 11 8 13 100 21 17 12 10 50 8 18 13 16 j i 70 60 80 60 11 8(60) 13 100 17 12 10 50 18 13 16 j i 70 80 100 17 10(80) 50 18 16 j i 70 20 17(20) 50 18 j i 50 50 18(50) Do đó ta có bảng sau: j i 50 70 60 80 110 7(50) 11 8(60) 13 100 21 17(20) 12 10(80) 50 8 18(50 13 16 Vậy phương án cực biên ban đầu là 50 0 60 0 0 20 0 80 0 50 0 0 Và f= 2870 Bài 9b phương pháp min cước 1 1 1 1 1 32 18 32 16 1 21 14 12 16 1 24 30 26 24 1 26 30 28 20 Giải j i 1 1 1 1 1 32 18 32 16 1 22 14 12(1) 16 1 24 30 26 24 1 26 30 28 20 j i 1 1 1 1 32 18 16(1) 1 24 30 24 1 26 30 20 j i 1 1 1 24(1) 30 1 26 30 j i 1 1 30(1) Do đó ta có bảng sau j i 1 1 1 1 1 32 18 32 16(1) 1 21 14 12(1) 16 1 24(1) 30 26 24 1 26 30(1) 28 20 Vậy phương án cực biên ban đầu là 0 0 0 1 0 0 1 0 1 0 0 0 0 1 0 0 Và f= 82 Bài 10b j i 30 60 50 40 45 1 (30) 5 7 2 80 5 7 4 9 55 12 2 3 6 → j i 60 50 40 15 5 7 2 80 7 4 9 55 2 (55) 3 6 → j i 5 50 40 15 5 7 2 (15) 80 7 4 9 → j i 5 50 25 80 7 4 (50) 9 → j i 5 25 30 7 (5) 9 (25) → f = 630 Vậy phương án cực biên ban đầu là 30005055015502500 Bài 11b j i 50 80 70 75 4 7 12 65 5 8 15 60 6 7 3 (60) → j i 50 80 10 75 4 (50) 7 12 65 5 8 15 → j i 80 10 25 7 (25) 12 65 8 15 → j i 55 10 65 8 (55) 15 (10) → f = 1145 Vậy phương án cực biên ban đầu là 50251005500060 Bài 12b j i 5 9 9 7 10 7 8 5 3 12 2 4 5 9 8 6 3 1(8) 2 → j i 5 9 1 7 10 7 8 5 3 12 2 (5) 4 5 9 → j i 9 1 7 10 8 5 3 (7) 7 4 5 9 → j i 9 1 3 8 5 7 4 (7) 5 → j i 2 1 3 8 (2) 5 (1) → f = 88 Vậy phương án cực biên ban đầu là 025700170080 3.3 Tìm phương án cực biên ban đầu bằng phương pháp Vogel Bài 5c Hiệu của 2 chi phí nhỏ nhất 1 3 4 1 j i 60 60 50 80 2 100 8 5 9 7 2 80 4 2 5 8 5 70 3 (60) 8 10 9 → Hiệu của 2 chi phí nhỏ nhất 3 4 1 j i 60 50 80 2 100 5 9 7 3 80 2 5 (50) 8 1 10 8 10 9 → Hiệu của 2 chi phí nhỏ nhất 3 1 j i 60 80 2 100 5 7 6 30 2 (30) 8 1 10 8 9 → Hiệu của 2 chi phí nhỏ nhất 3 2 j i 60 80 2 100 5 (30) 7 1 10 8 9 → Hiệu của 2 chi phí nhỏ nhất 2 j i 80 7 100 7 (70) 9 10 9 (10) → f = 1225 Vậy phương án cực biên ban đầu là 030030600070500010 Bài 6c Hiệu của 2 chi phí nhỏ nhất 4 8 5 7 12 j i 120 144 156 180 150 2 225 14 21 12 23 34 2 175 24 19 17 32 15 (150) 5 230 22 11 34 16 27 4 120 10 25 14 27 36 → Hiệu của 2 chi phí nhỏ nhất 4 8 5 7 j i 120 144 156 180 2 225 14 21 12 23 2 25 24 19 17 32 5 230 22 11 (144) 34 16 4 120 10 25 14 27 → Hiệu của 2 chi phí nhỏ nhất 4 5 7 j i 120 156 180 2 225 14 12 23 7 25 24 17 (25) 32 6 230 22 34 16 4 120 10 14 27 → Hiệu của 2 chi phí nhỏ nhất 4 2 4 j i 120 131 180 2 225 14 12 23 6 86 22 34 16 (86) 4 120 10 14 27 → Hiệu của 2 chi phí nhỏ nhất 4 2 4 j i 120 131 94 2 225 14 12 23 4 120 10 (120) 14 27 → Hiệu của 2 chi phí nhỏ nhất 12 23 j i 131 94 11 225 12 (131) 23 (94) → f = 10 569 Vậy phương án cực biên ban đầu là 0013194000250150014408601200000 Bài 7c Hiệu của 2 chi phí nhỏ nhất 5 7 8 10 j i 130 140 120 160 2 180 20 18 22 25 0 170 15 25 30 15 5 200 45 30 40 35(160) Hiệu của 2 chi phí nhỏ nhất 5 7 8 j i 130 140 120 2 180 20 18 22 10 170 15 25 30(120) 10 40 45 30 40 Hiệu của 2 chi phí nhỏ nhất 5 7 j i 130 140 2 180 20 18 10 50 15 25 15 40 45 30(40) Hiệu của 2 chi phí nhỏ nhất 5 7 j i 130 100 2 180 20 18 10 50 15 25(50) Hiệu của 2 chi phí nhỏ nhất 20 18 j i 130 50 2 180 20(130) 18 Hiệu của 2 chi phí nhỏ nhất 18 j i 50 18 50 18(50) j i 130 140 120 160 180 20(130) 18(50) 22 25 170 15 25(50) 30(120) 15 200 45 30(40) 40 35(160) Vậy phương án cực biên ban đầu là 130500005012000400160, f= 15150 Bài 8c Hiệu của 2 chi phí nhỏ nhất 1 6 4 3 j i 50 70 60 80 1 110 7 11 8 13 2 100 21 17 12 10 6 50 8 18(50) 13 16 Hiệu của 2 chi phí nhỏ nhất 14 6 4 3 j i 50 20 60 80 1 110 7 11 8 13 2 100 21(50) 17 12 10 Hiệu của 2 chi phí nhỏ nhất 6 4 3 j i 20 60 80 3 110 11(20) 8 13 2 50 17 12 10 Hiệu của 2 chi phí nhỏ nhất 4 3 j i 60 80 5 90 8(60) 13 2 50 12 10 Hiệu của 2 chi phí nhỏ nhất 3 j i 80 13 30 13(30) 10 50 10 Hiệu của 2 chi phí nhỏ nhất 10 j i 50 10 50 10(50) j i 50 70 60 80 110 7 11(20) 8(60) 13(30) 100 21(50) 17 12 10(50) 50 8 18(50) 13 16 Vậy phương án cực biên ban đầu là 02060305000005000, f= 2490 Bài 9c Hiệu của 2 chi phí nhỏ nhất 2 4 14 0 j i 1 1 1 1 2 1 32 18 32 16 2 1 22 14 12 16 0 1 24 30 26 24 6 1 26 30 28(1) 20 Hiệu của 2 chi phí nhỏ nhất 2 4 0 j i 1 1 1 2 1 32 18(1) 16 2 1 22 14 16 0 1 24 30 24 Hiệu của 2 chi phí nhỏ nhất 2 8 j i 1 1 6 1 22 16(1) 0 1 24 24 Hiệu của 2 chi phí nhỏ nhất 24 j i 1 24 1 24(1) j i 1 1 1 1 1 32 18(1) 32 16 1 22 14 12 16(1) 1 24 30 26 24(1) 1 26 30 28(1) 20 Vậy phương án cực biên ban đầu là 0100000100010010, f= 86 Bài 10c Hiệu của 2 chi phí nhỏ nhất 4 3 1 4 j i 30 60 50 40 1 45 1 (30) 5 7 2 1 80 5 7 4 9 1 55 12 2 3 6 → Hiệu của 2 chi phí nhỏ nhất 3 1 4 j i 60 50 40 3 15 5 7 2 (15) 3 80 7 4 9 1 55 2 3 6 → Hiệu của 2 chi phí nhỏ nhất 5 1 3 j i 60 50 25 3 80 7 4 9 1 55 2 (55) 3 6 → Hiệu của 2 chi phí nhỏ nhất 7 4 9 j i 5 50 25 3 80 7 4 9 (25) → Hiệu của 2 chi phí nhỏ nhất 7 4 j i 5 50 3 55 7 (5) 4 (50) → f = 630 Vậy phương án cực biên ban đầu là 30005055015502500 Bài 11c Hiệu của 2 chi phí nhỏ nhất 1 1 9 j i 50 80 70 3 75 4 7 12 3 65 5 8 15 3 60 6 7 3 (60) → Hiệu của 2 chi phí nhỏ nhất 1 1 3 j i 50 80 10 3 75 4 7 12 (10) 3 65 5 8 15 → Hiệu của 2 chi phí nhỏ nhất 1 1 j i 50 80 3 65 4 (50) 7 3 65 5 8 → Hiệu của 2 chi phí nhỏ nhất 1 j i 80 7 15 7 (15) 8 65 8 (65) → f = 1125 Vậy phương án cực biên ban đầu là 50151006500060 Bài 12c Hiệu của 2 chi phí nhỏ nhất 4 1 4 1 j i 5 9 9 7 2 10 7 8 5 3 2 12 2 (5) 4 5 9 1 8 6 3 1 2 → Hiệu của 2 chi phí nhỏ nhất 2 4 1 j i 9 9 7 2 10 8 5 3 1 7 4 5 9 1 8 3 1 (8) 2 → Hiệu của 2 chi phí nhỏ nhất 4 0 6 j i 9 1 7 2 10 8 5 3 (7) 1 7 4 5 9 → Hiệu của 2 chi phí nhỏ nhất 4 0 j i 9 1 3 3 8 5 1 7 4 (7) 5 → Hiệu của 2 chi phí nhỏ nhất 8 5 j i 2 1 3 3 8 (2) 5 (1) → f = 88 Vậy phương án cực biên ban đầu là 025700170080