Your boss asks you to purchase b; units of product i for each i in a...

 

Transcribed Image Text:

Your boss asks you to purchase b; units of product i for each i in a set P of products. (These products are all divisible, i.e. they can be obtained in fractional amounts.) Of course, your boss wants you to spend as little money as possible. You call up all the stores in a set S of stores, and store j gives you a per-unit price cij for product i for all i, j. (a) You decide to just order all b, units of product i from the store that gives the cheapest per-unit price for each i. Show that this is optimal. (b) Actually, there is another constraint. Your boss forgot to tell you that he does not want you to buy from too many different stores - he wants you to keep the number of stores from which you buy to at most (integer) k. Modify your formulation in (a), the resulting formulation should be an IP. (c) It turns out that the stores have special deals. If the total value of your order from store j is at least t; dollars, it will give you d; cash back. (All stores j offer such a deal, with perhaps different values of tj and d; .) Modify your formulation in (b), the resulting formulation should be an IP. Your boss asks you to purchase b; units of product i for each i in a set P of products. (These products are all divisible, i.e. they can be obtained in fractional amounts.) Of course, your boss wants you to spend as little money as possible. You call up all the stores in a set S of stores, and store j gives you a per-unit price cij for product i for all i, j. (a) You decide to just order all b, units of product i from the store that gives the cheapest per-unit price for each i. Show that this is optimal. (b) Actually, there is another constraint. Your boss forgot to tell you that he does not want you to buy from too many different stores - he wants you to keep the number of stores from which you buy to at most (integer) k. Modify your formulation in (a), the resulting formulation should be an IP. (c) It turns out that the stores have special deals. If the total value of your order from store j is at least t; dollars, it will give you d; cash back. (All stores j offer such a deal, with perhaps different values of tj and d; .) Modify your formulation in (b), the resulting formulation should be an IP.

Answer rating: 100% (QA)

a You decide to just order all b units of product i from the store that gives the cheapest perunit price for each i Show that this is optimal ANSWER Yes this is optimal By definition the cheapest peru... View the full answer