Skip to main content

SIMPLEX METHOD

Simplex method is an iterative procedure that allows to improve the solution at each step. This procedure is finished when it isn't possible to improve the solution.
Simplex method is based on the following property: if objective function, F, doesn't take the max value in the A vertex, then there is an edge starting at A, along which the value of the function grows.
You should take care about Simplex method only works with "≤" type inequality and independent coefficients higher or equal to zero, and you will have to standardize the restrictions for the algorithm. Case after this procedure "≥" o "=" type restrictions appear (or not modified) you should try other ways, being Two-Phase Simplex method the best choice.

Model of the problem is prepared to adapt it to the Simplex Method
This is the standard way of the model:
Objective function:
c1·x1 + c2·x2 + ... + cn·xn
Subject to:
a11·x1 + a12·x2 + ... + a1n·xn = b1
a21·x1 + a22·x2 + ... + a2n·xn = b2
...
am1·x1 + am2·x2 + ... + amn·xn = bm
x1,..., xn ≥ 0
To do this you must follow these rules:
  1. The objective must be a maximize or a minimize the function.
  2. All restrictions must be equal.
  3. All variables are non-negatives.
  4. The independent terms are non-negatives.



Changing the optimization type
If we want to minimize our model, we can keep it, but we must consider the new criteria for the halt condition (stop iterations when all coefficients in the value objective function row are less or equal to zero), and the leaving condition row. In order to not change criteria, we can convert the minimize objective function to maximize objective.
Advantages: We will not have to worry about halting criteria, or exit condition of rows, since they keep on.
Inconveniences/ Disadvantages :  In the event of the function having all its basic variables positive, and further the restrictions are inequality "≤", they become negative when doing the change and plus signs remain in the row of the value of the objective function, then Simplex method obeys the halting condition, and that optimal value would be obtained is 0, by default.
Solution: In fact this kind of problem does not exist, since so that the solution is greater than 0, any restriction should have the condition "≥", and then we would go into a model for the Two-Phase Simplex method(special condition).

Change in signs of constants to the right of restrictions
We will have to arrange our model so that the independent terms of restrictions will be greater or equal to 0, if not, Simplex method cannot be used. The only thing that would be necessary to do is multiply by "-1" the restrictions where independent terms be less than 0.
Advantages: With this simple modification of signs in restriction, we can use Simplex method.
Inconveniences: It can work out in restrictions where we have to modify the signs of constants, the signs of inequalities be ("=", "≤"), becoming ("=","≥") what in any event we will have to develop the Two-Phase Simplex method. This inconvenience is not controllable, although it would be able to benefit us only if terms of inequality exist ("≤","≥"), and terms "≥" coincide with restrictions where the independent term is negative.

Special Condition
If an inequality of the type "≥", appears in our model, will we have to add a new variable, called surplus variable si, with restriction si ≥ 0. The new variable appears with coefficient equal to zero in the objective function, and subtracting in inequalities.
A problem appears to us, let's see how to solve inequalities that contains an inequality type "≥"  :
a11·x1 + a12·x2 ≥ b1 -----> a11·x1 + a12·x2 - 1·xs = b1
As all our models based on that all his variables are greater or equal than zero, when we do the first iteration in the Simplex's model, the basic variables will not be in the base and they will take value zero, and all others will maintain their values. In this case our variable xs, after doing zero to x1and x2, will take the value - b1. The condition of not negativeness will not come true, so it will be necessary to add a new variable, xr, that will appear in the objective function with zero coefficient, and adding in the inequality of correspondent restriction. Would be left of the following way:
a11·x1 + a12·x2 ≥ b1 -----> a11·x1 + a12·x2 - 1·xs + 1 ·xr = b1
This type of variables are called artificial variables, and they will appear when there are inequalities with inequality ("=","≥"). This will take us compulsorily to accomplish the Two-Phase Simplex method, that will be explain later on.
Itself mode, if inequality has "≤" type, we will have to add a new variable, called slack variable si, with restriction si "≥" 0. The new variable appears with zero coefficient in the objective function, and adding up in the inequalities.
To sum up we can let this board, according to the inequality that appears, and with the value that the new variables must be with.
Type of inequality
Type of variable
≥
- surplus + artificial
=
+ artificial
≤
+ slack

Also, to solve the equations with the “≥” inequality, we can use another method apart from “Two Phase Method”. This method is known as “Big-M” Method. This will be explained later.
Labels:

Comments

Post a Comment

Popular posts from this blog

Advantages and Disadvantages of EIS Advantages of EIS Easy for upper-level executives to use, extensive computer experience is not required in operations Provides timely delivery of company summary information Information that is provided is better understood Filters data for management Improves to tracking information Offers efficiency to decision makers Disadvantages of EIS System dependent Limited functionality, by design Information overload for some managers Benefits hard to quantify High implementation costs System may become slow, large, and hard to manage Need good internal processes for data management May lead to less reliable and less secure data
1 comment
Read more

Inter-Organizational Value Chain

The value chain of   a company is part of over all value chain. The over all competitive advantage of an organization is not just dependent on the quality and efficiency of the company and quality of products but also upon the that of its suppliers and wholesalers and retailers it may use. The analysis of overall supply chain is called the value system. Different parts of the value chain 1.  Supplier     2.  Firm       3.   Channel 4 .   Buyer
Post a Comment
Read more

Big-M Method and Two-Phase Method

Big-M Method The Big-M method of handling instances with artificial  variables is the “commonsense approach”. Essentially, the notion is to make the artificial variables, through their coefficients in the objective function, so costly or unprofitable that any feasible solution to the real problem would be preferred, unless the original instance possessed no feasible solutions at all. But this means that we need to assign, in the objective function, coefficients to the artificial variables that are either very small (maximization problem) or very large (minimization problem); whatever this value,let us call it Big M . In fact, this notion is an old trick in optimization in general; we  simply associate a penalty value with variables that we do not want to be part of an ultimate solution(unless such an outcome is unavoidable). Indeed, the penalty is so costly that unless any of the  respective variables' inclusion is warranted algorithmically, such variables will ...
Post a Comment
Read more