最优化方法课件：2-2 线性规划的标准型和基本概念

1、1线性规划 线性规划问题及其数学模型 线性规划的单纯形法 线性规划的对偶理论 线性规划的灵敏度分析2美国数学家，美国全国科学院院士。线性规划的奠基人。1914年11月8日生于美国俄勒冈州波特兰市。1946年在伯克利加利福尼亚大学数学系获哲学博士学位。1947年丹齐克在总结前人工作的基础上创立了线性规划, 并提出了解决线性规划问题的单纯形法。 19371939年任美国劳工统计局统计员，19411952年任美国空军司令部数学顾问、战斗分析部和统计管理部主任。19521960年任美国兰德公司数学研究员，19601966年任伯克利加利福尼亚大学教授和运筹学中心主任。1966年后任斯坦福大学运筹学和计算

2、机科学教授。1971年当选为美国科学院院士。1975年获美国科学奖章和诺伊曼理论奖金。George Bernard Dantzig (1914) 3康托罗维奇，. 前苏联著名经济学家，苏联著名经济学家 。前苏联科学院院士 。前苏联国家科学技术委员会国民经济管理研究所经济问题研究主任。最优计划理论的创始人。 1912年生，1930年毕业于列宁格勒大学物理数学系，1935年获数学博士学位。1964年被选为苏联科学院院士。因提出资源最大限度分配理论，1975年与美籍荷兰学者T.C.库普曼斯一起获得诺贝尔经济学奖金。 4 康托罗维奇的主要贡献是把线性规划用于经济管理，创立了最优计划理论。对有效利用资源

3、和提高企业经济效益起了重大作用。他还提出经济效果的概念和衡量经济效果的统一指标体系,作为经济决策的定量依据,来选择最合理的社会生产结构。 主要著作有生产组织与计划的数学方法(1939)、资源最优利用的经济计算(1959)、最优计划的动态模型(1964)等。 5 佳林库普曼斯(1910年1985年)，美国人，1910年8月28日生于荷兰，1940年离开荷兰移居美国。1975年，他和康托罗维奇同时获得诺贝尔经济学奖。线性规划经济分析法的创立者。 6 冯诺依曼（John von Neumann，1903年12月28日1957年2月8日）是出生于匈牙利的美国籍犹太人数学家，现代电子计算机创始人之一。他

4、在计算机科学、经济、物理学中的量子力学及几乎所有数学领域都作过重大贡献。 1940年以后，冯诺伊曼转向应用数学。在力学、经济学、数值分析和电子计算机方面作出了卓越贡献。 从1942年起，他同莫根施特恩合作，写作博弈论和经济行为一书，使他成为数理经济学的奠基人之一。72 线性规划的标准型和基本概念 线性规划问题及其数学模型 线性规划的图解法 线性规划的标准形式 标准型线性规划的解的概念 线性规划的基本理论 问题的提出： 在生产管理的经营活动中，通常需要对“有限的资源”寻求“最佳”的利用或分配方式。有限资源：劳动力、原材料、设备或资金等 最佳：有一个标准或目标，使利润达到最大或成本达到最小。 有限

5、资源的合理配置有两类问题如何合理的使用有限的资源，使生产经营的效益达到最大；在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。 线性规划问题及其数学模型例，某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可提供的资源总量如下表所示：每吨产品的消耗 每周资源总量 甲乙维生素（公斤） 3020160设备（台班） 5115已知该厂生产每吨甲、乙药品的利润分别为5万元和2万元。但根据市场需求调查的结果，甲药品每周的产量不应超过4吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？ 定义x1

6、为生产甲种药品的计划产量数，x2为生产乙种药品的计划产量数。 数学模型为 s.t. （subject to) (such that) 每吨产品的消耗 每周资源总量 甲乙维生素（公斤） 3020160设备（台班） 5115单位利润（万元） 511例2 靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和80

7、0元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小工厂1工厂2200万m3500万m312决策变量：x1、x2分别代表工厂1和工厂2处理污水的数量(万m3)。则目标函数：min z=1000 x1+800 x2约束条件：第一段河流（工厂1工厂2之间）： (2x1)/500 0.2%第二段河流： 0.8(2x1) +(1.4x2)/7000.2%此外有： x12； x21.4化简有： min z=1000 x1+800 x2 x1 1 0.8x1 + x2 1.6 x1 2 x21.4 x1、x20称之为上述问题的数学模型。例，某铁器加工厂

8、要制作100套钢架，每套要用长为2.9米，2.1米和1.5米的圆钢各一根。已知原料长为7.4米，问应如何下料，可使材料最省？分析：在长度确定的原料上截取三种不同规格的圆钢，可以归纳出8种不同的下料方案：圆钢（米）291201010021002211301531203104料头（米）00.10.20.30.80.91.1.4设xj表示用第j种下料方案下料的原料根数，j=1,28, 数学模型 s.t. 这是一个下料问题，是在生产任务确定的条件下，合理的组织生产， 使所消耗的资源数最少的数学规划问题。 满足一组约束条件的同时，寻求变量x1至x8的值,使目标函数取得最 小值。 圆钢（米）2912010

9、10021002211301531203104料头（米）00.10.20.30.80.91.11.4且为整数 线性规划的一般数学模型 线性规划模型的特征：（1）用一组决策变量x1，x2，xn表示某一方案，且在一般情况下，变量的取值是非负的。（2）有一个目标函数，这个目标函数可表示为这组变量的线性函数。（3）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。（4）要求目标函数实现极大化（max）或极小化（min）。满足上述4个特征的规划问题称为线性规划问题 线性规划的一般数学模型 目标函数 满足约束条件 通常称 为决策变量， 为价值系数， 为消耗系数, 为资源限制系数。 线性规

10、划的图解法 适用于求解两个变量的线性规划问题 图解法的基本步骤例4,利用例1说明图解法的主要步骤， 例1的数学模型为 s.t. O51015x1x1=4x25101AB( 2, 5)CZ5x1+x2=1530 x1+20 x2=1605x1+2x2=5 图解法的几种可能结果 (1）有唯一最优解，如例1。（2）有无穷多最优解 如例1中的目标函数设为 maxZ=10 x1+2x2 则目标函数等值线10 x1+2x2=Z 与第二约束 5x1+x215 的边界线平行。将等值线沿梯度Z =（10，2）正方向平移 至B点时与可行域OABC的整条边界线AB重合。 这表明线段AB上的每一点都使目标函数取得同样

11、的最大值， 因而都是最优解。20O51015x1x1=4x25101AB（2，5）CZ5x1+x2=1530 x1+20 x2=16010 x1+2x2=5例5，试用图解法求解下列线性规划问题 st.（3） 无界解（或称无最优解） 无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值Z+, 极小化问题 则可使目标函数值Z-， 有无界解的线性规划问题的可行域是无界区域，但反之则不必然。-1 O24x1x224-Z=(3,2)-2x1+x2=2x1-3x2=3-1 O33（4）无可行解 某些线性规划问题的可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上最优

12、解了。 在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。 24例6 max z=x1+2x2 x1 + 2x21 x1 + x22 x1、x20无可行解。1112OA25以上几种情况的图示如下：可行域有界唯一最优解可行域有界多个最优解26可行域无界唯一最优解可行域无界无穷多最优解27可行域无界目标函数无界可行域为空集无可行解281. 有最优解 唯一最优解 无穷多最优解2. 最优解无界3. 无可行解29直观结论：（1）可行域可以是个凸多边形，可能无界，也可能为空；（2）若线性规划问题的最优解存在，它一定可以在可行域的某一个顶点上得到；（3）若在两个顶点上同时得到最优解，

13、则该两点连线上的所有点都是最优解，即LP有无穷多最优解；（4）若可行域非空有界，则一定有最优解。30O51015x1x25101AB( 2, 5)C5x1+x2=1530 x1+20 x2=160 标准线性规划模型 线性规划问题的标准形式： s.t 其中（2） （3）线性规划的标准形式（1）紧凑格式： s.t.向量格式： s.t. 其中 称为价值向量， 为决策变量向量， 为决策变量xj所对应的消耗系数向量， 为资源向量。矩阵格式：其中 为mn阶矩阵 为价值向量， 为决策变量向量， 为资源向量。33非标准形式线性规划问题的标准化（1）极大化与极小化 ： 若 ，令 ，则有 原目标函数 。(2)线性

14、不等式与线性等式： 其中 为非负松弛变量， 其中 为非负剩余变量。 35 (4) 非负变量与符号不受限制的变量 若 xi的符号不受限制，则可引进非负变量xi1,xi2，令 xi = xi1-xi2，这样就可以使线性规划里所有的变量都转化为有非负限制的变量。 (3) 右端项为负 约束两端乘以（1）例7，将下述线性规划问题化为标准型 解：令,其中符号不受限制37O51015x1x25101AB( 2, 5)C5x1+x2=1530 x1+20 x2=160考虑一个标准的线性规划问题： s.t 其中为n维列向量， 是n维列向量， 是m维列向量， 是mn阶矩阵，假定满足mn，且()=m，标准型线性规划

15、的解的概念 线性规划问题解的概念： (1) 可行解。满足约束条件的解可行解集称为线性规划问题的可行域。(2) 最优解。使目标函数达到最优值的的可行解称为最优解，最优解常用 表示。基向量，基变量 若是线性规划问题的一个基，那么一定是由m个线性无关的列向量组成，不失一般性，可设 称 为基向量，与基向量相对应的变量称为基变量。 基的个数 一个线性规划的基通常不是唯一的，但是基的个数不会超过 个。(3) 基。若是中mm阶非奇异矩阵，即|0，则称是线性规划问题的一个基。 (4) 基本解。设B是线性规划的一个基，若令n-m个非基变量等于0，则所得的方程组=b的解称为线性规划问题的一个基本解（简称基解）。基

16、本解的个数也不会超过 个。 由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。(5) 基本可行解。满足非负条件的基本解称为基本可行解 （简称基可行解）。与基本可行解对应的基称为可行基。 基本可行解的非零向量的个数小于等于m，并且都是非负的。当基本可行解中有一个或多个基变量取零值时，称此解为 退化的基本可行解。42 一个线性规划问题，如果它的所有基本可行解都是非退化的，那么 称这个线性规划是非退化的. 对非退化线性规划，可行基和基本可行解之间是一一对应的。 线性规划问题各种解的关系可用文氏图表示， 可行解基本解基本可行解例8、求下列约束方程所对应的线性规划的所有基本解， 基本可行解。

17、s.t 解：化为标准形式 为24阶矩阵。 且R(A)=2,所以该线性规划基的个数 =6个 取 , 为基变量， 若令非基变量 ， 约束方程组为 可得对应的基本解 是一个基本可行解。 按相同步骤，可求得线性规划其他4个基：对应基本解是一个基本可行解。 对应基本解是一个基本可行解。 对应基本解不是一个基本可行解。 对应基本解是一个基本可行解。 若利用图解法画出线性规划的可行域，如图，CDOBA44847例9、已知线性规划问题的约束条件为 试讨论可行域顶点和基本可行解之间的对应关系。解:可行域为四维凸多面体，可以推得在四维空间中有3个顶点，=(0,0,10,10)，=(0,10,0,10)，=(10,

18、0,0,0)。这3个顶点与线性规划的5个基本可行解的对应关系如下：顶点对应以x3,x4为基变量的基本可行解；顶点对应以x2,x4为基变量的基本可行解；顶点对应x1,x2;x1,x3和x1,x4为基变量的退化基本可行解， BCA 线性规划的基本理论 由图解法的步骤，可以从几何的角度得出结论：（1）线性规划问题的可行域是一个有界或无界的凸多边形，其顶点个数是有限个。（2）若线性规划问题有最优解，那么最优解一定可在可行域的某个顶点上找到。49 线性规划的基本定理 引理1：线性规划问题的可行域是一个凸集。 定理1：线性规划问题的可行解是基本可行解的充要条件是 的正分量所对应的系数列向量线性无关。 定理

19、2：设线性规划问题的可行解是的一个顶点的 充分必要条件是为基本可行解。 定理3：若可行域D非空，那么一定存在D的顶点（极点)。 若线性规划问题存在可行解，则一定存在基本可行解。定理4：若线性规划问题存在最优解，则必存在基本可行解 是最优解。50引理1：若线性规划问题存在可行域，则其可行域是一个凸集。证明：为了证明满足=，0的所有点（可行解）组成的几何体是凸集，只要证明中任意两点连线上的一切点均满足线性约束条件既可。任取，满足则对任意的有 线性规划的基本定理 又因为均0，所以由此可知，即是凸集。证明：必要性：因为是基本解，由基本解的定义，的非零分量所对应的系数列向量线性无关，又因为是可行解，由基本可行解的定义，非零分量均是正的，所以的正分量所对应的系数列向量线性无关。 定理1：线性规划问题的可行解 是基本可行解的充要条件是的