整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃-全文預(yù)覽
【正文】 ness 互補(bǔ)松弛 Sensitivity analysis 靈敏度分析 ? Ttransportation problem 運(yùn)輸問(wèn)題 ? Assignment problem 任務(wù)分配 (指派 ) 問(wèn)題 ? Bipartite matching 兩部圖匹配 Hungarian method 匈牙利算法 16 。令未標(biāo)記零對(duì)應(yīng)的同行同列上其它未標(biāo)記零的個(gè)數(shù)為該零的 指數(shù) ，選 指數(shù)最小 的先標(biāo)記 ( )；采用這種方法直至所有零都被標(biāo)記，或出現(xiàn) 情況 a，或 情況 c 。若矩陣中存在 m 個(gè)不同行不同列的零，就找到了最優(yōu)解 ? 若覆蓋變換后的效率矩陣零元素的直線少于 m 條，就尚未找到最優(yōu)解，設(shè)法進(jìn)一步變換矩陣，增加新的零 9 清華算法的步驟：例 第一步 ：變換效率矩陣，使每行每列至少有一個(gè)零 – 行變換 ：找出每行最小元素，從該行各元素中減去之 – 列變換 ：找出每列最小元素，從該列各元素中減去之 ????????????????????????????????????????????2210020112300023321012012230)1(023543)2(56)4(5778)5(8)7(910換變列換變行第二步 ：檢查覆蓋所有零元素的直線是否為 m條 劃線規(guī)則 逐行檢查 ，若該行只有一個(gè)未標(biāo)記的零，對(duì)其加 ( )標(biāo)記，將 ( )標(biāo)記元素同行同列上其它的零打上 *標(biāo)記。整數(shù)規(guī)劃 整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃 1 整數(shù)規(guī)劃簡(jiǎn)介 ? 要求所有 xj 的解為整數(shù)，稱為純整數(shù)規(guī)劃 ? 要求部分 xj 的解為整數(shù)，稱為混合整數(shù)規(guī)劃 ? 對(duì)應(yīng)沒(méi)有整數(shù)解要求的線性規(guī)劃稱之為松弛問(wèn)題 ? 整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn) ? 整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問(wèn)題的最優(yōu)解 ????????????????njxmibxatsxcxfjnjijijnjjj,2,1,0,2,1,),(..)(max(m in)11??且為整數(shù)2 整數(shù)規(guī)劃的分枝定解法 思路與解題步驟 ? 只解松弛問(wèn)題 在全部可行性域上解松弛問(wèn)題 – 若松弛問(wèn)題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解 分枝過(guò)程 – 若松弛問(wèn)題最優(yōu)解中某個(gè) xk=bk 不是整數(shù)，令 ? bk ? 為 bk 的整數(shù)部分 – 構(gòu)造兩個(gè)新的約
教學(xué)課件相關(guān)推薦
鄂ICP備17016276號(hào)-1