Loading
Notes
Study Reminders
Support
Text Version

Linear Programming

Set your study reminders

We will email you at these times to remind you to study.
  • Monday

    -

    7am

    +

    Tuesday

    -

    7am

    +

    Wednesday

    -

    7am

    +

    Thursday

    -

    7am

    +

    Friday

    -

    7am

    +

    Saturday

    -

    7am

    +

    Sunday

    -

    7am

    +

Today, we will deal with solution techniques, linear programming for optimization.
These are the concepts covered in this module, as we have mentioned earlier, what is a
structured problem; what is a semi structured problem; what is a model; classification;
purposes of modeling. All these we have covered and we have said, structured problem
is very-very routine; we can put the problem into some predefined structure and get a
mathematical model out of it.
Semi-structured, we can do it partially, balance is left to the ingenuity and newer models
can come in place and what is a model? Model is a mathematical expression of real life
situations and we can replicate them in the real life and classification of the models, we
have done it; some choice models, sorting model, ranking model, etc.; purposes of
modeling basically, it would enable us to take timely decisions.
(Refer Slide Time: 01:19)

Now, what are the solution techniques possible; optimization heuristics and simulation;
ok?
(Refer Slide Time: 01:30)

Today, we will deal with, today we will deal with; this one we had covered. Today, we
will deal with Solution Techniques, Optimization, Heuristics and Simulation. Of which
today, we will deal with only the first part that is solution techniques optimization; ok.

(Refer Slide Time: 01:44)

Now, optimization normally, we will take care of three; linear, integer and non-linear
optimization; ok. Today, we will deal with linear optimization or linear programming
which is commonly called linear programming optimizer of problem. Now, linear
programming if you see it is I would say 95 percent structured; some people will say no,
it is 100 percent structured. It is a very-very time-tested model; I agree 100 percent; fully
agree it is a fully structured time-tested model, linear programming.
Why I am saying semi structured in the sense that partial little bit 5 percent is sensitivity
analysis that within a range, this is the output possible. You can say that is also a part of
fully structured models, I agree with it the way you want to look at it; it is up to you; ok.
So, linear programming normally, we will call it as a fully structured model; ok.

(Refer Slide Time: 03:00)

So, let us see what we mean by that. A company manufactures two bags that goes
through the following processes. Company manufactures two types of bags rather two
types of bags that goes to the following processes; cutting and dyeing the material,
sewing, finishing ok, inserting the umbrella holder, the club separators inspection and
packaging. So, cutting, sewing, finishing and packaging, these are the four things that go
in; cutting, sewing, finishing and inspection; right.
(Refer Slide Time: 03:35)

Now, this is the time taken by each of these types of bags. What it is saying is that two
types of bags are getting manufactured; one is standard bag and one is deluxe bag. Now,
this there are four departments; cutting four processes; cutting, sewing, finishing and
inspection; cutting, sewing, finishing and inspection.
Now, a standard bag takes seven-tenth of an hour of standard. If you see, I am moving
the cursor and if you see here, a standard bag takes seven-tenth of a; sorry; standard bag
takes seven-tenth of an hour to manufacture in the cutting and dyeing process. Deluxe
bag takes 1 hour.
Sewing takes half an hour for standard bag and five-sixth of an hour in the deluxe bag.
Finishing takes 1 hour for the standard bag and deluxe bag, it takes two-third of an hour;
ok. An inspection takes one-tenth of an hour in the standard bag and one-fourth of an
hour in the deluxe bag; ok.
Now, the profit is rupees 9 and rupees 10. Question is how many pieces of these two
types of bags should the company manufacture? Now, if there was unlimited everything,
let the company manufacture as many as they want; but that is not the case. There is a
constraint or there are constraints. What are the constraints?
(Refer Slide Time: 04:57)

Let us take this example. A company manufactures two bags that goes through the
following processes; cutting and dyeing the material; cutting and dyeing the material,
sewing, finishing and inspection and packaging; ok. Now, if you see cutting and dyeing
takes up a seven-tenth of an hour, two types of bags are manufactured – standard bag and
deluxe bag.
Cutting and dyeing takes seven-tenth sorry seven-tenth of an hour; deluxe pack takes 1
hour. Sewing takes half an hour; deluxe bag takes five-sixth hour. Finishing takes 1 hour,
two-third hour, one-tenth hour this thing. So, if you see that normally, we are saying the
deluxe bag takes a bit more time right; deluxe bag takes some bit more time now; ok.
(Refer Slide Time: 05:59)

So, the profit for every bag is rupees 9 and deluxe bag is rupees 10 right. How many
pieces of these two types of bags should the company manufacture? The question is that
this cutting process has a 630, 600, 708, 135; 708, 135; ok. Now, this cutting and dyeing,
this is the time taken for 1 bag; but this cutting and dyeing process, total hours available
is 630; total hours available is 630, total hours available for sewing is 600, finishing is
700, inspection and packaging is 135; right; ok.
So, what should be; what should be the; so, what should be the model; ok? So, this is the
first, this is the first one that we are dealing with optimization techniques linear. What
did we say? We said the company manufactures two types of bags, each bag goes
through these four processes, these are the four processes, this is the time taken, profit is
this, this and this ok. Now, so, let us go by it. So, profit is 9 and 10.

(Refer Slide Time: 07:33)

So, what is my objective? My objective is to maximize this profit right. How many
standard bags should we manufacture? We do not know. So, let us keep it S. How many
deluxe bags should we manufacture? We do not know.
So, let us keep it at D. What is the profit? Total profit then 9 per bag into S bags
manufactured that is 9 x1 or 9S and 10 per bag into D number of bags manufactures. So,
10 D or 9 x1 plus 10 x2 ok. What are the constraints? Constraints is cutting takes seven-
tenth hour. So, seven-tenth of S plus 1 of D lesser than equal to how many hours were
available? 630 right; ok. 630 cutting hours was available right.

Next one was if I am correct, 600 for sewing; 600 hours are available, half of S plus five-
sixth of D; 1 of S plus two-third of D, I think this is 708, if I remember correctly; and
135 this is 135 ok. See is this clear? My model is maximize 9 x, 9 S plus seven 10 D;
maximize 9S plus 7D subject to seven-tenth hour into S bag seven-tenth hour per bag
into S number of bags manufactured. Seven-tenth hour per bag into S number of bags
manufactured plus 1 hour per bag into D number of bags manufactured and so, the total
hours available is 630; total hours available is 630.
So, this is my linear programming model; ok; let us go. So, you see this is the model in
the proper form max 10S plus 9D subject to seven-tenth of S plus one-tenth of D; half of
S plus five-sixth of D; 1 of S plus two-third of D and one-tenth of S plus one-fourth of D
less than equal to 135. So, this is the model. Now, the question is now the question is
how to solve this? How do we get the quantity of S and the quantity of D? How to solve
this; ok.
(Refer Slide Time: 10:17)

So, let us now go through that ok. The graph. Now, what was my equation? Let us take
one, seven-tenth of S plus 1 D is less than equal to 630; seven-tenth S plus 1 D is less
than equal to 630 right, when s is equal to 0, D should be equal to 630 right. For
simplicity purpose, we will make this as equal right when D is equal to 0, s is equal to
what? 6300 by 7 that is equal to 900; 7 9’s are 63.
So, for first constraint, constraint number 1, what did we get? S and D points; s is 0, D is
630; D is 0, S is 900 right. These are the two points that we get. Understood? First
equation was this, seven-tenth S plus 1 D is equal to 630 when s is equal to 0, D is equal
to 630; when D is 0, s is equal to 6300 divided by 7 that is 900. So, what are the two
points? s 0, D 630; D 0, s 900.
This is the first equation point. Sorry; let us go to the second point, let us go to the
second point, what was the previous equation half S plus five-six D less than equal to
600; half S plus five-six D less than equal to 600 ok. Let us go sorry, half S plus five-
sixth D less than equal to 600 right; ok.

So, when s is equal to 0, D is equal to what? 3600 by 7; sorry 3600. So, sorry, I am so
sorry; this is 3600 by 5 right 36 sorry; anyway 3600 by 5 that is equal to 3600 by 5 is
equal to 720. When D is equal to 0, s is equal to 1200; ok. So, my next equation becomes
s and D right. Half S plus five-six D is less than equal to 600; s 0, so D becomes 3600 by
5 is 720 and D is this; ok.
So, in this way, we can get the list of all equations clear. So, for equation 3, I will just for
equation 3, we will get 0, 1052 and sorry 1062 and 708, 0 and for equation number 4, we
will get 0, 540 1350 and 0 clear. So, this is the; ok.
(Refer Slide Time: 15:05)

So, what I will do is, I will erase this and is it clear? First if you solve these four
constrained equations, we get these values right. So, now, we will do a graph of these,
we will do a graph of this. Let us see; thank you!

(Refer Slide Time: 15:40)

Here let us see. So, we first equation, we got S 0 D 630; D 0 S is equal to 900 right.
Second equation, we got S is equal to 0 D is equal to 1 0 sorry D is equal to S is equal to
0 D is equal to 720; D is equal to 0 S is equal to 1200.
These two we solved; ok. Now, for the third constraint, we get S is equal to 0 D is equal
to 1062; D is equal to 0 S is equal to 708. For 4 we get, S is equal to 0 D is equal to 540;
D is equal to 0 S is equal to 1350 right. Now, let us draw a graph ok. Let this be S and let
this be D. Now, what is the maximum value of S? Is 1350? So, let us go at 0, 500, 1000,
1500.
What is the maximum value of D? D gets me at 1062. So, let us go for 500, 1000. Let us
take the first equation S 0, D 630. I will use different color. S 0, D 630; S is 0, D is 630
ok; D 0, S 900; D 0, S 900. This is my equation 1; ok. Then, S 0 let us use another color
then, let us use a green; S 0, D 720; ok; D 0, S 200; D 0, S 1200. Let us take the third one
S 0, D 1062, somewhere here D 0, S 708. This is equation 3. Then, S 0 equation 4, let us
use a fourth color; let us use this. S 0, D 540 and D 0, S 1350; so this one is my equation
4; right.
So, if you see what my objective was; sorry; what was my objective? My objective was
maximization right. So, my common space; so, let us go back again; if I can, I do not
know whether this color will work; my; sorry, my common space is this one right. So, I
have two points ok. So, I have these two feasible points right of which whichever is
maximum, I will get it.
Now, what are the; these two are the intersection point of these two lines; line 4, line 1
and line 3 and line 1 ok. So, if you can solve these two simultaneous equations, you will
get a value for this, for both these and the value for S and D whichever one gives me the
maximum number that is the maximum profit; ok. So, if you solve this, you will get S as
540 and D as 252; ok. So, this is the way by which you solve a graphical solution; ok.
(Refer Slide Time: 21:42)

Now, I have a question, if you solve this you will get; ok. You will get 540 S we have
manufactured and 540 S we have manufactured and 252 D we have manufactured right.
So, seven-tenth of hour per bag into 540 bags, 1 hour per bag into 252 that is equal to
630 hours right. Similarly, half hour per bag into 540 bags plus five-six of per hour into
252; so, this is basically the number of hours required.
What was the hours available? 630, 600, 708, 135. So, here hour required 630, we had
630. So, unused is 0. 480 hours were used, we had 600 hours; so, 120 is unused. 708, 708
is 0. 117 hours were used, we had 135 hours; so, eighteen hours were unused. These
unused hours; unused; these unused hours is called as slack variable.
These unused hours is called slack variable; ok. Just this, nothing else. Unused
constraint, unused quantity in a constraint is slack; ok. Just remember this thing; unused
is slack; ok. That means, we do not need this. This is one managerial decision. You can
find out wastage, you can find out where to reduce cost.
You can find out where to reduce cost because this is unused, you can negotiate with the
suppliers give me less; negotiate with the finance department, all along we have been
purchasing more; a new machine has come, this is not required; reduce the number of
may be working hours; ok. So, this is the use of slack variable; ok.