线性规划及单纯形法.ppt

1、第一章 线性规划及单纯形法1. 线性规划问题及其数学模型,1.1问题的引出 某公司计划制造、两种家电产品，已知各制造一件时分别占用的设备A、B的台时、调试时间；每天可用的设备能力及各售出一件时的获利情况如下表： 试问如何安排生产，该公司才能获利最大？,作业：1.3（2） 1.5 1.6（2） 1.8 1.13 1.14,Example 2,某采油区已建有n个计量站，各站目前尚未被利用的能力为bj（吨液量）。为适应油田开发的需要，规划在该油区打m口调整井，且这些井的位置已经确定。根据预测，调整井的产量分别为ai（吨液量/日）。考虑到原有计量站富余的能力，决定不另建新站，而用原有老站分工管辖调整井

2、。按规划要求，每口井只能属于一个计量站。假定i井到j站的距离dij已知，试确定各调整井与计量站的关系，使新建集输管线总长度最短。,Example 3,1.2 线性规划问题的数学模型,1.三例题的数学模型 对例1：设、两种家电产品分别生产x1，x2件,模型2,小结：线性规划研究的对象大致分为两类： （1）在现有的人财物等资源条件下，研究如何合理计划、安排，使得某一目标达到最大 （2）在任务确定后，研究如何合理计划、安排，以使所需资源为最少,1.4 L.P 模型中各量的称谓约定,1.3 线性规划模型的一般形式,1.6 LP模型的计法,1.7 LP模型的标准形 LP模型标准型的约定 约定： 目标函数

3、：最大值型 决策变量：非负 约束条件：等于型,4.对小于等于型约束条件,1.8 LP问题的标准化 1.对取值为负的变量 2.对自由变量,3.对求最小值型,6.对等于型约束条件 7.右端常数项为负时,5.对大于等于型约束条件,LP问题的标准化举例,Max z=2x1+x2 s.t. 5x2 15 6x1+2x2 24 x1+x2 5 x1,x20,5x2 15,x2=-2x1,6x1+2x2 24,2 图解法 2.1 图解法的局限性及其意义 2.2图解法的步骤： （1）变不等式约束为等式约束，图示可行域 （2）可行域上寻找最优解 （2.1）等直线法 （2.2）试算法,2.3 LP问题的解 唯一的

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

5、设A(aij) m n 为系数矩阵(nm)，其秩为m，B是A中的一个m m阶的非奇异的子阵，则称B是A的一个基。 思考： （4.1）基与向量组的极大线性无关组有什么关系？ （4.2）基与坐标系是什么关系？ （4.3）L.P.的A最多能有多少个基？,L.P.问题解的图示,3.2 L.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问题的可行域是凸集（证毕),定理2：LP问题的基可行

6、解对应可行域的顶点 （2.1）LP问题的基可行解对应可行域的顶点 （2.2） LP问题的可行域的顶点是基可行解,三段论证明法（证真，证伪）： 结论；结论“带有”的条件；证明的问题 人固有一死，或重于泰山，或轻于鸿毛，为人民利益而死，就比泰山还重；替法西斯利益而死，就比鸿毛还轻。 张思德同志,定理1：LP问题的可行域是凸集 结论 带有的条件：任意两点连线上的点还在集合内,（2.1）LP问题的基可行解对应可行域的顶点 （反证法）假设是一基本可行解，但不是可行域的顶点. 则由顶点的定义，一定能从可行域中找到异于两点：,因为是基可行解（非基变量未零），所以有:,以上两式相减得：,由于（1）、（2）是不

7、等的两点，则上式表明: 是线性相关的，从而说明不是基本可行解，与假设矛盾，假设不成立，故命题成立。证毕。,(2.2)LP问题的基可行解 可行域的顶点 引理：可行解是基可行解的充分必要条件是其正分量对应的系数列向量线形无关 证明： 必要性：不违一般，对基可行解: 而言，由基可行解的定义可知，必有： 线性无关。 充分性：当l=m，依据基本可行解的定义，可知是一基可行解，证毕； 当lm，由矩阵的秩是m可知，一定能从其余n-l个列向量中找出m-l个，构成一个基，并确认是该基下的基可行解（退化的基可行解）。,（反证法）假设是可行域的一顶点，但不是基可行解 不违一般，记： 是一顶点，但不是基可行解。既然是

8、一顶点，肯定是可行解，故有：,由于是顶点可行解，不是基可行解，根据引理，可知其正分量对应系数列向量线性相关，即有：,用0 乘（2）式得：,（1）加减（3）得：,选取适当的，做可行解：,如此又可得：,该式表明不是顶点，与假设矛盾，假设不成立，故命题成立。证毕。,定理3：LP问题的最优解一定能在顶点上得到 定义：设及（1）、（2）（k）是中的点，若存在 ：,则称是点（1）、（2）（k）凸组合。 引理：凸集上的任一点，都可表为其顶点的凸组合。（说明不证）,第四节 单纯形法步骤4.1 单纯形法计算步骤,1.LP模型标准化 2.编制初始单纯形表并确定初始可行基、初始基可行解,丹切克简介 理解： 降维/转

9、轴,4.1 单纯形法计算步骤,3.最优性检验 （1）计算机会成本: （2）计算检验数 当所有检验数小于等于0时，得到最优解，结束。反之，转下步。,4.基变换 相邻基:相差且仅相差一个列向量的两个基 (1)用启发性规则确定入基列向量及入基变量 K列称为主元列 (2)用规则(资源瓶颈)确定出基列向量及出基变量 L行称为主元行,5.修正单纯形表(1),6.返回步骤3,5.修正单纯形表(2) 1.主元素的概念 2.初等变换 主元行新元素旧元素/主元素 非主元行新元素旧元素（负该行与主元列交汇格元素新主行对应元素）,第五节 单纯形法的进一步讨论 5.1人工变量法,5.2 两阶段法,为去除求解过程中带有M

10、的不方便，采用两阶段法： 阶段1：求解只含人工变量的模型，若其最优解为零，即人工变量可挤出，转阶段2；否则，原问题无解。 阶段2：丢掉人工变量继续求解原模型；,如对模型（）而言，应用两阶段法则有： max z=-A1-A2 s.t. x1+ x2+x3 + s1 =4 -2x1+ x2- x3 +A1 - s2 =1 （） 3x2+x3 +A2 =9 variable not negative,两阶段法阶段1,两阶段法阶段2/丢掉人工变量继续求解,5.3 单纯形法中的循环问题 什么是循环？ 勃兰特规则: 小的进，小的出,5.4 L.P.的解及其在单纯形表中的体现 1.唯一的最优解 2.无穷多最

11、优解 3.褪化的基可行解 4.无解/无有界最优解,4.2单纯形法原理,讨论的模型为：,（1）确定初始基及其基可行解 对经过标准化的LP模型，总会存在一个初始可行基与其基可行解。不失一般性，记：,（2）从一个可行基转到相邻的可行基 定义：两个基可行解称为相邻的，如果它们之间变换且仅变换一个基变量。 对X（0）而言有：,（3）最优性检验和解的判别（3.1）启发性规则,将“基可行解”x(0)和x(1)分别代入目标函数得:,（3.2）最优性检验,（3.3）新基的存在性,6.应用举例 （1）资源分配问题 商场售货人员每周工作5天，连续休息2天，如何安排其作息，既能满足工作需要，又能使所需售货人员最少（讨

12、论）,（2）下料问题 制造某种机床，需要A,B,C三种轴件，其规格与数量如下表；各类轴件都用5.5米长的同一种圆钢下料。计划生产100台机床，最少需要多少根圆钢？,（3）配料问题 用n种原料A1,A2,An,配成具有m种成分B1,B2,Bm的某种产品，规定单位产品所含Bi种成分bi;原料单价分别为cj,数量限制为dj,其所含成分aij. 要求产品产量不低于t，问如何配料，成本最低。,设为配制该产品j种原料取用xj,6.应用举例 时代服装公司生产一款时装，预测今后6个月需求量如表； 每件服装用工2h，材料费10元，售价40元； 公司1月初有4名工人，每月工作200h，月薪2000元。 公司可于月

13、初雇佣新工人，招募费用1500元；也可解雇工人，补偿费1000元/人； 供不应求，短缺不补；但若超产，库存费5元/件.月； 试作决策，使6个月利润最大。,童心玩具厂下一年度的现金流（万元）如表所示，表中负号表示该月现金流出大于流入，为此该厂需借款。借款有两种方式：一是于上一年末借一年期贷款，一次得全部贷款额，从1月底起每月还息1%，于12月归还本金和最后一次利息；二是得到短期贷款，每月初获得，于月底归还，月息1.5%。当该厂有多余现金时，可短期存款，月初存入，月末取出，月息0.4%。问该厂应如何进行存贷款来操作，既能弥补可能出现的负现金流，又可使年末现金总量为最大。,设k月初的净现金流为sk 各月给定净现金为dk 1月初年期贷款xy k月初月期贷款xmk,宏银公司承诺为某建设项目从2003年起的4年中每年初分别提供以下数额贷款：2003年100万元，2004年150万元，2005年120万元，2006年110万元。以上贷款资金均需于2002年底前集齐。但为了充分发挥这笔资金的作用，在满足每年贷款额情况下，可将多余资金分别用于下列投资项目： （1）于2003年初购买A种债券，期限3年，到期后本息合计为投资额的140%，但限购60万元； （2）于2003