【正文】 路長(zhǎng)為1+1+1+1+3+1+1=9。即為：LE、AC、GH、KJ（圖中已標(biāo)明），路長(zhǎng)為3+2+2+3=10。圖中有8個(gè)奇點(diǎn)：A、C、E、G、H、J、K、L。10，解：最小費(fèi)用最大流為：（弧旁數(shù)字為）(16,16,1)(6,15,4)(14,14,1)(8,17,3)(8,11,2)(0,13,6)(8,8,2)最小費(fèi)用為110，最大流量為22。8，解：令。最大流如圖所示。2347522634652234354852ASBEITCFDGH6，.求網(wǎng)絡(luò)的最大流。（注：利用該相鄰矩陣的結(jié)構(gòu)特點(diǎn)，可以簡(jiǎn)化矩陣運(yùn)算的階數(shù)）3，解：最小生成樹為：最小生成樹的權(quán)值為：。（提示）：課文中圖45是過河問題的模型圖，可以用相鄰矩陣表示。這樣不斷地派生下去就會(huì)形成一個(gè)由節(jié)點(diǎn)(狀態(tài))和線（狀態(tài)的轉(zhuǎn)移關(guān)系）構(gòu)成的圖。然后對(duì)每一狀態(tài)，找出在此狀態(tài)下可能倒酒的方法及其可能產(chǎn)生的狀態(tài)。三種方案總成本均為3100元。指標(biāo)函數(shù)取為總成本，各階段成本從k階段開始到最后為止最低總成本遞推公式是：：。：：各月初的存貨，：每個(gè)月的生產(chǎn)量，：每個(gè)月的銷售量。（2）——每月月初的庫(kù)存量；——各階段的生產(chǎn)量；——第k階段（月）的需求量。（2）各階段狀態(tài)參數(shù)是在第k個(gè)地區(qū)之后（包含第k個(gè)地區(qū)）有零售店總數(shù)，是在第k個(gè)地區(qū)的零售店數(shù)目。由以上分析可知，有兩個(gè)最優(yōu)方案，利潤(rùn)都是22。（3）由可知，在店3卸下1箱。（5）最優(yōu)指標(biāo)函數(shù) 當(dāng)00000114412255233663446645566566666當(dāng)00000001010840481820120855405125112301230857654061397113401234085786654061410118114501234508578866654061411121281146012345608578886666540614111313128114當(dāng)0000000101028082082012024128012104012301230246131280131412611440123402468141312801415161482165012345024689141413128014161718169318601234560246891014141413128014161819201710420當(dāng)60123456046777720181614128020222221191571222，步驟如下：（1）由或2可知，在零售店1卸下1箱或2箱。（3）是分配給第k個(gè)店的貨物箱數(shù)。：：（1）將卸貨問題按零售店分為四個(gè)階段，順序4。對(duì)于3） 其它約束： 綜合以上各指標(biāo)要求，得到該問題的目標(biāo)規(guī)劃模型如下：第三章 動(dòng)態(tài)規(guī)劃。第三個(gè)目標(biāo)要求工序一每周生產(chǎn)時(shí)間最好等于150小時(shí)，工序二生產(chǎn)時(shí)間可適當(dāng)超過其能力75小時(shí)，即綜合以上各指標(biāo)要求，得到該問題的目標(biāo)規(guī)劃模型如下：14. 解：設(shè)是從第產(chǎn)地運(yùn)往銷地的商品數(shù)，則對(duì)a） 對(duì)b） 對(duì)c） 對(duì)d） 對(duì)e） 對(duì)f） 其中4580是由線性規(guī)劃得到的運(yùn)費(fèi)最小值。：設(shè)，分別表示每周生產(chǎn)A,S型號(hào)的微型計(jì)算機(jī)的臺(tái)數(shù)。2）目標(biāo)函數(shù)分別變?yōu)槿缦聝煞N情況，請(qǐng)分析解的變化 a) b)（假設(shè)和的按比例變動(dòng)）。由于非基變量的檢驗(yàn)數(shù)為0，所以此題有多個(gè)解。換基后，通過計(jì)算求得新的基本可行解，見表13。換基后，通過計(jì)算求得新的基本可行解，見表12。換基后，通過計(jì)算求得新的基本可行解，見表11。換基后，通過計(jì)算求得新的基本可行解，見表10。換基后，通過計(jì)算求得新的基本可行解，見表9。12，1）用單純形法求解；解：初始單純形表如表8。換基后，通過計(jì)算求得新的基本可行解，見表7。換基后，通過計(jì)算求得新的基本可行解，見表6。換基后，通過計(jì)算求得新的基本可行解，見表5。（3） 解：初始基變量為四個(gè)負(fù)偏差變量，得到初始單純形表如表4。換基后，通過計(jì)算求得新的基本可行解，見表3。換基后，通過計(jì)算求得新的基本可行解，見表2。11，（1）解：初始基變量為三個(gè)負(fù)偏差變量，得到初始單純形表如表1。三、計(jì)算題10， x1x2120圖1 圖解法第1題（1） 解：對(duì)于，桔黃色內(nèi)的部分滿足要求，對(duì)于，藍(lán)色內(nèi)的部分滿足要求，所以滿意解是＝2，＝0，＝1，其它偏差變量都等于零。 8. 答：應(yīng)該選擇D。要求正偏差變量最小。6） 要求不超過目標(biāo)值的目標(biāo)函數(shù)是。5） 要求至少達(dá)到目標(biāo)值的目標(biāo)函數(shù)是。4） 一對(duì)正負(fù)偏差變量至少一個(gè)等于零。3） 一對(duì)正負(fù)偏差變量至少一個(gè)大于零。2） 目標(biāo)約束一定是等式約束。 6， 判斷以下各種說法的正確性1） 正偏差變量大于等于零，負(fù)偏差變量小于等于零。如果是，則不再繼續(xù)求解，已獲得滿意解；如果不是，則需要繼續(xù)下一層次目標(biāo)的求解。 單純形法適用于能給目標(biāo)確定優(yōu)先級(jí)的場(chǎng)合，序列解法適用于目標(biāo)層次不需確定優(yōu)先級(jí)的場(chǎng)合。 出基變量的選擇：與單純形法相同。如果首項(xiàng)優(yōu)先級(jí)相同且系數(shù)相等，再比較第二個(gè)優(yōu)先級(jí)的系數(shù)非基變量的檢驗(yàn)數(shù)為：，由于，所以當(dāng)非基變量檢驗(yàn)數(shù)中的首項(xiàng)系數(shù)時(shí)，獲得滿意解。3，答：（一）初始基變量的選擇 首先選擇所有的負(fù)偏差變量為初始基變量；如果負(fù)偏差變量數(shù)小于約束方程數(shù)，則增加選擇不同約束條件的松弛變量；如果負(fù)偏差變量和松弛變量的總數(shù)還小于約束方程數(shù)時(shí)，則需要加入人工變量，此時(shí)引入的M將被視作最高優(yōu)先級(jí)，即0級(jí)優(yōu)先級(jí)：。（2） 當(dāng)約束要求目標(biāo)不低于目標(biāo)值，目標(biāo)函數(shù)求負(fù)偏差變量最小。2，答：一般目標(biāo)規(guī)劃是將多個(gè)目標(biāo)函數(shù)寫成一個(gè)由偏差變量構(gòu)成的函數(shù)求最小值，并按多個(gè)目標(biāo)的重要性，給定優(yōu)先等級(jí)和權(quán)重，順序求最小值?！?113◎0100100000100001得到最優(yōu)解的指派方案為：甲－B，乙－A，丙－C，丁－D；最少消耗時(shí)間為70?！?10◎11248。◎1124◎√√√004100110120051130再進(jìn)行試指派，尋找最優(yōu)解。22248?！?124◎由于獨(dú)立的0元素個(gè)數(shù)仍然少于矩陣的階數(shù)，因此作最少的直線覆蓋所有的0元素。22248。015100220110041240再進(jìn)行試指派，尋找最優(yōu)解。在沒有被直線覆蓋的部分中找出最小元素3；然后對(duì)沒有覆蓋的行中各元素中減去這個(gè)最小元素3；被直線覆蓋的列中各元素都加上這個(gè)最小元素3?！?457248。最后對(duì)沒有打√號(hào)的行畫橫線，將打有√號(hào)的列畫豎線。在沒有◎ 的行打√；對(duì)打√的行上的所有0元素的列打√號(hào)；再對(duì)打√的列上有◎ 的行上打 √號(hào)?！?457248。得01573550110014570進(jìn)行試指派，尋找最優(yōu)解。得首先進(jìn)行行、列變換，使每一行和每一列都出現(xiàn)0元素。1有4個(gè)工人，要指派他們分別完成4項(xiàng)工作，每人做各項(xiàng)工作所消耗的時(shí)間如表2，問如何分配工作可使總的消耗時(shí)間為最少？表2 工作工人ABCD甲15182124乙19232218丙26171618丁19212317解：首先進(jìn)行行、列變換，使每一行和每一列都出現(xiàn)0元素。點(diǎn)(x3，x2 , x1)約束條件是否滿足條件Z值◎①②③④（1，0，0）1不滿足（1，0，1）1不滿足（1，1，0）0不滿足（1，1，1）2不滿足至此，z值已不能再改進(jìn)，即得到最優(yōu)解。過濾條件為： ◎目標(biāo)函數(shù)可以改寫成：因?yàn)?，1，2是遞增的，變量(x3，x2 , x1)也按下述順序取值（0，0，0），（0，0，1），（0，1，0），（0，1，1）等。（2）解：通過觀察的方法找一個(gè)可行解，易得(x1 , x2 , x3)=(1 ,0 ,0)符合約束條件，計(jì)算出其目標(biāo)函數(shù)值Z =2。對(duì)于極小化問題，當(dāng)然希望z≤4，于是增加一個(gè)約束條件，后加的約束條件稱為過濾條件。因此得原問題的最優(yōu)解為。解（LP1211），得最優(yōu)解為。繼續(xù)對(duì)（LP121）進(jìn)行分解。對(duì)（LP12）增加兩個(gè)約束條件，將兩個(gè)約束分別并入（LP12）中，形成兩個(gè)分支，即后繼問題（LP121）和（LP122），這并不影響（LP12）的可行域。解（LP11），得最優(yōu)解為再解（LP12），得最優(yōu)解為。繼續(xù)對(duì)（LP1）進(jìn)行分解。(2) 解：求相應(yīng)的線性規(guī)劃（LP）得（LP）的最優(yōu)解首先注意其中一個(gè)非整數(shù)變量的解，如，在松弛問題中的解，于是原問題增加兩個(gè)約束條件，將兩個(gè)約束分別并入原問題的松弛問題（LP）中，形成兩個(gè)分支，即后繼問題（LP1）和(LP2)，這并不影響原問題的可行域。解（LP11），得最優(yōu)解為再解（LP12），無最優(yōu)解。解（LP1），得最優(yōu)解為再解（LP2），得最優(yōu)解為繼續(xù)對(duì)（LP1）進(jìn)行分解。則箱數(shù)的約束為重量的約束為厚度的約束為特殊約束自然約束目標(biāo)函數(shù)是使浪費(fèi)的空間最小，也就是裝的越多，空間浪費(fèi)的越少。得初始方案為：ABCD面食廠需求量甲02020乙151530丙101020面食廠需求量15252010由于所求的是最大化，因此要求檢驗(yàn)數(shù)全部小于等于零時(shí)為最優(yōu)方案。解：初始方案為：ABC日產(chǎn)量（供應(yīng)量）甲礦100100200乙礦150100250日銷量（需要量）100150200經(jīng)過調(diào)整的最優(yōu)方案為ABC日產(chǎn)量（供應(yīng)量）甲礦50150200乙礦50200250日銷量（需要量）100150200則運(yùn)輸量最少為5090＋5080＋15070＋20080=350001解：初始方案為：ABCD日產(chǎn)量（供應(yīng)量）甲礦10060160乙礦8020100丙礦14080220日銷量（需要量）80140120140經(jīng)過調(diào)整的最優(yōu)方案為ABCD日產(chǎn)量（供應(yīng)量）甲礦12040160乙礦8020100丙礦14080220日銷量（需要量）80140120140