确定型决策ppt课件

1、小组成员： 郑郑 婕婕1;.确定型决策确定型决策 -确定型决策概述 -确定型决策应具备的条件 -确定型决策主要方法线性规划法线性规划法 -线性规划法概述 -线性规划法数学模型 -线性规划法求解2;.确定型决策是指决策的自然状态是一种既定的情况，即在已知未来可能发生的情况的条件下，根据每一个行动方案只能产生的唯一的结果，选择最优方案。自然状态：指各种可行方案可能遇到的客观情况和状态。 例如：公司可以生产两种产品1和2，生产产品1在销量好的情况下获利100万，不好的情况下获50万，产品2在好的情况下获利90万，差的时候获利60万。3;.（1）存在着决策人希望达到的一个明确目标。（2）只存在一个确定

2、的自然状态。（3）存在着可供选择的两个或两个以上的行动方案。（4）不同的行动方案在确定状态下的损失或利益值可以计算出来。 例如：某企业可向三家银行借贷，但利率不同，分别为8%、7.5%、和8.5%。企业需决定向哪家银行借款。很明显，向利率最底的银行借款为最佳方案。这就是确定型决策。此外，象企业中确定状态下的库存管理库存管理，生产日程计划生产日程计划或设备计划设备计划的决策都属于确定型决策。4;.（1）线性规划法线性规划法（2）直观分析法（3）盈亏平衡分析方法（4）投资回收期法（5）排队法 5;.线性规划（Linear Programming),简称LP。线性规划法产生于20世纪40年代，广泛应

3、用于生产制造生产制造、物料分配物料分配、人力资源计人力资源计划划、运输问题运输问题和投资决策投资决策等方面。这种方法的本质是寻求如何使用有限的资源获得最大的效果，或者用最小的成本完成一项既定的任务。通常是在一些线性等式或不等式的约束条件下，寻求目标函数的最优值最优值。6;.p 问题的提出问题的提出 例1 ：生产计划问题 某公司可以生产两种新产品，其主要数据如下表 所示。 问：产品、各生产多少件，使利润最大？限制 设备台时128台时 材料A4016kg材料B0412kg利润23 显然，此问题是在设备可用时间和材料重量受到限制的情况下来寻求每周利润最大化，其决策方案是决定产品一和产品二各自的产量为

4、多少才最佳？ 7;.线性规划的几个概念线性规划的几个概念（1）决策变量 变量 是运筹学问题或系统中待确定的某些量，在实际问题中常常把变量X叫决策变量。在例1中，就可以记x1为生产产品1的产量；x2为生产产品二的产量。（2）约束条件 求目标函极值时的某些限制称为约束条件。在例1中，设备可用时间和材料重量的约束，全为“”的不等式约束。（3）目标函数 在例1中，生产计划安排的“最优化”要有一定的标准或评价方法，目标函数就是这种标准的数学描述，这里的目标要求生产的利润为最大。Tnxxxx),(218;.根据上面的规定，例1的产品组合问题可抽象地归结为一个数学模型，如下：限制 设备台时128台时 材料A

5、4016kg材料B0412kg利润23目标函数： max z = 2x1 + 3x2约束条件： 1x1 + 2x2 8 4x1 16 4x2 12 x1，x2 0 9;.线性规划的假定条件线性规划的假定条件（1）比例性假定。意味着每种经营活动对目标函数的贡献是一个常数，对资源的消耗也是一个常数。（2）可加性假定。每个决策变量对目标函数和约束方程的影响是独立于其他变量的，目标函数值是每个决策变量对目标函数贡献的总和。（3）连续性假定。决策变量应取连续值。（4）确定性假定。所有参数都是确定的参数，不包含随机因素。 10;.线性规划模型所需的数据线性规划模型所需的数据资源单位活动对资源的使用量资源可

6、利用量12n1a11a12a1nb12a21a22a2nb2mam1am2amnbm单位活动对Z的贡献c1c2cn11;.线性规划的数学模型：线性规划的数学模型：其中，目标函数可以是min的形式，函数约束中“”可以是“=”或“”，变量的非负性限制也可以取消。 0, 0, 0. .max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz12;.说明： (1)决策变量：x1，x2，xn 。 一组决策变量表示为问题的一个方案； (2)目标函数：max(min)z z为决策变量的线性函数; (3)约束条件 一

7、组线性不等式。cj为价值系数, bi为资源， aij为技术系数(i=1,m;j=1,n).13;.线性规划的标准型线性规划的标准型标准型标准型（z极大值，等式，b非负，x非负） njxmibxaxczjinjjijnjjj,10,1 max简记11 ，：0,0,0.max21221122222121112121112211nmnmnmmnnnnnnxxxbxaxaxabxaxaxabxaxaxatsxcxcxcz14;.用向量表示用向量表示 njxbxptscxzjnjjj, 1, 0 .max1TmjTmjjjjnTnbbbbxaaapccccxxxx) , , , ( :) , , ,(

8、), , , ( ) , , , (:21212121 的系数列向量其中15;. 用矩阵描述为：用矩阵描述为： 其中: X = (x1,x2,xn)T C = (c1,c2,cn) b = (b1,b2,bm)T 为系数矩阵 212222111211 mnmmnnaaaaaaaaaA njxbAxtscxzj, 1, 0 .max16;.标准型的化法标准型的化法 (1)minmax。 令z = -z即可。 (2)不等式。对于“”情况，在“”左边加上一个松弛变量（非负），变为等式，如x14,可令x1+x3=4,则x30； 对于“”情况：在“”左边减去一个剩余变量（非负），变为等式，如0.6x1+

9、0.4x26,可令0.6x1+0.4x2+x4=6 。 注意注意：松弛变量、剩余变量在目标函数中的价值系数为0。 (3)无约束变量。令xj = xj - xj”，xj,xj” 0，代入即可。 (4)变量xj0。令xj=- xj即可。 17;. 将下述问题化为标准型 min z = -x1+2x2-3x3 x1+ x2+ x3 7 x1- x2+ x3 2 -3x1+ x2+2x3 = 5 x1,x2 0，x3无约束 解：令x3 = x3-x3”，x3,x3” 0； 式加上一个松弛变量x4；式减去一个剩余变量x5； 令z = -z、； max z = x1- 2x2 + 3(x3 - x3”)

10、+ 0 x4 + 0 x5 x1 + x2 + (x3 - x3”) + x4 = 7 x1 - x2 + (x3 - x3”) - x5 = 2 -3x1 + x2 + 2(x3 - x3”) = 5 x1,x2,x3,x3”,x4,x5 0 18;. 图解法图解法比较简单、直观，适用于只有两个变量的线性规划问题。单纯形法单纯形法适用于两个或两个以上变量的线性规划问题，比较复杂的问题需要借助计算机软件求解。 19;.线性规划解的概念线性规划解的概念 设线性规划为 maxmax z z = cx cx Ax Ax = b b x x 0 0 A A为为m m n n矩阵矩阵, , n n m,

11、 Rankm, Rank A A = m (Am (A为行满秩矩阵）为行满秩矩阵） 1 1、可行解：满足条件、可行解：满足条件、的的X X； 2 2、最优解：满足、最优解：满足条件条件的可行解；的可行解； 3 3、基：取、基：取B B为为A A中的中的m m m m子矩阵，子矩阵，RankRank B B = m m，则称则称B B为线性规划问题的一个基。为线性规划问题的一个基。 取取B B = (p(p1 1,p,p2 2, ,p,pm m) p) pj j = (a(a1j1j,a,a2j2j, ,a,amjmj) )T T 则称则称x x1 1,x,x2 2, ,x,xm m为基变量，其

12、它为非基变量。为基变量，其它为非基变量。20;.4 4、基解：取、基解：取B B = (p(p1 1,p,p2 2, ,p,pm m) ) a a1111, ,a,a1m1m x x1 1 a a1m+11m+1, ,a,a1n1n x xm+1m+1 b b1 1 + + = a am1m1, ,a,ammmm x xm m a amm+1mm+1, ,a,amnmn x xn n b bm m 基基 基变量基变量 非基非基 非基变量非基变量 令令 x xm+1m+1 = = x xn n = 0 (0 (非基变量为非基变量为0)0) 则则 BXBXB B = b b )!( !mnmnCm

13、n基解个数TmnmTmBxxxXxxxbBX)0 , 0,(),(m )0()0(2)0(1)0()0(2)0(11 个个基解：21;.5、基可行解 满足式要求的基解。 如右图所示，各边交点O,QO,Q1 1,Q,Q2 2,Q,Q3 3,Q,Q4 4均为基可行解；而其延长线的交点Q5为基解，但不是基可行解。O(0,0)O(0,0)Q Q1 1(4,0)(4,0)Q Q2 2(4,2)(4,2)Q Q4 4(0,3)(0,3)Q Q3 3(2,3)(2,3)Q Q5 5(4,3)(4,3)6、可行基 基可行解对应的B为可行基。可行解可行解基可行解基可行解非可行解非可行解基解基解22;. 图解法图

14、解法 用图解法求用图解法求例例1 1。 max max z z = 2x2x1 1 + + 3x3x2 2 1x 1x1 1 + + 2x2x2 2 8 8 4x 4x1 1 16 16 4x4x2 2 12 12 x x1 1，x x2 2 0 0 解： (1)建立x x1 1 - - x x2 2坐标；x2x1 (2)约束条件的几何表示； Q1Q2Q3Q4 (3)目标函数的几何表示； * z z = 2x2x1 1 + + 3x3x2 2 o43zxx31321223;. 首先取z = 0，然后，使z逐渐增大，直至找到最优解所对应的点。* 可见，在Q2点z取到最大值。 因此， Q2点所对应

15、的解为最优解。 Q2点坐标为(4，2)。 即: x1 = 4，x2 = 2 由此求得最优解：x x1 1* * = 4 x4 x2 2* * = 2 2 最大值：maxmax z z = z z* * = 2x2x1 1 + + 3x3x2 2 = 1414x2x1Q1Q2(4,2)Q3Q4*4324;.讨论： (1)唯一最优解 maxmax z z = z z* *时，解唯一，如上例。 (2)无穷多最优解 对例1，若目标函数 z z = 2x2x1 1 + + 4x4x2 2，此时表示 目标函数的直线与表示 条件的直线平行， 最优点在线段Q3Q2上。 即存在无穷多最优解。x2x1Q1 Q2(

16、4,2)Q3(2,3)Q4o43*25;. (3)无界解 max z = 2x1 + 3x2 4x1 16 x1，x2 0 则x2 ，z 。 即存在无界解。 在实际问题中，可能 是缺少约束条件。o2241x2x26;.(4)无可行解 max z = 2x1 + 3x2 2x1 + 4x2 8 x1 + x2 1 x1，x2 0 无公共部分，无可行域。 即无可行解。 在实际问题中，可能是关系错。1124x1x227;. 单纯形法单纯形法 基本思路：基本思路：从可行域的一个顶点到另一个顶点迭代求最优解。 初始基可行解的确定初始基可行解的确定 1、松弛基（松弛变量对应的B） max z = x1 +

17、 3x2 x1 + 2x2 3 2x1 + 3x2 4 x1,x2 0max z = x1 + 3x2 + 0 x3 + 0 x4 x1 + 2x2 + x3 = 3 2x1 + 3x2 + x4 = 4 x1,x2,x3,x4 0 化标准型 取x3、x4为基变量,令非基变量x1= x2=0 初始基可行解：X(0) = (0 0 3 4)T B , 1 0 3 20 1 2 1 434321ppppppA则系数矩阵28;. 2、观察法 max z = x1 + 3x2 + 2x3 + x4 x1 + 2x2 + 3x3 = 3 3x2 + x3 + x4 = 4 x1,x2,x3,x4 0 选

18、 XB = (x1 x4)T 令x2 = x3 = 0 则 初始基可行解：X(0) = (3 0 0 4)T B , 1 1 3 00 3 2 1 :414321ppppppA则解29;.最优性的检验与解的判别最优性的检验与解的判别 mnjxmibxxaxcxczjnjiinjijmiininnjjj, 1 0, 1 max 111对于代入目标函数为非基变量可行为基变量设 , 1, , 1, 1 njjijiinjinxabxnjxmix30;.则njjjnjjjjnjmijijinjmiiinnjminjjijiinjjxZxzcZxaccbcxabcxcz1010111111 )( )(

19、)(miijinjjjjmiiinaczzcbcZ110 , , 其中31;.解的判别：1. 若 ，则此时的基可行解为最优解；2. 若存在某个非基变量 的检验数 ，且 ，则该线性规划问题具有无界解（或称无最优解）；3. 若所有 ，又，对于某个非基变量 有 ，则该线性规划问题具有无穷多最优解。. .的检验数为称jjxkx0knjj, 1, 0 0kp0j0kkx32;. 为主元出基行对应的变量则若、出基变量 0minmin02lkllklikikiiiiikikiiaxlabaabaab为入基变量。则，若、入基变量kkjjx 0max1 基变换基变换33;. 旋转运算（消元运算）旋转运算（消元运算） a1k 0 al-1k 0 pk = （alk） （1） al+1k 0 amk 0 得到基可行解，重复上面的步骤， 求出最优解。34;. 单纯形表单纯形表 mn, 2 , 1j0 xbxxaxczmaxjiinn1jjijmn1jjj，设35;. 建立单纯形表cBxBbc1cncn+1cn+mx1xnxn+1xn+mcn+1xn+1b1a11a1n101cn+mxn+mbmam1amn01m -z -z01 n 00j 用单纯形法求解 max z = x1 + 3x2 x1 + 2x2 8 4x1 16 4x2 12 x1,x2 036;.