《复习课运筹学》PPT课件.ppt
复习课运筹学,绍兴文理学院工学院计算机系2005.12.,模型、概念图解法标准化单纯形法对偶理论,线性规划问题,第五章,线性规划的图解法,max z=x1+3x2约束条件：x1+x26-x1+2x28 x10,x20,可行域,目标函数等值线,最优解(4/3,14/3),6,4,-8,6,约束条件(s.t.),线性规划问题,若干个决策变量x1,x2;2.约束条件(或或);3.符号约束(非负或非正或自由);4.目标函数(max或min)。,图解法,线性规划问题,Min z=3x1+2x2,约束条件,2x1+9x2182x1+4x2103x1+2x212 x10,x20,线性规划问题,目标函数 max f=3x1+4x2,线性规划问题,2x1+9x2=18,最优解(3.5,0.75),目标函数 f=3x1+4x2=13.5,3x1+2x2=12,2x1+4x2=10,可行解区域,约束条件,线性规划问题,目标函数 Max f=2x1+3x2,线性规划的标准化,用单纯形法求解线性规划要先标准化：目标函数求极大；全部是等式约束；所有决策变量全有非负约束。,Min zMax-z,不等式约束通过添加松弛变量()或剩余变量()化为等式约束。,处理非正和自由的变量,LP问题的单纯形法,用单纯形法求解下列线性规划,求最大；,全是的不等式；,常数项 b0;,全有非负约束。,这类最适用：单纯形法,LP问题的单纯形法,标准化；列初始单纯形表；迭代。,引入松弛变量x3,成x1+2x2+x3=2,引入松弛变量x4,成2x1+x2+x4=2,极小化极大。,两个松弛变量,LP问题的单纯形法,初始单纯形表,基变量是哪两个？,x3,x4,2,3,0,0,0,0,CB=?,LP问题的单纯形法,初始单纯形表,头两行?Zj=?末行？,2 3 0 0,1 2 1 0 2,2 1 0 1 2,0,0,LP问题的单纯形法,单纯形表,最优?谁进基?比值?谁出基？,12,LP问题的单纯形法,迭代,X2进基，x3出基，红格要变成几?,LP问题的单纯形法,第一次迭代,是最优解?谁进基?谁出基?,LP问题的单纯形法,第二次迭代,是最优解?最优解是?max?,LP问题的单纯形法,标准化；列初始单纯形表；迭代。,引入松弛变量x4,成x1+x4=2,引入松弛变量x5,成x1+x2+2x3+x5=4,三个松弛变量,引入松弛变量x6,成3x2+4x3+x6=6,LP问题的单纯形法,初始单纯形表,基变量是哪三个？,x,x5,1,2,0,0,x6,4,0,0,0,0,CB=?,1 0 0 1 0 0 2,1 1 2 0 1 0 4,0 3 4 0 0 1 6,0 0 0 0 0 0,0,1 2 4 0 0 0,线性规划,例1.一目标函数是Max Z的LP问题，用单纯形法解的过程中，得到如下数据有缺的单纯形表。,其中u为常数，求表中(*处)所有缺失的数。,分析,CB列中可确定哪几个？,0,6,0,0,0,Zj行中可确定哪几个？,6,0,0,0,0,0,0,0,Z1=？,j行中可确定哪几个？,C1-1=6,6,6u,3,5-6u,-3,1,150,a12=?,右下角=?,基变量列中可确定哪几个？,续,u=?时已得到唯一最优解。,u 5/6,u=0 时有最优解吗?,无有界最优解.,u=0.5 时有唯一最优解吗?,迭代一次得最优解.,对偶线性规划,LP问题对偶规划的提出求LP问题的对偶规划LP问题对偶单纯形法,例(对偶理论):原问题,几个变量？,这是要求X1,X2 使销售收入最_的LP问题,LP的对偶理论,设X1,X2 为产品1,产品2的产量,大,约束条件有几个？等式还是不等式约束？,Min f=y1 y2 y3 y4,其对偶有几个变量？约束条件有几个？求极大？极小？,4,2,极小,12,+16,+12,y1 y2 y3 y4,y1 y2 y3 y4,y1 y2 y3 y4,2,+,+4,+0,2,+2,+0,+4,2,3,0,，,，,，,+8,例1、写出下面问题的对偶规划,Max w=,y1 y2 y3,+2,+3,y1 y2 y3,y1 y2 y3,y1 y2 y3,y1 y2 y3,+,+0,+,+,+,-,自由,0,0,对一般的LP问题中：原问题第k个约束为等式或，对偶问题第k个变量是自由或非正变量。原问题第k个变量是自由或非正变量，则对偶问题第k个约束为等式或约束。,对偶问题,对偶关系对应表,Max f,-y1+2y2+y3,对偶规划,例2、写出下面问题的对偶规划,=6y1+9y2+4y3,2y1+5y3,3y2-2y3,y1 0,y3自由,y2 0,4 2-3,=,Min z=3X1+2X2+X3+4X4,2X1+4X2+5X3+X4 03X1-X2+7X3-2X4 25X1+2X2+X3+6X4 10X1,X2,X3,X4 0,例3、用对偶单纯形法解规划问题,运输问题,运输问题模型；表上作业法:求初始基可行解、判优、迭代。*用Excel解运输问题。,运输问题,产地数m=2,销地数n=3,产销平衡，决策变量个数m*n,等式约束数m+n，不等式约束数0,目标函数是总运价,要求最小。,表上作业法,运输问题的表上作业法：平衡产销；找出初始基可行解(西北角法、最小元素法、Vogel法)；基可行解是否最优的判别(闭回路法、位势法*)；非最优的基可行解的改进(闭回路调整法).,平衡产销,运输问题中产销不平衡时：产销：增加一个假想的仓库，运费为0，当新销地。产销：增加一个假想的产地，运费为0。总可以调整为产销平衡。,找出初始基可行解,运输问题的独立的等式约束数=系数矩阵的秩=基变量个数=m+n-1，非基变量个数=m*n-m-n+1。找出初始基可行解(m+n-1格)：西北角法；最小元素法;伏格尔(Vogel)法*等.,西北角法,最后得的初始基可行解。,3,4,4,2,2,2,2,3,3,6,6,找初始基可行解的西北角法,尽量用下标小的（左上角西北角优先安排）：x11=min(s1,d1)=d1=3,划去第一列（B1已满足）,s1s1-x11；x12=min(s1-x11,d2)=4,划去第一行（A1已满足）；划去m+n-1行(列)大功告成。,最小元素法,最后得的初始基可行解(不同于西北角法)。,3,1,1,4,4,3,6,3,3,3,3,找初始基可行解的最小元素法,尽量先用运价小的（就近优先安排，可能“因小失大”）：c21=min(cij)=1,x21=min(s2,d1)=3划去第一列（B1已满足）s2s2-x21；c23=min,x23=min(s2-x21,d3)=1划去第二行（A2已满足）d3d3-x23；划去m+n-1行(列)大功告成。,是基可行解？,不是！,从闭回路看。,？,？,4+5-1=8。,？,？,？,？,？,基可行解是否最优的判别,基可行解是否最优的判别(闭回路法、位势法*)；闭回路法求检验数,因为非最优的基可行解改进时用闭回路调整,所以优先介绍“闭回路法”位势法求检验数*.,闭回路法,对每个非基变量(如x11)求它的闭回路;,1,2,1,求它的检验数：3-1+2-3=10。,检验数无负是最优解，否则可调整。,-1,10,12,闭回路法调优,非基变量如x24检验数负,不是最优解;,利用它的闭回路调整:min(1,3)=1;,调整:奇加偶减，新方案再检验。,1,0,5,2,位势法判优,新方案再检验,逐个非基变量求检验数太繁，可用位势法求检验数；,检验数全部非负,找到最优解(不唯一)。,0,3,10,-2,3,-5,9,0,2,2,1,9,12,运输问题,例2.求下列运输问题的解。,检查产销是否平衡？,产销平衡？,20,最小元素法,用最小元素法求下列运输问题的初始基可行解。,用位势法检查此解是否最优？,3,5,5,1,3,3,位势法检验,求出位势检查此解是否最优？,求检验数此解优否？,0,2,1,4,-1,1,1,5,2,2,2,5,-1,否！闭回路？,如何调？,迭代、检验,用闭回路调整,调整量？,Min1,3=1,6,2,1,求位势！,0,1,4,1,0,0,1,求检验数！,3,6,1,1,1,5,有负的吗？,最优？,是！,总运费？,39！,一个求最大的LP问题的单纯形表如下：,课堂练习一.,求其中空缺的数(*)分别是什么？求出此LP问题的解。,x5,0,0,4,0,1,3,3/4,0,0,1,4,0,1,0,0,0,0,0,0,1,-1,6,解运输问题时,上表所示的是一个基可行解吗？为什么？,课堂练习二.,求解如下运输问题：,课堂练习三.,求下图中从A到E的最短路:,用标号法求得下图中从A到E的最短路,为A B2 C2 D1E,其长为7。,用标号法求得下图中从vs到vt的最短路,0,15,10,12,10,12,16,22,14,16,22,最短路为vs v3 vt,其长为22。,练习:求下图中从v1到v7的最短路,用标号法求得下图中从v1到v7的最短路,0,8,9,8,15,16,9,10,11,10,11,14,14,13,13,得：,运筹学,建模：问题类型、模式识别；选择解法：准确、快捷的计算。,解LP问题的软件,Excel:规划求解；Mathematica;LINDO与LINGO;有关知识可上网。,
