线性规划的建模与应用

线性规划的建模与应用第1页，课件共78页，创作于2023年2月本章内容要点线性规划问题的四种主要类型线性规划的建模与应用第2页，课件共78页，创作于2023年2月本章节内容3.1资源分配问题3.2成本收益平衡问题3.3网络配送问题3.4混合问题3.5线性规划模型的应用第3页，课件共78页，创作于2023年2月本章主要内容框架图第4页，课件共78页，创作于2023年2月3.1资源分配问题资源分配问题是将有限的资源分配到各种活动（决策）中去的线性规划问题。这一类问题的共性是在线性规划模型中每一个函数约束均为资源约束,并且每一种资源都可以表现为如下的形式：使用的资源数量可用的资源数量对任何资源分配问题，有三种数据必须收集：（1）每种资源的可供量；（2）每一种活动所需要的各种资源的数量,对于每一种资源与活动的组合,单位活动所消耗的资源量必须首先估计出来；（3）每一种活动对总的绩效测度（如总利润）的单位贡献（如单位利润）。第5页，课件共78页，创作于2023年2月3.1资源分配问题例3.1

某公司是商务房地产开发项目的主要投资商。目前，该公司有机会在三个建设项目中投资： 项目1：建造高层办公楼； 项目2：建造宾馆； 项目3：建造购物中心。每个项目都要求投资者在四个不同的时期投资：在当前预付定金，以及一年、二年、三年后分别追加投资。表3－1显示了四个时期每个项目所需资金（百万元）。投资者可以按一定的比例进行投资和获得相应比例的收益。年份办公楼项目宾馆项目购物中心项目0（现在）408090160805029080203107060净现值457050公司目前有2500万元资金可供投资，预计一年后，又可获得2000万元，两年后获得另外的2000万元，三年后还有1500万元以供投资。那么，该公司要在每个项目中投资多少比例，才能使其投资组合获得最大的总净现值？第6页，课件共78页，创作于2023年2月3.1资源分配问题解：这是一个资源分配问题。(1)决策变量设：x1，x2，x3分别为在办公楼项目、宾馆项目、购物中心项目中的投资比例(2)目标函数本问题的目标是总净现值最大。第7页，课件共78页，创作于2023年2月3.1资源分配问题(3)约束条件本题的约束条件是公司在各期可获得的资金限制（资源约束）。但要注意的是：前一期尚未使用的资金，可以在下一期使用（为了简化问题，不考虑资金可获得的利息）。因此，每一时点的资金限制就表现为累计的资金。表3－2显示了累计的资金数据。年份办公楼项目宾馆项目购物中心项目可用资金0（现在）40809025110016014045219024016065320031022080净现值457050第8页，课件共78页，创作于2023年2月3.1资源分配问题数学模型（线性规划模型）第9页，课件共78页，创作于2023年2月3.1资源分配问题电子表格模型第10页，课件共78页，创作于2023年2月3.2成本收益平衡问题成本收益平衡问题与资源分配问题的形式完全不同，这种差异主要是因为两种问题的管理目标不同而造成的。在资源分配问题中，各种资源是受限制的因素（包括财务资源），问题的目标是最有效地利用各种资源，使获利最大。而对于成本收益平衡问题，管理层采取更为主动的姿态，他们指明哪些收益必须实现（不管如何使用资源），并且要以最低的成本实现所指明的收益。这样，通过指明每种收益的最低可接受水平，以及实现这些收益的最小成本，管理层期望获得成本和收益之间的适度平衡。因此，成本收益平衡问题是一类线性规划问题，这类问题中，通过选择各种活动水平的组合，从而以最小的成本来实现最低可接受的各种收益水平。第11页，课件共78页，创作于2023年2月3.2成本收益平衡问题成本收益平衡问题的共性是，所有的函数约束均为收益约束，并具有如下的形式：

完成的水平最低可接受的水平如果将收益的含义扩大，所有以“”表示的函数约束均为收益约束。在多数情况下，最低可接受的水平是作为一项政策由管理层制定的，但有时这一数据也可能是由其他条件决定。成本收益平衡问题需要的三种数据：（1）每种收益的最低可接受水平（管理决策）；（2）每一种活动对每一种收益的贡献（单位活动的贡献）；（3）每种活动的单位成本。第12页，课件共78页，创作于2023年2月3.2成本收益平衡问题排班问题是成本收益平衡问题研究的最重要的应用领域之一。在这一领域中，管理层意识到在向顾客提供令人满意的服务水平的同时必须进行成本控制，因此，必须寻找成本和收益之间的平衡。于是，研究如何规划每个轮班人员才能以最小的成本提供令人满意的服务。例3.2

某航空公司正准备增加其中心机场的往来航班，因此需要雇佣更多的服务人员。不同时段有最少需要服务人员数，有5种排班方式，每8小时为一班。第13页，课件共78页，创作于2023年2月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每人每天工资(元)170160175180195第14页，课件共78页，创作于2023年2月3.2成本收益平衡问题解:这是一个纯成本收益平衡问题。（1）决策变量本问题的决策是不同排班的人数。设：xi为排班i的人数(i＝1,2,,5)（2）目标函数本问题的目标是人员总费用（工资）最少，即第15页，课件共78页，创作于2023年2月3.2成本收益平衡问题（3）约束条件

①每个时段的在岗人数必须不少于最低可接受水平（最少需要人数）②非负第16页，课件共78页，创作于2023年2月3.2成本收益平衡问题数学模型（线性规划模型）第17页，课件共78页，创作于2023年2月3.2成本收益平衡问题电子表格模型第18页，课件共78页，创作于2023年2月3.3网络配送问题通过配送网络能以最小的成本完成货物的配送，所以称之为网络配送问题。网络配送问题将在第4、5章中重点介绍。与确定资源和收益一样，在网络配送问题中，必须确定需求以及相应地确定需求的约束条件。确定需求约束的形式如下：提供的数量＝需求的数量第19页，课件共78页，创作于2023年2月3.3网络配送问题例3.3

某公司网络配送问题。某公司在两个工厂生产某种产品。现在收到三个顾客的下个月定单要购买这种产品。这些产品会被单独运送，表3—4显示了从每个工厂到每个顾客的运送一个产品的成本。该表同样表明了每个顾客的订货量和每个工厂的生产量。现在公司的物流经理要决定从每个工厂运送多少个产品到每个顾客那里才能使总成本最小？

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

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

最低可接受水平成本收益平衡问题混合问题确定需求约束LHS=RHS对于一些数量提供的数量=需求的数量网络配送问题混合问题*LHS=左式（一个SUMPRODUCT函数）RHS=右式（一般为常数）第27页，课件共78页，创作于2023年2月3.4混合问题配料问题。这类问题的一般提法是：由多种原料制成含有m种成分的产品，已知产品中所含各种成分的比例要求、各种原料的单位价格以及各原料所含成分的数量。考虑的问题是：应如何配料，可使产品的总成本最低。例3.4配料问题。某公司计划要用Ａ、Ｂ、C三种原料混合调制出三种不同规格的产品甲、乙、丙，产品的规格要求和单价、原料的供应量和单价等数据如表3—6所示。问：该公司应如何安排生产，可使总利润收入最大？第28页，课件共78页，创作于2023年2月3.4混合问题表3—6混合配料数据表ABC产品单价（元/千克）甲50%35%不限90乙40%45%不限85丙30%50%20%65原料供应量（千克）200150100原料单价（元/千克）603530第29页，课件共78页，创作于2023年2月3.4混合问题解：（1）决策变量本问题的难点在于给出的数据是非确定数值，而且各产品与原料的关系较为复杂。为了方便，设xij表示原料i（i=A，B，C）用于产品j（j=1为甲，j=2为乙，j=3为丙）的数量。（2）目标函数 本问题的目标是使利润最大，利润＝产品收入－原料支出第30页，课件共78页，创作于2023年2月3.4混合问题（3）约束条件本题的约束条件：原料供应量限制3个、规格要求7个和决策变量非负。在例3.4中，有9个决策变量和10个函数约束条件，包括5个资源约束、2个收益约束和3个确定需求约束。第31页，课件共78页，创作于2023年2月3.4混合问题电子表格模型第32页，课件共78页，创作于2023年2月3.5线性规划模型的应用前面按照函数约束的分类，介绍了四种线性规划问题：资源分配问题（,资源约束）、成本收益平衡问题（，收益约束）、网络配送问题（=，确定需求约束）和混合问题（包含两种或三种类型的约束函数）。本节按照应用方面介绍线性规划在生产计划问题、资金管理问题、市场调查问题和混合配料问题等方面的应用第33页，课件共78页，创作于2023年2月3.5线性规划模型的应用建立线性规划模型的过程可以分为四个步骤：

(1)设立决策变量；

(2)用决策变量的线性函数表示目标，并确定是求最大（Max）还是最小（Min）；

(3)明确约束条件并用决策变量的线性等式或不等式表示；

(4)根据决策变量的物理性质研究变量是否有非负性。第34页，课件共78页，创作于2023年2月3.5线性规划模型的应用生产计划问题是企业生产过程中常常遇到的问题，其中最简单的一种形式可以描述如下（资源分配问题）：用若干种原材料（资源）生产某几种产品，原材料（或某种资源）供应量有一定的限制，要求制定一个产品生产计划，使其在给定的资源限制条件下能得到最大收益。第35页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.5

某工厂生产甲、乙、丙三种产品，都要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，也可以自行生产，但产品丙必须本厂铸造才能保证质量。有关情况的数据如表3—9所示。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸件由本公司铸造和由外包协作各应多少件？第36页，课件共78页，创作于2023年2月3.5线性规划模型的应用表3—9自行生产或外包的有关数据产品甲产品乙产品丙工时限制单件铸造工时（小时）51078000单件机加工工时（小时）64812000单件装配工时（小时）32210000自产铸件成本（元/件）354外协铸件成本（元/件）56－机加工成本（元/件）213装配成本（元/件）322产品售价（元/件）231816第37页，课件共78页，创作于2023年2月3.5线性规划模型的应用解：（1）决策变量此问题的难度是由于产品甲和乙的铸件既可以外包协作，也可以自行生产，从而使问题复杂化。如果只设甲、乙、丙产品的产量分别为x1、x2、x3，则由于产品甲和乙的铸件来源不同造成单位利润不同，因此目标函数中x1和x2的系数不是常数，目标函数成为非线性函数，但是如果把它们区分开来，另设两个变量（采用第7章的可分离规划技术），则可以较容易地建立问题的线性规划模型。设x1、x2、x3分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数；x4、x5分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数。第38页，课件共78页，创作于2023年2月3.5线性规划模型的应用（2）目标函数本问题的目标是使得公司获得的利润最大。为了建立目标函数，首先计算各决策变量的单位利润：单位利润＝售价-成本（铸造、机加工、装配）第39页，课件共78页，创作于2023年2月3.5线性规划模型的应用（3）约束条件（3个资源约束、非负约束） ①铸造工时限制 ②机加工工时限制 ③装配工时限制 ④非负第40页，课件共78页，创作于2023年2月3.5线性规划模型的应用数学模型（线性规划模型）第41页，课件共78页，创作于2023年2月3.5线性规划模型的应用电子表格模型第42页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.6

某工厂生产A、B两种产品，均需经过两道工序，每生产1吨A产品需要经第一道工序加工2小时，第二道工序加工3小时；每生产1吨B产品需经过第一道工序加工3小时，第二道工序加工4小时。可供利用的第一道工序工时为15小时，第二道工序工时为25小时。生产产品B的同时可产出副产品C，每生产1吨产品B，可同时得到2吨产品C而不需要外加任何费用。副产品C一部分可以盈利，但剩下的只能报废，报废需要有一定的费用。各项费用的情况为：出售产品A每吨能盈利400元；出售产品B每吨能盈利800元；每销售1吨副产品C能盈利300元；当剩余的产品C报废时，每吨损失费为200元。经市场预测，在计划期内产品C的最大销量为5吨。问：如何安排A、B两种产品的产量可使工厂总的盈利为最大？第43页，课件共78页，创作于2023年2月3.5线性规划模型的应用解：（1）决策变量本问题的难度是由于副产品C的出现而使问题复杂化了。如果只设A、B、C产品的产量分别为x1、x2、x3

，则由于产品C的单位利润不同（赢利300元或损失200元），因此目标函数中x3的系数不是常数，目标函数成为非线性函数，但是如果把产品C的销售量和报废量区分开来，设作两个变量（采用第7章的可分离规划技术），则可以容易地建立线性规划模型。设A、B产品的产量分别为x1、x2；C产品的销售量和报废量分别为x3、x4。第44页，课件共78页，创作于2023年2月3.5线性规划模型的应用（2）目标函数本问题的目标是使工厂的总盈利最大，即

（3）约束条件（3个资源约束、1个确定需求约束、非负约束） ①第一道工序 ②第二道工序 ③产品B与产品C ④产品C的最大销量 ⑤非负 第45页，课件共78页，创作于2023年2月3.5线性规划模型的应用线性规划模型（数学模型）第46页，课件共78页，创作于2023年2月3.5线性规划模型的应用电子表格模型第47页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.7

某公司根据订单进行生产。已知半年内对某产品的需求量、单位生产费用和单位存储费用,还已知公司每月的生产能力为100，每月仓库容量为50。问：如何确定产品未来半年内每月最佳生产量和存储量，以使总费用最少。月份123456需求量504050455530单位生产费用825775850850775825单位存储费用403035204040第48页，课件共78页，创作于2023年2月3.5线性规划模型的应用解：（生产与库存问题，更多请参见第9章，动态规划）(1)决策变量本问题的决策为产品未来半年内每月的最佳生产量和库存量。设每月生产量为xi(i=1,2,,6)，每月月末库存量为si(i=1,2,,6)。(2)目标函数本问题的目标是总费用最小，而总费用＝生产总费用+存储总费用，即第49页，课件共78页，创作于2023年2月3.5线性规划模型的应用(3)约束条件①对于每个月上月库存量＋本月生产量－市场需求＝本月月末库存量②公司每月的生产能力为100③每月仓库容量为50④非负第50页，课件共78页，创作于2023年2月3.5线性规划模型的应用数学模型（线性规划模型）第51页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.7的电子表格模型第52页，课件共78页，创作于2023年2月3.5线性规划模型的应用资金管理问题线性规划在资金管理方面的应用主要包括投资组合优化、连续投资、财务计划、资本预算等。本小节将介绍线性规划在投资组合优化与连续投资方面的应用。更多的例子请见第9章。投资组合优化问题研究如何选择投资对象，例如，如何选择不同的债券或股票，在满足某些要求的前提下，使得利润最大或风险最小。因此，其决策变量是对各种可能的投资对象的投资组合，其目标函数通常是期望回报最大化或风险最小化，而约束条件则可包括总投资额、公司政策、法律法规等。例3.8是期望回报额最大化，采用线性规划模型。当考虑投资风险（成本）与收益之间的平衡时，更多的是采用非线性规划模型，具体见第7章。第53页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.8

投资组合优化问题。某公司董事会决定将20万现金进行债券投资。经咨询，现有五种债券是较好的投资对象，它们是：黄河汽车，长江汽车，华南电器，西南电器，缜山纸业。它们的投资回报率如表3—12所示。为减少风险，董事会要求，对汽车业的投资不得超过12万，对电器业的投资不得超过8万，其中对长江汽车业的投资不得超过对汽车业投资的65%，对纸业的投资不得低于对汽车业投资的20%。该公司应如何投资，才能在满足董事会要求的前提下使得总回报额最大？债券名称黄河汽车长江汽车华南电器西南电器缜山纸业回报率6.5%9.2%4.5%5.5%4.2%第54页，课件共78页，创作于2023年2月3.5线性规划模型的应用解：（1）决策变量本问题的决策变量是对五种投资对象的投资额。设：该公司对五种债券的投资额分别为x1，x2，x3，x4，x5（万元）。（2）目标函数本问题的目标是使得公司总回报额最大，即第55页，课件共78页，创作于2023年2月3.5线性规划模型的应用（3）约束条件 ①总投资额为20万现金 ②汽车业的投资不得超过12万 ③电器业的投资不得超过8万 ④对长江汽车业的投资不得超过对汽车业投资的65% ⑤对纸业的投资不得低于对汽车业投资的20% ⑥非负第56页，课件共78页，创作于2023年2月3.5线性规划模型的应用数学模型（线性规划模型）第57页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.8的电子表格模型第58页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.9

连续投资问题。某部门在今后五年内考虑给下列项目投资，已知：

项目A：从第一年到第四年每年年初都可以投资，并于次年年末收回本利115%；

项目B：第三年年初可以投资，到第五年年末能收回本利125%，但规定最大投资额不超过4万元；

项目C：第二年初可以投资，到第五年末能收回本利140%，但规定最大投资额不超过3万元；

项目D：五年内每年初都可以购买公债，于当年末归还，并加利息6%。该部门现有资金10万元，问应如何确定这些项目的每年投资额，使得第五年年末拥有的资金的本利总额最大？第59页，课件共78页，创作于2023年2月3.5线性规划模型的应用解：（1）决策变量本题是一个连续投资问题，由于需要考虑每年年初对不同项目的投资额，为了便于理解，建立双下标决策变量。设xij为第i年初给项目j的投资额（万元）根据给定条件，将决策变量列于表3—13中（P82）（2）约束条件

每年投资额＝可投资额（P82－83）最大投资额、非负第60页，课件共78页，创作于2023年2月3.5线性规划模型的应用项目A项目B项目C项目D第一年x1A——x1D第二年x2A—x2Cx2D第三年x3Ax3B—x3D第四年x4A——x4D第五年———x5D年份项目第61页，课件共78页，创作于2023年2月3.5线性规划模型的应用（3）目标函数该问题要求在第五年末拥有的资金的本利总额最大目标也可以是投资的总回报额最大但不是用Excel求解即可明白第62页，课件共78页，创作于2023年2月3.5线性规划模型的应用数学模型（线性规划模型）第63页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.9的电子表格模型第64页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.9的灵敏度分析

从影子价格（“阴影价格”列）可知：第一年初增加或减少投资1万元，将导致第五年末拥有资金的本利增加或减少1.40万元，目前第一年投资额为10万元；第二年初增加或减少投资1万元，将导致第五年末拥有资金的本利增加或减少1.32万元，目前第二年的投资金额来自第一年投资于项目D而收回的106％的本利3万元（从“终值”列得知）；同样可知第三年初、第四年初、第五年初增加或减少投资1万元，将导致第五年末拥有资金的本利分别增加或减少1.22万元、1.15万元、1.06万元。第65页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.10

某市场调查公司受某厂的委托，调查消费者对某种新产品的了解和反应情况。该厂对市场调查公司提出了以下要求：（1）共对500个家庭进行调查；（2）在被调查家庭中，至少有200个是没有孩子的家庭，同时至少有200个是有孩子的家庭；（3）至少对300个被调查家庭采用问卷式书面调查，其余家庭可采用口头调查；（4）在有孩子的被调查家庭中，至少有50％的家庭采用问卷式书面调查；（5）在没有孩子的被调查家庭中，至少有60％的家庭采用问卷式书面调查。第66页，课件共78页，创作于2023年2月3.5线性规划模型的应用对不同家庭采用不同调查方式的费用如表3—16所示。问：市场调查公司应如何进行调查，使得在满足厂方要求的条件下，使得总调查费用最少？表3—16市场调查费用表家庭类型调查费用（元）问卷式书面调查口头调查有孩子的家庭5030没有孩子的家庭4025第67页，课件共78页，创作于2023年2月3.5线性规划模型的应用解：（1）决策变量根据题意，本问题的决策变量如下：

x1：对有孩子的家庭采用问卷式书面调查的数目，

x2：对有孩子的家庭采用口头调查的数目，

x3：对没有孩子的家庭采用问卷式书面调查的数目，

x4：对没有孩子的家庭采用口头调查的数目。（2）目标函数本问题的目标是使得总调查费用最小。第68页，课件共78页，创作于2023年2月3.5线性规划模型的应用（3）约束条件 ①共对500个家庭进行调查； ②至少有200个是没有孩子的家庭； ③至少有200个是有孩子的家庭； ④至少有300个采用问卷式书面调查； ⑤有孩子的家庭中，至少50％采用问卷式书面调查； ⑥没有孩子的家庭中，至少60％采用问卷式书面调查； ⑦非负。第69页，课件共78页，创作于2023年2月3.5线性规划模型的应用数学模型（线性规划模型）第70页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.10的电子表格模型第71页，课件共78页，创作于2023年2月3.5线性规划模型的应用例3.11

某公司经营一个回收中心，专门从事四种固体废弃物的回收，并将回收物处理、混合成为可销售的三种产品。根据混合时各种材料的比例（规格），可将产品分成三种不同等级:A、B和C，它们的混合成本和售价也不同，具体如表3—19所示。回收中心可以从一些渠道定期收集到所需的固体废弃物，表3—20给出了中心每周可以收集到每种材料的数量以及处理成本。该公司是一家专门从事与环保有关的公司，公司的收益