Ordude #3-model Formulation

Operations Research OR#3 Model Formulation Lecturer Gesit Thabrani

Dual Degree – Management UNP Dual Degree – Management UNP

Learning Objectives After completing this chapter, students will be able to: 1. Understand the basic assumptions and properties of linear programming (LP) 2. Formulate the LP problems

Dual Degree – Management UNP

Outline 1. 2. 3.

What is Linear Programming? Requirements of a Linear Programming Problem Formulating LP Problems

Dual Degree – Management UNP

Linear Programming
Many management decisions involve trying to

make the most effective use of limited resources
Machinery, labor, money, time, warehouse space, raw

materials


Linear programming (LP LP) is a widely used

mathematical modeling technique designed to help managers in planning and decision making relative to resource allocation
Belongs to the broader field of mathematical programming
In this sense, programming refers to modeling and solving a problem mathematically Dual Degree – Management UNP

Requirements of a Linear Programming Problem
LP has been applied in many areas over the past

50 years
All LP problems have 4 properties in common 1. All problems seek to maximize or minimize some function quantity (the objective function) 2. The presence of restrictions or constraints that limit the degree to which we can pursue our objective 3. There must be alternative courses of action to choose from 4. The objective and constraints in problems must be expressed in terms of linear equations or inequalities

Dual Degree – Management UNP

LP Properties and Assumptions PROPERTIES OF LINEAR PROGRAMS 1. One objective function 2. One or more constraints 3. Alternative courses of action 4. Objective function and constraints are linear ASSUMPTIONS OF LP 1. Certainty 2. Proportionality 3. Additivity 4. Divisibility 5. Nonnegative variables Table 7.1 Dual Degree – Management UNP

Basic Assumptions of LP
We assume conditions of certainty exist and







numbers in the objective and constraints are known with certainty and do not change during the period being studied We assume proportionality exists in the objective and constraints We assume additivity in that the total of all activities equals the sum of the individual activities We assume divisibility in that solutions need not be whole numbers All answers or variables are nonnegative Dual Degree – Management UNP

Formulating LP Problems
Formulating a linear program involves developing

a mathematical model to represent the managerial problem
The steps in formulating a linear program are 1. Completely understand the managerial problem being faced 2. Define the decision variables 3. Identify the objective and constraints 4. Use the decision variables to write mathematical expressions for the objective function and the constraints Dual Degree – Management UNP

Formulating LP Problems
Decision variables are mathematical symbols that

represent levels of activity by the firm
For example, an electrical manufacturing firm desires to produce x1 radios, x2 toasters, and x3 clocks, where x1, x2, and x3 are symbols representing unknown variable quantities of each item. The final values of x1, x2, and x3, as determined by the firm, constitute a decision (e.g., the equation x1 = 100 radios is a decision by the firm to produce 100 radios).
The objective function is a linear mathematical relationship that describes the objective of the firm in terms of the decision variables. The objective function always consists of either maximizing or minimizing some value (e.g., maximize the profit or minimize the cost of producing radios) Dual Degree – Management UNP

Formulating LP Problems
The model constraints are also linear

relationships of the decision variables; they represent the restrictions placed on the firm by the operating environment.
The restrictions can be in the form of limited resources or restrictive guidelines.
For example, only 40 hours of labor may be available to produce radios during production. The actual numeric values in the objective function and the constraints, such as the 40 hours of available labor, are parameters
Status Function show that all the variables are nonnegative (nonnegativity constraints) Dual Degree – Management UNP

Formulating LP Problems Linear Programming Model

PROBLEMS FORMULATION

Identify the problem

Number of variable = 2 Number of variable >= 2

Determine objective function

Determine the constraints

Define status function

Maximize

inequality “<=”

X1 >= 0

Minimize

inequality “>=” equality “=”

Dual Degree – Management UNP

Formulating LP Problems
One of the most common LP applications is the

product mix problem
Two or more products are produced using limited resources such as personnel, machines, and raw materials
The profit that the firm seeks to maximize is based on the profit contribution per unit of each product
The company would like to determine how many units of each product it should produce so as to maximize overall profit given its limited resources Dual Degree – Management UNP

Flair Furniture Company
The Flair Furniture Company produces






inexpensive tables and chairs Processes are similar in that both require a certain amount of hours of carpentry work and in the painting and varnishing department Each table takes 4 hours of carpentry and 2 hours of painting and varnishing Each chair requires 3 of carpentry and 1 hour of painting and varnishing There are 240 hours of carpentry time available and 100 hours of painting and varnishing Each table yields a profit of $70 and each chair a profit of $50 Dual Degree – Management UNP

Flair Furniture Company
The company wants to determine the best

combination of tables and chairs to produce to reach the maximum profit HOURS REQUIRED TO PRODUCE 1 UNIT DEPARTMENT

(T) TABLES

(C) CHAIRS

AVAILABLE HOURS THIS WEEK

Carpentry

4

3

240

Painting and varnishing

2

1

100

$70

$50

Profit per unit Table 7.2

Dual Degree – Management UNP

Flair Furniture Company
The decision variables representing the actual

decisions we will make are T = number of tables to be produced per week C = number of chairs to be produced per week
The objective is to Maximize profit
The constraints are 1. The hours of carpentry time used cannot exceed 240 hours per week 2. The hours of painting and varnishing time used cannot exceed 100 hours per week Dual Degree – Management UNP

Flair Furniture Company
We create the LP objective function in terms of T

and C Maximize profit = $70T + $50C
Develop mathematical relationships for the two constraints
For carpentry, total time used is (4 hours per table)(Number of tables produced) + (3 hours per chair)(Number of chairs produced)


We know that

Carpentry time used ≤ Carpentry time available 4T + 3C ≤ 240 (hours of carpentry time) Dual Degree – Management UNP

Flair Furniture Company
Similarly

Painting and varnishing time used ≤ Painting and varnishing time available 2 T + 1C ≤ 100 (hours of painting and varnishing time) This means that each table produced requires two hours of painting and varnishing time
Both of these constraints restrict production

capacity and affect total profit

Dual Degree – Management UNP

Flair Furniture Company
The values for T and C must be nonnegative

T ≥ 0 (number of tables produced is greater than or equal to 0)

C ≥ 0 (number of chairs produced is greater than or equal to 0)


The complete problem stated mathematically

Maximize profit = $70T + $50C subject to 4T + 3C ≤ 240 (carpentry constraint) 2T + 1C ≤ 100 (painting and varnishing constraint) T, C ≥ 0 (nonnegativity constraint) Dual Degree – Management UNP

Shader Electronics The productproduct-mix problem at Shader Electronics


Two products

1. Shader Walkman, a portable CD/DVD player 2. Shader Watch Watch--TV, a wristwatchwristwatch-size Internet--connected color TV Internet


Determine the mix of products that will produce the maximum profit

Dual Degree – Management UNP

Shader Electronics Hours Required to Produce 1 Unit Department Electronic Assembly Profit per unit

Walkman Watch Watch--TVs (X1) (X2) 4 2 $7

3 1 $5

Available Hours This Week 240 100

Decision Variables: X1 = number of Walkmans to be produced X2 = number of WatchWatch-TVs to be produced Dual Degree – Management UNP

Shader Electronics
Objective Function:

Maximize Profit = $7 $7X X1 + $5 $5X X2 Or, usually we can state it as: Max Z = 7X1 + 5X2

Dual Degree – Management UNP

Shader Electronics First Constraint: Electronic time used

is ≤

Electronic time available

4X1 + 3X2 ≤ 240 (hours of electronic time) Second Constraint: Assembly time used

is ≤

Assembly time available

2X1 + 1X2 ≤ 100 (hours of assembly time) Dual Degree – Management UNP

Shader Electronics
The complete problem stated mathematically

Max Z = 7X1 + 5X2 subject to 4X1 + 3X2 ≤ 240 (hours of electronic time) 2X1 + 1X2 ≤ 100 (hours of assembly time) X1, X2 ≥ 0 (nonnegativity constraint)

Dual Degree – Management UNP

Minimization Case (Fertilizer)
A farmer is preparing to plant a crop in the spring and

needs to fertilize a field. There are two brands of fertilizer to choose from, Super-gro and Crop-quick. Each brand yields a specific amount of nitrogen and phosphate per bag, as follows: CHEMICAL CONTRIBUTION BRAND NITROGEN (LB./BAG)

PHOSPHATE (LB./BAG

Super-gro

2

4

Crop-quick

4

3


The farmer's field requires at least 16 pounds of nitrogen

and 24 pounds of phosphate. Super-gro costs $6 per bag, and Crop-quick costs $3. The farmer wants to know how many bags of each brand to purchase in order to minimize the total cost of fertilizing.

Dual Degree – Management UNP

Minimization Case (Fertilizer) Summary of LP Model Formulation Steps
Step 1. Define the decision variables


How many bags of Super-gro and Crop-quick

to buy


Step 2. Define the objective function
Minimize cost
Step 3. Define the constraints
The field requirements for nitrogen and phosphate

Dual Degree – Management UNP

Minimization Case (Fertilizer)
Decision Variables


This problem contains two decision

variables, representing the number of bags of each brand of fertilizer to purchase:
x1 = bags of Super-gro
x2 = bags of Crop-quick

Dual Degree – Management UNP

Minimization Case (Fertilizer)
The Objective Function
The farmer's objective is to minimize the total cost of fertilizing.
The total cost is the sum of the individual costs of each type of fertilizer purchased.
The objective function that represents

total cost is expressed as minimize Z = $6x1 + $3x2 where
$6x1 = cost of bags of Super-gro
$3x2 = cost of bags of Crop-quick

Dual Degree – Management UNP

Minimization Case (Fertilizer)
Model Constraints

Each bag of fertilizer contributes a number of pounds of nitrogen and phosphate to the field
The constraint for nitrogen is

2x1 + 4x2 ≥ 16 lb.


The constraint for phosphate is constructed like

the constraint for nitrogen: 4x1 + 3x2 ≤ 24 lb.


Nonnegativity constraints in this problem to

indicate that negative bags of fertilizer cannot be purchased: x1, x2 ≥ 0 Dual Degree – Management UNP

Minimization Case (Fertilizer)
The complete model formulation for

this minimization problem is Min Z = 6x1 + 3x2 subject to 2x1 + 4x2 ≥ 16 lb, of nitrogen 4x1 + 3x2 ≥ 24 lb, of phosphate x1, x2 ≥ 0 (nonnegativity constraint)

Dual Degree – Management UNP