《ch1 数学模型及单纯形法.ppt》由会员分享，可在线阅读，更多相关《ch1 数学模型及单纯形法.ppt（85页珍藏版）》请在三一办公上搜索。
1、Chapter1 线性规划及单纯形法,1.1 线性规划问题及数学模型 1.2 图解法 1.3 单纯形法 1.4 单纯形法的进一步讨论,本章主要内容：,page1,1.1 线性规划问题及数学模型,1.1.1 问题的提出规划问题Program 生产和经营管理中经常提出如何合理安排，使人力、物力等各种资源得到充分利用，获得最大的效益，这就是规划问题。线性linear 量与量之间按比例、成直线的关系，在数学上可以理解为一阶导数为常数的函数。,page2,1.1 线性规划问题及数学模型,线性规划 Linear Programming 求线性目标函数在线性约束条件下的最大值或最小值的问题，统称为线性规划问
2、题。通常解决下列两类问题：（1）在一定的资源条件限制下，如何组织安排生产获得最好的经济效益（如产品量最多、利润最大。）（2）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源（如资金、设备、材料、人工、时间等）去完成确定的任务或目标。,page3,1.1 线性规划问题及数学模型,例1 美佳公司计划制造、两种家电产品。已知各制造1件时分别占用的设备A，B的台时、调试工序时间及每天可用于这两种家电的能力、各售出1件时的获利情况，如下表所示。问该公司应制造两种家电各多少件，使获取的利润为最大。,page4,1.1 线性规划问题及数学模型,例2 捷运公司在下一年度的14月的4个月内拟租用仓库堆放
3、物资。已知各月份所需仓库面积列于表1-2。仓库租借费用随合同期而定，期限越长，折扣越大，具体数字见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积和期限。因此该厂可根据需要，在任何一个月初办理租借合同。每次办理时可签一份合同，也可签若干份租用面积和租借期限不同的合同，试确定该公司签订租借合同的最优决策，目的是使所付租借费用最小。,page5,1.1 线性规划问题及数学模型,1.1.2 线性规划问题的数学模型1）线性规划问题的数学定义：求取一组变量xj(j=1,2,.,n)，使之既满足线性约束条件，又使具有线性的目标函数取得极值的一类最优化问题称为线性规划问题。,怎样辨别一个模型
4、是线性规划模型？（1）问题的目标函数是多个决策变量的线性函数，通常是求最大值或最小值；（2）问题的约束条件是一组多个决策变量的线性不等式或等式。,page6,1.1 线性规划问题及数学模型,1.1.2 线性规划问题的数学模型2）线性规划的数学模型由三个要素构成 例1 例2,决策变量 Decision variables 目标函数 Objective function约束条件 Constraints,page7,例1,page8,max:maximize的缩写，“最大化”，s.t.subject to的缩写，“受限制于”,例1,page9,min：minimize，“最小化”,1.1.2 线性规
5、划问题的数学模型,目标函数：,约束条件：,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 线性规划
6、问题及数学模型,1.1.3 线性规划问题的标准形式,特点：(1)目标函数求最大值（有时求最小值）(2)约束条件都为等式方程，且右端常数项bi都大于或等于零(3)决策变量xj为非负。,page14,1.1.3 线性规划问题的标准形式,如何化标准形式？,目标函数的转换,如果是求极小值即，则可将目标函数乘以(-1)，可化为求极大值问题。,也就是：令，可得到上式。,即,若存在取值无约束的变量，可令 其中：,变量的变换,page15,1.1.3 线性规划问题的标准形式,约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,变量 的变换,可令，显然,page16,例3 将下述线性规划化为标准形
7、式,page17,1.1.3 线性规划问题的标准形式,课堂练习 将下列线性规划问题化为标准形式,用 替换，且,解:（）因为x3无符号要求，即x3取正值也可取负值，标准型中要求变量非负，所以,page18,1.1.3 线性规划问题的标准形式,(2)第一个约束条件是“”号，在“”左端加入松驰变量x4，x40,化为等式；(3)第二个约束条件是“”号，在“”左端减去剩余变量x5，x50；(4)第3个约束方程右端常数项为-5，方程两边同乘以(-1),将右端常数项化为正数；(5)目标函数是最小值，为了化为求最大值，令z=-z,得到max z=-z，即当z达到最小值时z达到最大值，反之亦然;,page19,
8、1.1.3 线性规划问题的标准形式,标准形式如下：,page20,作业,某药厂生产A、B、C三种药品，有甲乙丙丁四种原料可供选择（原材料供应不限），四种原料成本分别为每公斤4、7、9、5元。每公斤不同原料提取的各种药品数量g如下表所示：该厂要求每天生产药品A恰好115g，B至少260g，C不超过130g。使确定各种原料的每天需要量，使每天的总成本最小。试建立该问题的数学模型，并将模型化成标准型。,page21,1.2 图解法,线性规划问题的求解方法,一 般 有两种方法,图 解 法单纯形法,两个变量、直角坐标三个变量、立体坐标,适用于任意变量、但必需将一般形式变成标准形式,可行解：满足所有约束条
9、件的解。可行域：所有可行解的集合。最优解：使目标函数达到最大值的可行解。,page22,1.2 图解法,只有两个决策变量的线性规划问题，这时可以通过图解的方法来求解。图解法具有简单、直观、便于初学者窥探线性规划基本原理和几何意义等优点。其目的表现为：判别线性规划问题的求解结局；若存在最优解，将其找出。,page23,1.2 图解法,图解法的步骤：1）建立平面直角坐标系，标出坐标原点,坐标轴的指向和单位长度。2）对约束条件加以图解，找出可行域。3）画出目标函数等值线。4）结合目标函数的要求求出最优解。,page24,1.2 图解法,例1 用图解法求解线性规划问题,page25,1.2 图解法,p
10、age26,1.2 图解法,max Z=2X1+X2 X1+1.9X2 3.8 X1-1.9X2 3.8s.t.X1+1.9X2 10.2 X1-1.9X2-3.8 X1，X2 0,例 用图解法求解线性规划问题,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,max Z,min Z,此点是唯一最优解，且最优目标函数值 max Z=17.2,可行域,m
11、ax Z=2X1+X2,page28,1.2 图解法,max Z=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,max Z,（3.8，4）,34.2=3X1+5.7X2,蓝色线段上的所有点都是最优解这种情形为有无穷多最优解，但是最优目标函数值max Z=34.2是唯一的。,可行域,page29,1.2 图解法,min Z=5X1+4X2,x1,x2,o,X1-1.9X2=3.8(),X1+1.9X2=3.8(),X1+1.9X2=1
12、0.2(),D,L0：0=5X1+4X2,max Z,min Z,8=5X1+4X2,43=5X1+4X2,（0，2）,可行域,此点是唯一最优解,page30,1.2 图解法,2,4,6,x1,x2,2,4,6,无界解(无最优解),max Z=x1+2x2,例1.6,x1+x2=4(),x1+3x2=6(),3x1+x2=6(),max Z,min Z,page31,x1,x2,O,10,20,30,40,10,20,30,40,50,50,无可行解(即无最优解),max Z=3x1+4x2,例1.7,page32,1.2 图解法,(a)可行域有界(b)可行域有界(c)可行域无界 唯一最优解多
13、个最优解 唯一最优解,(d)可行域无界(e)可行域无界(f)可行域为空集 多个最优解 目标函数无界 无可行解,page33,1.2 图解法,学习要点：1.通过图解法了解线性规划有几种解的形式（唯一最优解；无穷多最优解；无界解；无可行解）2.若线性规划问题的可行域存在，则可行域是一个凸集；3.若线性规划问题的最优解存在，则最优解一定是可行域凸集的某个顶点；4.解题思路：先找凸集的任意顶点，计算在顶点处的目标函数值。,page34,1.3 单纯形法,1.3.1 线性规划问题的解,线性规划问题,求解线性规划问题，就是从满足约束条件(2)、(3)的方程组中找出一个解，使目标函数(1)达到最大值。,pa
14、ge35,1.3.1 线性规划问题的解,可行解：满足约束条件、的解为可行解。所有可行解的集合为可行域。最优解：使目标函数达到最大值的可行解。基：设A为约束条件的mn阶系数矩阵(mn)，其秩为m，B是矩阵A中m阶满秩子矩阵（B0），称B是规划问题的一个基。设：,称 B中每个列向量Pj(j=1 2 m)为基向量。与基向量Pj 对应的变量xj 为基变量。除基变量以外的变量为非基变量。,page36,1.3.1 线性规划问题的解,基解：某一确定的基B，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过 基可行解：满足变量非负约束条件的
15、基本解，简称基可行解。可行基：对应于基可行解的基称为可行基。,page37,例1.4 求线性规划问题的所有基矩阵。,解:约束方程的系数矩阵为25矩阵,r(A)=2，2阶子矩阵有10个，其中基矩阵只有9个，即,page38,例1.4 求线性规划问题的所有基。,page39,1.3.2 单纯形法基本原理,凸集：如果集合C中任意两个点X1、X2，其连线上的所有点也都是集合C中的点，称C为凸集。,page40,1.3.2 单纯形法基本原理,定理1：若线性规划问题存在可行解，则该问题的可行域是凸集。定理2：线性规划问题的基可行解X对应可行域(凸集)的顶点。定理3：若问题存在最优解，一定存在一个基可行解是
16、最优解。（或在某个顶点取得）,page41,解的几何意义,猜想1 线性规划的可行域是凸集；猜想2 最优解若存在，则可以在可行域的顶点上得到；猜想3 可行域的顶点的个数是有限的；猜想4 若有两个最优解，则其连线上的点也是最优解，即最优解有无穷多个 猜想5 对于标准型的线性规划X是可行域顶点的充分必要条件是X是基本可行解。,page42,1.3.3 单纯形法的计算步骤,单纯形法的思路,找出一个初始可行解,是否最优,转移到另一个基本可行解（找出更大的目标函数值）,最优解,是,否,循环,核心是：变量迭代,结束,page43,1.3.3 单纯形法的计算步骤,单纯形表,page44,1.3.3 单纯形法的
17、计算步骤,例1.8 用单纯形法求下列线性规划的最优解,解：1）将问题化为标准型，加入松驰变量x3、x4则标准型为:,page45,1.3.3 单纯形法的计算步骤,2）求出线性规划的初始基可行解，列出初始单纯形表。,检验数,page46,1.3.3 单纯形法的计算步骤,3）进行最优性检验,如果表中所有检验数，则表中的基可行解就是问题的最优解，计算停止。否则继续下一步。,4）从一个基可行解转换到另一个目标值更大的基可行解，列出新的单纯形表,确定换入基的变量。选择，对应的变量xj作为换入变量，当有一个以上检验数大于0时，一般选择最大的一个检验数，即：，其对应的xk作为换入变量。确定换出变量。根据下式
18、计算并选择，选最小的对应基变量作为换出变量。,page47,1.3.3 单纯形法的计算步骤,用换入变量xk替换基变量中的换出变量，得到一个新的基。对应新的基可以找出一个新的基可行解，并相应地可以画出一个新的单纯形表。5）重复3）、4）步直到计算结束为止。,page48,1.3.3 单纯形法的计算步骤,换入列,bi/ai2，ai20,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,p
19、age51,表1-9中所有j=0,且基变量中不含人工变量，最优解 X=(7/2,3/2,15/2,0,0);最优值 Z=17/2.,page52,算法思路,求一个初始基本可行解 是 判断基本可行解是否最优 结 束 不是 求使目标得到改善的基本可行解,是否存在？如何得到？,是否唯一？,如何判断？,如何改善？如何判断没有有限最优解？,page53,处理方法一 大法,人造基 添加人工变量造成基 去掉人工变量,5 单纯形法进一步讨论,page54,5 单纯形法进一步讨论,原问题的可行解新问题的可行解目标值,结论：新问题的最优解中，如果人工变量均为零，则得到的解也是原问题的最优解，否则原问题无可行解,p
20、age55,例6 大M法,page56,最优解:X=(0,5/2,3/2,0,0,0,0)最优值：Z=3/2,page57,处理方法二 两阶段法,人造基添加人工变量造成基去掉人工变量,page58,两阶段法,如果线性规划问题中的aij、bi或cj等参数值与这个代表M的数相对比较接近，或远远小于这个数字，由于计算机计算时取值上的误差，有可能使计算结果发生错误。为了克服这个困难，可以对添加人工变量后的线性规划问题分两个阶段来计算，称两阶段法。,page59,5单纯形法进一步讨论,第一阶段,第一阶段最优解中:如果Z0,则原问题没有基本可行解;如果Z=0,则若人工变量全为非基变量,则得到原问题的基本可
21、行解.否则基本可行解退化,继续迭代就可以得到基本可行解.,page60,5单纯形法进一步讨论,第二阶段,以第一阶段最优基作为初始基本可行解,继续迭代.,第一阶段,page61,例 6 两阶段法,第一阶段：,page62,请注意:第一阶段的最优解不是唯一的,page63,第二阶段,page64,几点注意事项,检验数的计算；进基变量的选取；若有不止一个变量可以进基时,只取一个；最小比值；若有不止一个最小比值时，只能选取其中之一行对应的基变量出基；没有有限最优解的情况；最优解是否唯一；最优表中非基变量检验数等于零时,可能最优解不唯一。,page65,1.3.3 单纯形法的计算步骤,学习要点：1.线性
22、规划解的概念以及3个基本定理2.熟练掌握单纯形法的解题思路及求解步骤,page66,单纯形法的进一步讨论人工变量法,解的判别：1）唯一最优解判别：最优表中所有非基变量的检验数非零,则线 规划具有唯一最优解。2）多重最优解判别：最优表中存在非基变量的检验数为零,则线则性规划具有多重最优解（或无穷多最优解）。3）无界解判别：某个k0且aik（i=1，2,m）则线性规划具有无界解。4）无可行解的判断：当用大M单纯形法计算得到最优解并且存在Ri0时，则表明原线性规划无可行解。5）退化解的判别：存在某个基变量为零的基本可行解。,page67,无可行解,page68,有可行解，但无最优解,page69,退
23、化解,page70,无穷多个最优解,page71,单纯形法的进一步讨论人工变量法,单纯性法小结:,page72,A,page73,线性规划模型的应用,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。,要求解问题的目标函数能用数值指标来反映，且为线性函数 存在着多种方案 要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述,page74,线性规划在管理中的应用,人力资源分配问题,例1.11 某昼夜服务的公交线路每天各时间段内所需司机和乘务人员人数如下表所示：,设司机和乘务人员分别在各时间段开始时上班，并连续工作8小时，问该公交线路应怎样安排司机和乘务人员，即
24、能满足工作需要，又使配备司机和乘务人员的人数减少?,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设备上加工。加工单位产品所需工序时间
25、及其他各项数据如下表，试安排最优生产计划，使该厂获利最大。,page77,线性规划在管理中的应用,page78,线性规划在管理中的应用,解：设xijk表示产品i在工序j的设备k上加工的数量。约束条件有：,page79,线性规划在管理中的应用,目标是利润最大化，即利润的计算公式如下：,带入数据整理得到：,page80,线性规划在管理中的应用,因此该规划问题的模型为：,page81,线性规划在管理中的应用,3.套裁下料问题,例：现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？,解：为了找到一个省料的套裁方案，必须先设计出较好的几个下料方案。其次要求这些方案的总体能裁下所有各种规格的圆钢，以满足对各种不同规格圆钢的需要并达到省料的目的，为此可以设计出4种下料方案以供套裁用。,page82,线性规划在管理中的应用,设按方案、下料的原材料根数分别为xj(j=1，2,3,4)，可列出下面的数学模型：,page83,线性规划在管理中的应用,4.配料问题,例：某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下：问两种食物各食用多少，才能既满足需要、又使总费用最省？,page84,线性规划在管理中的应用,解：设Xj 表示Bj 种食物用量,page85,
