Mastering Linear Programming: A Step-by-Step Guide to Graphical Solutions

[Music] [Music] [Applause]

[Music] [Applause] [Music]

welcome students to the another lecture on the course decision making with the spreadsheet

in the previous lecture i have talked about how to formulate a linear programming

problem in this lecture i am going to explain how to solve a linear programming

problem one method for solving a linear programming problem is using a graphical

method so agenda for this lecture is graphical solution for a maximization problem this

is the problem which i have brought here which i have taught in the previous lecture

ok a linear programming problem involving only two decision variables can be solved using a graphical solution

procedure so this problem maximization of profit

equal to 10 s plus 90 subjected to there are four constraint is there i will explain how to solve this problem

using a graphical method what is the graphical solution procedures

the graph will have a values of s on the horizontal axis and the d on the vertical axis

so in the horizontal axis i have taken s in the vertical axis i have taken d any point

on the graph can be identified by the s and d values which indicate the position of the point

along the horizontal and vertical axis respectively because every point s comma d

corresponds to a possible solution every point on the graph is called solution point the solution point where

s equal to 0 and d equal to 0 this point is referred to as the origin

because s and d must be non negative the graph in figure 1 only displays positive solutions

because the s is greater than or equal to 0 and d is greater than equal to zero so we

won't consider any negative solutions for example if you consider this point

say s equal to two hundred d equal to eight hundred and if it is this point s equal to four

hundred and d equal to 300 this is the one solution point the next stage is plotting all the constraint

into the graph so let us see how to plot the constraint number one that is cutting and dyeing

so i have taken the constraint number one seven upon ten s plus one d less than or equal to six thirty

to show all solution point that satisfy this relationship we start by graphing the solution

point satisfying the constraint as an equality even though it is less than or equal to

sign is there we will consider equal to sign so that is the points where 7 upon ten s

plus one d is equal to six thirty because the graph of this equation is a line

it can be obtained by identifying two points that satisfy this equation and then drawing a line through the

points so how can we get the two point when you in this equation

if you substitute s equal to zero you will get your d point

so ok if you substitute is equal to zero say d equal to six thirty so we got one point zero comma six thirty

the second one you substitute d equal to zero you will get the value for

s so when you substitute d equal to zero the value of our s is

nine hundred so we got another point nine hundred comma zero

that's the second point satisfying this equation s equal to nine hundred d equal to

zero given these two points we can now graph the line corresponding to the equation

so we got the two point ok now we can draw a line because all the points on the line

satisfy 7 upon 10 s plus 1 d equal to 630 we know any point on this line must

satisfy the constraint so all the point above this line will satisfy the

constraint but our constraint is less than or equal to six thirty

but where are the solution points satisfying where the constraint is having less than

or equal to six thirty so how to identify which side of this

this line satisfy our constraint you have to take any point which is below this

line and another point above the line

when you substitute for example i have taken arbitrarily 200 comma 200

you have to substitute these values into this equation if this point is satisfied you have to

shade on the left hand side that is towards the origin if it is not satisfying you have to

shed on the outside the the side this side you have to shade it

consider two point s equal to two hundred d equal to two hundred and s equal to six hundred and d equal

to five hundred what i have explained in the previous slides you can see from the figure two that the

first solution point is below the constraint line and the second point is above the constraint line which of these

solutions will satisfy the cutting and dying constraint when you substitute s equal to two

hundred and d equal to two hundred we are getting in the values of three forty so this three forty is less than six

thirty so the point which is on the left hand side of this line satisfy our constraint

because the 340 hours is less than 630 hours

available so s equal to 200 and d equal to 200 production combination our solution

point satisfy our constraint let us take the another point s equal to 600 d equal to 500

when you substitute this we are getting the value is ninety nine hundred and twenty

but the nine hundred and twenty is greater than six thirty that is violating our constraint so

the the region which satisfy our constraint is on the left hand side this region

if a solution point is not feasible for a particular constraint then all other solutions point on the

same side of the constrained line also not feasible if the solution point is

feasible for a particular constraint then all other solution points on the same side of the constraint line are

feasible for that constraint so what is the point here is suppose if you take any one point

if it is satisfying our constraint right so this is less than or equal to this equal to represents only the

straight line when you write less than or equal to this shaded line which is shaded in blue

color so what this point says that if any one point is satisfying on this

region so all other points below this line will satisfy our constraint

so one has to evaluate the constraint function for only one solution point one solution point to determine which

side of the constraint line is feasible obviously the

we have to see which side of this constraint line is feasible whether it can be either either on the left hand

side or the right hand side in this figure 3 we indicate all the points satisfying the cutting and dying

constrained by the shadowed region so this region is the region which satisfy our constraint

so this will be less than or equal to six hundred and thirty like that

the same way i have taken the another constraint that is sieving constraint so this less than or equal to six

hundred this less than or equal to 708 less than or equal to 135 so these points re satisfy our

constraint if i superimpose all the constraint i will get here this

kind of figure so the area which is common for all the constraint is called feasible region

so this is the region which is common for which satisfy all the constraint

so that particular region is feasible region why we are calling it is feasible region

any point if you take any point that point will satisfy all our constraint feasible solution and

feasible region the shaded region in this figure include every solution point that satisfy all

the constraint simultaneously solution that satisfy all the constraint are termed as

feasible solutions and the shaded region is called feasible solution region or simply the feasible

region any solution point on the boundary of the feasible solution are within the

feasible solu feasible region is a feasible solution point so in this boundary this is a feasible

solution point finding the optimal solution by trial and error one approach to finding the

optimal solution would be evolving to the objective function for each feasible solution

what is the meaning every solution is feasible solution we can substitute in our

these values in our objective function the optimal solution would be

the one yielding the largest value suppose if you take this is point number one

point number two so you will get z one z two ok if the set to z two is larger than

the z one because it is a maximization problem the z two is the point corresponding to z two

maybe say somewhere s two comma d two may be your optimal solution

the difficulty with this approach is the infinite number of feasible solutions are possible so checking all the points

and verifying whether which is the optimal value is very difficult one because one cannot possibly evaluate an

infinite number of feasible solutions so this trial and error procedure cannot be used to identify the optimal solution

so the trial and error solution will not be used

so we are going to find out an another method what we are going to do we are going to select some arbitrary value for

our profit contribution so select an arbitrary value for the profit contribution

and identify all feasible solutions s comma d that yield the selected value for example

which feasible solution provide a profit of thousand eight hundred dollar so i have fixed suppose if i want to have my

profit contribution is thousand eight hundred dollar what should be what should be the value of s and d

these solutions are given by the values of s and d in the feasible region that will make the objective function

solution for an arbitrary value of thousand eight hundred dollar of your profit contribution

suppose ah i want to make a profit contribution of thousand

eight hundred dollar ok so this is the line of ten years plus ninety equal to thousand eight hundred

dollar if i want to make this much profit contribution i have to find out what is the value of

s and d so because it is intersecting on the x

axis and y axis e i can find out where it is intersecting otherwise in this equation if i substitute s equal to 0 i

will get the d value if i substitute d equal to 0 i will get the s value so that is

and 180 comma zero one value then zero comma two hundred is a another value

this expression in simply the equation of a line which one ten in ten years plus ninety equal to thousand 800

all feasible solution points s comma d yielding a profit contribution of thousand eight

hundred dollar must be on the line so all the points all the points there is a points mean

value of s and d will satisfy this our objective function it is thousand eight hundred the procedure for

graphing the profit or objective function line is the same what i have explained previously

so when you substitute s equal to zero the d will be two hundred so we got one point this point

zero comma two hundred similarly when you substitute d equal to zero ok we will get another point

one eighty zero so this is a point of one eighty zero so drawing the line through

these two points identifies all solution that have a profit contribution of 1800 so the graph of this profit line is

presented in this figure so this line is our profit line because

we have taken only one value similarly i can take another profit contribution value arbitrarily three thousand six

hundred five thousand four hundred then i can plot this line

this line ten years plus ninety equal to three thousand six hundred 10 years plus 90 equal to 5400

because the objective function is to find the feasible solution yielding the largest profit contribution

let us proceed by selecting higher profit contribution and finding the solution yielding the

selected value for instance let us find all solutions yielding profit contribution of 3600

dollar and five thousand four hundred dollar to do so we must find the s and d values

that are on the following lines so these are the two lines right we have to find the all the points which are in these

two lines okay using the previous procedure for graphing the profit and cons constraint

line we draw the 3600 and 5400 dollar profit line as shown in

the graph although not all solutions points on the 5400 dollar profit line or

feasible region at least some points on the line are and it is therefore possible to obtain a

feasible solution that provides 5400 profit contribution when you look at this this line

where it is say this line right

it is not covering see this is covering only from this point to this point this region is not covered by this line

but all the points in this region will satisfy your objective function can we find a feasible solution yielding an

even higher profit contribution please look at the figure 8 and see what general observations you

can make about the profit lines which are already drawn there are two

points the point number one is the profit lines are parallel to each other look at this

one all the points are parallel to each other

second one is higher profit lines are obtained as

we move farther from the origin so when we move from

farther from the origin we are getting the higher profit line so when you go this way it may be five thousand

six hundred this may be something else so what are the two point all the objective functions are parallel

lines and when we move away from the origin our the value of objective function is

increasing these observations can also be expressed algeb

algebraically let p represents the total profit contribution that is a p equal to 10

s plus 9 d so i am going to find the i am going to write this one

y equal to m x plus c for one because i want to know what is

the slope here because d this this is a d this is d

this is yes this is not the s so if i write in this form i can find out this is the

slope of that objective function what is that 9 by

slope is minus 10 by 9. so when p equal to thousand eight hundred when you substitute in the

previous values you will getting minus ten by nine yes two hundred when you increase p equal to two three thousand

six hundred dollar again this is the equations

so what is the similarity you are saying even though the value of the objective function the right hand side is

increasing the slope remains constant minus ten by nine minus ten by nine minus ten by nine so this implies that

the objective function lines are parallel to each other so the slope minus ten by nine is the

same for each profit line because profit lines are parallel further we see that the d intercept

increases with larger profit contributions thus higher profit lines are farther

from the origin that we have understood algebraically next we will look at how to find out the

optimal solutions because the profit lines are parallel and higher profit lines are farther from

the origin we can obtain solution that yield increasingly larger values for the

objective function by continuing to move the profit line farther from the origin in such a

fashion that it remains parallel to the other profit lines so what it is meaning

suppose we have the objective function like this so when we draw a parallel lines

parallel lines and when we move away from this origins so there is a possibility the value of

our objective function will increase however at some point we will find that any further outward movement will place

the profit line completely outside the feasible region so when we move away from the origins

right we should be careful that we are not completely moving away from the feasible region

because solutions outside the feasible regions are unacceptable the point in the feasible region that

lies on the highest profit line is the optimal solution ok so what we have to do

you have to draw different objective function line we have to keep on move away from the origin at the particular

point the value will be highest so that corresponding point is your optimal solution

so what you can do you can take a ruler or the edge edge of a piece of paper

and move the profit line as far as from the origin you

as you can so what you can do you can move this way you can move this way you can move this way

what is the last point in the feasible region that you reach so this point

which is optimal solution is shown in graphically so this is the point

extreme point is our optimal solution so what is this point how we are getting this point there are two constraints are

intersecting one is finishing another one is cutting and dying ok

that two lines where it is intersecting that corresponding point is called your optimal solution when you substitute

that optimal solution your objective function you are getting your objective function as

7668 how to get that that intersection points

so there are two constraints so wherever the right hand side is 630 which one that is a cutting dying

constraint ok so

from this 7 upon 10 s plus 1 d equal to 630 even though it is less than or equal to

because i want to know the value of s and d i am taking equal to sign only not less than or equal to because otherwise

i cannot solve it so 7 upon 10 is 630 minus 1 d so from this if you find the s value

s is 900 minus 10 upon 7 d ok

this is our value of s ok the another constraint which is

intersecting is your finishing constraint so i have taken one by one s plus two upon three d seven zero eight

so instead of s right instead of v s i am going to substitute this value so that i have

taken here so nine hundred minus ten upon seven d plus

two pi three d two upon three d equal to seven zero eight

so what you can do this ah nine hundred you can bring on the right

hand side it will become minus one nine two so the remaining is minus ten upon seven

d plus two upon three d so d is common you take on the left hand side the remaining is minus ten upon

seven plus two upon three when you simplify this you will be getting minus sixteen upon

twenty one d equal to minus one hundred ninety two so the d value at the end you are getting two fifty two

so we got the d value when you substitute this d value into this yes you will get

540. so the optimal point here is 540 minus

252 that is the where the two constraints are intersecting so this point

so this point is 540 minus 252

how i got this point when i after drawing the objective function

line when i keep on moving away from the origin i found the extreme right side

edge is this one so this point is formed by intersection of two constraints

so i have solved the two constraint to get this point so 540 minus comma 252 when you substitute this value

you will be getting 7668 dollar a note on graphic line

suppose a company manufactures two models of small tablet

computers assume that there are two models one is assistant

model another one is professional model management needs

50 units of the professional model for its own sales force and expects sales of the professional

tablet to be at most one of the sales of the assistant tablet computer

so what the constraint enforcing this requirement is p minus 50 because this 50 is consumed

by their own sales force and it cannot exceed one half of the

assistant tablet so less than or equal to 1 by 2 a when you simplify this will be getting 2 p minus 100 less than or

equal to a so this is a constraint i want to i need to

plot it so substitute p equal to zero will getting a equal to minus hundred so this is the point

so when you substitute a equal to zero you will get p equal to fifty so this is another point so what is the point you

have to notice already we have defined that the solution will be only on the

positive side but there may be a situation for drawing here this line

you may get your point that point may lie on the negative sides but at the time of considering the

feasible region you have to consider only the positive side positive side positive

value of a and p there is a point you should note it there may be another situation

r greater than equal to t so r minus t greater than equal to t so

that is r equal to t so that is this point where it is a forty five degree line

so if r equal to hundred t also hundred that is the meaning that is a way of drawing the constraint

next we will be explaining an important term in a linear programming model that is

the slack variable otherwise it is another name is unused resources

so this was the given problem we got the value what is that optimal value s equal to 540

d equal to 252. so in the constraint number one when you substitute it the resources used is 630

but the hours available is six thirty so all the resources are fully utilized that is unused resources

so this slack variable for this first constraint is zero look at the second constrained sieving

constraint when you substitute 540 and 252 the resources

consumed is 480 but the available resources is 600. so 100 120 unit hours not utilized so here the slack

variable for the second constraint is 120 for the third constraint

hours required is 708 hours available also 708 so unused resource

resources is zero the resources are fully utilized that means there is zero slack values

the last constraint hours required is 117 but hours available is 135 there is a positive

slack variables so what is the meaning of slack variable in the linear programming context

the unused resources is called our slock variables thus

the complete solution tells management that the production of 540 standard bags and 252 deluxe bags will require

all available cutting and dyeing all available finishing time

so that means there won't be any unutilized resources so in these department all the resources

will be fully utilized because the value of slack variable is zero while

600 minus 480 so 120 hours of sieving time and

135 minus 117 so 18 hours of inspection packaging time will remain unused so what we are understanding out of this

four constraint we have zero slack variable for two constraint

for another two constraint we have some positive slack variables if it is a positive slack variables in

that department there are unutilized resources are available so 120 hours of unused

sieving time 18 hours of unused inspection packaging time are referred as

slack for the two department in linear programming terminology any unused capacity for a constraint less

than or equal to type is referred as slack associated with the constraint

so in a linear programming model if the constraint is the type of less than or equal to type

the corresponding unutilized resources called slack variable often variables called slack variables

are added to the formulation of a linear programming problem to represent the slack or ideal capacity

so that the slack unutilized resources has to be added in the linear programming problem so

unused capacity makes no contribution to the profit because idle

that is not going to help for achieving your profit so thus the slack variable have

coefficient of 0 in the objective function so when you introduce the slack variable

the contribution of the slack variable is 0 so in our objective function that will

have the 0 coefficient after the addition of 4

slack variables denoted as s 1 s 2 s 3 and s 4 the mathematical model

of the problem becomes like this see that we have added plus s 1 plus s 2

plus s 3 plus s 4 and it is equal to sign because the contribution of this s one

is zero so in our objective function the coefficient is zero s one zero s two zero s three and zero s four

so this is the value of slack variable so cutting and dying department zero slack variable

sieving department 120 finishing 0

inspection packaging 18. now i will introduce another term called binding constraint

what is the binding constraint we can see that the cutting and dying and the finishing constraint restrict or

bind to the feasible region of this point so this point so this point is formed by

finishing constraint and cutting and dying constrain so this is restricting our optimal solutions beyond which it

will become not optimal so this corresponding constraint is called binding constraint

thus this solution requires the use of all available time for these two operations

what are they finishing and cutting and dying in other words the graph shows as that the cutting and dying and the

finishing department will have zero slack for any constraint

if it is zero slack that constraint is called as binding constraint

on other hand sieving and inspection packaging constraint are not binding the feasible region see the

other constraint what are they this inspection and this sieving

not binding the feasible region at the optimal

solution which means we can expect some unused time or slog or slack for these two operations

which one sieving and inspection the next one is the redundant

constraint another term the sieving constraint does not affect the feasible region

and thus cannot affect the optimal solution it is called redundant constraint

will go back what is the redundant constraint you see this one receiving you know

this constraint it is not forming the part of the solution so this constraint is redundant

constraint even though it is a redundant we have to keep in our lp model because

when the resources of any constraint is changing so the redundant constraint may be a

binding constraint at a certain point of time ok so even though it is redundant

it is a custom to mark that redundant constraint also ok students in this class

i have explained how to solve a linear programming problem using a

graphical method i have taken a problem i have solved

that problem using a graphical method in that i have explained what is the feasible region

i have explained what is the optimal point and what is the optimal solution

then i also explained what is the slack variable then i have explained what is redundant

constraint in the next class the same

problem i will solve with the help of a graphical calculator called desmos

after that i will use excel solver to solve this problem thank you very much [Music]

[Applause] [Music] [Applause]

[Music] bye [Music]

you