Rimberio Co
LINEAR
PROGRAMMING
Presentation Design
Linear Programming is a problem-solving approach developed to help
managers make decisions.
It is also called linear optimization, a method to achieve the best outcome
in a mathematical model whose requirements are represented by linear
relationships. Linear programming is a special case of mathematical
programming.
It is mathematical modeling technique in which a linear function is
maximized or minimized when subjected to various constraints. This
technique has been useful for guiding quantitative decisions in business
planning, in industrial engineering, and—to a lesser extent—in the social
and physical sciences.
Presentation Design
To illustrate some of the properties that all linear progrsmming problems
have in common, consider the following typical applications :
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.
A fancial analyst must select an investment portfolio from a variety of stocks
and bond investment alternatives. The analyst would like to establish the
portfolio that maximizes the return on investment.
A marketing managr wants to determine hw best to allocate a fixed advertising
budget among alternatives advertising media such as radio, television,
newspaper and magazine. The managr would like to determine the media mix
that maximizes advertising effectiveness.
In all linear programming problems, the maximization or minimization of
some quantity is the objective.
All linear programing problems also have a second property : restrictions
or constraints , that limit the degree to which the objective can be pursued.
Constraints are another general feature of every linear programming
problem.
A SIMPLEX MAXIMIZATION PROBLEM
Gardner Inc. is small manufacturer of golf equipment and supplies whose
management has decided to move into the market for medium an high priced
golf bags. Gardner Inc.'s distributor is enthusiastic about the new product line
and has agreed to buy all golf bags Gardner Inc., produces over the three
months.
Each golf bag produced will require the following operations:
1. Cutting and dyeing the materials
2. Sewing
3. Finishing ( inserting umbrella holder, club separators and etc)
4. Inspection and packaging
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:
Gardner Inc.'s production is constrained by a limited number of hours available in each
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 packing will be availble for the production of golf bags during the
next three months.
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.
PROBLEM FORMULATION
Problem formulation or modeling is the process of translating the verbal statemen t of a problem
into a mathematical statement. Formulating models is an art that can only be mastered with practice
and experience.
We will illustrate the general guidelines by developing a mathematical model for the Gardner Inc's
problem.
1. Understand the Problem Thoroughly . We select the Gardner Inc., problem to introduce linear
programming because it is easy to understand.
2. Describe the Objective . The objective is to maximize the total contribution to profit.
3. Describe Each Constraint . Four constraints relate to the number of hours of manufacturin g
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 use must be less than or equal to the
number of hours of cutting and dyeing time available.
PROBLEM FORMULATION
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.
4. Define the dec ision Variables. The controllable inputs for Gardner Inc, are (1) number of
standard bags produced and (2) the number of deluxe bags produced.
Let S= number of standard bags
D = number of deluxe bags
In linear programming terminology S and D are referred to as the Decision Variables.
PROBLEM FORMULATION
5.Write the Objective in Terms of the Decision Variables .Gardner Inc. profit contribution
comes from two sources : (1) the profit contribution made by producing S standard bags and
(2) the profit contribution made by D deluxe bags. If Gardner Inc., makes $10 for every
standard bag the company will make $10 S if S standard bags are produced. Also, if the
company makes $9 for every deluxe bag the company will make $9 D if D deluxe bag are
produced. Thus we have
Total Profit Contribution = 10S + 9D
Because the objective ---Maximaize the total profit contribution -- is a function of the
decision variables S and D, we refer to 10S +9D as the objective function .
Using "Max" as an abbreviation for maximize , we write Gardner Inc.'s objective as:
Max 10S +9D
6. Write the Constraints in Terms of the Decision Variables .
Constraint 1:
Every standard bag Gardner Inc. produces will use 7/10 hours cutting and dyeing time:
Therefore , the total of hours of cutting and dyeing time used in the manufacture of S standard bags
is 7/10 S.
Every deluxe bag produced uses 1 hour of cutting and dyeing time, thus the production of D deluxe
bag will use 1 D hours of cutting and dyeing time.
Total hours of cutting and dyeing time used = 7/10 S + 1D
The director manufacturing stated that Gardner Inc., has at most 630 hours of cutting and dyeing
time available. Therefore the production combination we select must satisfy the requirement
Constraint 2:
Every standard bag manufactured will require 1/2 hours for sewing and every deluxe bag
will require 5/6 hours for sewing. Because 600 hours of sewing time are available , it
follows that :
Constraint 3:
Every standard bag manufactured will require 1 hour for finishing and every deluxe bag
will require 2/3 hour for finishing. With 708 hours of finishing time available , it follows
that :
Constraint 4:
Every standard bag manufactured will require 1/10 hour for inspection and packaging
and every deluxe bag will require 1/4 hour for inspection and packaging.
Because 135 hours of inspection and packaging time are available , it follows that :
To prevent the decision variables S and D from having a negative values , two
constraints must be added.
These constraints ensure that the solution to the problem will contain
nonnegative values for the decision variables and are thus referred to as the
NONNEGATIVE CONSTRAINTS. Nonnegative constraints are a general feature
of all linear programmming problems and may be written in the abbreviated
from :
Mathematical Statement of the Gardner Inc., Problem
We succeeded in translating the objective and constraints of the problem into a set
of mathematical relationship referred to as a mathematical model. The complete
mathematical model for the Gardner Inc., problem is as follows:
Rimberio Co
Linear programming has nothin to do with computer programming. the
word "programming" here means " choosing a course of action" .
Linear programming involves choosing a course of action when the
mathematical model of the problem contains only linear function.
THANK YOU
