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

 PAGE \* MERGEFORMAT 21 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átb1b2…bna1c11 X11…c1n X1na2c21 X21c22 X22…c2n X2n……………amCm1 Xm1cm2 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. xxxxxxDâ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. xxxxxxdâ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. xxxxxxxxxxxxxxxxMộ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 i508070754(50)71265581560673 j i8070257(25)12658156073 j i5570658(55)156073 j i701015(10)603 j i70603(60) j i508070754(50)7(25)126558(55)15(10)60673(60) Vậy phương án cực biên ban đầu là 5000010001, f=1145 Bài 2a j i502030606(50)1240543 j i2030101(10)24043 j i1030404(10)3 j i30303(30) j i502030606(50)1(10)24054(10)3(30) Vậy phương án cực biên ban đầu là 5010001030, f= 440 Bài 3a j i455560705(45)2390214 j i5560252(25)39014 j i3060901(30)4 j i60604(60) j i455560705(45)2(25)39021(30)4(60) Vậy phương án cực biên ban đầu là 4525003060, f=545 Bài 4a j i4555608030705(45)2361090214945065586601121377 j i55608030252(25)361090149450558660121377 j i30608030901(30)49450558660121377 j i608030604(60)9450586601377 j i8030508(50)66077 j i3030607(30)7 j i30307(30) j i4555608030705(45)2(25)36109021(30)4(60)94506558(50)660112137(30)7(30) Vậy phương án cực biên ban đầu là 452500003060000005000003030, f= 1365 Bài 5a j i60605080100608070→ j i60508040408070→ j i205080802070→ j i5080605070→ j i8010107070→ f = 1780 Vậy phương án cực biên ban đầu là 6040020000050101070 Bài 6a j i120144156180150225120175230120 → j i144156180150105105175230120→ j i3915618015017539230120→ j i156180150136136230120→ j i2018015023020120→ j i180150210180120→ j i1503030120120→ 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 130140120160180201822251701525301520045304035 Giải j i13014012016018020(130)1822251701525301520045304035 j i1401201605018(50)2225170253015200304035 j i9012016017025(90)3015200304035 j i1201608030(80)152004035 j i4016020040(40)35 j i16016035(160) Do đó ta có bảng sau: j i13014012016018020(130)18(50)22251701525(90)30(80)15200453040(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 5070608011071181310021171210508181316 Giải j i507060801107(50)1181310021171210508181316 j i7060806011(60)81310017121050181316 j i70608010017(10)121050181316 j i60809012(60)10501316 j i803010(30)5016 j i505016(50) Do đó ta có bảng sau: j i 507060801107(50)11(60)8131002117(10)12(12)10(30)508181316(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 1111132183216122141216124302624126302820 Giải j i1111132(1)183216122141216124302624126302820 j i111114(1)121613026241302820 j i11126(1)2412820 j i1120(1) Do đó ta có bảng sau: j i1111132(1)18321612214(1)12161243026(1)24126302820(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 i3060504045308055→ j i60504015158055→ j i455040804555→ j i5040353555→ j i1540551540→ f = 845 Vậy phương án cực biên ban đầu là 301504500003501540 Bài 11a j i50807075506560→ j i807025256560→ j i5570655560→ j i7010106060→ f = 1145 Vậy phương án cực biên ban đầu là 50250055100060 Bài 12a j i5997105128→ j i99755128 → j i4971248→ j i97888→ j i17817→ 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 i50807075471265581560673(60) j i508010754(50)712655815 j i8010257(25)1265815 j i5510658(55)15 j i101015(10) j i508070754(50)7(25)126558(55)1560673(60) Vậy phương án cực biên ban đầu là 50250055100060, f= 995 Bai 2b j i5020306061(20)240543 j i50304062(30)4053 j i50106405(40) j i10106(10) j i502030606(10)1(20)2(30)405(40)43 Vậy phương án cực biên ban đầu là 1020304000, f= 340 Bài 3b j i455560705239021(55)4 j i45607053352(35)4 j i10607053(60) j i10105(10)j i455560705(10)23(60)902(35)1(55)4 Vậy phương án cực biên ban đầu là 1006035550, f= 355 Bài 4b j i45556080307052361090214945065586601(45)121377 j i556080307023610901(55)49450558615121377 j i608030703(60)6103549450586151377 j i8030106103594(30)50861577 j i80106(10)59508157 j i7059508157(15) j i5559508(50) j i559(5) j i455560803070523(60)6(10)109021(55)49(5)4(30)506558(50)6601(45)12137(15)7 Vậy phương án cực biên ban đầu là 006010005505300005004500150, f= 1010 Bài 5b j i6060508010085978042 (60)587038109→ j i60508010089720458703 (60)109→ j i508010097205 (20)810109→ j i308010097 (80)10109→ j i30209 (20)1010 (10) → f = 1240 Vậy phương án cực biên ban đầu là 0006060020802001010 Bài 6b j i12014415618015022514211223341752419173215230221134162712010 (120)25142736→ j i144156180150225211223341751917321523011 (144)341627→ j i15618015022512 (156)233417517321586341627→ j i1801506923341753215 (150)861627 j i180692325328616 (86)→ j i946923 (69)2532 (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 130140120160180201822251701525301520045304035 Giải j i1301401201601802018222517015(130)25301520045304035 j i14012016018018222540253015(40)200304035 j i14012012018018(140)2225200304035 j i1201204022(40)252004035 j i801202004035(120) j i808040(80) Do đó ta có j i1301401201601802018(140)22(40)2517015(130)253015(40)200453040(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 5070608011071181310021171210508181316 Giải j i507060801107(50)1181310021171210508181316 j i 70608060118(60)1310017121050181316 j i70801001710(80)501816 j i 702017(20)5018 j i505018(50) Do đó ta có bảng sau: j i507060801107(50)118(60)131002117(20)1210(80)50818(501316 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 1111132183216121141216124302624126302820 Giải j i11111321832161221412(1)16124302624126302820 j i1111321816(1)12430241263020 j i11124(1)3012630 j i1130(1) Do đó ta có bảng sau j i1111132183216(1)1211412(1)16124(1)30262412630(1)2820 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 i30605040451 (30)5728057495512236→ j i6050401557280749552 (55)36→ j i5504015572 (15)80749→ j i550258074 (50)9→ j i525307 (5)9 (25)→ f = 630 Vậy phương án cực biên ban đầu là 30005055015502500 Bài 11b j i50807075471265581560673 (60)→ j i508010754 (50)712655815→ j i8010257 (25)1265815→ j i5510658 (55)15 (10)→ f = 1145 Vậy phương án cực biên ban đầu là 50251005500060 Bài 12b j i59971078531224598631(8)2→ j i5917107853122 (5)459→ j i91710853 (7)7459→ j i9138574 (7)5→ j i2138 (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ất1341j i606050802100859728042585703 (60)8109→ Hiệu của 2 chi phí nhỏ nhất341j i605080210059738025 (50)81108109→ Hiệu của 2 chi phí nhỏ nhất31j i60802100576302 (30)811089→ Hiệu của 2 chi phí nhỏ nhất32j i608021005 (30)711089→ Hiệu của 2 chi phí nhỏ nhất2j i8071007 (70)9109 (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ất485712j i1201441561801502225142112233421752419173215 (150)5230221134162741201025142736→ Hiệu của 2 chi phí nhỏ nhất4857j i1201441561802225142112232252419173252302211 (144)3416412010251427→ Hiệu của 2 chi phí nhỏ nhất457j i12015618022251412237252417 (25)3262302234164120101427→ Hiệu của 2 chi phí nhỏ nhất424j i1201311802225141223686223416 (86)4120101427→ Hiệu của 2 chi phí nhỏ nhất424j i120131942225141223412010 (120)1427→ Hiệu của 2 chi phí nhỏ nhất1223j i131941122512 (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ất57810j i130140120160218020182225017015253015520045304035(160) Hiệu của 2 chi phí nhỏ nhất578j i130140120218020182210170152530(120)1040453040Hiệu của 2 chi phí nhỏ nhất57j i130140218020181050152515404530(40) Hiệu của 2 chi phí nhỏ nhất57j i1301002180201810501525(50) Hiệu của 2 chi phí nhỏ nhất2018j i13050218020(130)18 Hiệu của 2 chi phí nhỏ nhất18j i50185018(50) j i13014012016018020(130)18(50)22251701525(50)30(120)152004530(40)4035(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ất1643j i507060801110711813210021171210650818(50)1316 Hiệu của 2 chi phí nhỏ nhất14643j i502060801110711813210021(50)171210 Hiệu của 2 chi phí nhỏ nhất643j i206080311011(20)813250171210 Hiệu của 2 chi phí nhỏ nhất43j i60805908(60)132501210 Hiệu của 2 chi phí nhỏ nhất3j i80133013(30)105010 Hiệu của 2 chi phí nhỏ nhất10j i50105010(50) j i50706080110711(20)8(60)13(30)10021(50)171210(50)50818(50)1316 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ất24140j i111121321832162122141216012430262461263028(1)20 Hiệu của 2 chi phí nhỏ nhất240j i111213218(1)162122141601243024 Hiệu của 2 chi phí nhỏ nhất28j i11612216(1)012424 Hiệu của 2 chi phí nhỏ nhất24j i124124(1) j i111113218(1)3216122141216(1)124302624(1)1263028(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ất4314j i306050401451 (30)572180574915512236→ Hiệu của 2 chi phí nhỏ nhất314j i605040315572 (15)380749155236→ Hiệu của 2 chi phí nhỏ nhất513j i6050253807491552 (55)36→ Hiệu của 2 chi phí nhỏ nhất749j i55025380749 (25)→ Hiệu của 2 chi phí nhỏ nhất74j i5503557 (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ất119j i50807037547123655815360673 (60)→ Hiệu của 2 chi phí nhỏ nhất113j i5080103754712 (10)3655815→ Hiệu của 2 chi phí nhỏ nhất11j i50803654 (50)736558→ Hiệu của 2 chi phí nhỏ nhất1j i807157 (15)8658 (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ất4141j i599721078532122 (5)459186312→ Hiệu của 2 chi phí nhỏ nhất241j i997210853174591831 (8)2→ Hiệu của 2 chi phí nhỏ nhất406j i917210853 (7)17459 → Hiệu của 2 chi phí nhỏ nhất40j i913385174 (7)5→ Hiệu của 2 chi phí nhỏ nhất85j i21338 (2)5 (1)→ f = 88 Vậy phương án cực biên ban đầu là 025700170080