System Engineering 3(3+0)

LESSON 1. Mathematical Formulation of The Problem

1.2 ALGORITHM: 

The procedure for mathematical formulation of linear programming problem consists of the following major steps:

Step1: Write down the decision variables of the problem.  

Step2: Formulate the objective function to be optimized (maximized or minimized) as a linear function of the decision variables.    

Step3: Formulate the other conditions of the problem such as resource limitations, market constraints ,inter-relation between variables etc. as linear equations or in equations in terms of the decision variables.  

      Step4: Add the ‘Non-negativity’ constraint from the consideration that negative values of the decision variables do not have any valid physical interpretation

The objective function, the set of constraints and the non-negative constraint together form a Linear Programming Problem.

1.3 SAMPLE PROBLEMS

Ex1: 

(Production allocation problem). A manufacturer produces two types of models M₁ and M₂.Each M₁ model requires 4 hours of grinding and 2 hours of polishing; whereas each M₂ model requires 2 hours of grinding and 5 hours of polishing. The manufacturer has 2 grinders and 3 polishers. Each grinder works for 40 hours a week and each polisher works for 60 hours a week. Profit on an M₁ model is Rs 3.00 and on an M₂ model is Rs. 4.00. Whatever is produced in a week is sold in the market.  How should the manufacturer allocate his production a week is sold in the market. How should the manufacturer allocate his production capacity to the two types of  models so that he may make the maximum profit in a week ?      

 

Solution:

Here is a real situation from an industry. The manufacturer can, if he so chooses, produce only model M₂ , but then his grinders would be idle and his profits may be maximum. This is only a guess. To be definite, we must tell how many M₁ models and how many M₂  models should be produced per week, in order that his profits may be maximum.

 

 Mathematical Formulation

 Decision variables: Let

                       X₁ = number of units of M₁ model, and

                       X₂ = number of units of M₂ model.  

Objective function: The objective of the manufacturer is to determine the number of M₁ and M₂  models so as to maximize the total profit.

            Z= 3x₁ + 4x₂

Constraints: For grindinding since each M₁ model requires 4 hours and each M₂ model requires 2 hours the total number of grinding hours needed per week is given by 4x₁ + 2x₂.

Similarly for polishing, the total number of polishing hours needed per week is 2x₁+5x₂

Further, since the manufacturer does not have more than 2 x 40(=80) hours of grinding and 3x60(=180) hours of polishing, the time constraints are

               4x₁ + 2x₂ ≤  80 and  2x₁+ 5x₂ ≤  180

Non- negativity constraints: Since the production of negative number of models is meaningless, we must have x₁ ≥ 0 and x₂ ≥ 0

Hence, the manufacturer’s allocation problem can be put in the following mathematical form:

Find two real numbers, x₁ and  x₂ such that

1. 4x₁ + 2x₂ ≤ 80

2. 2x₁+ 5x₂ ≤ 180

3. x₁≥ 0 , x₂ ≥ 0

and for  which the expression (objective function)    z = 3x₁ + 4x₂.

Ex .2: 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.

Machine	Product		Available Time (in machine hours per week)
	P1	P2
1	2	1	300
2	3	4	509
3	4	7	812
Profit	Rs. 50	Rs. 60

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.

Ex.3: 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