数学模型实验指导书

数学规划在工程技术、经济管理、科学研究和日常生活等许多领域中，人们经常遇到的一类决策问题是：在一系列客观或主观限制条件下，寻求使关注的某个或多个指标达到最大（或最小）的决策。例如，结构设计要在满足强度要求条件下选择材料的尺寸，使其总重量最轻；资源分配要在有限资源约束下制定各用户的分配数量，使资源产生的总效益最大；运输方案要在满足物资需求和装载条件下安排从各供应点到各需求点的运量和路线，使运输总费用最低；生产计划要按照产品工艺流程和顾客需求，制定原料、零件、部件等订购、投产的日程和数量，尽量降低成本使利润最高。上述这种决策问题通常称为优化问题。人们解决这些优化问题的手段大致有以下几种：1．依赖过去的经验判断面临的问题。这似乎切实可行，并且没有太大的风险，但是其处理过程会融入决策者太多的主观因素，常常难以客观地加以描述，从而无法确认结果的最优性。2．做大量的试验反复比较。这固然比较真实可靠，但是常要花费太多的资金和人力，而且得到的最优结果基本上离不开开始设计的试验范围。用数学建模的方法建立数学规划模型求解最优决策。虽然由于建模时要作适当的简化，可能使得结果不一定完全可行或达到实际上的最优，但是它基于客观规律和数据，又不需要多大的费用，具有前两种手段无可比拟的优点。如果在此基础上再辅之以适当的经验和试验，就可以期望得到实际问题的一个比较圆满的回答，是解决这种问题最有效、最常用的方法之一。在决策科学化、定量化的呼声日益高涨的今天，用数学建模方法求解优化问题，无疑是符合时代潮流和形势发展需要的。数学规划模型一般有三个要素：一是决策变量，通常是该问题要求解的那些未知量，不妨用n维向量x=(x1,x2,…,xn)T表示；二是目标函数，通常是该问题要优化（最小或最大）的那个目标的数学表达式，它是决策变量x的函数，这里抽象地记作f(x)；三是约束条件，由该问题对决策变量的限制条件给出，即x允许取值的范围x∈Ω,Ω称可行域，常用一组关于x的不等式（也可以有等式）gi(x)2≤0(I=1,2,…,m)来界定。一般地，这类模型可表示成如下形式：optz=f(x)（1）s.t.gi(x)≤0（2）这里opt(optimize)是最优化的意思，可以是求极小min(minimize)或求极大max(maximize)；s.t.(subjectto)是“受约束于”的意思，满足（2）式的解x称为可行解，同时满足（1）式，（2）式的解x*称为最优解。模型（1），（2）是微积分中多元函数的条件极值问题。当约束条件（2）比较简单（如全为等式）时，多元微积分中介绍过求解析解的基本原理和方法，即令目标函数（对等式约束需要加上与其对应的拉格朗日乘子的乘积项）的偏导数为零，求出驻点后再比较驻点上的函数值。但是，大多数实际问题归结的上述形式的模型很难用这种方法求解，因为：第一，解析方法只能处理目标函数f和约束条件gi，并且决策变量个数n，约束条件个数m比较小的情形，当f，gi稍微复杂时通常至少需要求解比较复杂的非线性方程（组），很难得到解析解；第二，当最优解在可行域的边界上取得时（不少实际问题正是如此），就不能用原有的求条件极值的方法求解，所以对于优化问题的这类模型必须寻求有效的数值解法。当模型（1），（2）中决策变量x的所有分量xi(i=1,…n)均为实数，且f,gi(i=1,…m)都是线性函数时，称为线性规划。若f,gi至少有一个非线性函数，则称为非线性规划。若x至少有一个分量只取整数，则称为整数规划。线性规划和非线性规划是连续规划，而整数规划是离散优化（组合优化），它们统称为数学规划。本实验指导书包括数学规划方面的两个实验：线性规划，整数规划。用LINDO和LINGO解线性规划和整数规划：LINDO(LinearInteractiveandDiscreteOptimizer)和LINGO(LinearInteractiveandGeneraiOptimizer)是由美国芝加哥大学的LinusSchrage于1986年开发的优化计算软件包，LINDO可以用来求解线性规划、线性整数规划、二次规划和整数二次规划，而LINGO除此之外还可以解非线性规划和非线性整数规划。从LINDO公司的主页（）上同学们可以了解更多的有关信息，并可以下载软件的试用版。3实验一线性规划（LP）1．实例及数学模型例．加工奶制品的生产计划问题一奶制品加工厂用牛奶生产A1、A2两种奶制品，1桶牛奶可以在设备甲上用12小时加工成3公斤A1，或者在设备乙上用8小时加工成4公斤A2。根据市场需求，生产的A1、A2能全部售出，且每公斤A1获利24元，每公斤A2获利16元。现在加工厂每天能得到50桶牛奶的供应，每天正式工人总的劳动时间为480小时，并且设备甲每天至多能加工100公斤A1，设备乙的加工能力没有限制。试为该厂制定一个生产计划，使每天获利最大，并进一步讨论以下3个附加问题：1）若用35元可以购买到1桶牛奶，应否作这项投资？若投资，每天最多购买多少桶牛奶？2）若可以聘用临时工人以增加劳动时间，付给临时工人的工资最多是每小时几元？3）由于市场需求变化，每公斤A1的获利增加到30元，应否改变生产计划？数学模型设每天用x1桶牛奶生产A1，用x2桶牛奶生产A2目标函数设每天获利为z元。x1桶牛奶可生产3x1公斤A1，获利24*3x1，x2桶牛奶可生产4x2公斤A2，获利16*4x2，故z=72x1+64x2约束条件原料供应生产A1、A2的原料（牛奶）总量不超过每天的供应50桶，即x1+x2≤50劳动时间生产A1、A2的总加工时间不超过每天正式工人总的劳动时间480小时，即12x1+8x2≤480设备能力A1的产量不得超过设备甲每天的加工能力100公斤，即3x1≤100非负约束x1、x2均不能为负值，即x1≥0，x2≥04综上所述可得Maxz=72x1+64x2(1)s.t.x1+x2≤50(2)12x1+8x2≤480(3)3x1≤100(4)x1≥0，x2≥0(5)显然，目标函数和约束条件都是线性的，这是一个线性规划（linearprogramming,LP），求出的最优解将给出使净利润最大的生产计划，要讨论的问题需要考虑参数的变化对最优解和影响，一般称为敏感性（或灵敏度）分析。2．用LINDO求解线性规划用LINDI求解线性规划(LP)时，首先在LINDO软件的模型窗口输入一个LP模型，模型以MAX或MIN开始，按线性规划问题的自然形式输入（见下面例子所示）。输入结束时只需键入END。以下解加工奶制品的生产计划问题：Maxz=72x1+64x2(1)s.t.x1+x2≤50(2)12x1+8x2≤480(3)3x1≤100(4)x1≥0，x2≥0(5)由于LINDO中已假设所有的变量都是非负的，所以非负约束条件不必输入；LINDO也不区分变量中的大小写字符（实际上任何小写字符将被转换为大写字符）；约束条件中的“〈=”及“〉=”可用“〈”及“〉”代替。在LINDO模型窗口输入如下：Max72x1+64x2ST!说明：ST以下为约束条件x1+x2=5012x1+8x2=480！说明：一个约束条件分成两行写也没关系3x1=1005END用鼠标单击菜单中的求解命令（SOLVE）就可以得到解答，结果窗口显示如下：LPOPTIMUMFOUNDATSTEP2OBJECTIVEFUNCTIONVALUE1)3360.000VARIABLEVALUEREDUCEDCOSTX120.0000000.000000X230.0000000.000000ROWSLACKORSURPLUSDUALPRICES2)0.00000048.0000003)0.0000002.0000004)40.0000000.000000NO.ITERATIONS=2一个问题解答之后，LINDO会询问是否需要做敏感性分析（DORANGE(SENSITVITY)ANALYSIS?）如果你不需要，应回答”N”(N))。计算结果表明：“LPOPTIMUMFOUNDATSTEP2”表示单纯形法在两次迭代（旋转）后得到最优解。“OBJECTIVEFUNCTIONVALUE1)3360.000”表示最优目标值为3360.000（LINDO中将目标函数自动看作第1行，从第二行开始才是真正的约束条件）。“VALUE”给出最优解中各变量（VARIABLE）的值：x1=20.000000，x2=30.000000。“REDUCEDCOST”的含义是（对MAX型问题）：基变量的REDUCEDCOST值为0，对于非基变量，相应的REDUCEDCOST值表示当非基变量增加一个单位时（其它非基变量保持不变）目标函数减少的量。本例中两个变量都是基变量。“SLACKORSURPLUS”给出松弛（或剩余）变量的值，表示约束是否取等式约束；第2、第3行松弛变量均为0，说明对于最优解而言，两个约束均取6等式约束；第4行松弛变量为40.000000，说明对于最优解而言，这个约束取不等式约束。“DUALPRICES”给出约束的影子价格（也称为对偶价格）的值：第2、第3、第4行（约束）对应的影子价格分别48.000000，2.000000，0.000000。“NO.ITERATIONS=2”表示用单纯形法进行了两次迭代（旋转）。如果对上面的“是否需要做敏感性分析”的询问回答“Y”（YES），则LINDO还会输出以下结果：RANGESINWHICHTHEBASISISUNCHANGED:OBJCOEFFICIENTRANGESVARIABLECURRENTALLOWABLEALLOWABLECOEFINCREASEDECREASEX172.00000024.0000008.000000X264.0000008.00000016.000000RIGHTHANDSIDERANGESROWCURRENTALLOWABLEALLOWABLERHSINCREASEDECREASE250.00000010.0000006.6666673480.00000053.33333280.0000004100.000000INFINITY40.000000以上显示的是当前最优基（矩阵）保持不变的充分条件（RANGESINWHICHTHEBASISISUNCHANGED），包括目标函数中决策变量应的系数的变化范围（OBJCOEFFICIENTRANGES）和约束的右端项的变化范围（RIGHTHANDSIDERANGES）两部分。例如：前一部分的输出行X172.00000024.0000008.000000表示决策变量X1当前在目标函数中对应的系数为72，允许增加24和减少8。也就是说，当该系数在区间[64，96]上变化时（假设其它条件均不变），当前最优基矩阵保持不变。对X2对应的输出行也可以类似地解释。由于此时约束没有任何改变，所以最优基矩阵保持不变意味着最优解不变（当然，由于目标函数中7的系数发生变化，最优值还是会变的）。后一部分的输出行250.00000010.0000006.666667表示约束2当前右端项为50，允许增加10和减少6.666667。也就是说，当该系数在区间[43.333333，60]上变化时（假设其它条件均不变），当前最优基矩阵保持不变。对约束3、约束4对应的输出行也可以类似地解释。由于此时约束已经改变，虽然最优基矩阵保持不变，最优解和最优值还是会变的。但是，由于最优基矩阵保持不变，所以前面的“DUALPRICES”给出的约束的影子价格此时仍然是有效的。用LINDO求解加工奶制品的生产计划，结果如下：20桶牛奶生产A1,30桶生产A2，利润3360元。1）35元可买到1桶牛奶，要买吗？由于原料的影子价格为48，3548,应该买！2）聘用临时工人付出的工资最多每小时几元？由于工时的影子价格为2，聘用临时工人付出的工资最多每小时2元3）A1获利增加到30元/千克，应否改变生产计划由于要使最优解保持不变，X1系数的允许变化范围为[64，96]