OPERATIONS RESEARCH LECTURE NOTES

operations research linear programming lecture notes and how operations research helps in decision making pdf free download
MarthaKelly Profile Pic
MarthaKelly,Mexico,Researcher
Published Date:12-07-2017
Your Website URL(Optional)
Comment
OPERATIONS RESEARCH LECTURE NOTES (2016-2017) Y. İlker Topcu, Ph.D. & Özgür Kabak, Ph.D. Acknowledgements: We would like to acknowledge Prof. W.L. Winston's "Operations Research: Applications and Algorithms" and Prof. J.E. Beasley's lecture notes which greatly influence these notes... We retain responsibility for all errors and would love to hear from visitors of this site Istanbul Technical University OR/MS team Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) MHN502E & ITY512E 2016-2017 CONTENTS 1. INTRODUCTION TO OR ..................................................................................... 1 1.1 TERMINOLOGY ...................................................................................................... 1 1.2 THE METHODOLOGY OF OR ............................................................................. 1 1.3 HISTORY OF OR .................................................................................................... 2 2. BASIC OR CONCEPTS ...................................................................................... 6 3. LINEAR PROGRAMMING ................................................................................ 11 3.1 FORMULATING LP ............................................................................................... 13 3.1.1 Giapetto Example .......................................................................................... 13 3.1.2 Advertisement Example ................................................................................ 14 3.1.3 Diet Example .................................................................................................. 15 3.1.4 Post Office Example ...................................................................................... 16 3.1.5 Sailco Example .............................................................................................. 16 3.1.6 Customer Service Level Example ............................................................... 17 3.2 SOLVING LP .......................................................................................................... 19 3.2.1 LP Solutions: Four Cases............................................................................. 19 3.2.2 The Graphical Solution ................................................................................. 19 3.2.3 The Simplex Algorithm .................................................................................. 24 3.2.4 The Big M Method ......................................................................................... 30 3.3 DUALITY ................................................................................................................. 33 3.3.1 Primal – Dual .................................................................................................. 33 3.3.2 Finding the Dual of an LP ............................................................................. 33 3.3.3 The Dual Theorem......................................................................................... 35 3.3.4 Economic Interpretation ................................................................................ 36 3.4 SENSITIVITY ANALYSIS ..................................................................................... 38 3.4.1 Reduced Cost................................................................................................. 38 3.4.2 Shadow Price ................................................................................................. 38 3.4.3 Conceptualization .......................................................................................... 38 3.4.4 Utilizing Lindo Output for Sensitivity ........................................................... 39 3.4.5 Some important equations ........................................................................... 40 3.4.6 Utilizing Simplex for Sensitivity .................................................................... 41 3.4.7 Duality and Sensitivity Analysis ................................................................... 43 3.4.8 The 100% Rule .............................................................................................. 43 Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) i MHN502E & ITY512E 2016-2017 4. TRANSPORTATION PROBLEMS .................................................................... 44 4.1 FORMULATING TRANSPORTATION PROBLEMS ....................................... 44 4.1.1 Formulating Balanced Transportation Problem ........................................ 45 4.1.2 Balancing an Unbalanced Transportation Problem ................................. 46 4.2 FINDING BFS FOR TRANSPORT’N PROBLEMS .......................................... 47 4.2.1 Northwest Corner Method ............................................................................ 48 4.2.2 Minimum Cost Method .................................................................................. 50 4.2.3 Vogel’s Method .............................................................................................. 51 4.3 THE TRANSPORTATION SIMPLEX METHOD ............................................... 53 4.4 TRANSSHIPMENT PROBLEMS ........................................................................ 56 4.5 ASSIGNMENT PROBLEMS ................................................................................ 59 4.5.1 LP Representation ......................................................................................... 59 4.5.2 Hungarian Method ......................................................................................... 59 5. INTEGER PROGRAMMING ............................................................................. 63 5.1 FORMULATING IP ................................................................................................ 64 5.1.1 Budgeting Problems ...................................................................................... 64 5.1.2 Knapsack Problems ...................................................................................... 66 5.1.3 Fixed Charge Problems ................................................................................ 66 5.1.4 Membership in Specified Subsets............................................................... 70 5.1.5 Either-Or Constraints .................................................................................... 72 5.1.6 If-Then Constraints ........................................................................................ 73 5.1.7 Traveling Salesperson Problems ................................................................ 74 5.2 SOLVING IP ........................................................................................................... 75 5.2.1 Categorization ................................................................................................ 75 5.2.2 LP Relaxation ................................................................................................. 76 5.2.3 Enumeration ................................................................................................... 77 5.2.4 The Branch-and-Bound Method .................................................................. 78 5.2.5 Cutting Planes ................................................................................................ 94 Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) ii MHN502E & ITY512E 2016-2017 1. INTRODUCTION TO OR 1.1 TERMINOLOGY The British/Europeans refer to "operational research", the Americans to "operations research" - but both are often shortened to just "OR" (which is the term we will use). Another term which is used for this field is "management science" ("MS"). The Americans sometimes combine the terms OR and MS together and say "OR/MS" or "ORMS". Yet other terms sometimes used are "industrial engineering" ("IE"), "decision science" ("DS"), and “problem solving”. In recent years there has been a move towards a standardization upon a single term for the field, namely the term "OR". “Operations Research (Management Science) is a scientific approach to decision making that seeks to best design and operate a system, usually under conditions requiring the allocation of scarce resources.” A system is an organization of interdependent components that work together to accomplish the goal of the system. 1.2 THE METHODOLOGY OF OR When OR is used to solve a problem of an organization, the following seven step procedure should be followed: Step 1. Formulate the Problem OR analyst first defines the organization's problem. Defining the problem includes specifying the organization's objectives and the parts of the organization (or system) that must be studied before the problem can be solved. Step 2. Observe the System Next, the analyst collects data to estimate the values of parameters that affect the organization's problem. These estimates are used to develop (in Step 3) and evaluate (in Step 4) a mathematical model of the organization's problem. Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 1 MHN502E & ITY512E 2016-2017 Step 3. Formulate a Mathematical Model of the Problem The analyst, then, develops a mathematical model (in other words an idealized representation) of the problem. In this class, we describe many mathematical techniques that can be used to model systems. Step 4. Verify the Model and Use the Model for Prediction The analyst now tries to determine if the mathematical model developed in Step 3 is an accurate representation of reality. To determine how well the model fits reality, one determines how valid the model is for the current situation. Step 5. Select a Suitable Alternative Given a model and a set of alternatives, the analyst chooses the alternative (if there is one) that best meets the organization's objectives. Sometimes the set of alternatives is subject to certain restrictions and constraints. In many situations, the best alternative may be impossible or too costly to determine. Step 6. Present the Results and Conclusions of the Study In this step, the analyst presents the model and the recommendations from Step 5 to the decision making individual or group. In some situations, one might present several alternatives and let the organization choose the decision maker(s) choose the one that best meets her/his/their needs. After presenting the results of the OR study to the decision maker(s), the analyst may find that s/he does not (or they do not) approve of the recommendations. This may result from incorrect definition of the problem on hand or from failure to involve decision maker(s) from the start of the project. In this case, the analyst should return to Step 1, 2, or 3. Step 7. Implement and Evaluate Recommendation If the decision maker(s) has accepted the study, the analyst aids in implementing the recommendations. The system must be constantly monitored (and updated dynamically as the environment changes) to ensure that the recommendations are enabling decision maker(s) to meet her/his/their objectives. 1.3 HISTORY OF OR (Prof. Beasley’s lecture notes) OR is a relatively new discipline. Whereas 70 years ago it would have been possible to study mathematics, physics or engineering (for example) at university it would not have been possible to study OR, indeed the term OR did not exist then. It was only Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 2 MHN502E & ITY512E 2016-2017 really in the late 1930's that operational research began in a systematic fashion, and it started in the UK. Early in 1936 the British Air Ministry established Bawdsey Research Station, on the east coast, near Felixstowe, Suffolk, as the centre where all pre-war radar experiments for both the Air Force and the Army would be carried out. Experimental radar equipment was brought up to a high state of reliability and ranges of over 100 miles on aircraft were obtained. It was also in 1936 that Royal Air Force (RAF) Fighter Command, charged specifically with the air defense of Britain, was first created. It lacked however any effective fighter aircraft - no Hurricanes or Spitfires had come into service - and no radar data was yet fed into its very elementary warning and control system. It had become clear that radar would create a whole new series of problems in fighter direction and control so in late 1936 some experiments started at Biggin Hill in Kent into the effective use of such data. This early work, attempting to integrate radar data with ground based observer data for fighter interception, was the start of OR. The first of three major pre-war air-defense exercises was carried out in the summer of 1937. The experimental radar station at Bawdsey Research Station was brought into operation and the information derived from it was fed into the general air-defense warning and control system. From the early warning point of view this exercise was encouraging, but the tracking information obtained from radar, after filtering and transmission through the control and display network, was not very satisfactory. In July 1938 a second major air-defense exercise was carried out. Four additional radar stations had been installed along the coast and it was hoped that Britain now had an aircraft location and control system greatly improved both in coverage and effectiveness. Not so The exercise revealed, rather, that a new and serious problem had arisen. This was the need to coordinate and correlate the additional, and often conflicting, information received from the additional radar stations. With the out-break of war apparently imminent, it was obvious that something new - drastic if necessary - had to be attempted. Some new approach was needed. Accordingly, on the termination of the exercise, the Superintendent of Bawdsey Research Station, A.P. Rowe, announced that although the exercise had again demonstrated the technical feasibility of the radar system for detecting aircraft, its operational achievements still fell far short of requirements. He therefore proposed that a crash program of research into the operational - as opposed to the technical - Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 3 MHN502E & ITY512E 2016-2017 aspects of the system should begin immediately. The term "operational research" RESEARCH into (military) OPERATIONS was coined as a suitable description of this new branch of applied science. The first team was selected from amongst the scientists of the radar research group the same day. In the summer of 1939 Britain held what was to be its last pre-war air defense exercise. It involved some 33,000 men, 1,300 aircraft, 110 antiaircraft guns, 700 searchlights, and 100 barrage balloons. This exercise showed a great improvement in the operation of the air defense warning and control system. The contribution made by the OR teams was so apparent that the Air Officer Commander-in-Chief RAF Fighter Command (Air Chief Marshal Sir Hugh Dowding) requested that, on the outbreak of war, they should be attached to his headquarters at Stanmore. On May 15th 1940, with German forces advancing rapidly in France, Stanmore Research Section was asked to analyze a French request for ten additional fighter squadrons (12 aircraft a squadron) when losses were running at some three squadrons every two days. They prepared graphs for Winston Churchill (the British Prime Minister of the time), based upon a study of current daily losses and replacement rates, indicating how rapidly such a move would deplete fighter strength. No aircraft were sent and most of those currently in France were recalled. This is held by some to be the most strategic contribution to the course of the war made by OR (as the aircraft and pilots saved were consequently available for the successful air defense of Britain, the Battle of Britain). In 1941 an Operational Research Section (ORS) was established in Coastal Command which was to carry out some of the most well-known OR work in World War II. Although scientists had (plainly) been involved in the hardware side of warfare (designing better planes, bombs, tanks, etc) scientific analysis of the operational use of military resources had never taken place in a systematic fashion before the Second World War. Military personnel, often by no means stupid, were simply not trained to undertake such analysis. These early OR workers came from many different disciplines, one group consisted of a physicist, two physiologists, two mathematical physicists and a surveyor. What such people brought to their work were "scientifically trained" minds, used to querying assumptions, logic, exploring hypotheses, devising experiments, collecting data, analyzing numbers, etc. Many too were of high intellectual caliber (at least four Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 4 MHN502E & ITY512E 2016-2017 wartime OR personnel were later to win Nobel prizes when they returned to their peacetime disciplines). By the end of the war OR was well established in the armed services both in the UK and in the USA. OR started just before World War II in Britain with the establishment of teams of scientists to study the strategic and tactical problems involved in military operations. The objective was to find the most effective utilization of limited military resources by the use of quantitative techniques. Following the end of the war OR spread, although it spread in different ways in the UK and USA. You should be clear that the growth of OR since it began (and especially in the last 30 years) is, to a large extent, the result of the increasing power and widespread availability of computers. Most (though not all) OR involves carrying out a large number of numeric calculations. Without computers this would simply not be possible. Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 5 MHN502E & ITY512E 2016-2017 2. BASIC OR CONCEPTS "OR is the representation of real-world systems by mathematical models together with the use of quantitative methods (algorithms) for solving such models, with a view to optimizing." We can also define a mathematical model as consisting of:  Decision variables, which are the unknowns to be determined by the solution to the model.  Constraints to represent the physical limitations of the system  An objective function  An optimal solution to the model is the identification of a set of variable values which are feasible (satisfy all the constraints) and which lead to the optimal value of the objective function. 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. Two Mines Example The Two Mines Company own two different mines that produce an ore which, after being crushed, is graded into three classes: high, medium and low-grade. The company has contracted to provide a smelting plant with 12 tons of high-grade, 8 tons of medium-grade and 24 tons of low-grade ore per week. The two mines have different operating characteristics as detailed below. Mine Cost per day (£'000) Production (tons/day) High Medium Low X 180 6 3 4 Y 160 1 1 6 Consider that mines cannot be operated in the weekend. How many days per week should each mine be operated to fulfill the smelting plant contract? Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 6 MHN502E & ITY512E 2016-2017 Guessing To explore the Two Mines problem further we might simply guess (i.e. use our judgment) how many days per week to work and see how they turn out.  work one day a week on X, one day a week on Y This does not seem like a good guess as it results in only 7 tones a day of high- grade, insufficient to meet the contract requirement for 12 tones of high-grade a day. We say that such a solution is infeasible.  work 4 days a week on X, 3 days a week on Y This seems like a better guess as it results in sufficient ore to meet the contract. We say that such a solution is feasible. However it is quite expensive (costly). We would like a solution which supplies what is necessary under the contract at minimum cost. Logically such a minimum cost solution to this decision problem must exist. However even if we keep guessing we can never be sure whether we have found this minimum cost solution or not. Fortunately our structured approach will enable us to find the minimum cost solution. Solution What we have is a verbal description of the Two Mines problem. What we need to do is to translate that verbal description into an equivalent mathematical description. In dealing with problems of this kind we often do best to consider them in the order:  Variables  Constraints  Objective This process is often called formulating the problem (or more strictly formulating a mathematical representation of the problem). Variables These represent the "decisions that have to be made" or the "unknowns". We have two decision variables in this problem: x = number of days per week mine X is operated y = number of days per week mine Y is operated Note here that x ≥ 0 and y ≥ 0. Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 7 MHN502E & ITY512E 2016-2017 Constraints It is best to first put each constraint into words and then express it in a mathematical form. ore production constraints - balance the amount produced with the quantity required under the smelting plant contract Ore High 6x + 1y ≥ 12 Medium 3x + 1y ≥ 8 Low 4x + 6y ≥ 24 days per week constraint - we cannot work more than a certain maximum number of days a week e.g. for a 5 day week we have x ≤ 5 y ≤ 5 Inequality constraints Note we have an inequality here rather than an equality. This implies that we may produce more of some grade of ore than we need. In fact we have the general rule: given a choice between an equality and an inequality choose the inequality For example - if we choose an equality for the ore production constraints we have the three equations 6x+y=12, 3x+y=8 and 4x+6y=24 and there are no values of x and y which satisfy all three equations (the problem is therefore said to be "over- constrained"). For example the values of x and y which satisfy 6x+y=12 and 3x+y=8 are x=4/3 and y=4, but these values do not satisfy 4x+6y=24. The reason for this general rule is that choosing an inequality rather than an equality gives us more flexibility in optimizing (maximizing or minimizing) the objective (deciding values for the decision variables that optimize the objective). Implicit constraints Constraints such as days per week constraint are often called implicit constraints because they are implicit in the definition of the variables. Objective Again in words our objective is (presumably) to minimize cost which is given by 180x + 160y Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 8 MHN502E & ITY512E 2016-2017 Hence we have the complete mathematical representation of the problem: minimize 180x + 160y subject to 6x + y ≥ 12 3x + y ≥ 8 4x + 6y ≥ 24 x ≤ 5 y ≤ 5 x, y ≥ 0 Some notes The mathematical problem given above has the form  all variables continuous (i.e. can take fractional values)  a single objective (maximize or minimize)  the objective and constraints are linear i.e. any term is either a constant or a 2 constant multiplied by an unknown (e.g. 24, 4x, 6y are linear terms but xy or x is a non-linear term) Any formulation which satisfies these three conditions is called a linear program (LP). We have (implicitly) assumed that it is permissible to work in fractions of days - problems where this is not permissible and variables must take integer values will be dealt with under Integer Programming (IP). Discussion This problem was a decision problem. We have taken a real-world situation and constructed an equivalent mathematical representation - such a representation is often called a mathematical model of the real-world situation (and the process by which the model is obtained is called formulating the model). Just to confuse things the mathematical model of the problem is sometimes called the formulation of the problem. Having obtained our mathematical model we (hopefully) have some quantitative method which will enable us to numerically solve the model (i.e. obtain a numerical solution) - such a quantitative method is often called an algorithm for solving the model. Essentially an algorithm (for a particular model) is a set of instructions which, when followed in a step-by-step fashion, will produce a numerical solution to that model. Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 9 MHN502E & ITY512E 2016-2017 Our model has an objective, that is something which we are trying to optimize. Having obtained the numerical solution of our model we have to translate that solution back into the real-world situation. "OR is the representation of real-world systems by mathematical models together with the use of quantitative methods (algorithms) for solving such models, with a view to optimizing." Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 10 MHN502E & ITY512E 2016-2017 3. LINEAR PROGRAMMING It can be recalled from the Two Mines example that the conditions for a mathematical model to be a linear program (LP) were:  all variables continuous (i.e. can take fractional values)  a single objective (minimize or maximize)  the objective and constraints are linear i.e. any term is either a constant or a constant multiplied by an unknown. LP's are important - this is because:  many practical problems can be formulated as LP's  there exists an algorithm (called the simplex algorithm) which enables us to solve LP's numerically relatively easily We will return later to the simplex algorithm for solving LP's but for the moment we will concentrate upon formulating LP's. Some of the major application areas to which LP can be applied are:  Work scheduling  Production planning & Production process  Capital budgeting  Financial planning  Blending (e.g. Oil refinery management)  Farm planning  Distribution  Multi-period decision problems o Inventory model o Financial models o Work scheduling Note that the key to formulating LP's is practice. However a useful hint is that common objectives for LP's are maximize profit/minimize cost. Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 11 MHN502E & ITY512E 2016-2017 There are four basic assumptions in LP:  Proportionality o The contribution to the objective function from each decision variable is proportional to the value of the decision variable (The contribution to the objective function from making four soldiers (43=12) is exactly four times the contribution to the objective function from making one soldier (3)) o The contribution of each decision variable to the LHS of each constraint is proportional to the value of the decision variable (It takes exactly three times as many finishing hours (2hrs3=6hrs) to manufacture three soldiers as it takes to manufacture one soldier (2 hrs))  Additivity o The contribution to the objective function for any decision variable is independent of the values of the other decision variables (No matter what the value of train (x2), the manufacture of soldier (x1) will always contribute 3x dollars to the objective function) 1 o The contribution of a decision variable to LHS of each constraint is independent of the values of other decision variables (No matter what the value of x1, the manufacture of x2 uses x2 finishing hours and x2 carpentry hours) st  1 implication: The value of objective function is the sum of the contributions from each decision variables. nd  2 implication: LHS of each constraint is the sum of the contributions from each decision variables.  Divisibility o Each decision variable is allowed to assume fractional values. If we actually can not produce a fractional number of decision variables, we use IP (It is acceptable to produce 1.69 trains)  Certainty o Each parameter is known with certainty Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 12 MHN502E & ITY512E 2016-2017 3.1 FORMULATING LP 3.1.1 Giapetto Example (Winston 3.1, p. 49) Giapetto's wooden soldiers and trains. Each soldier sells for 27, uses 10 of raw materials and takes 14 of labor & overhead costs. Each train sells for 21, uses 9 of raw materials, and takes 10 of overhead costs. Each soldier needs 2 hours finishing and 1 hour carpentry; each train needs 1 hour finishing and 1 hour carpentry. Raw materials are unlimited, but only 100 hours of finishing and 80 hours of carpentry are available each week. Demand for trains is unlimited; but at most 40 soldiers can be sold each week. How many of each toy should be made each week to maximize profits? Answer Decision variables completely describe the decisions to be made (in this case, by Giapetto). Giapetto must decide how many soldiers and trains should be manufactured each week. With this in mind, we define: x = the number of soldiers produced per week 1 x2 = the number of trains produced per week Objective function is the function of the decision variables that the decision maker wants to maximize (revenue or profit) or minimize (costs). Giapetto can concentrate on maximizing the total weekly profit (z). Here profit equals to (weekly revenues) – (raw material purchase cost) – (other variable costs). Hence Giapetto’s objective function is: Maximize z = 3x1 + 2x2 Constraints show the restrictions on the values of the decision variables. Without constraints Giapetto could make a large profit by choosing decision variables to be very large. Here there are three constraints: Finishing time per week Carpentry time per week Weekly demand for soldiers Sign restrictions are added if the decision variables can only assume nonnegative values (Giapetto can not manufacture negative number of soldiers or trains) Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 13 MHN502E & ITY512E 2016-2017 All these characteristics explored above give the following Linear Programming (LP) model max z = 3x1 + 2x2 (The Objective function) s.t. 2x + x 100 (Finishing constraint) 1 2 x1 + x2  80 (Carpentry constraint) x1  40 (Constraint on demand for soldiers) x1, x2 0 (Sign restrictions) A value of (x , x ) is in the feasible region if it satisfies all the constraints and sign 1 2 restrictions. Graphically and computationally we see the solution is (x1, x2) = (20, 60) at which z = 180. (Optimal solution) Report The maximum profit is 180 by making 20 soldiers and 60 trains each week. Profit is limited by the carpentry and finishing labor available. Profit could be increased by buying more labor. 3.1.2 Advertisement Example (Winston 3.2, p.61) Dorian makes luxury cars and jeeps for high-income men and women. It wishes to advertise with 1 minute spots in comedy shows and football games. Each comedy spot costs 50K and is seen by 7M high-income women and 2M high-income men. Each football spot costs 100K and is seen by 2M high-income women and 12M high-income men. How can Dorian reach 28M high-income women and 24M high- income men at the least cost? Answer The decision variables are x1 = the number of comedy spots x2 = the number of football spots The model of the problem: min z = 50x1 + 100x2 st 7x1 + 2x228 2x + 12x 24 1 2 x1, x20 Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 14 MHN502E & ITY512E 2016-2017 The graphical solution is z = 320 when (x1, x2) = (3.6, 1.4). From the graph, in this problem rounding up to (x , x ) = (4, 2) gives the best integer solution. 1 2 Report The minimum cost of reaching the target audience is 400K, with 4 comedy spots and 2 football slots. The model is dubious as it does not allow for saturation after repeated viewings. 3.1.3 Diet Example (Winston 3.4., p. 70) Ms. Fidan’s diet requires that all the food she eats come from one of the four “basic food groups“. At present, the following four foods are available for consumption: brownies, chocolate ice cream, cola, and pineapple cheesecake. Each brownie costs 0.5, each scoop of chocolate ice cream costs 0.2, each bottle of cola costs 0.3, and each pineapple cheesecake costs 0.8. Each day, she must ingest at least 500 calories, 6 oz of chocolate, 10 oz of sugar, and 8 oz of fat. The nutritional content per unit of each food is shown in Table. Formulate an LP model that can be used to satisfy her daily nutritional requirements at minimum cost. Calories Chocolate Sugar Fat (ounces) (ounces) (ounces) Brownie 400 3 2 2 Choc. ice cream (1 scoop) 200 2 2 4 Cola (1 bottle) 150 0 4 1 Pineapple cheesecake (1 piece) 500 0 4 5 Answer The decision variables: x : number of brownies eaten daily 1 x2: number of scoops of chocolate ice cream eaten daily x3: bottles of cola drunk daily x : pieces of pineapple cheesecake eaten daily 4 The objective function (the total cost of the diet in cents): min w = 50x1 + 20x2 + 30x3 + 80x4 Constraints: 400x + 200x + 150x + 500x 500 (daily calorie intake) 1 2 3 4 3x1 + 2x2 6 (daily chocolate intake) 2x1 + 2x2 + 4x3 + 4x4 10 (daily sugar intake) Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 15 MHN502E & ITY512E 2016-2017 2x1 + 4x2 + x3 + 5x4 8 (daily fat intake) x ≥ 0, i = 1, 2, 3, 4 (Sign restrictions) i Report The minimum cost diet incurs a daily cost of 90 cents by eating 3 scoops of chocolate and drinking 1 bottle of cola (w = 90, x = 3, x = 1) 2 3 3.1.4 Post Office Example (Winston 3.5, p.74) A PO requires different numbers of employees on different days of the week. Union rules state each employee must work 5 consecutive days and then receive two days off. Find the minimum number of employees needed. Mon Tue Wed Thur Fri Sat Sun Staff Needed 17 13 15 19 14 16 11 Answer The decision variables are x ( of employees starting on day i) i Mathematically we must min z = x1 + x2 + x3 + x4 + x5 + x6 + x7 s.t. x1 + x4 + x5 + x6 + x7 ≥ 17 x1 + x2 + x5 + x6 + x7 ≥ 13 x1 + x2 + x3 + x6 + x7 ≥ 15 x1 + x2 + x3 + x4 + x7 ≥ 19 x1 + x2 + x3 + x4 + x5 ≥ 14 + x2 + x3 + x4 + x5 + x6 ≥ 16 + x3 + x4 + x5 + x6 + x7 ≥ 11 x ≥ 0, t t The solution is (xi) = (4/3, 10/3, 2, 22/3, 0, 10/3, 5) giving z = 67/3. We could round this up to (x ) = (2, 4, 2, 8, 0, 4, 5) giving z = 25 (may be wrong). i However restricting the decision var.s to be integers and using Lindo again gives (xi) = (4, 4, 2, 6, 0, 4, 3) giving z = 23. 3.1.5 Sailco Example (Winston 3.10, p. 99) Sailco must determine how many sailboats to produce in the next 4 quarters. The demand is known to be 40, 60, 75, and 25 boats. Sailco must meet its demands. At st the beginning of the 1 quarter Sailco starts with 10 boats in inventory. Sailco can produce up to 40 boats with regular time labor at 400 per boat, or additional boats at Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 16 MHN502E & ITY512E 2016-2017 450 with overtime labor. Boats made in a quarter can be used to meet that quarter's demand or held in inventory for the next quarter at an extra cost of 20.00 per boat. Answer The decision variables are for t = 1,2,3,4 x = of boats in quarter t built in regular time t y = of boats in quarter t built in overtime t For convenience, introduce variables: i = of boats in inventory at the end quarter t t d = demand in quarter t t We are given that d1 = 40, d2 = 60, d3 = 75, d4 = 25, i0 =10 x ≤ 40, t t By logic i = i + x + y - d , t. t t-1 t t t Demand is met iff i ≥ 0, t t (Sign restrictions x , y ≥ 0, t) t t We need to minimize total cost z subject to these three sets of conditions where z = 400 (x + x + x + x ) + 450 (y + y + y + y ) + 20 (i + i + i + i ) 1 2 3 4 1 2 3 4 1 2 3 4 Report: Lindo reveals the solution to be (x1, x2, x3, x4) = (40, 40, 40, 25) and (y1, y2, y3, y4) = (0, 10, 35, 0) and the minimum cost of 78450.00 is achieved by the schedule Q Q Q Q 1 2 3 4 Regular time (x ) 40 40 40 25 t Overtime (y ) 0 10 35 0 t Inventory (i ) 10 10 0 0 0 t Demand (d ) 40 60 75 25 t 3.1.6 Customer Service Level Example (Winston 3.12, p. 108) CSL services computers. Its demand (hours) for the time of skilled technicians in the next 5 months is t Jan Feb Mar Apr May d 6000 7000 8000 9500 11000 t It starts with 50 skilled technicians at the beginning of January. Each technician can work 160 hrs/month. To train a new technician they must be supervised for 50 hrs by an experienced technician for a period of one month time. Each experienced Y. İlker Topcu, Ph.D. (www.ilkertopcu.info) & Özgür Kabak, Ph.D. (web.itu.edu.tr/kabak) 17

Advise: Why You Wasting Money in Costly SEO Tools, Use World's Best Free SEO Tool Ubersuggest.