第1章线性规划引论

1、线性规划 线性规划是一种帮助管理者制定决策的方法; 在许多领域都有成功的应用案例, 它在模型上表现为一个线性的函数在一组线性约束条件下的求极大值或求极小值问题; 最常见的三类问题是: 资源分配问题资源分配问题; 成本效益平衡问题和成本效益平衡问题和物流网络配送问题物流网络配送问题.资源分配问题资源分配问题 红星重型机械厂的产品组合问题 产品甲: 需要原料A,原料B,设备工时; 产品乙: 也需要原料A,原料B,设备工时;由于原料A,原料B,设备工时的数量有限,如何安排生产,使获利最大? 问题 1.公司是否该生产这两个产品? 2如果生产, 产品生产组合如何?(各生产多少?)资源分配问题资源分配问题

2、 这是一个定量问题 决策目标-利润最大化 步骤1-收集相关数据如下:甲乙资源总量原料A106原料B028设备工时2318单位利润4万元3万元资源分配问题资源分配问题 步骤2- 建立数学模型 1) 决策变量决策量化的手段 x1=产品甲产品甲 的生产数量的生产数量 x2 =产品乙产品乙 的生产数量的生产数量 2) 目标函数-衡量决策效果(优劣)的指标 Z= 4x1 + 3x2 求最大值求最大值 3) 约束条件 x1 6 (原料A数量约束) 2 x2 8 (原料B数量约束) 2x1 + 3x2 18 (设备工时约束) x1, x2 0 (非负约束) 建立数学规划模型的四个步骤建立数学规划模型的四个步

3、骤 明确问题，确定决策变量明确问题，确定决策变量； 决策变量是构成解决方案的要素或单元，决策变量的决策变量是构成解决方案的要素或单元，决策变量的组合构成一个可行解决方案。组合构成一个可行解决方案。 明确约束条件并用决策变量的等式或不等式表示；明确约束条件并用决策变量的等式或不等式表示； 尽可能分类描述，防止差错和遗漏尽可能分类描述，防止差错和遗漏 用决策变量的函数表示目标，并确定是求极大（用决策变量的函数表示目标，并确定是求极大（Max）、）、极小（极小（Min）还是特定值；）还是特定值； 根据决策变量的物理性质研究变量是否有非负性或上下根据决策变量的物理性质研究变量是否有非负性或上下界。界。

4、资源分配问题资源分配问题 资源分配（资源分配（resource-allocation）问题问题是将有限的资源 分配到各种活动中去的线性规划问题。这一类问题的 共性是在线性规划模型中每一个函数限制均为资源限 制(resource constraint) , 并且每一种有限资源都可以表 现为如下的形式： 使用的资源数量使用的资源数量 可用的资源数量可用的资源数量资源分配问题资源分配问题 例1的数学模型可以用代数形式描述如下： 这实际上是求一个线性函数在一组线性约束条件下的最大值问题，我们称之为线性规划问题模型线性规划问题模型。 资源分配问题资源分配问题 我们称x1、x2为决策变量决策变量， Z =

5、 4 x1 + 3 x2为目标函数目标函数， 约束（1.1）-（1.3）为函数约束函数约束，约束（1.4）为非非负约束负约束。 决策变量的任何一个取值称为模型的一个解解，若解满足所有约束条件，则称为可行解可行解，反之（至少违反一个约束条件），称其为非可行解非可行解，使目标函数值最大化的可行解称为最优解最优解。 成本收益平衡问题成本收益平衡问题 成本收益平衡问题（成本收益平衡问题（ Cost-benefit-trade-off Problem ） 是一类线性规划问题，这类问题中，通过选择各种 活动水平的组合，从而以最小的成本来实现最低可 接受的各种收益的水平。这类问题的共性是，所有 的函数约束均

6、为收益约束，并具有如下的形式： 完成的水平完成的水平 最低可接受的水平最低可接受的水平成本效益平衡问题成本效益平衡问题 某饲料公司希望用玉米、红薯两种原料配制一种混合饲料，各种原料包含的营养成份和采购成本都不相同，公司管理层希望能够确定混合饲料中各种原料的数量，使得饲料能够以最低的成本达到一定的营养要求。研究者根据这一目标收集到的有关数据如下： 成本效益平衡问题成本效益平衡问题 为建立线性规划模型，我们引入变量如下： x1 = 混合饲料中玉米的数量 x2 = 混合饲料中红薯的数量成本效益平衡问题成本效益平衡问题 目标函数是Z = 0.8 x1 + 0.5 x2，表示饲料的成本函数，即如何确定x

7、1、x2使得成本Z = 0.8 x1 + 0.5 x2最低且满足最低营养要求的约束，这些约束条件是： 碳水化合物需求： 8 x1 + 4 x2 20 蛋白质需求： 3 x1 + 6 x2 18 维他命需求： x1 + 5 x2 16 另有非负约束：x1 0， x2 0成本效益平衡问题成本效益平衡问题 因此，这个问题的线性规划模型为：物流网络配送问题物流网络配送问题 伟达物流公司需将甲、乙、丙三个工厂生产的一种新产品运送到A、B两个仓库，甲、乙两个工厂的产品可以通过铁路运送到仓库A，数量不限；丙工厂的产品可以通过铁路运送到仓库B，同样，产品数量不限。由于铁路运输成本较高，公司也可考虑由独立的卡车

8、来运输，可将多达80个单位的产品由甲、乙、丙三个工厂运到一个配送中心，再从配送中心以最多90单位的载货量运到各个仓库,公司管理层希望以最小的成本来运送所需的货物。 物流网络配送问题物流网络配送问题 需要收集每条线路上的单位运输成本和各工厂产品的产量以及各仓库分配量等数据： 物流网络配送问题物流网络配送问题 为了更清楚地说明这个问题，我们用一个网络图来表示该网络配送问题（见图2-1）。图中节点v1、v2、v3表示甲、乙、丙三个工厂，节点v4表示配送中心，节点v5、v6表示两个仓库；每一条箭线表示一条可能的运输路线，并给出了相应的单位运输成本，对运输量有限制的路线的最大运输能力也同时给出。物流网络

9、配送问题物流网络配送问题物流网络配送问题物流网络配送问题 我们要解决的是各条路线最优运输量，引入变量fij表示由 vi经过路线(vi,vj)运输到vj的产品数。问题的目标是总运输成本最小化，总运输成本可表示为： 总运输成本 = 7.5 f15+ 3 f14 + 8.2 f25 + 3.5 f24 + 2.3 f45 + 3.4 f34 + 2.3 f46 + 9.2 f36物流网络配送问题物流网络配送问题 相应的约束条件包括对网络中的每个节点的供求平衡约束。对生产节点v1、v2、v3来说，由某一节点运出的产品数量等于其产量，即： f15 + f14 = 100 f25 + f24 = 80 f

10、34 + f36 = 70物流网络配送问题物流网络配送问题 对配送中心v4，运进的产品数量等于运出的产品数量： f14 + f24 + f34 = f45 + f46 对仓库v5、v6，运进的产品数量等于其需求量 f15 + f25+ f45 = 120 f46+ f36 = 130物流网络配送问题物流网络配送问题 此外，对网络中有运输容量限制的路线的约束是：该路线上的运输产品数量不超过该线路的运输能力，即： f1480， f24 80， f3480， f45 90， f46 90。 并且，所有fij 0（非负约束）。物流网络配送问题物流网络配送问题共同的特征 从以上几个例子可以看出，线性规划

11、问题有如下共同的特征： 每个问题都用一组决策变量（x1, x2, . . . , xn ），这组决策变量的值都代表一个具体方案； 有一个衡量决策方案优劣的函数，它是决策变量的线性函数，称为目标函数。按问题不同，要求目标函数实现最大化或最小化； 存在一些约束条件，这些约束条件包括函数约束，可以用一组决策变量的线性函数（称为约束函数约束函数）大于等于“”、小于等于“”或等于“=”一个给定常数（称为右端项右端项）；决策变量的非负约束。一般形式 线性规划的一般形式为：资源分配问题一般形式 资源分配问题是将有限的资源分配从事各种活动的线性规划问题，其一般形式可以描述为： 管理层计划用m种资源去从事n种活

12、动，通过收集每种资源的总量和每种活动单位资源使用量以及单位贡献等数据如下表所示，来确定活动的数量使得在资源许可的条件下贡献最大。资源分配问题一般形式资源分配问题一般形式 我们用表示xj第j种活动的数量(水平)，则目标函数 最大化。 对于第i种资源， 我们有约束条件： 即资源消耗量不超过的资源总量 资源分配问题一般形式 因此，这类问题的数学模型为： 成本效益平衡问题一般形式 以上所讨论的成本效益平衡问题是通过选择各种活动水平的组合，从而以最小的成本实现最低可接受的各种效益水平。该问题的一般形式可描述为： 管理层计划用n种活动去提高m种效益的水平，通过调查得知每种活动对各种效益的单位贡献、每种活动

13、的单位成本以及每种效益的最低可接受水平如表 成本效益平衡问题一般形式成本效益平衡问题一般形式 我们用表示xj第j种活动的数量(水平)，则目标函数 最小化。对于第i种效益，我们有 成本效益平衡问题一般形式 因此，这类问题的数学模型为： 物流网络配送问题一般形式 物流网络配送问题一般形式可描述为：假定在一n个顶点m条弧（线路）的运输网络中，有若干发点发点发送一定数量的物资流，同时又有若干收点收点接收这些物资流。由于每条弧运输费用不同，运输能力也有一定限制，管理者希望以最小的运输成本完成由发点到收点的运输配送。 物流网络配送问题一般形式 我们用fij表示由 vi经过路线(vi,vj)运输到vj的流量

14、， Cij表示线路(vi,vj)的最大运输能力（容量限制）， wij表示由顶点vi沿线路(vi,vj)流向vj的单位流量成本。 物流网络配送问题一般形式 物流网络配送问题模型为 :线性规划问题的图解法线性规划问题的图解法 当决策变量只有两个时，线性规划问题可以用在平面上作图的方法求解，这种方法称为图解法。由于这种方法简单、直观、容易理解，所以有助于了解线性规划问题的实质和求解的原理。 现用红星重型机械厂的产品组合问题红星重型机械厂的产品组合问题中的线性规划来说明图解法 线性规划问题的图解法线性规划问题的图解法 红星重型机械厂的产品组合问题红星重型机械厂的产品组合问题的线性规划问题： 线性规划问

15、题的图解法线性规划问题的图解法 我们首先建立x1O x2坐标平面（见图2-2），坐标系上横轴是x1轴，纵轴是x2轴。由非负约束x1 0， x2 0可知，所有可行解的集合（称为可行域可行域）应在第一象限。然后，我们要逐个地查看每个函数约束都允许的非负解，再考虑所有的约束条件。 第一个函数约束x1 6，截取x1轴的直线x1 = 6的线上或线左边的解是满足这个约束条件的；第二个约束2x2 8，有相似的结果，即x2 = 4线及下方的解满足这个约束。我们将函数约束条件的边界直线称为约束边界约束边界，相应的方程称为约束边界方程约束边界方程 线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法线性规

16、划问题的图解法例1 确定了可行域以后，我们希望找出哪些解是最优解，即使目标函数Z = 4x1 + 3x2尽可能大的可行解。我们给目标函数一个值，例如给定Z =12，可以在图上画出一条直线4x1 + 3x2 = 12（见图1-3），在直线上的任一点处，对应的目标函数值均为12，故称该直线为目标函数的等值线等值线。Z =12只是目标函数的一个给定值，对于其它Z的给定值，如Z = 15也可在图上画出一条直线4x1 + 3x2 = 15，显然，对于Z的不同给定值k，4x1 + 3x2 = k是一组平行的直线族，当k的值由小变大时，目标函数的等值线平等移动，它与可行域的最后一个交点（一般是可行域的一个顶点）就是所求的最优点，即图2-3中的B点线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法线性规划问题的图解法 由上可以看出，线性规划问题的最优解出现在可行域的一个顶点上，此时线性规划问题