Introduction
In this comprehensive guide to linear programming, we will focus on the graphical method as a powerful tool for solving optimization problems. Linear programming is widely used in various fields for decision-making processes, particularly when evaluating how to maximize or minimize an objective function while maintaining constraints. This discussion will include understanding the graphical solution method, identifying feasible regions, and interpreting slack variables. To deepen your understanding, check out our resource on Understanding Linear Programming Problems in Decision Making.
What is Linear Programming?
Linear programming involves the optimization of a linear objective function, subject to linear equality or inequality constraints. It’s used in production, transportation, finance, and many other sectors. The aim is often to maximize profits or minimize costs, establishing the conditions under which this can be achieved. For more insights, refer to Understanding Linear Programming Problems Using Graphical Method and Excel Solver.
The Graphical Method of Linear Programming
The graphical method is a visual way to analyze linear programming problems, particularly effective when there are only two decision variables. Let’s dive deeper into the steps involved in solving a maximization problem using this method.
Step-by-Step Approach to Graphical Solutions
1. Formulating the Problem
To illustrate how to solve a linear programming problem graphically, we will consider the following example:
- Objective Function: Maximize Profit = 10S + 90D
- Constraints:
- $$\frac{7}{10}S + D \leq 630$$
- $$S + \frac{2}{3}D \leq 708$$
- $$D \leq 135$$
- $$S, D \geq 0$$
Where S stands for quantity of one product, and D represents another.
2. Graphing the Constraints
Plotting Individual Constraints
- Start by plotting each constraint line by converting inequalities to equalities. For example, for the first constraint:
$$\frac{7}{10}S + D = 630$$
- Identify points by setting S or D to zero:
- If S=0, then D=630.
- If D=0, then S=900.
By repeating this process for each constraint, you get:
- First Constraint: Line segments from (0, 630) to (900, 0)
- Second Constraint: From points derived by setting variables accordingly and calculating intersections.
3. Identifying the Feasible Region
The next step is to shade the feasible region based on the inequalities of the constraints. The feasible region includes all points that satisfy all constraints simultaneously.
Determining Feasibility
To identify which side of the line satisfies the inequality, pick test points. If the test point satisfies the inequality, shade the area where the corresponding values lie. For instance, if using the point (200, 200) satisfies a given constraint, shade that area.
4. Finding the Optimal Solution
Once all constraints are graphed and the feasible region is identified, we move to the objective function. The objective function line itself can be graphed. By selecting values for the profit level, you can draw parallel lines across the feasible region.
5. Trial and Error for Optimal Solutions
By systematically moving the profit line outward, you can identify the last point at which it remains within the feasible region. The corner points of this region often have potential as optimal solutions. The final optimal solution is achieved when the objective function's line is tangent to the feasible region boundary, essentially maximizing your output. In our case, substituting values from the derived corner points into the profit equation will give the highest profit achievable — for instance, achieving a profit of $7668 with particular amounts of S and D.
Understanding Slack Variables and Constraints
- Slack Variables: They represent unused resources in your constraints. For instance, if the sieving time has 120 hours not utilized, this represents a slack in this area. These give insights into constraints where resources aren't fully utilized.
- Binding vs Non-Binding Constraints: Binding constraints have no slack (fully utilized), while non-binding constraints allow for slack to exist. Recognizing these helps in understanding which constraints truly limit the maximum potential of your objective function. To learn more about this aspect, see Understanding Sensitivity Analysis in Linear Programming.
- Redundant Constraints: Some constraints might not affect the feasible region but should be taken into account as they can become binding under different conditions.
Conclusion
In summary, solving linear programming problems using graphical methods enables professionals to visualize complex situations and identify optimal solutions effectively. The integration of slack variables, binding constraints, and the identification of feasible regions is essential in reaching maximum outcomes. In forthcoming discussions, we will explore graphical calculators like Desmos and computational tools like Excel Solver to solve problems with greater complexity and efficiency. For a broader context on economics that affects these decisions, refer to Understanding Scarcity and Opportunity Cost in Economics and Understanding the Law of Increasing Opportunity Cost in Economics.
This step-by-step guide is intended for decision-makers and analysts looking to optimize their strategic planning and enhance their operations through linear programming. By following these methods, you can efficiently address real-world problems and maximize your organization’s potential profits.
[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
Heads up!
This summary and transcript were automatically generated using AI with the Free YouTube Transcript Summary Tool by LunaNotes.
Generate a summary for freeRelated Summaries

Understanding Linear Programming Problems Using Graphical Method and Excel Solver
Explore linear programming solutions using graphical methods and Excel solver in this detailed guide for students.

Understanding Linear Programming Problems in Decision Making
Explore the intricacies of linear programming and its applications in decision-making.

Understanding Sensitivity Analysis in Linear Programming
Learn how sensitivity analysis helps us evaluate the impact of changes in optimization models on optimal solutions.

Understanding Scarcity and Opportunity Cost in Economics
Explore scarcity, opportunity cost, and economic growth using the production possibilities frontier (PPF) concepts.

Understanding the Law of Increasing Opportunity Cost in Economics
Explore the law of increasing opportunity cost and how it shapes production decisions in economics.
Most Viewed Summaries

A Comprehensive Guide to Using Stable Diffusion Forge UI
Explore the Stable Diffusion Forge UI, customizable settings, models, and more to enhance your image generation experience.

Pamaraan at Patakarang Kolonyal ng mga Espanyol sa Pilipinas
Tuklasin ang mga pamamaraan at patakarang kolonyal ng mga Espanyol sa Pilipinas at ang mga epekto nito sa mga Pilipino.

Pamamaraan at Patakarang Kolonyal ng mga Espanyol sa Pilipinas
Tuklasin ang mga pamamaraan at patakaran ng mga Espanyol sa Pilipinas, at ang epekto nito sa mga Pilipino.

Kolonyalismo at Imperyalismo: Ang Kasaysayan ng Pagsakop sa Pilipinas
Tuklasin ang kasaysayan ng kolonyalismo at imperyalismo sa Pilipinas sa pamamagitan ni Ferdinand Magellan.

Ultimate Guide to Installing Forge UI and Flowing with Flux Models
Learn how to install Forge UI and explore various Flux models efficiently in this detailed guide.