水资源系统分析及应用：第二章 线性规划的基本理论及其应用

1、第二章 线性规划的基本理论及其应用2.1 线性规划的数学模型及其标准形式2.2 线性规划问题的图解法2.3 线性规划问题的单纯形解法2.4 非标准型线性规划问题的解法2.5 对偶问题2.6 灵敏度分析2.7 随机线性规划2.8线性规划的应用道路交通规划与规划有关的例子生产安排规划资源调配科学配餐线性规划问题的实践背景线性规划问题的数学模型线性规划问题的标准型2.1 线性规划的数学模型及其标准形式76.1緒言如何在有限的经济资源下进行最有效的调配与选用，以求发挥资源的最高效能。此问题愈来愈受到重视，也就是以最低的代价，获取最大的效益。兹列举如下：决定紧急设备与人员的地点，使反应时间最短化。决定飞

2、机、飞行员、地勤人员的飞航最佳日程安排。发展财务计划。决定动物饲料的最佳组合。决定最佳食谱计划。决定最佳生产日程安排。指出最佳工作指派。决定成本最低化的船运计划。指出工厂的最佳产品组合。8上述许多问题为在一些限制式(constraint)之下，以一组联立线性不等式或等式的方式表示，求线性目标函数(objective function)为极大或极小的问题。线性规划(linear programming, LP)就是数学家们针对这类问题研究所得的解法。1. 线性规划问题的实践背景背景：提高企业的经济效益是现代化管理的根本任务，各个领域中的大量问题都可以归结为线性规划问题。近几十年来，线性规划在各个

3、行业中都得到了广泛的应用。根据美国财富杂志对全美前500家大公司的调查表明，线性规划的应用程度名列前茅，有85%的公司频繁地使用线性规划，并取得了提高经济效益的显著效果。1. 线性规划问题的实践背景什么是线性规划？所谓线性规划，是求线性函数在线性(不等式或等式)约束下达最(小或大)值的问题。线性规划广泛应用于工农业、军事、交通运输、决策管理与规划、科学实验等领域。 。简单的来说, 线性规划研究线性最优化(optimization)問題。11线性规划是什么所谓线性规划简单的说，就是将决策上所面临的问题，以线性的数学式来加以描述，在线性等式及不等式组的条件下，使用特定的方法 线性规划 求得最优解。

4、线性规划模型是由四种成分组合而成：(1)目标；(2)决策变数；(3)限制式以及(4)参数。假想我们预备做一项决策,而该决策牵涉到n个变数(x1,x2, . . . , xn)有待决定。若是有一个目标函数可以表现为z(x1, x2, . . . , xn) =c1x1 + c2x2 + . . . +cnxn这种线性(一次)函數,同时这些变量之间的相互约束也可以用m个线性(一次)不等式来表示成ai1x1 + ai2x2 + . . . + anixn bi (i =1, 2, m)。那么我们就面对着一个线性规划问题:如果我们以向量c = (c1, c2, . . . ,cn)t来表示目标函数的系

5、數,向量x =(x1, x2, . . . ,xn)t来表示变數,向量b =(b1, b2, . . . ,bm)t来表示约束不等式的右手值,同时以矩阵A = (aij)mn来表示诸约束函数的系數,那么上述的线性规划问题可以简化成下列形式:换言之,线性规划的目的在求得一组变量特定值,使之在满足各个约束同时也达到目标函数的最小值。实际上,透过简单的数学转换,线性规划也可以处理最大值的问题。同时它的变數x1, x2, . . . ,xn也无需限制为非负值,而Ax b更可以改为Ax = b或者Ax b的约束形式。但是为了方便讨论起見,我们暂时集中精神在形式如(P)的问题上。线性规划问题大致可以分为两

6、类给出一定量的人力、物力、财力或其它资源，如何统筹规划这些有限的资源完成最大任务；给定一项任务，如何运筹规划，合理安排，以最少的资源来完成它。1. 线性规划问题的实践背景线性规划问题起源于20世纪初期，在二战期间得到发展1947年，G. B.Dantzig教授孕育1948年， T. C.Koop-mans和Dantzig两人于1948年夏天在美国加州圣塔摩尼加(Santa Monica)海滩散步时拟定名称。在1950和1960年代,线性规划的内容愈变愈豊富,更有许多成功的实用案例,所以愈来愈受世人瞩目。到了1975年,瑞典皇家科学院决定将当年的诺贝尔经济奖颁發给前面提到的L. V. Kanto

7、rovich和T.C.Koopmans以表彰他们在资源最佳分配理论的贡献。1979年，一位苏联数学家L. G. Khachian,利用椭球法(ellip-soid method)概念印证出线性规划问题可在多项式时间内求得解答。1984年由一位美国电话电报公司贝尔实验室的印度裔科学家N.Karmarkar他设计出一项内点法来解线性规划问题。线性规划的历史2. 线性规划问题的数学模型例1-1 某工厂生产甲，乙两种产品，这些产品分别需要在ABCD四种不同的设备上加工。按工艺规定，产品甲，乙在各设备上所需要的加工台时数如表1所示，已知各设备在计划期内有效台时数分别是12、8、16和12。该工厂每生产一

8、件产品甲可得利润2元，每生产一件产品乙可得利润3元。问应当如何安排生产计划，才能使利润最大化？（表1）设备ABCD可得利润产品甲21402元产品乙22043元有效台时数1281612问题的提出(一)2. 线性规划问题的数学模型分析：上述实际问题，通俗地说，就是在有效台时数一定的前提下，求使利润最大化的生产方案。建模：若以 分别代表产品甲，乙在计划期内的生产量。因为设备A的有效台时数为12，这是一个限制产量的条件，所以在确定产品甲，乙的产量时，要肯定不能超出设备A的有效台时数，即可用不等式表示为 12同理，对设备B、C、D也可以得到以下不等式：8 16 12考虑到实际意义，不可能为负值，即02.

9、 线性规划问题的数学模型用Z表示利润，则目标函数 于是，上述最优生产问题可以归纳为以下数学形式其中 必须满足以下条件 12 8s.t. 16 12 02. 线性规划问题的数学模型思考：模型与表（1）的对应关系？设备ABCD可得利润产品甲21402元产品乙22043元有效台时数1281612其中 必须满足以下条件 12 8s.t. 16 12 0例1.2 某汽车厂生产大轿车和载重汽车，所需资源、资源可用量和产品价格如下表所示: 大轿车 载重汽车 可用量钢材（吨） 2 2 1600工时(小时) 5 2.5 2500座椅 400（辆）获利(千元/辆) 4 3问应如何组织生产才能使工厂获利最大？ 问题

10、的提出(二)例1.2的数学模型s.t.,例1.3 营养配餐问题成年人每天需要从食物中摄取的营养以及四种食品所含营养和价格见下表。问如何选择食品才能在满足营养的前提下使购买食品的费用最小？例1.3 数学模型例1.4 有限水资源条件下种植结构优化问题(教材例2-2)一个灌区耕地面积1000hm2，可用灌溉水量360万m3。在安排种植计划时考虑两种粮食作物A,B，其灌溉定额分别为3000m3 /hm2，6000m3 /hm2，每公顷净收入分别为 4500元/hm2， 6000元/hm2 。问如何安排两种作物的种植面积才能使整个灌区净收入最大？例1.4 数学模型以作物A,B的种植面积x1,x2为决策变

11、量。则问题的提出 以上几例都有一些共同的特征：用一组变量表示某个方案，一般这些变量取值是非负的。存在一定的约束条件，可以用线性等式或线性不等式来表示。都有一个要达到的目标，可以用决策变量的线性函数来表示。 满足以上条件的数学模型称为线性规划模型。线性规划模型的一般形式如下：小结. 线性规划问题的特征线性规划模型的特征上述问题可看出线性规划问题有如下特点：1用一组未知变量（ ）表示某一方案，这组未知变量的一组确定值就代表一个具体的方案，这些未知变量称为决策变量。通常，根据决策变量所代表的事物的特点可以对变量的取值加以约束，例如非负约束、整数约束等。2存在一定的限制条件，通常称为约束条件，这些约束

12、条件可以用一组线性等式或者线性不等式来表达。3有一个目标要求，并且这个目标可以表示为决策变量的线性函数，称为目标函数。按所研究问题的不同，要求目标函数实现最大化或者最小化。小结：线性规划问题的特征 12 8 s.t. 16 12 0决策变量目标函数约束条件小结：线性规划问题的规范描述线性规划问题的规范描述s.t.约束条件目标函数决策变量价值系数技术系数限定系数3.线性规划问题的标准型(SLP)为什么要规定线性规划问题的标准型？便于比较，便于交流，便于计算机处理可以只针对这种标准形式来研究它的求解方法，对于不同形式的线性规划问题，只需要将其转换为标准型，然后再按标准型的求解方法求解。线性规划问题

13、的标准型(SLP)s.t极大化型约束方程为等式所有的决策变量为非负值约束方程的右端项系数为非负值SLP的特征()1、极大化型2、约束方程为等式3、所有的决策变量为非负值4、约束方程的右端项系数为非负值形式标准型的和式标准型的矩阵式各种符号的定义非标准形式如何写成标准形式一、目标函数是极小化的转化四、决策变量有上下界的转换例1.1 的标准型s.t例1.2 的标准型s.t习题附录A2，第二章习题2.2 线性规划问题的图解法图解法可行解及可行解集的特性线性规划问题解的特点单纯形法的思路1.2 线性规划问题的图解法图解法就是利用坐标图来求解线性规划问题例：配餐问题 营养学家指出，成人日常饮食每天至少要

14、摄入75克碳水化合物、60克蛋白质和60克脂肪。现有甲乙两种食物，在每千克甲中含105克碳水化合物，70克蛋白质、140克脂肪，花费为28元，在每千克乙中含105克碳水化合物，140克蛋白质、70克脂肪，花费为21元，请设计出符合营养学家要求并且花费最少的营养配餐。 整理数据，列表得：食物（千克）碳水化合物（千克）蛋白质（千克）脂肪（千克）甲0.1050.070.14乙0.1050.140.07最少摄入量0.0750.060.06解：设每天选择甲千克，乙 千克。即：目标函数：z=28x+21y约束条件0作出二元一次不等式组所表示的平面区域xy0设z=28x+21y，求z的最小值。第一步：点（x

15、，y）在此平面区域内运动时，如何求z=28x+21y的最小值。第二步：由z=28x+21y得：直线与此平面区域有公共点，求z的最小值。，当这族第三步：在区域内找一点，使直线经过该点时在y轴上的截距最小。MyxN解方程组：得M 点的坐标为所以答：每天食用食物A 143g，食物B 571g，能够满足日常饮食要求，又使花费最低，最低成本为16元。例1变式：若在上题条件之下想要食物总量最少，应怎样找到符合医生要求且摄入食物总量最少的营养配餐？ 讨论：相对于例1，只有目标函数发生变化，设z为进食总量 0设z=x+y，求z的最小值。当直线z=x+y与直线7x+7y=5重合时在y轴上的截距最小，所以线段MN

16、上所有点表示的解都是最优解。xyMN思考： 实际的线性规划问题中可能还会出现其他情况，比如要求解为整数等等，我们该怎么处理呢？ 例题分析例2 要将两种大小不同规格的钢板截成A、B、C三种规格，每张钢板可同时截得三种规格的小钢板的块数如下表所示 ： 解：设需截第一种钢板x张，第一种钢板y张，则 规格类型钢板类型第一种钢板第二种钢板A规格B规格C规格2121312x+y15,x+2y18,x+3y27,x0y0 作出可行域（如图）目标函数为 z=x+y今需要A,B,C三种规格的成品分别为15，18，27块，问各截这两种钢板多少张可得所需三种规格成品，且使所用钢板张数最少。返回X张y张例题分析x0y

17、2x+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解得交点B,C的坐标B(3,9)和C(4,8)调整优值法246181282724681015但它不是最优整数解.作直线x+y=12答（略）例题分析x0y2x+y=15x+3y=27x+2y=18x+y =02x+y15,x+2y18,x+3y27,x0,

18、xN*y0 yN*经过可行域内的整点B(3,9)和C(4,8)且和原点距离最近的直线是x+y=12，它们是最优解.答:(略)作出一组平行直线t = x+y，目标函数t = x+y返回B(3,9)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.若区域“顶点”处恰好为整点，那么它就是最优解；（在包括边

19、界的情况下）2.若区域“顶点”不是整点或不包括边界时，应先求出该点坐标，并计算目标函数值Z，然后在可行域内适当放缩目标函数值，使它为整数，且与Z最接近，在这条对应的直线中，取可行域内整点，如果没有整点，继续放缩，直至取到整点为止。3.在可行域内找整数解，一般采用平移找解法，即打网络、找整点、平移直线、找出整数最优解图解法求解线性规划问题的一般步骤建立直角坐标系找出所有约束条件所构成的公共区域，即可行域；改变目标函数值Z，使等值线平行移动，当移动到可行域上的某一点时，如果再移动就将脱离可行域，则该点使目标函数达到极值，该点坐标则为最优解。O12345613245678建立直角坐标系PQRS123

20、456132456O78找出所有约束条件所构成的公共区域，即可行域；可行域PQRS123456132456O78(4,2)改变目标函数值Z，使等值线平行移动，当移动到可行域上的某一点时，如果再移动就将脱离可行域，则该点使目标函数达到极值，该点坐标则为最优解。可行域思考：当目标函数改为时，最优解是什么？线性规划问题解的特点若线性规划问题存在唯一的最优解，那么它必定在顶点上（基本可行解）若线性规划问题存在多个最优解，那么必有几个相邻的顶点是最优解，其它最优解可以表示成这几个顶点的凸组合。若一个顶点的目标函数值比它的相邻顶点的目标函数值要好的话，它就是最优解。图解法的优缺点图解法利用坐标图来求解线性

21、规划问题，因此只适用于非常简单的情况约束条件较少决策变量不超过两个。三个决策变量即是一个空间问题，图解法在表达上有难度对于一般问题，难以求得精确解。但是，对于大量的管理实践问题，约束条件很多，决策变量三个以上，需要得到精确解，显然用图解法难以满足要求，1947年，美国人但泽（Danlzig）提出了一种求解一般线性规划问题的方法，单纯形法。 单纯形法的思路从某个顶点开始向目标函数值更好的邻近顶点移动判断此顶点是否为最优解：检查它是否比它的临近顶点的目标函数值都好，若是，则是最优解；若不是，则重复上述第二步。2.3 线性规划问题的单纯形解法线性规划问题解的基本概念单纯形解法解的最优性检验表解形式的

22、单纯形法单纯形解法的一些问题及其处理方法一、线性规划问题解的基本概念可行解最优解基及基本解可行基及基本可行解代数解与几何解的关系单纯形法的要点线性规划问题的解一、可行解 满足LP模型的约束条件且满足非负条件的解。例：二、最优解 使目标函数达到最大的可行解（存在多个可 行解，从中选择最优的解）三、基和基解 1、基：约束方程系数矩阵中任意m列所组成的mm阶非奇异子矩阵。基矩阵为：2、基本解 令非基变量为零，求解由基变量组成的方程组所得到的解。 互换变换、倍乘变换、消去变换四、基本可行解和可行基基本可行解：满足非负条件的基解（可行基所对应的解）可行基：基本可行解对应的基可行解基本解基本可行解结论：若

23、LP问题存在最优解，则一定可以在 基本可行解中找到。二、单纯形解法Step1: 建立基本可行解Step2: 计算变量的检验数Step3: 判断是否最优Step4: 若不是最优解，换基Step5: 计算新的基本可行解Step6: 迭代计算直到求得最优解或可判断无最优解为止*可行域的顶点对应LP问题的基本可行解*LP的最优解一定可以在基本可行解中找到思路建立初始基本可行基对于约束条件的右手项（限定系数）小于等于（）的情况，通过标准化，每个约束条件的左边加上一个松弛变量，该松弛变量的系数矢量是单位矢量。当约束条件的右手项（限定系数）都是小于等于时，可令松弛变量为初始基本可行基，于是可以很方便地得到初

24、始基本可行解。标准型线性方程组的增广矩阵表示它的初始可行基初始基本可行解初始基变量 是松弛变量。初始可行解（只要满足非负条件）初始基本可行解（非基变量取值为零时）目标函数与最优性检验第一次迭代确定入基变量，应当是 （Why），它的系数是4。确定出基变量，方法如下，得 (Why)对目标函数贡献大（价值系数高）受资源的约束，400所对应的资源最紧张确定新基和求解新的基本可行解新基新的基变量：新的基本可行解新的基本可行解和目标函数基本可行解目标函数第二次迭代确定入基变量：确定出基变量：不考虑零与负值确定新基和求解新的基本可行解新基新的基变量：新的基本可行解新的基本可行解和目标函数基本可行解目标函数第

25、三次迭代确定入基变量：确定出基变量：不考虑零与负值确定新基和求解新的基本可行解新基新的基变量：新的基本可行解基本可行解目标函数这是最优解。最大目标函数值为2600。新的基本可行解和目标函数三、关于解的最优性检验设线性规划模型为令基为B，并作相应的矩阵分割，从约束条件得代入目标函数得令则目标函数可写成可用 判断是否最优解，它叫做检验数。令则可用 判断是否最优解，它叫做检验数。对于线性规划问题标准型，最优性判别条件所有检验数均小于等于零。如果是求最小问题，则最优性判别条件是所有检验数均大于等于零。检验数是用非基变量表示基变量，带入目标函数的表达式中得来的非基变量的系数。它的含义是对应非基变量如果取

26、得一个大于零的值时，能给目标函数增大的量为 该值的检验数倍。 对最大化问题，如果检验数均小于等于零，意味着再进行迭代，也不能使目标函数增大了。用非基变量表示目标函数的表达式：Z=Z0+(Cj-Zj)XnXn为非基变量，Cj-Zj为检验数，Z0为求出的基可行解.从表达式很明显看出只有Cj-Zj0,Z达到最大值,即最优解. 单纯形法中的检验数的计算用基变量在目标函数中的系数，乘以你要算得那个变量对应的系数列的各个值，并求和，再减去你要算得那个变量在目标函数中对应的系数，就是检验数 四、表解形式的单纯形法表的格式在表上的计算方法表上计算的原理表解单纯形法的实例初始单纯形表43000000160025

27、0040025122.5010001000180050040043000单纯形表法求解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

28、.40.4100260000-1-0.40五、单纯形解法的一些问题及其处理方法换入变量的选择问题下标最先原则(勃兰特法则)检验数最大原则换出变量的选择问题比值最小原则下标最先原则(勃兰特法则)无换出变量的情况无界解非基变量检验数有等于零多个最优解的情况退化解与无可行解的情况单纯形法的进一步讨论1、无界解Oz cj2 3 0 0bcBxBx1 x2 x3 x4 0 0 x3 x4 1 -1 1 0-3 1 0 1 2 4 j 2 3 0 0 2 0 x1 x4 1 -1 1 0 0 -2 3 1 2 10 j 0 5 -2 0结论：若j0,对应的系数列向量0，则该LP存在无界解。2、多个解 cj

29、4 14 0 0b cB xBx1 x2 x3 x300 x3X42 7 1 07 2 0 121213j4 14 0 014 0 x2x42/7 1 1/7 045/7 0 -2/7 1315j 0 0 -2 0z=4221/27/314 4x2x1 0 1 7/45 -2/45 1 0 2/45 7/457/37/3j 0 0 -2 0z=4221/2结论：若某个非基变量的检验系数为零，则该 LP存在多个最优解。当所有的检验数全部小于等于零时,若有某个非基变量的检验数也是零,则该线性规划有无穷多组解,否则有唯一解.3、退化解cj2 0 1.5 0 0 0bcBxBx1 x2 x3 x4 x

30、5 x6000 x4x5x61 -1 0 1 0 02 0 1 0 1 01 1 1 0 0 1243223j2 0 1.5 0 0 0200 x1x5x61 -1 0 1 0 00 2 1 -2 1 00 2 1 -1 0 1201j0 2 1.5 -2 0 0基本可行解中基变量等于零*在单纯形法的计算过程中，确定出基变量时存在两 个或两个以上的最小比值，这时会出现退化解。特征：基本可行解中，基变量等于零*有时，退化会造成计算过程的循环，永远达不到最优解。*用勃兰特法则一定可以避免出现循环为避免循环,常采用1976年R.G.Bland提出Bland法则:单纯形表中有若干个检验数 大于零 时,

31、取下标号小的非基变量入基; 用 法则选取出基变量时,若比值相同,则选取下标号小的基变量出基.勃兰特（Bland）法则4、无可行解（大M法） cj20 30 0 0 0 -MbcBxBx1 x2 x3 x4 x5 x6 00-Mx3x4x6 10 1 0 0 0 0 0 1 0 01 1 0 0 -1 11503040j20+M 30+M 0 0 -M 0 3020-Mx2x1x60 1 1/10 -3/10 0 0 0 0 1 0 00 0 -1/10 -7/10 -1 1 6 30 4 j0 0 3-M/10 -11-7M/10 M 0 xB x1 x2 x3 x4 x5bx2x3x5 1

32、1 0 -4 0 -2 0 1 -3 0 3 0 0 a 153dj -3 0 0 0 讨论题在求解极大化LP问题中，得到如下单纯形表：1、当前解为最优解时，各参数应满足的条件；2、原问题存在无界解时，各参数应满足的条件；3、原问题存在多个解时，各参数应满足的条件；4、当 x4 作为进基变量取代 x5 时，目标值的增量为多少？结论：若基变量中有非零的人工变量，则该LP无可行解。多个最优解无界解1、d0, 0, a03、d0, =0, a04、六、(小结)单纯形法的矩阵表示=非基变量 基变量=非基变量基变量B-1bIBNI2.4 非标准线性规划问题的解法目标函数求极小问题等式约束大M方法大于等于

33、的约束条件常数项为负值的情况允许变量为负值的情况一、目标函数求极小问题方法1：目标函数标准化(变为极大问题)方法2：检验数最优解检验规则 标准型二、等式约束大M法人工变量标准化后可见没有初始单位可行基，加人工变量大M法然后用单纯形法求解（本例）初始单纯形表3500-Mb00-M41218103022100010001 4 6-18M3+3M5+2M000第一次迭代3500-Mb30-M412610002210-30100016312-6M05+2M-3-M00第二次迭代3500-Mb30546310000113-1.50100-10.54227004.50-M-2.5第三次迭代3500-Mb3

34、05226100001010-1/31/31/21/3-1/3036000-1.5-M-1大M法的要点1、人工变量的引入2、用大M法处理人工变量当目标函数求最大，则为-M当目标函数求最小，则为M三、大于等于的约束条件减去剩余变量化为等式加人工变量用大M法例如四、右手常数项为负值的情况两边同乘以-1标准化：加上松弛变量或减去剩余变量必要时加上人工变量加人工变量时，用大M法例如五、变量允许为负值的情况标准化处理必要时用人工变量用人工变量时，再用大M法例如处理以后成为4、无可行解 cj20 30 0 0 0 -MbcBxBx1 x2 x3 x4 x5 x6 00-Mx3x4x63 10 1 0 0

35、01 0 0 1 0 01 1 0 0 -1 11503040j20+M 30+M 0 0 -M 0 3020-Mx2x1x60 1 1/10 -3/10 0 01 0 0 1 0 00 0 -1/10 -7/10 -1 1 6 30 4 j0 0 3-M/10 -11-7M/10 M 0结论：若基变量中有非零的人工变量，则该LP无可行解。用计算机软件求解线性规划问题 关于线性规划问题的求解，有许多好的专业软件和商务软件，通过计算机可十分方便地完成求解过程。最简便易行的求解软件是Excel，下面介绍其使用方法。 （1）建立Excsl工作表。用 一组单元格表示变量，作为可变单元格（空）；用几组单

36、元格分别表示各约束条件和目标函数的系数；用一些单元格输入公式表示各组系数和变量的关系。 （2）打开工具栏中的“规划求解”对话框，指定存有目标函数的单元格为目标单元格，指定表示变量的单元格为可变单元格，建立约束条件。 （3）在规划求解对话框中按下“求解”按钮，即可求出最优解和最优值。推出规划求解对话框。2.5 对偶问题1、对偶问题的提出2、对称的对偶线性规划3、对偶的基本性质4、对偶单纯形法5、对偶问题的经济解释Duality theory 研究线性规划中原始问题与对偶问题之间关系的论。 发展简史:在线性规划早期发展中最重要的发现是对偶问题，即每一个线性规划问题(称为原始问题)有一个与它对应的对

37、偶线性规划问题（称为对偶问题）。 1928年美籍匈牙利数学家 J.von诺伊曼在研究对策论已发现线性规划与对策论之间存在着密切的联系。两零和对策可表达成线性规划的原始问题和对偶问题。一. 对偶问题的提出例：产品原材料工时定额单位产品收益A2210B31.512现有资源300180问1：如何生产使总收益最大？问2：若企业把资源出租，应如何确定合理的价格？出租可获得的收益不得低于自行生产的收益在满足上述要求的前提下，所定的价格对方愿意接受目标函数：约束条件：非负条件：产品原材料工时定额单位产品收益A2210B31.512现有资源300180 LP DLP2、价值系数资源系数（右项）3、资源系数（右

38、项）价值系数4、约束方程 =5、目标函数 max目标函数 min原始问题max z=CXs.t.AXbX 0对偶问题min w=Ybs.t. YACY 0maxbACCTATbminmnmn(LP)(DLP)LP与DLP的对偶关系一、标准形式的对偶关系原问题与对偶问题的关系 线性规划原问题与对偶问题之间的形式变换关系可以由表予以概述。原问题（或对偶问题） 对偶问题（或原问题） 目标函数 目标函数 变量 个数n00无约束 约束方程 个数n= 约束方程 个数m= 变量 个数m00无约束 约束方程右端项 目标函数中变量的系数 目标函数中变量的系数 约束方程右端项 表 利用表所描述的变换关系，可写出任

39、何一个线性规划问题的对偶问题。譬如，对于线性规划问题其对偶问题为 对偶问题的基本性质 对称性：即对偶问题的对偶是原问题。 弱对偶性：即若 是原问题的可行解， 是对偶问题的可行解，则存在关系： 。 无界性：若原问题（对偶问题）为无界解，则其对偶问题（原问题）无可行解。 对偶定理：若原问题有最优解，那么对偶问题也有最优解，而且它们的最优目标值相等。 松紧定理：若 和 分别为原问题与对偶问题的可行解，则它们为最优解的充要条件为 设原问题是 其对偶问题是 互补松弛性：若 和 分别是原问题和对偶问题的可行解。那么， 和 ，当且仅当 和 为最优解。 则原问题单纯形表的检验数行对应其对偶问题的一个基解，其对

40、应关系如表。 0表二、对称型对偶线性规划线性规划具有对称形式的两个条件所有变量非负约束条件都是不等式，且目标函数极大化时，不等式方向为，极小化时，为原对偶线性规划的对应关系 三、非对称的线性规划的对偶问题等式约束的对偶关系其它非对称约束的对偶关系 min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-x3 15=x10,x20,x3无非负要求(unr)例：对偶线性规划min z= 2x1+4x2-x3s.t. 3x1- x2+2x3 6 -x1+2x2-3x3 12 2x1+x2+2x3 8 x1+3x2-

41、x3 15maxw=6y1+12y2+8y3+15y4s.t. 3y1- y2+2y3+ y4 2 -y1+2y2+ y3+3y4 4 2y1-3y2+2y3- y4 -1 y1 0,y2 ,y3 0,y4 0=unr=x10 x20 x3: unr(无非负约束)原始问题变量的个数(3)等于对偶问题约束条件的个数(3)； 原始问题约束条件的个数(4)等于对偶问题变量的个数(4)。原始问题变量的性质影响对偶问题约束条件的性质，用 表示 原始问题约束条件的性质影响对偶问题变量的性质，用 表示三、 对偶问题的基本性质1、对称性对偶问题的对偶问题是原问题对偶变换对偶变换代数变换代数变换2、弱对偶性揭示

42、目标函数值的关系推论：1）极大化问题任一可行解的目标函数值是其对偶问题 最优值的下界。2）极小化问题任一可行解的目标函数值是其对偶问题 最优值的上界。例：1）原问题任一可行解 X=（1 1 1 1）（DLP）目标值 z=1010是DLP问题最优目标值的下界2）对偶问题任一可行解 Y=（1 1） 目标值 w=40 40是LP问题最优目标值的上界 弱对偶性的推论 若LP有最优解，则DLP也有最优解，且它们的目标值相等。原始对偶 问题目标函数值之间的关系1、可行解的目标函数值之间的关系 设X、Y分别是原始问题和对偶问题的可行解z=CX YAX Yb=w2、最优解的目标函数值之间的关系 设X*、Y*分

43、别是原始问题和对偶问题的最优解 z=CX*=Y*AX*=Y*b=w4、对偶定理（揭示最优解之间的关系） 若LP有最优解，则DLP也有最优解，且他们的目标值相等。（松弛变量检验数的相反数）对偶可行最优性代入目标函数由对偶定理可知，当原始问题获得最优解时，对偶问题同时获得最优解，其最优解可以从原始变量的最终单纯形表中直接读出。 cj 2 3 1 0 0bcBxB x1 x2 x3 x4 x5 2 3 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 j 0 0 -3 -5/3 -1/3 Z=8请确定对偶问题的最优解小结原问题(max) 对应关系 对偶问题(min)

44、有最优解有最优解无界解不可行不可行无界解（无可行解）（无可行解） （无界解）（无可行解）四、对偶单纯形法一、思路单纯形法：迭代过程始终保持B的可行性（最小规则）， 逐步满足最优性。从线性规划标准型的一个基本可行解出发，逐步迭代，使目标函数值不断改进，直到取得最优解为止，在整个运算过程中，始终保证解的可行性，即始终有先从非基变量中确定进基变量，再从基变量中选择出基变量。对偶单纯形法：迭代过程始终保持最优性（对偶可行性），再逐步满足可行性。先从基变量中确定出基变量，再从非基变量中选择进基变量3、换基迭代1. 化为标准型,建立初始单纯形表，所有检验数04、回到第2步(若所有aij0,则该LP无可行解

45、）二、计算步骤 cj-1 -2 -3 0 0 0bcBxB x1 x2 x3 x4 x5 x6 0 0 0 x4 x5 x6-1 1 -1 1 0 0 1 1 2 0 1 0 0 -1 1 0 0 1 -4 8 -2 j-1 -2 -3 0 0 0 j 1 3x1x5x6-1001 -1 1 -1 0 0 40 2 1 1 1 0 4 0 -1 1 0 0 1 -2j0 -3 -2 -1 0 0 j 3 cj-1 -2 -3 0 0 0bcBxB x1 x2 x3 x4 x5 x6-1 0 0 x1 x5 x6 1 -1 1 -1 0 0 0 2 1 1 1 0 0 -1 1 0 0 1 4

46、4 -2 j 0 -3 -2 -1 0 0 j 3 x1 x5 x2-10-21 0 0 -1 0 -1 60 0 3 1 1 2 0 0 1 -1 0 0 -1 2j0 0 -5 -1 0 -3 练习 cj -3 -5 -4 0 0bcB xB x1 x2 x3 x4 x500 x4x5 -3 -1 -2 1 0 -2 -3 -1 0 1-60-b2 j -3 -5 -4 0 0 j 1 5 2-3 0 x1 x5 1 1/3 2/3 -1/3 0 0 -7/3 1/3 -2/3 1 2040-b2 j 0 -4 -2 -1 0-3 0 x1x4 1 3/2 1/2 0 -1/2 0 7/2

47、 -1/2 1 -3/2b2/2 j 0 -1/2 -5/2 0 -3/2* 对偶单纯形法的适用前提能解决形如以下的LP问题：五、对偶问题的经济解释一、原始问题是利润最大化的生产计划问题单位产品的利润产品产量总利润资源限量单位产品消耗的资源剩余的资源消耗的资源二、对偶问题资源限量资源价格总利润对偶问题是资源定价问题，对偶问题的最优解y1、y2、.、ym称为m种资源的影子价格（Shadow Price）原始和对偶问题都取得最优解时，最大利润 max z=min w三、影子价格影子价格越大，说明这种资源越是相对紧缺影子价格越小，说明这种资源相对不紧缺如果最优生产计划下某种资源有剩余，这种资源的影子

48、 价格一定等于0如果资源的影子价格大于0，最优生产计划下该种资源全部用完第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.4220040000400200200400第三次迭代16002500400001

49、600250010.41001-0.50.40.5-0.4-10.4260000200200600原问题最优解对偶单纯形法的用途1、用于初始基本解不是可行解，但检验数符合最优条件的问题求解。2、对于变量较少，而约束条件数较多的问题，可先得到它的对偶问题，再用对偶单纯形法求解对偶问题，达到简化计算的目的。3、用于灵敏度分析。对偶单纯形法有以下优点：(1) 初始解可以是非可行解，当检验数都为负数时就可以进行基的变换，这时不需要加入人工变量，因此可以简化计算。(2) 当变量多于约束条件，使用对偶单纯形法计算可以减少计算工作量，因此对变量较少，而约束条件很多的线性规划问题，可先将它变换成对偶问题，然后

50、用对偶单纯形法求解。(3) 在灵敏度分析及求解整数规划的割平面法中，有时需要用对偶单纯形法。 对偶单纯形法的局限性：对大多数线性规划问题，很难找到一个初始可行基，因而这种方法在求解线性规划问题时很少单独应用。 原规划与对偶规划之间的关系1.原规划若有n个变量，则对偶规划有n个约束条件；原规划有m个约束条件，则对偶规划有m个变量。2.若原规划的目标函数是求极大值，则对偶规划的目标函数是求极小值，且这两个极值相等。3.原规划目标函数中变量的系数等于对偶规划中相应约束条件的右端常数项；原规划约束条件右端常数项等于对偶规划目标函数中相应变量的系数。4.原规划约束条件中不等号与对偶规划约束条件的不等号方

51、向相反。5.原规划中一个等式约束，对应于对偶规划的一个符号无限制的变量；反之，当一个原规划的变量无符号限制，它的对偶约束条件就是等式约束。1.6 灵敏度分析单纯形法的矩阵表示系数变化的灵敏度分析决策变量增减的灵敏度分析约束条件增减的灵敏度分析灵敏度分析小结单纯形法的矩阵表示灵敏度分析（优化后分析）一、参数的可变性 (cj ,bi ,aij)二、灵敏度分析的内容1、参数的变化对原最优解有什么影响？原最优解是否 仍为最优解?2、参数在什么范围变化时，原最优解保持不变？3、当原最优解已不再最优时，应如何利用原单纯形表， 以最简捷的方法求得新的最优解。三、最优性分析四、目标函数cj的变化1、非基变量c

52、j的变化 cj 2 3 1 0 0bcBxB x1 x2 x3 x4 x5 2 3 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 j 0 0 -3 -5/3 -1/3 Z=8欲使原问题的最优性保持不变，若要保持最优性不变一般情况：2、基变量cj的变化 cj 2 3 1 0 0bcBxB x1 x2 x3 x4 x5 2 3 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 j 0 0 -3 -5/3 -1/3 Z=8 1）讨论c2的变化范围2）一般情况对于所有的非基变量都应满足上述不等式,有(n-m)个,则 cj 2 3 1

53、0 0bcBxB x1 x2 x3 x4 x5 2 3 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 j 0 0 -3 -5/3 -1/3 Z=8 问：c2由3变为1时，应如何修改原最优计划？ cj 2 1 1 0 0bcBxB x1 x2 x3 x4 x5 2 1 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 j 0 0 1 -7/3 1/3 Z=4 3 6 1 1 1 1 0 0 3 6 -1 1 x1 x5 2 0 xB Z=6 0 -1 -1 -2 0 j x1 x2 x3 x4 x5cBb 2 1 1 0 0 c

54、j五、资源系数bi的变化 cj 2 3 1 0 0bcBxB x1 x2 x3 x4 x5 0 0 x3 x4 1 1 1 1 0 1 4 7 0 1 3 9 j 2 3 1 0 0 Z=0 2 3 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 j 0 0 -3 -5/3 -1/3 Z=8初始单纯形表最终单纯形表B的逆包含了矩阵变换的信息与初始单纯形表中单位矩阵所在的位置对应2、分别讨论b1由3变为9，b2由9变为15时对原最优解的影响对原问题的可行性无影响但是最优解发生了变化3、一般情况4、举例 1）确定b1 、b2的变化范围2）b2由9变为15时，应如何

55、修改原最优计划？ cj 2 3 1 0 0bcBxB x1 x2 x3 x4 x5 2 3 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 -1 4 j 0 0 -3 -5/3 -1/3 j31 0 3 x5 x2-3 0 3 -4 1 1 1 1 1 0 3 3 j-1 0 -2 -3 0 Z=9 cjee-10 16 -1 0 0b cB xB x1 x2 x3 x4 x5 -10 16 x1 x2 1 0 -1 -1 2 0 1 -1 -1 1 6 2 j 0 0 5 6 4Z=-282、非基变量cj的变化：3、基变量cj的变化：若最优基发生变化，用单纯形法修改

56、。4、资源系数bi的变化：若最优基发生变化，用对偶单纯形法修改。1、分析思路小结1、非基变量对应的系数六、约束方程系数aij（非基变量）的变化求a13的变化范围 cj 2 3 1 0 0bcBxB x1 x2 x3 x4 x5 2 3 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 j 0 0 -3 -5/3 -1/3 Z=8最终单纯形表中，基变量没有发生变化可行性不发生变化，影响最优性1、一般情况前例，求出a13的变化范围 cj 2 3 1 0 0bcBxBx1 x2 x3 x4 x5 2 3 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/3

57、 1/3 1 2 j 0 0 -3 -5/3 -1/3 Z=82、基变量对应的系数求a11由1变为2时，最优解的变化 cj 2 3 1 0 0bcBxB x1 x2 x3 x4 x5 2 3 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 j 0 0 -3 -5/3 -1/3 Z=8最终单纯形表中，显然原来的基变量的系数列向量未能组成单位矩阵的形式，即没有完成基交换，必须继续进行线性变换 cj 2 3 1 0 0bcBxB x1 x2 x3 x4 x5 2 3 x1 x2 1 0 -1 4/3 -1/3 0 1 2 -1/3 1/3 1 2 j 0 0 -3

58、-5/3 -1/3 Z=8 cj 2 3 1 0 0bcBxB x1 x2 x3 x4 x5 2 3 x1 x27/3 0 -1 4/3 -1/3 -1/3 1 2 -1/3 1/3 1 2 j Z=8 cj 2 3 1 0 0bcBxB x1 x2 x3 x4 x5 2 3 x1 x21 0 -3/7 4/7 -1/70 1 13/7 -1/7 2/7 3/7 15/7 j0 0 -26/7 -5/7 -4/7 Z=51/7因为技术退步了，所以最优解减少了七、决策变量增减的灵敏度分析 增加产品新品种相当于增加一列1、解决是否值得生产的问题2、解决若值得生产，生产计划应如何调整第一个问题可以直

59、接使用机会成本分析法第二个问题需先计算新的一列当前值，再 继续求解。增加新产品相当于增加一个决策变量，系数矩阵也将增加一列设研制出一种新产品小旅行车，每辆用旅行车1.5吨，工时1.25小时，座椅0.25套，利润3千元，试问该新产品是否该投产？第一种解法：设该车产量为 ，则利润成本0第二种解法可见值得生产。但新的生产计划如何呢？检验数0，继续迭代43 00030342006002000010100.51-0.5-0.4-0.40.41000.51-0.25260000-1-0.40143 000333440020030000101010-0.25-0.80.40.22-20.5100300000

60、-2 0.4-2043 000330480050020000122.5-0.510-0.25010-2-51.510032000-1-2 000得最优解，且可在两个角点上取得最优解，因此最优解有无穷多个。八、约束条件增减的灵敏度分析增加约束条件意味着可行域的减小在原最优解的表中增广一列和一行此时检验数不变（对偶问题仍为可行解）继续用对偶单纯形法求解关于约束条件增加灵敏度分析的例子如果在例1.1中规定，发动机供应每年只有600台，这相当于增加一个约束条件如下：设松弛变量为 （未用完的发动机数），则以 为基变量，在最终单纯形表中增加一行和一列，则43 00000340200600200-20000