Graduate
  1. Real Analysis  1.1. Set Theory and Logic  1.1.1. Sets and Operations  1.1.2. Relations and Functions  1.1.3. Logic and Quantifiers  1.1.4. Cardinality of Sets  1.2. Metric Spaces  1.2.1. Open and Closed Sets  1.2.2. Convergence of Sequences  1.2.3. Continuous Functions in Metric Spaces  1.2.4. Compactness and Completeness in Metric Spaces in Real Analysis  1.3. Sequence and Series  1.3.1. Convergence of Sequences  1.3.2. Infinite Series  1.3.3. Uniform Convergence  1.3.4. Power Series  1.4. Differentiation  1.4.1. Mean Value Theorems  1.4.2. Taylor Series  1.4.3. Functions of Several Variables  1.4.4. Partial Derivatives  1.5. Integration  1.5.1. Riemann and Lebesgue Integration  1.5.2. Improper Integrals  1.5.3. Measure Theory  1.5.4. Fubini’s Theorem  1.6. Functional Analysis  1.6.1. Banach Spaces  1.6.2. Hilbert Spaces  1.6.3. Operators on Spaces  1.6.4. Spectral Theory
  2. Abstract Algebra  2.1. Groups  2.1.1. Definitions and Examples in Groups in Abstract Algebra  2.1.2. Group Homomorphisms  2.1.3. Normal Subgroups  2.1.4. Sylow Theorems  2.2. Rings and Fields  2.2.1. Ideals and Factor Rings  2.2.2. Field Extensions  2.2.3. Galois Theory  2.2.4. Polynomial Rings  2.3. Modules  2.3.1. Module Homomorphisms  2.3.2. Free Modules  2.3.3. Tensor Products  2.3.4. Exact Sequences  2.4. Linear Algebra  2.4.1. Vector Spaces  2.4.2. Eigenvalues and Eigenvectors  2.4.3. Inner Product Spaces  2.4.4. Diagonalization
  3. Topology  3.1. General Topology  3.1.1. Open and Closed Sets  3.1.2. Compactness and Connectedness  3.1.3. Continuous Maps  3.1.4. Separation Axioms  3.2. Algebraic Topology  3.2.1. Fundamental Groups  3.2.2. Homotopy and Homology  3.2.3. Simplicial Complexes  3.2.4. Exact Sequences in Homology  3.3. Differential Topology  3.3.1. Manifolds  3.3.2. Smooth Functions  3.3.3. Tangent and Cotangent Spaces  3.3.4. Vector Bundles
  4. Differential Equations  4.1. Ordinary Differential Equations  4.1.1. First-Order Equations  4.1.2. Second-Order Linear Equations  4.1.3. Systems of Differential Equations  4.1.4. Stability Analysis  4.2. Partial Differential Equations  4.2.1. Classification of PDEs  4.2.2. Fourier Series  4.2.3. Green's Functions  4.2.4. Method of Characteristics  4.3. Dynamical Systems  4.3.1. Stability Theory  4.3.2. Limit Cycles  4.3.3. Chaos Theory  4.3.4. Bifurcation Theory
  5. Probability and Statistics  5.1. Probability Theory  5.1.1. Random Variables  5.1.2. Probability Distributions  5.1.3. Law of Large Numbers  5.1.4. Central Limit Theorem  5.2. Statistical Inference  5.2.1. Hypothesis Testing  5.2.2. Confidence Intervals  5.2.3. Bayesian Methods  5.2.4. Maximum Likelihood Estimation  5.3. Stochastic Processes  5.3.1. Markov Chains  5.3.2. Brownian Motion  5.3.3. Poisson Processes  5.3.4. Martingales
  6. Numerical Analysis  6.1. Numerical Solutions of Equations  6.1.1. Root Finding  6.1.2. Iterative Methods  6.1.3. Convergence Analysis  6.1.4. Error Bounds in Numerical Solutions of Equations  6.2. Numerical Linear Algebra  6.2.1. Matrix Factorizations  6.2.2. Eigenvalue Computations  6.2.3. Sparse Matrices  6.2.4. Preconditioning Techniques  6.3. Numerical Integration and Differentiation  6.3.1. Quadrature Methods  6.3.2. Finite Differences  6.3.3. Error Analysis in Numerical Integration and Differentiation  6.3.4. Adaptive Methods
  7. Complex Analysis  7.1. Complex Numbers  7.1.1. Polar Form  7.1.2. Complex Conjugates  7.1.3. Exponential Form  7.1.4. Roots of Unity  7.2. Analytic Functions  7.2.1. Cauchy-Riemann Equations  7.2.2. Power Series  7.2.3. Conformal Mappings  7.2.4. Harmonic Functions  7.3. Integration in the Complex Plane  7.3.1. Cauchy’s Theorem  7.3.2. Residue Theorem  7.3.3. Contour Integration  7.3.4. Integral Transforms
  8. Mathematical Logic and Foundations  8.1. Propositional Logic  8.1.1. Truth Tables  8.1.2. Logical Equivalences  8.1.3. Proof Techniques in Propositional Logic  8.1.4. Resolution  8.2. Predicate Logic  8.2.1. Quantifiers in Predicate Logic  8.2.2. Formal Systems in Predicate Logic  8.2.3. Completeness and Soundness  8.2.4. Model Theory  8.3. Set Theory  8.3.1. Cardinality and Ordinality  8.3.2. Axiomatic Systems  8.3.3. Zermelo-Fraenkel Set Theory  8.3.4. Forcing
  9. Optimization  9.1. Linear Programming  9.1.1. Simplex Method  9.1.2. Duality in Linear Programming  9.1.3. Sensitivity Analysis  9.1.4. Interior Point Methods  9.2. Nonlinear Programming  9.2.1. Gradient Descent  9.2.2. Lagrange Multipliers  9.2.3. Convex Optimization  9.2.4. Quadratic Programming  9.3. Combinatorial Optimization  9.3.1. Graph Algorithms  9.3.2. Integer Programming  9.3.3. Network Flows  9.3.4. Approximation Algorithms
  10. Discrete Mathematics  10.1. Graph Theory  10.1.1. Graph Representations  10.1.2. Planarity and Coloring  10.1.3. Shortest Path Algorithms  10.1.4. Network Flows  10.2. Combinatorics  10.2.1. Permutations and Combinations  10.2.2. Generating Functions  10.2.3. Recurrence Relations  10.2.4. Inclusion-Exclusion Principle  10.3. Cryptography  10.3.1. Number Theory Applications in Cryptography  10.3.2. Symmetric and Asymmetric Cryptography  10.3.3. RSA and Elliptic Curve Cryptography  10.3.4. Post-Quantum Cryptography

Graduate → Optimization → Linear Programming ↓


Duality in Linear Programming


Linear programming (LP) is a method for achieving the best results in mathematical models whose requirements are represented by linear relationships. It is a technique used for optimization, where you aim to minimize or maximize a linear objective function subject to a set of linear constraints. An essential aspect of linear programming is the concept of duality, which provides deep insight into the behavior of optimization functions.

Fundamentals of dualism

In linear programming, for every optimization problem, there is a corresponding dual problem. If the original problem is called the 'primal problem', its counterpart is known as the 'dual problem'. Duality provides a powerful insight - the optimal solution to one problem can be found by examining the solution to the other.

There are two main results regarding duality in linear programming:

  • Weak duality: The value of the objective function of the duality at any feasible solution is always greater than or equal to the value of the objective function of the original at any feasible solution.
  • Strong duality: If both a primitive and a duality have optimal solutions, then the optimal value of the objective function of the primitive is equal to that of the duality.

Primal and duality problem

Primary problem

Maximize: c 1 x 1 + c 2 x 2 + ... + c n x n
Subject: a 11 x 1 + a 12 x 2 + ... + a 1n x n ≤ b 1
             a 21 x 1 + a 22 x 2 + ... + a 2n x n ≤ b 2
             ,
             a m1 x 1 + a m2 x 2 + ... + a mn x n ≤ b m

             x 1 , x 2 , ..., x n ≥ 0

Double problem

Minimize: b 1 y 1 + b 2 y 2 + ... + b m y m
Subject: a 11 y 1 + a 21 y 2 + ... + a m1 y m ≥ c 1
             a 12 y 1 + a 22 y 2 + ... + a m2 y m ≥ c 2
             ,
             a 1n y 1 + a 2n y 2 + ... + a mn y m ≥ c n

             y 1 , y 2 , ..., y m ≥ 0

Interpretation and economic meaning

In the primary problem, the objective is to determine the maximum benefit (or profit) that can be obtained while satisfying the constraints imposed by resource limitations. Each decision variable represents a possible activity or strategy, and the constraints represent the limits on the resources required for these activities.

The duality problem, on the other hand, seeks the minimum cost necessary to meet or exceed a desired level of total profit. Here, the decision variables can be interpreted as shadow prices - the price of minimising each constraint in the primary optimisation problem. Duality provides a type of equilibrium price system.

Geometrical interpretation

Consider a two-dimensional space for easier visualization. For both primal and dual problems, the solutions lie at the vertices (corners) of their feasible regions. The corresponding primal and dual inequalities define geometric regions, and their intersection can potentially hold the optimal solution for both primal and dual problems.


    
    
    
    
    X
    Y
    Obstacle 1
    Obstacle 2

The principle of complementary lethargy

An integral component connecting the primal and dual formulations is the concept of complementary looseness. It consists of the conditions that must hold if both the primal and its dual have optimal solutions. For each pair of primal and dual constraints, the complementary looseness conditions must be met:

If x j > 0, then the j th duality conditions are strict;
If the binary constraint i is relaxed, then the ith fundamental variable is zero.

Thus, if any constraint in the original problem is relaxed, then the corresponding variable in the duality must have zero value at optimality, and vice versa.

Example of dualism

Sample elementary problem

Maximize z = 2x 1 + 3x 2
subject to
             x 1 + 2x 2 ≤ 10
             2x 1 + x 2 ≤ 8
             x 1 , x 2 ≥ 0

Compatible dual problem

Minimize w = 10y 1 + 8y 2
subject to
             y 1 + 2y 2 ≥ 2
             2y 1 + y 2 ≥ 3
             y 1 , y 2 ≥ 0

Applications and significance

The concept of duality is not just theoretical, but also has important practical implications. It allows us to derive the solution to one problem from the solution of another, potentially simpler problem. Duality is used in a variety of fields such as economics, engineering, military science, and transportation.

For example, in economics, the dual problem gives information about price optimization and resource allocation. Dual solutions indicate what value should be placed on additional resources, providing valuable pricing information to decision makers.

Conclusion

Duality in linear programming bridges the gap between different optimization approaches, allowing for deeper understanding and efficiency in solving complex problems. Whether for academic interest or for practical solutions, it is important to understand the concept of duality to make the most of linear programming techniques.


Graduate → 9.1.2


U
username
0%
completed in Graduate

← Prev (9.1.1)
Simplex Method
Next (9.1.3) →
Sensitivity Analysis

Comments 



Duality in Linear Programming

https://www.buddymath.com/g/9.1.2?bmal=en