运筹学习题ppt课件

单纯形表,1,解的几种情况在单纯形表上的体现（max型）：,唯一最优解：终表非基变量检验数均小于零；多重最优解：终表非基变量检验数中有等于零的；无界解：任意表有正检验数相应的系数列均非正。无解：最优解的基变量中含有人工变量,2,P3811(7),3,4,练习1：,某工厂生产I、II、III三种产品，分别经过A、B、C三种设备加工。已知生产单位各种产品所需的设备台时、设备的现有加工能力及每件产品的预期利润见下表：,(1)求获利最大的产品生产计划；(2)产品III每件的利润增加到多大时才值得安排生产；(3)如有一种新产品，加工一件需设备A、B、C的台时各为1，4，3小时，预期每件的利润为8元，是否值得安排生产。,5,解：（1）设x1，x2，x3分别为I、II、III三种产品的产量，z表示利润。该问题的线性规划模型为：,6,7,（2）设产品III每件的利润为c3,产品III每件的利润增加到20/3时才值得安排生产。,8,（3）设x7为新产品的产量。,9,所以最优解为x*=(100/3，0，0，0，0，200/3)T，即产品I的产量：100/3，新产品的产量：200/3；最优解目标函数值z*=2600/3,10,练习2：,已知下列线性规划问题，求：（1）用单纯形法求解，并指出问题属于哪一类解；（2）写出该问题的对偶问题，并求出对偶问题的最优解；,11,解：（1）将原问题划为标准形式：,12,所以最优解为x*=(15，5，0，10，0，0)T,最优解目标函数值z*=75非基变量的检验数0,为唯一最优解.,13,（2）对偶问题为：,y*=(0，9/4，1/2),对偶问题的最优解：,14,根据上表列出初始单纯形表,线性规划小结,15,原问题P与对偶问题D的关系表,16,练习3：,已知线性规划问题：求：（1）用图解法求解；（2）写出其对偶问题；（3）根据互补松弛定理，写出对偶问题的最优解。,17,解：（1）图解法,由上图可知：在B(2,4)处，目标函数达到最大值。即最优解为x*=(2,4)T最优解目标函数值z*=10,为唯一最优解,18,（2）该问题的对偶问题为：,（3）原问题的最优解x*=(2,4)T代入约束条件，可知约束条件取等式，因为x1*，x2*不为0，在对偶问题中相应的约束条件为紧约束，即,对偶问题的最优解及最优目标函数值为：,19,这说明yi是右端项bi每增加一个单位对目标函数z的贡献。对偶变量的值yi*所表示的第i种资源的边际价格，称为影子价格。,bi表示第i种资源的拥有量；对偶变量yi*代表在资源最优利用条件下，对单位第i种资源的估价。是根据资源在生产中作出的贡献而作的估价。,对偶定理：若(P)和(D)的任意一个有最优解，则另一个也有最优解，且目标函数的最优值相等。,对偶问题的经济解释影子价格,20,二、运输问题表上作业法,适合于产销平衡的运输问题产销不平衡问题要转化为产销平衡问题求解步骤：（1）求一个初始调运方案（初始基可行解）：在mxn维产销平衡表上给出m+n-1个数字。用西北角法、最小元素法、Vogel法（2）判断当前方案是否为最优（最优性检验）：计算各非基变量的检验数，当0最优。用闭回路法、位势法（3）方案调整与改进：确定进基变量和离基变量，找出新的基可行解(闭回路调整法)。返回（2）,21,某百货公司到甲、乙、丙三地采购A、B、C、D四种规格服装，预计销售后每套服装可得利润如下表：,请帮助该公司设计一个预期利润最大的方案。,练习：,22,解：产量销量，假想一个销地E，销量为1000,该问题求最大利润，将极大化问题化为极小化问题，然后再用表上作业法求解：先用Vogel法或最小元素法求初始基可行解；用位势法或闭回路法求出非基变量的检验数；若还未得到最优解，则用闭回路调整法，得到改进方案，再检验最优性。,23,四、整数规划,101整数规划的数学模型2过滤性隐枚举法3.指派问题与匈牙利法,24,在今后3年内有5项工程考虑施工，每项工程的期望收入和年度费用见下表，假定每一项已经批准的工程要在整个3年内完成，目标是要选出使总收入达到最大的那些工程，试将这个问题表示成0-1整数规划模型。,练习1：,25,26,用过滤性隐枚举法求解下列0-1规划问题：,练习2：,27,由上表可知，问题的最优解为x*=(1,0,1)，z*=8,28,分配甲、乙、丙、丁、戊五个人去完成A、B、C、D、E五项工作，每个人完成各项任务的时间如下表所示。(表中单位：小时),已知甲不可能完成任务D，丁只可以完成任务B、C，试确定最优分配方案，使完成任务的总时间为最少。,练习3：,29,解：若不可能完成任务，则效率矩阵相应的元素为M，变换效率矩阵：,30,得到初始分配方案：,因为独立0元素个数m=4，不等于矩阵的阶数n=5，转入下步。,31,此时独立0元素个数有5个，得到最优解，相应的解矩阵为：,即分配方案为：甲A，乙E，丙B，丁C，戊D，总时间为：25+33+27+37+20=142小时,32,有五个车队将分赴五个地区，各车队去各地区的收入如下表：,每个车队去一个地区，每个地区有一个车队去。求使总收入最大的指派方案。,练习4：,33,五、网络规划,1最小支撑树问题2最短路问题3最大流问题,34,1最小支撑树（最小树）,设T=(,)是赋权图（网络）G=(,)的一棵支撑树，的所有边的权数之和称为支撑树T的权数。图G的所有支撑树中，具有最小权数的支撑树是图G的最小支撑树（最小树）。最小树的应用：例如设计长度最小的公路网把若干城市联系起来；设计用料最省的电话线网把有关单位联系起来等。,35,破圈法,在图中找圈，并删除其中最大边（如果有两条或两条以上的边都是权最大的边，则任意去掉其中一条边）。如此进行下去，直至图中不存在圈。,例6.4,36,避圈法（Kruskal算法）,把边按权从小到大依次添入图中（若有两条或两条以权数相同且最小，则任取一条），要求添加的边不构成圈，直至填满n-1条边为止（n为结点数）,例6.5,37,P.1673(c),最小树的权数w(T)=18,38,2最短路问题,问题描述：求网络中起点vs到其它点（终点vt）之间的一条最短路线。最短路问题是网络分析中的一个基本问题，它不仅可以直接应用于解决生产实际的许多问题，若管道铺设、线路安排、厂区布局等，而且经常被作为一个基本工具，用于解决其它的优化问题.,39,Dijkstra（狄克斯屈）标号法,基本思想：从起点vs开始，逐步给每个结点vj标号(j,lj)其中j是正数，它表示获得此标号的前一点的下标；lj表示起点vs到vj的最短路权（称为固定标号，记为P标号）或表示起点vs到该点的最短路权的上界（称为临时标号，记为T标号）。给vj点一个P标号时，表示起点vs到vj的最短路权，vj点的标号不再改变。给vj点一个T标号时，表示表示起点vs到vj的最短路权的上界，凡是没有得到P标号的点都有T标号。算法的每一步是去修改T标号，并且把某一个具有T标号的点改变为具有P标号的点，当终点vt得到P标号时，计算结束。对于有n个结点的图，至多经过n-1步，就可以求出从vs至vt及各点的最短路，再根据每一点的第一个数j反向追踪找出最短路径。,40,P.1675(a),41,Warshall-Floyd算法(弗洛伊德算法),Dijkstra（狄克斯屈）标号法的局限性：如果某边上的权为负时(wij0)，该方法失效。Warshall-Floyd算法适合求解权为负的网络最短路问题。P139,找到从v1到v2的最短路？,42,P.1676,43,3最大流问题,问题描述：网络最大流问题是网络的另一个基本问题。许多系统包含了流量问题。例如交通系统有车流量，金融系统有现金流，控制系统有信息流等。许多流量问题主要是确定这类系统网络所能承受的最大流量以及如何达到这个最大流量。,44,求最大流的标号法（Ford-Fulkerson）,理论依据：可行流x是最大流不存在关于x的增广链思路：从某一可行流x出发，按一定规划找出一条增广链，按定理2的方法调整x，得到一个流量增大的可行流x，对x重复上述做法，直到找不出增广链为止。此时就得到一个最大流，同时还得到一个最小截集。,45,步骤：,从一个可行流x出发（若网络中没有给定x，则可以设x是零流），经过标号过程与调整过程。1、标号过程在这个过程中，网络中的点或者是未标号点，或者是标号点（又分为已检查和未检查两种），每个标号点的标号包含两部分：第一个标号表明它的标号是从哪一点得到的，以便找出增广链；第二个标号是为确定增广链的调整量用的。,46,标号过程开始，总先给vs标上(0,+)，这时vs是标号而未检查的点，其余都是未标号点，一般地，取一个标号而未检查的点vi，对一与vi相邻而未标号点vj：(1)在弧(vi,vj)上，则当该弧上的流量xij0，则给vj标号(-vi,b(vj)。这里b(vj)=minb(vi),xji。这时点vj成为标号而未检查的点。当xij=0时不给vj标号。当所有与vi相邻而未标号的点vj都执行上述手续后，vi成为标号而已检查过的点，给vi打。重复上述步骤，一旦vt被标上号，表明得到一条从vs到vt的增广链，转入调整过程。若所有标号点都检查过，而标号过程进行不下去时(vt未得到标号)，说明不存在增广链，当前的可行流即最大流，算法停止。,47,例6.10求网络的最大流与最小截集，图中每条弧傍括号中的数字是rij,48,2,2,