《第一讲规划模型.doc》由会员分享，可在线阅读，更多相关《第一讲规划模型.doc（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、第一讲 规划模型本讲介绍的规划模型是一类有着广泛应用的确定性的系统优化模型。这类规划问题，模型规范，建模直接，激发想象；模型求解方法典型，实用面宽广。掌握这类规划问题的数学建模、是建模者必须具备的基本建模素养。规划模型的应用极其广泛，其作用已为越来越多的人所重视。随着计算机的逐渐普及，它越来越急速地渗透于工农业生产、商业活动、军事行为、核科学研究的各个方面，为社会节省的财富、创造的价值无法估量。在数模竞赛过程中，规划模型是最常见的一类数学模型。从历年全国大学生数模竞赛试题的解题方法统计结果来看，规划模型共出现了近20次，占到了近50%，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求
2、解。下面首先讨论静态系统的优化问题，介绍线性规划、整数规划、目标规划和非线性规划；然后讨论动态系统的多阶段优化问题。线性规划问题及其数学模型线性规划模型线性规划是运筹学的重要分支之一。一般认为，运筹学的主要分支有规划论(包括线性规划、非线性规划、动态规划等)、排队论、对策论(亦称博奕论)与决策分析、图论、存贮论、模型论等分支线性规划只是运筹学中研究较早，理论比较完整、应用最广的一个分支。 1线性规划问题 在生产管理和经营活动中，经常提出一类问题，即如何合理地利用有限的人力、物力等资源、以便得到最好的经济效益。先来看两个实例。 问题1 拟定生产计划问题问题提出 某工厂生产甲、乙两种产品这两种产品
3、都需要在A，B，C三种不同设备上加工，每吨甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润值以及这三种加工设备在计划期内能提供的有限台时数均列于下表中如何安排生产计划，即甲、乙两种产品各生产多少吨，可使该厂所获利润最大?设备每吨产品的加工台时有限台时数甲乙A3436B5440C9876利润（千元/吨）3230求最大利润 模型建立 设计划期内甲、乙两种产品的产量分别为x1吨、x2吨(x1，x2称为决策变量)，该厂的目标是在不超过二种设备总有限台时数的条件下，确定产量x1及x2，以获得最大利润，用Z表示利润则有目标函数： Max Z = 32*x1 + 30*x2由于设备A，B，C在
4、计划期内的有效台时数分别为3640，76，可以得出限制产量的条件，即约束条件；3*x1+4*x2=36 (设备A对产量的限制)5*x1+4*x2=40 (设备B对产量的限制)，9*x1+8*x2=76 (设备C对产量的限制)，x1，x20 (产量不能为负值) 问题2运输问题问题提出 两个煤厂A1和A2每月进煤数量分别为60t和100t，联合供应三个居民区(Bl，B2，B3)。三个居民区每月对煤的需求量依次为50t、70t、40t，煤厂Al离居民区BI，B2，B3的距离分别为10 km、5km、6km，煤厂A2离居区民区BI，B2，B3的距离分别为4km，8km,12km问如何分配供煤量使得运输
5、量(tkm)达到最小?模型准备：将上述条件用表格形式表示有B1B2B3供给A1105660A24812100需求507040 模型建立 分配供煤量优劣的指标为运输量，设为Z，用xij表示Ai(I=1,2)煤厂提供给Bj(j1，2，3)居民区的煤量，则该问题的数学模型为 目标函数； minZlOx115x126x134x218x2212x23 约束条件：2线性规划问题的特点和数学模型 从以上两例可以看出，它们都属于一类优化问题它们的共同持点是： (1)每一个问题都用一组决策变量(x1，x2，xn)表示某一方案：这组决策变量的值就代表一个具体的方案一般这些变量的取值是非负的。 (2)存在一定的约束
6、条件，这些约束条件可以用一组线性等式或线性不等式来表示 (3)都有一个要求达到的目标，它可以用决策变量的线性函数来表示，这个函数称为目标函数按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划问题的数学模型，其一般形式为目标函数：约束条件（或s.t.）：约束条件常用英文缩写s.t.表示，而约束条件的最后一式又称为变量的非负性。线性规划主要应用目标函数求最值的情况，在以下各方面有广泛的应用：(1)在某一企业内部，如何配合产品的销售时间，使各部门的原料、产品的存储，分配的数量等最为合理；(2)在某企业生产的产品数量(或产值)固定时，如何在现有设备、人力、原料等条件限
7、制下，合理组织生产，使经济效益最高；(3)在某一地区的交通网(公路网或铁路网)中，如何合理地组织运输，使总运费最小；(4)当市场上产品(或原料)价格变动时，对于这些变化，企业如何做出最优决策；(5)合理下料问题：利用某种类型的原料下料时，如何达到既满足需求，又使废料最少；(6)配料问题生产某类由各种原料配制的产品(如混合饲料等)时，如何满足规定的质量标准，又使产品的成本最低；(7)库存问题，在仓库的容量及其它限制条件下，确定库存物资的品种、数量、期限，使得库存放益最高；(8)在投入产出模型中，引进某一目标函数，制定最优的企业(或地区)经济计划。二、线性规划问题的解法图解法只适用于两个变量的简单
8、线性规划问题。这种解法比较简单，也有助于几何直观地理解线性规划问题。这里不做介绍。软件解法：规划模型的求解常用软件求解，主要有Excel,Lingo,Matlab等，这里用Lingo求解。问题一：Max Z = 32x1 + 30x23x1+4x236 (设备A对产量的限制)5x1+4x240 (设备B对产量的限制)，9x1+8x276 (设备C对产量的限制)，x1，x20 (产量不能为负值)在Lingo中输入模型，注意书写格式：1， 目标函数的变量Z不写；程序不分大小写；2， 每行以分号结束；3， 加、减、乘、除等运算符号一个都不能少；4， “”号等同于“”号；5， 所有函数均要加以前缀“”
9、符号；6， 注释语句用感叹号“!”开头；7， 非负约束是软件的缺省设置，可以不输入。请看演示：程序：Max = 32*x1 + 30*x2;3*x1+4*x236;5*x1+4*x240;9*x1+8*x276;结果为： Global optimal solution found. Objective value: 282.6667 Infeasibilities: 0. Total solver iterations: 3 Variable Value Reduced Cost X1 1. 0. X2 8. 0. Row Slack or Surplus Dual Price 1 282.6
10、667 1. 2 0. 1. 3 1. 0. 4 0. 3.即经过3步迭代，得到全局最优解为X1=1.333，X2=8.0。最大利润为282.6667，设备A，C的资源(加工台时数)全部用完，设备B尚余1.33333台时数，若需要加班生产，即增加设备的台时数，设备A每增加1小时，可增加利润1.16667千元；设备B因有剩余1.33333，故增加设备B的台时数对利润没有影响；设备C每增加1小时，可增加利润3.千元。对问题二，有Lingo程序：min=10*x11+5*x12+6*x13+4*x21+8*x22+12*x23;x11+x12+x13=60; x21+x22+x23=100; x11
11、+x21=50; x12+x22=70; x13+x23=40;求解结果为： Global optimal solution found. Objective value: 940.0000 Infeasibilities: 0. Total solver iterations: 1 Variable Value Reduced Cost X11 0. 9. X12 20.00000 0. X13 40.00000 0. X21 50.00000 0. X22 50.00000 0. X23 0. 3. Row Slack or Surplus Dual Price 1 940.0000 -1
12、. 2 0. 0. 3 0. -3. 4 0. -1. 5 0. -5. 6 0. -6.结果解释：分配供煤量为(0，20，40；50，50，0)，最小运输量为940，三、线性规划问题解的理论1线性规划模型的标准型实际问题的线性规划模型是多种多样的，在众多的样式中可规定一种样式为标准型，以便于研究和求解在线性规划模型的标准型中，有n个决策变量，m个约束条件，约束条件为等式约束，且决策变量为非负求目标函数的最小值标准型表达式为：s.t.在标准型中，规定各约束条件的右端项bi0，否则等式两端乘以“-1”，其简写形式为；其中，A称为约束条件的系数矩阵，c为价值向量，b为资源向量，X为决策向量。关于线
13、性规划模型的求解，通常用单纯形法。这里不讲，只讲如何用Lingo11.0规划软件来求解。（Lingo软件的算法就是单纯形法）先建立如下例题的线性规划模型。例2某工厂生产甲、乙、丙三种铝合金产品，生产每单位产品甲需用铝和铁分别是3公斤和2公斤，生产每单位产品乙需用铝和铁分别是1公斤和3公斤，生产每单位产品丙需用铝和铁分别是1公斤和2公斤，已知生产每单位产品分别能获得5元、4元和3元，而工厂每天能得到的原料供应为铝840公斤、铁700公斤。试问如何安排三种铝合金产品的生产，可使工厂能获得最大利润？解：将所有关系用表格形式表出，便于建立模型。铝铁获利甲325乙134丙123供应量840700建立模型
14、如下：设决策变量：x1，x2，x3分别为甲、乙、丙的产量，则Max = 5*x1+4*x2+3*x3;S.t. 3*x1+x2+x3=840; 2*x1+3*x2+2*x3Options-General Solver-Dual Computations:选中prices & Rangens，点OK。再作灵敏度分析：LINGO-Range，得如下结果：Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increa
15、se Decrease X1 5. 7. 0.0 X2 4. 3. 0.0 X3 3. 0.0 INFINITY Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 840.0000 210.0000 606.6667 3 700.0000 1820.000 140.0000当前价值系数为5，4，3，当x1系数在5-0,5+7范围内变化时，最优解不变，但最优值（即最优获利）会随之改变。当x2系数在4-0,4+3.5范围内变化时，最优解不变。当前资源量为840，700，当铝供应量在840-60
16、6.6667,840+210范围内变化时，最优基不变（即原来不生产的x3仍不生产），但最优解会改变，最优值也会改变。同理，铁供应量在700-140，700+1820内变化时，最优基不变。例3某药厂生产A、B、C三种药物，可供选择的原料有甲、乙、丙、丁。四种原料的成本分别是每公斤5、6、4、8元，每公斤不同原料所能提取的各种药物的数量如下表ABC成本甲1525乙1416丙1514丁1628药厂要求每天生产A恰好100单位，B至少530单位，C不超过160单位，要求选配各种原料的数量既满足生产需要，又使总成本最小。试建立此问题的数学模型。请自己完成。例4某厂制造三种仪器，甲种仪器需要17小时加工装
17、配，8小时校验，售价300元；乙种仪器需要10小时加工装配，4小时校验，售价200元；丙种仪器需要2小时加工装配， 2小时校验，售价100元可供利用的加工装配时间为1000小时，校验时间为500小时，三种仪器所用的元件和材料基本一样。又据市场预测表明，对甲种仪器的要求不超过50台，乙种仪器不超过80台，丙种仪器不超过150台（整数规划）工厂要决定能获得最大总产值的最优生产计划试写出这个问题的数学模型解：建立表格形式：装配校验售价要求甲仪器17830050乙仪器10420080丙仪器22100150可供资源1000500建立模型如下：设生产仪器分别为x1,x2,x3Max = 300*x1+20
18、0*x2+100*x3;17*x1+10*x2+2*x3=1000;8*x1+4*x2+2*x3=500;X150;x280;x3变为）X5 + X6 + X7 + X8时，目标函数值-1当REDUCE COST 或DUAL PRICE 的值为。表示当微小扰动不影响目标函数。有时，通过分析DUAL PRICE，也可对产生不可行问题的原因有所了解。灵敏度分析：如果做敏感性分析，则系统报告当目标函数的费用系数和约束右端项在什么范围变化（此时假定其他系数保持不变）时，最优解或最优基保持不变。报告中INFINITY表示正无穷，Ranges in which the basis is unchanged
19、: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 1. 0.0 0.0 X2 1. 0.0 0.0 X3 1. INFINITY 0.0 X4 1. 15.13186 0.0 X5 0.0 0.0 0.0 X6 0.0 0.0 0.0 X7 0.0 0.0 INFINITY X8 0.0 0.0 1. Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decre
20、ase 2 .0 .3 .1 3 .0 41014.33 15247.02 4 .0 30601.41 82317.48 5 .0 27374.90 10176.58 6 .0 2350.135 6321.840 7 0.0 43454.00 .8 8 0.0 43454.00 INFINITY 9 0.0 . INFINITY 10 0.0 . .1如上例：目标函数中4的变量系数为，当它在1-0，1+15.13186= 1，16.13186 变化时，最优解保持不变。即价值系数的单独变化，能否引起最优解的变化。第一个约束右端项为，当它在-.1,+.3=15247.,.0625 范围变化时，最优
21、基保持不变 。即资源限制的单独变化能否引起最优基的变化。注意事项：） 目标函数用“min = ”或“max = ”开头，约束条件直接输入。） 变量名不能超过个字符。） 变量与其系数间的运算符号一个都不能少（如乘号“”等）。） = 与 = 与 等价，即小于等于与小于等价，大于等于与大于等价。） 一般LINGO中能接受括号“（）”，例：400*(X1+X2)。例2（整数规则）有四个工人，要分别指派他们完成四项不同的工作，每个人做各项工作所消耗的时间如表。问应该如何指派，才能使总的消耗时间为最小？工作所耗时间工人ABCD甲15182124乙19232218丙26171619丁19212317这是一道
22、典型的整数规则问题。我们记派第i人去做第j项工作记为Xij注意到每人只能做一项工作。每项工作一人做。我们得到目标函数为约束条件：min = 15*x11+19*x21+26*x31+19*x41+18*x12+23*x22+17*x32+21*x42+24*x13+22*x23+16*x33+23*x43+24*x14+18*x24+19*x34+17*x44;x11+x12+x13+x14=1;x21+x22+x23+x24=1;x31+x32+x33+x34=1;x41+x42+x43+x44=1;x11+x21+x31+x41=1;x12+x22+x32+x42=1;x13+x23+x3
23、3+x43=1;x14+x24+x34+x44=1;bin(x11); bin(x12); bin(x13); bin(x14); bin(x21); bin(x22); bin(x23); bin(x24); bin(x31); bin(x32); bin(x33); bin(x34); bin(x41); bin(x42); bin(x43); bin(x44);运行后我们可得到 Global optimal solution found. Objective value: 70.00000 Objective bound: 70.00000 Infeasibilities: 0. Extended solver steps: