Linear Programming Notes and questions

Linear Programming It is an important optimization (maximization or minimization) technique used in decision making is business and everyday life for obtaining the maximum or minimum values as required of a linear expression to satisfying certain number of given linear restrictions.

Linear Programming Problem (LPP) The linear programming problem in general calls for optimizing a linear function of variables called the objective function subject to a set of linear equations and/or linear in-equations called the constraints or restrictions.

Objective Function The function which is to be optimized (maximized/minimized) is called an objective function.

Constraints The system of linear in-equations (or equations) under which the objective function is to be optimized is called constraints.

Non-negative Restrictions All the variables considered for making decisions assume non-negative values.

Slack and Surplus Variables The positive variables which are added to left hand sides of the constraints to convert them into equalities are called the slack variables. The positive variables which are subtracted from the left hand sides of the constraints to convert them into equalities are called the surplus variables.

Important Definitions and Results

(i) Solution of a LPP

A set of values of the variables xl, x2,…., xn satisfying the constraints of a LPP is called a solution of the LPP.

(ii) Feasible Solution of a LPP

A set of values of the variables xl, x2,…xn satisfying the constraints and non-negative restrictions of a LPP is called a feasible solution of the LPP.

(iii) Optimal Solution of a LPP

A feasible solution of a LPP is said to, be optimal (or optimum), if it also optimizes the objective function of the problem.

(iv) Graphical Solution of a LPP

The solution of a LPP obtained by graphical method i.e., by drawing the graphs corresponding to the constraints and the non-negative restrictions is called the graphical solution of a LPP.

Important Question

1.      An aero plane can Carrey a maximum of 200 passengers. A profit of Rs. 1000 is made on each executive class ticket and a profit of Rs. 600 is made on each economy class ticket. The airline reserves at least 20 seats for the executive class. However, at least 4 times as many passengers prefer to travel by economy class, than by the executive class. Determine how many tickets of each type must be sold, in order to maximize profit for airline. What is the maximum profit? Make an L.P.P. and solve it graphically.                                                                       [Ans: at(40, 60)]

2.      A diet for a sick person must contain at least 4000 units of vitamins, 50 units of minerals and 1400 calories. Two foods X and Yare available at a cost of Rs. 4 and Rs. 3 per unit respectively. One unit of food X contains 200 units of vitamins, 1 unit of minerals and 40 calories, whereas 1 unit of Y contains 100 units’ vitamins, 2 units of minerals and 40 calories. Find what combination of foods X and Y should be used to have least cost, satisfying the requirements.

3.      A company sells two different products A and B. The two product are produced in a common production process which has a total capacity of 500 man hours. It takes 5 hours to produce a unit of A and 3 hours to produce a unite of B. the demand in the market shows that the maximum number of units of A that can be sold is 70 and that of B is 125. Profit on each unit of A is Rs. 20 and on b is Rs. 15. How many units of A and B should be produced to maximize the profit?                                                                                    [Ans: at (25, 125)]

4.      A producer has 30 and 17 units of labor and capital respectively which he can use to produce two types of goods X and Y. To produce one unit of X, 2 units of labor and 3 units of capital are required. Similarly, 3 units of labor and 1 unit of capital is required to produce one 1 unit of Y. If X and Y are priced at Rs. 100 and Rs. 120 per units. How should the producer use his resources to maximize the total revenue?                                                                                                          [Ans: at (3, 8)]

5.      A company produces two types of products A and B and sells at a profit of Rs. 5/unit and 3/unit respectively. Each product is processed on two machines M1 and M2. One unit of A requires one minute of processing time on M1 and two minutes of processing on M2; where one unit of B requires one minute of processing on M1 and one minute of processing on M2. Machines M1 and M2 are available for at-most 5 hours and 6 hours respectively in a day. Find how many units of A and B should be produced to maximize the profit.                                               [Ans: at(60, 240)]

6.       A manufacturer produces two types of steel trunks. Each product is processed on two machines A and B. One unit of first trunk requires 3 hours of processing time on A and 3 hours of processing on B; where the second type trunk requires 3 hours of processing on A and 2 hours of processing on B. Machines A and B can work at-most 18 hours and 15 hours respectively in a day. He earns a profit of Rs. 30/unit and 25/unit respectively. Find how many units each trunk should be produced to maximize the profit.                                                                                                                                  [Ans: at (3, 3)]

7.      A retired person has Rs. 70,000 to invest and two type of bonds are available. First type of bond yields an annual interest of 8% on the amount invested and second type of bond yields 10% per annum. As per norms he has to invest a minimum of 10,000 in first bond and at-most 30,000 in second bond. How should he plans to invest, to get maximum return after one year?

8.      A farmer has a supply of chemical fertilizer of type I which contains 10% nitrogen and 6% phosphoric acid and type II contains 5% nitrogen and 10% phosphoric acid. After testing the soil conditions of a field, it is found that at least 14 kg of nitrogen and 14 kg of phosphoric acid required. The fertilizer type I cost Rs. 2/kg and type II cost Rs. 3/kg. How many kilograms of each used be used minimize cost for good fertilizers.                                            [Ans: at (100, 80)]

9.      A house wife wishes to mix up to kinds of foods X and Y in such a way that mixture contains at least 10 units of vitamin A, 12 units of vitamin B and 8 units of vitamin C, the vitamin contains of 1 Kg of foods X and Y as follows:

Food	Vitamin A	Vitamin B	Vitamin C
X	1	2	3
Y	2	2	1

If one kg of food X costs Rs. 6 and food Y costs Rs. 10, find least cost of mixture.    [Ans: (2, 4)]

10. A manufacturer produces two types of cups A and B. three machines are required to manufacture the cups and time in minutes by machines to produce 1 cup given as:

Type of cups	Machine X	Machine Y	Machine Z
A	12	18	6
B	6	0	9

Each machine is available for a maximum period of 6 hours/day. If the profit on each cup A is 75 paisa and on B it is 50 paisa, show that 15 cups of type A and 30 cups of type B should give max profit.

11. A library has to accommodate two different types of books on a shelf. The books are 6 cm and 4 cm thick and weight 1 kg and 1.5 kg each. The shelf is 96 cm long and at most can support a weight of 21 kg. How should the shelf be filled with books of two types in order to include the greatest number of books?                                                                                 [Ans: at (12, 6)]

12. A man has Rs. 1500 for purchasing rice and wheat bags. A bag of rice and wheat costs Rs. 180 and Rs. 120 respectively. He has the storage capacity of at most 10 bags. He earns profit of 11 Rs. And Rs. 9 per bag of rice and wheat. Formulate the above in LPP to maximize the profit.                                                                                    

13. Sole graphically

Minimize Z= x – 7y + 190, where, x + y ≤ 8, x ≤ 5, y ≤ 5, x + y ≥ 4 and x, y ≥ 0.

14. There are two factories located one at place P and the other at place Q. From these locations, a certain commodity is to be delivered to each of the three depots situated at A, B and C. The weekly requirements of the depots are respectively 5, 5 and 4 units of the commodity while the production capacity of the factories at P and Q are respectively 8 and 6 units. The cost of transportation per unit is given below:

From/To	A	Cost in Rs. B	C
P	160	100	150
Q	100	120	100

      How many units should be transported from each factory to each depot in order that the transportation cost is minimum, what will be the minimum transportation cost?