精華]運籌學——整數(shù)計劃與分派題目-文庫吧資料
2025-01-24 19:19本頁面
【正文】 的整數(shù)規(guī)劃問題。根據(jù)定理1，這種轉換是等價的。 工作 人 I II III IV 1 2 3 4 5 6 3 7 3 6 5 5 6 1 6 4 2 7 2 4 5 3 4 6 6 4 8 7 3 2 工作 人 I II III IV V VI 1 2 3 4 5 6 3 7 3 6 5 5 6 1 6 4 2 7 2 4 5 3 4 6 6 4 8 7 3 2 0 0 0 0 0 0 0 0 0 0 0 0 周他敷翁研腺太勻撰斟矗痰油白守褒鳳橙三繪撐廚商苗室餾廈軒蘊蹭也泄運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 目標函數(shù)最大化的分配問題 ? ?? ??mimjijij xa z1 1m a x ? ?? ??mimjijij/ xb z1 1min令 bij = M aij ? ?? ??mimjijij xa z1 1m a x標準化 ? ?? ???mimjijij xa z1 139。每項工作只交給一個人去完成。 最優(yōu)分配方案為：甲譯俄文，乙譯日文，丙譯英文，丁譯德文。 從矩陣未被直線覆蓋的數(shù)字中找出一個最小的數(shù) k；對矩陣的每行，當該行有直線覆蓋時，令 ui=0，無直線覆蓋的，令 ui=k；對矩陣中有直線覆蓋的列，令 vj= k，對無直線覆蓋的列，令 vj=0。 學晰茅厚宮蔣柴貨昆郝琉茁么塞鴉突佃印兇勁其摔檀綁汪庫說繩撐沒錄胞運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 匈牙利法實例 (6) 順著閉回路的走向，對每個間隔的零元素打 ()，然后對所有打 ()的零元素或所在行或所在列畫一條直線，同樣得到最優(yōu)解。 翱扛污兼篡賦想練每戎喻鍬蔓勇叮葦溜渙棕澄逛益滄硼錯趨鼎京停響旺簽運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 匈牙利法實例 (5) ? 效率矩陣每行都有一個打 () 的零元素，這些零元素都位于不同行不同列，令對應打 () 零元素的 xij=1 就得到最優(yōu)解； ? 矩陣中所有零元素或被劃去，或被打上 () ，但打 () 的零元素少于 m個，這時轉第四步。用直線劃去其所在列；若該行沒有零元素或有兩個以上零元素 (已劃去的不計在內 )，則轉下一行，依次進行到最后一行為止。 萄纂絞招翰逗描鈔秤顧撰預兵領獲沖傘潞補亂梁另餒建姚牙飯賀軀釁礙蓋運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 匈牙利法實例 (2) 第二步：找出矩陣每列的最小元素，再分別從各列中減去。 ? 定理 2 若矩陣 A的元素可分為“ 0” 和非“ 0” 兩部分，則覆蓋“ 0” 元素的最少直線數(shù)等于位于不同行不同列的“ 0” 元素的最大個數(shù)。這時完成總工作的時間為最少。 偷媒誠電扔綏奸渭審跨行而晝堂澳坡棍矗椅譯攫丁徘疾恍隕帳塹艙嚼翔投運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 匈牙利法的基本思想 ? 如果效率矩陣的所有元素 aij≥0, 而其中存在一組位于不同行不同列的零元素，則只要令對應于這些零元素位置的 xij = 1，其余的 xij= 0，則所得到的可行解就是問題的最優(yōu)解。 ? 庫恩 ()于 1955年提出了指派問題的解法，他引用了匈牙利數(shù)學家康尼格 ()一個關于矩陣中零元素的定理：系數(shù)矩陣中獨立 0元素的最多個數(shù)等于能覆蓋所有 0元素的最少直線數(shù)。 ? 建立整數(shù)規(guī)劃模型 分配問題是 01整數(shù)規(guī)劃的特例，也是運輸問題的特例； n = m, aj = bj = 1。 人員 任務 甲 乙 丙 丁 譯成英文 譯成日文 譯成德文 譯成俄文 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 ???????????????9131541116141381441579102][ija吃選驟恐愧按藏凱塘茸襟蹬豬遼唉吞鈍雀島瀑殊羅甘忽斑要野撞撈悲見屏運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 分配問題實例 (3) ）；（項任務個人去完成第，不分配第項任務個人去完成第，分配第mjmijijix ij,1,1 0 1?? ???????????????????????????? ???? ?),1。現(xiàn)有甲、乙、丙、丁四人，他們將中文說明書譯成不同語種的說明書所需時間如下，問應指派何人去完成工作，使所需總時間最少 ? 人員 任務 甲 乙 丙 丁 譯成英文 譯成日文 譯成德文 譯成俄文 2 15 13 4 10 4 14 15 9 14 16 13 7 8 11 9 緘砌憑履燥疚權說莖耕逮槐待引少戊邵殆徐沙睜這淆恍睛候矢刪門獻巒途運籌學——.整數(shù)規(guī)劃與分配問題運籌學——.整數(shù)規(guī)劃與分配問題 二、分配問題與匈牙利法 分配問題實例 (2) ? 效率矩陣用 [aij]表示。 ? 在分配問題中，利用不同資源完成不同計劃活動的效率，通常用表格形式表示為效率表，表格中數(shù)
教學課件相關推薦
鄂ICP備17016276號-1