运筹学-线性规划

第二章线性规划(LinearProgramming)2.1LP的数学模型2.2图解法2.3单纯形法2.4单纯形法的进一步讨论－人工变量法2.5LP模型的应用本章主要内容：Page22.1线性规划问题的数学模型1.规划问题生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性规划通常解决下列两类问题：（1）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、原标材料、人工、时间等）去完成确定的任务或目标（2）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大.）Page32.1线性规划问题的数学模型例2.1某工厂在计划期内要安排Ⅰ、Ⅱ两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位Ⅰ、Ⅱ产品才能使工厂获利最多？ⅠⅡ资源限制设备11300台时原料A21400千克原料B01250千克单位产品获利50元100元Page42.1线性规划问题的数学模型解：设生产产品I和产品Ⅱ的产量分别为x1和x2。则有如下模型：目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1,x2≥0Page52.1线性规划问题的数学模型例2.2某企业计划生产甲、乙两种产品。这些产品分别要在A、B、C、D、四种不同的设备上加工。按工艺资料规定，单件产品在不同设备上加工所需要的台时如下表所示，企业决策者应如何安排生产计划，使企业总的利润最大？设备产品ABCD利润（元）甲21402乙22043有效台时1281612Page62.1线性规划问题的数学模型解：设x1、x2分别为甲、乙两种产品的产量，则数学模型为：maxZ=2x1+3x2x1≥0,x2≥0s.t.2x1+2x2≤12x1+2x2≤84x1≤164x2≤12Page7例2.3假定一个成年人每天需要从食物中获取3000卡热量，55克蛋白质和800毫克钙。如果市场上只有四种食品可供选择，它们每千克所含热量和营养成分以及市场价格如下表所示。问如何选择才能满足营养的前提下使购买食品的费用最小？序号食品名称热量（卡）蛋白质（克）钙（毫克）价格（元）1猪肉100050400102鸡蛋8006020063大米9002030034白菜200105002请同学们自己列出模型？2.1线性规划问题的数学模型Page82.1线性规划问题的数学模型2.线性规划的数学模型由三个要素构成决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints其特征是：（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。怎样辨别一个模型是线性规划模型？Page92.1线性规划问题的数学模型3.线性规划建模过程（1）理解要解决的问题，了解解题的目标和条件；（2）定义决策变量（x1，x2，…，xn），每一组值表示一个方案；（3）用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；（4）用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件Page102.1线性规划问题的数学模型00)()((min)max12211112121112211nmnmnmmnnnnxxbxaxaxabxaxaxaxcxcxcz目标函数：约束条件：4.线性规划数学模型的一般形式)21(j0)21(i)(Z(min)max11nxmbxaxcjnjijijnjjj简写为：Page112.1线性规划问题的数学模型其中，ci——称为价值系数aij——称为技术系数（或消耗系数）bi——称为资源系数Page122.1线性规划问题的数学模型向量形式：)(21ncccCnxxX1mjjjaaP1mbbB10)((min)maxXBxpCXzjj其中：Page132.1线性规划问题的数学模型矩阵形式：mnmnaaaaA11110)((min)maxXBAXCXZ其中：)(21ncccCnxxX1mbbB1Page142.1线性规划问题的数学模型5.线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj,,2,1,,2,1,0.max11特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。Page152.1线性规划问题的数学模型（2）如何化标准形式目标函数的转换如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。jjxczmin也就是：令，可得到上式。zzjjxczzmax即若存在取值无约束的变量，可令其中：jxjjjxxx0,jjxx变量的变换Page162.1线性规划问题的数学模型约束方程的转换：由不等式转换为等式。ijijbxa0iniinjijxbxxa称为松弛变量ijijbxa0iniinjijxbxxa称为剩余变量变量的变换可令，显然0jxjjxx0jxPage172.1线性规划问题的数学模型例2.4将下列线性规划问题化为标准形式,0,523247532min321321321321321无约束xxxxxxxxxxxxxxxZ用替换，且解:（１）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以33xx3x0,33xxPage182.1线性规划问题的数学模型(2)第一个约束条件是“≤”号，在“≤”左端加入松驰变量x4，x4≥0,化为等式；(3)第二个约束条件是“≥”号，在“≥”左端减去剩余变量x5，x5≥0；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z′=-z,得到maxz′=-z，即当z达到最小值时z′达到最大值，反之亦然;Page192.1线性规划问题的数学模型0,,,,,5)(252)(7)(500)(32max54332133215332143321543321xxxxxxxxxxxxxxxxxxxxxxxxxxZ标准形式如下：Page202.1线性规划问题的数学模型6.线性规划问题的解)3(,,2,1,0)2(),,2,1(.)1(max11njxmibxatsxcZjnjijijnjjj线性规划问题求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。Page212.1线性规划问题的数学模型可行解：满足约束条件②、③的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。Page222.2图解法线性规划问题的求解方法一般有两种方法图解法单纯形法两个变量、直角坐标三个变量、立体坐标适用于任意变量、但必需将一般形式变成标准形式下面我们分析一下简单的情况——只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。Page232.2图解法maxZ=2X1+X2X1+1.9X2≥3.8X1-1.9X2≤3.8s.t.X1+1.9X2≤10.2X1-1.9X2≥-3.8X1，X2≥0例2.5用图解法求解线性规划问题Page242.2图解法x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)4=2X1+X220=2X1+X217.2=2X1+X211=2X1+X2Lo：0=2X1+X2（7.6，2）DmaxZminZ此点是唯一最优解，且最优目标函数值maxZ=17.2可行域maxZ=2X1+X2Page252.2图解法maxZ=3X1+5.7X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1-1.9X2=-3.8(≥)X1+1.9X2=10.2(≤)（7.6，2）DL0：0=3X1+5.7X2maxZ（3.8，4）34.2=3X1+5.7X2蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。可行域Page262.2图解法minZ=5X1+4X2x1x2oX1-1.9X2=3.8(≤)X1+1.9X2=3.8(≥)X1+1.9X2=10.2(≤)DL0：0=5X1+4X2maxZminZ8=5X1+4X243=5X1+4X2（0，2）可行域此点是唯一最优解Page272.2图解法006346321212121xxxxxxxx、246x1x2246无界解(无最优解)maxZ=x1+2x2例1.6x1+x2=4(≥)x1+3x2=6(≥)3x1+x2=6(≥)maxZminZx1x2O10203040102030405050无可行解(即无最优解)0,050305.140221212121xxxxxxxxmaxZ=3x1+4x2例1.7Page292.2图解法学习要点：1.通过图解法了解线性规划有几种解的形式。(1)唯一最优解：一定对应于可行域的顶点；(2)无穷多最优解：多重解；(3)无界解：即无最优解的情况，原因：缺少必要的约束条件；(4)无可行解：即可行域为空集，原因：出现了相互矛盾的约束条件。Page302.2图解法学习要点：2.作图的关键有三点：(1)可行解区域要画正确(2)目标函数增加的方向不能画错(3)目标函数的直线怎样平行移动Page312.2图解法学习要点：3.结论(1)当线性规划问题的可行域非空时，它是有界或无解凸多边形。(2)若线性规划问题存在最优解，它一定在可行域的某个顶点获得。(3)若在两个顶点同时得到最优解，则它们连线上的任意一点都是最优解，即有无穷多最优解。Page322.3单纯形法基本原理1.单纯形法的基本思路基本思路：从可行域中某一个顶点开始，判断此顶点是否是最优解，如不是,则再找另一个使得其目标函数值更优的顶点，称之为迭代，再判断此点是否是最优解。直到找到一个顶点为其最优解，就是使得其目标函数值最优的解，或者能判断出线性规划问题无最优解为止。Page332.3单纯形法基本原理1.单纯形法的基本概念基：设A为约束条件②的m×n阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（∣B∣≠0），称B是规划问题的一个基（矩阵）。设：)(11111mmmmmppaaaaB称B中每个列向量Pj(j=12……m)为基向量。与基向量Pj对应的变量xj为基变量。除基变量以外的变量为非基变量。Page342.3单纯形法基本原理基本解：某一确定的基B，令非基变量等于零，由约束条件方程②解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过基本可行解：满足变量非负约束条件的基本解，简称基可行解。可行基：对应于基本可行解的基称为可行基。mnC非可行解可行解基本解基本可行解1.单纯形法的基本概念Page35基本最优解：最优解是基本可行解称为基本最优解。基本最优解对应的基称为最优基。2.3单纯形法基本原理Page362.3单纯形法基本原理例2.6求线性