第四讲线性规划-图解法(liu)

1、1第四讲 线性规划本讲的主要内容： 一、情况介绍 二、线性规划模型及标准化 线性规划模型的一般形式 线性规划模型的标准形 三、二维线性规划的图解法 图解法含义 图解法举例 几个概念 解的状态 图解法延伸2一、情况介绍 作为一门科学的线性规划，最早可以追溯到20世纪30年代末，前苏联数学家康德洛维奇等人关于生产组织和运输问题研究所作的开拓性工作。1947年，美国数学家G.B.Dantzig以及美国空军的SCOOP研究小组提出了线性规划问题的一般性解法即单纯形法,奠定了线性规划的理论基础。50年代后，随着电子计算机的介入，线性规划的应用越来越普遍，在生产、管理、军事等方面发挥着重要的作用。 线性规

2、划目前仍然还在发展，主要是：大型线性规划问题，线性规划解法研究等。3一、情况介绍 线性规划研究的问题可以归结为两大类别： 1、在现有的资源条件下，如何充分利用资源，使任务或目标完成得最好（求约束极大化问题）。 2、在给定目标下，如何以最少的资源消耗，实现这个目标（求约束极小化问题）。4一、情况介绍 线性规划问题就是在一定约束条件下，寻找目标函数的极值问题。 所谓线性规划，是指约束条件为线性等式或线性不等式，且目标函数也为线性函数。5二、线性规划模型及标准化1、线性规划模型的一般形式 根据实际问题的要求，可建立线性规划问题数学模型。线性规划问题的数学模型，由目标函数和约束条件两部分组成。下面我们

3、举例说明线性规划问题的数学模型。 例一：生产计划问题例一：生产计划问题 某工厂拥有A、B、C三种类型的设备，生产甲、乙、丙、丁四种产品。每件产品在生产中需要占用的设备机时数，每件产品可以获得的利润以及三种设备可利用的时数如下表所示：6二、线性规划模型及标准化产品甲产品乙产品丁产品丙设备能力设备A1.51.02.41.02000设备B1.05.01.03.58000设备C1.53.03.51.05000利 润5.247.308.344.187二、线性规划模型及标准化解：设变量xi为第i种产品的生产件数（i1，2，3，4），目标函数z为相应的生产计划可以获得的总利润。在加工时间以及利润与产品产量成

4、线性关系的假设下，可以建立如下的线性规划模型： Max z=5.24x1+7.30 x2+8.34x3+4.18x4 s.t. 1.5x1+1.0 x2+2.4x3+1.0 x42000 1.0 x1+5.0 x2+1.0 x3+3.5x48000 1.0 x1+3.0 x2+3.5x3+1.0 x45000 x1，x2，x3，x4 08二、线性规划模型及标准化1、线性规划模型的一般形式 例二：配料问题 某工厂要用四种合金T1，T2，T3和T4为原料，经熔炼成为一种新的不锈钢G。这四种原料含元素铬（Cr），锰（Mn）和镍（Ni）的含量（%），这四种原料的单价以及新的不锈钢材料G所要求的Cr，M

5、n和Ni的最低含量（%）如下表所示：9二、线性规划模型及标准化T1T2T3 T4GCr3.214.532.191.763.20Mn2.041.123.574.332.10Ni5.823.064.272.734.3011597827610二、线性规划模型及标准化 假设熔炼时重量没有损耗，要熔炼成100千克不锈钢G，应选用各种原料各多少才能使成本达到最小。 解：设选用原料T1，T2，T3和T4分别为x1，x2，x3，x4千克，根据条件，可建立相应的线性规划模型如下：11二、线性规划模型及标准化1、线性规划模型的一般形式 Min Z=115x1+97x2+82x3+76x4 s.t.0.0321x1

6、+0.0453x2+0.0219x3+0.0176x43.200.0204x1+0.0112x2+0.0357x3+0.0433x42.10 0.0582x1+0.0306x2+0.0427x3+0.0273x44.30 x1 + x2 + x3 + x4=100 x1 , x2 , x3 , x4012二、线性规划模型及标准化1、线性规划模型的一般形式 Max(Min) z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn(=、)b1 a21x1+a22x2+a2nxn(=、)b2 am1x1+am2x2+amnxn(=、)bm x1,x2, ,xn () 0，或者

7、没有限制13二、线性规划模型及标准化2、线性规划模型的标准形 Max z=c1x1+c2x2+cnxn s.t. a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1,x2, ,xn 014二、线性规划模型及标准化2、线性规划模型的标准化方法： （1）把最小化目标函数转化为求最大化问题。令 （2）把约束方程中的不等式转化为等式。具体做法是：对于小于等于情况，引进松弛变量，对于大于等于情况，引进剩余变量。 （3）变量取值可能无约束。令 （4）变量小于等于零，令 （5）右端项 小于零，等式两端同乘-1zzjjjxxxjj

8、xx jb15二、线性规划模型及标准化定理：线性规划模型的一般形式与它的标准形是等价的。 根据这一定理，由标准形求出的最优解，也一定是原问题的最优解。16二、线性规划模型及标准化 1、用“” 表示2、用向量表示3、用向量和矩阵表示1. .0njjjMaxCXs tA xXb. .0M a xC Xs tA XXb17各种符号的定义nmnmmnnpppaaaaaaaaaA21212222111211mnbbbbxxxX2121,ncccC2118三、二维线性规划的图解法1、图解法的含义 在直角坐标系中，描绘出约束条件和变量限制的公共区域，然后通过观察确定符合目标要求的变量的取值。2、图解法举例

9、19三、二维线性规划的图解法2、图解法举例 线性规划模型：120,0 xx12121212203024024025MaxZXXXXXXXX20可行域402520 250 x1x240最优解目标函数等值线0, 021xx25402402302021212121XXXXXXXXZMax三、二维线性规划的图解法2021三、二维线性规划的图解法3、几个概念 （1）法向量 正法向量和负法向量。由目标函数系数组成的与等值线垂直的向量，称为正法向量。正法向量的反号称为负法向量。 （2）等值线 使目标函数取相等值的所有点的集合，称为目标函数的等值线。22三、二维线性规划的图解法3、几个概念 （3）可行解 由约

10、束条件和变量取值限制围成的公共区域中的每一个点都称为线性规划问题的可行解。 （4）可行域 所有可行解的集合，构成线性规划问题的可行域。23三、二维线性规划的图解法4、解的状态（1）唯一解（2）无穷多个最优解 (目标函数直线与可行域某直线重合) max x1+2x2 s.t. -x1 + x22 x1+2x210 3x1+x215 x1,x20AB24三、二维线性规划的图解法4、解的状态（3）有可行解但无最优解（遗漏约束条件） Min x1-2x2 s.t. -x1 + x22 -x1+2x26 x1 , x20（4）无可行解也即问题无解 （建模错误） Min x1+2x2 s.t. x1+x21 2x1+x24 x1,x2025三、二维线性规划的图解法5、图解法延伸图解法延伸 （1）若线性规划问题有解，则可行域是凸集 （2）若存在最优解，则唯一最优解一定是可行域凸集的某个顶点，无穷最优解一定是可行域的某个边或面。