第1章-线性规划1-2节

1、线性规划是运筹学的一个重要分支。线性规划在理论上比较线性规划是运筹学的一个重要分支。线性规划在理论上比较成熟，在实用中的应用日益广泛与深入。特别是在电子计算成熟，在实用中的应用日益广泛与深入。特别是在电子计算机能处理成千上万个约束条件和决策变量的线性规划问题之机能处理成千上万个约束条件和决策变量的线性规划问题之后，线性规划的适用领域更为广泛了。从解决技术问题的最后，线性规划的适用领域更为广泛了。从解决技术问题的最优化设计到工业、农业、商业、交通运输业、军事、经济计优化设计到工业、农业、商业、交通运输业、军事、经济计划和管理决策等领域都可以发挥作用。它已是现代科学管理划和管理决策等领域都可以发挥

2、作用。它已是现代科学管理的重要手段之一。解线性规划问题的方法有多种，以下仅介的重要手段之一。解线性规划问题的方法有多种，以下仅介绍绍单纯形法单纯形法 。Page 2 LP的数学模型的数学模型 图解法图解法 单纯形法单纯形法 单纯形法的进一步讨论人工变量法单纯形法的进一步讨论人工变量法 LP模型的应用模型的应用Page 3生产和经营管理中经常提出如何合理安排，使人生产和经营管理中经常提出如何合理安排，使人力、物力和财力等各种资源得到充分利用，获得力、物力和财力等各种资源得到充分利用，获得最大的效益，这就是规划问题。最大的效益，这就是规划问题。（1 1）当任务或目标确定后，如何统筹兼顾，合理安排，

3、）当任务或目标确定后，如何统筹兼顾，合理安排，用最少的资源用最少的资源 （如资金、设备、原材料、人工、时间等）（如资金、设备、原材料、人工、时间等）去完成确定的任务或目标去完成确定的任务或目标（2 2）在一定的资源条件限制下，如何组织安排生产获得）在一定的资源条件限制下，如何组织安排生产获得最佳的经济效益（如产品量最多最佳的经济效益（如产品量最多 、利润最大、利润最大. .）Page 4例例1.1 某企业计划生产甲、乙两种产品。这些产品分别要某企业计划生产甲、乙两种产品。这些产品分别要在在A、B、C、D、四种不同的设备上加工。按工艺资料规定，、四种不同的设备上加工。按工艺资料规定，单件产品单件

4、产品在不同设备上加工所需要的台时如下表所示，在不同设备上加工所需要的台时如下表所示， 设设 备备产产 品品 A B C D利润（元）利润（元） 甲甲 2 1 4 0 2 乙乙 2 2 0 4 3 有有 效效 台台 时时 12 8 16 12产品产品乙乙产品产品甲甲Page 5Page 6用数学关系式描述这个问题用数学关系式描述这个问题: :设设x1, x2分别表示计划生产甲、乙两种产品的数量，称它分别表示计划生产甲、乙两种产品的数量，称它们为们为决策变量决策变量（或者简单地称（或者简单地称“变量变量”）。）。 生产甲、乙两种产品的数量生产甲、乙两种产品的数量x1, x2，受到资源拥有量的限受到

5、资源拥有量的限制，这是制，这是约束条件约束条件。即。即x1, x20。Page 7解解：数学模型可写为：数学模型可写为：这是目标函数这是目标函数这是约束条件（资这是约束条件（资源量的限制和产品源量的限制和产品数量非负的限制）数量非负的限制）Page 8 例例 1.2 靠近某河流有两个靠近某河流有两个化工厂化工厂(见图见图1-1)，流经第，流经第一化工厂的河流流量为每一化工厂的河流流量为每天天500万立方米，在两个工万立方米，在两个工厂之间有一条流量为每天厂之间有一条流量为每天200万立方米的支流。万立方米的支流。 图图1-1化工厂化工厂1每天排放含有某种有害物质的工业污水每天排放含有某种有害物

6、质的工业污水2万立方米，万立方米，化工厂化工厂2每天排放的工业污水为每天排放的工业污水为1.4万立方米。从化工厂万立方米。从化工厂1排出排出的污水流到化工厂的污水流到化工厂2前，有前，有20%可自然净化。根据环保要求，可自然净化。根据环保要求，河流中工业污水的含量应不大于河流中工业污水的含量应不大于0.2%。因此两个工厂都需处。因此两个工厂都需处理一部分工业污水。化工厂理一部分工业污水。化工厂1处理污水的成本是处理污水的成本是1000元元/万立万立方米方米,化工厂化工厂2处理污水的成本是处理污水的成本是800元元/万立方米。万立方米。Page 9设设: 112(2)22500100020.8(

7、2)(1.4)27001000 xxx经第 工厂前的水质要求：经第 工厂后的水质要求：问问:在满足环保要求的条件下，每厂各应处理多少工业污水，在满足环保要求的条件下，每厂各应处理多少工业污水，使两个工厂处理工业污水的总费用最小。使两个工厂处理工业污水的总费用最小。Page 100,4 . 126 . 18 . 018001000min212121121xxxxxxxxxz约束条件目标函数得到本问题的数学模型为：得到本问题的数学模型为：Page 11例例1.3 捷运公司在下一年度的捷运公司在下一年度的1-41-4月的月的4 4个月内拟租用仓库个月内拟租用仓库堆放物资。已知各月份所需仓库面积列于表

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

9、使所付租借费用最小。合同的最优决策，目的是使所付租借费用最小。第一节第一节 线性规划问题的数学模型线性规划问题的数学模型Page 12第一节第一节 线性规划问题的数学模型线性规划问题的数学模型 例例2中若用变量中若用变量 xij 表示捷运公司在表示捷运公司在第第 i (i=1, , 4)个月初签个月初签订的租借期为订的租借期为 j ( j=1, , 4)个月的仓库面积的合同个月的仓库面积的合同。因。因5月份月份起该公司不需要租借仓库，故起该公司不需要租借仓库，故x24，x33，x34，x42，x43，x44均均为零。该公司希望总的租借费用为最小，故有如下数学模型为零。该公司希望总的租借费用为最

10、小，故有如下数学模型：Page 13min 2800()4500()6000()7300151020120 ( =1,.,4; =1,.,4)112131411222321323141112131412131421222313142223313214233241ijz=x +x +x +x+x +x +x+x +x+xx +x +x +xx +x +x +x +x +xx +x +x +x +x +xx +x +x +xxij约束条件约束条件 s.t.min：minimize ， “最小化最小化”第一节第一节 线性规划问题的数学模型线性规划问题的数学模型目标函目标函数数Page 14 l每一个

11、线性规划问题都用一组每一个线性规划问题都用一组决策变量决策变量 表表示某一方案示某一方案，这组决策变量的值代表一个具体方案。一，这组决策变量的值代表一个具体方案。一般这些变量的取值是般这些变量的取值是非负非负且连续的；且连续的；l都有关于各种资源和都有关于各种资源和资源使用情况的技术数据资源使用情况的技术数据，创造新创造新价值的数据价值的数据；l存在存在可以量化的约束条件可以量化的约束条件，这些约束条件可以用一组线，这些约束条件可以用一组线性等式或线性不等式来表示性等式或线性不等式来表示; ;l都有一个达到某一目标的要求都有一个达到某一目标的要求，可用决策变量的线性函，可用决策变量的线性函数数

12、( (称为称为目标函数目标函数) )来表示。按问题的要求不同，要求目来表示。按问题的要求不同，要求目标函数实现最大化或最小化。标函数实现最大化或最小化。nx,x,x21; (1,;1,)ijjacim jn上述两个问题具有的共同特征：上述两个问题具有的共同特征：Page 15决策变量决策变量： 是问题中要确定的未知量。是问题中要确定的未知量。目标函数目标函数 ： 是决策变量的函数是决策变量的函数, 按优化目标是最大、还是按优化目标是最大、还是最小最小, 分别加分别加max or min。约束条件约束条件：指决策变量取值所受到的各种资源条件的限制。：指决策变量取值所受到的各种资源条件的限制。Pa

13、ge 161 12211 1122111 1221max (min) () () 00nnnnmmmnnmnzc xc xc xa xa xa xba xaxaxbxx 或或，或，11 max (min) z = (, ) (1 2) 0 ( 1 2)njjjnijjijjc xa xbimxjn或或简写为：简写为：Page 17 线性规划问题的标准形式线性规划问题的标准形式minjxbxatsxcZjnjijijnjjj, 2 , 1, 2 , 1, 0.max11 特点：特点：(1) 目标函数求最大值（有时求最小值）目标函数求最大值（有时求最小值）(2) 约束条件都为约束条件都为，且右端常

14、数项，且右端常数项(3) 决策变量决策变量xj为非负。为非负。Page ax0,1, 2,;1, 2,njjjjnjjjm jnmzC XP xbxjnCcccaxbaxbXPbjnaxb 目 标 函 数 ：约 束 条 件 ：用向量形式表示的标准形式线性规划用向量形式表示的标准形式线性规划线性规划问题的其他表示形式线性规划问题的其他表示形式Page 19用矩阵形式表示的标准形式线性规划用矩阵形式表示的标准形式线性规划1111211m12max0,;0b0b0b,nnmmnTnzCXAXbXaaAP PPaaXxxx 目标函数：约束条件：系数矩阵：零向量：；资源向量：决

15、策变量向量：Page 20 目标函数的转换目标函数的转换 如果是求极小值，即如果是求极小值，即 。此时，可将目标函数乘以。此时，可将目标函数乘以(- (-1)1)，可化为求极大值问题。，可化为求极大值问题。 jjxczmin也就是：令也就是：令 ，可得到上式。，可得到上式。zz maxmax()jjzzc x即即 若存在取值无约束的变量若存在取值无约束的变量 ，可令，可令 其中：其中：jxjjjxxx , 0jjxx 无约束无约束变量的变换变量的变换(2) 如何将一般线性规划转化为标准形式的线性规划如何将一般线性规划转化为标准形式的线性规划Page 21 约束方程的转换：由不等式转换为等式。约

16、束方程的转换：由不等式转换为等式。 ijijbxa0 iniinjijxbxxa称为松弛变量称为松弛变量 ijijbxa0 iniinjijxbxxa称为剩余变量称为剩余变量 变量变量 的变换：的变换：jjxx 0 jx 若约束条件右端的若约束条件右端的bi00jx 可令可令显然显然只需在所在式子的两端乘于只需在所在式子的两端乘于-1Page 22例例1.3 将下列线性规划问题化为标准形式将下列线性规划问题化为标准形式123123123123123m in235 7 42325,0, zxxxxxxxxxxxxxxx 无 约 束用用 替换替换 ，且，且 解解:（）因为（）因为 x3无符号要求无

17、符号要求 ，即，即x3取正值也可取负值，标准取正值也可取负值，标准型中要求变量非负，所以型中要求变量非负，所以33xx 3x0,33 xxPage 23(2) 第一个约束条件是第一个约束条件是“”号，在号，在“”左端加入松驰变量左端加入松驰变量x4，x4 0, 化为等式；化为等式；(3) 第二个约束条件是第二个约束条件是“”号，在号，在“”左端减去剩余变量左端减去剩余变量x5，x50；(4) 第第3个约束方程右端常数项为个约束方程右端常数项为-5，方程两边同乘以，方程两边同乘以(-1),将右将右端常数项化为正数；端常数项化为正数； (5) 目标函数是最小值，为了化为求最大值，令目标函数是最小值

18、，为了化为求最大值，令z=-z,得到得到max z=-z，即当，即当z达到最小值时达到最小值时z达到最大值，反之亦然达到最大值，反之亦然;Page 2412334512334123351233123345max23()005() 7 () 252() 5,0 zxxxxxxxxxxxxxxxxxxxxx xxxxx标准形式如下：标准形式如下：Page 2511max(1)(1,2,)(2)s.t0,1,2,(3)njjjnijjijjZc xa xbimxjn线性规划问题线性规划问题求解线性规划问题，就是从满足约束条件求解线性规划问题，就是从满足约束条件(2)、(3)的方程组的方程组中找出一个

19、解，使目标函数中找出一个解，使目标函数(1)达到最大值。达到最大值。Page 26 可行解可行解：满足约束条件、的解为可行解。所有可行：满足约束条件、的解为可行解。所有可行解的集合为解的集合为可行域可行域。 最优解最优解：使目标函数达到最大值的可行解称为最优解使目标函数达到最大值的可行解称为最优解。 基：基：设设A为约束条件的为约束条件的mn阶阶系数矩阵系数矩阵(mn)，其秩，其秩为为m，B是矩阵是矩阵A中中m阶满秩子矩阵（阶满秩子矩阵（ B 0），称），称B是规是规划问题的一个基。设：划问题的一个基。设：) (11111mmmmmppaaaaB 称称 B中每个列向量中每个列向量Pj ( j

20、= 1 2 m) 为为基向量基向量。与基向量。与基向量Pj 对应的变量对应的变量xj 为为基变量基变量。除基变量以外的变量为。除基变量以外的变量为非基变量非基变量。Page 27 基解：基解：对某对某一确定的基一确定的基B，令非基变量等于零，由约束，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变条件方程解出基变量，称这组解为基解。在基解中变量取非量取非0值的个数不大于方程数值的个数不大于方程数m，基解的总数不超过，基解的总数不超过 基可行解：基可行解：满足变量非负约束条件的基解，简称基可满足变量非负约束条件的基解，简称基可行解。行解。 可行基：可行基：对应于基可行解的基

21、称为可行基。对应于基可行解的基称为可行基。mnC非可行解非可行解可可行行解解基解基解基可行解基可行解Page 28例例1 考虑问题考虑问题5 , 1, 052222. .max52142132121jxxxxxxxxxxtsxxzj系数矩阵系数矩阵1001101021001121000100011B1010110022B,)5 , 22 , 0 , 0()1(1TXB，对应的基解为，对应的基解为TXB)6 , 3 , 0 , 0 , 1()2(2不是基可行解。基基Page 29线性规划问题的求解方法线性规划问题的求解方法一一 般般 有有两种方法两种方法图图 解解 法法单纯形法单纯形法两个变量、

22、直角坐标两个变量、直角坐标三个变量、立体坐标三个变量、立体坐标适用于任意变量、但必需将适用于任意变量、但必需将一般形式变成标准形式一般形式变成标准形式下面我们分析一下简单的情况下面我们分析一下简单的情况只有两个只有两个决策变量的线性规划问题，这时决策变量的线性规划问题，这时可以通过在可以通过在平面上作图的方法求解平面上作图的方法求解。图解法具有简单、。图解法具有简单、直观、便于初学者直观地了解线性规划基本直观、便于初学者直观地了解线性规划基本原理和几何意义等优点。原理和几何意义等优点。Page 30max Z = 2X1 + X2 X1 + 1.9X2 3.8 X1 - 1.9X2 3.8s.

23、t. X1 + 1.9X2 10.2 X1 - 1.9X2 -3.8 X1 ，X2 0例例1.5 用图解法求解线性规划问题用图解法求解线性规划问题Page 31x1x2oX1 - 1.9X2 = 3.8()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8 ()X1 + 1.9X2 = 10.2()4 = 2X1 + X2 20 = 2X1 + X2 17.2 = 2X1 + X2 11 = 2X1 + X2 Lo： 0 = 2X1 + X2 （7.6，2）Dmax Zmin Z此点是唯一最优解，此点是唯一最优解，且最优目标函数值且最优目标函数值 max Z=17.2可行域可行域max Z = 2X1 + X2Page 32max Z=3X1+5.7X2x1x2oX1 - 1.9X2 = 3.8 ()X1 + 1.9X2 = 3.8()X1 - 1.9X2 = -3.8()X1 + 1.9X2 = 10.2 ()（7.6，2）DL0： 0=3X1+5.7X2 max Z（3.8，4）34.2 = 3X1+5.7X2 蓝色线段上的所有点都是最蓝色线段上的所有点都是最优解这种情形为有无穷多最优解这种情形为有无穷多最优解，但是最优目