《线性规划》PPT课件.ppt

第二章 线性规划 Linear Programming,1 对线性规划的回顾 2 线性规划在工商管理中的应用 3 线性规划问题的计算机求解 4 内点算法简介 5 案例分析,线性规划定义：求一组变量x1、 x2、 、 xn的值，使之满足关于这组变量的若干个线性等式或不等式的约束条件，而且使这组变量的一个线性函数取到极大值(或极小值)。这些变量称为决策变量，所要优化的函数称为目标函数，决策变量是取实数值的连续变量。这样的问题称为线性规划。 线性规划模型的结构 目标函数：max，min max z(min f)=cjxj 约束条件：,=, aijxj (=, ) bi (i=1,2, m) 变量符号：0,unr,0 xj 0 (j=1,2, n),线性规划数学模型的标准形式（标准型） 目标函数求最大值 函数约束条件全为等式 决策变量全为非负 函数约束条件右端项全为非负,1 对线性规划的回顾,下述5种情况如何化为标准型？ 1. 约束条件为不等式 2.目标函数取最小值 3. xj为自由变量 4. 资源系数bi 0 5. mn,1 对线性规划的回顾,非标准形式化为标准形式总结,1 对线性规划的回顾,线性规划问题解的概念 可行解：满足函数约束条件和非负约束条件的解 最优解：使目标函数达到最大值的可行解 基：设A是约束方程组的mn阶系数矩阵，B是矩阵A中 mm阶非奇异子矩阵，称B是线性规划问题的一个基 基向量：基B中每一个列向量Pj 非基向量：A中其余列向量Pj（不在B中） 基变量：与基向量Pj对应的决策变量xj 非基变量：与非基向量对应的决策变量 基解 基可行解：满足非负约束条件的基解 可行基：对应于基可行解的基,1 对线性规划的回顾,1 可行解与最优解：,最优解一定是可行解，但可行解不一定是最优解。,基解不一定是可行解，可行解也不一定是基解。,2 可行解与基解：,3 可行解与基可行解：,基可行解一定是可行解，但可行解不一定是基可能解。,基可行解一定是基解，但基解不一定是基可行解。,4 基本解与基可行解：,1 对线性规划的回顾,线性规划问题解的概念,6 问题：最优解与基可行解？,最优解不一定是基可行解，基可行解也不一定是最优解。,5 最优解与基本解：,最优解不一定是基解，基解也不一定是最优解。,为什么？,1 对线性规划的回顾,考虑无穷多最优解的情况。,线性规划问题解的概念,线性规划解的性质,定理1 线性规划的可行域 R 是一个凸集，且有有限个顶点。,定理3 若线性规划有最优解，则必存在一个基可行解是最优解。,线性规划问题的可行域是一个凸集。,线性规划的每一个基可行解对应可行域的一个顶点(基可行解与可行域顶点一一对应)。,定理2 X是线性规划可行域 R 顶点的充要条件是 X是 线性规划的基本可行解。,1 对线性规划的回顾,若线性规划有最优解，则一定在凸集的某个（些）顶点上 达到最优，即此时一定存在某个顶点是最优解。,定理4 若线性规划在可行域的两个顶点上达到最优，则在两个顶点的连线上也达到最优。,若线性规划在两个顶点以上达到最优,则一定有无穷多个最优解。,最优解不一定是基可行解，基可行解也不一定是最优解。,单纯形法,一、单纯形法的解题思路 从某一基可行解开始，转化到另一个相邻的基可行解，并且使相应的目标函数值有改进。即从可行域的一个顶点沿约束边界转换到可行域的另一个相邻的且使目标函数值有改进的顶点，直到目标函数值到达最优时的顶点为止。 二、单纯形法的含义 单纯形法是一种迭代算法，首先找到一个初始基可行解，然后判断它是否为最优解，如果是就停止迭代，否则，按照一定的法则，再找到一个更好且与当前基可行解相邻的基可行解，再进行判断，直到找不到更好的基可行解或判断问题无解为止。,1 对线性规划的回顾,三、单纯形法的解题步骤 1、找出初始可行基，确定初始基可行解，建立初始单纯形表。,1 对线性规划的回顾,单纯形法,例：线性规划问题数学模型的某种标准形式,1 对线性规划的回顾,单纯形法(单纯形法的解题步骤),2、检验各非基变量xj（j=m+1，m+2，n）的检验数j，若j0，则已得最优解，停止计算，否则转入3。 3、在j0 （j=m+1，m+2，n）中，若有某个k对应的xk的系数列向量Pk0，则此线性规划问题存在无界解，停止计算，否则转入4。 4、根据 ，确定xk为换入变量，通过 ，计算确定xl为换出变量，转入5。,1 对线性规划的回顾,5、以alk为主元素进行迭代，把xk所对应的列向量 将xB列中xl的换为xk，得到新的单纯形表，重复25，直至终止。,单纯形法(单纯形法的解题步骤),单纯形法小结,单纯形表中解的表示形式 1、唯一最优解：最终单纯形表中，所有非基变量检验数j0 2、无穷多最优解：最终单纯形表中，某非基变量检验数j0 3、无界解：某检验数j0对应变量的系数列向量Pk0 4、退化基可行解：一个或几个基变量取值0的基可行解 出现退化基可行解，可能导致从某个基开始，经过若干次迭代后又回到原来的基，即单纯形法出现了循环，永远达不到最优解，导致计算失败。 为避免出现死循环，法则如下： 选择换入变量时，若有几个正的检验数具有相同的最大值，则选择下标最小的对应的非基变量作为换入变量 选择换出变量时，若按规则计算，有几个比值同时达到最小，则选择下标最小的对应的基变量作为换出变量,1 对线性规划的回顾,线性规划的对偶理论,1 对线性规划的回顾,1 对线性规划的回顾,对偶问题的性质,【性质1】对称性定理：对偶问题的对偶是原问题。 【性质2】弱对偶原理（弱对偶性）：设X 和Y 分别是问题（P）和（D）的任一可行解，则必有 z(X) f(Y). 【性质3】最优性判别定理：若 X* 和 Y* 分别是 P 和 D 的可行解且CX* = Y* b， 则X*, Y*分别是问题 P和D 的最优解。 【性质4】 (强对偶性) 原规划与对偶规划同有最优解，且两者最优值相等。 【性质5】互补松弛定理：设X、Y各为原规划与对偶规划的一个可行解，则X、Y为最优解的充分必要条件为 Y XS = YS X = 0。 【性质6】 (基解对应性) 原规划单纯形表中检验数行对应对偶规划的一个基解。,推论.若X和Y分别是问题（P）和（D）的可行解，则 CX是（D）的目标函数最小值的一个下界；Yb是（P）的目标函数最大值的一个上界。 推论.在一对对偶问题（P）和（D）中，若其中一个问题可行但目标函数无界，则另一个问题不可行；反之不成立。这也是对偶问题的无界性。 推论.在一对对偶问题（P）和（D）中，若一个可行（如P），而另一个不可行，（如D），则该可行的问题无界。,原规划与对偶规划解之间的关系,1 对线性规划的回顾,对偶单纯形法,1 对线性规划的回顾,基本思想是：从原规划的一个基本解出发，此基本解不一定可行，但它对应着一个对偶可行解（检验数非正），所以也可以说是从一个对偶可行解出发；然后检验原规划的基本解是否可行，即是否有负的分量，如果有小于零的分量，则进行迭代，求另一个基本解，此基本解对应着另一个对偶可行解（检验数非正）。如果得到的基本解的分量皆非负则该基本解为最优解。也就是说，对偶单纯形法在迭代过程中始终保持对偶解的可行性（即检验数非正），使原规划的基本解由不可行逐步变为可行，当同时得到对偶规划与原规划的可行解时，便得到原规划的最优解。,对偶单纯形法求解线性规划问题过程：,建立初始对偶单纯形表,对应一个基本解,所有检验数均非正,转2； 若b0,则得到最优解,停止;否则,若有bk0则选k行的基变量为出基变量,转3 若所有akj0( j = 1,2,n )，则原问题无可行解,停止;否则,若有akj0 则选 =minj / akjakj0=r/akr那么 xr为进基变量,转4； 4. 以akr为转轴元,作矩阵行变换使其变为1,该列其他元变为0,转2。,单纯形法和对偶单纯形法步骤,1 对线性规划的回顾,21,例6 用单纯形表求解例1。（见书P25） 解 已知该问题的标准型为: 取初始基变量为松弛变量x3、x4、x5，得初始基可行解X(0) = (0, 0, 180, 400, 210)T (此可行解对应图形法中的O点,参见教材p17) 。,22,建立初始单纯形表(表1-4)： 因j行中，1 = 31为最大正检验数，故选x1为入基变量；又因i列中最小比值在第一行，故定x3为出基变量。合之，知主元为6，用将其标出。,表1-4,31,180/6,6,23,作旋转变换得新单纯形表：,第1行=第1行/6,第2行=第2行-4第1行,第3行=第3行-3 第1行,得新基可行解X(1) = (30, 0, 0, 280, 120)T (此可行解对应图形法中的D点,参见教材p17)。由于只有2 = 35/3 0，故x2为入基变量；又因最小比值在第三行，故x5为出基变量。合之，知主元为4。,24,因所有的检验数j0 (j = 1, 2, , 5)，故当前基可行解X(2) = (20, 30, 0, 20, 0)T(此可行解对应图形法中的C点,参见教材p17)为最优解，删去松弛变量，即得原线性规划之最优解为X* = (20, 30) T，最优值z* = 1280。,以4为主元作旋转变换得下表：,25,2 线性规划在工商管理中的应用,2.1 人力资源分配的问题 2.2 生产计划问题 2.3 配料问题 2.4 投资问题,26,2.1 人力资源分配的问题,例1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?,解：设 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,2.1 人力资源分配的问题,例2一家中型的百货商场，它对售货员的需求经过统计分析如下表所示。为了保证售货人员充分休息，售货人员每周工作5天，休息两天，并要求休息的两天是连续的。问应该如何安排售货人员的作息，既满足工作需要，又使配备的售货人员的人数最少？,2.1 人力资源分配的问题,29,解：设 xi ( i = 1,2,7)表示星期一至日开始休息的人数,这样我们建立如下的数学模型。 目标函数： Min x1 + x2 + x3 + x4 + x5 + x6 + x7 约束条件：s.t. x1 + x2 + x3 + x4 + x5 28 x2 + x3 + x4 + x5 + x6 15 x3 + x4 + x5 + x6 + x7 24 x4 + x5 + x6 + x7 + x1 25 x5 + x6 + x7 + x1 + x2 19 x6 + x7 + x1 + x2 + x3 31 x7 + x1 + x2 + x3 + x4 28 x1,x2,x3,x4,x5,x6,x7 0,2.1 人力资源分配的问题,例3某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？,2.2 生产计划问题,解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种 产品的件数，x4,x5 分别为由外协铸造再由本公司加工和装配的甲、乙两 种产品的件数。 求 xi 的利润：利润 = 售价 - 各成本之和 产品甲全部自制的利润 =23-(3+2+3)=15 产品甲铸造外协，其余自制的利润 =23-(5+2+3)=13 产品乙全部自制的利润 =18-(5+1+2)=10 产品乙铸造外协，其余自制的利润 =18-(6+1+2)=9 产品丙的利润 =16-(4+3+2)=7 可得到 xi （i = 1,2,3,4,5） 的利润分别为 15、10、7、13、9 元。,2.2 生产计划问题,通过以上分析,可建立如下的数学模型: 目标函数： Max 15x1 + 10x2 + 7x3 + 13x4 + 9x5 约束条件： 5x1 + 10x2 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 0,2.2 生产计划问题,例4永久机械厂生产、三种产品，均要经过A、B两道工序加工。设有两种规格的设备A1、A2能完成 A 工序；有三种规格的设备B1、B2、B3能完成 B 工序。可在A、B的任何规格的设备上加工； 可在任意规格的A设备上加工，但对B工序，只能在B1设备上加工；只能在A2与B2设备上加工。数据如表。问：为使该厂获得最大利润，应如何制定产品加工方案？,2.2 生产计划问题,34,解：设 xijk 表示第 i 种产品，在第 j 种工序上的第 k 种设备上加工的数量。建立如下的数学模型: s.t. 5x111 + 10x211 6000 （ 设备 A1 ） 7x112 + 9x212 + 12x312 10000 （ 设备 A2 ） 6x121 + 8x221 4000 （ 设备 B1 ） 4x122 + 11x322 7000 （ 设备 B2 ） 7x123 4000 （ 设备 B3 ） x111+ x112- x121- x122- x123 = 0 （产品在A、B工序加工的数量相等） x211+ x212- x221 = 0 （产品在A、B工序加工的数量相等） x312 - x322 = 0 （产品在A、B工序加工的数量相等） xijk 0 , i = 1,2,3; j = 1,2; k = 1,2,3,2.2 生产计划问题,2.2 生产计划问题,目标函数为计算利润最大化，利润的计算公式为： 利润 = （销售单价 - 原料单价）* 产品件数之和 -（每台时的设备费用*设备实际使用的总台时数）之和。 这样得到目标函数： Max(1.25-0.25)(x111+x112)+(2-0.35)x221+(2.80-0.5)x312 300/6000(5x111+10x211)-321/10000(7x112+9x212+12x312)- 250/4000(6x121+8x221)-783/7000(4x122+11x322)-200/4000(7x123). 经整理可得： Max0.75x111+0.7753x112+1.15x211+1.3611x212+1.9148x312-0.375x121-0.5x221-0.4475x122-1.2304x322-0.35x123,2.3 配料问题,例5某工厂要用三种原料1、 2、3混合调配出三种不同规格的 产品甲、乙、丙，数据如右表。 问：该厂应如何安排生产，使利 润收入为最大？,解：设 xij 表示第 i 种（甲、乙、丙）产品中原料 j 的含量。这样我们建立数学模型时，要考虑： 对于甲： x11，x12，x13； 对于乙： x21，x22，x23； 对于丙： x31，x32，x33； 对于原料1： x11，x21，x31； 对于原料2： x12，x22，x32； 对于原料3： x13，x23，x33； 目标函数： 利润最大，利润 = 收入 - 原料支出 约束条件： 规格要求 4 个； 供应量限制 3 个。,2.3 配料问题,利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲乙丙使用的原料单价*原料数量，故有 目标函数 Max 50（x11+x12+x13）+35（x21+x22+x23）+25（x31+x32+x33）-65（x11+x21+x31）-25（x12+x22+x32）-35（x13+x23+x33） = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 约束条件： 从第1个表中有： x110.5(x11+x12+x13) x120.25(x11+x12+x13) x210.25(x21+x22+x23) x220.5(x21+x22+x23),2.3 配料问题,从第2个表中，生产甲乙丙的原材料不能超过原 材料的供应限额，故有 (x11+x21+x31)100 (x12+x22+x32)100 (x13+x23+x33)60 通过整理，得到以下模型：,2.3 配料问题,例5（续） 目标函数：Max z = -15x11+25x12+15x13-30x21+10x22-40x31-10x33 约束条件： s.t. 0.5 x11-0.5 x12 -0.5 x13 0 （原材料1不少于50%） -0.25x11+0.75x12 -0.25x13 0 （原材料2不超过25%） 0.75x21-0.25x22 -0.25x23 0 （原材料1不少于25%） -0.5 x21+0.5 x22 -0.5 x23 0 （原材料2不超过50%） x11+ x21 + x31 100 (供应量限制） x12+ x22 + x32 100 (供应量限制） x13+ x23 + x33 60 (供应量限制） xij 0 , i = 1,2,3; j = 1,2,3,2.3 配料问题,例6.汽油混合问题。一种汽油的特性可用两种指标描述，用“辛烷数”来定量描述其点火特性，用“蒸汽压力”来定量描述其挥发性。某炼油厂有1、2、3、4种标准汽油，其特性和库存量列于表1中，将这四种标准汽油混合，可得到标号为1，2的两种飞机汽油，这两种汽油的性能指标及产量需求列于表2中。问应如何根据库存情况适量混合各种标准汽油，既满足飞机汽油的性能指标，又使2号汽油满足需求，并使得1号汽油产量最高？,表 1,表 2,2.3 配料问题,解：设xij为飞机汽油i中所用标准汽油j的数量(L)。 目标函数为飞机汽油1的总产量：,库存量约束为：,产量约束为飞机汽油2的产量：,由物理中的分压定律， 可得有关蒸汽压力的约束条件：,同样可得有关辛烷数的约束条件为：,综上所述，得该问题的数学模型为：,2.3 配料问题, 2.4 投资问题,例7某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项 目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第 一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额 不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规 定最大投资额不能超过80万元；项目D：需在第二年年初投资，第五年末能收回本 利155%，但规定最大投资额不能超过100万元。 据测定每万元每次投资的风险指数如右表： 问： a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？ b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？,解： 1）确定决策变量：连续投资问题 设 xij ( i = 15，j = 14)表示第 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 x24,44,2）约束条件： 第一年：A当年末可收回投资，故第一年年初应把全部资金投出去，于是 x11+ x12 = 200； 第二年：B次年末才可收回投资，故第二年年初有资金1.1 x11，于是 x21 + x22+ x24 = 1.1x11； 第三年：年初有资金 1.1x21+ 1.25x12，于是 x31 + x32+ 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 3）目标函数及模型： a) Max z = 1.1x51+ 1.25x42+ 1.4x33 + 1.55x24 s.t. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； 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 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）, 2.4 投资问题,45,b)所设变量与问题a相同，目标函数为风险最小，有 Min f =x11+x21+x31+x41+x51+3(x12+x22+x32+x42)+4x33+5.5x24 在问题a的约束条件中加上“第五年末拥有资金本利在330万元”的条件， 于是模型如下： Min f = (x11+x21+x31+x41+x51)+3(x12+x22+x32+x42)+4x33+5.5x24 s.t.