OR1 ASSIGNMENT
IE 373 Operations Research I Fall 2021 Homework 3 Deadline Oct. 18, 2020 Rules (Please read carefully) • You are responsible to complete and return your solutions on time. Failure to submit a homework will result in a grade of 0%. • If you received some help to obtain the solution of a problem, you should acknowledge the source. In particular, for each question, I would like you to cite, if applicable, any book you consulted, any website you searched, or any individual you cooperated with (other than the instructor or the TA). This information will not be used to reduce your homework score, provided that help is limited to a reasonable portion of the homework. However, failing to report any assistance you may have received will be considered dishonest. • Remember, it is acceptable to ask your classmates for hints if you feel “stuck” on a problem. However, by no means you should share complete/almost-complete solutions, codes, formulations, mathematical proofs, or any other material that represents a substantial portion of the problem being solved. Any computational code must be done by each student individually. We will not accept two submissions that are equal/suspiciously similar with the excuse that the students reached the solution together. It is very easy for us to determine if two submissions come from the same source. Please, avoid being penalized for incurring in academic dishonesty. • The homework must be completed in white paper (i.e., computer paper) and the pages must be numbered. • You must upload the MS Excel and python files of your models to UB Learns. If you fail to do so, you will get 0 points in the respective problem. Please save the corresponding files into a compressed folder (.zip), and name it in the format “First Name-Last Name”. • No files will be received by email. Problem 1 You work for a company in Scotland that produces four varieties of scotch whiskey: red, black, blue, and gold. The production process of these whiskeys consists of blending six varieties of aged single malt mixtures (SMM). Each SMM contains a percentage of phenolic compounds and a percentage of aldehides that, when combined, give the whiskeys their corresponding aroma and flavor profile. Different combinations of the SMMs yield the different flavors required by each of the four whiskey varieties. Furthermore, given the aging process required to produce each SMM, their cost per liter of each SMM is also different (see Table 1). SMM Phenolic Compounds (%) Aldehides (%) Cost ($/lt) 1 45% 2% $75 2 30% 4% $60 3 60% 1% $115 4 34% 3% $35 5 38% 5% $40 6 30% 1% $30 Table 1: SMM composition and cost information In order to guarantee consistency in their aroma and flavor profile, depending on the variety, the whiskeys are required to have a minimum percentage of phenolic compounds and a maximum acceptable 1 IE 373 Operations Research I Fall 2021 percentage of aldehides. These requirements, the selling prices and the minimum demand of each variety are given in Table 2. Whiskey Phenolic Compounds (%) Aldehides (%) Price ($/lt) Demand (lt) Red 32% 5% $60 3,000 Black 38% 4% $80 2,000 Blue 45% 3% $90 1,500 Gold 50% 2% $110 600 Table 2: Whiskey requirements and selling price information You have 1,200 lt available of each SMM for the production process. Furthermore, the production plant cannot process more than 10,000 lt of whiskey in total. 1. Provide a formulation for this problem specifying the sets, parameters, decision variables, constraints, and objective function. You can provide a general or an explicit formulation. 2. Solve the problem using Gurobi. Problem 2 You are the owner of the new fancy restaurant in town. To operate the restaurant you use disposable napkins and tablecloths made from recyclable materials. Based on the number of customers you expect to have during the following two months, you have an estimation on number of napkins and tablecloths that you will need for the following 8 weeks (see Table 3). Type/Week 1 2 3 4 5 6 7 8 Napkins 1,800 1,200 1,250 1,700 2,000 4,000 5,000 1,500 Tablecloths 350 280 300 500 900 1,500 2,000 400 Table 3: Demand of napkins and tablecloths per week To satisfy the demand of napkins and tablecloths for each week you have three choices. One possibility is buying them from a small local retailer who can sell you individual units of napkins and tablecloths for a price of $3 and $9 per unit, respectively. Unfortunately, being a small retailer, they can sell you at the most 2,000 napkins and 400 tablecloths per week. A second option is buying them from a large manufacturer. The problem with this option is that, as a large manufacturer, they do not sell individual units, but sell product by box. Each box they sell costs $1,500 and contains 400 napkins and 50 tablecloths. This manufacturer can sell you as many boxes as you want each week. A third option is to order the napkins and tablecloths online from a company located in China. They sell napkins and tablecloths at a price of $2 and $8 per unit, respectively. The problem with this option is that it takes two weeks for the order to arrive. For example, if you order 100 napkins and 50 tablecloths during week 1, those will become available upon arrival in week 3. You can order as many items as you want from this company. For your inventory strategy, it is possible to buy more napkins and tablecloths from the manufacturers than the ones required for each week and save the excess and use them during the subsequent weeks. You can also buy fewer that the ones you need as long as you have enough napkins and tablecloths in your inventory to fulfill the given requirements. However, given the space limitations of your restaurant, you have available a small room with only 3,000 ft3 to store the napkins and tablecloths left at the end of each week. Assume that napkin and tablecloths have an individual size of 0.5 ft3 and 1 ft3, respectively. Suppose that the beginning of week 1 you have 200 napkins and 80 tablecloths available. Also, assume that you want to leave at least 300 napkins and 100 tablecloths as your final inventory for future weeks. Notice that the possibility of buying items from different manufacturers gives you many interesting options. For example buying in bulk from the large manufacturer is cheaper than buying from the local retailer, but because the product comes in a box with a predetermined number of items, you may end up 2 IE 373 Operations Research I Fall 2021 with more items than the ones you need. Also, buying from the company in China seems to be a good option as well, but you must consider the 2-week delay. The main objective of this problem is to identify the inventory policy that minimizes your costs, while satisfying the requirements of the restaurant. a Provide a formulation for this problem specifying the sets, parameters, decision variables, constraints, and objective function. You MUST provide a general formulation. b Solve the problem using Gurobi. c Report your results using tables to present: 1) the number of items of each type that you buy (immediate delivery) or order (delayed delivery) from each provider each week, 2) the inventory of items left at the end of each week per type. Now, consider the following variation of the problem. Suppose that the manufacturer that operates in China imposes the following additional condition. Since they have to ship the product from overseas, they decided not to sell you any product each week, unless the sum of the napkins and tablecloths that you order that week is more than 4,000 units. For example, with this new condition you can decide whether you order product from them during week t. If you do, the total amount of napkins and tablecloths you order from them that week must be at least 4,000 units. d. Provide a formulation for this variation specifying the additional decision variables, constraints, and ob- jective function. You MUST provide a general formulation. e. Solve the problem using Gurobi. f. Report your results using tables to present: 1) the number of items of each type that you buy (immediate delivery) or order (delayed delivery) from each provider each week, 2) the inventory of items left at the end of each week per type. Problem 2 Write the following problems in standard and canonical form: • min z = x1 + 8x2 − 6x4 s.t. − x1 + 6x2 + 8x3 − x4 ≥ −3 x1 + 9x2 + 8x3 + 4x4 ≤ 15 x2 + x4 ≥ 2 x1 free x2 ≥ 0 x3 ≤ 0 x4 ≥ 0 • min 3x1 − x2 s.t.x1 − 3x2 ≥ −3 2x1 + x2 ≥ −2 2x1 + x2 ≤ 8 4x1 − x2 ≤ 16 x1, x2 free 3 IE 373 Operations Research I Fall 2021 • max − 3x1 − 2x2 + 8x3 + 16x4 s.t.x1 + 2x2 + 2x3 + 4x4 = 3 − 3x1 + x2 + x3 − x4 = −1 x1, x2 ≥ 0 x3, x4 ≤ 0 • max 11x1 + 2x2 + x3 + 3x4 + 4x5 + x6 s.t.5x1 + x2 + x3 + 2x4 + x5 = 5 − 14x1 − 3x2 − 3x3 − 5x4 + x6 = 6 2x1 + 1 2 x2 + 1 2 x3 + 1 2 x4 ≤ 5 2 x1, x2, x4, x5, x6 ≥ 0 x3 ≤ 0 • min ∑ i∈W ∑ j∈T cijxij + ∑ j∈T ∑ k∈S hjkyjk s.t. ∑ j∈T xij ≤ bi ∀i ∈W∑ j∈T yjk ≥ dk ∀k ∈ S∑ i∈W xij = ∑ k∈S yjk ∀j ∈ T xij ≤ fij ∀i ∈W, ∀j ∈ T xij ≥ 0 ∀i ∈W, ∀j ∈ T yjk ≥ 0 ∀j ∈ T, ∀k ∈ S 4