# linear programming problem - how much additional resources should I buy?

I have the following linear optimization problem: Maximize $$\sum_{i=1}^{n}x_{i}B_{i}$$

subject to the constraints

$$a_{11}x_1+a_{12}x_2+\cdots+a_{1n}x_n \le l_1$$ $$...$$ $$a_{m1}x_1+a_{12}x_2+\cdots+a_{mn}x_n \le l_m$$

or more succinctly

$$\sum_{j=1}^{n}a_{ij}x_{j} \le l_i,\; i=1,\ldots,m$$

To give some context I produce Christmas hampers (I don't really but it makes the problem more realistic). Each Christmas hamper/basket is made from a set of products.

So I can produce $n$ different types of baskets out of $m$ different products. $B_i$ is the value of the basket, $i=1\ldots n$.

The cash value of product type $i$ that goes into making one basket of type $j$ is denoted by $a_{ij}$.

My current inventory for the $n$ products is given by $l_1,\ldots,l_n$.

As the problem stands it answers the question, what is the maximum gross profit I can make given my current inventory? The solution of this linear programming problem tells me how many baskets of each type to make, $x_1,\ldots,x_m$.

However suppose I have $C$ dollars to spend. Using this I can buy additional products to put into the baskets. That is create more baskets and increase my sales. The cost of each product is given by $b_1,\ldots,b_n$.

a) Is there a way I can extend the above linear programming problem so that I can determine how much of each product I should to purchase in order to maximize my sales?

b) At the moment I am maximizing my gross profit. I would also like to be able to maximize my net profit given by value of baskets produced minus the amount of additional products I purchased? I assume that my current inventory comes for free.

I would like to know how many of each basket to make (fractional baskets are allowed) and what additional products to buy given my current budget of $C$ dollars.

Can such a problem even be posed as a linear programming problem?

• @Ross Millikan - right you are – mark Dec 18 '14 at 16:13

## 1 Answer

Sure. Define a new set of variables $q_i$ for the amount you buy of product $i$. You can make a new constraint that the total spent is less than $C$ as $\sum b_iq_i \le C$. The $l_i$'s in your existing constraints become $l_i+q_i$. Your function to maximize has the total spent subtracted to get the net profit, so is $(\sum x_iB_i)-(\sum b_iq_i)$.

• This is super cool! You have any good reference suggestions to go get some more modelling experience for these types of problems? – mark Dec 18 '14 at 22:14
• No, I learned almost all I know about linear programming from the chapter in Numerical Recipes. Obsolete versions are free online. It is well written, but I know there are whole books on the subject. – Ross Millikan Dec 18 '14 at 23:05