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