【文章內容簡介】 x3≤5 xj=0或1j=1,2,3 用匈牙利法求解如下效率矩陣的指派問題 7 10 12 13 12 16 17 15 16 14 15 11 12 15 16 分配甲、乙、丙、丁四人去完成五項任務。每人完成各項任務時間如下表所示。由于任務數多于人數故規(guī)定其中有一個人可兼完成兩項任務其余三人每人完成一項。試確定總花費時間為最少的指派方案。人任務ABCDE 甲乙丙丁 已知下列五人各種姿勢的游泳成績（各為50米）試問如何進行指派從中選拔一個參加200米混合泳的接力隊使預期比賽成績?yōu)樽詈?。趙 錢 張 王 周仰泳 蛙泳 蝶泳 自由泳 （貨郎擔）問題可以敘述如下：某旅行商販從某一城市出發(fā)到其它幾個城市去推銷商品規(guī)定每個城市均須到達而且只到達一次然后回到原出發(fā)城市。已知城市i和j之間的距離為dij問該商販應選擇一條什么樣的線順序旅行使總的旅程為最短。試對此問題建立整數規(guī)劃模型。在每臺機床上加工三個產品的順序應保持一樣假定用tij表示在第j機床上加工第i個產品的時間問應如何安排使三個產品總的加工周期為最短。試建立此問題的整數規(guī)劃模型。習題參考第一章線性規(guī)劃及單純形法 （1）解：第一求可行解集合。令兩個約束條件為等式得到兩條直線在第一象限劃出滿足兩個不等式的區(qū)域其交集就是可行集或稱為可行域如圖11所示交集為（1/2, 0）。第二繪制目標函數圖形。將目標函數的系數組成一個坐標點（64）過原點O作一條矢量指向點（64）矢量的長度不限矢量的斜率保持4比6再作一條與矢量垂直的直線這條直線就是目標函數圖形目標函數圖形的位置任意如果通過原點則目標函數值Z=0如圖12所示。第三求最優(yōu)解。圖12的矢量方向是目標函數增加的方向或稱梯度方向在求最小值時將目標函數圖形沿梯度方向的反方向平行移動（在求最大值時將目標函數圖形沿梯度方向平行移動）直到可行域的邊界停止移動其交點對應的坐標就是最優(yōu)解如圖13所示。最優(yōu)解x=（1/2, 0）,目標函數的最小值Z=3。（2）無可行解；[求解方法與（1）類似]（3）無界解；（4）無可行解；（5）無窮多最優(yōu)解 z*=66（6）唯一最優(yōu)解 z*=92/3,x1=20/3,x2=3/8 （1）解：由題目可知其系數矩陣為因線性獨立故有 令非基變量得→ 得到一個基可行解。線性獨立故有 令非基變量得→得到一個基本解但非可行解。同理可以求出 得基本可行解。得基本可行解。得基本可行解。得基本可行解。得基本非可行解。得基本非可行解。（1）、（2）如下表所示其中打三角符號的是基本可行解打星號的為最優(yōu)解：x1x2x3x4x5zx1x2x3x4x5 △00000035 △000005 6000003 △009/205/200 △0005/200 *△0003/200 △* 4005/2000 △ 00005/29/2 0 △ (1)解：單純形法首先將問題化為標準型。加松弛變量x3x4得其次列出初始單純形表計算最優(yōu)值。CB XB 10 5 0 0 b X1 X2 X3 X4 0 X3 3 4 1 0 9 0 X4 5 2 0 1 8 σj 10 5 0 0 0 X3 0 14/5 13/5 21/5 10 X1 1 2/5 0 1/5 8/5 σj 0 1 02 X2 1 1 5/143/14 3/2 10 X1 0 01/72/7 1 σj 0 05/1425/14（表一）由單純形表一得最優(yōu)解為 法：（2）略 (1)解：大M法首先將數學模型化為標準形式式中x4x5為松弛變量x5可作為一個基變量第一、三約束分別加入人工變量x6 x7目標函數中加入Mx6Mx7一項得到大M單純形法數學模型由單純形表計算：CB XB 4 5 1 0 0MM b X1 X2 X3 X4 X5 X6 X7M X6 3 2 11 0 1 0 18 0 X5 2 1 0 0 1 0 0 4M X7 1 11 0 0 0 1 5 σj 4+4M 5+3M 1M 0 0 0M X61 0 112 1 0 10 5 X2 2 1 0 0 1 0 0 4M X71 01 0 0 0 1 1 σj 42M 0 1M2M 1 X31 0 112 0 X2 2 1 0 0 1M X72 0 012 σj 52M 0 0 1M 在迭代過程中人工變量一旦出基后不會在進基所以當人工變量X6出基后對應第六列的系數可以不再計算以減少計算量。當用大M單純形法計算得到最優(yōu)解并且存在人工變量大于零時則表明原線性規(guī)劃無可行解。兩階段單純形法首先化標準形同大M法第一、三約束分別加入人工變量x6 x7后構造0 0 0 10 0 4 1 11022M 第一階段問題 CB XB 0 0 0 0 0 1 1 b X1 X2 X3 X4 X5 X6 X7 1 X6 3 2 11 0 1 0 18 0 X5 2 1 0 0 1 0 0 4 1 X7 1 11 0 0 0 1 5 σj43 0 1 0 0 0 1 X6 0 1/2 113/2 0 12 0 X1 1 1/2 0 0 1/2 0 0 2 1 X7 0 1/21 01/20 1 3 σj 01 0 1 2 0 0 1 X61 0 112 1 0 10 0 X2 2 1 0 0 2 0 0 4 1 X71 01 01 0 1 1 σj 2 0 0 1 3 0 0 在第一階段的最優(yōu)解中人工變量不為零則原問題無可行解。注：在第二階段計算時初始表中的檢驗數不能引用第一階段最優(yōu)表的檢驗數必須換成原問題的檢驗數。(2)無窮多最優(yōu)解如X1＝（400）；X2＝（008）(3)無界解(4)唯一最優(yōu)解 X*＝（5/25/25/20）(5)唯一最優(yōu)解 X*＝（2433）(6)唯一最優(yōu)解 X*＝（140－4）（4）X*仍為最優(yōu)解max z＝λCX；（5）除C為常數向量外一般X*不再是該問題的最優(yōu)解；（6）最優(yōu)解變?yōu)棣薠*目標函數值不變。（7）d≥0,c1＜0, c2＜0（8）d≥0,c1≤0, c2≤0,但c1c2中至少一個為零（9）d＝0或d0而c10且d/4=3/a2（10）（11）（12） 解：設xj表示第j年生產出來分配用于作戰(zhàn)的戰(zhàn)斗機數；yj為第j年已出來的駕駛員；（aj－xj）為第j年用于駕駛員的戰(zhàn)斗機數；zj為第c10,d/43/a2 c20,a1≤0 x5為人工變量且c1≤0, c2≤0 j年用于駕駛員的戰(zhàn)斗機總數。則模型為 max z = nx1+(n1)x2+…+2xn1+xn =zj1+(ajxj)yj=yj1+k(ajxj)x1+x2+…+xj≤yj xj,yj,zj≥0(j=1,2, …,n)提示：設出每個管道上的實際流量則發(fā)點發(fā)出的流量等于收點收到的流量中間點則流入等于流出再考慮容量限制條件即可。目標函數為發(fā)出流量最大。設xij＝從點i到點j的流量 max z＝x12＋x13 ＝x23＋x24＋x25 x13＋x23＝x34＋x35 x24＋x34＋x54＝x46 x25＋x35＝x54＋x56以上為流量平衡條件 x12＋x13＝x46＋x56始點＝收點 x12≤10x13≤6x23≤4x24≤5x25≤3x34≤5x35≤8x46≤11x54≤3x56≤7 xij≥0對所有ij 提示：設每個區(qū)段上班的人數分別為x1x2…x6即可 解：設男生中挖坑、栽樹、澆水的人數分別為x1x1x13女生中挖坑、栽樹、澆水的人數分別為x2x2x23 ,S為植樹棵樹。由題意模型為： max S＝20 x11+10 x21 +x12 +x13 =30 x21 +x22 +x23 =20 20 x11+10 x21 =30 x12+20 x22=25 x13+15 x23 Xij≥0 i=1,2；j=1,2,3 解：設各生產x1,x2,x3 max z = x1++ +≤2000 ++≤2500 + +≤1200 x1,x2,x3≥0 解：設7－12月各月初進貨數量為xi件而各月售貨數量為yi件i＝12…6S為總收入則問題的模型為：max S＝29y1＋24y2＋26y3＋28y4＋22y5＋25y6－（28x1＋24x2＋25x3＋27x4＋23x5＋23x6）≤200＋x1≤500 y2≤200＋x1－y1＋x2≤500 y3≤200＋x1－y1＋x2－y2＋x3≤500 y4≤200＋x1－y1＋x2－y2＋x3－y3＋x4≤500 y5≤200＋x1－y1＋x2－y2＋x3－y3＋x4－y4＋x5≤500 y2≤200＋x1－y1＋x2－y2＋x3－y3＋x4－y4＋x5－y5＋x6≤500 xi≥0yi≥0 i＝12…6 整數 解：用x1x2x3分別代表大豆、玉米、麥子的種植面積（hm2公頃）；x4x5分別代表奶牛和雞的飼養(yǎng)數；x6x7分別代表秋冬和春夏季多余的勞動力（人日）則有第二章對偶理論和靈敏度分析 對偶問題為(1)(2)(3)(4)（1）因為對偶變量Y=CBB1,第k個約束條件乘上λ（λ≠0）即B1的k列將為變化前的1/λ由此對偶問題變化后的解（y’1, y’2, …, y’k,…y’m）=（y1, y2, …,(1/λ)yk,…ym）（2）與前類似y’r= y’i= yi（i≠r）（3）y’i=λyi（i=1,2, …,m）（4）yi（i=1,2, …,m）不變 (1)對偶問題為(2)由互補松弛性——（分別為松弛變量和最優(yōu)解）可得從而可知又由對偶性質的最優(yōu)性——可得四方程聯立即可求得對偶問題的最優(yōu)解： Y*＝（2210）解： 其對偶問題為 min w=8y1+12y2 2y1+2y2 ≥2(1)2y2 ≥1(2)y1+y2 ≥5(3)y1+2y2 ≥6(4)y1, y2 ≥0將y1*,y2* 代入約束條件得（1）與（2）為嚴格不等式由互補松弛性YsX*=0得x1*=x2*=0；又因為y1, y2≥0由互補松弛性 Y*Xs=0得Xs1=Xs2=0即原問題約束條件應取等號故 x3+x4=8解之得x3=4 x3+2x4=12x4=4 所以原問題最優(yōu)解為X*=(0, 0, 4, 4)T目標函數最優(yōu)值為 Z*=44。（1）略（2）原問題的解互補的對偶問題的解 第一步（000604080）（000－2－4－3）第二步（015002535）（10010－1）第三步（020/350/30080/3）（5/62/3011/600）（3）對偶問題的解對偶問題互補的對偶問題的解 第一步（000－2－4－3）（000604080）第二步（10010－1）（015002535）第三步（（5/62/3011/600）（020/350/30080/3）（4）比較（2）和（3）計算結果發(fā)現對偶單純形法實質上是將單純形法應用于對偶問題的求解又對偶問題的對偶即原問題因此兩者計算結果完全相同。（1）15/4≤c1≤50,4/5≤c2≤40/3（2）24/5≤b1≤169/2≤b2≤15（3）X*=（8/5021/50）（4）X*=（11/3002/3）（1）a=40,b=50,c=x2,d=x1,e=,f=80,g=s440（2）最大值（3）2?a+?b=90, ?a+2?b=80 （1）x1,x2,x3代表原稿紙、日記本和練習本月產量建模求解最終單純形表如下：x1x2x3x4x5 x2200007/31/1010 x1100004/31/10cjzj0010/31/1050（2）臨時工影子高于市場故應招收。招200人最合適。(1)s=13x1(2x1*+3x1*)+16x2(4x2*+2x2*）=5x1+8x2 max z=5x1+8x2 +4x2≤160 3x1+2x2≤180 x1,x2≥0X*=(50,15)max z=370（2）影子：A ：7/4B：1/2（3）CBB1（c3+11）≥0CB=73/4=（4）b’ =(160+a,180)，B1 b =((3/8)a +15,50a/4)≥0 得到40≤a ≤200a=200增加利潤350 X1 X2 X3 X4 X2 15+(3/8)a 0 1 3/81/4 X1 50a/4 1 01/41/21/2 s3707a/4 0 07/4 第三章 解： B1 B2 B3 B4 量 A1(10)A2(16)運輸問題（6）（7）（12）（10）（5）（9）9（10）A3(5)（4）（10）需要量 5 3 4 6 18 西北角法是優(yōu)先從運價表的西北角的變量賦值當行或列分配完畢后再在表中余下部分的西北角賦值以此類推直到右下角素分配完畢。, x11=min｛a1, b1｝= min｛4, 5｝= 4將4填 在C11的左側表示A14單位給B2。= min｛9, 54｝=。 B1 B2 B3 B4 量 A1 4(10)A2(16)（6）（7）（12）（5）（9）9（10）4（10）A3(5)（4）（10）需要量 B1 B2 B3 B4 量 A1 4(10)A2 1(16)5 3 4 6 18（6）（7）（12）（10）（5）（9）9（10）A3(5)（4）（10）需要量 B1 B2 B3 B4 量 A1 4(10)5 3 4 6 18（6）（7）（12）4 A2 1(16)3（10）4（5）1（9）9 A3(5)（4）（10）需要量5（10）5 5 3 4 6 18 最小素法的思想是就近優(yōu)先運送即最小運價cij對應的變量xij優(yōu)先賦值xij=min｛ai, bj｝然后在