管理运筹学讲义第1章线性规划

石家庄经济学院管理科学与工程学院1第1章线性规划Subtitle学习要点线性规划模型的结构及建模步骤线性规划的图解法及解的可能性线性规划的标准型及其转化方法正确理解可行解、可行域、最优解了解基矩阵、基变量、非基变量、基可行解线性规划的单纯形法原理和解的判定石家庄经济学院管理科学与工程学院2一、线性规划的三个要素第一节线性规划的一般模型•决策变量决策问题待定的量值取值要求非负•约束条件任何管理决策问题都是限定在一定条件下来进行的把各种限制条件表示为一组等式或不等式称为约束条件约束条件是决策方案可行的保障约束条件是决策变量的线性函数•目标函数衡量决策优劣的准则，如时间最短、利润最大、成本最低目标函数是决策变量的线性函数有的目标要求实现极大，有的则要求极小石家庄经济学院管理科学与工程学院3二、线性规划模型举例第一节线性规划的一般模型1.生产计划问题例.某厂生产甲乙两种产品，生产工艺路线为：各自的零部件分别在设备A、B上加工，最后都需在设备C上装配。经测算得到相关数据如表所示。应如何制定生产计划，使总利润为最大。据市场分析，单位甲乙产品的销售价格分别为73和75元，试确定获利最大的产品生产计划。产品设备工时消耗甲乙工时成本元/h生产能力hABC200234201510161032石家庄经济学院管理科学与工程学院4第一节线性规划的一般模型(1)决策变量：设x1为甲产品的产量，x2为乙产品的产量。(2)约束条件：生产受设备能力制约，能力需求不能突破有效供给量。设备A的约束条件表达为2x1≤16同理，设备B的加工能力约束条件表达为2x2≤10设备C的装配能力也有限，其约束条件为3x1+4x2≤32(3)目标函数：目标是企业利润最大化maxZ=3x1+5x2(4)非负约束：甲乙产品的产量为非负x1≥0，x2≥012121212max35216210s.t.3432,0Zxxxxxxxx综上的LP模型：石家庄经济学院管理科学与工程学院5第一节线性规划的一般模型2.物资运输问题例：某产品有3个供货源A1、A2、A3，有4个经销商（需求市场）B1、B2、B3、B4。已知各厂的产量、各经销商的销售量及从Ai到Bj的单位运费为Cij。为发挥集团优势，公司要统一筹划运销问题，求运费最小的调运方案。销地产地B1B2B3B4产量A1632550A2758420A3329730销量20301040石家庄经济学院管理科学与工程学院6第一节线性规划的一般模型(1)决策变量：设从Ai到Bj的运输量为xij，(2)目标函数：运费最小的目标函数为minZ=6x11+3x12+2x13+5x14+7x21+5x22+8x23+4x24+3x31+2x32+9x33+7x34(3)约束条件：产量之和等于销量之和,故要满足：供应平衡条件x11+x12+x13+x14=50x21+x22+x23+x24=20x31+x32+x33+x34=30销售平衡条件x11+x21+x31=20x12+x22+x32=30x13+x23+x33=10x14+x24+x34=40非负性约束xij≥0(i=1,2,3；j=1,2,3,4)石家庄经济学院管理科学与工程学院7第一节线性规划的一般模型3.产品配比问题例：用浓度45%和92%的硫酸配置100吨浓度80%的硫酸。决策变量：取45%和92%的硫酸分别为x1和x2吨约束条件：求解二元一次方程组得解1008.092.045.01002121xxxx非负约束：x1≥0，x2≥0石家庄经济学院管理科学与工程学院8第一节线性规划的一般模型若用5种不同浓度的硫酸(30%,45%,73%,85%,92%)配置100吨浓度80%的硫酸，5种硫酸价格分别为400、700、1400、1900、2500元/t，取这5种硫酸分别为x1、x2、x3、x4、x5，有有多少种配比方案？何为最好？123451234512345min400700140019002500100s.t.0.30.450.730.850.920.81000,1,2,...5jZxxxxxxxxxxxxxxxxj石家庄经济学院管理科学与工程学院9三、线性规划的一般数学模型第一节线性规划的一般模型•用一组非负决策变量表示的一个决策问题；•存在一组等式或不等式的线性约束条件；•有一个希望达到的目标，可表示成决策变量的极值线性函数。•具备以上三个特点的数学模型称为线性规划（LinearProgramming，简记为LP），它的一般形式为：11221111221121122222112212max(min)Z(,)(,)s.t.(,),,0nnnnnnmmmnnmncxcxcxaxaxaxbaxaxaxbaxaxaxbxxx石家庄经济学院管理科学与工程学院10三、线性规划的一般数学模型第一节线性规划的一般模型在线性规划模型中，z为目标函数；xj，j=1,2,…,n为决策变量；cj，j=1,2,…,n为价值系数;bi，i=1,2,…,m为资源常数；aij，i=1,2,…,m;j=1,2,…,n为工艺系数或技术系数。这里，cj，bi，aij均为常数。石家庄经济学院管理科学与工程学院11四、线性规划的图解方法第一节线性规划的一般模型1.线性规划的可行域可行域：满足所有约束条件的解的集合，即所有约束条件共同围城的区域。maxZ=3x1+5x22x1≤162x2≤103x1+4x2≤32x1≥0,x2≥0S.t.2x1=162x2=103x1+4x2=32x1x248103590ABCD石家庄经济学院管理科学与工程学院122x1=162x2=10x1x248103583x1+4x2=320ABCD四、线性规划的图解方法第一节线性规划的一般模型2.线性规划的最优解目标函数Z=3x1+5x2代表以Z为参数的一族平行线。最优解点C(4,5)，MaxZ=37Z=30Z=37Z=15石家庄经济学院管理科学与工程学院13五、线性规划解的可能性第一节线性规划的一般模型1.唯一最优解：只有一个最优点2.多重最优解：无穷多个最优解12121212max34216210s.t.3432,0Zxxxxxxxx2x1=162x2=103x1+4x2=32x1x248102580ABCDZ=24Z=32Z=12石家庄经济学院管理科学与工程学院14五、线性规划解的可能性第一节线性规划的一般模型3.无界解：可行域无界，目标函数值无限增大或减小12112max35216s.t.,0Zxxxxx石家庄经济学院管理科学与工程学院15五、线性规划解的可能性第一节线性规划的一般模型4.没有可行解：线性规划问题的可行域是空集12121212max355s.t.3424,0Zxxxxxxxxx1x2O24682468石家庄经济学院管理科学与工程学院16五、线性规划解的可能性第一节线性规划的一般模型•线性规划问题的可行域可记为：S={xAx=b,x0}如果S为一空集，线性规划不可行或无可行解。如果S不为空集，该线性规划一定有可行解，但不一定有有界最优解；若S为一非空有界集合，则线性规划一定存在最优解；石家庄经济学院管理科学与工程学院17一、线性规划的标准型式第二节线性规划的单纯形法标准型的特征w目标函数最大化w约束条件为等式w右端项为非负值w决策变量非负值石家庄经济学院管理科学与工程学院18一、线性规划的标准型式第二节线性规划的单纯形法1.标准型表达方式1）代数式njxmibxaxcZjinjjijnjjj,,2,10,,2,1s.t.max112）向量式1maxs.t.0(1,2,,)njjjjZxxjnCXpb3）矩阵式max0ZCXAX=bXA：技术系数矩阵，简称系数矩阵；b：可用的资源量，称资源向量；C：决策变量对目标的贡献，称价值向量；X：决策向量。石家庄经济学院管理科学与工程学院19一、线性规划的标准型式第二节线性规划的单纯形法1.标准型表达方式nxxxX2112TnccCcmbbbb21,,mnmmnnaaaaaaaaaA212222111211矩阵A也可表示为：A=(p1，p2，…，pn)，其中pj=(a1j，a2j，…，amj)T石家庄经济学院管理科学与工程学院20一、线性规划的标准型式第二节线性规划的单纯形法2.标准型转换方法1）对于极小化原问题minZ=CX，则令Z'=-Z，转为求maxZ'=-CX2）若某个bi0，则以－1乘该约束两端，使之满足非负性的要求。3）对于≤型约束，则在左端加上一个非负松弛变量，使其为等式。4）对于≥型约束，则在左端减去一个非负剩余变量，使其为等式。5）若某决策变量xk无非负约束，令xk=x'k-xk，(x'k≥0,xk≥0)。1234512312412512345max3500020160210..3432,,,,0Zxxxxxxxxxxxstxxxxxxxx石家庄经济学院管理科学与工程学院21非标准型转化举例minZ=x1+2x2-3x3x1+x2+x3≤9-x1-2x2+x3≥23x1+x2-3x3=5x1≤0，x2≥0，x3无约束标准型为maxZ'=x1'-2x2＋3(x3'-x3)-x1'+x2+x3'-x3＋x4=9x1'-2x2+x3'-x3-x5=2-3x1'+x2-3(x3'-x3)=5x1'x2x3'x3x4x5≥0令x1=-x1'，x3=x3'-x3Z=-Z'。石家庄经济学院管理科学与工程学院22二、线性规划之解的概念第二节线性规划的单纯形法1.线性规划的基与基本可行解2.线性规划的基本定理3.单纯形法解题思路石家庄经济学院管理科学与工程学院231.线性规划的基与基本可行解•基的定义：给定线性规划问题LP：A是mn满秩矩阵,nm，如果B是其中任一个mm满秩子矩阵，则称B是LP的一个基。第二节线性规划的单纯形法石家庄经济学院管理科学与工程学院24•基变量与非基变量假定B由A中前m个列向量构成，约束矩阵可划分为：A=(B,N)与基B对应的变量称为基变量，用xB表示；与非基N对应的变量称为非基变量，用xN表示。第二节线性规划的单纯形法石家庄经济学院管理科学与工程学院25•基本解（基解）如果令xN=0，则有：Ax=(B,N)(xB,xN)=BxB+NxN=BxBAx=b等价于BxB=b，由于B满秩，BxB=b有唯一解：xB=B-1b则x=(xB,xN)=(B1b,0)是线性规划P的基本解。最多为Cmn个石家庄经济学院管理科学与工程学院26•基本可行解与可行基满足非负条件的基本解为基本可行解，即XB=B-1b≥0。该解对应的基为可行基。可行解基本可行解基本解第二节线性规划的单纯形法石家庄经济学院管理科学与工程学院27例考虑线性规划模型Maxz=1500x1+2500x2s.t.3x1+2x2+x3=652x1+x2+x4=403x2+x5=75x1,x2,x3,x4,x5≥0注意，线性规划的基本解、基本可行解和可行基只与线性规划问题标准形式的约束条件有关。石家庄经济学院管理科学与工程学院2832100A=[P1,P2,P3,P4,P5]=2101003001A矩阵包含以下10个3×3的子矩阵：B1=[p1，p2，p3]B2=[p1，p2，p4]B3=[p1，p2，p5]B4=[p1，p3，p4]B5=[p1，p3，p5]B6=[p1，p4，p5]B7=[p2，p3，p4]B8=[p2，p3，p5]B9=[p2，p4，p5]B10=[p3，p4，p5]石家庄经济学院管理科