Linear Programming

Northwest Corner Method (Transportation Algorithm in Linear Programming)

The Northwest Corner Method (or upper left-hand corner) is a heuristic that is applied to a special type of Linear Programming problem structure called the Transportation Model, which ensures that there is an initial basic feasible solution (non artificial). Other methods for obtaining an initial basic solution are the Minimum Cell Cost Method and the Vogel Approximation Model. Generally, Vogel’s Model produces the best initial basic solution and the Northwest Corner the worst; nevertheless, the Northwest Corner Method involves the least number of calculations.

The Northwest Corner Method starts in the cell (route) corresponding to the northeast corner, or the upper left, of the tableau (variable $x_{11}$ ). Below is a description of the steps:

Step 1: Allocate the maximum amount available to the selected cell and adjust the associated supply and demand quantities by subtracting the allocated quantity.
Step 2: Exit the row or the column when the supply or demand reaches zero and cross it out, to show that you cannot make any more allocations to that row or column. If a row or a column simultaneously reach zero, only cross out one (the row or the column) and leave a zero supply (demand) in the row (column) that is not crossed out.
Step 3: If exactly one row or column is left that is not crossed out, stop. Otherwise, advance to the cell to the right if a column has just been crossed out, or to the cell below if a row was crossed out. Continue with Step 1.

Northwest Corner Method Example

In order to illustrate how to apply the Northwest Corner Method we will consider the following balanced transportation model that takes into account 3 silos products (supply) that satisfy the needs of 4 mills (demand). The transportation algorithm is based on the hypothesis that the model is balanced, in other words, that the total demand is equal to the total supply (if the model is not balanced it can always be increased with a fictitious source or a fictitious destination to restore the equilibrium or balance).

The per unit transport costs from silo i to mill j ( $c_{ij}$ ) is represented in the upper right-hand corner of each box. For example the unit cost of sending one product unit from silo 1 to mill 1 is $10. Furthermore silos 1, 2 and 3 have a capacity and supply of 15, 25 and 10 units, respectively. On the other hand mills 1, 2, 3 and 4 have requirements or demands of 5, 15, 15 and 15 units, respectively. The model is balanced (sum of the supply = sum of the demand = 50 units). By applying the Northwest Corner Model to the previous example the following results are obtained. The arrows indicate the order in which the allocated quantities are generated:

The quantity allocated to cell $x_{11}$ is 5 units, given that although silo 1 has a capacity of 15 units, mill 1 only needs (demand) 5 units (no more allocations are made to column 1 corresponding to mill 1).
Next we will move to the right and assign the maximum (10 remaining units) to cell $x_{12}$ (thereby completing the capacity of silo 1 and as a result it is no longer possible to make allocations to row 1).
Then we allocate 5 units to cell $x_{22}$ , which is actually less than the capacity of silo 2 but enough to satisfy the requirements of mill 2 (it is no longer possible to make additional allocations to column 2).We move to the right and allocate the maximum possible (5 units, which is the remaining capacity of silo 2, meaning that $x_{24}=5$ ), with which silo 2 operates at maximum capacity (new allocations to row 2 are no longer possible).
Finally 10 units are allocated from silo 3 to mill 4 ( $x_{34}=10$ ) meeting the mill’s demand (and the capacity of the corresponding silo).

Therefore the initial basic feasible solution is: $x_{11}=5$ , $x_{12}=10$ , $x_{22}=5$ , $x_{23}=15$ , $x_{24}=5$ , $x_{34}=10$ , reporting a program cost (the objective function value) of: Z=5(10)+10(2)+5(7)+15*(9)+5(20)+10*(18)=$520. Note that if the above problem is implemented computationally using Solver from Excel and Simplex LP as a problem solver, the following optimal solution is found (yellow cells) with a minimum cost (optimal value) of $435.

How to Calculate the Shadow Price of a Constraint

The Shadow Price of a constraint in Linear Programming indicates how much the value of an objective (optimal) function changes due to a marginal variation in the right-hand side of a constraint. It is assumed that the rest of the model’s parameters remain constant. It should be noted beforehand that the Shadow Price can be positive, zero, or negative, and these different possibilities will be discussed in the Blog.

Computational tools like Excel’s Solver can be used for obtaining the Sensibility Analysis from a Linear Programming model; however, here we will be focusing on calculating the Shadow Price of a constraint graphically, which will help us later on to understand the concepts behind the Solver results.

Calculate the Shadow Price of a Constraint Graphically

We will now calculate the Shadow Price of a constraint for the following Linear Programming model:

The optimal solution of this model is X=100 and Y=350 with an optimal value V(P)=3,100 according to the graphical Geogebra solution or the Solver solution from Excel. The following diagram shows the optimal solution obtained graphically at vertex C, which corresponds to the intersection of constraint 1 (R1: red color) and constraint 3 (R3: black color), this being the optimal basic feasible solution.

Suppose we want to know how the optimal value will change (with respect to its current value) if the right-hand side of constraint 1 is raised by one unit but without having to re-solve the problem. The shadow price allows us to answer that question and can anticipate the new optimal value resulting from a marginal variation of the right-hand side of a constraint.

A marginal variation of a right-hand side means that the new optimal solution can still be found using the current active constraints, i.e., those that are satisfied with equality (this conserves the optimal basis).

For constraint 1 if we increase its right-hand side, it will be moved upward in a parallel manner. If we want to guarantee that the new optimal solution can still be found with R1 and R3 active, we reach the vertex where R2 and R3 currently intercept corresponding to the coordinate X=166.67 and Y=350 (this is the maximum variation). In the same fashion if we decrease the right-hand side of constraint 1 and try to maintain R1 and R3 active in the new optimal, the last point where this is guaranteed is at vertex B, whose coordinates are X=0 and Y=350 (this will be the smallest variation). With this information we calculate the shadow price of constraint 1:

This shadow price is valid if the right-hand side of constraint 1 (currently b1=1,600) varies between [1,400,1,733.33]. For example, if the right-hand side of R1 increases from 1,600 to 1,700 the new optimal value would be V(P)=3,100+100*1.5=3,250. Similarly if the right-hand side of R1 decreased from 1,600 to 1,550 the new optimal value would be V(P)=3,100-50*1.5=3,025. (It is recommended you confirm these results graphically with TORA or IORTutorial).

Note that if the right-hand side variation of constraint 1 is outside of the interval [1,400,1,733.33], the shadow price cannot be used to predict the new optimal value. In an upcoming analysis we will finish calculating the shadow price of constraints 2 and 3 along with other Sensibility Analysis in solving Linear Programming models.

Linear Programming (Graphical Method)

The Graphical Method (graphic solving) is an excellent alternative for the representation and solving of Linear Programming models that have two decision variables. For this purpose there are computational tools that assist in applying the graphical model, like TORA, IORTutorial and Geogebra. Within this context we will present a series of Linear Programming exercises that have been solved using the graphical method.

Graphical Method Exercises Solved in Linear Programming

Exercise #1: A workshop has three (3) types of machines A, B and C; it can manufacture two (2) products 1 and 2, and all products have to go to each machine and each one goes in the same order; First to the machine A, then to B and then to C. The following table shows:

The hours needed at each machine, per product unit
The total available hours for each machine, per week
The profit of each product per unit sold

Formulate and solve using the graphical method a Linear Programming model for the previous situation that allows the workshop to obtain maximum gains.

Decision Variables:

$X_{1}$ : Product 1 Units to be produced weekly
$X_{2}$ : Product 2 Units to be produced weekly

Objective Function:

Maximize $X_{1}+1.5X_{2}$

Constraints:

$2X_{1}+2X_{2}\leq 16$
$X_{1}+2X_{2}\leq 12$
$4X_{1}+2X_{2}\leq 28$
$X_{1},X_{2}\geq 0$

The constraints represent the number of hours available weekly for machines A, B and C, respectively, and also incorporate the non-negativity conditions.

For the graphical solution of this model we will use the Graphic Linear Optimizer (GLP) software. The green colored area corresponds to the set of feasible solutions and the level curve of the objective function that passes by the optimal vertex is shown with a red dotted line.

The optimal solution is $X_{1}=4$ and $X_{2}=4$ with an optimal value $V(P)=1(4)+1,5(4)=10$ that represents the workshop’s profit.

Exercise #2: A winemaking company has recently acquired a 110 hectares piece of land. Due to the quality of the sun and the region’s excellent climate, the entire production of Sauvignon Blanc and Chardonnay grapes can be sold. You want to know how to plant each variety in the 110 hectares, given the costs, net profits and labor requirements according to the data shown below:

Suppose that you have a budget of US$10,000 and an availability of 1,200 man-days during the planning horizon. Formulate and solve graphically a Linear Programming model for this problem. Clearly outline the domain of feasible solutions and the process used to find the optimal solution and the optimal value.

Decision Variables:

$X_{1}$ : Hectares intended for growing Sauvignon Blanc
$X_{2}$ : Hectares intended for growing Chardonnay

Objective Function:

Maximize $50X_{1}+120X_{2}$

Constraints:

$X_{1}+X_{2}\leq 110$
$100X_{1}+200X_{2}\leq 10.000$
$10X_{1}+30X_{2}\leq 1.200$
$X_{1},X_{2}\geq 0$

Where the restrictions are associated with the maximum availability of hectares for planting, available budget, man-hours in the planting period and non-negativity, respectively.

The following graph shows the representation of the winemaking company problem. The shaded area corresponds with the domain of feasible solutions, where the optimal basic feasible solution is reached at vertex C, where the budget and man-days restraints are active. Thus solving said equation system the coordinate of the optimal solution is found where $X_{1}=60$ and $X_{2}=20$ (hectares). The optimal value is $V(P)=50(60)+120(20)=5.400$ (dollars).

Exercise #3: A company produces two different products. One of them needs 1/4 of an hour of assembly work per unit, 1/8 of an hour in quality control work and US$1.2 in raw materials. The other product requires 1/3 of an hour of assembly work per unit, 1/3 of an hour in quality control work and US$0.9 in raw materials. Given the current availability of staff in the company, each day there is at most a total of 90 hours available for assembly and 80 hours for quality control. The first product described has a market value (sale price) of US$8.0 per unit. In addition, the maximum amount of daily sales for the first product is estimated to be 200 units, without there being a maximum limit of daily sales for the second product.

Formulate and solve graphically a Linear Programming model that will allow the company to maximize profits.

Decision Variables:

$X_{1}$ : Product 1 units to be produced daily
$X_{2}$ : Product 2 units to be produced daily

Objective Function:

Maximize $(9-1.2)X_{1}+(8-0.9)X_{2}=7.8X_{1}+7.1X_{2}$

Constraints:

$\frac{X_{1}}{4}+\frac{X_{2}}{3}\leq 90$
$\frac{X_{1}}{8}+\frac{X_{2}}{3}\leq 80$
$X_{1}\leq 200$
$X_{1},X_{2}\geq 0$

The first constraint represents the daily assembly time constraints. The second constraint is the availability of time for quality control (also daily). The third constraint establishes an upper bound for the manufacturing and daily sales of Product 1. In addition, the non-negativity conditions for the decision variables are included.

The domain of feasible solutions has 5 vertexes that correspond with the problem’s optimal candidates. In particular the optimal vertex is D such that the optimal solution is $X_{1}=200$ and $X_{2}=120$ with an optimal value $V(P)=7.8(200)+7.1(120)=2,412$ that corresponds with the maximum profit for the company.

Important: On the date of this publication we have more than 15 articles that deal with Linear Programming that we recommend you review, where we go over the graphical solution to these types of models as well as solutions that use algorithms like the Simplex Method and the computational implementation with tools such as Solver and What’sBest!, among others.

10 Things You need to know about Simplex Method

The Simplex Method was developed by George Dantzing in 1947. It is without a doubt the most popular algorithm when it comes to solving a Linear Programming (LP) model, and it plays a major role in the introduction to Operations Research (OR).

Today we’re presenting a summary of 10 main concepts about the use and application of the Simplex Method for our users to be able to have a first approach to the method, while paying attention to some characteristic aspects:

Simplex Method (10 Things You need to know)

History: In 1947 it was first published by George Dantzing, an American mathematician.
Standard Form: The Simplex Method’s application requires the Linear Programming model to be on its standard form.
Basic Feasible Solution (BFS): A basic feasible solution matches a vertices in domain of a Linear Programming model’s feasible solutions.
Optimality Criterion: The Basic feasible solution is optimal if and only if the reduced costs of all the nonbasic variables are higher or equal to zero.
Infinite Solutions: This case is seen when there are reduced costs equal to zero in one or more optimal nonbasic variables.
Unbounded Problem: This case is seen when, while doing the calculus of the variable which leaves the base, all the elements ykj of the column j in the tableau are negative.
Infeasible Problem: This is the case when the optimal value of the problem in Phase 1 (in a Two Phase Simplex Method) is nonzero.
Rate of Convergence: If two or more nonbasic variables have negative reduced cost, the entrance to the base goes to the lowest reduced cost.
Postoptimal Analysis: Once we achieve the optimal solution through the Simplex Method, we can analyze the impact in the results with the alteration of the parameters.
Excel Solver: The Excel complement Solver allows us to use the Simplex Method as a solving method (Simplex LP)

This review is based on the experience we have teaching Operations Research and on the most frequent questions we receive daily from undergraduate students.

You can download the infographic as a PDF file here: Simplex Method

We encourage you to check and share this infographic on your social webs. Also, if you think there’s an important aspect missing in the previous list, you can use the commentary section at the bottom of this page to let us know. This is how we can keep updating the article with the main characteristics of the Simplex Method.

How to Solve a Linear Programming model with Dual Simplex Method

The Dual Simplex Method offers an alternative when solving Linear Programming (LP) models with algorithms. This method may be used in particular when the standard way to carry a linear programming model is not available from an initial basic feasible solution. Consider the following LP problem to illustrate the application of the Dual Simplex Method:

To solve the problem above in a standard form, we must add 2 excess non-negative variables for constraints 1 and 2, which we will respectively call X4 and X5. Thus the problem in its standard format is defined by:

Then we build the initial tableau of the Simplex Method:

How to continue the iterations of the Simplex Method? Before that, it is necessary to have an initial basic feasible solution. In this context if we want to use X4 and X5 as basic variables (and hence X1, X2 and X3 as basic variables) it is required that X4 and X5 are greater than or equal to zero, however, their coefficients in the respective rows are negative and therefore we can’t use them (matrix with “1” as a diagonal, and all the other coefficients at zero). So to form the identity we can multiply by “-1” row 1 and 2, obtaining the following:

Now X4 and X5 are basic variables and adopt the values of -1 and -3/2, respectively, which clearly does not satisfy the conditions of non-negativity for the decision variables, i.e. they do not correspond to a basic feasible solution. However, in this instance we can apply the Dual Simplex Method as an alternative resolution. To do this, we will select a variable to leave the base and adopt as a criterion for basic variable associated with “more negative” right hand side (RHS). In this instance the variable is X5. Then to determine which variable will go into the base we find a minimum quotient between the negative of the reduced cost of the non-basic variables and the strictly less than zero entries for non-core variables in row 2 (row associated with more negative right). I.e.: Min {-160/-2; -120/-2; -280/-2} = 60, then the minimum quotient is reached in the second column associated with the non-basic variable X2, therefore said variable enters the base.

Finally one iteration is done by performing the operations of the necessary rows, so we enter X2 into the base, meanwhile at the same time X5 leaves the base. The results are:

Note that now the basic variables are X4 and X2 where only X4 = -1/4 which does not satisfy the condition of being a feasible basic solution. Therefore we make a new iteration, in this case taking the base to the X4 variable and calculate the minimum quotient: Min {-40/-1; -160/-3; -60/-1/2} = 40, then the minimum quotient is in the first column, therefore variable X1 enters the base. Consequently the remaining table is updated as follows:

The basic variables are now X1=1/4 and X2=1/2 (which meet the conditions of non-negativity). Additionally, the reduced cost of the non-basic variables is greater than or equal to zero, therefore we face the optimal solution. We can additionally recognize that the optimum value is V(P)=100 that would be obtained by evaluating the optimal solution to the objective function, however, the value is obtained by said process with a changed sign.

The example above allowed us to appreciate how through the Dual Simplex Method can solve a linear programming model that after being solved by the standard form does not provide an initial basic feasible solution. Significantly, it is not the only algorithmic alternative to which we can appeal. For example we could have achieved the same results using the Two-Phase Simplex Method with some more work. Alternatively we can define the proposed problem with the dual model and solve it by the Simplex Method so that we may later use the conditions of Complementary Slackness Theorem. In summary before we use an optimization model we have several alternatives for resolution and it is the duty of solver to evaluate the different paths that we can take in terms of its complexity.