《水资源系统分析及应用：第二章 线性规划的基本理论及其应用》由会员分享，可在线阅读，更多相关《水资源系统分析及应用：第二章 线性规划的基本理论及其应用（287页珍藏版）》请在金锄头文库上搜索。
1、第二章 线性规划的基本理论及其应用2.1线性规划的数学模型及其标准形式2.2线性规划问题的图解法2.3线性规划问题的单纯形解法2.4非标准型线性规划问题的解法2.5对偶问题2.6灵敏度分析2.7随机线性规划2.8线性规划的应用道路交通规划道路交通规划与规划有关的例子生产安排规划生产安排规划资源调配资源调配科学配餐科学配餐n线性规划问题的实践背景n线性规划问题的数学模型n线性规划问题的标准型2.1线性规划的数学模型及其标准形式76.1緒言n如何在有限的经济资源下进行最有效的调配与选用，以求发挥资源的最高效能。此问题愈来愈受到重视，也就是以最低的代价，获取最大的效益。n兹列举如下：n决定紧急设备与
2、人员的地点，使反应时间最短化。n决定飞机、飞行员、地勤人员的飞航最佳日程安排。n发展财务计划。n决定动物饲料的最佳组合。n决定最佳食谱计划。n决定最佳生产日程安排。n指出最佳工作指派。n决定成本最低化的船运计划。n指出工厂的最佳产品组合。8n上述许多问题为在一些限制式(constraint)之下，以一组联立线性不等式或等式的方式表示，求线性目标函数(objectivefunction)为极大或极小的问题。n线性规划(linearprogramming,LP)就是数学家们针对这类问题研究所得的解法。1.1.线性规划问题的实践背景背景：背景：提高企业的经济效益是现代化管理的根本任务，各个领域中的大
3、量问题都可以归结为线性规划问题。近几十年来，线性规划在各个行业中都得到了广泛的应用。根据美国财富杂志对全美前500家大公司的调查表明，线性规划的应用程度名列前茅，有85%的公司频繁地使用线性规划，并取得了提高经济效益的显著效果。1.1.线性规划问题的实践背景什么是什么是线性性规划？划？所谓线性规划，是求线性函数在线性(不等式或等式)约束下达最(小或大)值的问题。线性规划广泛应用于工农业、军事、交通运输、决策管理与规划、科学实验等领域。简单的来说,线性规划研究线性最优化(optimization)問題。11n线性规划是什么n所谓线性规划简单的说，就是将决策上所面临的问题，以线性的数学式来加以描述
4、，在线性等式及不等式组的条件下，使用特定的方法线性规划求得最优解。n线性规划模型是由四种成分组合而成：(1)目标；(2)决策变数；(3)限制式以及(4)参数。假想我们预备做一项决策,而该决策牵涉到n个变数(x1,x2,.,xn)有待决定。若是有一个目标函数可以表现为z(x1,x2,.,xn)=c1x1+c2x2+.+cnxn这种线性(一次)函數,同时这些变量之间的相互约束也可以用m个线性(一次)不等式来表示成ai1x1+ai2x2+.+anixnbi(i=1,2,m)。那么我们就面对着一个线性规划问题:如果我们以向量c=(c1,c2,.,cn)t来表示目标函数的系數,向量x=(x1,x2,.,
5、xn)t来表示变數,向量b=(b1,b2,.,bm)t来表示约束不等式的右手值,同时以矩阵A=(aij)mn来表示诸约束函数的系數,那么上述的线性规划问题可以简化成下列形式:换言之,线性规划的目的在求得一组变量特定值,使之在满足各个约束同时也达到目标函数的最小值。实际上,透过简单的数学转换,线性规划也可以处理最大值的问题。同时它的变數x1,x2,.,xn也无需限制为非负值,而Axb更可以改为Ax=b或者Axb的约束形式。但是为了方便讨论起見,我们暂时集中精神在形式如(P)的问题上。线性规划问题大致可以分为两类给出一定量的人力、物力、财力或其它资源，如何统筹规划这些有限的资源完成最大任务；给定一
6、项任务，如何运筹规划，合理安排，以最少的资源来完成它。1.1.线性规划问题的实践背景n线性规划问题起源于20世纪初期，在二战期间得到发展n1947年，G.B.Dantzig教授孕育n1948年，T.C.Koop-mans和Dantzig两人于1948年夏天在美国加州圣塔摩尼加(SantaMonica)海滩散步时拟定名称。n在1950和1960年代,线性规划的内容愈变愈豊富,更有许多成功的实用案例,所以愈来愈受世人瞩目。n到了1975年,瑞典皇家科学院决定将当年的诺贝尔经济奖颁發给前面提到的L.V.Kantorovich和T.C.Koopmans以表彰他们在资源最佳分配理论的贡献。n1979年，
7、一位苏联数学家L.G.Khachian,利用椭球法(ellip-nsoidmethod)概念印证出线性规划问题可在多项式时间内求得解答。n1984年由一位美国电话电报公司贝尔实验室的印度裔科学家N.Karmarkar他设计出一项内点法来解线性规划问题。线性规划的历史2.2.线性规划问题的数学模型n例1-1 某工厂生产甲，乙两种产品，这些产品分别需要在ABCD四种不同的设备上加工。按工艺规定，产品甲，乙在各设备上所需要的加工台时数如表1所示，已知各设备在计划期内有效台时数分别是12、8、16和12。该工厂每生产一件产品甲可得利润2元，每生产一件产品乙可得利润3元。问应当如何安排生产计划，才能使利
8、润最大化？（表1）设备设备ABCD可得利润可得利润产品甲产品甲21402元元产品乙产品乙22043元元有效有效台时数台时数1281612问问题题的的提提出出(一一)2.2.线性规划问题的数学模型n分析：n上述实际问题，通俗地说，就是在有效台时数一定的前提下，求使利润最大化的生产方案。n建模：n若以分别代表产品甲，乙在计划期内的生产量。因为设备A的有效台时数为12，这是一个限制产量的条件，所以在确定产品甲，乙的产量时，要肯定不能超出设备A的有效台时数，即可用不等式表示为12n同理，对设备B、C、D也可以得到以下不等式：81612考虑到实际意义，不可能为负值，即02.2.线性规划问题的数学模型n用
9、Z表示利润，则目标函数n于是，上述最优生产问题可以归纳为以下数学形式其中必须满足以下条件128s.t.161202.2.线性规划问题的数学模型n思考：模型与表（1）的对应关系？设备设备ABCD可得利润可得利润产品甲产品甲21402元元产品乙产品乙22043元元有效有效台时数台时数1281612其中必须满足以下条件128s.t.16120例例1.2 某某汽汽车车厂厂生生产产大大轿轿车车和和载载重重汽汽车车，所所需需资资源源、资源可用量和产品价格如下表所示资源可用量和产品价格如下表所示: 大轿车 载重汽车 可用量钢材（吨） 2 2 1600工时(小时) 5 2.5 2500座椅 400（辆）获利(
10、千元/辆) 4 3问应如何组织生产才能使工厂问应如何组织生产才能使工厂获利最大获利最大？ 问题的提出问题的提出(二二)例1.2的数学模型s.t.,例例1.3 营养配餐问题营养配餐问题成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问如何选择食品才能在满足营养的前提下使购买食品的费用最小？例例1.3 数学模型数学模型例1.4有限水资源条件下种植结构优化问题(教材例2-2)n一个灌区耕地面积1000hm2，可用灌溉水量360万m3。在安排种植计划时考虑两种粮食作物A,B，其灌溉定额分别为3000m3/hm2，6000m3/hm2，每公顷净收入分别为4500元/hm2，6000元/
11、hm2。问如何安排两种作物的种植面积才能使整个灌区净收入最大？例1.4数学模型n以作物A,B的种植面积x1,x2为决策变量。则问题的提出问题的提出以上几例都有一些共同的特征：用一组变量表示某个方案，一般这些变量取值是非负的。存在一定的约束条件，可以用线性等式或线性不等式来表示。都有一个要达到的目标，可以用决策变量的线性函数来表示。满足以上条件的数学模型称为线性规划模型。线性规划模型的一般形式如下：小结小结. .线性规划问题的特征n线性规划模型的特征上述问题可看出线性规划问题有如下特点：n1用一组未知变量（）表示某一方案，这组未知变量的一组确定值就代表一个具体的方案，这些未知变量称为决策变量。通
12、常，根据决策变量所代表的事物的特点可以对变量的取值加以约束，例如非负约束、整数约束等。n2存在一定的限制条件，通常称为约束条件，这些约束条件可以用一组线性等式或者线性不等式来表达。n3有一个目标要求，并且这个目标可以表示为决策变量的线性函数，称为目标函数。按所研究问题的不同，要求目标函数实现最大化或者最小化。小结：线性规划问题的特征128s.t.16120决策变量目标函数约束条件小结：小结：线性规划问题的规范描述n线性规划问题的规范描述s.t.约束条件目标函数决策变量价值系数技术系数限定系数3.线性规划问题的标准型(SLP)n为什么要规定线性规划问题的标准型？n便于比较，便于交流，便于计算机处
13、理n可以只针对这种标准形式来研究它的求解方法，对于不同形式的线性规划问题，只需要将其转换为标准型，然后再按标准型的求解方法求解。线性规划问题的标准型(SLP)s.t极大化型约束方程为等式所有的决策变量为非负值约束方程的右端项系数为非负值nSLP的特征()1、极大化型2、约束方程为等式3、所有的决策变量为非负值4、约束方程的右端项系数为非负值n形式标准型的和式标准型的矩阵式各种符号的定义非标准形式如何写成标准形式一、目标函数是极小化的转化四、决策变量有上下界的转换例1.1的标准型s.t例1.2的标准型s.t习题n附录A2，第二章习题2.2线性规划问题的图解法n图解法n可行解及可行解集的特性n线性
14、规划问题解的特点n单纯形法的思路1.2 线性规划问题的图解法图解法就是利用坐标图来求解线性规划问题例例：配配餐餐问问题题 营养学家指出，成人日常饮食每天至少要摄入营养学家指出，成人日常饮食每天至少要摄入7575克碳水化克碳水化合物、合物、6060克蛋白质和克蛋白质和6060克脂肪。现有甲乙两种食物，在每千克克脂肪。现有甲乙两种食物，在每千克甲中含甲中含105105克碳水化合物，克碳水化合物，7070克蛋白质、克蛋白质、140140克脂肪，花费为克脂肪，花费为2828元，在每千克乙中含元，在每千克乙中含105105克碳水化合物，克碳水化合物，140140克蛋白质、克蛋白质、7070克脂克脂肪，花
15、费为肪，花费为2121元，请设计出符合营养学家要求并且花费最少的元，请设计出符合营养学家要求并且花费最少的营养配餐。营养配餐。 整理数据，列表得：食物（千克）碳水化合物（千克）蛋白质（千克）脂肪（千克）甲0.1050.070.14乙0.1050.140.07最少摄入量0.0750.060.06解：设每天选择甲千克，乙 千克。即：目标函数：z=28x+21y约束条件0 0作出二元一次不等式组所表示的平面区域xy0 0设z=28x+21y，求z的最小值。第一步：点（x，y）在此平面区域内运动时，如何求z=28x+21y的最小值。第二步：由z=28x+21y得：直线与此平面区域有公共点，求z的最小值
16、。，当这族第三步：在区域内找一点，使直线经过该点时在y轴上的截距最小。MyxN解方程组：得M 点的坐标为所以答：每天食用食物A 143g，食物B 571g，能够满足日常饮食要求，又使花费最低，最低成本为16元。例1变式：若在上题条件之下想要食物总量最少，应怎样找到符合医生要求且摄入食物总量最少的营养配餐？ 讨论：相对于例1，只有目标函数发生变化，设z为进食总量0 0设z=x+y，求z的最小值。当直线z=x+y与直线7x+7y=5重合时在y轴上的截距最小，所以线段MN上所有点表示的解都是最优解。xyMN思考：n 实际的线性规划问题中可能还会出现其他情况，比如要求解为整数等等，我们该怎么处理呢？
17、例题分析例例2 要要将将两两种种大大小小不不同同规规格格的的钢钢板板截截成成A、B、C三三种种规规格格，每每张钢板可同时截得三种规格的小钢板的块数如下表所示张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 解：解：设需截第一种钢板设需截第一种钢板x张，第一种钢板张，第一种钢板y张，则张，则 规格类型规格类型钢板类型钢板类型第一种钢板第一种钢板第二种钢板第二种钢板A规格规格B规格规格C规格规格2121312x+y15,x+2y18,x+3y27,x0y0 作出可行域（如图）作出可行域（如图）目标函数为目标函数为 z=x+y今需要今需要A,B,C三种规格的成品分别为三种规格的成品分别为15，1
18、8，27块，问各截这两种块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。钢板多少张可得所需三种规格成品，且使所用钢板张数最少。返回返回X张张y张张例题分析x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, xN*y0 yN*直线直线x+y=12经过的经过的整点是整点是B(3,9)和和C(4,8)，它们是最优解，它们是最优解. 作出一组平行直线作出一组平行直线z=x+y，目标函数目标函数z= x+y返回返回B(3,9)C(4,8)A(18/5,39/5)当直线经过点当直线经过点A时时z=x+y=11.4,x+y=12
19、解得交点解得交点B,C的坐标的坐标B(3,9)和和C(4,8)调整优值法调整优值法2 4 6181282724681015但它不是最优整数解但它不是最优整数解.作直线作直线x+y=12答（略）答（略）例题分析x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0, xN*y0 yN*经经过过可可行行域域内内的的整整点点B(3,9)和和C(4,8)且且和和原原点点距距离离最最近近的的直直线线是是x+y=12，它们是最优解，它们是最优解.答答:(略略)作出一组平行直线作出一组平行直线t = x+y，目标函数目标函数t = x+y返回返回B(3,9
20、)C(4,8)A(18/5,39/5)打网格线法打网格线法在可行域内打出网格线，在可行域内打出网格线，当直线经过点当直线经过点A时时t=x+y=11.4,但它不是最优整数解，但它不是最优整数解，将直线将直线x+y=11.4继续向上平移，继续向上平移，1212182715978不等式组不等式组 表示的平表示的平面区域内面区域内的的整数点整数点共有（共有（ ）个）个巩固练习巩固练习1:1 2 3 4 xy432104x+3y=12在可行域内找出最优解、线性规划整在可行域内找出最优解、线性规划整数解问题的一般方法是：数解问题的一般方法是：1.若区域若区域“顶点顶点”处恰好为整点，那么它就是最优解；处
21、恰好为整点，那么它就是最优解；（在包括边界的情况下）（在包括边界的情况下）2.若区域若区域“顶点顶点”不是整点或不包括边界时，应先求出不是整点或不包括边界时，应先求出该点坐标，并计算目标函数值该点坐标，并计算目标函数值Z，然后在可行域内适当，然后在可行域内适当放缩目标函数值，使它为整数，且与放缩目标函数值，使它为整数，且与Z最接近，在这条最接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续对应的直线中，取可行域内整点，如果没有整点，继续放缩，直至取到整点为止。放缩，直至取到整点为止。3.在可行域内找整数解，一般采用平移找解法，即打网在可行域内找整数解，一般采用平移找解法，即打网络、找
22、整点、平移直线、找出整数最优解络、找整点、平移直线、找出整数最优解n图解法求解线性规划问题的一般步骤n建立直角坐标系n找出所有约束条件所构成的公共区域，即可行域；n改变目标函数值Z，使等值线平行移动，当移动到可行域上的某一点时，如果再移动就将脱离可行域，则该点使目标函数达到极值，该点坐标则为最优解。O12345613245678n建立直角坐标系PQRS123456132456O78n找出所有约束条件所构成的公共区域，即可行域；可行域PQRS123456132456O78(4,2)n改变目标函数值Z，使等值线平行移动，当移动到可行域上的某一点时，如果再移动就将脱离可行域，则该点使目标函数达到极值
23、，该点坐标则为最优解。可行域n思考：当目标函数改为时，最优解是什么？线性规划问题解的特点n若线性规划问题存在唯一的最优解，那么它必定在顶点上（基本可行解）n若线性规划问题存在多个最优解，那么必有几个相邻的顶点是最优解，其它最优解可以表示成这几个顶点的凸组合。n若一个顶点的目标函数值比它的相邻顶点的目标函数值要好的话，它就是最优解。图解法的优缺点n图解法利用坐标图来求解线性规划问题，因此只适用于非常简单的情况n约束条件较少n决策变量不超过两个。三个决策变量即是一个空间问题，图解法在表达上有难度n对于一般问题，难以求得精确解。n但是，对于大量的管理实践问题，约束条件很多，决策变量三个以上，需要得到
24、精确解，显然用图解法难以满足要求，1947年，美国人但泽（Danlzig）提出了一种求解一般线性规划问题的方法，单纯形法单纯形法。 单纯形法的思路n从某个顶点开始n向目标函数值更好的邻近顶点移动n判断此顶点是否为最优解：检查它是否比它的临近顶点的目标函数值都好，若是，则是最优解；若不是，则重复上述第二步。2.3线性规划问题的单纯形解法n线性规划问题解的基本概念n单纯形解法n解的最优性检验n表解形式的单纯形法n单纯形解法的一些问题及其处理方法一、线性规划问题解的基本概念n可行解n最优解n基及基本解n可行基及基本可行解n代数解与几何解的关系n单纯形法的要点线性规划问题的解一、可行解满足LP模型的约
25、束条件且满足非负条件的解。例：二、最优解使目标函数达到最大的可行解（存在多个可行解，从中选择最优的解）三、基和基解1、基：约束方程系数矩阵中任意m列所组成的mm阶非奇异非奇异子矩阵。基矩阵为：2、基本解令非基变量为零，求解由基变量组成的方程组所得到的解。互换变换、倍乘变换、消去变换四、基本可行解和可行基基本可行解：满足非负条件的基解（可行基所对应的解）可行基：基本可行解对应的基可行解基本解基本可行解结论：若LP问题存在最优解，则一定可以在基本可行解中找到。二、单纯形解法nStep1:建立基本可行解nStep2:计算变量的检验数nStep3:判断是否最优nStep4:若不是最优解，换基nStep
26、5:计算新的基本可行解nStep6:迭代计算直到求得最优解或可判断无最优解为止*可行域的顶点对应LP问题的基本可行解*LP的最优解一定可以在基本可行解中找到思路建立初始基本可行基n对于约束条件的右手项（限定系数）小于等于（）的情况，通过标准化，每个约束条件的左边加上左边加上一个松弛变量，该松弛变量的系数矢量是单位矢量。n当约束条件的右手项（限定系数）都是小于等于时，可令松弛变量为初始基本松弛变量为初始基本可行基可行基，于是可以很方便地得到初始基本可行解。标准型线性方程组的增广矩阵表示n它的初始可行基初始基本可行解n初始基变量是松弛变量。n初始可行解（只要满足非负条件）n初始基本可行解（非基变量
27、取值为零时）n目标函数与最优性检验第一次迭代n确定入基变量入基变量，应当是（Why），它的系数是4。n确定出基变量出基变量，方法如下，得(Why)对目标函数贡献大（价值系数高）受资源的约束，400所对应的资源最紧张确定新基和求解新的基本可行解n新基n新的基变量：n新的基本可行解新的基本可行解和目标函数n基本可行解n目标函数第二次迭代n确定入基变量：n确定出基变量：不考虑零与负值确定新基和求解新的基本可行解v新基v新的基变量：v新的基本可行解新的基本可行解和目标函数v基本可行解v目标函数第三次迭代v确定入基变量：v确定出基变量：不考虑零与负值确定新基和求解新的基本可行解n新基n新的基变量：n新的
28、基本可行解n基本可行解n目标函数n这是最优解。最大目标函数值为2600。新的基本可行解和目标函数三、关于解的最优性检验n设线性规划模型为n令基为B，并作相应的矩阵分割，从约束条件得n代入目标函数n得n令n则目标函数可写成n可用判断是否最优解，它叫做检验数检验数。令则可用判断是否最优解，它叫做检验数检验数。对于线性规划问题标准型，最优性判别条件所有检验数均小于等于零。如果是求最小问题，则最优性判别条件是所有检验数均大于等于零。检验数是用非基变量表示基变量，带入目标函数的表达式中得来的非基变量的系数。它的含义是对应非基变量如果取得一个大于零的值时，能给目标函数增大的量为该值的检验数倍。对最大化问题
29、，如果检验数均小于等于零，意味着再进行迭代，也不能使目标函数增大了。用非基变量表示目标函数的表达式：Z=Z0+(Cj-Zj)XnXn为非基变量，Cj-Zj为检验数，Z0为求出的基可行解.从表达式很明显看出只有Cj-Zj0,Z达到最大值,即最优解.单纯形法中的检验数的计算单纯形法中的检验数的计算用基变量在目目标函函数数中的系数，乘以你要算得那个变量对应的系数列的各个值，并求和，再减去你要算得那个变量在目目标函函数数中对应的系数，就是检验数四、表解形式的单纯形法n表的格式n在表上的计算方法n表上计算的原理n表解单纯形法的实例初始单纯形表430000001600250040025122.501000
30、1000180050040043000单纯形表法求解430000001600250040025122.50100010001800500400043000第一次换基迭代4300000480050040000122.50100010-2-514002000不算不算16000300-4330202.54016000800+0500+4400第二次换基迭代43000034400200400001010100-0.80.402-21200负值负值 不算不算4002200000-1.22第三次换基迭代：最优解430000342006002000010100.51-0.5-0.4-0.40.4100260
31、000-1-0.40五、单纯形解法的一些问题及其处理方法n换入变量的选择问题n下标最先原则(勃兰特法则)n检验数最大原则n换出变量的选择问题n比值最小原则n下标最先原则(勃兰特法则)n无换出变量的情况无界解n非基变量检验数有等于零多个最优解的情况n退化解与无可行解的情况单纯形法的进一步讨论单纯形法的进一步讨论1、无界解、无界解Ozcj2300bcBxBx1x2x3x400x3x41-110-310124j230020x1x41-1100-231210j05-20结论：结论：若若j0,对应的系数列向量对应的系数列向量0，则该，则该LP存在无存在无界解。界解。2、多个解cj41400bcBxBx1
32、x2x3x300x3X42710720121213j41400140x2x42/711/7045/70-2/71315j00-20z=4221/27/3144x2x1017/45-2/45102/457/457/37/3j00-20z=4221/2结论：若某个非基变量的检验系数为零，则该LP存在多个最优解。当所有的检验数全部小于等于零时,若有某个非基变量的检验数也是零,则该线性规划有无穷多组解,否则有唯一解.3、退化解cj201.5000bcBxBx1x2x3x4x5x6000x4x5x61-10100201010111001243223j201.5000200x1x5x61-10100021
33、-210021-101201j021.5-200基本可行解中基变量等于零*在单纯形法的计算过程中，确定出基变量时存在两在单纯形法的计算过程中，确定出基变量时存在两个或两个以上的最小比值，这时会出现退化解个或两个以上的最小比值，这时会出现退化解。特征：基本可行解中，基变量等于零特征：基本可行解中，基变量等于零*有时，退化会造成计算过程的循环，永远达不到最有时，退化会造成计算过程的循环，永远达不到最优解优解。*用勃兰特法则一定可以避免出现循环用勃兰特法则一定可以避免出现循环为避免循环,常采用1976年R.G.Bland提出Bland法则:单纯形表中有若干个检验数大于零大于零时,取取下标号小下标号小
34、的非基变量入基入基;用法则选取出基出基变量时,若比值相同,则选取下标号小下标号小的基变量出基.勃兰特（Bland）法则4、无可行解（大M法）cj2030000-MbcBxBx1x2x3x4x5x600-Mx3x4x631010001001001100-111503040j20+M30+M00-M03020-Mx2x1x6011/10-3/100010010000-1/10-7/10-116304j003-M/10-11-7M/10M0xBx1x2x3x4x5bx2x3x5110-40-201-30300a153dj-3000讨论题讨论题在求解极大化在求解极大化LP问题中，得到如下单纯形表：问题
35、中，得到如下单纯形表：1、当前解为最优解时，各参数应满足的条件；、当前解为最优解时，各参数应满足的条件；2、原问题存在无界解时，各参数应满足的条件；、原问题存在无界解时，各参数应满足的条件；3、原问题存在多个解时，各参数应满足的条件；、原问题存在多个解时，各参数应满足的条件；4、当、当x4作为进基变量取代作为进基变量取代x5时，目标值的增量为多少？时，目标值的增量为多少？结论：结论：若基变量中有非零的人工变量，则该若基变量中有非零的人工变量，则该LP无可行解。无可行解。多个最优解无界解1、d0,0,a03、d0,=0,a04、六、六、(小结小结)单纯形法的矩阵表示单纯形法的矩阵表示=非基变量非
36、基变量基变量基变量=非基变量非基变量基变量基变量B-1bIBNI2.4 非标准线性规划问题的解法非标准线性规划问题的解法n目标函数求极小问题目标函数求极小问题n等式约束等式约束大大M方法方法n大于等于的约束条件大于等于的约束条件n常数项为负值的情况常数项为负值的情况n允许变量为负值的情况允许变量为负值的情况一、目标函数求极小问题n方法1：目标函数标准化(变为极大问题)n方法2：检验数最优解检验规则标准型二、等式约束大M法n人工变量n标准化后n可见没有初始单位单位可行基，加人工变量n大M法n然后用单纯形法求解（本例）初始单纯形表3500-Mb00-M4121810302210001000146-
37、18M3+3M 5+2M000第一次迭代3500-Mb30-M412610002210-30100016312-6M05+2M-3-M00第二次迭代3500-Mb30546310000113-1.50100-10.54227004.50-M-2.5第三次迭代3500-Mb305226100001010-1/31/31/21/3-1/3036000-1.5-M-1大M法的要点1、人工变量的引入2、用大M法处理人工变量当目标函数求最大，则为-M当目标函数求最小，则为M三、大于等于的约束条件三、大于等于的约束条件n减去剩余变量化为等式减去剩余变量化为等式n加人工变量加人工变量n用大用大M法法n例如例
38、如四、右手常数项为负值的情况n两边同乘以-1n标准化：加上松弛变量或减去剩余变量n必要时加上人工变量n加人工变量时，用大M法n例如五、变量允许为负值的情况五、变量允许为负值的情况n标准化处理标准化处理n必要时用人工变量必要时用人工变量n用人工变量时，再用大用人工变量时，再用大M法法n例如例如n处理以后成为处理以后成为4、无可行解cj2030000-MbcBxBx1x2x3x4x5x600-Mx3x4x631010001001001100-111503040j20+M30+M00-M03020-Mx2x1x6011/10-3/100010010000-1/10-7/10-116304j003-M
39、/10-11-7M/10M0结论：结论：若基变量中有非零的人工变量，则该若基变量中有非零的人工变量，则该LP无可行解。无可行解。用计算机软件求解线性规划问题关于线性规划问题的求解，有许多好的专业软件和商务软件，通过计算机可十分方便地完成求解过程。最简便易行的求解软件是Excel，下面介绍其使用方法。（1）建立Excsl工作表。用一组单元格表示变量，作为可变单元格（空）；用几组单元格分别表示各约束条件和目标函数的系数；用一些单元格输入公式表示各组系数和变量的关系。（2）打开工具栏中的“规划求解”对话框，指定存有目标函数的单元格为目标单元格，指定表示变量的单元格为可变单元格，建立约束条件。（3）在
40、规划求解对话框中按下“求解”按钮，即可求出最优解和最优值。推出规划求解对话框。2.5对偶问题对偶问题1、对偶问题的提出2、对称的对偶线性规划3、对偶的基本性质4、对偶单纯形法5、对偶问题的经济解释nDualitytheory研究线性规划中原始问题与对偶问题之间关系的论。n发展简史:在线性规划早期发展中最重要的发现是对偶问题，即每一个线性规划问题(称为原始问题)有一个与它对应的对偶线性规划问题（称为对偶问题）。1928年美籍匈牙利数学家J.von诺伊曼在研究对策论已发现线性规划与对策论之间存在着密切的联系。两零和对策可表达成线性规划的原始问题和对偶问题。一.对偶问题的提出例：产品原材料 工时定额
41、 单位产品收益A2210B31.512现有资源300180问1：如何生产使总收益最大？问2：若企业把资源出租，应如何确定合理的价格？出租可获得的收益不得低于自行生产的收益在满足上述要求的前提下，所定的价格对方愿意接受目标函数：约束条件：非负条件：产品原材料 工时定额 单位产品收益A2210B31.512现有资源300180LPDLP2、价值系数资源系数（右项）3、资源系数（右项）价值系数4、约束方程=5、目标函数max目标函数min原始问题maxz=CXs.t.AXbX0对偶问题minw=Ybs.t.YACY0maxbACCTATbminmnmn(LP)(DLP)LP与DLP的对偶关系一、标准
42、形式的对偶关系原问题与对偶问题的关系原问题与对偶问题的关系 n线性规划原问题与对偶问题之间的形式变换关系可以由表予以概述。原问题（或对偶问题） 对偶问题（或原问题） 目标函数 目标函数 变量 个数n00无约束 约束方程 个数n= 约束方程 个数m= 变量 个数m00无约束 约束方程右端项 目标函数中变量的系数 目标函数中变量的系数 约束方程右端项 表 利用表所描述的变换关系，可写出任何一个线性规划问题的对偶问题。譬如，对于线性规划问题其对偶问题为n对偶问题的基本性质对偶问题的基本性质 对称性：即对偶问题的对偶是原问题。 弱对偶性：即若 是原问题的可行解， 是对偶问题的可行解，则存在关系： 。
43、无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。 对偶定理：若原问题有最优解，那么对偶问题也有最优解，而且它们的最优目标值相等。 松紧定理：若 和 分别为原问题与对偶问题的可行解，则它们为最优解的充要条件为 设原问题是其对偶问题是 互补松弛性：若 和 分别是原问题和对偶问题的可行解。那么， 和 ，当且仅当 和 为最优解。 则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对应关系如表。0表n二、对称型对偶线性规划二、对称型对偶线性规划n线性规划具有对称形式的两个条件线性规划具有对称形式的两个条件n所有变量非负所有变量非负n约束条件都是不等式，且目标函数极大化时，约束条
44、件都是不等式，且目标函数极大化时，不等式方向为不等式方向为，极小化时，为，极小化时，为n原原对偶线性规划的对应关系对偶线性规划的对应关系 n三、非对称的线性规划的对偶问题三、非对称的线性规划的对偶问题n等式约束的对偶关系等式约束的对偶关系n其它非对称约束的对偶关系其它非对称约束的对偶关系minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38x1+3x2-x315=x10, x20, x3无非负要求(unr)例：对偶线性规划对偶线性规划minz=2x1+4x2-x3s.t.3x1-x2+2x36-x1+2x2-3x3122x1+x2+2x38
45、x1+3x2-x315maxw=6y1+12y2+8y3+15y4s.t.3y1-y2+2y3+y42-y1+2y2+y3+3y442y1-3y2+2y3-y4-1y10,y2,y30,y40=unr=x10x20x3:unr(无非负约束)q原始问题变量变量的个数(3)等于对偶问题约束条件约束条件的个数(3)；原始问题约束条件约束条件的个数(4)等于对偶问题变量变量的个数(4)。q原始问题变量的性质影响对偶问题约束条件的性质，用表示原始问题约束条件的性质影响对偶问题变量的性质，用表示三、对偶问题的基本性质1、对称性对偶问题的对偶问题是原问题对偶变换对偶变换代数变换代数变换2、弱对偶性揭示目标函
46、数值的关系推论： 1）极大化问题任一可行解的目标函数值是其对偶问题最优值的下界。2）极小化问题任一可行解的目标函数值是其对偶问题最优值的上界。例：例：1）原问题任一可行解X=（1111）（DLP）目标值z=1010是DLP问题最优目标值的下界2）对偶问题任一可行解Y=（11）目标值w=4040是LP问题最优目标值的上界弱对偶性的推论弱对偶性的推论若若LP有最优解，则有最优解，则DLP也有最优解，且它们的目标值相等。也有最优解，且它们的目标值相等。原始对偶问题目标函数值之间的关系1、可行解的目标函数值之间的关系设X、Y分别是原始问题和对偶问题的可行解z=CXYAXYb=w2、最优解的目标函数值之
47、间的关系设X*、Y*分别是原始问题和对偶问题的最优解z=CX*=Y*AX*=Y*b=w4、对偶定理（揭示最优解之间的关系）若LP有最优解，则DLP也有最优解，且他们的目标值相等。（松弛变量检验数的相反数）对偶可行最优性代入目标函数由对偶定理可知，当原始问题获得最优解时，对偶问题同时获得最优解，其最优解可以从原始变量的最终单纯形表中直接读出。cj23100bcBxBx1x2x3x4x523x1x210-14/3-1/3012-1/31/312j00-3-5/3-1/3Z=8请确定对偶问题的最优解小结原问题(max)对应关系对偶问题(min)有最优解有最优解无界解不可行不可行无界解（无可行解）（无
48、可行解）（无界解）（无可行解）四、对偶单纯形法一、思路1.单纯形法：迭代过程始终保持B的可行性（最小规则），逐步满足最优性。从线性规划标准型的一个基本可行解出发，逐步迭代，使目标函数值不断改进，直到取得最优解为止，在整个运算过程中，始终保证解的可行性，即始终有先从非基变量中确定进基进基变量，再从基变量中选择出出基基变量。2.对偶单纯形法：迭代过程始终保持最优性（对偶可行性），再逐步满足可行性。先从基变量中确定出基出基变量，再从非基变量中选择进进基基变量3、换基迭代1.化为标准型,建立初始单纯形表，所有检验数04、回到第2步(若所有aij0,则该LP无可行解）二、计算步骤cj-1-2-3000b
49、cBxBx1x2x3x4x5x6000x4x5x6-11-11001120100-11001-48-2j-1-2-3000j13x1x5x6-1001-11-100402111040-11001-2j0-3-2-100j3 cj-1-2-3000bcBxBx1x2x3x4x5x6-100x1x5x61-11-1000211100-1100144-2j0-3-2-100j3x1x5x2-10-2100-10-16003112001-100-12j00-5-10-3练习cj-3-5-400bcBxBx1x2x3x4x500x4x5-3-1-210-2-3-101-60-b2j-3-5-400j15
50、2-30x1x511/32/3-1/300-7/31/3-2/312040-b2j0-4-2-10-30x1x413/21/20-1/207/2-1/21-3/2b2/2j0-1/2-5/20-3/2*对偶单纯形法的适用前提能解决形如以下的LP问题：五、对偶问题的经济解释五、对偶问题的经济解释一、原始问题是利润最大化的生产计划问题一、原始问题是利润最大化的生产计划问题单位产品的利润单位产品的利润产品产量产品产量总利润总利润资源限量资源限量单位产品消耗的资源单位产品消耗的资源剩余的资源剩余的资源消耗的资源消耗的资源二、二、对偶问题对偶问题资源限量资源限量资源价格资源价格总利润总利润对偶问题是资源
51、定价问题，对偶问题的最优解对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为称为m种资源的影子价格（种资源的影子价格（ShadowPrice）原始和对偶问题都取得最优解时，原始和对偶问题都取得最优解时，最大利润最大利润maxz=minw三、影子价格三、影子价格影子价格越大，说明这种资源越是相对紧缺影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子如果最优生产计划下某种资源有剩余，这种资源的影子价格一定等于价格一定等于0如果资源的影子价格大于如果资源的影子价格大于0，最优生产
52、计划下该种资源全，最优生产计划下该种资源全部用完部用完第第i种资源全部用完种资源全部用完第第i种资源的影子价格大于种资源的影子价格大于0第第i种资源有剩余种资源有剩余第第i种资源的影子价格为种资源的影子价格为0例1.1的对偶问题初始单纯形表160025004000000-4-3-2-2-5-2.5-10100101600250040000800500400第一次迭代160025004000040004-32-25-2.510-1001160080050004000400200第二次迭代16002500400004002500-21.2-20.80110-102-0.42200400004002
53、00200400第三次迭代16002500400001600250010.41001-0.50.40.5-0.4-10.4260000200200600原问题最优解对偶单纯形法的用途1、用于初始基本解不是可行解，但检验数符合最优条件的问题求解。2、对于变量较少，而约束条件数较多的问题，可先得到它的对偶问题，再用对偶单纯形法求解对偶问题，达到简化计算的目的。3、用于灵敏度分析。对偶单纯形法有以下优点对偶单纯形法有以下优点：n(1)(1) 初始解可以是非可行解，当检验数都为负数时初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，就可以进行基的变换，这时不需要加入人
54、工变量，因此可以简化计算。因此可以简化计算。n(2)(2) 当变量多于约束条件，使用对偶单纯形法计算当变量多于约束条件，使用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，件很多的线性规划问题，可先将它变换成对偶问题，然后用对偶单纯形法求解。然后用对偶单纯形法求解。n(3) 在灵敏度分析及求解整数规划的割平面法中，在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法。有时需要用对偶单纯形法。 对偶单纯形法的局限性：对偶单纯形法的局限性：对大多数线性规划问题，对大多数线性规划问题，很难
55、找到一个初始可行基，因而这种方法在求解线很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。性规划问题时很少单独应用。 原规划与对偶规划之间的关系n1.1.原规划若有原规划若有n n个变量，则对偶规划有个变量，则对偶规划有n n个约束条件；原规划个约束条件；原规划有有m m个约束条件，则对偶规划有个约束条件，则对偶规划有m m个变量。个变量。n2.2.若原规划的目标函数是求极大值，则对偶规划的目标函数若原规划的目标函数是求极大值，则对偶规划的目标函数是求极小值，且这两个极值相等。是求极小值，且这两个极值相等。n3.3.原规划目标函数中变量的系数等于对偶规划中相应约束条原规划目
56、标函数中变量的系数等于对偶规划中相应约束条件的右端常数项；原规划约束条件右端常数项等于对偶规划件的右端常数项；原规划约束条件右端常数项等于对偶规划目标函数中相应变量的系数。目标函数中相应变量的系数。n4.4.原规划约束条件中不等号与对偶规划约束条件的不等号方原规划约束条件中不等号与对偶规划约束条件的不等号方向相反。向相反。n5.5.原规划中一个等式约束，对应于对偶规划的一个符号无限原规划中一个等式约束，对应于对偶规划的一个符号无限制的变量；反之，当一个原规划的变量无符号限制，它的对制的变量；反之，当一个原规划的变量无符号限制，它的对偶约束条件就是等式约束。偶约束条件就是等式约束。1.6 灵敏度
57、分析灵敏度分析n单纯形法的矩阵表示单纯形法的矩阵表示n系数变化的灵敏度分析系数变化的灵敏度分析n决策变量增减的灵敏度分析决策变量增减的灵敏度分析n约束条件增减的灵敏度分析约束条件增减的灵敏度分析n灵敏度分析小结灵敏度分析小结单纯形法的矩阵表示单纯形法的矩阵表示灵敏度分析（优化后分析）灵敏度分析（优化后分析）一、参数的可变性一、参数的可变性(cj,bi,aij)二、灵敏度分析的内容二、灵敏度分析的内容1、参数的变化对原最优解有什么影响？原最优解是否、参数的变化对原最优解有什么影响？原最优解是否仍为最优解仍为最优解?2、参数在什么范围变化时，原最优解保持不变？、参数在什么范围变化时，原最优解保持不
58、变？3、当原最优解已不再最优时，应如何利用原单纯形表，、当原最优解已不再最优时，应如何利用原单纯形表，以最简捷的方法求得新的最优解。以最简捷的方法求得新的最优解。三、最优性分析三、最优性分析四、目标函数四、目标函数cj的变化的变化1、非基变量、非基变量cj的变化的变化cj23100bcBxBx1x2x3x4x523x1x210-14/3-1/3012-1/31/312j00-3-5/3-1/3Z=8欲使原问题的最优性保持不变，欲使原问题的最优性保持不变，若要保持最优性不变若要保持最优性不变一般情况：一般情况：2、基变量、基变量cj的变化的变化cj23100bcBxBx1x2x3x4x523x1
59、x210-14/3-1/3012-1/31/312j00-3-5/3-1/3Z=81）讨论）讨论c2的变化范围的变化范围2）一般情况对于所有的非基变量都应满足上述不等式,有(n-m)个,则cj23100bcBxBx1x2x3x4x523x1x210-14/3-1/3012-1/31/312j00-3-5/3-1/3Z=8问：问：c2由由3变为变为1时，应如何修改原最优计划？时，应如何修改原最优计划？cj21100bcBxBx1x2x3x4x521x1x210-14/3-1/3012-1/31/312j001-7/31/3Z=43611110036-11x1x520xBZ=60-1-1-20jx
60、1x2x3x4x5cBb21100cj五、资源系数五、资源系数bi的变化的变化cj23100bcBxBx1x2x3x4x500x3x4111101470139j23100Z=023x1x210-14/3-1/3012-1/31/312j00-3-5/3-1/3 Z=8初始单纯形表最终单纯形表B的逆包含了矩的逆包含了矩阵变换的信息阵变换的信息与初始单纯形表中单位矩阵所在的位置对应2、分别讨论、分别讨论b1由由3变为变为9，b2由由9变为变为15时对原最优解的影响时对原最优解的影响对原问题的可行性无影响对原问题的可行性无影响但是最优解发生了变化但是最优解发生了变化3、一般情况、一般情况4、举例、举
61、例1）确定）确定b1、b2的变化范围的变化范围2）b2由由9变为变为15时，应如何修改原最优计划？时，应如何修改原最优计划？cj23100bcBxBx1x2x3x4x523x1x210-14/3-1/3012-1/31/3-14j00-3-5/3-1/3j31 03x5x2-303-411111033j-10-2-30Z=9cjee-1016-100bcBxBx1x2x3x4x5-1016x1x210-1-1201-1-1162j00564Z=-282、非基变量、非基变量cj的变化：的变化：3、基变量、基变量cj的变化：的变化：若最优基发生变化，用单纯形法修改。若最优基发生变化，用单纯形法修改
62、。4、资源系数、资源系数bi的变化：的变化：若最优基发生变化，用对偶单纯形法修改。若最优基发生变化，用对偶单纯形法修改。1、分析思路、分析思路小结小结1、非基变量对应的系数、非基变量对应的系数六、约束方程系数六、约束方程系数aij（非基变量）的变化非基变量）的变化求求a13的变化范围的变化范围cj23100bcBxBx1x2x3x4x523x1x210-14/3-1/3012-1/31/312j00-3-5/3-1/3Z=8最终单纯形表中，基变量没有发生变化可行性不发生变化，影响最优性可行性不发生变化，影响最优性1、一般情况、一般情况前例，求出前例，求出a13的变化范围的变化范围cj23100
63、bcBxBx1x2x3x4x523x1x210-14/3-1/3012-1/31/312j00-3-5/3-1/3Z=82、基变量对应的系数、基变量对应的系数求求a11由由1变为变为2时，最优解的变化时，最优解的变化cj23100bcBxBx1x2x3x4x523x1x210-14/3-1/3012-1/31/312j00-3-5/3-1/3Z=8最终单纯形表中，显然原来的基变量的系数列向量未能组成单位矩阵的形式，即没有完成基交换，必须继续进行线性变换cj23100bcBxBx1x2x3x4x523x1x210-14/3-1/3012-1/31/312j00-3-5/3-1/3Z=8cj231
64、00bcBxBx1x2x3x4x523x1x27/30-14/3-1/3-1/312-1/31/312jZ=8cj23100bcBxBx1x2x3x4x523x1x210-3/74/7-1/70113/7-1/72/73/715/7j00-26/7-5/7-4/7Z=51/7因为技术退步了，所以最优解减少了七、决策变量增减的灵敏度分析七、决策变量增减的灵敏度分析 增加产品新品种相当于增加一列1、解决是否值得生产的问题2、解决若值得生产，生产计划应如何调整第一个问题可以直接使用机会成本分析法第二个问题需先计算新的一列当前值，再继续求解。增加新产品相当于增加一个决策变量，系数矩阵也将增加一列n设研
65、制出一种新产品小旅行车，每辆用旅行车1.5吨，工时1.25小时，座椅0.25套，利润3千元，试问该新产品是否该投产？n第一种解法：设该车产量为，则利润成本利润成本0 0n第二种解法可见值得生产。但新的生产计划如何呢？检验数检验数0 0，继续迭代，继续迭代4300030342006002000010100.51-0.5-0.4-0.40.41000.51-0.25260000-1-0.40143000333440020030000101010-0.25-0.80.40.22-20.5100300000-20.4-2043000330480050020000122.5-0.510-0.25010-
66、2-51.510032000-1-2000得最优解，且可在两个角点上取得最优解，因此最优解有无穷多个。八、约束条件增减的灵敏度分析n增加约束条件意味着可行域的减小n在原最优解的表中增广一列和一行n此时检验数不变（对偶问题仍为可行解）n继续用对偶单纯形法求解关于约束条件增加灵敏度分析的例子n如果在例1.1中规定，发动机供应每年只有600台，这相当于增加一个约束条件如下：n设松弛变量为（未用完的发动机数），则n以为基变量，在最终单纯形表中增加一行和一列，则4300000340200600200-200001001000.51-0.5-0.5-0.4-0.40.4010000001260000-1-
67、0.400243000003400200400400001001000001-0.4-0.40.40100012-1-22200000-0.40-2增加约束后，最优目标函数值不会更好，一般会差一些。灵敏度分析总结n灵敏度分析步骤n灵敏度分析总是要修正甚至扩展单纯形表，修正后的单纯形表有四种可能（检验数与b列的四种组合），应分别对待处理。系数变化对解的结果的影响系数变化对解的结果的影响nC的变化只影响检验数（对偶问题的解），不影响原问题的基本解；nb的变化只影响原问题的基本解，不影响检验数（对偶问题的解）；nA中系数的变化可能既影响原问题的基本解，又影响对偶问题的解。n要深刻理解最终单纯形表中的
68、作用与意义n灵敏度分析时，要弄清楚：1）系数在什么范围内变化时，最优解（基）不变；2）若系数的变化使最优解发生变化，如何最简便地求得新最优解。例1.1中,若生产大轿车的钢材由2吨/辆变为3吨/辆，最优解如何变化呢？此时的系数矢量变为：因此在原最终的单纯形表中，的系数变为原最终单纯形表变为原最终单纯形表变为430000342006002000.510.50100.51-0.5-0.4-0.40.41002600继续求解43000034020040000101012-1-0.8-1.20.8100500220000-20.404300003040080050011.51.2501000.5-1.2
69、50011002400-0.50-1.500对于非基变量，例如现在的，可以分析在保证最优基不变时某个系数如的变化范围。当从3变为时，的检验数变为当时，最优基不变，即大轿车所用钢材从3吨/辆减少到2.67吨/辆时，仍应只生产载重汽车。当减少到2.67吨/辆以下时，就应考虑生产大轿车了。2.7随机线性规划n对象：随机系统（系统信息的描述是不确定的）n理论基础：概率理论（不确定性以概率形式表现出来）n概念：是研究线性随机系统最优化的理论与方法。n分类：概率规划（期望值规划）机会约束规划2.7.1概率规划目标函数单纯形法2.7.2机会约束规划目标函数确定右端项为随机参数2.8线性规划的应用 合理利用线
70、材问题：如何下料使用材最少。 配料问题：在原料供应量的限制下如何获取最大利润。 投资问题：从投资项目中选取方案，使投资回报最大。2.线性规划应用线性规划应用 一、线性规划- - 产品生产计划：合理利用人力、物力、财力等，使获利最大。 劳动力安排：用最少的劳动力来满足工作的需要。 运输问题：如何制定调运方案，使总运费最小。2.线性规划应用线性规划应用 数学规划的建模有许多共同点，要遵循下列原则： (1)容易理解。建立的模型不但要求建模者理解，还应当让有关人员理解。这样便于考察实际问题与模型的关系，使得到的结论能够更好地应用于解决实际问题。 (2)容易查找模型中的错误。这个原则的目的显然与(1)相
71、关。常出现的错误有：书写错误和公式错误。2.线性规划应用线性规划应用 (3)容易求解。对线性规划来说，容易求解问题主要是控制问题的规模，包括决策变量的个数和约束条件的个数。这条原则的实现往往会与(1)发生矛盾，在实现时需要对两条原则进行统筹考虑。2.线性规划应用线性规划应用 建立线性规划模型的过程可以分为四个步骤： (1)设立决策变量； (2)明确约束条件并用决策变量的线性等式或不等式表示； (3)用决策变量的线性函数表示目标，并确定是求极大（Max）还是极小（Min）； (4)根据决策变量的物理性质研究变量是否有非负性。2.线性规划应用线性规划应用 例3.123.12：某昼夜服务的公交线路每
72、天各时间段内所需司机和乘务人员数如下： 人力资源分配的问题人力资源分配的问题设司机和乘务人员分别在各时间段一开始时上班，并连续工作8h，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员? 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。目标函数：Min x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60 x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 0 人力资源分配的问题人力资源分配的
73、问题例3.13:3.13:某工厂要做100100套钢架，每套用长为2.9 2.9 m, m, 2.1m, 1.5m2.1m, 1.5m的圆钢各一根。已知原料每根长7.4 7.4 m m，问：应如何下料，可使所用原料最省？套裁下料问题套裁下料问题解:考虑下列各种下料方案（按一种逻辑顺序给出） 把各种下料方案按剩余料头从小到大顺序列出假设 x1,x2,x3,x4,x5 分别为上面前 5 种方案下料的原材料根数。我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 约束条件： s.t. x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3
74、x1 + x2 + 2x3+ 3x5 100 x1,x2,x3,x4,x5 0套裁下料问题套裁下料问题 例3.14:3.14:明兴公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配 三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如下表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？生产计划的问题生产计划的问题解：设 x1 ,x2 ,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4, x5 分别为由外协铸造再由本公司机加工和装配的甲、乙两种产品的件数
75、。 生产计划的问题生产计划的问题 求 xi 的利润:利润 = 售价 - 各成本之和可得到 xi（i=1,2,3,4,5）的利润分别为15、10、7、13、9元。 这样我们建立如下数学模型： 目标函数: Max 15x1+10x2+7x3+13x4+9x5 约束条件： s.t. 5x1+10x2+7x3 8000 6x1+4x2+8x3+6x4+4x5 12000 3x1+2x2+2x3+3x4+2x5 10000 x1,x2,x3,x4,x5 0 生产计划的问题生产计划的问题 例3.15:永久机械厂生产、三种产品，均要经过 A A、B B 两道工序加工。假设有两种规格的设备A A1 1、A A
76、2 2能完成 A A 工序；有三种规格的设备B B1 1、 B B2 2 、B B3 3能完成 B B 工序。可在 A A、B B的任何规格的设备上加工； 可在任意规格的A A设备上加工，但对B B工序, ,只能在B B1 1设备上加工； 只能在A A2 2与B B2 2设备上加工；数据如下表。问：为使该厂获得最大利润，应如何制定产品加工方案？ 生产计划的问题生产计划的问题解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量. 利润 = （销售单价 - 原料单价） 产品件数之和 - （每台时的设备费用设备实际使用的总台时数）之和。 生产计划的问题生产计划的问题这
77、样我们建立如下的数学模型:Max 0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123 s.t 5x111+10x2116000 （ 设备 A1 ） 7x112+9x212+12x31210000（ 设备 A2 ） 6x121+ 8x221 4000 ( 设备 B1 ） 4x122+11x322700 ( 设备 B2 ） 7x123 4000 （ 设备 B3 ）生产计划的问题生产计划的问题x111+ x112- x121- x122- x123 =
78、0 (产品在A、B工序加工的数量相等）x211+ x212- x221 = 0 (产品在A、B工序加工的数量相等）x312 - x322 = 0(产品在A、B工序加工的数量相等）xijk0, i=1,2,3; j=1,2; k=1,2,3生产计划的问题生产计划的问题 例3.13.16:6:某工厂要用三种原料1 1、2 2、3 3混合调配出三种不同规格的产品甲、乙、丙，数据如下表。问：该厂应如何安排生产，使利润收入为最大？配料问题配料问题配料问题配料问题 解：设 xij 表示第 i 种（甲、乙、丙） 产品中原料 j 的含量。这样我们建立数学 模型时，要考虑： 对于甲： x x1111，x x12
79、12，x x1313； 对于乙： x x2121，x x2222，x x2323； 对于丙： x x3131，x x3232，x x3333； 对于原料1 1： x x1111，x x2121，x x3131； 对于原料2 2： x x1212，x x2222，x x3232； 对于原料3 3： x x1313，x x2323，x x3333；目标函数： 利润最大，利润 = 收入 - 原料支出 约束条件：规格要求 4 个； 供应量限制 3 个。 Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 配料问题配料问题s.t. 0.5 x0.5 x1
80、111-0.5 x-0.5 x12 12 -0.5 x-0.5 x1313 0 0 （原材料1 1不少于50%50%） -0.25x-0.25x1111+0.75x+0.75x1212 -0.25x -0.25x1313 0 0 （原材料2 2不超过25%25%） 0.75 0.75x x2121-0.25x-0.25x2222 -0.25x -0.25x2323 0 0 （原材料1 1不少于25%25%） -0.5 x-0.5 x2121+0.5 x+0.5 x2222 -0.5 x -0.5 x2323 0 0 （原材料2 2不超过50%50%） x x1111+x+x2121+x+x31
81、31 100 ( 100 (供应量限制） x x1212+x+x2222+x+x3232 100 ( 100 (供应量限制） x x1313+x+x2323+x+x3333 60 ( 60 (供应量限制） x xijij0 ,i = 1,2,3; j = 1,2,30 ,i = 1,2,3; j = 1,2,3配料问题配料问题 例3.173.17：某部门现有资金200200万元，今后五年内考虑给以下的项目投资。已知：项目A A ：从第一年到第五年每年年初都可投资，当年末能收回本利110%110%；项目B B：从第一年到第四年每年年初都可投资，次年末能收回本利125%125%，但规定每年最大投资
82、额不能超过3030万元；项目C C：需在第三年年初投资，第五年末能收回本利140%140%，但规定最大投资额不能超过8080万元；项目D D：需在第二年年初投资， 第五年末能收回本利155%155%，但规定最大投资额不能超过100100万元。 投资问题投资问题 据测定每万元每次投资的风险指数如下表：据测定每万元每次投资的风险指数如下表：投资问题投资问题 a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？ b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？问：投资问题投资问题投资问题投资问题 解：1）确定决
83、策变量：连续投资问题 设 xij ( i = 15，j = 1、2、3、4)表示第 i 年初投资于A(j=1)、B(j=2)、C(j=3)、D(j=4)项目的金额。这样我们建立如下决策变量： A x11 x21 x31 x41 x51 B x12 x22 x32 x42 C x33 D x242）约束条件： 第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是： x11+ x12 = 200 第二年：B次年末才可收回投资故第二年年初的资金为1.1x11，于是： x21 + x22+ x24 = 1.1x11 第三年：年初的资金为1.1x21+1.25x12，于是 ： x31 + x
84、32+ x33 = 1.1x21+ 1.25x12 第四年：年初的资金为1.1x31+1.25x22，于是： x41 + x42 = 1.1x31+ 1.25x22 第五年：年初的资金为1.1x41+1.25x32，于是： x51 = 1.1x41+ 1.25x32 B、C、D的投资限制： xi2 30 ( i=1，2，3，4 )， x33 80，x24 100投资问题投资问题a)Max z=1.1x51+1.25x42+1.4x33+1.55x24s.t.x11+ x12 = 200 x21 + x22+ x24 = 1.1x11 x31 + x32+ x33 = 1.1x21+ 1.25x
85、12 x41 + x42 = 1.1x31+ 1.25x22 x51 = 1.1x41+ 1.25x32 xi2 30 ( i =1、2、3、4 )， x33 80，x24 100 xij0(i=1,2,3,4,5；j=1,2,3,4）最优解 Z=341.35 x11=170 x12=63 x13=0 x14=0 x15=33.5 x21=30 x22=24 x23=26.79999 x33=80 x42=1003）目标函数及模型：投资问题投资问题b) Min f = （x11+x21+x31+x41+x51)+ 3(x12+x22+x32+x42)+4x33+5.5x24 s.t. x11+
86、 x12 200 x21 + x22+ x24 1.1x11 + 200-(x11+ x12 ) x31 + x32+ x33 1.1x21+ 1.25x12 x41 + x42 1.1x31+ 1.25x22 x51 1.1x41+ 1.25x32 xi2 30 ( i =1、2、3、4 )， x33 80，x24 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 330 xij0(i=1,2,3,4,5；j = 1,2,3,4）投资问题投资问题牧草农场问题（最小化问题）牧草农场问题（最小化问题）n农场在试验一种新赛马食品。赛马食品有三种：普通饲料、高营养燕麦和新饲
87、料。成分如下表：饲料成分饲料成分普通饲料普通饲料S S高营养燕麦高营养燕麦E E新饲料新饲料A A饲料饲料A0.80.20.0饲料饲料B1.01.53.0饲料饲料C0.10.62.0每磅成本每磅成本0.250.503.00一匹马一天的最小进食量为：一匹马一天的最小进食量为： 3 3单位单位A A、6 6单位单位B B、4 4单位单位C C 总摄入量不能超过总摄入量不能超过6 6磅。磅。农场希望找到一种饲料组合，既可以满足马一天的农场希望找到一种饲料组合，既可以满足马一天的营养需要，又可以使总成本最低。营养需要，又可以使总成本最低。牧场问题的线性规划模型为：牧场问题的线性规划模型为：n最小化0.
88、25S+0.50E+3An约束条件n饲料A0.8S+0.2E3n饲料B1.0S+1.5E+3.0A6n饲料C0.1S+0.6E+2.0A4n总饲料量S+E+A6nS，E,A0n最优解S=3.514E=0.946A=1.541电子通信公司问题（电子通信公司问题（4变量）变量）n公司开发了新产品，有4种分销渠道。情况如下表：分销渠道分销渠道单位销售利润单位销售利润单位广告成本单位广告成本单位销售时间单位销售时间航海分销店航海分销店M90102商业分销店商业分销店B8483全国连锁店全国连锁店R7093直接邮购直接邮购D6015无无广告预算广告预算50005000美元，每个分销点最大销售时间美元，每
89、个分销点最大销售时间18001800小时。小时。现阶段产品现阶段产品600600个，个，全国连锁店最少销售全国连锁店最少销售150个个如何分配各渠道的销售量、销售时间以及广告预算，如何分配各渠道的销售量、销售时间以及广告预算，可以使销售利润最大。可以使销售利润最大。通信公司问题的线性规划模型：通信公司问题的线性规划模型：n最大化90M+84B+70R+60Dn约束条件n广告10M+8B+9R+15D5000n可销售时间2M+3B+3R1800n生产水平M+B+R+D=600n连锁店销售要求R150nM,B，R,D0n最优解M=25B=425AR=150D=0威尔特公司企业退休金财务计划威尔特公
90、司企业退休金财务计划n公司有一个提前退休计划，未来8年内为68个提前退休人员准备资金如下表(每年年初支付)：理财途径有理财途径有1. 1. 一年期储蓄一年期储蓄 利率利率4 42. 2. 第一年年初可以投资政府债券投资（第一年年初可以投资政府债券投资（3 3种），面种），面值值10001000，到期时支付，到期时支付10001000，利率是相对于面值的。，利率是相对于面值的。利息每年年末提取利息每年年末提取, ,不作复利计算。收益如下：不作复利计算。收益如下：年度年度12345678现金现金需求需求430210222231240195225255威尔特公司企业退休金财务计划威尔特公司企业退休金
91、财务计划债券债券价格价格利率利率到期年数到期年数111508.8755210005.50063135011.7507决策变量有决策变量有F F 八年计划所需总金额八年计划所需总金额B B1 1 第一年年初买入债券第一年年初买入债券1 1的单位数量的单位数量B B2 2 第一年年初买入债券第一年年初买入债券2 2的单位数量的单位数量B B3 3 第一年年初买入债券第一年年初买入债券3 3的单位数量的单位数量S Si i 第第i i年年初投资于储蓄的金额（年年初投资于储蓄的金额（i=1i=1、2 2、8 8）威尔特公司企业退休金财务计划：n最小值Fn约束条件n第一年F-1.15B1-1B2-1.3
92、5B3-S1=430n第二年0.08875B1+0.055B2+0.1175B3+1.04S1-S2=210n第三年0.08875B1+0.055B2+0.1175B3+1.04S2-S3=222n第四年0.08875B1+0.055B2+0.1175B3+1.04S3-S4=231n第五年0.08875B1+0.055B2+0.1175B3+1.04S4-S5=240n第六年1.08875B1+0.055B2+0.1175B3+1.04S5-S6=195n第七年1.055B2+0.1175B3+1.04S6-S7=225n第八年1.1175B3+1.04S7-S8=255n各参数0n最优解F
93、=1728.794B1=144.988B2=187.856B3=228.188S1=636.148S2=501.606S3=349.682S4=182.681S5=S6=S7=S8=0年初可用资金年初可用资金-投资于债券和储蓄的金额投资于债券和储蓄的金额=该年的支付责任该年的支付责任资源利用问题资源利用问题n假设某地区拥有m种资源，其中，第i种资源在规划期内的限额为bi(i=1，2，m)。这m种资源可用来生产n种产品，其中，生产单位数量的第j种产品需要消耗的第i种资源的数量为aij(i=1，2，m；j=1,2,n)，第j种产品的单价为cj(j=1，2，n)。试问如何安排这几种产品的生产计划，才
94、能使规划期内资源利用的总产值达到最大?设第j种产品的生产数量为xj(j=1，2，n)，则上述资源问题就是：n求一组实数变量xj(j=1，2，n)，使其满足农场种植计划模型农场种植计划模型 n某农场I、II、III等耕地的面积分别为100 hm2（公顷）、300 hm2和200 hm2，计划种植水稻、大豆和玉米，要求三种作物的最低收获量分别为190000 kg、130000 kg和350000kg。I、II、III等耕地种植三种作物的单产如表3.3.1所示。若三种作物的售价分别为水稻1.20元/kg，大豆1.50元/ kg，玉米0.80元/kg。那么，（1）如何制订种植计划，才能使总产量最大？（
95、2）如何制订种植计划，才能使总产值最大？表3.3.1不同等级耕地种植不同作物的单产(单位:kg / hm2)I等耕地II等耕地III等耕地水稻1100095009000大豆800068006000玉米140001200010000对于上面的农场种植计划问题，我们可以用线性规划方法建立模型。根据题意，决策变量设置如表3.3.2所示, 表中Xij表示在第j等级的耕地上种植第i种作物的面积。三种作物的产量可以用表3.3.3表示。表3.3.2作物计划种植面积（单位:hm2)表3.3.3三种作物的总产量（单位:kg）I等耕地II等耕地III等耕地水稻大豆玉米作物种类总产量水稻大豆玉米根据题意，约束方程如
96、下,耕地面积约束：最低收获量约束： 非负约束：调用Matlab软件系统优化工具箱中的linprog函数，进行求解运算，可以得到一个最优解（如表3.3.4所示）。在该方案下，最优值，即最大总产量为6892200kg。从表中可以看出，如果以追求总产量最大为种植计划目标，那么，玉米的种植面积在I、II、III等耕地上都占绝对优势。 （1）追求最大总产量的目标函数为：表3.3.4追求总产量最大的计划方案（单位：hm2）I等耕地II等耕地III等耕地水稻0021.1111大豆0021.6667玉米100300157.2222(2) 追求最大总产值的目标函数为：进行求解运算，可以得到一个最优解（如表3.3
97、.5所示）。在该方案下，最优值，即最大总产值为6830500元。从表中可以看出，如果以追求总产值最大为种植计划目标，那么，水稻的种植面积在I、II、III等耕地上都占绝对优势。 表3.3.5追求总产值最大的计划方案（单位：hm2）I等耕地II等耕地III等耕地水稻58.75 300 200大豆16.25 00玉米2500证券组合投资决策证券组合投资决策n某人有一笔50万的资金可用于长期投资，可供选择的投资机会包括购买国库券、公司债券、投资房地产、购买股票或银行保值储蓄等。不同的投资方式的具体参数见下表。序号投资方式投资期限（年）年收益率（%）风险系数增长潜力（%）1国库券311102公司债券1
98、0153153房地产6258304股票2206205短期定期存款110156长期保值储蓄5122107现金存款0300n投资者希望n投资组合的平均年限不超过5年，n平均的期望收益率不低于13%，n平均风险系数不超过4，n平均的收益的增长潜力不低于10%.n问：在满足上述要求的前提下投资者该如何选择投资组合使平均年收益率最高。解：由题意，目标：平均年收益率最高；决策变量：设xi是第i种投资在总投资中所占的比例；资源约束：投资组合的平均年限不超过5年；平均的期望收益率不低于13%；平均风险系数不超过4；平均的收益的增长潜力不低于10%；各项投资比例之和等于1。则，其线性规划模型为：Max Z=11
99、x1+15x2 +25x3 +20x4 +10x5 +12x6 +3x7s.t. 3x1+10x2 + 6x3+ 2x4+ x5 + 5x6 5 平均年限x1+3x2 + 8x3+ 6x4+x5+ 2x6 4 风险系数 15x2 +30x3+20x4+ 5x5+10x6 10 增长潜力x1+x2 +x3+ x4+ x5+ x6 + x7 =1 各项投资比例之和等于1 x1 , x2 , x3 , x4 , x5 , x6 , x7 0施肥问题施肥问题n某农场主需要对他的20亩菜地和30亩小麦地施肥。经土壤分析后，分析报告指出每亩菜地至少需施6公斤氮，2公斤磷，1.5公斤钾；每亩小麦地至少需施8
100、公斤氮，1公斤磷，3公斤钾。现市场上有A,B两种可用的肥料，相关数据如下表所示。n请帮助该农场主制定购买A,B两种肥料的合理预算和施肥方案。每袋重量（公斤）每袋价格（元）氮含量（）磷含量（）钾含量（）A406020520B605010105解：设xij表示第i种肥施于第j类用地的数量（袋），i=1,2,j=1,2.依题意，建立数学模型如下，min z= 60(x11+x12)+50(x21+x22)菜地：400.2x11+600.1x21206400.05x11+600.1x21202400.2x11+600.05x21201.5麦地：400.2x12+600.1x22308400.05x12+600.1x22301400.2x12+600.05x22303xij0, i, j=1,2.线性规划的其他应用线性规划的其他应用市场营销调查。医院绩效评定等线性规划的其他应用线性规划的其他应用n习题：217页n2-2、2-4、2-5、2-10
