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