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

数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 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 课课 程程 主讲：赵观兵主讲：赵观兵几何概念几何概念代数概念代数概念直线满足一个等式约束的解半平面满足一个不等式约束的解半平面的交集：凸多边形满足一组不等式约束的解目标函数等值线：一组平行线目标函数值等于一个常数的解1图图解解法法注：当目标函数求极大时，等值线向右移；当目标函数求微小时，等值线向左移。注：当目标函数求极大时，等值线向右移；当目标函数求微小时，等值线向左移。2 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵1图图解解法法 (1)分别取决策变量X1和X2为横轴和纵轴，建立直角坐标系。在直角坐标系中，图上随意一点的坐标代表了决策变量的一组取值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=03 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵1图图解解法法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所确定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=4003002003004004 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵1图图解解法法（3）把五个图合并成一个图，取各约束条件的公共部分，如图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是可行域的顶点，对有限个约束条件，则其可行域的顶点也是有限的。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 某公司由于生产须要，共须要某公司由于生产须要，共须要A A、B B两种原料至少两种原料至少350350吨（吨（A A，B B两种材料有确定替代性），其中两种材料有确定替代性），其中A A原料至少购进原料至少购进125125吨。但由于吨。但由于A A，B B两种原料的规格不同，各自所需的加工时间两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨也是不同的，加工每吨A A原料须要原料须要2 2个小时，加工每吨个小时，加工每吨B B原料需原料需要要1 1小时，而公司总共有小时，而公司总共有600600个加工小时。又知道每吨个加工小时。又知道每吨A A原料的原料的价格为价格为2 2万元，每吨万元，每吨B B原料的价格为原料的价格为3 3万元，试问在满足生产需万元，试问在满足生产需要的前提下，在公司加工实力的范围内，如何购买要的前提下，在公司加工实力的范围内，如何购买A A、B B两种两种原料，使得购进成本最低？原料，使得购进成本最低？8 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵进进一一步步讨讨论论解：目标函数：MinZ=2x1+3x2约束条件：s.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 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵1图图解解法法重要结论重要结论2：假如线性规划有唯一最优解（例假如线性规划有唯一最优解（例1、2、3），则确定有一），则确定有一个可行域的顶点对应最优解；个可行域的顶点对应最优解；无穷多个最优解。若将例无穷多个最优解。若将例1中的目标函数变为中的目标函数变为maxz=50 x1+50 x2，则线段，则线段BC上的全部点都代表最优解；上的全部点都代表最优解；无界解。即可行域的范围延长到无穷远，目标函数值可无界解。即可行域的范围延长到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽以无穷大或无穷小。一般来说，这说明模型有错，忽视了一些必要的约束条件；视了一些必要的约束条件；无可行解。若在例无可行解。若在例1的数学模型中再增加一个约束条件的数学模型中再增加一个约束条件4x1+3x21200，则可行域为空域，不存在满足约束条，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解。件的解，当然也就不存在最优解。11 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化一般形式一般形式目标函数：目标函数：Max（Min）Z=c1x1+c2x2+cnxn约束条件：约束条件：s.t.a11x1+a12x2+a1nxn（=,）b1a21x1+a22x2+a2nxn（=,）b2am1x1+am2x2+amnxn（=,）bmx1，x2，xn0标准形式标准形式目标函数：目标函数：MaxZ=c1x1+c2x2+cnxn约束条件：约束条件：s.t.a11x1+a12x2+a1nxn=b1a21x1+a22x2+a2nxn=b2am1x1+am2x2+amnxn=bmx1，x2，xn0，bi0注：只能运用一个脚码（变量连续编号），不能运用多重注：只能运用一个脚码（变量连续编号），不能运用多重脚码脚码12 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化 可以看出，线性规划的标准形式有如下四个特点：目标极大化；约束条件为等式；决策变量均非负；约束条件右端常数项非负。对于各种非标准形式的线性规划问题，我们总可以通过以下变换，将其转化为标准形式:13 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化1 1、变量不是大于等于、变量不是大于等于0 0的问题的问题（1 1）若）若xj0,xj0,令令 xj=-xj xj=-xj，则，则xj0 xj0（2 2）若变量为无约束）若变量为无约束 在在标标准准形形式式中中，必必需需每每一一个个变变量量均均有有非非负负约约束束。当当某某一一个变量个变量xjxj没有非负约束时，可以令：没有非负约束时，可以令：xj=xj-xj”xj=xj-xj”其中其中 xj0 xj0，xj”0 xj”0 即即用用两两个个非非负负变变量量之之差差来来表表示示一一个个无无符符号号限限制制的的变变量量，当然当然xjxj的符号取决于的符号取决于xjxj和和xj”xj”的大小。的大小。14 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化2 2、目标函数为微小化的问题：、目标函数为微小化的问题：设目标函数为：设目标函数为：Min Z=c1x1+c2x2+cnxn Min Z=c1x1+c2x2+cnxn (可以可以)令令 Z Z -Z -Z，则该微小化问题与下面的极大化问题有相同的最优解，则该微小化问题与下面的极大化问题有相同的最优解，即：即：Max Z=-c1x1-c2x2-cnxn Max Z=-c1x1-c2x2-cnxn 但必需留意，尽管以上两个问题的最优解相同，但它们但必需留意，尽管以上两个问题的最优解相同，但它们最优解的目标函数值却相差一个符号，即：最优解的目标函数值却相差一个符号，即：Min Z Min Z -Max Z-Max Z3 3、右端常数项为负数的问题：、右端常数项为负数的问题：在在标标准准形形式式中中，要要求求约约束束条条件件右右端端常常数数项项必必需需全全部部是是非非负负的的。当当某某个个右右端端常常数数项项为为负负时时，如如 bi0bi0，则则把把该该约约束束条条件件两两端端同同时时乘乘以以(-1)(-1)，得得到到：-ai1-ai1 x1-ai2 x1-ai2 x2-x2-ain-ain xn xn=-bibi15 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化4 4、约束条件不是等式的问题：、约束条件不是等式的问题：设约束条件为设约束条件为 ai1 x1+ai2 x2+ain xn bi ai1 x1+ai2 x2+ain xn bi 可可以以引引进进一一个个新新的的变变量量s s，使使它它等等于于约约束束右右边边与与左左边边之差之差 s=bi(ai1 x1+ai2 x2+ain xn)s=bi(ai1 x1+ai2 x2+ain xn)明显，明显，s s 也具有非负约束，即：也具有非负约束，即：s 0 s 0，这时新的约束条件成为这时新的约束条件成为 ai1 x1+ai2 x2+ain xn+s=bi ai1 x1+ai2 x2+ain xn+s=bi16 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化 当约束条件为 ai1 x1+ai2 x2+ain xn bi 时，类似地令 s=(ai1 x1+ai2 x2+ain xn)-bi 明显，s 也具有非负约束，即s0，这时新的约束条件成为 ai1 x1+ai2 x2+ain xn-s=bi17 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化 为了使约束由不等式成为等式而引进的变量s,当不等式为“小于等于”时称为“松弛变量”；当不等式为“大于等于”时称为“剩余变量”。假如原问题中有若干个非等式约束条件，则将其转化为标准形式时，必需对各个约束条件引进不同的松弛变量或剩余变量。结论：当约束条件为：“”：在约束条件的左端加入非负的松弛变量“”：在约束条件的左端减去非负的剩余变量注：*松弛变量和剩余变量在目标函数中的系数为0*18 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵例例4：将下列线性规划模型标准化：将下列线性规划模型标准化：2线性规划的标准化线性规划的标准化19 数数 据据 模模 型型 与与 决决 策策江江 苏苏 大大 学学 MBA MBA 课课 程程 主讲：赵观兵主讲：赵观兵2线性规划的标准化线性规划的标准化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