线性规划问题的最优解

宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 1 线性规划问题的最优解线性规划问题的最优解 引言引言 线性规划是运筹学的一个基本分支 其应用极其广泛 其作用以为越来越多的 人所重视 线性规划主要就实际问题抽象成数学形式 即求一组变量的值 在满足一 定的约束条件下 是某个目标达到最小或最大 而这些约束条件用可以用一组线性不 等式或线性方程来表示 而求得目标函数的最优解尤为重要 本文就线性规划问题的 最优解求解方法作出阐述 并举出实例加以强化 同时也指出了线性规划问题应用于 生产与运作管理的重要性 1 1 线性规划问题的最优解探讨线性规划问题的最优解探讨 1 1 线性规划问题的提出 考虑下面的线性规划问题的标准型 目标函数 1 CXZ min 约束条件 2 0X bAX 其中 阶矩阵 21n cccC T n xxxX 21 T m bbbb 21 nmij aA 设 B 是 A 中 m 个线性无关的列向量构成的一个基 阶矩阵 这样将矩 mmij aB 阵 A 分成两个部分 即 A X C 为基 B 对应的非 NB NB XX NB CC B X B C 基变量和系数 为 N 对应的非基变量和系数 这样将线性规划问题改写为 N X N X minZ 3 NB CC B B X X 约束条件 宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 2 4 0 NB N B XX b X X NB 经过矩阵变换 得出关于基 B 的标准型如下 N 5 1 min BCZ BN C 1 BCB N X 约束条件 6 0 11 NB NB XX bBNXBX T m bbbbB 2 1 1 mnmmmm nmm nmm aaa aaa aaa NB 21 22212 12111 1 将 5 6 展开为 7 Zmin 1 i m i ib c n mj1 1 ij m i ij acc j x 约束条件 8 i n mj j ij i bxax 1 mi 2 1 9 0 j xnj 2 1 令 称为检验数 1 0i m i ib cZ j 1 ij m i ij acc nmmj 2 1 j 1 2 最优解判别准则 准则一 若 为对应于基 B 的基本可行解 且对于一 T mbbbX 0 0 2 1 1 切的 0 则 X 为线性规划问题的最优解 nmmj 2 1 j 宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 3 证明 0 由 式可知 对任意一组可行解 j 7 T n xxxX 21 均有 但 能使等式成立 即 故 为线性 n j jjx cZ 1 0 ZZ 1 X 0 ZZ 1 X 规划问题的最优解 准则二 当 有某一个 设 j 0 nmmj 2 1 0 j 1 mj 则该线性规划问题有第二个最优的基本可行解 mi 2 1 01 ima 证明 构造一个行解 得 2 X 8 1 1 m imi i xabxmi 2 1 1m x0 0 j xnmj 2 根据 原则 0 min1 1 1 im im i mi a a b 1 Lm L a b 1m x 1 Lm L a b 0 L x 将 带入原目标函数 4 得 2 X 1 i m Lii ib cZ 1 m c1 1 im m i ia c1 Lm La c 1 Lm L a b 由于 故 1m 1 m c01 1 im m i ia c Z 1 i m Lii ib c L Lb c L m i ib c 1 0 Z 也是最优的基本可行解 2 X 推论 若 和 均为最优的基本可行解 1 X 2 X 2 1 1 XXX 10 均为最优可行解 准则三 当 0 有某一个 对一切 j nmmj 2 1 0 j 则该线性规划有无穷多个最优解 mi 2 1 宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 4 证明 构造一个新解 由 3 X 8 1 1 m imi i xabxmi 2 1 1m x 0 0 j xnmj 2 由于 故 01 ima0 0 i xmi 2 1 将代入原目标函数 4 得 1 X Z 1 i m Lii ib c 1 m c1 1 im m i ia c 由于 1m 1 m c01 1 im m i ia c 故 0 Z 1 i m Lii ib c 1 i m i ib c 当 时 仍为可行解 得到无穷多可行解 而目标函数仍为 3 X 即也是最优解 Z 1 i m i ib c 0 Z 3 X 以下举出一些实例 进一步说明线性规划最优解的具体求解方法 2 2 线性规划最优解的问题举例线性规划最优解的问题举例 2 1 图解法求解线性规划问题 例 求解下面的线性规划问题 5 1 1 6 2 1 0 20342 0574 0232 85max 6543 6542 6541 6 jx xxxx xxxx xxxx xZ j 宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 5 显然 是该线性规划问题 1 的一个最优解 T xxxX 621 T 0 0 0 20 0 0 因 及 05 4 cc 3 2 1 0 min4 4 4 ia a b i i i 0 14 1 a b 3 2 1 0 min55 5 ia a b i i 0 25 2 a b 可考虑如下线性规划问题 2 5 4 2 1 0 074 032 max 542 541 54 jx xxx xxx xxW j 易解得线性规划问题 2 的最优解为 T xxxxX 5421 T 0 0 0 0 0 XW 于是可得 是该线性规划问题 1 的唯一最优解 T xxxX 621 T 0 0 0 20 0 0 例 求解下面的线性规划问题 7 2 1 6 1456 2456 3456 max5 20 442225 230 0 1 2 6 j Zx xxxx xxxx xxxx xj 显然 是该线性规划问题 1 的一个最优解 T xxxX 621 T 0 0 0 0 20 0 因 及 05 4 cc 3 2 1 0 min4 4 4 ia a b i i i 0 14 1 a b 3 2 1 0 min55 5 ia a b i i 0 25 2 a b 可考虑如下线性规划问题 宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 6 2 5 4 3 1 0 02 02 max 543 541 54 jx xxx xxx xxW j 易解得线性规划问题 2 有无界解 是该问题的一个 T xxxxX 5431 T 1 2 3 0 可行解 于是线性规划问题的最优解不唯一 只要取03 XW 如下 T xxxX 621 13 2 45 6 0 3 25 4 242 1 0 2 0 xxs xs xs xs x 那么 也是线性规划问题的最优解 例如 分别取 s 0 5 0 25 时 则 X 和以及都是该线性规划问题 T 0 5 0 1 5 1 0 0 T 0 25 0 5 0 75 0 5 12 0 X T 0 0 0 0 25 0 1 的最优解 其中 是一退化的基可行解 是一非退 T 0 0 0 0 25 0 T 0 5 0 1 5 1 0 0 化的基可行解 而是一 T 0 25 0 5 0 75 0 5 12 0 1 0 0 1 5 1 0 5 00 25 0 0 0 0 2 TT 可行解而不是基解 例 要将两种大小不同的钢板结成 A B C 三种规格 每张钢板可同时截得三种规格 4 3 的小钢板的块数乳下表所示 钢板类型 规格类型 A 规格 B 规格 C 规格 第一种钢板 2 1 1 第二种钢板 1 2 3 今需 A B C 三种规格的成品分别为 15 18 27 块 问 各截取这两种钢板多 宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 7 少张可得所需三种规格成品 且使得所用钢板张数最少 解 需要截得第一种钢板 X 张 第二种钢板 Y 张 则 0 0 273 182 152 y x yx yx yx 作出可行区域图如下 目标函数为 经yxz 过可行区域内的整点且与 原点最近的直线是 它上面的整点12 yx 有 0 12 1 11 2 10 3 9 4 8 5 7 6 6 7 5 8 4 9 3 10 2 11 1 12 0 若逐一 讨论其是否在可行域内比 较麻烦时 只需先判断点 A 附近的整数点是否满足条件 若满足条件 则再试附近的整数点 若不满 5 39 5 18 足条件 则不需要再判断下去 故此题 我们只需先判断 A 点附近的整数点 3 9 4 8 分别代入 式 易得它们都满足条件 故我们还需判断 2 10 5 7 两点 代入 式发现它们 都不满足条件 则其余点不需要再判断 所以该题的最优解为 3 9 4 8 例 约束条件为 3 412 max52Sxx 宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 8 1 12 12 12 4 3 5210 0 x xx xx x x 利用图解法求解如下 此例中约束条件中存在和目标函数的系数成比例的约束条件 但是由于此约束条件在 可行域的形成中没有发挥作用 所以此问题没有多个最优解 图解法是求解含有两个变量的线性规划问题的一种很直观和有效的方法 所以在作 出问题的可行域时 则可根据这个必要条件 若可行域中没有与目标函数平行的边界 线时 则可直接判断出此问题一定没有 多个最优解 2 2 单纯型法求解线性规划问 题 例 求解问题 1 5 5 4 3 2 1 0 2 13 22 2min 532 432 321 32 jx xxx xxx xxxts xxZ j 解 这里是一个单位矩阵 且 故基 B 是可行基 541 AAAB 0 2 1 2 T b 为基变量 为非基变量 基 B 对应的基本可行解为 其 541 xxx 32 x x T x 2 1 0 0 2 目标函数值 方程组已是典式 得到第一张单纯性表如下 0 0 ZbAx 1 x 2 x 3 x 4 x 5 x RHS 宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 9 01 2000 1 x 1 21002 4 x 0 1 3101 5 x 01 1012 注意 第 0 行的元素应是将目标函数化成等价的方程 32 2xxZ 后的相应元素 02 32 xxZ 检验数 故当前解不是最优解 列中有两个元素均为正数 取 01 2 2 A 3222 a a 1 1 2 1 1 min min 32 3 22 2 a b a b 故转轴元为 为进基变量 为出基变量 进行旋转变换后得下表 22 a 2 x 4 x 1 x 2 x 3 x 4 x 5 x RHS 001 10 1 1 x 10 5204 2 x 01 3101 5 x 00 2 111 它对应的基本可行解为 其目标函数值为 但 仍不 T x 1 0 0 1 4 1 0 Z01 3 是最优解 此时为转轴元 进行旋转变换后得下表 33 a 1 x 2 x 3 x 4 x 5 x RHS 000 2 1 2 1 2 3 1 x 100 2 1 2 5 2 13 宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 10 2 x 010 2 1 2 3 2 5 3 x 001 2 1 2 1 2 1 它对应的基本可行解为 其目标函数值为 此时检验数向 T x 0 0 2 1 2 5 2 13 2 3 0 Z 量 故为最优解 0 例 接下面的 LP 问题 1 6 0 24 13 min 321 321 321 321 xxx xxx xxxts xxxZ 解 引进非负的剩余变量 将不等式约束化为等式约束0 4 x0 5 x 0 24 13 54321 5321 4321 xxxxx xxxx xxxx 若用原始单纯形法求解 需再引进两个非负的人工变量 然后利用两阶段法求解 由本例所具有的特点 我们只要将等式两端同乘以 1 就直接得到原问题的一 个基本 不可行 解和对偶问题的一个可行解 检验数向量 其对应的单纯0 形表如下 1 x 2 x 3 x 4 x 5 x RHS Z 1 1 1000 4 x 3 1 110 1 5 x 1 4 111 2 直接利用对偶单纯形法求解 所以为离基变量 由以下比值决12 12 bb 5 x 定进基变量 4 1 1 1 4 1 min 22 2 a 宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 11 因而为进基变量 以为转轴元 进行旋转变换后得下表 2 x 22 a 1 x 2 x 3 x 4 x 5 x RHS 4 5 0 4 3 0 4 1 2 1 4 x 4 13 0 4 3 1 4 1 2 1 2 x 4 1 1 4 1 0 4 1 2 1 显然为离基变量 计算 4 x 13 5 4 1 4 1 4 3 4 3 4 13 4 5 min 11 1 a 确定为进基变量 以为转轴元 进行旋转变换后得下表 1 x 11 a 1 x 2 x 3 x 4 x 5 x RHS 00 13 6 13 5 13 2 13 9 1 x 10 13 3 13 4 13 1 13 2 2 x 01 13 4 13 1 13 3 13 7 此时 故原问题的最优解为 其最优解为 0 b T x 0 0 0 13 7 13 2 13 9 由以上例题可见 在某些情况下使用对偶单纯形法比用原始单纯形法更具优越性 宿州学院 2011 届本科生毕业论文 线性规划问题的最优解 12 参考文献参考文献 1 胡运权等 运筹学基础及应用 M 第五版 北京 高等教育出版社 2008 06 2 管梅谷 郑汉鼎 线性规划 M