运筹学Operations Research•运筹学的三大来源–军事—孙武世界上第一个军事运筹学家—英国布置防空雷达（资源配置）—反潜飞机巡逻路线、水雷引爆深度–经济—数理经济的发展，经济平衡问题–管理—管理科学•3.教学内容安排Ø第一章线性规划Ø第六章动态规划Ø第二章对偶理论Ø第七章图与网络Ø第三章运输问题Ø第八章网络计划Ø第四章目标规划Ø第九章对策论Ø第五章整数规划Ø第十章决策论绪论•1.运筹学的产生及发展齐王田忌上上中中下下普莱格尔河田忌赛马歌尼斯堡七桥问题•2.运筹学的基本方法①分析问题②建立模型③求解模型及优化④验证解的合理性⑤建立对解的有效控制⑥解的实施•4.优化软件的学习–EXCEL规划求解–LINDO/LINGO–WINQSB1•5.参考书目–《运筹学教程（第三版）》，胡运权，清华大学出版社；–《数据、模型与决策：运用电子表格建模与案例研究（第2版）》，任建标，中国财经出版社；–《管理科学:运用Spreadsheet 建模和求解》，丁以中，学苑出版社；–《优化建模LINDO/LINGO软件》，谢金星，清华大学出版社。§1.1线性规划问题及模型一、问题的提出例1 美佳公司计划制造Ⅰ、Ⅱ两种家电1.决策变量：设Ⅰ、Ⅱ两种家电产品。已知各制造一件时分别占用的设产品的生产数量量分别为：x备A、B的台时、调试时间、调试工序1、x2以及每天可用于这两种家电的能力、各2.目标函数：设总利润为z，则有：售出一件时的获利情况，如下表所示。问公司应该制造两种家电各多少件，使max z = 2x1+ x2获利最大。3.约束条件：项目ⅠⅡ每天可用能力5x2 ≤15设备A(h)05156x1+ 2x2≤24设备B(h)6224调试工序(h)115x1＋x2≤5利润（元）21x1、x2≥0经济管理领域的其它应用（1）合理利用线材问题（2）配料问题（3）投资问题（4）产品生产计划（5）劳动力安排第1章线性规划（Linear Programming，LP）§1.1 线性规划问题及模型§1.2 线性规划的图解法§1.3 线性规划的单纯形法§1.4 线性规划的应用及软件求解例2 某厂生产三种药物，这些1.决策变量：设四种原料的使药物可以从四种不同的原料中用量分别为：x1、x2 、x3、x4提取。下表给出了单位原料可提取的药物量。2.目标函数：设总成本为z，则：药物单位成本min z = 5 x1+ 6 x2 + 7 x3 + 8 x4原料ABC（元／吨）甲12353.约束条件：乙2016x1+ 2x2+ x3 + x4≥160 丙1417丁12282x1+4 x3+2 x4＝200 要求：生产A种药物至少160单3x1＋x2+x3+2 x4 ≤180 位，B种药物恰好200单位，Cx1、x2、x3、x4≥0种药物不超过180单位，且使原料总成本最小。线性规划研究的两大类问题（1）已有一定数量的资源（人力、物质、时间等），研究如何充分合理地使用它们，才能使完成的任务量为最大。（2）当一项任务确定以后，研究如何统筹安排，才能使完成任务所耗费的资源量为最少。2二、线形规划数学模型1.决策变量：X= (x1,x2,…..,xn)T2.目标函数：max(minz) = c1x1+ c2x2+ ……. + cnxn3.约束条件：a11x1+ a12x2+……..+ a1nxn≤(=≥) b1a21x1+ a22x2+……..+ a2nxn≤(=≥) b2…………………………………………am1x1 + am2x2 +……..+ amnxn≤(=≥) bmx1,x2,……xn≥0max(min)z=CX②矩阵形式AX£ bæX³0çx1öX=çx÷ç2÷æç÷ça11a12La1nöçM决策变量÷èx÷A=çaaa÷2nnøç2122LLLL÷÷=(aij)m´n系数矩阵æççLçb1öèam1am2La÷mn÷øb=çb÷ç2÷ç÷常数项çM÷èbm÷øC=(c1c2Lcn)价值系数线性规划模型的一般假设比例性假定—资源及价格没有数量折扣可加性假定—各个变量是相互的连续性假定—连续型变量而非离散型确定性假定—参数是确定而非随机的模型的其它形式①求和形式nmax(min)z=åcjxjj=1ånaijxj£(³)bi(i=1,2,j=1L,m)xj³0(j=1,2,L,n)线性规划模型的特点1. 用一组决策变量X = (x1,x2,…,xn)T表示某一方案，且决策变量取值非负；2. 都有一个要达到的目标，并且目标要求可以表示成决策变量的线性函数；3. 都有一组约束条件，这些约束条件可以用决策变量的线性等式或线性不等式来表示。三、线性规划问题的标准形式1.求minz等价于求max(-z),n令Z¢=-Z,则maxZ¢=-åcjxj2.若b）；j=1i<0,则式子两端同乘（-13.约束条件为不等式，则添加松弛变量或剩余变量；4.取值无约束的变量，令x=x¢-x¢¢,其中x¢³0,x¢¢³0;5.若x£0,令x¢=-x,则x¢³0;maxz=åncjxjj=1ånaijxj=bi(i=1,2,j=1L,m)xj³0(j=1,2,L,n)3例3：将下述线性规划化为标准形式min z = x′1+ 2 x2 + 3 x3解:令z=-z, x1′=-x1, x3=x3′-x3〞－2x1+ x2+ x3 ≤9max z′= x′〞1－2 x2 －3 x′3+3x3+0x4 +0x5 －3xx3≥42 x′1+ x2+ x′3－x〞3+x4 ＝9st.1＋x2+2 4x1－2x2－3x3＝－63 x′＋xst.12+2 x′3－2x〞3－x5 ＝4x1 ≤0，x2≥0 、x3取值无约束4 x′′1+2x2+3 x3－3x〞3＝6x′1，x2，x′3，x〞3，x4 ，x5 ≥0 几何概念代数概念约束直线满足一个等式约束的解约束半平面约束半平面的交集：凸多边形﹖约束直线的交点基础解可行域的顶点基础可行解目标函数等值线：目标函数值等于一个常一组平行线数的解二、几种可能的结果(1)minz=2x1+3x2(2)maxz=3x1+2x21.唯一解ìì2x1+x22.无穷多最优解st.ï4x1+6x2³6í3xst.ï£2ï1+2x2³4í3x1+4x2³12îx1,x2³0ïîx1,x2³03.无界解(3)maxz=x1+x2(4)maxz=5x1+6x24.无可行解ì6x1+10x2£120ì2x1-x2³2st.ïí5£x1£10st.ïí-2x1+3xï2£2î3£x2£8ïîx1,x2³0§1.2 线性规划的图解法x2例1：max z = 2x1+ x25x2 ≤156xQQ31+ 2x2≤244xQ1＋x2≤52x1、x2≥00Q1x1最优解：X*=(x1, x2) ＝(3.5,1.5)，最优值：Z*= 8.5一、图解法解题步骤1. 用直线表示出所有的约束等式，找出可行域。2. 标出目标函数值增加的方向。3. 若求最大（小）值，则令目标函数等值线沿（逆）目标函数值增加的方向平行移动，找与可行域最后相交的点，该点就是最优解。4. 将最优解代入目标函数，求出最优值。§1.3 线性规划的单纯形法一、线形规划问题的基本概念二、三个基本定理三、单纯形表求解四、单纯形法的进一步讨论4一、线形规划问题的基本概念■可行解－－满足所有约束条件的解X= (x1,x2,…..,xn)T■可行域－－所有可行解的集合■最优解－－使目标函数达到最大的可行解x2例1：max z = 2xx1+ x522 ≤156xx1+ 2x2≤24Q31＋x2≤5 Q4x1、x2≥0Q20Q1x1■基解－－令所有非基变量为零，由m个约束方程解出m个基变量的唯一解XB= (x1,x2,…..,xn)T■基可行解－－满足非负约束条件的基解■可行基－－对应于基可行解的基例1：max z = 2x1+ x基向量P3PP5x≤15245基变量为x3x4x5，2 6x100非基变量为x1x2，x1+ 2x＋x2≤24基B＝01012≤5 x、x001求得一基解12≥0XB＝(0, 0, 15, 24, 5)T基可行解可行基解解例4：找出全部基解、基可行解，并确定最优解。max z = 2xP1 P2 P3 P4 P51+3 x2 + x3x1+ x3 ＝51 0 1 0 0St.x1＋2x2+ x4＝10xx1 2 0 1 0x2+5＝4 1-5 ≥00 1 0 0 1序号x1x2x3x4x5z是否基可行解①0051045√②0452017√③5005410√④0550-120×⑤100-50415×⑥52.5001.517.5√⑦540-3022×⑧2430019√■基－－系数矩阵A的一个m×m阶的满秩子矩阵，常记为B；■基向量Pj－－基中的每一个列向量；■基变量Xj、非基变量例1：max z = 2x1+ x2标准化后的系数矩阵基向量P3P4P55x051001006x2 ≤151+ 2x2≤24A＝62010基B＝010x1＋x2≤5 xx110010011、2≥0此时，基变量为x3x4x5、非基变量为x1x2一般情况下系数矩阵æça11a12La1nöæaa12La1möA=çaaa÷ç11ç21n÷a22a÷2mççLL22LL2÷=(a)ça21ijm´n基B=çèam1am2LLLLLL÷÷=(P1,P2,...Pm)a÷mn÷çøçLèam1am2La÷mm÷øx可行解2基解基可行解QQ34Q20Q1x1二、三个基本定理凸集－－如果集合C中任意两个点X中的点，称C为凸集。1,X2，其连线上所有的点也都是集合C顶点－－如果C中不存在任何两个不同的点X1,X2，使X成为这两个点连线上的一个点，则X为其顶点。即：不存在线性表示关系：X¹aX1+(1-a)X2(0
0ý=li=1îaikþalk表221000CB基bx1x2x3x4x50x15051002x3412/601/600x1510[4/6]0-1/61cj－zj01/30-1/30表321000CB基bx1x2x3x4x50x15/20015/4-15/22x37/21001/4-1/21x123/2010-1/43/2cj－zj000-1/4-1/2最优解: X*=(x1, x2 , x3, x4 , x5) ＝(7/2,3/2,15/20,0)，最优值:Z*= 17/2例.maxz=2x1+3x2maxz=2x1+3x2+0x3+0x4+0x5ìx1+2x2£8ïìx1+2x2+x=8ï3st.ïí4x1£16st.ïï4xí4x1x4=162£12ïï4x2+x5=12îx1,x2³0ïîx1-5³0表1（初始表）23000CB基bx1x2x3x4x50x38121000x4100100x51204001cj－zj23000表223000CB基bx1x2x3x4x50x321010-1/20x4100103x2301001/4cj－zj2000-3/4表1（初始表）21000CB基bx1x2x3x4x50x1505100x30424[6]20100x5511001cj－zj21000m检验数sj=cj-åciaij<0q=minìíbiaübîik>0ý=li=1aikþalk表221000CB基bx1x2x3x4x50x15051002x3412/601/600x1510[4/6]0-1/61cj－zj01/30-1/30单纯形法（表）计算步骤（1）找出初始可行基，确定初始基可行解，建立初始单纯形表；（2）检验各非基变量的检验数σ，则达到最优j＝c（若存在某个非基变量j－zj，若所有的非基变量检验数σ检验数σj≤0j＝0 ，则有无穷多最优解），否则继续；（3）若某个检验数σk>0,而其对应的系数列向量pk≤0，则此问题无界，停止计算，否则继续；（4）确定换入变量和换出变量，得到新的单纯形表；（5）重复（2）－（4）。表223000CB基bx1x2x3x4x50x321010-1/20x4100103x2301001/4cj－zj2000-3/4表323000CB基bx1x2x3x4x52x121010-1/20x4800-4123x2301001/4cj－zj00-201/4表423000CB基bx1x2x3x4x52x141001/400x5400-21/213x22011/2-1/80cj－zj00-3/2-1/807四、单纯形法的进一步讨论（1）人工变量法例6：max z = -3x1+ xx31＋x2 ＋x3 ≤4St.-2x1＋x2–x3 ≥13x2 ＋x3=9 x1、x2、x3≥0max z = -3x1+ xmax z = -3xxx3 + 0x4 + 0x5＋1+ xx3 + 0x4 + 0xx5 –M6-Mx1＋x2 ＋x3 + x4 =4x712 ＋x3 + 4 =4St.-2x1＋x2–x3 –x5= 1St.-2x1＋x2–x3 –x5 ＋x6 = 13x2 ＋x3=9 3x2 ＋x3＋x7 =9 x1-5≥0x1-7≥0（2）两阶段法第一阶段：构造仅含人工变量的目标函数和要求实现最小化。求解，若最优值ω＝0，这说明原问题存在基可行解，进行第二阶段计算；否则原问题无可行解，停止计算。第二阶段：将第一阶段得到的最终表，除去人工变量，将目标函数行的系数，换原问题的目标函数系数，作为第二阶段计算的初始表。例7：min z = －3x1+ x2 +x3解：min ω= x6+ x7x1－2x2 + x3≤11x1－2x2 + x3＋x4＝11St.－4x1+x2 +2 x3≥3－4x1+ x2 +2 x3－x5＋x6＝3－2x1＋x3 ＝1St.－2x1＋x3 ＋x7＝1x1-3≥0x1-7≥0第一阶段最终表0000011CB基bx1x2x3x4x5x6x70x4123001-22-50x210100-11-20x31-2010000cj－zj0000011第二阶段-31100CB基bx1x2x3x4x50x123001-21x410100-11x231-20100cj－zj-10001-3x41001/3-2/31x110100-11x2390012/3-4/3cj－zj0001/31/3目标函数值z=-2，最优解为x1＝4，x2＝1，x3＝9max z = -3x1+ x3 + 0xx4 + 0x5 –Mxx6-Mx71＋x2 ＋3 + x4 =4St.-2x1＋x2–x3 –x5 ＋x6 = 13x2 ＋x3＋x7 =9 x1-7≥0初始表-30100-M-MCB基bx1x2x3x4x5x6x70x441111000-Mx61-21-10-110-Mx790310001cj－zj-2M-34M10-M00最终表-30100-M-MCB基bx1x2x3x4x5x6x70x400001-1/21/2-1/20x25/2-1/2100-1/41/4¼1x33/23/20103/4-3/41/4cj－zj-9/2000-3/4-M+3/4-M-1/4第一阶段0000011CB基bx1x2x3x4x5x6x70x4111-2110001x63-4120-1101x71-2010001cj－zj6-1-301000x4103-20100-11x610100-11-20x31-2010001cj－zj0-1001030x4123001-22-50x210100-11-20x31-2010000cj－zj0000011此时ω＝0，原问题有可行解X=(0, 1, 1, 12, 0, 0, 0 )T单纯形法解的讨论1，目标函数为求最小值，当所有非基变量的检验数σj≥0时，达到最优。2，退化解。用θ规则确定换出变量时，有时同时存在两个以上相同的最小值，这样下一次迭代中就有一个或几个基变量等于0，这就出现退化解，迭代后目标函数值不变。这时不同的基表示同一顶点，可能出现迭代的循环，达不到最优解。3，无可行解。所有σj≤0，且基变量中有非零的人工变量。8§1.4 线性规划的软件求解一、Lindo求解法1、输入目标函数；2、输入st(或subject to）；3、标上行2），3）等；4、输入约束条件，运行即可。例1：max z = 2x,运行即可1+ x输入模型如下25x15max 2x1+x22 ≤St.6x1+ 2x＋x2≤24St x12≤5 2）5x2<＝15x1、x2≥03）6x1+2x2<＝244）x1＋x2 <＝5end第二步，观察求解结果详细求解结果2次迭代后求得线性规划最优解目标函数值第1行（即目标函数值）8.5变量值检验数（目标函数减少值）X1 3.5 0X2 1.5 0行松弛或剩余变量对偶价格2）（X3=）7.5 03）（X4=）0 0.254）（X5=）0 0.502次迭代第一步，输入模型如下，点击按钮求解是否进行敏感性分析？Lindo运行状态窗口当前状态Optimal 最优Feasible 可行Infeasible 不可行Unbounded 无界迭代次数2次不可行性“0”表示可行目标函数值8.5整数规划最优解不适用整数规划的界不适用分支数不适用所用时间0刷新时间间隔1秒注意事项１）目标函数及各约束条件之间一定要有Subject to (st)分开。２）变量取值必须是非负的。３）变量名不能超过８个字符。４）变量与其系数间可以有空格，单不能有任何运算符号（如乘号“＊”等）。５）要输入<=或>=约束，相应以<或>代替也可。６）一般LINDO中不能接受括号“（）“和逗号“，“，例：400(X1+X2) 需写成400X1+400X2；10,000需写成10000。7）表达式应当已经过简化。不能出现2X1+3 X2-4 X1，而应写成-２X1+3 X2。9二、EXCEL求解1、打开Excel，点击工具｜加载宏，选择规划求解复选框，单击确定。工具菜单将会有“规划求解”选项。3、目标函数单元格和约束条件单元格输入相关函数4、单击工具｜规划求解，打开规划求解参数对话框，进行相应设置2、在Excel上合理布置决策变量、目标函数和约束条件的位置。已知条件决策变量预留位置目标函数预留位置约束条件（左边项）预留位置5、单击“规划求解参数”对话框上选项按钮，进入“规划求解选项”对话框，选择采用线性模型和假定非负选项，单击确定，单击求解，即可。1011 