《运筹学复习资料.pptx》由会员分享，可在线阅读，更多相关《运筹学复习资料.pptx（49页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、 解 设 为分配给A县的救护车数量，其目标规划模型为：为分配给B县的救护车数量。第1页/共49页目标规划 某工厂计划生产A A、B B两种产品，每吨产品的耗电量指标、原材料消耗、单位产品利润及资源限量如表所示。厂长首先考虑要充分利用供电部门分配的电量限额6666，然后考虑利润不低于100100元；据市场调查结果，希望B产品的产量不低于A产品的产量，问应如何制定产品A A、B B的产量。建立该目标规划的数学模型。产品产品资源资源AB资源限量资源限量 电力电力101266原材料原材料218单位产品利润单位产品利润 1020第2页/共49页目标规划解：设x1、x2分别表示A A、B B两种产品的产量
2、，则目 标规划模型如下：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-,d2+,d3-,d3+0第3页/共49页第4页/共49页 6个人完成4项工作，由于个人和技术专长不同，他们完成4项工作任务所获得收益如下表：13545267683898841010911512111012613121113且规定每人只能做一项工作，一项工作任务只需一人操作，试求使 总收益最大的分派方案。第5页/共49页 解 此问题是一个非标准的
3、指派问题，虚设两项任务，并设任务的收益为0，化为标准的指派问题。标准的指派问题的收益矩阵为：第6页/共49页 将其化为极小值问题。第7页/共49页 最优解矩阵为：最优分派方案为：第3个人做第项工作，第4个人做第项工作，第5个人做第项工作，第6个人做第项工作，所得最大总收益为：第8页/共49页第9页/共49页用用Ford-Fulkerson标号法求下图中从标号法求下图中从s到到t的最大流及其流量，的最大流及其流量，并求网络的最小割。弧旁数字为（并求网络的最小割。弧旁数字为（cij，fij）。）。第10页/共49页解用解用Ford-Fulkerson标号法求出网络的增广链，如下图中虚线所示。（标号
4、法求出网络的增广链，如下图中虚线所示。（5分）分）第11页/共49页因此，网络中的可行流不是最大流，将其调整后得一新的可行流，如下图所因此，网络中的可行流不是最大流，将其调整后得一新的可行流，如下图所示（示（2分）分）第12页/共49页再用标号法在上图中找增广链，标号法中断，表明已找不出增广链，故上图中的可行流即为最大流，其流量为5+3+5=13。最小割为：3分分第13页/共49页第第11章章 网络计划网络计划第14页/共49页例(7.1b)：根据下表给定的条件，绘制PERT网络图。第15页/共49页ABCDEFGHIJKLM13987654210第16页/共49页第17页/共49页1(10分
5、)、写出如下线性规划问题的对偶问题，并利用弱对偶性说明z的最大值不大于1。第18页/共49页解 原问题的对偶问题为：由于（由于（0，1，0）是上述对偶问题的可行解，对原问题的任一可行解）是上述对偶问题的可行解，对原问题的任一可行解所以所以z的最大值不大于的最大值不大于1。第19页/共49页(10分)设有某个求极大值线性规划问题，它的某一次迭代结果如下表，试再进行一次迭代，判断迭代的结果是否已求得最优解，写出解的全部内容。Cj 2 5 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
6、-Z 2 0 0-5/2 0第20页/共49页解：再进行一次迭代结果如下：Cj25000基基bx1x2x3x4x5050 x3x2x546610301010001/2-1001Cj-Zj200-5/20052x3x2x126200101010-31/31/2-1/3-1/301/3Cj-Zj000-11/6-2/3第21页/共49页2(10分)、对于线性规划问题：（1）写出此问题的对偶问题；）写出此问题的对偶问题；（2）求出此问题和它的对偶问题的最优解）求出此问题和它的对偶问题的最优解和最优值。和最优值。第22页/共49页(1)对偶问题为：第23页/共49页(2)引入松弛变量y4,y5,y6,
7、将对偶问题规范化为：第24页/共49页用单纯形表迭代求最优解为：用单纯形表迭代求最优解为：最优解最优解Y Y*=(1,0,2,7,0,0)=(1,0,2,7,0,0)T T，z z*=max z=12=max z=12。第25页/共49页第26页/共49页（12分）给出下列线性规划的最优单纯形表，其中s1、s2分别为第1、第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
8、 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的变化范围。的变化范围。第27页/共49页解解（1）设）设 b2 b2+b2，则最终表中的，则最终表中的b变为：变为：其其中中，8 80，要要使使原原最最优优基基不不变变，还还应应满满足足：6+b20，即得到，即得到 b2-6，b b2 224。（2）设）设c3 c c3 3+c c3 3,则最终表中则最终表中x3的检验数变为：的检验数变
9、为：第28页/共49页于是原最终表变为下表：于是原最终表变为下表：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 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
10、3-6，故 c36。第29页/共49页习题2.6 用对偶单纯形法求解下述线性规划问题：解解 先将问题改写为先将问题改写为 第30页/共49页列出单纯形表，并用对偶单纯形法求解，计算步骤见表列出单纯形表，并用对偶单纯形法求解，计算步骤见表2-82-8最优解最优解X=(0X=(0，3/23/2，1)1)T T，min z=36min z=36第31页/共49页已知用单纯形法求得最优解的单纯形表如表已知用单纯形法求得最优解的单纯形表如表2-242-24所示。试分析所示。试分析在下列各种条件单独变化的情况下进行分析。在下列各种条件单独变化的情况下进行分析。(c)(c)增加一个变量增加一个变量x x7
11、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，重新确定最优解。，重新确定最优解。第32页/共49页解解:(c c)x7 在最终表中的检验数为在最终表中的检验数为第33页/共49页故最终表应变为故最终表应变为此时题目有无穷多最优解，其中之一为此时题目有无穷多最优解，其中之一为 x x1 1=3,x=3,x2 2=4/3,x=4/3,x7 7=1/3.=1/3.(d)原问题的最优解满足新增加的约束条件原问题的最优解满足新增加的约束条件 x1 4,故最优解故最优
12、解 不变，仍为不变，仍为X=(10/3,4/3)T.第34页/共49页习题习题2.11 2.11 已知线性规划问题：已知线性规划问题：当当 t t1 1=t=t2 2=0=0 时求解得最终单纯形表见表时求解得最终单纯形表见表 2-25.2-25.(a)(a)确定确定 a a1111、a a1212、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)当当
13、 t t1 1=0=0 时，时，t t2 2 值在什么范围内变化，上述最优基不变。值在什么范围内变化，上述最优基不变。第35页/共49页b b1 1=5,a=5,a1111=0,a=0,a12 12=1,=1,a a1313=2,=2,b b2 2=10,a=10,a2121=3,a=3,a22 22=1,1,a a2323=1.=1.第36页/共49页第37页/共49页 解：解：(b)(b)故有故有即即 6 6 t t1 1 8 8 时，时，原最优解不变。原最优解不变。第38页/共49页 解：解：(c)(c)第39页/共49页将下列线性规划问题化为标准形式，并列出初始单纯形表将下列线性规划问
14、题化为标准形式，并列出初始单纯形表令令，则则令令且且x x2 2,x x 2 2 0,0,问题化为标准形问题化为标准形 第40页/共49页再引入人工变量，问题变为再引入人工变量，问题变为第41页/共49页第42页/共49页将下列线性规划问题化为标准形式，并列出初始单纯形表将下列线性规划问题化为标准形式，并列出初始单纯形表令令再引入人工变量再引入人工变量：第43页/共49页第44页/共49页第第13章章 存储论存储论第45页/共49页241页9-1 若某种产品装配时需要一种外购件，已知年需求量为10000件，单价为100元。又每组织一次订货需2000元，每件每年的存储费用为外购件价值的20%，试求经济订货批量Q及每年最小的存储加订购总费用（设订货提前期为零）。第46页/共49页解解 已知：已知：D=10000件件/年，年，C=100元元/件，件，CD=2000元元/次，次，CP=20%C=20元元/件件,第47页/共49页祝您好运！第48页/共49页感谢您的观看！第49页/共49页