Bài giảng Quy hoạch tuyến tính - Chương 3: Bài toán vận tải

Mời các bạn tham khảo Bài giảng Quy hoạch tuyến tính - Chương 3: Bài toán vận tải sau đây để cung cấp cho các bạn những kiến thức về bài toán vận tải cân bằng thu phát, phương án cực biên, thuật toán thế vị, một số trường hợp đặc biệt.
Nội dung trích xuất từ tài liệu:
Bài giảng Quy hoạch tuyến tính - Chương 3: Bài toán vận tảiQUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TOÁN VẬN TẢICHƯƠNG 3. BÀI TOÁN VẬN TẢI1Bài toán cân bằng2Phương án cực biên3Thuật toán thế vị4Một số trường hợp đặc biệt1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT1.1. Lập mô hình bài toán:Có một loại hàng cần được chuyên 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ảo1QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TOÁN VẬN TẢI1. BÀI TOÁN VẬN TẢI CÂN BẰNG THU PHÁT1.2. Bài toá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 hoá (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 hoá (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 2cmjcmnYêu cầu bài toá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ảo2QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TOÁN VẬN TẢI1. BÀI TOÁ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 TOÁN VẬN TẢI CÂN BẰNG THU PHÁT1.3. Tính chất: Bài toán có tập phương án khác rỗng và luôn 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 Hoàng Tuấn soạn thảo3QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TOÁ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 quá 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ảo4QUY HOẠCH TUYẾN TÍNHCHƯƠNG 3. BÀI TOÁ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 quá (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 Hoàng Tuấn soạn thảo5