整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃

整數(shù)規(guī)劃整數(shù)規(guī)劃的難度遠(yuǎn)大于一般線性規(guī)劃14.1整數(shù)規(guī)劃簡(jiǎn)介要求所有xj的解為整數(shù)，稱(chēng)為純整數(shù)規(guī)劃要求部分xj的解為整數(shù)，稱(chēng)為混合整數(shù)規(guī)劃對(duì)應(yīng)沒(méi)有整數(shù)解要求的線性規(guī)劃稱(chēng)之為松弛問(wèn)題整數(shù)規(guī)劃的解是可數(shù)個(gè)的，最優(yōu)解不一定發(fā)生在極點(diǎn)整數(shù)規(guī)劃的最優(yōu)解不會(huì)優(yōu)于其松弛問(wèn)題的最優(yōu)解24.2整數(shù)規(guī)劃的分枝定解法

4.2.1思路與解題步驟只解松弛問(wèn)題1、在全部可行性域上解松弛問(wèn)題若松弛問(wèn)題最優(yōu)解為整數(shù)解，則其也是整數(shù)規(guī)劃的最優(yōu)解2、分枝過(guò)程若松弛問(wèn)題最優(yōu)解中某個(gè)xk=bk不是整數(shù)，令bk為bk的整數(shù)部分構(gòu)造兩個(gè)新的約束條件xkbk和xkbk+1，分別加于原松弛問(wèn)題，形成兩個(gè)新的整數(shù)規(guī)劃3、求解分枝的松弛問(wèn)題—定界過(guò)程設(shè)兩個(gè)分枝的松弛問(wèn)題分別為問(wèn)題1和問(wèn)題2，它們的最優(yōu)解有如下情況3表4.2.1分枝問(wèn)題解可能出現(xiàn)的情況情況2,4,5找到最優(yōu)解情況3在縮減的域上繼續(xù)分枝定界法情況6問(wèn)題1的整數(shù)解作為界被保留，用于以后與問(wèn)題2的后續(xù)分枝所得到的整數(shù)解進(jìn)行比較，結(jié)論如情況444.2.2分枝定界法舉例

例4.1.1

解：松弛問(wèn)題的最優(yōu)解為x1=2.5,x2=2,OBJ=23由x1=2.5得到兩個(gè)分枝如下：5表4.2.3分枝問(wèn)題的松弛解問(wèn)題II的解即原整數(shù)問(wèn)題的最優(yōu)解可能存在兩個(gè)分枝都是非整數(shù)解的情況，則需要兩邊同時(shí)繼續(xù)分枝，直到有整數(shù)解出現(xiàn)，就可以進(jìn)行定界過(guò)程當(dāng)有很多變量有整數(shù)約束時(shí)，分枝即廣又深，在最壞情況下相當(dāng)于組合所有可能的整數(shù)解一般整數(shù)規(guī)劃問(wèn)題屬于一類(lèi)未解決的難題，NP-complete，只有少數(shù)特殊問(wèn)題有好的算法，如任務(wù)分配問(wèn)題、匹配問(wèn)題64.6任務(wù)分配問(wèn)題例4.6.1有四個(gè)熟練工人，他們都是多面手，有四項(xiàng)任務(wù)要他們完成。若規(guī)定每人必須完成且只完成一項(xiàng)任務(wù)，而每人完成每項(xiàng)任務(wù)的工時(shí)耗費(fèi)如表4.6.1，問(wèn)如何分配任務(wù)使完成四項(xiàng)任務(wù)的總工時(shí)耗費(fèi)最少？7任務(wù)分配問(wèn)題的數(shù)學(xué)模型模型中：xij

為第i個(gè)工人分配去做第j

項(xiàng)任務(wù)；

aij

為第i

個(gè)工人為完成第j

項(xiàng)任務(wù)時(shí)的工時(shí)消耗；{aij}mm稱(chēng)為效率矩陣運(yùn)輸問(wèn)題是任務(wù)分配問(wèn)題的松弛問(wèn)題任務(wù)分配問(wèn)題不但是整數(shù)規(guī)劃，而且是01規(guī)劃任務(wù)分配問(wèn)題有2m個(gè)約束條件，但有且只有m個(gè)非零解，是自然高度退化的任務(wù)分配是兩部圖的匹配問(wèn)題，有著名的匈牙利算法下面介紹一種適合手算的算法(出自清華教科書(shū))84.6.1清華算法定理1如果從效率矩陣{aij}mm中每行元素分別減去一個(gè)常數(shù)ui，從每列元素分別減去一個(gè)常數(shù)vj，所得新的效率矩陣{bij}mm的任務(wù)分配問(wèn)題的最優(yōu)解等價(jià)于原問(wèn)題的最優(yōu)解。證明：略定理2若方陣中一部分元素為零，一部分元素非零，則覆蓋方陣內(nèi)所有零元素的最少直線數(shù)等于位于不同行、不同列的零元素的最多個(gè)數(shù)。證明：略清華算法的基本思路：根據(jù)定理1變換效率矩陣，使矩陣中有足夠多的零。若矩陣中存在m

個(gè)不同行不同列的零，就找到了最優(yōu)解若覆蓋變換后的效率矩陣零元素的直線少于m條，就尚未找到最優(yōu)解，設(shè)法進(jìn)一步變換矩陣，增加新的零9清華算法的步驟：例4.6.1第一步：變換效率矩陣，使每行每列至少有一個(gè)零行變換：找出每行最小元素，從該行各元素中減去之列變換：找出每列最小元素，從該列各元素中減去之第二步：檢查覆蓋所有零元素的直線是否為m條劃線規(guī)則1、逐行檢查，若該行只有一個(gè)未標(biāo)記的零，對(duì)其加()標(biāo)記，將()標(biāo)記元素同行同列上其它的零打上*標(biāo)記。若該行有二個(gè)以上未標(biāo)記的零，暫不標(biāo)記，轉(zhuǎn)下一行檢查，直到所有行檢查完；10清華算算法的的步驟驟：例例4.6.12、逐逐列檢檢查，若該該列只只有一一個(gè)未未標(biāo)記記的零零，對(duì)對(duì)其加加()標(biāo)記，，將()標(biāo)記元元素同同行同同列上上其它它的零零打上上*標(biāo)記。。若該該列有有二個(gè)個(gè)以上上未標(biāo)標(biāo)記的的零，，暫不不標(biāo)記記，轉(zhuǎn)轉(zhuǎn)下一一列檢檢查，，直到到所有有列檢檢查完完；3、重重復(fù)1、2后，可可能出出現(xiàn)三三種情情況；；a.每行都都有一一個(gè)(0)，，顯然然已找找到最最優(yōu)解解，令令對(duì)應(yīng)應(yīng)(0)位位置的的xij=1；；b.仍有零零元素素未標(biāo)標(biāo)記，，此時(shí)時(shí)，一一定存存在某某些行行和列列同時(shí)時(shí)有多多個(gè)零零，稱(chēng)稱(chēng)為僵局狀狀態(tài)，因?yàn)闉闊o(wú)法法采用用1.2中的方方法繼繼續(xù)標(biāo)標(biāo)記。。4、打破僵僵局。令未未標(biāo)記記零對(duì)對(duì)應(yīng)的的同行行同列列上其其它未未標(biāo)記記零的的個(gè)數(shù)數(shù)為該該零的的指數(shù)，選指數(shù)最最小的先標(biāo)標(biāo)記()；；采用用這種種方法法直至至所有有零都都被標(biāo)標(biāo)記，，或出出現(xiàn)情況a，或情況c。11清華算算法的的步驟驟：例例4.6.1c.所有零零都已已標(biāo)記記，但但標(biāo)有有()的的零的的個(gè)數(shù)數(shù)少于于m；開(kāi)始劃線過(guò)過(guò)程：對(duì)沒(méi)有有標(biāo)記記()的的行打打?qū)Υ蛐行猩纤衅淦渌懔阍厮貙?duì)應(yīng)應(yīng)的列列打再對(duì)打打列列上有有()標(biāo)標(biāo)記的的零元元素對(duì)對(duì)應(yīng)的的行打打重復(fù)，直至至無(wú)法法繼續(xù)續(xù)對(duì)沒(méi)有有打的的行劃劃?rùn)M線，對(duì)所所有打的的列劃劃垂線劃線后后會(huì)出出現(xiàn)兩兩種情情況：：(1)標(biāo)記()的零少于于m個(gè)，但劃有有m條直線，說(shuō)說(shuō)明矩陣中中已存在m個(gè)不同行不不同列的零零，但打破破僵局時(shí)選選擇不合理理，沒(méi)能找找到。回到到b重新標(biāo)記；；(2)少于m條直線，到到第三步；12清華算法的的步驟：例例4.6.1第三步：進(jìn)一步變換換；在未劃劃線的元素素中找最小者，設(shè)為對(duì)未被被直線覆蓋蓋的各元素素減去對(duì)兩條條直線交叉叉點(diǎn)覆蓋的的元素加上上只有一一條直線覆覆蓋的元素素保持不變變以上步驟實(shí)實(shí)際上仍是是利用定理1第四步：抹除所有標(biāo)標(biāo)記，回到到第二步，重新標(biāo)記記；13清華算法的的步驟：例例4.6.1答：最優(yōu)分分配方案為為x13=x21=x34=x42=1，其余余為0，即甲C，乙A，丙D，丁B，OBJ=20144.6.2關(guān)于清華算算法的適用用條件要求所有aij0若某些aij<0，則利用定定理1進(jìn)進(jìn)行變換換，使所有有bij0目標(biāo)函數(shù)為為min型型對(duì)于max型目標(biāo)函函數(shù)，將效效率矩陣中中所有aij反號(hào)，則等等效于求min型問(wèn)問(wèn)題；再利利用定理1進(jìn)行行變換，使使所有bij0，則則可采用清清華算法打破僵局時(shí)時(shí)選擇不當(dāng)當(dāng)?shù)慕Y(jié)果：：結(jié)果僅出現(xiàn)現(xiàn)3個(gè)個(gè)標(biāo)記()，但但卻劃出4條線線，說(shuō)明什么？？！15線性規(guī)劃有有關(guān)的英文文詞匯Operational/operationsresearch運(yùn)籌學(xué)Linearprogramming線線性規(guī)劃Feasibledomain可行行域Convexset凸凸集Basicfeasiblesolutions基礎(chǔ)礎(chǔ)可行解Simplexalgorithm單純純型法Pivot主主元Pivoting主元元變換Revised,dualsimplexalgorithm修修正、對(duì)對(duì)偶單純型型法Relativecost相對(duì)對(duì)成本(機(jī)機(jī)會(huì)成本)Shadowprice影影子子價(jià)格Slack,Surplus,Artificialvariable松松弛，剩剩余，人工工變量Unbounded,Infeasible,Degeneratesolution無(wú)無(wú)界解,無(wú)無(wú)可行解解,退化化解Duality對(duì)對(duì)偶性Primal,dualpr