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.
Latent Heat and Evaporation tutorial all along with the key concepts of Concept of latent heat, Application and Types of Latent Heat, Effects of Impurities and Pressure, Concept of evaporation, Factors affecting evaporation, Concept of boiling, Concept of Sublimation, Humidity and Weather
www.tutorsglobe.com - offers cost allocation homework help, cost allocation assignment help, answering questions to cost allocation accounting problems, online tutoring by live online tutors.
Theory and lecture notes of Domestic Spending all along with the key concepts of domestic spending, components of Real GDP, consumption spending, Investment spending, Government purchases, Net exports. Tutorsglobe offers homework help, assignment help and tutor’s assistance on domestic spending.
Transformation of alcohols and arenes tutorial all along with the key concepts of Oxidation of primary alcohols, Oxidation of secondary alcohols, Oxidation of tertiary alcohols and Transformation of arenes
Theory and lecture notes of Dependent Samples all along with the key concepts of Dependent samples - the mean of the difference, homework help, assignment help and two parameter testing tutors. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Dependent Samples.
tutorsglobe.com harmful effects of algae assignment help-homework help by online algae tutors
Ecological Population tutorial all along with the key concepts of Density, Distribution and Size, Growth Patterns, Mortality Patterns and Survivorship Curves, Age Structure, Population Growth Curve, Population Growth Rate, Basic Concepts of Rate
www.tutorsglobe.com offers other object oriented issues homework help, assignment help, case study, writing homework help, online tutoring assistance by computer science tutors.
Theory and lecture notes of Complex Numbers all along with the key concepts of complex numbers, Imaginary number, Equality of Complex Numbers, Complex Conjugates and Graphing Complex Numbers. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Complex Numbers.
tutorsglobe.com shape of s-orbitals assignment help-homework help by online shapes of orbitals tutors
Mechanism of Antibody Formation tutorial all along with the key concepts of Theories of Antibody Formation, Production of Antibodies, Qualitative Changes and Cellular Events, Antigen/antibody interactions, Lymphocytes, B-Lymphocytes and T-Lymphocytes
Lasers tutorial all along with the key concepts of Characteristics of Laser radiation, Directionality, Coherence, Emission and Absorption of Light, Stimulated Emission of Light, Absorption of Light, Elements of a Laser, Applications of Lasers
theory and lecture notes of dc motors ii all along with the key concepts of torque, speed, force, power delivered to load, output power and efficiency, speed-torque characteristics. tutorsglobe offers homework help, assignment help and tutor’s assistance on theory of dc motors ii.
Theory and lecture notes of Sampling Lab all along with the key concepts of Sampling Lab, Random Sampling, Systematic Sampling, Convenience Sampling, Stratified Sampling and Cluster Sampling. Tutorsglobe offers homework help, assignment help and tutor’s assistance on Theory of Sampling Lab.
Parasitic helminths and lifecycles tutorial all along with the key concepts of Types of Host, Definitive Host, Intermediate Host, Accidental Host, Paratenic Host and Reservoir Host
1950814
Questions Asked
3689
Tutors
1485891
Questions Answered
Start Excelling in your courses, Ask an Expert and get answers for your homework and assignments!!