运筹学1章

运筹学中南大学商学院吴良刚2兵者，国之大事也。死生之地，存亡之道，不可兵者，国之大事也。死生之地，存亡之道，不可不察也。故经之以五事，效之以计，而索其情。一曰道不察也。故经之以五事，效之以计，而索其情。一曰道,,二曰天，三曰地，四曰将，五曰法。二曰天，三曰地，四曰将，五曰法。夫未战而庙算胜者，得算多者；未战而庙算不夫未战而庙算胜者，得算多者；未战而庙算不胜者，得算少也。多算胜，少算不胜，而况於无算乎？胜者，得算少也。多算胜，少算不胜，而况於无算乎？兵法：一曰度，二曰量，三曰数，四曰称，五兵法：一曰度，二曰量，三曰数，四曰称，五曰胜。地生度，度生量，量生数，数生称，称生胜。曰胜。地生度，度生量，量生数，数生称，称生胜。导语3导语运筹学发展渊源运筹学的性质和特征运筹学解决问题的步骤运筹学的主要内容4运筹学内容数学规划：线性规划非线性规划整数规划动态规划随机规划模糊规划灰色规划等等图与网络理论存储论排队论博弈论决策论系统模拟等等目录第一章线性规划基础第二章线性规划专题第三章整数规划第四章动态规划第五章图与网络分析第六章存储论第一章线性规划基础线性规划问题及其数学模型线性规划图解法及其几何意义单纯形法原理单纯形法步骤及过程单纯形表单纯形法理论分析单纯形法进一步讨论71.线性规划问题及其数学模型maxZ=6x1+5x26x1+8x2≤54080x1+50x2≤400050x1+10x2≤2000x1,x2≥08问题的提出问企业如何安排生产计划，使一天的总利润最大？ABC原料产品ABC单位利润（百元）甲1103乙1214供应量683甲乙9MaxZ=3x1+4x2x1+x2≤6x1+2x2≤8x2≤3x1,x2≥01）假设x1,x2为甲、乙产品每天的生产量—决策变量x1，x2≥0—非负约束2）假设Z为总利润,希望最大maxZ=3x1+4x23）考虑限制条件A原料：x1+x2≤6B原料：x1+2x2≤8C原料：x2≤3原料产品ABC单位利润（百元）甲1103乙1214供应量68310OptZ=c1x1+c2x2+…+cnxna11x1+a12x2+…a1nxn≤(≥,=)b1a21x1+a22x2+…a2nxn≤(≥,=)b2…am1x1+am2x2+…+amnxn≤(≥,=)bmx1,x2,…xn≥0建模过程的一般形式线性规划模型由三部分组成1）一组决策变量；2）一个线性目标函数；3）一组线性约束方程。有n个决策变量，m个约束方程11线性规划问题的建模意义建立正确的模型，标志着问题已接近完成模型建立要求建模者熟悉待解决问题的内容明确目标要求和错综复杂的约束条件通过调查和统计得到原始可靠的数据线性规划适应范围广，技巧性强有一定的规律性12线性规划建模例1—资源合理利用问题电力2000千瓦煤540吨金属4吨总量6/8吨80/50公斤50/10千瓦A/B产品需求量AA、B产品利润/吨6000元/5000元B13线性规划建模例1—资源合理利用问题（1）确定变量。设用x1，x2（单位为吨）分别表示A、B产品的生产量。（2）目标函数。Z=6x1+5x2（千元）（3）约束条件。煤：6x1+8x2≤540（吨）金属:80x1+50x2≤4000（公斤）电力：50x1+10x2≤2000(千瓦）maxZ=6x1+5x26x1+8x2≤54080x1+50x2≤400050x1+10x2≤2000x1,x2≥0模型归纳问题分析14线性规划建模例2—合理下料问题D180公分？根70公分100根52公分150根35公分100根问题描述15线性规划建模例2—合理下料问题245252526705252570703523705235570353535652523535235235353553535353535x1x2x3x4x5x6x7x8决策变量16线性规划建模例2—合理下料问题目标函数：设Z表示钢管的耗用量的根数，Z1表示切割后的余料数（公分）Z=x1+x2+x3+x4+x5+x6+x7+x8Z1=5x1+6x2+23x3+5x4+24x5+6x6+23x7+5x8约束条件：70公分管料：2x1+x2+x3+x4≥100(根）52公分管料：2x2+x3+3x5+2x6+x7≥150(根）35公分管料：x1+x3+3x4+2x6+3x7+5x8≥100(根）目标函数与约束条件17线性规划建模例2—合理下料问题minZ=x1+x2+x3+x4+x5+x6+x7+x8或者minZ1=5x1+6x2+23x3+5x4+24x5+6x6+23x7+5x82x1+x2+x3+x4≥1002x2+x3+3x5+2x6+x7≥150x1+x3+3x4+2x6+3x7+5x8≥100x1~x8≥0归纳18线性规划建模例3—运输问题B1-50万吨A1-100万吨A2-80万吨A3-50万吨B2-70万吨B4-30万吨B3-80万吨1.5元/吨1.2230.32.570.81.420.32问题描述19线性规划模型的例3—运输问题决策变量A1-100万吨A2-80万吨A3-50万吨B1-50万吨B2-70万吨B4-30万吨B3-80万吨x11x31x12x14x13x34x21x22x23x24x32x3320线性规划建模3—运输问题B1-50万吨A1-100万吨A2-80万吨A3-50万吨B2-70万吨B4-30万吨B3-80万吨1.5元/吨1.2230.32.570.81.420.32minZ=1.5x11+2x12+0.3x13+3x14+7x21+0.8x22+1.4x23+2x24+1.2x31+0.3x32+2x33+2.5x34（万元）目标函数21线性规划建模例3—运输问题矿山的运输量与产量相等x11+x12+x13+x14=100万吨x21+x22+x23+x34=80x31+x32+x33+x34=50约束条件冶炼厂的运输量与需求量相等x11+x21+x31=50万吨x12+x22+x32=70x13+x23+x33=80x14+x24+x34=30B1-50万吨A1-100万吨A2-80万吨A3-50万吨B2-70万吨B4-30万吨B3-80万吨1.5元/吨1.2230.32.570.81.420.3222线性规划建模例4—投资方案选择问题问题描述方案编号方案内容投资(万元)年收益(万元)第1年第2年1更新旧设备，提高炼油能力500桶/天2002001002建造新装置，提高炼油能力1000桶/天3001502003往新厂建输油管，提高炼油能力100桶/天15050504往老厂建输油管，提高炼油能力50桶/天10070305增加槽车运输能力，提高出油20桶/天50402023线性规划建模例4—投资方案选择问题决策变量方案编号方案内容决策变量取值采纳舍弃1更新旧设备，提高炼油能力500桶/天x1X1=1X1=02建造新装置，提高炼油能力1000桶/天x2X2=1X2=03往新厂建输油管，提高炼油能力100桶/天x3X3=1X3=04往老厂建输油管，提高炼油能力50桶/天x4X4=1X4=05增加槽车运输能力，提高出油20桶/天x5X5=1X5=024线性规划建模例4—投资方案选择问题目标函数方案编号方案内容决策变量年收益(万元)1更新旧设备，提高炼油能力500桶/天x11002建造新装置，提高炼油能力1000桶/天x22003往新厂建输油管，提高炼油能力100桶/天x3504往老厂建输油管，提高炼油能力50桶/天x4305增加槽车运输能力，提高出油20桶/天x520设Z表示年收益，则目标函数为max：Z=100x1+200x2+50x3+30x4+20x5（万元)25线性规划建模例4—投资方案选择问题约束条件200x1+300x2+150x3+100x4+50x5≤650(万元)200x1+150x2+50x3+70x4+40x5≤460（万元）500x1+1000x2+100x3+50x4+20x5≥500(桶/天)500x1+1000x2+100x3+50x4+20x5≤1100(桶/天)x1+x2≤1-x2+x3=0x1~x5=1或者026线性规划建模例5—人员分派问题问题描述工作人员ABCD甲0.60.20.30.1乙0.70.40.30.2丙0.81.00.70.3丁0.70.70.50.427线性规划建模例5—人员分派问题决策变量xij=1/0工作j人员iABCD甲x11x12x13x14乙x21x22x23x24丙x31x32x33x34丁x41x42x43x4428线性规划建模例5—人员分派问题目标函数工作人员ABCD甲0.60.20.30.1乙0.70.40.30.2丙0.81.00.70.3丁0.70.70.50.4maxZ=0.6x11+0.2x12+0.3x13+0.1x14+0.7x21+0.4x22+0.3x23+0.2x24+0.8x31+1.0x32+0.7x33+0.3x34+0.7x41+0.7x42+0.5x43+0.4x4429线性规划建模例5—人员分派问题约束条件每个人只能做一项工作x11+x12+x13+x14=1x21+x22+x23+x24=1x31+x32+x33+x34=1x41+x42+x43+x44=1每项工作只能由一人来做x11+x21+x31+x41=1x12+x22+x32+x42=1x13+x23+x33+x43=1x14+x24+x34+x44=1xij=1或者0;i,j=1~430线性规划模型建立步骤归纳确定一组决策变量确定一个线性目标函数确定一组线性约束条件312.线性规划图解法及几何意义32图解法—例MaxZ=3x1+4x2x1+x2≤6x1+2x2≤8x2≤3x1,x2≥0x168x2346x2=3x1+2x2=8x1+x2=6绘出可行解域33图解法—例求最优解x168x2346x2=3x1+2x2=8x1+x2=6法线最优解（4，2）最优方案甲产品4吨，乙2吨，目标函数为Z=20(利润2000元)MaxZ=3x1+4x2x1+x2≤6x1+2x2≤8x2≤3x1,x2≥034图解法：一般过程1）绘出每个约束方程的约束平面设约束方程为a1x1+a2x2≤(≥,=)b(1)画出直线a1x1+a2x2=b(2)若约束方程为a1x1+a2x2≤b则半平面在直线-(a1,a2)方向(3)若约束方程为a1x1+a2x2≥b则半平面在直线(a1,a2)方向(4)若约束方程为a1x1+a2x2=b则半平面为该直线x1246x2246x1+x2=6x1+x26与(1,1)同方向(1,1方向)x1+x26与(1,1)反方向2x1-3x2=6(2,-3）方向2x1-3x262x1-3x2635图解法——一般过程2）绘出可行解域各个约束半平面相交的区域3）作法线相垂直的目标函数等值线设目标函数为Z=c1x1+c2x2,作与方向（c1,c2)相垂直的目标函数等值线在可行解域中移动(1)若目标函数为求最大值，则目标函数等值线沿方向（c1，c2）同方向移动(2)若目标函数为求最小值，则目标函数等值线沿方向（c1，c2）相反方向移动移动中确定使目标达到最优的可行解，该解即为最优解。4）解出最优解x1246x2246Z=3x1+4x2maxZ=3x1+4x2(3,4)方向法线(3,4)方向minZ=3x1+4x2-(3,4)方向36图解法—最优解的种类无穷多最优解无界解无可行解37图解法—无穷多解例MaxZ=x1+2x2x1+x2≤6x1+2x2≤8x2≤3x1,x2≥0x1123456789x21234657x2=3x1+2x2=8x1+x2=638图解法—无界解例MaxZ=x1+x2-2x1+x2≤4x1-x2≤2x1,x2≥0x1123456789x21234657x1-x2=2-2x1+x2=439图解法—无可行解例MaxZ=3x1+4x2x1+x2≥6x1≤2x2≤3x1,x2≥0x1123456789x2123465740线性规划的几何意义图解