最优化-lec4 Complementary Slackness 最优化理论与方法课件（英文版－南京大学）.pptVIP

* Definition – Subnetwork (定义 - 子网) Is this a subnetwork? Is this a subnetwork? * Definition – Path/Cycle(定义 - 路径/周期) A path of 1-3-2-4-5 A cycle of 1-2-5-3-1 * Definition – Tree/Spanning Tree(定义 - 树/生成树) A tree is a connected subnetwork containing no cycles. A spanning tree is a tree including every node in the network. * Properties of Tree/Spanning Tree(树属性/生成树) 1. Every tree consisting of at least two nodes has at least one end node. An end node is a node that is incident to exactly one arc. 2. A spanning tree for a network with m nodes contains exactly m-1 arcs. 3. If a spanning tree is augmented by adding to it an additional arc of the network, then exactly one cycle is formed. 4. Every connected network contains a spanning tree. * Properties of Tree/Spanning Tree The Property 5 implies that * Representation of the Basis * Complementary Slackness or 互补松弛性 * Complementary Slackness * Complementary Slackness Q. For example ?? In fact, the complementary slackness holds in the general form. In general, a complementary slackness condition holds a) between any variable in the primal and its corresponding constraint in the dual, and b) between any constraint in the primal and its corresponding variable in the dual. Remark: * The Dual Simplex Method dual simplex method primal simplex method * The Dual Simplex Method Steps of the dual simplex method * The Dual Simplex Method Steps of the dual simplex method Remark: 2) We can still apply the full tableau or the revised tableau to realize the dual simplex method. The format of the full tableau or the revise tableau is the same as that to realize the primal simplex method. * The Dual Simplex Method(对偶单纯形法) Example (Dual Simplex Method) This basis is optimal and feasible, so we stop. Primal solution? Dual solution? * Sensitivity Analysis The purpose of sensitivity analysis is to determine how the optimal solution of a linear program depends on the changes of the parameters. The developer of the model might wish to