第3章_线性规划的建模与应用.ppt

实用运筹学－运用Excel建模和求解 第3章 线性规划的建模与应用 本章内容要点 线性规划问题的四种主要类型 线性规划的建模与应用 本章节内容 3.1 资源分配问题 3.2 成本收益平衡问题 3.3 网络配送问题 3.4 混合问题 3.5 线性规划模型的应用 本章主要内容框架图 3.1资源分配问题 例3.1 某工厂要生产两种新产品：门和窗。 经测算，每生产一扇门需要在车间1加工1小时、在车间3加工3小时；每生产一扇窗需要在车间2和车间3各加工2小时。而车间1每周可用于生产这两种新产品的时间为4小时、车间2为12小时、车间3为18小时。 已知每扇门的利润为300元，每扇窗的利润为500元。而且根据经市场调查得到的该两种新产品的市场需求状况可以确定，按当前的定价可确保所有新产品均能销售出去。问该工厂如何安排这两种新产品的生产计划，可使总利润最大？ 3.1资源分配问题 解：例3.1可表示。 3.1资源分配问题 （1）决策变量 本问题的决策变量是每周门和窗的产量。 可设：x1为每周门的产量（扇）； x2为每周窗的产量（扇）。 （2）目标函数 本问题的目标是总利润最大。由于门和窗的单位利润分别为300元和500元，而其每周产量分别为x1和x2，所以每周总利润z为： z = 300x1＋500x2 （元） 3.1资源分配问题 （3）约束条件 本问题的约束条件共有四个。 车间1每周可用工时限制：x1 ? 4 车间2每周可用工时限制：2x2 ? 12 车间3每周可用工时限制：3x1 +2x2 ? 18 非负约束:x1 ? 0, x2 ? 0 3.1资源分配问题 例3.1的线性规划模型: 3.1 资源分配问题 资源分配问题是将有限的资源分配到各种活动（决策）中去的线性规划问题。这一类问题的共性是在线性规划模型中每一个函数约束均为资源约束, 并且每一种资源都可以表现为如下的形式： 使用的资源数量 ? 可用的资源数量 对任何资源分配问题，有三种数据必须收集： （1）每种资源的可供量； （2）每一种活动所需要的各种资源的数量, 对于每一种资源与活动的组合,单位活动所消耗的资源量必须首先估计出来； （3）每一种活动对总的绩效测度（如总利润）的单位贡献（如单位利润）。 3.2 成本收益平衡问题 成本收益平衡问题与资源分配问题的形式完全不同，这种差异主要是因为两种问题的管理目标不同而造成的。 在资源分配问题中，各种资源是受限制的因素（包括财务资源），问题的目标是最有效地利用各种资源，使获利最大。 而对于成本收益平衡问题，管理层采取更为主动的姿态，他们指明哪些收益必须实现（不管如何使用资源），并且要以最低的成本实现所指明的收益。这样，通过指明每种收益的最低可接受水平，以及实现这些收益的最小成本，管理层期望获得成本和收益之间的适度平衡。因此，成本收益平衡问题是一类线性规划问题，这类问题中，通过选择各种活动水平的组合，从而以最小的成本来实现最低可接受的各种收益水平。 3.2 成本收益平衡问题 成本收益平衡问题的共性是，所有的函数约束均为收益约束，并具有如下的形式： 完成的水平?最低可接受的水平 如果将收益的含义扩大，所有以“?”表示的函数约束均为收益约束。在多数情况下，最低可接受的水平是作为一项政策由管理层制定的，但有时这一数据也可能是由其他条件决定。 成本收益平衡问题需要的三种数据： （1）每种收益的最低可接受水平（管理决策）； （2）每一种活动对每一种收益的贡献（单位活动的贡献）； （3）每种活动的单位成本。 3.2 成本收益平衡问题 排班问题是成本收益平衡问题研究的最重要的应用领域之一。在这一领域中，管理层意识到在向顾客提供令人满意的服务水平的同时必须进行成本控制，因此，必须寻找成本和收益之间的平衡。于是，研究如何规划每个轮班人员才能以最小的成本提供令人满意的服务。 例3.2 某航空公司正准备增加其中心机场的往来航班，因此需要雇佣更多的服务人员。不同时段有最少需要服务人员数，有5种排班方式，每8小时为一班。 3.2 成本收益平衡问题 例3.2（续）5种排班方式 排班1：6AM～2PM，即早上6点上班； 排班2：8AM～4PM，即早上8点上班； 排班3：中午～8PM，即中午12点上班；排班4：4PM～午夜，即下午4点上班； 排班5：10PM～6M，即晚上10点上班。 3.2 成本收益平衡问题 解:这是一个纯成本收益平衡问题。 （1）决策变量 本问题的决策是不同排班的人数。 设：xi为排班i的人数 (i＝1,2,?,5 ) （2）目标函数 本问题的目标是人员总费用（工资）最少，即 3.2 成本收益平衡问题 （3）约束条件 ① 每个时段的在岗人数必须不少于最低