Simplex Method - Solve Standard Maximization Problem
logo for solving-math-problems.com
leftimage for solving-math-problems.com

Simplex Method - Solve Standard Maximization Problem

by Lucy
(Dallas )










































Maximum value of a linear objective function

Given the initial simplex tableau for the maximization linear programming problem with variables x , y, z and slack variables r, s, t, find the optimal solution using the simplex method:

_ x y z r s t P
4 1 1 1 0 0 0 30
2 3 1 0 1 0 0 60
1 2 3 0 0 1 0 40
-3-2-1 0 0 0 1 0

Comments for Simplex Method - Solve Standard Maximization Problem

Click here to add your own comments

Aug 03, 2012
Simplex Method – Maximize Objective Function
by: Staff


Answer:


Part I of IV

Note: the solution process for this problem is exceptionally long. The final solution is given at the end of Part IV.


   • Standard maximization problems – two variables – Graphical Solutions:

       You are, no doubt, familiar with determining the maximum value of a linear objective function involving only two variables (say x and y).

       When only two variables are involved, the constraints (represented by inequalities) can be plotted on two dimensional x-y coordinates. The corner values can be computed to find a solution.

       The process of finding a solution is visual, straightforward, and easy – but, it is generally limited to problems involving two variables.


   • Standard maximization problems – more than two variables – Simplex Method:

       The Simplex Method is a linear programming technique used to determine the maximum value of a linear objective function involving more than two variables (say, the variables x, y, and z in your problem statement).

       The Simplex Method can be used to solve the entire class of “Standard Maximization Problems”.


   • The definition of a Standard Maximization Problem is: Determine the maximum value of a linear objective function which is subject to various linear restrictions.

       The Standard maximization problem has three restrictions:

          1. It is limited to finding the “maximum” value of the objective function (not the minimum value).
          2. All variables must be non-negative (0 or greater than 0)
          3. All constraints must have the form: Ax + By + Cz + . . . ≤ N (where N ≥ 0)

       When these conditions are met, the Simplex Method will compute the maximum value of the objective function.



   • Initial simplex tableau

       The initial simplex tableau in your problem statement is the “augmented matrix” for a the system of linear equations.

------------------------------------

Aug 03, 2012
Simplex Method – Maximize Objective Function
by: Staff


------------------------------------

Part II


However, let’s back up and look at the problem the simplex tableau represents:

Although it is not shown in your problem statement, this is your problem (the problem represented by the Initial Simplex Tableau in your problem statement):

Maximize the objective function

P = 3x + 2y + z

subject to the following constraints

4x + y + z ≤ 30
2x + 3y + z ≤ 60
x + 2y + 3z ≤ 40

where x, y, and z are non-negative.


The slack variables r, s, and t are introduced to convert the inequalities into equations:

4x + 1y + 1z + 1r + 0 + 0 + 0 = 30

2x + 3y + 1z + 0 + 1s + 0 + 0 = 60

1x + 2y + 3z + 0 + 0 + 1t + 0 = 40

-3x - 2x - 1z + 0 + 0 + 0 + 1P = 0


The four equations are converted into the augmented matrix (Initial simplex tableau) shown below:

___x y z r s t P
R [ 4 1 1 1 0 0 0 30 ]
S [ 2 3 1 0 1 0 0 60 ]
T [ 1 2 3 0 0 1 0 40 ]
P [-3-2-1 0 0 0 1 0 ]


Row reduction of tableau

Look at the bottom row

P [-3-2-1 0 0 0 1 0 ]

Pick the most negative number (the furthest to the left on the number line)

-3

This column is the pivot column (in this case, the first column)

Divide the constant (far right) in each row by the number in the pivot column

___x y z r s t P
R [ 4 1 1 1 0 0 0 30 ] 30/4 = 7.5
S [ 2 3 1 0 1 0 0 60 ] 60/2 = 30
T [ 1 2 3 0 0 1 0 40 ] 40/1 = 40
---------------------------------------
P [-3 -2 -1 0 0 0 1 0 ]

Take the smallest number you calculated: 7.5

The 4 located in the pivot column for that row will be the pivot

The pivot number is the 4 located in row 1, column 1


Change the 4 into the number 1

¼ * Row 1 = the new Row 1

___x y z r s t P
R [ 1 ¼ ¼ ¼ 0 0 0 7.5 ]

S [ 2 3 1 0 1 0 0 60 ]

T [ 1 2 3 0 0 1 0 40 ]
---------------------------------------
P [-3-2-1 0 0 0 1 0 ]

The goal is to make everything above and below the pivot element (1, far left, first row) into 0’s

-2*(Row 1) + (Row 2) = new (Row 2)

___x y z r s t P
R [ 1 ¼ ¼ ¼ 0 0 0 7.5 ]

S [ 0 2.5 0.5 -0.5 1 0 0 45 ]

T [ 1 2 3 0 0 1 0 40 ]
---------------------------------------
P [-3-2-1 0 0 0 1 0 ]

------------------------------------

Aug 03, 2012
Simplex Method – Maximize Objective Function
by: Staff

------------------------------------

Part III

-1*(Row 1) + (Row 3) = new (Row 3)

___x y z r s t P
R [ 1 ¼ ¼ ¼ 0 0 0 7.5 ]

S [ 0 2.5 0.5 0 1 0 0 45 ]

T [ 0 1.75 2.75 -¼ 0 1 0 32.5 ]
---------------------------------------
P [-3-2-1 0 0 0 1 0 ]


3*(Row 1) + (Row 4) = new (Row 4)

___x y z r s t P
R [ 1 ¼ ¼ ¼ 0 0 0 7.5 ]

S [ 0 2.5 0.5 0 1 0 0 45 ]

T [ 0 1.75 2.75 -¼ 0 1 0 32.5 ]
---------------------------------------
P [0 -1.25 -0.25 0.75 0 0 1 22.5 ]

All the values under the first pivot value are now 0.

At this point, determine whether there are any negative numbers in row 4 in columns x, y, or z.

If there are no negative values, the problem is solved.

Since there are negative values, a second pivot point must be selected.

The second column, 4th row has the greatest negative value. Therefore, the second column is the new pivot column.



+++Replace the row for the slack variable “R” with “x”



2nd pivot element

___x y z r s t P
x [ 1 ¼ ¼ ¼ 0 0 0 7.5 ] 7.5/.25 = 30

S [ 0 2.5 0.5 0 1 0 0 45 ] 45/2.5 = 18

T [ 0 1.75 2.75 -¼ 0 1 0 32.5 ] 32.5 /1.75 = 18.5714
---------------------------------------
P [0 -1.25 -0.25 0.75 0 0 1 22.5 ]


The new pivot point is 2.5, located in the second column, the second row


0.4*(Row 2) = new (Row 2)

___x y z r s t P
x [ 1 ¼ ¼ ¼ 0 0 0 7.5 ]

S [ 0 1 0.2 -0.2 0.4 0 0 18 ]

T [ 0 1.75 2.75 -¼ 0 1 0 32.5 ]
---------------------------------------
P [0 -1.25 -0.25 0.75 0 0 1 22.5 ]


-1.75*(Row 2) + (Row 3) = new (Row 3)

___x y z r s t P
x [ 1 ¼ ¼ ¼ 0 0 0 7.5 ]

S [ 0 1 0.2 -0.2 0.4 0 0 18 ]

T [ 0 0 2.4 0.1 -0.7 1 0 1 ]
---------------------------------------
P [0 -1.25 -0.25 0.75 0 0 1 22.5 ]





1.25*(Row 2) + (Row 4) = new (Row 4)

___x y z r s t P
x [ 1 ¼ ¼ ¼ 0 0 0 7.5 ]

S [ 0 1 0.2 -0.2 0.4 0 0 18 ]

T [ 0 0 2.4 0.1 -0.7 1 0 1 ]
P [0 0 0 0.5 0.5 0 1 45 ]

+++Replace the row for the slack variable “S” with “y”

___x y z r s t P
x [ 1 ¼ ¼ ¼ 0 0 0 7.5 ]

y [ 0 1 0.2 -0.2 0.4 0 0 18 ]

T [ 0 0 2.4 0.1 -0.7 1 0 1 ]
P [0 0 0 0.5 0.5 0 1 45 ]

-(1/4)*(Row 2) + (Row 1) = new (Row 1)

___x y z r s t P
x [ 1 0 3/20 7/20 -2/20 0 0 3 ]

y [ 0 1 2/5 -0.2 0.4 0 0 18 ]

T [ 0 0 2.4 0.1 -0.7 1 0 1 ]
P [0 0 0 0.5 0.5 0 1 45 ]
------------------------------------

Aug 03, 2012
Simplex Method – Maximize Objective Function
by: Staff

------------------------------------

Part IV

All the values above and below the second pivot value are now 0.
At this point, determine whether there are any negative numbers in row 4 in columns x, y, or z.

Since there are no negative values, the problem is solved.

>>>> THE FINAL SOLUTION IS:
Objective function maximized: P = 45
Variable x = 3
Variable y = 18
Variable z = 0

----------------------------------------------------------------

check the solution:
Maximize the objective function

P = 3x + 2y + z

subject to the following constraints

4x + y + z ≤ 30
2x + 3y + z ≤ 60
x + 2y + 3z ≤ 40

x ≥ 0
y ≥ 0
z ≥ 0


P = 3x + 2y + z

P = 3* 3 + 2*18 + 0 = 45, OK


4x + y + z ≤ 30

4*3 + 18 + 0 ≤ 30, OK


2x + 3y + z ≤ 60

2*3 + 3*18 + 0 ≤ 60, OK


x + 2y + 3z ≤ 40

3 + 2*18 + 3*0 ≤ 40


2x + 3y + z ≤ 60

2*7.5 + 3*18 + z ≤ 60, OK




Thanks for writing.

Staff
www.solving-math-problems.com



Click here to add your own comments

Join in and write your own page! It's easy to do. How? Simply click here to return to Math Questions & Comments - 01.



Copyright © 2008-2014. All rights reserved. Solving-Math-Problems.com