Scribd
Upload
24 views2 pages

Simplex Method for Linear Programming

The document outlines a linear programming problem aimed at maximizing the objective function Z = 4x₁ + 5x₂ + 9x₃ + 11x₄, subject to three constraints. It details the conversion to standard form by introducing slack variables and setting up the initial simplex tableau. The document also describes the simplex method's iterative process for finding the optimal solution, emphasizing the identification of entering and leaving variables and the pivoting process.

Uploaded by

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

Simplex Method for Linear Programming

The document outlines a linear programming problem aimed at maximizing the objective function Z = 4x₁ + 5x₂ + 9x₃ + 11x₄, subject to three constraints. It details the conversion to standard form by introducing slack variables and setting up the initial simplex tableau. The document also describes the simplex method's iterative process for finding the optimal solution, emphasizing the identification of entering and leaving variables and the pivoting process.

Uploaded by

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

Linear Programming Solution Using Simplex Method

Problem Statement
Maximize Z = 4x₁ + 5x₂ + 9x₃ + 11x₄
Subject to:
x₁ + x₂ + x₃ + x₄ ≤ 15
7x₁ + 5x₂ + 3x₃ + 2x₄ ≤ 120
3x₁ + 5x₂ + 10x₃ + 15x₄ ≤ 100
x₁, x₂, x₃, x₄ ≥ 0

Step 1: Convert to Standard Form


Introduce slack variables s₁, s₂, s₃ to transform inequalities into equalities:
x₁ + x₂ + x₃ + x₄ + s₁ = 15
7x₁ + 5x₂ + 3x₃ + 2x₄ + s₂ = 120
3x₁ + 5x₂ + 10x₃ + 15x₄ + s₃ = 100

Objective function:
Z - 4x₁ - 5x₂ - 9x₃ - 11x₄ = 0

Step 2: Initial Simplex Tableau


Set up the initial simplex tableau with basic variables (s₁, s₂, s₃):
+------+------+------+------+------+------+------+-------+
| BV | x₁ | x₂ | x₃ | x₄ | s₁ | s₂ | RHS |
+------+------+------+------+------+------+------+-------+
| s₁ | 1 | 1 | 1 | 1 | 1 | 0 | 15 |
| s₂ | 7 | 5 | 3 | 2 | 0 | 1 | 120 |
| s₃ | 3 | 5 | 10 | 15 | 0 | 0 | 100 |
+------+------+------+------+------+------+------+-------+
| Z | -4 | -5 | -9 | -11 | 0 | 0 | 0 |
+------+------+------+------+------+------+------+-------+

Step 3: Simplex Iterations


1. Identify the entering variable: The variable with the most negative coefficient in the Z-
row is chosen.
2. Identify the leaving variable: Compute the minimum positive ratio of RHS to the pivot
column.
3. Perform pivoting: Update the tableau by making the pivot element 1 and other elements
in the column 0.
Repeat until there are no negative coefficients in the Z-row.
Note
The complete simplex computation involves several iterations. For brevity, computational
tools can be used to carry out the simplex algorithm steps. If needed, the solution can be
derived computationally.

You might also like