Chapter 2:

Linear Programing and Geometric/Graphic/

Method to Solve LP Problems
Objectives:
 Introduction
 Structure of Linear Programming Model
 Application Area of LP
 Graphical Solutions of LPP
 Special Case in LPP
Introduction to LP Model
• Linear Programming(LP) is a mathematical process that has been
developed to help management in decision making involving the
efficient allocation of scares resources to achieve a certain objective
• LP is a method for choosing the best alternative from a set of feasible
alternatives
Cont.
 LPM
• LPM is also called strategic resource allocation model
• LPM is a model, which is used for optimum allocation of scarce or
limited resources to competing products or activities under such
assumptions as certainty, linearity, fixed technology, and constant
profit per unit.
• they are a special type of mathematical programming model in that the
objective function and all constraint functions are linear.
• LP technique may be used for solving broad range of problems arising in
business, government, industry, hospitals, libraries, etc.
Structure (Components) of LP Model
 Cont.
1. Objective Function
• Is mathematical statement of the objective
• is the goal or objective of a management, stated as an intent to maximize or to
minimize some important quantity such as profits or costs
• is the criterion by which all decisions are evaluated.
• provides the focus for problem solving.
• a single, quantifiable objective must be specified by the decision maker in in
linear programming models, .
• Because we are dealing with optimization, the objective will be either
maximization or minimization.
• Hence, every LP problem will be either maximization or a minimization
problem.
• Once the objective is specified, it becomes the measure of effectiveness
against which alternate solutions are judged.
 Cont.
2. Decision variables
• DVs Represent unknown quantities to be solved for.
• The decision maker can control the value of the objective, which is
achieved through choices in the levels of decision variables.
• For example, how much of each product should be produced in order to
obtain the greatest profit?
 Cont.
3. Constraints
• Are the resource restrictions in LP model.
• The ability of a decision maker to select values of the decision variables
in an LP problem is subject to certain restrictions/limits
• coming from a variety of sources:
• availabilities of resources (e.g., raw materials, labor time, etc.),
• legal or contractual requirements (e.g., product standards, work
standards, etc.),
• technological requirements (e.g., necessary compressive strength or
tensile strength) or
• Forecasts demands or supplies
• customer orders,
• company policies, and so on.
 Cont.
3. Constraints…Cont’d
• Only solutions that satisfy all constraints in a model are acceptable
• solutions that satisfy all constraints referred to as feasible solutions.
• There may be several points that lie within the feasible region and
thus can be feasible solutions.
• But all feasible values are not optimal solutions.
• The optimal solution will be the one that provides the best value for
the objective function.
• The best value is the optimal value which can be expressed as Max Z
or Min Z.
 Cont.
3. Constraints…Cont’d
Generally speaking, a constraint has four elements:
1.A right hand side (RHS) quantity that specifies the limit for that
constraint. It must be a constant, not a variable.
• RHS has an algebraic sign that indicates:
• whether the limit is an upper bound that cannot be exceeded ( ≤ ),
• a lower bound that is the lowest acceptable amount ( ≥ ), or
• an equality that must be met exactly ( = )
2. System/structural constraints– involve more than one decision variable
3. Individual constraints – involve only one constraint, and
4. Non-negativity constraints – specify that no variable will be allowed to
take on a negative value. The non-negativity constraints typically apply in
an LP model, whether they are explicitly stated or not
 Cont.
4: Parameters
• parameters are symbols (fixed numerical numbers) that represents the objective function and
the constraints.
• The parameters are values that specify the impact that one unit of each decision variable will
have on the objective and on any constraint it pertains to.
• See the following model to understand the components of the LPM structure

 Non-negativity implies that the company can stop production of x and y or

can manufacture any amount of x and y. That is it cannot manufacture
negative quantities of x and y.
 Basic Assumptions of LP Model
I. Linearity:
• each decision variable has a linear impact on the objective function and
in each constraint in which it appears.
• In terms of a mathematical model, a function or equation is linear when
the variables included are all to the power 1 (not squared, cubed, square
root, etc.) and no products (e.g., x1x2) appear.
• For example,
• f (x1, x2) = 2x1 + x2 is a linear function of x1 and x2,
• but f (x1, x2) = x21 x2. is not a linear function of x1 and x2.

• Example: f (x1, x2) = 0x + 2y ≤ 50 – is linear inequality

: f (x1, x2) = 0x3 + 2y2 ≤ 50 – is not linear inequality
 Cont.
II. Proportionality:
 The contribution of the objective function from each decision variable
is proportional to the value (parameter) of the decision variable.
• The amount of each resource used (supplied) and its contribution to the
profit (or cost) in the objective function must be proportional to the value
of each decision variable.

• For example given max z = 5x + 4y (Objective function).

• For example, making 3 units of x contributes $15 (5x3) to the
OF, and
• making 3 units of y contributes $12 (4x3) to the OF.
 Cont.

II. Proportionality---
The contribution of each variable to the left-hand side of each
constraint is proportional to the value of each variable.

For example, let a certain labour constraint is 3x +4y ≤ 300

if 3 products of x is to be produced, then 2 x 3 = 6 labour hrs are
used, and
if 4 products of y is to be produced, then 4x4 = 16 labour hrs. are
used .
 Cont.
III. Additivity:
• means that the value of the objective function can be found by summing the
objective function contribution of all decision variables.
• The contribution to the objective function of any decision variable is independent
of the values of the other decision variables.
• For example,, given Max Z = 5x + 4y, no matter what the value of y, the manufacture
of x products will always contribute 5x dollars to the OF, and no mater what the
value of x, the manufacture of y products will always contribute 4y dollars to the OF
• This implies that the value of the objective function is the sum of the contributions from
individual variables.
 The total profit earned from the sale of two products X and Y must be equal to the
sum of the profits earned separately from X and Y.
 If the company makes 10 units of X and 5 units of Y, then
 Max Z = 5x10 + 4x5 = $70
 Cont.
III. Additivity….
• Also mean the total resources used can be found by summing the resources used
for all decision variables.
• The contribution of a variable to the left-hand side of each constraint is
independent of the values of the variable.
• This implies that the left-hand side of each constraint is the sum of the
contributions from each variable.
For example, given the Constraint M2: 1x + 2y ≤ 25,
 no matter what the value of y, the manufacture of x units use 1x M2 hours, and
 no matter what the value of x, the manufacture of y units use 2y M2 hours, and
 If the company makes 10 units of X and 5 units of Y, then
 Constraint M2 hours used = 1x10 + 2x5 = 20 hrs out of 25 hrs available
 Cont’d.
VI. Divisibility (Continuity)-
• means that the decision variables are continuous; assumes positive rational
numbers/values
• requirement pertains to potential values of decision variables; that is it is
assumed that non-integer values are acceptable.
• The divisibility assumption plus the non-negativity constraints mean that
decision variables can take on any value greater than or equal to zero.
• However, if the problem concerns, for example, the optimal number of houses
to construct, 3.5 do not appear to be acceptable.
• Instead, that type of problem would seem to require strictly integer solutions. In such
cases, integer-programming methods should be used.
• It should be noted, however, that some obvious integer type situations could be
handled under the assumption of divisibility.
• For example the production capacity of the machine is 2.30 hrs. per unit.
 Cont’d.
V. Certainty:
• This requirement involves two aspects of LP models.
• One aspect relates to the model parameters, i.e., the numerical values
associated to the decision variables.
• It is assumed that these values are known and constant.
• In practice, production times and other parameters may not be truly
constant.
• Therefore, the model builder must make an assessment as to the degree
to which the certainty requirement is met.
• Because large departures almost surely will have a significant effect on
the model and the value of objective function.
 Cont’d.
V. Certainty….
• The other aspect is the assumption that all relevant constraints have
been identified and represented in the model.
• The LPM operates under the system constraints. Thus the left out of
one or more constraints from may affect the optimality of the model
• Since the organization operates under numerous resource constraints,
the model builder should assess all important constraints that limits
the objective function of the organization
VI. Non-negativity:
• assumes that negative values of variables are unrealistic and,
therefore, will not be considered in any potential solutions.
• Only positive values and zero will be allowed and the non-negativity
assumption is inherent in LP models.
 Advantages of Linear Programming

helps in attaining the optimum use of scarce productive resources.

It indicates how a decision maker can employ productive resources
effectively by selecting and allocating these resources.
LP techniques improve quality of decisions. The decision making
approach of the user of this technique becomes more objective and less
subjective.
Highlight the bottlenecks in the production process. For example, when
a bottleneck occurs, some machines cannot meet demand while others
remain idle for some of the time.
• Helps in re-evaluation of a basic plan for changing conditions. If
conditions change when the plan is carried out, they can be determined so
as to adjust the remainder of the plan for best results.
 Formulation (Modelling) of LP
• Problem formulation, or modelling, is the process of translating the verbal
statement of a problem into a mathematical statement.
• Is the process of constructing the mathematical model using the components of
the LP based on the word problems.
• Decision variables are the variables whose values are unknown and are searched
• The coefficients of the variables in the OF are called the profit or cost
coefficients.
• Profit coefficient express the rate at which the value of the OF increases by
including in the solution one unit of each of the decision variables
• Cost coefficients express the rate at which the value of the OF decreases by
including in the solution one unit of each of the decision variables.
• The coefficients of the constraints’ variables are called the input-output
coefficients that indicate the rate at which the given resources are depleted or
utilized.
Steps in formulating LP models:
• Given the statement of the word problem, mathematical
model is developed by the following steps:
1. Identify the decision variables.
2. Determine the objective function.
3. Identify the constraints.
4. Determine appropriate values for parameters and determine
whether an upper limit, lower limit or equality is called for.
5. Build a model using this information
6. Validate (test) the model.
 Linear Programming Applications
• There is a wide range of problems that lend themselves to solution by linear
programming techniques.
• Some of these include
• production management (product mix, blending problems, production planning,
Assembly line balancing…),
• Marketing management (media selection, traveling sales man problem,
physical distribution),
• Financial management (portfolio selection, profit planning),
• agricultural application,
• military applications,
• personnel management (staffing problem, determination of equitable
salary and etc.)
 Solving LP Problems
using Graphical (Geometrical)
Method
LP Modeling & solving using Graphical (Geometrical) methods
 Geometrical/Graphical methods:
 are applied when we have only two decision variables in the problem.
 the inequalities (structural constraints) are considered to be equations.
 This is because one cannot draw a graph for inequality.
 The feasible solutions to the problem always lies in first quadrant (I
quadrants).
 Because we have non-negativity constraint in the problem requiring that
all the decision variables must have positive values.
 If the feasible solution lies in negative quadrants, it is extended to quadrant
I.
Steps of solving using graphical method

1. Change the inequalities to equalities,

2. Compute the intercepts
3. draw the graph using intercepts
4. Determine the corner points
5. Determine the feasible region
6. Use corner points or objective function method to determine the
optimal solution and optimal value
7. Interpret the result
 Graphic Solution- Example 1-Max. case
• Application- Product mix
• Company A decided to manufacture two models of color TV sets; Model A and B.
The profit realized is $300 from A and $250 from set B. Model A requires 2 labor
hrs and model B requires 1 labour hr. Moreover, Model A requires 1 machine hr
and model B requires 3 machine hrs. There are only 40 hrs available for labor
each day in the production department and only 45hrs available on machine time.
The company has an ability to sale (supply) 12 set of model A. The problem of the
company is to produce the optimal models that maximize the profit.
• Required:
Formulate L.P.M. to maximize the profit.
How many sets of each model of TV sets will be produced each day so that the
total profit will be as large as possible?
Compute the amount of slack for the Optimal of TV sets.
Cont.

Resources used per unit

Constraints Model A Model B Maximum Available hrs.
(x2)
(x1)

Labor hr. 2 1 40
Machine hr. 1 3 45
Marketing/demand 1 0 12
Profit $300 $250  
 Solution
1. Formulation of mathematical model (LPM):
Max Z=300X1 +250X2
st: 2X1 +X2 < 40  Labor hr.
X1 + 3X2 < 45  Machine hr.
X1 + < 12  Marketing hr.
X1, X2 > 0
2.Convert constraints inequalities into equalities and calculate
intercepts by simply assuming both sides (RHS & LHS) are equal
2X1 +X2 = 40 ==> (0, 40) and (20, 0)
X1 +3X2 = 45 ==> (0, 15) and (45, 0)
X1 = 12 ==> (12, 0)
X1, X2 = 0
 Solution…Cont’d
3. Draw the graph using the intercepts

•X.2 2x1 +x2 ≤ 40-Labor hrs.

(0, 40) x1 ≤ 12-Marketing

x1 +3x2 ≤ 45-Machine hr.

B (0,15)
C (12, 11)
Feasible
Region
X1
A D(12, 0) 20 45
 Solution…Cont’d
4. Identify the feasible area/Space/ of the solution which satisfies all constrains.
• Feasible area/region/space is the region in which all solutions that possibly
satisfy the all constraints at same time are included
• Feasible solutions are all values that can satisfy all constraints and can be
included in the FR
• Optimal solutions are the values that optimize the LP model.
• In case of Max problem, optimal solutions are that maximize the objective
function/target value/
• In case of Min problem, optimal solutions are that minimize the objective
function/target value/
• Note that all optimal solutions are feasible solutions but the vice versa may not
• In this case the FR lies in
• Polygon ABCD: A (0, 0), B (0, 15), C (12, 11) and D (12, 0)
 Solution…Cont’d
5. Identify the optimal points/values:
 In maximization problem, we select the co-ordinates giving maximum value.
 And in minimization problem, we select the co-ordinates, which give
minimum value.
Corners Max Z = 300 x1 + 250x2
A(0, 0) = 300x$0 + 250x$0 = $0
B(0, 15) = 300x$0 + 250x$15 = $3750
C(12, 11) = 300x$12 + 250x$11 = $6,350
D(12, 0) = 300x$12 + 250x$0 = $3600

6. Interpretation of the result - The company has to produce 12 units of

Model A TV set and 11 units of model B TV set to yield the maximum
profit of $6,350
 Slack
• is any unused capacity/resources/ for a constraint
• represents idle resource or unused resources,
• do not affect the value of the objective function.
• can not be less than 0, that is, it does not assume negative value because it is
associated with ≤ constraints.
• for each constraint is determined using optimal solution; x1= 12, & x2 = 11.

Constraints Amount of Hrs used Available hrs Slack hrs = (Av – used)
Labour hrs 2 (12) + 11= 35 40 5
Marketing 12 = 12 12 0
Machine hr. 12 +3 (11) = 45 45 0
 Note the constraint that includes the feasible solution always have zero slack
 Slack …Cont.
• Thus, the complete solution tells management that
the production of 12 Model A TV set and 11 Model B TV set will
require
 all available Machin hours ( 45 hrs) &
 all available demand (11), and
 Unused /idle/ 7 hours of labour time
• Thus 7 hours of unused labour time is referred to as slack.
 LP Modeling & GS --Maximization case 2
• Application: Product Mix
• A company manufactures two products: forklift and truck. These
products require the following machine resources. The resources are the
capacities of machine M1, M2, and M3. The available capacities for the
machines are 50, 25, and 15 hours respectively in the planning period.
Forklift requires 1 hour of machine M2 and 1 hour of machine M3. the
truck requires 2 hours of machine M1, 2 hours of machine M2 and 1 hour
of machine M3. The profit contribution of products X and Y are Birr 4
per unit and Birr 5 per unit respectively.
• Formulate the LP model to the optimal values that maximize the profit of
the company
 Solution…Cont’d
• Step 1: determine the decision variables
• Let the company manufactures x units of forklift and y units of truck.
• Step2: determine the objective: Max(Z): 4x + 5y
• Step 3: determine the constraints for each product and machine
Const. M1 = 0x + 2y ≤ 50
Const. M2 = 1x + 1y ≤ 25
Const. M3 = 1x + 2y ≤ 15
 Solution…Cont’d

• Step 4: formulate the LP model and determine intercepts

Max Z = 4x + 5y
St. M1. 0x + 2y ≤ 50
M2 1x + 2y ≤ 25
M3. 1x + 1y ≤ 15
x, y ≥ 0

Intercepts:
St. M1. 0x + 2y = 50  (0, 25) => horizontal line
M2 1x + 2y ≤ 25  (0, 12.5), ( 25,0)
M3. 1x + 1y ≤ 15  (0, 15), (15, 15)
Step 5: Draw the graph & determine the
FR
Max Z = 4x + 5y M1. 0x + 2y ≤ 50
M2 1x + 2y ≤ 25

M3. 1x + 1y ≤ 15

The FR lies in quadrant ABCD:

A(0, 0), B(0, 12.5) C (5, 10 ) & D(0, 15)
FR
Step 6: Detrain the Optimal points/value/

First determine the point C. 1x + 2(10) = 25

1x + 2y = 25 x = 25- 20 = 5
1x + 1y = 15 C(5, 10)
y = 10 – by eliminating x

Corners OF values
A(0, 0) = 4(0) + 5(0) = $0
B(0, 0) = 4(0) + 5(12.5) = $62.5
C(5, 10) = 4(5) + 5(10) = $70
D( 0, 15) = 4(0) + 5(15) = $75 The Optimal value
 Interpret the result
 The exact location of the optimal solution point is x = 5 & y= 10
 Hence, the optimal production quantities for manufacturing company are 5
forklifts and 10 trucks, with a resulting optimal profit contribution of
$6,350 (optimal value)

Compute the Slack

Constraints Amount of Hrs used Available hrs Slack hrs = (Av – used)
M1 0 (0) + 2(15) = 30 50 20
M2 1 (0) + 2(15) = 25 30 0
1(0) + 1(15) = 15 15 0
M3
 Maximization case 3.
• Par, Inc., is a small manufacturer of golf equipment and supplies whose
management has decided to move into the market for medium- and high-priced
golf bags. Par’s distributor is enthusiastic about the new product line and has
agreed to buy all the golf bags Par produces over the next three months.
• A golf bag, management determined that each golf bag produced will require the
following four operations: cutting and dyeing the material; sewing, finishing
and inspection and packaging.
• The director of manufacturing analysed each of the operations and concluded that
if the company produces a medium-priced standard model, each bag will
require 7⁄10 hour in the cutting and dyeing department, 1⁄2 hour in the sewing
department, 1 hour in the finishing department, and 1⁄10 hour in the inspection
and packaging department.
• The more expensive deluxe model will require 1 hour for cutting and dyeing,
5⁄6 hour for sewing, 2⁄3 hour for finishing, and 1⁄4 hour for inspection and
packaging.
cont’d
• Par’s production is constrained by a limited number of hours available in each
department where the director of manufacturing estimates that 630 hours for
cutting and dyeing, 600 hours for sewing, 708 hours for finishing, and 135
hours for inspection and packaging will be available for the production of
golf bags during the next three months.
• The accounting department analysed the production data, assigned all relevant
variable costs, and arrived at prices for both bags that will result in a profit
contribution of $10 for every standard bag and $9 for every deluxe bag
produced.
• Required tasks:
• Formulate the LP model
• Determine the optimal solution and the optimal value using corner points method of
graphical method
• Interpret the result
• Determine the slake amount.
 Cont’d
• Describe the Objective: The objective is to maximize the total contribution to
profit.
• Describe Each Constraint: Four constraints relate to the number of hours of
manufacturing time available; they restrict the number of standard bags and the
number of deluxe bags that can be produced.
• Constraint 1: Number of hours of cutting and dyeing time used must be less than
or equal to the number of hours of cutting and dyeing time available.
• Constraint 2: Number of hours of sewing time used must be less than or equal to
the number of hours of sewing time available.
• Constraint 3: Number of hours of finishing time used must be less than or equal
to the number of hours of finishing time available.
• Constraint 4: Number of hours of inspection and packaging time used must be
less than or equal to the number of hours of inspection and packaging time
available.
 Formulation of LPM-E.g. 2 ….cont’d
• Define the Decision Variables:
• The controllable inputs for Par, Inc., are (1) the number of standard bags
produced, and (2) the number of deluxe bags produced.
• Let S = number of standard bags and D = number of deluxe bags.
• In linear programming terminology, S and D are referred to as the decision
variables.
• Par’s total profit contribution comes from two sources: the profit contribution
made by producing S standard bags, and the profit contribution made by
producing D deluxe bags.
• If Par makes $10 for every standard bag, the company will make $10S if S
standard bags are produced. Also, if Par makes $9 for every deluxe bag, the
company will make $9D if D deluxe bags are produced.
• Thus, we have Total Profit Contribution, Max Z = 10S + 9D
 Formulation of LPM-E.g. 2….cont’d

• Formulate the Mathematical Model for the Problem:

• Max Z = 10S + 9D st.

7⁄10S + 1D ≤ 630  hrs of cutting & dying time
1⁄2 S + 5/6D ≤ 600 hrs sewing time
1S + 2⁄3D ≤ 708 Hrs of finishing time
1⁄10S + 1⁄4D ≤ 135  Hrs of inspection and packaging time
S, D ≥ O  Non-negativity
Cont’d.
Determine the optimal solutions and optimal value.
• Our job now is to find the product mix (i.e., the combination of S and
D) that satisfies all the constraints and, at the same time, yields a
value for the objective function that is greater than or equal to the
value given by any other feasible solution. This values are called
feasible values (alternative courses of actions).
• Once Feasible values are calculated, we will have found the optimal
solution and optimal value to the problem and determine the slack
amounts
 Compute the point of intersection of concurrent constraints
• Use simultaneous equation to obtain the intersection points of the constraints at
points C and D (i.e., intersection points of C & D constraint and finishing constraint).
7/10 S + 1D = 630……C & D
1S + 2⁄3 D = 708…….finishing
• To solve for D: 1S + 2⁄3 D= 708  S = 708 – 2/7 D. By substituting this result in the
equation 7/10 S + 1D = 630, we get:
7/10 (708 – 2/3 D) + 1D = 630
495.5 -14⁄30 D + 1D = 630
(-14D + 30D)/30 = 630 – 495.5
16D/30 = 134.5  D = (30 *134.5)/16  D = 252
• To solve for S:1S +2/3 D =708  S+2/3(252)S =708 – 168 S = 540
• In the same way solve for constraints C & D and I & P at point C. We get D = 300,
and S = 420
Draw the Graph
 Determine the Feasible Region (FR)
• The Feasible solutions lie in the feasible region that satisfies all constraints.
• The Feasible region is the Polygon ABCD. Therefore the alternative feasible
solutions are included under this polygon.
• But note that all feasible solutions in FR does not mean they are optimal values but
optimal values are included in feasible solutions.
• Determine the Optimal solution and Value that can achieve the greatest profit
using the corner points/coordinates/method.
Coordinates Max Z = 10S + 9D
A(0,0) 10*0 + 9*0 = $ 0
B(0,360) 10*0+9*360 = $ 3240
C (300, 420) 10*300+9*429 = $6861
D( 252, 540) 10*540+9*252 = $7668
E (708,0) 10*708 +9*0 = $1,080
 Interpretation of the Result
• The exact location of the optimal solution point is S = 540 and D = 252.
• Hence, the optimal production quantities for Par, Inc., are 540 standard
bags and 252 deluxe bags, with a resulting optimal profit contribution of
10(540) 9(252) = $7668 (optimal value).
Determine the amount of Slack variable of hrs at S = 540, and D = 252
for each constraints
Constraints Amount of Hrs used Available hrs Slack hrs
C & D hrs 7⁄10 *(540) + 1*(252) 630 0
Sewing hrs 1⁄2*(540)+5/6*(252) =480 600 120
Finishing hrs 540 + 2⁄3*(252) = 708 708 0
I & P hrs 1⁄10*(540)+1⁄4*(252) =117 135 18
 The Slack Variable
• Thus, the complete solution tells management that the production of 540
standard bags and 252 deluxe bags will require all available cutting and
dyeing time (630 hours) and all available finishing time (708 hours) while
600-480 =120 hours of sewing time and 135-117 = 18 hours of inspection
and packaging time will remain unused.
• The 120 hours of unused sewing time and 18 hours of unused inspection
and packaging time are referred to as slack for the two departments.
• In linear programming terminology, any unused capacity for a constraint
is referred to as the slack associated with the constraint.
• Unused capacity (slack) makes no contribution to profit; thus, slack
variables have coefficients of zero in the objective function. This zero
coefficient implies that slack variables, which represent unused resources,
do not affect the value of the objective function.
 Other Information at graphical solution
• By finding the optimal solution point Par, Inc. bags case, we can see that:
• the cutting and dyeing and the finishing constraints restrict, or bind, the
feasible region at these optimal points. These constraints are called binding
constraints. Thus, this solution requires the use of all available time for these
two operations. In other words, the graph shows us that the cutting and dyeing and
the finishing departments will have zero slack.
• On the other hand, the sewing and the inspection and packaging constraints are
not binding the feasible region at the optimal solution, which means we can
expect some unused time or slack for these two operations. These constraints are
called non-binding constraints.
• In addition the sewing capacity constraint in particular, did not affect the
feasible region. That is, the feasible region would be the same whether the sewing
capacity constraint were included or not. The sewing constraint does not affect the
feasible region and thus cannot affect the optimal solution; it is called a
redundant constraint.
Optimizing by Minimization
• In LP problem minimization case is used to reduce the unfavourable
things to minim point possible.
• Many linear programming problems involve minimizing as an objective
such as cost instead of maximizing a profit function.
• A restaurant, for example, may wish to develop a work schedule to meet
staffing needs while minimizing the total number of employees.
• Also, a manufacturer may seek to distribute its products from several
factories to its many regional warehouses in such a way as to minimize
total shipping costs.
• Minimization problems can be solved graphically by first setting up the
feasible solution region and then using the corner-point method or
objective function method to find the values that yield the minimum cost.
 Minimization Case 1
• Cohen Chemicals, Inc., produces two types of photo-developing fluids. The first,
a black-and-white picture chemical, costs Cohen $2,500 per ton to produce.
The second, a color photo chemical, costs $3,000 per ton. Based on an analysis
of current inventory levels and outstanding orders, Cohen’s production manager
has specified that at least 30 tons of the black-and-white chemical and at least
20 tons of the color chemical must be produced during the next month. In
addition, the manager notes that an existing inventory of a highly perishable raw
material needed in both chemicals must be used within 30 days. To avoid wasting
the expensive raw material, Cohen must produce a total of at least 60 tons of the
photo chemicals in the next month.
• Required tasks:
• Formulate the LP to minimize the cost of Cohen chemicals, Inc.; determine the
optimal solution and optimal value; interpret the result; determine the surplus
value for each constraints.
 Solution-Table summary

• The decision variables:

• Let X1 = number of tons of color picture chemical produced and
X2 = number of tons of black-and-white picture chemical produced
Table summary
Constraints (chemicals) Products Min production
requirements
x1 x2
tons of black & white picture 1 0 ≥ 30
chemical
tons of color picture chemical 0 1 ≥ 20
Total production 1 1 ≥ 60
cost per unit $2,500 $3,000
 Solution
• The Model
• Min Z = $2,500X1 + $3,000X2 St.
X1 ≥ 30 tons of black-and-white chemical
X2 ≥ 20 tons of color chemical
X1 + X2 ≥ 60 tons total
X1, X2 ≥ 0 non-negativity requirements
• Convert the inequalities to equalities and determine the interception
points
• x1 = 30  (0, 0) (30,0)
• x2 = 20  (0, 20) (0, 0)
Solution…Cont’d
• Draw the graph using intercept points
 Solution…Cont’d
• Determine the Corner points
• Minimization problems are often unbounded outward (that is, on the right
side and on the top).
• In this case, there are only two corner points, a and b.
• Determine the optimal solution
• The optimal solution will lie at one of the corners.
• Minimization problems are often unbounded outward (that is, on the right
side and on the top), but this characteristic causes no problem in solving them.
As long as they are bounded inward (on the left side and the bottom), we can
establish corner points. The optimal solution will lie at one of the corners. In
this case, there are only two corner points, a and b. It is easy to determine that
at point a, X1= 40 and X2 = 20, and that at point b, X1 = 30 and X2 = 30. The
optimal solution is found at the point yielding the lowest total cost.
 Solution
• Thus total cost at a
2,500X1+3,000X2 = 2,500(40)+3,000(20) = $160,000
• Total cost at b
2,500X1+3,000X2 = 2,500(30)+3,000(30)= $165,000.

The lowest cost to Cohen Chemicals is at point a.

• Hence the operations manager should produce 40 tons of the black-and-
white chemical and 20 tons of the colour chemical.
 Solution…Cont’d

• Interpreting the Result:

• The lowest cost to Cohen Chemicals is at point a. Hence the operations manager
should produce 40 tons of the black-and-white chemical and 20 tons of the color
chemical to minimize the cost of production.
• Determine the Surplus resource at x1 =40, and x2= 20

Amount Originally available Surplus

Constraints
Chemical produced resource (Av –Used)

tons of b & w chemical 40 + 0 = 40 30 -10

tons of color chemical 0 + 20 = 20 20 0- no surplus
40 +20 = 60 60 0- no surplus
Total production

• NB - slack variables are always positive whereas

- surplus variables are always negative
 Example 2: Minimization
• ABC Company mixes two foods – food K & food L- for a special diet. Food
K has 30 units of vitamin C and 90 units of vitamin D per kg. Food L has 40
units of vitamin C and 50 units of vitamin D per kg. The mixture is to have
at least 1,200 units of vitamin C and at least 2970 units of vitamin D. If
Food K costs 30 cents per kg, and Food L costs 20 cents per kg, how many
kg of each food should be used to meet this requirement while keeping
costs to minimum?. Solve the problem using graphic method.
Cont’d…
Cont’d…
 Cont’d…

• Point B is the intersection point of the two graphs, which is found when
the two constraints are equal. Use elimination procedure to determine the
values at the point of intersection.
 30X1+40X2 = 1,200 - multiply by -3 30X1 + 40( 9) =1200
90X1+ 50X2 = 2970 30X1= 1200 - 360

-90X1+ -120X2= -3600 30X1 = 840

90X1+ 50X2= 2970 X1 = 28
-70X2 = -630
X2 = 9
SO B (28, 9)
• All the three corners (A, B, and C) satisfies the constraints, but where is
the optimal value found is our next concern.
• So, we have to evaluate the objective function by considering this three
corner (extreme) points:
Cont’d…

• Thus the minimum cost is 1,020 cents when 28 kg of food K and 9

kg of food L are used.
 Other Application areas of LP- Exercise
• Mix of Ingredients
• A soup company wants to determine the optimal ingredients for its vegetable soup.
The main ingredients are: vegetables, potatoes, carrot, onions, meat, water,
flavorings
• The soup must meet these requirements:
• No more than half of the soup can be vegetables
• The ratio of water to meat should be 8:1
• The amount of meat should be between 5 and 6 percent of the soup.
• The flavorings should weigh no more than ½ ounce.
• The per ounce of the ingredient is $0.02 for the vegetables each, $0.05 for the meat,
0.001 for the water, and $ 0.05 for the flavorings.
•  Formulate an LP model that will determine the optimum amounts of the various
ingredients to achieve 15 ounce cans of soup at minimum cost.
• Chemical mixture
Cont.
• A chemical corporation produces a chemical mixture for the customer in
1000-pound batches. The mixture contains three ingredients- Zinc, mercury
and potassium. The mixture must conform to formula specifications (i.e., a
recipe-instruction) supplied by a customer. The company wants to know
the amount of each ingredient to put in the mixture that will meet all the
requirements of the mix and minimize total cost.
•  The customer has supplied the following formula specifications for each
batch of mixture.
• The mixture must contain at least 200 lb of mercury
• The mixture must contain at least 300 lb of zinc
• The mixture must contain at least 100 lb of potassium
• The cost per pound of mixture is of Mercury Birr4, of zinc Birr 8 and of
potassium Birr 9.
 Cont.
• Investment
• Innis consulting group Investments manages funds for a number of companies and wealthy
clients. The investment strategy is tailored to each client’s needs. For a new client, Innis has
been authorized to invest up to $1.2 million in two investment funds: a stock fund and a
money market fund. Each unit of the stock fund costs $50 and provides an annual rate of
return of $5 per dollar invested; each unit of the money market fund costs $100 and provides
an annual rate of return of $4 for each dollar invested.
• The client wants to minimize risk subject to the requirement that the annual income from the
investment be at least $60,000. According to Innis’s risk measurement system, each unit
invested in the stock fund has a risk index of 8, and each unit invested in the money market
fund has a risk index of 3; the higher risk index associated with the stock fund simply indicates
that it is the riskier investment. Innis’s client also specified that at least $3,000 be invested in
the money market fund.
• Determine how many units of each fund Innis should purchase for the client to minimize the total risk
index for the portfolio.
• How much annual income will this investment strategy generate?
• Suppose the client desires to maximize annual return. How should the funds be invested?
• What is the optimal solution, and what is the minimum total risk?
 Cont.
• Investment
• A client approached a stockbroker in an economy where stocks are sold in a
stock market. The client has the following request to the broker: Invest
$100,000 for maximum annual income under the following conditions:
• Spread the investment over no more than three different stocks.
• put no more than 40% of the investment in to any stock.
• put a minimum of $10,000 in to oil stock.
Stock Price per share Estimated annual return per share
Oil $120 $11
Auto 52 4
Health 18 2

Formulate an LP model of the problem.

 Cont.
• Marketing Application
• Supermarket store chain has hired an advertising firm to determine the types and amount of advertising it
should have for its stores. The three types of advertising available are radio, television commercials, and
news papers advertisements. The retail chain desires to know the number of each type of advertisement it
should purchase in order to maximize exposure. It is estimated that each ad or commercial will reach the
following potential audience and cost the following amount.
Exposure
Type of Advertisement (people /ad or commercial) Cost
Television commercial 20,000 Birr 15,000
Radio commercial 12,000 6,000
News paper advertisement 9,000 4,000
1. The company must consider the following resource constraints.
2. The budget limit for advertising is Birr 100,000
3. The television station has time available for 4 commercials.
4. The radio station has time available for 10 commercials.``
5. The news paper has space available for 7 ads.
6. The advertising agency has time and staff available for producing no more than a total of 15 commercials
and/or ads.
 Cont.
• Marketing problem
• The manager of a department store in Addis Ababa is attempting to
decide on the types and amounts of advertising the store should use.
He has invited representatives from the local radio station, television
station, and newspaper to make presentations in which they describe
their audiences.
•  a. The television station representative indicates that a TV commercial,
which costs Birr 15,000, would reach 25,000 potential customers. The
break down of the audience is as follows.
Male Female
Old 5,000 5,000
Young 5,000 10,000
 Cont.
• b. The news paper representative claims to be able to provide an
audience of 10,000 potential customers at a cost of Birr 4000 per ad.
The break down of the audience is as follows.
Male Female
Old 4,000 3,000
Young 2,000 1,000

 c. The radio station representative says that the audience for one of the station’s
commercials, which costs Birr 6000, is 15,000 customers. The break down of the
audience is as follows.
Male Female
Old 1,500 1,500
Young 4,500 7,500
 Cont.
• Marketing Application
• The store has the following advertising policy:
• Use at least twice as many radio commercials as news paper ads.
• Reach at least 100,000 customers
• Reach at least twice as many young people as old people
• Make sure that at least 30% of the audience is women.
•  Available space limits the number newspaper ads to 7. The store wants
to know the optimal number of each type of advertising to purchase to
minimize total cost.
• Required:
• Formulate appropriate linear programming model.
SPECIAL CASES IN GRAPHICS METHODS

The special cases in LP model includes:

• redundant constraint
• multiple/alternative feasible solution
• unbound feasible solution
• Mixed constraints
 1. Redundant Constraint
• Is a constraint plotted on a graph doesn’t form part of the boundary
making the feasible region of the LP problem
• is said to be redundant because it is out of work.
• is that can be eliminated from a linear constraint system without altering
or affecting the feasible area. That is if removed from the system
constraint the FR/FS still remains same
• as a result, they can be removed from a linear programming model
without affecting the optimal solution
Example:
• Let’s use our previous example on two TV sets
• Rembert the model for TV sets is:

Max Z=300X1 +250X2

st: 2X1 +X2 < 40  Labor hr.
X1 + 3X2 < 45  Machine hr.
X1 + < 12  Marketing hr.
X1, X2 > 0
 Cont.
The resulting graph is as follow

•X
.2 2x1 +x2 ≤ 40-Labor hrs.

(0, 40) x1 ≤ 12-Marketing

x1 +3x2 ≤ 45-Machine hr.

B (0,15)
C (12, 11)
Feasible
Region
X1
A D(12, 0) 20 45
 Cont.
• Looking at the graph the, labour hrs constraint: 2x1 +x2 ≤ 40, does not form part of
FR.Therefor, in this case, the labour hour constraint is redundant and not
binding
• Reddendum constraint is necessarily not binding for it never limit the FR
• Redundant constraint in maximization problem always have slack/idle resource,
i.e. has slack more than zero value.
• Constraints that form feasible region at feasible points are called binding
constraints. Because they limit the capacity of resources
• The binding constraints always have no slack resources. That is they have zero
slacks.
• Note that it is not necessarily to mean that any constraint forming feasible region
is binding. The constraint that forming FR is binding only if the optimal value
and optimal solution lies on such lines (constraints).
• For example see the case of Par, Inc. producing two bags- deluxe and standard
 Slack
• for each constraint is determined using optimal solution; x1= 12, & x2 = 11.

Constraints Amount of Hrs used Available hrs Slack hrs = (Av – used)
Labour hrs 2 (12) + 11= 35 40 5
Marketing 12 = 12 12 0
Machine hr. 12 +3 (11) = 45 45 0

 Note the constraint that includes the feasible solution always have zero slack
Par. Inc.- Deluxe (D) and Standard (S) bags
• From the graph, we can see that:
 the cutting and dyeing and the finishing constraints restrict, or bind, the feasible
region at these optimal points. These constraints are called binding constraints.
 Thus, this solution requires the use of all available time for these two operations. In other
words, the graph shows us that the cutting and dyeing and the finishing departments will
have zero slack.
 On the other hand, the sewing and the inspection and packaging constraints are not
binding the feasible region at the optimal solution, which means we can expect
some unused time or slack for these two operations.
 These constraints are called non-binding constraints.
 In addition the sewing capacity constraint in particular, did not affect the feasible
region.
 That is, the feasible region would be the same whether the sewing capacity
constraint were included or not.
 The sewing constraint does not affect the feasible region and thus cannot
affect the optimal solution; it is called a redundant constraint.
 Slack
The amount of Slack variable of hrs at S = 540, and D = 252 for each
constraints:

Constraints Amount of Hrs used Available hrs Slack hrs

C & D hrs 7⁄10 *(540) + 1*(252) 630 0
Sewing hrs 1⁄2*(540)+5/6*(252) =480 600 120
Finishing hrs 540 + 2⁄3*(252) = 708 708 0
I & P hrs 1⁄10*(540)+1⁄4*(252) =117 135 18
 2. Multiple/Alternative/optimal solutions
• This is a situation where by a LP has more than one optimal solution.
• will be found if two corners give optimal solution,
• the line segment joining these points on the graph will be the solutions.
• In this situation we have unlimited number of optimal solution without
increasing or decreasing the objective function.
 Example:
The information given below is for the products A and B.
Department Products Available Machine hrs per week
  A B  
Cutting 3 6 900
Assembly 1 1 200
Profit per unit $8 $16  
The LPP Model of the problem is:
Max. Z = 8x1 + 16x2 st:
3x1 + 6x2 ≤ 900
X1 + x2 ≤ 200
+ x2 ≤ 125
X1, x2 ≥ 0
The graph & optimal value and optimal solutions

Interpretation: Both C and D are optimal solutions.

Any point on the line segment CD will also lead to
the same optimal solution.
==>Multiple optimal solutions provide more choices
for management to reach their objectives.
 3. Infeasible Solution
• A solution is called feasible if it satisfies all the constraints and non-negativity
condition.
• the constraints are inconsistent; that is, there is no common feasible solution
to the problem that satisfies all constraints simultaneously .
• That is all constraints fail to have common points in common.
• Such a situation is called infeasibility.

Example: Max. Z=20X1+30X St:

2x1+x2< 40---- (0, 40) and (20, 0)
4x1+x2< 60----- (0, 60) and (15,0)
x1 > 30----- (30,0)(30, 1), etc.…
x 1, x 2 > 0
Cont.– the graph

 Note:
• In the above graph, there is no
common point in the shaded area.
• therefore, all constraints cannot be
satisfied simultaneously and there is
no feasible solution to the problem.
 4. Unbounded Solution
• Is the situation/case when the value of decision variables in LP is permitted to
increase infinitely without violating the feasibility condition
• The polygon indicating feasible region is not closed one i.e., the feasible area is
unbound.
• Hence the line can be moved indefinitely, still containing a part of the feasible
area.
• there is no finite maximum value of Z. That the value of Z can be increased
indefinitely.
• Unbounded solution and objective function happens in case of maximization
model only.
• In minimization case there is unbounded feasible region but the optimal value
can be definitely determined at minimum point.
 Example- Unbounded Solution
Max. Z = 3x1+2x2 St:

x1-x2 ≤ 1
x1+x2 ≥ 3
x1, x2 > 0
 two corners of the region are A (0, 3) and B (2, 1).
 The value of Max Z (A) = 3(0) + 2x 3 = 6 and Max Z
(B) = 3x2 + 2x1) = 8.
 And 8 is the optimal value in ideal case.
 But there exist a number of points in the shaded
region for which the value of the objective function is (1, 0)
more than 8.
 For example, the point (10, 12) lies in the region and (0, -1)
the function value at this point is 70 which are more
than 8.
 Mixed Constraints
• The constraints for linear program model are all same types, then such lp
models are not mixed constraints problems.
• But if linear programming problems contains constraints that involve two or
three types ( ≤, ≥ and/or =) are called mixed-constraint problems.
• Mixed constraint problem can exist for both maximization and minimization
case.
 Mixed Constraint Problem-Maximization case
• ABC gasoline company has two refineries with different production capacities. refinery a
can produce 4,000 gallons per day of super unleaded gasoline, 2000 gallons per day of
regular unleaded gasoline and 1000 gallons per day of leaded gasoline. on the other hand,
refinery b can produce 1000 gallons per day of super unleaded, 3000 gallons per day of
regular unleaded and 4,000 gallons per day of leaded.
• The company has made a contract with an automobile manufacturer to provide 24000
gasolines of super unleaded, 42000 gallons of regular unleaded and 36000 gallons of
leaded .the automobile manufacturer wants delivery in not more than 14 days.  the cost of
running refinery a is $1500 per day and refinery b is $2400 per day.
•  required:
a) Formulate this problem as a LPP
b) Determine the number of days the gasoline company should operate each refinery in order
to meet the terms of the above contract most economical.(i.e. At a minimum running cost)
c) Which grade of gasoline would be over produced?
 Solution: a) Model

Let X1 =The No of days refinery A should work & =>T o simplify the problem divide by 1000 the
X2 =The No of days refinery B should work. constraints
a. LPP of the problem  Min Z =1500x1+2400x2 St:
Min Z=1500x1 +2400x2 St:
4X1+1x2 > 24
4000x1+1000x2 > 24000
2X1+3x2 > 42
2000x1+3000x2 > 42000
X1+4x2 > 36
1000x1+2000x2> 36000 x1 < 14
x1 < 14 x2< 14
  x2 < 14 x1, X2 > 0
b). the number of days the gasoline company should operate each refinery in order to meet
the terms of the above contract most economical:

. 24
Delivery time: X1=14
SUG: 4X1+X2 =24
 
 
A (2.5, 14) B (14, 14)
Delivery time: X2=14
FR  
 

D (12, 6) C (14, 5.5)

LG: X1+4X2=36
 
RUG: 2X1+3X2 =42
(6, 0) (14, 0) (21, 0) (36, 0)
 Cont.
Note: Point A, B, C, and D are solved by elimination-substitution method
________________________________________________________________
. Corners Coordinates Max Z = 1500x1 + 2400x2
A (2.5, 4) $37350
B (14, 14) 54600
C (14, 5.5) 34200
D (12, 6) 32400
E (3, 12) 33300
_______________________________________________________________

Interpretation: The oil company should operate refinery A for 12 days

and refinery B for 6 days at a minimum operating cost of $32,400.
 C) Which grade of gasoline would be over produced?
• SUG: 4000X1+1000X2> 24000
4000(12) +1000(6)> 24000
54000 > 24000
• Therefore, 30,000 gallons over production
• RUG: 2000X1+3000X2>42000
2000(12) +3000(6)>42000
42000 > 42000
• Therefore, there is no over production of RUG
•  LG: 1000X1+4000X2>36000
1000(12) +1000(6)>36000
36000 > 36000
• Therefore, No over production of LG
Minimization case. Example 2 - Ozark Farms Daily
feed mix
• Ozark Farms uses at least 800 lb of special feed daily. The special feed is a
mixture of corn and soybean meal with the following compositions:

• The dietary requirements of the special feed are at least 30% protein and
at most 5% fibre. Ozark Farms wishes to determine the daily minimum-
cost feed mix.
 Mini. Cont.
DV: Because the feed mix consists of corn and soybean meal, the decision variables of
the model are defined as
x1 = lb of corn in the daily mix
x2   = lb of soybean meal in the daily mix
OF: The objective function seeks to minimize the total daily cost (in dollars) of the
feed mix and is thus expressed as Minimize z = 0.3x1 + 0.9x2
Constraints: The constraints of the model reflect the:
daily amount of feed needed and
the dietary requirements.
 Mini. Cont.
• Because Ozark Farms needs at least 800Ib of feed a day, the associated
constraint (daily feed) can be expressed as x1+ x2 ≥ 800- total feed mix
needed per day
• As for the protein dietary requirement constraint, the amount of protein
included in x1 lb of corn and x2 lb of soybean meal is 0.09x1lb + 0.6x2 lb.
• This quantity should equal at least 30% of the total feed mix of protein (x1 +
x2) lb-that is, 0.09x1 + 0.6x2 ≥ 0.3 (x1+x2)
• In a similar manner, the fibre requirement of at most 5% of total feed mix
of fibr is constructed as .02x1 + 0.06x2 ≤ 0.05 (x1+x2).
Mini. Cont.
• The l.p.p. model
• Minimize z= .3x1 + .9x2
• Subject to x1 + x2 ≥ 800
.21x1 –.30x2 ≤ 0
.03x1 - .0lx2 ≥ 0
x 1, x 2 ≥ 0
 Mini. Cont.
• Because the present model seeks the minimization of the objective
function, we need to reduce the value of z as much as possible in the
direction shown in Figure below.
• The optimum solution is the intersection of the two lines x1 + x2 = 800
and .21x1 - .3X2 = 0, which yields X1 = 470.591b and X2 = 329.41 lb.
• The associated minimum cost of the feed mix is z = .3 X 470.59 + .9 x
329.42 = $437.65 per day.
 Mixed constraint- Maximization case
• Calculate the maximal value of z = 5x + 3y for the following constraints.
x + 2y ≤ 14
3x – y ≥ 0
x – y ≤ 2
x, y ≥ 0
First: find interception points
x + 2y ≤ 14  (0, 7), ( 14, 0)
3x – y ≥ 0  (0, 0), ( 1, 0), (2, 0), (3,0)
x – y ≤ 2  (0, -2), ( 2, 0), (3, 1)
x, y ≥ 0
Cont.

B(6, 2)

C(6, 4)

0 )
2 ,
A(0, 0) D(
 Cont.

• Now pair the lines to form a system of linear equations to find the
corner points.
3x – y = 0 <--------- multiply by 2
x + 2y = 14
x + 2y = 14
X–y=2
3y = 12 6x -2y = 0
y = 4 x + 2y = 14
X -4 = 2 7x = 14
X = 6 X=2
C( 2, 6)  3(2) -y = 0
 Y= 6
 B( 2, 6)
Cont.
Coordinates Max Z = 5x + 3y
A(0,0) 5*0 + 3*0 = 0
B(6,2) 5*6 + 3*2 = 36
C (6, 4) 5*6 + 3*4 = 42
D( 2, 0) 5*2 + 3*0 = 10

Hence, the maximum of Max z = 42, lies at (6, 4)

 The End
I Thank I YOU