Operations Research 7th Edition HAMDY A - IARE

Transcription

INSTITUTE OF AERONAUTICAL ENGINEERING(Autonomous)Dundigal, Hyderabad - 500 043PREPARED BY:A. SOMAIAH, ASST. PROFESSORT. VANAJA, ASST. PROFESSORDEPT. OF MECHANICAL ENGINEERING1

SyllabusUNIT-IDevelopment – Definition– Characteristics and Phases – Types ofmodels - Operations Research models – applications.Allocation: Linear Programming Problem Formulation – Graphicalsolution – Simplex method – Artificial variables techniques: Two–phase method, Big-M method.UNIT-IITransportation Problem - Formulation – Optimal solution,unbalanced transportation problem – Degeneracy.Assignment problem – Formulation – Optimal solution – Variants ofAssignment Problem- Traveling Salesman problem.2

UNIT-IIISequencing - Introduction – Flow –Shop sequencing – n jobs throughtwo machines – n jobs through three machines – Job shop sequencing –two jobs through „m‟ machines.Replacement: Introduction – Replacement of items that deterioratewith time – when money value is not counted and counted –Replacement of items that fail completely, Group Replacement.UNIT-IVTheory Of Games: Introduction – Terminology - Solution of gameswith saddle points and without saddle points – 2 2 games – dominanceprinciple – m X 2 & 2 X n games - Graphical method.Inventory: Introduction – Single item – Deterministic models –Purchase inventory models with one price break and multiple pricebreaks – Stochastic models – demand may be discrete variable orcontinuous variable – Single period model and no setup cost.3

UNIT-VWaiting Lines: Introduction – Terminology - Single Channel –Poisson arrivals and exponential service times – with infinitepopulation and finite population models– Multichannel – Poissonarrivals and exponential service times with infinite population.Dynamic Programming: Introduction –Terminology - Bellman‟sPrinciple of optimality –Applications of dynamic programming –shortest path problem – linear programming problem.Simulation: Introduction, Definition, types of simulation models,steps involved in the simulation process - Advantages andDisadvantages – Application of Simulation to queuing andinventory.4

As its name implies, operations research involves“research on operations.” Thus, operations research isapplied to problems that concern how to conduct andcoordinate the operations (i.e., the activities) withinan organization .The nature of the organization is essentiallyimmaterial, in fact, OR has been applied extensivelyin such diverse areas as manufacturing, transportation,construction, telecommunications, financial planning,health care, the military, and public services, to namejust a few .5

Theprocess begins by carefully observing andformulating the problem, including gathering allrelevant data. Then construct a scientific model torepresent the real problem ,while explaining itsobjectives with the system constraints.It attempts to resolve the conflicts of interest amongthe components of the organization in a way that isbest for the organization as a whole. 6

Operations Research came into existence duringWorld War II, when the British and Americanmilitary management called upon a group ofscientists with diverse educational backgroundnamely, Physics, Biology, Statistics, Mathematics,Psychology, etc., to develop and apply a scientificapproach to deal with strategic and tactical problemsof various military operations.7

HISTORY OF OPERATIONS RESEARCHThe objective was to allocate scarce resources in aneffective manner to various military operations and tothe activities within each operation. The nameOperations Research (OR) came directly from thecontext in which it was used and developed, viz.,research on military operations8

During the 50s, Operations Research achieved recognitionas a subject for study in the universities. Since then thesubject has gained increasing importance for the students ofManagement, Public Administration, Behavioral Sciences,Engineering, Mathematics, Economics and Commerce, etc.Today, Operations Research is also widely used in regionalplanning, transportation, public health, communication etc.,besides military and industrial operations.9

In India, Operations Research came into existence in1949 with the opening of an Operations Research Unitat the Regional Research Laboratory at Hyderabadand also in the Defence Science Laboratory at Delhiwhich devoted itself to the problems of stores,purchase and planning. For national planning andsurvey, an Operations Research Unit was establishedin 1953 at the India Statistical Institute, Calcutta. In1957, Operations Research Society of India wasformed. Almost all the universities and institutions inIndia are offering the input of Operations Research intheir curriculum .10

OperationsResearch (OR)It is a scientific approach to determinethe optimum (best) solution to a decisionproblem under the restriction of limitedresources,usingthemathematicaltechniques to model, analyze, and solve theproblem11

Phases of OR Definition of the problemModel ConstructionSolution of the modelModel validityImplementation of the solution12

1.2.3.Decision VariablesObjective FunctionConstraints18

A company manufactures two products A&B. with 4 &3 units of price. A&B take 3&2 minutes respectively tobe machined. The total time available at machiningdepartment is 800 hours (100 days or 20 weeks). Amarket research showed that at least 10000 units of Aand not more than 6000 units of B are needed. It isrequired to determine the number of units of A&B to beproduced to maximize profit.22

Decision variables Objective FunctionX1 number of units produced of A.X2 number of units produced of B.Maximize Z 4 X1 3 X2 Constraints3 X1 2 X 2X1X2X1,X2 800x60 10000 6000 023

A farmer is interested in feeding his cattle at minimumcost. Two feeds are used A&B. Each cow must get atleast 400 grams/day of protein, at least 800 grams/dayof carbohydrates, and not more than 100 grams/day offat. Given that A contains 10% protein, 80%carbohydrates and 10% fat while B contains 40%protein, 60% carbohydrates and no fat. A costs Rs20/kg, and B costs Rs 50 /kg. Formulate the problemto determine the optimum amount of each feed tominimize cost.24

Decision variables Objective FunctionX1 weight of feed A kg/day/animalX2 weight of feed B kg/day/animalMinimize Z 20X1 50X2 ConstraintsProtein0.1 X1 0.4 X2Carbohydrates 0.8 X1 0.6 X2Fats0.1 X1X1,X2Cost function 0.40.8 00.125

An iron ore from 4 mines will be blended.The analysis has shown that, in order toobtain suitable tensile properties, minimumrequirements must be met for 3 basicelements A, B, and C. Each of the 4 minescontains different amounts of the 3 elements(see the table). Formulate to find the leastcost (Minimize) blend for one ton of ironore.26

Decision variablesX1 Fraction of ton to be selected from mine number 1X2 Fraction of ton to be selected from mine number 2X3 Fraction of ton to be selected from mine number 3X4 Fraction of ton to be selected from mine number 4 Objective FunctionMinimize Z 800 X1 400 X2 600 X3 500 X4 Constraints10 X1 3X2 8X3 2X490 X1 150 X2 75 X3 175 X445 X1 25 X2 20 X3 37 X4X1 X2 X3 X4X1, X2, X3, X4510 30 1 0 28

A company has 2 grades of inspectors 1&2. It isrequired that at least 1800 pieces be inspected per 8hour day. Grade 1 inspectors can check pieces at therate of 25 per hour with an accuracy of 98%. Grade 2inspectors can check at the rate of 15 pieces per hourwith an accuracy of 95%. Grade 1 costs 4 L.E/hour,grade 2 costs 3 L.E/hour. Each time an error is made byan inspector costs the company 2 L.E. There are 8grade 1 and 10 grade 2 inspectors available. Thecompany wants to determine the optimal assignment ofinspectors which will minimize the total cost ofinspection/day.29

Decision variablesX1 Number of grade 1 inspectors/day.X2 Number of grade 2 inspectors/day. Objective FunctionCost of inspection Cost of error Inspector salary/dayCost of grade 1/hour 4 (2 X 25 X 0.02) 5 L.ECost of grade 2/hour 3 (2 X 15 X 0.05) 4.5 L.EMinimize Z 8 (5 X1 4.5 X2) 40 X1 36 X2 ConstraintsX18(25) X1 200 X1 X1, X2 8(15)X2120 X2X2 810 18001800030

A company produces paper rolls with astandard width of 20 feet. Each special customerorders with different widths are produced byslitting the standard rolls. Typical orders aresummarized in the following tables.31

Formulate to minimize the trim loss and the numberof rolls needed to satisfy the order.32

Decision variablesX j Number of standard rolls to be cut according to setting jj 1, 2, 3, 4, 5, 6Number of 5 feet rolls produced 2 X2 2 X3 4 X4 X5Number of 7 feet rolls produced X1 X2 2 X5Number of 9 feet rolls produced X1 X3 2 X6Let Y1, Y2, Y3 be the number of surplus rolls of the 5, 7, 9 feetrolls thus Y1 2 X2 2 X3 4 X4 X5 - 150 Y2 X1 X2 2 X5 - 200 Y3 X1 X3 2 X6 - 300The total trim losses L (4X1 3 X2 X3 X5 2 X6 5Y1 7Y2 9Y3)*Where L is the length of the standard roll.34

Objective FunctionMinimize Z L(4X1 3 X2 X3 X5 2 X6 5Y1 7Y2 9Y3) Constraints2 X2 2 X3 4 X4 X5 - Y1 150X1 X2 2 X5 - Y2 200X1 X3 2 X6 - Y3 300X1, X2, X3, X4, X5, X6 0Y1, Y2, Y3 035

Maximize Z C1X1 C2X2 CnXn ConstraintsA11X1 A12X2 A1nXnA21X1 A22X2 A2nXn.Am1X1 Am2X2 . AmnXnX1, X2, , Xn B1B2 Bm 036

Maximizen c xz jjj 1 Constraintsn a xijj j 1xj 0bi, i 1, 2 ,., m, j 1, 2 ,., n37

A SolutionAny specifications of values of X1, X2, , Xn is called a solution. A Feasible SolutionIs a solution for which all the constraints aresatisfied. An Optimal SolutionIs a feasible solution that has the most favorable value of theobjective function (largest of maximize or smallest for minimize)39

Construction of the LP model Example 1: The Reddy Mikks CompanyReddy Mikks produces both interior and exterior paintsfrom two raw materials, M1&M2. The following tableprovides the basic data of the problem.41

A market survey indicates that the daily demand forinterior paint cannot exceed that of exterior paint bymore than 1 ton. Also, the maximum daily demand ofinterior paint is 2 ton.Reddy Mikks wants to determine the optimum (best)product mix of interior and exterior paints thatmaximizes the total daily profit42

Decision variablesX1 Tons produced daily of exterior paint.X2 Tons produced daily of interior paint.Objective FunctionMaximize Z 5 X1 4 X2Constraints6 X1 4 X224X1 2 X26 - X1 X21 2X2X1, X20 43

Any solution that satisfies all the constraints of themodel is a feasible solution. For example, X1 3 tonsand X2 1 ton is a feasible solution. We have aninfinite number of feasible solutions, but we areinterested in the optimum feasible solution that yieldsthe maximum total profit.44

The graphical solution is valid only for two-variableproblem .The graphical solution includes two basic steps:1. The determination of the solution spacethat defines the feasible solutions thatsatisfy all the constraints.2. The determination of the optimumsolution from among all the points in thefeasible solution space.45

46

47

ABCDEF consists of an infinite number of points; weneed a systematic procedure that identifies theoptimum solutions. The optimum solution isassociated with a corner point of the solution space.To determine the direction in which the profitfunction increases we assign arbitrary increasingvalues of 10 and 155 X1 4 X2 10And 5 X1 4 X2 15The optimum solution is mixture of 3 tons of exteriorand 1.5 tons of interior paints will yield a daily profitof 21000 .48

The Transportation Problem is a classic OperationsResearch problem where the objective is to determine theschedule for transporting goods from source todestination in a way that minimizes the shipping costwhile satisfying supply and demandconstraints.49

A typical Transportation Problem has thefollowing elements:1. Source(s)2. Destination(s)3. Weighted edge(s) showing cost oftransportation50

51

In many business situations, management needs toassign - personnel to jobs, - jobs to machines, machines to job locations, or - salespersons toterritories.Consider the situation of assigning n jobs to nmachines.When a job i ( 1,2,.,n) is assigned to machine j( 1,2, .n) that incurs a cost Cij.The objective is to assign the jobs to machines at theleast possible total cost.52

This situation is a special case of theTransportation Model And it is known as theassignment problem.Here, jobs represent “sources” and machinesrepresent “destinations.”The supply available at each source is 1 unitAnd demand at each destination is 1 unit.53

54

1. Arrivalprocess5. CustomerPopulation6. Servicediscipline2. Service timedistribution4. Waitingpositions 3. Number ofserversExample: students at a typical computer terminal roomwith a number of terminals. If all terminals are busy,the arriving students wait in a queue.55

A: Arrival processS: Service time distributionm: Number of serversB: Number of buffers (system capacity)K: Population size, andSD: Service discipline56

Arrival times:Interarrival times:tj form a sequence of Independent and IdenticallyDistributed (IID) random variablesThe most common arrival process: Poisson arrivals Inter-arrival times are exponential IID Poisson arrivals Notation: M Memoryless PoissonE ErlangH Hyper-exponentialG General Results valid for all distributions57

Time each student spends at the terminalService times are IIDDistribution: M, E, H, or GDevice Service center QueueBuffer Waiting positions58

First-Come-First-Served (FCFS)Last-Come-First-Served (LCFS)Last-Come-First-Served with Preempt and Resume(LCFS-PR)Round-Robin (RR) with a fixed quantum.Small Quantum Processor Sharing (PS)Infinite Server: (IS) fixed delayShortest Processing Time fir

Operations Research (OR) It is a scientific approach to determine the optimum (best) solution to a decision problem under the restriction of limited resources, using the mathematical techniques to model, analyze, and solve the problem 11