2线性规划图解法

§2.0线性规划简介第二章线性规划及其图解法（LinearProgramming，简称LP）本章结合了第五章的一些概念

线性规划是运筹学中研究较早、应用广泛、发展较快、方法较成熟的一个重要分支,是辅助人们进行科学管理的一种数学方法。是研究线性约束条件下线性目标函数的极值问题的数学理论和方法，英文缩写LP。

LP是运筹学的一个重要分支，广泛应用于军事作战、经济分析、经营管理和工程技术等方面。为合理地利用有限的人力、物力、财力等资源作出的最优决策，提供科学的依据。

1832和1911年法国数学家J.B.J.傅里叶和C.瓦莱－普森分都分别独立地提出线性规划的想法，但未引起注意。

1939年，前苏联数学家康托洛维奇用线性规划模型研究提高组织和生产效率问题

1947年，Dantzig提出求解线性规划的单纯形法

1950-1956年，主要研究线性规划的对偶理论

1951年美国经济学家T.C.库普曼斯把线性规划应用到经济领域，为此与康托罗维奇一起获1975年诺贝尔经济学奖。

1958年，发表整数规划的割平面法

1960年，Dantzig和Wolfe研究成功分解算法，奠定了大规模线性规划问题理论和算法的基础。一、线性规划发展概况线性规划的研究成果还直接推动了其他数学规划问题包括整数规划、随机规划和非线性规划的算法研究。由于数字电子计算机的发展，出现了许多线性规划软件，如MPSX，OPHEIE，UMPIRE等，可以很方便地求解几千个变量的线性规划问题。

1979年，Khachiyan，1984年，Karmarkaa研究成功线性规划的多项式算法。用卡马卡方法求解线性规划问题在变量个数为5000时只要单纯形法所用时间的1/50。

二、线性规划研究解决的主要问题

实际上，上述两类问题是一个问题的两个不同的方面，都是求问题的最优解（max或min）。

另一类是当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。一类是已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。线性规划在工商管理中应用有着广泛的用处，可以用来解决诸如：人力资源分配问题、生产计划问题、下料配料、投资问题（见第4章）以及运输问题（第7章）等。实际上远不止这些具体问题。但从一般意义上解决得问题有两类：三、LP解决问题的一般思路5、模型求解与解的调适。（获得最优方案——一组决策变量的取值）。1、对问题进行系统分析,搞清决策什么和决策目标是什么？2、明确是哪些因素（人为可控的，决策变量）影响决策目标（大小变化），确定决策变量对目标（函数）影响系数，且与目标函数是否呈线形关系。3、哪些资源约束（或需求约束）条件制约着目标（最大或最小）。决策变量对这些资源（或需求）的单位消耗（单位产出）是多少？，即要获得资源总量和投入产出系数。4、建立线形规划数学模型。6、方案实施与调整。§2.1LP问题的提出及其数学模型一、例示——问题提出例2.1-1某厂在计划期内安排生产两种产品，生产所需资源限制及单位产品原料消耗由下表给给出

利润50100问：应如何安排生产计划才能使总利润最大？

甲乙资源限制设备11300台时原料A21400kg原料B01250kg解：确定决策变量：设产品甲乙的产量分别为

：

x1、x22.建立目标函数：设总利润为z，本例是：

maxz=50x1+100x23.考虑约束条件：

x1+x2≤3002x1+x2≤400x2≤250

x1，x2≥0目标函数：maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250

x1，x2≥0满足

约束条件：4.得到本问题的数学模型：例2.1-2某厂生产两种产品，下表给出了单位产品所需资源及单位产品利润问：应如何安排生产计划，才能使总利润最大？

解：1.决策变量：设产品I、II的产量分别为

x1、x22.目标函数：设利润为z，则有：

maxz=2x1+3x23.约束条件：

x1+2x2≤84x1≤16

4x2≤12

x1，x2≥0例2.1-3某厂生产三种药物，这些药物可从四种不同的原料中提取。下表给出了单位原料可提取药物的量（有效单位数）要求：生产A种药物至少160单位；B种药物恰好200单位，C种药物不超过180单位，且使原料总成本最小。解：1.决策变量：设四种原料的使用量分别为：

x1、x2、x3

、x42.目标函数：设总成本为z，则有：

minz=5x1+6x2+7x3+8x43.约束条件：

x1+2x2+x3+x4≥1602x1+4x3+2x4

＝1603x1

＋x2+x3+2x4

≤180

x1、x2

、x3

、x4≥0

药物原料ABC单位成本（元／吨）甲1235乙2016丙1417丁1228二、LP问题一般模型1.决策变量：X=(x1,x2,…..,xn)T2.目标函数：max(minz)=c1

x1+c2

x2+…….+cnxn3.约束条件：a11x1+a12

x2+……..+a1n

xn≤(=≥)b1

a21x1+a22

x2+……..+a2n

xn≤(=≥)b2

…………am1x1+am2

x2+……..+amn

xn

≤(=≥)bm

x1,x2,……xn≥0三、LP模型特点1、都用一组决策变量X=(x1,x2,…,xn)T表示某一方案，且决策变量取值非负；———满足以上三个条件的数学模型称为线性规划数学模型或LP模型2、都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；3、都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式来表示。LP模型的其它表达形式①简约形式②矩阵形式决策变量常数项系数矩阵价值系数其中：四、线性规划数学模型的建立（一）建模条件1优化条件：问题所要达到的目标能用线型函数描述，且能够用极值（max或min）来表示；2限定条件：达到目标受到一定的限制，且这些限制能够用决策变量的线性等式或线性不等式表示；3选择条件：有多种可选择的方案供决策者选择，以便找出最优方案。（二）LP建模步骤1确定决策变量并收集有关参数：即需要我们作出决策或选择的量。一般情况下题目问什么，就把什么设置为决策变量。2找列出所有限定条件：即决策变量受到的所有的资源与需求等约束；3写出目标函数：即问题所要达到的目标，并明确是max还是min。（三）建模案例例2.1-4某厂生产A、B两种产品，有关参数资料如下表所示，问如何组织生产才能使效益最大：设：总利润为Z；产品A、B产量为x1、x2，产品C的销量为x3，报废量为x4，则：

maxz=4x1+10x2+3x3－2x4

2x1+3x2≤123x1+4x2≤244x2-x3-x4=0x3≤5

x1、x2

、x3

、x4≥0§2.2线性规划图解法一、解题步骤4将最优解代入目标函数，求出最优值。1建立坐标系并在直角平面坐标系中画出所有的约束等式，然后找出满足所有约束条件的公共部分，称为可行域，可行域中的点称为可行解。2标出目标函数值改善的方向。3画出目标函数等值线，若求最大（小）值，则令目标函数等值线沿目标函数值增加（或减少）的方向平行移动，找与可行域最后相交的点，该点就是最优解。用图解法求解下列线性规划问题（例1）

x1+2x2≤8①4x1≤16

②

4x2≤12③

x1，x2≥0

maxz=2x1+3x2最优解：X*=(2,4)T最优值：Z*=14目标函数等值线Z=0x2x1①②③线性规划的图解（例2）max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2目标函数：分别取决策变量为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，每个约束条件都代表一个半平面。图示如下：用图解法求解下列线性规划问题x2x1X2≥0X2=0x2x1X1≥0X1=0100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE综上得到最优解：最优目标值:1、凸集若连接n维点集P中任意两点x（1），x（2），其线段仍在P内，则称P为凸集。即：{x|x=

x(1)+(1-)x(2)，0<<1,x(1)P,x(2)P}P,则称P为凸集）2、极点若点x∈Ｐ,且x不是P中任何线段的内点，则称点x为凸集P的极点。显然多边形的顶点都是极点，四面体的顶点也都是极点，而圆周上、球面上的每一个点都是极点，其它点都不是极点。二、关于凸集、极点的概念三、线性规划解的性质定理1

线性规划的可行域R是一个凸集，且有有限个极点。定理2X是线性规划可行域R顶点的充要条件是X线性规划的基本可行解。定理3

若线性规划有最优解，则必有基本最优解。定理4

若线性规划在可行域的两个顶点上达到最优，则在两个顶点的连线上也达到最优。——线性规划的每一个基本可行解对应凸集的每一个顶点。——若线性规划有最优解，则一定在凸集的某个（些）顶点上达到最优。——若线性规划在两个顶点以上达到最优,则一定有无穷多个最优解。——最优解一定是基本可行解，但基本可行解不一定是最优解。四、线性规划问题求解可能出现的情况x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。

4、无可行解。如果例3再增加一个约束条件3、无界解。即可行域延伸到无穷远，目标函数值可以无穷大或无穷小。2、如果最优解出现在两个极点上，则会有无穷多个最优解。1、如果LP有最优解，则一定有一个可行域的极点对应这个最优解；

五、LP解的有关概念及其关系1可行解（feasiblesolution）：满足线性规划约束条件的解称为可行解。（一）有关概念2最优解（optimalsolution）：使线性规划目标函数达到最优的可行解称为最优解。3基本解（basicsolution）：以线性规划约束等式的系数矩阵A中任意m行m列组成的m×m满秩子矩阵为基矩阵，与基矩阵相对应的变量称为基变量（basicvariable），其余变量称为非基变量，若令非基变量为零，则可求得基变量的解（值），这个解称为基本解。

4基本可行解（basicfeasiblesolution）：满足非负约束的基本解称为基本可行解。若约束等式中有n个变量，m个约束，则基本解的个数≤令非基变量x1＝0，x2

＝0则得：X＝(0,0,3,1)T基本解当基变量为x2、x3，则非基变量为x1、x4令非基变量x1＝0，x4

＝0则得：X＝(0,－1,5,0)T基本解／基本可行解？／是基本可行解？

x1

＋2x2

＋x3

＝32x1

－x2

＋x4＝1x1,x2,x3,x4≥0解：系数矩阵为：设基变量为x3、x4，则非基变量为x1、x23）X＝(1/2,1/2,3/2,1/2)T／不是基本解可行解／是基本可行解？例讨论下述约束方程的解1可行解与最优解：最优解一定是可行解，但可行解不一定是最优解。（二）线性规划解之间的关系基本解不一定是可行解，可行解也不一定是基本解。2可行解与基本解：3可行解与基本可行解：基本可行解一定是可行解，但可行解不一定是基本解。基本可行解一定是基本解，但基本解不一定是基本可行解。4基本解与基本可行解：5最优解与基本解：最优解不一定是基本解，基本解也不一定是最优解。问题：最优解与基本可行解？非可行解可行解基本可行解基本解六、线性规划模型的标准形式及其标准化（一）线性规划模型标准形式特点

1．目标最大化；2．约束为等式；

3．决策变量均非负；4．右端项非负。特点Maxz=c1x1+c2x2

+…+cnxna11x1+a12x2+…+a1nxn

=b1a21x1+a22x2+…+a2nxn

=b2

...am1x1+am2x2+…+amnxn

=bm

x1，x2，…，xn≥0s.t

如果目标函数为Min该极小化问题与下面的极大化问题有相同的最优解，但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即：

（二）线性规划模型标准化问题1、极小化目标函数的问题：则令：z

＝-f

，Minf

＝—Maxz2、约束条件不是等式的问题：时，可以引进一个新的变量，使它等于约束右边与左边之差（2）当约束条件为类似地令则有：则有：（1）当约束条件为3.右端项有负值的问题：

则把该等式约束两端同时乘以-1，得到：

为了使约束方程由不等式成为等式而引进的变量,当不等式为“小于等于”时称引进的变量为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束，则将其转化为标准形式时，必须对各个约束引进不同的松弛变量或剩余变量。

在标准形式中，要求右端项必须每一个分量非负。当某一个右端项系数为负时，如

4.变量无符号限制的问题

在标准形式中，必须每一个变量均有非负约束。当某一个变量xj

没有非负约束时，可以令xj

=

xj’-

xj”

其中xj’≥0，xj”≥0即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj’和xj”的大小。总之通过上述问题的处理，线性规划模型的一般形式均可化为标准形式。标准化例题1一般形式标准形式标准化例题2§2.3灵敏度分析

灵敏度分析是建立数学模型和求得最优解后，研究线性规划的一个或多个参数()变化时，对最优解产生的影响，或者这些参数在一个多大范围内变化时，原LP问题的最优解不变的问题。

目标函数中的系数的变化只影响目标函数等值线的斜率，不影响可行域。所谓C的灵敏度分析是指，研究在目标函数中其他的系数不变，只有一个系数在保持最优解不变时该系数的取值范围。1．目标函数中的系数“C”的灵敏度分析一般情况：可将其写成：目标函数等值线的斜率为：有：可使原最优解仍是最优解。先假设产品乙的利润100元不变，即：代入（*）并整理得：考虑例1目标函数为：x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1要使最优解不变，其变化必然在构成极点的相交直线的斜率之间。对C1进行灵敏度分析maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1，x2≥0满足同样：假设C1=50不变时，代入：有：-1≤-（50/C2）≤0整理后得：50≤C2≤+∞即当50≤C2≤+∞时原最优解不变。2．约束条件中右边系数的灵敏度分析

当约束条件中右边系数变化时，线性规划的可行域发生变化，可能引起的最优解的变化，进而了解当其他约束不变时，某一约束条件的右端项每变化一个单位，使目标函数值的改变量。由讲义例1可知：（1）假设设备台时增加10个台时，即变为310台时，这时可行域扩大，但最优解所在的基点不变，得最优解为：X1=60，X2=250x1x2x2=0x1=0x2=250x1+x2=3102x1+x2=400图2-1（2）假设原料A增加10千克时，即变化为410，这时可行域扩大，但最优解仍为①和③约束方程的交点。此变化对总利润无影响，因此该约束条件的对偶价格为0。由于原最优解没有把原料A用尽，有50千克的剩余，因此增加10千克值增加了库存，而不会增加利润。这时，即变化后的总利润—变化前的总利润=增加的利润

(50×60+100×250)—(50×50+100×250)=500元，即：每增加一个台时的利润为：500/10=50元说明在一定范围内每增加（减少）1个台时的设备能力就可增加（减少）50元利润，称为该约束条件的对偶价格。图2-1x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=410

在一定范围内，当约束条件右边常数增加1个单位时（1）若约束条件的对偶价格大于0，则其最优目标函数值得到改善（变好）；（2）若约束条件的对偶价格小于0，则其最优目标函数值受到影响（变坏）；（3）若约束条件的对偶价格等于0，则最优目标函数值不变。作业布置：1、P24第3（2，3），第4题2、P25第6、7题原问题LP模型：Maxz=50x1+100x2s.t.x1+x2≤300 2x1+x2≤400 x2≤250 x1,x2≥02.4线性规划的对偶问题最优解为：x1=50x2=250

；maxZ=27500对偶问题：不妨提出这样的问题，如果该厂把设备（工时）和A、B原料租赁和转让出去，又要不比自己生产赚的少，该厂如何收取租金和转让费？或者说设备租赁至少多少钱一个工时，原料A、B应收多少钱一公斤？原问题：例2.1某厂在计划期内安排生产两种产品，生产所需资源限制及单位产品原料消耗由下表给给出甲乙资源限制设备11300台时原料