Running late today. In the middle of a constraint problem when I walked in.
The example problem has a very poor business model. Five people building toy trucks full time, for a maximum total profit of $140 dollars per week.
We’re switching to solving these constraint problems via the simplex method, now. Previously we’ve been using graphical methods to solve. Simplex method is an algebraic approach.
Simplex method was developed for maximization problems involving many variable and many constraints. Geometric solutions are extremely difficult to implement with more than two variable and two constraints. Simplex method scales to hundreds of variables and constraints.
A linear program in which the objective function is to be maximized is referred to as a maximum problem. A maximum problem is in standard form when:
- All the variables are non-negative
- Every other constraint is written as a linear expression that is less than or equal to a positive constant
It may be necessary to perform some algebraic operations on a constraint to force it into standard form.
Slack Variables are non-negative numbers, are needed to obtain systems of equations from our constraints. The function of a slack variable is to convert an inequality into an equality. The value of a slack variable is the number which must be added to the result of the left side of the inequality to make it exactly equal the right-side value, rather than being less than or equal. The point of converting the inequalities to equations via slack variables is to enable us to place those equations into a matrix and solve them via matrix operations.
When the inequalities have been rendered into equations, they can be placed into the initial simplex tableau. The initial simplex tableau is a matrix containing the constraint equations as the top rows, and the objective function as the last row. Each row will begin with variable P, which will have a coefficient of 0 in every column but the objective function. P will have a coefficient of 1 in the objective function row. Each row will also have an entry for each slack variable used, and each slack variable will only have a nonzero value in the equation it was defined in.