《运筹学习题课》PPT课件.ppt

运筹学习题课 Date1运筹学习题课 练习用图解法和单纯形法 求如下线性规划问题的最优 解： Max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0 Date2运筹学习题课 练习1.用图解法 01234567 1 2 3 4 5 (2.25,0) 4x1+x2=9 Date3运筹学习题课 练习 Max z =4 x1 + x2 x1 + 3x2 7 s.t. 4x1 + 2x2 9 x1 , x2 0 解：先要标准化：引入_个剩余变量;0 引入_个松弛变量;2 Maxz =4 x1 + x2 + 0x3 + 0x4 s.t. x1 + 3x2 + x3 = 7 4x1 + 2x2 + x4 = 9 x1 , x2 , x3 , x4 0 Date4运筹学习题课 练习2.用单纯形法 x3 x4 4100 0 0 1 3 1 0 7 4 2 0 1 9 迭代 次数 基 变量 CB x1x2x3x4 bi比 迭代 次数 基 变量 CB x1x2x3x4 bi比 0 zj j=Cj- zj 1 zj j=Cj- zj 0 0 0 0 0 4 1 0 0 7 9/4 4 1 0 0 x3 x1 0 41 0.5 0 0.25 2.25 0 2.5 1 -0.25 4.75 4 2 0 1 9 0 -1 0 -1 Date5运筹学习题课 .用图解法和单纯形法求如 下线性规划问题的最优解： Min f =2x1 + 3x2 x1 + x2 350 s.t. x1 125 2x1 + x2 600 x1 , x2 0 Date6运筹学习题课 .用图解法 0 100300400 100 200 300 400 200 (250,100) 2x1+3x2=800 Date7运筹学习题课 .用单纯形法求解：Min f =2x1 + 3x2 x1 + x2 350 s.t. x1 125 2x1 + x2 600 x1 , x2 0 解：先标准化，目标函数改为求： z f 的极大。Max z = -f = 2x13x2 引进两个剩余变量x3,x4，一个松弛变量x5 。 Max z =2x13x2 + 0x3 + 0x4 + 0x5 x1 + x2 x3 350 s.t. x1 x4 125 2x1 + x2 + x5 600 x1 , x2 , x3 , x4 , x5 0 Date8运筹学习题课 Max z =2x13x2 + 0x3 + 0x4 + 0x5 x1 + x2 x3 350 s.t. x1 x4 125 2x1 + x2 + x5 600 x1 , x2 , x3 , x4 , x5 0 系数矩阵中有没有三列可组成单位矩阵？ 它的系数矩阵是： 没有没有 ！ 前两行各乘1,可组成单位矩阵吗？ 可以可以, ,但没用但没用 ！ 因为这样做常数项就出现负数！ 要用人工变量要用人工变量！ Date9运筹学习题课 它的系数矩阵是 ： 显然x x 6 6 , x , x 7 7 必须为, 想一想两个M(大正数)的意图 。 追加两列 追加两列 ，引进人工变量，引进人工变量x x 6 6 , x , x 7 7 ， Max z =2x13x2 + 0x3 + 0x4 + 0x5Mx6Mx7 x1 + x2 x3 + x6 350 s.t. x1 x4 + x7 125 2x1 + x2 + x5 600 x1 , x2 , x3 , x4 , x5 , x6 , x7 0 Date10运筹学习题课 用单纯形法 x6 x7 -475M -M 0 -2M -M M M 0 -M -M 350 x5 -M -2+2M 3+M -M -M 0 0 0 125 300 基变量是谁？ CB列填什么 ？ 计算Zj求检验数 谁最大 ？ x1的-2+2M 求比值谁最小 ？ 125, 谁进基 ？ x1, 谁进基 ？ x7, x1 -M -2 0 -225M-250 Date11运筹学习题课 单纯形法(后两次迭代) 是最优基 ， 原问题的最优解是:(250,100)，最优值是 800 。 Date12运筹学习题课 前两个等式约束乘-1,适用对偶单纯形法 Max z =2x13x2 + 0x3 + 0x4 + 0x5 x1 + x2 x3 350 s.t. x1 x4 125 2x1 + x2 + x5 600 x1 , x2 , x3 , x4 , x5 0 0 0 0 0 0 0-2 -3 0 0 0 2 3 Date13运筹学习题课 .用对偶单纯形法 谁进基 ？ x1进基. 谁出基 ？ x3出基. x2进基. x5出基. Date14运筹学习题课 .用对偶单纯形法 (检验数全非正),常数项全非负,这是最优解 。 原问题的最优解是：x1=250,x2=100,Min f=800 。 Date15运筹学习题课 用单纯形法与对偶单纯形法的比较 。 单纯形法最好是：约束全是“”，且常数项 全非负，(求极大还是极小，目标函数的系数正 负倒是无所谓的)。此时初始基可行解易得。 否则就要利用引进人工变量等方法来寻找初 始基可行解。 对偶单纯形法最好是：求极大(极小)，且目 标函数的系数全负(正)的，全是不等式约束(但 约束是“”还是“”,常数项的符号倒是无所谓)。 此时初始正则基易得。 要善于选择工具! Date16运筹学习题课 单纯形法中人工变量的引进 单纯形法最好是：约束全是“”，且 常数项全非负，此时初始基可行解易得 。 引进的人工变量实际上最后必须是0 ，所以它们在求极大(小)问题的目标函 数的系数都是-M(M),这里的M是一个很 大的正数。此方法故也叫“大M法”，也 可叫“罚函数法”，M叫“罚因子”。 Date17运筹学习题课 单纯形法中无最优解 LP问题没有最优解分两种情况 ： 1.没有可行解(当然没有最优解) :如引进 了人工变量，最后它们中有不能为0的. 2.有可行解但没有有限的最优解：检验 数有正的但系数矩阵该列中所有系数没 有正数，不能继续迭代，这就说明该LP 问题没有有限的最优解。 Date18运筹学习题课 单纯形法中无可行解 P.88例1.解下列LP问题： Max z = 20x1 + 30x2 3x1 + 10x2 150 s.t. x1 30 x1 + x2 40 x1 , x2 0 用Excel的规 划求解得到 ： Date19运筹学习题课 图解法求图解法求P.88P.88例例1. 1. 0 103040 10 20 30 40 2050 可行域为空集可行域为空集 Date20运筹学习题课 用用单纯形法求解单纯形法求解 Max z=20x1+30x2 3x1 +10x2 150 s.t. x1 30 x1+ x2 40 x1 ,x2 0 +x4 = +x3 = ,x6 -x5 = ,x3 ,x4 ,x5 +x6 要化成等式约束，添加两个松弛变量 x3, x4，一个剩余变量x5 。 用单纯形法，再引进一个人工变量x6 。 +0x3+0x4+0x5-Mx6 Date21运筹学习题课 用单纯形法求解用单纯形法求解 Date22运筹学习题课 用单纯形法求解用单纯形法求解 检验数全非正，此解已是“最优解” ，但人工变量x6仍是基变量,且x6=40，所以 原线性规划问题没有可行解。 Date23运筹学习题课 线性规划中无可行解 1. (常数项非负,全是不等式约束.)不须引 进人工变量的LP问题会不会无可行解？ 在保证常数项非负的情况下，只有 遇到等式约束或“”的不等式约束才会 需要引进人工变量。若一个LP问题全 部是“”的不等式约束就不需要引进人 工变量。(0,0,0)就是该LP问题的一 个可行解,所以不会没有可行解。 Date24运筹学习题课 线性规划中无可行解 2. 须引进人工变量的LP问题是否一定 没有可行解？ 当然不一定 。 3. 没有最优解的LP问题是否一定没有 可行解？ 当然不一定 。 Date25运筹学习题课 线性规划中无最优解 1.没有可行解的LP问题会不会有最优解？ 答:没有可行解的LP问题一定没有最优解 。 2.有可行解的LP问题是否一定有最优解？ 答:有可行解的LP问题也可能没有最优解 。 有可行解的LP问题如可行域是有界的则它一 定有最优解。所以无最优解只会出现在可行域 是空集或是无界集的情况。 从一个一个的可行基迭代进程中如没有找到 最优(基)解，而又不能再继续迭代：出现检验 数有正的，但系数矩阵的该列中没有正的系数 。 下面就通过举例来讨论用单纯形法如何判断 有可行解的LP问题有还是没有最优解。 Date26运筹学习题课 无最优解的线性规划 P.90例2.解下列LP问题： Max z = x1 + x2 x1 x2 1 s.t. 3x1 +2x2 6 x1 , x2 0 用Excel的规划求解得到 ： Date27运筹学习题课 图解法求图解法求P.90P.90例例2. 2. -2-1 12 1 2 3 4 03 可行域为无界集可行域为无界集 目标函数等高线可无限上移目标函数等高线可无限上移 Date28运筹学习题课 用用单纯形法求解单纯形法求解 Max z= x1+ x2 x1 - x2 1 s.t. -3x1 +2x2 6 x1 , x2 0 +x4 = +x3 = ,x3 , x4 化等式约束，添加两个松弛变量x3, x4 。 +0x3 +0x4 先标准化先标准化 列出初始单纯形表 ： Date29运筹学习题课 用单纯形法求解用单纯形法求解 有两个检验数为正，选 ？ 进基 ， x2 该列系数只有一个为正，选 ？ 出基 。 x4 3 Date30运筹学习题课 让让x x 1 1 出基也类似出基也类似 有两个检验数为正，选 ？ 进基 ， x1 该列系数只有一个为正，选 ？ 出基 。 x3 1 Date31运筹学习题课 用单纯形法求解用单纯形法求解 有正检验数，此基可行解不是“最优解” ， 但该列没有正的系数，迭代无法继续下 去，即原LP问题没有最优解。 事实上0时(+1,)都是原LP问题的可 行解,令+说明它没有最优解。 Date32运筹学习题课 最优解不唯一的线性规划 1.有最优解的LP问题最优解会不会是否唯一 ？ 答:图解法中如最后目标函数的等高线停止移动 时恰好与可行域的某条边界线相叠.该LP问题的 最优解不唯一。 2.用Excel的规划求解找到一个LP问题的最优解 ,它唯一吗？ 答:由于Excel的规划求解的方法所限，得到LP 问题的一个最优解，不等于仅此一解，特别要 注意的是这个解都不一定是基解。 在最后的单纯形表的一个最优(基)解中出现某 非基变量的检验数为0，则此LP问题的最优解不 唯一有无穷多个。 下面举例说明用单纯形法如何判断LP问题的 最优解是否唯一。 Date33运筹学习题课 最优解不唯一的线性规划 P.91例3.解下列LP问题： Max z = 50x1 +50 x2 x1 + x2 300 s.t. 2x1 + x2 400 x2 250 x1 , x2 0 当你试图利用 Excel 的规划求解时，你 能从不同的初始解得到不同的最优解，可惜 的是这一点往往是被人们忽略的。 Date34运筹学习题课 .用图解法 0 100300 100 200 300 400 200 (100,200) 50x1+50x2=15000 (50,250) 两线叠合 ，连接 (100,200), (50,250)的线 段上的任一点 都是最优解无 穷多个。 Date35运筹学习题课 用用单纯形法求解单纯形法求解 Max z=50x1+50x2 x1 +x2 300 s.t. 2x1 +x2 400 x2 250 x1 , x2 0 +x4 = +x3 = ,x3 ,x4,x5 引进松弛变量x3 , x4 , x5 。 +0x3+0x4+0x5 先标准化先标准化 列出初始单纯形表 ： +x5= Date36运筹学习题课 用单纯形法求解用单纯形法求解 有两个检验数为正，选 ？ 进基 ， x1 该列系数有两个为正，选 ？ 出基。 x4 300 200 200 400 250 Date37运筹学习题课 让让x x 2 2 进基进基x x 3 3 出基迭代出基迭代 所有检验数非正，得一个最优解，但有一 个非基变量的检验数为0，可选 ？ 进基 ， x4 该列系数有两个为正，选 ？ 出基。 x5 100 50 250 50 Date38运筹学习题课 X4、x5可以轮流进基、出基。两“最优解” 。 Date39运筹学习题课 最优解不唯一的线性规划 1.有最优解的LP问题最优解会必可以在可行域 的某一顶点处得到。 2.有两个不同的最优解的LP问题就有无穷多个 最优解。 3.一个LP问题的可行域的某两个顶点处是最优 解,则它们连线段上的所有点无穷多个都是最 优解。 4.一个LP问题的可行域的某三个顶点处是最优 解,则以它们为顶点的三角形上的所有点无穷 多个都是最优解。依此类推：一个LP问题的 可行域的n个顶点处是最优解,则以它们点凸包 上(边及内部)的所有点无穷多个都是最优解 。 Date40运筹学习题课 单纯形法中最优解讨论 LP问题的最后的单纯形表中 ： 1.有取值大于0的人工变量仍是基 变量，这个LP问题没有可行解， 也没有最优解。 2.有一个正的检验数，且该列中的 系数非正，这个LP问题没有有限 的最优解。 3.检验数全非正，但有一个非基变 量的检验数是0，且可以进基，这 个LP问题有无穷多个最优解。 Date41运筹学习题课 运筹学方法使用情况(美1983) Date42运筹学习题课 运筹学方法在中国使用情况(随机抽样 ) Date43运筹学习题课 线性规划线性规划 .一目标函数是Max Z的LP问题，用单纯形法 解的过程中，得到如下数据有缺的单纯形表。 其中u u为常数，求表中(*处)所有缺失的数 。 Date44运筹学习题课 分析分析 C CB B 列中可确定哪几个列中可确定哪几个 ？ 0 0 6 6 0 0 0 0 0 0 Z Zj j 行行中可确定哪几个？中可确定哪几个？ 6 6 0 0 0 0 0 0 0 0 0 0 0 0 0 0 Z Z1 1 = = ？ j j 行行中可确定哪几个中可确定哪几个 ？ C C1 1 - 1 1 =6=6 6 6 6u6u 3 3 5-65-6u u-3-3 1 1 150150 a a 1212=? =? 右下角右下角=?=? 基变量列中可确定哪几个？基变量列中可确定哪几个？ Date45运筹学习题课 续续 u = ? u = ? 时时已已得到唯一最优解。得到唯一最优解。u 5/6 u 5/6 u = 5/6 u = 5/6 时有最优解吗时有最优解吗 ? ? 无有界最优解无有界最优解 . . u = 0.5 u = 0.5 时有唯一最优解吗时有唯一最优解吗? ? 迭代一次得最优解迭代一次得最优解 . . Date46运筹学习题课 运输问题运输问题 .求下列运输问题的解。 检查产销是否平衡？产销平衡! 2020 Date47运筹学习题课 最小元素法最小元素法 用最小元素法求下列运输问题的初始基可行解 。 用位势法检查此解是否最优 ？ 3 0 5 5 0 3 5 0 1 1 0 3 3 3 Date48运筹学习题课 位势法检验位势法检验 求出位势检查此解是否最优 ？ 求检验数此解优否 ？ 0 214 -1 1 1 5 22 2 5-1 否！闭回路 ？ 如何调 ？ Date49运筹学习题课 迭代、检验迭代、检验 用闭回路调整,调整量 ？ Min1,3=1 6 6 2 2 1 求位势 ！ 0 14 1 0 0 1 求检验数 ！ 36 11 15 有负的吗 ？ 最优 ？ 是 ！ 总运费 ？ 3939 ！ Date50运筹学习题课 一个求最大的LP问题的单纯形表如下 ： 课堂练习一 . 求其中空缺的数(*)分别是什么？求出此LP问题的解 。 x5x5 0 0 0 0 4 4 0 0 1 1 3 3 3/43/4 0 0 0 0 1 1 4 4 0 0 1