管理运筹学线性规划ppt课件.ppt

《管理运筹学线性规划ppt课件.ppt》由会员分享，可在线阅读，更多相关《管理运筹学线性规划ppt课件.ppt（70页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一讲第一讲 线性规划线性规划1经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一章第一章 线性规划的数学模型线性规划的数学模型 线性规划线性规划 Linear Programming LP规划论中的静态规划规划论中的静态规划解决有限资源的最佳分配问题解决有限资源的最佳分配问题求解方法：求解方法：图解法图解法单纯形解法单纯形解法 2经济

2、管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一章第一章 线性规划的数学模型线性规划的数学模型3经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 线性规划一般模型线性规划一般模型一、线性规划问题的三个要素一、线性规划问题的三个要素 决策变量决策变量决策问题待定的量值称为决策变量。决策问题待定的量值称为决策变量。决策变量的取值要求非负。决策变量的取值要求非负。约束条件约束条件

3、任任何何问问题题都都是是限限定定在在一一定定的的条条件件下下求求解解，把把各各种种限限制制条条件件表表示示为一组等式或不等式，称之为约束条件。为一组等式或不等式，称之为约束条件。约束条件是决策方案可行的保障。约束条件是决策方案可行的保障。LP的约束条件，都是决策变量的线性函数。的约束条件，都是决策变量的线性函数。目标函数目标函数衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。衡量决策方案优劣的准则，如时间最省、利润最大、成本最低。目标函数是决策变量的线性函数。目标函数是决策变量的线性函数。有的目标要实现极大，有的则要求极小。有的目标要实现极大，有的则要求极小。4经济管理学院经济管理学院

4、经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 线性规划一般模型线性规划一般模型例例例例1.1.生产计划问题生产计划问题生产计划问题生产计划问题 某某厂厂生生产产、两两种种产产品品，已已知知生生产产单单位位产产品品所所需需的的设设备备台台时时及及A、B两两种种原原材材料料的的消消耗耗，以以及及资资源源的的限限制制，相相关关数据如表所示：数据如表所示：问如何安排问如何安排、两产品的产量，使利润为最大。两产品的产量，使利润为最大。二、线性规划模型的构建二、线性规划模型的构建 产品资源工时单耗 资源限制设

5、备原料A原料B 1 1 2 1 0 1300台时400千克250千克单位产品获利 50元 100元5经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 线性规划一般模型线性规划一般模型(1)决决策策变变量量。要要决决策策的的问问题题是是、两两种种产产品品的的产产量量，因因此此有有两两个个决决策策变变量量：设设x1为为产产品品产产量量，x2为为产品产量。产品产量。(2)约约束束条条件件。生生产产这这两两种种产产品品受受到到现现有有生生产产能能力力的的制约，原料用量也受限制。制约，原

6、料用量也受限制。设备的生产能力总量为设备的生产能力总量为300台时，则约束条件表述为台时，则约束条件表述为 x1+x2 300A、B两种原材料两种原材料约束条件为约束条件为2x1+x2 400 x2 250建立模型建立模型6经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 线性规划一般模型线性规划一般模型(3)(3)目标函数目标函数目标函数目标函数。目标是利润最大化，用目标是利润最大化，用Z表示利润，则表示利润，则 maxZ=50 x1+100 x2(4)(4)非非非非负负负负

7、约约约约束束束束。、产产品品的的产产量量不不应应是是负负数数，否否则则没没有有实实际意义，这个要求表述为际意义，这个要求表述为 x1 0，x2 0综上所述，该问题的数学模型表示为综上所述，该问题的数学模型表示为 maxZ=50 x1+100 x2 x1+x2 300 2x1+x2 400 x2 250 x1 0,x2 07经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 线性规划一般模型线性规划一般模型 某某名名牌牌饮饮料料在在国国内内有有三三个个生生产产厂厂，分分布布在在城城

8、市市A1、A2、A3,其其一一级级承承销销商商有有4个个，分分布布在在城城市市B1、B2、B3、B4，已已知知各各厂厂的的产产量量、各各承承销销商商的的销销售售量量及及从从Ai到到Bj的的每每吨吨饮饮料料运运费费为为Cij，为为发发挥挥集集团团优优势势，公公司司要要统统一一筹划运销问题，求运费最小的调运方案。筹划运销问题，求运费最小的调运方案。例例例例2.2.运输问题运输问题运输问题运输问题 销地产地B1 B2 B3 B4产量A1A2A3 6 3 2 5 7 5 8 4 3 2 9 7523销量 2 3 1 48经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增

9、加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 线性规划一般模型线性规划一般模型(1)(1)决策变量决策变量决策变量决策变量。设从设从Ai到到Bj的运输量为的运输量为xij，(2)(2)目标函数目标函数目标函数目标函数。运费最小的目标函数为运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)(3)约束条件约束条件约束条件约束条件。产量之和等于销量之和产量之和等于销量之和,故要满足：故要满足：供应平衡条件供应平衡条件x11+x12+x13+x14=5x21+

10、x22+x23+x24=2x31+x32+x33+x34=3销售平衡条件销售平衡条件x11+x21+x31=2x12+x22+x32=3x13+x23+x33=1x14+x24+x34=4非负性约束非负性约束 xij0 (i=1,2,3；j=1,2,3,4)9经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 线性规划一般模型线性规划一般模型用一组非负决策变量表示一个决策问题，用一组非负决策变量表示一个决策问题，存在一定的等式或不等式的线性约束条件，存在一定的等式或不等式的线性约

11、束条件，有一个希望达到的目标，可表示成决策变量的线性有一个希望达到的目标，可表示成决策变量的线性函数。可能是最大化，也可能是最小化。函数。可能是最大化，也可能是最小化。线性规划一般模型的代数式线性规划一般模型的代数式 为：为：三、线性规划的一般模型三、线性规划的一般模型 max(min)Z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn (,)b1a21x1+a22x2+a2nxn (,)b2 am1x1+am2x2+amnxn(,)bmx1,x2,xn()010经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金

12、额为消费者购买商品的价款或接受服务的费用第二节第二节 线性规划的图解法线性规划的图解法 图解法即是用图示的方法来求解线性规划问题。图解法即是用图示的方法来求解线性规划问题。一个二维的线性规划问题，可以在平面图上求解，一个二维的线性规划问题，可以在平面图上求解，三维的线性规划则要在立体图上求解，这就比较麻三维的线性规划则要在立体图上求解，这就比较麻烦，而维数再高以后就不能图示了。烦，而维数再高以后就不能图示了。一、图解法的基本步骤一、图解法的基本步骤11经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受

13、服务的费用第二节第二节 线性规划的图解法线性规划的图解法1.可行域的确定可行域的确定 例例1的数学模型为的数学模型为 maxZ=50 x1+100 x2 x1+x2 300 2x1+x2 400 x2 250 x1 0,x2 0 x2=2502x1+x2=400五边形五边形ABCDO内内(含边界含边界)的任意一点的任意一点(x1，x2)都是满足所有都是满足所有约束条件的一个解，称之可行解约束条件的一个解，称之可行解。满足所有约束条件的解的集合，称之为可行域。即所有约束满足所有约束条件的解的集合，称之为可行域。即所有约束条件共同围城的区域。条件共同围城的区域。x1+x2=300ABCDOz=0=

14、50 x1+100 x2 Z=27500=50 x1+100 x212经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第二节第二节 线性规划的图解法线性规划的图解法2.最优解的确定最优解的确定目标函数目标函数 Z=50 x1+100 x2 代表以代表以Z为参数的一族平行线。为参数的一族平行线。等值线：位于同一直线上的点的目标函数值相同。等值线：位于同一直线上的点的目标函数值相同。最优解：可行解中使目标函数最优最优解：可行解中使目标函数最优(极大或极小极大或极小)的解。的解。最优值最优值:取

15、最优解时对应的目标函数值取最优解时对应的目标函数值13经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第二节第二节 线性规划的图解法线性规划的图解法由由线线性性不不等等式式组组成成的的可可行行域域是是凸凸集集(凸凸集集的的定定义义是是：集合内部任意两点连线上的点都属于这个集合集合内部任意两点连线上的点都属于这个集合)。可可行行域域有有有有限限个个顶顶点点。设设规规划划问问题题有有n个个变变量量，m个个约束，则顶点的个数不多于约束，则顶点的个数不多于Cnm个。个。目目标标函函数数最最优优值值

16、一一定定在在可可行行域域的的边边界界达达到到，而而不不可可能在其内部。能在其内部。二、几点说明二、几点说明14经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第二节第二节 线性规划的图解法线性规划的图解法三三、解的可能性、解的可能性x1=82x2=123x1+4 x2=36例例 maxZ=3x1+4 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0Z=24Z=36Z=12唯一最优解：只有一个最优点。唯一最优解：只有一个最优点。多多重重最最优优解解：无无穷穷多多个个最

17、最优优解解。若若在在两两个个顶顶点点同同时时得到最优解，则它们连线上的每一点都是最优解。得到最优解，则它们连线上的每一点都是最优解。15经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第二节第二节 线性规划的图解法线性规划的图解法无无界界解解：线线性性规规划划问问题题的的可可行行域域无无界界，使使目目标标函函数数无限增大而无界。（缺乏必要的约束条件）无限增大而无界。（缺乏必要的约束条件）三三、解的可能性（续）、解的可能性（续）例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-

18、3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=3Z=6Z=1216经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第二节第二节 线性规划的图解法线性规划的图解法无可行解：若约束条件相互矛盾，则可行域为空集无可行解：若约束条件相互矛盾，则可行域为空集三三、解的可能性（续）、解的可能性（续）例如例如 maxZ=3x1+2 x2 -2x1+x2 2 x1-3 x2 3 x1 0,x2 0-2x1+x2=2x1-3 x2=317经济管理学院经济管理学院经营者提供商品或者服务有欺

19、诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第三节第三节 线性规划的标准型线性规划的标准型线性规划问题的数学模型有各种不同的形式，如线性规划问题的数学模型有各种不同的形式，如目标函数有极大化和极小化；目标函数有极大化和极小化；约束条件有约束条件有“”、“”和和“”三种情况；三种情况；决策变量一般有非负性要求，有的则没有。决策变量一般有非负性要求，有的则没有。为为了了求求解解方方便便，特特规规定定一一种种线线性性规规划划的的标标准准形形式式，非标准型可以转化为标准型。标准形式为：非标准型可以转化为标准型。标准形式为：目标函数极大化，目标

20、函数极大化，约束条件为等式，约束条件为等式，右端常数项右端常数项bi0，决策变量非负。决策变量非负。一一、标准型、标准型18经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第三节第三节 线性规划的标准型线性规划的标准型1.代数式代数式二、标准型的表达方式二、标准型的表达方式 有代数式、矩阵式：有代数式、矩阵式：maxZ=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn b1 a21x1+a22x2+a2nxn b2 am1x1+am2x2+amnxnbm x1,x2,xn

21、0maxZ=cjxj aijxjbi (i=1,2,m)xj0 (j=1,2,n)简记19经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第三节第三节 线性规划的标准型线性规划的标准型2.矩阵式矩阵式 20经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第三节第三节 线性规划的标准型线性规划的标准型 目标函数极小化问题目标函数极小化问题目标函数极小化问题目标函数极小化问题 minZ=C

22、TX，只需将等式两端乘以，只需将等式两端乘以-1 即变为极大化问题。即变为极大化问题。因为因为minZ=-max(-Z)=CTX，令，令Z=-Z，则，则maxZ=-CX 右端常数项非正右端常数项非正右端常数项非正右端常数项非正 两端同乘以两端同乘以-1 约束条件为不等式约束条件为不等式约束条件为不等式约束条件为不等式当约束方程为当约束方程为“”时，左端加入一个非负的松弛变量，就把不等式时，左端加入一个非负的松弛变量，就把不等式变成了等式；变成了等式；当约束条件为当约束条件为“”时，不等式左端减去一个非负的剩余变量时，不等式左端减去一个非负的剩余变量(也可称也可称松弛变量松弛变量)即可。即可。决

23、策变量决策变量决策变量决策变量x xk k没有非负性要求没有非负性要求没有非负性要求没有非负性要求 令令xk=xk-x k，xk=xk，x k 0，用，用xk、x k 取代模型中取代模型中xk三、非标准型向标准型转化三、非标准型向标准型转化 21经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第三节第三节 线性规划的标准型线性规划的标准型例例1 的标准型的标准型 例例1 maxZ=3x1+5 x2 x1 8 2x2 12 3x1+4 x2 36 x1 0,x2 0 x1 +x3 =8 2x

24、2 +x4 =12 3x1+4 x2 +x5=36 x1,x2,x3,x4,x5 0 maxZ=3x1+5 x2+0 x3+0 x4+0 x5 22经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用 minZ=x1+2 x2+3 x3 x1+2 x2+x35 2x1+3 x2+x36 -x1 -x2 -x3-2 x1 0,x30 第三节第三节 线性规划的标准型线性规划的标准型例例 minZ=x1+2 x2-3 x3 x1+2 x2-x3 5 2x1+3 x2-x3 6 -x1 -x2 +x3

25、 -2 x1 0,x3 0标准化标准化123经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第三节第三节 线性规划的标准型线性规划的标准型标准化标准化2 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36 -x1 -(x2-x 2)-x3-2 x1,x2,x 2,x3 0 标准化标准化3 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x35 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+

26、x3 2 x1,x2,x 2,x3 024经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第三节第三节 线性规划的标准型线性规划的标准型标准化标准化4 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4=5 2x1+3(x2-x 2)+x36 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4 0标准化标准化5 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5=6

27、 x1+(x2-x 2)+x3 2 x1,x2,x 2,x3,x4,x5 025经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第三节第三节 线性规划的标准型线性规划的标准型标准化标准化6 minZ=x1+2(x2-x 2)+3 x3 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5 =6 x1+(x2-x 2)-x3 +x6=2 x1,x2,x 2,x3,x4,x5,x6 0标准化标准化7 maxZ=-x1-2(x2-x 2)-3x3+0 x4+0 x

28、5+0 x6 x1+2(x2-x 2)+x3+x4 =5 2x1+3(x2-x 2)+x3 -x5 =6 x1+(x2-x 2)-x3 +x6 =2 x1,x2,x 2,x3,x4,x5,x6 0 26经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第四节第四节 线性规划解的概念线性规划解的概念可行解：可行解：满足约束条件满足约束条件AX=b,X0的解。的解。最优解：最优解：使目标函数最优的可行解，称为最优解。使目标函数最优的可行解，称为最优解。基基mn，且，且m个方程线性无关，即矩阵个方

29、程线性无关，即矩阵A的秩为的秩为m；根；根据线性代数定理可知，据线性代数定理可知，nm，则方程组有多个解，这，则方程组有多个解，这也正是线性规划寻求最优解的余地所在。也正是线性规划寻求最优解的余地所在。一、线性规划解的概念一、线性规划解的概念 27经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第四节第四节 线性规划解的概念线性规划解的概念线性方程组的增广矩阵线性方程组的增广矩阵例例1 的标准型的标准型 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1 +x2 +x3

30、 =300 2 x1 +2x2 +x4 =400 x2 +x5=250 x1,x2,x3,x4,x5 0单位矩阵单位矩阵28经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第四节第四节 线性规划解的概念线性规划解的概念基矩阵：基矩阵：系数矩阵系数矩阵A中任意中任意m列所组成的列所组成的m阶非奇异子矩阵，称阶非奇异子矩阵，称为该线性规划问题的一个基矩阵。为该线性规划问题的一个基矩阵。或称为一个基，用或称为一个基，用B表示。表示。称基矩阵的列为基向量，用称基矩阵的列为基向量，用Pj表示表示(j

31、=1,2,m)。不在。不在B中的向量称为非基向量中的向量称为非基向量29经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第四节第四节 线性规划解的概念线性规划解的概念基变量：基变量：与基向量与基向量Pj相对应的相对应的m个变量个变量xj称为基变量，称为基变量，其余的其余的m-n个变量为非基变量。个变量为非基变量。基解：基解：令所有非基变量等于零，对令所有非基变量等于零，对m个基变量所求的解，个基变量所求的解，对应一个特定的基矩阵能求得一组唯一解，这个对应于基的解对应一个特定的基矩阵能求得一

32、组唯一解，这个对应于基的解称为基解。称为基解。结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。结合图解来看，基解是各约束方程及坐标轴之间交点的坐标。基变量是基变量是x3,x4,x5非基变量是非基变量是x1,x2令非基变量令非基变量x1=x2=0，得到一个基解，得到一个基解 x3=300，x4=400，x5=25030经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第四节第四节 线性规划解的概念线性规划解的概念基可行解：满足非负性约束的基解称为基可行解。基可行解：满足非负性约束的基解称

33、为基可行解。可行基：对应于基可行解的基，称为可行基。可行基：对应于基可行解的基，称为可行基。最优基：最优解对应的基矩阵，称为最优基。最优基：最优解对应的基矩阵，称为最优基。非可行解可行解基解31经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第四节第四节 线性规划解的概念线性规划解的概念 定理定理定理定理1 1.若线性规划问题存在可行域，则其可行域一定是凸集。若线性规划问题存在可行域，则其可行域一定是凸集。定理定理定理定理2 2.线性规划问题的基可行解对应可行域的顶点。线性规划问题的基可行

34、解对应可行域的顶点。定定定定理理理理3 3.若若可可行行域域有有界界，线线性性规规划划的的目目标标函函数数一一定定可可以以在在可可行行域域的顶点上达到最优。的顶点上达到最优。二、线性规划的基本定理二、线性规划的基本定理 线线性性规规划划问问题题可可以以有有无无数数个个可可行行解解，最最优优解解只只可可能能在在顶顶点点上上达达到到，而而有有限限个个顶顶点点对对应应的的是是基基可可行行解解，故故只只要要在在有有限限个个基基可行解中寻求最优解即可。可行解中寻求最优解即可。从从一一个个顶顶点点出出发发找找到到一一个个可可行行基基，得得到到一一组组基基可可行行解解，拿拿目目标函数做尺度衡量一下看是否最优

35、。标函数做尺度衡量一下看是否最优。如如若若不不是是，则则向向邻邻近近的的顶顶点点转转移移，换换一一个个基基再再行行求求解解、检检验验，如此迭代循环目标值逐步改善，直至求得最优解。如此迭代循环目标值逐步改善，直至求得最优解。三、线性规划的解题思路三、线性规划的解题思路 32经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第二章第二章 线性规划单纯形法线性规划单纯形法 单纯形法单纯形法(Simplex Method)是美国人丹捷格是美国人丹捷格(G.Dantzig)1947年创建的年创建的这种

36、方法简捷、规范，是举世公认的解决线性这种方法简捷、规范，是举世公认的解决线性规划问题行之有效的方法。规划问题行之有效的方法。单纯形法的表现形式：单纯形法的表现形式：代数法代数法表格法表格法矩阵法矩阵法33经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第二章第二章 线性规划单纯形法线性规划单纯形法34经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理

37、一、代数解法一、代数解法 非奇异子阵，做为一个基基变量基变量x3,x4,x5非基变量非基变量x1,x2 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1 +x2 +x3 =300 2 x1 +x2 +x4 =400 x2 +x5=250 x1,x2,x3,x4,x5 035经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理将基变量用非基变量线性表示，即将基变量用非基变量线性表示，即x3=300-x1 -x2 x4=400-2x1 -

38、x2 x5=250-x2 令非基变量令非基变量x1=0，x2=0，找到一个初始基可行解，找到一个初始基可行解：x1=0，x2=0，x3=300，x4=400，x5=250即即X0=(0,0,300,400,250)T一个可行解就是一个生产方案，在上述方案中两种产品都不一个可行解就是一个生产方案，在上述方案中两种产品都不生产，利润生产，利润Z=0。1.求初始基可行解求初始基可行解 36经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理确定入基变量确定入基变

39、量 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1 +x2 +x3 =300 2 x1 +x2 +x4 =400 x2 +x5=250从目标函数从目标函数maxZ=50 x1+100 x2+0 x3+0 x4+0 x5可知：可知：非非基基变变量量x1和和x2的的系系数数均均为为正正数数，生生产产哪哪种种产产品品都都会会增加利润。增加利润。因因为为x2的的系系数数大大于于x1的的系系数数，即即生生产产单单位位乙乙产产品品比比甲甲产产品品利利润润更更高高一一些些，故故应应优优先先多多生生产产乙乙产产品品，即即优优先先把把x2作为入基变量。作为入基变量。2.第一次迭代第一次迭

40、代 37经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理确定离基变量确定离基变量基变量用非基变量线性表示基变量用非基变量线性表示x3=300-x1 -x2 x4=400-2x1 -x2 x5=250-x2保持原非基变量保持原非基变量x1=0，x2变成基变量时应保证变成基变量时应保证 x3,x4,x5非负，即有非负，即有2.第一次迭代（续）第一次迭代（续）x3 =300-x2 0 x4=400-x2 0 x5=250-x2 0 x2 300 x2 400

41、 x2 250 则离基变量为则离基变量为x538经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理2.第一次迭代（续）第一次迭代（续）主元主元进基变量所在列为主列，离基变量所在行为主行进基变量所在列为主列，离基变量所在行为主行 maxZ=50 x1+100 x2+0 x3+0 x4+0 x5 x1 +x2 +x3 =300 2 x1 +x2 +x4 =400 x2 +x5=250 39经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消

42、费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理基变换基变换进行初等变换，变主元为进行初等变换，变主元为1，主列为单位列向量。，主列为单位列向量。2.第一次迭代（续）第一次迭代（续）-Z+50 x1+100 x2+0 x3+0 x4+0 x5=0 x1 +x2 +x3 =300 2 x1 +x2 +x4 =400 x2 +x5=250-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000=0 x1 +x3 -x5 =50 2 x1 +x4 -x5 =150 x2 +x5 =250此时此时x2，x3，x4

43、为基变量为基变量初等行变换初等行变换40经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理2.第一次迭代（续）第一次迭代（续）将基变量用非基变量线性表示，即将基变量用非基变量线性表示，即x2=250-x5 x3=50 x1+x5x4=150-2x1+x5令非基变量令非基变量x1=0，x5=0，找到另一个基可行解，找到另一个基可行解 x1=0，x2=250，x3=50，x4=150，x5=0即X1=(0,250,50,150,0)T目标函数目标函数Z=25

44、00041经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理确定入基变量确定入基变量3.第二次迭代第二次迭代 目标函数，目标函数，Z=50 x1+0 x2+0 x3+0 x4-100 x5+25000 非基非基变量变量x1的系数的系数 1=50（检验数）为正数，（检验数）为正数，确定确定x1为入基变量。为入基变量。-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000=0 x1 +x3 -x5 =50 2 x1 +x4 -x5 =150

45、 x2 +x5 =250第一次迭代结果第一次迭代结果42经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理确定出基变量确定出基变量3.第二次迭代第二次迭代（续）（续）x3=50+x5-x1 0 x2=150-2x1+x5 0 x4=250 x5 0 x1 50 x1 75基变量用非基变量线性表示基变量用非基变量线性表示 x1=50+x5-x1 x2=150-2x1+x5 x4=250 x5保持原非基变量保持原非基变量x5=0，x1变成基变量时应保证变成基

46、变量时应保证 x2,x3,x5非负，即非负，即 对应的对应的x3定为出基变量定为出基变量43经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理基变换基变换变主元为变主元为1，主列为单位列向量。，主列为单位列向量。3.第二次迭代（续）第二次迭代（续）-Z+50 x1+0 x2+0 x3+0 x4-100 x5+25000=0 x1 +x3 -x5 =50 2 x1 +x4 -x5 =150 x2 +x5 =250-Z+0 x1 +0 x2-50 x3+0

47、x4-50 x5+27500 =0 x1 +x3 -x5 =50 -2x3 +x4 +x5 =50 x2 +x5 =250基变量为基变量为x1 x2 ，x4 44经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理3.第二次迭代（续）第二次迭代（续）将基变量用非基变量线性表示，即将基变量用非基变量线性表示，即x1 =50 x3+x5x2=250-x5x4=50+2x3-x5 令非基变量令非基变量x3=0，x5=0，又找到一个基可行解，又找到一个基可行解 目

48、标函数目标函数-Z+0 x1 +0 x2-50 x3+0 x4-50 x5+27500 =0 x1=50，x2=250，x3=0，x4=50，x5=0即即 X2=(50,250,0,50,0)T Z=27500 检验数检验数j非正，得最优解非正，得最优解X*=(4,6,4,0,0)T，Z*=4245经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第一节第一节 单纯形法原理单纯形法原理二、单纯形法的几何意义二、单纯形法的几何意义X0=(0,0,300,400,250)TX1=(0,250，5

49、0，150,0)TX1=(50,250,0,50,0)Tx2=2502x1+x2=400 x1+x2=300ABCDO46经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第二节第二节 表格单纯形法表格单纯形法 表格单纯形法，是对上节讨论的方法步骤进行具体表格单纯形法，是对上节讨论的方法步骤进行具体化、规范化、表格化的结果。化、规范化、表格化的结果。一、单纯形法表一、单纯形法表CjC1C2CjCn比比值值CBXBbx1x2xjxnCB1xB1b1a11a12a1ja1n 1CB2xB2b2a

50、21a22a2ja2n 2CBnxBnbmam1am2amjamn m检验数检验数 j-Z 1 2 j n47经济管理学院经济管理学院经营者提供商品或者服务有欺诈行为的，应当按照消费者的要求增加赔偿其受到的损失，增加赔偿的金额为消费者购买商品的价款或接受服务的费用第二节第二节 表格单纯形法表格单纯形法将线性规划问题化成标准型。将线性规划问题化成标准型。找出或构造一个找出或构造一个m阶单位矩阵作为初始可行基，建立初始单纯形表。阶单位矩阵作为初始可行基，建立初始单纯形表。计计算算各各非非基基变变量量xj的的检检验验数数 j=Cj-CBPj，若若所所有有 j0，则则问问题题已已得得到到最优解，停止计