水资源系统分析第2章线性规划与单纯形法ppt课件.ppt

1 第二章线性规划 2 1一般数学模型 1 1问题的提出 例1长度100米的钢材 需要截成3米 8米 11米短材 如何截取使剩料最少 要求 3米的最少2根 最多9根 8米的最少4根 11米的最少1根 最多8根 3 例2某灌区在年初估算可供水量为360万m3 计划灌溉小麦 玉米两种 总面积1000hm2 两种作物的毛灌溉定额及灌溉净效益如表 问该年两种作物的种植计划如何安排可使灌溉总净效益最大 4 模型 5 6 例3甲 乙两水库给A B C三座城市供水 甲库可供水量20万m3 d 乙库为25万m3 d A B C需水为10万m3 d 15万m3 d 20万m3 d 已知输水费用 标 求满足三个城市用水需要费用最小的输水方案 7 成本表 8 Obj minf x c1ax1a c1bx1b c2cx2c S tx1a x2a 10 x1b x2b 15x1c x2c 20 x1a x1b x13 20 x21 x22 x23 25x11 x12 x23 0 城市需水量约束 水库供水量约束 9 规划模型的要素决策变量 规划的措施 方案 是需要确定的未知变量 目标函数 规划的目的和用要求约束条件 决策变量的取值范围线性目标和约束组成线性规划模型 1 2数学模型 10 产生和发展19世纪 法国科学家Fourier提出线性规划 1939年苏联数学家康托维奇 机器负荷分配 原材料的合理利用等生产组织问题 二战期间开始应用于军事规划 英 美 1947年 Dantzig美国空军 斯坦福大学教授 提出了单纯形法求解线性规划问题 线性规划之父 11 Dantzig 配餐问题 美国空军为了保证士兵的营养 规定每餐的食品中 要保证一定的营养成份 例如蛋白质 脂肪 维生素等等 都有定量的规定 这些营养成份可以由各种不同的食物来提供 例如牛奶提供蛋白质和维生素 黄油提供蛋白质和脂肪 胡萝卜提供维生素 等等 由於战争条件的限制 食品种类有限 又要尽量降低成本 於是在一盒套餐中 如何决定各种食品的数量 使得既能满足营养成份的需要 又可以降低成本 最佳的配餐方案 12 线性规划一般形式 ob Max min Z c1x1 c2x2 cnxn 1 1 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 13 简写形式 14 向量形式 15 矩阵形式 ob Max min Z c1x1 c2x2 cnxn 1 1 s t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0 16 1 3线性规划的标准型 17 目标函数为求极小值变量X小于等于0X 0c 变量X无约束X X X X X 0 18 d 约束条件为不等式 x3 x4称为松弛变量 在目标函数里系数为零 19 将下面的模型化为标准型 例4 20 21 将下列LP问题化为标准型Ob MinZ 2x1 3x2s t 课堂练习 22 Maxz 2x1 3x2 0 x4 0 x5 0 x6 0 x7 课堂练习答案 23 1 4线性规划问题的解 可行解最优解 24 基B为A的一个m阶的满秩矩阵 则为一个基 Pj 基向量 xj 基变量 其他非基变量 25 基解令非基变量xm 1 xm 2 xn 0 因 B 0根据克莱姆法则 可以解出m个约束方程的m个基变量的唯一解X x1x2 xm 加上非基变量得到一个基解X x1x2 xm0 0 26 基可行解满足非负约束的基解 可行基对应基可行解的基 满意解可行不最优的解 27 例5 下面问题中 什么是基 基变量 基解 基可行解和可行基 28 系数矩阵 基 29 令非基变量xm 1 xm 2 xn 0 解出m个约束方程的m个基变量的唯一解X x1x2 xm T 加上非基变量得到一个基解X x1x2 xm0 0 T 30 令x1 x2 0 得基解 X 001281612 T此解为基可行解P p3p4p5p6 为可行基 31 找出下面模型的一个基 求基解 判断是否可行基 Maxz x1 2x2 3x4 3x5 0 x6 0 x7 课堂练习 32 课堂练习答案 系数矩阵 基 基可行解 33 2图解法 在坐标系上画出约束条件画出目标函数确定最优解简单直观 只适用于两个变量的情况 34 求解的直观原理 在只有两个决策变量的情况下目标函数可以简化成 x2 f x1 g z Z相当与坐标轴上的截距 不同的Z值组成一组平行线 同时对应X1 X2的不同取值范围 35 ob maxz 2x1 3x2s tx1 2x2 84x1 16 4x2 122x1 2x2 12x1 0 x2 0 以例3说明 36 O x1 x2 X1 2x2 8 4x1 16 4x2 12 2x1 2x2 12 ob maxz 2x1 3x2x2 2 3x1 z 3s tx1 2x2 84x1 16 4x2 122x1 2x2 12x1 0 x2 0 x2 2 3 X1 z 3 唯一解 x1 x2 4 2 z 14 37 O x1 x2 4x1 16 4x2 12 x2 2 4 X1 z 3 无穷多解 38 无界解 O x1 x2 4x1 16 x2 2 3 X1 z 3 39 无解 无可行域 O x1 x2 x2 x1 4 x2 0 7x1 4 40 图解法练习 课堂练习 41 课堂练习答案 x1 x2 X1 2x2 10 x2 4 X1 x2 1 X1 3x2 Z 2 4 o x2 1 3 x1 Z 3 Z 14 42 3单纯形法原理 3 1预备知识 凸集和顶点凸集 如何集合C内任意两个点X1 X2的连线上的所有点都在集合内部 则C为凸集 X X1 1 X2 C0 1 43 顶点 C中点X 若不在C中任何其他两点的连线上 则为顶点 A 不存在X X1 1 X20 1 有界凸集中的点都可由顶点的凸组合表示 44 扩展到n维 n个顶点 任一点 或者说 点集 是凸集 45 3 2几个基本定理 定理1 若线性规划问题存在可行解 可问题的可行域是凸集 证明 46 证明 47 引理可行解X x1 xn 为基本可行解的充要条件是X的正分量对应的系数列向量是线性独立的 证明 1 必要性基本可行解X的正分量对应的系数列向量是线性独立的 2 充分性X的正分量对应的系数列向量是线性独立的基本可行解 48 基可行解满足非负约束的的基解 由于非基变量为0 所以基可行解 x1 xm 中正分量集合不超过m 其对应系数列向量也不超出 p1 pm p1 pm 线性独立 其子集必然线性独立 1 必要性 49 P1 P2 Pk线性独立 若P的秩为m k m 恰构成一个基 X为基可行解 2 充分性 可行解X的正分量对应的系数列向量P1 P2 Pk是线性独立的X x1 x2 xk xm 0 0 基本可行解 若k m 在剩余P中找出m k个向量与P1 Pk构成一个基 P1 P2 Pk Pm 对应的解为 x1 x2 xk xm 0 X是基本可行解 0 0 50 基本可行解X的正分量对应的系数列向量是线性独立的 不是基本可行解X的正分量对应的系数列向量不是线性独立的 51 定理2线性规划问题的基本可行解X对应可行域的顶点可行解X是基本可行解可行域顶点可行解X不是基本可行解非可行域顶点 0 52 证明1 X不是基本可行解非可行域顶点由于不是基本可行解所以X的正分量对应的系数列向量不是线性独立的 设X的前m个分量为正 1 2 Pj不线性独立 53 1 2 1 2 X不是顶点 都为可行解 54 证明2 X基本可行解X是可行域顶点反正法 设X x1x2 xr0 0 不是顶点 则必有另外两个不同可行解Y Z 使X Y 1 Z 1 0 55 x有r个正分量 X不是基可行解 56 定理3若线性规划问题存在最优解 一定存在一个基可行解是最优解 证明 设 是最优解 57 代入目标函数 同为最优解 可能有一个顶点 若仍不是顶点 可继续做下去 直到达到顶点 为最优解 58 0 x1 x2 可行域是凸集 基可行解对应顶点 基可行解中存在最有解 59 3 3确定初始基可行解 方法 先找到一个基可行解 如果不是最优解 再转到另一个基可行解 是目标函数不断优化 直到最优解 步骤 1 找到一个基 求出可行解2 判优3 有向基可行解的转化 60 举例说明 ob maxz 2x1 3x2s t2x1 2x2 12x1 2x2 84x1 164x2 12x1 0 x2 0 61 标准型 MaxZ 2x1 3x2 0 x3 0 x4 0 x5 0 x6 1 11 2x1 2x2 x3 12x1 2x2 x4 84x1 x5 16 1 12 4x2 x6 12x1 x2 x3 x4 x5 x6 0 62 一 选择初始基可行解B初始基用非基变量表示基变量x3 12 2x1 2x2 x4 8 x1 2x2x5 16 4x1 x6 12 4x2当x1 x2 0时 得初始解 x 0 0 0 12 8 16 12 T代入目标函数式得 Z 2x1 3x2 0 1 13 63 二 最优检验从Z 2 0 3 0 看出 非基变量x1 x2均是正的 x1 x2 只要变成大于0的基变量 Z将增加 三 确定换入变量及其值从非基变量中选一个作为换入变量 成为基变量 一般选价值系数大的变量max cj 选x2 64 四 确定换出变量由于基变量个数的约束 m 必须将一个大于0的基变量变为等于0的非基变量 从Z最大的角度出发 希望换入变量x2的值尽量大 但有约束 65 x3 12 2x1 2x2 0 x4 8 x1 2x2 0 x5 16 4x1 0 x6 12 4x2 0当非基变量x1 0 得 x3 12 2x2 0 x4 8 2x2 0 x5 16 0 x6 12 4x2 0由上式得x2 min 12 2 8 2 16 12 4 3当x2 3时 x6 0 并使x3 x4 x5 0故用x2换x6基变量为x2x3 x4 x5 非基变量为x1 x6 66 五 求另一个更好的基可行解x3 12 x1 2x2 x3 6 x1 x6 2x4 8 x1 2x2 x4 2 x1 x6 2x5 16 4x1 x5 16 4x14x2 12 x6 x2 3 x6 4当x1 x6 0时 x 1 0 3 6 16 0 T代入目标得 Z 2x1 3x2 9一次寻优迭代结束 1 16 67 六 求另一个更好的基可行解X1为换入变量 x1 min 6 2 4 2故用x1换x4 得x 2 2 3 2 0 8 0 T再一次迭代x 3 4 2 0 0 0 4 T此时得到Z 14 max 68 3 最优性检验的判别经过若干次迭代后 基变量与非基变量aij bi 表示迭代后的系数 以便区别于原系数 其目标函数如何呢 代入目标函数 整理后 69 步骤1 初始基可行解的确定方法1 观察法方法2 当时 加松弛变量 化标准型 X1 a1 m 1xm 1 a1 nxn b1x2 a2 m 1xm 1 a2 nxn b2 Xm am m 1xm 1 am nxn bm 1 20 1 21 1 22 则得 B P1 P2 Pm 移项得 70 X1 b1 a1 m 1xm 1 a1nxnx2 b2 a2 m 11xm 1 a2n xn xm bm am m 1xm 1 amnxn令非基变量xm 1 xm 2 xn 0 xi bi i 1 2 m x x1 x2 xm 0 0 T b1 b2 0 0 T 1 23 71 方法3 约束是 形式 人造基大M法 两阶段法 72 步骤2 基可行解的转换 设有初始基可行解 基矩阵可以是单位矩阵形式 73 由于 74 步骤3最优性检验 如果 j 0 则迭代X 1 能改进目标函数 计算所有非基变量的 取最大值换入 75 j为检验数1 对一切j m 1 n 有 j 0时 则x 0 为局部最优 由于可行域是凸集 所以也是全局最优解 2 换入变量 Max j 0 k3 若有一个 m k 0 对一切i 1 2 m 有ai m k 0 无界解 或无最优解 76 4单纯形表 目标函数系数矩阵 基向量 非基向量检验数换入 换出变量迭代 77 78 1求初始基可行解 建立初始单纯形表2最优性检验 若非基变量检验数则停止迭代计算 否则转入下一步 3求另一个更好的基可行解 1 确定换入变量 xk为换入变量 2 确定换出变量 xl为换入变量 主要步骤 79 4若换入变量xk所在列的系数aik 均小于等于0 原线性规划无界 停止计算 否则转入下一步 5初等变换 求另一个单位矩阵对应的基可行解 将主元素alk 变换为1 所在列的其余元素变为0 得到新的单纯形表 80 MaxZ 2x1 3x2 0 x3 0 x4 0 x5x1 2x2 x3 84x1 x4 164x2 x5 12x1 x2 x3 x4 x5 0 例题5 81 1 x3 x4 x5 为基变量 初始基可行解 x0 0 0 8 16 12 初始单纯形表如下 0 x3 x4 x5 0 0 0 8 16 12 2 3 0 0 0 4 3 82 2 进行初等行变换 在xB列中用x2换x5 得到新的基解x1 0 3 2 16 0 z 9 2 0 0 0 3 4 2 4 83 3 重复上述计算过程 x5换出x4变量 84 4 重复上述计算过程 最优解x 4 2 0 0 4 z 14 85 课堂练习 86 第一步 87 第二步 88 第三步 89 1 5单纯形法的进一步讨论 1 5 1人工变量法模型约束方程 型 引入松弛变量标准化后 系数矩阵含有单位阵 容易得到初始基可行解 对于一些标准化后的问题 系数矩阵不含单位阵 无法直观地得到初始基可行解 90 MinZ 10 x1 8x2 7x32x1 2x2 6x1 x2 x3 4x1 x2 x3 0MaxZ 10 x1 8x2 7x3 0 x4 0 x52x1 2x2 x4 6x1 x2 x3 x5 4x1 x2 x3 x4 x5 0 标准化 91 系数矩阵为无法得到初始基可行解 当取x4和x5为初始基变量 当其它非基变量等于0时 x4 6 x5 4 不是可行解 为从A中得到可行基 在A中加上一列 变为 6 4 92 即将标准形线性规划的约束方程化为 2x1 2x2 x4 x6 6x1 x2 x3 x5 4x1 x2 x3 x4 x5 x6 0变量x6称为人工变量 x3和x6构成初始可行基 令其它非基变量为0 则可得一初始基可行解x0 0 0 4 0 0 6 93 标准化后 第一个约束方程已严格为 左边加入人工变量x6后 可能破坏约束 但如果人工变量x6 0 则不会破坏 人工变量在初始基可行解中不为0 但如果在后面的迭代过程中 如能把所有人工变量转变为非基变量 则人工变量都为0 这样 原有约束方程不会被破坏 94 如果已得到最优解 满足最优检验条件 而基变量中还有人工变量 人工变量不全为0 则无解 不存在满足所有约束方程的可行解 将人工变量从初始基可行解中转变为非基变量的方法有 1 大M法 2 两阶段法 95 例7 标准化 96 p4 p6 p7 增加人工变量 97 3 2M 4M 1 0 M 0 0 98 6M 3 0 4M 1 0 3M 4M 0 99 0 0 3 0 3 2 M 3 2 M 1 2 x1 x2 x3 x4 x5 0 5 2 3 2 0 0 Z 3 2 100 9 2 0 0 0 3 4 M 3 4 M 1 4 x1 x2 x3 x4 x5 0 5 2 3 2 0 0 Z 3 2 101 课堂练习 102 标准型 103 0 4 2M 0 6 3M M 104 105 Z 0 45 1200 0 200 540 人工变量是非基变量 106 5 2两阶段法 大M法不利于计算机计算两阶段法构造合适目标函数找出一组可行基构造Z x1 x2 也能换出人工变量 107 Z达到最大值0 x1 x2为0 有两种可能 1 x1 x2成为非基变量 得到不包含人工变量的初始可行基 进入下一阶段 2 x1或x2是基变量 但为零 退化 Z达到最大但不是0 说明起码不可能将人工变量完全换出 问题无解 108 109 2 4 0 0 1 0 0 第一阶段1 110 6 0 4 0 3 4 0 第一阶段2 111 0 0 0 0 0 1 1 第一阶段3 112 0 0 3 0 3 2 第二阶段1 113 9 2 0 0 0 3 4 第二阶段2 114 5 3解的判别 1 无界解目标函数为最大 如换入变量xk所在列所有技术系数均小于等于0 即aik 0 i 1 2 m 则利用最小规则无法得到一个换出变量 115 2 退化解一般情况 基可行解中非0分量个数等于约束方程的个数m 如果某一基可行解中非0分量个数小于m 即一些基变量值等于0 该基解为退化解 116 按 规则确定换出变量时 同时存在两个以上相同的最小比值 在下一次迭代中就有一个或几个基变量等于零 这就出现了退化解 继续迭代 ob值不变 造成死循环 判别 当bi中有一个以上为0时 就称为退化 避免 摄动法 词典序法 勃兰特 法 117 2 无穷多解非基变量检