运筹学期末复习提纲课件.ppt

1、l线性规划问题及其数学模型l图解法l单纯形法原理l单纯形法计算步骤l单纯形法的进一步讨论l目标能表成求 MAX 或 MINl达到目标有多种方案l实现目标有一定条件l目标和条件都能用线性函数表示例如，对于线性规划问题 0,6323523632max432143214214321xxxxxxxxxxxxxxxz其系数矩阵为 31125023则下面两个矩阵都是该线性规划问题的基。12233152和还能找出其它基吗？基解基解：令非基变量等于0的解。基可行解：基可行解：基解 + 可行解 例如，对于上面的线性规划问题，如果取x1，x2为基变量，则令非基变量x3，x4为零，约束方程组为 623232121x

2、xxx解之得 。故我们得到基解注意到这个基解还是一个可行解。 712,71521xx0, 0,712,7154321xxxx是否所有的基解都是基可行解？（选x1,x3作为基变量）0,1823122453max54321321423221xxxxxxxxxxxxxxz2.3 (1)x1x2x3x4x5z是否可行12620036y24306027y34600-642n460-612018n5094-6045n60640630y740012612y800412180y(2) 图解法 对只包含两个决策变量只包含两个决策变量的线性规划问题，可以用图解法图解法来求解。图解法顾名思义就是通过作图来求解的方法

3、，它简单直观、并有助于说明一般线性规划问题求解的基本原理。 线性规划的标准形式线性规划的标准形式0,.,. .max2122122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz它具有如下四个特征：目标函数求max；约束方程符号取“=” ；bi非负；所有决策变量xj非负。l线性规划问题的所有可行解构成的集合是凸集，也可能为无限集。他们有有限个顶点，线性规划问题的每个基可行解对应可行域一个顶点，反之亦然。若线性规划问题有最优解，必在某顶点达到。l将人工变量在目标函数中反映出来得到如下形式的线性规划：0,4222212

4、232max876543216321853217432187321xxxxxxxxxxxxxxxxxxxxxxMxMxxxxz0, 0, 0, 2, 0, 2 . 1, 4 . 1, 087654321xxxxxxxx4 . 5527*z因此最优解为最优目标函数值为需要说明的是，如果在用大M法求解线性规划问题时，最终表的基变量中还含有人工变量，那么这个最终表并没有给出原来问题的基可行解，从而没有给出原来的线性规划问题最优解。这时原来线性规划问题为无可行解无可行解。用用EXCEL执行该计算过程执行该计算过程0, 2, 0,56,57, 0654321xxxxxx4 . 55/27*z故原来问题的

5、最优解为最优目标函数值这一结果与大M法得到的结果是一致的。无可行解的判别无可行解的判别：在用大M法求解线性规划问题时，若最终单纯形表的基变量中含人工变量；或用两阶段法求解时，第一阶段最终表的基变量中含非零的人工变量，也就是第一阶段最优目标函数值不等于零，则线性规划问题无可行解。 规范形式的线性规划与对偶规划问题规范形式的线性规划与对偶规划问题0. .maxXbAXtsCXz0. .minYCYAtsYbw原问题（LP）对偶问题（DLP） 3.2.2 弱对偶性定理：弱对偶性定理： 如果X、Y分别是原问题和对偶问题的一个可行解，则其对应的原问题的目标函数值不大于对偶问题的目标函数值，也即YbCX0

6、XbAX0YCYAYbYAXYAXCXCX)(证明：证明：因为X、Y分别是原问题（3.1）与对偶问题（3.2）的可行解，故： 所以l推论一：推论一：原问题任一可行解的目标函数值是其对偶问题目标函数值的下界；反之对偶问题任一可行解的目标函数值是起原问题目标函数值的上界。l推论二：如果原问题存在无界解，则对偶问题一定无可行解；反之，如果对偶问题存在无界解，原问题也一定不存在可行解。l注意，该推论的逆反定理并不成立。l注意，该推论的逆反定理并不成立。l推论三：如果原问题无解，且对偶问题有可行解，则对偶问题具有无解解，；反之，如果对偶问题无解，且原问题有可行解，则对偶问题具有无界解。l 最优性定理约束

7、 方程 也分为两种情况： ，约束条件比较松； ，约束条件比较紧；yi=0,分为两种情况：yi0，约束条件比较松；yi=0，约束条件比较紧；injjijbxa1injjijbxa1injjijbxa1变量同其对偶问题的约束方程之间至多只能够有一个取松弛的情况，当其中一个取松弛的情况时，另外一个比较紧，即取严格等号 。l例已知下面的LP1和LP2为一组对偶规划，且已知LP1的最优解为X=（1.5，1）。试运用互补松弛定理求出对偶问题的最优解Y。0,934425223max2121212121xxxxxxxxs.t.xxz生产计划问题（LP1）资源定价问题（LP2）0,232342. .945min

8、321321321321yyyyyyyyytsyyyw解：由X=（1.5，1）得55 . 3221 xx01y0, 021xx232342321321yyyyyy联立求解得：5 . 0, 5 . 0, 0321yyy 解：由X=（1.5，1）得55 . 3221 xx01y0, 021xx232342321321yyyyyy联立求解得：5 . 0, 5 . 0, 0321yyy 解：由X=（1.5，1）得55 . 3221 xx01y0, 021xx232342321321yyyyyy联立求解得：5 . 0, 5 . 0, 0321yyy 约束条件右端向量b的变化（1）偏差变量）偏差变量 d+

9、：正偏差变量，表示决策值超出目标值的部分：正偏差变量，表示决策值超出目标值的部分 d-：负偏差变量，表示决策值未达到目标值的部分：负偏差变量，表示决策值未达到目标值的部分 按定义有：按定义有：d+ 0， d- 0 ，d+ d- = 0（2）绝对约束和目标约束）绝对约束和目标约束 绝对约束（硬约束）：必须严格满足的约束条件绝对约束（硬约束）：必须严格满足的约束条件 目标约束（软约束）：目标规划特有目标约束（软约束）：目标规划特有 （3）优先因子（）优先因子（P）和权系数（）和权系数（W） 优先因子用优先因子用P1，P2， Pl表示，规定表示，规定 Pl Pl+1，表示，表示Pl比比Pl+1有更大

10、的优先权。有更大的优先权。（4）目标函数）目标函数 决策值决策值=目标值目标值 min f (d+ + d- ) 决策值决策值目标值目标值 min f (d- ) l例例4.1 某企业计划生产甲、乙两种产品。已知有关数某企业计划生产甲、乙两种产品。已知有关数据见表据见表4-1。问如何安排生产使获得的总利润最大？。问如何安排生产使获得的总利润最大？项项 目目甲甲 乙乙 拥有量拥有量原材料原材料（kg）2111设备设备（台时台时)1210利利 润（元润（元/件）件）810表表 4-1l设设x1、x2分别表示计划生产产品甲、乙的产量，它的数学模分别表示计划生产产品甲、乙的产量，它的数学模型为：型为：

11、l它的最优解为它的最优解为x1=4，x2=3，最大目标函数值为，最大目标函数值为62。max z=8x1+10 x2 2x1+ x2 11st. x1+ 2x2 10 x1 , x20l但企业的经营目标不仅是利润，企业还考虑了以下问题：但企业的经营目标不仅是利润，企业还考虑了以下问题：（1）根据市场信息，产品甲开始出现滞销现象，故考虑产品）根据市场信息，产品甲开始出现滞销现象，故考虑产品甲的产量应不超过产品乙；甲的产量应不超过产品乙；（2）超过计划供应的原材料需高价采购，应避免过量消耗；）超过计划供应的原材料需高价采购，应避免过量消耗； （3）应尽可能充分利用设备台时，但不希望加班；）应尽可能

12、充分利用设备台时，但不希望加班；（4）应尽可能达到并超过计划利润指标）应尽可能达到并超过计划利润指标56元。元。 l例例4.2 例例4.1的决策者经过综合考虑，决策者的目标分别为：的决策者经过综合考虑，决策者的目标分别为：首先原材料使用限额不能突破；其次产品甲的产量不大于首先原材料使用限额不能突破；其次产品甲的产量不大于产品乙；再次充分利用设备台时，不希望加班；最后利润产品乙；再次充分利用设备台时，不希望加班；最后利润额不少于额不少于56元。问应如何安排生产？元。问应如何安排生产？l解：原材料使用限额的约束是绝对约束，其他三个约束是解：原材料使用限额的约束是绝对约束，其他三个约束是属于目标约束

13、，分别赋予这三个目标的优先因子为属于目标约束，分别赋予这三个目标的优先因子为P1，P2，P3。这问题的数学模型为：。这问题的数学模型为： 2x1 + x2 11 x1 - x2 + d1- - d1+ =0 x1 + 2x2 + d2- - d2+ =108x1 + 10 x2 + d3- - d3+ =56 x1,x2,di-,di+ 0 i=1,2,3min P1 d1+ , P2 ( d2- + d2+ ) , P3 d3- s.t.32目标规划模型的一般形式：目标规划模型的一般形式： Min Pl（ wlk-dk- + wlk+dk+ ）,l=1,2,Lk =1Kckj xj + dk

14、- - dk+ = gk ， k =1，2，Kj =1naij xj （=，） bi ，i =1，2，mj =1nxj 0 , j =1，2，ndk- ，dk+ 0 , k =1，2，KS.t.33目标规划模型的一般形式：目标规划模型的一般形式： Min Pl（ wlk-dk- + wlk+dk+ ）,l=1,2,Lk =1Kckj xj + dk- - dk+ = gk ， k =1，2，Kj =1naij xj （=，） bi ，i =1，2，mj =1nxj 0 , j =1，2，ndk- ，dk+ 0 , k =1，2，KS.t.当总产量当总产量 = = 总销量，称为产销平衡问题总销量

15、，称为产销平衡问题 当总产量当总产量总销量，称为产销不平衡问题总销量，称为产销不平衡问题06=+5=+6=+3=+9=+4=+7=+5+10+4+7+8+2+9+01+3+11+3=min343332312423222114131211342414332313322212312111343332312423222114131211343332312423222114131211xxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxxs.t.xxxxxxxxxxxxzl运输问题含有运输问题含有mn个变量，个变量，m+n个约束方程。其系数矩阵的结构比个约束方程。其系数矩阵的结构比较

16、特殊，对应变量较特殊，对应变量xij的系数向量，其分量中除第的系数向量，其分量中除第i个和第个和第m+j个为个为1以以外，其余的都为零外，其余的都为零 l模型中只有个相互独立的约束方程。因此，运输问题的任一基可行解模型中只有个相互独立的约束方程。因此，运输问题的任一基可行解都有都有m+n-1个基变量个基变量 。2) 沃格尔法沃格尔法列罚数列罚数行罚数行罚数25130116213012 321212017635200126 31433111= c11-c13+c23-c21=3-3+2-1=1解的最优性检验解的最优性检验 1) 闭回路法闭回路法63 34130310-1 -529121-1101

17、2vj ui基变量：基变量：cij = ui+vj 非基变量：非基变量：ij = cij (ui + vj)l1.一般产销不平衡运输问题一般产销不平衡运输问题1)1)总产量总产量 总销量总销量 n1jjm1iiba 0 xn,3,2,1j,bxm,3,2,1i,ax.t .sxczminijm1ijijn1jiijm1in1jijij假想一销地假想一销地Bn+1，令销量为，令销量为 , 运价运价c = 0 n1jjm1iiba5.1 整数规划实例及一般模整数规划实例及一般模型型5.2 分支定界法分支定界法5.3 0-1整数规划整数规划5.4 指派问题指派问题l纯整数规划：纯整数规划：xj全部是

18、整数全部是整数l混合整数规划：混合整数规划： xj部分是整数部分是整数l0-1型整数规划：型整数规划：xj = 0或或1整数规划的可行解集合是它的松弛问题可整数规划的可行解集合是它的松弛问题可行解集合的一个子集，即整数规划的可行解行解集合的一个子集，即整数规划的可行解一定是其松弛问题的可行解（反之不然）一定是其松弛问题的可行解（反之不然）整数规划问题的最优目标函数值不会优于整数规划问题的最优目标函数值不会优于其松弛问题最优解的目标函数值其松弛问题最优解的目标函数值若松弛问题的可行解满足整数约束，则它若松弛问题的可行解满足整数约束，则它也是整数规划的可行解也是整数规划的可行解整数规划问题的最优解

19、不能由其松弛问题整数规划问题的最优解不能由其松弛问题最优解经过简单取整得到最优解经过简单取整得到如用如用“舍入取整法舍入取整法”可得可得到到4 4个点即个点即(2(2，2), (22), (2，3), (33), (3，2), (32), (3，3)3)。显。显然，它们都不可能是整数然，它们都不可能是整数规划的最优解。规划的最优解。且取整数0,823324max21212121xxxxxxxxz松弛问题最优解整数规划最优解不能通过舍入取整地方法，由松弛不能通过舍入取整地方法，由松弛问题的解得到整数规划的最优解问题的解得到整数规划的最优解6.1 动态规划的基本概念动态规划的基本概念6.2 最优化

20、原理最优化原理6.3 经济管理问题举例经济管理问题举例动态规划的分类：动态规划的分类：离散确定型离散确定型 离散随机型离散随机型 连续确定型连续确定型 连续随机型连续随机型决策决策1 1状态状态1决策决策2 2状态状态2决策决策n n状态状态3状态状态n1、阶段、阶段 ，阶段数，阶段数阶段变量：阶段变量：k; 阶段数记作阶段数记作n。无后效性：如果某阶段的状态给定，这阶段以后过程的无后效性：如果某阶段的状态给定，这阶段以后过程的发展不受这阶段以前各阶段状态的影响发展不受这阶段以前各阶段状态的影响 3、决策、决策 某阶段状态确定后，为确定下一阶段的状态，所作出某阶段状态确定后，为确定下一阶段的状

21、态，所作出的决定（选择）。的决定（选择）。 决策变量：决策变量：u k(s k) 表示第表示第k阶段状态为阶段状态为s k时的决策时的决策 允许决策集合：允许决策集合：D k ( s k )2、状态、状态每个阶段开始时所处的自然状态或客观条件每个阶段开始时所处的自然状态或客观条件状态变量：状态变量：s k状态集合：状态集合：S k4、策略：、策略： 由决策组成的序列称为策略。由决策组成的序列称为策略。 p 1 , n u 1(s 1) , u 2(s 2) , , u n(s n) 允许策略集合：允许策略集合：P1 , n最优策略：最优策略： p* 1 , n 子策略：子策略：5、状态转移方程

22、、状态转移方程 s k+1 = T k ( s k , u k )6、效益、效益(指标指标)函数函数: Vkn(sk,pkn(sk) 阶段效益函数：阶段效益函数：wk(sk,uk (sk) 最优效益函数：最优效益函数：fk(sk) 最优策略最优策略:pkn*()knkpx)*,()(,11,111nnpsVsf全过程的最优效益函数全过程的最优效益函数07681614141621202226所以最短路为AB1C2D2E，最短路长为26。0)()(),(min)(f5511ksfsfuswskkkkkk动态规划的基本方程（逆序法）：动态规划的基本方程（逆序法）：f k ( sk)表示从第表示从第k

23、阶段状态阶段状态sk到终点到终点F的最短距离的最短距离如果一个策略是最优策略，则其子策略也一定是最优策略；如果一个策略是最优策略，则其子策略也一定是最优策略；如果两段子策略都是最优策略，则连起来是否是最优策略呢？如果两段子策略都是最优策略，则连起来是否是最优策略呢？动态规划的基本方程（动态规划的基本方程（顺序法顺序法）：）：0)()(),(),(min)(f11111ksfssusfuswskkkkkkkkk图与网络的基本概念图与网络的基本概念 最短路径问题最短路径问题 最大流问题最大流问题 最小费用最大流问题最小费用最大流问题5 5、连通图：、连通图：圈：圈：无向无向图G =（V, E）中起

24、点和终点重合的）中起点和终点重合的链称为链称为圈圈初等、简单圈：初等、简单圈：没有重复点没有重复点的的圈称为圈称为初等圈初等圈，没有重复边，没有重复边的圈称为的圈称为简单圈简单圈。( v( v1 1 , e , e1 1 , v , v2 2 , e , e6 6 , v , v4 4 , e , e3 3 , v , v3 3 , e , e5 5 , v , v1 1 ) )6 6、子图与生成子图：、子图与生成子图：子图：子图：图图G=( V, E )，E是是E的子集，的子集，V是是V的子的子集，且集，且E 的边与的边与V的顶点想关联，的顶点想关联， G=( V, E)是图是图G的一个的一

25、个子图子图。生成子图生成子图：若：若V=V，则，则G是是G的的生成子图生成子图7.1.2 树的概念及性质树的概念及性质1、树（、树（T）：）：无圈的连通图称为无圈的连通图称为树树 树叶树叶 分枝点分枝点7.1.2 树的概念及性质树的概念及性质2 2、树的性质、树的性质性质性质7.17.1 树中任意两点之间有且只有一条链。树中任意两点之间有且只有一条链。性质性质7.27.2 如图如图G G中任意两点之间，有且只有一中任意两点之间，有且只有一条链，则该图条链，则该图G G是一个树。是一个树。性质性质7.37.3 一个树，则一个树，则m=n-1m=n-1。性质性质7.47.4 树中任意两个不相邻的点

26、之间增加一树中任意两个不相邻的点之间增加一条边，则形成唯一的圈。条边，则形成唯一的圈。性质性质7.57.5 一个树如果去掉任何一条边，该图就一个树如果去掉任何一条边，该图就不再连通。不再连通。7.1.2 7.1.2 树的概念及性质树的概念及性质3 3、图的生成树、图的生成树生成树（支撑树）：生成树（支撑树）：图图G G的生成子图是一棵树，则的生成子图是一棵树，则称该树为称该树为G G的的生成树生成树图图G G中属于生成树的边称为中属于生成树的边称为树枝树枝，不属于生成树的，不属于生成树的边称为边称为弦弦定理定理7.37.3：图图G=G=（V,EV,E）, ,有生成树的充分必要条件有生成树的充分必要条件为为G G是连通图是连通图精品课件精品课件！精品课件精品课件！4、最小生成树、最小生成树：图：图G = ( V，E )的生成树所有树枝上的的生成树所有树枝上的权数的总和权数的总和,称为称为生成树的权生成树的权。权数最小的生成树称为。权数最小的生成树称为最小生成树最小生成树。寻找最小生成树的方法：避圈法、破圈法寻找最小生成树的方法：避圈法、破圈法最小生成树最小生成树权权=11