Introduction to Simplex Method
It was invented by G. Danztig in 1947. The simplex method gives an algorithm, that is, a rule of procedure generally involving repetitive application of a prescribed operation, which is based on the basic theorem of linear programming.
The Simplex algorithm is an iterative method for resolving LP problems in a finite number of steps. It contains
Benefits
Computational Procedure of Simplex Method
Take an example
Maximize Z = 3x1 + 2x2
Subject to
x1 + x2 ≤ 4
x1 - x2 ≤ 2
& x1 ≥ 0, x2 ≥ 0
Answer
Step 1 - Note down or write the given GLPP in the form of SLPP
Maximize Z = 3x1 + 2x2 + 0s1 + 0s2
x1 + x2+ s1= 4
x1 - x2 + s2= 2
x1 ≥ 0, x2 ≥ 0, s1 ≥ 0, s2 ≥ 0
Step 2 - Then present the constraints in the form of matrix
Step 3 - Now construct the starting simplex table with the use of notations
Cj → 3 2 0 0
Basic Variables
CB XB
X1 X2 S1 S2
Min ratio
XB /Xk
s1
s2
0 4
0 2
1 1 1 0
1 -1 0 1
Z= CB XB
Δj
Step 4 - Calculation of Z and Δj and check the basic feasible solution for optimality by the rules known.
= 0 *4 + 0 * 2 = 0
Δj = Zj - Cj
= CB Xj - Cj
Δ1 = CB X1 - Cj = 0 * 1 + 0 * 1 - 3 = -3
Δ2 = CB X2 - Cj = 0 * 1 + 0 * -1 - 2 = -2
Δ3 = CB X3 - Cj = 0 * 1 + 0 * 0 - 0 = 0
Δ4 = CB X4 - Cj = 0 * 0 + 0 * 1 - 0 = 0
Process to check the basic feasible solution for optimality by the rules known
Rule 1 - If all Δj ≥ 0, then the solution under the test will be optimal. Other optimal solution will exist if any non-basic Δj is zero as well.
Rule 2 - If at least one Δj is negative, then the solution is not optimal and one can proceed to improve the solution in the further step.
Rule 3 - If corresponding to any negative Δj, eacjh and every elements of the column Xj are negative or zero, then the solution under examination will be unbounded.
In this problem it is seem that Δ1 and Δ2 are negative. Therefore proceed to enhance or improve this solution
Step 5 - To enhance the basic feasible solution, the vector entering the basis matrix and the vector to be removed from the basis matrix are to be find out.
The incoming vector Xk is always chosen parallel to the most negative value of Δj. It is signified through (↑).
The outgoing vector is chosen parallel to the minimum positive value of minimum ratio. It is symbolized through (→).
Step 6 - Now mark the key element or pivot element through '1''.The element at the intersection of incoming vector and outgoing vector is the pivot element.
(Xk)
4 / 1 = 4
2 / 1 = 2 → outgoing
Z= CB XB = 0
↑incoming
Δ1= -3 Δ2= -2 Δ3=0 Δ4=0
x1
3 2
(R1=R1 - R2)
0 2 1 -1
2 / 2 = 1 → outgoing
2 / -1 = -2 (neglect in case of negative)
Z=0*2+3*2= 6
Δ1=0 Δ2= -5 Δ3=0 Δ4=3
Step 7 - Then repeat step 4 through step 6 until an optimal solution is attained.
x2
2 1
3 3
(R1=R1 / 2)
0 1 1/2 -1/2
(R2=R2 + R1)
1 0 1/2 1/2
Z = 11
Δ1=0 Δ2=0 Δ3=5/2 Δ4=1/2
As all Δj ≥ 0, optimal basic feasible solution is achieved
Thus the solution is Max Z = 11, x1 = 3 and x2 = 1
Worked Examples
Solve with the help of simplex method
Example 1
Maximize Z = 80x1 + 55x2
4x1 + 2x2 ≤ 40
2x1 + 4x2 ≤ 32
SLPP
Maximize Z = 80x1 + 55x2 + 0s1 + 0s2
4x1 + 2x2+ s1= 40
2x1 + 4x2 + s2= 32
Cj → 80 55 0 0
0 40
0 32
4 2 1 0
2 4 0 1
40 / 4 = 10→ outgoing
32 / 2 = 16
Δ1= -80 Δ2= -55 Δ3=0 Δ4=0
80 10
0 12
(R1=R1 / 4)
1 1/2 1/4 0
(R2=R2- 2R1)
0 3 -1/2 1
10/1/2 = 20
12/3 = 4→ outgoing
Z = 800
Δ1=0 Δ2= -15 Δ3=40 Δ4=0
80 8
55 4
(R1=R1- 1/2R2)
1 0 1/3 -1/6
(R2=R2 / 3)
0 1 -1/6 1/3
Z = 860
Δ1=0 Δ2=0 Δ3=35/2 Δ4=5
As all Δj ≥ 0, optimal basic feasible solution is achieved. Hence the solution is Max Z = 860, x1 = 8 and x2 = 4
Email based Simplex Method assignment help – homework help
Are you not finding solution for simplex method problems? Do you need expert’s guide in solving your operation research assignments or homework for simplex method based questions? We at www.tutorsglobe.com offer simplex method assignment help, simplex method homework help, simplex method problems solutions and linear programming assignment help with step by step answers. Our specialized tutors are expert in solving complex level problems in simplex method.
www.tutorsglobe.com offers answering questions to theories of international trade, the principle of absolute advantage, economics assignment help - homework help by online tutors.
Theory and lecture notes of Contingency tables on the TI-82 all along with the key concepts of contingency tables on the ti-82, homework help, assignment help. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Contingency tables on the TI-82.
www.tutorsglobe.com offers conceptual and technical designs homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
Theory and lecture notes of Microeconomic Theory all along with the key concepts of Microeconomic theory, Macroeconomics, Microeconomics, Methodologies, Rationality, Optimization Problem. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Microeconomic theory.
galilean transformation tutorial all along with the key concepts of frames of reference, non- invariance of electromagnetic phenomena under galilean transformation, ether hypothesis, michelson-morley experiment
www.tutorsglobe.com offers price elasticity of supply homework help - price elasticity of supply assignment help, answering questions to price elasticity of supply, economics solutions by tutors help.
tutorsglobe.com spinal cord functioning assignment help-homework help by online co-ordination systems tutors
tutorsglobe.com perl assignment help-homework help by online computer programming tutors
tutorsglobe.com anterior urethra assignment help-homework help by online types of normal flora tutors
www.tutorsglobe.com offers Objects Relationship Model homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
tutorsglobe.com types of epistasis assignment help-homework help by online epistasis tutors
www.tutorsglobe.com offers The Cost of Prototyping homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
gramophone is a type of record player. the sound that is stored in the place is converts in to an electrical note through a tone arm.
Theory and lecture notes of Divergence all along with the key concepts of World Distribution of Income Today, OECD Economies, Economies Converged, Iron Curtain, Policy: Post-Communism. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Divergence.
theory and lecture notes on power in ac circuits all along with the key concepts of power dissipation in an ac circuit, instantaneous power, average power, complex power. tutorsglobe offers homework help, assignment help and tutor’s assistance on power in ac circuits ii.
1940958
Questions Asked
3689
Tutors
1460767
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!