线性规划的建模与应用.ppt

《线性规划的建模与应用.ppt》由会员分享，可在线阅读，更多相关《线性规划的建模与应用.ppt（78页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院实用运筹学实用运筹学运用运用ExcelExcel建模和求解建模和求解第第3 3章章线性规划的建模与应用线性规划的建模与应用第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院本章内容要点本章内容要点线性规划问题的四种主要类型线性规划问题的四种主要类型线性规划的建模与应用线性规划的建模与应用第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院本章节内容本章节内容3.1 3.1 资源分配问题资源分配

2、问题3.2 3.2 成本收益平衡问题成本收益平衡问题3.3 3.3 网络配送问题网络配送问题3.4 3.4 混合问题混合问题3.5 3.5 线性规划模型的应用线性规划模型的应用第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院本章主要内容框架图本章主要内容框架图第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.1 3.1 资源分配问题资源分配问题资资源源分分配配问问题题是是将将有有限限的的资资源源分分配配到到各各种种活活动动（决决策策）中中去去的的线线性性规规划划问问题题。这这一一类类问

3、问题题的的共共性性是是在在线线性性规规划划模模型型中中每每一一个个函函数数约约束束均均为为资资源源约约束束,并并且且每每一一种种资资源源都可以表现为如下的形式：都可以表现为如下的形式：使用的资源数量使用的资源数量 可用的资源数量可用的资源数量对任何资源分配问题，对任何资源分配问题，有三种数据必须收集有三种数据必须收集：（1 1）每种资源的）每种资源的可供量可供量；（2 2）每每一一种种活活动动所所需需要要的的各各种种资资源源的的数数量量,对对于于每每一一种种资资源源与与活活动动的的组组合合,单单位位活活动动所所消消耗耗的的资资源源量量必必须须首首先先估估计计出来；出来；（3 3）每每一一种种活

4、活动动对对总总的的绩绩效效测测度度（如如总总利利润润）的的单单位位贡贡献献（如单位利润）。（如单位利润）。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.1 3.1 资源分配问题资源分配问题例例3.13.1 某某公公司司是是商商务务房房地地产产开开发发项项目目的的主主要要投投资资商商。目目前前，该公司有机会在三个建设项目中投资：该公司有机会在三个建设项目中投资：项目项目1 1：建造高层办公楼；：建造高层办公楼；项目项目2 2：建造宾馆；：建造宾馆；项目项目3 3：建造购物中心。：建造购物中心。每每个个项项目目都都要要求求投投资资者者在在

5、四四个个不不同同的的时时期期投投资资：在在当当前前预预付付定定金金，以以及及一一年年、二二年年、三三年年后后分分别别追追加加投投资资。表表3 31 1显显示示了了四四个个时时期期每每个个项项目目所所需需资资金金（百百万万元元）。投投资资者者可可以以按按一定的比例进行投资和获得相应比例的收益。一定的比例进行投资和获得相应比例的收益。年份年份办公楼项目办公楼项目宾馆项目宾馆项目购物中心项目购物中心项目0 0（现在）（现在）4040808090901 16060808050502 29090808020203 3101070706060净现值净现值454570705050公司公司目前有目前有2500

6、2500万万元资金可供投元资金可供投资，预计资，预计一年后一年后，又可获得又可获得20002000万万元元，两年后两年后获得获得另外的另外的20002000万元万元，三年后还有三年后还有15001500万元万元以供投资。以供投资。那么，该公司要那么，该公司要在每个项目中在每个项目中投投资多少比例资多少比例，才，才能使其投资组合能使其投资组合获得最大的总净获得最大的总净现值？现值？第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.1 3.1 资源分配问题资源分配问题解：解：这是一个资源分配问题。这是一个资源分配问题。(1)(1)决策变量决策

7、变量 设设：x1，x2，x3分分别别为为在在办办公公楼楼项项目目、宾宾馆馆项项目目、购购物物中中心心项项目目中中的的投投资资比比例例(2)(2)目标函数目标函数 本问题的目标是总净现值最大。本问题的目标是总净现值最大。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.1 3.1 资源分配问题资源分配问题(3)(3)约束条件约束条件 本本题题的的约约束束条条件件是是公公司司在在各各期期可可获获得得的的资资金金限限制制（资资源源约约束束）。但但要要注注意意的的是是：前前一一期期尚尚未未使使用用的的资资金金，可可以以在在下下一一期期使使用用（为

8、为了了简简化化问问题题，不不考考虑虑资资金金可可获获得得的的利利息息）。因因此此，每每一一时时点点的的资资金金限限制制就就表表现现为为累累计计的的资资金金。表表3 32 2显显示示了了累累计的资金数据。计的资金数据。年份年份办公楼项目办公楼项目宾馆项目宾馆项目购物中心项目购物中心项目可用资金可用资金0 0（现在）（现在）40408080909025251 110010016016014014045452 219019024024016016065653 32002003103102202208080净现值净现值454570705050第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学

9、城市学院浙江大学城市学院 计算分院计算分院3.1 3.1 资源分配问题资源分配问题数学模型（线性规划模型）数学模型（线性规划模型）第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.1 3.1 资源分配问题资源分配问题电子表格模型电子表格模型第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.2 3.2 成本收益平衡问题成本收益平衡问题u成成本本收收益益平平衡衡问问题题与与资资源源分分配配问问题题的的形形式式完完全全不不同同，这这种差异主要是因为两种问题的种差异主要是因为两种问题的管理目

10、标不同管理目标不同而造成的。而造成的。u在在资资源源分分配配问问题题中中，各各种种资资源源是是受受限限制制的的因因素素（包包括括财财务务资资源源），问问题题的的目目标标是是最最有有效效地地利利用用各各种种资资源源，使使获获利利最大最大。u而而对对于于成成本本收收益益平平衡衡问问题题，管管理理层层采采取取更更为为主主动动的的姿姿态态，他他们们指指明明哪哪些些收收益益必必须须实实现现（不不管管如如何何使使用用资资源源），并并且且要要以以最最低低的的成成本本实实现现所所指指明明的的收收益益。这这样样，通通过过指指明明每每种种收收益益的的最最低低可可接接受受水水平平，以以及及实实现现这这些些收收益益的

11、的最最小小成成本本，管管理理层层期期望望获获得得成成本本和和收收益益之之间间的的适适度度平平衡衡。因因此此，成成本本收收益益平平衡衡问问题题是是一一类类线线性性规规划划问问题题，这这类类问问题题中中，通通过过选选择择各各种种活活动动水水平平的的组组合合，从从而而以以最最小小的的成成本本来来实实现现最最低低可可接受的各种收益水平接受的各种收益水平。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.2 3.2 成本收益平衡问题成本收益平衡问题u成成本本收收益益平平衡衡问问题题的的共共性性是是，所所有有的的函函数数约约束束均均为收益约束，并具有

12、如下的形式：为收益约束，并具有如下的形式：完成的水平完成的水平 最低可接受的水平最低可接受的水平 如如果果将将收收益益的的含含义义扩扩大大，所所有有以以“”表表示示的的函函数数约约束束均均为为收收益益约约束束。在在多多数数情情况况下下，最最低低可可接接受受的的水水平平是是作作为为一一项项政政策策由由管管理理层层制制定定的的，但但有有时这一数据也可能是由其他条件决定。时这一数据也可能是由其他条件决定。u成本收益平衡问题需要的成本收益平衡问题需要的三种数据三种数据：（1 1）每种收益的）每种收益的最低可接受水平最低可接受水平（管理决策）；（管理决策）；（2 2）每每一一种种活活动动对对每每一一种种

13、收收益益的的贡贡献献（单单位位活活动动的的贡献贡献）；）；（3 3）每种活动的）每种活动的单位成本单位成本。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.2 3.2 成本收益平衡问题成本收益平衡问题u排排班班问问题题是是成成本本收收益益平平衡衡问问题题研研究究的的最最重重要要的的应应用用领领域域之之一一。在在这这一一领领域域中中，管管理理层层意意识识到到在在向向顾顾客客提提供供令令人人满满意意的的服服务务水水平平的的同同时时必必须须进进行行成成本本控控制制，因因此此，必必须须寻寻找找成成本本和和收收益益之之间间的的平平衡衡。于于是是，

14、研研究究如如何何规规划划每每个个轮轮班班人人员员才才能能以以最最小小的的成成本本提提供供令令人人满满意的服务。意的服务。u例例3.23.2 某某航航空空公公司司正正准准备备增增加加其其中中心心机机场场的的往往来来航航班班，因因此此需需要要雇雇佣佣更更多多的的服服务务人人员员。不不同同时时段段有有最最少少需需要要服服务务人人员员数数，有有5 5种种排排班方式，每班方式，每8 8小时为一班。小时为一班。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.2 3.2 成本收益平衡问题成本收益平衡问题例例3.23.2（续）（续）5 5种排班方式种排

15、班方式排班排班1 1：6AM6AM2PM2PM，即早上，即早上6 6点上班；点上班；排班排班2 2：8AM8AM4PM4PM，即早上，即早上8 8点上班；点上班；排班排班3 3：中午：中午8PM8PM，即中午，即中午1212点上班；排班点上班；排班4 4：4PM4PM午夜，即下午午夜，即下午4 4点上班；点上班；排班排班5 5：10PM10PM6M6M，即晚上，即晚上1010点上班。点上班。时段时段排班排班1 1排班排班2 2排班排班3 3排班排班4 4排班排班5 5最少需要人数最少需要人数6AM6AM8AM8AM48488AM8AM10AM10AM797910AM10AM中午中午6565中午

16、中午2PM2PM87872PM2PM4PM4PM64644PM4PM6PM6PM73736PM6PM8PM8PM82828PM8PM10PM10PM434310PM10PM午夜午夜5252午夜午夜6PM6PM1515每人每天工资每人每天工资(元元)170170160160175175180180195195第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.2 3.2 成本收益平衡问题成本收益平衡问题解解:这是一个纯成本收益平衡问题这是一个纯成本收益平衡问题。（1 1）决策变量）决策变量 本问题的决策是不同排班的人数。本问题的决策是不同排班

17、的人数。设：设：xi为排班为排班i的人数的人数(i1,2,1,2,5),5)（2 2）目标函数）目标函数 本问题的目标是人员总费用（工资）最本问题的目标是人员总费用（工资）最少，即少，即第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.2 3.2 成本收益平衡问题成本收益平衡问题（3 3）约束条件）约束条件 每个时段的在岗人数必须不少于最每个时段的在岗人数必须不少于最低可接受水平（最少需要人数）低可接受水平（最少需要人数）非负非负第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.2

18、3.2 成本收益平衡问题成本收益平衡问题数学模型（线性规划模型）数学模型（线性规划模型）第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.2 3.2 成本收益平衡问题成本收益平衡问题电子表格模型电子表格模型第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.3 3.3 网络配送问题网络配送问题u通过配送网络能以最小的成本完成货物的配通过配送网络能以最小的成本完成货物的配送送，所以称之为网络配送问题。网络配送问，所以称之为网络配送问题。网络配送问题将在第题将在第4 4、5 5章中重点介绍

19、。章中重点介绍。u与确定资源和收益一样，在网络配送问题中，与确定资源和收益一样，在网络配送问题中，必须确定需求以及相应地确定需求的约束条必须确定需求以及相应地确定需求的约束条件。件。u确定需求约束确定需求约束的形式如下：的形式如下：提供的数量需求的数量提供的数量需求的数量第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.3 3.3 网络配送问题网络配送问题u例例3.33.3 某公司网络配送问题。某公司在两个工厂生产某种某公司网络配送问题。某公司在两个工厂生产某种产品。现在收到三个顾客的下个月定单要购买这种产品。这产品。现在收到三个顾客的下

20、个月定单要购买这种产品。这些产品会被单独运送，表些产品会被单独运送，表 3434显示了从每个工厂到每个顾客显示了从每个工厂到每个顾客的运送一个产品的成本。该表同样表明了每个顾客的订货量的运送一个产品的成本。该表同样表明了每个顾客的订货量和每个工厂的生产量。现在公司的物流经理要决定从每个工和每个工厂的生产量。现在公司的物流经理要决定从每个工厂运送多少个产品到每个顾客那里才能使总成本最小？厂运送多少个产品到每个顾客那里才能使总成本最小？单位运输成本（元单位运输成本（元/个）个）产量（个）产量（个）顾客顾客1 1顾客顾客2 2顾客顾客3 3工厂工厂1 17007009009008008001212工

21、厂工厂2 28008009009007007001515订货量订货量(个个)10108 89 927(27(产销平衡产销平衡)第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.3 3.3 网络配送问题网络配送问题解解:由于由于“总产量（总产量（2727）总订货量（）总订货量（2727）”，所以本，所以本问题是一个问题是一个平衡运输问题平衡运输问题。（1 1）决策变量）决策变量 本问题的决策为从每个工厂运送多少个产品到每本问题的决策为从每个工厂运送多少个产品到每个顾客那里。设：个顾客那里。设：xi-j为从工厂为从工厂i运输到顾客运输到顾客j

22、的产品数的产品数量（量（iF1,F2;j=C1,C2,C3)（2 2）目标函数）目标函数 本问题的目标是使得公司总运输成本最低。本问题的目标是使得公司总运输成本最低。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.3 3.3 网络配送问题网络配送问题（3 3）约束条件）约束条件 从工厂运送出去的产品数量等于其产量从工厂运送出去的产品数量等于其产量 顾客收到的产品数量等于其订货量顾客收到的产品数量等于其订货量 非负非负第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.3 3.3 网络

23、配送问题网络配送问题数学模型（线性规划模型）数学模型（线性规划模型）第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.3 3.3 网络配送问题网络配送问题电子表格模型电子表格模型第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.4 3.4 混合问题混合问题u前面讨论了线性规划问题的三种类型：资源前面讨论了线性规划问题的三种类型：资源分配问题、成本收益平衡问题以及网络配送分配问题、成本收益平衡问题以及网络配送问题。如表问题。如表3535所总结的，每一类问题都是所总结的，每一类问题都是以

24、一类约束条件为特色的。以一类约束条件为特色的。u实际上，实际上，纯资源分配问题纯资源分配问题的共性是它所有的的共性是它所有的函数约束均为函数约束均为资源约束资源约束u而而成本收益平衡问题成本收益平衡问题的共性是它所有的函数的共性是它所有的函数约束均为约束均为收益约束收益约束u网络配送问题网络配送问题中，主要的函数约束为一特定中，主要的函数约束为一特定类型的类型的确定需求约束确定需求约束。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.4 3.4 混合问题混合问题u但许多线性规划问题并不能直接归入三类中但许多线性规划问题并不能直接归入三类

25、中的某一类，一些问题勉强可以归入一类，因的某一类，一些问题勉强可以归入一类，因其主要的函数约束与表其主要的函数约束与表3535的相应函数约束的相应函数约束大致相同。另一些问题却没有一类占主导地大致相同。另一些问题却没有一类占主导地位的函数约束，不能归入前三类中的某一类。位的函数约束，不能归入前三类中的某一类。因此，混合问题是第四类线性规划问题，这因此，混合问题是第四类线性规划问题，这一类型将包括所有未归入前述三类中的线性一类型将包括所有未归入前述三类中的线性规划问题。规划问题。u一些混合问题仅包含两类函数约束，而更多一些混合问题仅包含两类函数约束，而更多的是包含三类函数约束。的是包含三类函数约

26、束。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.4 3.4 混合问题混合问题u表表 35 35 各类函数约束各类函数约束类型类型形式形式*解释解释主要用于主要用于资源约束资源约束LHS LHS RHS RHS对于特定的资源对于特定的资源使用的数量使用的数量 可获得的数量可获得的数量资源分配问题资源分配问题混合问题混合问题收益约束收益约束LHS LHS RHS RHS对于特定的收益对于特定的收益到达的水平到达的水平 最低可接受水平最低可接受水平成本收益平衡成本收益平衡问题问题混合问题混合问题确定需求确定需求约束约束LHS=RHSLHS

27、=RHS对于一些数量对于一些数量提供的数量提供的数量=需求的数量需求的数量网络配送问题网络配送问题混合问题混合问题*LHS=左式（一个左式（一个SUMPRODUCT函数）函数）RHS=右式（一般为常数）右式（一般为常数）第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.4 3.4 混合问题混合问题u配料问题配料问题。这类问题的一般提法是：由多种。这类问题的一般提法是：由多种原料制成含有原料制成含有m m种成分的产品，已知产品中所含种成分的产品，已知产品中所含各种成分的比例要求、各种原料的单位价格以各种成分的比例要求、各种原料的单位价格以及

28、各原料所含成分的数量。考虑的问题是：应及各原料所含成分的数量。考虑的问题是：应如何配料，可使产品的总成本最低。如何配料，可使产品的总成本最低。u例例3.4 3.4 配料问题配料问题。某公司计划要用、。某公司计划要用、C C三种原料混合调制出三种不同规格的产品甲、三种原料混合调制出三种不同规格的产品甲、乙、丙，产品的规格要求和单价、原料的供应乙、丙，产品的规格要求和单价、原料的供应量和单价等数据如表量和单价等数据如表 3636所示。问：该公司应所示。问：该公司应如何安排生产，可使总利润收入最大？如何安排生产，可使总利润收入最大？第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院

29、浙江大学城市学院 计算分院计算分院3.4 3.4 混合问题混合问题u表表 36 36 混合配料数据表混合配料数据表A AB BC C产品单价产品单价（元（元/千克）千克）甲甲 50%50%35%35%不限不限9090乙乙 40%40%45%45%不限不限8585丙丙30%30%50%50%20%20%6565原料供应量原料供应量（千克）（千克）200200150150100100原料单价原料单价（元（元/千克）千克）606035353030第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.4 3.4 混合问题混合问题解：解：（1 1）决策

30、变量决策变量 本问题的难点在于给出的数据是非确定数值，而本问题的难点在于给出的数据是非确定数值，而且各产品与原料的关系较为复杂。为了方便，设且各产品与原料的关系较为复杂。为了方便，设xij表表示原料示原料i（i=A=A，B B，C C）用于产品）用于产品j（j=1=1为甲，为甲，j=2=2为乙，为乙，j=3=3为丙）的数量。为丙）的数量。（2 2）目标函数）目标函数本问题的目标是使利润最大，本问题的目标是使利润最大，利润产品收入原料支出利润产品收入原料支出第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.4 3.4 混合问题混合问题（3

31、3）约束条件）约束条件 本题的约束条件：原料供应量限制本题的约束条件：原料供应量限制3 3个、规格要求个、规格要求7 7个个和决策变量非负。和决策变量非负。在例在例3.43.4中，有中，有9 9个决策变量和个决策变量和1010个函数约束条件，个函数约束条件，包括包括5 5个资源约束、个资源约束、2 2个收益约束和个收益约束和3 3个确定需求约束。个确定需求约束。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.4 3.4 混合问题混合问题电子表格模型电子表格模型第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城

32、市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用u前面前面按照函数约束按照函数约束的分类，介绍了四种线性的分类，介绍了四种线性规划问题：资源分配问题（规划问题：资源分配问题（,资源约束）、资源约束）、成本收益平衡问题（成本收益平衡问题（，收益约束）、网络配，收益约束）、网络配送问题（送问题（=，确定需求约束）和混合问题（包，确定需求约束）和混合问题（包含两种或三种类型的约束函数）。含两种或三种类型的约束函数）。u本节本节按照应用按照应用方面介绍线性规划在方面介绍线性规划在生产计划生产计划问题问题、资金管理问题资金管理问题、市场调查问题市场调查问题和和混合混合配料问题

33、配料问题等方面的应用等方面的应用第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用u建立线性规划模型的过程可以分为四个步骤：建立线性规划模型的过程可以分为四个步骤：(1)(1)设立设立决策变量决策变量；(2)(2)用决策变量的线性函数表示用决策变量的线性函数表示目标目标，并确定，并确定是求最大（是求最大（MaxMax）还是最小（）还是最小（MinMin）；）；(3)(3)明确明确约束条件约束条件并用决策变量的线性等式并用决策变量的线性等式或不等式表示；或不等式表示；(4)(4)根据决策变量的

34、物理性质研究变量是否有根据决策变量的物理性质研究变量是否有非负非负性。性。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用u生产计划问题生产计划问题是企业生产过程中常是企业生产过程中常常遇到的问题，其中最简单的一种形常遇到的问题，其中最简单的一种形式可以描述如下（资源分配问题）：式可以描述如下（资源分配问题）：用若干种用若干种原材料原材料（资源）（资源）生产生产某某几种几种产品产品，原材料（或某种资源），原材料（或某种资源）供供应量应量有一定的限制，要求制定一个产有一定的限制，要求制定一个

35、产品品生产计划生产计划，使其在给定的资源限制，使其在给定的资源限制条件下能得到条件下能得到最大收益最大收益。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用u例例3.53.5 某工厂生产甲、乙、丙三种产某工厂生产甲、乙、丙三种产品，都要经过铸造、机加工和装配三个品，都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包车间。甲、乙两种产品的铸件可以外包协作，也可以自行生产，但产品丙必须协作，也可以自行生产，但产品丙必须本厂铸造才能保证质量。有关情况的数本厂铸造才能保证质量。有关情

36、况的数据如表据如表3939所示。问：公司为了获得最所示。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸件由本公司少件？甲、乙两种产品的铸件由本公司铸造和由外包协作各应多少件？铸造和由外包协作各应多少件？第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用u表表 39 39 自行生产或外包的有关数据自行生产或外包的有关数据产品甲产品甲产品乙产品乙产品丙产品丙工时限制工时限制单件铸造工时（小时）单件铸造工时（小时）5 510107 7

37、8 0008 000单件机加工工时（小时）单件机加工工时（小时）6 64 48 812 00012 000单件装配工时（小时）单件装配工时（小时）3 32 22 210 00010 000自产铸件成本（元自产铸件成本（元/件）件）3 35 54 4外协铸件成本（元外协铸件成本（元/件）件）5 56 6机加工成本（元机加工成本（元/件）件）2 21 13 3装配成本（元装配成本（元/件）件）3 32 22 2产品售价（元产品售价（元/件）件）232318181616第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的

38、应用线性规划模型的应用解：解：（1 1）决策变量）决策变量 此问题的难度是由于产品甲和乙的铸件既可以外包协作，此问题的难度是由于产品甲和乙的铸件既可以外包协作，也可以自行生产，从而使问题复杂化。如果只设甲、乙、丙产品也可以自行生产，从而使问题复杂化。如果只设甲、乙、丙产品的产量分别为的产量分别为x1、x2、x3，则由于产品甲和乙的铸件来源不同造，则由于产品甲和乙的铸件来源不同造成单位利润不同，因此目标函数中成单位利润不同，因此目标函数中x1和和x2的系数不是常数，目标的系数不是常数，目标函数成为非线性函数，但是如果把它们区分开来，另设两个变量函数成为非线性函数，但是如果把它们区分开来，另设两个

39、变量（采用第（采用第7 7章的可分离规划技术），则可以较容易地建立问题的章的可分离规划技术），则可以较容易地建立问题的线性规划模型。线性规划模型。设设x1、x2、x3分别为分别为三道工序都由本公司加工三道工序都由本公司加工的甲、乙、丙的甲、乙、丙三种产品的件数；三种产品的件数；x4、x5分别分别为由外协铸造为由外协铸造再由本公司机加工再由本公司机加工和装配的甲、乙两种产品的件数。和装配的甲、乙两种产品的件数。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用（2 2）目标函数）目标函数 本问

40、题的目标是使得公司获得的利润最大。本问题的目标是使得公司获得的利润最大。为了建立目标函数，首先计算各决策变量的为了建立目标函数，首先计算各决策变量的单位利润：单位利润：单位利润售价单位利润售价-成本（铸造、机加工、装配）成本（铸造、机加工、装配）第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用（3 3）约束条件）约束条件（3 3个资源约束、非负约束）个资源约束、非负约束）铸造工时限制铸造工时限制 机加工工时限制机加工工时限制 装配工时限制装配工时限制 非负非负 第第3章章 线性规划线性规划

41、的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用数学模型（线性规划模型）数学模型（线性规划模型）第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用电子表格模型电子表格模型第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用例例3.63.6 某工厂生产某工厂生产A A、B B两种产品，均需经过两道工序，每生产两种产品

42、，均需经过两道工序，每生产1 1吨吨A A产品需要经第一道工序加工产品需要经第一道工序加工2 2小时，第二道工序加工小时，第二道工序加工3 3小时；小时；每生产每生产1 1吨吨B B产品需经过第一道工序加工产品需经过第一道工序加工3 3小时，第二道工序加工小时，第二道工序加工4 4小时。可供利用的第一道工序工时为小时。可供利用的第一道工序工时为1515小时，第二道工序工时小时，第二道工序工时为为2525小时。小时。生产产品生产产品B B的同时可产出的同时可产出副产品副产品C C，每生产，每生产1 1吨产品吨产品B B，可同时得，可同时得到到2 2吨产品吨产品C C而不需要外加任何费用。副产品而

43、不需要外加任何费用。副产品C C一部分可以盈利，一部分可以盈利，但剩下的只能报废，报废需要有一定的费用。但剩下的只能报废，报废需要有一定的费用。各项费用的情况为：出售产品各项费用的情况为：出售产品A A每吨能盈利每吨能盈利400400元；出售产品元；出售产品B B每每吨能盈利吨能盈利800800元；每销售元；每销售1 1吨副产品吨副产品C C能盈利能盈利300300元；当剩余的产元；当剩余的产品品C C报废时，每吨损失费为报废时，每吨损失费为200200元。元。经市场预测，在计划期内产品经市场预测，在计划期内产品C C的最大销量为的最大销量为5 5吨。吨。问：如何安排问：如何安排A A、B B

44、两种产品的产量可使工厂总的盈利为最大？两种产品的产量可使工厂总的盈利为最大？第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用解：解：（1 1）决策变量）决策变量 本问题的难度是由于副产品本问题的难度是由于副产品C C的出现而使问题复的出现而使问题复杂化了。如果只设杂化了。如果只设A A、B B、C C产品的产量分别为产品的产量分别为x1、x2、x3 ，则由于产品，则由于产品C C的单位利润不同（赢利的单位利润不同（赢利300300元或损失元或损失200200元），因此目标函数中元），因此目

45、标函数中x3的系数不是常数，目标函数的系数不是常数，目标函数成为非线性函数，但是如果把产品成为非线性函数，但是如果把产品C C的销售量和报废量的销售量和报废量区分开来，设作两个变量（采用第区分开来，设作两个变量（采用第7 7章的可分离规划技章的可分离规划技术），则可以容易地建立线性规划模型。术），则可以容易地建立线性规划模型。设设A A、B B产品的产量分别为产品的产量分别为x1、x2；C C产品的销售量和报产品的销售量和报废量分别为废量分别为x3、x4。第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性

46、规划模型的应用（2 2）目标函数）目标函数 本问题的目标是使工厂的总盈利最大，即本问题的目标是使工厂的总盈利最大，即 （3 3）约束条件）约束条件 （3 3个资源约束、个资源约束、1 1个确定需求约束、非负约束）个确定需求约束、非负约束）第一道工序第一道工序 第二道工序第二道工序 产品产品B B与产品与产品C C 产品产品C C的最大销量的最大销量 非负非负 第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用线性规划模型（数学模型）线性规划模型（数学模型）第第3章章 线性规划线性规划的建模与

47、应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用电子表格模型电子表格模型第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用例例3.73.7 某公司根据订单进行生产。已知半年内某公司根据订单进行生产。已知半年内对某产品的需求量、单位生产费用和单位存储对某产品的需求量、单位生产费用和单位存储费用费用,还已知公司每月的生产能力为还已知公司每月的生产能力为100100，每月，每月仓库容量为仓库容量为5050。问：如何确定产品未来半

48、年内。问：如何确定产品未来半年内每月最佳生产量和存储量，以使总费用最少。每月最佳生产量和存储量，以使总费用最少。月份月份1 12 23 34 45 56 6需求量需求量505040405050454555553030单位生产费用单位生产费用825825775775850850850850775775825825单位存储费用单位存储费用404030303535202040404040第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用解：解：（生产与库存问题，更多请参见第（生产与库存问题，更多请

49、参见第9 9章，动态规划）章，动态规划）(1)(1)决策变量决策变量 本问题的决策为产品未来半年内每月的最佳生本问题的决策为产品未来半年内每月的最佳生产量和库存量。设每月生产量为产量和库存量。设每月生产量为xi(i=1,2,=1,2,6,6)，每月月末库存量为每月月末库存量为si(i=1,2,(i=1,2,6,6)。(2)(2)目标函数目标函数 本问题的目标是总费用最小，而总费用生产本问题的目标是总费用最小，而总费用生产总费用总费用+存储总费用，即存储总费用，即第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应

50、用线性规划模型的应用(3)(3)约束条件约束条件 对于每个月对于每个月上月库存量本月生产量市场需求本月月末库存量上月库存量本月生产量市场需求本月月末库存量 公司每月的生产能力为公司每月的生产能力为100100 每月仓库容量为每月仓库容量为5050 非负非负第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规划模型的应用数学模型（线性规划模型）数学模型（线性规划模型）第第3章章 线性规划线性规划的建模与应用的建模与应用浙江大学城市学院浙江大学城市学院 计算分院计算分院3.5 3.5 线性规划模型的应用线性规