运筹学 复习资料

复习题第4章目标规划某市准备在下一年度预算中购置一批救护车，每辆救护车购置价为20万元。救护车用于所属的两个郊区县,各分配xA和xB台，A县救护站从接到求救到救护车出动的响应时间为(40-xA)min，B县相应的响应时间为(50-4xB)min，该市确定如下优先级目标。P1：救护车购置费用不超过400万元。要求建立目标规划模型。P2：A县的响应时间不超过5min。P3：B县的响应时间不超过5min。

解设为分配给A县的救护车数量，

其目标规划模型为：为分配给B县的救护车数量。目标规划

某工厂方案生产A、B两种产品，每吨产品的耗电量指标、原材料消耗、单位产品利润及资源限量如表所示。厂长首先考虑要充分利用供电部门分配的电量限额66，然后考虑利润不低于100元；据市场调查结果，希望B产品的产量不低于A产品的产量，问应如何制定产品A、B的产量。建立该目标规划的数学模型。产品资源AB资源限量

电力101266原材料218单位产品利润

1020目标规划解：设x1、x2分别表示A、B两种产品的产量，那么目标规划模型如下：minZ=P1(d1-+d1+)+P2d2-+P3d3-2x1+x2≤810x1+12x2+d1--d1+=6610x1+20x2+d2--d2+=100-x1+x2+d3--d3+=0x1,x2,d1-,d1+,d2-,d2+,d3-,d3+≥0复习题第5章指派问题ⅠⅡⅢⅣ13545267683898841010911512111012613121113且规定每人只能做一项工作，一项工作任务只需一人操作，试求使总收益最大的分派方案。解此问题是一个非标准的指派问题，虚设两项任务Ⅴ，Ⅵ并设任务的收益为0，化为标准的指派问题。标准的指派问题的收益矩阵为：将其化为极小值问题。最优解矩阵为：

最优分派方案为：第3个人做第Ⅳ项工作，第4个人做第Ⅲ项工作，第5个人做第Ⅱ项工作，第6个人做第Ⅰ项工作，所得最大总收益为：复习题第10章图与网络规划用Ford-Fulkerson标号法求以下图中从s到t的最大流及其流量，并求网络的最小割。弧旁数字为〔cij，fij〕。解用Ford-Fulkerson标号法求出网络的增广链，如以下图中虚线所示。〔5分〕因此，网络中的可行流不是最大流，将其调整后得一新的可行流，如以下图所示〔2分〕再用标号法在上图中找增广链，标号法中断，说明已找不出增广链，故上图中的可行流即为最大流，其流量为5+3+5=13。最小割为：3分复习题第11章网络方案例(7.1b)：根据下表给定的条件，绘制PERT网络图。*例题*ABCDEFGHIJKL例题*复习题第1、2章线性规划及对偶问题1

(10分)、写出如下线性规划问题的对偶问题，并利用弱对偶性说明z的最大值不大于1。

解原问题的对偶问题为：

由于〔0，1，0〕是上述对偶问题的可行解，对原问题的任一可行解所以z的最大值不大于1。(10分)设有某个求极大值线性规划问题，它的某一次迭代结果如下表，试再进行一次迭代，判断迭代的结果是否已求得最优解，写出解的全部内容。Cj25000基bx1x2x3x4x5050x3x2x546610301010001/2-1001Cj-Z200-5/20解：再进行一次迭代结果如下：Cj25000基bx1x2x3x4x5050x3x2x546610[3]01010001/2-1001Cj-Zj200-5/20052x3x2x126200101010-31/31/2-1/3-1/301/3Cj-Zj000-11/6-2/32(10分)、对于线性规划问题：

〔1〕写出此问题的对偶问题；〔2〕求出此问题和它的对偶问题的最优解和最优值。(1)对偶问题为：

(2)引入松弛变量y4,y5,y6,将对偶问题标准化为：用单纯形表迭代求最优解为：最优解Y*=(1,0,2,7,0,0)T，z*=maxz=12。〔12分〕给出以下线性规划的最优单纯形表，其中s1、s2分别为第1、第2约束方程中的松弛变量。cj621200cB

基bx1x2x3s1s2

12x384/31/311/300s26-250-11cj-zj-10-20-40(1)求出最优基不变的b2的变化范围；(2)求出最优解不变的c3的变化范围。解（1）设b2→b2+△b2，则最终表中的b变为：其中，8≥0，要使原最优基不变，还应满足：6+△b2≥0，即得到△b2≥-6，∴

b2≥24。（2）设c3→c3+△c3,则最终表中x3的检验数变为：于是原最终表变为下表：cj621200cB基bx1x2x3s1s2

12x384/31/311/300s26-250-11cj-zj-10-4△c3/3-2-△c3/30-4-△c3/30要使原最优解不变，应满足：解得△c3≥-6，故c3≥6。习题2.6用对偶单纯形法求解下述线性规划问题：

解先将问题改写为列出单纯形表，并用对偶单纯形法求解，计算步骤见表2-8最优解X=(0，3/2，1)T，minz=36用单纯形法求得最优解的单纯形表如表2-24所示。试分析在以下各种条件单独变化的情况下进行分析。(c)增加一个变量x7,其在目标函数中系数c7=4,P7=(1,2,3,2)T(d)增加一个新的约束x14，重新确定最优解。解:(c)x7

在最终表中的检验数为故最终表应变为此时题目有无穷多最优解，其中之一为x1=3,x2=4/3,x7=1/3.(d)原问题的最优解满足新增加的约束条件

x14,故最优解不变，仍为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

值在什么范围内变化，上述最优基不变。b1=5,a11=0,a12=1,

a13=2,b2=10,a21=3,a22=–1,

a23=1.

解：(b)故有即

–6t18

时，原最优解不变。

解：(c)P46.1.6(a)将以下线性规划问题化为标准形式，并列出初始单纯形表令，那么令且x2,x2

0,问题化为标准形

再引入人工变量，问题变为P46.1.6(b)将以下线性规划问题化为标准形式，并列出初