运筹学复习资料.ppt
,复习题,第 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两种产品，每吨产品的耗电量指标、原材料消耗、单位产品利润及资源限量如表所示。厂长首先考虑要充分利用供电部门分配的电量限额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-,d2+,d3-,d3+0,复习题,第 5 章 指派问题,6个人完成4项工作，由于个人和技术专长不同，他们完成4项工作任务所获得收益如下表：,且规定每人只能做一项工作，一项工作任务只需一人操作，试求使 总收益最大的分派方案。,解 此问题是一个非标准的指派问题，虚设两项任务，并设任务的收益为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网络图。,*例题*,*例题*,复习题,第 1、2 章 线性规划及对偶问题,1(10分)、写出如下线性规划问题的对偶问题，并利用弱对偶性说明z的最大值不大于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分）给出下列线性规划的最优单纯形表，其中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，重新确定最优解。,解:(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 值在什么范围内变化，上述最优基不变。,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元/件,祝您好运！,
