2024-1-3运筹学64学时总复习要点

运筹学总复习 2024.1.3复习内容与要求：1 建模方面：目标规划、动态规划、整数规划2 计算方面：线性规划、对偶规划、运输问题、指派问题、割平面算法、最大流、网络安排、对策论、决策论。【例题1】用单纯形法求解线性规划问题的解。解：添加三个松弛变量，把上述规划化成标准型 基变量bX1X2X3X4X5X3410100X4601010X51832001025000基变量bX1X2X3X4X5X3410100X2601010X56300-21-30200-50基变量bX1X2X3X4X5X320012/3-1/3X2601010X12100-2/31/3-3400-5-11/3-2/3最优解是（2，6）最优值是34。【例题2】某公司制造三种产品A、B、C，须要两种资源（劳动力和原材料），现要确定总利润最大的生产安排，列出下述线性规划 求：（1）线性规划问题的最优解；（2）求对偶问题的数学模型及其最优解；(3) 最优解不变的状况下，求产品A的利润允许变更范围；（4）假定能以10元的价格购进15单位的材料，这样做是否有利，为什么？（5）当可利用的资源增加到60单位时，求最优解。（6）当产品B的原材料消耗削减为2个单位时，是否影响当前的最优解，为什么？（7）增加约束条件2x1+x2+3x320，对原最优解有何影响，对对偶解有何影响？解答：（1）线性规划问题的最优解首先将问题标准化：cj31500CBXBbx1x2x3x4x500x4x54530 63 345【5】1001963150005x4x315633/5-14/50110-11/50-300-1最优解为X*=(x1,x2,x3,x4,x5)T=(0,0,6,15,0)T，最优目标值z*=30（2）求对偶问题的数学模型及其最优解；y1*=0,y2*=1 (3) 最优解不变的状况下，求产品A的利润允许变更范围；最优解不变的状况下，（4）假定能以10元的价格购进15单位的材料，这样做是否有利，为什么？有利单位材料的影子价格是1元，10元钱购进15单位的材料的单位价格为2/3元，低于影子价格。同时，在保持最优基不变的状况下购进15吨的原材料，最优基不变。该材料的影子价格仍为1元。（5）当可利用的资源增加到60单位时，求最优解。cj31500CBXBbx1x2x3x4x505x4x3-151233/5-14/50110【-1】1/50-300-105x5x3159-36/513/501-11/510-3-20-10最优解为X*=(x1,x2,x3,x4,x5)T=(0,0,9,0,15)T，最优目标值z*=45（6）当产品B的原材料消耗削减为2个单位时，是否影响当前的最优解，为什么？x2在最有表是非基变量，该产品的原材料消耗只影响x2的检验数。（7）增加约束条件2x1+x2+3x320，对原最优解有何影响，对对偶解有何影响？增加的约束条件，相当于增加了一个约束方程 cj241000CBXBb x1x2x3x4x5x6050x4x3x615620 33/52-14/510 13 1 0 0-11/500010-30 0 -10050x4x3x615623 3/5 4/5-14/5-7/5 0 1 0 1 00 -11/5 -3/5 0 0 1 0 -3 00-1 0对原问题的最优解无影响，对对偶问题的最优解也无影响。【例题3】已知如下线性规划问题：已知其对偶问题的最优解为Y=(4,1)。试用对偶理论求出原问题的最优解。解：对偶问题是：设原问题最优解为X(x1，x2 ，x3，x4)T ,将Y带入对偶问题约束条件中，得(1)(2)为严格不等式；由互补松弛条件知，。因为y1=40，及y2=10，所以原问题的两个约束条件应取等号，故有解方程组得：, 所以原问题的最优解为X=(0,0,4,4)，最优值z=44。【例题4】用对偶单纯形法求下面问题解：Cj 4600min( zj - cj)/ai*jCBXBbx1x2x3x4ai*j00x3-80-1(-2)104,3*0x4-75-3-101OBJ=0zj 0000zj - cj-4-600Cj 4600CBXBbx1x2x3x46x2401/21-1/200x4-35(-5/2)0-1/212/5*,6OBJ=240zj 36-30zj - cj-10-30Cj 4600CBXBbx1x2x3x46x23301-3/51/54x114101/5-2/5OBJ=254zj 46-14/5-2/5zj - cj00-14/5-2/5答：最优解为x1 =14，x2 =33，目标函数值为254。【例题5】给定下列运输问题的单位运价表及各个产销地的产量和销量，B1B2B3B4产量A1291079A213425A384257销量3846求运费最小的运输方案。解：（1）利用伏格尔法求初始基B1B2B3B4产量A135 19A255A3347销量3846（2）写出位势表并计算各变量的检验数。B1B2B3B4uiA100 300A24-120-5A311003-5vj2977（3）当前检验数有负数，闭回路法调整。B1B2B3B4产量A1369A2505A3347销量3846并计算上表所描述的调运方案的检验数B1B2B3B4uiA1140A243-5A3102-4vj2867可见，检验数全为正，故最优解为32 + 67 + 53 + 34 + 42 = 83。【例题6】某市准备在下一年度预算购置一批救援车，已知每辆救援车购置价格为20万元。救援车用于所属的两个县，各安排xA和xB台，县救援站从接到求救电话到救援车出动的响应时间为（40-3x）min，B县相应的响应时间为（50-4xB）min，该市确定如下优先级目标。P1：救援车的购置费用不超过400万元；P2：A县的响应时间不超过5min；P3：B县的响应时间不超过5min。要求：（1）建立目标规划模型（不用求解）。（2）若对优先级目标作出调整，P2变P1，P3变P2，P1变P3，重新建立目标规划模型（不用求解）。解：设xA为安排给A县的救援车数，xB为安排给B县的救援车数量。(1) 目标规划模型为：(2) 与（1）比较，只是目标函数变更了，而约束条件没有变更。故（2）的目标规划模型为：【例题7】某厂拟建两种不同类型的冶炼炉。甲种炉每台投资为2个单位，乙种炉每台许投资为1个单位，总投资不能超过10个单位；又该厂被许可用电量为2个单位，乙种炉被许可用电量为2个单位，但甲种炉利用余热发电，不仅可以满意本身须要，而且可供出电量1个单位。已知甲种炉每台收益为6个单位，乙种炉每台收益为4个单位。试问：应建甲、乙两种炉各多少台，使之收益最大？该问题也可如下表表示。（要求用割平面法求解该整数规划问题）甲种炉(x1) 乙种炉(x2) 限 量每台投资/单位2110用电量/单位-122收益/单位64解：设x1,x2为甲乙种炉应建台数，则用单纯形法求最优解，见下表。基变量bX1X2X3X4X31021105X42-1201-z06400X1511/21/2010X4705/21/2114/5-z-3001-30X118/5102/5-1/5X214/5011/52/5-z-32.800-16/5-2/5最优解为确定割平面方程：从而，构造割平面，并且标准化，加入最优表中，用对偶单纯形法求最优解，见下表。基变量bX1X2X3X4X5X118/5102/5-1/50X214/5011/52/50X5-4/500-1/5-2/51-z-32.800-16/5-2/50基变量bX1X2X3X4X5X14101/20-1/2X2201001X42001/21-5/2-z-3200-30-1。此解为整数解，故计算停止。【例题8】某部门有4个工人，现指派他们分别完成4项工作。每人做各项工作所消耗的时间（h）如下表所示，问如何分派工作，使总的消耗时间最少？消耗 工作工人ABCD甲3353乙3252丙1516丁46410解：变换效率矩阵如下：3353逐(0)0*20*逐(0)0*20*3252行1030列1(0)30*1516标0*4(0)5标0*4(0)546410记0*20*6记0*20*6每行每列都有两个以上的0 未找到最优解4(0) 0*2 0*重0*(0)20*81(0)3 0*新10*3(0)5 0*4(0)5标0*4(0)51 0*2 0*6记(0)20*62637划线过程(发觉有4条直线) 找到最优解答：简单看出，共有四个最优解：甲B，乙D，丙A，丁C；甲D，乙B，丙A，丁C；甲B，乙D，丙C，丁A；甲D，乙B，丙C，丁A；OBJ=10。【例题9】安排甲、乙、丙、丁四人去完成5项任务。每人完成各项任务时间如下表所示。由于任务数多于人数，故规定其中有一人可兼完成两项任务，其余三人每人完成一项，试确定总花费时间最少的指派方案。ABCDE甲2529314237乙3938262033丙3427284032丁2442362345解：假设增加一个人戊完成各项工作的时间取A、B、C、D、E最小值。得效率矩阵为：各行减最小值，各列减最小值：得变换得进一步最有指派方案甲B，乙C,D，丙E，丁A最低费用2926203224131【例题10】某公司准备将3千万元资金用于改造扩建所属的3个工厂，每个工厂的利润增长额与所安排的投资有关。各工厂在获得不同的投资额时所能增加的利润如下表所示，问应如何安排资金，使公司总的利润为最大。 利润 投资工厂01千万2千万3千万102.541020358.530269解：K为阶段变量，k=1,2,3 Sk:第k阶段所剩的资金数 Xk：第k阶段安排给第k个工厂的资金数 gk（xk）：将xk安排给第k个工厂的效益 状态转移方程：Sk+1= Sk-xk 递推关系：第三阶段，k=3X3=s3x3s3g3(x3)f3(s3)x*301230000122126623993其次阶段：s3=s2-x2， 0s23， 0x2s2x2s2f2(s2)x*2012300+00010+23+02120+63+25+06030+93+65+28.5+090,1第三阶段S1=3S2=s1-x1, 0x1s1x1s1f1(s1)x*1012330+92.5+64+310+0103最优安排方案为，x1*=3,x2*=0,x3*=0最佳获益值：10千万。【例题11】现有一批重要物资空运到距离灾区发生地最近的某机场后，要通过马路运输将物资运往10个重灾地点，下图为各重灾地点的交通网络示意图，其中1代表机场，2-11代表10个重灾区，12和13代表道路节点。请你求出从机场到各重灾区的最短路径。解：本题干脆运用Dijkstra标号算法即可求出从机场1到各灾区的最短路。第一步：对灾区1进行标号，为（0，-），接着对其余各点进行临时标号，分别为灾区3：（-，150）；灾区10：（-，100）；灾区9：（-，190）；道路节点12：（-，100）；道路节点13：（-，80）；灾区2：（-，）；0灾区4：（-，）；灾区5：（-，）；灾区6：（-，）；灾区7：（-，）；灾区8：（-，）；灾区11：（-，）；其次步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1：（0，-）；道路节点13：（80，-）；灾区3：（-，150）；灾区10：（-，100）；灾区9：（-，190）；道路节点12：（-，100）；灾区2：（-，）；0灾区4：（-，）；灾区5：（-，）；灾区6：（-，）；灾区7：（-，）；灾区8：（-，）；灾区11：（-，）；第三步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1：（0，-）；道路节点13：（80，-）；道路节点12：（100，-）；灾区10：（100，-）；灾区3：（-，150）；灾区9：（-，145）；灾区2：（-，140）；灾区6：（-，125）；灾区4：（-，）；灾区5：（-，）；灾区7：（-，）；灾区8：（-，）；灾区11：（-，）；第四步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1：（0，-）；道路节点13：（80，-）；道路节点12：（100，-）；灾区10：（100，-）；灾区6：（125，-）；灾区3：（-，150）；灾区9：（-，145）；灾区2：（-，140）；灾区4：（-，）；灾区5：（-，）；灾区7：（-，）；灾区8：（-，165）；灾区11：（-，307）；第五步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1：（0，-）；道路节点13：（80，-）；道路节点12：（100，-）；灾区10：（100，-）；灾区6：（125，-）；灾区2：（140，-）；灾区3：（-，150）；灾区9：（-，145）；灾区4：（-，225）；灾区5：（-，）；灾区7：（-，215）；灾区8：（-，165）；灾区11：（-，307）；第六步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1：（0，-）；道路节点13：（80，-）；道路节点12：（100，-）；灾区10：（100，-）；灾区6：（125，-）；灾区2：（140，-）；灾区9：（145，-）；灾区3：（-，150）；灾区4：（-，225）；灾区5：（-，）；灾区7：（-，215）；灾区8：（-，165）；灾区11：（-，245）；第七步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1：（0，-）；道路节点13：（80，-）；道路节点12：（100，-）；灾区10：（100，-）；灾区6：（125，-）；灾区2：（140，-）；灾区9：（145，-）；灾区3：（150，-）；灾区4：（-，183）；灾区5：（-，196）；灾区7：（-，215）；灾区8：（-，165）；灾区11：（-，245）；第八步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1：（0，-）；道路节点13：（80，-）；道路节点12：（100，-）；灾区10：（100，-）；灾区6：（125，-）；灾区2：（140，-）；灾区9：（145，-）；灾区3：（150，-）；灾区8：（165，-）；灾区4：（-，183）；灾区5：（-，196）；灾区7：（-，210）；灾区11：（-，245）；第九步：选择临时标号最小的，转为永久性标号，并将各结点标号重新标号灾区1：（0，-）；道路节点13：（80，-）；道路节点12：（100，-）；灾区10：（100，-）；灾区6：（125，-）；灾区2：（140，-）；灾区9：（145，-）；灾区3：（150，-）；灾区8：（165，-）；灾区4：（183，-）；灾区5：（196，-）；灾区7：（210，-）；灾区11：（245，-）；算法结束。【例题12】求下面网络s到t的最大流和最小截，从给定的可行流起先标号法。(要求每得到一个可行流后，即每次增广之后，重新画一个图，标上增广后的可行流，再进行标号法)解：答：最大流为15，最小割截为【例题13】绘制工程图，计算各工作的最早起先时间和最早完工时间，并给出关键路途。工序内容工时(天)紧前工序ABCDEFG 初步探讨探讨选点准备调研方案联系调研点培训工作人员实地调研写调研报告并汇总 124235 4 / A ABB、CD、E F解：（）工程图如下： 12A3B4CDE567FG（）各工序时间如下图， 工程ESEFA01B13C15D35E58F813G1317（）关键路途是A-C-E-F-G 【例题14】甲乙乒乓球队进行团体对抗赛，每对由三名球员组成，双方都可排成三种不同的阵容，每一种阵容可以看成一种策略，双方各选一种策略参赛。竞赛共赛三局，规定每局胜者得1分，输者得-1分，可知三赛三胜得3分，三赛二胜得1分，三赛一胜得-1分，三赛三负得-3分。甲队的策略集为S1=1，2，3，乙队的策略集为S1=1，2，3，依据以往竞赛得分资料，可得甲队的赢得矩阵为A，如下：A=1 1 11 -1 -33 -1 3 试问这次竞赛各队应采纳哪种阵容上场最为稳妥。解：甲队的1，2，3 三种策略可能带来的最少赢得，即矩阵A中每行的最小元素分别为： 1，-3，-1，在这些最少赢得中最好的结果是1，即甲队应实行策略1 ，无论对手采纳什么策略，甲队至少得1分。而对乙队来说，策略1，2，3 可能带来的最少赢得，即矩阵A中每列的最大因素（因为两人零和策甲队得分越多，就使得乙队得分越少），分别为： 3，1，3，其中乙队最好的结果为甲队得1分，这时乙队实行2 策略，不管甲队采纳什么策略甲队的得分不会超过1分（即乙队的失分不会超过1）。这样可知甲队应采纳1 策略，乙队应实行2 策略。把这种最优策略1 和2 分别称为局中人甲队、乙队的最优纯策略。这种最优纯策略只有当赢得矩阵A=（aij）中等式 max min aij = min max aij i j j i成立时，局中人才有最优纯策略，并把（1 ，2）称为对策G在纯策略下的解，又称（1 ，2）为对策G的鞍点。【例题15】矩阵对策的混合策略5 9 8 6 A=解：首先设甲运用1 的概率为X1，运用2 的概率为X2，并设在最坏的状况下（即乙出对其最有利的策略状况下），甲的赢得的平均值等于V。这样我们建立以下的数学关系：1.甲运用1 的概率X1和运用2 的概率X2的和为1，并知概率值具有非负性，即X1+ X2=1，且有X10，X20.2.当乙运用1 策略时，甲的平均赢得为：5X1+ 8X2，此平均赢得应大于等于V，即5X1+ 8X2V3.当乙运用2 策略时，甲的平均赢得为：9X1+ 6X2，此平均赢得应大于等于V，即9X1+ 6X2V其次步，我们来考虑V的值，V的值与赢得矩阵A的各因素的值是有关的，假如A的各元素的值都大于零，即不管甲采纳什么策略，乙采纳什么策略，甲的赢得都是正的。这时的V值即在乙出对其最有利的策略时甲的平均赢得也明显是正的。因为A的全部元素都取正值，所以可知V0.第三步，作变量替换，令Xi =(i=1，2)考虑到V0，这样把以上5个数量关系式变为：X1+ X2 =，X10，X20，5X1+ 8X2 19X1+ 6X2 1对甲来说，他希望V值越大越好，也就是希望的值越小越好，最终，我们就建立起求甲的最优混合策略的线性规划的模型如下：min X1+ X2约束条件： 5X1+ 8X2 19X1+ 6X2 1 X10，X20同样求出乙最优混合策略，设y1, y2分别为乙出策略1，2 的概率，V为甲出对其最有利的策略的状况下，乙的损失的平均值。同样我们可以得到：y1+ y2=1,5y1+ 9y2 V8y1+ 6y2 Vy10，y20.同样作变量替换，令yi =(i=1，2)得关系式： y1+ y2 =5y1+ 9y2 18y1+ 6y2 1y10，y20.乙希望损失越少越好，即V越小越好而越大越好，这样我们也建立了求乙的最优混合策略的线性规划的模型如下：max y1+ y2约束条件： 5y1+ 9y2 18y1+ 6y2 1y10，y20.