Scribd
Upload
8 views5 pages

Linear Programming Problem Structure

The document outlines the general structure of a linear programming problem, including the objective function and constraints. It details the steps of the Simplex Method for solving such problems, from formulating the problem to determining the optimal solution through iterative testing for feasibility and optimality. Key steps include finding the initial basic solution, testing for optimality, and repeating the process until an optimal solution is achieved.

Uploaded by

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

Linear Programming Problem Structure

The document outlines the general structure of a linear programming problem, including the objective function and constraints. It details the steps of the Simplex Method for solving such problems, from formulating the problem to determining the optimal solution through iterative testing for feasibility and optimality. Key steps include finding the initial basic solution, testing for optimality, and repeating the process until an optimal solution is achieved.

Uploaded by

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

General structure of Linear programming problem

(Maximize or Minimize) Z=c1x1+c2x2+...+cnxn (objective function)

Subject to the constraints


a11x1+a12x2+...+a1nxn(≤,≥,=)b1
a21x1+a22x2+...+a2nxn(≤,≥,=)b2
:
:
am1x1+am2x2+...+amnxn(≤,≥,=)bm (constraints)

and x1,x2,...,xn≥0 (non-negative condition)


Simplex Method Steps (Rule)
Step-1:Formulate the Problem
a. Formulate the mathematical model of the given
linear programming problem.

b. If the objective function is minimization type then


change it into maximization type. Min z = - Max (-z)

c. All the bi>0. So if any bi<0 then multiply the


corresponding constraint by -1 to make bi>0. So
sign ≤ changed to ≥ and vice versa

d. Transform every ≤ constraint into an = constraint by


adding a slack variable to every constraint and assign a
• Step-2:Find out the Initial basic solution

Find the initial basic feasible solution by setting zero


value to the decision variables.
• Step-3:Test for Optimality

a. Calculate the values of cj-zj in the last row of simplex


table.

b. If all cj-zj≤0 , the current basic feasible solution is the


optimal solution.

c. If cj-zj>0, then select the variable that has largest cj-


zj and enter this variable into the new table. This column
• Step-4:Test for Feasibility (variable to leave the
basis)

a. Find the ratio by dividing the elements


of Value column by the positive values of key
column (say aij>0)

b. Find the minimum ratio and this row is called key


row (pivot row) and corresponding variable will
leave the solution.

c. The intersection element of key row and key


column is called key element (pivot element).
• Step-5:Determine the new solution

a. The new values of key row can be obtained by


dividing the key row elements by the pivot element.

b. The numbers in the remaining rows can be


computed by utilizing the following formula:

Row(new) = Row(old) - (value of key column and


Row(old)) × KeyRow(new)

Step-6:Repeat the procedure

Goto step 3 and repeat the procedure until all the


values of c -z ≤0.

You might also like