运筹学--第2节(线性规划-标准型)

第一章线性规划及单纯形法讲授：施宏远日期：2015-03目录线性规划介绍线性规划数学模型线性规划的图解法线性规划的单纯形法一、线性规划的重要地位是运筹学中应用最广泛的方法之一；是运筹学最基本的方法之一，整数规划，目标规划和多目标规划，网络规划都是以线性规划为基础的；是解决稀缺资源最优分配的有效方法，使付出的费用最小或获得的收益最大。线性规划介绍如果规划问题的数学模型中:决策变量的取值是连续的;目标函数是决策变量的线性函数;约束条件是含决策变量的线性等式或不等式;则该类规划问题的数学模型称为线性规划的数学模型。二、定义线性规划介绍三、研究对象有一定的人力、财力、资源条件下，如何合理安排使用，效益最高某项任务确定后，如何安排人、财、物，使之最省线性规划介绍四、线性规划解决的管理问题：1.合理利用线材问题；2.配料问题；3.投资问题；4.产品生产计划；5.劳动力安排；6.运输问题。线性规划介绍1.要求达到某些数量上的最大化或最小化；2.在一定的约束条件下追求其目标。五、线性规划问题的共同点：线性规划介绍线性规划的数学模型一、问题的提出二、线性规划数学模型的一般形式三、线性规划数学模型的标准形式例1美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表I—l所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。分析和表述问题1、确定决策目标，明确主要决策什么目标：利润最大！例1美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表I—l所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。分析和表述问题假设：利润——Z家电I的数量——x1家电II的数量——x2例1美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表I—l所示。问该公司每天应制造I、II两种家电各多少件，使获取的利润为最大。分析和表述问题目标函数：maxZ=2x1＋x2例1美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表I—l所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。分析和表述问题2、要辨认哪些是决策的关键影响因素，在选取这些关键因素时存在哪些资源和环境的限制设备，调试工序时间受限制例1美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如表I—l所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。分析和表述问题3、列出表述问题的各种基本要素，并确定各要素之间的关系。5x2≤156x1+2x2≤24x1+x2≤5x1≥0,x2≥0用数学语言描述目标函数约束条件解：用变量x1和x2分别表示美佳公司制造家电I和II的数量。例2、生产计划问题AB备用资源煤1230劳动日3260仓库0224利润4050求：利润最大的生产计划。x1+2x2303x1+2x2602x224x1，x20maxZ=40x1+50x2解:设产品A,B产量分别为变量x1，x2例4求：最低成本的原料混合方案原料ABＣ每单位成本14102261253171642538每单位添加剂中维生12148素最低含量解：设每单位添加剂中原料i的用量为xi(i=1,2,3,4)minZ=2x1+5x2+6x3+8x44x1+6x2+x3+2x412x1+x2+7x3+5x4142x2+x3+3x48xi0(i=1,…,4)x1+2x2303x1+2x2602x224x1，x20maxZ=40x1+50x2minZ=2x1+5x2+6x3+8x44x1+6x2+x3+2x412x1+x2+7x3+5x4142x2+x3+3x48xi0(i=1,…,4)线性规划模型特点决策变量：向量(x1…xn)T决策人要考虑和控制的因素。非负。约束条件：线性等式或不等式目标函数：Z=ƒ(x1…xn)线性式，求Z极大或极小21线性规划的一般式max(min)Z=C1x1+C2x2+…+Cnxna11x1+a12x2+…+a1nxn(=,)b1a21x1+a22x2+…+a2nxn(=,)b2………am1x1+am2x2+…+amnxn(=,)bmxj0(j=1,…,n)简写为：njjjXCZ1max(min)),,2,1(0),,2,1(1njxmibxajinjjij23线性规划的一般式max(min)Z=C1x1+C2x2+…+Cnxna11x1+a12x2+…+a1nxn(=,)b1a21x1+a22x2+…+a2nxn(=,)b2………am1x1+am2x2+…+amnxn(=,)bmxj0(j=1,…,n)c1c2…cnx1x2...xn用矩阵形式表示：线性规划的适用情况•要解决的问题的目标可以用数值指标反映•对于要实现的目标有多种方案可选择•有影响决策的若干约束条件线性规划标准形式线性规划的标准形式目标函数：max约束条件：=变量符号：≥00..maxXbAXtsXCzT（一）一般型a11x1+a12x2+…+a1nxn=b1a21x1+a22x2+…+a2nxn=b2…………am1x1+am2x2+…+amnxn=bmxj0(j=1,2,…,n)maxZ=c1x1+c2x2+…+cnxn其中bi0(i=1,2,…,m)线性规划标准型的几种表示法（二）矩阵型maxZ=CXAX=bX0b0P1P2………Pna11a12………a1n其中A=a21a22………a2n…………………am1am2………amnx1X=x2xn…b1b=b2bm…C=(C1C2…Cn)(三)向量型x1AX=(P1P2…Pn)x2=bxn…P1x1+P2x2+…+Pnxn=b01XbxpnjjjCXZmax化标准型(2)、约束条件(4)、变量(1)、目标函数(3)、右端常数（1）目标函数目标函数为求最小值，xoZ-ZnjjjXCZ1minnjjjXCZ1'max令Z'=-Z（2）约束条件x3为松弛变量x4为剩余变量松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。当约束条件为“≤”时，242621xx如2426321xxx＋可化为当约束条件为“≥”时，18121021xx如181210421xxx可化为x1+2x2+x3=303x1+2x2+x4=602x2+x5=24x1,…,x50转化为：maxZ=40x1+50x2+0·x3+0·x4+0·x5x1+2x2303x1+2x2602x224x1，x20例：maxZ=40x1+50x2松弛变量例:4x1+6x2+x3+2x412x1+x2+7x3+5x4142x2+x3+3x48xi0(i=1,…,4)4x1+6x2+x3+2x4-x5=12x1+x2+7x3+5x4-x6=142x2+x3+3x4-x7=8x1,…,x70剩余变量（3）右端常数右端项b＜0时，只需将等式或不等式两端同乘(－1)，则等式右端项必大于零。（4）变量3x1'-3x1+2x28x1'-x1–4x214x1',x1,x20a、x0的情况，3x1+2x28x1–4x214x20令x1=x1'-x1b、x取值无约束的情况。令x'＝-x。令x=x'-xx1'+x211x1'16x1',x20c、x两边有约束的情况。x1+x25-6x110x20-6+6x1+610+6令x1'=x1+60x1'16x1'+x2+x3=11x1'+x4=16x1',x2,x3,x4,,0将minZ=-x1+2x2–3x3x1+x2+x37x1-x2+x32x1，x20，x3无限制化为标准型例：解：①令x3=x4-x5②加松弛变量x6③加剩余变量x7④令Z'=-ZmaxZ'=x1–2x2+3x4–3x5x1+x2+x4-x5+x6=7x1-x2+x4-x5-x7=2x1,x2,x4,…,x70minZ=-x1+2x2–3x3x1+x2+x37x1-x2+x32x1，x20，x3无限制练习补充作业、运输问题从仓库到工厂运送单位原材料的成本，工厂对原材料的需求量，仓库目前库存分别如表所示，求成本最低的运输方案。工厂仓库123库存121350222430334210需求401535设xij为i仓库运到j工厂的原棉数量(i＝1，2，3，j＝1，2，3)minZ=2x11+x12+3x13+2x21+2x22+4x23+3x31+4x32+2x33x11+x12+x1350x21+x22+x2330x31+x32+x3310x11+x21+x31=40x12+x22+x32=15x13+x23+x33=35xij0