## CBSE Class 12 Commerce Mathematics Linear Programming Introduction

CBSE Class 12 Commerce Mathematics Linear Programming : The CBSE envisions a robust, vibrant and holistic school education that will engender excellence in every sphere of human endeavour. The Board is committed to provide quality education to promote intellectual, social and cultural vivacity among its learners. It works towards evolving a learning process and environment, which empowers the future citizens to become global leaders in the emerging knowledge society. The Board advocates Continuous and Comprehensive Evaluation with an emphasis on holistic development of learners. The Board commits itself to providing a stress-free learning environment that will develop competent, confident and enterprising citizens who will promote harmony and peace.

### CBSE Class 12 Commerce Mathematics Linear Programming Complete Notes

CBSE Class 12 Commerce Mathematics Linear Programming : Cakart team members provides here CBSE Class 12 Commerce Mathematics Linear Programming Complete Notes and other CBSE Class 12 Commerce Mathematics Complete Notes in pdf format. We provides you direct link for downloading CBSE Class 12 Commerce Mathematics Linear Programming Complete Notes in pdf format. Download CBSE Class 12 Commerce Mathematics Linear Programming Complete Notes and read well.

### CBSE Class 12 Commerce Mathematics Linear Programming Complete Notes

CBSE Class 12 Commerce Mathematics Linear Programming : The history of mathematics can be seen as an ever-increasing series of abstractions. The first abstraction, which is shared by many animals was probably that of numbers: the realization that a collection of two apples and a collection of two oranges (for example) have something in common, namely quantity of their members. Greek mathematician Pythagoras (c. 570 – c. 495 BC), commonly credited with discovering the Pythagorean theorem Mayan numerals

As evidenced by tallies found on bone, in addition to recognizing how to count physical objects, prehistoric peoples may have also recognized how to count abstract quantities, like time – days, seasons, years. Evidence for more complex mathematics does not appear until around 3000 BC, when the Babylonians and Egyptians began using arithmetic, algebra and geometry for taxation and other financial calculations, for building and construction, and for astronomy. The earliest uses of mathematics were in trading, land measurement, painting and weaving patterns and the recording of time.

### Download here CBSE Class 12 Commerce Mathematics Linear Programming Complete Notes in pdf format

### CBSE Class 12 Commerce Mathematics Linear Programming Complete Notes

CBSE Class 12 Commerce Mathematics Linear Programming : CBSE Class 12 Commerce Mathematics Linear Programming introductory notes on topics that fall under the broad heading of the field of operations research (OR). They were originally used by me in an introductory OR course I give at Imperial College. They are now available for use by any students and teachers interested in OR subject to the following conditions.

#### Linear programming – solution

CBSE Class 12 Commerce Mathematics Linear Programming : CBSE Class 12 Commerce Mathematics Linear Programming : To get some insight into solving LP’s consider the Two Mines problem that we had before – the LP formulation of the problem was:

minimise 180x + 160y subject to 6x + y >= 12 3x + y >= 8 4x + 6y >= 24 x <= 5 y <= 5 x,y >= 0

Since there are only two variables in this LP problem we have the graphical representation of the LP given below with the feasible region (region of feasible solutions to the constraints associated with the LP) outlined.

To draw the diagram above we turn all inequality constraints into equalities and draw the corresponding lines on the graph (e.g. the constraint 6x + y >= 12 becomes the line 6x + y = 12 on the graph). Once a line has been drawn then it is a simple matter to work out which side of the line corresponds to *all* feasible solutions to the original inequality constraint (e.g. *all* feasible solutions to 6x + y >= 12 lie to the right of the line 6x + y = 12).

CBSE Class 12 Commerce Mathematics Linear Programming : We determine the optimal solution to the LP by plotting (180x + 160y) = K (K constant) for varying K values (iso-profit lines). One such line (180x + 160y = 180) is shown dotted on the diagram. The smallest value of K (remember we are considering a minimisation problem) such that 180x + 160y = K goes through a point in the feasible region is the value of the optimal solution to the LP (and the corresponding point gives the optimal values of the variables).

CBSE Class 12 Commerce Mathematics Linear Programming : Hence we can see that the optimal solution to the LP occurs at the vertex of the feasible region formed by the intersection of 3x + y = 8 and 4x + 6y = 24. Note here that it is *inaccurate* to attempt to read the values of x and y off the graph and instead we solve the simultaneous equations

- 3x + y = 8
- 4x + 6y = 24

to get x = 12/7 = 1.71 and y = 20/7 = 2.86 and hence the value of the objective function is given by 180x + 160y = 180(12/7) + 160(20/7) = 765.71

Hence the optimal solution has cost 765.71

It is clear that the above graphical approach to solving LP’s can be used for LP’s with two variables but (alas) most LP’s have more than two variables. This brings us to the *simplex* algorithm for solving LP’s.

CBSE Class 12 Commerce Mathematics Linear Programming :

#### Simplex

Note that in the example considered above the optimal solution to the LP occurred at a vertex (corner) of the feasible region. In fact it is true that for *any* LP (not just the one considered above) the optimal solution occurs at a vertex of the feasible region. This fact is the key to the simplex algorithm for solving LP’s.

Essentially the simplex algorithm starts at one vertex of the feasible region and moves (at each iteration) to another (adjacent) vertex, improving (or leaving unchanged) the objective function as it does so, until it reaches the vertex corresponding to the optimal LP solution.

The simplex algorithm for solving linear programs (LP’s) was developed by Dantzig in the late 1940’s and since then a number of different versions of the algorithm have been developed. One of these later versions, called the *revised simplex* algorithm (sometimes known as the “product form of the inverse” simplex algorithm) forms the basis of most modern computer packages for solving LP’s.

Although the basic simplex algorithm is relatively easy to understand and use, the fact that it is widely available in the form of computer packages means that I decided it was not worth teaching you the details of the simplex algorithm. Instead I decided to teach you some things about the output from a simplex based LP package.

#### LP output

Recall the production planning problem concerned with four variants of the same product which we formulated before as an LP. To remind you of it we repeat below the problem and our formulation of it.

**CBSE Class 12 Commerce Mathematics Linear Programming : **

#### Production planning problem

A company manufactures four variants of the same product and in the final part of the manufacturing process there are assembly, polishing and packing operations. For each variant the time required for these operations is shown below (in minutes) as is the profit per unit sold.

Assembly Polish Pack Profit (£) Variant 1 2 3 2 1.50 2 4 2 3 2.50 3 3 3 2 3.00 4 7 4 5 4.50

- Given the current state of the labour force the company estimate that, each year, they have 100000 minutes of assembly time, 50000 minutes of polishing time and 60000 minutes of packing time available. How many of each variant should the company make per year and what is the associated profit?
- Suppose now that the company is free to decide how much time to devote to each of the three operations (assembly, polishing and packing) within the total allowable time of 210000 (= 100000 + 50000 + 60000) minutes. How many of each variant should the company make per year and what is the associated profit?

#### Production planning solution

#### Variables

Let:

x_{i} be the number of units of variant i (i=1,2,3,4) made per year

T_{ass} be the number of minutes used in assembly per year

T_{pol} be the number of minutes used in polishing per year

T_{pac} be the number of minutes used in packing per year

where x_{i} >= 0 i=1,2,3,4 and T_{ass}, T_{pol}, T_{pac} >= 0

#### Constraints

(a) operation time definition

T_{ass} = 2x_{1} + 4x_{2} + 3x_{3} + 7x_{4} (assembly)

T_{pol} = 3x_{1} + 2x_{2} + 3x_{3} + 4x_{4} (polish)

T_{pac} = 2x_{1} + 3x_{2} + 2x_{3} + 5x_{4} (pack)

(b) operation time limits

The operation time limits depend upon the situation being considered. In the first situation, where the maximum time that can be spent on each operation is specified, we simply have:

T_{ass} <= 100000 (assembly)

T_{pol} <= 50000 (polish)

T_{pac} <= 60000 (pack)

In the second situation, where the only limitation is on the total time spent on all operations, we simply have:

T_{ass} + T_{pol} + T_{pac} <= 210000 (total time)

#### Objective

Presumably to maximise profit – hence we have

maximise 1.5x_{1} + 2.5x_{2} + 3.0x_{3} + 4.5x_{4}

which gives us the complete formulation of the problem.

**CBSE Class 12 Commerce Mathematics Linear Programming : **

**Solution – using the QSB package**

Using the package we have:

which sets up the input and then we have a spreadsheet type screen into which we enter the problem data, as below

There are a number of points to make:

- In order to input an LP to the package we need to rearrange the constraints such that the right-hand side of the constraint is just a number (and hence all the variables are collected together on the left-hand side of the constraint).
- Lower and upper bounds allows us to constrain the values a single variable may take, i.e. lower bound <= variable <= upper bound. We could, if we have wished, entered the restrictions on T
_{ass}, T_{pol}and T_{pac}above as bounds rather than as explicit constraints. - Always save your problem at regular intervals, and especially after input – if you do not then you may lose it (e.g. if you exit the package without first having saved the problem).
- If you use the package you have various options involving solving and displaying tableau. If I was going to teach you the simplex algorithm in detail then the term “tableau” would become familiar to you. As I do not intend to go into that level of detail then we solve without displaying any tableau.
- MPS – stands for Mathematical Programming System and is a standard data format (initially from IBM). You may encounter it if you ever solve LP’s. All serious LP packages will read an MPS file and MPS files are now a common way of transferring LP problems between different people and different software packages.

We can show the problem in a more natural form (equation form) by using “Switch to Normal Model Form” to get:

The solution to this problem is also shown below.

We can see that the optimal solution to the LP has value 58000 (£) and that T_{ass}=82000, T_{pol}=50000, T_{pac}=60000, X_{1}=0, X_{2}=16000, X_{3}=6000 and X_{4}=0.

This implies that we only produce variants 2 and 3 (a somewhat surprising result in that we are producing none of variant 4 which had the highest profit per unit produced).

- How can you explain (in words) the fact that it appears that the best thing to do is not to produce any of the variant with the lowest profit per unit?
- How can you explain (in words) the fact that it appears that the best thing to do is not to produce any of the variant with the highest profit per unit?

Referring back to the physical situation we can see that at the LP optimal we have 18,000 minutes of assembly time that is not used (T_{ass}=82000 compared with a maximum time of 100000) but that all of the polishing and packing time is used.

For each constraint in the problem we also have a “Slack or Surplus” column. This column tells us, for a particular constraint, the difference between the left-hand side of the constraint when evaluated at the LP optimal (i.e. when evaluated with X_{1}, X_{2}, X_{3} and X_{4} taking the values given above) and the right-hand side of the constraint.

Constraints with a “Slack or Surplus” value of zero are said to be *tight* or *binding* in that they are satisfied with equality at the LP optimal. Constraints which are not tight are called *loose*.

A summary of the input to the computer for the second situation considered in the question (only limitation is on total time spent on all operations) is shown below.

which in equation form is:

The solution to this problem is also shown below.

We can see that the optimal solution to the LP has value 78750 (£) and that T_{ass}=78750, T_{pol}=78750, T_{pac}=52500, X_{1}=0, X_{2}=0, X_{3}=26250 and X_{4}=0.

This implies that we only produce variant 3.

Note here how much higher the associated profit is than before (£78750 compared with £58000, an increase of 36%!). This indicates that, however the allocation given before of 100,000; 50,000 and 60,000 minutes for assembly, polishing and packing respectively was arrived at it was a bad decision!

Below we solve this LP with the Solver add-in that comes with Microsoft Excel.

Take this spreadsheet and look at Sheet A. You should see the problem we considered above set out as:

Here the values in cells B2 to B5 are how much of each variant we choose to make – here set to zero. Cells C6 to E6 give the total assembly/polishing and packing time used and cell F6 the total profit associated with the amount we choose to produce.

To use Solver in Excel do Tools and then Solver. In the version of Excel I am using (different versions of Excel have slightly different Solver formats) you will get the Solver model as below:

Here our target cell is F6 (ignore the use of $ signs here – that is a technical Excel issue if you want to go into it in greater detail) which we wish to maximise. We can change cells B2 to B5 – i.e. the amount of each variant we produce subject to the constraint that C6 to E6 – the total amount of assembly/polishing/packing used cannot exceed the limits given in C7 to E7.

In order to tell Solver we are dealing with a linear program click on Options in the Solver box and you will see:

where both the ‘Assume Linear Model’ and ‘Assume Non-Negative’ boxes are ticked – indicating we are dealing with a linear model with non-negative variables.

Solving via Solver the solution is:

We can see that the optimal solution to the LP has value 58000 (£) and that T_{ass}=82000, T_{pol}=50000, T_{pac}=60000, X_{1}=0, X_{2}=16000, X_{3}=6000 and X_{4}=0.

This implies that we only produce variants 2 and 3 (a somewhat surprising result in that we are producing none of variant 4 which had the highest profit per unit produced).

- How can you explain (in words) the fact that it appears that the best thing to do is not to produce any of the variant with the lowest profit per unit?
- How can you explain (in words) the fact that it appears that the best thing to do is not to produce any of the variant with the highest profit per unit?

Referring back to the physical situation we can see that at the LP optimal we have 18,000 minutes of assembly time that is not used (T_{ass}=82000 compared with a maximum time of 100000) but that all of the polishing and packing time is used.

For the second situation given in the question, where the only limitation is on the total time spent on all operations examine Sheet B in spreadsheet lp.xls

Invoking Solver in that sheet you will see:

where cell C7 is the total amount of processing time used and the only constraint in Solver relates to that cell not exceeding the limit of 210000 shown in cell C8. Note here that if you check Options in Solver here you will see that both the ‘Assume Linear Model’ and ‘Assume Non-Negative’ boxes are ticked.

Solving we get:

We can see that the optimal solution to the LP has value 78750 (£) and that T_{ass}=78750, T_{pol}=78750, T_{pac}=52500, X_{1}=0, X_{2}=0, X_{3}=26250 and X_{4}=0.

This implies that we only produce variant 3.

Note here how much higher the associated profit is than before (£78750 compared with £58000, an increase of 36%!). This indicates that, however the allocation given before of 100,000; 50,000 and 60,000 minutes for assembly, polishing and packing respectively was arrived at it was a bad decision!

#### Problem sensitivity

Problem sensitivity refers to how the solution changes as the data changes. Two issues are important here:

- robustness; and
- planning.

We deal with each of these in turn.

**Robustness**

Plainly, in the real world, data is never completely accurate and so we would like some confidence that any proposed course of action is relatively insensitive (robust) with respect to data inaccuracies. For example, for the production planning problem dealt with before, how sensitive is the optimal solution with respect to slight variations in any particular data item.

For example consider the packing time consumed by variant 3. It is currently set to *exactly* 2 minutes, i.e. 2.0000000. But suppose it is really 2.1, what is the effect of this on what we are proposing to do?

What is important here is what you might call “*the shape of the strategy*” rather than the specific numeric values. Look at the solution of value 58000 we had before. The shape of the strategy there was “*none of variant 1 or 4, lots of variant 2 and a reasonable amount of variant 3*“. What we would like is that, when we resolve with the figure of 2 for packing time consumed by variant 3 replaced by 2.1, this general shape remains the same. What might concern us is if we get a very different shape (e.g. variants 1 and 4 only).

If the general shape of the strategy remains essentially the same under (small) data changes we say that the strategy is **robust**.

If we take Sheet A again, change the figure of 2 for packing time consumed by variant 3 to 2.1 and resolve we get:

This indicates that for this data change the strategy is robust.

**Planning**

With regard to planning we may be interested in seeing how the solution changes as the data changes (e.g. over time). For example for the production planning problem dealt with above (where the solution was of value 58000 involving production of variants 2 and 3) how would increasing the profit per unit on variant 4 (e.g. by 10 per cent to 4.95 by raising the price) impact upon the optimal solution.

Again taking Sheet A, making the appropriate change and resolving, we get:

indicating that if we were able to increase the profit per unit on variant 4 by 10 per cent to 4.95 it would be profitable to make that variant in the quantities shown above.

There is one thing to note here – namely that we have a fractional solution X_{3}=1428.571 and X_{4}=11428.57. Recall that we have a linear program – for which a defining characteristic is that the variables are allowed to take fractional values. Up to now for this production planning problem we had not seen any fractional values when we solved numerically – here we do. Of course in reality, given that the numbers are large there is no practical significance to these fractions and we can equally well regard the solution as being a conventional integer (non-fractional) solution such as X_{3}=1429 and X_{4}=11429.

**Approach**

In fact the approach taken both for robustness and planning issues is identical, and is often referred to as **sensitivity analysis**.

Given the LP package it is a simple matter to change the data and resolve to see how the solution changes (if at all) as certain key data items change.

In fact, as a by-product of using the simplex algorithm, we automatically get sensitivity information (e.g. the reduced cost information given on the LP output for the production planning problem):

- for the variables, the Reduced Cost (also known as Opportunity Cost) column gives us, for each variable which is currently zero, an
*estimate*of how much the objective function will change if we make that variable non-zero. This is often called the “*reduced cost*” for the variable.**Note here than an alternative (and equally valid) interpretation of the reduced cost is the amount by which the objective function coefficient for a variable needs to change before that variable will become non-zero.** - for each constraint the column headed Shadow Price tells us by how much the objective function will change if we change the right-hand side of the corresponding constraint. This is often called the “
*marginal value*” or “*dual value*” for the constraint.

However, interpreting simplex sensitivity information is somewhat complicated and so, for the purposes of this course, I prefer to approach sensitivity via resolving the LP. Those interested in interpreting the sensitivity information automatically produced by the simplex algorithm can find some information here.

#### LP – State of the art

Most large LP’s are not entered directly into the computer in the same fashion as in our simple package. Instead an algebraic modelling language is used. A tutorial description of one of these modelling languages is available here. More about advanced LP can be found here.

Until the 1980’s all packages for solving LP’s relied upon variants of the simplex algorithm. However in 1984 Karmarkar published a new algorithm for LP, called an interior point method, which is completely different from the simplex algorithm.

Karmarkar’s work has sparked an immense amount of LP research, both into interior point methods and into improving the simplex algorithm.

Since 1984 new commercial software products have appeared, e.g.

- OSL (Optimisation Solutions and Library) from IBM
- Cplex (Cplex Optimisation)

Both these products now include both simplex and interior point algorithms.

Let us consider the case where we have formulated some problem as an LP and we are thinking of solving it numerically. Can we find a computer package that has the capacity to solve our LP?

In terms of LP’s the key factor is the number of constraints and a typical workstation/mainframe LP package (e.g. OSL (version 2)) has the capacity for 2 billion variables and 16 million constraints (excluding bounds on variables which are treated implicitly rather than explicitly).

However, these capacity limits *vastly* overstate what we could actually solve in real-life. To give you a rough idea of the state of the art the following results have been reported:

Code Number of constraints Number of variables Time Computer OSL 105,000 155,000 4 hours IBM 3090 750 12,000,000 27 mins IBM 3090 Cplex 145 1,000,000 6 mins Cray Y-MP 41,000 79,000 3 mins Cray 2

This is not to say that it is going to be impossible to solve very large LP’s by simplex as there is a small chance that advanced LP theory might enable us to solve such problems (by *decomposition* or by taking advantage of any *structure* in the LP) but essentially we face a very difficult task.

Note here that the problem with solving very large LP’s via simplex is not merely a matter of using a faster computer – the problem is theoretical in nature due to large LP’s being *degenerate* (there is some evidence to suggest that for large LP’s the solution time required when using simplex is approximately proportional to (number of constraints)^{2.4}).

### CBSE Class 12 Commerce Mathematics 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.