线性规划的图解法和标准化.ppt

《线性规划的图解法和标准化.ppt》由会员分享，可在线阅读，更多相关《线性规划的图解法和标准化.ppt（22页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵例例1.目标函数：Maxz=50 x1+100 x2约束条件：s.t.x1+x2300(A)2x1+x2400(B)x2250(C)x10(D)x20(E)得到最优解：x1=50，x2=250最优目标值z=275001图图解解法法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：1 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵几何

2、概念几何概念代数概念代数概念直线满足一个等式约束的解半平面满足一个不等式约束的解半平面的交集：凸多边形满足一组不等式约束的解目标函数等值线：一组平行线目标函数值等于一个常数的解1图图解解法法注：当目标函数求极大时，等值线向右移；当目标函数求极小时，等值线向左移。注：当目标函数求极大时，等值线向右移；当目标函数求极小时，等值线向左移。2 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵1图图解解法法 (1)分别取决策变量X1和X2为横轴和纵轴，建立直角坐标系。在直角坐标系中，图上任意一点的坐标代表了决策变量的一组取值，例1的每个

3、约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=03 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵1图图解解法法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=4003002003004004 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵1图图解解法法（3）把五个图合

4、并成一个图，取各约束条件的公共部分，如图3-1所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图3-15 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵1图图解解法法（4）目标函数Z=50 x1+100 x2，当Z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，Z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件，则其可行域的顶点也是

5、有限的。x1x2z=20000=50 x1+100 x2图3-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE6 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵例2max z=x1+3x2s.t.x1+x26-x1+2x28x10,x20可行域目标函数等值线最优解64-860 x1x21图图解解法法7 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵进进一一步步讨讨论论 例例3 3

6、某公司由于生产需要，共需要A、B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A、B两种原料，使得购进成本最低？8 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵进进一一步步讨讨论论解：目标函数：MinZ=2x1+3x2约束条件：s

7、.t.x1+x2350 x11252x1+x2600 x1,x20采用图解法，如左图：得Q点坐标（250，100）为最优解。100200300400500600100200300400600500 x1=125x1+x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200 x1x2Q9 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵重要结论1：线性规划的可行域是凸集可行域的顶点为有限个线性规划的最优解一定可以在某个顶点上实现凸集凸集不是凸集顶点1图图解解法法10 数数 据据 模模

8、型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵1图图解解法法重要结论重要结论2：如果线性规划有唯一最优解（例1、2、3），则一定有一个可行域的顶点对应最优解；无穷多个最优解。若将例1中的目标函数变为maxz=50 x1+50 x2，则线段BC上的所有点都代表最优解；无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解。11 数数 据据 模模 型型

9、与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化一般形式一般形式目标函数：Max（Min）Z=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bm x1，x2，xn0标准形式标准形式目标函数：MaxZ=c1x1+c2x2+cnxn约束条件：s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bm x1，x2，xn0，

10、bi0注：只能使用一个脚码（变量连续编号），不能使用多重脚码12 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化 可以看出，线性规划的标准形式有如下四个特点：目标极大化；约束条件为等式；决策变量均非负；约束条件右端常数项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:13 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化1 1、变量不是大于等于、变量不是大

11、于等于0 0的问题的问题（1）若xj0,令 x xj j=-=-x xj j，则xj0（2）若变量为无约束 在标准形式中，必须每一个变量均有非负约束。当某一个变量xj没有非负约束时，可以令：x xj j=x xj j-x xj j”其中 xj0，xj”0 即用两个非负变量之差来表示一个无符号限制的变量，当然xj的符号取决于xj和xj”的大小。14 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化2 2、目标函数为极小化的问题：、目标函数为极小化的问题：设目标函数为：Min Z=c1x1+c2x

12、2+cnxn (可以)令 Z -Z，则该极小化问题与下面的极大化问题有相同的最优解，即：Max Z=-c1x1-c2x2-cnxn 但必须注意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即：Min Z -Max Z3 3、右端常数项为负数的问题：、右端常数项为负数的问题：在标准形式中，要求约束条件右端常数项必须全部是非负的。当某个右端常数项为负时，如 bi0，则把该约束条件两端同时乘以(-1)，得到：-ai1 x1-ai2 x2-ain xn=-bi15 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵

13、观兵2线性规划的标准化线性规划的标准化4 4、约束条件不是等式的问题：、约束条件不是等式的问题：设约束条件为 ai1 x1+ai2 x2+ain xn bi 可以引进一个新的变量s s，使它等于约束右边与左边之差 s=bi(ai1 x1+ai2 x2+ain xn)显然，s 也具有非负约束，即：s 0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi16 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化 当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，

14、类似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 显然，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-s=bi17 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。如果原问题中有若干个非等式约束条件，则将其转化为标准形式时，必须对各个约束条件引进不同的松弛变量或剩余变量。结论：当约束条件为：结论：当约束条件

15、为：“”：在约束条件的左端加入非负的松弛变量：在约束条件的左端加入非负的松弛变量“”：在约束条件的左端减去非负的剩余变量：在约束条件的左端减去非负的剩余变量注：注：*松弛变量和剩余变量在目标函数中的系数为松弛变量和剩余变量在目标函数中的系数为0 0*18 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵例例4：将下列线性规划模型标准化：将下列线性规划模型标准化：2线性规划的标准化线性规划的标准化19 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的

16、标准化线性规划的标准化20 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化例例5：将以下线性规划问题转化为标准形式：将以下线性规划问题转化为标准形式Minf=2x1-3x2+4x3s.t.3x1+4x2-5x362x1+x38x1+x2+x3=-9x1,x2,x3 0解：首先，将目标函数转换成极大化：令 z=-f=-2x1+3x2-4x3 其次考虑约束条件，有2个不等式约束，引进松弛变量X4和剩余变量x5。第三个约束条件的右端常数项为负，在等式两边同时乘-1。21 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化 通过以上变换，可以得到以下标准形式的线性规划问题：Max z=-2x1+3 x2-4x3 s.t.3x1+4x2-5x3 +x4 =6 2x1 +x3 -x5 =8 -x1 -x2 -x3 =9 x1,x2,x3,x4,x5 022