Optimization Problem for New Store Placement Decision-Making
A company plans to establish two new stores at different locations to cater to four potential customers. The goal is to minimize total costs, including initial investments, transportation, and inventory costs. Integer linear programming is used to identify the optimal store locations based on constraints related to capacity, demand, and cost factors. Various binary variables are introduced to formulate the problem effectively and efficiently.
Download Presentation
Please find below an Image/Link to download the presentation.
The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author. Download presentation by click this link. If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.
E N D
Presentation Transcript
Example 4 A company decided to develop its activities by creating two new stores. Three places are considered for this aim. The following figure shows the possible transportation relations between mentioned places and four new customers, for example first place can support just first, third and fourth customers. Also this figure contains the capacity of each store (if it is built), demand of each customer and transportation cost of one unit between the places and the customers. The initial investment cost for constructing the store at each place and its inventory cost is summarized in the following table. Formulate an integer linear programming problem to choose the best places for creating these stores and minimize the total investment, transportation and inventory cost. A1 Place Initial investment Inventory cost (per unit) K1 P1 1 A2 K2 P2 2 K3 P3 3 A3
Lets xij be the number of the products which will be sent from ith store (if its construct) to the jth customer. Then two of the following three constraints should be hold for the problem. These constraints said that the number of the products which will be send from each of the stores should be less than the capacity of them. + + + + + + + As you seen before we can manage this situation by using the auxiliary binary variables say yi for i=1,2,3. x x x x x x x x A x A 11 13 14 x x 1 A 21 22 23 24 2 31 32 34 3 1 0 if theith place consider to construct the store Otherwise = y 0 i ij Then we can rewrite the above (either/or) constraint as follow + + + + + + + + x x x y y y y x x x y x y A x y A For example in the optimal solution if y1 and y3 take 1 as their value then y2 should be equal to zero. Then the right hand of the second constraint is zero so the value of x21, x22, x23 and x24 are equal to zero. ( The summation of four non-negative variables is zero then they should be equal to zero.) 11 13 14 x x 1 1 y A 21 22 23 24 2 2 31 32 34 = 3 3 + 2 y 1 2 , 3 , {0,1} 1 2 3 + + + + + = = + = x x x x x x x x x D 11 21 31 D D x 1 The next types of the constraint are related to the customers obviously the demand of the customers should meet. 22 32 2 13 23 3 = D 14 24 34 4
To write the objective function based on the aim of the company the total cost should be minimized. The total cost contains initial construction cost to build each of the storages, the transportation cost between the storages (if its construct ) and customers and inventory cost, for example for the first place + + + + + + ( ) K y 11 11 c x 13 13 c x 14 14 c x P x x x 1 1 1 11 13 14 Initial construction cost Transportation cost Inventory cost If we consider the same logic for second and third place, then the related IP is as follows + + + + + + ( c x P x ) Min K y 11 11 c x c x c x + 13 13 c x c x c x + 14 14 c x c x c x + P x + + x + + x 1 1 K y K y 1 11 13 14 + + + + + + + + ( ) P x x x x x 2 2 21 21 22 22 23 23 24 ( 24 2 21 22 23 24 + ) x 3 3 31 31 32 32 34 34 3 31 32 34 + + + + + + + + x x x y y y y x x x y x y A x y A + + + + + = = + = 11 13 14 x x 1 1 x x x x x x x x x x D 11 21 31 D D x 1 y A 21 22 22 24 2 2 12 32 2 31 32 34 = 3 3 13 23 3 + 2 y = D 1 2 , 3 14 24 34 4 , {0,1} 0 1 2 3 ij
Example 5 Three products A, B and C produce by four machines. The technological order and time scheduling for each of machines are pointed in the following figure. The product B must delivered at t o clock and product C must be delivered two hours after B. Formulated the problem in a manner that products are complete in minimum time respect to above restrictions. Note that a machine can not work on the two products at the same time From the figure we can conclude that for example product A is produced by first, third and forth machines and if we start to use the first machine to produce A at ko clock the machine should spend a1 hours to work on A and the third machine may start to work on this product after k+ a1o clock. Then lets define the variables as follow: xAi the time which ith machine start to work on product A where i=1,3,4 xBi the time which ith machine start to work on product B where i=1,2,4 xCi the time which ith machine start to work on product C where i=2,3 Now Assume that the last operation of the machines on the mentioned products will finish at Wo clock then because the aim is minimizing the production duration then W should minimized. Then the time of last operation on each product should be less than W this means that
+ + + x x x a b c W W W 4 4 A 4 4 B 3 3 C From the given information the last operation on product B should done before to clock and the last operation on product C should finish until t+2o clock. Then we have the following constraints. + + + x x b c t t 4 4 B 2 3 3 C + + + + + Now technological order for producing each one of the products implies the following constraints. For example for product B the second machine can start to work on B after xB1+b1o clock and xB4 which is the starting time for machine four to work on product B should be after xB2+b2 the time which the second machine complete its operation on product B. x x a a x x 1 1 3 A A : For A 3 3 4 A A x x x b b c x x x 1 1 2 B B : For B 2 2 4 B B : For C 2 2 3 C C Beside of the above mentioned constraints there are some either/or constraint because of starting time of using each one of the machines to produce the products. For example the first machine is used to produce both of A and B but if one of them start to use this machine other one should wait to finish the production of first product and after that it can start to use the first machine. Then we have the following either/or constraints:
+ + + + + x x x x a c a a x x x x or or or or x b x 1 1 1 1 1 b c b 1 A B B A x x x + + + x x x 2 2 2 2 2 2 C B B C 3 3 3 3 3 3 A C C A 4 4 4 4 4 4 A B B A For each pair of these constraint we should use a auxiliary binary variable say yi for i=1,2,3,4. Then we have these constraints x a x For Machine x b x + + + + + + + + + + My M + + + + + + 1 1 1 1 A B 1 {0,1} y 1 (1 ) y 1 1 c b 1 1 B A x x x x My M 2 2 2 2 C B 2 {0,1} For Machine y 2 (1 ) y 2 2 2 2 B C x x a c x x My M 3 3 3 3 A C 3 {0,1} For Machine y 3 (1 ) y 3 3 3 3 C A x x a b x x My M 4 4 4 4 1 A B 4 {0,1} For Machine y 4 ( ) y 4 4 4 4 B A Here for example for machine 4 in optimal solution if auxiliary binary variable y4 is equal to 0, product A will be used machine 4 earlier than product B and product B should wait machine 4 to complete its work on A and then it can use this machine. But when y4=1 then product B start to use machine 4 earlier than product A, and A should wait.
The IP related to Example 5 is as follow: Min W + + + + + + + + + + x x x x x x x x a b c b a c a b x x x x x x x x My M My M My M My M + S.t 1 1 1 1 A B (1 ) {0,1} y y + + + x x x a b c W W W 1 1 1 1 1 B A 4 4 A + + + + + 2 2 2 2 C B 4 4 B (1 ) {0,1} y y 2 2 2 2 2 B C 3 3 C + + + x x b c t t 4 4 B 3 3 3 3 A C 2 (1 ) {0,1} y y 3 3 C 3 3 3 3 3 C A + + + + + x x x x x a a b b c x x x x x 1 1 3 A A 4 4 4 4 A B (1 ) {0,1} y y 3 2 4 A A 4 4 0 0 0 4 4 4 B x x x A = = = 1 1 2 1,3,4 1,2,4 2,3 B B i i i Ai 2 2 4 B B Bi 2 2 3 C C Ci
Example 6 Let
Example 7 (Knapsack Problem) Assume that Jone should take bread, catchup, sausage and soft drink for school picnic. He has a knapsack with capacity 6kg. The weight and value (degree of importance) for each unit of mentioned items are summarized in the following table. Formulate the problem in a manner that respect to the capacity of his knapsack the value of the knapsack be maximized. The fraction values are not acceptable. Bread 250 gr 50 Catchup 400 gr 10 sausage 500 gr 30 soft drink 1200 gr 35 Weight Value Lets xj be the number of the units for ith item which Jone will put in his Knapsack. Then IP related to this problem is as follows 50 10 30 . 250 400 500 S t x x x x + + + 35 x Max x x x x + 1 2 3 4 + + 1200 6000 1 1 1 1 x 1 2 3 4 1 2 x 3 x 4 = 1,2,3,4 x Integer j j
