运筹学 复习练习题

串讲练习题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 z=2x1-x2+2x3 -x1+x2+x3=4 -x1+x2-x36 x10,x20,x3无约束（1） 写出其对偶问题并化为标准型式。（2） 用单纯形法求出原问题的最优解。3应用对偶问题性质，求出下面问题的最优解。4.某混合饲料场为某种动物配置饲料。已知此动物的生长速度与饲料中的三种营养成分甲、乙、丙有关，且每头动物每天需要营养甲85g、乙5g、丙15g。现有五种饲料中都含有这三种营养成分，每种饲料每公斤所含营养成分及每种饲料成本如下表所示。求既满足动物生长需要又使成本最低的饲料配方。饲料营养甲/g营养乙/g营养丙/g成本/元10.500.100.08222.000.060.70633.000.040.35541.500.150.25450.800.200.0235.京成畜产品公司计划在市区的东西南北四区建立销售门市部，拟议中有10个位置可供选择，考虑到各地区居民的生活水平及居民居住密集度，规定：在东区由三个点至多选择两个；在西区由两个点中至少选一个；在南区由两个点中至少选一个；在北区由三个点中至少选两个。各点的设备投资及每年可获利润由于地点不同都是不一样的，预测情况如下表。但投资总额不能超过720万元，问应选择哪几个销售点可使年利润为最大。投资额10012015080709080140160180利润364050222030254858616已知下表为求解某线性规划问题的最终单纯形表，表中为松弛变量，问题的约束条件为形式。5/201/211/205/21-1/20-1/61/30-40-4-2（1） 写出原线性规划问题的数学模型；（2） 写出原问题的对偶问题；（3） 直接由上表写出对偶问题的最优解。7已知线性规划问题 max z=2x1+x2 5x215 6x1+2x224x1+x2 5 x1,x20（1）写出其对偶问题并化为标准型式； （2）用单纯形法求出原问题的最优解；唯一最优解（3）根据最终单纯形表写出其对偶问题的最优解，三种资源的影子价格各为多少并说明其涵义；（4）若第三种资源增加3单位，问最优解有何变化，资源的影子价格变为多少。8运输问题课后习题3.3（1）（2）9指派问题 课后习题5.710最小树问题 课后习题10.4，10.511最短路问题 课后习题10.6 10.712.最大流问题：10.12,10.13部分答案：2解：（1）其对偶问题为： 化成标准型式为：（2）原问题的准标准型为： 用大M法求解 Cj-2 -1 2 -2 M 0 cBxBb x2 x4 x5 x6 x7 M0X6x7461 1 1 -1 1 0 1 1 -1 1 0 1 46检验数-2-M 1-M 2-M M-2 0 0-20X7421 1 1 -1 1 0 0 0 -2 2 -1 1-1检验数0 1 0 -4 M+2 0-2-2X5511 1 0 0 1/2 1/2 0 0 -1 1 -1/2 1/2 检验数0 1 0 0 M 2所以，原问题的最优解为：4解：设为每千克混合饲料中所含5种饲料的重量 目标函数为： 约束条件有：6解：（1）首先设a、b、c表示对应原模型的价值系数，则由检验数的计算公式，得解此方程组，得：a=6，b=-2，c=10再由单纯形表与原模型标准型的特点，得有这两个关系式，可得：所以：愿问题的模型为：（2）由原问题的模型，得到其对偶问题模型： （3）由对偶理论，从原问题的最终单纯形表中，直接得到对偶问题的最优解：7（2）唯一最优解 （3）其对偶问题的最优解为： 第一种资源影子价格为0，第二种资源为1/4，第三种资源为1/2 其含义为：每增加一个单位的第一种资源，最优值不会增加，每增加一个单位的第二种资源，最优值增加1/4，每增加一个单位的第三种资源，最优值会增加1/2。所以要想增加最优值，可以增加第二和第三种资源。 （4）第三种资源增加三个单位，= 新最优解为：13有七个城市V1,V2,，V7其公路网如下图所示，弧旁数字为该段公路的长度，有一批货物要从V1运到V7，试用迪克斯特拉算法或双标号法求出走那条路距离最短。 用狄克斯特拉算法或双标号法标号 （7分）得到最短路路径：V1V3V4V5V7（2分）最短路路权：10（1分）14.几个工地之间建立一个局域网，由于条件不同，各工地间相连的费用不同，如下图所示，求A,B,C,D,E间的最小连线方案。（10分）工地A工地B工地C工地D工地EA071153B7010144C11100137D5141306E34760由对称表格画出连通图（4分）由破圈法或避圈法得到最小树（4分），最小权和22（2分）