运筹学讲义复习.ppt

1,第一章 线性规划及单纯形法,线性规划主要解决有限资源的最佳分配问题 决策变量 决策变量的取值要求非负。 约束条件 存在一组决策变量构成的线性等式或不等式的约束条件。 目标函数 存在唯一的线性目标函数（极大或极小）。 求解方法： 图解法 单纯形解法,2,线性规划标准型,标准型 目标函数极大化， 约束条件为等式， 右端常数项bi0， 决策变量非负。,简记,maxZ= cjx aijxjbi ( i=1,2,m) xj0 ( j=1,2,n),3,非标准型向标准型转化 目标函数极小化问题 只需将目标等式两端乘以 -1 即变为极大化问题。 右端常数项非正 将约束等式两端同乘以 -1 约束条件为不等式 当约束方程为“”时，左端加入一个非负的松弛变量； 当约束条件为“”时，不等式左端减去一个非负的剩余变量(也可称松弛变量)即可。 决策变量xk没有非负性要求 令xk=xk-x k， xk=xk，x k 0， 用xk、x k 取代模型中xk,4,线性规划解的概念,基 m个线性无关的约束方程，称为一个基，用B表示。 称基矩阵的列为基向量，用Pj表示(j=1,2,m) 。 基变量 与基向量Pj相对应的m个变量xj称为基变量 其余的m-n个变量为非基变量。 基解 令所有非基变量等于零，求出基变量的值， 基解是各约束方程及坐标轴之间交点的坐标。 基可行解：满足非负性约束的基解。 最优基：最优解对应的基矩阵，称为最优基。,5,线性规划的解题思路 线性规划问题可以有无数个可行解，最优解只可能在顶点上达到。 顶点对应的是基可行解，故只要在有限个基可行解中寻求最优解。 从一个顶点出发找到一个可行基，得到一组基可行解， 以目标函数做尺度衡量是否最优：若不是，则向邻近的顶点转移，换一个基再求解、检验，如此迭代使目标值逐步改善，直至求得最优解。,6,解的可能性,唯一最优解：只有一个最优点。 多重最优解 两个顶点同是最优解，其连线上的每一点都是最优解，即无穷多个最优解 。 判据：最优单纯形表中存在非基变量的检验数等于k = 0。 无界解 LP问题的可行域无界，目标函数无限增大，缺乏必要的约束 。 判据：若某个k 0所对应的系数列向量Pk0（有进基变量但无离基变量），则是无界解。 无可行解 若约束条件相互矛盾，则可行域为空集。 判据：最终单纯形表中人工变量仍没有置换出去，则没有可行解。,人工变量问题,没有单位列向量的约束方程，需加入人工变量 。 人工变量最终必须等于0才能保持原问题性质不变，在目标函数中令其系数为-M。 M为无限大的正数，若人工变量不为0，则目标函数永远达不到最优，所以必须将人工变量逐步从基变量中替换出去。 如若到最终表中人工变量仍没有置换出去，那么这个问题就没有可行解，当然亦无最优解。,8,1、 下表为用单纯形法计算时某一步的表格。已知该线性规划的目标函数为 约束形式为 x1、x2 、x3为松弛变量，表中解代入目标函数后得Z=14,9,2、某医院昼夜24h各时段内需要的护士数量如下：2:00-6:00 10人，6:00-10:00 15人，10:00-14:00 25人，14:00-18:00 20人，18:00-22:00 18人，22:00-2:00 12人。护士分别于2:00,6:00,10:00,14:00,18:00,22:00分6批上班，并连续工作8小时。试确定：a、该医院至少应设多少名护士，才能满足值班需要？b、若医院可聘用合同工护士，上班时间同正式工护士。若正式工护士报酬为10元/h，合同工护士报酬为15元/h，问医院是否应聘合同工护士及聘多少名？,10,第二章 线性规划的对偶理论与灵敏度分析,对偶问题的数学模型 原问题一般模型： 对偶问题一般模型： maxZ=CX min =Yb AX b YA C X 0 Y 0,11,对偶问题的基本性质,一、单纯形法计算的矩阵描述(表2-3，表3-4，见书P54）,12,二、基本性质（P57） 1、弱对偶性：极大化原问题的任一可行解的目标函数值，不大于其对偶问题任意可行解的目标函数值。 2、最优性。 3、强对偶性。 4、互补松弛性。,13,三、影子价格,对偶问题的经济解释 这说明yi是右端项bi每增加一个单位对目标函数Z的贡献。 对偶变量的值 yi*所表示的第i种资源的边际价值，称为影子价值。 若原问题的价值系数Cj表示单位产值，则yi 称为影子价格。 若原问题的价值系数Cj表示单位利润，则yi 称为影子利润。 影子价格不是资源的实际价格，而是资源配置结构的反映，是在其它数据相对稳定的条件下某种资源增加一个单位导致的目标函数值的增量变化。 对资源i总存量的评估：购进 or 出让 对资源i当前分配量的评估：增加 or 减少,14,四、对偶单纯形法 五、灵敏度分析,1、给出线性规划问题,要求：（1）写出其对偶问题 2）其对偶问题最优解为,，试根据对偶问题性质求出原问题的最优解,15,（1）其对偶问题为： (2)根据对偶问题互补松弛性质，由 代入对偶问题约束条件，可知 有 ，解得，原问题最优解为,16,第三章 运输问题,一、数学模型 设从Ai 到Bj的运输量为xij,（假定产销平衡） 则总运费： minZ= Cij xij 产量约束： xij = ai i=1,2,m, 销量约束： xij = bj j=1,2,n, 非负性约束： xij 0,17,二、表上作业法 1、确定初始方案：最小元素法、西北角法和Vogel法。 2、解的最优性检验：闭回路法和对偶变量法（位势法） 3、解的改进。 三、进一步讨论 将产销不平衡的问题转换为产销平衡问题。,18,1、已知运输问题的供需关系与单位运价表，试用表上作业法求最优解,19,20,第四章 整数规划,一、数学模型,21,二、分枝定界法,分枝定界法(Branch and Bound Method) 基本思想： 先求出整数规划相应的线性规划(即不考虑整数限制)的最优解， 若求得的最优解符合整数要求，则这个解就是原整数规划的最优解； 若不满足整数条件，则任选一个不满足整数条件的变量来构造新的约束，在原可行域中剔除部分非整数解。 然后，再在缩小的可行域中求解新构造的线性规划的最优解，这样通过求解一系列线性规划问题，最终得到原整数规划的最优解。 定界的含义： 整数规划是在相应的线性规划的基础上增加变量为整数的约束条件，整数规划的最优解不会优于相应线性规划的最优解。 对极大化问题来说，相应线性规划的目标函数最优值是原整数规划函数值的上界；,22,分枝定界法,例 maxZ= 5x1 +8 x2 x1 + x2 6 5x1 +9 x2 45 x1, x2 0 x1, x2取整数 第一步,不考虑变量的整数约束,求相应LP(问题1)的最优解： x1=2+/4，x2 =3+3/4，Z1=41+1/4 第二步,定界过程 上界41+1/4； 下界为0。 第三步，分枝过程 将不满足整数约束的变量x1进行分枝，构造两个新的约束条件： x1 2，x1 3 ,23,分枝定界法,问题2：maxZ= 5x1 +8 x2 问题3： maxZ= 5x1 +8 x2 x1 + x2 6 x1 + x2 6 5x1 +9 x2 45 5x1 +9 x2 45 x12 x1 3 x1, x2 0 x1, x2 0 x1, x2取整数 x1, x2取整数 求解问题2相应的线性规划的最优解：x1=2，x2 =3+8/9，Z2=41+1/9 求解问题3相应的线性规划的最优解：x1=3，x2 =3，Z3=39 第四步，定界过程 下界39； 上界41+1/9。 第五步，分枝过程 将不满足整数约束的变量x2进行分枝，构造两个新的约束条件： x2 3，x2 4,24,分枝定界法,问题4：maxZ= 5x1 +8 x2 问题5： maxZ= 5x1 +8 x2 x1 + x2 9 x1 + x2 9 5x1 +9 x2 45 5x1 +9 x2 45 x12 x1 2 x23 x2 4 x1, x2 0 x1, x2 0 x1, x2取整数 x1, x2取整数 求解问题4相应的线性规划的最优解：x1=2，x2 =3，Z4=34 求解问题5相应的线性规划的最优解：x1=1+4/5，x2 =4，Z5=41 第六步，定界过程 下界39； 上界41。 第七步，分枝过程 将不满足整数约束的变量x1进行分枝，构造两个新的约束条件： x1 1，x1 2,25,分枝定界法,问题6： maxZ= 5x1 +8 x2 问题7： maxZ= 5x1 +8 x2 x1 + x2 6 x1 + x2 6 5x1 +9 x2 45 5x1 +9 x2 45 x12 x1 2 x24 x2 4 x11 x1 2 x1, x2 0 x1, x2 0 x1, x2取整数 x1, x2取整数 求解问题6相应的线性规划的最优解：x1=1，x2 =4+4/9，Z6=40+5/9 求解问题7相应的线性规划的最优解：无可行解 第八步，定界过程 LP7的无最优解，不必再分枝，下界39； 上界为40+5/9。 第九步，分枝过程 将不满足整数约束的变量x2进行分枝，构造两个新的约束条件： x2 4，x2 5,26,分枝定界法,问题8：maxZ= 5x1 +8 x2 问题9： maxZ= 5x1 +8 x2 x1 + x2 6 x1 + x2 6 5x1 +9 x2 45 5x1 +9 x2 45 x12 x1 2 x2 4 x2 4 x11 x1 1 x24 x2 5 x1, x2 0 x1, x2 0 x1, x2取整数 x1, x2取整数 求解问题8相应的线性规划的最优解：x1=1，x2 =4，Z8=37 求解问题9相应的线性规划的最优解：x1=0，x2 =5，Z9=40 第十步，定界过程 下界为40； 上界为40。 上界=下界，得整数规划问题的最优解：x1=0，x2 =5，Z=40,27,分枝定界过程,x12,x1 3,x23,x2 4,x11,x1 2,x24,x2 5,分枝定界法,28,x23,x2 4,x11,x12,x24,x2 5,分枝定界法,29,三、指派问题的数学模型及其解法-匈牙利法 设xij=0或1，为1时表示第i个人做第j事 为0时表示不指派第i个人做第j事 数模： minZ=cijxij xij=1 i=1,n xij=1 j=1,n Xij=0或1,30,最有值为：21,31,第五章 网络计划,一、绘制网络图 二、计算时间参数和求关键路线 1、事项时间：最早和最迟 2、工作时间：工序最早可能开工时间与工序最早可能完工时间，工序最迟必须开工时间与工序最迟必须完工时间 3、时差：工序总时差，在不影响其紧后工序最迟必须开工时间的前提下，本工序可以推迟的时间 工序单时差：在不影响其紧后工序最早可能开工时间的前提下，本工序可以推迟的时间 图上计算法和表上计算法。 三、网络优化,32,已知下列资料，要求绘制网络图，并计算最早开工、最迟开工及总时差，指出关键路线。,33,第六章 排队论,一、基本概念及肯道尔（D.G.Kendall）分类 1、队长 N(t)和排队长 Nq(t) 2、等待时间 T(t)和逗留时间Tq(t) 3、忙期B和闲期I 4、记为Pn(t)时刻时系统处于状态n的概率分布。 N(t)-N-L Nq(t)- Nq-Lq T(t)-T-W Tq(t)- Tq-Wq B-B I- I Pn(t)- Pn n :当系统处于状态n时，新来顾客的平均到达率， n：当系统处于状态n时，整个系统的平均服务率， 记s系统中并行的服务台数,34,二、Poisson过程和负指数分布 状态平衡方程和状态转移，概率分布。 三、 M/M/S等待制排队模型 1、