线性规划及单纯形法.ppt

《线性规划及单纯形法.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、第一章线性规划及单纯形法§1.线性规划问题及其数学模型1.1问题的引出某公司计划制造Ⅰ、Ⅱ两种家电产品，已知各制造一件时分别占用的设备A、B的台时、调试时间；每天可用的设备能力及各售出一件时的获利情况如下表：试问如何安排生产，该公司才能获利最大？ⅠⅡ每天可用能力设备A（h）0515设备B（h）6224调试工序(h)115利润（元）21作业：1.3（2）1.51.6（2）1.81.131.14Example2某采油区已建有n个计量站，各站目前尚未被利用的能力为bj（吨液量）。为适应油田开发的需要，规划在该油区打m口调整井，且这些

2、井的位置已经确定。根据预测，调整井的产量分别为ai（吨液量/日）。考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井。按规划要求，每口井只能属于一个计量站。假定i井到j站的距离dij已知，试确定各调整井与计量站的关系，使新建集输管线总长度最短。Example31.2线性规划问题的数学模型1.三例题的数学模型对例1：设Ⅰ、Ⅱ两种家电产品分别生产x1，x2件ⅠⅡ每天可用能力设备A（h）0515设备B（h）6224调试工序（h）115利润（元）21模型2BA1…j…n产液量1x11…x1j…x1na1……ixi1

3、…xij…xinai……mxm1…xmj…xmnam处理能力bj小结：线性规划研究的对象大致分为两类：（1）在现有的人财物等资源条件下，研究如何合理计划、安排，使得某一目标达到最大（2）在任务确定后，研究如何合理计划、安排，以使所需资源为最少1.4L.P模型中各量的称谓约定xj决策变量Cj价值系数A=（aij）m×n技术系数与系数矩阵bi右端常数项z目标函数值1.3线性规划模型的一般形式1.6LP模型的计法1.7LP模型的标准形LP模型标准型的约定约定：目标函数：最大值型决策变量：非负约束条件：等于型4.对小于等于型约束条件1

4、.8LP问题的标准化1.对取值为负的变量2.对自由变量3.对求最小值型6.对等于型约束条件7.右端常数项为负时5.对大于等于型约束条件LP问题的标准化举例Maxz=2x1+x2s.t.5x2≤156x1+2x2≤24x1+x2≤5x1,x2≥054321123455x2≤15x2=-2x16x1+2x2≤24§2图解法2.1图解法的局限性及其意义2.2图解法的步骤：（1）变不等式约束为等式约束，图示可行域（2）可行域上寻找最优解（2.1）等直线法（2.2）试算法2.3LP问题的解唯一的最优解无穷多最优解无界解—缺少约束条

5、件无解—约束条件矛盾2.4图解法引出的思考LP问题可行域是凸集(有两个最优解就有无穷多个最优解)？凸集：设有集合S,X(1)X(2)是其中任意两点，若对于：恒有X属于S,则称S是一个凸集。（几何解释）LP问题的最优解一定能在定点上达到？顶点：设有集合S,V是S上的一个点，若V不能用异于它的两点表为:则称V是S的一个顶点。§3单纯形法原理3.1LP问题的概念设有LP问题：(1)可行解(2)可行域(3)最优解判断：最优解一定是可行解，复亦如是？(5)基变量(6)非基变量(7)基解(8)可行基与基可行解(4)基：设A＝(aij)m

6、n为系数矩阵(n>m)，其秩为m，B是A中的一个mm阶的非奇异的子阵，则称B是A的一个基。思考：（4.1）基与向量组的极大线性无关组有什么关系？（4.2）基与坐标系是什么关系？（4.3）L.P.的A最多能有多少个基？L.P.问题解的图示可行解基解基可行解非可行解3.2L.P.的三定理证明：LP问题的可行域如（2）、（3）所示，X（1）、X（2）是其上任意两点，X（1）、X（2）属于En，做：X=λX（1）＋（1-λ）X（2）0<λ<1因为0<λ<1，所以，X满足（3）要求。所以，X满足（2）的要求，根据凸集定义可知，LP问

7、题的可行域是凸集（证毕)定理2：LP问题的基可行解对应可行域的顶点（2.1）LP问题的基可行解对应可行域的顶点（2.2）LP问题的可行域的顶点是基可行解三段论证明法（证真，证伪）：①结论；②结论“带有”的条件；③证明的问题人固有一死，或重于泰山，或轻于鸿毛，为人民利益而死，就比泰山还重；替法西斯利益而死，就比鸿毛还轻。张思德同志……定理1：LP问题的可行域是凸集结论带有的条件：任意两点连线上的点还在集合内（2.1）LP问题的基可行解对应可行域的顶点（反证法）假设Ｘ是一基本可行解，但不是可行域的顶点.则由顶点的定义，一定能从可行

8、域中找到异于Ｘ两点：因为Ｘ是基可行解（非基变量未零），所以有:以上两式相减得：由于Ｘ（1）、Ｘ（2）是不等的两点，则上式表明:是线性相关的，从而说明Ｘ不是基本可行解，与假设矛盾，假设不成立，故命题成立。证毕。(2.2)LP问题的基可行解←←可行域的顶点引理１：可行解是基可行解