ch1 数学模型及单纯形法

Chapter1线性规划及单纯形法,1.1线性规划问题及数学模型1.2图解法1.3单纯形法1.4单纯形法的进一步讨论,本章主要内容：,page1,1.1线性规划问题及数学模型,1.1.1问题的提出规划问题Program生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性linear量与量之间按比例、成直线的关系，在数学上可以理解为一阶导数为常数的函数。,page2,1.1线性规划问题及数学模型,线性规划LinearProgramming求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问题。通常解决下列两类问题：（1）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大。）（2）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、材料、人工、时间等）去完成确定的任务或目标。,page3,1.1线性规划问题及数学模型,例1美佳公司计划制造、两种家电产品。已知各制造1件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出1件时的获利情况，如下表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。,page4,1.1线性规划问题及数学模型,例2捷运公司在下一年度的14月的4个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。,page5,1.1线性规划问题及数学模型,1.1.2线性规划问题的数学模型1）线性规划问题的数学定义：求取一组变量xj(j=1,2,.,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。,怎样辨别一个模型是线性规划模型？（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。,page6,1.1线性规划问题及数学模型,1.1.2线性规划问题的数学模型2）线性规划的数学模型由三个要素构成例1例2,决策变量Decisionvariables目标函数Objectivefunction约束条件Constraints,page7,例1,page8,max:maximize的缩写，“最大化”，s.t.subjectto的缩写，“受限制于”,例1,page9,min：minimize，“最小化”,1.1.2线性规划问题的数学模型,目标函数：,约束条件：,3）线性规划数学模型的一般形式,简写为：,page10,1.1.2线性规划问题的数学模型,向量形式：,其中：,page11,1.1.2线性规划问题的数学模型,矩阵形式：,其中：,page12,1.1线性规划问题及数学模型,课堂练习某企业有三个工厂甲、乙、丙生产某种产品销往四个销售点A、B、C、D。每个计划期内甲乙丙的供应量分别为150、200和250件，销售点A、B、C、D的需求量分别是120、140、160和180件。各工厂运送至各销售点的运价如表所示，试制定总运价最小的调运方案（建立该问题的线性规划模型）。,page13,1.1线性规划问题及数学模型,1.1.3线性规划问题的标准形式,特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。,page14,1.1.3线性规划问题的标准形式,如何化标准形式？,目标函数的转换,如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。,也就是：令，可得到上式。,即,若存在取值无约束的变量，可令其中：,变量的变换,page15,1.1.3线性规划问题的标准形式,约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,变量的变换,可令，显然,page16,例3将下述线性规划化为标准形式,page17,1.1.3线性规划问题的标准形式,课堂练习将下列线性规划问题化为标准形式,用替换，且,解:（）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以,page18,1.1.3线性规划问题的标准形式,(2)第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3)第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z=-z,得到maxz=-z，即当z达到最小值时z达到最大值，反之亦然;,page19,1.1.3线性规划问题的标准形式,标准形式如下：,page20,作业,某药厂生产A、B、C三种药品，有甲乙丙丁四种原料可供选择（原材料供应不限），四种原料成本分别为每公斤4、7、9、5元。每公斤不同原料提取的各种药品数量g如下表所示：该厂要求每天生产药品A恰好115g，B至少260g，C不超过130g。使确定各种原料的每天需要量，使每天的总成本最小。试建立该问题的数学模型，并将模型化成标准型。,page21,1.2图解法,线性规划问题的求解方法,一般有两种方法,图解法单纯形法,两个变量、直角坐标三个变量、立体坐标,适用于任意变量、但必需将一般形式变成标准形式,可行解：满足所有约束条件的解。可行域：所有可行解的集合。最优解：使目标函数达到最大值的可行解。,page22,1.2图解法,只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。其目的表现为：判别线性规划问题的求解结局；若存在最优解，将其找出。,page23,1.2图解法,图解法的步骤：1）建立平面直角坐标系，标出坐标原点,坐标轴的指向和单位长度。2）对约束条件加以图解，找出可行域。3）画出目标函数等值线。4）结合目标函数的要求求出最优解。,page24,1.2图解法,例1用图解法求解线性规划问题,page25,1.2图解法,page26,1.2图解法,maxZ=2X1+X2X1+1.9X23.8X1-1.9X23.8s.t.X1+1.9X210.2X1-1.9X2-3.8X1，X20,例用图解法求解线性规划问题,page27,1.2图解法,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1-1.9X2=-3.8(),X1+1.9X2=10.2(),4=2X1+X2,20=2X1+X2,17.2=2X1+X2,11=2X1+X2,Lo：0=2X1+X2,（7.6，2）,D,maxZ,minZ,此点是唯一最优解，且最优目标函数值maxZ=17.2,可行域,maxZ=2X1+X2,page28,1.2图解法,maxZ=3X1+5.7X2,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1-1.9X2=-3.8(),X1+1.9X2=10.2(),（7.6，2）,D,L0：0=3X1+5.7X2,maxZ,（3.8，4）,34.2=3X1+5.7X2,蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值maxZ=34.2是唯一的。,可行域,page29,1.2图解法,minZ=5X1+4X2,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1+1.9X2=10.2(),D,L0：0=5X1+4X2,maxZ,minZ,8=5X1+4X2,43=5X1+4X2,（0，2）,可行域,此点是唯一最优解,page30,1.2图解法,2,4,6,x1,x2,2,4,6,无界解(无最优解),maxZ=x1+2x2,例1.6,x1+x2=4(),x1+3x2=6(),3x1+x2=6(),maxZ,minZ,page31,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解(即无最优解),maxZ=3x1+4x2,例1.7,page32,1.2图解法,(a)可行域有界(b)可行域有界(c)可行域无界唯一最优解多个最优解唯一最优解,(d)可行域无界(e)可行域无界(f)可行域为空集多个最优解目标函数无界无可行解,page33,1.2图解法,学习要点：1.通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）2.若线性规划问题的可行域存在，则可行域是一个凸集；3.若线性规划问题的最优解存在，则最优解一定是可行域凸集的某个顶点；4.解题思路：先找凸集的任意顶点，计算在顶点处的目标函数值。,page34,1.3单纯形法,1.3.1线性规划问题的解,线性规划问题,求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。,page35,1.3.1线性规划问题的解,可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。基：设A为约束条件的mn阶系数矩阵(m0,40,10,换出行,将3化为1,5/3,1,18,0,1/3,0,1/3,10,1,1/3,30,30,0,5/3,0,4/3,乘以1/3后得到,1,0,3/5,1/5,18,0,1,1/5,2/5,4,0,0,1,1,page49,解：,表1-7,page50,page51,表1-9中所有j0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。,page67,无可行解,page68,有可行解，但无最优解,page69,退化解,page70,无穷多个最优解,page71,单纯形法的进一步讨论人工变量法,单纯性法小结:,page72,A,page73,线性规划模型的应用,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。,要求解问题的目标函数能用数值指标来反映，且为线性函数存在着多种方案要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述,page74,线性规划在管理中的应用,人力资源分配问题,例1.11某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：,设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即能满足工作需要，又使配备司机和乘务人员的人数减少?,page75,线性规划在管理中的应用,解：设xi表示第i班次时开始上班的司机和乘务人员人数。,此问题最优解：x150，x220，x350，x40，x520，x610，一共需要司机和乘务员150人。,page76,线性规划在管理中的应用,2.生产计划问题,某厂生产、三种产品，都分别经A、B两道工序加工。设A工序可分别在设备A1和A2上完成，有B1、B2、B3三种设备可用于完成B工序。已知产品可在A、B任何一种设备上加工；产品可在任何规格的A设备上加工，但完成B工序时，只能在B1设备上加工；产品只能在A2与B2设备上加工。加工单位产品所需工序时间及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。,page77,线性规划在管理中的应用,page78,线性规划在管理中的应用,解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：,page79,线性规划在管理中的应用,目标是利润最大化，即利润的计算公式如下：,带入数据整理得到：,page80,线性规划在管理中的应用,因此该规划问题的模型为：,page81,线性规划在管理中的应用,3.套裁下料问题,例：现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？,解：为了找到一个省料的套裁方案，必须先设计出