运筹学总复习.doc

《运筹学总复习.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、基本要求一、将线性规划化为标准型和写出相应的对偶规划；二、用图解法求解具有两个决策变量的线性规划问题；三、用单纯形方法及人工变量法求解线性规划问题；四、灵敏度分析；五、整数规划与分枝定界法，0-1规划与隐枚举法，指派问题六、求解产销平衡的运输问题和产销不平衡的运输问题；七、动态规划与求解；八*、带回收的资源利用问题及连续型的动态规划求解；九*、存储问题求解（无限供货能力下不容许缺货及容许缺货模型）例题选讲例：某工厂在计划期内要安排生产Ⅰ、Ⅱ两种产品，这些产品分别需要在A、B、C、D四种不同的设备上加工。

2、按工艺规定：产品Ⅰ和Ⅱ在个设备上所需要的加工时数于下表中。已知各设备在计划期内的有效台时数分别是12、8、16和12。该工厂每生产一件产品Ⅰ可得利润2圆，每生产一件产品Ⅱ可得利润3圆，问：应如何安排生产，可获得最大利润。设备产品ABCDⅠ2142Ⅱ3214解设生产产品Ⅰ和Ⅱ分别为和件，则由条件可得关系⑴标准型的概念：①目标函数为极大化；②资源常数；③约束条件关系为等式；④决策变量。例：将下面的线性规划化为标准型无非负限制解二、图解法例用图解法求解线性规划问题极大化解：最优解三、单纯形方法对于具有两个以上

3、决策变量的线性规划问题，我们采用单纯形方法进行求解。具体过程是：⑴建立单纯形表，在单纯形表中，务必使基变量的价值系数为零，则检验数行是价值系数行的相反数；⑵若检验数则当前解为最优解（当前解是基变量取相应的资源常数，非基变量取为零）；若存在检验数，则要进行相应的换基，即：迭代；⑶①进基：进基变量：②出基：出基变量为第行所对应的基变量，由下面的关系确定③以主元进行迭代，目标：主元化为1，该列的其余元化为零。⑷再一次判定当前解是否为最优解。例用单纯形法求解线性规划极大化解引入松弛变量，得到原规划的标准型极大化

4、单纯形表为所以，最优解为最优解值为21.人工变量法对于约束条件中没有阶单位阵的线性规划，通过引入适当的人工变量，再加以求解。1.大法在大法中，引入的人工变量的价值系数为，而相应的约束条件系数向量为单位向量。2.二阶段法例用人工变量法求解线性规划。s.t.符号不限。例求解规划建立对偶规划的要点⑴原规划是极大化，则对偶规划是极小化；⑵原规划的价值系数是对偶规划中的资源常数；⑶原规划与对偶规划的约束条件系数矩阵为矩阵的转置关系；⑷原规划中的第个决策变量无非负限制，则对偶规划中的第个约束条件为等式；⑸原规划中的

5、第个决策变量非正，则对偶规划中的第个约束条件取反向不等式；例求下面问题的对偶规划极大化无非负限制。解极小化对偶单纯形法基本要求：检验数；资源常数存在负值。解法：1．列出对偶单纯形表；2．将基变量在目标函数中系数化为零，检验数为新目标函数中系数的相反数；3．判断，若，则当前解为最优解；若中存在负项，则进行迭代，确定出基和进基变量；出基：记为第r行对应的变量；进基：，为进基变量；以为主元进行迭代。目标：将主元化为1，该列的其余元化为0。灵敏度分析灵敏度分析的任务：确定各个变量使得最优解保持不变的变化范围；以

6、及在最优解改变的时候求出相应的最优解。⑴非基变量的价值系数的变化范围，使最优解保持不变。⑵基变量的价值系数的变化范围，使最优解保持不变。：若最优解改变，则对两种情况有⑶资源常数变化范围使最优基不变：：⑷非基变量的系数向量的增量的变化范围使最优解不变：⑸增加新的决策变量使最优解保持不变：例：设线性规划求：1.最优解;2.确定的范围,使最优解不变;取,求最优解;3.确定的范围,使最优基不变,取求最优解;4.引入求最优解;解1.由单纯形方法得即,原问题的最优解为2.因为非基变量,故当时,即时,最优解不变;为基

7、变量,由公式,当最优解不变,即时,最优解不变.现对最优解改变,此时原最优表为即相应的最优解为3.此时得最优基不变.即最优基不变.当最优解改变,此时此时最优表为即最优解为4.此时故最优解改变.相应的最优表为例用分枝定界法求解整数规划用隐枚举法求解0-1规划运输问题（产销平衡）的求解方法：表上作业法1.用最小元素法求初始解；2.用位势法求出当前解所对应的位势：若为基变量，则行位势和列位势满足关系3.用位势法计算非基变量的影响系数：若为非基变量，则影响系数与行位势和列位势满足关系4.最优解的判定：若影响系数则

8、当前解为最优解；否则通过解的调整求出最优解；5.解的调整：⑴记：⑵令为所对应的非基变量，以为当前变量，构造闭回路；⑶在闭回路上确定最大调整量；⑷求出新解6.重新判定当前解是否为最优解。产销不平衡的运输问题的求解方法：设置虚拟产地或销地以达到产销平衡.指派问题的求解：1.的指派问题的最小值解的求解方法：⑴用行缩减和列缩减在每行和每列至少产生一个零；⑵用划线法判定是否有个独立的零；⑶如果有个独立的零，则可以求出最小值解；⑷若没有个独立的零，重新