运筹学课件-第一章线性规划资料

第一章第一章 线性规划与单纯线性规划与单纯形法形法5/25/202411.1 1.1 线性规划问题及其数学模型线性规划问题及其数学模型例1 产品生产计划问题 某工厂计划用现有的铜、铅两种资源生产甲、乙两种电缆，已知甲、乙两种电缆的单位售价分别为6万元和4万元。生产单位产品甲、乙电缆对铜、铅的消耗量及可利用的铜、铅数量如下表所示：5/25/20242 单位产品消耗量与价格表 另外，市场对乙电缆的最大需求量为7单位，而对甲电缆的需求量无限制。问该工厂应如何安排生产才能使工厂的总收入最大?5/25/20243例2 配料问题 某混合饲料加工厂计划从市场上购买甲、乙两种原料生产一种混合饲料。混合饲料对VA、VBl、VB2和VD的最低含量有一定的要求。已知单位甲、乙两种原料VA、VBl、VB2和VD的含量，单位混合饲料对VA、VBl、VB2和VD的最低含量以及甲、乙两种原料的单位价格如表所示。5/25/20244原料甲原料乙混合饲料最低含量VA含量0.50.52VBl含量10.33VB2含量0.20.61.2VD含量0.50.22原料单价(元)0.30.55/25/20245 问该加工厂应如何搭配使用甲乙两种原料，才能使混合饲料在满足VA、VBl、VB2和VD的最低含量要求条件下，总成本最小?5/25/20246例3 污水处理问题 环保要求河水含污低于2，河水可自身净化20%。问：化工厂1、2每天各处理多少污水，使总费用最少？200万m3500万m32万m31.4万m3化工厂1化工厂21000元/万m3800元/万m35/25/20247分析：设化工厂1处理污水x1万m3,化工厂2处理污水x2万m3。min z=1000 x1+800 x2 (2-x1)/500 2/1000 (1-0.2)(2-x1)+1.4-x2/(500+200)2/1000 x1 2 x2 1.4 x1，x2 0 这里min z:表示求z的最小值。5/25/20248以上数学模型有什么特点？以上数学模型有什么特点？线性规划模型的定义线性规划模型的定义线性规划的一般形式线性规划的一般形式5/25/20249建模过程：建模过程：1.理解要解决的问题，了解问题的目标和条件；2.定义决策变量（x1，x2，xn），每一组值表示一个方案；3.用决策变量的线性函数形式写出目标函数，确定最大化或最小化目标；4.用一组决策变量的等式或不等式表示解决问题过程中必须遵循的约束条件。5/25/202410线性规划的组成：线性规划的组成：目标函数 Max F 或 Min F约束条件 s.t.(subject to)满足于决策变量 用符号来表示可控制的因素5/25/202411在管理中一些典型的线性规划应用在管理中一些典型的线性规划应用合理利用线材问题：如何在保证生产的条件下，下料最少配料问题：在原料供应量的限制下如何获取最大利润投资问题：从投资项目中选取方案，使投资回报最大产品生产计划：合理利用人力、物力、财力等，使获利最大劳动力安排：用最少的劳动力来满足工作的需要运输问题：如何制定调运方案，使总运费最小5/25/202412 练 习 1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下：设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?5/25/202413 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样建立如下的数学模型：目标函数：Min x1+x2+x3+x4+x5+x6 约束条件：s.t.x1+x6 60 x1+x2 70 x2+x3 60 x3+x4 50 x4+x5 20 x5+x6 30 x1,x2,x3,x4,x5,x6 05/25/2024141.2 线性规划图解法线性规划图解法 对于只有两个决策变量的线性规划问题，可以在平面直角坐标系上作图表示线性规划问题的有关概念，并求解。下面通过案例详细讲解其方法：5/25/202415 例1、某工厂在计划期内要安排、两种产品的生产，已知生产单位产品所需的设备台时及A、B两种原材料的消耗、资源的限制，如下表：问题：工厂应分别生产多少单位、产品才能使工厂获利最多？5/25/202416线性规划模型：线性规划模型：目标函数：Max z=50 x1+100 x2 约束条件：s.t.x1+x2 300 2 x1+x2 400 x2 250 x1,x2 05/25/202417 (1)分别取决策变量X1,X2 为坐标向量建立直角坐标系。在直角坐标系里，图上任意一点的坐标代表了决策变量的一组值，例1的每个约束条件都代表一个半平面。x2x1X20X2=0 x2x1X10X1=0一、图解法求解步骤5/25/202418（2）对每个不等式(约束条件)，先取其等式在坐标系中作直线，然后确定不等式所决定的半平面。100200300100200300 x1+x2300 x1+x2=3001001002002x1+x24002x1+x2=4003002003004005/25/202419（3）把五个图合并成一个图，取各约束条件的公共部分，如图1-1所示。100100 x2250 x2=250200300200300 x1x2x2=0 x1=0 x2=250 x1+x2=3002x1+x2=400图1-15/25/202420（4）目标函数z=50 x1+100 x2，当z取某一固定值时得到一条直线，直线上的每一点都具有相同的目标函数值，称之为“等值线”。平行移动等值线，当移动到B点时，z在可行域内实现了最大化。A，B，C，D，E是可行域的顶点，对有限个约束条件则其可行域的顶点也是有限的。x1x2z=20000=50 x1+100 x2图1-2z=27500=50 x1+100 x2z=0=50 x1+100 x2z=10000=50 x1+100 x2CBADE5/25/202421例：用图解法解以下线性规划 max f(x)=6x1+4x2 s.t.2x1+x2 10 x1+x2 8 x2 7 x1 0,x2 05/25/202422二、线性规划解的几种情况 通过图解法，可以看出对于一般线性规划问题，求解结果有以下几种情况：1、唯一最优解、唯一最优解 2、无穷多最优解、无穷多最优解 3、无界解、无界解 4、无可行解、无可行解5/25/202423用图解法解下列线性规划问题，并指出问题是具有唯一最优解、无穷多最优解、无界解还是无可行解？1、Max z=x1+3x2 s.t.5 x1+10 x2 50 x1 +x2 1 x2 4 x1 0,x2 05/25/202424 2、Min z=x1+1.5x2 s.t.x1+3x2 3 x1 +x2 2 x1 0,x2 05/25/202425 3、Max z=2x1+2x2 s.t.x1-x2-1 -0.5 x1 +x2 2 x1 0,x2 05/25/2024264、Max z=x1+x2 s.t.x1-x2 0 3 x1 -x2-3 x1 0,x2 05/25/202427四、通过图解法，我们可以得到如下结论：1、线性规划的可行域为凸集。2、线性规划的最优解在凸集的某一顶点上达到（特殊情况为凸集的某一边界）。3、线性规划的可行域若有界，则一定有最优解。5/25/202428一、线性规划问题的标准形1、标准型 max z=c1x1+c2x2+cnxn a11x1+a12x2+a1nxn=b1 a21x1+a22x2+a2nxn=b2 am1x1+am2x2+amnxn=bm x1，x2，xn 0 1.3线性规划问题的单纯形法（线性规划问题的单纯形法（Simplex Method）5/25/2024295/25/202430用向量表示5/25/202431 用矩阵描述为：max z=CX AX=b X 0 其中:X=(x1,x2,xn)T C=(c1,c2,cn)b=(b1,b2,bm)T 5/25/2024322、将下列非标准型线性规划化为标准型线性规划（1）Min f(x)=3x1-2x2+4x3 s.t.2 x1+3x2+4x3 300 x1+5x2+6x3 400 x1+x2+x3 200 x1 0,x2 0,x3 正负不限5/25/202433（2）Min f(x)=-x1+2x2-3x3 s.t.x1+x2+x3 7 x1-x2+x3 2 -x1+x2+2x3=5 x1 0,x2 0,x3 正负不限5/25/202434二、线性规划解的概念二、线性规划解的概念 设线性规划为 maxmax z z=CX CX AX AX=b b X X 0 0 A A为为m m n n矩阵矩阵,n,n m,Rankm,Rank A A=m(Am(A为行满秩矩阵）为行满秩矩阵）1 1、可行解：满足条件、可行解：满足条件、的的X X；2 2、最、最优解：解：满足足条件条件的可行解；的可行解；3 3、基：取、基：取B B为A A中的中的m m m m子矩子矩阵，RankRank B B=m m，则称称B B为线性性规划划问题的一个基。的一个基。取取B B=(p(p1 1,p,p2 2,p,pm m)p pj j=(a(a1j1j,a,a2j2j,a,amjmj)T T 则称则称x x1 1,x,x2 2,x,xm m为基变量，其它为非基变量。为基变量，其它为非基变量。5/25/2024354 4、基解：、基解：设设B B是线性规划是线性规划LPLP的一个基，在的一个基，在AX=bAX=b中，令非基变中，令非基变量取零时由量取零时由AX=bAX=b求出的解称为求出的解称为LPLP的对应于基的对应于基B B的基本解的基本解 (基解基解)。5/25/2024365 5、基可行解、基可行解 满足式要求的基解。6 6、可行基、可行基 基可行解对应的B为可行基。可行解可行解基可行解基可行解非可行解非可行解基解基解5/25/202437三、单纯形法的基本思路 从可行域的一个顶点到另一个顶点迭代求最优解。5/25/202438 四、四、单纯形法求解步骤单纯形法求解步骤 1 1、初始基可行解的确定、初始基可行解的确定 1 1）观察法）观察法2 2）人工变量法）人工变量法5/25/202439 2 2、最优性的检验与解的判别、最优性的检验与解的判别5/25/202440则5/25/202441 解的判别：1)最优解；（教材P24）2)无界解（或称无最优解）；3)无穷多最优解。5/25/202442 3 3、基变换、基变换5/25/202443 4 4、旋转运算、旋转运算 a1k 0 al-1k 0 pk=（alk）（1）al+1k 0 amk 0 得到基可行解，重复 2）4），求出最优解。5/25/202444五、五、单纯形表单纯形表 建立单纯形表cBxBbc1cncn+1cn+mx1xnxn+1xn+mcn+1xn+1b1a11a1n101cn+mxn+mbmam1amn01m 1 n 005/25/202445 用单纯形法求解 （1）max z=x1+3x2 x1+2x2 8 4x1 16 4x2 12 x1,x2 05/25/202446 （2）5/25/202447 （3）5/25/202448 （4 4）maxmax z z=2x x1 1-x x2 2+x x3 3 3x x1 1+x x2 2 +x x3 3 6060 x x1 1-x x2 2+2x x3 3 1010 x x1 1+x x2 2-x x3 3 2020 x x1 1,x,x2 2,x,x3 3 0 05/25/2024491.4 单纯形法的进一步讨论例 求解如下线性规划问题 Min f(x)=10 x1+8x2+7x3 s.t.2x1+x2 6 x1+x2+x3 4 x1 0,x2 0,x3 0 5/25/2024501、用大M法求解 （M为很大的正数）法则：对于max问题，人工变量在目标函数中的价值系数为-M；5/25/2024511）Max f(x)=x1+2x2+3x3 x4 s.t.x1+2x2+3x3 =15 2x1+x2+5x3 =20 x1+2x2+x3+x4=10 x1 0,x2 0,x3 0,x4 0 5/25/2024522）求解如下线性规划问题 Min f(x)=10 x1+8x2+7x3 s.t.2x1+x2 6 x1+x2+x3 4 x1 0,x2 0,x3 05/25/2024532、两阶段法 由于大M不是一个确定的数，所以大M法适宜于手工计算，而不适合求解。为此，引入两阶段法。第一阶段：给线性规划加入人工变量，并构造辅助规划。5/25/202454 以人工变量为初始基变量，列表计算。若本阶段无最优解，表示原线性规划无解，停止计算；若有最优解，则转第二阶段。第二阶段：在第一阶段最优表中，去掉人工变量，换上原问题目标函数，作为本阶段初始表，以此用单纯形法进行迭代运算，求出结果。5/25/2024551）用两阶段法求解 min z=x1+5x2 2x1+3x2 6 2x1+x2 1 x1,x2 05/25/2024562）Max f(x)=5x1+3x2+6x3 s.t.x1+2x2+x3 18 2x1+x2+3x3 16 x1+x2+x3=10 x1 0,x2 0,x3无约束5/25/2024571.5 两个需要说明的问题5/25/202458 若存在两个以上相同的最大值（最小比值），就会出现退化解。理论上讲，退化解可能使计算出现循环，从而得不到最优解。然而，实际问题中很少出现这种情况。当计算中出现最大值（最小比值）相同的情况时，可按Bland规则来计算。Bland 规则：在相同的最大j中（j0），选下标小的非基变量入基；对相同的最小比值中，选下标小的基变量出基。5/25/202459建模及计算机求解 例:某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是1.5m、1m、0.7m，这些轴需要用同一种圆钢来做，圆钢长度为4m。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？5/25/202460 方案规格1 2 3 4 5 6 7 8 9 10需求量Y1(1.5m)Y2(1m)Y3(0.7m)2 2 1 1 1 0 0 0 0 0 1 0 2 1 0 4 3 2 1 00 1 0 2 3 0 1 2 4 5100010001000余料0 0.3 0.5 0.1 0.4 0 0.3 0.6 0.2 0.55/25/202461 设方案j(j=1,2,10)需用的圆钢为根，则可建立如下求解模型：5/25/202462 例一家中型的百货商场，它对售货员的需求经过统例一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作货人员每周工作5 5天，休息两天，并要求休息的两天天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？工作需要，又使配备的售货人员的人数最少？5/25/202463 解：设 xi(i=1,2,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。目标函数 Min x1+x2+x3+x4+x5+x6+x7 约束条件：s.t.x1+x2+x3+x4+x5 28 x2+x3+x4+x5+x6 15 x3+x4+x5+x6+x7 24 x4+x5+x6+x7+x1 25 x5+x6+x7+x1+x2 19 x6+x7+x1+x2+x3 31 x7+x1+x2+x3+x4 28 x1,x2,x3,x4,x5,x6,x7 05/25/202464思考：分别用图解法和单纯形法求解下列线性规划,并指出单纯形法迭代的每一步相当于图形上的哪一个顶点？5/25/2024655/25/202466