[管理学]运筹学对偶规划.ppt

第二节 * * * * * * * * * * * * * * * * * * * * * * 3、无界性 定理：在互为对偶的两个问题中，若一个问题具有无界解，则另一个问题无可行解。 推论1：在互为对偶的两个问题中，若一个问题无可行解，则另一个问题或具有无界解或无可行解。 推论2：在互为对偶的两个问题中，若一个问题有可行解，另一个问题无可行解，则可行的问题无界。 无界解 无可行解 无可行解 无界解 对偶问题 原问题 例1、利用对偶理论证明问题无界（无最优解） 解： 设对偶变量为 max s.t. min s.t. 则对偶问题为 由 知， 第一个约束 可知对偶问题无 条件不成立， 可行解。 易知(0, 0, 0)T 是原问题的一 个可行解，故原问题可行。 由无界性定理可知，原问题 有无界解，即无最优解。 对偶问题 不可行 原问题无界 或不可行 无界 不可行 练习、证明下列线性规划问题无最优解 min s.t. max s.t. 对偶问题 原问题的一个可行解： …… 对偶问题不可行：找矛盾 4、最优性 定理：设 和 分别是原问题（P）和其对偶问题（D）的可行解，且有 则 和 分别是原问题（P）和其对偶问题（D）的最优解。 设 和 分别是P和D的最优解： 因此 5、互补松弛性 定理：设 和 分别是原问题和其对偶问题的最优解， 若对偶变量 ，则原问题相应的约束条件 若约束条件 ，则相应的对偶变量 5、互补松弛性 定理：设 和 分别是原问题和其对偶问题的最优解， 若对偶变量 ，则原问题相应的约束条件 若约束条件 ，则相应的对偶变量 定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。 5、互补松弛性 定理：设 和 分别是原问题和其对偶问题的最优解， 若对偶变量 ，则原问题相应的约束条件 若约束条件 ，则相应的对偶变量 若 ，则 若 ，则 若 ，则 若 ，则 例2、利用互补松弛定理求最优解 max s.t. 已知原问题的最优解是 求对偶问题的最优解。 解： 设对偶变量为 min s.t. 则对偶问题为 设对偶问题的最优解为 因 由互补松弛性知 解方程组得 故对偶问题的最优解为 例3、利用互补松弛定理求最优解 已知原问题的最优解是 max s.t. 求对偶问题的最优解。 对偶变量为 min s.t. 则对偶问题为 设对偶问题的最优解为 将 代入原问题约束条件得 解： 由互补松弛性知 又 故对偶问题的最优解为 得 例4、利用互补松弛定理求最优解 已知其对偶问题的最优解是 min s.t. 求原问题的最优解。 对偶问题为 设原问题的最优解为 解： min s.t. 将 代入原问题约束条件得： (2)、(3)、(4)为严格不等式 由互补松弛性知 又因 由互补松弛性知 得 故原问题最优解为 6、强对偶性（对偶定理） 定理：若原问题有最优解，则其对偶问题也一定具有最优解，且目标函数的最优值相等。 s.t. 用单纯形法求原问题的最优解： s.t. 非基变量 基变量 Xs X I A 0 C 基变量 基变量 基可 系数 行解 0 Xs b XB XN B N CB CN XB I 0 CB CN B N XB XN 单纯形法计算的矩阵描述 非基变量 基变量 Xs I 0 基变量 基变量 基可 系数 行解 0 Xs b 基变量 非基变量 XB 基变量 基变量 基可 系数 行解 CN－CBB-1N B-1N B-1 XN Xs B-1b CB 进行初等 行变换 －CBB-1 若CN－CBB-1N ≤0 －CBB-1 ≤0 最优解X*= B-1b B-1存在 6、强对偶性（对偶定理） min w =bTY s.t. ATY ≥CT Y ≥ 0 若CN－CBB-1N ≤0 －CBB-1 ≤0