Difference between revisions of "Duality"

From Cornell University Computational Optimization Open Textbook - Optimization Wiki
Jump to navigation Jump to search
Line 18: Line 18:
 
<math>x_j\gneq 0 \qquad (j=1, 2, ... ,n)  </math> </blockquote>
 
<math>x_j\gneq 0 \qquad (j=1, 2, ... ,n)  </math> </blockquote>
 
'''Dual'''<blockquote>
 
'''Dual'''<blockquote>
Minimize <math>v=\textstyle \sum_{i=1}^m \displaystyle b_i y_i</math></blockquote><blockquote>subject to:  <math>\textstyle \sum_{i=1}^m \displaystyle a_{i,j} y_i\lneq c_j \qquad (j=1, 2, ... , n)  </math></blockquote><math>y_i\gneq 0 \qquad (i=1, 2, ... , m)  </math>  
+
Minimize <math>v=\textstyle \sum_{i=1}^m \displaystyle b_i y_i</math></blockquote><blockquote>subject to:  <math>\textstyle \sum_{i=1}^m \displaystyle a_{i,j} y_i\lneq c_j \qquad (j=1, 2, ... , n)  </math>
 +
 
 +
<math>y_i\gneq 0 \qquad (i=1, 2, ... , m)  </math></blockquote>
 
== Numerical Example ==
 
== Numerical Example ==
  

Revision as of 19:27, 7 November 2020

Author: Claire Gauthier, Trent Melsheimer, Alexa Piper, Nicholas Chung, Michael Kulbacki (SysEn 6800 Fall 2020)

Steward: TA's name, Fengqi You

Introduction

Every linear programming optimization problem may be viewed either from the primal or the dual, this is the principal of duality. Duality develops the relationships between one linear programming problem and another related linear programming problem. For example in economics, if the primal optimization problem deals with production and consumption levels, then the dual of that problem relates to the prices of goods and services. The dual variables in this example can be referred to as shadow prices.

The shadow price of a constraint ...

Theory, methodology, and/or algorithmic discussions

Definition:

Primal

Maximize


subject to:

Dual

Minimize

subject to:

Numerical Example

Applications

Conclusion

References

  1. https://ocw.mit.edu/courses/sloan-school-of-management/15-084j-nonlinear-programming-spring-2004/lecture-notes/lec18_duality_thy.pdf
  2. http://web.mit.edu/15.053/www/AMP-Chapter-04.pdf