Math Canonical Form
ADVERTISEMENT
1
2
3Lecture on 3-25
SA305 Spring 2013
1
Canonical Form
To construct the simplex method we need to put our linear programs all in a similar form
so that the algorithm is standardized and can use the mechanics of the extreme points.
Definition 1.1. A linear program with n variables is in canonical form if it is of the following
form
max c x
Ax = b
x
0
where A = (a ) is a m
n matrix, m
n, and the rows of A are linearly independent.
Can every linear program be put in canonical form? First let’s look at an example.
Example 1.2. Let
x + 2y
1
2x + y
1
x, y
0
be the constraints of a LP.
For each constraint where there might be slack or surplus you add or subtract a slack
or surplus variable to amke the constraint equality and then append the LP with the non-
negativity of these new variables.
So our new constraints look like
x
+ 2y +
s
= 1
1
2x +
y
s
= 1
2
x, y, s
, s
0.
1
2
Now let’s put this in matrix form. Let
x
y
x =
s
1
s
2
1 2 1
0
A =
2 1 0
1
and
1
ADVERTISEMENT
0 votes
Related Articles
Related forms
Related Categories
Parent category: Education