第1章 线性规划

1、运 筹 学在英国称为在英国称为“Operational Research”Operational Research”，其他英语国家称为，其他英语国家称为“Operations Research”Operations Research”，直译直译“作业研究作业研究”或或“操作研究操作研究”意译意译运筹学，取运筹学，取“运筹帷幄之中，决胜千里之外运筹帷幄之中，决胜千里之外” ” 之意之意。在英国称为在英国称为“Operational Research”Operational Research”，其他英语国家称为，其他英语国家称为“Operations Research”Operations Res

2、earch”，直译直译“作业研究作业研究”或或“操作研究操作研究”意译意译运筹学，取运筹学，取“运筹帷幄之中，决胜千里之外运筹帷幄之中，决胜千里之外” ” 之意之意。“田忌赛马”故事 田忌与齐王赛马，约定每胜一马得千金，各按马力强弱，以强、中、弱的先后顺序捉对较量，齐王的马都比较好，田忌的三匹马都略逊一筹，因而比赛输了。 异日又赛，田忌一改常策，以弱、强、中的出场次序分对齐王的强、中、弱三马，终以一负两胜赢得千金。之后的思考博弈之前的故事，到此就截止了，后人都夸田忌有对策。可如果事情继续发展，接下来会怎样呢，齐王输了，肯定会仔细分析，为什么输呢，推断出田忌的对策，然后想到下回再赛马，该如何排兵

3、布阵，安排顺序呢。如果田忌足够聪明，他应该也想到，齐王这回输了，肯定会分析输的原因，然后会采取什么对策呢。如此双方都进行算计。最后结局如何呢！ 哥尼斯堡的七桥”故事 18世纪著名古典数学问题之一。在哥尼斯堡，普雷格尔河流经此镇，奈发夫岛位于河中，共有7座桥横跨河上，把全镇连接起来。当地居民热衷于一个难题：是否存在一条路线，可不重复地走遍七座桥，每座桥只能经过一次而且起点与终点必须是同一地点。这就是柯尼斯堡七桥问题柯尼斯堡七桥问题。 七桥所成之图形中，没有一点含有偶数条数，因此上述的任务无法完成 把一个实际问题抽象成合适的“数学模型”。这种研究方法就是“数学模型方法数学模型方法”。这并不需要运用

4、多么深奥的理论，但想到这一点，却是解决难题的关键。 运筹学的工作步骤运筹学的工作步骤p 提出和形成问题提出和形成问题p 建立模型建立模型p 求解求解p 检验检验p 实施实施第一章第一章 线性规划的基本概念线性规划的基本概念p 线性规划问题及其数学模型线性规划问题及其数学模型p 线性规划的图解法线性规划的图解法p 线性规划的标准形式线性规划的标准形式p 标准型线性规划的解的概念标准型线性规划的解的概念p 线性规划的基本理论线性规划的基本理论n 问题的提出：问题的提出： 在生产管理的经营活动中，通常需要对在生产管理的经营活动中，通常需要对“有限的有限的资源资源”寻求寻求“最佳最佳”的利用或分配方式

5、。的利用或分配方式。l有限资源：劳动力、原材料、设备或资金等有限资源：劳动力、原材料、设备或资金等 l最佳：有一个标准或目标，使利润达到最大或成本最佳：有一个标准或目标，使利润达到最大或成本达到最小。达到最小。 有限资源的合理配置有两类问题有限资源的合理配置有两类问题l如何合理的使用有限的资源，使生产经营的效益达如何合理的使用有限的资源，使生产经营的效益达到最大；到最大；l在生产或经营的任务确定的条件下，合理的组织生在生产或经营的任务确定的条件下，合理的组织生产，安排经营活动，使所消耗的资源数最少。产，安排经营活动，使所消耗的资源数最少。 p线性规划问题及其数学模型线性规划问题及其数学模型 与

6、规划问题有关的数学模型总有两部分组成与规划问题有关的数学模型总有两部分组成：l约束条件：反映了有限资源对生产经营约束条件：反映了有限资源对生产经营活动的种种约束，或者生产经营必须完成的活动的种种约束，或者生产经营必须完成的任务；任务；l目标函数：反映生产经营者在有限资源目标函数：反映生产经营者在有限资源条件下希望达到的生产或经营的目标。条件下希望达到的生产或经营的目标。例，例，某制药厂生产甲、乙两种药品，生产这两种药品要消某制药厂生产甲、乙两种药品，生产这两种药品要消耗某种维生素。生产每吨药品所需要的维生素量，所占用的耗某种维生素。生产每吨药品所需要的维生素量，所占用的设备时间，以及该厂每周可

7、提供的资源总量如下表所示：设备时间，以及该厂每周可提供的资源总量如下表所示：每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤） 30302020160160设备（台班）设备（台班） 5 51 11515已知该厂生产每吨甲、乙药品的利润分别为已知该厂生产每吨甲、乙药品的利润分别为5 5万元和万元和2 2万万元。但根据市场需求调查的结果，甲药品每周的产量不应超元。但根据市场需求调查的结果，甲药品每周的产量不应超过过4 4吨。问该厂应如何安排两种药品的产量才能使每周获得吨。问该厂应如何安排两种药品的产量才能使每周获得的利润最大？的利润最大？ 定义定义x x1

8、 1为生产甲种药品的计划产量数，为生产甲种药品的计划产量数，x x2 2为生产乙种药品的计划产量数。为生产乙种药品的计划产量数。目标：目标： 使总利润使总利润 Z=5xZ=5x1 1+2x+2x2 2 极大化极大化 约束：约束： 每周资源总量的限制，每周资源总量的限制， 30 x30 x1 1+20 x+20 x2 2160160 5x5x1 1+ x+ x2 2 1515甲种药品每周产量不应超过甲种药品每周产量不应超过4 4吨的限制吨的限制 x x1 144计划生产数不可能是负数，计划生产数不可能是负数， x x1 10 x0 x2 200每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总

9、量 甲甲乙乙维生素（公斤）维生素（公斤） 30302020160160设备（台班）设备（台班） 5 51 11515单位利润（万元）单位利润（万元） 5 5 数学模型为数学模型为 s.t.s.t. （subject to)subject to) (such that) (such that) 这是一个如何合理的使用有限的资源，使生产经营的效益达到最大这是一个如何合理的使用有限的资源，使生产经营的效益达到最大的数学规划问题。的数学规划问题。 在满足一组约束条件的限制下，寻求决策变量在满足一组约束条件的限制下，寻求决策变量x x1 1，x x2 2的决策值，使目的决策值，使目标函数达到最大值。标函

10、数达到最大值。121212112maxZ=5x +2x30 x20 x1605xx15x4x0,x0每吨产品的消耗每吨产品的消耗 每周资源总量每周资源总量 甲甲乙乙维生素（公斤）维生素（公斤） 30302020160160设备（台班）设备（台班） 5 51 11515单位利润（万元）单位利润（万元） 5 5例：例：某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料某化工厂根据一项合同要求为用户生产一种用甲、乙两种原料混合配制而成的特种产品。已知甲、乙两种原料都含有混合配制而成的特种产品。已知甲、乙两种原料都含有A A、B B、C C三种三种化学成分，两种原料分别所含三种化学成分的百分比含量

11、，以及按合化学成分，两种原料分别所含三种化学成分的百分比含量，以及按合同规定的产品中三种化学成分的最低含量如下表所示：同规定的产品中三种化学成分的最低含量如下表所示： 已知甲、乙两种原料的成本分别是每公斤已知甲、乙两种原料的成本分别是每公斤3 3元和元和2 2元，厂方希望元，厂方希望总成本达到最小，问如何配置该产品？总成本达到最小，问如何配置该产品？ 原料原料化学成分含量（化学成分含量（% %） 产品中化学成分的最低含量产品中化学成分的最低含量（% %） 甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5化学成分化学成分定义定义x x1 1，x x2 2分别为

12、每公斤产品中甲，乙两种原料的数量，分别为每公斤产品中甲，乙两种原料的数量，目标：使总成本目标：使总成本 Z=3xZ=3x1 1+2x+2x2 2 极小化极小化 约束：配料平衡条件，约束：配料平衡条件， x x1 1+x+x2 2=1=1产品中产品中A A、B B、C C三种化学成分的最低含量三种化学成分的最低含量 12x12x1 1+3x+3x2 244 2x2x1 1+3x+3x2 222 3x3x1 1+15x+15x2 255非负性条件非负性条件 x x1 10,x0,x2 200 原料原料化学成分含量（化学成分含量（% %） 产品中化学成分的最低含量产品中化学成分的最低含量（% %）

13、甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5单位成本（元）单位成本（元）化学成分化学成分 数学模型：数学模型： s.t.s.t. 这是一个原料配制问题，是在生产任务确定的条件下，合理的组织这是一个原料配制问题，是在生产任务确定的条件下，合理的组织 生产，使所消耗的资源数最少的数学规划问题。生产，使所消耗的资源数最少的数学规划问题。 满足一组约束条件的同时，寻求变量满足一组约束条件的同时，寻求变量x x1 1和和x x2 2的值使目标函数取得最小的值使目标函数取得最小 值。值。 原料原料化学成分含量（化学成分含量（% %） 产品中化学成分的最低含量（产品中

14、化学成分的最低含量（% %） 甲甲乙乙A A12123 34 4B B2 23 32 2C C3 315155 5单位成本（元）单位成本（元）化学成分化学成分121212121212minZ=3x +2xxx112x3x42x3x23x15x0 x0,x0n 线性规划的一般数学模型线性规划的一般数学模型 线性规划模型的特征：线性规划模型的特征：（1 1）用一组决策变量）用一组决策变量x x1 1，x x2 2，x xn n表示方案，且在一般情况下，表示方案，且在一般情况下，变量的取值是非负的。变量的取值是非负的。（2 2）有一个目标函数，这个目标函数可表示为这组变量的线）有一个目标函数，这个目

15、标函数可表示为这组变量的线性函数。性函数。（3 3）存在若干个约束条件，约束条件用决策变量的线性等式）存在若干个约束条件，约束条件用决策变量的线性等式或线性不等式来表达。或线性不等式来表达。（4 4）要求目标函数实现极大化（）要求目标函数实现极大化（maxmax）或极小化（）或极小化（minmin）。）。满足上述满足上述4 4个特征的规划问题称为线性规划问题个特征的规划问题称为线性规划问题 线性规划的模型的一般形式线性规划的模型的一般形式: : 目标函数目标函数 满足约束条件满足约束条件 通常称通常称 为决策变量，为决策变量， 为价值系数，为价值系数， 为消耗系数为消耗系数, , 为资源限制系

16、数。为资源限制系数。 1122nnmax(min)Z=c x +c x +c x1111221nn12112222nn2m11m22mnnm12n a xa xa x(,)b a xa xa x(,)b axaxax(,)b x ,x ,x0 12nx ,x ,x12nc ,c ,c1112mna ,a ,a12mb ,b ,bp 线性规划的图解法线性规划的图解法 适用于求解两个变量的线性规划问题适用于求解两个变量的线性规划问题n 图解法的基本步骤图解法的基本步骤利用例利用例1 1说明图解法的主要步骤，说明图解法的主要步骤， 例例1 1的数学模型为的数学模型为 s.t. 121212112ma

17、xZ5x2x30 x2 0 x160 5xx15 x4x0, x0O51015x1x1=4x25101AB( 2, 5)CZ5x1+x2=1530 x1+20 x2=1605x1+2x2=5121212112maxZ5x2x30 x2 0 x160 5xx15 x4x0, x012ZZZ=5 2xx，（ ，） 线性规划图解法的基本步骤：线性规划图解法的基本步骤：（1 1）建立以）建立以x x1 1,x,x2 2为坐标轴的直角坐标系，画出线性规划为坐标轴的直角坐标系，画出线性规划 问题的可行域问题的可行域, ,（2 2）求目标函数）求目标函数 Z=CZ=C1 1x x1 1+C+C2 2x x2

18、 2 的梯度的梯度Z =Z =（c c1 1,c,c2 2）, ,（3 3）任取等值线）任取等值线 C C1 1x x1 1+C+C2 2x x2 2=Z=Z0 0, , 沿梯度沿梯度Z Z正方向平移正方向平移, , （若是极小化问题，则沿负梯度方向（若是极小化问题，则沿负梯度方向- -Z Z平移），平移）， 求等直线将离未离可行域时与可行域的交点。求等直线将离未离可行域时与可行域的交点。（4 4）若交点存在，则该点坐标就是最优解）若交点存在，则该点坐标就是最优解 。*Xn 图解法的几种可能结果图解法的几种可能结果 (1(1）有唯一最优解，如例）有唯一最优解，如例1 1。（2 2）有无穷多最优

19、解）有无穷多最优解 如例如例1 1中的目标函数设为中的目标函数设为 maxZ=10 xmaxZ=10 x1 1+2x+2x2 2 则目标函数等值线则目标函数等值线10 x10 x1 1+2x+2x2 2=Z =Z 与第二约束与第二约束 5x5x1 1+x+x2 21515 的边界线平行。将等值线沿梯度的边界线平行。将等值线沿梯度Z =Z =（1010，2 2）正方向平移）正方向平移 至至B B点时与可行域点时与可行域OABCOABC的整条边界线的整条边界线ABAB重合。重合。 这表明线段这表明线段ABAB上的每一点都使目标函数取得同样的最大值，上的每一点都使目标函数取得同样的最大值， 因而都是

20、最优解。因而都是最优解。O51015x1x1=4x25101AB（2，5）CZ5x1+x2=1530 x1+20 x2=16010 x1+2x2=5212xx10maxZ12ZZZ=2xx，（10，）例例5 5，试用图解法求解下列线性规划问题试用图解法求解下列线性规划问题 st.（3 3） 无界解（或称无最优解）无界解（或称无最优解） 无界解是指线性规划问题的最优解无界。无界解是指线性规划问题的最优解无界。若是极大化问题，则可使目标函数值若是极大化问题，则可使目标函数值Z+,Z+, 极小化问题极小化问题 则可使目标函数值则可使目标函数值Z-Z-， 有无界解的线性规划问题的可行域通常是无界区域，

21、但反之有无界解的线性规划问题的可行域通常是无界区域，但反之则不必然。则不必然。12121212minZ3x2x-2xx2 x -3x3 x0,x0 -1 O24x1x224-Z=(3,2)-2x1+x2=2x1-3x2=3-1 O3312121212minZ3x2x-2xx2 x -3x3 x0,x012ZZZ=2xx，（-3,- ）（4 4）无可行解）无可行解 某些线性规划问题的可行域是空集，既不存在满足某些线性规划问题的可行域是空集，既不存在满足所有约束条件的点，这时问题无可行解，当然更谈不上所有约束条件的点，这时问题无可行解，当然更谈不上最优解了。最优解了。 在实际中出现这种情况可以认为

22、资源条件无法满足在实际中出现这种情况可以认为资源条件无法满足人们的要求，既不存在可行方案。人们的要求，既不存在可行方案。 n 标准线性规划模型标准线性规划模型 线性规划问题的标准形式：线性规划问题的标准形式： s.t s.t 其中其中(1.1)(1.1)为目标函数，为目标函数，(1.2)(1.2)为约束条件，为约束条件，(1.3)(1.3)为非负条件，为非负条件， 为称呼方便，有时将为称呼方便，有时将(1.3)(1.3)也称为约束条件。也称为约束条件。（1.21.2） （1.31.3）p线性规划的标准形式线性规划的标准形式（1.11.1）1122nn1111221nn12112222nn2 m

23、11m22mnnm 12nmaxZ=c x +c x +c xa x +a x +a x =ba x +a x +a x =bax +ax +ax =b x ,x ,x0l紧凑格式：紧凑格式： s.t.s.t.l向量格式：向量格式： s.t.s.t. 其中其中 称为价值向量，称为价值向量， 为决为决策变量向量，策变量向量， 为决策变量为决策变量x xj j所对应的消耗系数所对应的消耗系数向量，向量， 为资源向量。为资源向量。njjj=1maxZ=C xnjjj=1jP x =bx0, j=1,2,nmaxZ=CXnijjij=1ja x =b , i=1,2,mx0, j=1,2,n12nC=

24、(c ,c ,c )12nX=(x ,x ,x )Tj1j2jmjP =(a ,a ,a )T12mb=(b ,b ,b )TmaxZ=CXAX=bX011121n21222nm1m2mnaa.aaa.aA=.aa.al矩阵格式：矩阵格式：其中其中 为为mn阶矩阵阶矩阵 为价值向量，为价值向量， 为决策变量向量，为决策变量向量， 为资源向量。为资源向量。12nC=(c ,c ,c )12nX=(x ,x ,x )T12mb=(b ,b ,b )Tn非标准形式线性规划问题的标准化非标准形式线性规划问题的标准化（1 1）极大化与极小化）极大化与极小化 ： 若若 ，令，令 ，则有，则有 原目标函数原

25、目标函数 。(2)(2)线性不等式与线性等式：线性不等式与线性等式： 其中其中 为非负松弛变量，为非负松弛变量， 其中其中 为非负剩余变量。为非负剩余变量。 njjj=1minZ=C xn+ixn+kxZ = -Znjjj=1maxZ =max( -Z)= -maxZ= -C xnjjj=1minZmaxZ = -C xnnijjiijjn+iij=1j=1a xb a x +x=bnnkjjkkjjn+kkj=1j=1a xb a x - x=b (3) (3) 非负变量与符号不受限制的变量非负变量与符号不受限制的变量 若若 x xi i的符号不受限制，则可引进非负变量的符号不受限制，则可引

26、进非负变量x xi1i1,x,xi2i2，令，令 x xi i = x= xi1i1-x-xi2i2，这样就可以使线性规划里所有的变量都转化为有非负限，这样就可以使线性规划里所有的变量都转化为有非负限制的变量。制的变量。 例例6 6，将下述线性规划问题化为标准型，将下述线性规划问题化为标准型 123123123123123minZ=-x +2x -3x xxx7 x -xx2 3x -x -2x5x0,x0,x解：令解：令, ,可将目标函数化为可将目标函数化为maxmax型，型，令令, ,其中其中1245124 56124571245124567maxZ = x -2x +3x -3x xxx

27、 -xx =7 x -xx -x -x =23x -x -2x +2x 5x ,x ,x ,x ,x ,x0Z = -Z345x =x -x45x0, x0.考虑一个标准的线性规划问题：考虑一个标准的线性规划问题： s.t s.t 其中为其中为n n维行向量，维行向量， 是是n n维列向量，维列向量， 是是m m维列向量，维列向量， 是是m mn n阶矩阵，假定满足阶矩阵，假定满足mnmn，且，且( ()=m)=m，maxZCX (1.4)AXb (1.5) X0 (1.6)p标准型线性规划的解的概念标准型线性规划的解的概念 线性规划问题解的概念：线性规划问题解的概念： (1) (1) 可行解

28、。满足约束条件可行解。满足约束条件(1.5)(1.5)，(1.6)(1.6)的解的解称为线性规划问题的可行解。称为线性规划问题的可行解。可行解集称为线性规划问题的可行域。可行解集称为线性规划问题的可行域。(2) (2) 最优解。使目标函数（最优解。使目标函数（1.4)1.4)达到最优值的的可行解称为最优解，达到最优值的的可行解称为最优解，最优解常用最优解常用 表示。表示。(3) (3) 基。若是中基。若是中m mm m阶非奇异矩阵，即阶非奇异矩阵，即| |0|0，则称是线性规，则称是线性规划问题的一个基。划问题的一个基。 (1.4) CXmaxZAXb (1.5) X0 (1.6)*X12nX

29、=(x ,x ,x )TD= X / AX=b ,X0 若是线性规划问题的一个基，那么一定是由若是线性规划问题的一个基，那么一定是由m m个线性无关的列个线性无关的列向量组成，不失一般性，可设向量组成，不失一般性，可设 称称 为基向量，为基向量，与基向量相对应的变量称为基变量。与基向量相对应的变量称为基变量。 一个线性规划的基通常不是唯一的，但是基的个数也不会超过一个线性规划的基通常不是唯一的，但是基的个数也不会超过 个。一旦线性规划的基确定了，那么相应的基向量、基变量和非个。一旦线性规划的基确定了，那么相应的基向量、基变量和非 基变量也就确定了。基变量也就确定了。11121m21222m12

30、mm1m2mmaa.aaa.aB=(P,P ,P ).aa.amnCj1j2jmjp =(a ,a ,a), (j=1,2,m)jPjx , (j=1,2,m)( (4) 4) 基本解。设基本解。设B B是线性规划的一个基，若令是线性规划的一个基，若令n-mn-m个非基变量等于个非基变量等于0 0，则，则所得的方程组所得的方程组=b=b的解称为线性规划问题的一个基本解（简称基解）。的解称为线性规划问题的一个基本解（简称基解）。 有一个基就可以求得一个基本解。有一个基就可以求得一个基本解。 由基的有限性可知，基本解的个数也不会超过由基的有限性可知，基本解的个数也不会超过 个。个。 由于基本解中的

31、非零分量可能是负数，所以基本解不一定是可行的。由于基本解中的非零分量可能是负数，所以基本解不一定是可行的。(5) (5) 基本可行解。满足非负条件的基本解称为基本可行解基本可行解。满足非负条件的基本解称为基本可行解 （简称基可行解）。（简称基可行解）。与基本可行解对应的基成为可行基。与基本可行解对应的基成为可行基。 基本可行解的非零向量的个数小于等于基本可行解的非零向量的个数小于等于m m，并且都是非负的。，并且都是非负的。 由于基本可行解的数目一般少于基本解的数目，因此可行基由于基本可行解的数目一般少于基本解的数目，因此可行基 的数目也要少于基的数目。的数目也要少于基的数目。 当基本可行解中

32、有一个或多个基变量是取零值时，称此解为当基本可行解中有一个或多个基变量是取零值时，称此解为 退化的基本可行解。退化的基本可行解。mnC 线性规划问题各种解的关系可用文氏图表示，线性规划问题各种解的关系可用文氏图表示， 可行解基本解基本解基本可行解例例7 7、求下列约束方程所对应的线性规划的所有基本解，、求下列约束方程所对应的线性规划的所有基本解， 基本可行解。基本可行解。 s.t s.t 解：化为标准形式解：化为标准形式 为为2 24 4阶矩阵。阶矩阵。 且且R(A)=2,R(A)=2,所以该线性规划基的个数所以该线性规划基的个数 =6 =6个个 取取 , , 为基变量，为基变量， 若令非基变

33、量若令非基变量 ， 约束方程组为约束方程组为 可得对应的基本解可得对应的基本解 是一个基本可行解。是一个基本可行解。 12212x2x8x2 x ,x0123241234x2xx 8 x x2 x ,x ,x ,x012341210A=(P ,P ,P ,P )010124C11212B =(P,P )0112x ,x34x =x0122x2x8 x21(4,2,0,0)TX 8b=2 按相同步骤，可求得线性规划其他按相同步骤，可求得线性规划其他4 4个基个基：21410B =(P ,P )01对应基本解对应基本解是一个基本可行解。是一个基本可行解。 32321B =(P ,P )104242

34、0B =(P ,P )1153410B =(P ,P )01T5X =(0,0,8,2)12341210A=(P,P ,P ,P )0101T2X =(8,0,0,2)T3X =(0,2,4,0)T4X =(0,4,0,-2)对应基本解对应基本解是一个基本可行解。是一个基本可行解。 对应基本解对应基本解不是一个基本可行解。不是一个基本可行解。 对应基本解对应基本解是一个基本可行解。是一个基本可行解。 8b=2 若利用图解法画出线性规划的可行域，如图，若利用图解法画出线性规划的可行域，如图，12212x2x8x2 x ,x012345X =(4,2,0,0)B, X =(8,0,0,2)A, X

35、 =(0,2,4,0)CX =(0,4,0,-2)D, X =(0,0,8,2)O.CDOBA4481228xx12x +2x =82x =2p 线性规划的基本理论线性规划的基本理论由图解法的步骤，可以从几何的角度得出以下两个由图解法的步骤，可以从几何的角度得出以下两个结论：结论：（1 1）线性规划问题的可行域是一个有界或无界的凸多边）线性规划问题的可行域是一个有界或无界的凸多边形，其顶点个数是有限个。形，其顶点个数是有限个。（2 2）若线性规划问题有最优解，那么最优解一定可在可）若线性规划问题有最优解，那么最优解一定可在可行域的某个顶点上找到。行域的某个顶点上找到。n几个基本概念几个基本概念

36、（1 1）凸集：设）凸集：设k k是是n n维欧式空间的一个点集，若任意两点维欧式空间的一个点集，若任意两点X X(1)(1)k, Xk, X(2)(2)kk的连线上的一切点的连线上的一切点XX(1)(1)+ (1-)X+ (1-)X(2)(2)kk( 01),( 01),则称则称k k为凸集。为凸集。 连接几何形体中任意两点的线段仍完全在该几何形体之中。连接几何形体中任意两点的线段仍完全在该几何形体之中。 有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集。（2 2）凸组合：设）凸组合：设X X(1)(1)，X X(2)(2)，X X(k)(k)是是n n维欧式空间中的维欧式空间中的k

37、k个点，个点， 若存在若存在1,1, 2 2, , , k k满足满足00i i1,( 1,( i=1,2,k), 使使X=X=1 1X X(1)(1)+2 2 X X(2)(2)+ +k k X X(k)(k)， 则称则称X X为为X X(1)(1)，X X(2)(2)，X X(k)(k)的凸组合。的凸组合。 凸集凸集k k中任意两点中任意两点X X(1)(1)，X X(2)(2)连线上的任一点连线上的任一点X X都是都是X X(1)(1)与与X X(2)(2)的一的一个凸组合。个凸组合。 (3) (3) 顶点：设顶点：设k k为凸集，为凸集，Xk,Xk,若若X X不能用不能用X X(1)(

38、1)k,Xk,X(2)(2)kk两点的两点的 一个凸组合表示为一个凸组合表示为X=XX=X(1)(1)+ (1-)X+ (1-)X(2)(2), ,其中其中01 00,m+1jn = m+kxm+kxm+k0m+1m+2-1Bm+1,m+1,nnxxZC B b+( )xl 换出变量的确定换出变量的确定 最小比值原则最小比值原则 如果确定为换入变量，方程如果确定为换入变量，方程其中为中与对应的系数列向量。其中为中与对应的系数列向量。现在需在现在需在 中确定一个基变量为换出变量。中确定一个基变量为换出变量。 当由零慢慢增加到某个值时，当由零慢慢增加到某个值时， 的非负性可能被打破。的非负性可能被

39、打破。为保持解的可行性，可以按最小比值原则确定换出变量：为保持解的可行性，可以按最小比值原则确定换出变量： 若若B12mX =(x ,x ,x )T-1-1-1im+ki-1-1m+kim+k(B b)(B b)min/(B P) 0,1im =(B P)(B P)ll m+kx-1-1-1-1BNBm+km+kX=B b-B NXX=B b-B Pxm+kPm+kxm+kx则选取对应的基变量则选取对应的基变量 为换出变量。为换出变量。 xlBX 定理定理3 3：无最优解判别定理：无最优解判别定理 若若 是一个基本可行解，有一个检验数是一个基本可行解，有一个检验数 ，但是，则该线性规划问题无最

40、优解。但是，则该线性规划问题无最优解。1B bX=0-1m+kB P0m+k0证：令证：令 ，则得新的可行解，则得新的可行解将上式代入将上式代入因为因为 , , 故当故当+时，时，Z+Z+。-1-1-1-1Bm+km+km+kX =B b-B PxB b-B Pm+1-1-1Bm+1m+knBm+knxZ=C B b+(, )C B b+x m+kx,(0) m+k0n用初等变换求改进了的基本可行解用初等变换求改进了的基本可行解假设是线性规划假设是线性规划 的可行基，则的可行基，则令非基变量，则基变量。令非基变量，则基变量。可得基本可行解可得基本可行解 。 1B bX=0BNXA X =b(B

41、 N )bXmaxZ=CX,AX=b,X0B-1-1NX(I,BN )=BbX用逆阵左乘约束方程组的两端，等价于对方程组施以一系列用逆阵左乘约束方程组的两端，等价于对方程组施以一系列的初等的初等“行变换行变换”。变换的结果是将系数矩阵中的可行基变换成。变换的结果是将系数矩阵中的可行基变换成单位矩阵单位矩阵I I，把非基变量系数列向量构成的矩阵变换成，把，把非基变量系数列向量构成的矩阵变换成，把资源向量资源向量b b变换成。变换成。1B1BX =B b1B N1B bNX =0且改进了的基本可行解只是在的基变量的基础上用一个换且改进了的基本可行解只是在的基变量的基础上用一个换入变量替代其中一个换

42、出变量，其它的基变量仍然保持不变。这些入变量替代其中一个换出变量，其它的基变量仍然保持不变。这些基变量的系数列向量是单位矩阵基变量的系数列向量是单位矩阵I I中的单位向量。为了求得改进的基中的单位向量。为了求得改进的基本可行解本可行解 ，只需对增广矩阵，只需对增广矩阵 施行初等行变换，将换入变量的系数列向量变换成换出变量所对施行初等行变换，将换入变量的系数列向量变换成换出变量所对应的单位向量即可。应的单位向量即可。由于行初等变换后的方程组由于行初等变换后的方程组与原约束方程组与原约束方程组 或同解或同解B-1-1NX(I,B N)=B bXAX=bX-1-1(I,BN ,Bb)BNX(B ,N

43、 )=bXX123451234123512345maxZ=5x2x3xxxx2x2xx83x4xxx7 x ,x ,x ,x ,x012210A=341018b7 C = ( 5 , 2 , 3 ,1 , 1 )例例1 1解：解：( () )确定初始的基本可行解。确定初始的基本可行解。 ，基变量，基变量 ，非基变量，非基变量 。4510B=(P P )=0145x ,x123x ,x ,x14BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x 1NB8X=0X =Bb=7X = (0 ,0 ,0 , 8 , 7 )T1B8Z

44、=C B b=(-1,1)17 (2) 检验检验 是否最优。是否最优。检验向量检验向量 因为因为1 1=3=3，3 3=4 =4 均大于零，均大于零，所以不是最优解。所以不是最优解。X =(0,0,0,8, 7)T-1NNB123122=C-C B N=(5,2,3)-(-1,1)341=(5,2,3)-(2,2,-1)=(3, 0, 4) 14BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x X =(0,0,0,8, 7)T（3）基本可行解的改进基本可行解的改进 选取换入变量选取换入变量因为因为max3max3，4=44

45、=4，取，取x x3 3为换入变量。为换入变量。 选取换出变量选取换出变量 且且 ， 选取选取x x4 4为换出变量为换出变量. .8 78min,2 12X = (0,0,0,8, 7 )T11382Bb=,BP07114BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x N123= (,)(3, 0, 4)4-1-13335x82=B b-B P x =-xx71 （4）求改进了的基本可行解求改进了的基本可行解 对约束方程组的增广矩阵施以初等行变换，使换入变量对约束方程组的增广矩阵施以初等行变换，使换入变量x x3 3所

46、对应的所对应的系数列向量系数列向量 变换成换出变量变换成换出变量x x4 4所对应的单位向量所对应的单位向量 , , 注意保持基变量注意保持基变量x x5 5的系数列向量的系数列向量 为单位向量不变。为单位向量不变。32P =1 41P0 50P =1 111 104122 108 2234 10 1734 10 17111 10422 5-1301 322 X14BBN25N3xxC =(-1,1)101228X =,X = x,B=,N=,b=xC =(5,2,3)013417x 第一行除以第一行除以第二行减去第一行第二行减去第一行可得改进的基本可行解。可得改进的基本可行解。 ，基变量，基

47、变量，非基变量。非基变量。基本可行解基本可行解目标函数值目标函数值易见目标函数值比原来的易见目标函数值比原来的Z=-1Z=-1增加了，增加了， 再转向步骤再转向步骤(2)(2)3510B=(P P )=0113BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 1NB4X =0X =B b=3X = (0,0,4, 0, 3)T1B4Z=C Bb=(3,1)153C = (5 ,2 ,3 ,1,1)C = (5 ,2 ,3 ,1,1)111 104122 10822 534 10 17-1301 32235x x1

48、24x ,x ,x（2）检验检验 是否最优。是否最优。检验向量检验向量因为，因为，所以仍不是最优解。所以仍不是最优解。X = (0,0,4, 0, 3)T-1NNB12411122=C-C B N=(5,2,-1)-(3,1)5-1322=(5,2,-1)-(4,6,1)=(1, -4, -2) X =(0,0,4, 0, 3)T13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 110 （3）基本可行解的改进基本可行解的改进 选取换入变量选取换入变量因为，取为换入变量。因为，取为换入变量。 选取换出变量选取换

49、出变量且且 ，选取为换出变量选取为换出变量. .433min,1/2 5/25/2X = (0,0,4, 0, 3)T111142Bb=, BP0352110 1x5x13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 3-1-11115x41/2=B b-B P x =-xx35/2 （4）求改进了的基本可行解求改进了的基本可行解 对约束方程组的增广矩阵施以初等行变换，使换入变量所对应对约束方程组的增广矩阵施以初等行变换，使换入变量所对应的系数列向量变换成换出变量所对应的单位向量的系数列向量变换成换出变量所对

50、应的单位向量 , , 112P =5250P1 X1x5x111111041104 2222665-12-11030135555223172-101 5555 66-12105555 13BBN25N411x1xC =(3,1)10422X =,X = x,B=,N=,b=xC =(5,2,-1)015-133x22 第二行乘以第二行乘以/第一行减以第二行的第一行减以第二行的/倍倍可得改进的基本可行解。可得改进的基本可行解。 ，基变量，基变量，非基变量非基变量基本可行解基本可行解目标函数值目标函数值 比比Z=15Z=15增加了，再转向步增加了，再转向步骤骤(2)(2)3110B=(P P )=

51、012B3BN4N1523-117xC =(3,5)x105555X =,X = x,B=,N=,b=C =(2,-1,1)x016-126x55551NB175X =0X =B b=65617X=(,0,0,0)55T1B17815Z=C Bb=(3,5)655C = (5 ,2 ,3,1,1)C = (5 ,2 ,3,1,1)31x ,x245x ,x ,x3172-111011104555522 566-1-12301310225555（2）检验检验 是否最优。是否最优。检验向量检验向量因为所有检验数均小于零，因为所有检验数均小于零，所以是最优解，所以是最优解，-1NNB24523-15

52、55=C-CBN =(2,-1,1)-(3,5)6-125553647-26-9-2=(2,-1,1)-(,)=(,)555555 617X =(,0,0,0)55T*617X =X =(,0,0,0)55T*81Z =52B3BN4N1523-117xC =(3,5)x105555X =,X = x,B=,N=,b=C =(2,-1,1)x016-126x5555p表格单纯形法表格单纯形法通过例我们发现，在单纯形法的求解过程中，有下列重要指标：通过例我们发现，在单纯形法的求解过程中，有下列重要指标：l 每一个基本可行解的检验向量每一个基本可行解的检验向量根据检验向量可以确定所求得的基本可行解

53、是否为最优解。如果不根据检验向量可以确定所求得的基本可行解是否为最优解。如果不是最优又可以通过检验向量确定合适的换入变量。是最优又可以通过检验向量确定合适的换入变量。l 每一个基本可行解所对应的目标函数值每一个基本可行解所对应的目标函数值通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值通过目标函数值可以观察单纯形法的每次迭代是否能使目标函数值有效地增加，直至求得最优目标函数为止。有效地增加，直至求得最优目标函数为止。 在单纯形法求解过程中，每一个基本可行解都以在单纯形法求解过程中，每一个基本可行解都以某个经过初等行某个经过初等行变换的变换的约束方程组中的单位矩阵约束方程组中的单位矩阵

54、为可行基。为可行基。当当= =时，时，-1-1= =，易知：，易知：-1NNB=C-C B N1BZ=C BbNNB=C-C NBZ=C b 可将这些重要结论的计算设计成如下一个简单的表格，可将这些重要结论的计算设计成如下一个简单的表格，即单纯形表来完成：即单纯形表来完成：CCBCNCBXBbX1X2Xm Xm+1Xm+2XnC1C2.CmX1X2.Xmb1b2.bmI IN12.mZCBb0CN- -CBN例例2 2、试利用单纯形表求例、试利用单纯形表求例1 1中的最中的最优解：优解：得初始的单纯形表：得初始的单纯形表：C = (5 ,2 ,3 ,1,1)122108(Ab)=3410171

55、23451234123512345maxZ=5x2x3xxxx2x2xx83x4xxx7 x ,x ,x ,x ,x0NNB=C-C NBZ=C b初始基本可行解，初始基本可行解，Z= -1Z= -1，X = (0,0,0,8, 7 )T122108x4-130400-1Z341017x51x1x2x3x4x5bXBCB523-11C换入变量，换出变量，为主元进行旋转变换换入变量，换出变量，为主元进行旋转变换3x4x基本可行解，基本可行解，Z= 15Z= 15，X = (0,0,4, 0, 3)T1/2111/204x331-40-2015Z5/230-1/213x51x1x2x3x4x5bX

56、BCB523-11C122108x4-130400-1Z341017x51x1x2x3x4x5bXBCB523-11C8/27/1最优解最优解 最优值最优值 617X,0,0,055T换入变量，换出变量，换入变量，换出变量，/ /为主元进行旋转变换为主元进行旋转变换1x5xNNB=C-C N081Z54/1/21/2111/204x331-40-2015Z3/5/25/230-1/213x51x1x2x3x4x5bXBCB523-11C02/513/5-1/517/5x330-26/50-9/5-2/581/5Z16/50-1/52/56/5x15x1x2x3x4x5bXBCB523-11C例

57、例3 3、用单纯形方法求解线性规划问题、用单纯形方法求解线性规划问题解：本题的目标函数是求极小化的线性函数，解：本题的目标函数是求极小化的线性函数，可以令可以令则则这两个线性规划问题具有相同的可行域和最优解，这两个线性规划问题具有相同的可行域和最优解，只是目标函数相差一个符号而已。只是目标函数相差一个符号而已。 121324125jminZ=-x -2xxx4xx3x2xx8x0 j1,2,3,4,5，12Z = -Z = x +2x1212minZ=-x -2xmaxx +2xZ010103x220012-12x30-010103x224/1101004x303/1010103x40_101

58、004x300000-18Z100-212x11100-206Z2/1100-212x50120000Z8/2120018x50 x1x2x3x4x5bXBCB12000C最优解最优值最优解最优值X2,3,2,0,0TmaxZ=8 or minZ=-82/23/1-因为非基变量因为非基变量x x4 4的检验数的检验数4 4=0=0，由无穷多最优解判别定理，本例，由无穷多最优解判别定理，本例的线性规划问题存在无穷多最优解。事实上若以的线性规划问题存在无穷多最优解。事实上若以x x4 4为换入变量，以为换入变量，以x x3 3为为换出变量，再进行一次迭代，可得一下单纯形表：换出变量，再进行一次迭代

59、，可得一下单纯形表：最优解最优解 最优值最优值最优解的一般表示式最优解的一般表示式maxZ=8 or minZ=-8X4,2,0,1,0TX(2,3,2,0,0)(1) 4,2,0,1,0,01.TTC12000CBXBbx1x2x3x4x5021x4x2x1124001/21-1/201-1/201/210100Z80000-1对于极小化的线性规划问题的处理：对于极小化的线性规划问题的处理：l先化为标准型，即将先化为标准型，即将极小化问题变换为极大化问题，然后利用单极小化问题变换为极大化问题，然后利用单纯形方法求解纯形方法求解l直接利用单纯形方法求解，但是检验是否最优的准则有所不同，直接利用

60、单纯形方法求解，但是检验是否最优的准则有所不同，即：即： 若某个基本可行解的所有非基变量对应的检验数若某个基本可行解的所有非基变量对应的检验数 （而不是（而不是），），则基本可行解为最优解则基本可行解为最优解否则采用最大减少原则（而非最大增加原则）来确定换入变量，否则采用最大减少原则（而非最大增加原则）来确定换入变量，即：即： 若若则选取对应的非基变量则选取对应的非基变量x xm+km+k为换入变量为换入变量 确定了换入变量以后，换出变量仍采用最小比值原则来确定。确定了换入变量以后，换出变量仍采用最小比值原则来确定。 NNB= C-CN0jjm+kmin / 0因因但但所以原问题所以原问题无最