《运筹学复习资料.ppt》由会员分享，可在线阅读，更多相关《运筹学复习资料.ppt（50页珍藏版）》请在三一文库上搜索。
1、,复习题,第 4 章 目标规划,某市准备在下一年度预算中购置一批救护车，已知每辆救护车购置价为20万元。救护车用于所属的两个郊区县,各分配xA和xB台， A县救护站从接到求救电话到救护车出动的响应时间为(40- xA)min， B县相应的响应时间为(50- 4 xB )min，该市确定如下优先级目标。,P1：救护车购置费用不超过400万元。,要求建立目标规划模型。,P2： A县的响应时间不超过5min。,P3： B县的响应时间不超过5min。,解 设 为分配给A县的救护车数量，,其目标规划模型为：,为分配给B县的救护车数量。,目标规划,某工厂计划生产A、B两种产品，每吨产品的耗电量指 标、原材
2、料消耗、单位产品利润及资源限量如表所示。 厂长首先考虑要充分利用供电部门分配的电量限额66， 然后考虑利润不低于100元； 据市场调查结果，希望B产品的产量不低于A产品的产量， 问应如何制定产品A、B的产量。建立该目标规划的数学模型。,目标规划,解：设x1、x2分别表示A、B两种产品的产量，则目 标规划模型如下： minZ=P1 (d1- + d1+ ) + P2d2- + P3d3- 2x1+x2 8 10 x1+12x2 +d1- - d1+ =66 10 x1+20 x2 +d2- - d2+ =100 -x1+x2 +d3- - d3+ =0 x1,x2 ,d1- ,d1+ ,d2-
3、, d2+ ,d3- , d3+ 0,复习题,第 5 章 指派问题,6个人完成4项工作，由于个人和技术专长不同，他们完成4项工作任务所获得收益如下表：,且规定每人只能做一项工作，一项工作任务只需一人操作，试求使 总收益最大的分派方案。,解 此问题是一个非标准的指派问题，虚设两项任务， 并设任务的收益为0， 化为标准的指派问题。 标准的指派问题的收益矩阵为：,将其化为极小值问题。,最优解矩阵为：,最优分派方案为：第3个人做第项工作，第4个人 做第项工作，第5个人做第项工作，第6个人做第项工作， 所得最大总收益为：,复习题,第 10 章 图与网络规划,用Ford-Fulkerson标号法求下图中从
4、s到t的最大流及其流量， 并求网络的最小割。弧旁数字为（cij，fij）。,解用Ford-Fulkerson标号法求出网络的增广链，如下图中虚线所示。（5分）,因此，网络中的可行流不是最大流，将其调整后得一新的可行流，如下图所示（2分）,再用标号法在上图中找增广链，标号法中断，表明已找不出增广链，故上图中的可行流即为最大流，其流量为5+3+5=13。最小割为：,3分,复习题,第11章 网络计划,例(7.1b)：根据下表给定的条件，绘制PERT网络图。,*例题*,*例题*,复习题,第 1、2 章 线性规划及对偶问题,1 (10分) 、写出如下线性规划问题的对偶问题，并利用弱对偶性说明z的最大值不
5、大于1。,解 原问题的对偶问题为：,由于（0，1，0）是上述对偶问题的可行解，对原问题的任一可行解,所以z的最大值不大于1。,(10分)设有某个求极大值线性规划问题，它的某一次迭代结果如下表，试再进行一次迭代，判断迭代的结果是否已求得最优解，写出解的全部内容。,解：再进行一次迭代结果如下：,2(10分)、对于线性规划问题：,（1）写出此问题的对偶问题； （2）求出此问题和它的对偶问题的最优解和最优值。,(1)对偶问题为：,(2)引入松弛变量y4,y5,y6,将对偶问题规范化为：,用单纯形表迭代求最优解为：,最优解Y*=(1,0,2,7,0,0)T，z* = max z=12。,（12分）给出下
6、列线性规划的最优单纯形表，其中s1、s2分别为第1、第2约束方程中的松弛变量。,(1)求出最优基不变的b2的变化范围； (2)求出最优解不变的c3的变化范围。,解得c3-6，故 c36。,习题2.6 用对偶单纯形法求解下述线性规划问题：,解 先将问题改写为,列出单纯形表，并用对偶单纯形法求解，计算步骤见表2-8,最优解X=(0，3/2，1)T，min z=36,已知用单纯形法求得最优解的单纯形表如表2-24所示。试分析在下列各种条件单独变化的情况下进行分析。,(c) 增加一个变量x7,其在目标函数中系数c7=4,P7=(1,2,3,2)T (d)增加一个新的约束x14，重新确定最优解。,解:
7、(c) x7 在最终表中的检验数为,故最终表应变为,此时题目有无穷多最优解，其中之一为 x1 = 3, x2 = 4/3, x7 = 1/3.,(d) 原问题的最优解满足新增加的约束条件 x1 4, 故最优解 不变，仍为X=(10/3, 4/3)T.,习题2.11 已知线性规划问题：,当 t1 = t2 =0 时求解得最终单纯形表见表 2-25.,(a)确定 a11、a12、a13、a21、a22、a23、 c1、 c2、 c3和 b1、 b2 的值。 (b)当 t2= 0 时， t1 值在什么范围内变化，上述最优解不变。 (c)当 t1= 0 时， t2 值在什么范围内变化，上述最优基不变。
8、,b1 = 5, a11 = 0, a12 = 1, a13 = 2, b2 = 10, a21 = 3, a22 = 1, a23 = 1.,解：(b),故有,即 6 t1 8 时， 原最优解不变。,解：(c),P46.1.6 (a)将下列线性规划问题化为标准形式，并列出初始单纯形表,令,，,则,令,且x2, x 2 0, 问题化为标准形,再引入人工变量，问题变为,P46.1.6 (b)将下列线性规划问题化为标准形式，并列出初始单纯形表,令,再引入人工变量,：,复习题,第13章 存储论,241页9-1 若某种产品装配时需要一种外购件，已知年需求量为10000件，单价为100元。又每组织一次订货需2000元，每件每年的存储费用为外购件价值的20%，试求经济订货批量Q及每年最小的存储加订购总费用（设订货提前期为零）。,解 已知：D=10000件/年，C=100元/件，CD=2000元/次，CP=20%C =20元/件,祝您好运！,