Bài giảng Tối ưu hóa: Chương 3 - ThS. Phạm Trí Cao

Bài giảng Tối ưu hóa chương 3 trình bày về bài toán vận tải. Chương này cung cấp cho người học các nội dung: Bài toán vận tải cân bằng thu phát, các khái niệm và định nghĩa, thuật toán thế vị, bài toán vận tải không cân bằng thu phát, bài toán dạng vận tải có hàm mục tiêu cực đại,... Mời các bạn cùng tham khảo.
Nội dung trích xuất từ tài liệu:
Bài giảng Tối ưu hóa: Chương 3 - ThS. Phạm Trí CaoThS. Phạm Trí Cao * Chương 3 03/01/2014  I) BAØI TOAÙN VAÄN TAÛI CAÂN BAÈNG THU PHAÙT CHÖÔNG 3:  1) Baøi toaùn  Coù m ñòa ñieåm A1, A2, ..., Am cuøng saûn BAØI TOAÙN VAÄN TAÛI xuaát 1 loaïi haøng vôùi caùc löôïng haøng töông öùng laø a1, a2, .., am. Coù n ñòa ñieåm tieâu thuï loaïi haøng treân laø B1 , B2 , ..., Bn vôùi caùc yeâu caàu töông öùng laø b1 , b2 ,.., bn.  Ta goïi Ai laø traïm phaùt thöù i, Bj laø traïm thu thöù j. Ta coù caùc giaû thieát sau: Giaûi: * Haøng coù theå chôû töø traïm phaùt Ai baát kyø ñeán traïm Goïi xij laø soá ñôn vò haøng chuyeân chôû töø traïm thu Bj baát kyø. phaùt (i) ñeán traïm thu (j). * Chi phí chuyeân chôû 1 ñôn vò haøng töø traïm phaùt (i) * Ñieàu kieän cho bieán goïi: xij >=0 , i,j ñeán traïm thu (j) laø cij , cij >=0 * Ñieàu kieän ñeå caùc traïm phaùt thì phaùt heát haøng: n * Toång löôïng haøng coù ôû m traïm phaùt (toång phaùt)  x ij = ai : traïm phaùt (i) phaùt heát haøng j 1 = toång löôïng haøng yeâu caàu ôû n traïm thu (toång thu): m n * Ñieàu kieän ñeå caùc traïm thu thì thu ñuû haøng:  a i =  b j (ñk caân baèng thu phaùt) m i 1 j 1  x = bj : traïm thu (j) thu ñuû haøng i  1 ij Haõy laäp phöông aùn vaän chuyeån haøng sao cho: caùc * Toång chi phí vaän chuyeån laø: traïm phaùt thì phaùt heát haøng, caùc traïm thu thì thu ñuû n m m n f(X)=   c x    c x haøng vaø toång chi phí vaän chuyeån laø nhoû nhaát? j 1 i 1 ij ij i 1 j 1 ij ij 1ThS. Phạm Trí Cao * Chương 3 03/01/2014 Vaäy moâ hình baøi toaùn vaän taûi laø: 2) Baûng vaän taûi Ta ghi taát caû caùc tham soá cuûa baøi toaùn vaøo Tìm ma traän X= (xij)m*n sao cho: baûng sau, goïi laø baûng vaän taûi: n m f(X)=   c x  min (1) T B1 Bj Bn j 1i1 ij ij F (b1) (bj) (bn) n A1 c11 c1j c1n  x ij = ai , i (2) (a1) x11 x1j x1j j 1 Ai ci1 cij cin m (ai) xi1 xij xin  x ij = bj , j (3) Am cm1 cmj cmn i 1 (am) xm1 xmj xmn xij >=0 , i,j (4) Ví duï soá:  Ta coù moâ hình baøi toaùn laø: Giaû söû ta coù 2 traïm phaùt vaø 3 traïm thu. Löôïng ...