第二章 最优化-线性规划.ppt

第二章线性规划 2 2 1凸集与凸函数 3 凸集 定义2 1 1设集合DRn 若对于任意点x y D 及实数a 0 a 1 都有ax 1 a y D 则称集合D为凸集 常见的凸集 单点集 x 空集 整个欧式空间Rn 超平面H x Rn a1x1 a2x2 anxn b 半空间H x Rn a1x1 a2x2 anxn b 实心圆 实心球 实心长方体等都是凸集 4 凸集 从直观上看 没有凹入部分 或没有空洞的是凸集 几何解释为 集合D中任两点连线上的每一点仍在D中 则D为凸集 5 凸集的例 例2 1 2超球 x r为凸集证明设x y为超球中任意两点 0 a 1 则有 ax 1 a y a x 1 a y ar 1 a r r 即点ax 1 a y属于超球 所以超球为凸集 6 凸集的性质 i 有限个 可以改成无限 凸集的交集为凸集 即 若Dj j J 是凸集 则它们的交集D x x Dj j J 是凸集 ii 设D是凸集 b是一实数 则下面集合是凸集bD y y bx x D 7 凸集的性质 iii 设D1 D2是凸集 则D1与D2的和集D1 D2 y y x z x D1 z D2 是凸集 注 和集与并集有很大的区别 凸集的并集未必是凸集 而凸集的和集是凸集 例 D1 x 0 T x R 表示x轴上的点 D2 0 y T y R 表示y轴上的点 则D1 D2表示两个轴的所有点 它不是凸集 D1 D2 R2是凸集 8 推论凸集的线性组合是凸集 定义2 1 2设xi Rn i 1 k 实数li 0 则称为x1 x2 xk的凸组合 容易证明 凸集中任意有限个点的凸组合仍然在该凸集中 两点的凸组合 三点的凸组合 多点的凸组合 9 极点 定义2 1 3设D为凸集 x D 若D中不存在两个相异的点y z及某一实数a 0 1 使得x ay 1 a z则称x为D的极点 凸集 极点 凸集 极点 10 极点 例D x Rn x a a 0 则 x a上的点均为极点 证明 设 x a 若存在y z D及a 0 1 使得x ay 1 a z 则a2 x 2 a2 y 2 1 a 2 z 2 2a 1 a y z a2 不等式取等号 必须 y z a 容易证明y z x 根据定义可知 x为极点 11 凸函数 定义2 1 4设函数f x 定义在凸集DRn上 若对任意的x y D 及任意的a 0 1 都有f ax 1 a y af x 1 a f y 则称函数f x 为凸集D上的凸函数 12 凸函数 定义2 1 5设函数f x 定义在凸集DRn上 若对任意的x y D x y 及任意的a 0 1 都有f ax 1 a y af x 1 a f y 则称函数f x 为凸集D上的严格凸函数 将上述定义中的不等式反向 可以得到凹函数和严格凹函数的定义 13 凸函数的例 例2 1 3设f x x 1 2 试证明f x 在 上是严格凸函数 证明 设x y R 且x y a 0 1 都有f ax 1 a y af x 1 a f y ax 1 a y 1 2 a x 1 2 1 a y 1 2 a 1 a x y 2 0 因此f x 在 上是严格凸函数 14 凸函数的几何性质 对一元函数f x 在几何上af x1 1 a f x2 0 a 1 表示连接 x1 f x1 x2 f x2 的线段 f ax1 1 a x2 表示在点ax1 1 a x2处的函数值 所以一元凸函数表示连接函数图形上任意两点的线段总是位于曲线弧的上方 对于一元凸函数f x 可以发现 位于函数曲线上方的图形是凸集 事实上这一结论对于多元函数也是成立的 而且是充要条件 即有下面的定理 15 凸函数的性质 i 设f x 是凸集DRn上的凸函数 实数k 0 则kf x 也是D上的凸函数 ii 设f1 x f2 x 是凸集DRn上的凸函数 实数l m 0 则lf1 x mf2 x 也是D上的凸函数 iii 设f x 是凸集DRn上的凸函数 b为实数 则水平集S f b x x D f x b 是凸集 下面的图形给出了凸函数f x y x4 3x2 y4 y2 xy的等值线 f x y 2 4 6 8 10 12 的图形 可以看出水平集为凸集 16 凸函数的性质 17 凸函数的判断 定理2 1 1设f x 定义在凸集DRn上 x y D 令F t f tx 1 t y t 0 1 则 该定理的几何意义是 凸函数上任意两点之间的部分是一段向下凸的弧线 i f x 是凸集D上的凸函数的充要条件是对任意的x y D 一元函数F t 为 0 1 上的凸函数 ii f x 是凸集D上的严格凸函数的充要条件是对任意的x y D x y 一元函数F t 为 0 1 上的严格凸函数 18 凸函数的判断 19 一阶条件 定理2 1 2 一阶条件 设在凸集DRn上f x 可微 则f x 在D上为凸函数的充要条件是对任意的x y D 都有f y f x f x T y x 定理2 1 3 一阶条件 设在凸集DRn上f x 可微 则f x 在D上为严格凸函数的充要条件是对任意的x y D x y 都有f y f x f x T y x 20 二阶条件 设在开凸集DRn上f x 可微 则 i f x 是D内的凸函数的充要条件为 在D内任一点x处 f x 的Hesse矩阵G x 半正定 其中 ii 若在D内G x 正定 则f x 在D内是严格凸函数 21 凸规划 定义2 1 6设DRn为凸集 则f x 为D上的凸函数 则称规划问题minf x s t x D为凸规划问题 定理2 1 5 i 凸规划的任一局部极小点x是整体极小点 全体极小点组成凸集 ii 若f x 是DRn上的严格凸函数 且凸规划问题minf x s t x D的整体极小点存在 则整体极小点唯一 22 2 2线性规划的标准型与基本概念 23 线性规划的一般形式 min max c1x1 c2x2 cnxns t a11x1 a12x2 a1nxn 或 b1a21x1 a22x2 a2nxn 或 b2 am1x1 am2x2 amnxn 或 bmx1 x2 xn 0 24 线性规划的标准型 minc1x1 c2x2 cnxns t a11x1 a12x2 a1nxn b1a21x1 a22x2 a2nxn b2 am1x1 am2x2 amnxn bmx1 x2 xn 0其中bi 0 在标准形式中目标函数一律改为最大化或最小化 此处我们统一为最小化 约束条件 非负约束条件除外 一律化成等式 且要求其右端项大于等于零 25 矩阵 向量形式的标准型 mincTx LP s t Ax bx 0 其中c c1 c2 cn T x x1 x2 xn T b b1 b2 bm T c 价格向量A 约束矩阵b 右端向量 26 矩阵 向量形式的标准型 记A p1 p2 pn 其中pj a1j a2j amj T 线性规划 LP 又可以表示为 27 线性规划解的情况 满足约束条件的向量x是可行解 全体可行解构成可行域D D F时但目标函数无下界时 称线性规划 LP 无界或无最优解 D F时 称线性规划无可行解 D F时若目标函数有下界 可以证明线性规划 LP 必有最优解 28 可行域为凸集 定理2 2 1线性规划问题mincTx LP s t Ax bx 0的可行域D为凸集 证明任取x y D 则有Ax b x 0 Ay b y 0 对任意的a 0 1 设z ax 1 a y 则z 0 且Az A ax 1 a y aAx 1 a Ay ab 1 a b b因此z DD为凸集 29 一般形式转化为标准型 i 极大 极小maxf x min f x ii 若约束条件是小于等于型 则在该约束条件不等式左边加上一个新变量 称为松弛变量 将不等式改为等式 如 iii 若约束条件是大于等于型 则在该约束条件不等式左边减去一个新变量 称为剩余变量 将不等式改为等式 如 30 一般形式转化为标准型 iv 若某个约束方程右端项 则在约束方程两端乘以 1 不等号改变方向 然后再将不等式化为等式 v 若变量xj无非负约束 则引入非负变量xj 0 xj 0 令xj xj xj 31 例将线性规划miny 2x1 x2 3x3s t x1 x2 x3 7x1 x2 x3 2 3x1 x2 2x3 5x1 x2 0 x3是自由变量化为标准型 解 令x3 x3 x3 得到标准型miny 2x1 x2 3x3 3x3 s t x1 x2 x3 x3 x4 7x1 x2 x3 x3 x5 2 3x1 x2 2x3 2x3 5x1 x2 x3 x3 x4 x5 0 32 例将线性规划maxy 250 x1 350 x2s t 5x1 6x2 2508x1 6x2 30010 x1 20 x2 700 x1 0 x2 0化为标准型 解 令x2 x2 得到标准型min y 250 x1 350 x2 s t 5x1 6x2 x3 2508x1 6x2 x4 300 10 x1 20 x2 700 x1 0 x2 0 x3 0 x4 0 33 基本概念 设约束矩阵A的秩为m 行满秩 且m n 则A中必存在m阶非奇异子阵B 不妨设B p1 p2 pm 称B为线性规划问题 LP 的一个基矩阵 或称为基 基矩阵中的列向量称为基向量 对应的决策变量称为基变量 其余变量称为非基变量 34 基本概念 在约束方程组取定基矩阵B p1 p2 pm 之后 令非基变量均为0 得到的方程组p1x1 p2x2 pmxm b有唯一解 这样得到约束方程组的一个解向量x x1 x2 xm T通过这种方法得到的满足约束方程组的解称为基矩阵B对应的基解 35 基本概念 如果基解又满足非负条件 则称之为基可行解 此时的基B称为可行基 基可行解中非零分量的个数不会超过m 若基可行解中非零分量的个数恰为m 称此基可行解为非退化的基可行解 否则称为退化的基可行解 若一个线性规划的所有基可行解都是非退化的 称此线性规划是非退化的 线性规划 LP 的基解个数不会超过 36 例考虑线性规划min2x1 x2s t x1 x2 x3 5 x1 x2 x4 02x1 2x2 x5 22x1 x2 x3 x4 x5 0 该线性规划有5个变量 3个约束 最多个基解 事实上 该线性规划只有7个基解 p1 p2线性相关 下面列出7个基解及对应的基 p1 p3 p4 11 0 6 11 0 T不可行 p1 p3 p5 0 0 5 0 22 T退化 p1 p4 p5 5 0 0 5 12 T非退化 p2 p3 p4 0 11 6 11 0 T不可行 p2 p3 p5 0 0 5 0 22 T退化 p2 p4 p5 0 5 0 5 12 T非退化 p3 p4 p5 0 0 5 0 22 T退化 37 2 3线性规划的基本定理 38 本节的基本定理要说明要找线性规划的最优解只需在基可行解中选择就可以了 这样将选择的范围控制在有限个 定理2 3 1设x是标准型线性规划 LP 的可行解 x为 LP 的基可行解的充要条件是 x的正分量对应的系数列向量线性无关 39 定理2 3 2设x是标准型线性规划 LP 的可行解 x为 LP 的基可行解的充要条件是 x为可行域D的极点 证明 必要性不妨设x x1 x2 xm 0 0 T是 LP 的基可行解 且x1 x2 xm是基变量 假设有u v D 0 a 1 使得x au 1 a v当m 1 j n时 0 xj auj 1 a vj 因此uj vj 0 所以p1u1 p2u2 pmum p1v1 p2v2 pmvm b从而p1 u1 v1 p2 u2 v2 pm um vm 0由于x是基可行解 所以p1 p2 pm线性无关 uj vj i 1 2 m 从而u v 这说明x为极点 40 充分性设x x1 x2 xk 0 0 T是可行域的极点 其中x1 x2 xk 0 假设x不是基可行解 于是p1 p2 pk线性相关 即有一组不全为0的数a1 a2 ak 使得a1p1 a2p2 akpk 0 2 4 又x D 所以x1p1 x2p2 xkpk b 2 5 用e 0乘 2 4 再与 2 5 相加减得 x1 ea1 p1 x2 ea2 p2 xk eak pk b x1 ea1 p1 x2 ea2 p2 xk eak pk b 41 令u x1 ea1 x2 ea2 xk eak 0 0 Tv x1 ea1 x2 ea2 xk eak 0 0 T则有Au b Av b 当e充分小时 可使u 0 v 0 因此 当e充分小时 u v都是 LP 的可行解 且u v x 1 2u 1 2v 这与x是D的极点相矛盾 因此x是基可行解 推论 线性规划 LP 的可行域D x Ax b x 0 最多具有有限个极点 42 p1 p3 p4 11 0 6 11 0 T不可行 p1 p3 p5 0 0 5 0 22 T退化 p1 p4 p5 5 0 0 5 12 T非退化 p2 p3 p4 0 11 6 11 0 T不可行 p2 p3 p5 0 0 5 0 22 T退化 p2 p4 p5 0 5 0 5 12 T非退化 p3 p4 p5 0 0 5 0 22 T退化 前例中三个退化的基可行解对应着同一个极点 基可行解与极点不是一一对应 43 有可行解 有基可行解 定理2 3 3若线性规划 LP 存在可行解 则它一定存在基可行解 44 有最优解 有最优的基可行解 定理2 3 4若线性规划 LP 存在最优解 则必存在基可行解是最优解 45 单纯形方法的思路 找出一基可行解 极点 若其不是最优 找到一个相邻极点新的目标函数值不大于原目标函数值经过有限次迭代给出最优解或判断无最优解 46 单纯形方法的思路 几何 线性规划min 72x1 64x2s t x1 x2 x3 5012x1 8x2 x4 4903x1 x5 100 x1 x2 x3 x4 x5 0的等价形式为 min 72x1 64x2s t x1 x2 5012x1 8x2 4903x1 100 x1 x2 0 47 O A B C D 梯度方向 x2 0 x1 0 x5 0 x3 0 x4 0 等值线 基可行解O 48 O A B C D x2 0 x1 0 x5 0 x3 0 x4 0 基可行解A 49 O A B C D x2 0 x1 0 x5 0 x3 0 x4 0 基可行解B 50 O A B C D x2 0 x1 0 x5 0 x3 0 x4 0 基可行解C 是最优解 51 单纯形方法的思路 代数 例考察线性规划min 72x1 64x2s t x1 x2 x3 5012x1 8x2 x4 4903x1 x5 100 x1 x2 x3 x4 x5 0以x3 x4 x5为基变量 容易得到基可行解 0 0 50 490 100 T 由于x1的价格系数为负数 增加x1的取值可以使得目标函数值减少 类似的 我们也可以增加x2的取值 使得目标函数值减少 由于 72负得多一些 我们先增加x1 52 单纯形方法的思路 代数 min 72x1 64x2s t x1 x2 x3 5012x1 8x2 x4 4903x1 x5 100 x1 x2 x3 x4 x5 0 x1可以增加多少 x1 50 x1 490 12 x1 100 3 因此x1的最大取值为min 50 490 12 100 3 100 3 此时x5的取值为0 x5 出基 53 单纯形方法的思路 代数 根据3x1 x5 100 我们将原来的线性规划改写如下min 64x2 24x5 2400s t x2 x3 x5 3 50 38x2 x4 4x5 90 x1 x5 3 100 3x1 x2 x3 x4 x5 0此时 基变量为x1 x3 x4 基可行解为 100 3 0 50 3 90 0 T 若x2 其系数为负 的取值增加 可以使得目标函数值减少 x2 50 3 x2 90 8 因此x2的最大取值为min 50 3 90 8 90 8 x4 出基 54 单纯形方法的思路 代数 此时 x4 x5是非基变量 将原规划化为min8x4 8x5 3120s t x3 x4 8 x5 6 65 12x2 x4 8 x5 2 45 4x1 x5 3 100 3x1 x2 x3 x4 x5 0解为 100 3 45 4 65 12 0 0 T x5最大可以取为65 2 对应的 线性规划可以转化为下页的形式 55 单纯形方法的思路 代数 min48x3 2x4 3380s t 6x3 3x4 4 x5 65 2x2 3x3 x4 4 55 2x1 2x3 x4 4 45 2x1 x2 x3 x4 x5 0对应的解为 45 2 55 2 0 0 65 2 T 此时 目标函数中非基变量的系数为正 因此目标函数的取值不能再减少 最优值为 3380 56 单纯形方法的思路 代数 单纯形方法求解线性规划 首先找出一个基可行解 将目标函数写成非基变量的线性组合 再加上一个常数 的形式 如果组合的系数全部非负 则已经找到最优解 如果组合的系数中有负数 从中选取一个变量 进基 来增加取值 可以使得函数值减少 根据约束条件 可以控制增加的范围 在进基变量取最大值时 有一个变量出基 从而得到另一个基可行解 重复上面的过程 可以求得最优解 57 2 4单纯形方法 58 设线性规划R A m x1 x2 xm是基变量 而xm 1 xn是非基变量 并记基矩阵B p1 p2 pm N pm 1 pn A B N 则上述线性规划问题化为 59 进一步可以将线性规划问题转化为以下形式 60 规范式 线性规划与基变量x1 xm对应的规范式 线性规划与基变量xj1 xjm对应的规范式 S j1 jm T 1 2 n S 61 2 4 1基可行解是最优解的判断准则 在规范式 中 令非基变量xj 0 j T 得到一个基解x0 x1 xn T 其中 如果b j 0 j S 则x0是基可行解 62 最优性条件 定理2 4 1设x0是线性规划 LP 对应于基B pj1 pjm 的基可行解 与基变量xj1 xjm对应的规范式中 若x0的全体判别数非负 则x0是 LP 的最优解 63 判断无最优解 定理2 4 2设x0是线性规划 LP 对应于基B p1 pm 的基可行解 与基变量x1 xm对应的规范式中 若存在sk 0 且对所有的i 1 2 m有aik 0 则线性规划 LP 无最优解 64 基可行解的转换 从上面定理可以看出 如果某个判别数为负时 可以构造新的可行解 使得目标函数值减少 1 确定进基变量负的判别数对应的变量都可以作为进基变量 一般的 若sk min sj sj 0 则以xk为进基变量 65 基可行解的转换 2 确定离基变量 采用最小比值准则 设已确定xk为进基变量 根据 min qi b i a ik a ik 0 b l a lk ql 则称第l行为主行 与主行所对应的基变量xl为离基变量 66 单纯形方法 如果线性规划是非退化的 则按照上面的方法 进基 离基 迭代一次后 目标函数值有所下降 经过有限次迭代之后 一定可以得到一个基可行解 使得其所有判别数非负 得到最优解 或者其有一个判别数是负的 但对应列向量的所有分量非正 线性规划无最优解 这种求解线性规划的方法称为单纯形方法 67 2 5单纯形表 68 建立实用单纯形表 以下是初始单纯形表 69 例2 5 1用单纯形法解线性规划minf 2x1 3x2s t x1 x2 6x1 2x2 8x1 4x2 3x1 x2 0 解引入松弛变量将原问题化为标准型minf 2x1 3x2s t x1 x2 x3 6x1 2x2 x4 8x1 x5 4x2 x6 3x1 x2 x3 x4 x5 x6 0 70 显然p3 p4 p5 p6是一组基 标准型线性规划中的系数以及这一组基可用表格的形式给出 minf 2x1 3x2s t x1 x2 x3 6x1 2x2 x4 8x1 x5 4x2 x6 3x1 x2 x3 x4 x5 x6 0 目标函数中的系数 基向量 基变量的价格系数 右端系数 约束等式的系数 cj 2 30000p1p2p3p4p5p6 Bp3p4p5p6 cB0000 b6843 111000120100100010010001 71 第一步的判别数 由于在此例中基变量的价格系数均为0 所以判别数就是价格系数 sj 2 30000 进基变量 s2 3 min sj sj 0 所以x2为进基变量 离基变量的判别标准 qi bi ai2 ai2 0 qi64 3 离基变量 q6 minqi 所以x6为离基变量 3 3 标出主元 72 第二步迭代过程 p3p4p5p2 写出基向量 p6换成p2 归一化 若主元不等于1 则进行行变换 将主元变为1 此处不变 3010001 写出价格系数 000 3 消去 用初等行变换将主元所在列其它元素消为0 p5所在行不变 4100010 p2所在行乘以 1加到p3所在行 310100 1 p2所在行乘以 2加到p4所在行 210010 2 p2所在行乘以3加到判别数所在行 sj 200003 73 第二步迭代过程 p3p4p5p2 3010001 000 3 4100010 310100 1 210010 2 sj 200003 74 sj 200003 进基变量 s1 2 min sj sj 0 所以x1为进基变量 离基变量的判别标准 qi bi ai1 ai1 0 qi324 离基变量 q4 2 minqi x4为离基变量 2 2 标出主元 75 第三步迭代过程 p3p1p5p2 写出基向量 p4换成p1 归一化 若主元不等于1 则进行行变换 将主元变为1 此处不变 3010001 写出价格系数 0 20 3 消去 用初等行变换将主元所在列其它元素消为0 p2所在行不变 2000 112 p1所在行乘以 1加到p3所在行 1001 101 p1所在行乘以 1加到p5所在行 210010 2 p1所在行乘以2加到判别数所在行 sj00020 1 76 第三步迭代过程 p3p1p5p2 3010001 0 20 3 2000 112 1001 101 210010 2 sj00020 1 77 sj00020 1 进基变量 s6 1 min sj sj 0 所以x6为进基变量 离基变量的判别标准 qi bi ai6 ai6 0 qi1 13 离基变量 q5 1 minqi x5为离基变量 此处可选x3 1 1 标出主元 78 第四步迭代过程 p3p1p6p2 写出基向量 p5换成p6 归一化 若主元不等于1 则进行行变换 将主元变为1 此处除以2 2010 0 写出价格系数 0 20 3 消去 用初等行变换将主元所在列其它元素消为0 1000 1 p6所在行乘以 1加到p3所在行 0001 0 p6所在行乘以2加到p1所在行 4100010 p6所在行乘以1加到判别数所在行 sj0003 2 0 p6所在行乘以 1加到p2所在行 79 第四步迭代过程 p3p1p6p2 2010 0 0 20 3 1000 1 0001 0 4100010 sj0003 2 0 80 sj0003 21 20 此时所有的判别数都非负 迭代终止 最优解为x 4 2 0 0 0 1 T 原问题的最优解为x 4 2 T 最优值为f 2 4 3 2 14 81 2 6初始基可行解的求法 82 对于线性规划问题mincTxs t Ax b b 0 x 0 引入松弛变量化为标准型mincTxs t Ax IxS bx xS 0 其中I是单位矩阵 xS xn 1 xn m T 则可以将xS作为基变量 以 0 0 b1 bm T为初始基可行解进行单纯形迭代 对于一般的线性规划问题 无法简单给出初始基可行解 83 为了使初始可行基成为一个单位矩阵 在有些约束条件中需要加入人工变量 但加入人工变量后的数学模型与未加入人工变量的数学模型一般是不等价的 在这一点上 人工变量与松弛变量或剩余变量是不同的 松弛变量或剩余变量只是将不等式改写为等式 而改写前后 两个约束是等价的 84 2 6 1大M单纯形法 对于线性规划问题 引入人工变量xn 1 xn m 构造辅助线性规划问题 85 M是相当大的正数 可以理解为正无穷 对人工变量起到惩罚的作用 逼迫辅助线性规划的最优解中人工变量均为0 上述辅助线性规划模型与原规划模型一般是不等价的 只有当最优解中 人工变量都取零值时 才可认为两个问题的最优解是相当的 关于这一点有以下的结论 1 辅助线性规划问题的最优解中 人工变量都处在非基变量位置 即取零值 则原问题有最优解 且将前者最优解中去掉人工变量部分即为后者最优解 86 2 若辅助线性规划问题的最优解中包含非零的人工变量 则原问题无可行解 3 若辅助线性规划问题的最优解的基变量中包含人工变量 但该人工变量取值为0 这时可将某个非基变量引入基变量中来替换该人工变量 从而得到原问题的最优解 87 大M方法算例 例2 6 1用大M单纯形法求解线性规划minf x 3x1 x2 x3s t x1 2x2 x3 11 4x1 x2 2x3 x4 3 2x1 x3 1x1 x2 x3 x4 0 引入松弛变量x5 人工变量x6 x7 构造辅助线性规划min 3x1 x2 x3 Mx6 Mx7s t x1 2x2 x3 x5 11 4x1 x2 2x3 x4 x6 3 2x1 x3 x7 1x1 x7 0 注 根据线性规划问题本身的形式 可以少引进一些人工变量 88 单纯形方法求解 第一步的判别数 s1 3 1 0 4 M 2 M 6M 3类似地可以给出其它各个判别数 sj6M 3 M 1 3M 1M000 qi113 21 x3进基 x7离基 标出主元 注 人工变量一旦离基 则在迭代时不再参与计算 89 续表 90 91 求得辅助规划问题的最优解为 4 1 9 0 0 0 0 T 原线性规划的最优解为 4 1 9 0 T 最优值为 3 4 1 3 1 9 2 注 根据各个判别数 可以发现M应满足 3M 12 在实际问题中可以取M为适当大的一个数 比如比问题中的系数大一个数量级 92 2 6 2两阶段单纯形法 对于线性规划问题 引入人工变量xn 1 xn m 构造辅助线性规划问题 93 将上述辅助线性规划问题拆成两个线性规划 即为两阶段法 第1阶段求解第1个线性规划 第1个线性规划的目标函数是对所有人工变量之和求最小 1 若求得的最优解中 所有人工变量都处在非基变量的位置 即 则从第1阶段的最优解中去掉人工变量后 即为原问题的一个基本可行解 作为原问题的一个初始基本可行解 再求解原问题 从而进入第2阶段 94 2 假若求得第1阶段的最优解中 至少有一个人工变量不为零值 则说明添加人工变量之前的原问题无可行解 不再需要进入第2阶段 因此两阶段法的第1阶段求解 有两个目的 一为判断原问题有无可行解 二 若有 则可求得原问题的一个初始基本可行解 再对原问题进行第2阶段的计算 95 两阶段法算例 例2 6 2用两阶段法求解线性规划min4x1 x2 x3s t 2x1 x2 2x3 43x1 3x2 x3 3x1 x2 x3 0 解 引入人工变量 构造辅助线性规划 minx4 x5s t 2x1 x2 2x3 x4 43x1 3x2 x3 x5 3x1 x2 x3 x4 x5 0 96 单纯形表 97 单纯形表 最优解 1 2 0 3 20 0 T 最优值w 0 由此得到原线性规划的一个基可行解x0 1 2 0 3 2 T 将上表的最后部分转到新的单纯形表中 求解原线性规划 不过判别数要重新计算 98 求解原线性规划的单纯形表 得到原线性规划的最优解x 0 2 5 9 5 T 最优值f 11 5 99 2 7线性规划的对偶理论 100 假设某工厂有m种设备 B1 B2 Bm 一年内各设备的生产能力 有效台时数 为b1 b2 bm 利用这些设备可以加工n种产品 A1 A2 An 单位产品的利润分别为c1 c2 cn 第j种产品需要在第i种设备上加工的台时数为aij 问在设备能力允许的条件下怎样安排生产计划 使全年总收入最多 设x1 x2 xn为各产品的计划年产量 s为全年总收入 易建立该问题的数学模型 101 假设某工厂有m种设备 B1 B2 Bm 一年内各设备的生产能力 有效台时数 为b1 b2 bm 利用这些设备可以加工n种产品 A1 A2 An 单位产品的利润分别为c1 c2 cn 第j种产品需要在第i种设备上加工的台时数为aij 问在设备能力允许的条件下怎样安排生产计划 使全年总收入最多 设x1 x2 xn为各产品的计划年产量 s为全年总收入 易建立该问题的数学模型 102 对偶问题 假设工厂将所有的设备用于出租 需要给各种设备制定出租价格 定价原则有两条 一是出租后得到的单位利润不得少于直接生产时的收入 二是出租价格尽量的低 以利于市场竞争 设第i种设备Bi的单位台时的出租价格为yi 全年总收入为w 则该问题的数学模型为 103 对偶问题 假设工厂将所有的设备用于出租 需要给各种设备制定出租价格 定价原则有两条 一是出租后得到的单位利润不得少于直接生产时的收入 二是出租价格尽量的低 以利于市场竞争 设第i种设备Bi的单位台时的出租价格为yi 全年总收入为w 则该问题的数学模型为 104 可以看出 原始规划与对偶规划是同一组数据参数 只是位置有所不同 所描述的问题实际上是同一个问题从另一种角度去描述 原始线性规划 对偶线性规划 105 对称形势下对偶问题的一般形式 定义2 7 1满足下列条件的线性规划问题称为具有对称形式 其变量均具有非负约束 其约束条件当目标函数求极大时取 号 当目标函数求极小时均取 号 106 对称形势下对偶问题的一般形式 原始线性规划mincTx LP s t Ax bx 0 对偶线性规划maxbTy DP s t ATy cy 0 107 对合性 定理2 7 1对偶线性规划的对偶问题是原始线性规划问题 108 例写出下面线性规划的对偶规划模型 109 解 按照对称形式的对偶关系 其对偶模型为 110 非对称形式下对偶线性规划 并非所有线性规划问题具有对称形式 故下面讨论一般情况下线性规划问题如何写出其对偶问题 原问题和对偶问题有很多内在联系 它们之间存在着严格的对应关系 目标函数类型之间的对应关系 目标函数系数与右边项的对应关系 约束系数矩阵之间的对应关系 约束类型与变量类型之间的对应关系 111 由于前面三个对应关系与标准形式下的对应关系一致 故我们只需讨论约束类型与变量类型之间的对应关系 112 例写出下列线性规划问题的对偶问题 1 113 答案 114 2 115 答案 116 117 118 对偶规划的性质 考虑如下的线性规划min5x1 3x2 LP s t x1 2x2 x3 24x1 x2 x4 3x1 x2 x3 x4 0 其对偶规划为max2y1 3y2 DP s t y1 4y2 52y1 y2 3 y1 0 y2 0y1 y2无约束 119 对偶规划的性质 LP 的三个基可行解 只写出x1 x2 及对应的目标函数值为 2 0 10 0 3 9 4 7 5 7 5 DP 的四个基可行解 只写出y1 y2 及对应的目标函数值为 0 0 0 3 2 0 3 0 5 4 15 4 1 1 5 可见 LP 在可行解上的取值不小于 DP 在可行解上的取值 若两者取值相等 则对应的解都是最优解 120 弱对偶性定理 标准型线性规划mincTx LP s t Ax bx 0 对偶线性规划maxbTy DP s t ATy c 若x0 y0分别是 LP 与 DP 的可行解 则Ax0 b x0 0 ATy0 c 于是y0Tb y0T Ax0 y0TA x0 ATy0 Tx0 cTx0 定理2 7 4极小化线性规划问题的目标函数值不小于其对偶规划的目标函数值 121 定理2 7 5 最优性 若x0是原始线性规划的可行解 y0是对偶线性规划的可行解 且cTx0 bTy0 则x0与y0分别是原始线性规划问题与对偶线性规划问题的最优解 证明 122 定理2 7 6若原始线性规划问题与对偶线性规划问题之一具有无界的目标函数值 则另一个无可行解 即 若原问题有可行解而其对偶问题无可行解 则原问题目标函数值无界 反之对偶问题有可行解而其原问题无可行解 则对偶问题的目标函数值无界 123 对偶的线性规划问题的解 两个互为对偶的线性规划的解的情况 1 两个都有可行解 2 两个都无可行解 两个都有最优解 最优值相等 一个有最优解 3 一个有可行解 无最优解 目标函数无界 则另一个无可行解 124 互补松弛性 ATy c Tx 0 bTy cTx Ax b 定理2 7 8x y分别是原始线性规划问题与对偶线性规划的可行解 则x y分别是最优解的充要条件为 ATy c Tx 0 125 互补松弛性 原始线性规划minf 2x1 3x2s t x1 x2 x3 6x1 2x2 x4 8x1 x5 4x2 x6 3x1 x2 x3 x4 x5 x6 0 对偶线性规划maxf 6y1 8y2 4y3 3y4s t y1 y2 y3 2y1 2y2 y4 3y1 0y2 0y3 0y4 0 原始规划最优解x 4 2 0 0 0 1 T 对偶规划最优解y 0 3 2 1 2 0 T 对偶规划y 的松弛量q c ATy 0 0 0 3 2 1 2 0 T 互补松弛性 qTx 0 126 2 8对偶单纯形法 127 1 最优解的判别 已知线性规划问题的基矩阵B及它对应的基解 并且此基解的所有判别数非负 若xB B 1b 0则所得的基解为最优解 128 2 确定离基变量 令min B 1b i B 1b i 0 B 1b l 则以xl为离基变量 若xl所在行的所有系数alj 0 j 1 2 n 则线性规划问题无可行解 129 3 确定进基变量 设目标函数的形式为 已确定离基变量为xl 设进基变量为xk 在目标函数中 用xk替换xl 令 则xk为进基变量 130 算例 例2 8 1用对偶单纯形法解线性规划minz 12x1 8x2 16x3 12x4s t 2x1 x2 4x3 22x1 2x2 4x4 3x1 x2 x3 x4 0 minz 12x1 8x2 16x3 12x4s t 2x1 x2 4x3 x5 2 2x1 2x2 4x4 x6 3x1 x2 x3 x4 x5 x6 0 引入松弛变量得到标准型线性规划 131 构造对偶单纯形表 minz 12x1 8x2 16x3 12x4s t 2x1 x2 4x3 x5 2 2x1 2x2 4x4 x6 3x1 x2 x3 x4 x5 x6 0 sj128161200 选取离基变量b6 3 min bj bj 0 3 选取进基变量 s4 a64 max sj a6j a6j 0 3 主元 132 3 41 21 2010 1 4 6216003 2 2 1 4010 2 3 2 4 2 133 4 4 12 4 基解已可行 最优解为x 0 3 2 1 8 0 T 最优值为z 14 134 2 9灵敏度分析 135 灵敏度分析 在线性规划中 已经求得了最优解 若系数cj bi aij等发生变化的时候 最优解是否发生变化 怎样变化 这一类问题称为灵敏度分析 通常 我们进行灵敏度分析时 都假设只有一个系数发生变化 136 灵敏度分析 设已经用单纯形法求得线性规划mincTx LP s t Ax bx 0的最优解xB B 1b 基矩阵B p1 p2 pm 称为最优基 最优值z cBTxB cBTB 1b 137 非基变量价格系数的变化 若xr是非基变量 其价格系数cr的变化不影响解的可行性 由于sk ck cBTB 1pk cr的变化只影响xr的判别数 不影响其它变量的判别数 设cr的变化量为Dcr sr cr Dcr cBTB 1pr sr Dcr 因此 若sr Dcr 0 即Dcr sr最优解 最优值都不变 138 基变量价格系数的变化 若xr是基变量 其价格系数cr的变化不影响解的可行性 由于sk ck cBTB 1pk cr变化时 cB发生变化 所有的非基变量的判别数都发生变化 设cr的变化量为Dcr cB cB DcB其中DcB 0 0 Dcr 0 0 Tsj cj cB TB 1pj cj cBTB 1pj DcBTB 1pj sj Dcrarj 139 基变量价格系数的变化 sj sj Dcrarj在所有的判别数仍然非负时 最优解不变 根据上面的式子 可以得到max sj arj arj0 在满足上述条件的情况下 最优值由原来的z 变为z Dcrxr 实际讨论时 只要写出新的判别数 然后解不等式即可求得价格系数的变化范围 140 右端项的变化 右端项变化 原来的最优解不再可行 原始线性规划 对偶线性规划 判别数不变 对偶解的可行性不变 右端项的变化 价格系数的变化 最优基B不变 对偶解y cBTB 1 T的最优性不变 按照基重新写出的基解的可行性不变 判别数的非负性不变 什么条件下成立 141 B仍然是最优基 xB B 1 b Db B 1b B 1Db xB B 1Db B 1 bij m m Db 0 0 Dbr 0 0 TxB xB Dbr b1r b2r bmr T xB i xB i Dbrbir i 1 2 m 当xB 0 即 xB i Dbrbir 0时 最优基B不变 即max xB i bir bir 0 Dbr min xB i bir bir 0 142 影子价格 对偶最优解的经济解释 当线性规划原问题求得最优解xj j 1 2 n 时 其对偶问题也得到最优解yi i 1 m 代入各自的目标函数后有 其中 bi代表第i种资源的拥有量 对偶变量yi 的意义代表在资源最优利用条件下对单位资源i的估价 这种估计不是资源的市场价格 而是根据在生产中做出的贡献而作的估价 为区别一般意义的价格 我们将其 yi 称为影子价格 shadowprice 143 影子价格的几点说明 1 资源的市场价格是已知数 相对比较稳定 而它的影子价格则有赖于资源的利用情况 是未知数 因企业生产任务 产品结构等情况发生变化 资源的影子价格也随之改变 2 影子价格是一种边际价格 在上式中对Z求bi的偏导数得 这说明yi 的值相当于在资源得到最优利用的生产条件下 bi每增加一个单位时目标函数Z的增量 144 影子价格的几点说明 3 资源的影子价格实际上又是一种机会成本 在纯市场经济条件下 当某一资源的市场价格低于该影子价格时 可以买进这种资源 相反 当市场价格高于影子价格时 就会卖出这种资源 随着资源的买进卖出 它的影子价格也将随之发生变化 一直到影子价格与市场价格保持同等水平时 才处于平衡状态 145 影子价格的几点说明 4 根据互补松弛定理 生产过程中如果某资源bi未得到充分利用 则该种资源的影子价格为零 又当某资源的影子价格不为零时 表明该种资源已消耗完毕 146 影子价格的几点说明 5 一般说来 对线性规划问题的求解是确定资源的最优分配方案 而对于对偶问题的求解则是确定对资源的恰当估价 这种估计直接涉及资源的最有效利用 例如 在一个大公司内部 可借助资源的影子价格确定一些内部结算价格 以便控制有限资源的使用和考核下属企业经营的好坏 又如 在社会上可对一些最紧缺的资源 借助影子价格规定使用这种单位资源时必须上交的利润额 以控制一些经济效益低的企业自觉地节约使用紧缺资源 使有限资源发挥更大的经济效益 147 2 10整数线性规划 148 整数线性规划 如果线性规划的全部或部分变量要求取为整数 就称为整数线性规划 有时简称为整数规划 所有的变量都要求是整数时 称为纯整数线性规划 部分变量要求取整数时 称为混合型整数线性规划 求解的简单思路 先不考虑整数要求 求解一般的线性规划 若求得的最优解不满足整数要求时 用 舍入取整 的方法处理 该方法有时会带来很大的误差 甚至得到的解不可行 149 2 10 1割平面法 考虑整数规划min x1 x2s t 2x1 x2 64x1 5x2 20 x1 x2 0且为整数如果不考虑整数约束 其可行域见下图 最优解为 5 3 8 3 T 150 5 3 8 3 151 割平面法 如果考虑整数约束 那么可行域是 LP 可行域内的13个整点 我们考虑的方法之一是首先将 LP 的最优点附近的一块区域 挖掉 再求解 挖掉的区域内不含任何整点 152 5 3 8 3 153 解 LP 最终单纯形表为 考虑x2对应的方程 由单纯形表得到 由于x2 x3 2为整数 可得 化为等式约束 x3 x4 x5 2 154 割平面法 考虑到x3 6 2x1 x2 x4 20 4x1 5x2 根据2 3 x3 3 x4 3 0可以得到x1 x2 4可以看出