整數規(guī)劃問題及分配問題(參考版)
2024-10-22 19:51本頁面
【正文】 從表面看 ， 似乎有 6個最優(yōu)解 ， 但根據問題的特殊性 ， 它們都是相同的 ， 即 ??????????10010000001010132154321AAABBBBB所以 ， 最優(yōu)指派方案是 總的建造費用最省 ， 是 4+7+9+8+7=35萬元 。2239。 ?iAi 現在 ， 用匈牙利解法求最優(yōu)指派方案如下： ?????????????????????????????????????????????????????????00051200051203610130361013057000057000C???????????????????????????????????????????????????????????????***********39。反映投標費用的系數矩陣為 4A 5A21,AA 3A ??????????71012814151296179778432154321AAABBBBB由于每家建筑公司最多可承建兩個新商店 ， 因此 ， 把每家建筑公司化作相同的兩家 （ 和 ） 。 根據實際情況 ， 可以允許每家建筑公司承建一個或兩個商店 。 若某人可做幾件事，則可將該人化作相同的幾個“人”來接受指派，這幾個“人”做同一件事的費用系數當然都一樣。 若人多事少 ， 則添上一些虛擬的 “ 事 ” ， 這些 “ 事 ”被各人做的費用系數同樣可取 0， 也可取足夠大的數 M。 人數和事數不等的指派問題 若人少事多 ， 則添上一些虛擬的 “ 人 ” 。 nnijaA ?? )(m nnijnnij ambB ?? ??? )()(例 711 矩陣 ?????????????9118713161491514410413152A 的最大元素為 ， 取 ， 求出 B矩陣 1633 ?a 16?m??????????????????????????????????????????758930271212612311491611168167161316161614169161516141641610164161316516216B 則以 B為系數矩陣的最小化指派問題和以 A為系數矩陣的最大化指派問題有相同最優(yōu)解 。 商業(yè)公司應當對五家建筑公司怎樣分配建造任務 ， 才能使總建造費用最少 ？ 54321 , BBBBB54321 , AAAAAiAjB ijc2A3A4A5A 4 8 7 15 12 7 9 17 14 10 6 9 12 8 7 6 7 14 6 10 6 9 12 10 6 1B 2B 3B 4B 5B1Aijc jBiA????????????????)0(4320405)0(12323771811)0(300)0(0*****對各行元素分別減去本行的最小元素 ， 對各列也如此 ， 得 ??????????????????????????????????????????????????0432040501232377181103000004630408112633710281134000061012961061477812910141791215786674? ? ? 利用匈牙利法求得最優(yōu)解為： 54321*1000001000000000100100100AAAAAX?????????????????54321 , BBBBB總的建設費用最少為 34萬元 不規(guī)范形式的轉化 要求所有 aij ?0 若某些 aij 0 ，則利用定理 1 進行變換，使所有 bij ? 0 目標函數為 min型 對于 max型目標函數，將效率矩陣中所有 aij 反號，則等效于求 min型問題；再利用定理 1 進行變換，使所有 bij ? 0，則可采用上述算法 三、 一般的指派問題 最大化指派問題 設最大化指派問題系數矩陣 ， 其中最大元素 為 。 為了盡早建成營業(yè) ， 商業(yè)公司通知了 五個建筑公司 ， 以便讓每家新商店由一個建筑公司承建 。 （ 5）出現 c情況的處理方法（劃線過程） 行表示人，列表示任務 ?對沒有標記 ( ) 的行打 ?(沒有安排任務 ) ?對打 ? 行上所有其它零元素 0*對應的列打 ?(任務被安排 ) ?再對打 ? 列上有 ( ) 標記的零元素對應的行打 ? ?重復上面 3步驟，直至無法繼續(xù) ?對沒有打 ? 的行劃橫線 (已經安排任務 )，對所有 打 ? 的列劃垂線 (任務已經被安排 ) ? ??????????????221*0*02)0(1123)0(*0)0(23? ? 劃線后會出現兩種情況： (1) 標記 ( )的零少于 m個，但劃有 m條直線，說明矩
教學課件相關推薦
鄂ICP備17016276號-1