数据、模型与决策3

Data,ModelandDecisions数据、模型与决策Session3LinearProgrammingFormulationandApplications线性规划的建模与应用KeyCategoriesofLPProblems线性规划问题主要类型资源分配问题（resource-allocation）

成本收益平衡问题（cost-benefit-trade-off）

网络配送问题（distribution-network）

混合问题（mixedProblem）3.1资源分配问题资源分配问题是将有限的资源分配到各种活动（决策）中去的线性规划问题。这一类问题的共性是在线性规划模型中每一个函数约束均为资源约束,并且每一种资源都可以表现为如下的形式：使用的资源数量可用的资源数量对任何资源分配问题，有三种数据必须收集：（1）每种资源的可供量；（2）每一种活动所需要的各种资源的数量,对于每一种资源与活动的组合,单位活动所消耗的资源量必须首先估计出来；（3）每一种活动对总的绩效测度（如总利润）的单位贡献（如单位利润）。3.1资源分配问题例3.1某公司是商务房地产开发项目的主要投资商。目前，该公司有机会在三个建设项目中投资： 项目1：建造高层办公楼； 项目2：建造宾馆； 项目3：建造购物中心。每个项目都要求投资者在四个不同的时期投资：在当前预付定金，以及一年、二年、三年后分别追加投资。表3-1显示了四个时期每个项目所需资金（百万元）。投资者可以按一定的比例进行投资和获得相应比例的收益。年份办公楼项目宾馆项目购物中心项目0（现在）408090160805029080203107060净现值457050公司目前有2500万元资金可供投资，预计一年后，又可获得2000万元，两年后获得另外的2000万元，三年后还有1500万元以供投资。那么，该公司要在每个项目中投资多少比例，才能使其投资组合获得最大的总净现值？3.1资源分配问题解：这是一个资源分配问题。(1)决策变量设：x1，x2，x3分别为在办公楼项目、宾馆项目、购物中心项目中的投资比例(2)目标函数本问题的目标是总净现值最大3.1资源分配问题(3)约束条件本题的约束条件是公司在各期可获得的资金限制（资源约束）。但要注意的是：前一期尚未使用的资金，可以在下一期使用（为了简化问题，不考虑资金可获得的利息）。因此，每一时点的资金限制就表现为累计的资金。表3-2显示了累计的资金数据。年份办公楼项目宾馆项目购物中心项目可用资金0（现在）40809025110016014045219024016065320031022080净现值4570503.1资源分配问题数学模型（线性规划模型）3.1资源分配问题电子表格模型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点上班。时段排班1排班2排班3排班4排班5最少需要人数6AM～8AM√488AM～10AM√√7910AM～中午√√65中午～2PM√√√872PM～4PM√√644PM～6PM√√736PM～8PM√√828PM～10PM√4310PM～午夜√√52午夜～6PM√15每人每天工资(元)1701601751801953.2成本收益平衡问题解:这是一个纯成本收益平衡问题。（1）决策变量本问题的决策是不同排班的人数。设：xi为排班i的人数(i＝1,2,,5)（2）目标函数本问题的目标是人员总费用（工资）最少，即3.2成本收益平衡问题（3）约束条件

①每个时段的在岗人数必须不少于最低可接受水平（最少需要人数）②非负3.2成本收益平衡问题数学模型（线性规划模型）3.2成本收益平衡问题电子表格模型3.3网络配送问题通过配送网络能以最小的成本完成货物的配送，所以称之为网络配送问题。与确定资源和收益一样，在网络配送问题中，必须确定需求以及相应地确定需求的约束条件。确定需求约束的形式如下：提供的数量＝需求的数量3.3网络配送问题例3.3某公司网络配送问题。某公司在两个工厂生产某种产品。现在收到三个顾客的下个月定单要购买这种产品。这些产品会被单独运送，表3-4显示了从每个工厂到每个顾客的运送一个产品的成本。该表同样表明了每个顾客的订货量和每个工厂的生产量。现在公司的物流经理要决定从每个工厂运送多少个产品到每个顾客那里才能使总成本最小？

单位运输成本（元/个）产量（个）顾客1顾客2顾客3工厂170090080012工厂280090070015订货量(个)108927(产销平衡)3.3网络配送问题解:由于“总产量（27）＝总订货量（27）”，所以本问题是一个平衡运输问题。（1）决策变量本问题的决策为从每个工厂运送多少个产品到每个顾客那里。设：xi-j为从工厂i运输到顾客j的产品数量（i＝F1,F2;j=C1,C2,C3)（2）目标函数本问题的目标是使得公司总运输成本最低3.3网络配送问题（3）约束条件①从工厂运送出去的产品数量等于其产量②顾客收到的产品数量等于其订货量③非负3.3网络配送问题数学模型（线性规划模型）3.3网络配送问题电子表格模型3.4混合问题前面讨论了线性规划问题的三种类型：资源分配问题、成本收益平衡问题以及网络配送问题。每一类问题都是以一类约束条件为特色的。实际上，纯资源分配问题的共性是它所有的函数约束均为资源约束（≤）而成本收益平衡问题的共性是它所有的函数约束均为收益约束（）网络配送问题中，主要的函数约束为一特定类型的确定需求约束（＝）3.4混合问题但许多线性规划问题并不能直接归入三类中的某一类，一些问题勉强可以归入一类，因其主要的函数约束与表3-5的相应函数约束大致相同。另一些问题却没有一类占主导地位的函数约束，不能归入前三类中的某一类。因此，混合问题是第四类线性规划问题，这一类型将包括所有未归入前述三类中的线性规划问题。一些混合问题仅包含两类函数约束，而更多的是包含三类函数约束。3.4混合问题表3-5各类函数约束类型形式*解释主要用于资源约束LHSRHS对于特定的资源使用的数量

可获得的数量资源分配问题混合问题收益约束LHSRHS对于特定的收益到达的水平

最低可接受水平成本收益平衡问题混合问题确定需求约束LHS=RHS对于一些数量提供的数量=需求的数量网络配送问题混合问题*LHS=左式（一个SUMPRODUCT函数）RHS=右式（一般为常数）3.4混合问题配料问题。这类问题的一般提法是：由多种原料制成含有m种成分的产品，已知产品中所含各种成分的比例要求、各种原料的单位价格以及各原料所含成分的数量。考虑的问题是：应如何配料，可使产品的总成本最低。例3.4配料问题。某公司计划要用Ａ、Ｂ、C三种原料混合调制出三种不同规格的产品甲、乙、丙，产品的规格要求和单价、原料的供应量和单价等数据如表3-6所示。问：该公司应如何安排生产，可使总利润最大？3.4混合问题表3-6混合配料数据表ABC产品单价（元/千克）甲50%35%不限90乙40%45%不限85丙30%50%20%65原料供应量（千克）200150100原料单价（元/千克）6035303.4混合问题解：（1）决策变量本问题的难点在于给出的数据是非确定数值，而且各产品与原料的关系较为复杂。为了方便，设xij表示原料i（i=A，B，C）用于产品j（j=1为甲，j=2为乙，j=3为丙）的数量。（2）目标函数 本问题的目标是使总利润最大总利润＝产品收入－原料支出3.4混合问题（3）约束条件本题的约束条件：原料供应量限制3个、规格要求7个和决策变量非负。在例3.4中，有9个决策变量和10个函数约束条件，包括5个资源约束、2个收益约束和3个确定需求约束。3.4混合问题电子表格模型3.5线性规划模型的应用前面按照函数约束的分类，介绍了四种线性规划问题：资源分配问题（,资源约束）成本收益平衡问题（，收益约束）网络配送问题（=，确定需求约束）混合问题（包含两种或三种类型的约束函数）本节按照应用方面介绍线性规划在生产计划问题、资金管理问题、市场调查问题和混合配料问题等方面的应用3.5线性规划模型的应用建立线性规划模型的过程可以分为四个步骤：设立决策变量；用决策变量的线性函数表示目标，并确定是求最大（Max）还是最小（Min）；明确约束条件并用决策变量的线性等式或不等式表示；根据决策变量的物理性质研究变量是否有非负性。3.5线性规划模型的应用生产计划问题是企业生产过程中常常遇到的问题，其中最简单的一种形式可以描述如下（资源分配问题）：用若干种原材料（资源）生产某几种产品，原材料（或某种资源）供应量有一定的限制，要求制定一个产品生产计划，使其在给定的资源限制条件下能得到最大收益。3.5线性规划模型的应用例3.5某工厂生产甲、乙、丙三种产品，都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，也可以自行生产，但产品丙必须本厂铸造才能保证质量。有关情况的数据如表3-9所示。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸件由本公司铸造和由外包协作各应多少件？3.5线性规划模型的应用表3-9自行生产或外包的有关数据产品甲产品乙产品丙工时限制单件铸造工时（小时）51078000单件机加工工时（小时）64812000单件装配工时（小时）32210000自产铸件成本（元/件）354外协铸件成本（元/件）56－机加工成本（元/件）213装配成本（元/件）322产品售价（元/件）2318163.5线性规划模型的应用解：（1）决策变量此问题的难度是由于产品甲和乙的铸件既可以外包协作，也可以自行生产，从而使问题复杂化。如果只设甲、乙、丙产品的产量分别为x1、x2、x3，则由于产品甲和乙的铸件来源不同造成单位利润不同，因此目标函数中x1和x2的系数不是常数，目标函数成为非线性函数，但是如果把它们区分开来，另设两个变量，则可以较容易地建立问题的线性规划模型。设x1、x2、x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数；x4、x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。3.5线性规划模型的应用（2）目标函数本问题的目标是使得公司获得的总利润最大。为了建立目标函数，首先计算各决策变量的单位利润：单位利润＝售价-成本（铸造、机加工、装配）3.5线性规划模型的应用（3）约束条件（3个资源约束、非负约束） ①铸造工时限制 ②机加工工时限制 ③装配工时限制 ④非负3.5线性规划模型的应用数学模型（线性规划模型）3.5线性规划模型的应用电子表格模型3.5线性规划模型的应用例3.7某公司根据订单进行生产。已知半年内对某产品的需求量、单位生产费用和单位存储费用,还已知公司每月的生产能力为100，每月仓库容量为50。问：如何确定产品未