Simplex Method

Pamantasan ng Lungsod ng Maynila

Graduate School of Management

Gen. Luna cor. Muralla St., Intramuros, Manila, Metro Manila

Written Report

in

Decision Science

Submitted by: Angela Angco

Cherry Hernandez

CHAPTER 9

LINEAR PROGRAMMING:

THE SIMPLEX METHOD

I. INTRODUCTION

The simplex method, devised by George B. Dantzig in 1947, is a highly efficient method of solving more complex linear programming problems. The simplex method is a procedure that starts with an initial basic feasible solution. It then proceeds step by step to subsequent solutions each of which is a feasible solution and has greater profit or lesser cost than the previous solution. It is an iterative process which means that in working towards an optimal solution, the computational process is repeated over and over following a standard pattern until the best solution is obtained.

In the simplex method, each new solutions yields a value of the objective function as large or larger than, or less or lesser than, the previous solution, so that it is assured that it is moving to the optimal solution.

II. DEFINITION OF TERMS

* Artificial variable – a computational device in linear programming to achieve an initial solution to the problem.

* Cj column – the profit or cost per unit.

* Zj row – the opportunity cost of bringing one unit of a variable into the solution.

* Cj – Zj row – represents the net profit or loss caused by bringing one unit of a variable into the solution of a linear programming problem.

* Degeneracy – a condition resulting from a tie in the ratios determining the replaced row, which produces a basic variable with a zero value.

* Iterative process – a step by step process following a standard pattern.

* Optimal column – the column which has the largest positive value (maximizing problem) in the Cj – Zj row or has the largest negative value (minimizing problem).

* Intersectional elements – elements...