最优化课件Y07_线性规划

7.1 7.1 标准形式标准形式 7.2 7.2 单纯形法单纯形法 第7讲 线性 规划 污水管网监理规划下载职业规划大学生职业规划个人职业规划职业规划论文 1968年设诺贝尔经济学奖，1969到1992年32名获奖者中有13人(40%)从事过 与线性规划有关的研究工作 ¾一定的人、财、物下，效益最高 ¾一定的任务下，人、财、物最省 7.1 标准形式 1．等式约束 2．设计变量非负 3．右端项非负 11 1 12 2 1a x a x b+ ≤ 0ix ≤ { 0 iu xu = −≥ 松驰变量 无正负要求 11 1 12 2 3 1 3 0 a x a x x b x + + =⎧⎨ ≥⎩ 11 1 12 2 1a x a x b+ ≥ 11 1 12 2 3 1 3 0 a x a x x b x + − =⎧⎨ ≥⎩ 剩余变量 0 0 ix u v u v = −⎧⎪ ≥⎨⎪ ≥⎩ 1 1 2 2 11 1 12 2 1 1 21 1 22 2 2 2 1 1 2 2 min . . ( ) 0, 1,2, , n n n n n n m m mn n m j z c x c x c x a x a x a x b a x a x a x bs t m n a x a x a x b x j n = + + + + + =⎧⎪ + + + = <⎨⎪ + + + =⎩ ≥ = L L L M L L min . . 0 Tz C X s t AX b X = = ≥ 4．标准形式 5．概念 1 2 1 2 1 2 1 2 min 2 . . 3 5 15 6 2 24 0 x 0 z x x s t x x x x x = − − + ≤ + ≤ ≥ ≥ 基本解：等式约束AX=b中令非基变量=0得到的解(m个非0，n-m个0) ¾基本解个数≤从n个变量中取m个变量的组合数 ! !( )! m n nC m n m = − 基本可行解 基： A中m个线性无关的列向量。 基向量：组成基的列向量，m个。非基向量n-m个 基变量：与基向量对应的变量，m个。非基变量n-m个 例： 1 2 3 1 2 4 3 5 15 6 2 24 0i x x x x x x x + + = + + = ≥ 松弛向量、剩余变量并不出现在目标函数中 x1 x2 O BA E C D 15 3( , ) 4 4 4 5 3 12 (1)可行域为凸集 (2)最优解在顶点达到 每个顶点为基本可行解 如B点： x1 =5, x4 =-6, x2 =0, x3 =0 其它顶点也是基本解(但不可行) 找出所有基本解→基本可行解→最优解边(面)？ 相等 多解 基不唯一 与基对应 内部？ 等值线 为直线 量大，需系统化 7.2 单纯形法 (1)确定一个初始可行解 (2)寻找使目标函数有较大下降的新可行解 (3)判断是否最优，否则转(2) 从凸多面体一顶点向邻近 更好顶点搜索 1947年George Bernard Dantzig(美)提出；近100年来最成功的10个算法之一。 (1)取x3 , x4 为基变量，令其它x1 , x2 =0，则得初始可行解(0, 0, 12, 8) 1 2 1 2 1 2 1 2 min 3 4 . . 2 3 12 2 8 0,x 0 z x x s t x x x x x = − − + ≤ + ≤ ≥ ≥ 例： 1 2 3 1 2 4 2 3 12 2 8 x x x x x x + + = + + = (2)此时f=-3x1 -4x2 ，显然非最小(系数为负，若x1 , x2 ↑，则f↓) 其中x2 系数较大，使x2 成为新的基变量(进基)，将原x3 , x4 中的一个换出。看约 束表达式，随x2 ↑，x3 和x4 中x3 先退为0，将x3 换出基变量(退基) (3)用非基变量表示目标函数 其中x1 系数为负，f非最小。 1 3 1 2 1 1 3 12 23 4 3 4( ) 3 1 4 16 3 3 x xz x x x x x − −= − − = − − = − + − (4)x1 进基，x4 退基，非基量为x3 , x4 3 4 1 2 1 3 3 4 3 1 5 13 4 3(3 ) 4(2 ) 17 4 4 2 2 4 4 x xz x x x x x x= − − = − + − − − + = − + + 其中x3 , x4 系数为正，若变动则f ↑ ，即当前为最小。 顶点为(0, x2 , 0, x4 )，若向其 它顶点变动，则非基量x1 , x3 变非0，便于考察f变化趋势 顶点为(x1 ,x2 ,0,0) 此时x3 =0, x4 =0，求出x1 =3, x2 =2，f(X*)=17 (1)为什么用非基量表示目标函数？ (2)谁进基？ (3)谁退基？ 问 题 快递公司问题件快递公司问题件货款处理关于圆的周长面积重点题型关于解方程组的题及答案关于南海问题 ： 当前顶点非基量=0，邻近点≠0， 可考察向邻点搜索时f变化趋势 新目标函数表达式中，系数负大者 约束各行中xk 系数aik 相对较大者，即bi /aik 较小者 (4)剩余变量处理？ ij ja x b≥ ij j ka x x b− = 若仍简单取前几个为0，取后几个为基量，则xk <0，为非 可行解，不能作为初始解。人工变量法 1 1 2 2 n n n m m x b x bA x b + + + + =⎡ ⎤⎢ ⎥ + =⎢ ⎥⎢ ⎥ + =⎣ ⎦ O M 1 2min ( ) n n n mg f X Mx Mx Mx+ + += + + + +L求： 若M很大，则g最小就是原f最小。此时xn+i =0 ，否则无解。－大数法 1 2min n n n mg x x x+ + += + + +L或先求： 将其最优解(=0)作为原问题初始解，再解原问 题－两阶段法 增广初始可行解： (0, 0, …, 0, b1 , b2 , …, bm ) 1947年美国人G.B.Dantzig提出单纯形法，在线性规划中占绝对优势； 但，1972年V.Klee和G.Minty构造m=2n个不等式约束算例，单纯形法需 检验完所有顶点，计算步数大于2n，即(最坏)复杂性并不好 1979年苏联数学家L.G.Khachiyan，将椭球法发展用于线性规划，复杂性为多 项式。即线性规划可经过多项式次数运算解决，理论意义重大。 但，实际效果远不及单纯形法。因为一般复杂性与最坏复杂性几乎相当 Karmarkar算法 第7讲 线性规划 7.1　标准形式 幻灯片编号 3 7.2　单纯形法 幻灯片编号 5 幻灯片编号 6 幻灯片编号 7 幻灯片编号 8