参数线性规划课件.ppt

1、 第六节第六节 参数线性规划参数线性规划目标函数的系数含有参数目标函数的系数含有参数 的线性规划问题的线性规划问题约束条件右端的常数项含有约束条件右端的常数项含有参数的线性规划问题参数的线性规划问题参数线性规划概念参数线性规划概念 当参数当参数 或或 沿某一方向连沿某一方向连续变动时，目标函数值续变动时，目标函数值z将随将随 或或 的变动而呈线性变动，的变动而呈线性变动，z是这个是这个变动参数的线性函数，因而称为参变动参数的线性函数，因而称为参数线性规划。数线性规划。jcibjcib模型模型目标函数的系数含有参数的线性规划模型目标函数的系数含有参数的线性规划模型约束条件右端的常数项含有参数的约

2、束条件右端的常数项含有参数的LP模型模型0)()(maxXbAXXCCz0)(maxXbbAXCXzCC：价值向量：变动向量：参数 ：资源向量 ：变动向量 ：参数 bb参数线性规划问题的分析步骤：参数线性规划问题的分析步骤：（1）令）令 求解得最终单纯形表；求解得最终单纯形表；（2）将）将 或或 项反映到最终单纯形表中去；项反映到最终单纯形表中去；（3）随）随 值的增大或减小，观察原问题或对偶值的增大或减小，观察原问题或对偶 问题。问题。（4）重复第（）重复第（3）步，一直到）步，一直到 值继续增大或减小值继续增大或减小 时，表中的解（基）不再出现变化时为止。时，表中的解（基）不再出现变化时为

3、止。确定现有解（基）允许的确定现有解（基）允许的 的变动范围；的变动范围；当当 的变动超出这个范围时，用单纯的变动超出这个范围时，用单纯形法或对偶单纯形法求新的解。形法或对偶单纯形法求新的解。0Cb举例分析举例分析 分析分析 值变化时，下述参数线性规划值变化时，下述参数线性规划问题最优解的变化。问题最优解的变化。0,52426155)21()2()(max212121221xxxxxxxxxz 先令先令 求得最优求得最优 解，然后解，然后将将 反映在最终单纯形表中，见下表：反映在最终单纯形表中，见下表：0C25214140002/34/10102/3212/14/10012/722/154/5

4、1002/15000021221354321xxxxxxxxbXCBBjcjjzc 最优解保持不变的条件213217151z25214140002/34/10102/3212/14/10012/722/154/51002/15000021221354321xxxxxxxxbXCBBjcjjzc 当当 时时1检验数检验数非负非负20515100005/110321105/10122615/4006000021221454321xxxxxxxxbXCBBjcjjzc 当当 时，换基得：时，换基得：187,1z当 时，由原最终单纯形表5/125214140002/34/10102/3212/14/1

5、0012/722/154/51002/15000021221354321xxxxxxxxbXCBBjcjjzc 检验数检验数非负非负0613103531016/103/201006/103/11420015015000021251354321xxxxxxxxbXCBBjcjjzc 48512z当 时，最终单纯形表5/10613103531016/103/201006/103/11420015015000021251354321xxxxxxxxbXCBBjcjjzc 48512z当 时，原最终单纯形表2检验数检验数非负非负0613103531016/103/201006/103/11420015

6、015000021251354321xxxxxxxxbXCBBjcjjzc 0002121001150010262400015015000021254354321xxxxxxxxbXCBBjjzc02z当 时，最终单纯形表2目标函数值目标函数值 随随 值变化的情况值变化的情况)(z-2-1/5-1127.21523举例分析举例分析 分析分析 值变化时，下述参数线性规划值变化时，下述参数线性规划问题最优解的变化。问题最优解的变化。0,524261552)(max212121221xxxxxxxxxz2/14/10002/34/1010412312/14/1001412722/154/510045

7、21500001221354321xxxxxxxxbXCBBjcjjzc 先令先令 求得最优求得最优 解，然后解，然后将将 反映在最终单纯形表中，见下表：反映在最终单纯形表中，见下表：0C最优基不变条件是 最优值为 4121766z0,62x则若当当 时时2001061040601001152001501500001241354321xxxxxxxxbXCBBjcjjzc 610,6z2/14/10002/34/1010412312/14/1001412722/154/51004521500001221354321xxxxxxxxbXCBBjcjjzc 先令先令 求得最优求得最优 解，然后解，

8、然后将将 反映在最终单纯形表中，见下表：反映在最终单纯形表中，见下表：0b最优基不变条件是 最优值为 4121766z064x则，若03/115/100005/1103106/115/101613216/115/20061100001221554321xxxxxxxxbXCBBjcjjzc 当当 时时6 当 时最优值为 319618z02/100102/10132112102/510152545012/100221700001223554321xxxxxxxxbXCBBjcjjzc 当当 时时18 当 时最优值 当 时，所在元素均为正，故原问题无可行解 242x2112 z1824参数线性规划参数线性规划