1

There are n cities $c_1,c_2,...c_n$(in decreasing order of popularity) where a company wants to open its N branches. There is cost $w_i$ for opening a branch in city $c_i$. If company has budget W , how it should open its branches such that maximum number of branches should be opened in most popular cities. A maximum of $k_i$ number of branches can be opened in city $c_i$.

I can formulate it as a linear programming problem but can't figure how to address the issue of maximum number of branches in most popular cities.

rrpp
  • 21
  • If the problem is as stated, the solution suggested below looks good (with min instead of max). However the marginal utility of say the 20th branch in one city may not be as high as that of the first branch in a new city. Hence your objective function probably needs some work. – Macavity Mar 09 '14 at 02:03

1 Answers1

1

As stated, you should just compute the number of branches in the first city as $\lfloor \frac W{c_1} \rfloor$ See if it exceeds $k_1$. Open $\min (\lfloor \frac W{c_1} \rfloor,k_1)$ in the first city. Calculate how much money you have left, go on to city $2$ and do the same. You have not given an objective function that rewards branches in the less preferred cities unless the first ones are full.

Ross Millikan
  • 374,822