# A-30

# Module A

# The Simplex Solution Method

Now the model constraint is in proper form to be transformed into an equation and solved by the simplex method.

Summary of Simplex Irregularities M u l t i p l e o p t i m a l s o l u t i o n s a r e i d e n t i f i e d b y f o r a n o n b a s i c v a r i a b l e . T o d e t e r m i n e t h e a l t e r n a t e s o l u t i o n ( s ) , e n t e r t h e n o n b a s i c v a r i a b l e ( s ) w i t h a v a l u e c j - z j c j - z j ( o r z j equal to zero. - c j ) = 0

An infeasible problem is identified in the simplex procedure when an optimal solution is a c h i e v e d ( i . e . , w h e n a l l ) a n d o n e o r m o r e o f t h e b a s i c v a r i a b l e s a r e a r t i f i c i a l . c j - z j … 0

An unbounded problem is identified in the simplex procedure when it is not possible to select a pivot row—that is, when the values obtained by dividing the quantity values by the corresponding pivot column values are negative or undefined.

Resource Requirements

Resource

TABLE CHAIR

Total Available per Day

Labor (hr.)

2

4

40

Wood (bd. ft.)

18

18

216

Storage (ft.^{2})

24

12

240

The company wants to know the number of tables and chairs to produce per day to maximize profit. The model for this problem is formulated as follows:

maximize Z = $160x_{1 }+ 200x_{2 }

The original linear programming model is called the primal, and the alternative form is the dual.

Every linear programming model has two forms: the primal and the dual. The original form of a linear programming model is called the primal. All the examples in this module are primal models. The dual is an alternative model form derived completely from the pri- mal. The dual is useful because it provides the decision maker with an alternative way of looking at a problem. Whereas the primal gives solution results in terms of the amount of profit gained from producing products, the dual provides information on the value of the constrained resources in achieving that profit.

The dual solution variables provide the value of the resources, that is, shadow prices.

The following example will demonstrate how the dual form of a model is derived and what it means. The Hickory Furniture Company produces tables and chairs on a daily basis. Each table produced results in $160 in profit; each chair results in $200 in profit. The production of tables and chairs is dependent on the availability of limited resources— labor, wood, and storage space. The resource requirements for the production of tables and chairs and the total resources available are as follows:

subject to

The Dual

o f l a b o r o f w o o d o f s t o r a g e s p a c e x 1 , x 2 Ú 0 2 4 x 1 + 1 2 x 2 … 2 4 0 f t . 2 1 8 x 1 + 1 8 x 2 … 2 1 6 b d . f t . 2 x 1 + 4 x 2 … 4 0 h r .