第一章线性规划及单纯形法

第一章线性规划及单纯形法LinearProgrammingandSimplexMethod北京物资学院运筹学教学课件北京物资学院信息学院李珍萍2013年9月第一节线性规划问题的数学模型第二节两变量线性规划问题的图解法第三节线性规划问题的基本定理第四节单纯形法第五节单纯形法的进一步讨论第六节线性规划应用案例分析本章内容第一节线性规划问题的数学模型线性规划是运筹学中研究较早、发展较快、应用较广、比较成熟的一个分支，它是一种合理利用和调配有限资源的数学方法。线性规划研究的问题：极大化问题：面对一定的资源，要求充分利用，以获得最大的经济效益。极小化问题：给定一项任务，要求统筹安排，尽量做到用最少的人力、物力资源去完成这一任务。一、引例：生产安排问题原料配比问题运输问题二、线性规划问题的结构特征三、线性规划问题的数学模型线性规划问题的一般形式线性规划问题的标准形式一般形式向标准形式的转化本节内容安排一、引例例1[生产安排问题]某企业使用A、B、C三台机器生产甲、乙两种产品。已知未来两周内A、B、C三台机器的使用时间分别不得超过80，60，45小时，生产每单位产品所需要各台机器的加工时间及每单位产品的利润如下表所示，问企业如何安排未来两周的生产，才能使总利润达到最大？产品机器甲乙可利用的机时（小时）A2480B3260C3045单位产品的利润（元）5060可控因素：生产两种产品的数量，设分别为x1,x2，目标是生产利润最大，设生产利润为z.利润函数为：125060zxx限制条件：三台设备的使用时间不超过可利用机时设备A:2x1+4x2≤80设备B:3x1+2x2≤60设备C:3x1≤45蕴涵约束：产量为非负x10,x20目标函数约束条件121212112max5060248032603450,0zxxxxxxxxx设生产甲乙两种产品的数量分别为x1,x2单位，总利润为z.例2[原料配比问题]某企业使用三种原料B1,B2,B3配置某种食品，要求食品中蛋白质、脂肪、糖、维生素的含量分别不低于15、20、25、30单位。以上三种原料的单价以及每单位原料所含各种成分的数量如下表所示，问应如何配置食品，才能使成本最低？原料营养成分B1B2B3食品中营养成分的需要量蛋白质56815脂肪34620糖85425维生素1012830原料单价（元）202530设x1,x2,x3分别表示原料B1,B2,B3的用量，z表示食品成本。该问题的数学模型为：123123123123123123min2025305681534620..854251012830,,0zxxxxxxxxxstxxxxxxxxx例3[运输问题]设要从甲地调出物资2000吨，从乙地调出物资600吨，从丙地调出物资500吨，分别供应给A地1700吨、B地1100吨、C地200吨、D地100吨。已知每吨运费如下表所示。假定运费与运量成正比例，问怎样才能找到一个总运费最省的调拨计划？丙1726384315375151乙1572521甲DCBA销地产地单位：元/吨x22x11x12x13x21x23x31x32x33x14x24x34用（i=1,2,3;j=1,2,3,4）分别表示从甲乙丙三个产地运往A,B,C,D四个销地的物资数量。ijx则该问题的数学模型为111213142122232431323334min21257155151371543382617zxxxxxxxxxxxx11121314212223243132333411213112223213233314243420006005001700..11002001000,1,2,3;1,2,3,4ijxxxxxxxxxxxxxxxstxxxxxxxxxxij简化表达式34114131min1,2,3..1,2,3,401,2,3;1,2,3,4ijijijijijijjiijzcxxaistxbjxij二、线性规划问题的结构特征：（1）都有一组决策变量。（2）都有一组线性的约束条件，它们是线性等式或不等式。（3）都有一个确定的目标，这个目标可以表示成决策变量的线性函数，根据问题不同，有的要求实现极大化，有的要求实现极小化。线性规划问题的本质：研究在一组线性约束下，一个线性函数的极值问题。所以称为线性规划linearprogramming(LP)1.线性规划问题的一般形式1122max(min)...nnzcxcxcx1111221121122222112212...(,)...(,)..........................................(,),,...,0nnnnmmmnnmnaxaxaxbaxaxaxbaxaxaxbxxxs.t（1）（2）（3）一般形式的简化表达1(,)1,2,...,01,2,...,nijjijjaxbimxjn1max(min)njjjzcx三、线性规划问题的数学模型：规范形式极大化问题极小化问题11221111221121122222112212min.....................................................,,...,0nnnnnnmmmnnmnzcxcxcxaxaxaxbaxaxaxbstaxaxaxbxxx11221111221121122222112212max.....................................................,,...,0nnnnnnmmmnnmnzcxcxcxaxaxaxbaxaxaxbstaxaxaxbxxx2.线性规划的标准形式1maxnjjjzcx10nijjijjaxbx(1,2,...,)im(1,2,...,)jns.t.1122max...nnzcxcxcx1111221121122222112212................................................,,...,0nnnnmmmnnmnaxaxaxbaxaxaxbaxaxaxbxxxs.t（1）（2）（3）标准形式的简化表达标准形式的矩阵表达max0ZCXAXbXmnmmnnaaaaaaaaaA.....................212222111211nxxxX21mbbbb21ncccC21标准形式的向量表达1max0njjjZCXPxbX12jjjmjaaPa标准形式的特点：(1).目标函数极大化(2).约束条件全部是等式(3).所有的变量都是非负的(4).约束条件右端常数为非负的3.一般形式向标准形式的转化：(1)目标函数极大化对于极小化的目标函数可以等价地转化成求1njjjzcx'1()njjjzzcx的极大化。(2)不等式约束化等式约束对于形的不等式，可以在不等式的左边加上（减去）一个非负的变量使不等式化成等式。这样的变量称为松弛（剩余）变量。()例如：1nijjijaxb1nijjniijaxxb1nijjijaxb1nijjniijaxxb(3)自由变量化非负变量的差自由变量可以用两个非负变量的差代替，例如对于一个符号无限制的变量，可以引进两个非负变量并设jx'0,0jjxx'jjjxxx(4)约束条件右端的负常数化为正常数对于右端常数为负数的约束，可以两端同时乘以-1。取值小于等于0的变量，可以用一个非负变量的相反数表示。例将下列LP问题化成标准形式121212121min222250zxxxxxxxxxs.t.''122'1223'1224'1225'122345max()2()22()2()5,,,,,0zxxxxxxxxxxxxxxxxxxxxxs.t.课堂练习：将下列LP问题化成标准形式12312312312312min232832532360,0zxxxxxxxxxxxxxx''1233''12334''12335''1233''123345max'2328322532336,,,,,0zxxxxxxxxxxxxxxxxxxxxxxxx'''33311,,zzxxxxx解：令作业：P46页习题1-4题第二节两变量线性规划问题的图解法一、几个概念二、两变量线性规划问题的图解法三、两变量线性规划问题解的性质可行解：任何一组满足所有约束条件的决策变量值称为LP问题的一个可行解。12,,...,nxxx最优解：使目标函数达到最大（小）值的可行解。最优值：最优解对应的目标函数值。可行域：所有可行解的集合称为可行域。{,0}DXAXbX一、几个概念：二、两变量LP问题的图解法图解法是根据平面直角坐标系和二元一次方程（不等式）的特点设计的。1.图解法的一般步骤：（1）建立直角坐标系，以为横轴，为纵轴。1x2x（2）将约束条件在直角坐标系中表示，并找出可行域。（3）作出目标函数的等值线簇，找出目标函数值的增加（或减小）方向，用箭头表示。（4）确定出问题的最优解。若为极大（小）化问题，目标函数沿增加（减小）方向平移，与可行域的最后一个交点即为最优解。例1用图解法解下列线性规划问题最优解x*=(10,15)T,最优值z*=5010+6015=1400.010203040102030x2x1(1)(10,15)可行域有界,有唯一最优解z=0z=600121212112max506024803260..3450,0zxxxxxxstxxx例2121212212max2263212..20,0zxxxxxxstxxx⑴⑵⑶无穷多最优解x1x212121212max22..1,0zxxxxstxxxx例3、⑴⑵无有限最优解x1x212121212min22..1,0zxxxxstxxxx⑴⑵可行域无界,有唯一最优解x1x2例4、12121212min321..236,0zxxxxstxxxx⑴⑵x1x2可行域为空,无可行解例5、可行域是空集。可行域存在，则一定是一个凸多边形.无有限最优解（可行域一定无界）。最优解存在且唯一，则一定在顶点上达到。最优解存在且不唯一，一定存在一个顶点是最优解。2.图解法求解两变量LP问题时可能出现的情况：三.两变量线性规划问题解的性质1.两变量线性规划问题的可行域是若干个半平面的交集，它是一个有界或无界的凸多边形，并且有有限个顶点。2.对于给定的线性规划问题，如果它有最优解，最优解总可以在可行域的某个顶点上达到。第三节线性规划问题的基本定理一、可行区域的几何结构二、基可行解及线性规划的基本定理一、可行区域的几何结构1.基本假设2.凸集及其性质3.可行域的凸性4.问题1.基本假设考虑线性规划的标准形式max..0zCXAXbstX其中,,,TnmmnXCRbRAR，并且假定可行域{,0}nDXRAXbX不空，系数矩阵A是行满秩的，m