Scribd
Upload
5 views10 pages

Example 1 Simplex Method

The document outlines the process of solving a linear programming problem using the simplex method, starting with the formulation of the objective function and constraints. It details the steps involved in converting the problem into standard form, creating the initial simplex tableau, and performing iterations to find the optimal solution. The final tableau indicates the maximum value of the objective function and the values of the decision variables at optimality.

Uploaded by

fatimazaabia99
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd
5 views10 pages

Example 1 Simplex Method

The document outlines the process of solving a linear programming problem using the simplex method, starting with the formulation of the objective function and constraints. It details the steps involved in converting the problem into standard form, creating the initial simplex tableau, and performing iterations to find the optimal solution. The final tableau indicates the maximum value of the objective function and the values of the decision variables at optimality.

Uploaded by

fatimazaabia99
Copyright
© All Rights Reserved
We take content rights seriously. If you suspect this is your content, claim it here.
Available Formats
Download as PDF, TXT or read online on Scribd

Example

Solve the following L.P. using simplex method

Max Z= 6X1+4X2
Subject to
X1+X2 ≤12
X1-2X2 ≤ 6
X2 ≤ 8
X1, X2 ≥ 0
Solution
Put the problem in standard form
First step: Add SLACK variables

Max Z- 6X1-4X2=0
Subject to
X1+X2 +X3 =12
X1-2X2 +X4 =6
X2 +X5 = 8
X1, X2, X3, X4, X5 ≥ 0
Max z - 6x1 - 4x2 =0
Subj. to:
The Simplex Tableau x1 + x2 + x 3 = 12
initial tableau x1 - 2x2 + x4 = 6
x2 + x5 = 8

Basic
Eq Var z x1 x2 x3 x4 x5 RHS

0 z 1 -6 -4 0 0 0 0

1 x3 0 1 1 1 0 0 12

2 x4 0 1 -2 0 1 0 6

3 x5 0 0 1 0 0 1 8
z = 6x1 + 4x2
The Simplex Algorithm
Step 1: Select a new variable to enter the basis.

Pick the non-basic variable having the greatest negative value.

Basic
Eq Var z x1 x2 x3 x4 x5 RHS

0 z 1 -6 -4 0 0 0 0

1 x3 0 1 1 1 0 0 12

2 x4 0 1 -2 0 1 0 6

3 x5 0 0 1 0 0 1 8
Step 2: Select a basic variable to leave the basis.

Pick the basic variable having the smallest ratio of the RHS divided by the
corresponding positive coefficient from the incoming variable.

1x1 - 2x2 + x4 = 6
Basic
Eq Var z x1 x2 x3 x4 x5 RHS Ratio

0 z 1 -6 -4 0 0 0 0

1 x3 0 1 1 1 0 0 12 12/1

2 x4 0 1 -2 0 1 0 6 6/1

3 x5 0 0 1 0 0 1 8
pivot point
Step 3: Use row operations to find the new basic solution.

Basic
Eq Var z x1 x2 x3 x4 x5 RHS

0 z 1 -6 -4 0 0 0 0

1 x3 0 1 1 1 0 0 12

2 x4 0 1 -2 0 1 0 6

3 x5 0 0 1 0 0 1 8

Basic
Eq Var z x1 x2 x3 x4 x5 RHS

0 z 1 0 -16 0 6 0 36

1 x3 0 0 3 1 -1 0 6

2 x1
0 1 -2 0 1 0 6
3 x5 0 0 1 0 0 1 8
Max z = 6x1 + 4x2
Subj. to:
x2 x1 + x2 <= 12
12 x1 -2x2 <= 6
x2 <= 8

8
(4,8)
z

z
(10,2)

x1
6 12

-3
2nd Iteration z = 6x1 + 4x2

Find minimum ratio

Pick the non-basic variable having the greatest negative value.

Basic
Eq Var z x1 x2 x3 x4 x5 RHS Ratio

0 z 1 0 -16 0 6 0 36

1 x3 0 0 3 1 -1 0 6 6/3

2 x1 0 1 -2 0 1 0 6

3 x5 0 0 1 0 0 1 8 8/1
Pivot point
Basic
Eq Var z x1 x2 x3 x4 x5 RHS

0 z 1 0 -16 0 6 0 36

1 x3 0 0 3 1 -1 0 6

2 x1 0 1 -2 0 1 0 6

3 x5 0 0 1 0 0 1 8

Basic
Eq Var z x1 x2 x3 x4 x5 RHS

0 z 1 0 0 16/3 2/3 0 68

1 x2 0 0 1 1/3 -1/3 0 2

2 x1
0 1 0 2/3 1/3 0 10
3 x5 0 0 0 -1/3 1/3 1 6
Max z = 6x1 + 4x2
Subj. to:
x2 x1 + x2 <= 12
12 x1 -2x2 <= 6
x2 <= 8

8
(4,8)
z

z
(10,2)

x1
6 12

-3

You might also like