[资料]《运筹学》课堂作业及答案.docx

第一部分绪论第二部分线性规划与单纯形法1判断下列说法是否正确：(a)图解法同单纯形法虽然求解的形式不同，但从几何上理解，两者是一致的；(b)线性规划模型屮增加一个约束条件，可行域的范闱一般将缩小，减少一个约束条件, 可行域的范围一般将扩大；(c)线性规划问题的每一个基解对应可行域的一个顶点；(d)如线性规划问题存在可行域，则可行域一定包含塑标的原点；(e)对取值无约束的变量Xi ,通常令X J —X) —X i其中作换入变量；(g)单纯形法计算中，如不按最小比值原则选取换出变量，则在下一个解中至少有一个基变量的值为负；(h)单纯形法计算中，选収最大正检验数九对应的变量Xk作为换入变量，将使目标函数值得到最快的增长；(i)一旦一个人工变量在迭代屮变为非基变量后，则该变量及相应列的数字可以从单纯形表中删除，而不影响计算结果；(j)线性规划问题的任一可行解都可以用全部基可行解的线性组合表示；(k)若X】，X2分别是某一线性规划问题的最优解，则X =入］X’十入2X?也是该线性规划问题的最优解，其中八，兀可以为任意正的实数；⑴线性规划用两阶段法求解时，第一阶段的目标函数通常写为mm n —h均为大于零的常数；(m) 对一个有n个变量、m个约朿的标准型的线性规划问题，其可行域的顶点恰好为Jn个；(n) 单纯形法的迭代计算过程是从一个可行解转转换到目标函数值更大的另一个可行(o) 线性规划问题的可行解如为最优解，则该可行解一定是基可行解；(p) 若线性规划问题具有可行解，且其可行域有界，则该线性规划问题最多具有有限个数的最优解；(q) 线性规划可行域的某一顶点若其日标函数值优于相邻的所有顶点的目标函数值，则该顶点处的目标函数值达到最优；(r) 将线性规划约束条件的“W”号及“2”号变换成号，将使问题的最优目标 函数值得到改善；(s) 线性规划目标函数屮系数最大的变量在最优解屮总是収正的值；(t) 一个企业利用3种资源生产4种产品，建立线性规划模型求解得到的最优解中，最 多只含有3种产品的组合；(u) 若线性规划问题的可行域可以伸展到无限，则该问题一定具有无界解；(v) —个线性规划问题求解吋的迭代工作量主要取决于变量数的多少，与约束条件的数 量关系相对较小。

【答案】1. 1 (a) (b) (f) (g) (i) (J) (1) (q) (t)正确，(c) (d) (e) (h) (k) (m) (n) (o) (p)(r) (s) (U) (v)不正确。

2用图解法求解下列线性规划问题，并指出各问题是具有唯一最优解、无穷多最优解、 无界解或无可行解。

(a) min z — + 4工2 (b) max z = )+ 8.r z2攵1+孔上1s. t. & 3文| + 4孔 $ 1. 54，孔 $ 0乃十22.ri + 才2 0 4 rV 6 2JC \ — 5.7*2 W 0JT| # 才2°》0 【答案】(a)唯一最优解，z*=3, XL1/2, X 2=0；(b) 无可行解；(c) 有可行解，但max 刁无界； (d) 无穷多最优解，z*二66。

1.25表1-6中给出某•求极大化问题的单•纯形表，问表中5，血，6, 〃为何值 时以及表中变ill ：屈哪一种类型时有：(a) 表中解为唯一最优解；(b) 表中解为无穷多最优解之一； (O 表中解为退化的可行解；(d) 下一步迭代将以4替换基变Mxs ； (e) 该线性规划问题具有无界解； (f) 该线性规划问题无可行解。

表1.62小+2工2£10s. t. f —才|+ 孔$ 8巧，兀$ 0(c) max z = .r\(ci) max z = 3J T| +4JTI + 6业12 s. t. y2工2》4【答案】1.25(a)dN0, Ci<0, C2<0；(b)dNO, c】W0, C2W0,但ci, C2 中至少一个为零;(c)d=O,或d>0,而6>0 且d/4—3 / a2；(d)Ci>0, 3/a2<d/4；(e)C2>0, a」WO；(f)xs为人工变量,且cWO, C2W0。

3某战略轰炸机群奉命摧毁敌人军事目标。

已知该目标有四个要害部位，只要摧毁其屮之一即可达到目的。

为完成此项任务的汽油消耗量限制为48000 1、重型炸弹48枚、轻型炸弹32枚。

E机携带重型炸弹时每升汽油可飞行2 km,带轻型炸弹时每升汽油可飞行3 knio 乂知每架飞机每次只能装载一枚炸弹，每出发轰炸一次除来冋路程汽油消耗(空载时每升汽油可飞行4 km)外，起飞和降落每次各消耗100 1。

有关数据如表1 — 17所示。

表1—17为了使摧毁敌方军事门标的可能性最大，应如何确定飞机轰炸的方案。

要求建立这个问题的线性规划模型。

【答案】用i二1, 2分别代表重型和轻型炸弹，j二1, 2, 3, 4分别代表四个要害部位，Xij为投到第J部位的i种型号炸弹的数量，则问题的数学模型为min 2 (1 -0.(1 -0. 20)*«« (1 -0.15)*»(1-0. 25)^ (1-0. 08)'"(1-0. 16)M«(l-0. !2)z»(l-0. 20)%1.5 X 450 ,1.5 X 480 . 1.5 X 540 , 1.5 X 600---- 2 ----- -•' ----- 2 ------ 十---- 2---- x,* 十 2 ---- +1. 75 X 450 , 1. 75 X 480 . 2 X540 . 2X 600―3—小 + —3—斤+ —y-m + —+・1- *] 1OO(X|| - J 4 + 丿-+ 匸利+ £初+ x:l + ) C 48 000口W 32JT II + ” 4”5 + 才八 + 八 + W 48几P 0 i1. 2i > =■ 1 • •••• 4式中目标函数非线性，但rain z等价于max lg(l/z),因此目标函数可改写为max lg(l/z)=0. 045 7.m +0. 096 9JT I2 +0. 070 4J*I3 +0. 124 8T U +0. 036 2X2I +0. 065 6^22 +°・ 055 4^23 +0. 096 9^244用单纯形法求解下列线性规划 max Z 二 3X| + 4x 2 + x 32 兀]+ 3X 2 + x3 < 1v X, + 2X 2 + 2X 3 < 3 x ： >0, ./ = 1,2,3 u J 【解】单纯形表:最优解：X= (1/2, 0, 0, 0, 5/2)；最优值 Z=3/2max Z = 2Xj + x 2 - 3x 3 + 5x 4Xj +5兀2 + 3兀3 - 7无4 <30 (2)•:3%! - x 2 + x 3 + x 4 < 10 2兀]一 6兀一兀3 + 4X 4 <20 >0,7 = 1,...,4【解】单纯形表:因为入7=3>0并且4/7<0（匸1,2,3）,故原问题具有无界解，即无最优解。

线性规划的对偶理论与灵敏度分析2.1写岀下列线性规划问题的对偶问题：（a ） min N = 3Q +2互 一3JC 3.T| - 2xz + 3小 + 4工4 =3x 2 + 3J ?3 + 412— 52x\ — 3.r 2 — 7片—4二=2 Tj ? 0,, M 0,丁2 •力无约束JI(b) max N =In工丿< S (/ = 1,・・・"小) n^a lf T, = b, (z = mi + 1 ,・•・"◎)r ;无约束(c) max z =ik£ £工・,二心d = l・2・3・4)5. t •丿 _ " ' ■八x t , > 0(i — 1 ■•••■4 8 j【答案】(3)max w —3y\ — 5y2 H~2J /3*（）ESi — 1 k — 1(d) min z=工工「宀J — I I(f = 1. 2, 3, 4)(/ = 1, 2, 3) (/ = 1, 2) (/ = 1 ■ 2, 3, 4)2. 2 Li 知线性规划问题:M + 2/3 W 3 —2，i + 力一3/3 = 2s. t. v 3j/]+ 3J /2— 7歹3 =— 34»i+ 4/2— 4歹3$ 4 M < 0^2 > 0,夕3无约束m(b) min w = 丫 byi=lm〉J 切“ W Cj (j = 1,…，n }) m工 5* A 6 (j =山 + 1,…，n 2 )〉：= Cj(j = © + 19 …” w) 1 = 1•yi > o (, = 1,・・・，％) yi 无约束 (i = m\ + 1,…，7心)y W 0 & = 7712 + 1 •…5)(d) max w —41= 1< ci.y, + % i W c z y f + jru + y^2 冬 5M +力+力+ M 冬Cy, $ o^,4 V* + 几G $ C tk乙无约束max n = g 心十ck 孔十门七用单纯形法求解得最终单纯形表如表2〜2所示。

(a)求dll 疋12，如2 山23和b, b 2；⑹求Cl ，c2°3。

表2—2「4一 _轨工33/2 1 01 1/2 -1/2 •T221/2 1 0 -1 2 勺一夠-3-4【答案】2. 2 a 11 = 9 / 2 U2\ = 5/2 a 」2 = 19 (222 = 1 Qi3=4, ©3=2;“=4心=8。

【解析】(1)由题意可设初始单纯形表的增广矩阵为由单纯形运算法则可知，(A l :B l ) = (A 3:B.)助以 9 6/i | — 9 / 2,纠? = 1，a 】？ — 4,6?91 = 5 / 2,Q" — 1,dg — 2,b 、— &— 5 (2)由检验数的计覧式可知 _「C }-(C ^C 2/2) = -3< 0 _ (c) / 2 - c ：) = 0 0 — (73/2 + 25) = —4求解上述方程组得：C1=7,C 2=4,C 3=82.3已知线性规划问题：。

】531 0 :a 22°231 : 62 -0 11/2 • -1/2 :3/2 r1 0-122 -使其第4, 5列组成单位矩阵最终单纯形表的增广矩阵为「1(A. 〃」=L1/2 对矩阵(A 烏5)作初等行变换,1 0 1 1/2-1/2： 3/2^ ―► - 2 0 2 1 -1:3^ —>-9/2 1 4 1 0:8- = (A 3 1/2 1 0 -1 2=2--5/2 1 2 0 1U--5/2 1 2 0 lb-iBJmax z= 10x] + 5化3JTI +4JC2 £ 9s. t. -<5J?I + 2工2 W 8、4 . JT2 > 0用单纯形法求得最终表如表28所示。