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

1、第一章 线 性 规 划及单纯形法,1、一般线性规划问题的数学模型,2、图解法,4、单纯形法的计算步骤,5、单纯形法的进一步讨论,6、线性规划模型的应用,3、单纯形法原理,为了完成一项任务或达到一定的目的，怎样用最少的人力、物力去完成或者用最少的资源去完成较多的任务或达到一定的目的，这个过程就是规划。,例1 有一正方形铁皮，如何截取x使容积为最大？,x,a,此为无约束极值问题,一、一般线性规划问题的数学模型,（一）、问题的提出,例2 已知资料如下表所示，问如何安排生产才能使利润最大？或如何考虑利润大，产品好销。,模 型,max Z = 2x1 + 3x2,x1 0 , x2 0,s.t.,2x1

2、 + 2x2 12 x1 + 2x2 8 4x1 16 4x2 12,此为带约束的极值问题,1、问题中总有未知的变量，需要我们去解决。,要求：有目标函数及约束条件，一般有非负条件存在，由此组成规划数学模型。,如果在规划问题的数学模型中，变量是连续的（数值取实数）其目标函数是有关线性函数（一次方），约束条件是有关变量的线性等式或不等式，这样，规划问题的数学模型是线性的。反之，就是非线性的规划问题（其中一个条件符合即可）。,（二）线性规划问题的数学模型,目标函数：,约束条件：,2、线性规划数学模型的一般形式,也可以记为如下形式：,目标函数：,约束条件：,如将上例用表格表示如下：,设变量,向 量 形

3、 式：,矩阵形式：,规 划,确定型 随机型,静态规划 动态规划,线 性规 划 非线性规划,整数规划 非整数规划,整数规划 非整数规划,3、规划类型,（三）线性规划问题的标准形式,1、标准形式,其中bi为非负,2、特征： .目标函数为求极大值，也可以用求极小值； .所有约束条件（非负条件除外）都是等式，右端常数项为非负； .变量为非负。,3、转换方式：,.目标函数的转换,如果是求极小值即 ，则可将目标函数乘以（1），可化为求极大值问题。,也就是：令 ，可得到上式。,即,.约束方程的转换：由不等式转换为等式。,称为松弛变量,称为剩余变量,.变量的变换,若存在取值无约束的变量 ，可令 其中：,例 1

4、 将下列线性规划问题化为标准形式,为无约束（无非负限制）,解: 用 替换 ，且 ，,将第3个约束方程两边乘以（1）,将极小值问题反号，变为求极大值,标准形式如下：,引入变量,例2 将线性规划问题化为标准型,为无约束,解：,例3 将下述线性规划模型化为标准形式。,标准形式,（四）线性规划问题的解,1、解的概念, 可行解：满足约束条件、的解为可行解。所有解的集合为可行解的集或可行域。, 最优解：使目标函数达到最大值的可行解。, 基：B是矩阵A中mn阶非奇异子矩阵（B0），则B是一个基。,则称 Pj ( j = 1 2 m) 为基向量。 Xj 为基变量，否则为非基变量。, 基解：满足条件，但不满足条

5、件的所有基对应的解，最多为 个。, 基可行解：满足非负约束条件的基解，简称基可行解。, 可行基：对应于基可行解的基称为可行基。,非可行解,可 行 解,基解,基可行解,Max z=2x1+3x2 st. x1+x23 x1+2x24 x1,x20,Max z=2x1+3x2 +0 x3 +0 x4 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2, x3 , x40,A=,x1 x2 x3 x4,1 1 1 0 1 2 0 1,可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。,设,B=,1 0 0 1,，令,，则,| B |=10,令 x1=x2 =0

6、，则 x3 =3, x4=4，X=(0,0,3,4)T,例：,x3 x4,基变量,令,B=,1 1 1 0,x1 x3,，则,令 x2=x4 =0，则 x3 =-1, x1=4，X=(4,0,-1,0)T,| B |=-10,非基可行解,基可行解,标准化,建立直角坐标 ，图中阴影部分及边界上的点均为其解，是由约束条件来反映的。,例1,二、图 解 法,0,1 2 3 4 5 6 7 8,1 2 3 4 5 6,作 图, 最 优 解：x1 = 4 x2 = 2,有唯一最优解，Z = 14,x2,x1,(4 2),例2,例3,无穷多最优解,无界解,x1,x1,x2,x2,x1,x2,无可行解,例4,

7、练习1, 线性规划问题的可行域是凸集（凸多边形）。,凸集,凸集,不是凸集,顶 点, 最优解一定是在凸集的某一顶点实现（顶点数目不超过 个）,三、单纯形法原理, 先找一个基可行解，与周围顶点比较，如不是最大，继续比较，直到找出最大为止。,3、解的情况,唯 一 解 无 穷 解 无 界 解 无可行解,有最优解,无最优解,（一）、基本思想,将模型的一般形式变成标准形式，再根据标准型模型，从可行域中找一个基可行解，并判断是否是最优。如果是，获得最优解；如果不是，转换到另一个基可行解，当目标函数达到最大时，得到最优解。,（二）、线性规划模型的标准形式,1、标准形式,四、单纯形法,（三）、单纯形法,例一、,

8、变成标准型,约束方程的系数矩阵,为基变量,为非基变量,I 为单位矩阵且线性独立,Max z=2x1+3x2 st. x1+x23 x1+2x24 x1,x20,Max z=2x1+3x2 +0 x3 +0 x4 st. x1+x2+x3=3 x1+2x2+x4=4 x1, x2, x3 , x40,A=,x1 x2 x3 x4,1 1 1 0 1 2 0 1,可行解：X=(0，0)T，X=(0，1)T，X=(1/2，1/3)T 等。,设,B=,1 0 0 1,，令,，则,| B |=10,令 x1=x2 =0，则 x3 =3, x4=4，X=(0,0,3,4)T,回顾：,x3 x4,基变量,令

9、,B=,1 1 1 0,x1 x3,，则,令 x2=x4 =0，则 x3 =-1, x1=4，X=(4,0,-1,0)T,| B |=-10,非基可行解,基可行解,标准化,令：,则：, 基本可行解为（0 0 12 8 16 12） 此时，Z = 0,然后，找另一个基可行解。即将非基变量换入基变量中，但保证其余的非负。如此循环下去，直到找到最优解为止。,注意：为尽快找到最优解，在换入变量时有一定的要求。如将目标系数大的先换入等。,找出一个初始可行解,是否最优,转移到另一个目标函数 （找更大的基可行解）,最优解,是,否,循 环,直到找出为止，核心是：变量迭代,结束,其步骤总结如下：,当 时， 为换

10、入变量,确定换出变量,为换出变量,接下来有下式：,用高斯法，将 的系数列向量换为单位列向量，其步骤是：,结果是：,代入目标函数：,有正系数表明：还有潜力可挖，没有达到最大值；,此时：令 得到另一个基本可行解 （0，3，6，2，16，0）,有负系数表明：若要剩余资源发挥作用，就必须支付附加费用。当 时，即不再利用这些资源。,如此循环进行，直到找到最优为止。,本例最优解为： （4，2，0，0，0，4）,（四）、单纯形表,例 题：,2 3 0 0 0 0,12/2,8/2,12/4,3,x2,3,0,1,0,0,0,1/4,2,6,2,0,1,0,0,-1/2,1,0,0,1,0,0,-1/2,-9

11、,0,0,0,0,2,-3/4,2 0 0 0 0 -3/4,6/2,2,16/4,0 0 0 -2 0 1/4,-13,-Z,4 4 12,0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4,2 2 8 3,x3 x1 x5 x2,0 2 0 3,x1 x2 x3 x4 x5 x6,b,xB,cB,2 3 0 0 0 0,cj,0 0 0 -2 0 1/4,-13,-Z,4 4 12,0 0 1 -2 0 1/2 1 0 0 1 0 -1/2 0 0 0 -4 1 2 0 1 0 0 0 1/4,2 2 8 3,x3 x1 x5

12、x2,0 2 0 3,x1 x2 x3 x4 x5 x6,b,xB,cB,2 3 0 0 0 0,cj,练习,（一）、模型情况 变 量：xj0 xj0 xj无约束 结 1、组成 约束条件： = b 目标函数： max min 果 2 、变量 xj0 令 xj= -xj ， xj0 xj0 不处理 xj 无约束 令xj = xj xj, xj0 , xj0,唯一最优 无穷最优 无界解 无可行解,五、单纯形法的进一步讨论,例：,加入人工变量后，目的是找到一个单位向量，叫人工基。其目标价值系数要确定，但不能影响目标函数的取值。一般可采用两种方法处理：大M法和两阶段法。,即假定人工变量在目标函数中的系

13、数为M（任意大正数），如果是求极大值，需加-M；如果是求极小值，需加M。如基变量中还存在M，就不能实现极值。,.大M法：,最优解为（4 1 9 0 0 0 0），Z = 2,最优解为（4 1 9 0 0 0 0），Z = 2,用计算机处理数据时，只能用很大的数代替M,可能造成计算机上的错误，故多采用两阶段法。,第一阶段： 在原线性规划问题中加入人工变量，构造如下模型：,.两阶段法：,对上述模型求解（单纯形法），若W=0,说明问题存在基本可行解，可以进行第二个阶段；否则，原问题无可行解，停止运算。,第二阶段：在第一阶段的最终表中，去掉人工变量，将目标函数的系数换成原问题的目标函数系数，作为第二阶

14、段计算的初始表（用单纯形法计算）。,例：,第一阶段,第二阶段,最优解为（4 1 9 0 0），目标函数 Z = -2,设规划模型约束条件为 ，需加入人工变量 ，而得到一个mm的单位矩阵，即基变量组合。因人工变量为虚拟变量，且存在于初始基本可行解中，需要将它们从基变量中替换出来。若基变量中不含有非零的人工变量，表示原问题有解。若当 ，而还有人工变量（非零）时，则表示原问题无可行解。,1、目标函数：max , min,3、无可行解的判断：运算到检验数全负为止， 仍含有人工变量，无可行解。,5、退化： 即计算出的（用于确定换出变量）存在有两个以上相同的最小比值，会造成下一次迭代中由一个或几个基变量等

15、于零，这就是退化（会产生退化解）。 虽任意换出变量，目标函数值不变，但此时不同的基却表示为同一顶点，其特例是永远达不到最优解。需作如下处理： .当 中出现两个以上最大值时，选下标最小的非基变量为换入变量； .当中出现两个以上最小值时，选下标最小的基变量为换出变量。,根据上表列出初始单纯形表 A,（二）、线性规划小结,A,练习,作业,一般而言，一个经济、管理问题凡是满足以下条件时，才能建立线性规划模型。 .要求解问题的目标函数能用数值指标来反映，且为线性函数； .存在着多种方案； .要求达到的目标是在一定条件下实现的，这些约束可用线性等式或不等式描述。,六、线性规划模型的应用,（一）、资源的合理

16、利用,一般提法： 某厂计划在下一生产周期内生产B1,B2, Bn种产品，要消耗A1,A2, Am种资源，已知每件产品所消耗的资源数、每种资源的数量限制以及每件产品可获得的利润如表所示，问如何安排生产计划，才能充分利用现有的资源，使获得的总利润最大？,（二）、生产组织与计划问题,一般提法：某工厂用机床A1,A2, Am 加工B1,B2, Bn 种零件。在一个周期内，各机床可能工作的机时（台时），工厂必须完成各种零件的数量、各机床加工每个零件的时间（机时/个）和加工每个零件的成本（元/个）如表所示，问如何安排各机床的生产任务，才能完成加工任务，又使总成本最低？,（三）、合理下料问题,一般提法 设用

17、某种原材料截取零件A1,A2, Am的毛坯。根据以往的经验，在一种原材料上可以有B1,B2, Bn种不同的下料方式，每种下料方式可截得的各种毛坯个数以及每种零件的需要量如表所示，问应如下料才能既满足需要又使原材料消耗最少？,现有一批某种型号的圆钢长8米，需要截取2.5米长的毛坯100根，长1.3米的毛坯200根。问如何才能既满足需要，又能使总的用料最少？,100 200,3 2 1 0 0 2 4 6,2.5米 1.3米,需要 根数,一 二 三 四,下料 下料 毛 件数 方式 坯型号,设变量为 第 j 种方法的所有 原料件数,例题1：,（四）、合理配料问题,一般提法 某饲养场用n种饲料B1,B

18、2, Bn配置成含有m种营养成分A1,A2, Am的混合饲料，其余资料如表所示。问应如何配料，才能既满足需要，又使混合饲料的总成本最低？,例题2：,某人每天食用甲、乙两种食物（如猪肉、鸡蛋），其资料如下： 问两种食物各食用多少， 才能既满足需要、又使 总费用最省？,设：Xj 表示Bj 种食 物用量。,（五）、运 输 问 题,已知资料如表所示：,模型如下：,某运输问题的资料如下：,例题3：,（六）、作物布局问题,此外，还有连续投资、投入产出等模型问题。,例2.2 某地区有三个矿山A1，A2，A3，生产同一种矿物。另外有四个这种矿物消费地（铁厂）B1，B2，B3，B4。各矿山产量及铁厂的需要量和矿

19、山将矿物运到铁厂的单位运价如表2-2。问应如何调运，才使总运费最省？,（一）运输问题的数学模型,解：该题有两个限制条件：一个是产量，一个是需量。目标是总运费最省。 设：xij表示从第i个矿山运往第j个铁厂的矿物运量。这样得到以下两组线性方程组： （1）各矿山矿物的生产量与运出量平衡方程：,（2）各铁厂矿物供应量与需要量平衡方程,（3）矿物的运输量应非负,（4）目标函数,（二）资源最优利用的数学模型,例2.3 某厂生产A、 B产品1kg需用资源数见表2-3 ，已知生产A1kg价值7千元，B1kg12千元。应该生产A和B产品各多少才能使总价值最大。,解：设A、B两产品的计划产量为x1、x2 则数学

20、模型为：,（三）机床负荷问题的数学模型,例2.4 设某车间需加工甲、乙两种零件。这两种零件可以在三种不同机床铣床、六角车床、自动机床上进行加工。机床数及生产效率如表2-4。,（三）机床负荷问题的数学模型,此表说明，在一台铣床上一个工作日可以加工15件甲零件或20件乙零件，余类同。该车间共有3台铣床，3台六角车床，1台自动机床。问如何合理安排机床的加工任务，使得在产品配套比例条件下（设甲、乙零件1:1配套），使成套产品的数量达到最大。,解：设xij表示第i种机床用来生产第j种产品的台数，则数学模型为： （1）加工甲、乙产品机床台数平衡方程：,（2）甲、乙零件配套比例平衡方程：,（3）变量非负：,（4）目标函数求成套产品数量最大：,（四）人员分配的数学模型,例2.5 有四件工作，分配给四人，每人能力不同，工作效率也不同如表2-5，规定每项工作由一个人担任和每个工人只分配一项工作。问应分配哪个人去完成哪项工作可使总效率达到最大。,解：设xij表示i个工人分配担任第j项工作的情况，并xij取1和0两个值， xij=1，表示第i个工人分配担任第j项工作； xij