规划理论及模型

第一讲 规划理论及模型一、引言二、线性规划模型 三、整数线性规划模型 四、0-1整数规划模型 五、非线性规划模型 六、多目标规划模型回

停 下

七、动态规划模型

一、引言我们从2005年“高教社杯”全国大学生数模

竞 赛的B题“DVD在线租赁”问题的第二问和第三问 谈起.其中第二个问题是一个如何来分配有限资源， 从而达到人们期望目标的优化分配数学模型. 它 在运筹学中处于中心的地位. 这类问题一般可以 归结为 数学规划模型.

最优化问题概述 最优化问题的定义 最优化问题的分类及处理方法

最优化模型的基本要素

最优化问题的定义 最优化问题就是在给定条件下寻找最佳方案的问题，即在资源给定时寻找最好的目标，或在目标 确定时使用最少的资源。

最优化问题的分类及处理方法 无条件最优化问题：求导法等 约束条件为等式的有约束条件的最优化问题：拉 格朗日乘数法等 约束条件为不等式的有约束条件的最优化问题： 数学规划 数学规划模型：目标规划(一个、多个)、动 (静)态规划(与时间是否有关)、线性规划 (整数规划、0-1规划)、非线性规划

最优化(规划)模型的基本要素决策变量、目标函数和约束条件： 决策变量是问题中有待确定的未知因素。 目标函数是指对问题所追求的目标的数学描述。 约束条件是指实现问题目标的限制因素。

引例某工厂在计划期内要安排生产I、II两种产品，该工厂每生产一件产品I 可获利2元，每生产一件产品II可获利3元。问应如何安排计划使该工厂获利 最多？已知生产单位产品所需的设备台时及A、B两种原材料的消耗，如下表 所示 I II

设备 原材料A 原材料B

1 4 0

2 0 4

8台时 16kg 12kg

运用规划模型解决最优化问题的一般方法步 骤如下：①前期分析：分析问题，找出要解决的目标，约束 条件，并确立最优化的目标。 ②定义变量，建立最优化问题的数学模型，列出目 标函数和约束条件。 ③针对建立的模型，选择合适的求解方法或数学软 件。 ④编写程序，利用计算机求解。 ⑤对结果进行分析，讨论诸如：结果的合理性、正 确性，算法的收敛性，模型的适用性和通用性，算 法效率与误差等。

规划模型的应用极其广泛，其作用已为越来 越多的人所重视. 随着计算机的逐渐普及，它越

来越急速地渗透于工农业生产、商业活动、军事行为核科学研究的各个方面，为社会节省的财富、 创造的价值无法估量. 特别是在数模竞赛过程中，规划模型是最常 见的一类数学模型. 从92-06年全国大学生数模竞 赛试题的解题方法统计结果来看，规

划模型共出 现了15次，占到了50%,也就是说每两道竞赛题

中就有一道涉及到利用规划理论来分析、求解.

二、线性规划模型线性规划模型是所有规划模型中最基本、最 简单的一种. 2.1 线性规划模型的标准形式

例1.(食谱问题)设有 n 种食物，各含 m 种营养素，第 j 种食物中第 i 中营养素的含量为 aij , n 种 食物价格分别为c1, c2, …, cn,请确定食谱中n 种食 物的数量x1, x2, …, xn,要求在食谱中 m 种营养素 的含量分别不低于b1, b2, …, bm 的情况下，使得总 总的费用最低.

解 首先根据食物数量及价格可写出食谱费用为c1 x 1 c 2 x 2 c n x n ,

其次食谱中第 i 种营养素的含量为a i 1 x 1 a i 2 x 2 a in x n .

因此上述问题可表述为：m in c 1 x 1 c 2 x 2 c n x n a 1 1 x 1 a 1 2 x 2 a 1 n x n b1 a x a 2 2 x 2 a 2 n x n b2 21 1 s .t . a x a m1 1 m 2 x 2 a m n x n bm x 1 0 , x 2 0 , x n 0

上述食谱问题就是一个典型的线性规划问题， 它是指在一组线性的等式或不等式的约束条件下，

寻求以线性函数的最大(小)值为目标的数学模型.

例：某豆腐店用黄豆制作两种不同口感的豆腐出售。制作 口感较鲜嫩的豆腐每千克需要0.3千克一级黄豆及0.5千克 二级黄豆，售价10元；制作口感较厚实的豆腐每千克需要

0.4千克一级黄豆及0.2千克二级黄豆，售价5元。现小店购入9千克一级黄豆和8千克二级黄豆。 问：应如何安排制作计划才能获得最大收益。

一、问题前期分析 该问题是在不超出制作两种不同口感豆腐所需黄豆总量条 件下合理安排制作计划，使得售出各种豆腐能获得最大收

益。二、模型假设 1.假设制作的豆腐能全部售出。 2.假设豆腐售价无波动。

变量假设： 设计划制作口感鲜嫩和厚实的豆腐各x1千克和 x2千克，可获得收益R元。目标函数：获得的总收益最大。 总收益可表示为：。。。

受一级黄豆数量限制：。。。受二级黄豆数量限制：。。。

综上分析，得到该问题的线性规划模型：

运输问题(常见典型的线性规划问题)

例2. 设要从甲地调出物资2000吨，从乙地调出物资1100吨，分别供给A地1700吨、B地1100吨、C 地200吨、D地100吨. 已知每吨运费如表1.1所示. 假定运费与运量成正比. 在这种情况下，采用不 同的调拨计划，运费就可能不一样. 现在问：怎 样才能找出一个运费最省的调拨计划？