运筹学 复习练习题.doc

《运筹学 复习练习题.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、串讲练习题1.某公司生产的产品A，B，C和D都要经过下列工序：刨、立铣、钻孔和装配。已知每单位产品所需工时及本月四道工序可用生产时间如下表所示：刨立铣钻孔装配A0.52.00.53.0B1.01.0.0.51.0.C1.01.01.02.0D0.51.01.03.0可用生产时间（小时）1800280030006000又知四种产品对利润贡献及本月最少销售需要单位如下：产品最少销售需要单位元/单位A1002B6003C5001D4004问该公司该如何安排生产使利润收入为最大？（建立模型）2．已知线性规划问题min

2、z=2x1-x2+2x3-x1+x2+x3=4-x1+x2-x3≤6x1≤0,x2≥0,x3无约束（1）写出其对偶问题并化为标准型式。（2）用单纯形法求出原问题的最优解。3．应用对偶问题性质，求出下面问题的最优解。4.某混合饲料场为某种动物配置饲料。已知此动物的生长速度与饲料中的三种营养成分甲、乙、丙有关，且每头动物每天需要营养甲85g、乙5g、丙15g。现有五种饲料中都含有这三种营养成分，每种饲料每公斤所含营养成分及每种饲料成本如下表所示。求既满足动物生长需要又使成本最低的饲料配方。饲料营养甲/g营养乙/g

3、营养丙/g成本/元10.500.100.08222.000.060.70633.000.040.35541.500.150.25450.800.200.0235.京成畜产品公司计划在市区的东西南北四区建立销售门市部，拟议中有10个位置可供选择，考虑到各地区居民的生活水平及居民居住密集度，规定：在东区由三个点至多选择两个；在西区由两个点中至少选一个；在南区由两个点中至少选一个；在北区由三个点中至少选两个。各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况如下表。但投资总额不能超过720万元，问应选择

4、哪几个销售点可使年利润为最大。投资额10012015080709080140160180利润364050222030254858616．已知下表为求解某线性规划问题的最终单纯形表，表中为松弛变量，问题的约束条件为形式。5/201/211/205/21-1/20-1/61/30-40-4-2（1）写出原线性规划问题的数学模型；（2）写出原问题的对偶问题；（3）直接由上表写出对偶问题的最优解。7．已知线性规划问题maxz=2x1+x25x2≤156x1+2x2≤24x1+x2≤5x1,x2≥0（1）写出其对偶问题

5、并化为标准型式；（2）用单纯形法求出原问题的最优解；唯一最优解（3）根据最终单纯形表写出其对偶问题的最优解，三种资源的影子价格各为多少并说明其涵义；（4）若第三种资源增加3单位，问最优解有何变化，资源的影子价格变为多少。8．运输问题课后习题3.3（1）（2）9．指派问题课后习题5.710．最小树问题课后习题10.4，10.511．最短路问题课后习题10.610.712.最大流问题：10.12,10.13部分答案：2．解：（1）其对偶问题为：化成标准型式为：（2）原问题的准标准型为：用大M法求解Cj-2-12-

6、2M0θcBxBbx2x4x5x6x7M0X6x746［1］11-11011-110146检验数σ-2-M–1-M2-MM-200-20X742111-11000-2［2］-11-1检验数σ010-4M+20-2-2X55111001/21/200-11-1/21/2检验数σ0100M2所以，原问题的最优解为：4．解：设为每千克混合饲料中所含5种饲料的重量目标函数为：约束条件有：6．解：（1）首先设a、b、c表示对应原模型的价值系数，则由检验数的计算公式，得解此方程组，得：a=6，b=-2，c=10再由单纯形

7、表与原模型标准型的特点，得有这两个关系式，可得：所以：愿问题的模型为：（2）由原问题的模型，得到其对偶问题模型：（3）由对偶理论，从原问题的最终单纯形表中，直接得到对偶问题的最优解：7．（2）唯一最优解（3）其对偶问题的最优解为：第一种资源影子价格为0，第二种资源为1/4，第三种资源为1/2其含义为：每增加一个单位的第一种资源，最优值不会增加，每增加一个单位的第二种资源，最优值增加1/4，每增加一个单位的第三种资源，最优值会增加1/2。所以要想增加最优值，可以增加第二和第三种资源。（4）第三种资源增加三个单位

8、，=新最优解为：13．有七个城市V1,V2,…，V7其公路网如下图所示，弧旁数字为该段公路的长度，有一批货物要从V1运到V7，试用迪克斯特拉算法或双标号法求出走那条路距离最短。用狄克斯特拉算法或双标号法标号（7分）得到最短路路径：V1—V3—V4—V5—V7（2分）最短路路权：10（1分）14.几个工地之间建立一个局域网，由于条件不同，各工地间相连的费用不同，如下图所示，求A,B,C,D,E间的最小