[高等教育]運(yùn)籌學(xué)4整數(shù)規(guī)劃-資料下載頁
2025-01-19 19:10本頁面
【正文】 ??Min ① 從只有一個(gè)０元素的行開始 ， 給該０元素加圈 ， 同時(shí)劃去 該０元素所在列的其它０元素； ????????????006330009051490159② 從只有一個(gè)０元素的列開始，給該０元素加圈，同時(shí)劃去該０元素所在行的其它０元素； 第二步：在各行各列中找出獨(dú)立的０元素． ????????????006330009051490159第三步：用最少的直線覆蓋所有 “ 0”， ① 對沒有◎的行打 “ √” ②在已打 “ √” 的行中，對所有０所在列打“ √” ③ 在已打 “ √” 的列中，對 ◎ 所在行打 “ √” ④重復(fù) √ √ √ 第三步：用最少的直線覆蓋所有 “ 0”， ????????????006330009051490159√ √ √ ⑤ 對沒有打 “ √” 的行畫一橫線， 對打 “ √” 的列畫一垂線． 第四步：這里直線數(shù)等于 3（ 等于 4時(shí)停止運(yùn)算 ） ， 要進(jìn)行下一輪計(jì)算 。 （ 1） 從矩陣未被直線覆蓋的數(shù)字中找出一個(gè)最小的數(shù) a， 表中 a＝５ 。 (2) 直線相交處的元素加上 a， 未被直線覆蓋的元素減去 a，被直線覆蓋而沒有相交的元素不變 ， 得到下列矩陣 4 1 0 0 49 0 0 40 0 5 33 6 5 0????????????√ ????????????006330009051490159√ √ 重復(fù)第二步 :在各行各列中找出獨(dú)立的０元素． 4 1 0 0 49 0 0 40 0 5 33 6 5 0???????????? 第五步：最優(yōu)分配 最優(yōu)解： ????????????1111＝X最優(yōu)值 Z＝ 73＋ 87＋ 82＋ 88＝ 330 ????????????88809086907983829578879590739285＝C4 1 0 0 49 0 0 40 0 5 33 6 5 0???????????? 工作 人員 A B C D 甲 85 92 73 90 乙 95 87 78 95 丙 82 83 79 90 丁 86 90 80 88 ????????????1111＝X甲 → C 乙 → B 丙 → A 丁 → D 最優(yōu)分配 ● 不平衡的指派問題 1．當(dāng)人數(shù) m小于工作數(shù) n時(shí)，加上 n－ m個(gè)人，例如 ??????????1716131074569102022????????????00001716131074569102022Min 9 4 10 0 6 1 1 1 02 1 0 30 3 6 70 0 0 0???????? 0 0 0 10 0 1 01 0 0 00 1 0 0X????????????＝2．當(dāng)人數(shù) m大于工作數(shù) n時(shí)，加上 m－ n項(xiàng)工作，例如 ????????????????1235461714836111095????????????????00000000001235461714836111095● 求最大值的指派問題 匈牙利法的條件是：模型求最小值、效率 cij≥0 令 ??)(m a x,ijijjicMCcM????則 iji jij xcw ? ? ??m iniji jij xcz ? ??m a x與 的最優(yōu)解相同。 設(shè) C=(cij)m m 對應(yīng)的模型是求最大值 將其變換為求最小值 iji jij xcz ? ??m a x【 例５ .9】 某人事部門擬招聘 4人任職 4項(xiàng)工作，對他們綜合考評的 得分如下表（滿分 100分），如何安排工作使總分最高。 ????????????88809086907983829578879590739285丁丙乙甲＝C【 解 】 M＝ 95，令 )95( ijcC ????????????????71559516121301780522310＝C?????????????21004011780178021907＝C用匈牙利法求解： ?????????????71559516121301780522310＝C?????????????2022017807802907＝C0 1 0 01 0 0 00 0 0 10 0 1 0X????????????＝最優(yōu)解： 即甲安排做第二項(xiàng)工作、乙做第一項(xiàng)、丙做第四項(xiàng)、丁做第三項(xiàng)。 總分為： Z＝ 92＋ 95＋ 90＋ 80＝ 357 ● 其它 某工廠訂購了 3臺機(jī)器 (A、 B、 C），有 4個(gè)位置可供機(jī)器安裝，但 B機(jī)器不能安裝在第二號位置。由于這 4個(gè)安裝位置離工廠中心的遠(yuǎn)近不同，所需要的運(yùn)送費(fèi)用也就不同，見下表。問這些機(jī)器安裝在哪幾個(gè)位置合適，可使總的運(yùn)送費(fèi)用達(dá)到最小。 位置 機(jī)器 一 二 三 四 A 13 10 12 11 B 15 13 20 C 5 7 10 6 解： 1）在（ B，二）處添上一個(gè)很大的數(shù) M，以排除機(jī)器 B安 裝在二號位置的可能。 2）在第四行虛設(shè)一行。 13 10 12 1115 13 205 7 10 60 0 0 0MC????????＝13 10 12 1115 13 205 7 10 60 0 0 0MC????????＝3 0 2 12 0 70 2 5 10 0 0 0M????????????0 1 0 00 0 1 01 0 0 00 0 0 1X????????????＝本章介紹了整數(shù)規(guī)劃的數(shù)學(xué)模型的特征及其應(yīng)用； 1． 整數(shù)規(guī)劃的最優(yōu)解是先求相應(yīng)的線性規(guī)劃的最優(yōu)解然后取整得到 . 2． 部分變量要求是整數(shù)的規(guī)劃問題稱為純整數(shù)規(guī)劃 . 3． 求最大值問題的目標(biāo)函數(shù)值是各分枝函數(shù)值的上界 . 4． 求最小值問題的目標(biāo)函數(shù)值是各分枝函數(shù)值的下界 . 5． 變量取 0或 1的規(guī)劃是整數(shù)規(guī)劃 . 求解方法有：解一般整數(shù)規(guī)劃用分枝定界法、割平面法； 解 0－ 1規(guī)劃用隱枚舉法； 解指派問題用匈牙利法。 試一試，下例結(jié)論是否正確： 6． 整數(shù)規(guī)劃的可行解集合是離散型集合 . 7． 將指派 （ 分配 ） 問題的效率矩陣每行分別加上一個(gè)數(shù)后最優(yōu)解 不變 . 8． 匈牙利法求解指派問題的條件是效率矩陣的元素非負(fù) . 9． 匈牙利法可直接求解極大化的指派問題 . 10． 高莫雷 （ R..） 約束是將可行域中一部分非整數(shù)解切割掉 . 11． 指派問題也是一個(gè)特殊的運(yùn)輸問題 . 12． 指派問題也可用運(yùn)輸問題求其最優(yōu)解 . 13． 在用隱枚舉求解具有 n個(gè)變量的 01規(guī)劃時(shí)需枚舉 2的 n次冪個(gè)可能 . 作業(yè)：教材 P The End of Chapter 5
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號-1