运筹学复习题(推荐).doc

运筹学复习资料基本要求一、将线性规划化为标准型和写出相应的对偶规划；二、用图解法求解具有两个决策变量的线性规划问题；三、用单纯形方法及人工变量法求解线性规划问题；四、灵敏度分析；五、整数规划与分枝定界法，0-1规划与隐枚举法，指派问题六、求解产销平衡的运输问题和产销不平衡的运输问题；七、动态规划与求解。例题选讲例：某工厂在计划期内要安排生产、两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。按工艺规定：产品和在个设备上所需要的加工时数于下表中。已知各设备在计划期内的有效台时数分别是12、8、16和12。该工厂每生产一件产品可得利润2圆，每生产一件产品可得利润3圆，问：应如何安排生产，可获得最大利润。 设备产品ABCD21423214 解 设生产产品和分别为和件，则由条件可得关系 标准型的概念： 目标函数为极大化； 资源常数； 约束条件关系为等式； 决策变量。 例： 将下面的线性规划化为标准型 无非负限制 解 二、图解法 例 用图解法求解线性规划问题 极大化 解：最优解三、单纯形方法 对于具有两个以上决策变量的线性规划问题，我们采用单纯形方法进行求解。具体过程是： 建立单纯形表，在单纯形表中，务必使基变量的价值系数为零，则检验数行是价值系数行的相反数； 若检验数则当前解为最优解（当前解是基变量取相应的资源常数，非基变量取为零）；若存在检验数，则要进行相应的换基，即：迭代； 进基：进基变量 ： 出基：出基变量为第行所对应的基变量，由下面的关系确定 以主元进行迭代，目标：主元化为1，该列的其余元化为零。 再一次判定当前解是否为最优解。 例 用单纯形法求解线性规划 极大化 解 引入松弛变量，得到原规划的标准型 极大化 单纯形表为 所以，最优解为最优解值为21.人工变量法对于约束条件中没有阶单位阵的线性规划，通过引入适当的人工变量，再加以求解。 1. 大法在大法中，引入的人工变量的价值系数为，而相应的约束条件系数向量为单位向量。2.二阶段法例 用人工变量法求解线性规划。 s.t. 符号不限。例 求解规划 建立对偶规划的要点 原规划是极大化，则对偶规划是极小化；原规划的价值系数是对偶规划中的资源常数； 原规划与对偶规划的约束条件系数矩阵为矩阵的转置关系； 原规划中的第个决策变量无非负限制，则对偶规划中的第个约束条件为等式； 原规划中的第个决策变量非正，则对偶规划中的第个约束条件取反向不等式； 例 求下面问题的对偶规划极大化 无非负限制。 解 极小化 对偶单纯形法 基本要求：检验数；资源常数存在负值。 解法：1 列出对偶单纯形表；2 将基变量在目标函数中系数化为零，检验数为新目标函数中系数的相反数；3 判断，若，则当前解为最优解； 若中存在负项，则进行迭代，确定出基和进基变量； 出基：记为第r行对应的变量； 进基：，为进基变量； 以为主元进行迭代。目标：将主元化为1，该列的其余元化为0。灵敏度分析 灵敏度分析的任务：确定各个变量使得最优解保持不变的变化范围；以及在最优解改变的时候求出相应的最优解。 非基变量的价值系数的变化范围，使最优解保持不变。 基变量的价值系数的变化范围，使最优解保持不变。：若最优解改变，则对两种情况有 资源常数变化范围使最优基不变： 非基变量的系数向量的增量的变化范围使最优解不变： 增加新的决策变量使最优解保持不变： 例：设线性规划 求：1.最优解; 2.确定的范围,使最优解不变; 取,求最优解; 3.确定的范围,使最优基不变, 取求最优解; 4.引入求最优解;解 1.由单纯形方法得即,原问题的最优解为2.因为非基变量,故当时,即时, 最优解不变; 为基变量,由公式,当最优解不变, 即时,最优解不变.现对最优解改变,此时原最优表为即相应的最优解为3.此时得最优基不变.即最优基不变.当最优解改变,此时此时最优表为即最优解为4.此时故最优解改变.相应的最优表为例 用分枝定界法求解整数规划用隐枚举法求解0-1规划运输问题（产销平衡）的求解方法：表上作业法1.用最小元素法求初始解；2.用位势法求出当前解所对应的位势：若为基变量，则行位势和列位势满足关系3.用位势法计算非基变量的影响系数：若为非基变量，则影响系数与行位势和列位势满足关系4.最优解的判定：若影响系数则当前解为最优解；否则通过解的调整求出最优解；5.解的调整：记：令为所对应的非基变量，以为当前变量，构造闭回路；在闭回路上确定最大调整量；求出新解6.重新判定当前解是否为最优解。产销不平衡的运输问题的求解方法：设置虚拟产地或销地以达到产销平衡.指派问题的求解：1.的指派问题的最小值解的求解方法：用行缩减和列缩减在每行和每列至少产生一个零；用划线法判定是否有个独立的零；如果有个独立的零，则可以求出最小值解；若没有个独立的零，重新进行调整，以求出个独立的零。2.的指派问题的最小值解的求解方法：设置虚拟变量，其价值系数取为零。3.指派问题中的最大值求解。例 求下面运输问题的最小值解：12341311310721923437410593656解：由最小元素法得到初始解：v1=2v2=9v3=3v4=101934u1=01311310743u2=-121923431u3=-53741059633656则：，最小值为-6，非基变量为，闭回路，最大调整量为1，得新解：，重新计算位势及影响系数，得下表：v1=8v2=9v3=3v4=101234u1=01311310752u2=-721923431u3=-53741059633656，最小值为-5，非基变量为，闭回路，最大调整为2，得新解：重新计算位势及影响系数，得下表：v1=3v2=4v3=3v4=51234u1=01311310725u2=-221923413u3=03741059633656，此时，故当前解为最优解。最优解值为：。产销不平衡的运输问题：对产销不平衡的运输问题，求解的基本方法是设置虚拟变量，其单位运输成本为0，从中求出最优解。例：求下面运输问题的最小运费解：1234121134721035953781272346例: 求解运输问题123413276502752360325452560402015例：求下面指派问题的最小值解： 解： 故最优解为：，最优解值为。例：求下面指派问题的最小值及最大值解：例：求下面指派问题的最大值解：例：最短路问题：求下面从到的最短线路和最短距离：解：；所以：所以：,。例：设有某种肥料共6个单位，准备给4块粮田用，其每块粮田施肥数量与增产粮食的关系如下表所示。试求对每块田施多少单位重量的肥料，才能使总的粮食增产最多。施 肥粮 田1234120251828242453947360576165475657874585709080690739585解：表1，对两块田的施肥：0123456收益田1田2120+00+252501242+020+250+454511360+042+2520+450+576721475+060+2542+4520+570+658722585+075+2560+4542+5720+650+7010532690+085+2575+4560+5742+6520+700+7312042表2，对三块田的施肥：0123456收益123125+00+1825010245+025+180+3945110367+045+1825+390+6167210487+067+1845+3925+610+78872205105+087+1867+3945+6125+780+901062126120+0105+1887+3967+6145+7825+900+95128213表3，对四块田的施肥：0123456收益12346128+0106+2887+4767+6545+7825+800+851342202所以最优解为2，2，0，2，最大增产量为134。例 某工厂有100太机器，拟分四个周期使用，在每一周期中有两种生产任务，据经验，把台机器投入第一种生产任务，则在一个周期内有台机器作废；余下的机器全部投入第二种生产任务，且有机器作废。在第一种任务中，每台机器可收益10个单位，而第二种任务中每台机器可收益7个单位，问怎样分配机器，能使总收益为最大？