运筹学ch1、2(lhd)

信息学院罗捍东1运筹学Operationsresearch罗捍东主讲中南财经政法大学信息学院[e-mail]:13971144986信息学院罗捍东2运筹学是一门应用科学，它广泛应用现有的科学技术知识和数学方法，解决实际中提出的专门问题，为决策者选择最优决策提供定量依据。第一章运筹模型概论运筹学作为一门新兴的学科是在第二次世界大战期间出现的。当时英美成立了名为“运作研究”(OprtationalResearch)小组，通过科学方法的运用成功地解决了许多非常复杂的战略和战术问题。信息学院罗捍东3例如如何合理运用雷达有效地对付德国空袭；对商船队如何进行编队护航，在船队遭受德国潜艇攻击时使船队损失最少；反潜深水炸弹在各种情况下如何调整其爆炸深度，才能增加对德国潜艇的杀伤力等；军队营养物质供应问题。运筹学分为许多分枝；线性规划、整数规划、非线性规划、动态规划、对策论、存贮论、决策分析等。信息学院罗捍东4第二章线性规划模型第一节引言信息学院罗捍东5例1:(生产计划问题)某工厂生产I、II两种产品。每件产品的单位利润，所消耗的两种材料数、设备工时及这两种材料、设备工时的限额如下表：如何安排生产才能使利润最大？III资源限量设备材料A材料B1402048台时16kg12kg利润23信息学院罗捍东612max23Zxx解：设x1、x2分别表示两种产品的产量，那么该问题的数学模型可以表示为：目标函数约束条件决策变量12121228416.412,0xxxstxxx信息学院罗捍东7•第i种资源的拥有量为bi;i=1,2,…,m,生产一个单位第j种产品需要消耗第i种资源的数量为aij;第j种产品的利润（单价,产值）为cj。j=1,2,…,n。•上述问题推广到一般情况：•有m种不同资源（例如原材料，动力资源，资金，劳力等）可以用来生产n种不同产品。假设有关的数据为：•设x1、x2、…、xn分别表示n种产品的产量，则其数学模型为：如何安排生产才能使总的利润最大？信息学院罗捍东811221111221121122222112212max.,,,0nnnnnnmmmnnmnZcxcxcxaxaxaxbaxaxaxbstaxaxaxbxxx信息学院罗捍东9例2：(配料问题)一饲养场饲养动物出售，每只动物每天至少需要700克蛋白质，30克矿物质，100毫克维生素。现有四种饲料可供选用，各种饲料每公斤营养成分含量及单价如下表所示；饲料营养成分ⅠⅡⅢⅣ需要量蛋白质3215700克矿物质10.50.2230克维生素0.510.32.5100毫克单价(元/公斤)0.81.20.62四种饲料各采购多少，才能使总费用最小？信息学院罗捍东10解：设x1、x2、x3、x4分别表示四种饲料的采购量，那么该问题的数学模型可以表示为：12341234123412341234min0.81.20.623257000.50.2230.0.50.32.5100,,,0Zxxxxxxxxxxxxstxxxxxxxx信息学院罗捍东11•上述模型推广到一般情况为：•每只动物每天至少需要有m种不同营养成分bi；•有n种饲料可供选用，每公斤第j种饲料所含第i种营养成分量为aij;•第j种饲料的单价为cj。i=1,2,…,m，j=1,2,…,n。•设x1、x2、…、xn分别表示n种饲料的采购量，则其数学模型为：如何采购才能使总费用最小？信息学院罗捍东1211221111221121122222112212min.,,,0nnnnnnmmmnnmnZcxcxcxaxaxaxbaxaxaxbstaxaxaxbxxx信息学院罗捍东13例3：(运输问题)设有两个砖厂A1、A2，产量分别为23万块、27万块，现将其产品联合供应三个施工现场B1、B2、B3，其需要量分别为17万块、18万块、15万块。各产地到各施工现场的单位运价如下表：问如何调运才能使总运费最省？现场砖厂B1B2B3A15147A26189信息学院罗捍东14解：设xij表示从砖厂Ai运往现场Bj的数量(i=1,2;j=1,2,3),则其数学模型如下：111213212223111213212223112112221323min51476189232717.18150(1,2,1,2,3)ijZxxxxxxxxxxxxxxstxxxxxij信息学院罗捍东15•一组决策变量x表示一个方案,一般x大于等于零。•约束条件是线性等式或不等式。•目标函数是线性的。求目标函数最大值或最小值线性规划问题的共同特征信息学院罗捍东16线性规划模型的一般形式11221111221121122222112212max(min)......(,)...(,)......................................................(,),,...,0nnnnnnmmmnnmnZcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx信息学院罗捍东17例4：(投资问题)某投资公司在第一年初有100万元资金，每年都有如下的投资方案可供考虑采纳：“假使第一年投入一笔资金，第二年又继续投入此资金的50%，那么到第三年就可回收第一年投入资金的两倍金额”。投资公司要设法决定最优的投资策略使第六年所掌握的资金最多。解：设x1为第一年的投资;x2为第一年的保留资金；12100xx则设x3为第二年新的投资；x4为第二年的保留资金；1342()2xxxx则信息学院罗捍东18•设x5为第三年新的投资；x6为第三年的保留资金；35641()22xxxxx则57863()22xxxxx则•设x7为第四年新的投资；第四年的保留资金为x8；•设x9为第五年的保留资金：第五年不再进行新的投资，因为这笔投资要到第七年才能回收。798522xxxx则•约束条件保证每年满足如下的关系：追加投资金额+新投资金额+保留资金=可利用的资金总额。信息学院罗捍东19•到第六年实有资金总额为x9+2x7，整理后得到下列线性规划模型：7912123413456356785789max2100222042220.4222042200,1,2,,9jZxxxxxxxxxxxxxstxxxxxxxxxxj信息学院罗捍东20例5：（下料问题）某一机床需要用甲、乙、丙三种规格的钢轴各一根，这些轴的规格分别是2.9,2.1,1.5(m),这些钢轴需要用同一种圆钢来做，圆钢长度为7.4m。现在要制造100台机床，最少要用多少根圆钢来生产这些钢轴？解：第一步：设一根圆钢切割成甲、乙、丙三种钢轴的根数分别为y1,y2,y3，则切割方式可用不等式2.9y1+2.1y2+1.5y3≤7.4表示，求这个不等式的有实际意义的非负整数解共有8组，也就是有8种不同的下料方式，如下表所示：信息学院罗捍东21方案规格12345678y1(2.9m)21110000y2(2.1m)02103210y3(1.5m)10130234余料0.10.30.901.10.20.81.4•设x1、x2、…、x8表示按8种方案下料的圆钢根数，则问题的数学模型为：信息学院罗捍东2287654321minxxxxxxxxZ＋123423567134678210023210032341000128.,,jxxxxxxxxxstxxxxxxxj，信息学院罗捍东23第二节线性规划的数学模型一、线性规划问题的标准形式信息学院罗捍东24线性规划模型的一般形式11221111221121122222112212max(min)......(,)...(,)......................................................(,),,...,0nnnnnnmmmnnmnZcxcxcxaxaxaxbaxaxaxbaxaxaxbxxx信息学院罗捍东2511221111221121122222112212max.......................................................,,...,0nnnnnnmmmnnmnZcxcxcxaxaxaxbaxaxaxbstaxaxaxbxxx目标函数最大约束条件等式决策变量非负线性规划问题的标准形式信息学院罗捍东26–用求和号表示为：11max1,2,....01,2,...,njjjnijjijjZcxaxbimstxjn线性规划问题的标准形信息学院罗捍东27–用向量表示为：线性规划问题的标准形1max.01,2,...njjjjZCXPxbstxjn111222jjjnmmjaxbaxbXPb.........xba其中：12nC(c,c,...c)信息学院罗捍东28–用矩阵表示为：C—价值向量b—资源向量X—决策变量向量A—资源消耗系数矩阵11121212221212(,,...,)nnnmmmnaaaaaaAPPPaaamaxs.t0ZCXAXbX信息学院罗捍东29一般线性规划问题的标准形化1)若目标函数为：minZ=CX，则令Z′=-Z,于是得到maxZ′=-CX2)若约束条件为：1122,kkknnkaxaxaxb引进松弛变量xn+1,使：11221kkknnnkaxaxaxxb显然：111220.nkkkknnxbaxaxax信息学院罗捍东30若约束条件为：1122,kkknnkaxaxaxb引进松弛变量xn+1,使：11221kkknnnkaxaxaxxb显然：111220nkkknnkxaxaxaxb若xk无非负约束，则令：//////,0,0kkkkkxxxxx信息学院罗捍东31123123123123123min3283325,0Zxxxxxxxxxxxxxxx、无约束例1：将下列线性规划化为标准形解：标准形为：123312334123351233123345max3328332()50Zxxxxxxxxxxxxxxxxxxxxxxxx、、、、、信息学院罗捍东32二、线性规划问题的解的概念可行解：满足AX=b,X≥0的解X称为线性规划问题的可行解。可行域：可行解的全体称为可行域。最优解：使Z=CX达到最大值的可行解称为最优解。max.0ZCXAXbstX标准型信息学院罗捍东33标准形的假定(),0,010.irankAmmnbbi(1)矩阵A的秩(2).若有可对第个约束方程两边同时乘以.信息学院罗捍东34基：若B是矩阵A中m×m阶非奇异子矩阵，则称B是线性规划问题的一个基。不妨设：11121212221212()mmmmmmmaaaaaaBPPPaaa,1,2,,jPjm,1,2,,jxjm,1,2,,jxjmmn线性规划问题解的概念——基向量——基变量——非基变量信息学院罗捍东35,(,),(,),BBNNXABNCCCXX此时max.0ZCX