Integer Programming 9 MIT Massachusetts Institute of

Integer Programming 9 Mit Massachusetts Institute Of-Free PDF

  • Date:01 Feb 2020
  • Views:37
  • Downloads:0
  • Pages:48
  • Size:1.65 MB

Share Pdf : Integer Programming 9 Mit Massachusetts Institute Of

Download and Preview : Integer Programming 9 Mit Massachusetts Institute Of

Report CopyRight/DMCA Form For : Integer Programming 9 Mit Massachusetts Institute Of


9 1 Some Integer Programming Models 273, Capital Budgeting In a typical capital budgeting problem decisions involve the selection of a number of. potential investments The investment decisions might be to choose among possible plant locations to select. a configuration of capital equipment or to settle upon a set of research and development projects Often it. makes no sense to consider partial investments in these activities and so the problem becomes a go no go. integer program where the decision variables are taken to be x j 0 or 1 indicating that the jth investment. is rejected or accepted Assuming that c j is the contribution resulting from the jth investment and that ai j is. the amount of resource i such as cash or manpower used on the jth investment we can state the problem. formally as,Maximize cjxj,subject to,ai j x j bi i 1 2 m. xj 0 or 1 j 1 2 n, The objective is to maximize total contribution from all investments without exceeding the limited availability. bi of any resource, One important special scenario for the capital budgeting problem involves cash flow constraints In this. case the constraints,ai j xi bi, reflect incremental cash balance in each period The coefficients ai j represent the net cash flow from in.
vestment j in period i If the investment requires additional cash in period i then ai j 0 while if the. investment generates cash in period i then ai j 0 The righthand side coefficients bi represent the incre. mental exogenous cash flows If additional funds are made available in period i then bi 0 while if funds. are withdrawn in period i then bi 0 These constraints state that the funds required for investment must. be less than or equal to the funds generated from prior investments plus exogenous funds made available or. minus exogenous funds withdrawn, The capital budgeting model can be made much richer by including logical considerations Suppose for. example that investment in a new product line is contingent upon previous investment in a new plant This. contingency is modeled simply by the constraint, which states that if xi 1 and project i new product development is accepted then necessarily x j 1 and. project j construction of a new plant must be accepted Another example of this nature concerns conflicting. projects The constraint,x1 x2 x3 x4 1, for example states that only one of the first four investments can be accepted Constraints like this commonly. are called multiple choice constraints By combining these logical constraints the model can incorporate. many complex interactions between projects in addition to issues of resource allocation. The simplest of all capital budgeting models has just one resource constraint but has attracted much. attention in the management science literature It is stated as. Maximize cjxj,274 Integer Programming 9 1,subject to. xj 0 or 1 j 1 2 n, Usually this problem is called the 0 1 knapsack problem since it is analogous to a situation in which a.
hiker must decide which goods to include on his trip Here c j is the value or utility of including good j. which weighs a j 0 pounds the objective is to maximize the pleasure of the trip subject to the weight. limitation that the hiker can carry no more than b pounds The model is altered somewhat by allowing more. than one unit of any good to be taken by writing x j 0 and x j integer in place of the 0 1 restrictions on. the variables The knapsack model is important because a number of integer programs can be shown to be. equivalent to it and further because solution procedures for knapsack models have motivated procedures for. solving general integer programs, Warehouse Location In modeling distribution systems decisions must be made about tradeoffs between. transportation costs and costs for operating distribution centers As an example suppose that a manager must. decide which of n warehouses to use for meeting the demands of m customers for a good The decisions to. be made are which warehouses to operate and how much to ship from any warehouse to any customer Let. 1 if warehouse i is opened,0 if warehouse i is not opened. xi j Amount to be sent from warehouse i to customer j. The relevant costs are, f i Fixed operating cost for warehouse i ifopened for example a cost to. lease the warehouse, ci j Per unit operating cost at warehouse i plus the transportation cost for. shipping from warehouse i to customer j,There are two types of constraints for the model.
i the demand d j of each customer must be filled from the warehouses and. ii goods can be shipped from a warehouse only if it is opened. The model is,Minimize ci j xi j f i yi 1,i 1 j 1 i 1. subject to,xi j dj j 1 2 n 2,xi j yi dj 0 i 1 2 m 3. xi j 0 i 1 2 m j 1 2 n,yi 0 or 1 i 1 2 m,9 1 Some Integer Programming Models 275. The objective function incorporates transportation and variable warehousing costs in addition to fixed. costs for operating warehouses The constraints 2 indicate that each customer s demand must be met The. summation over the shipment variables xi j in the ith constraint of 3 is the amount of the good shipped from. warehouse i When the warehouse is not opened yi 0 and the constraint specifies that nothing can be. shipped from the warehouse On the other hand when the warehouse is opened and yi 1 the constraint. simply states that the amount to be shipped from warehouse i can be no larger than the total demand which. is always true Consequently constraints 3 imply restriction ii as proposed above. Although oversimplified this model forms the core for sophisticated and realistic distribution models. incorporating such features as, 1 multi echelon distribution systems from plant to warehouse to customer. 2 capacity constraints on both plant production and warehouse throughput. 3 economies of scale in transportation and operating costs. 4 service considerations such as maximum distribution time from warehouses to customers. 5 multiple products or, 6 conditions preventing splitting of orders in the model above the demand for any customer can be supplied.
from several warehouses, These features can be included in the model by changing it in several ways For example warehouse. capacities are incorporated by replacing the term involving yi in constraint 3 with yi K i where K i is the. throughput capacity of warehouse i multi echelon distribution may require triple subscripted variables xi jk. denoting the amount to be shipped from plant i to customer k through warehouse j Further examples of. how the simple warehousing model described here can be modified to incorporate the remaining features. mentioned in this list are given in the exercises at the end of the chapter. Scheduling The entire class of problems referred to as sequencing scheduling and routing are inherently. integer programs Consider for example the scheduling of students faculty and classrooms in such a way. that the number of students who cannot take their first choice of classes is minimized There are constraints on. the number and size of classrooms available at any one time the availability of faculty members at particular. times and the preferences of the students for particular schedules Clearly then the ith student is scheduled. for the jth class during the nth time period or not hence such a variable is either zero or one Other. examples of this class of problems include line balancing critical path scheduling with resource constraints. and vehicle dispatching, As a specific example consider the scheduling of airline flight personnel The airline has a number of. routing legs to be flown such as 10 A M New York to Chicago or 6 P M Chicago to Los Angeles The. airline must schedule its personnel crews on routes to cover these flights One crew for example might be. scheduled to fly a route containing the two legs just mentioned The decision variables then specify the. scheduling of the crews to routes,1 if a crew is assigned to route j. 0 otherwise,1 if leg i is included on route j,0 otherwise. c j Cost for assigning a crew to route j, The coefficients ai j define the acceptable combinations of legs and routes taking into account such charac.
teristics as sequencing of legs for making connections between flights and for including in the routes ground. time for maintenance The model becomes,Minimize cjxj. 276 Integer Programming 9 1,subject to,ai j x j 1 i 1 2 m 4. xj 0 or 1 j 1 2 n, The ith constraint requires that one crew must be assigned on a route to fly leg i An alternative formulation. permits a crew to ride as passengers on a leg Then the constraints 4 become. ai j x j 1 i 1 2 m 5,If for example,a1 j x j 3, then two crews fly as passengers on leg 1 possibly to make connections to other legs to which they have been. assigned for duty, These airline crew scheduling models arise in many other settings such as vehicle delivery problems.
political districting and computer data processing Often model 4 is called a set partitioning problem since. the set of legs will be divided or partitioned among the various crews With constraints 5 it is called a. set covering problem since the crews then will cover the set of legs. Another scheduling example is the so called traveling salesman problem Starting from his home a. salesman wishes to visit each of n 1 other cities and return home at minimal cost He must visit each city. exactly once and it costs ci j to travel from city i to city j What route should he select If we let. 1 if he goes from city i to city j,0 otherwise, we may be tempted to formulate his problem as the assignment problem. Minimize ci j xi j,subject to,xi j 1 j 1 2 n,xi j 1 i 1 2 n. xi j 0 i 1 2 n j 1 2 n, The constraints require that the salesman must enter and leave each city exactly once Unfortunately the. assignment model can lead to infeasible solutions It is possible in a six city problem for example for the. assignment solution to route the salesman through two disjoint subtours of the cities instead of on a single. trip or tour See Fig 9 1, Consequently additional constraints must be included in order to eliminate subtour solutions There are. a number of ways to accomplish this In this example we can avoid the subtour solution of Fig 9 1 by. including the constraint,x14 x15 x16 x24 x25 x26 x34 x35 x36 1.
9 2 Formulating Integer Programs 277,Figure 9 1 Disjoint subtours. This inequality ensures that at least one leg of the tour connects cities 1 2 and 3 with cities 4 5 and 6 In. general if a constraint of this form is included for each way in which the cities can be divided into two groups. then subtours will be eliminated The problem with this and related approaches is that with n cities 2n 1. constraints of this nature must be added so that the formulation becomes a very large integer programming. problem For this reason the traveling salesman problem generally is regarded as difficult when there are. many cities, The traveling salesman model is used as a central component of many vehicular routing and scheduling. models It also arises in production scheduling For example suppose that we wish to sequence n 1. jobs on a single machine and that ci j is the cost for setting up the machine for job j given that job i has. just been completed What scheduling sequence for the jobs gives the lowest total setup costs The problem. can be interpreted as a traveling salesman problem in which the salesman corresponds to the machine. which must visit or perform each of the jobs Home is the initial setup of the machine and in some. applications the machine will have to be returned to this initial setup after completing all of the jobs That. is the salesman must return to home after visiting the cities. 9 2 FORMULATING INTEGER PROGRAMS, The illustrations in the previous section not only have indicated specific integer programming applications. but also have suggested how integer variables can be used to provide broad modeling capabilities beyond those. available in linear programming In many applications integrality restrictions reflect natural indivisibilities. of the problem under study For example when deciding how many nuclear aircraft carriers to have in the. U S Navy fractional solutions clearly are meaningless since the optimal number is on the order of one or. two In these situations the decision variables are inherently integral by the nature of the decision making. This is not necessarily the case in every integer programming application as illustrated by the capital. budgeting and the warehouse location models from the last section In these models integer variables arise. from i logical conditions such as if a new product is developed then a new plant must be constructed. and from ii non linearities such as fixed costs for opening a warehouse Considerations of this nature. are so important for modeling that we devote this section to analyzing and consolidating specific integer. programming formulation techniques which can be used as tools for a broad range of applications. Binary 0 1 Variables, Suppose that we are to determine whether or not to engage in the following activities i to build a new plant. ii to undertake an advertising campaign or iii to develop a new product In each case we must make a. yes no or so called go no go decision These choices are modeled easily by letting x j 1 if we engage in. the jth activity and x j 0 otherwise Variables that are restricted to 0 or 1 in this way are termed bi. Integer Programming 9 The linear programming models that have been discussed thus far all have beencontinuous in the sense that decision variables are allowed to be

Related Books