1-1第一讲规划模型1

第一讲规划模型本讲介绍的规划模型是一类有着广泛应用的确定性的系统优化模型。这类规划问题，模型规范，建模直接，激发想象；模型求解方法典型，实用面宽广。掌握这类规划问题的数学建模、是建模者必须具备的基本建模素养。规划模型的应用极其广泛，其作用已为越来越多的人所重视。随着计算机的逐渐普及，它越来越急速地渗透于工农业生产、商业活动、军事行为、核科学研究的各个方面，为社会节省的财富、创造的价值无法估量。在数模竞赛过程中，规划模型是最常见的一类数学模型。从历年全国大学生数模竞赛试题的解题方法统计结果来看，规划模型共出现了近20次，占到了近50%，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解。下面首先讨论静态系统的优化问题，介绍线性规划、整数规划、目标规划和非线性规划；然后讨论动态系统的多阶段优化问题。线性规划问题及其数学模型线性规划模型线性规划是运筹学的重要分支之一。一般认为，运筹学的主要分支有规划论(包括线性规划、非线性规划、动态规划等)、排队论、对策论(亦称博奕论)与决策分析、图论、存贮论、模型论等分支．线性规划只是运筹学中研究较早，理论比较完整、应用最广的一个分支。1．线性规划问题在生产管理和经营活动中，经常提出一类问题，即如何合理地利用有限的人力、物力等资源、以便得到最好的经济效益。先来看两个实例。问题1拟定生产计划问题问题提出某工厂生产甲、乙两种产品．这两种产品都需要在A，B，C三种不同设备上加工，每吨甲、乙产品在不同设备上加工所需的台时，它们销售后所能获得的利润值以及这三种加工设备在计划期内能提供的有限台时数均列于下表中．如何安排生产计划，即甲、乙两种产品各生产多少吨，可使该厂所获利润最大?设备每吨产品的加工台时有限台时数甲乙A3436B5440C9876利润（千元/吨）3230求最大利润模型建立设计划期内甲、乙两种产品的产量分别为x1吨、x2吨(x1，x2称为决策变量)，该厂的目标是在不超过二种设备总有限台时数的条件下，确定产量x1及x2，以获得最大利润，用Z表示利润．则有目标函数：MaxZ=32*x1+30*x2由于设备A，B，C在计划期内的有效台时数分别为36．40，76，可以得出限制产量的条件，即约束条件；3*x1+4*x2=36(设备A对产量的限制)5*x1+4*x2=40(设备B对产量的限制)，9*x1+8*x2=76(设备C对产量的限制)，x1，x2≥0(产量不能为负值)．问题2运输问题问题提出两个煤厂A1和A2每月进煤数量分别为60t和100t，联合供应三个居民区(Bl，B2，B3)。三个居民区每月对煤的需求量依次为50t、70t、40t，煤厂Al离居民区BI，B2，B3的距离分别为10km、5km、6km，煤厂A2离居区民区BI，B2，B3的距离分别为4km，8km,12km．问如何分配供煤量使得运输量(t·km)达到最小?模型准备：将上述条件用表格形式表示有B1B2B3供给A1105660A24812100需求507040模型建立分配供煤量优劣的指标为运输量，设为Z，用xij表示Ai(I=1,2)煤厂提供给Bj(j＝1，2，3)居民区的煤量，则该问题的数学模型为目标函数；minZ＝lOx11＋5x12＋6x13＋4x21＋8x22＋12x23约束条件：)()3,2,1;2,1(,0)(40)(70)(50)(100)(6032313222121211122322211131211运煤量不能为负的需求煤量的需求煤量的需求煤量的供煤量的供煤量jixBxxBxxBxxAxxxAxxxij2．线性规划问题的特点和数学模型从以上两例可以看出，它们都属于一类优化问题．它们的共同持点是：(1)每一个问题都用一组决策变量(x1，x2，……，xn)表示某一方案：这组决策变量的值就代表一个具体的方案．一般这些变量的取值是非负的。(2)存在一定的约束条件，这些约束条件可以用一组线性等式或线性不等式来表示．(3)都有一个要求达到的目标，它可以用决策变量的线性函数来表示，这个函数称为目标函数．按问题的不同，要求目标函数实现最大化或最小化。满足以上三个条件的数学模型称为线性规划问题的数学模型，其一般形式为目标函数：nnxcxcxcZ2211max(min)约束条件（或s.t.）：nixbxaxaxabxaxaxabxaxaxaimnmnmmnnnn,2,1,0),(),(),(22112222212111212111约束条件常用英文缩写s.t.表示，而约束条件的最后一式又称为变量的非负性。线性规划主要应用目标函数求最值的情况，在以下各方面有广泛的应用：(1)在某一企业内部，如何配合产品的销售时间，使各部门的原料、产品的存储，分配的数量等最为合理；(2)在某企业生产的产品数量(或产值)固定时，如何在现有设备、人力、原料等条件限制下，合理组织生产，使经济效益最高；(3)在某一地区的交通网(公路网或铁路网)中，如何合理地组织运输，使总运费最小；(4)当市场上产品(或原料)价格变动时，对于这些变化，企业如何做出最优决策；(5)合理下料问题：利用某种类型的原料下料时，如何达到既满足需求，又使废料最少；(6)配料问题．生产某类由各种原料配制的产品(如混合饲料等)时，如何满足规定的质量标准，又使产品的成本最低；(7)库存问题，在仓库的容量及其它限制条件下，确定库存物资的品种、数量、期限，使得库存放益最高；(8)在投入产出模型中，引进某一目标函数，制定最优的企业(或地区)经济计划。二、线性规划问题的解法图解法只适用于两个变量的简单线性规划问题。这种解法比较简单，也有助于几何直观地理解线性规划问题。这里不做介绍。软件解法：规划模型的求解常用软件求解，主要有Excel,Lingo,Matlab等，这里用Lingo求解。问题一：MaxZ=32x1+30x23x1+4x2≤36(设备A对产量的限制)5x1+4x2≤40(设备B对产量的限制)，9x1+8x2≤76(设备C对产量的限制)，x1，x2≥0(产量不能为负值)．在Lingo中输入模型，注意书写格式：1，目标函数的变量Z不写；程序不分大小写；2，每行以分号结束；3，加、减、乘、除等运算符号一个都不能少；4，“”号等同于“≤”号，“”号等同于“≥”号；5，所有函数均要加以前缀“@”符号；6，注释语句用感叹号“!”开头；7，非负约束是软件的缺省设置，可以不输入。请看演示：程序：Max=32*x1+30*x2;3*x1+4*x236;5*x1+4*x240;9*x1+8*x276;结果为：Globaloptimalsolutionfound.Objectivevalue:282.6667Infeasibilities:0.000000Totalsolveriterations:3VariableValueReducedCostX11.3333330.000000X28.0000000.000000RowSlackorSurplusDualPrice1282.66671.00000020.0000001.16666731.3333330.00000040.0000003.166667即经过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.166667千元。对问题二，有Lingo程序：min=10*x11+5*x12+6*x13+4*x21+8*x22+12*x23;x11+x12+x13=60;x21+x22+x23=100;x11+x21=50;x12+x22=70;x13+x23=40;求解结果为：Globaloptimalsolutionfound.Objectivevalue:940.0000Infeasibilities:0.000000Totalsolveriterations:1VariableValueReducedCostX110.0000009.000000X1220.000000.000000X1340.000000.000000X2150.000000.000000X2250.000000.000000X230.0000003.000000RowSlackorSurplusDualPrice1940.0000-1.00000020.0000000.00000030.000000-3.00000040.000000-1.00000050.000000-5.00000060.000000-6.000000结果解释：分配供煤量为(0，20，40；50，50，0)，最小运输量为940，三、线性规划问题解的理论1．线性规划模型的标准型实际问题的线性规划模型是多种多样的，在众多的样式中可规定一种样式为标准型，以便于研究和求解．在线性规划模型的标准型中，有n个决策变量，m个约束条件，约束条件为等式约束，且决策变量为非负．求目标函数的最小值．标准型表达式为：nnxcxcxcZ2211max(min)s.t.nixbxaxaxabxaxaxabxaxaxaimnmnmmnnnn,2,1,022112222212111212111在标准型中，规定各约束条件的右端项bi≥0，否则等式两端乘以“-1”，其简写形式为；0..minXbAXtsXczT其中，A称为约束条件的系数矩阵，c为价值向量，b为资源向量，X为决策向量。关于线性规划模型的求解，通常用单纯形法。这里不讲，只讲如何用Lingo11.0规划软件来求解。（Lingo软件的算法就是单纯形法）先建立如下例题的线性规划模型。例2某工厂生产甲、乙、丙三种铝合金产品，生产每单位产品甲需用铝和铁分别是3公斤和2公斤，生产每单位产品乙需用铝和铁分别是1公斤和3公斤，生产每单位产品丙需用铝和铁分别是1公斤和2公斤，已知生产每单位产品分别能获得5元、4元和3元，而工厂每天能得到的原料供应为铝840公斤、铁700公斤。试问如何安排三种铝合金产品的生产，可使工厂能获得最大利润？解：将所有关系用表格形式表出，便于建立模型。铝铁获利甲325乙134丙123供应量840700建立模型如下：设决策变量：x1，x2，x3分别为甲、乙、丙的产量，则Max=5*x1+4*x2+3*x3;S.t.3*x1+x2+x3=840;2*x1+3*x2+2*x3=700;结果为：Globaloptimalsolutionfound.Objectivevalue:1540.000Infeasibilities:0.000000Totalsolveriterations:2VariableValueReducedCostX1260.00000.000000X260.000000.000000X30.0000000.000000RowSlackorSurplusDualPrice11540.0001.00000020.0000001.00000030.0000001.000000x1=260,x2=60,x3=0,最大利润为1540元。资源全部用完。灵敏度分析：先设置：LINGO-Options-GeneralSolver-DualComputations:选中prices&Rangens，点OK。再作灵敏度分析：LINGO-Range，得如下结果：Rangesinwhichthebasisisunchanged:ObjectiveCoefficientRangesCurre