第一部分线性规划

1、线性规划数学模型的标准形式及解的概念线性规划数学模型的标准形式及解的概念 线性规划的基本理论线性规划的基本理论两变量线性规划的图解法两变量线性规划的图解法 线性规划问题及其数学模型线性规划问题及其数学模型 (Linear Programming , LP) 线性规划是运筹学的重要分枝线性规划是运筹学的重要分枝,也是运筹学最基本的部分也是运筹学最基本的部分. 20世纪世纪30 年代末，前苏联学者康托洛维奇首先研究了线性年代末，前苏联学者康托洛维奇首先研究了线性规划问题规划问题.1939年，他撰写的年，他撰写的生产组织与计划中的数学方法生产组织与计划中的数学方法一书，是线性规划应用于工业生产问题的

2、经典著作一书，是线性规划应用于工业生产问题的经典著作. 后来丹西格（后来丹西格（G. B. Dantzig）于）于 1947 年发现了单纯形方年发现了单纯形方法，并将其应用于与国防有关的诸如人员的轮训、任务的分派法，并将其应用于与国防有关的诸如人员的轮训、任务的分派等问题等问题. 此后，线性规划的理论和方法日渐趋于成熟此后，线性规划的理论和方法日渐趋于成熟. 线性规划所研究的对象属于最优化的范畴，本质上是一线性规划所研究的对象属于最优化的范畴，本质上是一个极值问题个极值问题. 和其它最优化问题一样，在建立线性规划问题的和其它最优化问题一样，在建立线性规划问题的数学模型时，应首先明确三个基本要素

3、：数学模型时，应首先明确三个基本要素： 决策变量决策变量（decision variables）：它们是决策者所控制的）：它们是决策者所控制的那些数量，它们取什么数值需要决策者来决策，问题的求解那些数量，它们取什么数值需要决策者来决策，问题的求解就是找出决策变量的最优值就是找出决策变量的最优值. 约束条件约束条件(constraints):它们是决策者在现实世界中所受它们是决策者在现实世界中所受到的限制，或者说决策变量在这些限制范围之内才有意义到的限制，或者说决策变量在这些限制范围之内才有意义. 目标函数目标函数(objective function):它代表决策者希望对其进行它代表决策者希望

4、对其进行优化的那个指标优化的那个指标.目标函数是决策变量的函数目标函数是决策变量的函数. 线性规划问题的线性规划问题的特征特征是目标函数和约束条件中的函数都是目标函数和约束条件中的函数都是决策变量的线性函数是决策变量的线性函数, 并且约束是必不可少的并且约束是必不可少的 (否则不存在否则不存在有实际意义的解有实际意义的解). 线性规划是指如何最有效或最佳地谋划经济活动线性规划是指如何最有效或最佳地谋划经济活动. 它所研它所研究的问题有究的问题有两类两类： 一类一类是指一定资源的条件下，达到最高产量、最高产值、是指一定资源的条件下，达到最高产量、最高产值、最大利润；最大利润； 一类一类是，任务量

5、一定，如何统筹安排，以最小的消耗去完是，任务量一定，如何统筹安排，以最小的消耗去完成这项任务成这项任务.如最低成本问题、最小投资、最短时间、最短距如最低成本问题、最小投资、最短时间、最短距离等问题离等问题. 前者是求极大值问题，后者是求极小值问题前者是求极大值问题，后者是求极小值问题. 总之总之,线性规划是一定限制条件下线性规划是一定限制条件下, 求目标函数极值的问题求目标函数极值的问题. 本小节介绍什么是线性规划问题，如何将实际本小节介绍什么是线性规划问题，如何将实际问题转化为线性规划模型，线性规划问题的标准形问题转化为线性规划模型，线性规划问题的标准形式以及求解简单线性规划问题的图解法。式

6、以及求解简单线性规划问题的图解法。 用线性规划方法解决实际问题的第一步是要将用线性规划方法解决实际问题的第一步是要将实际问题转化为线性规划模型。下面通过例子说明实际问题转化为线性规划模型。下面通过例子说明如何把具体问题转化为线性规划模型如何把具体问题转化为线性规划模型.某工厂生产甲、乙两种产品某工厂生产甲、乙两种产品.已知生产甲种产品已知生产甲种产品1t需消耗需消耗A种矿石种矿石10t、B种矿石种矿石5t、煤、煤4t；生产乙种产品；生产乙种产品1t需消耗需消耗A种矿石种矿石4t、B种种矿石矿石4t、煤、煤9t.每每1t甲种产品的利润是甲种产品的利润是600元元,每每1t乙种产品的利润是乙种产品

7、的利润是1000元元.工厂在生产这两种产品的计划中要求消耗工厂在生产这两种产品的计划中要求消耗A种矿石不超过种矿石不超过300t、 消耗消耗B种矿石不超过种矿石不超过200t、消耗煤不超过、消耗煤不超过360t.若你是厂长若你是厂长,你应如何安排甲乙两种产品的产量你应如何安排甲乙两种产品的产量(精确到精确到0.1t),才能使利润总额达才能使利润总额达到最大到最大?分分析析问问题题:1.本问题给定了哪些原材料本问题给定了哪些原材料(资源资源)?2.该工厂生产哪些产品该工厂生产哪些产品?3.各种产品对原材料各种产品对原材料(资源资源)有怎样的要求有怎样的要求?4.该工厂对原材料该工厂对原材料(资源

8、资源)有何限定条件有何限定条件?5.每种产品的利润是多少每种产品的利润是多少?利润总额如何计算利润总额如何计算? 原原 材材料料每吨产品消耗的原材料每吨产品消耗的原材料A种矿石种矿石B种矿石种矿石煤煤甲产品甲产品(t)乙产品乙产品(t)1054449原原 材料限材料限 额额300200360利利 润润6001000 xtyt把题中限制条件进行转化：把题中限制条件进行转化：约束条件约束条件10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y. 目标函数目标函数：设生产甲、乙两种产品分别为设生产甲、乙两种产品分别为x t、yt,利润总额为利润总额为z元元解解:

9、设生产甲、乙两种产品分别为设生产甲、乙两种产品分别为xt、yt,利润总额为利润总额为z元元,那么那么10 x+4y3005x+4y2004x+9y360 x0y 0z=600 x+1000y.画画出以上不等式组所表示的可行域出以上不等式组所表示的可行域作出直线作出直线L 600 x+1000y=0.5x+4y=2004x+9y=360由由10 x+4y=3005x+4y=2004x+9y=360600 x+1000y=0M求求得交点得交点M的坐标为的坐标为(12.4,34.8) ，此时，利润此时，利润z=60012.41+1000 34.8=41926答答:应生产甲产品约应生产甲产品约12.4

10、吨，乙产品吨，乙产品34.4吨，能使利润总额达到最大，最大值为吨，能使利润总额达到最大，最大值为 41926元。元。(12.4,34.4)经过可行域上的点经过可行域上的点M时时,目标函数目标函数在在y轴上截距最大轴上截距最大.9030 0 xy10 201075405040此时此时z=600 x+1000y取得最大值取得最大值.48.3429100041.1229360 yx把直线把直线L向右上方平向右上方平移移实际问题实际问题线性规划问题线性规划问题寻找约束条件寻找约束条件建立目标函数建立目标函数列表列表设立变量设立变量转化转化1.约束条件要写全约束条件要写全; 3.解题格式要规范解题格式要

11、规范. 2.作图要准确作图要准确,计算也要准确计算也要准确;注意注意:结论结论 某工厂拥有某工厂拥有A、B、C三种类型的设备，生产甲、乙两种三种类型的设备，生产甲、乙两种产品产品. 每件产品在生产中需要占用的设备机时数，每件产品可每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：以获得的利润以及三种设备可利用的时数如下表所示： 产品产品设备设备甲甲乙乙设备能力设备能力（小时）（小时）A3265B2140C0375利润（元利润（元/件）件）15002500max问题：工厂应如何安排生产可获得最大的总利润？问题：工厂应如何安排生产可获得最大的总利润？设

12、变量设变量xi为第为第i 种种(甲、乙甲、乙)产品的生产件数产品的生产件数(i1，2). 根据题意，两种产品的生产受到设备能力根据题意，两种产品的生产受到设备能力(机时数机时数)的限制的限制. 对设备对设备A，两种产品生产所占用的机时数不能超过，两种产品生产所占用的机时数不能超过65，即，即 3 x1 + 2 x2 65；对设备对设备B，两种产品生产所占用的机时数不能超过，两种产品生产所占用的机时数不能超过40，于是，于是我们可以得到不等式：我们可以得到不等式： 2 x1 + x2 40；对设备对设备C，两种产品生产所占用的机时数不能超过，两种产品生产所占用的机时数不能超过75，于是，于是我们

13、可以得到不等式：我们可以得到不等式： 3 x2 75 ；另外，产品数不可能为负，即另外，产品数不可能为负，即: x1 ，x2 0.同时，我们有一个追求目标，即获取最大利润同时，我们有一个追求目标，即获取最大利润.于是可写出目于是可写出目标函数标函数Z 为相应的生产计划可以获得的总利润：为相应的生产计划可以获得的总利润： Z = 1500 x1 + 2500 x2 .综合上述讨论，在加工时间以及利润与产品产量成线性关系综合上述讨论，在加工时间以及利润与产品产量成线性关系的假设下，把目标函数和约束条件放在一起，可以建立如下的假设下，把目标函数和约束条件放在一起，可以建立如下的线性规划模型的线性规划

14、模型 目标函数目标函数 maxZ =1500 x1+2500 x2 约束条件约束条件 s.t. 3 x1+2 x2 65 2 x1+ x2 40 3 x2 75 x1 , x20这里典型的利润最大化的生产计划问题这里典型的利润最大化的生产计划问题. 例例1.2 靠近某河流有两个化工厂，流经第一化工厂的河流流靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天量为每天500万万m3，在两个工厂之间有一条流量为，在两个工厂之间有一条流量为200万万m3的的支流支流. 两化工厂每天排放某种有害物质的工业污水分别为两化工厂每天排放某种有害物质的工业污水分别为2万万m3和和1.4万万m3. 从第一化工

15、厂排出的工业污水流到第二化工厂以前从第一化工厂排出的工业污水流到第二化工厂以前, 有有20%可以自然净化可以自然净化. 环保要求河流中工业污水含量不能大于环保要求河流中工业污水含量不能大于0.2%. 两化工厂处理工业污水的成本分别为两化工厂处理工业污水的成本分别为1000元元/万万m3和和800元元/万万m3. 现在要问在满足环保要求的条件下现在要问在满足环保要求的条件下, 每厂各应处理多每厂各应处理多少工业污水少工业污水, 使这两个工厂处理工业污水的费用最小使这两个工厂处理工业污水的费用最小.工厂工厂1工厂工厂2200万万m3500万万m3 决策变量：决策变量：x1 , x2分别代表工厂分别

16、代表工厂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例例1.3 捷运公司在下一年度的捷运公司在下一年度的14月份的月份的4个月内拟个月内拟租用仓库堆放物资租用仓库堆

17、放物资. 已知各月份所需仓库面积列于下已知各月份所需仓库面积列于下表表1-2. 仓库租借费用随合同期而定仓库租借费用随合同期而定, 期限越长期限越长, 折扣折扣越大，具体数字见表越大，具体数字见表1-3. 租借仓库的合同每月初都租借仓库的合同每月初都可办理可办理, 每份合同具体规定租用面积和期限每份合同具体规定租用面积和期限. 因此该因此该厂可根据需要厂可根据需要, 在任何一个月初办理租借合同在任何一个月初办理租借合同. 每次每次办理时可签一份合同办理时可签一份合同, 也可签若干份租用面积和租用也可签若干份租用面积和租用期限不同的合同期限不同的合同. 试确定该公司签订租借合同的最优试确定该公司

18、签订租借合同的最优决策决策, 目的是使所租借费用最少目的是使所租借费用最少.月份月份 1 2 3 4所需仓库面积所需仓库面积 15 10 20 12表表1-2表表1-3合同租借期限合同租借期限 1个月个月 2个月个月 3个月个月 4个月个月合同期内的租费合同期内的租费 2800 4500 6000 7300单位：单位：100m2单位单位:元元/100m2解解: : 设设 xij表示捷运公司在第表示捷运公司在第i (i=1 , 2 , 3 , 4)月初签订的租期月初签订的租期为为j (j=1 , 2 , 3 , 4)个月的仓库面积的合同个月的仓库面积的合同(单位为单位为100m2) . 11x1

19、2x13x14x21x22x23x31x32x41x151020121514131211 xxxx10232221141312 xxxxxx1241322314 xxxx20323123221413 xxxxxx2800 z)(41312111xxxx 4500 )(322212xxx 6000 )(2313xx 147300 x 经过上面的讨论，得到下面的经过上面的讨论，得到下面的LP模型：模型： )4 , 1; 4 , 1(012201015.4132231432312322141323222114131214131211jixxxxxxxxxxxxxxxxxxxxxstij)(4500)

20、(2800min32221241312111xxxxxxxz 1423137300)(6000 xxx 目标函数目标函数约束条件约束条件练习：练习：某公司计划制造某公司计划制造A、B两种家电，已知各制造一件两种家电，已知各制造一件A、B产品时分别占用的设备甲、乙的台时，调试时间，调试工序每产品时分别占用的设备甲、乙的台时，调试时间，调试工序每天可用于这两种家电的能力，各售出一件的获利情况如下表所天可用于这两种家电的能力，各售出一件的获利情况如下表所示，问该公司如何安排生产，使获得的利润最大。示，问该公司如何安排生产，使获得的利润最大。AB每天可用能力每天可用能力设备甲（设备甲（h）0515设备

21、乙（设备乙（h）6224调试工序（调试工序（h）115利润（元）利润（元）21解：解：设设A、B的产量分别为的产量分别为x1 , x2 件，则有件，则有 max z = 2x1 + x2s.t. 5x2 15 6x1 + 2x2 24 x1 + x2 5 x1 , x2 0 练习：练习：某药厂生产某药厂生产A、B、C三种药物，可供选三种药物，可供选择的原料有甲、乙、丙、丁，四种原料的成本分别择的原料有甲、乙、丙、丁，四种原料的成本分别是是5元，元，6元，元，7元，元，8元。每公斤不同原料所能提取元。每公斤不同原料所能提取的各种药物的数量（单位：克的各种药物的数量（单位：克/公斤）见下表公斤）见

22、下表 药厂要求每天生产药厂要求每天生产A药恰好药恰好100克，克，B药至少药至少530克，克，C药不超过药不超过160克，要求选配各种原料的数克，要求选配各种原料的数量既满足生产需要，又使总成本最小，试建立此问量既满足生产需要，又使总成本最小，试建立此问题的数学模型题的数学模型. 药名药名原料原料ABC成本（元成本（元/kg）甲甲1525乙乙1416丙丙1517丁丁1628生产量生产量恰好恰好100克克至少至少530克克不超过不超过160克克解：解：设设 x1 , x2 , x3 , x4 分别为原料甲、乙、丙、丁分别为原料甲、乙、丙、丁 的选配数量（单位：公斤），则有的选配数量（单位：公斤）

23、，则有min z =5x1+6x2+7x3+8x4 s . t . x1+ x2+ x3+ x4 = 100 5x1+4 x2+5 x3+ 6 x4 530 2x1+ x2+ x3+ 2 x4 160 x1 , x2 , x3 , x4 0 从以上几个例子中可以归纳出线性规划问题的一般形式：从以上几个例子中可以归纳出线性规划问题的一般形式： 对于一组变量对于一组变量 xj，j = 1 , 2 , , n 取取 Max ( Min ) z = c1x1 + c2x2 + + cnxn ( 1- 1 ) s. t. a11 x1 + a12 x2 + + a1n xn ( = ,) b1 a21

24、x1 + a22 x2 + + a2n xn ( = ,) b2 am1 x1 + am2 x2 + + amn xn ( = ,) bm ( 1- 2 ) x1 , x2 , , xn 0 ( 1- 3 ) 这是线性规划数学模型的一般形式这是线性规划数学模型的一般形式.其中其中. 式式(1-1) 称为称为它只有两种形式：它只有两种形式：Max或或 Min ; 式式(1-2) 称为称为它们表示问题所满足的各种条件它们表示问题所满足的各种条件 , 一般有三种形式：一般有三种形式：“大大于等于于等于”、 “小于等于小于等于”（这两种情况又称不等式约束）或（这两种情况又称不等式约束）或 “等于等于”

25、(又称等式约束又称等式约束)；式；式很很多多情况下决策变量都蕴含了这个假设，它们在表述问题时常常情况下决策变量都蕴含了这个假设，它们在表述问题时常常不一定明确指出，建模时应该注意这个情况。在实际当中，不一定明确指出，建模时应该注意这个情况。在实际当中，有些决策变量允许取任何实数，如温度变量、资金变量等，有些决策变量允许取任何实数，如温度变量、资金变量等，这时不能人为地强行限制其非负这时不能人为地强行限制其非负. 在线性规划模型中在线性规划模型中, 也直接称也直接称 z 为为目标函数目标函数；称；称xj ，j = 1 , 2 , n 为为决策变量；决策变量；称称cj ，j = 1 , 2 , ,

26、 n 为为目标函数系数目标函数系数或或价值系数价值系数或或费用系数；费用系数；称称bi , i = 1 , 2 , , m 为为约束右端约束右端常数常数或简称或简称右端项右端项, 也称也称资源常数；资源常数；称称aij ，i = 1 , 2 , , m ; j = 1 , 2 , , n 为为约束系数约束系数或或技术系数技术系数. 这里，这里，cj ，bi ，aij 均均为常数为常数. 线性规划的数学模型可以表示为下列简洁的形式：线性规划的数学模型可以表示为下列简洁的形式： njjjxczMinMax1)(例如在（例如在（1 . 2）中的第一个式子）中的第一个式子 a11 x1 + a12 x

27、2 + + a1n xn ( = ,) b1 ),2,1(0),2,1(),(1njxmibxajnjijji(1.4).ts可以写成：可以写成：111),(bxanjjj 第二个式子第二个式子a21 x1 + a22 x2 + + a2n xn ( = ,) b2 可以写成：可以写成：212),(bxanjjj 线性规划的数学模型还可以表示为下列矩阵形式或较简洁的线性规划的数学模型还可以表示为下列矩阵形式或较简洁的分量形式分量形式.记向量和矩阵记向量和矩阵 ,21 mbbbb,21 nxxxX,21 ncccC mnmmnnaaaaaaaaaA212222111211为了书写方便，可把列向量

28、记为行向量的转置，如为了书写方便，可把列向量记为行向量的转置，如 X = ( x1，x2，xn )T . 对于对于n 维列向量维列向量X，用符号表示：，用符号表示：X Rn ；A 是是m行行n列的矩阵，称列的矩阵，称 m n 矩阵矩阵. 在这里在这里, 矩阵矩阵A有时表示为：有时表示为： A = ( P1， P2，Pn ) ，其中其中 Pj = ( a1j，a2j，amj )T Rm .于是，线性规划问题可有于是，线性规划问题可有矩阵形式表示矩阵形式表示： XCzMinMaxT )(bAXts),(. 0 X(1.5)和和向量形式表示：向量形式表示： njjjxczMinMax1)( njjj

29、bxPts1),(.njxj,2,10 (1.6)这里，向量的等式与不等式表示所有分量有一致的关系这里，向量的等式与不等式表示所有分量有一致的关系, 即当即当X ，Y Rn 时，时，XY 表示对所有表示对所有i = 1,2, ,n 有有xi yi ;其它其它也类似也类似. 于是，在线性规划模型中，称于是，在线性规划模型中，称 C 为为目标函数系数向量目标函数系数向量或或价值价值系数向量系数向量或或费用系数向量；费用系数向量；称称b为为约束右端常数向量约束右端常数向量或简称或简称右右端项端项, 也称也称资源常数向量；资源常数向量；称称A为为约束系数矩阵约束系数矩阵或或技术系数矩技术系数矩阵阵.可

30、以看出，可以看出，线性规划模型有如下特点：线性规划模型有如下特点：决策变量决策变量x1 , x2 , , xn 表示要寻求的方表示要寻求的方 案，每一组值就案，每一组值就 是一个方案；是一个方案；约束条件是用等式或不等式表述的限制条件；约束条件是用等式或不等式表述的限制条件；一定有一个追求目标，或希望最大或希望最小；一定有一个追求目标，或希望最大或希望最小；目标函数和所有约束条件都是线性的目标函数和所有约束条件都是线性的 例例 把下列线性规划分别用矩阵形式和向量形式表示出来把下列线性规划分别用矩阵形式和向量形式表示出来Max z = 3x1 + 2x2 5x3s. t . x1 3x2 +3x

31、3 4 2x1 + 3x2 +7x3 5x1 , x2 , x3 0,732331 A,321 xxxX,54 b 73,33,21321PPP则线性规划的矩阵形式为：则线性规划的矩阵形式为：XCzMaxT bAXts .0 X 523C 为了讨论的方便，在所有为了讨论的方便，在所有bi 0，i = 1,2, , n 的前提下的前提下, 我我们称以下形式的线性规划问题为线性规划的规范形式：们称以下形式的线性规划问题为线性规划的规范形式：则线性规划的向量形式为则线性规划的向量形式为XCzMaxT bxPxPxPts 331211.0 X.2211tsxcxcxczMaxnn .,2,102211

32、2222212111212111njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn(1.7)XCzMaxT bAXts .0 X(1.8)而称以下的形式为标准矩阵形式：而称以下的形式为标准矩阵形式： XCzMaxT bAXts .0 X(1.9)标准形式：标准形式：矩阵形式：矩阵形式： .2211tsxcxcxczMaxnn .,2,1022112222212111212111njxbxaxaxabxaxaxabxaxaxajmnmnmmnnnn(1.10)可以看出可以看出, 线性规划的线性规划的标准形式有如下标准形式有如下四个特点四个特点：目标最大化、约束为等式、目标最大

33、化、约束为等式、决策变量均非负、右端项非负决策变量均非负、右端项非负.w求极小值的求极小值的目标函数转化：目标函数转化： min f (x) = -max-f (x)= -max z (z = -f(x)w变量取值限制约束的转化：变量取值限制约束的转化： xi 0 做变量代换做变量代换：yi = - xi xi 为为自由变量，做变量代换自由变量，做变量代换： xi = ui - vi ui 0, vi 0w不等式约束转化为等式约束：不等式约束转化为等式约束：引入引入松弛变量松弛变量将将 约束转化为标准形式约束转化为标准形式 x1+x2 10 x1+x2+xs=10，xs 0引入引入剩余变量剩余

34、变量将将 约束转化为标准形式约束转化为标准形式 x1+x2 10 x1+x2 - xs=10，xs 0 将下式转变为标准形式将下式转变为标准形式43212453xxxxzMax 0,953413223183624321432143214321xxxxxxxxxxxxxxxx解：解：目标函数满足要求，变量也满足非负要目标函数满足要求，变量也满足非负要 求；第三个约求；第三个约束条件为等式约束；只须在第一个约束条件引入一个束条件为等式约束；只须在第一个约束条件引入一个“松弛松弛变量变量”将其变为等式，在第二个约束中引入一个将其变为等式，在第二个约束中引入一个“剩余变量剩余变量”将其变为等式约束，所

35、以标准形为：将其变为等式约束，所以标准形为：43212453xxxxzMax 0,9534132231836265432143216432154321xxxxxxxxxxxxxxxxxxxx43212453xxxxzMax 0,953413223183624321432143214321xxxxxxxxxxxxxxxx 将下式转变为标准形式将下式转变为标准形式min z = 3x1 - x2 + 4x3 s.t. x1 - 2x2 + 5x3 0 -2x1 + x2 - 3x3 0 -3x1 - x2 = 0 x1 0, x2 0 , x3 为自由变量为自由变量作变量代换：作变量代换：x2=

36、-y, x3= u - v，w = - z ,引入松弛变量引入松弛变量 x4 和和 x5 ，得标准型为：得标准型为：Max w = -3x1 - y - 4u + 4v s.t. x1+ 2y + 5u - 5v - x4= 0 -2x1 - y - 3u + 3v + x5 = 0 -3x1 + y = 0 x1 0 , y 0 , u 0 , v 0 , x4 0 , x5 0例例1.6 将以下线性规划问题转化为标准形式将以下线性规划问题转化为标准形式 Min f = 3.6 x1 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 6.1 x3 15.7 4.1

37、x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 0 解：解：首先，将目标函数转换成极大化：令首先，将目标函数转换成极大化：令 z = f = 3.6x1 + 5.2x2 1.8x3 ， 其次考虑约束，有其次考虑约束，有2个不等式约束，引进松弛变量个不等式约束，引进松弛变量x4，x5 0.于是，我们可以得到以下标准形式的线性规划问题：于是，我们可以得到以下标准形式的线性规划问题： Max z = 3.6 x1 + 5.2 x2 1.8 x3 s. t. 2.3 x1 + 5.2 x2 6.1 x3 + x4 = 15.7 4.1 x1 + 3.3 x

38、3 x5 = 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 , x4 , x5 0 Min f = 3.6 x1 5.2 x2 + 1.8 x3 s. t. 2.3 x1 + 5.2 x2 6.1 x3 15.7 4.1 x1 + 3.3 x3 8.9 x1 + x2 + x3 = 38 x1 , x2 , x3 0 一、线性规划的图解法（解的几何表示）一、线性规划的图解法（解的几何表示） 对于只有两个变量的线性规划问题，可以在二维直角坐对于只有两个变量的线性规划问题，可以在二维直角坐标平面上作图表示线性规划问题的有关概念，并求解。图解标平面上作图表示线性规划问题的有关

39、概念，并求解。图解法求解线性规划问题的步骤如下：法求解线性规划问题的步骤如下： (1)分别取决策变量分别取决策变量x1 ，x2 为坐标向量建立直角坐标系为坐标向量建立直角坐标系; (2)对每个约束（包括非负约束）条件，先取其等式在坐对每个约束（包括非负约束）条件，先取其等式在坐标系中作出直线标系中作出直线, 通过判断确定不等式所决定的半平面通过判断确定不等式所决定的半平面.各约各约束半平面交出来的区域束半平面交出来的区域(存在或不存在存在或不存在) , 若存在，其中的若存在，其中的点点表示的解表示的解称为此线性规划的称为此线性规划的可行解可行解。这些。这些符合约束限制的点符合约束限制的点集合集

40、合，称为，称为可行集或可行域可行集或可行域. 进行进行(3)；否则该线性规划问题；否则该线性规划问题无可行解无可行解. (3)任意给定目标函数一个值作一条目标函数的等值线任意给定目标函数一个值作一条目标函数的等值线,并确定该等值线平移后值增加的方向并确定该等值线平移后值增加的方向,平移此目标函数的等平移此目标函数的等值线值线,使其达到既与可行域有交点又不可能使值再增加的位使其达到既与可行域有交点又不可能使值再增加的位置置(有时有时交于无穷远处，此时称无有限最优解交于无穷远处，此时称无有限最优解) .若有交点时若有交点时,此目标函数等值线与可行域的交点即最优解此目标函数等值线与可行域的交点即最优

41、解(一个或多个一个或多个). 此目标函数的值即最优值。此目标函数的值即最优值。 图解法简单、直观图解法简单、直观，便于初学便于初学者了解线性规划基本原理和几何意义者了解线性规划基本原理和几何意义；例例1.7 用图解法求解线性规划问题用图解法求解线性规划问题 max z = 50 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 0，x2 02x1+ x2 50 x1 30 20 10 x2 40 50 10 20 30 4x1+3x2 120z = 50 x1+30 x2= 600z = 50 x1+30 x2= 900z = 50 x1+30 x2=

42、1350(15, 20)z*=1350练习：练习：用图解法求解线性规划问题用图解法求解线性规划问题 max z = x1 + 2x2 s.t. x1 + x2 6 2x1 + x2 8 x2 5 x1 0，x2 0o123456x1123456x2 x1 + x2 62x1 + x2 8x2 5z =x1 + 2x2 =2z =x1 + 2x2 =4z =x1 + 2x2 =11(1, 5 ) z*=11 有效与无效有效与无效(紧与松紧与松)约束：与最优解相关约束：与最优解相关的约束为有效的约束为有效(紧紧)约束约束. 最优解：总是在可行域的边界上，一般最优解：总是在可行域的边界上，一般由可行

43、域的极点表示由可行域的极点表示. 可行域：由约束平面围起来的凸多边形可行域：由约束平面围起来的凸多边形区域，可行域内的每一个点代表一区域，可行域内的每一个点代表一 个可个可行解行解.例例 1 . 8 用图解法求解用图解法求解 max z = x1 + x2 s.t. x1 + 2x2 4 x1 - 2x2 5 x1, x2 0 无可行解的线性规划问题无可行解的线性规划问题14235123x1 x2x1 + 2x2 4x1 - 2x2 5例例1 .9 用图解法求解：用图解法求解： max z = 2x1 + x2s.t. x1 + x2 2 x1 - 2x2 0 x1 , x2 0无界的线性规划

44、问题无界的线性规划问题14235123x1 x2x1 + x2 2z = 2x1+x2x1 - 2x2 0 如果目标函数线平行与一个约束线，线性规划如果目标函数线平行与一个约束线，线性规划问题有无穷多最优解。问题有无穷多最优解。例例1 .10 用图解法求解：用图解法求解： max z = 40 x1 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1 0，x2 0 存在无穷多最优解存在无穷多最优解2x1+ x2 50 x1 30 20 10 x2 40 50 10 20 30 4x1+3x2 120z = 40 x1+30 x2图解法的观察（二）图解法的观察（二

45、）如果可行域为空集如果可行域为空集,线性规划线性规划 问题无可行解；问题无可行解；如果目标函数等值线可以无限制地在可行域内如果目标函数等值线可以无限制地在可行域内向改善的方向移动，线性规划问题无界；向改善的方向移动，线性规划问题无界；线性规划问题可能存在无穷多个最优解线性规划问题可能存在无穷多个最优解.1. 线性规划的解线性规划的解2. 线性规划的基与基本可行解线性规划的基与基本可行解3. 线性规划的基本定理线性规划的基本定理1. 线性规划的解线性规划的解 线性规划解的定义：线性规划解的定义：(1)满足线性规划问题所有约束条件的解是该问满足线性规划问题所有约束条件的解是该问题的题的可行解可行解

46、。(2)线性规划问题全部可行解的集合构成线性规线性规划问题全部可行解的集合构成线性规划问题的划问题的可行域可行域。(3)使目标函数达到极值的可行解称为线性规划使目标函数达到极值的可行解称为线性规划问题的问题的最优解最优解。线性规划问题的可行域可记为：线性规划问题的可行域可记为：S = x Ax = b, x 0 如果如果 S 为一空集，线性规划为一空集，线性规划不可行不可行 或或 无可行解无可行解.如果如果 S 不为空集，该线性规划一定有可不为空集，该线性规划一定有可行解行解，但不一定有有界最优解；但不一定有有界最优解；若若 S 为一有界集合，则线性规划一定存为一有界集合，则线性规划一定存在最

47、优解；在最优解；若对任意大的若对任意大的 M 0，都存在可行都存在可行解使得该线性规划的目标函数值解使得该线性规划的目标函数值 z = CTX M, 则该线性规划问题则该线性规划问题无界无界。基的基的定义定义：给定线性规划问题给定线性规划问题 P： max cT x | Ax = b, x 0 A是是 m n 满秩矩阵满秩矩阵, n m，如果如果 B 是其中任是其中任一个一个 m m 满秩子矩阵，则称满秩子矩阵，则称 B 是是 P 的一个的一个基基例如：例如：max z = 3x1+4x2+5x3+2x4 x1+2x2+3x3 3x4 = 5 2 x1+2x2+ x3 +4x4 = 6 x1

48、, x2 , x3 , x 4 0 取取 2221B则则 41223321A为一个为一个 2 4 阶矩阵阶矩阵02422221, B所以所以 A 为为2 4 阶满秩矩阵，阶满秩矩阵，B为为2 2 阶满秩子阶满秩子矩阵，矩阵，B 为线性规划的一个基。为线性规划的一个基。取取 4133C 1232D 4232H都有都有014,04,015 HDC 所以，所以，C、D、H也都是线性规划的基。也都是线性规划的基。基变量与非基变量基变量与非基变量假定假定 B 由由 A 中前中前 m 个列向量构成，约束矩阵可划个列向量构成，约束矩阵可划分为：分为： A = ( B, N )与与基基 B 对应的变量称为对应

49、的变量称为基变量基变量，用，用 XB 表示表示；与非基与非基 N 对应的对应的变量称为变量称为非基变量非基变量,用用 XN 表示表示.例如，在上面的例子中，如果取例如，在上面的例子中，如果取B 为为 2221B则则 4133CN而而 为为x1，x2 的系数，所以的系数，所以x1，x2 2221B为基变量，为基变量，x3，x4 为非基变量。即为非基变量。即若取若取 ，则，则 1232B 4231N则则 B 为为 x2，x3 的系数，所以的系数，所以x2，x3 为基变为基变量，而量，而x1，x4 为非基变量为非基变量. 21xxXB 43,xxXN基本解基本解如果令如果令 XN = 0，则有：则有

50、： AX =( B,N ) (XB , XN) = BXB + NXN = BXB AX = b 等价于等价于 BXB = b，由于由于 B 满秩，满秩， BXB = b 有唯一解有唯一解 ：XB = B-1b 则则 X = (XB , XN ) = (B 1b, 0) 是线性规划是线性规划 P 的的基本解基本解.例如在上例中例如在上例中 max z = 3x1+4x2+5x3+2x4 x1+2x2+3x3 3x4 = 5 2 x1+2x2+ x3 +4x4 = 6 x1 , x2 , x3 , x 4 0 取取 x2 , x3 为基变量，令非基变量为基变量，令非基变量 x1 = x4 = 0

51、上列约束变为：上列约束变为：2x2+3x3 = 5 2x2+ x3 = 6 得得 2141332xx如果取如果取 x1 , x2为基变量，令非基变量为基变量，令非基变量 x3 = x4 = 0上列约束变为：上列约束变为： x1+2x2= 5 2 x1+2x2= 6 2121xx则则TX)0,2/1,4/13,0( 为基本解为基本解.则则TX)0,0,2,1( 为基本解为基本解.如果取如果取 x3 , x4为基变量，令非基变量为基变量，令非基变量 x1 = x2 = 0上列约束变为：上列约束变为：3x3 3x4 = 5 x3 +4x4 = 6 1513153843xx基本可行解与可行基基本可行解

52、与可行基满足非负条件的基本解为满足非负条件的基本解为基本可行解，基本可行解，该该解对应的基为解对应的基为可行基可行基.可行解可行解基本解基本解退化基本可行解与退化基退化基本可行解与退化基 基本可行解中如果存在取零值的基变基本可行解中如果存在取零值的基变量，则该解为量，则该解为退化的基本可行解，退化的基本可行解，该解该解对应的基为对应的基为退化基退化基. 如果基变量都不为零，则基本可行解为如果基变量都不为零，则基本可行解为非退化的，对应的基为非退化的，对应的基为非退化可行基非退化可行基.如果线性规划所有基本可行解都是非退化如果线性规划所有基本可行解都是非退化解，则该问题为解，则该问题为非退化线性

53、规划问题非退化线性规划问题 .线性规划问题可能有唯一最优解，也可能线性规划问题可能有唯一最优解，也可能有无穷多最优解，如果目标函数线恰好与有无穷多最优解，如果目标函数线恰好与某一约束平行时，这类问题就会有无穷多某一约束平行时，这类问题就会有无穷多最优解，我们称这类问题有最优解，我们称这类问题有替代最优解替代最优解.设设 x1, ., xk 是是n维欧氏空间中的维欧氏空间中的 k 个点，若存在个点，若存在 1, ., k，且满足且满足 0 i 1 , i =1, ., k， k ki i=1，使得使得： x = 1 x1 + . + k xk则称则称 x 是是 x1 , . , xk 的的凸组合

54、凸组合.集合集合C En 称为凸集，如果对任意称为凸集，如果对任意 x1, x2 C , 0 1 , 有有 x1 + (1 - ) x2 C .Cx2x1凸集没有凹陷部分，该集合内任取两点连凸集没有凹陷部分，该集合内任取两点连线上的任何点都应该在集合内线上的任何点都应该在集合内. 在凸集中，不能表示为不同点的凸组合的点在凸集中，不能表示为不同点的凸组合的点称为凸集的极点，用严格的定义描述如下称为凸集的极点，用严格的定义描述如下. 设设S为一凸集，且为一凸集，且X S，X1 S，X2 S.对于对于0 1，若，若 X = X1 + (1- ) X2 则必定有则必定有X = X1 = X2 ,则称则

55、称X为为S的一个的一个极点极点. 可以证明，线性规划的可行域以及最优可以证明，线性规划的可行域以及最优解有以下性质：解有以下性质： （1）若线性规划的）若线性规划的可行域非空可行域非空，则可，则可行域行域必定为一凸集必定为一凸集； （2）若线性规划的）若线性规划的可行域非空可行域非空，则至，则至多多有有限个极点有有限个极点； （3）若线性规划）若线性规划有最优解有最优解，则至少有，则至少有一个极点是最优解一个极点是最优解. 这样，求线性规划最优解的问题，从在这样，求线性规划最优解的问题，从在可行域内无限个可行解中搜索的问题转化为可行域内无限个可行解中搜索的问题转化为线性规划问题所有可行解组成的

56、线性规划问题所有可行解组成的集合集合S = x | Ax= b , x 0 是是凸集凸集. 线性规划的可行域是由有限个线性规划的可行域是由有限个(n个个)超半超半空间的交集形成的。如果线性规划问题的可空间的交集形成的。如果线性规划问题的可行域不空，是一个在行域不空，是一个在n 维空间的凸多面体，这维空间的凸多面体，这类凸集又称为类凸集又称为多面凸集多面凸集.在其可行域的有限个极点上搜索的问题在其可行域的有限个极点上搜索的问题.x 是线性规划问题基本可行解的充是线性规划问题基本可行解的充要条件是要条件是 x 为可行域为可行域 S = x | Ax = b, x 0 的的极点极点.本定理给出了线性

57、规划基本可行解与线性本定理给出了线性规划基本可行解与线性规划可行域极点的等价关系，建立了线性规划规划可行域极点的等价关系，建立了线性规划基本解代数和几何意义基本解代数和几何意义 之间的联系之间的联系.定理定理1.3 给定线性规划给定线性规划 LP：max cTx | Ax = b , x 0 A是秩为是秩为m 的的 m n 矩阵。矩阵。(i)若若P存在可行解，则必存在基本可存在可行解，则必存在基本可行解行解.(ii)若若P存在最优解，则必存在最优基存在最优解，则必存在最优基本可行解本可行解. 1. 1. 单纯形方法的推导单纯形方法的推导2. 2. 单纯形计算表单纯形计算表3. 3. 单纯形方法

58、的基本定理单纯形方法的基本定理4. 4. 如何寻找初始可行解如何寻找初始可行解5. 5. 改进单纯形方法改进单纯形方法1.3.1. 单纯形方法推导单纯形方法推导单纯形方法的基本思想单纯形方法的基本思想 从可行域的一个基本可行解从可行域的一个基本可行解( (极点极点) )出发，出发，判别它是否已是最优解，如果不是，寻找下判别它是否已是最优解，如果不是，寻找下一个基本可行解，并使目标函数得到改进，一个基本可行解，并使目标函数得到改进，如此迭代下去，直到找到最优解或判定问题如此迭代下去，直到找到最优解或判定问题无界为止无界为止. .例例1.11 求解线性规划：求解线性规划：max z = 50 x1

59、 + 30 x2 s.t. 4x1 + 3x2 120 2x1 + x2 50 x1, x2 0s.t. 4x1 + 3x2 + x3 = 120 2x1 + x2 + x4 = 50 x1 , x2 , x3 , x4 0 选选 x3 , x4 为基变量为基变量 ,解：解：将原问题转化为标准型模型：将原问题转化为标准型模型： max z = 50 x1+ 30 x2解线性规划可用单纯形法解线性规划可用单纯形法转换为典则形式转换为典则形式 max z = 50 x1 + 30 x2 s.t. x3 = 120 4x1 3x2 x4 = 50 2x1 x2 x1 , x2 , x3 , x4 0

60、(用非基变量表示基变量和目标函数的形式称为关于基的典则形用非基变量表示基变量和目标函数的形式称为关于基的典则形式式)寻找初始可行解：寻找初始可行解：令非基变量为零，令非基变量为零， 得到：得到： X(1) = (0, 0, 120, 50)， z(1) = 0最优性检验最优性检验 : 该解是最优解吗？该解是最优解吗？第一次换基迭代第一次换基迭代 选选 x1入基入基.得到下列不等式关系得到下列不等式关系: x3 = 120 4x1 3x2 0 x4 = 50 2x1 x2 0 简化为：简化为：120 4x1 0 50 2x1 0 选选 x1= min(120/4, 50/2) = 25, 才使上