Linear Programming And The Simplex Method Computer Science Essay

Published:

This essay has been submitted by a student. This is not an example of the work written by our professional essay writers.

A linear programming (LP) problem in mathematics, is one in which we are to find the maximum or minimum value of a linear function, subject to a number of linear constraints which may take the form of equalities and inequalities.

The function that we wish to maximize or minimise is referred to as the "objective function", in more general terms we wish to optimise the function. In order to do this, the real or integer values of the solution that correspond to the solution being optimal are systematically chosen from within an allowed set.

Below is a simple example.

Maximize π = x1 + x2

Subject to the constraints:

x1 + x2 ≤ 4

4x1 + 2x2 ≤ 12

-x1 + x2 ≤ 1

x1 ≥ 0

x2 ≥ 0

This LP problem contains five constraints in two unknowns. All of the constraints are inequalities and are linear, as the inequality involves a linear function of the unknowns. The constraints x1 ≥ 0, x2 ≥ 0 are called non-negativity constraints, and are often included in the formulation of LP problems. The other constraints are called the main constraints. The objective function in this case is x1 + x2, which should be maximized according to this formulation.

Since there are only two unknowns, this method may be solved using a graphical approach. This would involve plotting a graph of the set of points that satisfy all the constraints, which would form a plane. The values that would satisfy the constraints are called the constraint set. The feasible region of solutions is the region under the lines of the constraints that satisfy all of the constraints.

The point needed that gives the optimal solution and achieves the maximum of x1 + x2 is the point (x1, x2). The objective function is constant on lines with gradient -1, for example the line x1 + x2 =1. The point that is needed to achieve the maximum of the objective function is therefore the point on the line of gradient -1 that is furthest from the initial starting point at the origin and also still touches the feasible region, or constraint set. This point is on the intersection of the lines x1 + 2x2 =4, and 4x1 + 2x2 =12, which corresponds to the point (x1, x2 ) =( ,. The value of the objective function at this point is then = + = .

In general, a linear objective function always takes on a maximum or minimum value at a corner point of the feasible region, or constraint set, provided it is bounded. Occasionally, an entire edge of the feasible region or constraint set can correspond to the maximum.

When many constraints and many unknowns are involved an LP problem may not be so easily formulated. Some variables may be constrained, while others have no bound. However, here two types of formulations help simplify the problem; these are the "Standard Maximum Problem" and the "Standard Minimum Problem". In these types of problems all the variables have non-negativity constraints and all the main constraints are inequalities.

Problems involving two or more variables are beyond the scope of the two-dimensional graphical approach. This is when the simplex method needs to be introduced (Ferguson, 2010).

4.2 The Simplex Method

The Simplex Method is an algorithm that systematically finds the optimal solution to a LP problem (Dantzig, 1947). The algorithm checks adjacent corners of the feasible region, (constraint set) which provide basic feasible solutions and tests whether or not the new solution is optimal. When moving to any adjacent corner gives no improvement, the solution has been found. Any variables set to zero in a particular solution are referred to as 'not in the basis' whereas those variables with a non-zero value at a particular solution are referred to as 'in the basis' or 'basic solutions'.

The next section will outline the procedure for maximization problems, with minimisation problems being discussed directly after. For this method, the set of linear inequalities must be converted to a system of linear equations, by introducing a different 'slack' variable to each inequality. A slack variable represents the difference between the linear expression on the left of the inequality and its maximum value.

An inequality of the form 'less than or equal to' such as 2x1 + 3x2 + 6x3 ≤ 480 can be transformed in to an equation by adding a slack variable. So the inequality becomes a linear equation of the form 2x1 + 3x2 + 6x3 + s1= 480. If the inequalities are satisfied, the slack variable cannot be negative.

If the inequality was of the form 'greater than or equal to' then the equality is transformed by subtracting a surplus variable. For example, the inequality 2x1 + 3x2 + 6x3 ≥ 480 would become the linear equation 2x1 + 3x2 + 6x3 - s1 = 480.

4.3.1 Formulating a Maximization Problem

The following example shall be used in order to show the maximization of an objective function using the Simplex Method.

Maximize π = 5x1 + 7x2 + 10x3

Subject to the constraints

2x1 + 3x2 + 6x3 ≤ 480

2x1 + 2x2 + 3x3 ≤ 360

3x1 + 2x2 + 2x3 ≤ 240

x1 ,x2 ,x3 ≥ 0

Firstly convert the inequalities to equations, as outlined in Section 4.2 by the addition of 3 slack variables; s1, s2 and s3. The slack variable in this problem may be thought of as the amount of resource that is unused.

2x1 + 3x2 + 6x3 + s1 = 480

2x1 + 2x2 + 3x3 + s2 = 360

3x1 + 2x2 + 2x3 +s3 = 240

Next, set up an initial simplex tableau. The initial tableau represents the first basic feasible solution, at the origin, when x1, x2 and x3 are all equal to zero. The tableau is comprised of the coefficient matrix of the constraint equations, to the right is a column vector of the constants which appear on the right hand side of the constraint equations, and the top row of the tableau is the coefficients of the objective function, the coefficients are entered as negative values. The slack variables all enter the basic solution with coefficient zero, as does the constant column that corresponds to the objective function, as shown below:

x1

x2

x3

s1

s2

s3

Constant

Ï€

-5

-7

-10

0

0

0

0

s1

2

3

6

1

0

0

480

s2

2

2

3

0

1

0

360

s3

3

2

2

0

0

1

240

Tableau 4.1: Initial Simplex Tableau.

In order to increase the value of the objective function, a new basic solution is considered. To move to a new basis, a new variable must enter the basis, and one of the initial variables in the basis must leave. The process of selecting the variable to enter the basis and the variable that leaves the basis is called 'change of basis'. The largest negative value in the objective function decides which variable enters the basis. In this example, x3 is the variable that will enter the basis, as determined by the -10 value in the objective function. The x3 column then becomes the pivot column for the next tableau.

The variable that will leave the basis in order to make way for x3 is determined by the 'displacement ratio'. The displacement ratio is found by dividing the elements of the constant column by the elements of the pivot column. The row with the smallest, positive displacement ratio will determine the variable to leave the basis, and will become the pivot row.

x1

x2

x3

s1

s2

s3

Constant

Ratio

Ï€

-5

-7

-10

0

0

0

0

0

s1

2

3

6

1

0

0

480

80

s2

2

2

3

0

1

0

360

120

s3

3

2

2

0

0

1

240

120

Tableau 4.2.

Since the smallest, positive displacement ratio is in the row of s1, the variable s1 will leave the basis. The s1 row will now become the pivot row. The intersection of the pivot row and pivot column is called the pivot element, which is in this case 6.

In order to produce the next tableau to examine the next feasible solution, a process called 'pivoting' must take place. Pivoting involves converting the pivot element to a one, and all other elements in the pivot column to a zero, as in the Gaussian elimination method of finding an inverse matrix.

Firstly, replace the s1 with an x3 as x3 as this is the variable that will enter the basis. Now, to transform the pivot element in to a one, the entire row will be multiplied by the reciprocal of the pivot element. In this example, multiply row x3, (previously named row s1) of tableau 4.2 by

x1

x2

x3

s1

s2

s3

Constant

Ï€

-5

-7

-10

0

0

0

0

x3

0.33333

0.5

1

0.16667

0

0

80

s2

2

2

3

0

1

0

360

s3

3

2

2

0

0

1

240

Tableau 4.3

Now that the pivot element has been converted to a one, the rest of the pivot column must be converted to zero elements. This is done for each row (including the objective function row) separately using the new pivot row, such that:

New equation = old equation - entering column coefficient * new pivot equation

The next tableau is shown below:

x1

x2

x3

s1

s2

s3

Constant

Ï€

-1.6667

-2

0

1.66667

0

0

800

x3

0.33333

0.5

1

0.16667

0

0

80

s2

1

0.5

0

-0.5

1

0

120

s3

2.33333

1

0

-0.3333

0

1

80

Tableau 4.4

Now, the steps are repeated, the most negative coefficient in the objective function is now -2, and so x2 will enter the new basis. The variable that will leave the basis is determined by the smallest, positive displacement ratio.

x1

x2

x3

s1

s2

s3

Constant

Ratio

Ï€

-1.6667

-2

0

1.66667

0

0

800

-

x3

0.33333

0.5

1

0.16667

0

0

80

160

s2

1

0.5

0

-0.5

1

0

120

240

s3

2.33333

1

0

-0.3333

0

1

80

80

Tableau 4.5

As can be seen in Tableau 4.5 above, the smallest, positive displacement ratio is 80 which correspond to row s3; therefore, x2 will enter the new basis in place of s3.

Using the procedure from before, transforming the pivot element which is in this case already a one, and all other elements in the pivot column to a zero. As the pivot element is already a one, the pivot row does not need to be transformed, and can be wrote in to the tableau as it is. The following tableau is formed next:

x1

x2

x3

s1

s2

s3

Constant

Ï€

3

0

0

1

0

2

960

x3

-0.8333

0

1

0.33333

0

-0.5

40

s2

-0.1667

0

0

-0.3333

1

-0.5

80

x2

2.33333

1

0

-0.3333

0

1

80

Tableau 4.6

As there are no negative coefficients left in the objective function, this is the final tableau and the optimal solution has been found. The maximum for the objective function is equal to 960, as taken from the constant column value in the objective function row.

Also, this tableau can tell us how many of each variable are created to reach this maximum, x3 is present in the basis, and has a constant value of 40, this shows us that 40 of x3 are needed to achieve the maximum. The variable x2 is also present in the basis, with a constant value of 80; therefore 80 of x2 are needed to reach this maximum. As the variable x1 is not in the basis, this tells us that in order to reach the optimum the value of x1 must be zero. Also, there is a slack variable, s2 present in the basis, this tells us that there are 80 units of slack, or unused resources in relation to the constraint that contains s2.

4.3.2 Formulating a Minimisation Problem

A minimisation problem is formulated in almost the same way as that of a maximization problem. However, when the inequalities are of the form 'greater than or equal to' a surplus variable is subtracted from the left hand side, thus transforming each linear inequality into a linear equation as described in Section 4.2. The initial and subsequent tableaus are then created in the same way as in the maximization problem outlined in Section 4.2.1.

4.4 - Using a Computer Package

As can be seen, the Simplex algorithm can be quite time consuming to do by hand especially when there are multiple variables involved. For this reason, a computer package is most often used to implement the algorithm.

4.4.1 - Xpress-MP

The chosen package for this report is Xpress-MP. Xpress-MP is a mathematical modelling and optimization software. Xpress-MP provides the user with tools to formulate and solve linear, quadratic and integer programming problems. The two main components of Xpress-MP are Xpress-Mosel and Xpress-Optimizer. Xpress-Mosel is the environment for modelling the problems whilst Xpress-Optimizer recognises the best way in which to solve the problem.

Xpress-Interactive Visual Environment (Xpress-IVE) is the graphical user interface for Microsoft Windows operating systems. Xpress-IVE brings Xpress-Mosel and Xpress-Optimization together to give a simple development environment in which to learn about and use the function and features of the Xpress-MP suite.

The usefulness of Xpress-MP comes from the ability of the program to recognise a model's structure and to distinguish between its various components. This allows the user to be made aware of any errors in the program, including usually, typing errors. This feature can save debugging time and can allow for typographical errors to be identified and immediately corrected.

Xpress-MP is able to effectively perform the simplex algorithm. However, it should be noted that when inputting the problem to the Xpress-MP interface there is no need to add the slack and surplus variables to transform inequalities to equalities as the Xpress-MP program does this for the user.

Consider the maximization problem from Section 4.3.1

Maximize π = 5x1 + 7x2 + 10x3

Subject to the constraints

2x1 + 3x2 + 6x3 ≤ 480

2x1 + 2x2 + 3x3 ≤ 360

3x1 + 2x2 + 2x3 ≤ 240

x1,x2 ,x3 ≥ 0

This problem can be solved using the Xpress-IVE interface. First the variables must be declared to the program, for this model the variables are x1,x2 ,x3.

The variables are input using the following code:

declarations

X1 : mpvar

X2 : mpvar

X3 : mpvar

end-declarations

Also notice that the writing highlighted in blue here is recognised by Xpress-MP as key words of the language. These must be included for the program to recognise the variables in the problem.

The next step is to input the constraints of the problem. Once again please note that there is no requirement to convert the constraints from inequalities to equalities as the Xpress MP package can deal with the inequalities, saving the user time. The constraints are input in the following way:

2*X1 + 3*X2 + 6*X3 <= 480

2*X1 + 2*X2 + 3*X3 <= 360

3*X1 + 2*X2 + 2*X3 <= 240

As can be seen above, any mathematical symbols and numbers are coloured red. This allows the user to be able to distinguish between mathematical symbols and variables and also to allow faster location of mathematical symbols and numbers within the program.

The next step is to add the objective function to the program. This is the function which is being maximized, or minimized, in the problem. The objective function must be given a name, it is normal to relate its name to the problem, for example, profit or cost. For this example as we are maximizing the objective function the objective function shall be named "profit". It is then input in the following way:

profit:= 5*X1 + 7*X2 + 10*X3

After defining the objective function, we must now declare whether this is a maximization or minimization problem. This is done in the following way:

For a maximization problem:

maximize(profit)

Conversely, for a minimization problem:

minimize(profit)

Finally, we must determine what results are to be printed and displayed to the answer. Usually the objective function value would be required, along with the value of each variable that gives this optimum result.

Using the command "writeln" which means print in Xpress-MP, we input the following:

Writeln("Profit is £", getobjval)

Using the above code gives a user friendly output. Instead of just displaying the value of the objective function and not indicating exactly what the displayed value represents, this code allows the user to see the value of the objective value displayed in £ for this example, along with the introduction "Profit is". Using the above code will produce the following output to the user:

Profit is £ (value of objective function)

Thus anything between inverted commas is printed as it is seen.

Also, as mentioned above, the user often requires the values of each variable that produce the optimum. In order to display the values of X1, X2 and X3 similar coding has to be implemented. However, we need to inform the program that we want the solutions of X1, X2 and X3 this is done using the following code:

writeln("X1 is :", getsol(X1))

writeln("X 2 is :", getsol(X2))

writeln("X 3 is :", getsol(X3))

The command "getsol" is what informs Xpress-MP that it needs to determine the values of each variable and display the answer to the user.

The last command needed is to inform Xpress-MP that this is the end of the problem, and so the following needs to be placed after the final command to print the solutions:

end-model

Xpress-MP also allows the user to input comments to the program. These are done by first inserting an exclamation mark and then writing the comment, you will notice that these will be displayed in green. Comments are useful for the user to remember what has been done and also for others to understand the program. They can be used to define where constraints and solutions are in longer more complex variables or also to include comments as to the nature of the variables and or what they represent. Anything wrote after an exclamation mark on that line is ignored by the program and does not affect the running of the program.

Figure 4.4.1 shown below is a screen shot of the above example. Within this program you will see comments have been added to allow the program to be easily understood as the sections of inputting the problem have all been separated.

Figure 4.4.1: Screenshot Xpress-MP formulation

In order to run the program, the small play button located on the tool bar just below "modules" must be pressed. When this has been done, a list of answers should be displayed in the right hand side screen as shown below in Figure 4.4.2.

Figure 4.4.2: Screenshot Xpress-MP answers

By comparing the information provided by Xpress-MP to that determined in the simplex example done by hand, you can see that the answers given are the same, thus Xpress-MP has carried out the simplex algorithm effectively, and in a much faster time.

4.5 - Summary

This chapter has introduced Xpress-MP as a tool for solving the simplex algorithm in a more time effective way. There has been a brief introduction in to how Xpress-MP operates and what results can be produced by the program. For more complex problems with many more variables, performing the simplex algorithm by hand is an exhausting task and so the simplex algorithm shall be performed by using Xpress-MP for the remainder of this project.

Writing Services

Essay Writing
Service

Find out how the very best essay writing service can help you accomplish more and achieve higher marks today.

Assignment Writing Service

From complicated assignments to tricky tasks, our experts can tackle virtually any question thrown at them.

Dissertation Writing Service

A dissertation (also known as a thesis or research project) is probably the most important piece of work for any student! From full dissertations to individual chapters, we’re on hand to support you.

Coursework Writing Service

Our expert qualified writers can help you get your coursework right first time, every time.

Dissertation Proposal Service

The first step to completing a dissertation is to create a proposal that talks about what you wish to do. Our experts can design suitable methodologies - perfect to help you get started with a dissertation.

Report Writing
Service

Reports for any audience. Perfectly structured, professionally written, and tailored to suit your exact requirements.

Essay Skeleton Answer Service

If you’re just looking for some help to get started on an essay, our outline service provides you with a perfect essay plan.

Marking & Proofreading Service

Not sure if your work is hitting the mark? Struggling to get feedback from your lecturer? Our premium marking service was created just for you - get the feedback you deserve now.

Exam Revision
Service

Exams can be one of the most stressful experiences you’ll ever have! Revision is key, and we’re here to help. With custom created revision notes and exam answers, you’ll never feel underprepared again.