线性规划的概念及图解法

例1：某中药厂用当归作原料制成当归丸与当归膏，生产1盒当归丸需要5个劳动工时，使用2kg当归原料，销售后获得利润160元；生产1盒当归膏需要2个劳动工时，使用5kg当归原料，销售后获得利润80元；工厂现有可供利用的劳动工时为4000工时，可供使用的当归原料为5800kg，为避免当归原料存放时间过长而变质，要求把5800kg当归原料都用掉。问工厂如何安排生产，才能使得两种产品销售后获得的总利润最大？一、概念的引出解设工厂生产x1盒当归丸与x2瓶当归膏，可建立以下数学模型：）2,1（i,0x5800x5x24000x2x5x80x160Smaxi212121整数目标函数为：约束条件为：21x80x160Smax）2,1（i,0x5800x5x24000x2x5i2121整数决策变量为：x1,x2例2某公司由于生产需要，共需要A，B两种原料至少350吨（A，B两种材料有一定替代性），其中A原料至少购进125吨。但由于A，B两种原料的规格不同，各自所需的加工时间也是不同的，加工每吨A原料需要2个小时，加工每吨B原料需要1小时，而公司总共有600个加工小时。又知道每吨A原料的价格为2万元，每吨B原料的价格为3万元，试问在满足生产需要的前提下，在公司加工能力的范围内，如何购买A，B两种原料，使得购进成本最低？解：设购买A种原料为x1，B种原料为x2，可建立以下数学模型：目标函数：MinS=2x1+3x2约束条件：s.t.x1+x2≥350x1≥1252x1+x2≤600x1,x2≥0s.t.是subjectto的缩写。意思为“满足于，受约束于”决策变量为：x1,x2数学规划模型实际问题中的优化模型mixgtsxxxxfzMaxMiniTn,2,1,0)(..),(),()(1或x~决策变量f(x)~目标函数gi(x)0~约束条件数学规划线性规划非线性规划整数规划线性规划问题（LP）：一组线性不等式约束下求线性目标函数的极大值或极小值问题。决策变量的一组取值便构成了线性规划问题的一个解；满足约束条件的解称为可行解；所有可行解构成的集合称为可行解集；使目标函数达到所追求极值的可行解称为最优解；最优解所对应的目标函数值称为最优值。相关定义：二、线性规划的表现形式一般形式：目标函数和所有的约束条件都是设计变量的线性函数.目标函数：Max(Min）z=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤（=,≥）b1a21x1+a22x2+…+a2nxn≤（=,≥）b2…………am1x1+am2x2+…+amnxn≤（=,≥）bmx1，x2，…，xn≥0基本线性规划形式目标函数：Max（Min)S=c1x1+c2x2+…+cnxn约束条件：s.t.a11x1+a12x2+…+a1nxn≤b1a21x1+a22x2+…+a2nxn≤b2…………am1x1+am2x2+…+amnxn≤bmx1，x2，…，xn≥0，bi≥0建模过程1.理解要解决的问题，了解解题的目标和条件；2.定义决策变量（x1，x2，…，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件三、线性规划问题的数学模型•生产安排•原料搭配问题•条件下料问题•物资运输问题某家具厂需要长80cm的角钢与长60cm的角钢，它们皆从长210cm的角钢截得。现在对长80cm角钢的需要量为150根，对长60cm角钢的需要量为330根。问工厂应如何下料，才能使得用料最省？写出数学模型。条件下料问题1分析：共有三种下料方式，第一种是将1根长210的角钢截得2根长80cm的角钢；第二种是将1根长210的角钢截得1根长80cm和2根60cm的角钢；第三种是将210cm的角钢截得3根长60cm的角钢。现这三种下料方式应该混合使用。解：设第一种下料方式用掉x1根角钢；第二种下料方式用掉x2根角钢；第三种下料方式用掉x3根角钢；变量x1x2x3即为决策变量。数学模型为：）（ixxxxxxxxSi3,2,1,0330321502min3121321整数某车间有一批长度为7.4m的同型钢管，因生产需要，需将其截成长2.9m、2.1m、1.5m三种不同长度的管料。若三种管料各需100根，问应如何下料，才能使得用料最省？写出数学模型。条件下料问题2ⅠⅡⅢⅣⅤ2.9120102.1002211.531203合计/m7.47.37.27.16.6料头/m00.10.20.30.8规格/m方案下料方案分析：解：设第一种下料方式用掉x1根管料；第二种下料方式用掉x2根管料；第三种下料方式用掉x3根管料；第四种下料方式用掉x4根管料；第五种下料方式用掉x5根管料；变量x1x2x3x4x5即为决策变量。数学模型为：）（ixxxxxxxxxxxxxxxxSi5,4,3,2,1,0100323100221002min532154342154321整数例1.目标函数：MaxS=50x1+100x2约束条件：s.t.x1+x2≤3002x1+x2≤400x2≤250x1≥0x2≥0四图解法对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。四图解法(1)分别取决策变量X1,X2为坐标向量建立直角坐标系。取各约束条件的公共部分x1x2x2=0x1=0x2=250x1+x2=3002x1+x2=400图2-1（2）目标函数z=50x1+100x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50x1+100x2图2-2z=27500=50x1+100x2z=0=50x1+100x2z=10000=50x1+100x2CBADE•重要结论1：–当线性规划问题的可行域非空时，它是有界或无界的凸多边形（凸集）;–如果线性规划有最优解，则一定有一个可行域的顶点对应一个最优解；–无穷多个最优解。若将例1中的目标函数变为maxz=50x1+50x2，则线段BC上的所有点都代表了最优解；•重要结论2：–无界解。即可行域的范围延伸到无穷远，目标函数值可以无穷大或无穷小。一般来说，这说明模型有错，忽略了一些必要的约束条件；–无可行解。若在例1的数学模型中再增加一个约束条件4x1+3x2≥1200，则可行域为空域，不存在满足约束条件的解，当然也就不存在最优解了。