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

线性规划的图解法和标准化第1页，共23页，星期日，2025年，2月5日例1.目标函数：Maxz=50x1+100x2约束条件：s.t.x1+x2≤300(A)2x1+x2≤400(B)x2≤250(C)x1≥0(D)x2≥0(E)得到最优解：x1=50，x2=250最优目标值z=27500§1图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过例1详细讲解其方法：第2页，共23页，星期日，2025年，2月5日几何概念代数概念直线满足一个等式约束的解半平面满足一个不等式约束的解半平面的交集：凸多边形满足一组不等式约束的解目标函数等值线：一组平行线目标函数值等于一个常数的解§1图解法注：当目标函数求极大时，等值线向右移；当目标函数求极小时，等值线向左移。第3页，共23页，星期日，2025年，2月5日§1图解法(1)分别取决策变量X1和X2为横轴和纵轴，建立直角坐标系。在直角坐标系中，图上任意一点的坐标代表了决策变量的一组取值，例1的每个约束条件都代表一个半平面。x2x1X2≥0X2=0x2x1X1≥0X1=0第4页，共23页，星期日，2025年，2月5日§1图解法（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300x1+x2≤300x1+x2=3001001002002x1+x2≤4002x1+x2=400300200300400第5页，共23页，星期日，2025年，2月5日§1图解法（3）把五个图合并成一个图，取各约束条件的公共部分，如图3-1所示。100100x2≤250x2=250200300200300x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图3-1第6页，共23页，星期日，2025年，2月5日§1图解法（4）目标函数Z=50x1+100x2，当Z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，Z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件，则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图3-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE第7页，共23页，星期日，2025年，2月5日例2max z=x1+3x2 s.t. x1+x2≤6 -x1+2x2≤8 x1≥0,x2≥0可行域目标函数等值线最优解64-860x1x2§1图解法第8页，共23页，星期日，2025年，2月5日进一步讨论例3某公司由于生产需要，共需要A、B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A、B两种原料，使得购进成本最低？第9页，共23页，星期日，2025年，2月5日进一步讨论解：目标函数：MinZ=2x1+3x2约束条件：s.t.x1+x2≥350x1≥1252x1+x2≤600x1,x2≥0采用图解法，如左图：得Q点坐标（250，100）为最优解。1002003004005006001