运筹学胡运权第五版课件

运筹学(OperationsResearch)一、古代朴素的运筹学思想例如：田忌赛马二、运筹学的起源•国外–英文原名OperationsResearch简称“O.R.”–直译为：运用研究或作业研究–正式出现于1938年7月英国一份关于防空作战系统运行的研究报告中–二战后运筹学的发展经历了三个阶段绪论•国内–1956年成立第一个运筹学小组–1957年从“夫运筹策帷幄之中，决胜于千里之外”中摘取“运筹”二字，将O.R.正式翻译为“运筹学”三、运筹学的定义研究工具：数学，计算机科学及其他相关科学研究目的：对有限资源进行合理规划、使用，并提供优化决策方案。研究对象：复杂系统的组织和管理参考《大英百科全书》、《辞海》、《中国企业管理百科全书》等。四、运筹学研究的基本特点•系统的整体优化•多学科的配合•模型方法的应用五、运筹学研究的基本步骤•分析与表述问题•建立数学模型•对问题求解•对模型和模型导出的解进行检验•建立对解的有效控制•方案的实施六、本课程的主要学习内容第一章线性规划及单纯形法第二章线性规划的对偶理论第三章运输问题第四章整数规划与分配问题第六章图与网络分析第一章线性规划及单纯形法LinearProgrammingandSimplexMethodxa22xxaV此为无约束的极值问题6ax有0dxdV由§1.1一般线性规划问题的数学模型1-1问题的提出例1用一块边长为a的正方形铁皮做一个无盖长方体容器，应如何裁剪可使做成的容器的容积最大？)20(ax解：如图设四个角上减去的小正方形边长为x，则容器体积为：时，容积最大例2常山机器厂生产I、II两型产品。这两型产品都分别要在A、B、C三种不同设备上加工。按工艺规定，生产每件产品的单位利润、消耗三种设备的工时以及各种设备工时的限额如下表：如何安排生产才能使总的利润最大？单位产品消耗设备工时III设备工时限量（小时）设备A设备B设备C240205121615单位利润（元）23解：设计划期内两种产品的数量分别为x1，x2，则总利润为：maxz=2x1+3x22x1+2x2124x1165x215x10，x20简记为：s.t.（约束于：）z=2x1+3x2在满足限制条件下求z的最大值。此为有约束极值问题1-2线性规划问题的数学模型原型模型数学模型提炼数学工具1、原型：现实世界中人们关心、研究的实际对象。模型：将某一部分信息简缩、提炼而构造的原型替代物。数学模型：对现实世界的一个特定对象，为达到一定目的，根据内在规律做出必要的简化假设,并运用适当数学工具得到的一个数学结构。3、规划问题数学模型的三要素（2）目标函数：问题要达到的目标要求，表示为决策变量的函数。用z=f(x1，x2，…，xn)表示。（1）决策变量：决策者为实现规划目标采取的方案、措施，是问题中要确定的未知量。用x1，x2，…，xn表示。（3）约束条件：决策变量取值时受到的各种可用资源的限制，表示为含决策变量的等式或不等式。2、规划问题即求目标函数在若干约束条件下的最值。4、线性规划问题（LinearProgramming）的数学模型（2）一般形式：（1）条件：决策变量为可控的连续变量，目标函数和约束条件都是线性的。简记为“L.P.”max(或min)z=c1x1+c2x2+…+cnxns.t.a11x1+a12x2+…+a1nxn≤（=，≥）b1a21x1+a22x2+…+a2nxn≤（=，≥）b2…am1x1+am2x2+…+amnxn≤（=，≥）bmx1,x2,…,xn≥0（3）其他形式：连加形式向量形式12(,,,)nCccc12nxxXx其中称为价值行向量；决策列向量12jjjmjaaPa12mbbbb系数列向量右端列向量矩阵形式12(,,,)nCccc12nxxXx其中称为价值行向量；决策列向量11121212221212,,,nnnmmmnaaaaaaAPPPaaa12mbbbb右端列向量约束矩阵或系数矩阵1-3线性规划问题的标准形式1、标准形式或2、条件目标函数求极大值约束条件全是等式（线性方程组）决策变量全非负右端常数全非负3、标准化方法（1）若目标函数求极小值，即则令zz转化为（2）若约束条件为不等式，则依次引入松弛变量或剩余变量（统称为松弛变量），转化为等式约束条件。注意：松弛变量在目标函数中系数全为0。约束为≥不等式，减去松弛变量，化为等式约束条件；约束为≤不等式，加上松弛变量，化为等式约束条件。多退少补例：maxz=2x1+3x22x1+2x2124x1165x215x10，x20s.t.12345123142512345max230002212416s.t.515,,,,0zxxxxxxxxxxxxxxxxx标准化0jjjxxx且jjjxxx（3）若决策变量xj≤0，则令（4）若决策变量xj取值无限制，则令（5）若约束等式的右端常数bi≤0，则等式两边同时乘以“-1”。0jjxx，其中（“一分为二”）例：将下列线性规划模型化为标准形式。123123123123123min2329324..32360,0,zxxxxxxxxxstxxxxxx取值无限制11133333(0)(0,0)zzxxxxxxxx解：令则问题化为标准形式：12334512334123351233123345max23300293224s.t.32336,,,,,0zxxxxxxxxxxxxxxxxxxxxxxxxxx并引入松弛变量x4,x5,1-4线性规划问题的解已知线性规划的标准形式：或1、求解线性规划问题：从满足（2）、（3）的方程组中找出一个解使目标函数（1）达到最大值。2、可行解：所有可行解的集合。可行域：满足约束条件（2）、（3）的解。记做最优解：12nxxXx使目标函数达到最大值的可行解。（1）基：设A为线性规划问题约束条件的mn系数矩阵（mn），且B为其mm子矩阵，若|B|≠0（即B可逆），则称B为该线性规划问题的一个基。（3）基变量：每个基向量所对应的决策变量，即x1，x2,…,xm记为XB=(x1,x2,…,xm)T（4）非基变量：除去基变量之外的其他决策变量，即xm+1，xm+2,…,xn，记为XN=(xm+1,xm+2,…,xn)T3、基不妨假设A中前m行m列对应的子矩阵为一个基，即),,,(211111mmmmmPPPaaaaB（2）基向量：基B中每个列向量，即P1，P2,…,Pm（5）基解（基本解）：在约束方程组中，令所有非基变量xm+1=xm+2=…=xn=0后，解出基变量的唯一解，得到的解（6）基可行解（基本可行解）：满足决策变量非负要求的基解。（7）可行基：与基可行解对应的基。1200mxxXx（8）基最优解：使目标函数达到最大值的基可行解。Cmn注意：基解最多个。（9）最优基：与基最优解对应的基。4、线性规划问题各种解之间的关系约束方程的解空间基解可行解非可行解基可行解最优解例：在下述线性规划问题中，列出全部基、基解、基可行解，并指出最优解。12345123142512345max230002212416s.t.515,,,,0zxxxxxxxxxxxxxxxxx解：系数矩阵为12345221004001005001PPPPPA若取基为B=(P1,P2,P3),则基变量为x1,x2,x3,非基变量为x4,x5令x4=x5=0，代入约束方程组解得x1=4,x2=3,x3=-2123122212416515xxxxx从而得到一个基解X=(4,3,-2,0,0)T这个基解不是基可行解！该L.P.共有8个基解。若取基为B=(P3,P4,P5)=I3,则基变量为x3,x4,x5,非基变量为x1,x2令x1=x2=0，代入约束方程组345121615xxx从而得到一个基解X=(0,0,12,16,15)T这个基解是基可行解！（注意：选择单位矩阵为基可以较方便的求出一个基可行解。）同理可得其他基解.基B基解是基可行解？目标函数值x1x2x3x4x5P1P2P343-200否17P1P2P433040是15P1P2P542005是14P1P3P5404015是8P1P4P5600-815否12P2P3P4036160是9P2P4P506016-15否18P3P4P500121615是0（最优基）（最优解）（最优目标函数值）§1.2图解法1、适用范围：仅含两个决策变量的L.P.2、步骤：（1）作平面直角坐标系，标上刻度；（2）作出约束方程所在直线，确定可行域；（3）作出一组目标函数的等值线，判定优化方向；（4）沿优化方向移动，确定与可行域相切的点，确定最优解，并计算最优目标函数值。例：用图解法求解下列线性规划问题。（1）maxz=2x1+3x2s.t.2x1+2x212----------①4x116----------②5x215----------③x10,x20x1x222468460①2x1+2x2=12③5x2=15②4x1=16Z=6Z=0A(3,3)Zmax有唯一最优解，当x1=x2=3时，Zmax=15C(4,0)D(0,3)(0,0)B(4,2)顶点基可行解A（3,3）（3,3,0,4,0）B（4,2）（4,2,0,0,5）C（4,0）（4,0,4,0,15）D（0,3）（0,3,6,16,0）O（0,0）（0,0,12,16,15）一一对应（2）（3）0,0412231843s.t.43max212212121xxxxxxxxxZ①②③无穷多最优解0,142s.t.max21212121xxxxxxxxZ①②无界解x1x1x2x20,12322s.t.23max21212121xxxxxxxxZ①②x1x2无可行解（4）3、线性规划问题解的类型（1）唯一最优解：只有一个解为最优解（2）无穷多最优解：有无穷多个解为最优解（3）无界解：目标函数的取值无界（4）无可行解：可行域为空集，即存在互相矛盾的约束条件。4、可行域的特征（1）若L.P.的可行域不是空集，则可行域为凸集。（2）若L.P.有最优解，则一定可以在可行域的顶点上找到最优解。（3）L.P.的顶点与基可行解一一对应。3-1预备知识：凸集与顶点§1.3单纯形法（SimplexMethod）原理（1）凸集：对于集合C中任意两点连线段上的点，若全在C内，则称集合C为凸集。直观特征：图形从内部向外部凸出。凸集非凸集（2）顶点：凸集中不在任意两点的连线段内部的点。X1X4X3X5X23-2几个基本结论（1）若线性规划问题存在可行解，则可行域为凸集。（2）线性规划问题的可行解X=(x1,x2,···,xn)T为基可行解的充要条件是X的正分量所对应的系数列向量线性无关。（3）线性规划问题的基可行解1-1对应可行域的顶点。例如：比较表1-1和图1-3（4）若线性规划问题有最优解，则一定存在一个基可行解为最优解。注意：若线性规划问题有最优解，不一定所有的最优解都是基可行解。单纯形法的计算步骤：初始基可行解使目标函数值增大的新的基可行解是否最优解？结束是否3-3确定初始基可行解已知线性规划问题形如：引入松弛变量xsi(i=1,2,…,m)化为标准形式：注意：约束条件全是≤1111111