Karnataka Class 12 Commerce Maths Unit V – Linear Programming Complete Notes
Karnataka Class 12 Commerce Maths Unit V – Linear Programming : CBSE is a renowned educational Board, which comes under the Union Government of India. This eminent board was formed in 1952 and associated with the Board of High School and Intermediate Education, Rajputana. Ajmer, Gwalior, Merwara and Central India were included in the administrative territory of this board along with the other places including Bhopal, Ajmer and Vindhya Pradesh. From 1952 onwards, it has been providing a standard education and robust learning environment to all. The Central Board of Secondary Education or CBSE is a prestigious board of education and it provides affiliation to public and private schools. Apart from this, all Jawahar Navodaya Vidyalayas and kendriya vidyalayas are affiliated to this board.
Karnataka Class 12 Commerce Maths Unit V – Linear Programming Complete Notes
Karnataka Class 12 Commerce Maths Unit V – Linear Programming : Here our team members provides you Karnataka Class 12 Commerce Maths Unit V – Linear Programming Complete Notes in pdf format. Here we gave direct links for you easy to download Karnataka Class 12 Commerce Maths Unit V – Linear Programming Complete Notes. Karnataka Class 12 Commerce Maths Unit V – Linear Programming topics are Introduction, related terminology such as constraints, objective function, optimization, different types of linear programming (L.P.) problems, mathematical formulation of L.P. problems, graphical method of solution for problems in two variables, feasible and infeasible regions (bounded and unbounded), feasible and infeasible solutions, optimal feasible solutions (up to three non-trivial constraints). Download these Karnataka Class 12 Commerce Maths Unit V – Linear Programming Complete Notes and read well.
Download here Karnataka Class 12 Commerce Maths Complete Notes In PDF Format
Karnataka Class 12 Commerce Maths Unit V – Linear Programming Complete Notes
Karnataka Class 12 Commerce Maths Unit V – Linear Programming : Linear programming (LP) (also called linear optimization) is a method to achieve the best outcome (such as maximum profit or lowest cost) in a mathematical model whose requirements are represented by linear relationships. Linear programming is a special case of mathematical programming (mathematical optimization). More formally, linear programming is a technique for the optimization of a linear objective function, subject to linear equality and linear inequality constraints. Its feasible region is a convex polythene, which is a set defined as the intersection of finitely many half spaces, each of which is defined by a linear inequality. Its objective function is a real-valued caffeine (linear) function defined on this polyhedron. A linear programming algorithm finds a point in the polyhedron where this function has the smallest (or largest) value if such a point exists.
Linear programs are problems that can be expressed in canonical form as
where x represents the vector of variables (to be determined), c and b are vectors of (known) coefficients, A is a (known) matrix of coefficients, and is the matrix transpose. The expression to be maximized or minimized is called the objective function (c^{T}x in this case). The inequalities Ax ≤ b and x ≥ 0 are the constraints which specify a convex polytope over which the objective function is to be optimized. In this context, two vectors are comparable when they have the same dimensions. If every entry in the first is less-than or equal-to the corresponding entry in the second then we can say the first vector is less-than or equal-to the second vector.
Linear programming can be applied to various fields of study. It is widely used in business and economics, and is also utilized for some engineering problems. Industries that use linear programming models include transportation, energy, telecommunications, and manufacturing. It has proved useful in modeling diverse types of problems in planning, routing, scheduling, assignment, and design.
Karnataka Class 12 Commerce Maths Unit V – Linear Programming Complete Notes
Karnataka Class 12 Commerce Maths Unit V – Linear Programming : Linear programming is the process of taking various linear inequalities relating to some situation, and finding the “best” value obtainable under those conditions. A typical example would be taking the limitations of materials and labor, and then determining the “best” production levels for maximal profits under those conditions.
In “real life”, linear programming is part of a very important area of mathematics called “optimization techniques”. This field of study (or at least the applied results of it) are used every day in the organization and allocation of resources. These “real life” systems can have dozens or hundreds of variables, or more. In algebra, though, you’ll only work with the simple (and graphable) two-variable linear case.
The general process for solving linear-programming exercises is to graph the inequalities (called the “constraints”) to form a walled-off area on the x,y-plane (called the “feasibility region”). Then you figure out the coordinates of the corners of this feasibility region (that is, you find the intersection points of the various pairs of lines), and test these corner points in the formula (called the “optimization equation”) for which you’re trying to find the highest or lowest value.
ADVERTISEMENT | |
Find the maximal and minimal value of z = 3x + 4y subject to the following constraints:
= 0, x – y <= 2″ style=”border: 0px;”>
The three inequalities in the curly braces are the constraints. The area of the plane that they mark off will be the feasibility region. The formula “z = 3x + 4y” is the optimization equation. I need to find the (x, y) corner points of the feasibility region that return the largest and smallest values of z.
My first step is to solve each inequality for the more-easily graphed equivalent forms:
= x – 2″ style=”border: 0px;”>
It’s easy to graph the system: Copyright © Elizabeth Stapel 2006-2011 All Rights Reserved
To find the corner points — which aren’t always clear from the graph — I’ll pair the lines (thus forming a system of linear equations) and solve:
y = –( ^{1}/_{2} )x + 7 y = 3x | y = –( ^{1}/_{2} )x + 7 y = x – 2 | y = 3x y = x – 2 |
–( ^{1}/_{2} )x + 7 = 3x –x + 14 = 6x 14 = 7x 2 = xy = 3(2) = 6 | –( ^{1}/_{2} )x + 7 = x – 2 –x + 14 = 2x – 4 18 = 3x 6 = xy = (6) – 2 = 4 | 3x = x – 2 2x = –2 x = –1y = 3(–1) = –3 |
corner point at (2, 6) | corner point at (6, 4) | corner pt. at (–1, –3) |
So the corner points are (2, 6), (6, 4), and (–1, –3).
Somebody really smart proved that, for linear systems like this, the maximum and minimum values of the optimization equation will always be on the corners of the feasibility region. So, to find the solution to this exercise, I only need to plug these three points into “z = 3x + 4y“.
(2, 6): z = 3(2) + 4(6) = 6 + 24 = 30
(6, 4): z = 3(6) + 4(4) = 18 + 16 = 34
(–1, –3): z = 3(–1) + 4(–3) = –3 – 12 = –15
Then the maximum of z = 34 occurs at (6, 4),
and the minimum of z = –15 occurs at (–1, –3).
Karnataka Class 12 Commerce Maths Unit V – Linear Programming Complete Notes
Karnataka Class 12 Commerce Maths Unit V – Linear Programming : Linear programming is a simple technique where we depict complex relationships through linear functions and then find the optimum points. The important word in previous sentence is depict. The real relationships might be much more complex – but we can simplify them to linear relationships.
Applications of linear programming are every where around you. You use linear programming at personal and professional fronts. You are using linear programming when you are driving from home to work and want to take the shortest route. Or when you have a project delivery you make strategies to make your team work efficiently for on time delivery.
Example of a linear programming problem
Let’s say a FedEx delivery man has 6 packages to deliver in a day. The warehouse is located at point A. The 6 delivery destinations are given by U, V, W, X, Y and Z. The numbers on the lines indicate the distance between the cities. To save on fuel and time the delivery person wants to take the shortest route.
So, the delivery person will calculate different routes for going to all the 6 destinations and then come up with the shortest route. This technique of choosing the shortest route is called linear programming.
In this case, the objective of the delivery person is to deliver the parcel on time at all 6 destinations. The process of choosing the best route is called Operation Research. Operation research is an approach to decision-making, which involves a set of methods to operate a system. In the above example, my system was the Delivery model.
Linear programming is used for obtaining the most optimal solution for a problem with given constraints. In linear programming, we formulate our real life problem into a mathematical model. It involves an objective function, linear inequalities with subject to constraints.
Is the linear representation of the 6 points above representative of real world? Yes and No. It is oversimplification as the real route would not be a straight line. It would likely have multiple turns, U turns, signals and traffic jams. But with a simple assumption, we have reduced the complexity of the problem drastically and are creating a solution which should work in most scenarios.
Formulating a problem – Let’s manufacture some chocolates
Example: Consider a chocolate manufacturing company which produces only two types of chocolate – A and B. Both the chocolates require Milk and Choco only. To manufacture each unit of A and B, following quantities are required:
- Each unit of A requires 1 unit of Milk and 3 units of Choco
- Each unit of B requires 1 unit of Milk and 2 units of Choco
The company kitchen has a total of 5 units of Milk and 12 units of Choco. On each sale, the company makes a profit of
- Rs 6 per unit A sold
- Rs 5 per unit B sold.
Now, the company wishes to maximize its profit. How many units of A and B should it produce respectively?
Solution: The first thing I’m gonna do is represent the problem in a tabular form for better understanding.
Milk | Choco | Profit per unit | |
A | 1 | 3 | Rs 6 |
B | 1 | 2 | Rs 5 |
Total | 5 | 12 |
Let the total number of units produced of A be = X
Let the total number of units produced of B be = Y
Now, the total profit is represented by Z
The total profit the company makes is given by the total number of units of A and B produced multiplied by its per unit profit Rs 6 and Rs 5 respectively.
Profit: Max Z = 6X+5Y
which means we have to maximize Z.
The company will try to produce as many units of A and B to maximize the profit. But the resources Milk and Choco are available in limited amount.
As per the above table, each unit of A and B requires 1 unit of Milk. The total amount of Milk available is 5 units. To represent this mathematically,
X+Y ≤ 5
Also, each unit of A and B requires 3 units & 2 units of Choco respectively. The total amount of Choco available is 12 units. To represent this mathematically,
3X+2Y ≤ 12
Also, the values for units of A can only be integers.
So we have two more constraints, X ≥ 0 & Y ≥ 0
For the company to make maximum profit, the above inequalities have to be satisfied.
This is called formulating a real-world problem into a mathematical model.
Common terminologies used in Linear Programming
Let us define some terminologies used in Linear Programming using the above example.
- Decision Variables: The decision variables are the variables which will decide my output. They represent my ultimate solution. To solve any problem, we first need to identify the decision variables. For the above example, the total number of units for A and B denoted by X & Y respectively are my decision variables.
- Objective Function: It is defined as the objective of making decisions. In the above example, the company wishes to increase the total profit represented by Z. So, profit is my objective function.
- Constraints: The constraints are the restrictions or limitations on the decision variables. They usually limit the value of the decision variables. In the above example, the limit on the availability of resources Milk and Choco are my constraints.
- Non-negativity restriction: For all linear programs, the decision variables should always take non-negative values. Which means the values for decision variables should be greater than or equal to 0.
Process to formulate a Linear Programming problem
Let us look at the steps of defining a Linear Programming problem generically:
- Identify the decision variables
- Write the objective function
- Mention the constraints
- Explicitly state the non-negativity restriction
For a problem to be a linear programming problem, the decision variables, objective function and constraints all have to be linear functions.
If the all the three conditions are satisfied, it is called a Linear Programming Problem.
Download here Karnataka Class 12 Commerce Maths Unit V – Linear Programming Complete Notes In PDF Format
Karnataka Class 12 Commerce Maths Unit V – Linear Programming Complete Notes
Cakart.in provides India’s top Class 12 Commerce faculty video classes – online & in Pen Drive/ DVD – at very cost effective rates. Get Class 12 Commerce Video classes from www.cakart.in to do a great preparation for primary Student.