Consider the following inventory problem. You are running a company that sells s

Question

Consider the following inventory problem. You are running a company that sells some large product (lets assume you sell trucks), and predictions tell you the quantity of sales to expect over the next n months. Let di denote the number of sales you expect in month i. We’ll assume that all sales happen at the beginning of the month, and trucks that are not sold are stored until the beginning of the next month. You can store at most S trucks, and it costs C to store a single truck for a month. You receive shipments of trucks by placing orders for them, and there is a xed ordering fee of K each time you place an order (regardless of the number of trucks you order). You start out with no trucks. The problem is to design an algorithm that decides how to place orders so that you satisfy all the demands {di}, and minimize the costs. In summary:
• There are two parts to the cost: (1) storage–it costs C for every truck on hand that is not needed that month; (2) ordering fees–it costs K for every order placed.

• In each month you need enough trucks to satisfy the demand di, but the number left over after satisfying the demand for the month should not exceed the inventory limit S.
Give an algorithm that solves this problem in time that is polynomial in n and S.

Explanation / Answer

Here is the algorithm for the above problem,

The subproblems will represent the optimal way to satisfy orders 1, , i with an inventory of s trucks left over after the month i. Let OPT(i, s) denote the value of the optimal solution for this subproblem.

• The problem we want to solve is OPT(n, 0) as we do not need any leftover inventory at the end.

• The number of subproblems is n(S +1) as there could be 0, 1, , S trucks left over after a period.

• To get the solution for a subproblem OPT(i, s) given the values of the previous sub-problems, we have to try every possible number of trucks that could have been left over after the previous period. If the previous period had z trucks left over, then so far we paid OPT(i — 1, z) and now we have to pay zC for storage. In order to satisfy the demand of di and have s trucks left over, we need s di trucks. If z < s di we have to order more and pay the ordering fee of K.

In summary the cost OPT(i, s) is obtained by taking the smaller of OPT(i— 1, s+di)+ C(s+di) (if s+di < S), and the minimum over smaller values of z, minz<min(s+d,,$) (OPT (i-1, z) zC K). We can also observe that the minimum in this second term is obtained when z — 0.With this extra observation we get that

— if s di > S then OPT(i, s) — OPT(i — 1, 0) K,

— else OPT (i, s) min(0 PT (i — 1, s di) + C(s + di), OPT (i — 1, 0) +K).

Related Questions

Navigate

• Browse (All)
• Browse C
• Subjects

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