《高等运筹第二讲(刘巍)大连海事大学》由会员分享，可在线阅读，更多相关《高等运筹第二讲(刘巍)大连海事大学（95页珍藏版）》请在金锄头文库上搜索。
1、高等运筹学高等运筹学大大连海事大学海事大学刘巍刘巍第二篇 运筹学中的数学规划第三章第三章 线性规划线性规划第四章第四章 非线性规划非线性规划第五章第五章 锥规划锥规划第六章第六章 矩阵规划矩阵规划第七章第七章 变分不等式与互补问题变分不等式与互补问题第八章第八章 整数规划整数规划第九章第九章 动态规划动态规划第十章第十章 向量优化（多目标优化）向量优化（多目标优化）线性规划模型若干决策变量：若干决策变量： 如如 x1 ,x2 ,xn 目标函数：关于决策变量的线性函数目标函数：关于决策变量的线性函数约束条件：关于决策变量的线性不等式（或等式）约束条件：关于决策变量的线性不等式（或等式）目的：目的
2、： 在满足约束条件的决策变量中找出一组在满足约束条件的决策变量中找出一组使目标函数达到最优的决策变量！使目标函数达到最优的决策变量！ 线性规划的一般模式目标函数：max(min)Z=c1x1+c2x2+c3x3+cnxn约束条件：a11x1+a12x2+a13x3+a1nxn (= )b1 a21x1+a22x2+a23x3+a2nxn (= )b2 am1x1+am2x2+am3x3+amnxn (= )bn非负性约束：x1 0,x2 0,xs 0 线性规划问题的数学模型 目目目目标标函数：函数：函数：函数： 约约束条件：束条件：束条件：束条件：简写写为： 向量形式：向量形式：向量形式：向量
3、形式：其中：其中： 矩矩矩矩阵阵形式：形式：形式：形式：其中：其中：线性规划问题的解求解求解线性性规划划问题，就是从，就是从满足足约束条件束条件(2)、(3)的方程的方程组中找出一个解，使目中找出一个解，使目标函数函数(1)达到最大达到最大值。可行解可行解：满足足约束条件束条件、的解的解为可行解。所有可行解可行解。所有可行解的集合的集合为可行域。可行域。最最优解解：使目：使目标函数达到最大函数达到最大值的可行解。的可行解。 基：基：设A为约束条件束条件的的mn阶系数矩系数矩阵(mn)，其秩，其秩为m，B是矩是矩阵A中中m阶满秩子矩秩子矩阵（ B 0），称），称B是是规划划问题的的一个基。一个基
4、。设：称称 B中每个列向量中每个列向量Pj ( j = 1 2 m) 为基向量。与基向量基向量。与基向量Pj 对应的的变量量xj 为基基变量量。除基。除基变量以外的量以外的变量量为非基非基变量量。 基解：某一确定的基B，令非基变量等于零，由约束条件方程解出基变量，称这组解为基解。在基解中变量取非0值的个数不大于方程数m，基解的总数不超过 基可行解：满足变量非负约束条件的基本解，简称基可行解。 可行基：对应于基可行解的基称为可行基。非可行解非可行解可可行行解解基解基解基可行解基可行解线性规划的求解自自1939年苏联数学家康托罗维奇提出线年苏联数学家康托罗维奇提出线性规划间题和性规划间题和1947
5、年美国数学家丹齐格年美国数学家丹齐格求解线性规划问题的通用方法一单纯形求解线性规划问题的通用方法一单纯形法以来，线性规划可以说是研究得最为法以来，线性规划可以说是研究得最为透彻的一个研究方向。单纯形法统治线透彻的一个研究方向。单纯形法统治线性规划领域达性规划领域达40年之久，而且至今仍是年之久，而且至今仍是最好的应用最广泛的算法之一。虽然它最好的应用最广泛的算法之一。虽然它在最坏情况具有指数复杂性，但在平均在最坏情况具有指数复杂性，但在平均意义下已经证明是一个多项式算法。意义下已经证明是一个多项式算法。 目前，关于单纯形算法的研究主要在于目前，关于单纯形算法的研究主要在于如何选取主元。另一大类
6、算法是内点法，如何选取主元。另一大类算法是内点法，它起源于它起源于1979年苏联数学家卡奇扬提出年苏联数学家卡奇扬提出的多项式椭球算法，而因的多项式椭球算法，而因1984年美籍印年美籍印度裔数学家卡玛卡提出的多项式时间算度裔数学家卡玛卡提出的多项式时间算法而迅速成为国际热点，各式各样的算法而迅速成为国际热点，各式各样的算法大量涌现法大量涌现:仿射变换法、势函数方法、仿射变换法、势函数方法、对数罚函数法、路径跟踪法、原始对偶对数罚函数法、路径跟踪法、原始对偶法、不可行内点法等等。法、不可行内点法等等。 目前线性规划的内点法也趋于成熟，这目前线性规划的内点法也趋于成熟，这方面的研究者们目前大都致力
7、于以线性方面的研究者们目前大都致力于以线性规划作为特例的锥规划，以及如何利用规划作为特例的锥规划，以及如何利用线性规划松弛求解整数规划等方面的研线性规划松弛求解整数规划等方面的研究。然而，就线性规划而言，是否存在究。然而，就线性规划而言，是否存在强多项式算法仍然是一个重要且困难的强多项式算法仍然是一个重要且困难的理论问题。理论问题。 连接几何形体中任意两点的接几何形体中任意两点的线段仍完全在段仍完全在该几何形几何形体之中。体之中。 有限个凸集的交集仍然是凸集。有限个凸集的交集仍然是凸集。单纯形法基本原理单纯形法基本原理凸集：如果集合凸集：如果集合C中任意两个点中任意两个点X1、X2，其，其连线
8、上的所有点上的所有点也都是集合也都是集合C中的点，称中的点，称C为凸集。凸集。凸集凸集凸集凸集不是凸集不是凸集顶顶 点点 顶点：如果凸集点：如果凸集C中不存在任何两个不同的点中不存在任何两个不同的点X1，X2，使，使X成成为这两个点两个点连线上的一个点上的一个点单纯形法基本原理定理定理定理定理1 1：若：若：若：若线线性性性性规规划划划划问题问题存在可行解，存在可行解，存在可行解，存在可行解，则该问题则该问题的可行域是的可行域是的可行域是的可行域是凸集。凸集。凸集。凸集。定理定理定理定理2 2：线线性性性性规规划划划划问题问题的基可行解的基可行解的基可行解的基可行解X X对应对应可行域可行域可
9、行域可行域( (凸集凸集凸集凸集) )的的的的顶顶点。点。点。点。定理定理定理定理3 3：若：若：若：若问题问题存在最存在最存在最存在最优优解，一定存在一个基可行解是最解，一定存在一个基可行解是最解，一定存在一个基可行解是最解，一定存在一个基可行解是最优优解。（或在某个解。（或在某个解。（或在某个解。（或在某个顶顶点取得）点取得）点取得）点取得）单纯形法的计算步骤单纯形法的思路找出一个初始可行解找出一个初始可行解找出一个初始可行解找出一个初始可行解是否最是否最是否最是否最优优转转移到另一个基本可行解移到另一个基本可行解移到另一个基本可行解移到另一个基本可行解（找出更大的目（找出更大的目（找出更
10、大的目（找出更大的目标标函数函数函数函数值值）最最最最优优解解解解是是是是否否否否循循循循环环核心是：核心是：核心是：核心是：变变量迭代量迭代量迭代量迭代结结束束束束单纯形法的进一步讨论人工变量法人工变量法：前面讨论了在标准型中系数矩阵有单位矩阵，很容易确定一组基可行解。在实际问题中有些模型并不含有单位矩阵，为了得到一组基向量和初基可行解，在约束条件的等式左端加一组虚拟变量，得到一组基变量。这种人为加的变量称为人工变量，构成的可行基称为人工基，用大M法或两阶段法求解，这种用人工变量作桥梁的求解方法称为人工变量法。二、二、 线性规划应用线性规划应用应用问题应用问题 线性规划的应用线性规划的应用1
11、 1 人力资源分配的问题2 2 生产计划的问题3 3 套裁下料问题4 4 配料问题5 5 投资问题人力资源分配的问题 例1某昼夜服务的公交线路每天各时间段内所需司机和乘务人员数如下： 设司机和乘务人员分别在各时间段一开始时上班，并连续工作八小时，问该公交线路怎样安排司机和乘务人员，既能满足工作需要，又配备最少司机和乘务人员?人力资源分配的问题 解：设 xi 表示第i班次时开始上班的司机和乘务人员数,这样我们建立如下的数学模型。 目标函数： Min Z= x1 + x2 + x3 + x4 + x5 + x6 约束条件：s.t. x1 + x6 60 x1 + x2 70 x2 + x3 60
12、x3 + x4 50 x4 + x5 20 x5 + x6 30 x1,x2,x3,x4,x5,x6 02 2生产计划的问题 例2某公司面临一个是外包协作还是自行生产的问题。该公司生产甲、乙、丙三种产品，都需要经过铸造、机加工和装配三个车间。甲、乙两种产品的铸件可以外包协作，亦可以自行生产，但产品丙必须本厂铸造才能保证质量。数据如表。问：公司为了获得最大利润，甲、乙、丙三种产品各生产多少件？甲、乙两种产品的铸造中，由本公司铸造和由外包协作各应多少件？生产计划的问题 解：设 x1,x2,x3 分别为三道工序都由本公司加工的甲、乙、丙三种产品的件数，x4,x5 分别为由外协铸造再由本公司加工和装配
13、的甲、乙两种产品的件数。 求 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 元。生产计划的问题通过以上分析,可建立如下的数学模型:目标函数：Max f= 15x1 + 10x2 + 7x3 + 13x4 + 9x5 约束条件：5x1 + 10x2
14、 + 7x3 8000 6x1 + 4x2 + 8x3 + 6x4 + 4x5 12000 3x1 + 2x2 + 2x3 + 3x4 + 2x5 10000 x1,x2,x3,x4,x5 03 3套裁下料问题 例5某工厂要做100套钢架，每套用长为2.9 m,2.1 m,1.5 m的圆钢各一根。已知原料每根长7.4 m，问：应如何下料，可使所用原料最省？ 解： 共可设计下列5 种下料方案，见下表 设 x1,x2,x3,x4,x5 分别为上面 5 种方案下料的原材料根数。这样我们建立如下的数学模型。 目标函数： Min z= x1 + x2 + x3 + x4 + x5 约束条件： s.t.
15、x1 + 2x2 + x4 100 2x3 + 2x4 + x5 100 3x1 + x2 + 2x3 + 3x5 100 x1,x2,x3,x4,x5 0用计算软件计算得出最优下料方案：按方案1下料30根；按方案2下料10根；按方案4下料50根。 即 x1=30; x2=10； x3=0； x4=50； x5=0； 只需90根原材料就可制造出100套钢架。注意：在建立此类型数学模型时，约束条件用大于等于号比用等于号要好。因为有时在套用一些下料方案时可能会多出一根某种规格的圆钢，但它可能是最优方案。如果用等于号，这一方案就不是可行解了。套裁下料问题4 4配料问题 例6某工厂要用三种原料1、2、
16、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 个。配料问题利润=总收入-总成本=甲乙丙三种产品的销售单价*产品数量-甲
17、乙丙使用的原料单价*原料数量，故有目标函数目标函数Max f= 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个表中，生产甲乙丙的原材料不能超过原材
18、料的供应限额，故有 (x11+x21+x31)100 (x12+x22+x32)100 (x13+x23+x33)60 通过整理，得到以下模型：配料问题例6（续）目标函数：Max f = -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 （原材
19、料2不超过50%） x11+ x21 + x31 100 (供应量限制） x12+ x22 + x32 100 (供应量限制） x13+ x23 + x33 60 (供应量限制） xij 0 , i = 1,2,3; j = 1,2,3 例8某部门现有资金200万元，今后五年内考虑给以下的项目投资。已知：项目A：从第一年到第五年每年年初都可投资，当年末能收回本利110%；项目B：从第一年到第四年每年年初都可投资，次年末能收回本利125%，但规定每年最大投资额不能超过30万元；项目C：需在第三年年初投资，第五年末能收回本利140%，但规定最大投资额不能超过80万元；项目D：需在第二年年初投资，第
20、五年末能收回本利155%，但规定最大投资额不能超过100万元。 据测定每万元每次投资的风险指数如右表：问：问：a）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利金额为最大？b）应如何确定这些项目的每年投资额，使得第五年年末拥有资金的本利在330万元的基础上使得其投资总的风险系数为最小？ 解：解： 1 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
21、 D x24投资问题2 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.25x3
22、2； B、C、D的投资限制： xi2 30 ( i =1、2、3、4 )，x33 80，x24 100 3 3）目标函数及模型：）目标函数及模型：a) 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 =
23、 1、2、3、4、5；j = 1、2、3、4） 投资问题b)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. x11+ x12 = 200 x21 + x22+ x24 = 1.1x11； x31 + x32+ x33 = 1.1x21+ 1.25x12； x41 +
24、x42 = 1.1x31+ 1.25x22； x51 = 1.1x41+ 1.25x32； xi2 30 ( i =1、2、3、4 )，x33 80，x24 100 1.1x51 + 1.25x42+ 1.4x33+ 1.55x24 330 xij 0 ( i = 1、2、3、4、5；j = 1、2、3、4）投资问题三、线性规划的对偶问题三、线性规划的对偶问题再谈招聘总经理再谈招聘总经理案 例 （一）泰山股份公司可以生产两种产品出售，需要三种资泰山股份公司可以生产两种产品出售，需要三种资源，已知各产品的利润、各资源的限量和各产品的源，已知各产品的利润、各资源的限量和各产品的资源消耗系数如下表：
25、资源消耗系数如下表：目前生产现状：目前生产现状：不生产产品不生产产品A ，生产产品，生产产品B每天每天30 ， 获利获利3600 产品A产品B资源限量设 备劳动力原材料9434510360200300利润元/kg70120招聘总经理！约翰：约翰： 我应聘！我应聘！ 在现有资源状况下，可以使利润达到在现有资源状况下，可以使利润达到4200 以上！以上！ 方案是：方案是： 生产生产A 产品产品20 ， 生产生产 B 产品产品 24 可行性：可行性：9*20+4*24=276 0 cs Minj / asj asj 0 br Min-bi / air air 0 灵敏度分析（续）灵敏度分析（续）A中元素发生变化中元素发生变化 （只讨论 N 中某一列变化情况） 与增加变量 xn+1 的情况类似，假设 pj 变化 。那么，重新计算出 B-1pj j = cj - cri ari j 填入最优单纯形表，若 j 0 则最优解不变；否则，进一步用单纯形法求解。灵敏度分析（续）灵敏度分析（续）可得最优解：x* = ( 3.2,0.8,0,0,2.4 )T f* = 15.2灵敏度分析（续）灵敏度分析（续）灵敏度分析小结：灵敏度分析小结： 1 Ci 发生变化 2 Bj发生变化 3 A中元素发生变化返回目录第二讲结束第二讲结束
