【正文】 該法適用于任何01規(guī)劃問(wèn)題的求解。 例（詳見(jiàn)書(shū)） 該法只在變量少的情況下使用才有效。（2）如果問(wèn)題是要求在前m個(gè)約束條件中至少滿足k(1km)個(gè)，則可將()中的原約束條件修改為：其中M為充分大的正數(shù)，k為整數(shù)。當(dāng)y=1時(shí)，②式對(duì)Xj起了約束作用，而①式成了多余的條件。易見(jiàn)，當(dāng)y=0時(shí)，①式就是原來(lái)的第r個(gè)約束條件，具有約束作用。Xi （5）如果項(xiàng)目i與項(xiàng)目j要么同時(shí)被選中，要么同時(shí)不被選中，則在()中加入新的約束條件：Xj=Xi (i185。（3）如果在可供選擇的k(k163。n)個(gè)項(xiàng)目中，必須且只能選擇一項(xiàng)，則在()中加入新的約束條件： （2）如果可供選擇的k(k163。假定現(xiàn)有m種資源對(duì)可供選擇的n個(gè)項(xiàng)目進(jìn)行投資的數(shù)學(xué)模型為：求一組決策變量X1,X2,…,Xn，使 （）（）（） 滿足 其中，Cj表示投資第j項(xiàng)獲得的期望收益，aij表示第i種資源投于第j項(xiàng)目數(shù)量，bj表示第i種資源的限量。 二、01變量產(chǎn)生的背景和應(yīng)用引例（詳見(jiàn)書(shū)P72例2）由引例可見(jiàn)，利用01變量處理一類“可供選擇條件”的問(wèn)題查非常簡(jiǎn)明且方便的。如在指派問(wèn)題中，當(dāng)n=20，則有可行解20！個(gè)，而20！2X1018，這在計(jì)算機(jī)上也是不可能實(shí)現(xiàn)的。2）完全枚舉法 此法僅在決策變量很少的情況下才實(shí)際有效。CX－當(dāng)CX－163。CX*163。設(shè)X*是原ILP的最優(yōu)解，X是其松馳問(wèn)題的非整數(shù)最優(yōu)解，是“舍入取整”的整數(shù)可行解，d為給出目標(biāo)函數(shù)值的允許誤差。但在處理個(gè)別實(shí)際問(wèn)題是，如果允許目標(biāo)函數(shù)值在某一誤差范圍內(nèi)，有時(shí)也可采用“舍入取整”得到的整數(shù)可行解作為原問(wèn)題整數(shù)最優(yōu)解的近似。求解ILP問(wèn)題方法的思考：1）“舍入取整”法：即先不考慮整數(shù)性約束，而去求解其相應(yīng)的LP問(wèn)題（稱為松馳問(wèn)題），然后將得到的非整數(shù)最優(yōu)解用“舍入取整”的方法。這是因?yàn)镮P的可行解集是由一些離散的非負(fù)整數(shù)所組成，不是一個(gè)凸集。凡決策變量均是01變量的IP為01規(guī)劃。ILP問(wèn)題數(shù)學(xué)模型的一般形式為：求一組變量X1,X2,…,Xn，使人們對(duì)IP感興趣，還因?yàn)橛行┙?jīng)濟(jì)管理中的實(shí)際問(wèn)題的解必須滿足如邏輯條件和順序要求等一些特殊的約束條件。對(duì)求整數(shù)最優(yōu)解的問(wèn)題，稱為整數(shù)規(guī)劃(Integer Programming)(簡(jiǎn)記為IP)。3 整數(shù)線性規(guī)劃問(wèn)題及其解法 一、整數(shù)線性規(guī)劃在上一章討論的LP問(wèn)題中,對(duì)決策變量只限于不能取負(fù)值的連續(xù)型數(shù)值,即可以是正分?jǐn)?shù)或正小數(shù)。mn列nm行當(dāng)mn時(shí) 當(dāng)mn時(shí) ，但可以不唯一。當(dāng)m185。取得最小的最優(yōu)解就是使Z取得最大的最優(yōu)解。0），將其轉(zhuǎn)化為求所得到的最優(yōu)解就是原問(wèn)題的最優(yōu)解。故指派問(wèn)題有以下性質(zhì)：若從效率矩陣(Cij)nxn的一行（列）各元素中分別減去該行（列）的最小元素，得到的新效率矩陣(bij)nxn不改變?cè)概蓡?wèn)題的最優(yōu)解。與Z同時(shí)達(dá)到最小值。 （3）解矩陣是指派問(wèn)題的可行解，但不一定是最優(yōu)解。0，因此必有最優(yōu)解()。2 指派問(wèn)題及其解法引例任務(wù)人員EJGR甲215134乙1041415丙9141613丁78119當(dāng)指派第i人去完成第j項(xiàng)工作否則 解：設(shè)Xij表示第i人從事第j項(xiàng)工作，且因此，該問(wèn)題的數(shù)學(xué)模型為MinZ=2X11+15X12+13X13+4X14+10X21+4X22+14X23+15X24 +9X31+14X32+16X33+13X34+7X41+8X42+11X43+9X44表示第j項(xiàng)工作只指派人完成表示第i人被指派完成一項(xiàng)工作Xij=0或1(i,j=1,2,3,4)諸如此類，有n項(xiàng)任務(wù)，恰好有n個(gè)人可承擔(dān)這些任務(wù)，但由于每人的專長(zhǎng)技術(shù)不同，完成任務(wù)的效率(所費(fèi)時(shí)間_不同，為使完成n項(xiàng)任務(wù)的總效率最高（即所需總時(shí)最少），應(yīng)如何指派（分派）人員的問(wèn)題統(tǒng)稱為指派（分派）問(wèn)題。 “轉(zhuǎn)運(yùn)問(wèn)題”的方法步驟： (1)建立擴(kuò)大的產(chǎn)銷平衡運(yùn)輸問(wèn)題單位運(yùn)價(jià)表。凡類似上述情況下的調(diào)運(yùn)物資并使總運(yùn)費(fèi)最小的問(wèn)題統(tǒng)稱為轉(zhuǎn)運(yùn)問(wèn)題。 (2)運(yùn)往各銷地的物資可先運(yùn)給其中的幾個(gè)銷地，再轉(zhuǎn)運(yùn)給其它銷地。然后再用產(chǎn)銷平衡的運(yùn)輸問(wèn)題的解法進(jìn)行解之。 二、產(chǎn)銷不平衡的運(yùn)輸?shù)膯?wèn)題及其求解方法 ：產(chǎn)大于銷 產(chǎn)小于銷 ：將不平衡轉(zhuǎn)化為平衡。以上ii)，iii)均出現(xiàn)退化解。閉回路外的各調(diào)運(yùn)量不變。 iii) 確定調(diào)整量q=min{第奇數(shù)次拐角格的調(diào)運(yùn)量} iv) 在閉回路上進(jìn)行調(diào)整：對(duì)閉回路上每個(gè)奇數(shù)次拐角格的調(diào)運(yùn)量－q對(duì)閉回路上每個(gè)第偶數(shù)次（含起始格）拐角格的調(diào)運(yùn)量+q。 ii) 作閉回路：以換入變量空格為出發(fā)點(diǎn)，用水平或垂直線向前劃，當(dāng)碰到某一恰當(dāng)數(shù)格轉(zhuǎn)90176。于是有v3=3,v4=10,u2=1,v1=2,u3=5,v2=9第三步：按σij= (ui+vj)－Cij (i,j206。 第二步：利用圈數(shù)格分別算出ui和vj，即令u1=0，然后按ui+vj=Cij (i,j206。JB 即有方程組 共m+n個(gè)未知數(shù) s=m+n－1個(gè)方程顯然上述方程有解，且由于含有一個(gè)自由變量，因此，可令任一未知數(shù)為0，就可求出上述方程組的解(ui1,ui2,…uim,vj1,vj2,…vjn)──稱為位勢(shì)解。 v1,v2,…,vn是對(duì)應(yīng)運(yùn)輸問(wèn)題m+n個(gè)約束條件的對(duì)偶變量，B為含有人工變量的初始可行基，由LP問(wèn)題的對(duì)偶理論知CBB1=(u1,u2,…um。其計(jì)算步驟方法，并通過(guò)對(duì)引例的求解過(guò)程說(shuō)明之一。由于上述特點(diǎn)，若按單純形法求解必須增加人工變量，致使計(jì)算量大大增加，故用特殊解法──表上作業(yè)法。于是，該LP問(wèn)題有且僅有m+n－1個(gè)基變量。平衡表（單位：噸） 運(yùn)價(jià)表 （單位：元/噸）銷地產(chǎn)地B1B2B3B4產(chǎn)量B1B2B3B4A17311310A241928A3974105銷 量3656解：這是一個(gè)產(chǎn)銷平衡的運(yùn)輸問(wèn)題，其數(shù)學(xué)模型是： 設(shè)Xij表示從Ai調(diào)運(yùn)產(chǎn)品到Bj的數(shù)量（噸），則minZ=3X11+11X12+3X13+10X14+X21+9X22 +2X23+8X24+7X31+4X32+10X33+5X34x11+x12+x13+x14 =7x21+x22+x23+x24 =4x31+x32+x33+x34 =9x11 +x21 +x31 =3x12 +x22 +x32 =6x13 +x23 +x33 =5x14 +x24 +x34 =6xij≥0 (i=1,2,3, j=1,2,3,4) 一、產(chǎn)量平衡的運(yùn)輸問(wèn)題及其解法 特點(diǎn)：（1）其系數(shù)矩陣的結(jié)構(gòu)疏松，且每一列向量 Pij=(0,…1,…1,…0)T=ei+em+j 可以證明，r(A)=m+n－1。已知從各工廠到各銷售點(diǎn)的單位產(chǎn)品的運(yùn)價(jià)為下表所示。1 運(yùn)輸問(wèn)題及其解法引例：某公司經(jīng)銷甲產(chǎn)品，它下設(shè)三個(gè)加工廠，每日的產(chǎn)量分別為：A17噸，A24噸，A39噸。第二章 特殊LP問(wèn)題及其解法所謂特殊LP問(wèn)題是指LP模型的系數(shù)矩陣具有特殊的結(jié)構(gòu)，有可能找到比單純形法更為簡(jiǎn)便的求解方法，從而節(jié)省人力和物力。目前的基B對(duì)應(yīng)的解有可能既不是原始可行，也不是對(duì)偶可行。第二種情況（當(dāng)j206。例：（5）技術(shù)系數(shù)aij變化的分析第一種情況（當(dāng)j206。對(duì)增加新約束條件的分析方法步驟是：第一步：將目前的最優(yōu)解代入新增加的約束，若能滿足約束條件，則說(shuō)明新增約束對(duì)目前的最優(yōu)解（即最優(yōu)生產(chǎn)方案）不構(gòu)成影響（稱此約束為不起作用約束），可暫時(shí)不考慮新增約束條件。 即新產(chǎn)品的機(jī)會(huì)成本小于目前的市場(chǎng)價(jià)格時(shí)，應(yīng)投產(chǎn)否則不應(yīng)投產(chǎn)。解不等式組 =(CB+△CB)B1N－CN=(CBB1N－CN)+△CBB1N≥0 即 (CBB1N－CN)+(0,…,△Cr,…,0)B1N≥0得到使最優(yōu)解不變△Cr的允許變化范圍； 例 （3）對(duì)增加新產(chǎn)品的分析設(shè)革企業(yè)在計(jì)劃期內(nèi)，擬議生產(chǎn)新產(chǎn)品Xn+1，并已知新產(chǎn)品的單位利潤(rùn)為Cn+1，消耗系數(shù)向量為Pn+1=(a1,n+1,a2,n+1,…am,n+1)T，此時(shí)應(yīng)如何分析才能確定該新產(chǎn)品理澡投產(chǎn)？增加新產(chǎn)品應(yīng)在不影響企業(yè)目前計(jì)劃期內(nèi)最優(yōu)生產(chǎn)的前提下進(jìn)行。否則，用單純形法繼續(xù)迭代，求得新的最優(yōu)解。 例 （1）當(dāng)CN中某個(gè)Cj發(fā)生變化時(shí)，只影到非基變量xj的檢驗(yàn)數(shù) 由于 若，則△Cj≤σj。若br的變化使B1b中某些分量小于0，則目前的基成為非可行基，為此，可用對(duì)偶單純形法迭代求得新的最優(yōu)解。即當(dāng)參數(shù)A、b、c中的某一個(gè)或幾個(gè)發(fā)生變化時(shí)，考察是否影響以下兩式的成立？ 當(dāng)b中某個(gè)br發(fā)生改變時(shí)，將影響基變量的取值XB=B1b。（4）可以預(yù)測(cè)產(chǎn)品的價(jià)格 （5）可作為同類企業(yè)經(jīng)濟(jì)效益評(píng)估指標(biāo)之一。影價(jià)=0，說(shuō)明該資源有剩余， 成為長(zhǎng)線資源。 (1)在非退化情況下