第1章线性规划引论

《第1章线性规划引论》由会员分享，可在线阅读，更多相关《第1章线性规划引论（47页珍藏版）》请在文档大全上搜索。

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表示两个仓库；每一条箭线表示一条可能的运输路线，并给出了相应的单位运输成本，对运输量有限制的路线的最大运输能力也同时给出。物流网络