Duality
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 Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z=\textstyle \sum_{j=1}^n \displaystyle c_j x_j}
subject to:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \sum_{j=1}^n \displaystyle a_{i,j} x_j\lneq b_j \qquad (i=1, 2, ... ,m) }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_j\gneq 0 \qquad (j=1, 2, ... ,n) }
Dual
Minimize Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle v=\textstyle \sum_{i=1}^m \displaystyle b_i y_i}
subject to:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \textstyle \sum_{i=1}^m \displaystyle a_{i,j} y_i\lneq c_j \qquad (j=1, 2, ... , n) }
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle y_i\gneq 0 \qquad (i=1, 2, ... , m)}
Constructing a Dual:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{matrix} \max(c^Tx) \\ \ s.t. Ax\leq b \\ x \geq 0 \end{matrix}} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \quad \longrightarrow \quad} Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \begin{matrix} \\ \min(b^Ty) \\ \ s.t. A^Tx\geq c \\ y \geq 0 \end{matrix}}
Numerical Example
Construct the Dual for the following maximization problem:
maximize Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle z=6x_1+14x_2+13x_3}
subject to:
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle \tfrac{1}{2}x_1+2x_2+x_3\leq 24}
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle x_1+2x_2+4x_3\leq 60}
For the problem above, form augmented matrix A. The first two rows represent constraints one and two respectively. The last row represents the objective function.
Failed to parse (SVG (MathML can be enabled via browser plugin): Invalid response ("Math extension cannot connect to Restbase.") from server "https://wikimedia.org/api/rest_v1/":): {\displaystyle A =\begin{bmatrix} \tfrac{1}{2} & 2 & 1 & 24 \\ 1 & 2 & 4 & 60 \\ 6 & 14 & 13 & 1 \end{bmatrix}}
Note that the original maximization problem had three variables and two constraints.