Strategic allocation of resources using linear programming model with parametric analysis: in MATLAB and Excel Solver
©2014
Textbook
74 Pages
Summary
Since the late 1940s, linear programming models have been used for many different purposes. Airline companies apply these models to optimize their use of planes and staff. NASA has been using them for years to optimize their use of limited resources. Oil companies use them to optimize their refinery operations. Small and medium-sized businesses use linear programming to solve a huge variety of problems, often involving resource allocation.<br>In my study, a typical product-mix problem in a manufacturing system producing two products (each product consists of two sub-assemblies) is solved for ist optimal solution through the use of the latest versions of MATLAB having the command simlp, which is very much like linprog. As analysts, we try to find a good enough solution for the decision maker to make a final decision. Our attempt is to give the mathematical description of the product-mix optimization problem and bring the problem into a form ready to call MATLAB’s simlp command. The objective of this study is to find the best product mix that maximizes profit. The graph obtained using MATLAB commands, give the shaded area enclosed by the constraints called the feasible region, which is the set of points satisfying all the constraints. To find the optimal solution we look at the lines of equal profit to find the corner of the feasible region which yield the highest profit. This corner can be found out at the farthest line of equal profit, which still touches the feasible region.<br>The most critical part is the sensitivity analysis, using Excel Solver, and Parametric Analysis, using computer software, which allows us to study the effect on optimal solution due to discrete and continuous change in parameters of the LP model including to identify bottlenecks. We have examined other options like product outsourcing, one-time cost, cross training of one operator, manufacturing of hypothetical third product on under-utilized machines and optimal sequencing of jobs on machines.
Excerpt
Table Of Contents
i
TABLE OF CONTENTS
ABSTRACT
ACKNOWLEDGEMENTS
TABLE OF CONTENTS
i
LIST OF FIGURES
iv
LIST OF TABLES
v
LIST OF ABBREVIATIONS
vi
CHAPTER 1
INTRODUCTION
1.1 HISTORY
1
1.2 PRINCIPLES OF MATHEMATICAL PROGRAMMING
1
1.3 LINEAR PROGRAMMING
2
1.3.1
Limitations of LP model
3
1.4 MOTIVATION
3
1.4.1
Examples of successful LP applications.
4
1.5 CHARACTERSTICS OF LINEAR PROGRAMMING
5
1.6 SOLVING LP PROBLEMS
7
1.7 BASIC STEPS FOR SOLVING A LP MODEL
7
1.7.1
Recognize the problem
8
1.7.2
Define the problem
9
1.7.3
Define the decision variables
9
1.7.4
Collect the necessary parametric data
9
1.7.5
Formulate a model
10
1.7.6
Solve the model
10
1.7.7
Verify and validate the model
10
1.7.8
Analyze model output
11
1.7.9
Interpret model results
11
1.7.10 Recommend a course of action
11
1.8 FORMULATING LP PROBLEMS
11
1.9 OBJECTIVES OF THE STUDY
12
1.10 ORGANISATION OF THE STUDY
12
1.11 SUMMARY
12
CHAPTER 2
LITERATURE REVIEW
2.1 INTRODUCTION
13
2.2 DECISION MAKING IN POM
13
2.3 THE SIMPLEX METHOD
15
2.4 THE COMMAND linprog
15
ii
2.5 USING EXCEL SOLVER OPTIMIZATION PROBLEM
16
2.5.1
Spreadsheet modeling & Excel Solver
17
2.6 PRODUCTION OUTSOURCING: A LP MODEL FOR THE TOC
17
2.7 GENERAL RESOURCE ALLOCATION MODEL
18
2.8 SUMMARY
19
CHAPTER 3
LINEAR PROGRAMMING MODEL
3.1 INTRODUCTION
20
3.2 THE PROBLEM STATEMENT
21
3.3 FORMULATION OF LP MODEL
23
3.4 SOLUTION USING MATLAB
24
3.5 THE COMMAND simlp
25
3.6 THE OPTIMAL SOLUTION USING MATLAB
27
3.7 SOLUTION USING EXCEL SOLVER
27
3.8 OPTIMAL SCHEDULING ON MACHINES
29
3.8.1
Assumptions in sequencing problem
29
3.8.2
Processing two jobs through four machines
29
3.9 SUMMARY
33
CHAPTER 4
INTERPRETING COMPUTER SOLUTIONS OF LP PROBLEM
4.1
INTRODUCTION
34
4.2 TERMS
34
4.2.1
Slack variables
36
4.2.2
Basic & non-basic variables
36
4.3 ANSWER REPORT ANALYSIS
37
4.4 SENSITIVITY ANALYSIS
38
4.4.1
Find the bottleneck
38
4.4.2
Find the range over which the unit profit may change
39
4.4.3
Find the marginal benefit of increasing the time availability
39
4.4.4
Find the range over which the time availability may change
41
4.5 PARAMETRIC ANALYSIS
41
4.5.1
Variation in resource availability (Right hand side value)
42
4.5.2
Variation in resource consumed (coefficient of constraint) per unit of
P product
43
4.5.3
Variation in resource consumed (coefficient of constraint) per unit of
Q product
45
4.6 SUMMARY
46
iii
CHAPTER 5
RESULT & DISCUSSIONS
5.1 INTRODUCTION
47
5.2 SEARCH FOR THE OPTIMAL SOLUTION
47
5.3 BOTTLENECKS
49
5.4 RANGE OVER WHICH THE UNIT PROFIT MAY CHANGE
49
5.5 MARGINAL BENEFIT OF INCREASING THE TIME AVAILABILITY
50
5.6 RANGE OVER WHICH THE TIME AVAILABILITY MAY CHANGE
51
5.7 REDUCED COST FOR NON-BASIC VARIABLES
52
5.8 SLACK VALUES FOR CONSTRAINTS
53
5.9 RECOMMENDED COURSE OF ACTION
53
5.9.1
Product Outsourcing
53
5.9.2
One-time cost
54
5.9.3
Cross Training of one machine operator
55
5.9.4
Possibility of third product manufacturing
55
5.9.5
Optimal sequencing to process jobs on machines
57
5.10
SUMMARY
57
CHAPTER 6
CONCLUSIONS
6.1 INTRODUCTION
58
6.2 SUMMARY OF THE PRESENT WORK
58
6.3 SUMMARY OF CONTRIBUTION
59
6.4 SCOPE FOR FUTURE WORK
59
6.5 CONCLUDING REMARKS
59
REFERENCES 60
iv
Figure 1.1 Flow chart of Formulation of LP problem
11
Figure 3.1 The resource time per product in minutes
22
Figure 3.2 MATLAB graph
25
Figure 3.3 Excel spreadsheet for a LP model
27
Figure 3.4 Solver parameters dialogue box
28
Figure 3.5 Graphical solution of 2 jobs and 4 machines
31
Figure 3.6 Gantt Chart
32
Figure 4.1 Solver results dialogue box
34
Figure 4.2 Answer report
37
Figure 4.3 Sensitivity report
38
Figure 4.4 Jensen LP solver spread sheet
42
Figure 4.5 Parametric response of RHS constraint
43
Figure 4.6 Parametric response of coefficient of variable P
44
Figure 4.7 Parametric response of coefficient of variable Q
45
Figure 5.1 Corners of the feasible region
48
Figure 5.2 Answer Report of one-time cost
55
LIST OF FIGURES
.
v
LIST OF TABLES
Table 3.1 Characterstics of LP problems in POM
20
Table 4.1 Changes in Z with changes in the RHS
40
Table 4.2 Parametric analysis of RHS of constraint
43
Table 4.3 Parametric analysis of coefficient of variables
P
44
Table 4.4 Parametric analysis of coefficient of variables
Q
45
Table 5.1 Optimum values
47
Table 5.2 Range of objective function coefficient
50
Table 5.3 Shadow prices for constraints
51
Table 5.4 Range of RHS coefficients
52
Table 5.5 Slack variables for constraints
53
Table 5.6 Product Outsourcing Data
54
vi
LIST OF ABBREVIATIONS
Abbreviation Expansion
GAMS
INF
LP
OE
OFC
OR
POM
RM
TOC
General Algebraic Modeling System
Infinity
Linear Programming
Operating Expenses
Objective Function Coefficient
Operation Research
Production and Operations Management
Raw Material
Theory of Constraints
1
CHAPTER 1
INTRODUCTION
1.1 HISTORY
Linear programming was developed as a discipline in the 1940's, motivated initially by the
need to solve complex planning problems in wartime operations. Its development accelerated
rapidly in the postwar period as many industries found valuable uses for linear programming.
The founders of the subject are generally regarded as George B. Dantzig, who devised the
simplex method in 1947, and John von Neumann, who established the theory of duality that
same year. The Nobel prize in economics was awarded in 1975 to the mathematician Leonid
Kantorovich (USSR) and the economist Tjalling Koopmans (USA) for their contributions to
the theory of optimal allocation of resources, in which linear programming played a key role.
Many industries use linear programming as a standard tool, e.g. to allocate a finite set of
resources in an optimal way. Examples of important application areas include airline crew
scheduling, shipping or telecommunication networks, oil refining and blending, and stock and
bond portfolio selection.
Linear programming (LP) is one of the most important general methods of operations
research. Countless optimization problems can be formulated and solved using LP
techniques. Operations research (OR) is a discipline explicitly devoted to aiding decision
makers.
Operations research was born with the increasing need to solve optimal resource allocation
during WWII
· Air Battle of Britain
· North Atlantic supply routing problems
· Optimal allocation of military convoys in Europe
1.2 PRINCIPLES OF MATHEMATICAL PROGRAMMING
Mathematical programming is a general technique to solve resource allocation problems
using optimization. Mathematical models are designed to have optimal (best) solutions.
Optimization problems are real world problems we encounter in many areas such as
mathematics, engineering, science, business and economics. In these problems, we find the
optimal, or most efficient, way of using limited resources to achieve the objective of the
situation. This may be maximizing the profit, minimizing the cost, minimizing the total
distance travelled or minimizing the total time to complete a project. For the given problem
2
we formulate a mathematical description called a mathematical model to represent the
situation. Types of problems:
· Linear programming
· Integer programming
· Dynamic programming
· Decision analysis
· Network analysis and CPM ( Critical Path Method )
1.3 LINEAR PROGRAMMING
Company managers are often faced with decisions relating to the use of limited resources.
These resources may include men, materials and money. In other sector, there are insufficient
resources available to do as many things as management would wish. The problem is based
on how to decide on which resources would be allocated to obtain the best result, which may
relate to profit or cost or both. Linear Programming is heavily used in Micro-Economics and
Company Management such as Planning, Production, Transportation, Technology and other
issues. Although the modern management issues are ever changing, most companies would
like to maximize profits or minimize cost with limited resources. Therefore, many issues can
be characterized as Linear Programming Problems (Sivarethinamohan, 2008). A linear
programming model can be formulated and solutions derived to determine the best course of
action within the constraint that exists. The model consists of the objective function and
certain constraints.
A typical mathematical program consists of a single objective function, representing either a
profit to be maximized or a cost to be minimized, and a set of constraints that circumscribe
the decision variables. In the case of a linear program (LP) the objective function and
constraints are all linear functions of the decision variables. At first glance these restrictions
would seem to limit the scope of the LP model, but this is hardly the case. Because of its
simplicity, software has been developed that is capable of solving problems containing
millions of variables and tens of thousands of constraints. Countless real-world applications
have been successfully modeled and solved using linear programming techniques.
It is defined as a specific class of mathematical problem, in which a linear objective function
is maximized (or minimized) subject to given linear constraints. This problem class is broad
enough to encompass many interesting and important applications, yet specific enough to be
tractable even if the number of variables is large.
Typical optimization problems maximize or minimize the value of a given variable (such as
3
profit, total costs, etc.) when other specified variables (production capacity, required product
quantities, etc.) are constrained. The field of mathematical programming includes a number
of optimization methods, each described by a mathematical model. In such a model, there is
one expression the objective function that should be maximized or minimized (or in some
cases set to a desired value). In addition, the model must include constraints that are
described by mathematical expressions. The most widely used models include only linear
relationships, and belong to the field of linear programming. In such models both the
objective function and the constraints are linear mathematical expressions. Mathematical
model is a set of equations and inequalities that describe a system.
1.3.1 Limitations of Linear Programming Model
·
It is applicable to only static situations since it does not take into account the effect of
time. The OR team must define the objective function and constraints which can
change due to internal as well as external forces.
· It assumes that the values of the coefficients of decision variables in the objective
function as well in all the constraints are known with certainity. Since in most of the
business situations, the decision variable coefficients are known only
probabilistically, it cannot be applied to such situations.
· In some situations it is not possible to express both the objective function and
constraints in linear form. For example, in production planning we often have non-
linear constraints on production capacities like setup and takedown times which are
often independent of the quantities produced. The misapplication of LP under non-
linear conditions usually result in an incorrect solution.
· Linear programming deals with problems that have a single objective. Real life
problems may involve multiple and even conflicting objectives. One has to apply goal
programming under such situations.
When comparison is made between the advantages and disadvantages/limitations of LP, its
advantages clearly overweigh its limitations. It must be clearly understood that LP
techniques, like other mathematical tools only help the manager to take better decisions; they
are in no way a substitute for the manager.
1.4 MOTIVATION
When we refer to resources we are talking about all the things that are required for production
and operations. Included in this term are personnel, machines and equipment, cash, capital
funds, material and supplies, utilities, floor space, time and other resources. These are the
4
means of production and one or more may be scarce to each operations manager`s particular
situation. The dominant question for the users of these resources is : Can we get the
quantities of what we need when we need them ?Many companies have had great success in
recent years using operations research(OR) tools such as linear programming ,simulation, and
decision analysis to reduce costs and improve their operations. One of the best ways to
determine how best to allocate the scarce resources is with the use of Linear Programming
(LP). Five common types of LP problems encountered are: product mix, ingredient mix,
transportation, production plan, and assignment. Depending upon each problem type which
could be described by posing three questions about each problem:
Q1.What is the single management objective?
Q2. What information do we need to achieve our objective?
Q3. What factors restrain us from achieving our objective?
The problem types as listed above are directly or indirectly of strategic importance to POM.
Such real-world decisions often involve hundreds or even thousands of constraints, large
quantities of data, many products and services, many time periods, numerous decision
alternatives and other complications. The complexity of these constrained decisions prompted
the development of linear programming methods. LP is a powerful tool in POM-powerful
because of the variety of uses to which it is put by operations managers. The ability to think
in terms of optimizing an objective within a set of constraints in real POM decision situations
will definitely set a manager apart. This thinking is at the heart of linear programming.
1.4.1 Examples of successful LP application
· Scheduling school buses to minimize total distance traveled.
· Allocating police patrols to high crime areas to minimize response time.
· Scheduling tellers at banks to minimize total cost of labor.
· Blending raw materials in feed mills to maximize profit while producing animal feed.
· Selecting the product mix in a factory to make best use of available machine-hours
and labor-hours available while maximizing profit.
5
· Allocating space for tenants in a shopping mall to maximize revenues to the leasing
company.
· Crew scheduling problems
· Network flow models
· Pollution control and removal
· Estimation techniques
1.5 CHARACTERISTICS OF LINEAR PROGRAMMING
a) Deterministic (no probabilities).
b) Single Objective: maximize or minimize some quantity (the objective function).
c) Continuous decision variables (unknowns to be determined)
d) Constraints limit ability to achieve objectives.
e) Objectives and constraints must be expressed as linear equations or inequalities
The concept behind a linear programming problem is simple. It consists of the following
terminology:
Decision
Variables
Decision variables describe the quantities that the decision makers would like
to determine. They are the unknowns of a mathematical programming model.
Typically we will determine their optimum values with an optimization
method. In a general model, decision variables are given algebraic
designations such as
. The number of decision variables is n,
and
is the name of the jth variable. In a specific situation, it is often
convenient to use other names such as
or
or
. In computer models
we use names such as FLOW1 or AB_5 to represent specific problem-related
quantities. An assignment of values to all variables in a problem is called a
solution.
Objective
Function
The objective function evaluates some quantitative criterion of immediate
importance such as cost, profit, utility, or yield. The general linear objective
6
function can be written as
Here is the coefficient of the jth decision variable. The criterion selected
can be either maximized or minimized.
Constraints A constraint is an inequality or equality defining limitations on decisions.
Constraints arise from a variety of sources such as limited resources,
contractual obligations, or physical laws. In general, an LP is said to have m
linear constraints that can be stated as
One of the three relations shown in the large brackets must be chosen for
each constraint. The number
is called a technological coefficient, and the
number is called the right-hand side value of the ith constraint. Strict
inequalities ( and ) are not permitted. When formulating a model, it is
good practice to give a name to each constraint that reflects its purpose.
Simple Upper
Bound
Associated with each variable, , may be a specified quantity, , that
limits its value from above;
When a simple upper is not specified for a variable, the variable is said to be
unbounded from above.
Nonnegativity
Restrictions
In most practical problems the variables are required to be nonnegative;
This special kind of constraint is called a non-negativity restriction.
Sometimes variables are required to be non-positive or, in fact, may be
unrestricted (allowing any real value).
7
Complete
Linear
Programming
Model
Combining the aforementioned components into a single statement gives:
The constraints, including non-negativity and simple upper bounds, define
the feasible region of a problem. If minimization is desired instead of
maximization, this can be accomplished by reversing the signs of c
1
...c
n
.
Parameters The collection of coefficients for all values of the indices i and j
are called the parameters of the model. For the model to be completely
determined all parameter values must be known.
1.6 SOLVING LP PROBLEMS
In 1947 George Dantzig developed the simplex method of LP. Dantzig`s simplex method was
probably the beginning of the development of the present day field of mathematical
programming. The graphical solution approach conceptually demonstrates the process of LP
solutions to those who have no experience with LP. Graphical solutions are therefore
intended as a teaching tool to assist you in understanding the process of LP solutions. The
simplex, transportation, and assignment methods are the practical LP solution tools. Although
use of the simplex method by hand to solve LPs is tedious and error prone, enough standard
LP computer programs are available for this task that real LP problems are always solved on
computers . Several computer programs are available to solve LP problems:
·LINDO - Linear INteractive Discrete Optimizer ·GAMS - also solves non linear problems
·Matlab Toolbox - Optimization toolbox (from Mathworks)
·Excel Solver
1.7 BASIC STEPS FOR SOLVING A LINEAR PROGRAMMING MODEL
i) Recognize the problem
ii) Define the problem
8
iii) Define the decision variables
iv) Collect the necessary parametric data
v) Formulate a model
vi) Solve the model.
vii) Verify and validate the model
viii) Analyze model output
ix) Interpret model results
x) Recommend a course of action.
1.7.1 Recognize the problem
Before a problem can be analyzed, one must become aware of the existence of a problem. In
the real world, problems hardly ever come pre-identified as such. One must proactively
search for and identify problems. This must be done carefully because the apparent problem
one perceives may not be the real problem. The analyst must distinguish between symptoms
and actual problems. Symptoms are signs that indicate the existence of certain conditions,
typically anomalous, somewhere in the system. A symptom is a reflection of some root
cause. Treating a symptom, doctors well know, will not cure the underlying illness. The
analyst must strive to uncover root causes and not be misled by superficial appearances.
Another important point is the type of problem present. The word problem has a negative or
pejorative connotation: something is not going right. Let us call these negative problems. A
negative problem exists when actual system performance falls below standards or
expectations, creating a performance gap. The greater the performance gap, the greater the
problem. Negative problems must be corrected promptly, for underperforming systems in
competitive Darwinian environments such as the business world will inexorably be driven
into extinction. In passing, keep in mind that there are two basic ways for performance gaps
to arise: (1) the system may be under performing or (2) the performance
standards/expectations may be set at unrealistically high levels. If the latter is the case, then
the standards/expectations must be revised so as to make them attainable. Unattainable
system states are immediately excluded from consideration in all system-analytic methods,
including LP, for there is nothing to be done about things which are impossible.
More important, however, are the positive problems: novel opportunities that perhaps should
be pursued. Negative problems must be corrected so that attention can be focused on finding
positive problems and capitalizing on the opportunity they present before our competitors do
so. Positive problems represent the future, and may well prove to be more profitable in the
long run than continuing with present activities. Positive problems are generally harder to
9
detect, for no symptoms may exist or be apparent. To detect opportunities, visionary
leadership is essential. It takes visionaries to convert negative problems into novel
opportunities. There is another useful way to classify problems: urgency vs. importance.
Urgent problems are those that demand immediate attention, although the solution need not
be optimal.
Negative problems are often of this type. Important problems, on the other hand, require
thorough attention and usually call for well-planned or optimal solutions. Urgent problems
can typically be treated with a quick but effective solution, which may be temporary, whereas
important problems entail considerable effort to devise efficient long-term solutions. Of
course, a problem can be both urgent and important; therefore, be analytically prepared.
1.7.2 Define the problem
Linear programming requires that the analyst clearly define two fundamental aspects of the
problem:
Objective: the system state or performance level one aims to attain
Constraints: the requirements that must be met by the proposed solution
Specifying the objective and all relevant constraints constitutes a complete LP problem
definition.
1.7.3 Define the decision variables
A decision variable is a system setting whose value is assigned by the decision maker. A
decision is made when a value is specified for a decision variable. Decision variables are
sometimes called controllable variables because they are under the control of the decision
maker. Decision variables are defined by specifying the metric (standard of measurement)
used for quantification, the entity being referenced and the time span of reference. The time
span may be omitted if the problem calls for a one-time or single-period decision.
Examples:
a) Let x = dozens of widgets produced per hour
b) Let y = pounds of chocolate consumed per person per week
c) Let z
i
= dollars invested in financial instrument i (i = 1, 2, ..., n)
1.7.4 Collect the necessary parametric data
Many, if not most of the elements needed to model the system of interest are not under the
control of the decision maker. For instance, in manufacturing systems, products must comply
with detailed specifications, production processes follow fixed operating procedures, and
financial aspects are strictly budgeted. These requirements are normally quantified by the
people involved in those activities, such as engineering and accounting finance. The
