《线性规划模型上.ppt》由会员分享，可在线阅读，更多相关《线性规划模型上.ppt（40页珍藏版）》请在三一办公上搜索。
1、第3章 线性规划模型(上),在工程技术、经济管理、科学研究和日常生活等诸多领域中，人们经常遇到这样一类决策问题：在一系列客观或主观限制条件下，寻求所关注的某个或多个指标达到最大(或最小)的决策。例如，生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部件等订购、投产的日程和数量，尽量降低成本使利润最高；运输方案要在满足物资需求和装载条件下安排从各供应点到各需求点的运量和路线，使运输总费用最低。这一类问题的特点就是：在若干可能的方案中寻求某种意义下的最优方案。数学上称为最优化问题，而研究处理这种问题的方法叫最优化的方法。优化模型是一种特殊的数学模型，优化建模方法是一种特殊的数学建模方法。,常
2、见的线性规划问题：运输问题；合理下料问题；生产的组织与计划问题；配料问题；分派问题；布局问题。,优化模型一般有下面三个要素：1决策变量，它通常是该问题要求解的那些未知量；2目标函数，通常是该问题要优化(最大或最小)的那个目标的数学表达式，它是决策变量的函数。3约束条件，由该问题对决策变量的限制条件给出。优化模型从数学上可表示成如下一般形式：,其中“s.t.”表示“subject to”，意思是“受约束于”，如果f(x),h(x),g(x)均为线性函数，则上述模型称为线性规划(Linear Programming，简记为LP)，否则称为非线性规划(NLP),线性规划模型的基本结构,1.决策变量
3、未知数。它是通过模型计算来确定的决策因素。又分为实际变量求解的变量和计算变量，计算变量又分松弛变量（上限）和人工变量（下限）。2.目标函数经济目标的数学表达式。目标函数是求变量的线性函数的极大值和极小值这样一个极值问题。3.约束条件实现经济目标的制约因素。它包括：生产资源的限制（客观约束条件）、生产数量、质量要求的限制（主观约束条件）、特定技术要求和非负限制。,线性规划模型的基本假设,1.线性 目标函数和约束条件2.可分性 活动对资源的可分性3.可加性 活动所耗资源的可加性，资源总需要量为多种活动所需资源数量的总和。4.明确性 目标的明确性5.单一性 期望值的单一性6.独立性 变量是独立的表示
4、各种作业对资源都是互竟关系，没有互助关系7.非负性,3.1 线性规划(目标函数和约束条件都是线性函数)一、几个相关概念 一个线性规划问题有解：指能找出一组,满足约束条件，并称这组xj为问题的可行解。可行域：指全部可行解组成的集合。最优解：指可行域中使目标函数值达到最优的可行解。线性规划问题无解：指不存可行解或最优趋向无限大。,二、求解一般方法：一）图解法：对于只含2个变量的线性规划问题，可通过在平面上作图的方法求解。步骤如下：1在平面上建立直角坐标系；2图示约束条件，找出可行域；3图示目标函数，即为一直线；4将目标函数直线沿着其法线方向向可行解域边界平移，直到与可行解域第一次相切为止，这个切点
5、就为最优点。,二）用Matlab,Lindo/Lingo,Mathematica软件实现 线性规划问题在Mathematica4.0软件包求解有两种方法：I直接输入表达式求解，命令格式如下：目标函数求最小时，使用下列命令 ConstrainedMin目标函数，限制条件，变量表 目标函数求最大时，使用下列命令ConstrainedMax目标函数，限制条件，变量表 注意：在输入限制条件时，1）等号要写两个；（2）所有变量都要转化为非负的形式，Mathematica4软件系统自动在第一象限求解，所以x11 0之类的约束条件可以不输入。,例如，求解下列问题,第一步，通过变量替换，将所有变量化为非负的形
6、式。令 x1=y11 y12，x2=y21 y22，x3=y31 y32，x4=y41 y42，x5=y51 y52，其中所有变量yij0，代入原问题。,第二步，在Mathematica4.0软件包中编写程序如下：ConstrainedMin7(y21y22)5(y31y32)53(y41y42)6(y51y52),-(y11-y12)+6(y21y22)4(y41y42)3(y51y52)6,y31y32+2(y41-y42)5(y51y52)10,4(y11-y12)5(y31y32)+2(y61y62)=7,y11-y12 2,y11-y12 10,y21y22 7,y31y325,y1
7、1,y12,y21,y22,y31,y32,y41,y42,y51,y52,y61,y62 使用命令运行求解。,II将线性规划问题转化为矩阵形式求解，命令格式如下：LinearProgramming c,A,b 它要求必须首先将线性规划问题转化为以下“大于等于求最小”的形式：,例如，有线性规划问题：max f=3x1+2x2s.t.2x1 x2-2,x1+2 x2 8,x1+x2=5,x1,x2 0首先将其转化为符合程序要求的标准形式：,第一步 转化如下：min(-f)=-3x1 2x2s.t.2x1-x2-2，-x1-2x2-8，x1+x2 5，-x1-x2-5，x1,x2 0,第二步 转化
8、为矩阵形式：,于是，得到目标函数的系数向量为c=(-3,-2)，约束条件的系数矩阵为,约束条件的常数向量为：,最后在Mathematica4中输入以下程序：,c=-3,-2;A=2,-1,-1,-2,1,1,-1,-1;b=-2,-8,5,-5;x=LinearProgramming c,A,b;Print“x=”,x f=-c.x;Print“fmax=”,f 其中“c.x”表示向量的内积。程序运行之后，得到以下结果：x=5,0 fmax=15,32 线性规划模型的实例例1 家具生产的安排 家具公司生产桌子和椅子，用于生产的劳力共计450个工时，木材共有4立方米，每张桌子要使用15个工时，0
9、.2立方木材售价80元。每张椅子使用10个工时，0.05立方木材售价45元。问为达到最大的效益，应如何安排生产？,分析：1）求什么？生产多少桌子？x1 生产多少椅子？x22)优化什么？收益最大 max f=80 x1+45 x23）限制条件？原料总量 0.2 x1+0.05 x2 4 劳力总数 15 x1+10 x2 450 x1 0,x2 0,图解法的步骤：,1.在直角坐标系中画出可行解集：分别画出满足每个约束包括变量非负要求的区域，其交集就是可行解集，或称可行域；,2.绘制目标函数图形：先过原点作一条矢量指向点(c1,c2)，矢量的方向就是目标函数值增加的方向，称为梯度方向，再作一条与矢量
10、垂直的直线，这条直线就是目标函数图形；,3.求最优解：依据目标函数求最大或最小移动目标函数直线，直线与可行域相交的点对应的坐标就是最优解。,一般地，先将目标函数直线放在可行域中：若要求最大值，则将目标函数直线沿着矢量方向移动；若要求最小值，则将目标函数直线沿着矢量的反方向移动。,模型：以产值为目标取得最大收益图示法求解：,例2 有两个农场A和B，上级规定它们每月分别向三个大学食堂送米65吨、110吨，这三个大学食堂每月需米分别为50吨、80吨、45吨。A农场离大学分别为15Km、10Km、11Km，B农场离大学分别为14Km、18Km、25Km。问如何分配这两个农场供米，使总运输量（吨公里）最
11、小？,解：（一）求最优调度方案 设A农场为D1、D2、D3分别送米x1、x2、x3吨；B农场为D1、D2、D3分别送米x4、x5、x6吨；得到模型如下：min f=15x1+10 x2+11x3+14x4+18x5+25x6,用Mathematica4.0软件包求解：（1）表达式输入法（ConstrainedMin命令和ConstrainedMax命令的应用）ConstrainedMin15x1+10 x2+11x3+14x4+18x5+25x6,x1+x2+x3=50,x2+x5=80,x3+x6=45,x1,x2,x3,x4,x5,x6 注意：ConstrainedMin命令和Constr
12、ainedMax命令默认全体变量0。（2）矩阵输入法（LinearProgramming命令的应用）,所求最优解为(x1,x2,x3,x4,x5,x6)=(0,20,45,50,60,0),fmin=2475吨公里。,（二）讨论上级分配方案是否合理 ConstrainedMin15x1+10 x2+11x3+14x4+18x5+25x6,x1+x2+x3=50,x2+x5=80,x3+x6=45,x1,x2,x3,x4,x5,x6,a,b 此时的最优解为：（x1,x2,x3,x4,x5,x6）=(0，80，45，50，0，0),fmin=1995吨公里。a=125，b=50。可见，以最小吨公里
13、为衡量标准，上级原来的规定并不是资源的最优配置，应该改进为：A农场送米125吨，B农场送米50吨。,例3 合同与库存 某化肥厂若从某月开始增产，每吨成本增加10元，若从某月开始减产，每吨成本增加5元。本年度12月份计划生产2000吨，预计下一年1月的库存为1000吨，库存最大容量为5000吨。合同订购各月提货量如下表（单位：千吨）。在保证库存和提货的前提下，制定最佳生产计划，使因产量变化引起的成本增加总额最少。,解：建模假设 1）生产量与提货量基本同步增长；2）生产量由上升到下降，其中只有一次转折，不妨6月份为转折点；3）设第j月的生产量为xj，j=112。,成本总和 S=10(x1-2000
14、)+(x2-x1)+(x3-x2)+(x4-x5)+(x5-x4)+(x6-x5)+5(x6-x7)+(x7-x8)+(x8-x9)+(x9-x10)+(x10-x11)+(x11-x12)=15x6 5x12 20000min S=15x6 5x12 20000 x2 x1 0,x3 x2 0,x4 x3 0,x5 x4 0,x6 x5 0,x6 x7 0,x7 x8 0,x8 x9 0,x9 x10 0,x10 x11 0,x11 x12 0本月售后余量=本月生产量+上月库存量 本月提货量库存限制：0 本月售后余量 5000,第1月 0 x1+1000-20005000,即1000 x1
15、6000；第2月 0 x2+(x1+1000-2000)3000 5000,即 4000 x2+x1 9000；第3月 8000 x3+x2+x1 13000,第4月 14000 x4+x3+x2+x1 19000,第5月 22000 x5+x4+x3+x2+x1 27000,第6月 32000 x6+x5+x4+x3+x2+x137000,第7月 42000 x7+x6+x5+x4+x3+x2+x147000,第8月 48000 x8+x7+x6+x5+x4+x3+x2+x1 53000,第9月 52000 x9+x8+x7+x6+x5+x4+x3+x2+x1 57000,第10月 5500
16、0 x10+x9+x8+x7+x6+x5+x4+x3+x2+x1 60000,第11月 57000 x11+x10+x9+x8+x7+x6+x5+x4+x3+x2+x1 62000,第12月 59000 x12+x11+x10+x9+x8+x7+x6+x5+x4+x3+x2+x1 64000,所求最优解为Smin=82666.7 元,x1=4333.33吨，x2=4333.33吨，x3=4333.33吨,x4=6000吨,x5=7666.67吨，x6=7666.67吨，x7=7666.67吨,x8=6000吨,x9=4000吨，x10=4000吨，x11=4000吨，x12=4000吨。,例4
17、 某企业拥有一种股票，若现在卖出，价值100万元。另外，已知价值 x万元的股票n年后卖出，可得 万元。银行年利率取0.017，按复利计算，寻找最佳卖出时机，使得20年后收入最大。,解：设现值100万元的股票中有xj万元股票在第j年年头卖出，则,例5 假定一天中的第j个小时（j=1，2，24）需要公共汽车的最小数量是bj，每辆公共汽车开6小时，如果在时间j的公共汽车数超过最低需要数bj，那麽每辆公共汽车1小时要发生额外成本cj。问：如何安排车辆使额外总成本最少？,解：设第j个小时安排xj 辆汽车开始上路服务，则,Subject to:x1+x20+x21+x22+x23+x24b1,x2+x21
18、+x22+x23+x24+x1b2x3+x22+x23+x24+x1+x2b3,x4+x23+x24+x1+x2+x3b4x5+x24+x1+x2+x3+x4b5,x6+x1+x2+x3+x4+x5b6x7+x2+x3+x4+x5+x6b7,x8+x3+x4+x5+x6+x7b8x9+x4+x5+x6+x7+x8b9,x10+x5+x6+x7+x8+x9b10 x11+x6+x7+x8+x9+x10b11,x12+x7+x8+x9+x10+x11b12x13+x8+x9+x10+x11+x12b13,x14+x9+x10+x11+x12+x13b14x15+x10+x11+x12+x13+x1
19、4b15,x16+x11+x12+x13+x14+x15b16x17+x12+x13+x14+x15+x16b17,x18+x13+x14+x15+x16+x17b18x19+x14+x15+x16+x17+x18b19,x20+x15+x16+x17+x18+x19b20 x21+x16+x17+x18+x19+x20b21,x22+x17+x18+x19+x20+x21b22x23+x18+x19+x20+x21+x22b23,x24+x19+x20+x21+x22+x23b24xj0,Integer,例6 设婚姻介绍所里有4位男士、5位女士要求服务。婚姻介绍所根据各自的条件，分别为他们得
20、出若他们相识后的预测幸福值如下：,婚姻介绍所应如何介绍他们相识，才能使总的幸福值最大？,设变量xij=1,若介绍Mi与Wj相识；否则xij=0。则有如下(0，1)规划。,用Mathematica4.0软件包求解（输入时不含条件xij=0或1），得不到解。但只要将矩阵改为方阵即可（加零行或者零列）。例如，将上表改为下表，即可求解。,此时，用Mathematica4.0软件包求解(输入时不含条件xij=0或1)，得解：fmax=25,x13=1,x25=1,x34=1,x42=1,x51=1,其他xij=0。即应分别介绍第1位男士与第3位女士，第2位男士与第5位女士，第3位男士与第4位女士，第4位
21、男士与第2位女士相识，第1位女士则不作介绍。,上面的两个例子中有一个共同特点，就是决策变量的取值为0或1，这种问题称0-1整数规划问题。0-1整数规划要求线性规划模型中的决策变量 xij 只能取值为0或1.,0-1整数规划模型,0-1整数规划模型的求解目前并没有非常好的算法，对于变量比较少的情形，我们可以采取简单隐枚举法，该方法是一种基于判断条件（过滤条件）的穷举法.大家有兴趣可查找相关资料。,例7 有 n 个物品，编号为 1,2,n，第 i 件物品,重 ai 千克，价值为 ci 元，现有一个载重量不超过,大，应如何装载这些物品？,a 千克的背包，为了使装入背包的物品总价值最,用变量 xi 表
22、示物品 i 是否装包，i=1,2,n，,并令：,解,可得到背包问题的规划模型为：,例8 有n 项任务，由 n 个人来完成，每个人只能,做一件，第 i 个人完成第 j 项任务要 cij 小时，如,何合理安排时间才能使总用时最小？,引入状态变量 xij，并令：,解,则总用时表达式为：,可得到指派问题的规划模型为：,上面介绍的指派问题称为指派问题的标准形,式，还有许多其它的诸如人数与任务数不等、及,但一般可以通过一些转化，将其变为标准形式.,某人可以完成多个任务，某人不可以完成任务，,某任务必须由某人完成等特殊要求的指派问题.,对于标准形式的指派问题，我们可以利用匈,牙利算法实现求解.它将指派问题中
23、的系数构成,一个矩阵，利用矩阵上简单的行和列变换，结合,解的判定条件，实现求解.,局限性：1.线性规划它是以价格不变和技术不变为前提条件的，不能处理涉及到时间因素的问题。因此，线性规划只能以短期计划为基础。2.在生产活动中，投入产出的关系不完全是线性关系，由于在一定的技术条件下，报酬递减规律起作用，所以要满足线性假定是不可能的。在线性规划解题中，常常把投入产出的非线性关系转化为线性关系来处理，以满足线性的假定性，客观上产生误差。3.线性规划本身只是一组方程式，并不提供经济概念，它不能代替人们对现实经济问题的判断。,技术经济研究中运用线性规划方法的特点及局限性,技术经济研究中运用线性规划方法的特
24、点及局限性,特点：1.可以使研究对象具体化、数量化。可以对所研究的技术经济问题做出明确的结论；2.线性3.允许出现生产要素的剩余量4.有一套完整的运算程序,练习1 合理用料问题。某汽车需要用甲、乙、丙三种规格的轴各一根，这些轴的规格分别是1.5，1，0.7(m)，这些轴需要用同一种圆钢来做，圆钢长度为4 m。现在要制造1000辆汽车，最少要用多少圆钢来生产这些轴？,练习2：某厂生产两种产品，需要三种资源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：,问题：如何安排生产计划，使得获利最多？,练习3：某运输问题，已知资料如下表所示，问如何调运，使产销平衡且总运费最小？,单位运费,产地,销地,单位：百万/吨,
