LINEAR PROGRAMMING

LESSON 2 – MANAGEMENT SCIENCE

Introduction
 Many big choices made by a company rely on the best
path to accomplish the firm's objectives, according to the
operational climate constraints imposed on the manager.

 Such constraints that take the form of finite capital, such

as time, labor, energy, content, or money; or they may be
in the form of stringent instructions, such as a cereal or
engineering design manual.
Introduction
 One of the company firms' most important objectives is to
get as much income as possible or, in other terms, to
increase profit.

 The aim of specific business structures within a company

(such as a production or packaging department) is
frequently to minimize costs.
Learning Objectives
After studying this module, you should be able to:
1. Understand and define linear programming.
2. Identify all necessary items that must be included in a
model.
3. Write a verbal statement of the objective function and each
constraint.
4. Define the decision variables.
5. Write the objective function in terms of the decision
variables.
6. Write the constraints in terms of the decision variables.
7. Makes a decision about the solution of the problem
Linear Programming
 Linear Programming is a computer science technique to
address issues of optimization process.

 The word "linear" implies the linearity of all mathematical

relationships within a model. The standard model is the set of
linear equations and/or inequalities (called constraints) and
the linear objective function (to be maximized or minimized).

 The constraints of non-negativity (variables are negative or

positive) are also included in the model. The manager's aim is
to find the right solution for the highest objective function
value.
Formulation of the Mathematical Model
Example:
ABC, Inc. creates 2 types of toys: car and boat. The car is
priced at P550, and the boat at P700. The cost of the car is P50,
while P70 for the boat. The car needs 1 hour of woodwork labor
and 1 hour of painting and assembling labor. The boat requires 2
hours of woodwork labor and1 hour of painting and assembling
labor. Cost of woodwork labor is P30 per hour, worth of painting
and assembling labor is P20 per hour. Monthly, ABC has 5000
existing hours of woodwork labor and 3000 hours of painting
and assembling labor. There is an unlimited demand for boat,
while an average demand for car is at most 2000. ABC wants to
get the best out of monthly profit (total revenue - total cost).
Formulation
1. Decision variables
 The variables would explain thoroughly the management's
decisions to be made. To optimize the income, the manager
needs to determine how many cars and how many boats will be
generated per month.

 In this scenario, the variables to the decision are:

 x1= number of cars produce each month;
 x2= number of boats produce each month
Formulation
2. Objective function
 This function reflects the criteria of the management which
must be maximized or minimized.

 The management aims to optimize gross monthly income

in the circumstance of the ABC as the disparity between
total monthly revenues and total monthly costs.
 Revenue and cost can be represented as the function of the
variables x1 and x2 for decision.
Objective function
1. Total revenue (TR) = revenue from sold car + revenues
from sold boat. The price of one car is P550 and ABC
produces x1 of car, the revenue resulting from the cars is
550x1. Likewise, the revenue from sold boats is 700x2.

 The total monthly revenue from production is expressed

as:
 TR= 500x1 + 700x2
Objective function
2. Monthly wood cost (WC) = WC of produced cars + WC
of produced boats. The wood cost of production of one
car (50 ) and the total number of produced car is x1, the
monthly wood cost of all produced cars is 50x1.
Likewise, the monthly wood cost of all boats is 70x2.

 Total monthly wood cost is :

WC= 50x1 + 70x2
Objective function
3. Woodwork labor cost (WLC) = WLC of produced cars +
WLC of produced boats. One car needs 1 hour of
woodwork labor and cost of 1 hour of this labor is 30 ,
the unit cost is 30 . The monthly cost of carpentry labor
used for all produced cars is 30x1. One boat requires 2
hours, the monthly cost of woodwork labor used for
boats is 60x2.
 Total monthly cost of woodwork labor: 
WLC= 30x1 + 60x2
Objective function
4. Painting and assembling labor cost (PALC) = PALC of
produced cars + PALC of produced boats. Both a piece
of car and boat need 1 hour of painting and assembling
labor. Cost of this labor is 20 per hour.

 Therefore the total monthly cost of painting and

assembling labor:
PALC= 20x1 +20x2
Objective function

5.The total monthly cost can be expressed as:

TC= WC + WLC + PALC
= (50x1 + 70x2) + (30x1 + 60x2) + (20x1 +20x2)
TC= 100x1 + 150x2
Objective function
6. The total profit:
TP = TR − TC
= (550x1 + 700x2) − (100x1 + 150x2 )
= 450x1 + 550x2

the objective function in the linear programming model is:

Maximize z = 450x1 + 550x2

450 and 550 in the function are termed objective function

coefficients.
Formulation
 3. Constraints
 If no restrictions are imposed, objective function (profit) can
expand to infinity. There are three limits (called constraints)
to the development of toys, though:
1. ABC, Inc. has just 5000 hours of woodwork labor
accessible per month.
2. No more than 3000 hours of finished labor can be used
each month.
3. Because of minimal demand, there will be a maximum of
2000 cars delivered each month.
Constraints
 Expressing the constraints in mathematical way:
 One car needs 1 hour of woodwork labor. If ABC manufactures
monthly x1 of cars, x1 hours of labor are consumed. Since one
boat requires 2 hours and the manufacturing quantity equals x2,
the monthly consumption of woodwork labor is 2x2 hours.
 Total consumption of woodwork labor for both products can be
expressed as x1 + 2x2. This is actual use of labor (in hours) that
cannot be greater than available number of hours (5000). With
this, the constraint can be:
x1 + 2x2 ≤ 5000
Constraints
 The creation of the second constraint regarding painting and
assembling labor is like to the foregoing: 
x1 + x2 ≤ 3000

 The last constraint is easy to be construct. The number of

produced cars x1 must be less than or equal to 2000:
x1 ≤ 2000

 Technological coefficients are coefficients of the decision

variables in the constraints while numbers 5000, 3000 and 2000
are termed right-hand side values.
  
Formulation
 Non-negativity Constraints
 Both decision variables have rational sign restrictions: because
the values of variables reflect numbers of toys made, we would
expect them not to be negative:
x1, x2 ≥ 0
Formulation of Mathematical Model
 Summary of mathematical model in standard form:

Maximize z = 450x1 + 550x2

subject to
x1 + 2x2 ≤ 5000
x1 + x2 ≤ 3000
x1 ≤ 2000
x1, x2 ≥ 0
Graphical Solution of
Linear Programming Problems
 When a linear programming problem only involves two
decision variables, it can be graphically overcome. The
next phase proceeds to solution:

 Step 1 - Graphing a feasible area

 That restriction (including non-negativity constraints) can be
drawn very easily; because all constraints have to be met
concurrently, the mixture of drawn constraints defines the area
that is feasible. Each point from the feasible area suits the
feasible solution.
 There are 3 constraints and 2 non-negativity constraints in
the ABC’s problem. Non-negativity constraints are simple
to graph, as all x1 and x2 variations must be in the first
quadrant of x1-x2 plane (Figure 2.1).
 Linear inequality graphing (woodwork labor constraint)
x1 + 2x2 ≤ 5000

 the borderline needs to be draw, corresponding to the

linear equation
x1 + 2x2 = 5000 .
 Coordinates of two points must be find to get the
borderline. The simplest way is to look for the
borderline’s intersection points with axes x1 and x2. If x1
is set to zero (i.e. no cars are manufactured), then x2 =
5000/2 = 2500 (2500 boats can be manufactured). This
condition refers to the point A (0, 2500) in Figure 2.2.

 Also, if x2 is set to zero (no boats are manufactured), then

x1 = 5000 (5000 cars can be manufactured). It links to the
point B (5000, 0) in Figure 2.2.
 Linking points A and B by a straight get a graphical
illustration of the equation x1 + 2x2 = 5000 We must now
decide which portion of the first quadrant (divided by line
AB) conforms to the x1 + 2x2 5000 inequality.

 For this reason the general approach is to pick an arbitrary

point (of course not from the line) and to test if it is
feasible. When the point is feasible so the whole area is
always feasible.
 The best way is to take origin, (0 , 0) in our case. After
these coordinates have been substituted by the constraints,
we get 5000 0 (the restriction is met). Therefore, the area
of origin included is feasible (shaded in Figure 2.2).

Figure 2.2 Woodwork Labor

 Drawn in Figure 2.3 is the second inequality 3000 x1 + x2 ≤
(painting and assembling labor constraint), the last constraint
2000x1 ≤ is comprehended in Figure 2.4.

Figure 2.3 Painting and Assembling Labor

 Feasible area can be seen on the left side of the line while
2000x1 = is emphasized by a line parallel to the axis x2.
Step 2 - Combining the constraints
 If all of the restrictions are drawn independently, they
must be placed together in a single graph. Practically, this
final graph may be built by systematic addition of the
individual feasible areas from the beginning.
 The ultimate graph of the feasible area in the example is
seen in Figure 2.5. Any solution in this area is feasible as
regards all the constraints.
Step 3 – Graphing an objective function
 In the example the goal of the management is represented
as the function of profit z= 450x1 + 550x2. Because of the
endless number of equations this feature can not
necessarily be viewed as a single line. The basic equation
depends on z value.
 Figure 2.6 introduces three of those equations of values
495,000, 1,485,000 and 2,475,000. All the lines are
parallel to each other and can be constructed in the same
way as the constraints borderline in Step 1. Both points on
a specific line produce the same profit, and hence the lines
are typically called isoprofit lines. The arrow expressed
income growth.
Step 4 – Finding the optimal solution
 Integrating the feasible region with the isoprofit lines, we
will consider the isoprofit line that is as far from the origin
as feasible, which also crosses the feasible field.

 The dotted isoprofit line in Figure 2.7 correlates to the

maximum profit z = 1,550 000. This line intersects a
viable area corner point, which is considered an optimal
solution. It is point X (1000, 2000)
 There are two potential ways of seeking the best approach
using the model's graphical representation:
 The first approach has only been illustrated. We can determine
the "best" point of the feasible area, by finding a slope and the
growth direction of the isoprofit line. This level is the optimal
solution, and the isoprofit line suits the ideal objective function
optimal value. Within this section of the text it is important to
notice that a convex set is the feasible field of all linear
programming models.
 A set of points S is a convex set if the section of the line
connecting each pair of points in S is entirely enclosed in S. 

 The disparity between convex and non-convex sets is

shown in Figure 2.8. Although the first three examples are
convex sets (a), (b) and (c), the group (d) is non-convex.
 The set (a) varies significantly from the sets (b) and (c),
due to nonlinear border. If the convex set boundary
consists only of linear segments, as seen in cases (b) and
(c), the set is called a convex polyhedron, which reflects
the standard feasible field of linear programming models.
It is the feature which is useful in linear programming
methods.
 The key problem is how to measure optimum solution of
coordinates X(1000, 2000). As it is apparent from Figure
2.6, this point is the borderline intersection of two
constraints. Determining the co-ordinates is therefore very
simple by solving the series of two linear equations. The
borderlines compare in our situation are:
x1 + 2x2 = 5000 , x1 + x2 = 3000 .

 Pretty simple solution: x1 = 1000 and x2 = 2000. Those

values are point X coordinates. Incorporating them into
objective function z = 450x1 + 550x2 = 1 550 000.
 It is important to identify a corner point before beginning
to explain the second approach used to find the best
solution in the graph. With respect to the convex
polyhedron definition it is possible to describe the corner
point clearly as follows:
 
A point P in convex polyhedron S is a corner point if it does
not lie on any line joining any pair of other (than P) points
in S.
 Keystone of the second approach is the basic linear
programming theorem:
 
The optimal feasible solution, if it exists, will occur at one or
more of the corner points.
 
 In this theorem, what we need is to define the feasible
area's corner points and determine the objective values for
all of those points. The optimal solution is the corner point
and has the highest objective value.
 The feasible area in the example contains 5 corner points
(Figure 2.9), of which the coordinates can be observed in
Table 2.1. All the coordinates were calculated in the
manner described above: after classification of the
intersected lines, the set of equations is solved and the x1
and x2 co-ordinates provide the solution. The objective
value z is then calculated for each solution by
incorporating the co-ordinates into the objective function.
 From the table it is evident that the optimal solution
corresponds to the maximum objective value
z = 1,550,000.
Corner point x1 x2 z

A 0 0 0

B 2000 0 900 000

C 2000 1000 1 450 000

D 1000 2000 1 550 000

E 0 2500 1 375 000

 Simplex method is a general method used for solving
linear programming problems. It is an iterative algorithm
for efficient searching for the optimal solution.

 The method uses the Gauss- Jordan method of solving

simultaneous equations. In addition, the method is based
on the basic linear programming theorem (the search can
concentrate only on the corner points of the feasible area).
 The run of algorithm starts in one of the corner points
(usually in the origin) and moves to adjacent corner that
improves the value of the objective function. The process
of movement continues until no further improvement is
possible.

 The simplex method and its variations have been

programmed and therefore even large linear programming
problems can be easy solved.
Understanding the Optimal Solution
 The appropriate and reliable analysis of the findings is
almost as critical as the model itself. After the solution has
been obtained, it is necessary to go back to the start of the
modeling process and compare the variables with their
real representations.
Understanding the Optimal Solution
 In the case, x1 represents the number of cars created each
month, and x2 is the number of boats generated every
month.
 Therefore it is optimal to produce 1000 cars and 2000
boats every month as the optimal solution we have got
x1 = 1000 and x2 = 2000.
 When the management maintains this output plan, ABC,
Inc. generates income of 1,550,000 per month
 When the production varied from the measured approach
but nevertheless followed all product constraints, the
profit would've been lower. By violating at least one limit,
the management can achieve greater income than 1 550
000. That will be an infeasible approach.
 Analyzing the findings ABC would be involved in
practical usage of available resources (working hours) and
meeting limited demand. If we integrate the optimal
values of x1 and x2 into all the restrictions, we can see
whether they are fulfilled exactly as equations or as
inequalities.
 As for woodwork labor, the limit's left-hand side value is
1000 + 2(2000) = 5000,
which is almost the same as the right-hand side value 5000
(the constraint is obligatory). Since the right-hand side
relates to the hours of work available, equality means that no
hour stays or all available hours are being used for optimal
production.
 The painting and assembling labor condition is similar.
The constraint's left-hand side value is
1000 + 2000 = 3000,
the right-hand side value is always equal to 3000; therefore,
all required painting and assembling labor hours are used.
 The last constraint relates to demand limitation (the
amount of cars created should be less than or equivalent to
2000). Because output of 1000 cars is optimal (the
constraint is non-binding), this is not the restriction that
affects ABC, Inc's production.
 The organization could increase cars production as it
succeeded in having more hours of work or developing
the technologies (i.e. reducing unit labor consumption).
Note:
 Slack variable is defined for the inequality of type “≤”.
 This variable assesses the difference between the left-hand
side and the right-hand side of the constraint. In both labor
constraints, zero is the slack variable in the example, as
both sides of the constraints equal to each other.
 In demand constraint, 1000 is the slack variable, as the
right-hand side value is 2000 and left-hand side value is
1000. In inequality of type “≥”, we express a surplus
variable assessing the difference between the left-hand
side and the right-hand side of the constraint. For
example, if ABC produce at least 600 cars because of
demand requirements (x1 ≥ 600) then ABC will actually
produce 1000 cars, therefore, 400 is the surplus variable.
 The estimation of the effect on the optimal solution of the
modifications in a particular environment is the concept of
a post-optimal (sensitivity) analysis. We have forecast
future increases in resource stocks (available labor hours)
in technology, so it is important to examine how shifts in
commodity prices impact profit.
 Figure 2.10 we compares the original objective function
z = 450x1+550x2 with the function z = 750x1 + 550x2 (the price of
the cars changes from 550 to 850 ), getting a new optimal solution
(2000, 1000) with the profit z = 2,050,000.
 Sensitivity analysis defines, typically for coefficients of
objective function and right-hand side values, the array of
their potential changes that do not have the cardinal effect
on the optimal solution.
 Changing the car’s price from 550 to 649 (i.e. the
objective function coefficient was improved from 450 to
549), the optimal solution would be the original corner
point (1000, 2000).
 Only modification would be higher profit, while the
production assembly would be alike. If the price increased
to 651, the optimal solution (2000, 1000) would be
attained, and resulting in this recommendation the
business should change the production assembly from the
base.
 The price 650 provides the business the option to
manufacture either 1000 cars (and 2000 boats) or 2000
cars (and 1000 boats).
 Modification in coefficients of objective function impacts
only its slope, whereas the feasible area remains static.
The best corner point was determined by the slope of the
function. If right-hand side value is modified the feasible
area is also modified.
 The constraint’s borderline’s movement was due to
change (the new borderline is parallel with the original).
Smaller change in the right-hand side value means smaller
change in the feasible area while big changes in the
feasible area makes the cardinal change as shown by
Figure 2.11 (decrease in available painting and assembling
labor from 3000 to 2000 hours).
 Corner points original number of 5 decreases to 3. In this
situation, new optimal solution is presented by the corner
point (0, 2000).

Figure 2.11 Change in Painting and Assembling Labor

 As the optimal corner point is out of the constraint of
woodwork labor, there are several idle hours of this labor,
i.e. in this inequality the slack variable now is nonzero.
The precise sum remaining can be calculated simply by
inserting the coordinates (0, 2000) into the constraint's
left- hand side. When 0 + 2(2000) = 4000, the amount of
hours remaining unused is 5000-4000 = 1000.
Note:
 These modifications can be analyzed independently, i.e.
only one parameter is modified (the other is fixed), so we
are evaluating the effect on the optimal solution and the
profit. The basic aspects of the sensitivity analysis are the
lowered costs and the shadow prices along with the levels
of objective function coefficients and the ranges on right-
hand hands.
Special Cases of Linear Programming Models
 Only one optimal solution has been attained in the
production problem of ABC, Inc. It is a distinctive in most
cases linear programming problems. Figure 2.12 express
the feasible area together with the objective function z (the
arrow specifies the improvement direction’s of the
objective value). Unique optimal solution is the corner
point A.
 In the previous discussion, the price of the car is 650
(instead of 550), the management of ABC, Inc. has two
basic possibilities how to optimize the profit. Producing
1000 cars (and 2000 boats) or 2000 cars (and 1000 boats)
would bring the identical optimal profit 1,650,000.
A linear programming problem with two or more optimal
solutions is said to have alternative (or multiple) optimal
solutions.
 A linear programming problem with two or more optimal
solutions is said to have alternative (or multiple) optimal
solutions.
 This condition occurs in graphical depiction of the model
when the objective function line is parallel to the borderline
of one constraint, as can be shown in Figure 2.13.
 Because the objective function reflects the isoprofit line (in
case of maximization) or the isocost line (in case of
minimization), all the solutions at the edge of the feasible
area have the same objective value (optimal). There are two
optimal corner points (B and C) and the infinite number of
optimal points on line segment BC.
 Figure 2.14 shows an interesting alternative of just described
case. The difference is evident – the feasible area is unbounded
and there is only one optimal corner point D; the other optimal
points lie on the borderline running to infinity.
 There is no optimal solution if the feasible solution area is
unbounded and the objective value is being enhanced in
the direction of unboundedness, therefore, the optimal
solution is endless (see Figure 2.15). Since these instances
are uncommon in reality, this finding typically indicates
mistake in formulation.
 Infeasibility exists when no solution meets any of the
constraints. There is no common feasible area (no feasible
solution) in case of two constraints graphed in Figure
2.16.
 In reality this scenario sometimes occurs, particularly if
the manager wants to be too accurate in model
formulation. In order to remove the infeasibility, the
model must be simplify by for example eliminating any
vain restrictions.
END OF MODULE
Exercises
 Required:
1. Define the decision variables
2. Compute for the Optimal Solution

 PR Developments is skilled in analyzing the response of

customers to the latest goods and services. A client,
launching new form of body lotion, requested the PR
Developments to plan a campaign of specific door-to - door
interviews about the opinion of households. Households
with children and without children should be interviewed;
interviews will be held both daytime and nighttime.
 A schedule for performing 1000 interviews with the
following constraints is set:
 
1. There will be interviews with at least 300 households with
children.
2. Interviews will be conducted for at least 400 households without
children.
3. The total number of evening interviews should be greater than or
equal to the number of daytime interviews.
4. At least 35 percent of interviews should be conducted in
households with children at evening.
5. At least 65 per cent of interviews will be performed in
households without children evening time
 The cost varies according to interview type. Household
interview with children is more complicated and longer;
evening interviewers are paid better than daytime interviewers. 
 The estimation of the cost is as follows:

Household Daytime Evening

interview interview
with children 50 60
without children 40 50
 PR Creations project manager can recommend interview
schedule that would satisfy the constraints for the lowest
minimum total cost.