Difference between revisions of "Linear programming"

From Optimization for Chemical Engineering: 4G3
Jump to navigation Jump to search
 
(39 intermediate revisions by the same user not shown)
Line 1: Line 1:
__NOTOC__
__NOTOC__
{{ClassSidebar
{{ClassSidebarYouTube
| date = 07 January 2015
| date = 07 January to 04 February 2015
| dates_alt_text =  
| dates_alt_text =  
| vimeoID1 = 116180574
| vimeoID1 = c5d5Sqh5enE
| vimeoID2 =
| vimeoID2 = E-GlTTLzbSc
| vimeoID3 =
| vimeoID3 = jUq6QTTAPJc
| vimeoID4 =
| vimeoID4 = t_U015J0iqQ
| vimeoID5 =
| vimeoID5 = ZDr5iu9LzuE
| vimeoID6 =
| vimeoID6 = EUC4dRqZhXw
| vimeoID7 =
| vimeoID7 = hpuAPO3BTew
| vimeoID8 =
| vimeoID8 = loWOX4zCpZ0
| vimeoID9 =
| vimeoID9 =
| vimeoID10 =
| vimeoID10 =
Line 19: Line 19:
| assignment_instructions =  
| assignment_instructions =  
| assignment_solutions =  
| assignment_solutions =  
| video_download_link_MP4 = https://www.dropbox.com/s/7ha86cwn8hk0508/2015-4G3-Class-01B.mp4?dl=0
| video_download_link_MP4 = http://learnche.mcmaster.ca/media/2015-4G3-Class-01B.mp4
| video_download_link_MP4_size = 610 M
| video_download_link_MP4_size = 610 M
| video_notes1 =
| video_notes1 =
| video_download_link2_MP4 =  
| video_download_link2_MP4 = http://learnche.mcmaster.ca/media/2015-4G3-Class-02A.mp4
| video_download_link2_MP4_size = 566 M
| video_download_link2_MP4_size = 812 M
| video_notes2 =
| video_notes2 =
| video_download_link3_MP4 =  
| video_download_link3_MP4 = http://learnche.mcmaster.ca/media/2015-4G3-Class-02B.mp4
| video_download_link3_MP4_size = 521 M
| video_download_link3_MP4_size = 840 M
| video_notes3 =
| video_notes3 =
| video_download_link4_MP4 =  
| video_download_link4_MP4 = http://learnche.mcmaster.ca/media/2015-4G3-Class-03A.mp4
| video_download_link4_MP4_size = 504 M
| video_download_link4_MP4_size = 820 M
| video_notes4 =
| video_notes4 =
| video_download_link5_MP4 =  
| video_download_link5_MP4 = http://learnche.mcmaster.ca/media/2015-4G3-Class-03B.mp4
| video_download_link5_MP4_size = 610 M
| video_download_link5_MP4_size = 807 M
| video_notes5 =
| video_notes5 =
| video_download_link6_MP4 =  
| video_download_link6_MP4 = http://learnche.mcmaster.ca/media/2015-4G3-Class-04A.mp4
| video_download_link6_MP4_size = 542 M
| video_download_link6_MP4_size = 819 M
| video_notes6 =
| video_notes6 =
| video_download_link7_MP4 =  
| video_download_link7_MP4 = http://learnche.mcmaster.ca/media/2015-4G3-Class-04B.mp4
| video_download_link7_MP4_size = 549 M
| video_download_link7_MP4_size = 817 M
| video_notes7 =
| video_notes7 =
| video_download_link8_MP4 =
| video_download_link8_MP4 = http://learnche.mcmaster.ca/media/2015-4G3-Class-04B-wrap-up.mp4
| video_download_link8_MP4_size =  540 M
| video_download_link8_MP4_size =  459 M
| video_notes8 =
| video_notes8 =
| video_download_link9_MP4 =  
| video_download_link9_MP4 =  
Line 56: Line 56:
| video_notes12 =}}
| video_notes12 =}}


<!-- http://learnche.mcmaster.ca/media/2015-4G3-Class-01B.mp4 -->
<!--
== References ==
== References ==


Please use these references to read ahead, or for extra background reading on membranes.
Dr. Marlin has made a [[Media:4G3-Linear-Programming-Notes-Thomas-Marlin.pdf |great, short e-book on Linear Programming]]. You will find reading his notes very rewarding, and a great supplement to the class lectures.
 
* Ghosh, R. "Principles of Bioseparations Engineering", Chapter 11, [http://catalogue.mcmaster.ca/catalogue/Record/1405538 McMaster] (reserve)
* Geankoplis, C.J. "Transport Processes and Separation Process Principles", Chapter 13 in 3rd and 4th edition, [http://catalogue.mcmaster.ca/catalogue/Record/1219775 McMaster Libraries] (reserve)
* Seader, Henley and Roper, "Separation Process Principles", Chapter 14 in 2nd and 3rd edition [http://catalogue.mcmaster.ca/catalogue/Record/1270236 McMaster Libraries] (reserve)
* Richardson and Harker, "Chemical Engineering, Volume 2", 5th edition, Chapter 8 [http://books.google.ca/books/about/Coulson_and_Richardson_s_Chemical_Engine.html?id=ottGCe1CDUoC ebook]
* Perry's Chemical Engineers' Handbook, Chapter 20.4, [http://accessengineeringlibrary.com/browse/perrys-chemical-engineers-handbook-eighth-edition/p200139d899720_36001 Direct link] (McMaster subscription)
* Schweitzer, "Handbook of Separation Techniques for Chemical Engineers", Chapter 2.1, [http://catalogue.mcmaster.ca/catalogue/Record/1156427 McMaster library]
* Wankat, "Separation Process Engineering", 2nd edition, chapter 16 [http://catalogue.mcmaster.ca/catalogue/Record/1444655 McMaster library]
-->


== Resources ==
== Resources ==
Line 80: Line 69:
! Topic
! Topic
! Slides/handouts for class
! Slides/handouts for class
! Video file
! References and Notes
! References and Notes
|-
|-
Line 90: Line 78:
* Introductory linear programming problem
* Introductory linear programming problem
| align="left" colspan="1"|
| align="left" colspan="1"|
[[Media:2015-4G3-Handout-1B.pdf|Handout from class]]
[https://docs.google.com/document/d/1WxIMpERJgZZUbdok_eUAFdMJ_2U2A_jDAVq0sSoJ2ro Handout from class]
| [https://www.dropbox.com/s/7ha86cwn8hk0508/2015-4G3-Class-01B.mp4 Video]  
|align="left" colspan="1"|
|-
| 12 January
| 02A
| align="left" colspan="1"|
* More terminology related to optimization
* Continue with our introductory LP problem
* Geometric aspects of the optimum
* Moving LP problems into standard form
| align="left" colspan="1"|
[https://docs.google.com/document/d/1zQkvE0h9S-NRgGJIxD-zVGD6fbsHUSFRFK3hjW-hkRg Handout from class]
|align="left" colspan="1"|
|align="left" colspan="1"|
<!-- An important and useful reference that you should read as self-study described [http://onlinelibrary.wiley.com/doi/10.1002/14356007.o16_o04/full how membranes are made] (requires a McMaster internet connection). -->
We covered topics on page 11, 13, 14 and 17 of the notes by Marlin (see comment above).
|-
| 14 January
| 02B
| align="left" colspan="1"|
* Getting the LP problem into standard form
* Starting to understand the Simplex method to solve LPs
| align="left" rowspan="2"|
[https://docs.google.com/document/d/1NfY58o58LSGGZausUrowQMGdNuftbdCMwDbK-mUF-PQ/ Handout from class]
|align="left" rowspan="2"|
We covered topics on page 21 to 29 of the notes by Marlin, however, I did not focus on the mathematical details; we only consider the geometric viewpoint in 4G3.
|-
| 19 January
| 03A
| align="left" colspan="1"|
* Running the simplex method to solve LPs
* Interpretation of the optimum solution
|-
| 21 January
| 03B
| align="left" colspan="1"|
* Interpretation of general LP models
* Understand the effects of changes in the model on the optimum solution (i.e. sensitivity analysis)
| align="left" colspan="1"|
[https://docs.google.com/document/d/13GjbGCOxqO67pUDfVVQOfzBGvFl6gqZCNIrT54YMFPk Handout from class]
|align="left" |
See page 37 and 38 in Marlin's notes for an alternative visualization of sensitivity analysis.
|-
| 26 January
| 04A
| align="left" colspan="1"|
* Understand the effects of changes in the model on the optimum solution (i.e. sensitivity analysis)
** The effect of \(b_i\) changes on the RHS
** The effect of \(A\) changes on the LHS
** The effect of \(c_i\) changes in the objective
| align="left" colspan="1"|
[https://docs.google.com/document/d/1o8GdJERF0NvH2EafNbfOSDGIUaV8-pr6roGSb241oXY Handout from class]
|align="left" |
|-
| 28 January and 04 February
| 04B
| align="left" colspan="1"|
* Recapped some concepts on sensitivity analysis
* Considered sensitivity analysis where two or more variables were varied
* Getting a general understanding of LPs
** Allocation problems
** Blending problems
| align="left" colspan="1"|
[https://docs.google.com/document/d/1EQSzelonUYt0rcyj5s8tOPcQimQvhBKGIKLUgJpURNY/edit Handout from class]
|align="left" |
|}
 
 
 
The R-code used to draw the plot in the class handout 2B and 3A.
<syntaxhighlight lang="R">
plot(c(0, 100), c(0, 70), type = "n", xlab = expression(x[1]), ylab = expression(x[2]), asp = 1)
abline(a=1500/10, b=-16/10, lw=7)            # Placement
abline(a=1000/12, b=-10/12, lw=5)            # Solder
abline(a=500/8, b=-4/8, lw=3)                # Inspection
abline(v=0, h=0)
title(expression("Objective: Maximize 10"~x[1]~"+ 15"~x[2]))
 
text(20, 55, expression("Inspection: 4"~x[1]~"+ 8"~x[2]~"+ "~x[5]~" = 500"), srt=332.5)
text(35, 57, expression("Solder: 10"~x[1]~"+ 12"~x[2]~"+ "~x[4]~" = 1000"), srt=319.5)
text(65.5, 50, expression("Placement: 16"~x[1]~"+ 10"~x[2]~"+ "~x[3]~" = 1500"), srt=301)
text(2, 30, expression("Non-negativity: "~x[1]>=~"0"), srt=90)
text(45, 2, expression("Non-negativity: "~x[2]>=~"0"), srt=0)


delta=2
text(0+delta, 0+delta, "[0]")
text(0+delta, 62.5-2*delta, "[1]")
text(62.5, 31.25-1.5*delta, "[2]")
text(87-delta, 10.9-1.0*delta, "[3]")
text(93.75-2.1*delta, 0+1.0*delta, "[4]")
</syntaxhighlight>


<!--
<!--

Latest revision as of 11:54, 12 August 2018

Class date(s): 07 January to 04 February 2015








References

Dr. Marlin has made a great, short e-book on Linear Programming. You will find reading his notes very rewarding, and a great supplement to the class lectures.

Resources

Scroll down, if necessary, to see the resources.

Date Class number Topic Slides/handouts for class References and Notes
07 January 01B
  • Degrees of freedom
  • Terminology related to optimization
  • Introductory linear programming problem

Handout from class

12 January 02A
  • More terminology related to optimization
  • Continue with our introductory LP problem
  • Geometric aspects of the optimum
  • Moving LP problems into standard form

Handout from class

We covered topics on page 11, 13, 14 and 17 of the notes by Marlin (see comment above).

14 January 02B
  • Getting the LP problem into standard form
  • Starting to understand the Simplex method to solve LPs

Handout from class

We covered topics on page 21 to 29 of the notes by Marlin, however, I did not focus on the mathematical details; we only consider the geometric viewpoint in 4G3.

19 January 03A
  • Running the simplex method to solve LPs
  • Interpretation of the optimum solution
21 January 03B
  • Interpretation of general LP models
  • Understand the effects of changes in the model on the optimum solution (i.e. sensitivity analysis)

Handout from class

See page 37 and 38 in Marlin's notes for an alternative visualization of sensitivity analysis.

26 January 04A
  • Understand the effects of changes in the model on the optimum solution (i.e. sensitivity analysis)
    • The effect of \(b_i\) changes on the RHS
    • The effect of \(A\) changes on the LHS
    • The effect of \(c_i\) changes in the objective

Handout from class

28 January and 04 February 04B
  • Recapped some concepts on sensitivity analysis
  • Considered sensitivity analysis where two or more variables were varied
  • Getting a general understanding of LPs
    • Allocation problems
    • Blending problems

Handout from class


The R-code used to draw the plot in the class handout 2B and 3A.

plot(c(0, 100), c(0, 70), type = "n", xlab = expression(x[1]), ylab = expression(x[2]), asp = 1)
abline(a=1500/10, b=-16/10, lw=7)            # Placement
abline(a=1000/12, b=-10/12, lw=5)            # Solder
abline(a=500/8, b=-4/8, lw=3)                # Inspection
abline(v=0, h=0)
title(expression("Objective: Maximize 10"~x[1]~"+ 15"~x[2]))

text(20, 55, expression("Inspection: 4"~x[1]~"+ 8"~x[2]~"+ "~x[5]~" = 500"), srt=332.5) 
text(35, 57, expression("Solder: 10"~x[1]~"+ 12"~x[2]~"+ "~x[4]~" = 1000"), srt=319.5)
text(65.5, 50, expression("Placement: 16"~x[1]~"+ 10"~x[2]~"+ "~x[3]~" = 1500"), srt=301)
text(2, 30, expression("Non-negativity: "~x[1]>=~"0"), srt=90)
text(45, 2, expression("Non-negativity: "~x[2]>=~"0"), srt=0)

delta=2
text(0+delta, 0+delta, "[0]")
text(0+delta, 62.5-2*delta, "[1]")
text(62.5, 31.25-1.5*delta, "[2]")
text(87-delta, 10.9-1.0*delta, "[3]")
text(93.75-2.1*delta, 0+1.0*delta, "[4]")