Tag Archives: GLP

graphical method linear programming

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

machine products table

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.

glp linear programming

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:

wine production

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).

wine graphic solution

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.

graphical method linear programming

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.