Linear Programming - Model Formulation & Graphical Method

In fact, the most difficult problem in the application of management science is the formulation of a model. Therefore, it is important to consider model formulation before launching into the details of linear programming solution. Model formulation is the process of transforming a real word decision problem into an operations research model. In the sections that follow, we give several Lilliputian examples so that you can acquire some experience of formulating a model. All the examples that we provide in the following sections are of static models, because they deal with decisions that occur only within a single time period.

"Model formulation is partially an art." -Vinay Chhabra & Manish Dewan

Product Mix Problem

In product mix selection, the decision-maker strives to determine the combination of the products, which will maximize the profit without violating the resource constraints. In the instance below, the objective is to maximize the profit. In the subsequent examples, you will see other objectives, such as minimum cost.

Example 1

Universal Corporation manufactures two products- P₁ and P₂. The profit per unit of the two products is Rs. 50 and Rs. 60 respectively. Both the products require processing in three machines. The following table indicates the available machine hours per week and the time required on each machine for one unit of P₁ and P₂. Formulate this product mix problem in the linear programming form.

Solution

Let x₁ and x₂ be the amounts manufactured of products P₁ and P₂ respectively. The objective here is to maximize the profit, which is given by the linear function

Maximize z = 50x₁ + 60x₂

Since one unit of product P₁ requires two hours of processing in machine 1, while the corresponding requirement of P₂ is one hour, the first constraint can be expressed as
2x₁ + x₂ £ 300

Similarly, constraints corresponding to machine 2 and machine 3 are
3x₁ + 4x₂ £ 509
4x₁ + 7x₂ £ 812

In addition, there cannot be any negative production that may be stated algebraically as
x₁ ³ 0, x₂ ³ 0

A variable that is also allowed to assume negative values is said to be unrestricted in sign.

The problem can now be stated in the standard linear programming form as

Maximize z = 50x₁ + 60x₂

subject to

2x₁ + x₂ £ 300
3x₁ + 4x₂ £ 509
4x₁ + 7x₂ £ 812

x₁ ³ 0, x₂ ³ 0

This procedure is commonly referred to as the formulation of the problem.

• Additivity. The total amounts of each input and the corresponding profit are the sums of the inputs and profit for each individual process. For example, one unit of Product 1 and one unit of Product 2 require 3 (2 + 1) hours of processing in machine 1, 7 (3 + 4) hours of processing in machine 2, 11 (4 + 7) hours of processing in machine 3, and yield Rs.110 (50 + 60) profit.
• Divisibility. The activity levels are allowed to assume fractional values as well as integer values. For example, we admit the possibility of x1 = 509/3 or 169.67, x2 = 509/4 or 127.25.
• Proportionality. The total amounts of each input and the associated profit are directly proportional to the level of output.
  

  Doubling (or tripling) the production of a product will exactly double (or triple) the profit and required resources.

  For example, to manufacture 1 unit of product 1 (x1 = 1), we require 2 hours of processing in machine 1, 3 hours of processing in machine 2, 4 hours of processing in machine 3, and the profit is Rs.50. By the same token, to manufacture 10 units of product 1 (x1 = 10), we require 20 hours of processing in machine 1, 30 hours of processing in machine 2, 40 hours of processing in machine 3, and the profit is Rs.500.
  

For all the examples in the subsequent sections of this chapter, we assume these assumptions to hold good.

Packaging Problem

Example 2

The Best Stuffing Company manufactures two types of packing tins- round & flat. Major production facilities involved are cutting and joining. The cutting department can process 200 round tins or 400 flat tins per hour. The joining department can process 400 round tins or 200 flat tins per hour. If the contribution towards profit for a round tin is the same as that of a flat tin, what is the optimal production level?

Solution.

Let
x₁ = number of round tins per hour
x₂ = number of flat tins per hour

Since the contribution towards profit is identical for both the products, the objective function can be expressed as x₁ + x₂. Hence, the problem can be formulated as

Maximize Z = x₁ + x₂

subject to

(1/200)x₁ + (1/400)x₂ £ 1
(1/400)x₁ + (1/200)x₂ £ 1

x₁ ³ 0, x₂ ³ 0

i.e., 2x₁ + x₂ £ 400
x₁ + 2x₂ £ 400

x₁ ³ 0, x₂ ³ 0