This Paper A short summary of this paper 37 Full PDFs related to this paper
QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢICHƯƠNG 3. BÀI TỐN VẬN TẢI1Bài tốn cân bằng2Phương án cực biên3Thuật tốn thế vị4Một số trường hợp đặc biệt1. BÀI TỐN VẬN TẢI CÂN BẰNG THU PHÁT1.1. Lập mơ hình bài tốn:Có một loại hàng cần được chun chở từ haikho (trạm phát) P1 và P2 tới ba nơi tiêu thụ (trạm thu)T1, T2, T3 . Lượng hàng có ở hai kho và lượng hàngcần ở ba nơi tiêu thụ cũng như số tiền vận chuyển mộtđơn vị hàng từ mỗi kho đến các nơi tiêu thụ được choở bảng sau:1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁTTHUPHÁTP130 tấnP275 tấnT135 tấnT225 tấnT345 tấn523211Tìm phương án vận chuyển thỏa yêu cầu về thuphát sao cho chi phí vận chuyển bé nhất.Nguyễn Hoàng Tuấn soạn thảo1 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI1. BÀI TỐN VẬN TẢI CÂN BẰNG THU PHÁT1.2. Bài tốn cân bằng:Giả sử có m kho là nơi phát hay cung cấp hànghoá, kho thứ i chứa ai đơn vị hàng hố (i = 1,2,..,m);có n nơi tiêu thụ hay nhận hàng hoá, nơi nhận thứ jcần bj đơn vị hàng hố (j = 1,2,..,n).Giá tiền hay cước phí vận chuyển một đơn vịhàng hóa từ kho thứ i đến nơi nhận thứ j là cij đơn vịtiền tệ.Bài toán được gọi là cân bằng nếu tổng lượngmnphát = tổng lượng thu: ai b ji 1j 11. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁTBài toán vận tải thường cho dưới dạng bảng sau:Thub1b2…bj….bnPháta1c11c12c1 jc1na2c21c22c2 jc2n………aici 1ci 2cijcin………amcm 1cm 2cmjcmnu cầu bài tốn: tìm cách phân bổ lượng hàng vậnchuyển xij từ trạm phát i đến trạm thu j thỏa:1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁTTổng chi phí vận chuyển thấp nhấtm nf cij xij min(1.2)i 1 j 1Tổng lượng hàng phát đin xij ai i 1, m (1.3)Tổng lượng hàng nhận vềm xij b j j 1, n (1.4)j 1i 1Một phương án bài toán (bộ xij thỏa 1.3 và 1.4) códạng ma trận nên cũng gọi là ma trận phương án.Nguyễn Hoàng Tuấn soạn thảo2 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI1. BÀI TỐN VẬN TẢI CÂN BẰNG THU PHÁTVí dụ: Xét lại bài toán vận tải đã biết ở trênTHUPHÁTP130 tấnP275 tấnT135 tấnT225 tấnT345 tấn523211 bài toán vận tải cân bằng thu phát1. BÀI TỐN VẬN TẢI CÂN BẰNG THU PHÁT1.3. Tính chất: Bài tốn có tập phương án khác rỗng và ln cóphương án tối ưu. Ma trận cước phí có hạng = m + n – 1.2. PHƯƠNG ÁN CỰC BIÊN2.1. Ơ chọn, ơ loại:§2Ta viết (i ; j) là ô dòng i và cột j của bảng.Những ô trong bảng có lượng hàng phân phối xij > 0gọi là ô chọn. Ngược lại, những ô có lượng hàng phânphối xij = 0 gọi là ơ loại.Nguyễn Hồng Tuấn soạn thảo3 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI2. PHƯƠNG ÁN CỰC BIÊN2.2. Tập ô đường đi:Tập ô đường đi (gọi tắt “đường đi”) là tập hợpcác ô trong bảng thỏa có một và chỉ một ơ khác cũngthuộc “đường đi” nằm trên cùng dịng hoặc cùng cộtvới nó, gọi là hai ơ liên tiếp.Nhận xét: Trên một dịng hay cột của “đường đi”có khơng q hai ơ.2. PHƯƠNG ÁN CỰC BIÊNVí dụ 1.••••••2. PHƯƠNG ÁN CỰC BIÊNVí dụ 2.●●●●●Nguyễn Hoàng Tuấn soạn thảo4 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI2. PHƯƠNG ÁN CỰC BIÊN2.3. Chu trình:Một đường đi khép kín được gọi là một chu trình.Ví dụ 1.••••••2. PHƯƠNG ÁN CỰC BIÊNVí dụ 2.●●●●●●●●2. PHƯƠNG ÁN CỰC BIÊN2.4. Tính chất:Xét bảng vận tải có m dịng và n cột.a) Tập ơ chọn khơng là chu trình có khơng q (m+ n – 1) ơ.b) Tập ơ chọn khơng là chu trình có đủ (m + n – 1)ơ. Ta thêm vào tập ơ này một ơ loại bất kì thì ơ nàycùng với một số ơ chọn đã có sẽ tạo thành chu trìnhduy nhất đi qua nó.Nguyễn Hồng Tuấn soạn thảo5 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI2. PHƯƠNG ÁN CỰC BIÊNVí dụ 2.4. Xét bài tốn vận tải có 3 dịng, 4 cột vớimột phương án có 3 + 4 – 1 = 6 ô chọn:●●●●●●2. PHƯƠNG ÁN CỰC BIÊN2.5. Phương án cực biên:Phương án cực biên trong bài tốn vận tải làphương án có tập ơ chọn của nó khơng chứa chutrình.2. PHƯƠNG ÁN CỰC BIÊNVí dụ 2.4. Xét phương án trong bài toán vận tải chobởi bảng sau:3080455540505757412213040Nguyễn Hoàng Tuấn soạn thảo360235159501066 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI2. PHƯƠNG ÁN CỰC BIÊN2.6. Phương pháp thành lập2.6.1. Nguyên lý phân bổ tối đa ô chọn.Phân bổ lượng hàng nhiều nhất có thể cho ơ đã đượcchọn xij = min{ai ; bj}, có hai trường hợp sau: Trạm thu nhận đủ hàng thì tạm xố trạm này và ghinhớ lượng hàng thừa ở nơi phát. Trạm phát chuyển hết hàng thì tạm xóa trạm phátnày và ghi nhớ lượng hàng còn thiếu ở nơi thu.2. PHƯƠNG ÁN CỰC BIÊN2.6. Phương pháp thành lập2.6.2. Nguyên tắc chọn ô phân bổ.Ba cách:- Góc Tây Bắc: từ trên xuống dưới và từ trái qua phải ô đầu tiên (1;1) dễ nhớ nhưng phương án tìmđược kém (f cách xa f tối ưu)- Ơ có cước phí nhỏ nhất dễ nhớ, phương án vừa- Ơ chọn Fogel khó nhưng phương án tìm đượctốt (f rất gần f tối ưu), thực hiện như sau:2. PHƯƠNG ÁN CỰC BIÊN+ Bước 1: Tính hiệu số giữa hai ơ có cước phí nhỏnhất của mỗi dịng và mỗi cột của ma trận cước phí.+ Bước 2: Ơ được chọn là có ơ cước phí nhỏ nhấtcủa dịng hay cột có hiệu số này lớn nhất.Hai nguyên tắc này phối hợp xen kẽ nhau và lặp lạiđến khi ta được phương án hoàn chỉnh.Nguyễn Hoàng Tuấn soạn thảo7 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI2. PHƯƠNG ÁN CỰC BIÊNVí dụ 2.6. Thành lập một phương án cực biên của bàitốn vận tải sau:j30405060i80157245574955122363. THUẬT TỐN THẾ VỊ1: Thành lập phương án cực biên ban đầu§BƯỚC3(xuất phát) theo Nguyên lý phân bổ tối đa với các ôchọn phân bổ bằng các phương pháp: góc Tây Bắc,cước phí thấp nhất, Fogel,…BƯỚC 2: Xét dấu hiệu tối ưu của phương án. Tìm các biệt số dịng ui và biệt số cột vi của phươngán bằng cách giải hệ phương trình ơ chọn:uivjcij3. THUẬT TỐN THẾ VỊBƯỚC 2: Xét dấu hiệu tối ưu của phương án.Hệ này chứa (m + n) ẩn nhưng chỉ có nhiều nhất(m + n – 1) phương trình có một ẩn được chọntrước làm tham số kĩ thuật giải: cho ẩn màhàng/cột của nó có nhiều ơ chọn nhất bằng 0. Tính các ước lượng cho các ô loại:ui v j cijij Nếu mọi ∆ ≤ 0 phương án đang xét tối ưu.Ngược lại, nếu có ∆ > 0 phương án khơng tối ưu Bước 3Nguyễn Hồng Tuấn soạn thảo8 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI3. THUẬT TỐN THẾ VỊVí dụ 3.1. Xét khả năng tối ưu của phương án trongbảng vận tải sau:j30i80145554050605725749122330503510640153. THUẬT TOÁN THẾ VỊVí dụ 3.2. Xét khả năng tối ưu của phương án trongbảng vận tải sau:308040150605729305045574551223456405103. THUẬT TỐN THẾ VỊVí dụ 3.3. Xét khả năng tối ưu của phương án trongbảng vận tải sau :j30i14050605727492380205604510123565540Nguyễn Hoàng Tuấn soạn thảo159 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI3. THUẬT TOÁN THẾ VỊBƯỚC 3: Cải tiến phương án cực biên mới tốt hơn. Đưa ơ loại có ước lượng ∆ lớn nhất bổ sung thành ôchọn của phương án ô này kết hợp với một số ôchọn đã có trong phương án tạo thành chu trình Kduy nhất đi qua nó. Đánh dấu âm/dương +/– xen kẽ cho chu trình Knày. Bắt đầu từ ơ chọn mới bổ sung mang dấu + đếnhết. Sau đó chia chu trình K thành hai tập ô sau:K+ = {ô (i ; j) mang dấu +}K– = {ô (i ; j) mang dấu –}3. THUẬT TOÁN THẾ VỊBƯỚC 3: Cải tiến phương án cực biên mới tốt hơn. Xác định lượng hàng điều chỉnh:q = min{xij, với (i ; j) ϵ K–} Xây dựng phương án cực biên mới từ phương áncực biên cũ đang có như sau: xij q;(i, j ) K xij xij q;(i, j ) K x;(i, j ) K ij3. THUẬT TOÁN THẾ VỊVí dụ 3.5. Từ phương án này, hãy tìm phương án tốiưu của bài tốn.j30i80145554050605725749122330503540Nguyễn Hồng Tuấn soạn thảo1061510 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI3. THUẬT TỐN THẾ VỊVí dụ 3.6. Từ phương án này, hãy tìm phương án tốiưu của bài tốn.308040150605729305045574551223456405103. THUẬT TỐN THẾ VỊVí dụ 3.7. Từ phương án này, hãy tìm phương án tốiưu của bài tốn.j30i4015507602803040105741223945405655553. THUẬT TỐN THẾ VỊVí dụ 3.8. Giải bài toán vận tải với phương án cựcbiên ban đầu được cho trong bảng sau:30907040503802541374304012050Nguyễn Hoàng Tuấn soạn thảo40620254011 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI3. THUẬT TỐN THẾ VỊVí dụ 3.9. Giải bài tốn vận tải:508020604070551279114234. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT4.1. Phương án suy biến.Phương án suy biến là phương án có ít hơn(m + n – 1) ơ chọn.Cách giải bài tốn vận tải có phương án cực biênban đầu suy biến: bổ sung thêm các ơ loại bất kì củabảng làm ơ chọn giả (lượng hàng phân bổ xij = 0) chođủ (m + n – 1) ô chọn và đảm bảo không tạo thànhchu trình phương án cực biên khơng suy biến tiếp tục giải bằng thuật toán thế vị.4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆTVí dụ 4.1.1. Giải bài tốn bảng vận tải từ phương ánvận chuyển ban đầu sau:j40i1100602424541250380404017020505100100Nguyễn Hoàng Tuấn soạn thảo12 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆTVí dụ 4.1.2. Giải bài tốn vận tải với phương án banđầu sau:25103020251053576810253522204. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT4.2. Bài tốn vận tải khơng cân bằng thu phátHướng giải quyết: Thêm vào các trạm phát/thu giảcó cước phí = 0 để chuyển bài tốn thành cân bằng.• Trường hợp phát > thu thêm trạm thu giả bn+1với lượng hàng = Σphát – Σthu• Trường hợp phát < thu thêm trạm phát giảam+1 với lượng hàng = Σthu – Σphát4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆTVí dụ 4.2. Giải bài tốn vận tải khơng cân bằng thuphát cho bởi bảng vận tải sau:j405080i9061140574704113Nguyễn Hoàng Tuấn soạn thảo13 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT4.3. Bài tốn có ơ cấmVì một lí do nào đó, có một nơi phát khơng thểchuyên chở hàng đến một nơi nhận được.Phương pháp giải: xóa cấm và gán cước phí giả =∞. Tiếp tục giải bài toán bằng thuật toán thế vị đã học.4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆTVí dụ 4.3. Giải bài tốn vận tải có ơ cấm cho bởi bảngsau:j100i807015066551098954011105774. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆT4.4. Bài toán lợi nhuận lớn nhấtBài toán vẫn giải bằng thuật toán thế vị như trênnhưng với nguyên tắc chọn ô chọn ngược lại: ô chọnlà ơ có lợi nhuận lớn nhất.Nguyễn Hồng Tuấn soạn thảo14 QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TỐN VẬN TẢI4. MỘT SỐ TRƯỜNG HỢP ĐẶC BIỆTVí dụ 4.4. Giải bài tốn vận tải lợi nhuận lớn nhất sau:j70i5585606511101065798749080100Nguyễn Hoàng Tuấn soạn thảo15 |
