INTRODUCTION TO LINEAR

PROGRAMMING

PRESENTED BY: ALLAN DELA CRUZ, MBA

BBMASCIX - ALLAN DELA CRUZ, MBA

LINEAR PROGRAMMING

A problem-solving approach developed to help managers make

decisions.

The problem of maximizing or minimizing a linear function that is

subjected to linear constraints.

a mathematical modeling technique that involves maximizing or

minimizing a linear function while taking into account various constraints.

BBMASCIX - ALLAN DELA CRUZ, MBA

Constraints

• Any limitation to which the objective can be pursued.

• The limitations should be expressed in the mathematical form,
regarding the resource.

BBMASCIX - ALLAN DELA CRUZ, MBA

Characteristics of Linear Programming

1. Constraints – The limitations should be expressed in the mathematical

form, regarding the resource.
2. Objective Function – In a problem, the objective function should be
specified in a quantitative way.
3. Linearity – The relationship between two or more variables in the function
must be linear. It means that the degree of the variable is one.
4. Finiteness – There should be finite and infinite input and output numbers.
In case, if the function has infinite factors, the optimal solution is not
feasible.
5. Non-negativity – The variable value should be positive or zero. It should not
be a negative value.
6. Decision Variables – The decision variable will decide the output. It gives
the ultimate solution of the problem. For any problem, the first step is to
identify the decision variables.

BBMASCIX - ALLAN DELA CRUZ, MBA

BBMASCIX - ALLAN DELA CRUZ, MBA

Example of a Linear
Programming
Problem (LPP)
• Let’s say a FedEx delivery man has 6
packages to deliver in a day. The
warehouse is located at point A. The 6
delivery destinations are given by U, V, W,
X, Y, and Z. The numbers on the lines
indicate the distance between the cities.
To save on fuel and time the delivery
person wants to take the shortest route.
To illustrate some of the properties that all linear programming
problems have in common, consider the following typical
applications:

1. A manufacturer wants to develop a production schedule and an inventory policy that will
satisfy sales demand in future periods. Ideally, the schedule and policy will enable the
company to satisfy demand and at the same time minimize the total production and inventory
costs.
2. A financial analyst must select an investment portfolio from a variety of stock and bond
investment alternatives. The analyst would like to establish the portfolio that maximizes the
return on investment.
3. A marketing manager wants to determine how best to allocate a fixed advertising budget
among alternative advertising media such as radio, television, newspaper, and magazine. The
manager would like to determine the media mix that maximizes advertising effectiveness.
4. A company has warehouses in a number of locations throughout the United States. For a set of
customer demands, the company would like to determine how much each warehouse should
ship to each customer so that total transportation costs are minimized.

BBMASCIX - ALLAN DELA CRUZ, MBA

Steps for solving linear programming
problems:

Determine the choice factors

Develop the objective function

Determine whether the function should be decreased or maximized

Record the limitations

Verify that decision variables are either larger than or equal to 0. (Non-negative inhibition)

Utilize either the simplex or graphical method to resolve the linear programming issue

BBMASCIX - ALLAN DELA CRUZ, MBA

 A SIMPLE MAXIMIZATION PROBLEM

• 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.
• After a thorough investigation of the steps involved in manufacturing a golf bag,
management determined that each golf bag produced will require the following
operations:
• 1. Cutting and dyeing the material
BBMASCIX - ALLAN DELA CRUZ,

• 2. Sewing
• 3. Finishing (inserting umbrella holder, club separators, etc.)
• 4. Inspection and packaging
MBA
 Continuation

• The director of manufacturing analyzed each of the operations and concluded

that if the company produces a medium-priced standard model, each bag will
require ⁷⁄₁₀ hour in the cutting and dyeing department, ¹⁄₂ hour in the sewing
department, 1 hour in the finishing department, and ¹⁄₁₀ hour in the inspection
and packaging department. The more expensive deluxe model will require 1
hour for cutting and dyeing, ⁵⁄₆ hour for sewing, ²⁄₃ hour for finishing, and ¹⁄₄ hour
for inspection and packaging.
• Par’s production is constrained by a limited number of hours available in each
BBMASCIX - ALLAN DELA CRUZ,

department. After studying departmental workload projections, 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.
MBA
 Continuation

• The accounting department analyzed 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.

• Develop a mathematical model of the Par, Inc., problem that can be

used to determine the number of standard bags and the number of
BBMASCIX - ALLAN DELA CRUZ,

deluxe bags to produce in order to maximize total profit contribution.

MBA
 Problem Formulation

• Understand the Problem Thoroughly

• 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.
BBMASCIX - ALLAN DELA CRUZ,
MBA
 • 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.
BBMASCIX - ALLAN DELA CRUZ,

• 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.
MBA
 • 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
D = number of deluxe bags
BBMASCIX - ALLAN DELA CRUZ,

• In linear programming terminology, S and D are referred to as the

decision variables.
MBA
Make a simple table

BBMASCIX - ALLAN DELA CRUZ, MBA

 • Write the Objective in Terms of the Decision Variables:
• Par’s profit contribution comes from two sources: (1) the profit contribution made
by producing S standard bags, and (2) the profit contribution made by producing D
deluxe bags.

Total Profit Contribution = 10S + 9D

• Because the objective—maximize total profit contribution—is a function of the

BBMASCIX - ALLAN DELA CRUZ,

decision variables S and D, we refer to 10S + 9D as the objective function. Using “Max”
as an abbreviation for maximize, we write Par’s objective as follows:
Max 10S + 9D
MBA
BBMASCIX - ALLAN DELA CRUZ, MBA

Write the Constraints in Terms Constraint 1:

of the Decision Variables:
BBMASCIX - ALLAN DELA CRUZ, MBA
BBMASCIX - ALLAN DELA CRUZ, MBA

Mathematical Statement of the

Par, Inc., Problem
BBMASCIX - ALLAN DELA CRUZ, MBA
BBMASCIX - ALLAN DELA CRUZ, MBA
 Another Illustration

• A farmer has recently acquired a 110 hectares piece of land. He has

decided to grow Wheat and barley on that land. Due to the quality of the
sun and the region’s excellent climate, the entire production of Wheat
and Barley can be sold. He wants to know how to plant each variety in
the 110 hectares, given the costs, net profits and labor requirements
according to the data shown below:
BBMASCIX - ALLAN DELA CRUZ,
MBA
BBMASCIX - ALLAN DELA CRUZ, MBA
 Formulation of a Linear Problem

Step 1: Identify the decision variables

• The total area for growing Wheat = X (in hectares)

• The total area for growing Barley = Y (in hectares)

• X and Y are my decision variables.

BBMASCIX - ALLAN DELA CRUZ,
MBA
 • Step 2: Write the objective function
• Since the production from the entire land can be sold in the market. The
farmer would want to maximize the profit for his total produce. We are
given net profit for both Wheat and Barley. The farmer earns a net profit
of US$50 for each hectare of Wheat and US$120 for each Barley.
• Our objective function (given by Z) is, Max Z = 50X + 120Y
BBMASCIX - ALLAN DELA CRUZ,
MBA
 • Step 3: Writing the constraints
• 1. It is given that the farmer has a total budget of US$10,000. The cost of
producing Wheat and Barley per hectare is also given to us. We have an
upper cap on the total cost spent by the farmer. So our equation
becomes:
• 100X + 200Y ≤ 10,000
BBMASCIX - ALLAN DELA CRUZ,
MBA
 • 2. The next constraint is the upper cap on the availability of the total number of
man-days for the planning horizon. The total number of man-days available is
1200. As per the table, we are given the man-days per hectare for Wheat and
Barley.

10X + 30Y ≤ 1200

BBMASCIX - ALLAN DELA CRUZ,

• 3. The third constraint is the total area present for plantation. The total
available area is 110 hectares. So the equation becomes,
X + Y ≤ 110
MBA
 • Step 4: The non-negativity restriction
• The values of X and Y will be greater than or equal to 0. This goes without
saying.
X ≥ 0, Y ≥ 0
BBMASCIX - ALLAN DELA CRUZ,
MBA
 Solving an LP Through the Graphical Method

• Since we know that X, Y ≥ 0. We will consider only the first quadrant.

• To plot for the graph for the above equations, first I will simplify all the
equations.
• 100X + 200Y ≤ 10,000 can be simplified to X + 2Y ≤ 100 by dividing by
100.
• 10X + 30Y ≤ 1200 can be simplified to X + 3Y ≤ 120 by dividing by 10.
• The third equation is in its simplified form, X + Y ≤ 110.
BBMASCIX - ALLAN DELA CRUZ,
MBA
 • The optimal feasible solution is achieved at the point of intersection where the
budget & man-days constraints are active. This means the point at which the
equations X + 2Y ≤ 100 and X + 3Y ≤ 120 intersect gives us the optimal solution.
• The values for X and Y which gives the optimal solution is at (60,20).
• To maximize profit the farmer should produce Wheat and Barley in 60 hectares
and 20 hectares of land respectively.
• The maximum profit the company will gain is,
BBMASCIX - ALLAN DELA CRUZ,

• Max Z = 50 * (60) + 120 * (20)

• = US$5400
MBA
BBMASCIX - ALLAN DELA CRUZ, MBA
 • References: AN INTRODUCTION TO MANAGEMENT
SCIENCE:QUANTITATIVE APPROACHES TO DECISION
MAKING; David R. Anderson; Dennis J. Sweeney;
Thomas A. Williams; Jeffrey D. Camm; Kipp Martin

BBMASCIX - ALLAN DELA CRUZ, MBA