Problem 1: [10 pts] There are two warehouses V and W that supply widgets to dest

Question

Problem 1: [10 pts] There are two warehouses V and W that supply widgets to destinations Di, 1 ? i ? n. Let di represent the demand of destination i (how many widgets Di requires) and let vi, wi represent the cost of shipping ONE widget to destination Di from Vi, Wi respectively. Warehouses V and W have a supply of widgets of sV and sW respectively. Assume there is a sufficient supply of widgets, i.e. sV + sW = the sum from i=1 to n of: di. The warehouse problem is finding a schedule xi and yi of integers for each 1 ? i ? n such that when xi widgets are sent from V to Di and yi widgets are sent from W to Di, the following constraints are satisfied:

(1) The demand at Di is filled, di = xi + yi.

(2) The inventory at V is sufficient, sV = the sum from i=1 to n of: xi.

(3) The inventory at W is sufficient, sW = the sum from i=1 to n of: yi.

(4) The total shipping cost is minimized, minx,y the sum from i=1 to n of: (vixi + wiyi).

(a) Let gj(x) be the cost incurred when V has an inventory of x widgets, and supplies are sent to destinations Di for all 1 ? i ? j in the optimal manner (note that W is not mentioned because knowledge of the inventory for V implies knowledge of the inventory for W). Write a recurrence relation for gj(x) in terms of gj?1. Justify / explain your answer.

(b) Use this recurrence to devise a dynamic programming algorithm that finds the cost of the cheapest solution to the warehouse problem. Analyze your algorithm.

Explanation / Answer

here are two warehouses V and W that supply widgets to destinations Di, 1 ? i ? n. Let di represent the demand of destination i (how many widgets Di requires) and let vi, wi represent the cost of shipping ONE widget to destination Di from Vi, Wi respectively.

Related Questions

Navigate

• Browse (All)
• Browse P
• Subjects

Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.