运筹学第一章线性规划及单纯形法

null第一章 线性规划及单纯形法第一章 线性规划及单纯形法目 录目 录 线性规划介绍 线性规划数学模型 线性规划的图解法 线性规划的单纯形法问题的提出问题的提出在现有各项资源条件的限制下，如何确定 方案 气瓶 现场处置方案 .pdf气瓶 现场处置方案 .doc见习基地管理方案.doc关于群访事件的化解方案建筑工地扬尘治理专项方案下载 ，使预期目标达到最优；或为了达到取其目标，确定使资源消耗最少的方案。问题的提出问题的提出例1 美佳公司计划制造I，II两种家电产品。已知各制造一件时分别占用的设备A、B的台时、调试时间及A、B设备和调试工序每天可用于这两种家电的能力、各售出一件时的获利情况如 表 关于同志近三年现实表现材料材料类招标技术评分表图表与交易pdf视力表打印pdf用图表说话 pdf 1-1所示。问该公司应制造A、B两种家电各多少件，使获取的利润为最大。 nullnull例2、生产计划问题 A B 备用资源 煤 1 2 30 劳动日 3 2 60 仓库 0 2 24 利润 40 50 nullmax Z= 40x1 +50x2解:设产品A, B产量分别为变量x1 ， x2问题的提出问题的提出例3：捷运公司拟在下一年度的1-4月的4个月内需租用仓库堆放物资，已知各月所需仓库面积如表1-2。仓库租借费用随合同期限而定，合同期越长，折扣越大，具体见表1-3。租借仓库的合同每月初都可办理，每份合同具体规定租用面积数和期限。该厂可在任何一月办理租借合同，每次办理一份或若干份均可。为使租借费用最小，公司应如何选择签订合同的最优决策？ nullnull例4求：最低成本的原料混合方案null解：设每单位添加剂中原料i的用量为xi(i =1,2,3,4)minZ= 2x1 + 5x2 +6x3+8x4null补充作业、运输问题 从仓库到工厂运送单位原材料的成本，工厂对原材料的需求量，仓库目前库存分别如表所示，求成本最低的运输方案。null设xij为i 仓库运到 j工厂的原棉数量(i ＝1，2，3， j ＝1，2，3)minZ= 2x11 + x12+3x13+2x21 +2x22 +4x23 +3x31 +4x32 +2x33线性规划介绍一、线性规划模型特点 决策变量：向量(x1… xn)T 决策人要考虑和控制的因素非负 约束条件：线性等式或不等式 目标函数：Z=ƒ(x1 … xn) 线性式，求Z极大或极小线性规划介绍线性规划介绍线性规划介绍二、线性规划解决的管理问题： 合理利用线材问题； 配料问题； 投资问题； 产品生产计划； 劳动力安排； 运输问题。线性规划介绍线性规划介绍 要求 对教师党员的评价套管和固井爆破片与爆破装置仓库管理基本要求三甲医院都需要复审吗 达到某些数量上的最大化或最小化； 在一定的约束条件下追求其目标。三、线性规划问题的共同点： 线性规划的数学模型线性规划的数学模型一、线性规划数学模型的一般形式 二、线性规划数学模型的标准形式用数学语言描述用数学语言描述解：用变量x1和x2分别表示美佳公司制造家电I和II的数量。null线性规划的一般式max(min)Z=C1x1+ C2x2+…+Cnxnnull简写为：null用矩阵和向量形式表示：线性规划标准形式线性规划标准形式线性规划的标准形式 目标函数：max 约束条件 ：= 变量符号 ：≥0线性规划标准型的几种表示法（一）一般式 （二）矩阵式 （三）向量式返回线性规划标准型的几种表示法null(一) 一般型MaxZ=C1X1+ C2X2+…+CnXna11X1+ a12X2+…+ a1nXn =b1 a21X1+ a22X2+…+ a2nXn =b2 … … … … am1X1+ am2X2+…+ amnXn =bm Xj 0(j=1,2,…,n)其中 bi 0 (i=1,2,…,m) 返回null(二) 矩阵型maxZ=CX AX=b X 0 C=(C1 C2 …Cn )返回null(三) 向量型P1 X1+ P2 X2 + … +Pn Xn=b返回null(四) 化标准型 1. 约束条件 3. 变量 2. 目标函数返回 4. 右端项系数null1. 约束条件x3为松弛变量x4为剩余变量 松弛变量或剩余变量在实际问题中分别表示未被充分利用的资源和超出的资源数，均未转化为价值和利润，所以引进模型后它们在目标函数中的系数均为零。当约束条件为“≤”时，当约束条件为“≥”时，null例1maxZ=2X1+ X2+0·X3 +0·X4+0·X5+X3 =15 +X4 =24 +X5 = 5 null例2minZ=2X1+ 5X2+6X3 +8X4 4x1 + 6x2 + x3+2x4 12 x1 + x2 +7x3+5x4 14 2x2 + x3+3x4  8 xi  0 (i =1,…,4) - X5 =12 - X6 =14 - X7 =8 7）+0X5+0X6 +0X7null转化为：maxZ=40x1+ 50x2+0·x3 +0·x4+0·x5例：max Z= 40x1 +50x2松弛变量null例:剩余变量返回null2. 目标函数nullminZ=2X1+ 5X2+6X3 +8X4maxZ= -2X1 - 5X2 -6X3 -8X4返回null3.变量a、x  0的情况，令x1= x1'- x1 "b、x取值无约束的情况。令x ' ＝-x。令x= x'-x"null c、x两边有约束的情况。-6+6  x1+6  10+6 令x1' = x1 +6 0  x1' 16null将 min Z = -x1+2x2 –3x3化为标准型例：null解：① 令x3 =x4 - x5② 加松弛变量x6③加剩余变量x7 ④ 令Z'= -ZmaxZ'= x1 –2x2 +3x4 –3x5 返回nullX1+X2 +X3 -9-X1-X2 -X3  94.右端项系数返回null例：将 min Z = -X1+2X2 -3X3化为标准型null解：① 令X3 =X4 - X5② 加松弛变量X6③ 加剩余变量X7 ④ 令Z'= -ZmaxZ'= X1 -2X2 +3X4 -3X5 返回练 习练 习null线性规划的图解法线性规划的图解法定义1：满足约束(1)、(2)的X=(x1 …xn)T称为LP问题的可行解，全部可行解的集合称为可行域。定义2：满足(3)的可行解称为LP问题的最优解.null1、判别线性规划问题的求解结局； 2、是在存在最优解的条件下，找出问题的最优解。 1、在平面上建立直角坐标系 2、图示约束条件，找出可行域 3、图示目标函数和寻找最优解图解法求解的目的：图解法的步骤：null例1、maxZ=40x1+ 50x2 null(1)、建立坐标系 x1+2x2  30 x1+2x2 =30 (0,15) (30,0)3x1+2x2 =60 (0,30) (20,0) 2x2 =24 X1+2X2  30 3X1+2X2  60 2X2  24 X1 , X2 0x1 0 x1 =0 (纵) x2 0 x2=0 (横)(2)、确定可行域 解：maxZ=40x1+ 50x2null(3)、求最优解解：x1 = 15, x2 = 7.5Z=40x1+50x2 x2 =-4/5x1+Z/50maxZ =975maxZ=40x1+ 50x2null最优解：BC线段 B点 C点 x(1)=(6,12) x(2)=(15,7.5) x= x(1)+(1-) x(2) (0   1)求解nullmaxZ=1200 null无界解 无有限最优解null无解 无可行解练 习练 习max z=x1+3x2 x1+ x2≤6 s.t. -x1+2x2≤8 x1 ≥0, x2≥0 练 习练 习max z=x1+3x2 s.t. x1+ x2≤6 -x1+2x2≤8 x1 ≥0, x2≥0可行域目标函数等值线最优解64-860x1x2null由图解法得到的启示(1)、线性规划问题的解的情况有四种：唯一最优解；无穷多最优解；无界解；无可行解。(3)、若有最优解，定可在可行域的顶点得到。(2)、若线性规划可行域存在，则可行域是一个凸集。(4)、解题思路是找出凸集的各顶点的最大目标函数值。线性规划解的情况线性规划解的情况当目标函数的直线族与某约束条件直线平行，且该问题有解时。线性规划解的情况线性规划解的情况有解但可行域可伸展到无穷时线性规划解的情况线性规划解的情况约束条件直线无公共区域。线性规划的单纯形法线性规划的单纯形法一、线性规划的基本概念 二、单纯形法的迭代原理 三、单纯形法的计算步骤 四、单纯形法的进一步讨论 五、单纯形法小结线性规划的相关概念线性规划的相关概念 矩阵的秩——矩阵A中，不为零的子式的最高阶数，称为矩阵A的秩。逆矩阵——设有n阶方阵A，如果存在n阶方阵B，满足AB=BA=E，则称A阵是可逆的，且称B是A的逆矩阵。线性规划的相关概念线性规划的相关概念矩阵的初等变换： （1）对调矩阵的两行或两列； （2）以非零数k乘矩阵的某一行（列）的所有元素； （3）以数k乘矩阵的某行（列）的所有元素加到另一行（列）的对应元素上去。对方程组的系数矩阵A作初等行变换，得到新的方程组与原方程组同解。null解：用变量x1和x2分别表示美佳公司制造家电I和II的数量。null 可行解——满足方程约束条件的解X＝（x1，x2，…xn)T, 称为线性规划问题的可行解。全部可行解的集合称为可行域。最优解——使目标函数达到最大值的可行解称为最优解线性规划的基本概念MaxZ=C1X1+ C2X2+…+CnXna11X1+ a12X2+…+ a1nXn =b1 a21X1+ a22X2+…+ a2nXn =b2 … … … … am1X1+ am2X2+…+ amnXn =bm Xj 0(j=1,2,…,n)null基(基阵) ——设A为约束方程组的m×n阶系数矩阵, (n>=m)，设其秩为m，B是矩阵A中的一个m×m阶的满秩子矩阵，称B是线性规划问题的一个基。线性规划的基本概念如果矩阵A的满秩子矩阵不是唯一的， 则基阵也是不唯一的nullB==(P1,P2,…Pm)基向量——基阵B中的每一个列向量Pj称为基向量， 基变量——与基向量对应的变量称为基变量， 非基变量——基变量外的其他变量称为非基变量。线性规划的基本概念线性规划的基本概念X= (x1 … xm xm+1 … xn )T=(XB XN)T 基变量 非基变量 XB XN…nullnullnullMaxZ=C1X1+ C2X2+…+CnXna11X1+ a12X2+…+ a1nXn =b1 a21X1+ a22X2+…+ a2nXn =b2 … … … … am1X1+ am2X2+…+ amnXn =bm Xj 0(j=1,2,…,n)其中 bi 0 (i=1,2,…,m) n>=m线性规划的基本概念null找出该线性规划问题的全部基解，指出其中的基可行解，并确定最优解线性规划的基本概念MaxZ=2x1+ 3x2+x3x1+ + x3 =5 x1 + 2x2 + x4 =10 x2 +x5 =4 xj 0(j=1,2,…,5)nullMaxZ=2x1+ 3x2+x3x1+ + x3 =5 x1 + 2x2 + x4 =10 x2 +x5 =4 xj 0(j=1,2,…,5)为何不选x2、x4 、 x5作为基变量？null定理1 若线性规划问题存在可行解，则问题的可行域是凸集。 定理2 线性规划问题的基可行解X对应线性规划问题可行域的顶点。 定理3 若线性规划问题有最优解，一定存在一个基可行解是最优解线性规划的基本定理nullAX=b的求解BXB +NXN=b BXB =b-NXN B-1 BXB = B-1 （b-NXN） XB = B-1 b - B-1N XNA=(B N) X=(XB XN )T1. XN＝0，2.若同时B为单位矩阵，则 XB = b， 即X=(b，0)为AX=b的一个解线性规划的基本概念线性规划的基本概念X= (x1 … xm xm+1 … xn )T=(XB XN)T 基变量 非基变量 XB XN…返回nullMaxZ=2x1+ 3x2+x3x1+ + x3 =5 x1 + 2x2 + x4 =10 x2 +x5 =4 xj 0(j=1,2,…,5)验证nullnull基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（5，3，1，0，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=20null基变量x1、x2、x4，非基变量x3、x5、x6基础解为 （x1，x2，x3，x4，x5，x6）=（27/5，12/5，0，2/5，0，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=18null基变量x1、x2、x5，非基变量x3、x4、x6基础解为（x1，x2，x3，x4，x5，x6）=（6，3，0，0，-3，0） 是基础解，但不是可行解，不是一个极点。null基变量x1、x2、x6，非基变量x3、x4、x5基础解为（x1，x2，x3，x4，x5，x6）=（3，4，0，0，0，4） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=18null基变量x2、x3、x4，非基变量x1、x5、x6基础解为 （x1，x2，x3，x4，x5，x6）=（0，21/2，27/2，-30，0，0） 是基础解，但不是可行解。null基变量x1、x2、x3，非基变量x4、x5、x6基础解为（x1，x2，x3，x4，x5，x6）=（0，3，6，0，15，0） 是基础可行解，表示可行域的一个极点。 目标函数值为：z=15null基变量x1、x2、x3，非基变量x4、x5、x6基础解为 （x1，x2，x3，x4，x5，x6）=（0，11/2，-3/2，0，0，10） 是基础解但不是可行解。null※ 基本解中最多有m个非零分量。null基阵B非基阵N求出一个基本解，并判断是不是可行解？null令X1 = X2 =0, 则 X3=30, X4=60, X5=24null求出基变量是x1 , x3 , x4的基解，是不是可行解？nullnull∴X=(1, 0, 3/2, 3/2)T 是 基本可行解 单纯形法的迭代原理单纯形法的迭代原理找出一个基可行解判断是否最优转换到相邻的基可行解找到最优解否是单纯形法计算步骤单纯形法计算步骤1.求初始基可行解，列出单纯形表 例题5：用单纯形法求解线性规划问题例题5：用单纯形法求解线性规划问题解： 1、先将上述问题化成标准形式有解： 1、先将上述问题化成标准形式有找到一个初始基可行解X=(0,0,15,24,5)T15245P1P2P3P4P5null2、列初始单纯形表：nullX1进基；X4出基；nullx123、列新单纯形表：3、列新单纯形表：X2进基；X5出基；nullx21nullnull4、列新单纯形表：解为：X=(7/2,3/2,15/2,0,0)。目标函数值为: maxZ=2x1+x2+0x3+0x4+0x5 =2×7/2+1×3/2+0×15/2+0+0=8.5 练习题 用券下载整式乘法计算练习题幼小衔接专项练习题下载拼音练习题下载凑十法练习题下载幼升小练习题下载免费 练习题 解：原问题化为标准型null列初始单纯形表null列初始单纯形表X2入基，X6出基nullnull作业：人工变量法人工变量法当化为标准形后的约束条件的系数矩阵中不存在单位矩阵时，可以人为地增加变量，在最优解中人工变量取值必须为零。为此，令目标函数中人工变量的系数为任意大的负值－M。这种人为增加变量的方法称为人工变量法，亦称大M法。null例1：Max z= 6x1 +4x2 2x1 +3x2  100 4x1 +2x2  120 x1 =14 x2  22 x1 ,x2 0null解：化成标准型nullmaxZ=6x1+4x22x1 +3x2 +x3 =100 4x1 +2x2 +x4 =120 x1 =14 x2 - x5 = 22 x1 … x7 0加人工变量+x6+x7-Mx6 -Mx7null列初始单纯形表null 6 4 0 0 0 - M - M CB xB b x1 x2 x3 x4 x5 x6 x7 0 x3 100 2 3 1 0 0 0 0 0 x4 120 4 2 0 1 0 0 0 -M x6 14 1 0 0 0 0 1 0 -M x7 22 0 1 0 0 -1 0 1 -36 M M +6 M +4 0 0 - M 0 0Cj0 x3 72 0 3 1 0 0 -2 0 0 x4 64 0 2 0 1 0 -4 0 6 x1 14 1 0 0 0 0 1 0 -M x7 22 0 1 0 0 -1 0 1 84-22M 0 M+4 0 0 -M 6-M 0nullCj0 x3 6 0 0 1 0 (3) -2 -3 0 x4 20 0 0 0 1 2 -4 -2 6 x1 14 1 0 0 0 0 1 0 4 x2 22 0 1 0 0 -1 0 1 172 0 0 0 0 4 6-M 4-M 0 x5 2 0 0 1/3 0 1 -2/3 -1 0 x4 16 0 0 -2/3 1 0 -8/3 0 6 x1 14 1 0 0 0 0 1 0 x2 24 0 1 1/3 0 0 -2/3 -2 180 0 0 -4/3 0 0 -M-10/3 -M 6 4 0 0 0 - M - M CB xB b x1 x2 x3 x4 x5 x6 x7解为：X=(14,24,0,16,2)。目标函数值为: maxZ=6x1+4x2 =6×14+4×24=180练 习练 习用大M法求解下列问题：两阶段法两阶段法对添加人工变量后的线性规划问题分两个阶段来计算，称为两阶段法。两阶段法两阶段法 第一阶段是先求解一个目标函数中只包含人工变量的线性规划问题，即令目标函数中其它变量的系数取零，人工变量的系数取某个正的常数(一般取1)，在保持原问题约束条件不变的情况下求这个目标函数极小化时的解。 null作辅助问题原问题两阶段法两阶段法在第一阶段中，当人工变量取值为0时，目标函数值也为0。这时候的最优解就是原线性规划问题的一个基可行解。如果第一阶段求解结果最优解的目标函数值不为0，也即最优解的基变量中含有非零的人工变量，表明原线性规划问题无可行解。null解题过程：第1阶段：解辅助问题当进行到最优表时， ①若W=0, 则得到原问题的一个 基本可行解，转入第2阶段。 ②若W>0, 则判定原问题无可行解。 第2阶段：去除人工变量，求解原问题。第一阶段的最优解为原问题的初始基可行解。nullmaxZ= -x1 +2x2 x1 +x2  2 -x1 +x2  1 x2  3 x1 x2 0例： x1 +x2 -x3 =2 -x1 +x2 -x4 =1 x2 +x5 =3 x1 … x5 01.化标准型：maxZ= -x1 +2x2 +x6+x72.增加人工变量，构造单位矩阵：,x6, x7  0null3. 建立只包含人工变量的辅助问题。minW=x6 +x7 x1 +x2 -x3 +x6 =2 -x1 +x2 -x4 +x7 =1 x2 +x5 =3 x1 … x7 03null 0 0 0 0 0 1 1 CB xB b x1 x2 x3 x4 x5 x6 x7 1 x6 2 1 1 -1 0 0 1 0 1 x7 1 -1 (1) 0 -1 0 0 1 0 x5 3 0 1 0 0 1 0 0 3 0 -2 1 1 0 0 00 x1 1/2 1 0 -1/2 1/2 0 1/2 -1/2 0 x2 3/2 0 1 -1/2 -1/2 0 1/2 1/2 0 x5 3/2 0 0 -1/2 1/2 1 -1/2 -1/2 0 0 0 0 0 0 1 11 x6 1 2 0 -1 1 0 1 -1 0 x2 1 -1 1 0 -1 0 0 1 0 x5 2 1 0 0 1 1 0 -1 1 -2 0 1 -1 0 0 2解为：X=(1/2,3/2,0,0,3/2,0,0)。目标函数值为:minW=x6+x7 =0 可转入第二阶段。去除人工变量，以第一阶段最优解为基可行解。null解为：X=(0,3,1,2,0)。目标函数值为:maxZ=-x1+2x2 =64.去除人工变量，以第一阶段的最优解为基可行解,求解原问题。0 x4 1 2 0 -1 1 0 2 x2 2 1 1 -1 0 0 0 x5 1 -1 0 1 0 1 4 -3 0 2 0 00 x4 2 1 0 0 1 1 2 x2 3 0 1 0 0 1 0 x3 1 -1 0 1 0 1 6 -1 0 0 0 -2计算中的几个问题计算中的几个问题☼目标函数极大化时解的最优性判别 以σi ≥ 0作为判别表中解是否最优的标志 ☼目标函数极小化时解的最优性判别 以σi 0作为判别表中解是否最优的标志1、目标函数情况null2、退化解null 在下一次迭代中有一个或几个基变量为0，从而出现退化解。可能会导致循环，永远达不到最优解。退化解null退化问题解决办法Bland 原则 （1976 年 第9届国际数学规划大会）null3、无可行解的判别 当线性规划问题中添加人工变量后，无论用人工变量法或两阶段法，初始单纯形表中的解因含非零人工变量，故实质上是非可行解。当求解结果出现所有σi0时， 如基变量中仍含有非零的人工变量(两阶段法求解时第一阶段目标函数值不等于零)，表明问题无可行解。单纯形法小结单纯形法小结null找出初始基可行解 列出初始单纯形表计算检验数σi所有σi ≤ 0基变量中 含人工变量有非基变量 检验数为零唯一 最优解对某一σi>0 有Pi ≤ 0无界解无可行解无穷多 最优解迭代运算 1.用xk替换xl 2.列出新的单纯形表 1）对主元素行（第l行） bl’＝bl/alk,alj’/alk 2)其他行（i≠l） bi＝bi－aik·bl/alk，aij’=aij-aik·alj/alk单纯形法计算步骤框图作 业作 业P43 1.1(2)(3) 1.2(2) 1.8 1.13 1.16