COMPUTER SOLUTION METHODS
The graphical solutions discussed earlier are obviously limited to two variables problems. The other examples discussed do involve more them two variables but are relatively simple and compared to the real life problems encountered by the organisation of today. These problems could be solved manually by the Simplex Method but the method is complicated and involves laborious calculations.
In actual applications, LP problems are solved by computer methods. Today, there are many efficient computer softwares available. While using the software for solving LP models, one need not always be concerned about the internal details of the solution method, though there is no doubt that one can become a better user of the software if one knows its details. Effective use of these software models can be made if one
 fully understands the LP model and its assumptions.
 is skilful in recognising an LP problem.
 can formulate the problems well.
 can arrange for solution using a computer package and is
 capable of interpreting the output from such packages.
Before the computer solution methods are discussed, we need to understand certain basics. Most computer methods are based upon algebraic solution procedure, like of which are used in Simplex Method. Let us recapitulate the following three requirements in solving a LPP by Simplex Method.
 All constraints must be stated as equations.
 The right hand side of a constraint cannot be negative.
 All variables are restricted to nonnegative values.
It can be shown that the optimal solution to a LPP is included in the set of basic feasible solutions of the Simplex procedure. So, the optimal solution can be found by performing a search of the set of basic feasible solutions. This is what the Simplex method accomplishes. It begins with a basic feasible solution consisting of two pools of variables – basic variables and nonbasic variables. The Simplex method determines whether the objective function can be improved by exchanging a basic variable and a nonbasic variable. If an exchange will result in an improvement, an existing basic variable is set equal to 0 (becoming a nonbasic variable) an existing nonbasic variable is included in the pool of basic variables and the system of equations is resolved with the new set of basic variables to form a new basic feasible solution. A determination is made again regarding whether a better solution exists. If yes, another exchange takes place and the process repeats itself. The simplex method is termed as iterative process because a specified set of solution steps are repeated until an optimal solution is identified.
REVIEW
 . What are the essential characteristics of a Linear Programming model?
 Explain the terms : Key decision, objective, alternative and restrictions in the context of linear optimisation models by assuming a suitable industrial situation.
 Discuss the application of LP in any functional area of management. Use suitable example from business or industry,
 “Linear Programming is the most widely used and most successfully used mathematical approach to decisionmaking”, Comment
 Explain the advantages and major limitations of LP model. Illustrate your answer with suitable examples.
 What are the major allocation problems that can be solved by using LP model? Briefly discuss each one of them.
 “Each LP problem with a feasible solution area offers infinite number of solutions”. Do you agree with this statement? Justify your answer.
 What are the basic characteristics and assumptions of a LP model?
 Explain important characteristics of the industrial situations to which linear programming method can be successfully applied. Illustrate applications of this technique with a suitable example.
10. Write at least five application areas of Linear Programming.
11. II. Explain the graphical method of solving an LPP involving two variables.
12. Write the general form of LPP and prove that the feasible region of an LPP is a convex set.
13. Illustrate graphically the following special cases of LP problems.
 Multiple optimal solutions.
 No – feasible solution
 Unbounded problem.
14. Write the standard form of LPP in matrix form.
15. Write a short note on the limitations of Linear Programming.
16. Discuss briefly the steps to formulate a Linear Programming Problem. Give suitable examples.
17. Explain the following terms
 Linearity
 Feasible Solution
 Objective function
 Unbounded solution
 Optimal solution.
18. Orient Paper Mills produces two grades of paper X and Y. Because of raw material availability limitations, not more than 500 tons of grade X and 250 tons of grade Y can be produced in a month. Total production hours in a month are 400 Product X needs 15 minutes and product Y needs 25 minutes for production of one ton of product each. Profit margin of X is Rs 200 and Y is Rs 400 per ton. Formulate a LPP to optimise the product mix for maximum profit.
19. Prime Enterprises manufactures three types of dolls. The Boy requires ½ meter of red cloth, 1½ meters of green cloth and 1 ½ meters of black cloth and 5 kg of fibre. The Girl requires ½ meter of red cloth, 2 meters of green cloth, one meter of black cloth and 6 kg of fibre. The Dog requires ½ meter of red, one meter of green, ¼ meter of black and 2 kg of fibre. The profits on the three are respectively Rs 3, 5 and 2, The firm has 1000 meters of red, 1500 meters of green, 2000 meters of black and 6000 kg of fibre. Find the number of dolls of each type to be manufactured, set up LP for maximum profit.
 Three products are produced on three different operations. The limit of available time for the three operations are respectively 430, 460 and 420 minutes and profit per unit for the three products are Rs 3, 2 and 5 respectively. Times in minutes per unit on each machine operation is as follows:

Product 

Operation 
I 
II 
III 
1 
1 
2 
1 
2 
3 
0 
2 
3 
1 
4 
0 
Write LP model for this problem.
28. Old hens can be bought at Rs 2 each and young ones at Rs 5 each. The old hen lays 3 eggs per week and young hen lays 5 eggs per week, each egg being worth 30 paise, A hen costs Rs 1 per week to feed. Mr A has only Rs 80 to spend for hens. How many of each kind should Mr A buy to give a profit of at least Rs 6 per week, 8 assuming that Mr A cannot house more than 20 hens?
A small manufacturer employs 5 skilled men and 10 semiskilled men and makes an article in two qualities, a deluxe model and an ordinary model. Making of a deluxe model requires 2 hours work by a skilled man and 2 hours work by a semiskilled man. The ordinary model requires one hour work by a skilled man and 3 hours work by a semiskilled man. By union rules no man can work for more than 8 hours a day. The manufacturer’s clear profit of the deluxe model is Rs 10 and of the ordinary model Rs 8. Formulate the model of the problem.
A firm manufactures three products A, Band C. The profits are Rs 3, Rs 2 and Rs 4 respectively. The firm has two machines and the processing time in minutes for each machine on each product is given below.
Product 

Machine 
A 
B 
C 

C 
4 
3 
5 

D 
2 
2 
4 
Machines C and D have 2,000 and 2,500 machineminutes respectively. The firm must manufacture 100 A’s, 200 B’s and 50 C’s but not more than 150 A’s set up an LP model to maximise the profit.
A farmer has 100 acre farm. He can sell all the tomatoes, lettuce or reddish he can raise. The price he can obtain is Rs 1 per kg for tomatoes, Rs 0.75 head for lettuce and Rs 2 per kg reddish. The average yield per acre is 2000 kg of tomatoes, 3000 heads of lettuce and 1000 kg of reddish. Fertiliser is available at Rs 0.50 per kg and the amount required per acre is 100 kg each for tomatoes and lettuce and 50 kg for reddish. labour required for sowing, cultivating and harvesting per acre is 5 mandays for tomatoes and reddish and 6 mandays for lettuce. A total of 400 man days of labour are available at Rs 20 per manday.
Formulate an LP model for this problem in order to maximise the farmer’s total profit.
A manufacturer of metal office equipment makes desks, chairs, cabinets and bookcases. The work is carried out in three major departments, metal stamping, assembly and finishing. The exhibits A, B and C give requisite data of the problem.
Exhibit A 

Departments 
Time required in hours per unit of product 

Products 

Desk 
Chair 
Cabinet 
Bookcases 
Hours available/week 

Stamping 
4 
2 
3 
3 
800 
Assembly 
10 
6 
8 
7 
1200 
Finishing 
10 
8 
8 
8 
800 
Exhibit B 

Cost (Rs) of operation per unit of product 

Products 

Department 
Desk 
Chair 
Cabinet 
Bookcases 

Stamping 
15 
8 
24 
21 

Assembly 
30 
18 
24 
21 

Finishing 
35 
28 
25 
21 
Exhibit C 

Selling price (Rs) per unit of product 

Desk 175 
Chair 55 
Cabinet 145 
Book case 130 
In order to maximise weekly profits, what should be the production programmes? assume that the items produced can be sold. Which department needs to be expanded for increasing profits.)
A used car dealer wishes to stock up his lot to maximise his profit. He can select cars A, E and C which are valued wholesale at Rs 5000, Rs 7000 and Rs 8000 respectively. These can be sold at Rs 6000, Rs 8500 and Rs 10,500 respectively. For each car type, the probabilities of sale are
Type of Car 
Probability of sale in 90 days 
A 
0.7 
B 
0.8 
C 
0.6 
For every two cars of type E, he should buy a one car of type A or C. If he has Rs 1,00,000 to invest, what should he buy to maximise his expected gain? Formulate the linear programming problem.
A certain farming organisation operates three farms of comparable productivity. The output of each farm is limited both by useable acreage and by the amount of water available for irrigation. Following is the data for upcoming season.
Farm 
Useable Acreage 
Water available in acre feet 
1 
400 
1500 
2 
600 
2000 
3 
300 
900 
The organisation is considering three crops for planting which differ primarily in their expected profit per acre and their consumption of water. Furthermore, the total average that can be devoted to each of the crops is limited by the amount 8 appropriate harvesting equipment available.
Crop 
Minimum Acreage 
Water consumption in acre feet per acre 
Expected profit per acre 
A 
700 
5 
Rs 400 
B 
800 
4 
Rs 300 
C 
300 
3 
Rs 100 
In order to maintain a uniform work load among the farms, it is the policy of the organisation that the percentage of useable acreage planted must be the same at each farm. However, any combination of the crops may be frown at any of the farms. The organisation wishes to know, how much of each crop should be planted at the respective farms in order to maximise expected profits. Formulate thus as a linear programming problem.
Illustrated Case Studies
Case Study No 1.
ABC Ltd engages Quality Control inspectors from a consultancy company which has a pool of such manpower as it does not want to have inspector on its own pay roll. It uses 40 inspectors of Grade 1 level and 60 inspectors of Grade II level. The company expects the following standards.
Atleast 1600 pieces must be inspected in a day of 8 hours.
If an error in inspection is made it will cost the company Rs 50. The company is interested in knowing the optimal assignment of inspectors so that the inspection costs are minimised.
The company uses three types of raw materials to produce the alloy of above specifications. The properties of the raw material required for this purpose are as given below.
Property 

Parameter of Specification 
Raw material P 
Raw material Q 
Raw material R 
Chromium (%) 
8 
12 
16 
Melting point (^{0}C) 
700^{0}C 
650^{0}C 
600^{0}C 
Specific Gravity 
0.98 
1.02 
0.96 
The cost of the raw materials per unit in open market are
P = Rs 10,000
Q = Rs 25,000
R = Rs 8000
The company wants stock to the specifications so that they can continue getting the orders from defence department, which is their main stay for profits and also give them the credibility and good will in the market. At the same time, they are interested in reducing the cost of raw materials to the minimum, Advise the company as to what percentage of raw materials P, Q and R are to be used for making the alloy.
Case Study No. 3
ABC Ltd is engaged in assembling different types of washing machines. The balance sheet of the company as on 31 March 2003 is as follows.
Liabilities 
Assets 

Equity share capital 
2,50,000 
Land 
2,00,000 
Capital Reserves 
20,000 
Building 
50,000 
General Reserves 
1,40,000 
Plant & Machinery 
1,20,000 
Profit & Loss A/c 
20,000 
Furniture 
20,000 
Long Term Loan 
1.50,000 
Transport 
25,000 
Loans 
75,000 
Inventory 
10,000 
(a) Bank X 
75,000 
Receivable 
70,000 
(b) Bank Y 
75,000 
Cash 
21,35,000 
Total 
7,30,000 
Total 
7,30,000 
The company is able to sell all the types of washing machine it manufactures but gets the payment only on the first of next month of the sales month. The company pays the labour, materials and other expenses in cash. The company had taken a loan of Rs 75,000 from bank X and this has to be paid back on 01.4.2003. However, the company has tied up with bank Y to take a loan of Rs 75,000. The other, overheads of the company are
a) Salaries Rs 30,000 for a month.
b) Interest on long term loan 8%
c) Interest on loan from Bank X and Bank Y – Rs 2000/month.
ABC Ltd is manufacturing the following types of washing machines. These have to be finished and bled in any assembly line. The following data is available for the production of the washing machines.
The company has an order of 4 semiautomatic and 10 fully automatic machines for the next month.
The management of the company is interested in knowing that how many units of each type of washing machines should they assemble next month so that they can earn maximum profit. The company is very careful regarding their functional matters and wants to be sure that the cash available next month is sufficient to meet all the operations of the next month. What advice will you give to the company management?
Case Study No Four
A Corporate house has made huge profits from their cashcow product which is very well accepted in the market. It is planning to launch a new product after one year and R & D department is in the advance stages of the development of the product. The corporate house has consulted its investment research department to park Rs 10 crore which has advised them as follows.
Type of Investment 

Parameter for decisionmaking 
A 
B 
C 
D 
Risk 
High 
High 
Medium 
Low 
Expected returns % 
40 
30 
10 
6 
The management in its Board meeting has decided the following guidelines for ensuring the safety of the funds.
(a) Total amount invested in high risk funds must be less than 50%.
(b) Total amount invested in medium risk funds must be less than 30%.
(c) Total amount invested in low risk funds must be less than 10%.
(d) Total amount invested in high risk funds A and B should be in the ratio of 2:3 of the total amount.
What should be the portfolio of the corporate house so thatthey are able to maximise their returns?
Formulate the problem as an LPP.
Case Study Five. A Company is manufacturing three products in its factory using three different routes by using Lathes, drills and shearing machines. The details of these are as follows:
Type of 
Product A 
Product B 
Product C 
Availability of Machines (Hours) 

Machines 
1 
2 
3 
1 
2 
1 
2 

Lathes 
0.4 
0.5 
 
0.6 
 
0.4 
 
300 
Drills 
0.6 
0.2 
0.4 
0.4 
0.2 
0.2 
0.6 
400 
Shearing Machine 
0.3 
0.6 
0.6 
0.2 
0.8 
0.5 
0.2 
500 
All the product manufactured can be sold in the market at sale price of product A Rs 200, product B Rs 260 and product C Rs 100. The company has to meet the market demand of 200, 220 and 180 units of products A, Band C respectively.
Formulate the problem as a LPP.
 Infeasible and unbounded solution
 Linearity and certainty in L.P. probelm.
 Basic feasible solution.
 Objective functions of L.P.P.
 Linearity and divisibility.
 Multiple optimum solution.
 Basic feasible solution.
 Linearity and divisibility.
 Multiple optimum solution.
10. Nonnegativity constraint in a L.P.P.
11. Linear Programming problem.
12. Graphic method.
13. Optimal solution of a L.P.P.
14. Initial Basic Solution of a L.P.P.
15. Assumptions underlying L.P.P.
16. Objective function of L.P.P.
17. Basic solution in L.P.P.
18. O.R. (Professional)
19. Feasible solution v/s Optimum solution of L.P.P. (Professional)
20. Objective function of a L.P.P. (Professional)
21. Feasible solution v/s Optimum solution. (Professional)
22. Discuss briefly the application of Linear Programming in various functional areas of management.
23. Discuss briefly the application of Linear Programming in decision making.
24. Discuss briefly the steps to formulate a Linear Programming problem. Explain with an example.
25. Discuss the formulation of a minimization linear programming problem.
27. Vitamin A and B found is in foods F_{1} and F_{2}. One unit of food F_{1} contains 3 units of vitamin A and 4 units of vitamin B and that of F_{2} contains 6 units of vitamin A and 3 units of vitamin B. One unit of food F_{1} and F_{2} costs Rs. 4 and Rs. 5 respectively. The minimum daily need per person of vitamin A and B is 80 and 100 units respectively. Assuming that anything in excess of daily minimum requirement is harmful, find out the optimum mixture of F_{1} and F_{2} at the minimum cost which meets the minimum requirement of vitamin A and B.
30. Orient Paper Mills produces two grades of paper X and Y. Because of raw material restrictions not more than 400 tons of grade X and 300 tons of grade Y can be produced in a week. There are 160 production hours in a week. It requires 0.2 and 0.4 hours to produce a ton of product X and Y respectively with corresponding profits of Rs. 20 and Rs. 50 per ton. Formulae a Linear Programming problem to optimize the product mix for maximum profit and solve it.
Prima Enterprises manufactures three type of dolls. The Boy requires half metre of red cloth, 11/2 metres of green cloth, 11/2 metres of black cloth and 5 kg. of fibre. The Girl requires ½ metre of red cloth, 2 metre of green cloth, 1 metre of black and 6 kg. of fibre. The Dog requires of ½ metre of red, 1 metre of green, ¼ metre of black and 2 kg. of fibre. The profits on the three are respectively 3, 5 and 2 rupees. The firm has 1,000 metres of red, 1,500 metres of green, 2,000 metres of black and 6,000 kg. of fibre. To find the number of dolls of each type to be manufactured, set up a L.P. for maximum profit.
Max. Z = 3X_{1} + 5X_{2} + 2X_{3}
Subject to
 Three products are produced on three different operations. The limits on the available times for the three operations are respectively 430, 460 and 420 minutes and the profit per unit for the three products are Rs. 3, Rs. 2 and Rs. 5 respectively.
Time in minutes per unit on each machine operation is as follows:
Operations 
I 
II 
III 
1 
1 
2 
1 
2 
3 
0 
2 
3 
1 
4 
0 
Formulate following L.P.P. One unit of product P, contributes Rs. 70 and requires 30 units of raw material and 20 hours of labour. One unit of P_{1} contributes Rs. 50 and requires 10 units of raw material and 10 hours of labour. Availability of raw material is 480 units and time available is 400 hours,
 An advertising company wishes to plan an ad. campaign in three different media. T.V., Radio and magazine, The purpose of advertising is to reach as many potential customers as possible. Result of market survey are as follows:
TV Prime day (Rs.) 
Prime Time (Rs.) 
Radio (Rs.) 
Magazine (Rs.) 

Cost of an Ad. Unit 
40,000 
75,000 
30,000 
15,000 
No. of potential customers Reached/Unit 
4,00,000 
9,00,000 
5,00,000 
2,00,000 
No. of women Customers reached/Unit 
3,00,000 
4,00,000 
2,00,000 
1,00,000 
The company does not want to spend more than Rs, 8,00,000 on advertising. It is further required that:
 At least 2 million exposures take place among women.
 Ad. on T.V. be limited to Rs. 5,00,000
 At least 3 ad, units be bought on prime day and two units during prime time and
 No. of ad units on Radio and Magazine should each be between 5 and 10.
REVIEW
 Infeasible and unbounded solution (ii) Linearity and certainty in L.P. problem
 (i) Basic feasible solution (ii) Objective functions of L.P.P.
 Linearly and divisibility (ii) Multiple optimum solution.
 Basic feasible solution.
 (i) Linearity and divisibility (ii) Multiple optimum solution.
 NonNegativity constraint in a L.P.P.
 Linear Programming problem (ii) Graphical method (iii) Optimal solution of a
LPP.  Initial Basic solution of a L.P.P.
 (a) Assumption underlying L.P.P. (b) Objective function of L.P.P.
10. Discuss the formulation of a minimization linear programming problem.
11. Discuss briefly the application of Linear Programming in various functional areas of management.
12. Discuss briefly the application of Linear Programming in decision making.
13. Discuss briefly the steps to formulate Linear Programming problem. Explain with an example.
14. Define:
 Feasible solution
 Basic solution
 Basic feasible solution
 Non degenerate
 BFS
 Degenerate BFS
 Optimum BFS
Unbounded solution
 Vitamin A and B is found in foods F_{1} and F_{2}. One unit of food F_{1} contains 3 units of vitamin A and 4 units of vitamin B and that of F, contains 6 units of vitamin A and 3 units of vitamin B. One unit of food F_{1} and F_{2} cost Rs. 4 and Rs. 5 respectively. The minimum daily need per person of vitamin A and B is 80 and 100 units respectively. Assuming that anything in excess of daily minimum requirement is harmful, find out the optimum mixture of F_{1} and F_{2} at the minimum cost which meets the minimum requirement of Vitamin A and B.
Formulate this as a Linear Programming Problem.
A company sells two products A and B and makes a profit of Rs. 40 and Rs. 30 per unit respectively. Two products are produced in a common production process and sold in different markets. Production process has a total capacity of 30,000 man hours. It takes 3 hours to produce a unit of A and one hour to produce a unit of B. Market survey shows that the maximum units of A that can be sold 8,000 and that of B 12,000. Subject to these liminations, the product can be sold in any combination.
Prima Enterprises manufactures three types of dolls. The Boy requires half meter of red cloth. 11/2 meters of green cloth, 2 meter of black cloth and 5 kg. of fibre. The Girls requires ½ meter of red cloth, 2 meter of green cloth, 1 meter of black and 6 kg of fibre. The Dog requires ½ meter of red, 1 meter of green, ¼ meter of black and 2 kg of fibre. The profit on the three are respectively 3, 5 and 2 rupees. The firm has 1,000 meters of red, 1,500 meters of green, 2,000 meters of black and 6,000 kg. of fibre. To find the number of dolls of each type to be manufactured, set up a L.P. for maximum profit.
(b) Three products are produced on three different operations. The limits on the available time for the three operations are respectively 430, 460 and 420 minutes and the profit per unit for the three products are Rs. 3, Rs. 2 and Rs. 5 respectively. Time in minutes per unit on each machine operation is as follows:
Product 

Operations 
I 
II 
III 
1 
1 
2 
1 
2 
3 
0 
2 
3 
1 
4 
0 
Write, L.P. model for this problem.
Old hens can be bought at Rs. 2 each and young ones at Rs. 5 each. The old hens lay 3 eggs per week and the young ones lay 5 eggs per week, each egg being worth 30 Paise. A hen costs Rs. 1 per week to feed. Mr Amit has only Rs. 80 to spend for hens. How many of each kind should Mr. Amit buy to give a profit of atleast Rs. 6 per weak, assuming that Mr. Amit cannot have more than 20 hens? Give the mathematical formulation of LPP only.
A firm makes product A and B and has a total production of a capacity of 9 tonn per day. A and B requiring the same production capacity. The firm has a permanent contract to supply alteast 2 tonnes of A and 3 tonnes of B per day to another Co. Each tonne of A requires 20 machine hour production time and each tonn of B requires 50 machine hour production time, the daily maximum possible of machine hrs is 360. Profit per unit of product A is SO
 and that of product B is Rs. 120. Formulate LPP.
Recent Comments