CO250 Study Guide - Final Guide: Linear Programming, Simplex Algorithm

• School: University of Waterloo
• Department: Combinatorics and Optimization
• Course: CO250
• Professor: Joseph Cheriyan

Document Summary

In sections 1 and 2, we give two examples of the simplex method using dictionaries, so that the reader will have an intuitive understanding of how the method works. In section 3 (see the last page), we will formalize the method. This example is taken from ch vatal and the notes follow those given in ch vatal, chapter 2. 3x1 + 4x2 + 2x3 8 xi 0, for i = 1, 2, 3. Add slack variables to this linear program to get a linear program in sef (standard equality form), such that if we solve the new linear program then we will also solve the original linear program. (2. 2) max. + x6 = 8 xi 0, for i = 1, 2, 3, 4, 5, 6. De ne a new variable z and let z = 5x1 + 4x2 + 3x3.