Slide template - York University



Section 1: Introduction

Question: What is "operations research" ?

Is it just another mathematics course that claims to be useful in the 'real world'?

"'What's Best' is saving us over a $1,000,000 USD a year " claims one business that uses it.

'What's Best' is a cross between a spreadsheet program and a linear programming package – to use it, you must be able to mathematically model the problem as a linear optimization problem.

So is "operations research" the same as "linear programming"?

No, but linear programming is a part of operations research.

The question is best answered by looking historically a the origins of operations research (O.R.).

O.R. was founded in the 2nd World War to allocate scarce resources, both at home and abroad.

The term linear programming which forms a major part of optimization (also called linear optimization) came into usage approx. 1947 or 1948; i.e. it is a relatively new subject.

Some of the early researchers in the field were: Danzig, Von Neumann, Stiegler, Hitchcock, Kuhn, Tucker.

Linear programming involves equations and inequalities of 1st degree; all of the variables are to the first power and there are no products of variables. While O.R. also contains non-linear programming, some of the non-linear programming problems can be solved using "linear methods".:

Definition 1.1: O.R. (management science) is a scientific approach to decision that seeks to design and operate a system, usually under conditions requiring the allocation of scarce resources.

Definition 1.1a: A system is an organization of interdependent components that work together to accomplish the goal of the system.

Ex. 1. x1+2x2=5 linear equation in 2 variables

Ex. 2. x1+2x2 ≤ 5 linear inequality in 2 variables

Ex. 3. x12+2.x22=5 non-linear equation (quadratic)

Ex. 4. x1+2x1x2 ≤ 5 non-linear inequality

What are the variables? They represent goods, costs, or other real items described by the MODEL.

In some applications, we might require several small models which together comprise the MODEL.

How It is Done:

Example 1.1: (A simplified diet problem) A nutritionist wishes that the diet of her patient, a pregnant woman, is adequate in vitamin K and iron. The nutritionist intends to ask the woman to eat sufficient quantities of fish, poultry, and meat to achieve this goal. Table I summarizes the data.

| |Vitamin K |Iron |

|fish |2.3 |1.8 |

|poultry |2.7 |1.6 |

|red meat |3.1 |11.7 |

Table I (mg. per 100 gm. serving)

(Note: The numbers for Vitamin K are fictitious.)

The nutritionist wishes the woman to have at least 35 mg. and 100 mg. Per week of Vitamin K and iron respectively. What should the diet content be?

Solution: To model the problem, we introduce the variables

Let

x1= # of 100 mg. servings of fish per week

x2= # of 100 mg. servings of poultry per week

x3= # of 100 mg. servings of red meat per week

Then

[pic]

[pic]

There are many possible solutions; e.g.

x1=100 x2=0 x3=0

x1=3 x2=1 x3=8

x1=–1 x2=3 x3=100

How do we choose the right solution for us?

What do we mean by the right solution since two of the three solutions above are real world solutions which satisfy the criteria?

Suppose the nutritionist wishes to minimize the fat content of the diet.

| |Fat |

|fish |7.0 |

|poultry |4.7 |

|red meat |10.2 |

Table 2 (gm of fat per 100 gm. serving)

(Note: The numbers for Fat are fictitious.)

Problem: minimize [pic]

subject to

[pic]

[pic]

[pic]

Note that we added additional constraints (3) (actually 3 more constraints) in order to make our model match a real world problem since the number of servings cannot be negative.

Def. 1.1: [pic] is called the objective function.

Def. 1.2: (1), (2) and (3) are called the constraints. (3)

are called the nonnegativity restrictions.

The above is an example of a linear programming or linear optimization problem.

Recall: A function [pic] is called linear iff

(1) for any [pic] and any real k, [pic] and

(2) for any [pic] and [pic] , [pic]

This is satisfied by the objective function since all of the terms contain a variable to the 1st degree and it is additive.

Notice that linearity implies that if the inputs x1,x2 and x3 are doubled then the outputs and the objective function (fat) are also doubled.

Vitamin K:[pic]

Iron: [pic]

Fat: [pic]

Additive: If the woman was given x11 servings of fish, x21 servings of poultry and x31 servings of red meat and later in the same week was given x12 servings of fish, x22 servings of poultry, and x32 servings of red meat, then

Total Vitamin K = [pic]

[pic]

Total iron= =[pic]

[pic]

Total fat=

[pic]

[pic]

Remark: The additivity property is, in the real world, only a first order approximation; however long experience shows it is a reasonable approximation for this model which has many uses other than just a diet.

Example 1.2: U.S. Labs manufactures heart valves from the valves of pigs. Different heart operations require valves of different sizes. The cost and size of the valves purchased from three different suppliers is given in Table I below. Each month, U.S. Labs places one order with each supplier. At least 500 large, 300 medium and 300 small valves must be purchased each month. Because of the limited availability of pig valves, at most 500 valves per month can be purchased from each supplier. Formulate an LP problem that can be used to minimize the cost of acquiring the needed valves.

| |Cost per valve |% Large |% Medium |% Small |

|Supplier #1 |5 |40 |40 |20 |

|Supplier #2 |4 |30 |35 |35 |

|Supplier #3 |3 |20 |20 |60 |

Table I

Remark: We should recognize this is a diet type problem with the three suppliers playing the role of fish, poultry, red meat and the percentage of large, medium, and small playing the role of vitamin K an iron.

Solution: Let xi= # valves purchased from Supplier i, i=1,2,3

cost: z=5x1+4x2+3x3

# large valves: .4x1+.3x2+.2x3 ≥ 500 (1)

# med valves: .4x1+.35x2+.2x3 ≥ 300 (2)

# small valves: .2x1+.35x2+.6x3 ≥ 300 (3)

Max available: xi ≤ 500, i=1,2,3

Nonnegativity: xi ≥ 0, i=1,2,3

LP problem: min z=5x1+4x2+3x3

s.t.

.4x1+.3x2+.2x3 ≥ 500 (1)

.4x1+.35x2+.2x3 ≥ 300 (2)

.2x1+.35x2+.6x3 ≥ 300 (3)

x1 ≤ 500 (4)

x2 ≤ 500 (5)

x3≤ 500 (6)

xi≥0 i=1,2,3

Problems with this model:

(1) xi i=1,2,3 should each be integer.

(2) Fractional amounts may occur in .4x1, .3x2 etc. This can be overcome by using [pic] = greatest integer function namely

[pic]

However this may still be a problem since it is possible that

[pic] may be < x1. This problem can be corrected somewhat by letting

xi1= # large valves from supplier I, i=1,2,3

xi2= # medium valves from supplier I, i=1,2,3

xi3= # small valves from supplier I, i=1,2,3

xi=xi1+xi2+xi3

The problem with this approach is that it assumes control over xi1,xi2,xi3 which in fact one does not have.

An alternate approach is to take xi so that .4x1 etc. are all integer and make this a constraint on the problem. We will deal with this more next term.

Example 1.3: (A Modeling Example)

■ Eli Daisy produces the drug Wozac in batches by heating a chemical mixture in a pressurized container.

■ Each time a batch is produced, a different amount of Wozac is produced.

□ The amount produced is the process yield (measured in pounds).

■ Daisy is interested in understanding the factors that influence the yield of Wozac production process.

■ Describe a model-building process for this situation.

■ Daisy is first interested in determining the factors that influence the process yield.

□ This is a descriptive model since it describes the behavior of the actual yield as a function of various factors.

■ Daisy might determine that the following factors influence yield:

□ Container volume in liters (V)

□ Container pressure in milliliters (P)

□ Container temperature in degrees centigrade (T)

□ Chemical composition of the processed mixture

■ Letting A, B, and C be the percentage of the mixture made up of chemical A, B, and C, then Daisy might find , for example, that:

■ To determine the relationship, the yield of the process would have to be measured for many different combinations of the factors.

■ Knowledge of this equation would enable Daisy to describe the yield of the production process once volume, pressure, temperature, and chemical composition were known.

[pic]

■ Prescriptive models “prescribe” behaviour for an organization that will enable it to best meet its goals.

□ Components of this model include:

■ objective function(s)

■ decision variables

■ constraints

■ An optimization model seeks to find values of the decision variables that optimize (maximize or minimize) an objective function among the set of all values for the decision variables that satisfy the given constraints.

■ The Daisy example seeks to maximize the yield for the production process.

■ In most models, there will be a function we wish to maximize or minimize. This function is called the model’s objective function.

■ To maximize the process yield we need to find the values of V, P, T, A, B, and C that make the yield equation (below) as large as possible.

[pic]

■ In many situations, an organization may have more than one objective.

□ For example, in assigning students to the two high schools in Bloomington, Indiana, the Monroe County School Board stated that the assignment of students involve the following objectives:

■ equalize the number of students at the two high schools

■ minimize the average distance students travel to school

■ have a diverse student body at both high schools

Def. 1.3: Variables whose value are under our control and influence system performance are called decision variables.

□ In the Daisy example, V, P, T, A, B, and C are decision variables.

■ In most situations, only certain values of the decision variables are possible.

□ For example, certain volume, pressure, and temperature conditions might be unsafe. Also, A, B, and C must be nonnegative numbers that sum to one.

Def.1.4: The restrictions on the decision variables are called constraints.

■ Suppose the Daisy example has the following constraints:

□ Volume must be between 1 and 5 liters

□ Pressure must be between 200 and 400 milliliters

□ Temperature must be between 100 and 200 degrees centigrade

□ Mixture must be made up entirely of A, B, and C

□ For the drug to perform properly, only half the mixture at most can be product A.

Mathematically, these constraints can be expressed as follows:

V ≤ 5 (1)

V ≥ 1 (2)

P ≤ 400 (3)

P≥ 200 (4)

T≤ 200 (5)

T≥ 100 (6)

A+B+C=1 (7)

A≤ .5 (8)

A≥ 0 (9)

B≥ 0 (10)

C≥ 0 (11)

The optimization problem for Eli Daisy is

maximize [pic]

subject to (s.t.)

V ≤ 5 (1)

V ≥ 1 (2)

P ≤ 400 (3)

P≥ 200 (4)

T≤ 200 (5)

T≥ 100 (6)

A+B+C=1 (7)

A≤ .5 (8)

A≥ 0 (9)

B≥ 0 (10)

C≥ 0 (11)

Remark: The Daisy problem is not an LP problem because even though its constraints are linear inequalities, the objective function is non-linear.

Definition 1.5: Any specification of the decision variables which satisfy all of the constraints is said to be in the feasible region.

For example, V=2, P=300, T=150, A=.4,B=.3,C=.3 is a point in the feasible region.

Definition 1.6: An optimal solution to an LP problem is a point in the feasible region which optimizes the objective function.

In the Daisy example, using LINGO or LINDO or other optimization software, the optimum solution is V=5,P=200,T=100, A=.294,B=0, C=.706 and the maximum yield =z=209.384.

Daisy problem formulation in LINGO

[pic]

Solution extract of Daisy example (shown without slack, surplus or dual prices) using LINGO 16.0

[pic]

Remark: Non-linear problems like the Daisy example are typically much harder to solve than the linear ones.

Def. 1.7: A static model is one in which the decision variables do not involve sequences of decisions over multiple periods.

Def. 1.8: A dynamic model is one in which the decision variables do involve sequences of decisions over multiple periods.

Def. 1.9: If one or more of the decision variables is required to be an integer, then we say that the optimization problem is an integer model. Otherwise the optimization problem is a noninteger model.

Remark: Integer models are often harder to solve than noninteger models. We will learn how to solve these next term.

Def. 1.10: A determinisitic model is a model which for any value of the decision variables, the objective function and whether or not the constraints are satisfied is known with certainty. Any model which is not deterministic is called stochastic.

The Seven Step Model Building Process

1. Formulate the problem.

▪ Define the problem.

▪ Specify objectives.

▪ Determine the parts of the organization to be studied.

2. Observe the system.

▪ Determine the parameters affecting the problem.

▪ Collect data to estimate the values of the parameters.

3. Formulate a mathematical model of the problem.

4. Verify the model and use the model for prediction.

▪ Does the model yield results for values of the decision variables not used to develop the model?

▪ What eventualities might cause the model to become invalid?

5. Select a suitable alternative.

▪ Given a model and a set of suitable alternative soltions, determine which solution best meets the organization's objectives.

6. Present the results and conclusion(s) of the study to the organization.

▪ Present the results to the decision maker(s). If necessary present several alternative solutions and permit the organization to choose the one that best meets their needs.

▪ Any nonapproval of the study's recommendations my have stemmed from an incorrect problem definition or failure to involve the decision maker(s) from the start of the project. In such a case return to step 1,2 or 3.

7. Implement and evaluate recommendations.

▪ Assist in implementing the recommendations

▪ Monitor and dynamically update the system as the environment and parameters change to ensure that recommendations enable the organization to meet its goals.

B General Diet Problem (Example 1.4)

1. n different foods F1,F2,…Fn

2. m different nutrients N1,N2,…Nm

3. assumptions: each man needs bi units of nutrients Ni per week i=1,2,…m

4. aij=amount of ith nutrient contained in a unit of food j

5. diet: (x1,x2,…,xn) where xi=# units of food Fi

Total N1 in diet: [pic]

Total N2 in diet: [pic]

[pic]

Total Nm in diet: [pic]

So to meet the assumptions in (3) we must have

[pic]

[pic]

[pic]

[pic]

Also [pic]

6. cost: Let ci=cost of a unit of food Fi i=1,2,…,n

a. note that cost does not have to be dollars; it could be amount of fat, for example

Total cost of diet: [pic]

So the generalized diet problem is an LP problem namely

min z=[pic]

subject to

[pic]

[pic]

[pic]

[pic]

[pic]

We can use summation notation to make this more compact as we shall see in the next slide:

min [pic]

s.t.

[pic]

[pic]

Using matrix notation, we can make it more compact still:

Let [pic] (c1,c2,…cn), [pic] ,[pic]

and [pic]

Then the LP problem becomes

min [pic]

s.t.

[pic]

[pic]

The general diet problem is actually a special case of the general linear production model.

C Prototype Example – The Reddy Mikks Co.(Example 1.5)

The Reddy Mikks Co. owns a small paint factory that produces both interior and exterior house paints for wholesale distribution. Two base materials A and B are required to produce the paint. The maximum availability of A is 6 tons per day and that of B is 8 tons per day. The daily requirements of the materials per ton of exterior and interior paint are summarized in Table 1 below.

| |Tons of raw material per ton of |Max. available |

| |Exterior paint |Interior Paint |(tons/day) |

|Raw material A |1 |2 |6 |

|Raw material B |2 |1 |8 |

table i

A market survey has established that the daily demand for interior paint cannot exceed that of exterior paint by more than 1 ton. The survey also shows that the maximum demand for interior paint is limited to 2 tons per day.

The wholesale price per ton is $3,000 for exterior paint and $2,000 for interior paint.

How much exterior pant and interior paint should the company produce daily to maximize gross income?

Remark: This problem is also an example of a general linear production model.

Let xI=# tons of interior paint to be produced per day

and xE=# tons of exterior paint to be produced per day

mat A: xE+2xI ≤ 6 (1)

mat B: 2xE+xI ≤ 8 (2)

nonnegativity assumption: xI≥ 0, xE≥ 0

marketing dept.: xI–xE ≤ 1 (3)

xI ≤ 2 (4)

Gross revenue (in thouands of $): 3xE+2xI

LP problem max z=3xE+2xI

s.t.

xE+2xI ≤ 6 (1)

2xE+xI ≤ 8 (2)

–xE + xI ≤ 1 (3)

xI ≤ 2 (4)

xE ≥ 0, xI ≥ 0

D. General Linear Production Model (Example 1.6)

Def. 1.11 m goods G1,G2,…,Gm An activity is a set of numbers

[pic] where [pic] denotes the amount of Gi used in a unit of the activity .

a. if (i≤ 0, then Gi is called an input of the activity

b. if (i≥ 0, then Gi is called an output of the activity

Def. 1.12 a linear production model is a set of activities P1,P2,…,Pn such that multiplying the inputs by a constant multiplies the outputs by the same constant and such that a sum of two input vectors yields an output which is the sum of the individual output vectors

[pic]

[pic] or [pic] is called the production matrix for the general linear production model. Often we take [pic]

as the production matrix, an m x n matrix so that we can write

[pic] as the output vector.

Example 1.7 (of a linear production model – baking a cake and other pastries)

1. G1,G2,…Gm are food inputs (flour, eggs, sugar, etc.)

2. P1,P2,…,Pn correspond to different recipes for different cakes and pastry

3. [pic] is the production matrix.

Example 1.8 (Chemical Reaction with/without catalyst)

1. if (i≤ 0, then Gi is called an input of the reaction

2. if (i≥ 0, then Gi is called an output of the reaction

3. if Gi is a catalyst in reaction j, then we would have (ij=0, since the amount of the input and output are the same but opposite in sign. To avoid this difficulty, we would introduce a

fictitious output [pic] which is the same as Gi so that we can have an input of the catalyst Gi and an equal but positive output of the same catalyst.

Def. 1.13: in a linear production model, the activity Pi is being operated at level or intensity xi if each of its inputs are given by [pic] or equivalently, if its outputs are xi multiplied by the outputs of the input vector ((i1,… (im).

Def. 1.14: A set of nonnegative intensities (x1,x2,..,xn) for P is called a production schedule for P.

To show that some of the problems we have considered are examples of production problems, we will establish the appropriate dictionaries:

For the Diet Problem:

goods = nutrients N1,N2,…,Nm

activity Pi = consumption of a unit food Fi

Production Matrix

[pic] actually use [pic]

production schedule = (x1,x2,…,xn) = diet

For the Reddy Mikks Co. problem:

goods = material A, material B, ext paint, int paint

activities = production of exterior paint

production of interior paint

Production matrix

[pic]

production schedule = (xE,xI)

Taking the transpose yields

[pic]

[pic]

Similar for rest of inequalities.

Example 1.9: Production to meet given demand at minimum cost

1. P a linear production model

a. (j = demand for ( # units desired of) Gj

b. ci = cost of operating Pi at unit level

c. (x1,…,xn) = the production schedule

We want (x1,…,xn) so that

(1) xi ≥ 0 for i=1,…,n

(2) [pic] for j = 1,…,m

(3) [pic] is minimized

Example 1.10: Maximize income from given production (i.e. from fixed supplies)

Essentially the same setup as Example 1.9 except here

ci = income associated with activity Pi

(j = fixed supply of the jth good

We want a production schedule (x1,…,xn) such that total income is maximized

(1) xi ≥ 0 for i=1,…,n

(2) [pic]

E. Feasible Region

Def. 1.14: The feasible region for a problem is the set of points which satisfy the constraints of the problem

Example (Reddy Mikks problem)

|xI | | | | | |

ABCDEF is the feasible region for the Reddy Mikks Co. problem

F. Convex Set

Def. 1.15: A set C is convex iff for any [pic] and any real number [pic] , [pic].

convex

not convex

Def. 1.16: a point [pic] of a convex set C is called an extreme point of C, iff whenever [pic] for [pic] and [pic]

then [pic] .

Theorem 1.1: The feasible region for an LP problem is a convex set.

We will show that the feasible region for the Reddy Mikks Co. LP is a convex set.

Suppose (xE,xI) and (x'E,x'I) are two feasible solutions.

Note: The difference between a feasible solution and a solution to the LP problem is that while both may be implemented, the feasible solution satisfies the constraints; e.g. it may be possible to run a computer with the cpu running at a clock speed of a or 2a. While the former may satisfy the heat constraints and other constraints, the latter may not but the computer may run (for a time) at both speeds.

Let [pic] .

Let [pic] . That is, we are taking

[pic] , a general convex combination of

(xE,xI) and (x'E,x'I). Is [pic] in the feasible region ?

Check: (1) [pic]

so the first inequality holds.

Check (2): [pic]

so (2) holds.

Check (3):

[pic]

so (3) holds.

Check (4): [pic]

Furthermore, [pic]

since [pic] , xE≥ 0, [pic] and [pic]

Similarly [pic] so we have shown that [pic] is a feasibe solution for the LP problem.

Remark: The proof of the theorem follows similar lines except that one uses general forms of the constraints.

Theorem 1.2: There exists an extreme point optimal solution to an LP problem whenever a finite optimal solution exists.

Proof: deferred

end of section 1

-----------------------

If YES, solution to Real World Problem

Real World Problem

If NO, feedback to MODEL.

Does it fit the real world problem we staVi[pic]Xi[pic]zi[pic]„i[pic]†i[pic]´i[pic]¶i[pic]¸i[pic]ºi[pic]¼i[pic]Äi[pic]Èi[pic]Êi[pic]èi[pic]êi[pic]þi[pic]j[pic]hAx[?]hAx[?]:?B*EHRHdaJ,phÿhAx[?]B*EHRHdaJ,ph€€-hAx[?]>*[pic]B*EHRHdaJ,ph€€$hŽqsh˜=m>*[pic]B*EHRHdaJ,ph€€hŽqsB*EHRHdaJ,ph€€-hŽqs>*[pic]B*EHRHdaJ,ph€€hKCh˜=mEHRrted with or are the assumptions we made too simplistic?

Mathematical Model

(system of equations, constraints, inequalities, etc.)

Analysis of Mathematical Model

Interpretation of Mathematical Results

xI–xE=1 (3)

2xE+xI = 8 (2)

xI = 2 (4)

C

E

D

F

B

xE+2xI = 6 (1)

A

................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download