Simplex Algorithm in Linear Programming
Uploaded by
ScribdTranslationsSimplex Algorithm in Linear Programming
Uploaded by
ScribdTranslationsAlgebraic Method in Linear Programming
1. Introduction
We have solved cases of simple linear programs: two
variables and three or five constraints. As the
the number of constraints increases, the graphic method proves to be
increasingly difficult to implement.
In the presence of three variables, we must call upon a
graphical representation in space, a very delicate exercise . . .
However, in practice, linear programs consist of several
dozens of variables and constraints. Thus, the use of a
general method becomes essential.
The simplex algorithm is the most widely used of the methods of
linear programming resolution. It was developed in 1948
by B. Dantzig. Since then, this algorithm has been the subject of certain
scientific articles and has served in the resolution of many
linear models.
2. Principle of the algorithm
When considering a linear program with more than 2 variables, the
graphical resolution becomes difficult, but the properties remain the same
same. If the objective function can have an optimal value in the
feasible region, it is located at one of the corners of the region
feasible. To reach the optimal value, only the vertices must
so be examined.
One could deduce that it is sufficient to calculate the value of the
objective function at each vertex and finally choose the best one.
big of these values; but this approach is impractical for the
large programs: a program with 100 variables and 10 constraints,
which is a medium-sized, if not small, program, would already have more
from 1,730 billion peaks!
An 'intelligent' procedure is therefore necessary: the algorithm of
simplex uses an iterative procedure that allows to find the
optimal value or, failing that, highlights that the feasible region
it is empty.
1
The principle of the simplex algorithm is as follows:
Phase I: Initialization Procedure
Determine a first vertex of the feasible region D. If this
procedure fails, this means that the realizableDest region is empty;
Phase II: Iterative Procedure
Move from a vertex of D to another neighboring vertex of D, in such a way that
improve the value of the objective function each time. This new
the summit will be adjacent to the previous one in the sense that they will both be
ends of an edge of D;
Stop Test: Stop Procedure
Two stopping tests determine whether to stop the calculation,
because we have reached an optimal solution or because it does not exist
to define the optimal solution, or if we should move towards a new one
summit.
Complete Treatment: Example
Let the linear program for maximization be in Canonical form.
PLC (Canonical Linear Program):
➔ Deviation variables
The resolution method we are studying in this chapter requires
that the model constraints be expressed in the form of equations
linear (Standard Form) instead of inequalities (Formulation
Canonical).
One can easily transform a linear inequality having a sign
in a linear equation by adding a non-negative variable called
difference variable as follows:
Let the constraint be:
x 4;x 0
Adding to the first member of the inequality, the margin variable
2
ever verifying 0, we obtain: x + e = 4 and then e = 4 - x
represents the gap between 4 and the quantity actually used x.
the slack variable introduced in the corresponding constraint
will then represent a timeout, which can be either positive or zero.
We add as many different gap variables as there are
constraints of the type.
We then obtain the linear maximization program in the form
StandardPLS (Standard Linear Programming):
The 3 variables 1 , 2 , 3are all positive or zero and are
deviation variables.
➔ Illustration of the algorithm
We will now see how to apply the steps of the
algebraic method.
Initialization of the algorithm
The question that arises is:
How to choose the starting point?
If the constraints are expressed as equalities, it is enough to take
the origin as a starting point.
(x1; x2= (0;0)
In algebraic terms, all the original decision variables: x1
and x2are excluded from the database.
Automatically, in the system of equations:
3
we read the value of the basic variables:
Hence the basic feasible solution to start with:
(0;0;4;12;18)
What is the value of the objective function for this
first basic solution?
The formulation of the example in standard form allows for expression
easily each deviation variable (here base variable) as well as the
objective function Z as linear functions of decision variables
only (here variables outside of base : x1,x2) :
On a Dictionary 1 (Dic 1)
The starting base solution can be summarized as follows:
Transition from one peak to another
Phase II of the simplex algorithm consists of moving from a vertex
to an adjacent summit in order to improve the function each time
objectives.
Algebraically, this operation corresponds to a change of basis.
the new database differs from the old database by only one
variable. We will therefore move from our basic solution of
departure towards another feasible base solution by following an edge
along which the value decreases.
4
a.-Choice of the entering variable
The question that arises is then: how to choose an edge along
which value should increase?
Algebraically, this question is equivalently phrased as
Which external variable will be entered into the database?
On a : Z = 300x1+ 500x2
To obtain a better solution, all you need to do is to run one of the
two variables x1or x2from zero value to a positive value.
It is therefore preferable to choose x.2which is worth 500 per unit while x1
is worth only 300.
One can thus hope to move 'faster' towards the optimal solution. By
against the value of x1remains nothing.
The selection criterion for the incoming variable is therefore as follows:
We choose the variable with the positive coefficient (of the function
the highest objective.
Note that to be able to apply this simple criterion (the choice of the
incoming variable), the objective function Z must be expressed in
function of the only out-of-base variables.
Here, we choose the variable x2
B.- Choice of the outgoing variable
We can now ask the following two questions:
a) how far can we increase the dex value2?
b) which basic variable should leave the base, that is, must-
Does it become out of the base, that is to say having a null value?
(Note that the number of basic variables must always be
exactly equal to 3: number of constraints.
Assuming that x1remains outside the base (and therefore equal to 0) in (Dic 1), we
obtains the variations of the base variables as a function of ex2:
5
But to maintain a viable solution and not leave the region.
feasible, it is also necessary that the components remain positive. We
we must have x3> 0, x40 and x5In fact:
Constraint (C1) does not impose any restrictions on the increase of ex.2
because it does not contain x2In total, the most restrictive constraint
for x2thus (C2). Therefore, it is necessary to stop at the value x2= 6(it's a
response to question a) for which the variable x4becomes null and
going beyond would make it negative. So,
We can assume that x4is currently out of stock (this is a response to
the questionb).
It is concluded that the output variable is x.4that is to say the first
which cancels out when x2grows from 0.
We report the second members of the constraints to
corresponding coefficients of the entering variable.
The outgoing variable corresponds to the smallest positive ratio.
Calculation of the new summit
The question that arises is:
How to calculate the new basic solution?
We will respond to it using system resolution. More
Precisely, we will make a dictionary change by exchanging.
the roles of x2and x4We use the second equation of (Dic 1) to
express x2depending on the new out-of-base variables, x1and x4 :
Exchange equation:
We then replace x2by this expression in the other equations
the dictionary (of constraints):
6
The first iteration is complete. The second basic solution can
can be summarized as follows:
—Off-base variables: x 1= 0, x4= 0 ;
Base variables: x2= 6, x3= 4, x5= 6 ;
Objective function value: Z = 3000.
Stop test
The question that arises now is:
How to know that the solution found is optimal?
To answer this question, we will examine the news.
expression of the objective function Z. The last equation of
dictionary (Dic 2):
Z = 3000 + 300 x1- 250 x2
Like x1with a positive coefficient, it is interesting to bring in x1
based on this, which leads to a second iteration.
The stopping criterion will therefore be as follows:
the current basic solution is optimal if all the coefficients of
the objective function Z is negative or zero when Z is expressed
based solely on off-base variables.
Second iteration
Given Z = 3000 + 300x1-250.x2we therefore select for the variable
entrantex1Indeed, it is the variable with the highest positive coefficient, and
besides the only possible one.
To determine the output variable, let's study the variation of the basic variables.
in
7
8
9
Common questions
Powered by AITransforming a linear maximization program into standard form is essential as it aligns the problem's constraints to be expressed as equations, accommodating the inclusion of slack variables . This transformation allows the application of structured algebraic methods of the simplex algorithm, facilitating easier manipulation of constraints and permits the straightforward tracking of variables and iterative improvements towards an optimal solution .
The stopping criterion for the simplex algorithm is met when all coefficients of the objective function are negative or zero when expressed solely in terms of non-basic variables. This indicates that no further positive adjustment can improve the objective, meaning the current solution is optimal . Alternatively, if no feasible vertex improves the objective value or maintains feasibility, the simplex recognizes that no solution exists. This criterion ensures that the algorithm either finds an optimal solution or determines that such a solution is impossible .
The use of an exchange equation in the simplex method maintains solution feasibility by re-expressing constraints as variables enter and exit the basis. This technique ensures that the new basic variables remain non-negative, obeying problem constraints . It carefully computes how changes in entering variables affect existing ones, maintaining feasibility across iterations, crucial for progressing towards optimal solutions without violating problem boundaries .
The simplex algorithm determines the entering variable by selecting the external variable with the highest positive coefficient in the objective function, as this will most rapidly improve the objective function . For the exiting variable, the choice is based on maintaining the non-negativity of basic variables; the outgoing variable must be the one with the smallest positive ratio when compared to the entering variable's coefficients . This careful selection ensures the progression towards an optimal solution while maintaining feasibility .
The initial basic feasible solution is critical because it serves as the starting point for the iterative process of the simplex algorithm. If the constraints are expressed as equalities, the origin can be used as a starting point, setting all decision variables to zero, and reading the initial values of slack variables directly from the equations . This initial state allows the algorithm to commence evaluating feasible solutions and iteratively improve upon them, crucial for ensuring the convergence of the algorithm to an optimal result .
Choosing the entering variable significantly impacts the simplex algorithm's efficiency in reaching an optimal solution. By selecting the variable with the highest positive coefficient from the objective function, the algorithm ensures that subsequent calculations maximize the step improvement in the objective value . This careful selection guides the trajectory towards optimality by enabling the largest feasible increase, thereby potentially reducing the number of iterations needed and minimizing computational expense .
Transforming inequalities into equations with slack variables is vital because the simplex method requires the linear program’s constraints to be expressed in the form of equations rather than inequalities . For example, the constraint x ≤ 4 can be transformed into the equation x + e = 4, where e is a non-negative slack variable representing how much of the constraint's limit is unused . This allows the constraints to be handled within the algebraic framework of standard linear programs .
The dictionary representation in the simplex algorithm provides a systematic way to track changes in the solution as variables enter and exit the basis. Each dictionary maintains the equations relating non-basic and basic variables, simplifying the calculation of new solutions as they iteratively adjust . The dictionary helps visualize the shifts from one vertex to another and assists in ensuring operations remain within the feasible region, crucial for maintaining solution viability and eventual optimization .
The simplex algorithm iteratively improves the value of the objective function by moving from one vertex of the feasible region to an adjacent one, ensuring improvement at each step via basis change, rather than evaluating every vertex . This contrasts with the impractical approach of evaluating each vertex, which would involve too many calculations in large-scale problems. Instead, the simplex identifies and moves along beneficial directions, thereby optimizing efficiently by working on a reduced problem space .
The primary challenge with the graphical method is its impracticality for programs with a large number of variables and constraints, as it requires examining an enormous number of vertices. For example, a program with 100 variables and 10 constraints may have over 1,730 billion vertices . The simplex algorithm addresses this issue through an iterative process that finds the optimal value by examining only a subset of the vertices efficiently, eventually leading to an optimal solution or proving that the feasible region is empty .