Excerpt

## TABLE OF CONTENTS

DECLARATION

ABSTRACT

ACKNOWLEDGEMENTS

TABLE OF CONTENTS

LIST OF FIGURES

LIST OF TABLES

LIST OF ABBREVIATIONS

CHAPTER 1 INTRODUCTION

1.1 HISTORY

1.2 PRINCIPLES OF MATHEMATICAL PROGRAMMING

1.3 LINEAR PROGRAMMING

1.3.1 Limitations of LP model

1.4 MOTIVATION

1.4.1 Examples of successful LP applications

1.5 CHARACTERSTICS OF LINEAR PROGRAMMING

1.6 SOLVING LP PROBLEMS

1.7 BASIC STEPS FOR SOLVING A LP MODEL

1.7.1 Recognize the problem

1.7.2 Define the problem

1.7.3 Define the decision variables

1.7.4 Collect the necessary parametric data

1.7.5 Formulate a model

1.7.6 Solve the model

1.7.7 Verify and validate the model

1.7.8 Analyze model output

1.7.9 Interpret model results

1.7.10 Recommend a course of action

1.8 FORMULATING LP PROBLEMS

1.9 OBJECTIVES OF THE PRESENT WORK

1.10 ORGANISATION OF THE DISSERTATION

1.11 SUMMARY

CHAPTER 2 LITERATURE REVIEW

2.1 INTRODUCTION

2.2 DECISION MAKING IN POM

2.3 THE SIMPLEX METHOD

2.4 THE COMMAND *linprog*

2.5 USING EXCEL SOLVER OPTIMIZATION PROBLEM

2.5.1 Spreadsheet modeling & Excel Solver

2.6 PRODUCTION OUTSOURCING: A LP MODEL FOR THE TOC

2.7 GENERAL RESOURCE ALLOCATION MODEL

2.8 SUMMARY

CHAPTER 3 LINEAR PROGRAMMING MODEL 20-

3.1 INTRODUCTION

3.2 THE PROBLEM STATEMENT

3.3 FORMULATION OF LP MODEL

3.4 SOLUTION USING MATLAB

3.5 THE COMMAND *simlp*

3.6 THE OPTIMAL SOLUTION USING MATLAB

3.7 SOLUTION USING EXCEL SOLVER

3.8 OPTIMAL SCHEDULING ON MACHINES

3.8.1 Assumptions in sequencing problem

3.8.2 Processing two jobs through four machines

3.9 SUMMARY

CHAPTER 4 INTERPRETING COMPUTER SOLUTIONS OF LP PROBLEM 34-

4.1 INTRODUCTION

4.2 TERMS

4.2.1 Slack variables

4.2.2 Basic & non-basic variables

4.3 ANSWER REPORT ANALYSIS

4.4 SENSITIVITY ANALYSIS

4.4.1 Find the bottleneck

4.4.2 Find the range over which the unit profit may change

4.4.3 Find the marginal benefit of increasing the time availability

4.4.4 Find the range over which the time availability may change

4.5 PARAMETRIC ANALYSIS

4.6 SUMMARY

CHAPTER 5 RESULT & DISCUSSIONS 47-

5.1 INTRODUCTION

5.2 SEARCH FOR THE OPTIMAL SOLUTION

5.3 BOTTLENECKS

5.4 RANGE OVER WHICH THE UNIT PROFIT MAY CHANGE

5.5 MARGINAL BENEFIT OF INCREASING THE TIME AVAILABILITY

5.6 RANGE OVER WHICH THE TIME AVAILABILITY MAY CHANGE

5.7 REDUCED COST FOR NON-BASIC VARIABLES

5.8 SLACK VALUES FOR CONSTRAINTS

5.9 RECOMMENDED COURSE OF ACTION

5.9.1 Product Outsourcing

5.9.2 One-time cost

5.9.3 Cross Training of one machine operator

5.9.4 Possibility of third product manufacturing

5.9.5 Optimal sequencing to process jobs on machines

5.10 SUMMARY

CHAPTER 6 CONCLUSIONS 58-

6.1 INTRODUCTION

6.2 SUMMARY OF THE PRESENT WORK

6.3 SUMMARY OF CONTRIBUTION

6.4 SCOPE FOR FUTURE WORK

6.5 CONCLUDING REMARKS

REFERENCES

## LIST OF FIGURES

**Figure 1.1** Flow chart of Formulation of LP problem

**Figure 3.1** The resource time per product in minutes

**Figure 3.2** MATLAB graph

**Figure 3.3** Excel spreadsheet for a LP model

**Figure 3.4** Solver parameters dialogue box

**Figure 3.5** Graphical solution of 2 jobs and 4 machines

**Figure 3.6** Gantt Chart

**Figure 4.1** Solver results dialogue box

**Figure 4.2** Answer report

**Figure 4.3** Sensitivity report

**Figure 4.4** Jensen LP solver spread sheet

**Figure 4.5** Parametric response of RHS constraint

**Figure 4.6** Parametric response of coefficient of variable P

**Figure 4.7** Parametric response of coefficient of variable Q

**Figure 5.1** Corners of the feasible region

**Figure 5.2** Answer Report of one-time cost

## LIST OF TABLES

**Table 3.1** Characterstics of LP problems in POM

**Table 4.1** Changes in Z with changes in the RHS

**Table 4.2** Parametric analysis of RHS of constraint

**Table 4.3** Parametric analysis of coefficient of variables P

**Table 4.4** Parametric analysis of coefficient of variables Q

**Table 5.1** Optimum values

**Table 5.2** Range of objective function coefficient

**Table 5.3** Shadow prices for constraints

**Table 5.4** Range of RHS coefficients

**Table 5.5** Slack variables for constraints

**Table 5.6** Product Outsourcing Data

## LIST OF ABBREVIATIONS

illustration not visible in this excerpt

## 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 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

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 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

- 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:

illustration not visible in this excerpt

### 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

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 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 zi = 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 analyst must collect this information. Any piece of information in the form of a constant quantity is called a parameter. A **parameter** is simply a numerical constant that specifies particular system attributes. Sometimes system requirements vary depending on certain other factors, in which case they are known as **uncontrollable variables**.

#### 1.7.5 Formulate a model

In LP, model formulation means expressing the objective and each of the constraints algebraically in terms of the decision variables and parameters. This is usually straightforward if the problem and the decision variables have been defined correctly. Difficulties in model formulation are typically a sign that something was amiss when defining the problem or the decision variables. Make sure steps 1 and 2 are complete and correct (coherent) before attempting to formulate a model.

There may be several possible ways to model the same problem. Which way is best depends on what information the analyst wants to obtain from the analysis. It is advisable to begin with a relatively simple model at the outset and subsequently refine it if additional information is desired.

#### 1.7.6 Solve the model

Model solution in LP is computationally intensive and normally conducted by means of computer software. In this module, we will examine the graphical solution method to illustrate the basic concepts of LP. But the graphical method, although theoretically sound, is very limited in power and therefore practically useless for real-world applications. We will make use of MATLAB and Excel's Solver Add-In to illustrate a practical solution method. There are many software options available, however, all of which provide the same basic information regarding LP solutions.

#### 1.7.7 Verify and validate the model

**Model verification** means ensuring that the model is computationally correct, that it calculates what it is supposed to. A model containing errors (of both omission and commission) is useless. **Model validation** means ensuring that the model is representationally correct, that it accurately reproduces the behavior of the real-world system being modeled. Verification deals with the internal consistency of the model while validation addresses its external (representational) correctness. In LP, verifying and validating a model can range from a simple inspection of the output to detailed comparisons of model results to the system's operational statistics.

#### 1.7.8 Analyze model output

The computer provides the solution to the LP problem along with a sensitivity analysis. However, in LP the term **solution** means the optimal quantities the model assigns to the decision variables. The term **value** means the result obtained for the objective function with that **optimal solution**. The term **optimal** means the best possible value that complies with all problem constraints, one that maximizes or minimizes the value of the objective function. **Sensitivity analysis** consists of additional information provided by the model. This includes the **opportunity costs** (called **shadow prices** or **dual prices**) for all resources, the ranges in which these dual prices hold, and the range where the model solution remains valid if the objective function parameters (called objective function coefficients) were to change. Keep in mind that a model is an idealized representation of a real-world system and therefore the model solution is also an idealized result. In order to make effective use of model results, the next step must be performed.

#### 1.7.9 Interpret model results

Every model is a simplification of the actual system being analyzed. Thus model solutions must be interpreted in the light of real-world considerations that may deviate from the simplifying assumptions built into the model. One way of dealing with this is to work interactively with the model to assess the impact of different possible conditions on model results. A great deal can be learned about system behavior by experimenting with the model, without affecting the actual system. The insight thus gained can be extremely useful for managers in the implementation phase of the project as well as in control of operations.

#### 1.7.10 Recommend a course of action

Presentation of the findings concludes the LP modeling analysis includes sensitivity analysis, parametric analysis and sequence modeling.

### 1.8 FORMULATING LP PROBLEMS

illustration not visible in this excerpt

**Fig 1.1 Flow chart of formulation of LP problem**

### 1.9 OBJECTIVES OF THE PRESENT WORK

The objectives of the present work are listed below:

- Detailed study of how LP can be used to support strategic management decisions and objectives achieved within constraints imposed on organizations

- Formulate a linear programming model for a given problem

- Solve linear programming models using **MATLAB & Excel Solver** to find an optimal solution

- Analyze the information provided in answer report, sensitivity analysis and parametric analysis to study the affect of discrete and continuous changes in model parameters on the optimal solution

- To identify the bottle-necks

- To determine the optimal sequence needed to process jobs on various machines and to calculate the total time needed to complete the jobs

- To recommend a course of action.

### 1.10 ORGANISATION OF THE DISSERTATION

This dissertation is organized as follows. Chapter 1 provides the motivation and objectives of the dissertation. Chapter 2 provides a brief literature review relevant to the dissertation. Chapter 3 explains the problem statement and its optimal solution using MATLAB and Excel Solver. It provides the optimal scheduling to minimize the total processing time for two products using graphical method and Gantt chart. Chapter 4 provides Sensitivity Analysis using Excel Solver and Parametric Analysis using Jensen LP Solver. Chapter 5 summarizes the results and recommends a course of action. Chapter 6 concludes the dissertation and provides the scope for future work.

### 1.11 SUMMARY

The motivation and objectives of the present work and organization of the dissertation were explained in this chapter. The subsequent chapter provides a review of relevant literature.

## CHAPTER 2 ITERATURE REVIEW

### 2.1 INTRODUCTION

Today, perhaps more than ever before, operations managers understand that most decisions must be made and objectives achieved with in constraints imposed on organizations. Customer demand for products and services, limited production resources, government regulations, quality requirements, and technological limitations are examples of constraints in POM. Within these and other constraints, managers seek to accomplish their operation strategies. At world class companies, managers at all levels use the power of linear programming and other analysis tools to solve complex, constrained business problems. *LP is applied to both strategic, one-of-a-kind, long range decisions and short range, recurring decisions.* Both types can be of strategic importance in equipping a company for competition in a highly competitive industry.

A brief literature review of the topics that has been covered in this work is provided in this chapter. The review takes into account most of the relevant work that has been published and are accessible, on the topics under study. The journals, books and other resources used are mentioned below and documented in the reference section.

### 2.2 DECISION MAKING IN POM

**Norman Gaither & Greg Frazier. Operations Management**. **Cengage Learning,2009**

*According to authors no other approach helps us understand how operations managers manage than the examination of the decisions in POM, because in large part ,operations managers manage decisions about all the activities of production systems.*

Of the many functions in business there are three primary functions: operations, marketing, and finance/accounting.POM is nothing but Production and Operations management responsible for the management of an organization’s productive resources or its production system, which converts inputs into the organization’s products and services. This conversion process is the heart of what is called operations or production. Without operations, no products or services could be produced; without marketing, no products or services could be sold ;without finance/accounting, financial failure would surely result. Achievement of the organizational goals of profitability, survival, and growth dynamic business climate requires cooperative teamwork among these primary business functions. In this study, we shall pay particular attention to the decisions that operations managers make and how they make them. Classifying operations decisions is difficult, but in our experience as operations managers, decisions tended to fall into three general categories:

**[...]**

- Quote paper
- Dinesh Gupta (Author), 2013, Strategic Allocation of Resources Using Linear Programming Model with Parametric Analysis, Munich, GRIN Verlag, https://www.grin.com/document/271318

Comments

This e-book is very much helpful to those who are interested in learning to solve simple or complex Linear Programming problems through MATLAB and Excel Solver explained in a very easy manner. This method of solving LP problems is less tedious and are not error prone compared to solving by hand.