1-1第一讲 规划模型1

第一讲 规划模型 本讲介绍的规划模型是一类有着广泛应用的确定性的系统优化模型。这类规 划问题，模型规范，建模直接，激发想象；模型求解方法典型，实用面宽广。掌 握这类规划问题的数学建模、是建模者必须具备的基本建模素养。 规划模型的应用极其广泛，其作用已为越来越多的人所重视。随着计算机的 逐渐普及，它越来越急速地渗透于工农业生产、商业活动、军事行为、核科学研 究的各个方面，为社会节省的财富、创造的价值无法估量。 在数模竞赛过程中，规划模型是最常见的一类数学模型。从历年全国大学生 数模竞赛试题的解题方法统计结果来看，规划模型共出现了近 20 次，占到了近 50%，也就是说每两道竞赛题中就有一道涉及到利用规划理论来分析、求解。 下面首先讨论静态系统的优化问题，介绍线性规划、整数规划、目标规划和 非线性规划；然后讨论动态系统的多阶段优化问题。 线性规划问题及其数学模型 线性规划模型 线性规划是运筹学的重要分支之一。一般认为，运筹学的主要分支有规划论 (包括线性规划、非线性规划、动态规划等)、排队论、对策论(亦称博奕论)与决 策分析、图论、存贮论、模型论等分支线性规划只是运筹学中研究较早，理论 比较完整、应用最广的一个分支。 1线性规划问题 在生产管理和经营活动中，经常提出一类问题，即如何合理地利用有限的人 力、物力等资源、以便得到最好的经济效益。先来看两个实例。 问题 1 拟定生产计划问题 问题提出 某工厂生产甲、乙两种产品这两种产品都需要在 A，B，C 三种 不同设备上加工，每吨甲、乙产品在不同设备上加工所需的台时，它们销售后所 能获得的利润值以及这三种加工设备在计划期内能提供的有限台时数均列于下表 中如何安排生产计划，即甲、乙两种产品各生产多少吨，可使该厂所获利润最 大? 每吨产品的加工台时 设备 甲 乙 有限台时数 A 3 4 36 B 5 4 40 C 9 8 76 利润（千元/吨） 32 30 求最大利润 模型建立 设计划期内甲、乙两种产品的产量分别为 x1 吨、x2 吨(x1，x2 称为决策变量)，该厂的目标是在不超过二种设备总有限台时数的条件下，确定 产量 x1 及 x2，以获得最大利润，用 Z 表示利润则有目标函数： Max Z = 32*x1 + 30*x2 由于设备 A，B，C 在计划期内的有效台时数分别为 3640，76，可以得出限制产 量的条件，即约束条件； 3*x1+4*x2”号等同于“”号； 5， 所有函数均要加以前缀“”符号； 6， 注释语句用感叹号“!”开头； 7， 非负约束是软件的缺省设置，可以不输入。 请看演示： 程序： Max = 32*x1 + 30*x2; 3*x1+4*x2Options-General Solver-Dual Computations:选中 prices 17*x1+10*x2+2*x3250000 变为 ）X5 + X6 + X7 + X8250001 时，目标函数值933400-1933399 当 REDUCE COST 或 DUAL PRICE 的值为。表示当微小扰动不影响目标函数。 有时，通过分析 DUAL PRICE，也可对产生不可行问题的原因有所了解。 灵敏度分析：如果做敏感性分析，则系统报告当目标函数的费用系数和约束右端 项在什么范围变化（此时假定其他系数保持不变）时，最优解或最优基保持不变。 报告中 INFINITY 表示正无穷， Ranges in which the basis is unchanged: Objective Coefficient Ranges Current Allowable Allowable Variable Coefficient Increase Decrease X1 1.000000 0.0 0.0 X2 1.000000 0.0 0.0 X3 1.000000 INFINITY 0.0 X4 1.000000 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.162101 Righthand Side Ranges Row Current Allowable Allowable RHS Increase Decrease 2 250000.0 261836.3 182249.1 3 380000.0 41014.33 15247.02 4 265200.0 30601.41 82317.48 5 408100.0 27374.90 10176.58 6 130100.0 2350.135 6321.840 7 0.0 43454.00 116890.8 8 0.0 43454.00 INFINITY 9 0.0 5129700. INFINITY 10 0.0 1890676. 396936.1如 上例：目标函数中4 的变量系数为，当它在1-0，1+15.13186= 1，16.13186 变化时，最优解保持不变。即价值系数的单独变化，能否引起最 优解的变化。 第一个约束右端项为 250000，当它在250000-182249.1,250000+261836.3 =15247.015625,436222.0625 范围变化时，最优基保持不变 。即资源限制的 单独变化能否引起最优基的变化。 注意事项： ） 目标函数用“min = ”或“max = ”开头，约束条件直接输入。 ） 变量名不能超过个字符。 ） 变量与其系数间的运算符号一个都不能少（如乘号“”等）。 ） = 与 等价，即小于等于与小于等价，大于等于与大于等 价。 ） 一般 LINGO 中能接受括号“（）”，例：400*(X1+X2)。 例 2（整数规则）有四个工人，要分别指派他们完成四项不同的工作，每个人 做各项工作所消耗的时间如表。问应该如何指派，才能使总的消耗时间为最小？ 工作所耗时间 工人 A B C D 甲 15 18 21 24 乙 19 23 22 18 丙 26 17 16 19 丁 19 21 23 17 这是一道典型的整数规则问题。 我们记派第 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+x33+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.000000 Extended solver steps: 0 Total solver iterations: 0 Variable Value Reduced Cost X21 1.000000 19.00000 X12 1.000000 18.00000 X33 1.000000 16.00000 X44 1.000000 17.00000 当 x21=x12=x33=x44=1 ，其