线性规划图解法和标准化.pptx
《线性规划图解法和标准化.pptx》由会员分享,可在线阅读,更多相关《线性规划图解法和标准化.pptx(22页珍藏版)》请在淘文阁 - 分享文档赚钱的网站上搜索。
1、会计学1线性规划图解法和标准化线性规划图解法和标准化2几何概念几何概念代数概念代数概念 直 线满足一个等式约束的解 半平面满足一个不等式约束的解半平面的交集:凸多边形满足一组不等式约束的解目标函数等值线:一组平行线 目标函数值等于一个常数的解1图图 解解 法法注:当目标函数求极大时,等值线向右移;当目标函数求极小时,等值线向左移。注:当目标函数求极大时,等值线向右移;当目标函数求极小时,等值线向左移。第2页/共22页第1页/共22页311图图图图 解解解解 法法法法 (1)(1)分别取决策变量分别取决策变量X X1 1和和X X2 2为横轴和纵轴,建立直角坐标系。为横轴和纵轴,建立直角坐标系。
2、在直角坐标系中,图上任意一点的坐标代表了决策变量的在直角坐标系中,图上任意一点的坐标代表了决策变量的一组取值,例一组取值,例1 1的每个约束条件都代表一个半平面。的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=0第3页/共22页第2页/共22页411图图图图 解解解解 法法法法(2 2)对每个不等式)对每个不等式(约束条件约束条件),先取其等式在坐标系中作直,先取其等式在坐标系中作直线,然后确定不等式所决定的半平面。线,然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+
3、x2=400300200300400第4页/共22页第3页/共22页511图图图图 解解解解 法法法法(3 3)把五个图合并成一个图,取各约束条件的公共部分,如)把五个图合并成一个图,取各约束条件的公共部分,如图图3-13-1所示。所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图3-1第5页/共22页第4页/共22页611图图图图 解解解解 法法法法(4 4)目标函数)目标函数Z=50 xZ=50 x1 1+100 x+100 x2 2,当,当Z Z取某一固定值时得到一条取某一固定值时得到一
4、条直线,直线上的每一点都具有相同的目标函数值,称之为直线,直线上的每一点都具有相同的目标函数值,称之为“等值线等值线”。平行移动等值线,。平行移动等值线,当移动到当移动到B B点时,点时,Z Z在可在可行域内实现了最大化行域内实现了最大化。A A,B B,C C,DD,E E是可行域的顶点,是可行域的顶点,对有限个约束条件,则其可行域的顶点也是有限的。对有限个约束条件,则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图3-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE第6页/共22页第5页
5、/共22页7例例2 2 maxmax z=x z=x1 1+3x+3x2 2s.t.s.t.x x1 1+x+x2 266-x-x1 1+2x+2x2 288x x1 1 0,x0,x2 200可行域目标函数等值线最优解64-860 x1x211图图图图 解解解解 法法法法第7页/共22页第6页/共22页8进进进进 一一一一 步步步步 讨讨讨讨 论论论论 例例例例3 3 3 3 某公司由于生产需要,共需要某公司由于生产需要,共需要A A、B B两种原料至少两种原料至少350350吨(吨(A A,B B两种材料有一定替代性),其中两种材料有一定替代性),其中A A原料至少购进原料至少购进1251
6、25吨。但由于吨。但由于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两种两种原料,使得购进成本最
7、低?原料,使得购进成本最低?第8页/共22页第7页/共22页9进进进进 一一一一 步步步步 讨讨讨讨 论论论论解:目标函数:解:目标函数:Min Z=2xMin Z=2x1 1+3 x+3 x2 2 约束条件:约束条件:s.t.xs.t.x1 1+x+x2 2 350 350 x x1 1 125125 2 x 2 x1 1+x+x2 2 600600 x x1 1 ,x,x2 2 0 0 采用图解法,如左图:得采用图解法,如左图:得QQ点坐点坐标(标(250250,100100)为最优解。)为最优解。100200300400500600100200300400600500 x1=125x1+
8、x2=3502x1+3x2=8002x1+3x2=9002x1+x2=6002x1+3x2=1200 x1 x2 Q第9页/共22页第8页/共22页10重要结论1:线性规划的可行域是凸集线性规划的可行域是凸集可行域的顶点为有限个可行域的顶点为有限个线性规划的最优解一定可以在某个顶点上实现线性规划的最优解一定可以在某个顶点上实现凸集凸集不是凸集顶点1图图 解解 法法第10页/共22页第9页/共22页111图图 解解 法法 重要结论重要结论重要结论重要结论2 2:n n如果线性规划有如果线性规划有唯一最优解唯一最优解(例(例1 1、2 2、3 3),则一定有一个可行域的顶点对),则一定有一个可行域
9、的顶点对应最优解;应最优解;n n无穷多个最优解无穷多个最优解。若将例。若将例1 1中的目标中的目标函数变为函数变为max z=50 xmax z=50 x1 1+50 x+50 x2 2,则线段,则线段BCBC上的所有点都代表最优解;上的所有点都代表最优解;n n无界解无界解。即可行域的范围延伸到无穷。即可行域的范围延伸到无穷远,目标函数值可以无穷大或无穷小。远,目标函数值可以无穷大或无穷小。一般来说,这说明模型有错,忽略了一般来说,这说明模型有错,忽略了一些必要的约束条件;一些必要的约束条件;n n无可行解无可行解。若在例。若在例1 1的数学模型中再的数学模型中再增加一个约束条件增加一个约
10、束条件4x4x1 1+3x+3x2 212001200,则可,则可行域为空域,不存在满足约束条件的行域为空域,不存在满足约束条件的解,当然也就不存在最优解。解,当然也就不存在最优解。第11页/共22页第10页/共22页1222线性规划的标准化线性规划的标准化线性规划的标准化线性规划的标准化一般形式一般形式一般形式一般形式目标函数:目标函数:Max Max(MinMin)Z=cZ=c1 1 x x1 1+c+c2 2 x x2 2+c+cn n x xn n 约束条件:约束条件:s.t.s.t.a a1111 x x1 1+a a1212 x x2 2+a a1n1n x xn n (=,=,)
11、b b1 1 a a2121 x x1 1+a a2222 x x2 2+a a2n2n x xn n (=,=,)b b2 2 a am1m1 x x1 1+a am2m2 x x2 2+a amnmn x xn n (=,=,)b bmm x x1 1,x x2 2,x xn n 0 0 n n标准形式标准形式标准形式标准形式目标函数:目标函数:MaxMax Z =c Z =c1 1 x x1 1+c+c2 2 x x2 2+c+cn n x xn n 约束条件:约束条件:s.t.s.t.a a1111 x x1 1+a a1212 x x2 2+a a1n1n x xn n =b b1
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 线性规划 图解法 标准化
限制150内