《运筹学习题答案》.pdf

1第一章第一章 习题习题1. 思考题（1）微分学求极值的方法为什么不适用于线性规划的求解？（2）线性规划的标准形有哪些限制？如何把一般的线性规划化为标准形式？（3）图解法主要步骤是什么？从中可以看出线性规划最优解有那些特点？（4）什么是线性规划的可行解，基本解，基可行解？引入基本解和基可行解有什么作用？（5）对于任意基可行解，为什么必须把目标函数用非基变量表示出来？什么是检验数？它有什么作用？如何计算检验数？（6）确定换出变量的法则是什么？违背这一法则，会发生什么问题？（7）如何进行换基迭代运算？（8）大 M 法与两阶段法的要点是什么？两者有什么共同点？有什么区别？（9）松弛变量与人工变量有什么区别？试从定义和处理方式两方面分析10）如何判定线性规划有唯一最优解，无穷多最优解和无最优解？为什么？2. 建立下列问题的线性规划模型：（1）某厂生产 A，B，C 三种产品，每件产品消耗的原料和设备台时如表 1-18 所示 ：表表 1-18产品ABC资源数量原料单耗机时单耗22.5335620002600利润101420另外，要求三种产品总产量不低于 65 件，A 的产量不高于 B 的产量试制定使总利润最大的模型。

2） 某公司打算利用具有下列成分 （见表 1-19） 的合金配制一种新型合金 100 公斤，新合金含铅，锌，锡的比例为 3：2：5表表 1-19合金品种12345含铅%含锌%含锡%306010102070502030101080501040单价（元/kg）8.56.08.95.78.8如何安排配方，使成本最低？（3）某医院每天各时间段至少需要配备护理人员数量见表 1-202表表 1-20班次时间最少人数1234566:0010:0010:0014:0014:0018:0018:0022:0022:002:002:006:00607060502030假定每人上班后连续工作 8 小时，试建立使总人数最少的计划安排模型能否利用初等数学的视察法，求出它的最优解？（4） 某工地需要 30 套三角架， 其结构尺寸如图 1-6 所示 仓库现有长 6.5 米的钢材如何下料，使消耗的钢材最少？图 1-63. 用图解法求下列线性规划的最优解： 0,425 . 1341264min) 1 (2121212121xxxxxxxxxxz0,825103244max)2(2121212121xxxxxxxxxxz0,605442223296max)3(21221212121xxxxxxxxxxxz0,112343max)4(21212121xxxxxxxxz331.41.41.734. 把下列线性规划化为标准形式：无约束432143213214313210, 0132212min) 1 (xxxxxxxxxxxxxxxxxz无约束211212121, 0218232max)2(xxxxxxxxxz5. 判定下列集合是否凸集：（1）R1=(x1,x2)|x12+2x222（2）R2=(x1,x2)|x122x2+30,x20,|x1|1（3）R3=(x1,x2)|x1x21,x11,x206. 求出下列线性规划的所有基本解，并指出其中的基可行解和最优解。

5 , 1, 018231224853max521423121jxxxxxxxxxxzj7. 求下列线性规划的解：（1）（2）0,182368253max21212121xxxxxxxxz0,14242max21212121xxxxxxxxz（3）（4）0,1222max21212121xxxxxxxxz0, 0, 0201026032max321321321321321xxxxxxxxxxxxxxxz48. 利用大 M 法或两阶段法求解下列线性规划：（1）（2）0,217223max2121212121xxxxxxxxxxz0,54218232max32132121321321xxxxxxxxxxxxxxz（3）（4）0,2631234max212212121xxxxxxxxxz0,1223615263343min4321432143214321xxxxxxxxxxxxxxxxz9. 对于问题0bmaxXAXCXz（1）设最优解为 X*，当 C 改为时，最优解为，则CX0)(*XXCC（2）如果 X1，X2均为最优解，则对于0，1，X1+（1）X2均为最优解10. 用单纯形法求解问题 2（4） （合理下料问题） 。

11. 表 1-21 是一个求极大值线性规划的单纯形表，其中x4，x5，x6是松弛变量表表 1-21cj22CBXBbx1x2x3x4x5x62x5x2x12141-12a21-1-1-2-a+8j-1（1）把表中缺少的项目填上适当的数或式子2）要使上表成为最优表，a 应满足什么条件？（3）何时有无穷多最优解？（4）何时无最优解？（5）何时应以x3替换x1？5第二章习题第二章习题1. 思考题（1）如何在以 B 为基的单纯形表中，找出 B1？该表是怎样由初始表得到的？（2）对偶问题的构成要素之间，有哪些对应规律？（3）如何从原问题最优表中，直接找到对偶最优解？（4）叙述互补松弛定理及其经济意义5）什么是资源的影子价格？它在经济管理中有什么作用？（6）对偶单纯形法有哪些操作要点？它与单纯形法有哪些相同，哪些地方有区别？（7）灵敏度分析主要讨论什么问题？分析的基本思路是什么？四种基本情况的分析要点是什么？2. 已知某线性规划的初始单纯形表和最终单纯形表如表 2-21，请把表中空白处的数字填上，并指出最优基 B 及 B1表表 2-21cj2-11000CBXBbx1x2x3x4x5x6000 x4x5x63111-1112-1100010001j2-1100002-1x4x1x210155-11/2-1/2-21/21/2j3. 某个线性规划的最终表是表 2-22：表 2-22cj01-200CBXBbx1x2x3x4x501-2x1x2x313/25/21/2100010001-1/2-1/2-1/25/23/21/2j000-1/2-1/2初始基变量是x1，x4，x5。

1）求最优基 B=（P1，P2，P3） ；（2）求初始表4. 写出下列线性规划的对偶问题：6无约束321321321321321, 0, 013142423max) 1 (xxxxxxxxxxxxxxxz无约束432143132143214321, 0, 0122224232min(2)xxxxxxxxxxxxxxxxxxznnjxnnjxnjxmmibxammibxamibxaxczjjjinjjijinjjijinjjijnjjj, 1, 0, 1, 1, 0, 1, 1, 2 , 1,max(3)221121211111无约束njmixnjbxmiaxxczijjmiijinjijminjijij, 1, 10, 1, 1min(4)11115. 已知线性规划70,min32123232221211313212111332211xxxbxaxaxabxaxaxaxcxcxcz（1）写出它的对偶问题；（2）引入松弛变量，化为标准形式，再写出对偶问题；（3）引入人工变量，把问题化为等价模型：0,)(max7127532322212116431321211176332211xxbxxxaxaxabxxxaxaxaxxMxcxcxcz再写出它的对偶问题。

试说明上面三个对偶问题是完全一致的由此，可以得出什么样的一般结论？6. 利用对偶理论说明下列线性规划无最优解：0, 0, 032242max321321321321xxxxxxxxxxxxz7. 已知表 2-23 是某线性规划的最优表，其中x4，x5为松弛变量，两个约束条件为型表表 2-23cjCBXBbx1x2x3x4x5x3x15/23/2011/2-1/2101/2-1/601/3j0-40-4-2（1）求价值系数 cj和原线性规划；（2）写出原问题的对偶问题；（3）由表 2-23 求对偶最优解8. 已知线性规划问题84 , 3 , 2 , 1, 02263326368min314343214214321jxxxxxxxxxxxxxxxxzj（1）写出对偶问题；（2）已知原问题的最优解为 X*=（1，1，2，0）T，求对偶问题的最优解9*. 已知线性规划无约束321321321321321, 0,4163253234maxxxxxxxxxxxxxxxxz的最优解为 X*=（0，0，4）T1）写出对偶问题；（2）求对偶问题最优解10. 用对偶单纯形法解下列各线性规划：0,43232432min(1)321321321321xxxxxxxxxxxxz0,10536423425min(2)321321321321xxxxxxxxxxxxz11. 设线性规划问题（2.41）njxmibxaxczjinjjijnjjj, 2 , 1, 0, 2 , 1max11的 m 种资源的影子价格为y1*，y2*，ym*。

线性规划9（2.42）njxmibxabxaxczjinjjijnjjjnjjj, 2 , 1, 0, 20max11111与（2.41）是等价的，两者有相同的最优解，请说明（2.42）的 m 种资源的影子价格为（y1*/，y2*，ym*） ，并指出这一结果的经济意义12*. 已知线性规划0, 0,4233222812min4321432143214321xxxxxxxxxxxxxxxxz（1）写出对偶问题，用图解法求最优解；（2）利用对偶原理求原问题最优解13. 线性规划0,4262max32121321321xxxxxxxxxxxz的最优单纯形表如表 2-24 所示表表 2-24cj2-1100CBXBbx1x2x3x4x520 x1x56101013111101j0-3-1-20（1）x2的系数 c2在何范围内变化，最优解不变？若 c2=3，求新的最优解；（2）b1在何范围内变化，最优基不变？如 b1=3，求新的最优解；（3）增加新约束 x1+2x32，求新的最优解；10（4）增加新变量x6，其系数列向量 P6=，价值系数 c6=1，求新的最优解2114. 某厂生产甲、乙、丙三种产品，有关资料如表 2-25 所示。

表表 2-25甲乙丙原料数量AB6334554530产品价格415（1）建立使总产值最大的线性规划模型；（2）求最优解，并指出原料 A，B 的影子价格；（3）产品甲的价格在什么范围内变化，最优解不变？（4）若有一种新产品，其原料消耗定额为：A 为 3 单位，B 为 2 单位，价格为 2.5单位，求新的最优计划 ；（5）已知原料 B 的市场价为 0.5 单位，可以随时购买，而原料 A 市场无货问该厂是否应购买 B，购进多少为宜？新的最优计划是什么？（6）由于某种原因，该厂决定暂停甲产品的生产，试重新制定最优生产计划15*. 分析下列参数规划中，当 t 变化时，最优解的变化情况0,18231224)5()23(max(1)21212121xxxxxxxtxtz0,524261552max(2)212121221xxxxtxxxxxz16. 在例 14 中，原料甲的影子价格为 5 元/kg，补充 20000kg 后，产值 z*似乎应增加520000=100000（元） ；但实际上只增加了 88000 元试解释这个“矛盾”现象产品消耗定额原料11第三章第三章 习 题习 题1表335和表336分别给出了各产地和各销地的产量和销量，以及各产地至各销地的单位运价，试用表上作业法求最优解。

表 335销地 产地B1B2B3B4产量A1A2A3359637267648557075销量40455560200表3-36 销地 产地B1B2B3B4产量A1A2A3978523674768302545销量202025351002试求表3-37给出的产销不平衡运输问题的最优解表3-37 销地 产地B1B2B3。