管理运筹学单纯形法

1、管理运筹学单纯形法第1页，共29页，2022年，5月20日，8点11分，星期二5.1 线性规划求解的相关概念 一、相关定理定理1 线性规划问题的可行解集S是凸集。定理2 线性规划问题的基本可行解X对应于可行域S的顶点。也就是说，可行域的顶点就是线性规划问题的基本可行解。定理3 若线性规划问题有最优解，它一定在其可行域的顶点上达到。第2页，共29页，2022年，5月20日，8点11分，星期二二、基本概念单纯形法的基本思路：单纯形法也可以说是一种找凸集极点的计算方法，但它并不是要求去计算所有的极点，而是从凸集的一个初始解出发，沿凸集的边缘逐个验算所遇到的极点，直到找到使目标函数最优的极点为止。初始

2、可行解:第一个找到的可行域的顶点。三、单纯形法试算程序框图（见图51） 第3页，共29页，2022年，5月20日，8点11分，星期二开 始转变为标准型增加额外变量(松弛、剩余、人工变量)建立初始单纯形表最优停找出“换入”“换出”变量修正单纯形表是否图51第4页，共29页，2022年，5月20日，8点11分，星期二5.2 线性规划模型的变换 一、线性规划模型标准型的特点 目标函数是求极大值或极小值；所有的变量都是非负的；除变量的非负约束外，其余的约束条件都是等式约束；每个约束方程右边的常数都是非负的 。除变量的非负约束等式约束思考:若右边的常数不是非负怎么办?第5页，共29页，2022年，5月2

3、0日，8点11分，星期二二、线性规划模型的变换 根据线性规划模型约束条件的不同，将其划分为三种类型：1.“”类型的约束条件的变换 变换的方法：在不等式中增加一个额外的变量，称为松弛变量，以S表示之。松弛变量在约束方程中的系数为1，在目标函数中的系数为0，所以它的引入并不影响目标函数值。 松弛变量即表示作为决策限制条件的某种有限资源未被利用的部分。 第6页，共29页，2022年，5月20日，8点11分，星期二2“”类型的约束条件的变换变换的方法：引入剩入变量及人工变量，以S和A表示。剩余变量在约束方程中的系数为-1，在目标函数中的系数为0，人工变量在约束方程中的系数为1，在目标函数中的系数为是一

4、任意大正数，以M表示之。在求最大值的目标函数中，M取负号；在求最小值的目标函数中，M取正号。剩余变量一般用来表示决策要求的某一最低标准超过要求的量，人工变量仅为了单纯形法在运算上方便，无其它特殊意义。 第7页，共29页，2022年，5月20日，8点11分，星期二3“=”类型的约束条件 变换的方法：引入人工变量，人工变量在约束方程中的系数为1，在目标函数中的系数为任意大的正数M。在求最大值的目标函数中，M取负号；在求最小值的目标函数中，M取正号。 第8页，共29页，2022年，5月20日，8点11分，星期二三、模型变换方法归纳 约束条件类型变 换 方 法对于约束条件对于目标函数+S+0S-S+A

5、求max时，+0S-MA求min时，+0S+MA=+A求max时，-MA求min时，+MA表中，S为松弛变量或剩余变量，A为人工变量，M为一任意大的正数。第9页，共29页，2022年，5月20日，8点11分，星期二单纯形法 1.单纯形法的基本思想 从一个初始的基本可行解出发，沿着不断改进目标函数值的方向进行迭代，经过若干基本可行解，直到得出最优解。 计算顺利进行的保证条件：最优性条件：它保证每次变动不会得到更差的解可行性条件：它保证每次变动仍是基本可行解可行域是不变的 第10页，共29页，2022年，5月20日，8点11分，星期二2.单纯形法的计算步骤将线性规划问题转化为标准型编制初始单纯行表

6、判别基本可行解是否为最优找出“换入”或“换出”变量，以便进行换基先找出主元行与主元列：对于求极大值问题，取Cj-Zj为正数且最大者所在的列为主元列，取bi/aij为正数且最大者所在的行为主元行，主元行与主元列之交点元素称为主元素，在右上方记“*”主元素正上方对应的变量为“换入”变量，主元素左边对应的基变量为“换出”变量。修正单纯形表运算规则：新行主元行元素=旧行元素/主元素其他新行元素=旧行元素-交点元素*新主元行相应元素【交点元素指该行与主元列之交点元素】对新基本可行解进行判别，是否达到最优，是则停；否则继续上述程序对于求最大值问题，全部判别数为零与负数时，即Cj-Zj 0，得最优解第11页

7、，共29页，2022年，5月20日，8点11分，星期二线性规划模型的一般形式：求一组变量x1，x2，xn的值,使目标函数：Z = c1x1 + c2x2 + + cnxn的值最大或最小，并满足的约束条件： a11x1 + a12x2 + + a1nxn (，=) b1 a21x1 + a22x2 + + a2nxn (，=) b2 am1x1 + am2x2 + + amnxn (，=) bm x1，x2 xn 0第12页，共29页，2022年，5月20日，8点11分，星期二线性规划一般形的标准型：第13页，共29页，2022年，5月20日，8点11分，星期二一般型的初始单纯形表：CjC1 C

8、2 Cn 0 0 0 x1 x2 xn Sn+1 Sn+2 Sn+m解b0 Sn+10 Sn+2 0 Sn+ma11 a12 a1n 1 0 0a21 a22 a2n 0 1 0 am1 am2 amn 0 0 1 b1b2bn机会成本行Zj判别数行Cj-Zj目标函数第14页，共29页，2022年，5月20日，8点11分，星期二例1求max Z=7x1+10 x2 满足 7x1+7x24910 x1+5x250 x1，x20 用单纯形法求解。第15页，共29页，2022年，5月20日，8点11分，星期二例2 第2章例1中我们得线性规划模型为：目标函数：max Z = 50 x1+100 x2

9、满足 x1 + x2 300 2x1 + x2 400 x2 250 x1，x2 0用单纯形法求解。第16页，共29页，2022年，5月20日，8点11分，星期二本题模型的标准型为：求max Z=50 x1+100 x2+0S3+0S4+0S5 满足 x1+x2+ S3 =300 2x1+x2 +S4 =400 x2 +S5 =250 x1，x2，S3，S4，S50第17页，共29页，2022年，5月20日，8点11分，星期二Cj 50100000 x1x2S3S4S5解0 S30 S40 S51 1 1 0 02 1 0 1 00 1* 0 0 1300400250 ZjCj-Zj0 0 0

10、 0 050 100 0 0 000 S30 S4100 x2 1* 0 1 0 -1 2 0 0 1 -1 0 1 0 0 150150250 ZjCj-Zj 0 100 0 0 10050 0 0 0 -10025000第18页，共29页，2022年，5月20日，8点11分，星期二Cj 50100 0 0 0 x1 x2 S3 S4 S5 解50 x10 S4100 x2 1 0 1 0 -1 0 0 -2 1 1 0 1 0 0 15050250ZjCj-Zj50 100 50 0 500 0 -50 0 -5027500此时，Cj-Zj0 则此时为最优解。即：x1=50 x2=250

11、S3=0S4=50 S5=0 Z=27500 第19页，共29页，2022年，5月20日，8点11分，星期二3.人工变量法用单纯形法求最小值问题，与求最大值问题类似，其区别在于判别数为零或者正值，即Cj-Zj0时得到最优解，在决定“换入”及“换出”变量时，取Cj-Zj为负且绝对值最大者为主元列，其余步骤同求最大值问题。这种求线性规划的方法，称为“人工变量法”或称为“大M”法，这就是当一个 线性规划问题在增加了松弛变量后 仍不能提供基本可行解时，需要采用“人工变量”来获得一个初始的基本可行解。第20页，共29页，2022年，5月20日，8点11分，星期二例3求线性规划： min Z=2x1+3x

12、2 满足 2x1+x24 -x1+x22 x1,x20第21页，共29页，2022年，5月20日，8点11分，星期二单纯形法的步骤归纳如下：根据线性规划模型的特点，将问题改写成标准型以各变量为列，各约束方程的系数为行，全部决策变量为0，松弛变量或人工变量为基变量，建立初始单纯形表计算机会成本行Zj及判别数行Cj-Zj，检验问题是已达最优，是则停，否则进行下一步找出主元素，确定“换出”及“换入”变量进行换基及迭代运算，修正单纯形表重返第3步第22页，共29页，2022年，5月20日，8点11分，星期二单纯形法的经济信息例：设某制药厂生产A和B两种药品，在已有条件下。药品A的生产能力为5吨/月,药

13、品B生产能力为4吨/月，设每吨药品A耗电0.5万度，每吨药品B耗电1万度，电力部门供电能力为每月5万度，若药品A价格为每吨4千元，药品B的价格为每吨1千元，问每月应如何分配电力资源，使产值最大？本题解题过程第23页，共29页，2022年，5月20日，8点11分，星期二由题：Cj列表示每一个基变量对目标函数的贡献初始表最右端bi列，表示的是各松弛变量的最大值，即相应资源的约束条件的上限初始表提供的基本可行解为 x1= x2=0 不生产A、B S3=5 闲置的药品A的生产能力 S4=4 闲置的药品B的生产能力 S5=5 闲置的电力资源第24页，共29页，2022年，5月20日，8点11分，星期二例

14、2： 某医院营养室专门为病员制作甲、乙、丙三种营养食品，其中每种食品都要包含两种主要营养素A、B，具体数据如下表，而且A营养素的供应量为12千克，B营养素的供应量为20千克，试问该营养室每天制作甲、乙、丙三种食品各多少份才能使其利润最高？ 甲乙丙A111B132利润（元/份）586第25页，共29页，2022年，5月20日，8点11分，星期二对偶规划线性规划是研究资源最优利用的途径，所谓最优利用包含两方面的含意：1.在一定的资源条件下完成最多的任务或做出最大的贡献2.完成给定的任务，使用的资源最小对于一个求极大值问题必存在一个求极小值的问题与其对应，而且两者包含相同的数据，称前一个问题为原问题

15、，则后一个问题便是原问题的对偶问题。反之，若称后一问题为原问题，则前一个问题是对偶问题。第26页，共29页，2022年，5月20日，8点11分，星期二对偶规划的定义例2：某人某月营养成分的最低需求量，不同食品的营养成分含量及其单件如表所示，问某人每月怎样购买这些食品，才能满足营养要求，又可花钱最少？ABCD最低需求量（单位）含量（单位/千克） 糖524260 蛋白质321440 脂肪312535单价（元/千克）1.50.70.91.2某食品厂拟生产单一营养成分的食品糖、蛋白质和脂肪，仍用例2中的数据，问该厂如何确定食品的单价，才能在市场竞争中立于不败之地，并可获利润最多？第27页，共29页，2022年，5月20日，8点11分，星期二食品单一营养成分单价A B C D （x1） （x2） （x3） （x4）单一营养成分需求量y1y2y3 5 2 4 2 3 1 1 4 3 1 2 5 604035食品单价1.5 0.7 0.9 1.2 minZmaxW例3是例2的对偶问题，例3与例2互为对偶线性规划原规划与对偶规划具有对称性，如图所示：第28页，共29页，2022年，5月20日，8点11分，星期二原规划与对偶规划之间的关系1.原规划若有n个变量，则对偶规划有n个约束条件；原规划有m个约