Suppose that Team members A and C have decided to work together in their tasks. They have decided that their skills are complementary and by working together in both of the tasks assigned to them they can do a better job than if they work independently. A has very good writing speed, he can write 4 pages per hour but his rate of grammatical errors is very high (3 errors per page). On the other hand, C is slower (2.5 pages per hour) but his error rate is very low (1 error per page). They want to write a report that will earn them the highest grade.
They have discovered that the grade given by the professor is very much influenced by the number of pages of the written assignments (the more pages the higher the grade assigned). However, they have also discovered that for every five errors in grammar, he deducts the equivalent of one written page, and also that the maximum number of mistakes the instructor will tolerate in an assignment is 80. Help this team of students to determine the best strategy (you need to define the meaning of this) given the total time constraint available to work in the project. The total time allocated to both of them is 8 hours. Also because of previous commitments C cannot work more than 6 hours in the project
You have found graphically the optimal solution. Based on that solution do the following exercise.
You are given the alternative of increasing the number of errors allowed to 90 or to increase the number of total number of hours allowed to work in the project to 9 (for both team members). What option would you choose? Explain.
At the end of the exercise each team should turn in the individual and team solutions in a single package for grading
The instructor may select a member of the team to present the their solution to the rest of the class
Notice that by increasing (or decreasing) the availability of a scarce resource (hours or total number of errors allowed) the straight line (representing the constraint) moves in parallel to the original one (but note that the slope does not change)
Also note that the total-errors constraint is a non-binding constraint. That is, it does not impact the current optimal solution. (at what point is this no longer true?)
Unfortunately we can get the graphical solution of the LP problem only for problems with 2 and 3 decision variables
Therefore we need to find an alternative method to get the optimal solution of LP problems
We know that the optimal solution must be in a corner point (why?)
We also know that a corner point is defined by the intersection of two constraints (for the 2 decision variable case we solve a different subset of two linear equations for each corner point). What about when we have three or more decision variables? Can you identify all the corner points?
So what we could do is solve the subsets of linear equations corresponding to all the corner points. Then we evaluate the objective function at those corner points and the one yielding the best objective value is our optimal solution.
However, since there is a large number of corner points (how many?) this is impractical. We need a smart way to search for the optimal solution. This is what the the simplex algorithm does for us.
Simplex Method .- An algebraic, iterative method to solve linear programming problems.
The simplex method identifies an initial basic solution (Corner point) and then systematically moves to an adjacent basic solution, which improves the value of the objective function. Eventually, this new basic solution will be the optimal solution.
The simplex method requires that the problem is expressed as a standard LP problem (see module on Standard Form). This implies that all the constraints are expressed as equations by adding slack or surplus variables.
The method uses Gaussian elimination (sweep out method) to solve the linear simultaneous equations generated in the process.
Step 0: Using the standard form determine a starting basic feasible solution by setting n-m non-basic variables to zero.
Step 1: Select an entering variable from among the current non-basic variables, which gives the largest per-unit improvement in the value of the objective function.
If none exists stop; the current basic solution is optimal. Otherwise go to Step 2.
Step 2: Select a leaving variable from among the current basic variables that must now be set to zero (become non-basic) when the entering variable becomes basic.
Step 3: Determine the new basic solution by making the entering variable, basic; and the leaving variable, non-basic, and return to Step 1.
Divide the pivot row by the pivot element and call it the new pivot row. Copy the result in the tableau for the next iteration
For every row of the current tableau (excluding the pivot row) subtract the product of its pivot-column coefficient times the new pivot row. Copy the result in the corresponding row of the next-iteration tableau. Make sure to properly identify the new basic variable.
One way to assess the efficiency of the simplex algorithm is to count the number of iteration needed to arrive to the optimal solution and to compare this against the total number of corner point solutions given by the formula:
(n) = number of variables, (m) = number of equations