第4部分线规划.ppt
《第4部分线规划.ppt》由会员分享,可在线阅读,更多相关《第4部分线规划.ppt(99页珍藏版)》请在三一文库上搜索。
1、第4章 线性规划,本章要点 掌握线性规划的基本概念 透过单纯形解法了解线性规划的科学性 了解影子价格和灵敏度分析 学会线性规划的建模方法 学会利用软件求解各类线性规划问题,第1节 线性规划的数学模型,一、线性规划问题 人类社会的主要矛盾:欲望与现实的矛盾 企业会遇到市场的局限、产能的局限、配件的局限、资金的局限,这些限制妨碍了我们对利益的追求,于是人们拓展市场、扩大产能、积累资金 但是无论如何,约束始终是存在的,这是人类无法摆脱的宿命。 我们能够做的就是最优化地配置资源,在既定的条件下把资源的效用发挥到极致。,例1.生产计划问题,某公司生产A、B两种矿产品,销路不成问题。制约因素主要有技术工人
2、、设备台时和原材料供应。已知,该公司应该如何制定每天的生产计划,使其产值最大?,例1.生产计划问题,设X1为A产品产量,X2为B产品的产量, 用z表示产值,则每天的产值表示为maxz=80X1+140X2,称为目标函数。 将制约因素表达出来,即有: 人力不超过300工时:6X1+4X2300 设备不超过280台时:4X1+6X2 280 矿石不超过320公斤:2X1+8X2 320,例1.生产计划问题,生产计划问题的数学模型:,例2.护士排班问题,医院的护士24小时都需要值班,不同时段需要的人数不同,按照4小时一个时段排班,每班工作8小时,具体的统计数据如下表:,例2.护士排班问题,设第时段上
3、班的人数为 Xj,例2.护士排班问题,线性规划问题的一般特征,max(min)z=,二、线性规划模型的标准型,线性规划模型的标准型,1.缩写形式,线性规划模型的标准型,2.向量形式,线性规划模型的标准型,3.矩阵形式,三、非标准型的转化,1.约束条件不等式的转化 约束条件不等式为“”时。在不等式左边加上一个松弛变量 约束条件不等式为“”时。在不等式左边减去一个剩余变量 2.自由变量 个别问题中存在无非负要求的变量,这时令,XK=XK-XK,则XK0,XK 0 3.极小化的目标函数 若目标函数为min, 令Z=-Z,使Z=CX。求maxZ等价于求minZ,例3. 写出例1的标准型,例4. 将下列
4、转化为标准型,设Z=-Z,令X3=X3-X3,再引入松弛变量X4和剩余变量 X5,第2节 线性规划的基本概念和定理,一、线性规划的基本概念 1.可行解 满足所有约束条件的解称为可行解 “一致同意原则” 2.可行域 可行解的集合叫做可行域 3. 基矩阵 约束方程的系数矩阵A是mn阶的矩阵,设nm,则A中必有 个m阶的方阵,若方阵的行列式值不为0,即方阵为非奇异子阵,则可基于这个矩阵求得一组解,这个矩阵就叫做这组解的基矩阵,相应的这组解就叫做基解,例1的系数矩阵 右端项,以子矩阵,为基,求得,以子矩阵,为基,求得,以子矩阵,为基,求得,一、线性规划的基本概念,4.基可行解 立足于基矩阵得到的解叫做
5、基解,基解中的可行解叫做基可行解。前述 都是基解, 是 基可行解,而 不是基可行解,因为不满足非负性约束。,一、线性规划的基本概念,5.凸集 设K是n维欧式空间的一个点集,若任意两点 均有 则称K为凸集。 凸集的几何意义是:集合K中任意两点连线上的点仍然属于K。,二、 线性规划的图解法,以例1.生产计划问题为例,50,75,25,0,25,50,75,100,125,150,x1,x2,A,B,C,D,三、线性规划的基本定理,定理1. 线性规划的可行域是凸集。 定理2.线性规划的可行解为基可行解的充要条件是:X的非零分量所对应的系数列向量线性无关。 定理3. 如果线性规划有可行解,则一定有基可
6、行解。 定理4. 线性规划问题的基可行解对应于可行域的顶点。 定理5. 若线性规划问题的可行域非空有界,则线性规划问题的最优解一定可以在其可行域的某个顶点上得到。,特殊的线性规划问题,1.无穷多解 当目标函数与某个约束条件平行时,有无穷多最优解。,50,75,25,0,25,50,75,100,125,150,X1,x,2,特殊的线性规划问题,2.无界解 若可行域是一个开区间,有可能出现“没有最好,只有更好”最优解无界的情形。,特殊的线性规划问题,3.无可行解 当约束条件相互矛盾时,可行域是一个空集,即呈现没有可行解的情形,第3节 线性规划的单纯形解法,单纯形法的解题思路: 1.从可行解到基解
7、 谁做人大代表? 2.从基解到最优解 谁说了算?,一、单纯形法的代数解释,显然, 的系数矩阵是一个非奇异子阵,以此为基得到一个基可行解 ,即:不生产A产品,也不生产B产品,人力剩余300工时,设备剩余280台时,即矿石剩余320公斤。,仍以例1.为例,一、单纯形法的代数解释,显然, 不是最优解, Z(0)=0. 令X20,保持X1=0,生产量取决于资源的支持:,解得,左式的含义是什么?右式为什么是min?,得到第二组基可行解,一、单纯形法的代数解释,分析:X(1)=(0, 40,140,40,0)T,Z(1)=5600,是否最优? 将基变量用非基变量线性表示: 代入目标函数: 解释各参数的内涵
8、,X1的系数为45,表明生产A产品有利可图,于是当前解还不是最优解。,一、单纯形法的代数解释,两个非基变量中,保持X5为0,迫使X10 解得: 于是得到一组新解: 更正 新解是否最优呢?还需要进一步检验 更正:教材82页数字错误,X3取值由70改为60,一、单纯形法的代数解释,将 代入目标函数进行检验 两个非基变量的系数均为负值,说明闲置设备或剩余矿石都将使产值减少,故此判断:当前的解已是最优解。,二、单纯形法原理,1.寻找初始基可行解 设有如下线性规划模型 以前m列为基矩阵B,相应地 为基变量,非基变量取零值,则得到一组解,2.最优性检验 将基变量用非基变量线性表示: 代入Z,3.基变换 当
9、某个非基变量的检验数 时,说明还有改进的空间,于是让 进基,而基变量的个数是有限的,只能是m个,这时必须迫使原有的某个基变量出基,谁出来呢?凭“实力”较量:令 比值最小的变量就是出基变量。一进一出就叫做一次基变换。,4.线性变换 进基 出基,交叉点上的系数 叫做主元素(或枢轴元素),用高斯消去法将主元素变为1,同列中的其它元素变为零,由此得到一组新的基解 回到2.进行最优性检验,直至所有的 就可以宣布:已经得到了最优解。 求解过程结束。,三、单纯形表的格式和算法,为了使单纯形法的计算更加便捷和规范,dantzig设计了一种表格,将前述运算过程纳入表格之中,这个表格叫做单纯形表。 将例1标准化后
10、,装入表格进行求解,四、单纯形法的矩阵描述,将标准型拆分:,将约束条件移项: 左乘 得: 代入目标函数得:,第4节 线性规划应用举例与求解,线性规划的核心在于应用 应用的关键在于建模 建模的要点在于变量设置 用合适的变量表达目标函数、约束条件,就得到了数学模型。 求解可以借助计算机软件,例5.污水处理问题,河流沿岸有某公司的两个化工厂,A厂每天排放污水2万方;B厂每天排放污水1.4万方。A厂排出的污水流到B厂之前,有20可以自然净化。根据环保要求,河水中污水含量不得超过0.2。已知A厂污水处理成本1000元/万方,B厂污水处理成本800元/万方。问公司应该如何分配污水处理的数量,使得总成本最低
11、?,例5.污水处理问题建模,解:设A厂处理X1万方/天,B厂处理X2万方/天 主要约束: A厂的排放点不超标: B厂的排放点不超标: A厂处理量不可能超过2万方 B厂处理量不可能超过1.4万方,例5.污水处理问题建模,例5.数据输入,例5.结果输出,例6.合理下料问题,某学校为建造车棚,需要用100个铝合金三角架作龙骨,底梁长度2.9米,两个斜梁分别是2.1米和1.5米,已知原料长度7.4米。问如何下料使得所用原料最省?,2.9m,2.1m,1.5m,例6.合理下料问题建模,解:本题的变量设置不是显而易见的。首先要设计若干个截取方案,把按照某方案截取的根数作为决策变量 。方案要尽可能完备,遗漏
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 部分 线规
链接地址:https://www.31doc.com/p-2606154.html