USA: +1-585-535-1023

UK: +44-208-133-5697

AUS: +61-280-07-5697

COMPUTER SOLUTION METHODS

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

  1. fully understands the LP model and its assumptions.
  2. is skilful in recognising an LP problem.
  3. can formulate the problems well.
  4. can arrange for solution using a computer package and is
  5. 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.

  1. All constraints must be stated as equations.
  2. The right hand side of a constraint cannot be negative.
  3. All variables are restricted to non-negative 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 non-basic variables. The Simplex method determines whether the objective function can be improved by exchanging a basic variable and a non-basic variable. If an exchange will result in an improvement, an existing basic variable is set equal to 0 (becoming a non-basic variable) an existing non-basic variable is included in the pool of basic variables and the system of equations is re-solved 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

  1. . What are the essential characteristics of a Linear Programming model?

 

  1. Explain the terms : Key decision, objective, alternative and restrictions in the context of linear optimisation models by assuming a suitable industrial situation.
  2. Discuss the application of LP in any functional area of management. Use suitable example from business or industry,
  3. “Linear Programming is the most widely used and most successfully used mathematical approach to decision-making”, Comment
  4. Explain the advantages and major limitations of LP model. Illustrate your answer with suitable examples.
  5. What are the major allocation problems that can be solved by using LP model? Briefly discuss each one of them.
  6. “Each LP problem with a feasible solution area offers infinite number of solutions”. Do you agree with this statement? Justify your answer.
  7. What are the basic characteristics and assumptions of a LP model?
  8. 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.

  1. Multiple optimal solutions.
  2. No – feasible solution
  3. 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

  1. Linearity
  2. Feasible Solution
  3. Objective function
  4. Unbounded solution
  5. 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.

20. 

  1. 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.

22. 

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 semi-skilled 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 semi-skilled man. The ordinary model requires one hour work by a skilled man and 3 hours work by a semi-skilled 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 machine-minutes 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 man-days for tomatoes and reddish and 6 man-days for lettuce. A total of 400 man- days of labour are available at Rs 20 per man-day.

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 book-cases. 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

Book-cases

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

Book-cases

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 (0C)

7000C

6500C

6000C
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 semi-automatic 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 cash-cow 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 decision-making

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 that-they 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.

  1. Infeasible and unbounded solution
  2. Linearity and certainty in L.P. probelm.
  3. Basic feasible solution.
  4. Objective functions of L.P.P.
  5. Linearity and divisibility.
  6. Multiple optimum solution.
  7. Basic feasible solution.
  8. Linearity and divisibility.
  9. Multiple optimum solution.

10. Non-negativity 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 F1 and F2. One unit of food F1 contains 3 units of vitamin A and 4 units of vitamin B and that of F2 contains 6 units of vitamin A and 3 units of vitamin B. One unit of food F1 and F2 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 F1 and F2 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, 1-1/2 metres of green cloth, 1-1/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 = 3X1 + 5X2 + 2X3

Subject to

 

  1. 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 P1 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,

  1. 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:

  1. At least 2 million exposures take place among women.
  2. Ad. on T.V. be limited to Rs. 5,00,000
  3. At least 3 ad, units be bought on prime day and two units during prime time and
  4. No. of ad units on Radio and Magazine should each be between 5 and 10.

 

REVIEW

  1. Infeasible and unbounded solution (ii) Linearity and certainty in L.P. problem
  2. (i) Basic feasible solution (ii) Objective functions of L.P.P.
  3. Linearly and divisibility (ii) Multiple optimum solution.
  4. Basic feasible solution.
  5. (i) Linearity and divisibility (ii) Multiple optimum solution.
  6. Non-Negativity constraint in a L.P.P.
  7. Linear Programming problem (ii) Graphical method (iii) Optimal solution of a
    LPP.
  8. Initial Basic solution of a L.P.P.
  9. (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:

  1. Feasible solution
  2. Basic solution
  3. Basic feasible solution
  4. Non degenerate
  5. BFS
  6. Degenerate BFS
  7. Optimum BFS

Unbounded solution

  1. Vitamin A and B is found in foods F1 and F2. One unit of food F1 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 F1 and F2 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 F1 and F2 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.

Orient paper mills products 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 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 products X and Y respectively, with corresponding profits of Rs. 20 and Rs. 50 per ton. Formulate a Linear Programming problem to optimize the product mix for maximum profit.

Prima Enterprises manufactures three types of dolls. The Boy requires half meter of red cloth. 1-1/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

  1. and that of product B is Rs. 120. Formulate LPP.