运筹学(2,3,4章)复习.ppt

第 2 章 线性规划与单纯形法 基可行解的结构：非零元素的个数不超过约束矩阵的秩（行数） 1、各种解的定义（基解、基可行解、最优解） 2、单纯形法（以最大化目标函数为例，2.9） ① 掌握单纯表上各个元素的含义 ②检验数的计算； ③换入变量的确定：检验数大于零的变量作为换入变量都可以使目标值增加（选最大的，目标增加的最快 ） ④换出变量的确定 ⑤ 掌握线性规划各种解的判别条件（唯一解、无穷多解、无界解，退化解）（以练习2.10为例说明） ⑥ B- 的确定 （在灵敏度分析时也要用到） 第 3 章 对偶理论和灵敏度分析 1、线性规划对偶性质及应用 ① 利用对偶性质求线性规划的解，（分两步） 要正确的写出线性规划的对偶规划（以对称形式为基准） 利用互补松弛条件求出线性规划的解（例3.7 ，练习2.2,2.3） ② 原始问题与对偶问题解之间的关系 2、灵敏度分析（与单纯形方法、对偶单纯形方法接在一起）() (1) bi 的变化: ① 给出 bi 的变化范围，使最优基不 变 ： B-b≥0 ② 若最优基变了（至少有一个bi0），要用对偶单纯形方法求出新的最优解 给出 Cj 的变化范围，使最优解不变 -------所有检验数不大于零 ② 若最优解变了（至少有一个检验数大于零）， 要用单纯形方法求出新的最优解 (2) Cj 的变化 补充例题： 已知线性规划 的最终单纯形表格为： , cj 2 -1 1 0 0 0 cB xB b x1 x2 x3 x4 x5 x6 0 x4 10 0 0 1 1 -1 -2 2 x1 15 1 0 1/2 0 1/2 1/2 -1 x2 5 0 1 -3/2 0 -1/2 1/2 σj 0 0 -3/2 0 -3/2 -1/2 确定x2的系数c2的变化范围，使原最优解保持最优； -2≤c2≤0 若c2=-4，求新的最优计划。X*=(10,0,0), Z*=20 b3在什么范围内变化，最优基不变？10≤b3≤25 b3=30时，新的最优方案是什么？ X*=(17.5,7.5,0), Z*=27.5 1 写出下列线性规划问题的对偶问题 解：假设对应三个约束的对偶变量分别为y1, y2, y3,写出对偶问题如下： 解：假设对应三个约束的对偶变量分别为y1, y2, y3,写出对偶问题如下： 解：假设对应三个约束的对偶变量分别为y1, y2, y3,写出对偶问题如下： 2 已知线性规划问题 其对偶问题的最优解为y*1=1.2, y*2=0.2,由对偶理论直接求出原问题的最优解。 分析：类似于例3.7利用对偶理论的互补松弛定理求解 解：写出对偶问题 将 y*1=1.2, y*2=0.2带入约束条件，得到(3)(4)为严格不等式，由互补松弛性可得x*1=x*2=0, 因为y*1， y*2 0, 原问题的两个约束为等式约束，所以有 求解后得到 x*3= x*4 =4，所以原问题的最优解为X*=(0,0,4,4) 6(1) 用对偶单纯形发解线性规划 解：把线性规划转化为下面的形式 取y4, y5为基变量，得对偶单纯形表（1） 表（1） 此时基本解为Y=(0,0,0,-2,-1),不可行，所以转第二步。因为Min{-2,-1}=-2, 所以y4为换出变量；又因为min{-24/-6, -5/-1}=4, 所以y2为换入变量，得到新的单纯形表（2） 表（2） 此时基本解为Y=(0,1/3,0,0,-1/3),不可行，所以转第二步。因为-1/30,所以y5为换出变量；又因为min{-15/-5, -1/(-2/3),-4/(-1/3)}=3/2, 所以y3为换入变量，得到新的单纯形表（3） 表（3） 此时基本解为Y=(0,1/4,1/2,0,0)是可行的，所以满足最优检验下的基本可行解，因而是最优解。 4 利用三种资源生产两种产品的最优计划问题归结为下列线性规划 已知最优表是2.32。最优计划是两种产品分别生产35单位和10单位，最大产值Z*=215单位。（1）确定 x2 的系数 c2 的变化范围，使原最优解保持最优；（2）若 c2=6，求新的最优解。 表（2.32） 解（1）x2为基变量，则当 Max{?j/a2j ?a2j0}≤ ?c2 ≤Min{?j/a2j?a2j0} 最优解保持不变。即  -3/2≤ ?c2 ≤-1/(-1)=1  （2）若c2=6,单纯形表若