How to Solve a Linear Programming model with OpenSolver

OpenSolver is a great Excel Add-in that solves optimization models. The following article will describe how to solve a Linear Programming model using this tool (first you must Download and install OpenSolver in Excel). For educational purposes we will consider a linear programming model with two decision variables and four constraints, nevertheless you can easily extend its application to larger problems.

Maximize 30X+20Y

Subject to:

  • 5X+2Y\leq 140
  • 3X+2Y\leq 120
  • X,Y\geq 0

We will then need to prepare an Excel spreadsheet that includes the model’s parameters and variables (this step is similar to loading a problem in Frontline’s Solver). You can see that cells B2 and C2 (yellow color) have been assigned as the decision variables and cell E2 corresponds to the objective function (blue cell), which is a formula that links the decision variables to their respective parameters. Finally cells D5 and D6 are formulas that represent the “left-hand side (LHS)” of the problem’s constraints (for example, cell D5 corresponds to B2*B5+C2*C5 or equivalently SUMPRODUCT(B2:C2;B5:C5)).

opensolver objective function

Once the previous step has been completed you must run OpenSolver, whose menu can be accessed from the “Data” tab in Excel. Then select “Model…” as shown below:

opensolver menu

The interface for implementing the model is quite similar to the traditional Solver (Frontline) version. The objective cell is defined (E2) in maximization; next you must select the range of decision variables (as shown in the following image) and the constraints. If you try to replicate the structure of the example we are going over in this article, then it should look like this:

opensolver model

Then we select “Save Model” (the structure of the template will change and become different colors, one of the characteristics OpenSolver has that makes this Add-in such a intuitive tool for the user).

opensolver excel

Finally we select “Solve”:

solve opensolver

The program is run and gives us the optimal solution (X=0 and Y=60) and the optimal value V(P)=1,200 for the optimization problem:

optimal solution opensolver

The results achieved are consistent with those obtained in the graphical solution of the problem that we went over in the article “What does a Shadow Price of Zero mean in Linear Programming” as shown in the following image:

infinite solutions

Below you can download the file that contains OpenSolver’s solution to this problem so that you can familiarize yourself with this Excel Add-in: OpenSolver Excel.

Production and Inventory Problem solved using Solver in Excel

Linear Programming allows us to tackle various real life problems, some of which we have already gone over in previous articles, such as the Transportation Problem, the Product Mix Problem and the Diet Problem. In the following article we will analyze a different classic application known as the Production Inventory Problem.

This problem is essentially used for establishing a policy for production within a time period that satisfies certain demand requirements, respecting the manufacturing limits and at a minimal cost. These types of models can be extended to use with several products, however, for this example we will only consider one single product:

production and inventory problem

We define the following linear optimization model: (Given: there is an initial inventory of 50 units => I0=50).

1. Decision Variables:

Xt: Units to produce in month t (t=1,…,6 with t=1 =>January; t=6=>June)
It: Units to be stored as inventory until the end of month t (t=1,…,6 with t=1 =>January; t=6=>June)

2. Objective Function: Minimize the production and inventory costs during the planning period, defined as: 60X1 + 60X2 + 55X3 + 55X4 + 50X5 + 50X6 + 15I1 + 15I2 + 20I3 + 20I4 + 20I5 + 20I6

3. Constraints:

Satisfy the demand requirements (known as the inventory balance constraint):

  • X1 + 50 – I1 = 100 (January)
  • X2 + I1 – I2 = 130 (February)
  • X3 + I2 – I3 = 160 (March)
  • X4 + I3 – I4 = 160 (April)
  • X5 + I4 – I5 = 140 (May)
  • X6 + I5 – I6 = 140 (June )

Respect the monthly production maximum capacity:

  • X1 <= 120   X2 <= 120   X3 <= 150   X4 <= 150   X5 <= 150   X6 <= 150

Non-negativity conditions:

  • Xt >= 0       It >= 0    For all t.

The following tutorial demonstrates how to implement this Linear Programming model using Solver in Excel:

The optimal solution is shown below with an optimal value of $43,450. One can see that a total of 780 units are produced between January and June, which together with the initial inventory of 50 units satisfies the monthly demand requirements.

optimal solution production and inventory

Would you like to receive the Excel file with Solver’s solution to this problem? get free and immediate access to the file now: Production and Inventory

What does a Shadow Price of Zero mean in Linear Programming

As we have discussed in previous articles, the Shadow Price of a constraint represents the rate of change of the optimal value as a result of a marginal change in the right-hand side of a constraint. “Marginal” is understood as a modification that does not change the geometry of the problem, that is to say, the new optimal solution can be found by solving the system of equations that led to the original active constraints (previously updating the parameter we are modifying). In this context the shadow price can be a value that is positive, negative or zero, in this article we will be referencing the latter.

Consider the following Linear Programming model in 2 variables:

lp infinite solutions

The previous problem can be solved graphically using Geogebra, which generates a problem with infinite optimal solutions in the section of the straight line that connects vertexes B and C and can be generally described as: (X,Y)= λ(0.60)+(1- λ)(10.45) with λ in the interval between [0,1]. The optimal value is therefore V(P)=1,200.

infinite solutions

What are the active constraints at the optimal? If we consider for example vertex B (optimal solution), the active constraints are 3X+2Y<=120 and X>=0, nevertheless if we select vertex C (also optimal solution) the active constraints are 5X+2Y<=140 and 3X+2Y<=120.

Given the previously stated, will the optimal value increase if there are additional resource units available representing the right-hand side of the constraint 5X+2Y<=140? In order to answer this we try and keep the constraints of vertex C active by identifying the maximum variation (increasing the value of the right-hand side) that retains the original active constraints (this will produce a parallel shift of the constraints that we have shown with the red color dotted line) which is attained at the coordinate (X,Y)=(40,0). Similarly in order to determine the minimal variation for the right-hand side, we move the constraint in a decreasing direction to the coordinate (X,Y)=(0,60) trying to maintain the original active constraints (orange color dotted line).

zero shadow price

We evaluate this result in the following formula in order to calculate the Shadow Price value, obtaining the following:

shadow price zero

Therefore the shadow price of constraint 1 (5X+2Y<=140) is zero, which indicates that if the value of the parameter representing its right-hand side increases or decreases (currently b1=140) in the interval between [120,200] the optimal value of the problem will not be affected. The above is consistent with what was obtained using the confidentiality analysis of constraints by Solver in Excel:

shadow price zero in solver

In general a Shadow Price equaling zero means that a change in the parameter representing the right-hand side of such constraint (in an interval that maintains the geometry of the problem) does not have an impact on the optimal value of the problem. Nevertheless, there are special cases like the Linear Programming problems that support infinite solutions (like the one described in this article) where a constraint with a shadow price of zero can be active in one of the optimal vertexes (the most common case is a constraint with a shadow price of zero that is not active in the optimal).

What is a Degenerate Optimal Solution in Linear Programming

When applying the Simplex Method to calculate the minimum coefficient or feasibility condition, if there is a tie for the minimum ratio or minimum coefficient it can be broken arbitrarily. In this instance, at least one basic variable will become zero in the following iteration, confirming that in this instance the new solution is degenerate. The practical implication of this condition indicates that the model has at least one redundant constraint.

Degenerate Optimal Solution

Let’s consider the following Linear Programming model which we will solve using the Simplex Method and which we will also represent graphically with Geogebra:

Degenerate Optimal Solution LP

We put the above problem in its minimized standard form, adding x_{3} and x_{4}, as slack variables for constraints 1 and 2, respectively.

standard-Degenerate-Optimal

Which produces the following Simplex Method initial tableau:

initial tableau Degenerate Optimal Solution

To facilitate the fast convergence of the algorithm we select x_{2} as the entering variable. Next we calculate the feasibility criteria (smallest coefficient): Min\begin{Bmatrix}\frac{8}{4};\frac{4}{2}\end{Bmatrix}=2 (if a tie exists we arbitrarily select variable x_{3} as the variable that leaves the basis. Then we update the tableau:

simplex Degenerate Optimal Solution

Now x_{1} enters the basis. The feasibility criteria determines that: Min\begin{Bmatrix}\frac{2}{1/4};\frac{0}{1/2}\end{Bmatrix}=0 x_{4}  leaves the basis. A new iteration is made:

Degenerate Optimal Solution simplex

The degenerate optimal solution is reached for the linear problem. Note that x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18. As this is a two-dimensional problem, the solution is overdetermined and one of the constraints is redundant just like the following graph confirms:

Degenerate Optimal Solution

In practice knowing that some resources (like those associated with a constraint) are superfluous can be useful during the implementation of a solution. From a theoretical point of view, the degeneration has two implications: it produces the cycling or circling phenomenon (it’s possible that the Simplex Method repeats a series of iterations without ever improving the value of the objective function and the calculations are interminable, as can be observed in the previous example); the second theoretical aspect arises when iterations 1 and 2 are examined. Although they differ in the classification of basic and nonbasic variables, both produce identical values for all variables and for the objective value x_{1}=0, x_{2}=2, x_{3}=0, x_{4}=0, V(P)=18.

 

Vogel Approximation Method (Transportation Algorithm in Linear Programming)

The Vogel Approximation Method is an improved version of the Minimum Cell Cost Method and the Northwest Corner Method that in general produces better initial basic feasible solution, which are understood as basic feasible solutions that report a smaller value in the objective (minimization) function of a balanced Transportation Problem (sum of the supply = sum of the demand).

Applying the Vogel Approximation Method requires the following steps:

Step 1: Determine a penalty cost for each row (column) by subtracting the lowest unit cell cost in the row (column) from the next lowest unit cell cost in the same row (column).

Step 2: Identify the row or column with the greatest penalty cost. Break the ties arbitrarily (if there are any). Allocate as much as possible to the variable with the lowest unit cost in the selected row or column. Adjust the supply and demand and cross out the row or column that is already satisfied. If a row and column are satisfied simultaneously, only cross out one of the two and allocate a supply or demand of zero to the one that remains.

Step 3:

  • If there is exactly one row or column left with a supply or demand of zero, stop.

  • If there is one row (column) left with a positive supply (demand), determine the basic variables in the row (column) using the Minimum Cell Cost Method. Stop.

  • If all of the rows and columns that were not crossed out have zero supply and demand (remaining), determine the basic zero variables using the Minimum Cell Cost Method. Stop.

In any other case, continue with Step 1.

Vogel Approximation Method Example

Let’s reconsider a balanced transportation problem that has 3 supply sources (silos) and 4 demand sources (mills). The numerical values in the upper right-hand corner of each box, from now on , represent the per unit transportation cost from silo i to mill j. For example, c_{ij} is the per unit transportation cost from silo 1 to mill 1.

Vogel Approximation Method

Based on what we previously described, the first step consists of calculating the penalty cost for each row and column of the tableau that represents the previous transportation problem. For example, in row 1 the lowest cost is $2 and the next lowest unit cost is $10. Thus the penalty cost for that row is $8 ($10-$2). The same calculation is replicated for each row and column of the tableau, which is trivial, and gets the following results (the penalty costs of the respective rows and columns have been marked in orange for clarity):

example vogel method

Since row 3 has the highest penalty cost ($10) and the cell corresponding to x_{31} has the lowest unit cost of that row, 5 units are allocated to x_{31} (it is unnecessary to do more even when the capacity of silo 3 would allow it given that the demand for mill 1 is only 5 units). In doing so column 1 should be crossed out (we have marked it in yellow) and next comes the calculation of the new penalty costs as shown below:

Now the highest penalty cost is $9 ($11-$2), which is found in row 1. As a result the highest quantity possible is allocated to the variable x_{12}, thus obtaining x_{12}=15, at the same time row 1 and row 2 are satisfied. Column 2 is arbitrarily crossed out and the supply of row 1 is adjusted to zero.

Continuing on in the same manner, row 2 now has the highest penalty cost that corresponds to $11 ($20-$9), therefore x_{23}=15 is allocated, so that column 3 is crossed out and there are 10 units left in row 2. Only column 4 is left and it has 15 positive supply units. By applying the Minimum Cell Cost Method to this column, we successively allocate x_{14}=0, x_{34}=5, x_{24}=10 (it is recommended to confirm these results). Also note that there are other possible solutions that depend on how the ties are broken.

The value of the objective function associated with this initial feasible solution is Z=15(2)+0(11)+15(9)+10(20)+5(4)+5(18)=$475 which is similar to what was reached using the Minimum Cell Cost Method, nevertheless, the Vogel Approximation Method generally gives a better initial solution.