《第4部分线规划.ppt》由会员分享，可在线阅读，更多相关《第4部分线规划.ppt（99页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第4部分线规划 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望第1节 线性规划的数学模型v一、线性规划问题一、线性规划问题v人类社会的主要矛盾：欲望与现实的矛盾v企业会遇到市场的局限、产能的局限、配件的局限、资金的局限，这些限制妨碍了我们对利益的追求，于是人们拓展市场、扩大产能、积累资金v但是无论如何，约束始终是存在的，这是人类无法摆脱的宿命。v我们能够做的就是最优化地配置资源，在既定的条件下把资源的效用发挥到极致。例例1.生产计划问题生产计划问题v某公司生产A、
2、B两种矿产品，销路不成问题。制约因素主要有技术工人、设备台时和原材料供应。已知资源 产品A产品B产品资资源限量源限量人力64300设备46280矿石28320售价（元售价（元/公斤）公斤）80140该公司应该如何制定每天的生产计划，使其产值最大？例例1.生产计划问题生产计划问题v设X1为A产品产量，X2为B产品的产量，v用z表示产值，则每天的产值表示为maxz=80X1+140X2，称为目标函数。v将制约因素表达出来，即有：人力不超过300工时:6X1+4X2300设备不超过280台时:4X1+6X2 280矿石不超过320公斤:2X1+8X2 320例例1.生产计划问题生产计划问题v生产计划
3、问题的数学模型：例例2.护士排班问题护士排班问题v医院的护士24小时都需要值班，不同时段需要的人数不同，按照4小时一个时段排班，每班工作8小时，具体的统计数据如下表：序号时段最低人数最低人数16：00-10：0060210：00-14：0070314：00-18：0060418：00-22：0050522：00-2：002062：00-6：0030例例2.护士排班问题护士排班问题v设第时段上班的人数为 Xj例例2.护士排班问题护士排班问题线性规划问题的一般特征 max(min)z=二、线性规划模型的标准型二、线性规划模型的标准型线性规划模型的标准型线性规划模型的标准型v1.缩写形式缩写形式 线
4、性规划模型的标准型线性规划模型的标准型v2.向量形式向量形式线性规划模型的标准型线性规划模型的标准型v3.矩阵形式矩阵形式三、非标准型的转化三、非标准型的转化v1.约束条件不等式的转化约束条件不等式的转化 v约束条件不等式为“”时。在不等式左边加上一个松弛变量 v约束条件不等式为“”时。在不等式左边减去一个剩余变量 v2.自由变量自由变量 个别问题中存在无非负要求的变量，这时令，XK=XK-XK,则XK0，XK 0v3.极小化的目标函数极小化的目标函数 若目标函数为min，令Z=-Z，使Z=CX。求maxZ等价于求minZ例例3.写出例1的标准型例例4.将下列转化为标准型设Z=-Z，令X3=X
5、3-X3，再引入松弛变量X4和剩余变量 X5第2节 线性规划的基本概念和定理v一、线性规划的基本概念一、线性规划的基本概念v1.可行解可行解 满足所有约束条件的解称为可行解满足所有约束条件的解称为可行解 “一致同意原则一致同意原则”v2.可行域可行域 可行解的集合叫做可行域v3.基矩阵基矩阵 约束方程的系数矩阵A是mn阶的矩阵，设nm，则A中必有 个m阶的方阵，若方阵的行列式值不为0，即方阵为非奇异子阵，则可基于这个矩阵求得一组解，这个矩阵就叫做这组解的基矩阵，相应的这组解就叫做基解 v例1的系数矩阵 右端项以子矩阵为基，求得以子矩阵为基，求得以子矩阵为基，求得一、线性规划的基本概念一、线性规
6、划的基本概念v4.基可行解基可行解 立足于基矩阵得到的解叫做基解，基解中的可行解叫做基可行解。前述 都是基解，是 基可行解，而 不是基可行解，因为不满足非负性约束。一、线性规划的基本概念一、线性规划的基本概念v5.凸集凸集 设K是n维欧式空间的一个点集，若任意两点 均有 则称K为凸集。v凸集的几何意义是：集合K中任意两点连线上的点仍然属于K。二、二、线性规划的图解法线性规划的图解法v以例1.生产计划问题为例 5075250255075100125150 x1x2ABCD三、线性规划的基本定理三、线性规划的基本定理v定理1.线性规划的可行域是凸集。v定理2.线性规划的可行解为基可行解的充要条件是
7、：X的非零分量所对应的系数列向量线性无关。v定理3.如果线性规划有可行解，则一定有基可行解。v定理4.线性规划问题的基可行解对应于可行域的顶点。v定理5.若线性规划问题的可行域非空有界，则线性规划问题的最优解一定可以在其可行域的某个顶点上得到。特殊的线性规划问题v1.无穷多解无穷多解 当目标函数与某个约束条件平行时，有无穷多最优解。5075250255075100125150X1x2特殊的线性规划问题v2.无界解无界解 若可行域是一个开区间，有可能出现“没有最好，只有更好”最优解无界的情形。50100500100150特殊的线性规划问题v3.无可行解无可行解 当约束条件相互矛盾时，可行域是一个
8、空集，即呈现没有可行解的情形 50100500100150第3节 线性规划的单纯形解法v单纯形法的解题思路：v1.从可行解到基解 谁做人大代表？v2.从基解到最优解 谁说了算？一、单纯形法的代数解释一、单纯形法的代数解释显然，的系数矩阵是一个非奇异子阵，以此为基得到一个基可行解 ，即：不生产A产品，也不生产B产品，人力剩余300工时，设备剩余280台时，即矿石剩余320公斤。仍以例1.为例一、单纯形法的代数解释一、单纯形法的代数解释v显然，不是最优解,Z(0)=0.v令X20，保持X1=0，生产量取决于资源的支持：解得左式的含义是什么？右式为什么是min？得到第二组基可行解一、单纯形法的代数解
9、释一、单纯形法的代数解释v分析：X(1)=(0,40,140,40,0)T,Z(1)=5600，是否最优？v将基变量用非基变量线性表示：v 代入目标函数：v解释各参数的内涵，X1的系数为45，表明生产A产品有利可图，于是当前解还不是最优解。一、单纯形法的代数解释一、单纯形法的代数解释v两个非基变量中，保持X5为0，迫使X10v 解得：v于是得到一组新解：更正更正v新解是否最优呢？还需要进一步检验更正：教材更正：教材82页数字错误，页数字错误，X3取值由取值由70改为改为60一、单纯形法的代数解释一、单纯形法的代数解释v将 代入目标函数进行检验v两个非基变量的系数均为负值，说明闲置设备或剩余矿石
10、都将使产值减少，故此判断：当前的解已是最优解。二、单纯形法原理二、单纯形法原理v1.寻找初始基可行解寻找初始基可行解v设有如下线性规划模型设有如下线性规划模型v以前以前m列为基矩阵列为基矩阵B，相应地，相应地 为基变量，非为基变量，非基变量取零值，则得到一组解基变量取零值，则得到一组解 v2.最优性检验最优性检验v将基变量用非基变量线性表示：代入Z v3.基变换基变换v当某个非基变量的检验数当某个非基变量的检验数 时，说明还时，说明还有改进的空间，于是让有改进的空间，于是让 进基，而基变量的进基，而基变量的个数是有限的，只能是个数是有限的，只能是m个，这时必须迫使个，这时必须迫使原有的某个基变
11、量出基，谁出来呢？凭原有的某个基变量出基，谁出来呢？凭“实实力力”较量：令较量：令v v比值最小的变量就是出基变量。一进一出就比值最小的变量就是出基变量。一进一出就叫做一次基变换。叫做一次基变换。v4.线性变换线性变换v 进基进基 出基，交叉点上的系数出基，交叉点上的系数 叫做主叫做主元素（或枢轴元素），用高斯消去法将主元元素（或枢轴元素），用高斯消去法将主元素变为素变为1，同列中的其它元素变为零，由此得，同列中的其它元素变为零，由此得到一组新的基解到一组新的基解 v回到回到2.进行最优性检验，直至所有的进行最优性检验，直至所有的 就可以宣布：已经得到了最优解。就可以宣布：已经得到了最优解。v
12、求解过程结束。求解过程结束。三、单纯形表的格式和算法三、单纯形表的格式和算法v为了使单纯形法的计算更加便捷和规范，dantzig设计了一种表格，将前述运算过程纳入表格之中，这个表格叫做单纯形表。v将例1标准化后，装入表格进行求解Cj80140000CiXBbx1x2x3x4x5i0 x330064100750 x42804601046.70 x532028001j801400000X31405010-1/2280X4405/2001-3/4140 x2401/41001/8160j45000-17.50X360001-2180X1161002/5-3/10140 x236010-1/101/5
13、j000-18-4四、单纯形法的矩阵描述四、单纯形法的矩阵描述 v将标准型拆分：v将约束条件移项：v左乘 得：v代入目标函数得：第4节 线性规划应用举例与求解v线性规划的核心在于应用v应用的关键在于建模v建模的要点在于变量设置v用合适的变量表达目标函数、约束条件，就得到了数学模型。v求解可以借助计算机软件例例5.污水处理问题污水处理问题v河流沿岸有某公司的两个化工厂，河流沿岸有某公司的两个化工厂，A厂每天排放污厂每天排放污水水2万方；万方；B厂每天排放污水厂每天排放污水1.4万方。万方。A厂排出的污厂排出的污水流到水流到B厂之前，有厂之前，有20可以自然净化。根据环保可以自然净化。根据环保要求
14、，河水中污水含量不得超过要求，河水中污水含量不得超过0.2。已知。已知A厂污厂污水处理成本水处理成本1000元元/万方，万方，B厂污水处理成本厂污水处理成本800元元/万方。问公司应该如何分配污水处理的数量，使得万方。问公司应该如何分配污水处理的数量，使得总成本最低？总成本最低？A厂厂B厂厂500万立方万立方/天天200万万 立立 方方/天天例例5.污水处理问题建模污水处理问题建模v解：解：设A厂处理X1万方/天，B厂处理X2万方/天v主要约束：vA厂的排放点不超标：vB厂的排放点不超标：vA厂处理量不可能超过2万方vB厂处理量不可能超过1.4万方 例例5.污水处理问题建模污水处理问题建模例5
15、.数据输入例5.结果输出例例6.合理下料问题合理下料问题v某学校为建造车棚，需要用100个铝合金三角架作龙骨，底梁长度2.9米，两个斜梁分别是2.1米和1.5米，已知原料长度7.4米。问如何下料使得所用原料最省？2.9m2.1m1.5m例例6.合理下料问题建模合理下料问题建模v解：解：本题的变量设置不是显而易见的。首先要设计若干个截取方案，把按照某方案截取的根数作为决策变量 。方案要尽可能完备，遗漏了方案则会影响最优化的结果。长度 方案123456782.9M2.1M1.5M103201022120013111030004余料00.10.20.30.80.91.11.4例例6.合理下料问题建模
16、合理下料问题建模例6.数据输入例6.结果输出例例7.滚动投资问题滚动投资问题v新任经理发现小金库里有100万元资金，令企划部找项目投资，力争第五年末本利和最大。企划部提出四个投资项目：vA项目，从第一年到第四年每年年初投资，并于次年末收回本利110，每年至少投资10万元；vB项目，第二年初投资，第五年末收回本利135，投资额度不超过20万元；vC项目，第三年初投资，第五年末收回本利125，投资额度在20-40万元之间；vD项目，每年年初投资，年末收回本利104。v问应该如何安排不同项目不同年度的投资额度？例例7.滚动投资问题滚动投资问题v解：解：设第i年投资于j项目的金额为 万元第一年第二年第
17、三年第四年第五年A项目1.1B项目1.35D项目1.04C项目1.25例例7.滚动投资问题建模滚动投资问题建模例7.数据处理v首先进行变量置换，依出现次序排列用 代换 ，原有数学模型变为：例7.数据输入例7.结果输出第5节 对偶问题与灵敏度分析v一、一、对偶问题的提出对偶问题的提出v线性规划的另一面线性规划的另一面v卖产品还是卖资源？卖产品还是卖资源？v卖资源所得不少于卖产品卖资源所得不少于卖产品v对立的等价问题对立的等价问题例例8.资源转让问题资源转让问题 v例例1.的思考的思考：A、B两种产品，市场前景很好，销路不成问题。现在有意转换经营方式，拟将各种资源出租出让，问公司转让资源的价格底线
18、是什么？资源 产品A产品B产品资资源限量源限量人力64300设备46280矿石28320售价（元售价（元/公斤）公斤）80140例8.的分析与建模v思考：将三种资源出让，应该不少于原有的收益，否则企业宁愿选择继续自己生产。v决策的约束条件是：出租制造产品所耗的资源不少于自行生产该产品的收益；v目标函数是：资源转让的收益底线。例8.的分析与建模v设劳动力、设备台时和矿石的出让价格分别为 v生产A产品的资源至少应带来80元的产值 v生产B产品的资源至少应带来140元的产值v目标函数：转让的收益底线例8.的分析与建模二、原问题与对偶问题的关系二、原问题与对偶问题的关系原问题和对偶问题是相互对应的关系
19、 v1.原问题目标函数max，约束条件是“”形式；对偶问题目标函数min，约束条件是“”形式。v2.原问题的价值系数对应对偶问题的右端项，原问题的右端项对应对偶问题的价值系数；v3.原问题的变量对应对偶问题的约束条件，原问题有n个变量，对偶问题就有n个约束条件。原问题有m个约束条件，对偶问题就有m个变量。v4.原问题系数矩阵的转置就是对偶问题系数矩阵 三、三、对偶问题的基本性质对偶问题的基本性质v（1）对称性：对偶问题的对偶是原问题。v（2）弱对偶性：极大化原问题的任意可行解的目标值，不可能超过极小化的对偶问题的任意可行解的目标值。v（3）无界性：若其中一个问题无界，则另一问题无可行解。v（4
20、）强对偶性：若两个互为对偶的问题之一有最优解、那么另一个必有最优解，且两者目标函数值相等。三、三、对偶问题的基本性质对偶问题的基本性质ZX三、三、对偶问题的基本性质对偶问题的基本性质v（5）互补松弛定理：和 分别是原问题和其对偶问题的最优解的充分必要条是:v v这个定理的含义是：对偶问题的原始变量对应原问题的松弛变量，原问题的原始变量对应对偶问题的剩余变量，两者“你死我活”、“势不两立”，甚至有时还会“同归于尽”。例例9.对偶定理的运用 v例7.设有线性规划问题如下：v已知其最优解为 ，求对偶问题的最优解。v解：根据对偶规则，写出其对偶问题：v 故有：v根据对偶定理有如下对应关系：三、三、对偶
21、问题的基本性质对偶问题的基本性质v(6)原问题检验数对应对偶问题的一组解（证明略）v原问题检验数的反数反数恰好对应对偶问题的解。v原问题松弛变量对应对偶问题的原始变量v原问题原始变量对应对偶问题的剩余变量四、四、对偶最优解的经济解释对偶最优解的经济解释影子影子价格价格 v 的含义是：在其它条件不变的情况下，增加一个单位的第i种资源所引起的目标函数最优值的变化。亦即：每单位第i种资源对目标函数值的贡献率。对资源bi求偏导数：影子价格的应用v影子价格不是市场价格，只是企业资源配置状况的反应，揭示了资源的稀缺度。v注意注意：影子价格仅仅是“边际效用”v揭示了稀缺资源和过剩资源v提示了购入资源的代价v
22、提示了出让注意的底线v判断新产品的开发价值五、灵敏度分析五、灵敏度分析决策决策现在现在将来将来过去过去数据数据实施实施拷问拷问支持支持v问题：环境是不断变化的，模型给定的价值系数、资源限量、技术系数也会发生变化，那么最优解的结构稳定性如何呢？v灵敏度分析就是要解答这样的问题：在保持最优基不变的前提下，各类参数的允许变化范围是什么。灵敏度分析灵敏度分析灵敏度分析案例灵敏度分析案例v例例10.某艺术陶瓷制品公司生产6种定型产品，原料车间制成磁泥和釉浆之后，还需要经过成型、上釉、贴花/彩绘、焙烧四道工序。产产品品资资源源P1P2P3P4P5P6资源限量资源限量（分钟）（分钟）成型成型35246480
23、00上釉上釉11.511.2212500贴花贴花0.1-0.1-0.15-200彩绘彩绘-5-6-84000焙烧焙烧1212312500单位价格单位价格5080407010060v根据销售合同，根据销售合同，P1最多生产最多生产600件，件，P4至少生产至少生产80件，件，P6最多生产最多生产500件，其件，其余产品销路较好。请根据资源情况求出余产品销路较好。请根据资源情况求出最优生产计划，并且根据灵敏度分析结最优生产计划，并且根据灵敏度分析结果回答下述问题：果回答下述问题：v1.本公司的资源配置状况如何？本公司的资源配置状况如何？v2.如果可以增加资源，应该优先增加哪种？如果可以增加资源，应
24、该优先增加哪种？v3.为什么为什么P5的价格最高却不生产该产品？的价格最高却不生产该产品？v4.产品产品P4是否盈利，如果续签合同应该如何定价？是否盈利，如果续签合同应该如何定价？v5.如果客户要求如果客户要求P6降价降价5元，生产计划有没有变化？元，生产计划有没有变化？v6.产品产品P1的价格上限为什么是的价格上限为什么是infinity?v7.产品产品P2的价格下限为什么是的价格下限为什么是-infinity?v8.解读约束条件解读约束条件1的灵敏度分析参数之间的关联。的灵敏度分析参数之间的关联。v9.如果彩绘师傅同意加班，每小时如果彩绘师傅同意加班，每小时100元工资值不值元工资值不值？
25、最多安排多长的加班时间？最多安排多长的加班时间？v10.主打产品主打产品P3的价格在什么区间波动最优解不变？的价格在什么区间波动最优解不变？最优值变不变？最优值变不变？例10.详解第6节 运输问题v一、运输问题的结构一、运输问题的结构vm个产地，个产地，n个销地，从第个销地，从第i个产地到第个产地到第j个销地的单个销地的单位运输费用位运输费用 。如何确定一个调运方案使得总运。如何确定一个调运方案使得总运费最省？费最省？产 销B1B2Bn产量A1C11C12C1na1A2C21C22C2na2AmCm1Cm2Cmnam销量b1b2bn二、二、非标运输问题非标运输问题v1.供需不平衡的运输问题供需
26、不平衡的运输问题v产大于销：增加一个虚拟的销地产大于销：增加一个虚拟的销地v销大于产：增加一个虚拟的产地销大于产：增加一个虚拟的产地v例例4-11（略）（略）二、二、非标运输问题非标运输问题v2.弹性需求问题弹性需求问题v例例12.三个统配煤矿给四个地区供应煤炭，作三个统配煤矿给四个地区供应煤炭，作为冬季取暖之用。甲地区（华北）最低需求为冬季取暖之用。甲地区（华北）最低需求30万吨，最高需求万吨，最高需求50万吨；乙地区（东北）万吨；乙地区（东北）需求需求70万吨；丙地区（广东）最低需求为零，万吨；丙地区（广东）最低需求为零，最高需求最高需求30万吨；丁地区（上海）最低需求万吨；丁地区（上海）
27、最低需求10万吨，最高不限。供给数量、需求数量及万吨，最高不限。供给数量、需求数量及相应运费数据如下表：如何安排调运方案，相应运费数据如下表：如何安排调运方案，使总运费最少？使总运费最少？2.弹性需求问题弹性需求问题地区煤矿甲乙丙丁产量产量ABC1614191313202219231715506050最低需求最低需求最高需求最高需求3050707003010不限2.弹性需求问题弹性需求问题v分析：v数学讲究严谨和明确，多大的或多小的数字都好处理，唯独模棱两可的事情不好处理。v首先，将刚性部分与弹性部分区分开来v其次，界定丁地区的“多多益善”v第三，以最高需求为基准建立供需平衡点v第四，设置一个
28、虚拟煤矿D，用以弥补产能的缺口v最后，参数设计，运筹学如何说“no”2.弹性需求问题建模弹性需求问题建模地区煤矿甲1甲2乙丙丁1丁2产量产量ABCD161419M1614190131320M22192301715MM1715M050605050需求需求3020703010502102.弹性需求问题的求解v计算机不认得惩罚项M，必须转换为具体数值，M只要“足够大”即可，设 ，取值243.航运调度问题v例例13.航运公司经营六个港口之间的四条航线 航线航线起点起点终点终点航班数航班数/天天航行天数航行天数1234EBADDCFB3211173713终点起点 A B C D E FABCDEF 0
29、1 2 14 7 7 1 0 3 13 8 8 2 3 0 15 5 514 13 15 0 17 20 7 8 5 17 0 3 7 8 5 20 3 0 3.航运调度问题v假定船只型号相同，装船、卸船各需要一天时间，问该公司至少需要配备多少条船才能满足运营的需要？v解题思路：v分类：载重船与空驶船v载重船分航线测算，共计91艘v空驶船多少艘？3.航运调度问题ABCFDE1213调度中心港口每天到达数每天需求数余缺余缺ABCDEF012301120130-1-1+2+2-3+13.航运调度问题供方 需方A B E需求量需求量CDF2 3 514 13 177 8 3221供给量供给量1 1
30、3港口分为两类：空船供应港和空船需求港，有了供需双方，又有相互之间的航行天数（相当于单位运费），于是得到运输问题的数学模型：3.航运调度问题v输出结果：vC港每天调往A港1艘、E港1艘；D港每天调往B和E各1艘；F港每天调往E港1艘。共需空驶船数：21+51+131+171+3140艘。v空驶船和载重船加在一起，共需131艘运输船。启示与思考：启示与思考：v（1）该公司有没有达到经济规模？v（2）如果可以并购重组，应该放弃哪条航线，兼并哪条航线？第7节 整数规划v有整数要求的线性规划问题v纯整数规划、混合整数规划、0-1规划v如何求解？方法多样化，此处不讲解法，用计算机求解即可。一、纯整数规划
31、一、纯整数规划v例例14.某集装箱运输公司有甲乙两种货物可供装运，相关数据如下表，问如何装运使得每车的收益最高？约束 货物甲 乙限量限量体积（M3）重量（吨）5 42 52413单位价格2000 1000例10.建模与求解二、混合整数规划二、混合整数规划v例例15.某塑胶制品厂生产台布和地板革，使用相同的生产线加工，每周可用工时186，另外两种化工原料比较紧俏。如何安排生产使得总利润最大？约束 产品台布（块）地板革（米）资资源限制源限制工时原料A（公斤）原料B（公斤）0.02 0.010.8 0.30.4 0.5118670006500单单位利位利润润（元）（元）15 9例15.混合整数规划求
32、解三、三、01型整数规划型整数规划v例16.某公司拟投资800万元开辟新的商业网点，可供选择的店铺有6个，有三个附加条件：第一，若选择项目1，就必须同时选择项目2；第二，项目2、3、4中至少选择一个；第三，项目5、6中最多选择一个。怎样选择项目才能使总预期收益最大？店铺投资额（万元）投投资资收益（万元收益（万元/年）年）124080233090327085418065526082635095例16.选址问题求解解：设解：设0-1变量变量四、四、指派问题指派问题v例例17.四个外语学院学生组成翻译公司，接到一项业务：把一个产品说明书翻译成A、B、C、D四种语言，应指派何人做何种工作，能使总的时间最少？学生 语种1234A149415B117910C136105D1791513四、四、指派问题求解指派问题求解v将数据输入，点击solve即得：