Unit 5

Linear Programming

Q1) A dietician mixes together two kinds of food, say, A and B in such a way that the mixture contains at least 6 units of vitamin P, 7 units of vitamin Q, 12 units of vitamin R and 9 units of vitamin S. The vitamin contents of 1 kg of food A and 1 kg of food B are given below:

One kg of food X costs Rs. 5, whereas one kg of food Y costs Rs. 8. Formulate the linear programming problem.

A1)

Decision variables- Here decision variables are units of food A and B.

Let food A in the mixture be and food B in the mixture .

Objective function- To minimize the cost,

Total cost of food A and B  =

Or

Now we will write the constraints one by one-

Constraint-1: 

Constraint-2: 

Constraint-3: 

Constraint-4: 

Constraint-5: 

Mathematical formation will be as follows-

To minimize,

Subject to the constraints-

Q2) A manufacturer has 3 machines 1, 2 and 3. Machines 1 and 2 are capable of being operated for at the most 12 hours whereas machine 3 must be operated at least for 5 hours a day. He produces two items each requiring the use of the three machines.

The number of hours required for producing 1 unit of each of the items X and Y on the three machines are given below:

She makes a profit of Rs. 60 on item X and Rs. 40 on item Y. Assuming that he can sell all that he produces, how many of each item should be produced so as to maximize the profit. Formulate the above as L.P.P.

A2)

Decision variables- Here decision variables are item X and Y.

Let the production of item X be and the production of item Y be .

Objective function- To maximize the profit,

Now we will write the constraints one by one-

Constraint-1: 

Constraint-2: 

Constraint-3: 

Constraint-4: 

Mathematical formation will be as follows-

To maximize,

Subject to the constraints-

Q3) Find the maximum value of Z = 2x + 3y subject to the constraints-

A3)

Any point (x,y) satisfying the conditions lies in the first quadrant only.

Also since the desired point (x,y) lies within the convex region ABCDE.

Its vertices are A(3,3), B(20,3), C(20,10), D(18,12) and E(12,12).

The value of Z at these points are-

Z(A) = 15

Z(B) = 49

Z(C) = 70

Z(D) = 72

Z(E) = 60

Here 72 is the maximum value which is at D.

So that the solution of the LPP is x = 18 and y = 12 and maximum Z  = 72

Q4) A factory manufactures two types of items, A and B, each type requiring the use of two machines, an automatic and a hand operated. It takes 4 minutes on the automatic and 6 minutes on hand operated machines to manufacture a package of item A, while it takes 6 minutes on automatic and 3 minutes on the hand operated machines to manufacture a package of item B. Each machine is available for at the most 4 hours on any day. The manufacturer can sell a package of item A at a profit of Rs. 7 and item B at a profit of Rs 10. Assuming that he can sell all the items he manufactures, how many packages of each type should the factory owner produce in a day in order to maximise his profit ?

Determine the maximum profit.

A4)

We can tabulate the data as follows-

Decision variables- Let the manufacturer produce x packages of item A and y packages of item B per day respectively.

Objective function-  Suppose Z denotes the maximum profit,

Constraints-

1st constraint-

2nd constraint-

3rd constraint-

Mathematical formulation-

The mathematical form of this LPP can be written as-

Maximize
 

Subject to the constraints-

Tables for the region represented by inequalities-

For the first constraint-

For second condition-
 

Now we draw on x and y axes.

The coordinates of the vertices O, C, E and B of the feasible region OCEBO are O (0, 0), C (40, 0), E (30, 20) and B (0, 40). The coordinates of E are obtained by solving the equations 4x + 6y = 240 and 6x + 3y = 240.             

Therefore Z is maximum at x = 30 and y = 20 and the maximum value of Z is 410.

Q5) Max. Z = 5 X1 + 8 X2

Subject to constraints

4 X1 + 6 X2 ≤ 24

4 X1 + 8 X2 ≤ 40

X1, X2 ≥ 0
A5)

There is no common feasible region for line AB and CD.

Hence, solution is infeasible.

Q6) Explain LPP.

A6)

We use linear programming to optimize the linear function subject to given linear constraints.

LPP is the popular mathematical technique which is used to make maximum profit and minimum loss.

Important definitions-

Linear programming problem-

We need to optimize the linear function Z subject to certain conditions, these types of problems are called Linear programming problem or in short LPP.

Objective functions-

This is a linear function of several variables, subject to the conditions.

Optimal value-

This is a maximum or minimum value of a object function which is to be calculated in a LPP.

Q7) Write the step to solve LLP graphically.

A7)

Step by step procedure to solve LPP graphically-

Now plot the given constraints on

coordinate plane and find the convex region.

Now determine the convex region and find the value of the objective function at each vertex. The vertex which gives the max or min value of the objective function gives the optimal solution of the LPP.

Q8) Solve the following LPP graphically-

Maximize-

Subject to the constraints-

A8)

Change the given constraints into equations-

The line   meets the x-axis at the point A(10,0) and meets the y-axis at the point B(0,5). Join A and B to get the graph for the line.             

Hence origin (0,0) satisfies the inequality so that half plane containing the origin represent the solution set of .

And

The line meets the x-axis at the point C(5,0) and meets the y-axis at the point D(0,15). Join C and D to get the graph for the line.

Hence origin (0,0) satisfies the inequality   so that half plane containing the origin represent the solution set of.

Now all the points in first quadrant satisfies  .

So that first quadrant is the region represented by

Hence the region OCEBO satisfies all the inequalities.

And each point on the region is the feasible solution of the problem.

Feasible solution-

Here in this problem the feasible solution is (5,0), (4,3) and (0,5).

Now we can obtain the optimal solution of the problem.

As we know that any point in the feasible region that gives the optimal value is called an optimal solution.

The value of the objective function at corner points of the feasible region is given below-

Here we see that the maximum value of Z is 18.

Q9) Max Z = 60 X1 + 20X2∆

Subject to

2 X1 + 4X2 ≥ 120

8 X1 + 6X2 ≥ 240

X1, X2 ≥ 0

A9)

Max Z = 60 X1 + 20X2 + 0S1 + 0S2 - MA1 - MA2

Subject to

2 X1 + 4X2 - S1 + A1 = 120

8 X1 + 6X2 - S2 + A1 = 240

X1, X2, S1, S2, A1, A2, ≥ 0

When we solve this LPP by simplex method, we will get the following values in 4th Simplex Table.

Max Positive Cj - Zj = 30

Key Column = S1

But there is no positive Replacement Ration R means there is an Entering variable, but there is no outgoing variable.

Hence, the solution is unbounded or infinity.

The value of Z (Profit) keeps on increasing infinitely.

Q10) Max Z = 3 X1 + 2 X2

Subject to:

X1 + X2 ≤ 4

2 X1 + X2≥ 10

X1, X2 ≥ 0

A10)

Standard Form

Max Z = 3 X1 + 2 X2 + 0S1 + 0S2 - MA1

Subject to

X1 + X2 + S1 = 4

2 X1 + X2 - S2 + A1 = 10

X1, X2, S1, S2, A1 ≥ 0

When we solve this LPP by simplex method, we will get the following values in 2nd Simplex Table.

No positive ∆ value.

All Cj - Zj values are either zero or negative. Hence, test of optimality is satisfied. So, the solution appears to be optimal. But an artificial variable (A1) is present in the basis, which has objective function coefficient of - M (infinity).

Hence, the solution is infeasible (Not feasible).

Infeasibility occurs when there is no solution which satisfies all the constraints of the LPP.