Simplex method for operations research and simulation

The simplex method, whose great virtue is its simplicity, is a very practical method, since it only works with the coefficients of the objective function and the restrictions.

We will illustrate its operation by means of an example, but previously we will show the decision rules to determine the variable that enters, the one that leaves, the big M, and how to determine that we are in the optimum; All these decision rules were derived from the algebraic method, only here they have been arranged to be used in the type of simplex board to be used.

simplex-method-research-simulation-and-operations-1

TYPES OF RESTRICTIONS

Restrictions

A slack variable is added, with cost (or profit) in the objective function equal to 0.

Ejm:

2X1 - 4X2 <= 1, it remains:

2X1 - 4X2 + X3 = 1 Cj of X3 in the objective function will be 0.

Restrictions ³

An excess variable is subtracted, with cost (or profit) in the objective function equal to 0, and an artificial variable with cost + M or –M is added depending on whether it is maximization or minimization.

Ejm:

2X1 + 3X2> = 1, it remains:

2X1 + 3X2 - X3 + X4 = 1 Cj of X3 in the objective function will be 0. and Cj of X4 (artificial) is ± M

Constraints =

An artificial variable with cost + M or –M is added depending on whether it is maximization or minimization.

Ejm:

2X1 + 3X2 = 8, it remains:

2X1 + 3X2 + X3 = 8 Cj of X3 in the objective function will be ± M

Additionally, the following notes are presented to take into account:

If in the simplex board of the optimal solution there is at least one surplus or artificial variable within the basic variables, with a value> 0, the problem has no solution, this means that there are at least two exclusive restrictions, therefore There is no area of feasible solutions and less a solution, in this case the formulation of the problem should be reviewed.If when choosing the variable that comes out, none of the basic variables restricts the growth of the non-basic variable chosen to enter, the problem has indeterminate solution and the formulation should be reviewed in search of a new restriction that was not taken into account in the initial formulation. If in the simplex board of the optimum, at least one of the non-basic variables has zero coefficient (0) in the function target, this is your Zj - Cj = 0,the problem has multiple solutions and one of them is being offered to us.

Example 1

Xi being the quantity of product i to be produced.

Maximize Z = X1 + X2 {Total gain in soles}

5X1 + 3X2 <= 15 {Hours available dep. TO}

3X1 + 5X2 <= 15 {Hours available dep. B}

Xj> = 0; j = 1, 2

The Maximization problems, with all their restrictions <= and with the condition of non-negativity, are called Standard Form or Normal Form

Here we must achieve a feasible basic solution, using the slack and / or artificial variables, leaving the system of equations like this:

Maximize Z = X1 + X2

5X1 + 3X2 + X3 = 15

3X1 + 5X2 + X4 = 15

Xj> = 0; j = 1,2,3,4

The basic variables are those whose coefficients form the unit matrix.

In this chaos accidentally are the slack variables X3 and X4.

The value of the objective function Z, is in front of the box of Zj - Cj, in this case it is worth zero (0) and is calculated by multiplying the row vector (in the table it is the column immediately before that of the basic variables VB) that contains the coefficients of the basic variables in the original objective function by the column vector of the independent terms b

CX _B = Vector row of the coefficients in the original objective function of the current basic variables, their values are in the first column of the board.

b = Column vector of the independent terms of the constraints, which at the same time are the values of the current basic variables, their values are found under the column called b

CX _B = (0.0); b = (15,15) ' Z = CX _B * b = (0) (15) + (0) (15) = 0

The value of the Zj - Cj is calculated multiplying the row vector CX _B by the pointing vector aj of the column of the j-th variable, minus the Cj, that is:

Zj - Cj = CX _B. aj - Cj;

The calculations are carried out as follows:

Z1 - C1 = CX _B a1 - C1 = (0,0). (5,3) '- 1 = (0) (5) + (0) (3) - 1 = -1

Z2 - C2 = CX _B a2 - C2 = (0,0). (3,5) '- 1 = (0) (3) + (0) (5) - 1 = -1

Z3 - C3 = CX _B a3 - C3 = (0,0). (1,0) '- 0 = (0) (1) + (0) (0) - 0 = 0

Z4 - C4 = CX _B a4 - C4 = (0,0). (0,1) '- 0 = (0) (0) + (0) (1) - 0 = 0

The variable that comes out and the variable that comes in are listed below:

Cj	one	one	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
0	X3	fifteen	5	3	one	0	15/5 = 3
0	X4	fifteen	3	5	0	one	15/3 = 5
Zj - Cj	0	-one	-one	0	0

Variable input X1

Variable output X3

The variable that has the most negative Zj-Cj is either X1 or X2. X1 is chosen at random.

In this iteration b / a gives: 15/5 = 3 and 15/3 = 5;

This means that the basic variable X3 restricts the growth of the input variable, X1, to 3 (it does not allow it to take values higher than 3) and the basic variable X4 restricts the growth of the input variable X1 to 5 (not the lets take values higher than 5).

Of course the basic variable that restricts the growth of the input variable X1 the most is X3, therefore, it is the basic variable chosen to leave.

The row of the basic variable chosen to exit is divided by the element that is at the intersection of said row with the column of the input variable, the resulting row is the pivot row and is placed on a new board, from which multiples of the pivot row are added to the other rows of the previous board in such a way that the variable chosen to enter is eliminated from each of them, in our case X1, this procedure is called, make a one (1) in the intersection and the rest of the column zeros (0), therefore a unit vector will appear in said column, the procedure is repeated in each iteration, until all the Zj - Cj are greater or equal to zero in the case of maximizing or less or equal to zero in the case of minimizing.

Below are all the iterations and in each row the values by which they were multiplied to be added to other rows, this is expressed as adding multiples from one row to another.

Notice that multiples of the constraints are added to the objective function to eliminate the basic variables from it.

Cj	one	one	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
one	X1	3	one	3/5	1/5	0	5
0	X4	6	0	16/5	-3/5	one	8/15
Zj - Cj	3	0	-2/5	1/5	0

Variable input X2

Variable output X4

Cj	one	one	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
one	X1	8/15	one	0	5/16	0
one	X2	8/15	0	one	-3/16	5/16
Zj - Cj	15/4	0	0	1/8	1/8

Optimal solution:

X1 * = 15/8

X2 * = 15/8

Z * = 15/4

The solution is unique: X1 * = 15/8; X2 * = 15/8; Z * = 14/4

Example 2

Minimize Z = 6X1 + 4X2 + 2X3

6X1 + 2X2 + 6X3> = 6

6X1 + 4X2 = 12

2X1 - 2X2 <= 2

Xj> = 0; j = 1, 2, 3

Minimize Z = 6X1 + 4X2 + 2X3 + MX5 + MX6

6X1 + 2X2 + 6X3 - X4 + X5 = 6

6X1 + 4X2 + X6 = 12

2X1 - 2X2 + X7 = 2

Xj> = 0; j = 1, 2, 3, 4, 5, 6, 7

The basic variables are X5 = 6, X6 = 12, X7 = 2

Optimal solution:

Decision variables:

X1 = 0, X2 = 3, X3 = 0, Z = 12

Slack variables: X4 = 0, X7 = 8

Artificial variables: X5 = 0, X6 = 0

A BREAKTHROUGH OF POST-OPTIMAL ANALYSIS

Maximize Z = X1 + X2 {Total gain in soles}

5X1 + 3X2 <= 15 {Hours available dep. TO}

3X1 + 5X2 <= 15 {Hours available dep. B}

Xj> = 0; j = 1, 2

Optimal board:

Cj	one	one	0	0	b / a a> 0
	VB	b	X1	X2	X3	X4
one	X1	8/15	one	0	5/16	0
one	X2	8/15	0	one	-3/16	5/16
Zj - Cj	15/4	0	0	1/8	1/8

Optimal solution:

X1 * = 15/8

X2 * = 15/8

Z * = 15/4

Reduced cost:

Units = (monetary unit) / (product unit) = (um) / (up) = the same units as Cj

Dual price:

Units = (monetary unit) / (resource unit) = (um) / (ur)

Interpretation of the reduced cost:

In how many monetary units the objective function worsens when producing a unit of a product that is not being produced.

In minimization: (Dz / Dx) In maximization: (Ñz / Dx)

If the variable is basic, the reduced cost is 0. If the variable is non-basic, it is> = 0. When it is 0 it means alternative solutions.

Interpretation of Dual Price:

In how many monetary units will the objective function vary by varying in a limiting resource unit.

When it is> 0: (Dz / Db) or (Ñz / Ñb)

When it is <0: (Dz / Ñb) or (Ñz / Db)

A constraint is limiting when it limits the objective function. This happens when the equality of the constraint is satisfied.

If the constraint is non-limiting, the dual price is 0.

If the constraint is limiting, it can take any positive, negative, or 0 value.

DISSECTED ANIMALS

A Stuffed Animals Company is producing stuffed pigeons and hawks. In the current market conditions, he can sell hawks and pigeons with profits of $ 20.00 and $ 12.00 respectively.

The skins of hawks are tougher and take more time to work than the skins of pigeons. The fur machine can handle 4 hawk skins per minute or 8 pigeon skins, using the same capacity. The filling line can fill 5 hawks or 4 pigeons per minute. The hawks go to a final operation in a beak sharpening machine that has a capacity of 3.5 hawks per minute. The working day in the division is 8 hours.

Formulate the linear programming model, which solves the case. Formulate the dual problem of the model formulated in (a). Solve the model, and make an administrative interpretation of the solution. Determine the optimal solution of the dual problem by reading it directly from the optimal table. found in question c.

Unless specified otherwise, the following questions are independent of each other and are based on the initial statement of the problem.

There is the possibility of working overtime on the leather machine, on the filling line, and on the sharpening machine. What is the greatest profit that is generated for each overtime in each of the sections? The Company Manager visits the line of hawks and pigeons, and observes that there is idle capacity in some of the processes. He resolved to order that all the centers of the process be used, in all their installed capacity. What would you say to him? What would happen to the optimal solution if the profits for each pigeon fall as /. 9.00?.To give a better finish to the toys, a lacquering line has been installed; the lacquering line can fill 5 hawks per minute or 4 pigeons at the same time, also the day is 8 hours. Would it affect the optimal solution ?; if so, find the new solution.

THEORETICAL NOTE:

In this question, observe if the new restriction is fulfilled by the current solution, if so, it would be a redundant restriction and does not affect the current solution, but if the current solution does not comply with it, then it will be necessary to solve the problem again considering this new restriction.

MODEL:

X1 = number of pigeons to produce in the day

X2 = number of hawks to produce in the day

MAX 12X1 + 20X2

SUBJECT TO

0.125X1 + 0.25X2 <= 480 fur machine

0.25X1 + 0.2X2 <= 480 fill line

0.2857143X2 <= 480 peak sharpening

END

LP OPTIMUM FOUND AT STEP 2

OBJECTIVE FUNCTION VALUE

1) 39680.00