THE SPECIAL PURPOSE ALGORITHMS OF

LINEAR PROGRAMMING

By:
ENGR. MARIZEN B. CONTRERAS
 THE TRANSPORTATION METHOD:
MINIMIZATION PROCESS
• Transportation problems are concerned with
selecting routes from the source of supply to
the distribution outlets.
• The objective is either to minimize cost of
transportation or maximize the contribution
to profit.
• Repetitive procedures are used in going from
one table to another, to come up with an
optimum solution.
• In the minimization process, the table is said
to be optimum id the improvement
computations are all positive ; while in
maximization process, the table is said to be
optimum if the improvements are all negative.
• There are two methods of solving a
transportation problem: the Stepping Stone
Method and the Modified Distribution or
MODI method.
• A transportation problem may be balanced or
unbalanced. A balanced transportation has
equal number of units of demand and supply
units.
 The Stepping Stone Method
• The stepping stone method makes used of an
unused or vacant cell as a point of destination
to evaluate if the solution can still be
improved. The general process is to look for
available three occupied cells, rectangular in
position to the point of destination. The
movement is vertical and horizontal.
 Transportation Method: Demand
Equals Supply
• The RSV Gravel Supply Company received a contract to
supply gravel to three new road projects located at three
different location. Project A needs 174 truckloads,
project B, 204 truckloads and Project C,143. The
company has three gravel warehouses located in three
different places. Warehouse 1 has 158 truckloads
available, warehouse 2 has 184 and warehouse 3 has
179.The cost of transportation from the warehouse to
the projects are: from warehouse 1 to projects A, B,C; ₱4,
₱8 and ₱8 per truckload, respectively. From warehouse
2: ₱16, ₱24 and ₱16 and from warehouse 3: ₱8, ₱16and
₱24, respectively. The objective is to design a pan of
distribution that will minimize the cost of transportation.
Transportation Table:

Supply

158
Warehouses 1
4 8 8
184
2

16 24 16
179
3

8 16 24
Demand

521
174 204 143
521
 Exercise
• The Aban Construction supply won a bidding to
supply cements to three horizontal (road)
Projects 1,2, and 3 require 100 bags, 170 bags,
and 180 bags respectively; it has three
warehouses A, B, and C. The available bags per
warehouse are as follows 120 bags for A, 180
bags for B, and 150 bags for C. It will cost P5/bag
to transport cement from warehouse A to Project
1, P2/bag to project 2; P4 to project 3; warehouse
B costs P3, P5, and P4 respectively for Projects
1,2, and 3; P4, P3, P2 for warehouse C.
 THE MODI (MODIFIED DISTRIBUTION)
METHOD OF TRANSPORTATION PROBLEM
• In this method, we have to add a new row
above the table for cost factors and a new
column to the left of the table.
• We make use of Vi for cost factors of supply, and
Wj for cost factors of demand. The key to the
use of MODI is to utilize the occupied cells for
each Vi and Wj values and then use these values
to calculate the net contributions of the vacant
cells.
 Summary of MODI Method
• Add the cost factors to get the cost of the
occupied cells, by assuming one value and
solving for the rest.
• Subtract the outside cost factors from the
indicated cost of the vacant cells. The most
negative result indicates the point of
destination for transfer.
THE UNBALANCED TRANSPORTATION
PROBLEM
• In actual practice, it seldom happens that the
quantity demanded is just equal to the quantity
supplied. Under normal situation transportation
problems come as unbalanced problems. But
since we can only handle a balanced table, we
must find a way of converting an unbalanced
table to a balanced one. This can be done by
the use of a dummy. A dummy is something we
pretend to exists, although in reality it does not.
We must remember the following:
• If the demand is greater, use a dummy supply
• If the supply is greater, use a dummy demand
 Supply is Greater than Demand
A B C Supply
1 4 8 8 76
2 16 24 16 82
3 8 16 24 77
Demand 72 102 41 215/235

A B C Dummy Supply

1 4 8 8 0 76
2 16 24 16 0 82
3 8 16 24 0 77
Dema 72 102 41 20 235/235
nd
 Demand is Greater than Supply
A B C Supply
1 4 8 8 56
2 16 24 16 82
3 8 16 24 77
Demand 80 102 41 223/215

A B C Supply
1 4 8 8 56
2 16 24 16 82
3 8 16 24 77
Dummy 0 0 0 8
Demand 80 102 41 223/223
LINEAR PROGRAMMING:
ASSIGNMENT METHOD
 Assignment Method
• The problem is concerned with allocating the
jobs to each of the workers for minimum cost.
There are three main steps to follow in
solving an assignment problem.
• Subtract the smallest cost from each country
in each row. If each zero can now be assigned
one-to-one correspondence with the
“workers” , an optimal solution is reached. If it
cannot, go on step 2.
• Subtract the smallest cost in each column. If
the zero entries can now be distributed one-
to-one correspondence with the “workers”, an
optimal solution is reached. If it cannot, go on
step 3
• Cover the zero entries by vertical or horizontal
lines, using the least number of lines possible.
This can be done by covering first the row or
the column having the most zeros). Subtract
the smallest uncovered cost but add it to the
entry found at the intersection of the lines. If
an assignment is already possible, an optimal
solution is reached. If not, repeat step 3.
• An assignment is optimum if the number of
lines used is equal to the number of rows or
the number of columns.
• Four engineers are to work on 4 projects of
PSV Construction Company. The problem is to
decide which engineer should be assigned to
which project. Each engineer charges different
fees on each project, due to distances of the
projects and the complexity of the work. The
cost of assigning particular engineers to
particular projects are as follows:
• The objective is to find the least cost of the
assignment.

Engineer/ A B C D
Project
1 11,000 8,000 10,000 7,000
2 6,000 5,000 3,000 8,000
3 4,000 8,000 10,000 9,000
4 11,000 10,000 5,000 7,000
 Exercise
• Engineer Morasa has to assign 4 teams to
work on 4 projects. The costs charged by each
team are as follows. Costs are in thousands of
pesos. Determine the least cost of assignment
1 2 3 4
A 15 18 20 16
B 18 17 14 20
C 21 20 13 15
D 17 15 18 19
BREAK-EVEN POINT ANALYSIS
 Break-Even Point (BEP)
• The common point between the total revenue
and the total cost is called break even point. At
this point the total revenue equals to the total
cost. The company has no profit but has no
loss.
 Total Revenue, Total Cost and Profit
Functions
• The total revenue(TR) is obtained by finding the
product of the selling price per unit by the number of
units sold. Total cost (TC) is obtained by finding the
sum of the fixed cost (FC) and variable cost (VC).
Fixed cost is constant while the variable cost
represents the cost of production per unit.
• The following formulas should be remembered:
– TR=selling price per unit times the number of units sold.
– TC=FC+VC, ( where VC=cost per unit times the number of
units)
– Profit=TR-TC
– At break even points, TR=TC or TR-TC=0 or Profit=0
 Break-Even Analysis: Linear Function
A firm sells its product at P6 per unit. The product has a variable
cost of P3 per unit and the Company’s fixed cost is P9,000.
Determine each of the following:
1. TR, TC and profit functions
2. Sales volume when profit is P9,000
3. Profit when sales are 600 units
4. The break-even quantity and revenue
5. The amount by which the variable cost per unit has to be
decreased or increased for the firm to break evem at 2,000
units. Assume that the selling price is fixed cost remain
constant.
6. The new selling price per unit in order to break even at 300
units, assuming the FC and VC remain constant.
7. Number of units to sell to cover the fixed cost.
• A manufacturer sells his product at P10 per unit
– Find the total revenue if the volume of sales is 1800
– If fixed cost is P3000, represent the total cost when
the variable cost per unit is P5
– Suppose that the variable cost per unit is 70% of the
selling price. Represent the total cost when fixed
cost is P5000
– If the variable cost is 20% of the selling price and the
fixed cost is P1000, find the break even point.
 Break-Even Analysis: Non- Linear
Functions
• To increase or maximize the profit, it is a
common belief that an increase in production
would increase the profit. This is however not
true in general, for as the market becomes
saturated with the product5, we cannot expect
to continue selling it as its original price. The
price should be decreased therefore and the
decrease sometimes depends on the number of
units to purchase by the customer.
A product sells at P12 per unit. Fixed cost is P40 and
the variable cost per unit is P7. After observing that
the sale of the product has begun to decline, its per
unit selling price is decreased by 10% of units sold.
Variable cost and fixed cost remain unchanged.
• Represent the new selling price per unit.
• Write the TR, TC and profit functions.
• Find the break-even point quantity and revenue.
• Find the profit at a sale of 50 units
 Finding the Critical Points of Non-
Linear Functions
There are two critical points:
• Maxima or maximum point
• Minima or minimum point
Steps in Locating the Critical Points
Locate and classify of Y=-4x^2+40x-10

Solution:
• Y’ = -8x +40
• -8x + 40 = 0
• -8x = -40
• x=5
Substituting x = 5 in the original equation
• Y = -4(5)2 + 40(5) -10
• Y = 90 Critical point is (5, 90)

Testing whether the point is maxima or minima:

• Y’ = -8x+4
• Y” = -8

Since Y” is negative, therefore the critical point (5,

90) is a maximum point.
Application of Maxima and Minima in
Business
 Solution:
• P = -.1x2 + 5x -40
• P = -0.2x + 5
• -0.2x + 5 = 0
• -0.2x = -5
• x = 25 number of units for maximum profit
To find the maximum profit, substitute 25 in x and
find P.
• P = -.1(25)2 + 5(25) -40
• P = 22.50 Maximum profit
• The selling price of a particular article is P200
per unit. It has been decided to reduce the
price per unit by 1% of the volume of sale.
Variable cost per unit is P150, and the fixed
cost is P10000.
– Write the TR, TC and Profit functions
– Find the BEP qty
– Find the units to cover the fixed cost
– Find the maximum profit
 PROJECT MANAGEMENT
• Projects that take months or years to
complete are usually developed outside the
normal production system. Project
organizations within the firm may be set up to
handle such jobs and are often disbanded
when the project is complete. On other
occasions, managers find projects just a part
of their job.
 The management of projects involves
three phases:
Planning
• This phase includes goal setting, defining the project, and
team organization.
Scheduling
• This phase relates to people, money, and supplies to
specific activities and relates activities to each other.
Controlling
• Here the firm monitors, resources, costs, quality, and
budgets. It also revises or changes plans and shifts
resources to meet time and cost demands
 PROJECT ORGANIZATION
• An organization formed to ensure that
programs (projects) receive the proper
management and attention.
 The project organization works best
when:
• Work can be defined with a specific goal and
deadline.
• The job is unique or somewhat unfamiliar to the
existing organization
• The work contains complex interrelated tasks
requiring specialized skills
• The project is temporary but critical to the
organization
• The project cuts across organizational lines.
 WORK BREAKDOWN STRUCTURE
(WBS)
• The work breakdown structure defines the
project by dividing it into its major
subcomponents (or tasks), which are then
subdivided into more detailed components,
and finally into a set of activities (or work
packages) and their costs.
The work breakdown structure typically decreases in
size from top to bottom and is indented like this:

Level
• Project
• Major tasks in the project
• Subtasks in major tasks
• Activities (or work packages) to be completed
 PROJECT SCHEDULING
• Project scheduling involves sequencing and
allotting time to all project activities. One
popular project scheduling approach is the
Gantt chart.
Gantt charts are low-cost means of helping
managers make sure that:
• All activities are planned for
• Their order of performance is accounted for
• The activity time estimates are recorded
• The overall project time is developed.
 Project scheduling serves several
purposes:
• It shows the relationship of each activity to
others and to the whole project
• It identifies the precedence relationships among
activities.
• It encourages the setting of realistic time and
cost estimates for each activity
• It helps make better use of people, money, and
material resources by identifying critical
bottlenecks in the project.
 PROJECT MANAGEMENT
TECHNIQUES: PERT AND CPM
• Program evaluation and review technique (PERT)
and the critical path method (CPM) were both
developed in the 1950s to help managers
schedule, monitor, and control large and complex
projects.
• Program evaluation and review technique (PERT)
is a project management technique that employs
three time estimates for each activity.
• Critical Path Method (CPM) is a project
management technique that uses only one time
factor per activity.
THE FRAMEWORK OF PERT AND CPM
PERT and CPM both follow six basic steps:
• Define the project and prepare the work breakdown
structure
• Develop the relationships among the activities. Decide
which activities must precede and which must follow
others
• Draw the network connecting all the activities
• Assign time and/or cost estimates to each activity.
• Compute the longest time path through the network.
This is called the critical path.
• Use the network to help plan, schedule, monitor and
control the project.
 Basic Terms in PERT CPM
• Critical Path: The longest time path through the
task network. The series of tasks (or even a single
task) that dictates the calculated finish date of
the project (That is, when the last task in the
critical path is completed, the project is
completed) The "longest" path (in terms of time)
to the completion of a project. If shortened, it
would shorten the time it takes to complete the
project. Activities off the critical path would not
affect completion time even if they were done
more quickly.
• Slack Time: The amount of time a task can be delayed
before the project finish date is delayed. Total slack can
be positive or negative. If total slack is a positive it
indicates the amount of time that the task can be
delayed without delaying the project finish date. If
negative, it indicates the amount of time that must be
saved so that the project finish date is not delayed. Total
Slack = Latest Start - Earliest Start. By default and by
definition, a task with 0 slack is considered a critical task.
If a critical task is delayed, the project finish date is also
delayed. (Also known as float time)
• All activities on the critical path have zero slack
• Earliest Start (ES) = the earliest finish of the
immediately preceding activity
• Earliest Finish (EF) = is the ES plus the activity
time
• Latest Start (LS) and Latest Finish (LF) = the
latest an activity can start (LS) or finish (LF)
without delaying the project completion
• Crashing: Shifting resources to reduce slack time so
the critical path is as short as possible. Always raises
project costs and is typically disruptive – a project
should be crashed with caution.
• Network Diagram: A wire diagram, Also known as a
PERT network diagram. A diagram that shows tasks
and their relationships. Limited because it shows
only task relationships. Strength: easy to read task
relationships.
• Activity-on-Node (AON): It uses nodes to represent
the activity and arrows to represent precedence
relationships
 PERT CALCULATIONS
• Define tasks
• Place Tasks in a logical order, find the critical
path. The longest time path through the task
network. The series of tasks (or even a single
task) that dictates the calculated finish date
• Generate estimates: Optimistic, pessimistic, likely
and PERT- expected, Standard Deviation and
variance are included
• Determine earliest and latest dates
• Determine probability of meeting expected date
• Steps 1 and 2 are logic and legwork, not
calculation – these require a clear goal.
Assuming steps 1 and 2 have been completed
begin calculations – use a table to organize your
calculations. Simple calculations are used to
estimate project durations.
• Based on input of 3 estimated durations per
task
• Most Optimistic (a) – best case scenario
• Cables By Us is bringing a new product on line
to be manufactured in their current facility in
existing space. The owners have identified 11
activities and their precedence relationships.
Develop an AON for the project.
ACTIVI DESCRIPTION IMMEDIATE DURATION
TY PREDECESSOR (weeks)
A Develop product specifications None 4
B Design manufacturing process A 6
C Source and purchase materials A 3
D Source and purchase tooling and B 6
equipment
E Receive and install tooling and D 14
equipment
F Receive materials C 5
G Pilot production run E,F 2
H Evaluate production design G 2
I Evaluate process performance G 3
J Write documentation report H,I 4
K Transition to manufacturing J 2
 Revisiting Cables By Us Using Probabilistic Time Estimates
ACTI DESCRIPTION OPTIMIS MOST PESSIMIS t variance
VITY TIC TIME LIKELY TIC TIME
TIME
A Develop product 2 4 6
specifications
B Design manufacturing 3 7 10
process
C Source and purchase 2 3 5
materials
D Source and purchase tooling 4 7 9
and equipment
E Receive and install tooling 12 16 20
and equipment
F Receive materials 2 5 8
G Pilot production run 2 2 2
H Evaluate product design 2 3 4
I Evaluate process 2 3 5
performance
J Write documentation 2 4 6
K Transition to manufacturing 2 2 2
 Reducing Project Completion Time
• Project completion times may need to be
shortened because:
– Different deadlines
– Penalty clauses
– Need to put resources on a new project
– Promised completion dates
• Reduced project completion time is “crashing”
• Crashing a project needs to balance
– Shorten a project duration
– Cost to shorten the project duration
• Crashing a project requires you to know
– Crash time of each activity
– Crash cost of each activity
• Crash cost/duration = (crash cost-normal
cost)/(normal time – crash time)
 Reducing the Time of a Project
(crashing)
Activity Normal Normal Crash Crash Max. Reduce
Time Cost ($) Time Cost ($) weeks of cost per
(wk) reduction week
A 4 8,000 3 11,000 1 3,000
B 6 30,000 5 35,000 1 5,000
C 3 6,000 3 6,000 0 0
D 6 24,000 4 28,000 2 2,000
E 14 60,000 12 72,000 2 6,000
F 5 5,000 4 6,500 1 1500
G 2 6,000 2 6,000 0 0
H 2 4,000 2 4,000 0 0
I 3 4,000 2 5,000 1 1,000
J 4 4,000 2 6,400 2 1,200
K 2 5,000 2 5,000 0 0