第一讲线性规划第一讲线性规划(LinearProgramming,LP)概述•线性规划问题的提出最早是1939年由前苏联数学家康托洛维奇在研究铁路运输的组织问题、工业生产的管理问题时提出来的。•1947年，美国学者丹西格（G.B.Dantzig）提出了线性规划问题的单纯形方法。•线性规划理论最为成熟、应用最为广泛第一节线性规划问题及其数学模型一、问题提出例例11（生产计划问题）某企业利用A、B、C三种资源，在计划期内生产甲、乙两种产品，已知生产单位产品资源的消耗、单位产品利润等数据如下表，问如何安排生产计划使企业利润最大？产品资源甲乙资源限制ABC120111300kg400kg250kg单位产品利润(元/件)50100•决策变量：x1、x2——分别代表甲、乙两种产品的生产数量。目标函数：maxz=50x1+100x2约束条件：x1+x2≤3002x1+x2≤400x2≤250即有：maxz=50x1+100x2x1+x2≤3002x1+x2≤400x2≤250x1、x2≥0称之为上述问题的数学模型。•例2靠近某河流有两个化工厂，流经第一化工厂的河流流量为每天500万m3，在两个工厂之间有一条流量为200万m3的支流。两化工厂每天排放某种有害物质的工业污水分别为2万m3和1.4万m3。从第一化工厂排出的工业污水流到第二化工厂以前，有20%可以自然净化。环保要求河流中工业污水含量不能大于0.2%。两化工厂处理工业污水的成本分别为1000元/万m3和800元/万m3。现在要问在满足环保要求的条件下，每厂各应处理多少工业污水，使这两个工厂处理工业污水的费用最小.工厂1工厂2200万m3500万m3•决策变量：x1、x2——分别代表工厂1和工厂2处理污水的数量(万m3)。•则目标函数：minz=1000x1+800x2•约束条件：第一段河流（工厂1——工厂2之间）：(2－x1)/500≤0.2%第二段河流：[0.8(2－x1)+(1.4－x2)]/700≤0.2%此外有：x1≤2；x2≤1.4•化简有：minz=1000x1+800x2x1≥10.8x1+x2≥1.6x1≤2x2≤1.4x1、x2≥0称之为上述问题的数学模型。–从上述两个例子，我们可以总结出线性规划的数学模型的一般形式。max(min)z=c1x1+c2x2+…+cnxn——目标函数a11x1+a12x2+…+a1nxn=(≥,≤)b1a21x1+a22x2+…+a2nxn=(≥,≤)b2——约束条件…………………………………am1x1+am2x2+…+amnxn=(≥,≤)bmx1，x2，…，xn≥0–模型特点：目标函数(Objectivefunction)与约束条件(Constraint)均为线性的；目标函数实现极大化或极小化。第二节线性规划图解法(GraphicalSolution)一、基本概念•可行解(FeasibleSolution)——任一满足约束条件的一组决策变量的数值；•可行域(Feasi...
