复习课运筹学.ppt

《复习课运筹学.ppt》由会员分享，可在线阅读，更多相关《复习课运筹学.ppt（58页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、复习课运筹学 Still waters run deep.流静水深流静水深,人静心深人静心深 Where there is life,there is hope。有生命必有希望。有生命必有希望模型、概念模型、概念图解法图解法标准化标准化单纯形法单纯形法对偶理论对偶理论线性规划问题线性规划问题第五章第五章线性规划的图解法线性规划的图解法 max z=x1+3x2约束条件：x1+x26 -x1+2x28 x10,x20可行域可行域可行域可行域目标函数等值线目标函数等值线最优解最优解最优解最优解(4/3,14/3)(4/3,14/3)64-860 x1x2约束条件 (s.t.)线性规划问题线性规划问

2、题2.5x1+1.5x2 90 4x1+5x2200 3x1+10 x2300 x10,x20目标函数目标函数 max z=7x1+12x21.若干个决策变量若干个决策变量x1,x2;2.2.约束条件约束条件(或或或或);3.3.符号约束符号约束(非负或非正或自由非负或非正或自由);4.4.目标函数目标函数(max或或min)。图解法线性规划问题线性规划问题 x1+x26 x1x24 x1+3x262x1+x24x10,x20s.t.Min z=3x1+2x2线性规划的标准化线性规划的标准化 用用单单纯纯形形法法求求解解线线性性规规划要先标准化：划要先标准化：v目标函数求极大；目标函数求极大；

3、v全部是等式约束；全部是等式约束；v所所有有决决策策变变量量全全有有非非负负约束。约束。Min zMax-z 不等式约束不等式约束通过添加松弛通过添加松弛变量变量()或剩或剩余变量余变量()化化为等式约束。为等式约束。处理非正和自由的变量处理非正和自由的变量LPLP问题的单纯形法问题的单纯形法用单纯形法求解下列线性规划用单纯形法求解下列线性规划求最大；求最大；全是全是的不等式；的不等式；常数项常数项 b0;b0;全有非负约束。全有非负约束。这类最适用：这类最适用：单纯形法单纯形法LPLP问题的单纯形法问题的单纯形法标准化；列初始单纯形表；迭代。标准化；列初始单纯形表；迭代。引入松弛变量引入松弛

4、变量x3 ,成成x1+2x2+x3=2引入松弛变量引入松弛变量x4 ,成成2x1+x2+x4=2极小化极大。极小化极大。两两个个松松弛弛变变量量LPLP问题的单纯形法问题的单纯形法初始单纯形表初始单纯形表基变量是哪两个基变量是哪两个？x x3 3x x4 42 23 30 00 00 00 0C CB B=?=?LPLP问题的单纯形法问题的单纯形法初始单纯形表初始单纯形表头两行头两行?Z?Zj j=?=?末行末行？2 3 0 02 3 0 01 2 1 0 21 2 1 0 22 1 0 1 22 1 0 1 20 00 0LPLP问题的单纯形法问题的单纯形法单纯形表单纯形表最优最优?谁进基谁

5、进基?比值比值?谁出基？谁出基？1 12 2LPLP问题的单纯形法问题的单纯形法迭代迭代X X2 2进基，进基，x x3 3出基，红格要变成几出基，红格要变成几?LPLP问题的单纯形法问题的单纯形法第一次迭代第一次迭代是最优解是最优解?谁进基谁进基?谁出基谁出基?LPLP问题的单纯形法问题的单纯形法第二次迭代第二次迭代是最优解是最优解?最优解是最优解是?max?max?LPLP问题的单纯形法问题的单纯形法标准化；列初始单纯形表；迭代。标准化；列初始单纯形表；迭代。引入松弛变量引入松弛变量x4 ,成成x1+x4=2引入松弛变量引入松弛变量x5 ,成成x1+x2+2x3+x5=4三三个个松松弛弛变

6、变量量引入松弛变量引入松弛变量x6 ,成成3x2+4x3+x6=6LPLP问题的单纯形法问题的单纯形法初始单纯形表初始单纯形表基变量是哪三个基变量是哪三个？x xx x5 51 12 20 00 0 x x6 64 40 00 00 00 0C CB B=?=?1 1 0 0 0 0 1 1 0 0 0 0 2 21 1 1 2 1 2 0 0 1 0 1 0 4 40 0 3 4 3 4 0 0 0 1 0 1 6 60 0 0 0 0 0 0 0 0 00 00 01 1 2 4 2 4 0 0 0 00 0线性规划线性规划例例1.1.一目标函数是一目标函数是Max Z的的LPLP问题，用

7、单纯形法问题，用单纯形法解的过程中，得到如下数据有缺的单纯形表。解的过程中，得到如下数据有缺的单纯形表。其中其中u u为常数，求表中为常数，求表中(*处处)所有缺失的数。所有缺失的数。分析分析C CB B列中可确定哪几个列中可确定哪几个？06000Z Zj j行中可确定哪几个？行中可确定哪几个？60000000Z Z1 1=？j j行中可确定哪几个行中可确定哪几个？C C1 1-1 1=6=666u35-6u5-6u-31150a a1212=?=?右下角右下角=?=?基变量列中可确定哪几个？基变量列中可确定哪几个？续续u=?u=?时时已已得到唯一最优解。得到唯一最优解。u 5/6 u 5/6

8、 u=0 u=0 时有最优解吗时有最优解吗?无有界最优解无有界最优解.u=0.5 u=0.5 时有唯一最优解吗时有唯一最优解吗?迭代一次得最优解迭代一次得最优解.对偶线性规划对偶线性规划vLP问题对偶规划的提出问题对偶规划的提出v求求LP问题的对偶规划问题的对偶规划vLP问题对偶单纯形法问题对偶单纯形法例例(对偶理论对偶理论):原问题原问题几个变量？几个变量？这是要求这是要求X1,X2 使销售收入最使销售收入最_的的LP问题问题LPLP的对偶理论的对偶理论设设X1,X2 为产品为产品1,产品产品2的产量的产量大大约束条件有几个？约束条件有几个？等式还是不等式约束？等式还是不等式约束？Min f

9、=y1 y2 y3 y4 其对偶有几个变量？其对偶有几个变量？约束条件有几个？约束条件有几个？求极大？极小？求极大？极小？42极小极小12+16+12y1 y2 y3 y4 y1 y2 y3 y4 y1 y2 y3 y4 2+4+02+2+0+4230，+8Min z=2x1+x2-x3 x1+x2-x3 =1x1-x2+x3 2 x2+x3 3x1 0,x2 0,x3自由自由例例1、写出下面问题的对偶规划、写出下面问题的对偶规划Max w=y1 y2 y3 +2+3y1 y2 y3 y1 y2 y3 y1 y2 y3 y1 y2 y3 +0+-自由自由,0,0 对一般的对一般的LP问题中：问

10、题中：原问题第原问题第k个约束为个约束为等式等式或或，对偶，对偶问题第问题第k个变量是个变量是自由自由或非正或非正变量。变量。原问题第原问题第k个变量是个变量是自由自由或非正或非正变量，变量，则对偶问题第则对偶问题第k个约束为个约束为等式等式或或约束。约束。对偶问题对偶问题 原问题原问题 对偶问题对偶问题目标函数类型目标函数类型 Max Min目标函数与右边目标函数与右边 目标函数系数目标函数系数 右边常数项右边常数项常数项的对应关系常数项的对应关系 右边常数项右边常数项 目标函数系数目标函数系数变量数与约束数变量数与约束数 变量数变量数n 约束数约束数 n的对应关系的对应关系 约束数约束数m

11、 变量数变量数m原问题变量类型与原问题变量类型与 变量变量 0约束约束对偶问题约束类型对偶问题约束类型 变量变量 0 约束约束的对应关系的对应关系 自由变量自由变量 约束约束原问题约束类型与原问题约束类型与 约束约束 变量变量 0 对偶问题变量类型对偶问题变量类型 约束约束 变量变量 0 的对应关系的对应关系 约束约束 自由变量自由变量对偶关系对应表对偶关系对应表运输问题运输问题运输问题模型；运输问题模型；表上作业法表上作业法:求初始基求初始基可行解、判优、迭代。可行解、判优、迭代。*用用ExcelExcel解运输问题。解运输问题。运输问题运输问题产地数产地数m=2,m=2,销地数销地数n=3

12、,n=3,产销平衡，产销平衡，决策变量个决策变量个数数m*n,m*n,等式等式约束数约束数m+nm+n，不等式约束不等式约束数数0,0,目标函目标函数是总运价数是总运价,要求最小。要求最小。表上作业法表上作业法运输问题的表上作业法：运输问题的表上作业法：平衡产销；平衡产销；找出初始基可行解找出初始基可行解(西北角法、西北角法、最小元素法、最小元素法、VogelVogel法法)；基可行解是否最优的判别基可行解是否最优的判别(闭闭回路法、位势法回路法、位势法*)；非最优的基可行解的改进非最优的基可行解的改进(闭闭回路调整法回路调整法).).平衡产销平衡产销:运输问题中产销不平衡时：运输问题中产销不

13、平衡时：:产产 销：增加一个假想的仓销：增加一个假想的仓库，运费为库，运费为0 0，当新销地。，当新销地。:产产 销：增加一个假想的产销：增加一个假想的产地，运费为地，运费为0 0。:总可以调整为产销总可以调整为产销平衡平衡。找出初始基找出初始基可行解可行解运输问题的独立的等式约束数运输问题的独立的等式约束数=系数系数矩阵的秩矩阵的秩=基变量个数基变量个数=m+n-1=m+n-1，非基变，非基变量个数量个数=m*n-m-n+1=m*n-m-n+1。找出初始基可行解找出初始基可行解(m+n-1(m+n-1格格)：西北角法西北角法；最小元素法最小元素法;伏格尔伏格尔(Vogel)(Vogel)法法

14、*等等.西北角法西北角法最后得的初始基可行解。最后得的初始基可行解。34422223366找找初初始始基基可可行行解解的的西西北北角角法法尽量用下标小的（左上角尽量用下标小的（左上角西北角优先安排）：西北角优先安排）：x x1111=min(s=min(s1 1,d,d1 1)=d)=d1 1=3,=3,划去第一划去第一列（列（B B1 1已满足）已满足）,s,s1 1ss1 1-x-x1111；x x1212=min(s=min(s1 1-x-x1111,d,d2 2)=4,)=4,划去第一划去第一行（行（A A1 1已满足）；已满足）；划去划去m+n-1m+n-1行行(列列)大功告成。大功

15、告成。最小元素法最小元素法最后得的初始基可行解最后得的初始基可行解(不同于西北角法不同于西北角法)。31144363333找初始基可行解找初始基可行解的最小元素法的最小元素法尽量先用运价小的（就近优先安尽量先用运价小的（就近优先安排，可能排，可能“因小失大因小失大”）：）：c c2121=min(c=min(cijij)=1,x)=1,x2121=min(s=min(s2 2,d,d1 1)=3)=3划去第一列（划去第一列（B B1 1已满足）已满足）s s2 2ss2 2-x-x2121；c c2323=min,x=min,x2323=min(s=min(s2 2-x-x2121,d,d3

16、3)=1)=1划去划去第二行（第二行（A A2 2已满足）已满足）d d3 3dd3 3-x-x2323；划去划去m+n-1m+n-1行行(列列)大功告成。大功告成。是基可行解是基可行解？不是！不是！从闭回路看。从闭回路看。？4+5-1=8 。？基可行解是否基可行解是否最优的判别最优的判别基可行解是否最优的判别基可行解是否最优的判别(闭回路法、位势法闭回路法、位势法*)；闭回路法闭回路法求检验数求检验数,因为非最因为非最优的基可行解改进时用闭回路优的基可行解改进时用闭回路调整调整,所以优先介绍所以优先介绍“闭回路法闭回路法”位势法位势法求检验数求检验数*.运输问题运输问题例例2.2.求下列运输

17、问题的解。求下列运输问题的解。检查产销是否平衡？检查产销是否平衡？产销平衡产销平衡？2020最小元素法最小元素法用最小元素法求下列运输问题的初始基可行解。用最小元素法求下列运输问题的初始基可行解。用位势法检查此解是否最优用位势法检查此解是否最优？30550350110333位势法检验位势法检验求出位势检查此解是否最优求出位势检查此解是否最优？求检验数此解优否求检验数此解优否？0214-11152225-1否！闭回路否！闭回路？如何调如何调？迭代、检验迭代、检验用闭回路调整用闭回路调整,调整量调整量？Min1,3=1621求位势！求位势！0141001求检验数！求检验数！361115有负的吗有负

18、的吗？最优最优？是是！总运费总运费？3939！求下图中从求下图中从A A到到E E的最短路的最短路:AB1C3B2C1C2225611312316ED3D1D2134514用标号法求得下图中从用标号法求得下图中从A到到E的最短路的最短路AB1C3B2C1C2225611312316ED3D1D21345140233464576为为A B2 C2 D1E,其长为其长为7。vsv2v3v1v4vt151041010102012453用标号法求得下图中从用标号法求得下图中从vs到到vt的最短路的最短路 01510121014121622141622最短路最短路为为vs v3 vt,其长为其长为22。练习练习:求下图中从求下图中从v v1 1到到v v7 7的最短路的最短路 用标号法求得下图中从用标号法求得下图中从v1到到v7的最短路的最短路0898151691011101114141313得：得：运筹学运筹学建模：问题建模：问题类型、模式识类型、模式识别；别；选择解法：选择解法：准确、快捷准确、快捷的计算。的计算。解解LP问题的问题的软件软件Excel:Excel:规划求解；规划求解；Mathematica;Mathematica;LINDOLINDO与与LINGO;LINGO;有关知识可上网。有关知识可上网。