Mathematics 209: Finite Mathematics

Study Guide

Unit 6: Linear Programming: The Simplex Method

In this unit, you will learn to solve problems using linear programming with more than two variables. The unit starts with a geometric approach and finishes with an algebraic method.

Objectives

When you have completed this unit, you should be able to

1. establish the relationship between the graphical solution method and the simplex method.
2. apply the simplex method to solve a linear programming problem.
3. apply the big $M$ method to solve a mixed linear programming problem.

A Geometric Introduction to the Simplex Method

Indications

1. Read Section 6-1, A Geometric Introduction to the Simplex Method, on pages 294–299 of the textbook.
2. Do odd-numbered exercises 1–7 on pages 299–300 of the textbook. If you have difficulty, consult your tutor to discuss the problem.
3. Answer the questions listed below, and then compare your answers with those given in the Answers to Study Guide Questions.

Questions

1. If we have a system of linear inequalities

   $\begin{array}{llll}\hfill a_{1}x+a_{2}y& \le k_1& \hfill & \\ \hfill b_{1}x+b_{2}y& \le k_2& \hfill & \\ \hfill c_{1}x+c_{2}y& \le k_3,& \hfill & \end{array}$

   how many slack variables do we introduce? Why?

2. In question 1, above, how many basic variables do we select, and how many nonbasic variables do we have?
3. If we use an augmented matrix to find the basic solutions, what are the dimensions of this matrix?
4. What is the difference between a basic solution and a basic feasible solution?

The Simplex Method: Maximization with Problem Constraints of the Form $\le$

Indications

1. Read Section 6-2, The Simplex Method: Maximization with Problem Constraints of the Form $\le \text{,}$ on pages 300–314 of the textbook.
2. Do odd-numbered exercises 1–35 on pages 314–315 of the textbook. If you have difficulty, consult your tutor to discuss the problem.
3. Solve odd-numbered problems 37–49 on pages 316–317 of the textbook. If you have difficulty, consult your tutor to discuss the problem.
4. Answer the questions listed below, and then compare your answers with those given in the Answers to Study Guide Questions.

Questions

5. If a problem has $n$ problem constraints with $m$ variables each, how many variables does the initial system have? What are the dimensions of the initial simplex tableau?
6. The flow chart on page 308 indicates that if in Step 2 there are no negative indicators in the bottom row, then the optimal solution has been found. What is this optimal solution if the first time we apply Step 2 there are no negative indicators in the bottom row? Explain.
7. If the objective function is of the form $P=-a_1{x}_1+a_2{x}_2{a}_3{x}_3$ with $a_1,a_2,a_3>0\text{,}$ what is the maximum number of times we apply Step 2 in the simplex method as indicated on page 308?

The Dual Problem: Minimization with Problem Constraints of the Form $\ge$

Indications

1. Read Section 6-3, The Dual Problem: Minimization with Problem Constraints of the Form $\ge \text{,}$ on pages 317–328 of the textbook.
2. Do odd-numbered exercises 1–43 on pages 329–330 of the textbook. If you have difficulty, consult your tutor to discuss the problem.
3. Solve odd-numbered problems 45–49 on page 331 of the textbook. If you have difficulty, consult your tutor to discuss the problem.
4. Answer the questions listed below, and then compare your answers with those given in the Answers to Study Guide Questions.

Questions

8. If a matrix $A$ has the dimensions $m\times n\text{,}$ what are the dimensions of its transpose?
9. What is the relationship between the coefficients of the objective function to be minimized and the maximization dual problem?
10. Geometrically, what does it mean to say that a problem has no optimal solution?

Maximization and Minimization with Mixed Problem Constraints

Indications

1. Read Section 6-4, Maximization and Minimization with Mixed Problem Constraints, on pages 332–345 of the textbook.
2. Do odd-numbered exercises 1–31 on pages 345–346 of the textbook. If you have difficulty, consult your tutor to discuss the problem.
3. Solve odd-numbered problems 33–47 on pages 346–348 of the textbook. If you have difficulty, consult your tutor to discuss the problem.
4. Answer the questions listed below, and then compare your answers with those given in the Answers to Study Guide Questions.

Questions

11. When do we use the big $M$ method to solve a linear programming problem?
12. Is there a limit to the number of constraint inequalities or equalities we can have if we wish to apply the big $M$ method?
13. Can we use the big $M$ method if the problem has only constraint inequalities of type $\ge \text{?}$

Finishing This Unit

1. Review the objectives of this unit and make sure you are able to meet each of them.
2. Study the section of the Chapter 6 Review titled Important Terms, Symbols and Concepts, on pages 348–349 of the textbook.
3. If there is a concept, definition, example or exercise that is not yet clear to you, go back and re-read it. Contact your tutor if you need help.
4. You might want to do odd-numbered exercises 1-29 from the Review Exercise section on pages 349–351 of the textbook. The questions on the practice examination are taken from this exercise. If you have difficulty, consult your tutor to discuss the problem.
5. Complete the practice examination provided for this unit. Evaluate yourself, first checking your answers against those provided in the Answers section at the end of the textbook, and then comparing your solutions with those provided on pages S-346 to S-370 of the Student Solutions Manual portion of the textbook. The number of points in a question may indicate the number of steps in the solution. Give yourself full credit if your answer is correct and you give a complete solution, even if your solution differs from that shown in the Student Solutions Manual.
6. Once you have written and evaluated the practice examination, complete and submit the third assignment. You will find instructions in the Assignment Drop Box on the course home page.

Practice Examination

Time: 1.5 hours
Total points: 46
Passing grade: 50%

Do the following exercises from the Chapter 6 Review Exercise on pages 349–351 of the textbook.

To obtain full credit you must justify all your answers and show your work.

1. Exercise 7, part (B)  (Marks: 6 pts.)
2. Exercise 14  (Marks: 10 pts.)
3. Exercise 16  (Marks: 10 pts.)
4. Exercise 18  (Marks: 10 pts.)
5. Exercise 26  (Marks: 10 pts.)