Linear programming. (L P).
A quote from Swami Vivekananda.
“He alone teaches who has something to give for teaching is not talking, teaching is not imparting doctrines, it is communicating.”
Linear programming is all about maximization and minimization; maximum output with minimum input. The solutions are economical, for a problem with all its limitations, constraints. we have used the words limitations, constraints.
Methods to Solve Linear Programming
a) Graphical Method
b) Simplex Method
Limitation: As per dictionary, means restriction, a point beyond which something does not continue/ a ceiling.
Constraint: restriction/stipulation/to put limit on or subject to limitations.
Applications: Business and investment. Railway, air travel, Bus travel, manufacturing and transportation, Electronics (chip production) to fabricate shortest routes in the chip, (VLSI --very large-scale integration), in Diet optimization .ie to say combination of foods to get all nutritional requirements with less cost.
Objective function (OF): A linear equation z = ax + by, where a and b are constants, whose value is to be maximized or minimized, is known as objective function.
Feasible Region (FR): A common region which is found by all constraints. (Only non-negative constraints.) is known as feasible region. It is also called as a convex polygon. The region apart from the feasible region is known as infeasible region.
Optimal feasible solution: Any point in the F R that shows the optimal value of the Objective function is called feasible solution. In a LPP the maximum value of O F is always finite.
Solve a LP question:
1. To fix up the variables, form the linear inequations from the data given, in the question.
2. To form Objective function where we decide with minimum cost, to get maximum profit /gain.
3. To draw the graphs for the formulated inequations and find the truth set region. We shall be able to assess the minimum or maximum from the vertices of the boundary of the region, substituting the coordinates in the objective function.
Objective function expresses the main aim of the model- either to be minimised or maximised. It is a linear equation of the form Z = ax + by.
Note: Some questions do have the words, at least, at the most. One has to take care, pay attention. At least bare minimum (>=); at the most maximum (< =)
Problems for discussion:
A chemist wishes to provide his customers, at, least cost, the minimum daily requirements of two vitamins A, B by using a mixture of two products P, Q. The amount of each vitamin in one gram of each product, cost per gram of each product and the minimum daily requirements are given below. Find the least expensive combination which provides the minimum requirement of the two vitamins.
Find the least expensive combination which provides the minimum requirement of the two vitamins.
Ans: Let x grams of product P and y grams of product Q be required for making a mixture which will provide at, least cost the minimum requirements of two vitamins A and B.
The inequations as per given date are: 6x + 2y > = 12, ie 3x + y>= 6 and
2 x + 2Y >= 8 ie x + y >= 4, x > =0, y > = 0. Min Z = 1.x + 2y
The feasible region is unbounded. the coordinates are A (0,6), B (1,3) C (4,0)
The cost is minimum at B (1, 3). Hence the chemist has to make mixture of 1 gm of product P and 3 grams of product Q, so as to give 12 units of vitamin A and 8 units of vitamin B. it cost Rs. 1 + 6 = Rs.7.
2. Solve the problem graphically:
Minimize Z = -3x +4y subject to x +2y <= 8 ,3x + 2y <= 12, x > =0, y > = 0.
The feasible region coordinates are A (2,3), B (3,2) C (4,0);
On verification Z is – 12, at (4, 0), the minimum value.
3.A furniture dealer deals in only two items, chairs and stools. He has Rs .10000 to invest and a space to store 60 pieces. A chair cost him Rs .500, and a stool Rs. 100.He can sell a chair at a profit of Rs 60 and a stool at a profit of Rs 25. Assume that he can sell all the items that he pays for, how should he invest his money in order that he may maximize his profit?
Ans: As per given data let us proceed to find the profit.
Let x be the number of chairs and y be the number of stools.
x +y <= 60 ---1.; 500x + 100y <= 10000 i.e.(5x+y) <= 100 -----2; x>= 0--- 3. y >=0 ----4.
P is maximum when x = 10 and y = 50.,60 x 10 + 25 x 60 = 600 + 1250= Rs.1850.
Hence for maximum profit, the dealer must invest Rs.1850, purchase 10 chairs and 50 stools.
4.A dealer in rural area wishes to purchase a number of sewing machines. He has only rs.28800 to invest and has space for at most 20 items. An electronic machine costs him Rs.1800 and manually operated machine costs him Rs. 1200.He can sell an electronic machine at a profit of Rs.110, and manually operated machine at a profit of Rs.90. Assume that he can sell all the items he has purchased. How much should he invest in order to maximize his profit.
Ans: Let us assume, the number of electronic machines be x and y be number of manually operated machine,
As per given data, x + y < = 20 and 1800x+ 1200y < = 28800 ie 3x + 2y <= 48.
x > =0, y > = 0. To maximize z = 110 x+ 90 y
Feasible region coordinates are A (0,20), B (8,12) C (12,6), D (16.0)
Z is maximum at x = 8 and y = 12. Hence the dealer has to invest Rs.1960 ,8 electronic machines and 12 manually operated machine.
5. An aeroplane carries a maximum of 200 passengers. A profit of Rs 400 is made on each first-class ticket and a profit of Rs 300 is made on each economy class ticket. The airline reserves at least 20 seats for first class. However at least 4 times as many passengers prefer to travel by economy class than by first class. Determine how many of each type of tickets must be sold in order to maximize profit for the airline. What is maximum profit.
Ans: Let the number of first-class tickets sold be x and the number of economy class be y. As per data x+ y <= 200; x < = 20, y < = 4x, x >=0, y > = 0.
Z = 400 x + 300 y.
The feasible region vertices are A (20,80), B (40,160); C (20, 180);
Z is maximum when x = 40 and y = 160.
Hence the airline should sell 40 first class tickets, and 160 economy class tickets. Max profit is Rs. 400x40 + 300x160 = 16000+ 48000= Rs. 64000.
6.A person wishes to invest at most Rs.18000 in savings certificate and national savings bonds. He has a plan to invest at least Rs. 4000 in savings certificate and Rs.5000 in national savings bonds. The rate of interest on savings certificate 6.8% per annum, and that on national savings Bond is 7.75% per annum. Determine his investment in each scheme so as to earn maximum interest in a year.
Ans: Let Rs, X be invested in savings certificate and Rs. Y be invested in national savings bonds. To maximize Z = 6.8% x X + 7.75% x Y
As per given data the constraints are, X + Y <= 18000, X>= 4000,
Y>= 5000, X>=0, Y >= 0.
The feasible region coordinates are A (4000,5000), B (13000,5000), C (4000,14000),
The maximum is at C and the annual interest earned is Rs.1357 (Rs 272+ Rs .1357).
