Duality - Revision history

SYSEN5800TAs: /* References */

2024-12-04T20:21:48Z

References

← Older revision		Revision as of 16:21, 4 December 2024
Line 197:		Line 197:

	== References ==		== References ==
	~~[[New Topics in Fall 2024]]~~

SYSEN5800TAs at 20:20, 4 December 2024

2024-12-04T20:20:57Z

← Older revision		Revision as of 16:20, 4 December 2024
Line 197:		Line 197:

	== References ==		== References ==
			[[New Topics in Fall 2024]]

Asa273: /* Duality Interpretation */ Fixed typos

2021-09-04T14:44:25Z

Duality Interpretation: Fixed typos

← Older revision		Revision as of 10:44, 4 September 2021
Line 110:		Line 110:
	'''subject to:'''		'''subject to:'''

	<math>12x_1+2x_2+~~3x_3~~\leq 50</math>		<math>12x_1+2x_2+4x_3\leq 50</math>

	<math>80x_1+40x_2+20x_3\leq 460</math>		<math>80x_1+40x_2+20x_3\leq 460</math>
Line 129:		Line 129:
	<math>2y_1+40y_2+3y_3\geq 25</math>		<math>2y_1+40y_2+3y_3\geq 25</math>

	<math>~~3y_1~~+20y_2+1y_3\geq 21</math>		<math>4y_1+20y_2+1y_3\geq 21</math>

	<math>y_1,y_2,y_3\geq 0</math>		<math>y_1,y_2,y_3\geq 0</math>

Wc593 at 11:27, 21 December 2020

2020-12-21T11:27:37Z

← Older revision		Revision as of 07:27, 21 December 2020
Line 1:		Line 1:
	Author: Claire Gauthier, Trent Melsheimer, Alexa Piper, Nicholas Chung, Michael Kulbacki (SysEn 6800 Fall 2020)		Author: Claire Gauthier, Trent Melsheimer, Alexa Piper, Nicholas Chung, Michael Kulbacki (SysEn 6800 Fall 2020)

	~~Steward: TA's name, Fengqi You~~

	== Introduction ==		== Introduction ==

Wc593: /* Constructing a Dual: */

2020-12-21T09:58:42Z

Constructing a Dual:

← Older revision		Revision as of 05:58, 21 December 2020
Line 10:		Line 10:
	== Theory, methodology, and/or algorithmic discussions ==		== Theory, methodology, and/or algorithmic discussions ==

	=== Definition: ===		=== Definition ===

	'''Primal'''<blockquote>Maximize <math>z=\textstyle \sum_{j=1}^n \displaystyle c_j x_j</math> </blockquote><blockquote>subject to:		'''Primal'''<blockquote>Maximize <math>z=\textstyle \sum_{j=1}^n \displaystyle c_j x_j</math> </blockquote><blockquote>subject to:
Line 22:		Line 22:
	subject to:<blockquote><math>\textstyle \sum_{i=1}^m \displaystyle y_ia_{i,j}\gneq c_j \qquad (j=1, 2, ... , n) </math></blockquote><blockquote><math>y_j\gneq 0 \qquad (i=1, 2, ... , m)</math></blockquote></blockquote>Between the primal and the dual, the variables <math>c</math> and <math>b</math> switch places with each other. The coefficient (<math>c_j</math>) of the primal becomes the right-hand side (RHS) of the dual. The RHS of the primal (<math>b_j</math>) becomes the coefficient of the dual. The less than or equal to constraints in the primal become greater than or equal to in the dual problem. <ref name=":1"> Ferguson, Thomas S. ''A Concise Introduction to Linear Programming.'' University of California Los Angeles. https://www.math.ucla.edu/~tom/LP.pdf </ref>		subject to:<blockquote><math>\textstyle \sum_{i=1}^m \displaystyle y_ia_{i,j}\gneq c_j \qquad (j=1, 2, ... , n) </math></blockquote><blockquote><math>y_j\gneq 0 \qquad (i=1, 2, ... , m)</math></blockquote></blockquote>Between the primal and the dual, the variables <math>c</math> and <math>b</math> switch places with each other. The coefficient (<math>c_j</math>) of the primal becomes the right-hand side (RHS) of the dual. The RHS of the primal (<math>b_j</math>) becomes the coefficient of the dual. The less than or equal to constraints in the primal become greater than or equal to in the dual problem. <ref name=":1"> Ferguson, Thomas S. ''A Concise Introduction to Linear Programming.'' University of California Los Angeles. https://www.math.ucla.edu/~tom/LP.pdf </ref>

	=== Constructing a Dual: ===		=== Constructing a Dual ===
	<math>\begin{matrix} \max(c^Tx) \\ \ s.t. Ax\leq b \\ x \geq 0 \end{matrix}</math> <math> \quad \longrightarrow \quad</math><math>\begin{matrix} \min(b^Ty) \\ \ s.t. A^Tx\geq c \\ y \geq 0 \end{matrix}</math>		<math>\begin{matrix} \max(c^Tx) \\ \ s.t. Ax\leq b \\ x \geq 0 \end{matrix}</math> <math> \quad \longrightarrow \quad</math><math>\begin{matrix} \min(b^Ty) \\ \ s.t. A^Tx\geq c \\ y \geq 0 \end{matrix}</math>

	=== Duality Properties: ===		=== Duality Properties ===
	The following duality properties hold if the primal problem is a maximization problem as considered above. This especially holds for weak duality.		The following duality properties hold if the primal problem is a maximization problem as considered above. This especially holds for weak duality.

Line 69:		Line 69:
	* Solving a Linear Programming problem by the Simplex Method gives you a solution of its dual as a by-product. This simplex algorithm tries to reduce the infeasibility of the dual problem. The dual simplex method can be thought of as a disguised simplex method working on the dual. The dual simplex method is when we maintain dual feasibility by imposing the condition that the objective function includes every variable with a nonpositive coefficient, and terminating when the primal feasibility conditions are satisfied. <ref name=":3"> Chvatal, Vasek. (1977). ''The Dual Simplex Method.'' W.H. Freeman and Co. http://cgm.cs.mcgill.ca/~avis/courses/567/notes/ch10.pdf </ref>		* Solving a Linear Programming problem by the Simplex Method gives you a solution of its dual as a by-product. This simplex algorithm tries to reduce the infeasibility of the dual problem. The dual simplex method can be thought of as a disguised simplex method working on the dual. The dual simplex method is when we maintain dual feasibility by imposing the condition that the objective function includes every variable with a nonpositive coefficient, and terminating when the primal feasibility conditions are satisfied. <ref name=":3"> Chvatal, Vasek. (1977). ''The Dual Simplex Method.'' W.H. Freeman and Co. http://cgm.cs.mcgill.ca/~avis/courses/567/notes/ch10.pdf </ref>

	=== Duality Interpretation: ===		=== Duality Interpretation ===

	* Duality can be leveraged in a multitude of interpretations. The following example includes an economic optimization problem that leverages duality:		* Duality can be leveraged in a multitude of interpretations. The following example includes an economic optimization problem that leverages duality:

	'''Economic Interpretation Example:'''		'''Economic Interpretation Example'''

	* A rancher is preparing for a flea market sale in which he intends to sell three types of clothing that are all comprised of wool from his sheep: peacoats, hats, and scarves. With locals socializing the high quality of his clothing, the rancher plans to sell out of all of his products each time he opens up a store at the flea market. The following shows the rancher's materials, time, and profits received for his peacoats, hats, and scarves, respectively.		* A rancher is preparing for a flea market sale in which he intends to sell three types of clothing that are all comprised of wool from his sheep: peacoats, hats, and scarves. With locals socializing the high quality of his clothing, the rancher plans to sell out of all of his products each time he opens up a store at the flea market. The following shows the rancher's materials, time, and profits received for his peacoats, hats, and scarves, respectively.

LockheedELDP: Added interpretation section.

2020-12-12T18:30:35Z

Added interpretation section.

← Older revision		Revision as of 14:30, 12 December 2020
Line 100:		Line 100:
	\|20		\|20
	\|1		\|1
	\|20		\|21
	\|}		\|}
	* With limited materials and time for an upcoming flea market event in which the rancher will once again sell his products, the rancher needs to determine how he can make best use of his time and materials to ultimately maximize his profits. The rancher is running lower than usual on wool supply; he only has 50 square feet of wool sheets to be made for his clothing this week. Furthermore, the rancher only has 460 inches of sewing materials left. Lastly, with the rancher ~~only~~ has ~~$115~~ to ~~spare on~~ clothing ~~production costs~~.		* With limited materials and time for an upcoming flea market event in which the rancher will once again sell his products, the rancher needs to determine how he can make best use of his time and materials to ultimately maximize his profits. The rancher is running lower than usual on wool supply; he only has 50 square feet of wool sheets to be made for his clothing this week. Furthermore, the rancher only has 460 inches of sewing materials left. Lastly, with the rancher has a limited time of 25 hours to produce his clothing line.
	*		*
	*		*
	* he rancher ~~is able to make~~ the following linear program:		* With the above information the rancher creates the following linear program:


	<math>~~175x1~~ + ~~25x2~~ + ~~20x3~~</math>		'''maximize''' <math>z=175x_1+25x_2+21x_3</math>

			'''subject to:'''

			<math>12x_1+2x_2+3x_3\leq 50</math>

			<math>80x_1+40x_2+20x_3\leq 460</math>

			<math>7x_1+3x_2+1x_3\leq 25</math>

			<math>x_1,x_2,x_3\geq 0</math>

			* Before the rancher finds the optimal number of peacoats, hats, and scarves to produce, a local clothing store owner approaches him and asks if she can purchase his labor and materials for her store. Unsure of what is a fair purchase price to ask for these services, the clothing store owner decides to create a dual of the original primal:


			'''minimize''' <math>v=50y_1+460y_2+25y_3</math>

			'''subject to:'''

			<math>12y_1+80y_2+7y_3\geq 175</math>

			<math>2y_1+40y_2+3y_3\geq 25</math>

			<math>3y_1+20y_2+1y_3\geq 21</math>

			<math>y_1,y_2,y_3\geq 0</math>

			* By leveraging the above dual, the clothing store owner is able to determine the asking price for the rancher's materials and labor. In the dual, the clothing store owner's objective is now to minimize the asking price, where <math>y_1</math> represents the the amount of wool, <math>y_2</math> represents the amount of sewing material, and <math>y_3</math> represents the rancher's labor.
	*		*

LockheedELDP at 17:52, 12 December 2020

2020-12-12T17:52:03Z

@@ Line 75: / Line 75: @@
 '''Economic Interpretation Example:'''
-* A rancher is preparing for a flea market sale in which he intends to sell three types of clothing that are all comprised of wool from his sheep: peacoats, hats, and scarves. With locals socializing the high quality of his clothing, the rancher always sells all of these products each time he opens up a store at the flea market. With limited materials and time for an upcoming flea market event in which the rancher will once again sell his products, the rancher needs to determine how he can make best use of his time, production costs, and materials to ultimately maximize his profits. Since its a busy week at the ranch, the rancher expects to only be able to spend a maximum of 25 hours on producing his clothing line for the upcoming flea market sale. Furthermore, the rancher is running lower than usual on wool supply; he only has 100 square feet of wool sheets to be made for his clothing this week. Lastly, with the rancher being risk adverse in nature, he refuses to spend more than ....
+* A rancher is preparing for a flea market sale in which he intends to sell three types of clothing that are all comprised of wool from his sheep: peacoats, hats, and scarves. With locals socializing the high quality of his clothing, the rancher plans to sell out of all of his products each time he opens up a store at the flea market. The following shows the rancher's materials, time, and profits received for his peacoats, hats, and scarves, respectively.
+*

LockheedELDP at 04:59, 12 December 2020

2020-12-12T04:59:31Z

← Older revision		Revision as of 00:59, 12 December 2020
Line 47:		Line 47:

	Essentially, as you choose values of x or y that come closer to the optimal solution, the value of z for the primal, and v for the dual will converge towards the optimal solution. On a number line, the value of z which is being maximized will approach from the left side of the optimum value while the value of v which is being minimized will approach from the right-hand side.		Essentially, as you choose values of x or y that come closer to the optimal solution, the value of z for the primal, and v for the dual will converge towards the optimal solution. On a number line, the value of z which is being maximized will approach from the left side of the optimum value while the value of v which is being minimized will approach from the right-hand side.
	[[File:Duality numberline .png\|thumb\| '''Figure 1: Graphical Representation of Duality''']]		[[File:Duality numberline .png\|thumb\| '''Figure 1: Graphical Representation of Duality''']]

	* If the primal is unbounded, then the dual is infeasible		* If the primal is unbounded, then the dual is infeasible
Line 75:		Line 75:
	'''Economic Interpretation Example:'''		'''Economic Interpretation Example:'''

	* A rancher is preparing for a flea market sale in which he intends to sell three ~~pieces~~ of clothing that are comprised of wool from his sheep: peacoats, hats, and scarves. With locals socializing the high quality of his clothing, the rancher always sells all of these products each time he opens up a store at the flea market. With limited materials and time for an upcoming flea market event in which the rancher will once again sell his products, the rancher needs to determine how he can make best use of his time, production costs, and materials to ultimately maximize his profits. Since its a busy week at the ranch, the rancher expects to only be able to spend a maximum of 25 hours on producing his clothing line for the upcoming flea market sale. Furthermore, the rancher is running lower than usual on wool supply; ~~his current~~		* A rancher is preparing for a flea market sale in which he intends to sell three types of clothing that are all comprised of wool from his sheep: peacoats, hats, and scarves. With locals socializing the high quality of his clothing, the rancher always sells all of these products each time he opens up a store at the flea market. With limited materials and time for an upcoming flea market event in which the rancher will once again sell his products, the rancher needs to determine how he can make best use of his time, production costs, and materials to ultimately maximize his profits. Since its a busy week at the ranch, the rancher expects to only be able to spend a maximum of 25 hours on producing his clothing line for the upcoming flea market sale. Furthermore, the rancher is running lower than usual on wool supply; he only has 100 square feet of wool sheets to be made for his clothing this week. Lastly, with the rancher being risk adverse in nature, he refuses to spend more than ....
	*
	* ultimate objective is to ~~make as much profit from~~ his ~~sales at~~ the ~~flea market~~. ~~His peacoats sell~~

	* Solving a Linear Programming problem by the Simplex Method gives you a solution of its dual as a by-product. This simplex algorithm tries to reduce the infeasibility of the dual problem. The dual simplex method can be thought of as a disguised simplex method working on the dual. The dual simplex method is when we maintain dual feasibility by imposing the condition that the objective function includes every variable with a nonpositive coefficient, and terminating when the primal feasibility conditions are satisfied. <ref name=":3" />		*

	== Numerical Example ==		== Numerical Example ==

LockheedELDP at 04:55, 12 December 2020

2020-12-12T04:55:38Z

← Older revision		Revision as of 00:55, 12 December 2020
Line 70:		Line 70:

	=== Duality Interpretation: ===		=== Duality Interpretation: ===
	Duality can be leveraged in a multitude of interpretations. ~~In this~~
			* Duality can be leveraged in a multitude of interpretations. The following example includes an economic optimization problem that leverages duality:

			'''Economic Interpretation Example:'''

			* A rancher is preparing for a flea market sale in which he intends to sell three pieces of clothing that are comprised of wool from his sheep: peacoats, hats, and scarves. With locals socializing the high quality of his clothing, the rancher always sells all of these products each time he opens up a store at the flea market. With limited materials and time for an upcoming flea market event in which the rancher will once again sell his products, the rancher needs to determine how he can make best use of his time, production costs, and materials to ultimately maximize his profits. Since its a busy week at the ranch, the rancher expects to only be able to spend a maximum of 25 hours on producing his clothing line for the upcoming flea market sale. Furthermore, the rancher is running lower than usual on wool supply; his current
			*
			* ultimate objective is to make as much profit from his sales at the flea market. His peacoats sell

	* Solving a Linear Programming problem by the Simplex Method gives you a solution of its dual as a by-product. This simplex algorithm tries to reduce the infeasibility of the dual problem. The dual simplex method can be thought of as a disguised simplex method working on the dual. The dual simplex method is when we maintain dual feasibility by imposing the condition that the objective function includes every variable with a nonpositive coefficient, and terminating when the primal feasibility conditions are satisfied. <ref name=":3" />		* Solving a Linear Programming problem by the Simplex Method gives you a solution of its dual as a by-product. This simplex algorithm tries to reduce the infeasibility of the dual problem. The dual simplex method can be thought of as a disguised simplex method working on the dual. The dual simplex method is when we maintain dual feasibility by imposing the condition that the objective function includes every variable with a nonpositive coefficient, and terminating when the primal feasibility conditions are satisfied. <ref name=":3" />

LockheedELDP: Added Figure Name

2020-12-12T04:43:06Z

Added Figure Name

← Older revision		Revision as of 00:43, 12 December 2020
Line 47:		Line 47:

	Essentially, as you choose values of x or y that come closer to the optimal solution, the value of z for the primal, and v for the dual will converge towards the optimal solution. On a number line, the value of z which is being maximized will approach from the left side of the optimum value while the value of v which is being minimized will approach from the right-hand side.		Essentially, as you choose values of x or y that come closer to the optimal solution, the value of z for the primal, and v for the dual will converge towards the optimal solution. On a number line, the value of z which is being maximized will approach from the left side of the optimum value while the value of v which is being minimized will approach from the right-hand side.
	[[File:Duality numberline .png\|thumb]]		[[File:Duality numberline .png\|thumb\| '''Figure 1: Graphical Representation of Duality''']]

	* If the primal is unbounded, then the dual is infeasible		* If the primal is unbounded, then the dual is infeasible
Line 67:		Line 67:
	'''Dual Simplex Method'''		'''Dual Simplex Method'''

	* Solving a Linear Programming problem by the Simplex Method gives you a solution of its dual as a by-product. This simplex algorithm tries to reduce the infeasibility of the dual problem. The dual simplex method can be thought of as a disguised simplex method working on the dual. The dual simplex method is when we maintain dual feasibility by imposing the condition that the objective function includes every variable with a nonpositive coefficient, and terminating when the primal feasibility conditions are satisfied. <ref> Chvatal, Vasek. (1977). ''The Dual Simplex Method.'' W.H. Freeman and Co. http://cgm.cs.mcgill.ca/~avis/courses/567/notes/ch10.pdf </ref>		* Solving a Linear Programming problem by the Simplex Method gives you a solution of its dual as a by-product. This simplex algorithm tries to reduce the infeasibility of the dual problem. The dual simplex method can be thought of as a disguised simplex method working on the dual. The dual simplex method is when we maintain dual feasibility by imposing the condition that the objective function includes every variable with a nonpositive coefficient, and terminating when the primal feasibility conditions are satisfied. <ref name=":3"> Chvatal, Vasek. (1977). ''The Dual Simplex Method.'' W.H. Freeman and Co. http://cgm.cs.mcgill.ca/~avis/courses/567/notes/ch10.pdf </ref>

			=== Duality Interpretation: ===
			Duality can be leveraged in a multitude of interpretations. In this

			* Solving a Linear Programming problem by the Simplex Method gives you a solution of its dual as a by-product. This simplex algorithm tries to reduce the infeasibility of the dual problem. The dual simplex method can be thought of as a disguised simplex method working on the dual. The dual simplex method is when we maintain dual feasibility by imposing the condition that the objective function includes every variable with a nonpositive coefficient, and terminating when the primal feasibility conditions are satisfied. <ref name=":3" />

	== Numerical Example ==		== Numerical Example ==