《运筹学》 课件 第3章-线性规划的扩展

7/16/2024第3章线性规划的扩展1CONTENTS目录3.1

运输问题3.2

目标规划3.3

数包络分析7/16/202423.1运输问题例3.1

某个公司从三个产地A1,A2,A3将物品运往四个销地B1，B2，B3，B4。各产地的产量、各销地的销量和各产地运往各销地的每件物品的运费如下表所示。应如何调运，使得总运输费用最小？3.1.1运输问题的建模（1）问题的提出7/16/20244其中，

cij为从产地Ai运到销地Bj的线路的运输价格;

a1,a2,a3分别为16,10,22；b1,b2,b3,b4分别为8,14,12,14。解：设xij为从产地Ai运到销地Bj的运量，（i=1,2,3;j=1,2,3,4）。

3.1.1运输问题的建模7/16/20245运输问题（TransportationProblem，简记为TP）：在每个产地的供应量与每个销地的需求量已知，并知道各地之间的运输单价的前提下，把某种产品从多个产地调运到多个销地，如何确定每条运输线路上的运量使得总的运输费用最小的问题。02运输问题的一般模型（2）运输问题的一般模型3.1.1运输问题的建模7/16/20246图3.1运输问题的示意图02运输问题的一般模型3.1.2运输问题的一般模型3.1.1运输问题的建模7/16/20247所有产地的总供给量所有销地的总销售量设为从产地Ai运到销地Bj的运量。根据供需关系可以将运输问题分为三种类型：1）供需平衡的物资调运问题，S=D总供给等于总需求。当供需平衡时，每个产地的物资可全部运出，每个销地的需求都可以得到满足，因此供需平衡的物资调运问题的数学模型为：02运输问题的一般模型3.1.1运输问题的建模7/16/20248这是一个具有mn个决策变量，m+n个约束条件的线性规划问题。在一些实际的问题中还要求为整数，如调运的物资为电脑、家电或其它包装成箱的物资，从而形成一个整数规划问题。02运输问题的一般模型3.1.1运输问题的建模7/16/202492）供大于求的物资调运问题，S>D总供给大于总需求时，有些产地的物资不能全部运出，数学模型改为：3.1.1运输问题的建模7/16/2024103）供不应求的物资调运问题，S<D总供给小于总需求时时，数学模型为：3.1.1运输问题的建模7/16/202411将不平衡的供需关系配平注：缺啥补啥，来配平。3.1.1运输问题的建模7/16/202412例3.2

某公司在不同地区有三个工厂，产品将运往四个地区销售。已知各线路的单位运输成本和供需关系见下表，请写出物资调运问题的数学模型，并转化为供需平衡的表格形式。解：（略）3.1.1运输问题的建模7/16/202413以上讨论说明运输问题是一类具有特殊结构的线性规划。供需平衡的物资调运问题是运输问题的基本问题，因为可以将供过于求/供不应求的运输问题通过增加虚拟的销地/产地转化为供求平衡的运输问题。运输问题的特征体现在它的技术系数矩阵A中各元素仅可取值为1或0，且对应于决策变量的系数列向量，只有第i个和第m+j个分量取值为1，其余分量的取值均为0，即这里，表示仅在第k个分量取值为1的m+n维单位列向量。3.1.1运输问题的建模7/16/202414m行n行系数矩阵的特殊结构决定了平衡运输问题具有以下三个性质。3.1.1运输问题的建模7/16/2024151、运输问题中任意m+n个决策变量的系数列向量都是线性相关的。可以进一步证明，运输问题的基变量的个数为m+n-1。如果我们能得到决策变量的m+n-1个线性无关的系数列向量，就得到一个相应的基可行解。2、运输问题必存在最优解。（课后思考，为什么？）3、如果运输问题中的所有供给量和需求量都为整数，则该问题的任意基可行解均为整数解。这时不必考虑整数约束运输问题的主要特征：3.1.1运输问题的建模7/16/202416定义3.1

凡是能排列成（其中互不相同，互不相同）形式的变量集合，称为一个闭回路，其中诸变量称为这个闭回路的顶点。图3.3闭回路辨析图（3）运输问题的基本定理3.1.1运输问题的建模7/16/202417闭回路的几何特征：1、每一个顶点格子都是90°转角点；2、每一行（或列）若有闭回路的顶点，则有两个顶点；3、每两个顶点格子的连线都是水平的或垂直的；4、闭回路中顶点的个数必为偶数。闭回路的代数性质：性质3.1

构成闭回路的变量组对应的列向量组必线性相关。3.1.1运输问题的建模7/16/202418性质3.2

若变量组中有一个部分组构成闭回路，则该变量组对应的列向量组是线性相关的。推论：若变量组对应的列向量组线性无关，则该变量组一定不包含闭回路。该推论可以用反证法和性质3.2得到。定义3.2在变量组中，若有某一个变量xij

是它所在的行（第i

行）或列（第j

列）组的一个孤立点。3.1.1运输问题的建模7/16/202419性质3.3若一变量组中不包含任何闭回路，则该变量组必有定理3.1变量组孤立点。对应的列向量组线性无关的充要条件是该变量组中不包含任何闭回路。3.1.1运输问题的建模7/16/202420既然运输问题是线性规划问题，当然可以直接用单纯形法求解。但运输问题变量较多（如有20个产地50个销地的运输问题就有20×50＝1000个变量，直接求解效率不高。是一种根据运输问题的特殊结构进行优化的单纯形法，可以显著而表上作业法就提高解题效率。其求解步骤也分为确定初始基可行解、最优性判别和改善基可行解这三个主要步骤。3.1.2运输问题的表上作业法7/16/202421产销平衡的运输问题有m+n-1个基变量，基变量非负，而其余为零。可用划线法（包括西北角法、最小元素法、沃格尔法）来确定初始基可行解中各基变量的位置和数值。每确定一个基变量的值，将供需平衡表中满足需求的销地所在列或搬运一空的产地所在行划去。共m+n-1次线。确定下来的基变量的数值取该基变量对应线路上现有的产地余量和销地余量的最小值。01确定初始基可行解（1）

确定初始基本可行解7/16/2024221）西北角法西北角法（NorthwestCornerMethod）优先满足表中未划去部分的左上角（西北角）空格的供销需求。其目的只是找初始基可行解，不考虑优化。为了在供求平衡表的基础上，同时标注求解过程中所需的其他信息，将Ai和Bj的交叉格（Ai，Bj）中的运价cij放在该格的右上角，在该格子的左下角标注从Ai到Bj的线路的其他信息。01确定初始基可行解（1）

确定初始基本可行解7/16/202423例3.3试运用西北角法给出例3.1的初始可行方案。解：该运输方案的总成本z=512（1）

确定初始基本可行解7/16/202424

Step1.找出目前未划去的最小运价，设为cst①若产地余量>销地余量，则销地上运满，填xst=销地的余量，划去第t列；②若产地余量<销地余量，则产地全运出，填xst=产地的余量，划去第s行；③若产地余量=销地余量，填xst=产地/销地的余量；因为同时满足了产地和销地的要求，同时划去第s行和第t列。还要在同时划去的第s行、第t列的任一其他空格添加一个0。Step2.重复step1直至，所有运价都划去。

2）最小元素法基本步骤：（1）

确定初始基本可行解7/16/202425例3.4试运用最小元素法给出例3.1的初始可行方案。解：其计算结果如表3.7。表3.7最小元素法的供求平衡表（1）

确定初始基本可行解7/16/202426最小运价法的不足图3.4一个简单的运输模型最小元素法可得:x11=1，x12=1，x22=2，总成本25；可是令x21=1，x12=2，x22=1，总成本20。可见，当只考虑最小运价线路的充分利用，而导致运价较小的线路（如该例中A2与B1，A1与B2之间线路）不能合理利用。（1）

确定初始基本可行解7/16/2024273）伏格尔（Vogel）法伏格尔法优先满足未划去部分各产地（销地）运出（运入）次小运价与最小运价的差值最大者的最小运价线路的物资调运。这种方法能一定程度地减少只顾使用最小运价线路，而导致某产地或销地的最大次小运价线路上运输量的增加导致的成本增加。例如，对图3.4模型可以列出供求平衡表，如表3.8。（1）

确定初始基本可行解7/16/202428表3.8图3.4模型的伏格尔法供求平衡表（1）

确定初始基本可行解7/16/202429例3.5

试运用伏格尔法给出例3.1的初始可行方案。（1）

确定初始基本可行解7/16/2024解：30如同一般目标函数最小化的线性规划一样，最小运输成本问题的基可行解是否最优可以根据非基变量检验数是否全部非负来判断。基本有闭回路法和对偶变量法这两种方法。1）闭回路法对每一个空格（非基变量）找从其出发，其余点为数字格（基变量）的闭合回路。具体操作为：从一个代表非基变量的空格出发，沿水平或垂直方向前进，只有碰到代表基变量的填入数字的格子才能向左或向右转90°（当然也可不改变方向）继续前进，这样继续下去，直至回到出发的那个空格。02最优性检验（2）

最优性检验7/16/202431由此形成的封闭的折线构成的闭回路。一个非基变量存在惟一的闭回路。令该非基变量变为1，相应调整闭合回路上各个格子的运量，求出的总运输费用的增量就是该非基变量的检验数。当一个原非基变量xij变为1，其余基变量不变，（2）

最优性检验7/16/202432例3.6试对例3.1用最小元素法求出的初始可行解进行最优性检验解：因为非基变量x24的检验数为负数，所以该方案不是最优方案。

（2）

最优性检验7/16/2024332）对偶变量法（位势法）有m个产地和n个销地的产销平衡的调运问题的对偶问题如下：对于一个基B，令（2）

最优性检验7/16/202434由于基变量的检验数为零，对于m+n-1个基变量xij有：为求出m+n的变量，可任意令（相当于划去第行），解出其余这样就可以用对偶变量来求所有非基变量的检验数是否非负。若都满足，则最优，否则还不是最优，还要改善可行方案。（2）

最优性检验7/16/202435表3.11对偶变量法检验数表由于，所有非基变量的检验数非负，所以该方案是一个最优解。例3.7试检验例3.1中伏格尔法的解得到的运输方案的最优性。（2）

最优性检验7/16/202436在所有为负值的检验数中，选其中最小的负检验数，以它对应的非基变量为入基变量，然后以该非基变量所在格为出发点作一个闭回路。该原非基变量的运量的调整值等于闭回路顶点的序号中，所有偶数序号的顶点的调运量的最小值。同时，对闭回路中偶数/奇数序号顶点减/加该调整量，以保证产销平衡。

（3）

改进的运输方案7/16/202437例3.8试用闭回路法调整例3.1中最小元素法得到的可行方案。可以进一步验证调整后的方案是最优方案。（3）

改进的运输方案7/16/2024381）无穷多最优解当某个非基变量的检验数为0时，该问题有无穷多最优解。如表3.10中x11的检验数为0，表示该例有无穷多最优解。只要把检验数为0的非基变量x11作为入基变量，调整运输方案，就可得到另一个最优方案。从出发，找到闭合路（4）

特殊情况的处理7/16/202439为了产销平衡调整闭回路中其他变量的值，;其余变量不变。详见表3.13。表3.13另一最优解（4）

特殊情况的处理7/16/2024402）退化有两种情况会出现某个基变量为零的退化情况。在用划线法确定初始基可行解时，若某选择的基变量所在格对应的产地余量和销地余量恰好相等。这时该基变量=产地余量，对应产地和销地都已平衡。但为了保证划线法每确定一个基变量划一线的原则，应先划去对应产地所在行/销地所在列，再在销地所在列/产地所在行的其它格中任选一个填0作为退化的基变量，最后再划去其所在的列/行。（4）

特殊情况的处理7/16/202441当用闭回路法调整时，出现回路中偶数节点格中有多于1个等于最小值。这时入基变量取该最小值，导致有多个原基变量变为0。这时，只能选其中任一个为0的原基变量出基，而其余的作为退化的基变量必须在其所在格中填0，以保证基变量的个数不变。03改进运输方案（4）

特殊情况的处理7/16/202442例3.9北方的某汽车制造集团企业有三个组装厂，即A工厂、B工厂、C工厂，每年分别需要生活用煤和取暖用煤2000t，1000t，3000t，由山西省大同、阳泉两处煤矿负责供应。这两处煤矿的价格和质量都基本相同。两处煤矿能供应该化工企业的煤的数量，山西阳泉为4000t，山西大同为1500t，由煤矿至该化工企业的单位运价（百元／t）如表3.14所示。由于供不应求，经企业领导研究平衡决定A工厂供应量不少于1500t，B工厂需要量应全部满足，C工厂供应量可减少300t。试求：总运费为最低的调运方案。01需求可变的运输问题3.1.3几种特殊的运输问题（1）需求可变的运输问题7/16/202443解：主要步骤（1）判断供需关系（2）分析各销地的刚性、柔性需求（3）列出供需平衡表3.1.3几种特殊的运输问题7/16/202444拓展思考：（1）若C工厂为了能争取到更多的煤，声称有多少煤都愿意买下，则如何写出这种情况下的供需平衡及运价表。（2）若大同到C工厂的运输线路因泥石流被破坏，则需要如何调整供需平衡及运价表。3.1.3几种特殊的运输问题7/16/202445其中，cij

为从i点运到j点的单位运价，si为发点i的供应量，dj为收点j的需求量。

图3.5转运问题的网络图（2）转运问题3.1.3几种特殊的运输问题7/16/202446转运问题（TransshipmentProblem）将节点分为产地（发点）、销地（收点）和转运点。其中，任何节点都可以承担转运功能。转运点的运出量等于运入量。发点的运出量大于运入量。收点的运入量大于运出量。因此，转运问题关于运输节点的约束也相应分为发点约束、收点约束以及转运点约束。（2）转运问题3.1.3几种特殊的运输问题7/16/202447运输问题模型是在经济管理中有着广泛应用的重要模型。因为与一般的线性规划相比运输问题模型在变量个数相同的条件下，表上作业法较单纯形法简单有效，所以，常常尽可能地将一些线性规划问题化为运输问题的模型。一些管理问题直接可体现为供给和需求的形式，如按合3.1.4运输问题的应用举例7/16/2024同生产的生产计划问题等。48例3.11某集团公司为降低设备采购的成本，对生产设备实行集中采购。采购部门计划通过招标采购某种生产设备。共邀请了m家工厂来参加投标。假设各厂家提供的是同质产品。每个厂家都提供了一份标书，在标书中注明了该厂单位产品的价格和按此价格所能提供的数量，设为ai。该采购部门将这些产品运往不同的n个地区的子公司，第j个地区的设备需求量为bj，运输费用由该采购部门支付。根据这些标书，该部门应该向哪些厂家订货，订货量各为多少？（1）

投标裁决问题7/16/202449从第i个厂家订货并往到第j个地区时的单位产品成本，cij。设决策变量xij为从第i个厂家订货后运至第j个地区的订货量，（i=1，…，m；j=1，…，n）。

解：（1）

投标裁决问题7/16/202450例3.12某数码产品制造公司有3个分厂，生产A、B两种数码产品。生产方式分为正常生产和加班生产两种，加班生产成本大于正常生产成本。现要制定两个月的工作计划：第一月A、B产品的需求量分别为200和600件，第二月A、B产品的需求量分别为400和700件。各厂生产A和B产品所需时间、可用时间数据由表3.1.20的数据给出。设两种产品的单位产品制造时间都为1小时。如果在第一月生产第二月的产品，则需存放一个月，3个工厂的保管费分别为10，15和20元。试拟定生产计划，使总成本最低。

（2）生产排程问题7/16/202451解：（2）生产排程问题7/16/202452例3.13某航空公司使用上海作为中转枢纽，以最少的航班数满足国内北方城市和南方城市之间的航空出行需求。从上午10点到11点有四架分别来自哈尔滨、长春、吉林、沈阳的波音747客机将在上海虹桥机场降落。这些飞机上的乘客将分别去往福州、广州、深圳、厦门。飞机的离场时间为11点30分到12点30分。表3.1.26列出了各个航班的乘客去往各目的地的情况表，即转机情况表。例如，来自哈尔滨的飞机，若飞往厦门则有38人不转机，剩下的去福州、广州和深圳等城市的都需要转机。此外，表中航班的出发地和目的地都是按时间的先后顺序排列的。例如，福州在广州之前表示去往福州的飞机将先于去往广州的飞机起飞。表格中标记为“-”的两个格子表示，由于来自沈阳的飞机到中转站（上海）的时间最迟，已经来不及在去福州和广州的城市的飞机起飞前完成到这两地的转机流程。请问应如何安排各航班离开虹口机场后的目的地，以使得在虹桥机场转机的乘客数最少？（3）

机场航班转机问题7/16/202453设xij是从北方城市i到南方城市j的线路上的“运量”，xij是取值为0或1的二值选择变量。设cij为从北方城市i到南方城市j的线路上不转机的人数。（3）

机场航班转机问题7/16/2024解：54案例1新美电器公司是新进在中国南方崛起的智能家用电器公司。从一家小型科技创业企业起家，凭借其研发的家用智能机器人技术，首先在深圳建立了第一个制造基地。随着业务的发展又在顺德建立了第二个制造基地。为了覆盖全国的市场，公司在北京、上海和广州建立分销中心，向9个目标客户区销售产品。这九个地区的编号分别为T1，...，T9。两个生产基地的生产成本不同。深圳基地的单位生产成本为1050元，而顺德基地由于有更熟练的工人和改进的新一代设备，单位生产成本比深圳少50元。公司的快速发展，曾一度使得公司高层无暇顾及分销系统的效率。然后，随着新的竞争对手的涌入，技术壁垒的突破，市场竞争日趋激烈。公司高层意识到需要将提高分销系统的效率放在当前日程中了。目前，深圳的一个季度的生产能力为30000台，而顺德的生产能力是20000台。表3.22为公司统计的从各生产基地到3个分销中心的单位产品的运输价格。

北京上海广州深圳基地423215顺德基地-3512表3.22

从生产基地到分销中心的运输价格（单位：元/台）3.1.5运输问题的管理案例7/16/202455公司的市场部向高层提供了下个季度的各客户地区的需求预测，详见表3.23客户地区需求客户地区需求客户地区需求T16300T41210T72750T24880T56120T88580T32130T64830T94460表3.23下季度需求预测表（单位：台）从各分销中心向各客户地区的单位产品的运输成本如表3.24所示。

T1T2T3T4T5T6T7T8T9北京321314460----上海525445602747343327广州----5433242125表3.24分销中心到各客户区的运输价格（单位：元）现有的分销系统中北京负责T1，T2，T3，T4，上海负责T5，T6，T7，广州负责T8，T9地区。每个客户区都由唯一指定的分销中心负责。3.1.5运输问题的管理案例7/16/202456请根据已知的资料，帮助该公司高管做以下分析：（1）根据目前的分销策略，为使得总的运输成本最小，下个季度的制造和运输方案是什么？（2）有些高管建议放弃客户区必须由唯一指定的分销中心负责的原则，认为可以让客户从任意可行的分销中心拿货。请给出按该意见实施前后在总成本上的差异。（3）公司想知道如果允许从生产基地到客户区的直接供货是否有利于提升效率。假设深圳到T2，顺德到T8，T9的单位运输成本分别为3.5，0.3，0.7元。考虑这三条直供线路后，分销的总成本能否减少。3.1.5运输问题的管理案例7/16/2024573.2目标规划(1)问题提出例3.15某公司分厂用一条生产线生产两种产品A和B，每周生产线运行时间为60小时，生产一台A产品需要4小时，生产一台B产品需要6小时．根据市场预测，A、B产品平均销售量分别为每周9、8台，它们销售利润分别为12、18万元。在制定生产计划时，经理考虑下述4项目标：3.2.1多目标规划模型7/16/202459首先，产量不能超过市场预测的销售量；其次，工人加班时间最少；第三，希望总利润最大；最后，要尽可能满足市场需求,当不能满足时,市场认为B产品的重要性是A产品的2倍．试建立这个问题的数学模型．3.2.1多目标规划模型7/16/202460设决策变量x1，x2

分别为产品A，B的产量

MaxZ=12x1+18x2

s.t.4x1+6x2

60

x1

9x2

8

x1,x2

0容易求得上述线性规划的最优解为(9,4)T

到(3,8)T

所在线段上的点,最优目标值为Z*=180,即可选方案有多种.在实际上,这个结果并非完全符合决策者的要求,它只实现了经理的第一、二、三条目标，而没有达到最后的一个目标。进一步分析可知，要实现全体目标是不可能的。3.2.1多目标规划模型7/16/202461(2)目标规划模型的基本概念

把例3.15的4个目标表示为不等式.仍设决策变量x1，x2

分别为产品A，B的产量.那么,

第一个目标为:x1

9，x2

8

；第二个目标为:4x1+6x2

60

；第三个目标为:希望总利润最大，要表示成不等式需要找到一个目标上界，这里可以估计为252（=12

9+18

8），于是有

12x1+18x2

252；第四个目标为:x1

9，x2

8；3.2.1多目标规划模型7/16/202462下面引入与建立目标规划数学模型有关的概念．（1）正、负偏差变量d

+，d-

我们用正偏差变量d

+表示决策值超过目标值的部分；负偏差变量d-表示决策值不足目标值的部分。因决策值不可能既超过目标值同时又末达到目标值，故恒有d

+

d-＝0．（2）绝对约束和目标约束我们把所有等式、不等式约束分为两部分：绝对约束和目标约束。3.2.1多目标规划模型7/16/202463绝对约束指必须严格满足的等式约束和不等式约束；如在线性规划问题中考虑的约束条件，不能满足这些约束条件的解称为非可行解，所以它们是硬约束。设例1中生产A，B产品所需原材料数量有限制，并且无法从其它渠道予以补充，则构成绝对约束。目标约束目标规划特有的，我们可以把约束右端项看作要努力追求的目标值，但允许发生正式负偏差，用在约束中加入正、负偏差变量来表示，于是称它们是软约束。3.2.1多目标规划模型7/16/202464对于例3,15,我们有如下目标约束

x1

+d1--d1+=9(1)

x2+d2--d2+=8(2)

4x1+6x2

+d3--d3+=60(3)12x1+18x2+d4--d4+=252(4)3.2.1多目标规划模型7/16/202465(3)优先因子与权系数

对于多目标问题，设有L个目标函数f1,f2,

,fL,决策者在要求达到这些目标时，一般有主次之分。为此，我们引入优先因子Pi

，i=1,2,

,L.无妨设预期的目标函数优先顺序为f1,f2,

,fL,我们把要求第一位达到的目标赋于优先因子P1，次位的目标赋于优先因子P2、…，并规定Pi>>Pi+1，i=1,2,

,L-1.

即在计算过程中,首先保证P1级目标的实现，这时可不考虑次级目标；而P2级目标是在实现P1级目标的基础上考虑的，以此类推。当需要区别具有相同优先因子的若干个目标的差别时，可分别赋于它们不同的权系数wj

。优先因子及权系数的值，均由决策者按具体情况来确定．3.2.1多目标规划模型7/16/202466（4）目标规划的目标函效．目标规划的目标函数是通过各目标约束的正、负偏差变量和赋于相应的优先等级来构造的．决策者的要求是尽可能从某个方向缩小偏离目标的数值。于是，目标规划的目标函数应该是求极小：Minf＝f（d+，d-)

其基本形式有三种：3.2.1多目标规划模型7/16/202467①要求恰好达到目标值，即使相应目标约束的正、负偏差变量都要尽可能地小。这时取

Min（d++d-)；②要求不超过目标值，即使相应目标约束的正偏差变量要尽可能地小。

这时取

Min（d+)；③要求不低于目标值，即使相应目标约束的负偏差变量要尽可能地小。

这时取

Min（d-)；3.2.1多目标规划模型7/16/202468

对于例3.15,我们根据决策者的考虑知第一优先级要求Min（d1++d2+

)；第二优先级要求Min（d3+

)；第三优先级要求Min（d4-)；第四优先级要求Min（d1-+2d2-)，这里,当不能满足市场需求时,市场认为B产品的重要性是A产品的2倍．即减少B产品的影响是A产品的2倍，因此我们引入了2:1的权系数。3.2.1多目标规划模型7/16/202469综合上述分析，可得到下列目标规划模型

Minf=P1（d1++d2+

)+P2d3++P3d4-+P4（d1-+2d2-

)s.t.x1

+d1--d1+=9x2+d2--d2+=84x1+6x2

+d3--d3+=6012x1+18x2

+d4--d4+=252x1,x2

,di-,di+

0,i=1,2,3,4.

3.2.1多目标规划模型7/16/202470(3)目标规划模型的一般形式式中的第二行是L个目标约束，第三行是m个绝对约束，clj

和gl

是目标参数。3.2.1多目标规划模型7/16/202471LP：MaxZ=100X1+

80X2

2X1+4X2

500s.t4X1+2X2

400X*=(50,100)X1,

X20Z*=13000

例3.16某工厂生产甲，乙两种产品，受到金工和装配有效工时限制。在单件收益已知的条件下，要求制定一个收益最大的计划。具体数据见表3.27。

甲乙有效工时金工42400装配24500收益10080

表3.41基本数据表3.2.1多目标规划模型7/16/202472目标：去年总收益9000，增长要求11.1%

即：今年希望总收益不低于10000引入d+：决策超过目标值部分(正偏差变量)

d-：决策不足目标值部分(负偏差变量)目标约束：100X1+80X2-d++d-=10000

d+•d-=0d+,d-

03.2.1多目标规划模型7/16/202473可得到目标规划模型如下所示：3.2.1多目标规划模型7/16/202474原材料价格上涨，超计划要高价购买，所以要严格控制市场情况，产品Ⅰ销售量下降，产品Ⅰ的产量不大于产品Ⅱ的产量尽可能达到并超过利润计充分利用设备，不希望加班划指标56千元例3.17某企业生产两种产品，受到原材料供应和设备限制。在单件利润等有关数据已知的条件下，要求一个获利最大的生产计划。具体数据见表3.28。

ⅠⅡ资源拥有量原材料2111设备1210利润810

表3.28基本数据表3.2.1多目标规划模型7/16/202475建模：设定约束条件。(目标约束、绝对约束)规定目标约束优先级建立模型

设X1，X2为产品Ⅰ，产品Ⅱ产量。3.2.1多目标规划模型7/16/2024762X1+X2

11X1-X2+d1--d1+=0X1+2X2+d2--d2+=108X1+10X2+d3--d3+=56X1,

X2,

di-,

di+0di-•

di+=0d1-:X1产量不足X2部分d1+

:X1产量超过X2部分d2-:设备使用不足10

部分d2+

:设备使用超过10部分d3-:利润不足56部分d3+

:利润超过56部分或

MinZ1=d1+MinZ2=d2-+d2+

MinZ3=d3-

MinZ=p1d1++p2(d2-+d2+)+p3(d3-)3.2.1多目标规划模型7/16/202477

对只具有两个决策变量的目标规划的数学模型，我们可以用图解法来分析求解．通过图解示例，可以看到目标规划中优先因子，正、负偏差变量及权系数等的几何意义。下面用图解法来求解例3.15我们先在平面直角坐标系的第一象限内，作出与各约束条件对应的直线，然后在这些直线旁分别标上G-i，i=1，2，3，4。图中x，y分别表示问题的x1和x2；各直线移动使之函数值变大、变小的方向用+、-表示di+,di-．3.2.2几何意义及图解法7/16/202478图105101520yx2015105+-G-1+-G-2+-G-3G-4+-3.2.2几何意义及图解法7/16/202479

下面我们根据目标函数的优先因子来分析求解．首先考虑第一级具有P1优先因子的目标的实现，在目标函数中要求实现Min（d1++d2+),取d1+=d2+=0.图2中浅红色阴影部分即表示出该最优解集合的所有点。我们在第一级目标的最优解集合中找满足第二优先级要求Min（d3+)的最优解.取d3+=0

,可得到图3中浅绿阴影部分即是满足第一、第二优先级要求的最优解集合。3.2.2几何意义及图解法7/16/202480图205101520yx2015105+-G-1+-G-2+-G-3G-4+-3.2.2几何意义及图解法7/16/202481图305101520yx2015105+-G-1+-G-2+-G-3G-4+-3.2.2几何意义及图解法7/16/202482

第三优先级要求Min（d4-)，根据图示可知，d4-不可能取0值，我们取使d4-最小的值72得到图4中两阴影部分的交线(红色粗线)，其表示满足第一、第二及第三优先级要求的最优解集合。

最后，考虑第四优先级要求Min（d1-+2d2-)，即要在黑色粗线段中找出最优解。由于d1-的权因子小于d2-，因此在这里可以考虑取d2-=0。于是解得d1-=5，最优解为A点x=3，y=8。3.2.2几何意义及图解法7/16/202483图405101520yx2015105+-G-1+-G-2+-G-3G-4+-A(3,8)3.2.2几何意义及图解法7/16/202484目标规划的数学模型,特别是约束的结构与线性规划模型没有本质的区别，只是它的目标不止是一个,虽然其利用优先因子和权系数把目标写成一个函数的形式,但在计算中无法按单目标处理,所以可用单纯形法进行适当改进后求解。

在组织、构造算法时，我们要考虑目标规划的数学模型一些特点，作以下规定：因为目标规划问题的目标函数都是求最小化，所以检验数的最优准则与线性规划是相同的；3.2.3单纯形法7/16/202485因为非基变量的检验数中含有不同等级的优先因子，Pi>>Pi+1，i=1,2,

,L-1.于是从每个检验数的整体来看：Pi+1（i=1,2,

,L-1）优先级第k个检验数的正、负首先决定于P1

，P2，…，Pi

优先级第k个检验数的正、负。若P1

级第k个检验数为0，则此检验数的正、负取决于P2级第k个检验数；若P2

级第k个检验数仍为0，则此检验数的正、负取决于P3级第k个检验数，依次类推。换一句话说，当某Pi级第k个检验数为负数时，计算中不必再考察Pj（j>I

）级第k个检验数的正、负情况；根据目标规划模型特征，当不含绝对约束时，di-

（i=1,2,…,K）构成了一组基本可行解。在寻找单纯形法初始可行点时，这个特点是很有用的。3.2.3单纯形法7/16/202486解目标规划问题的单纯形法的计算步骤:1)建立初始单纯形表．在表中将检验数行按优先因子个数分别列成K行。初始的检验数需根据初始可行解计算出来，方法同基本单纯形法。当不含绝对约束时，di-

（i=1,2,…,K）构成了一组基本可行解，这时只需利用相应单位向量把各级目标行中对应di-

（i=1,2,…,K）的量消成0即可得到初始单纯形表。置k＝1；

2)检查当前第k行中是否存在小于0，且对应的前k-1行的同列检验数为零的检验数。若有取其中最小者对应的变量为换入变量，转3)。若无这样的检验数，则转5)；3.2.3单纯形法7/16/2024873)按单纯形法中的最小比值规则确定换出变量，当存在两个和两个以上相同的最小比值时，选取具有较高优先级别的变量为换出变量，转4）；4)按单纯形法进行换基运算，建立新的单纯形表，（注意：要对所有的行进行初等变换运算）返回2)；5)当k＝K时，计算结束。表中的解即为满意解。否则置k=k+1，返回2）。3.2.3单纯形法7/16/202488例3.18试用单纯形法来求解例3.15的目标规划模型3.2.3单纯形法7/16/202489解:首先处理初始基本可行解对应的各级检验数。3.2.3单纯形法7/16/202490（1）k=1，在初始单纯形表中基变量为（d1-,d2-,d3-,d4-)T=（9，8，60，252)T

；（2）因为P1与P2优先级的检验数均已经为非负，所以这个单纯形表对P1与P2优先级是最优单纯形表；（3）下面考虑P3优先级，第二列的检验数为-18，此为进基变量，计算相应的比值bi/aij写在

列。通过比较，得到d2-

对应的比值最小，于是取a22（标为*号）为主元进行矩阵行变换得到新的单纯形表；（4）下面继续考虑P3优先级，第一列的检验数为-12，此为进基变量，计算相应的比值bi/aij

，得到d3-

对应的比值最小，于是取a31（标为*号）为转轴元进行矩阵行变换得到新的单纯形表；3.2.3单纯形法7/16/2024913.2.3单纯形法7/16/202492（5）当前的单纯形表各优先级的检验数均满足了上述条件,故为最优单纯形表。我们得到最