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?

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

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)$.

  • $\begingroup$ This is super cool! You have any good reference suggestions to go get some more modelling experience for these types of problems? $\endgroup$ – mark Dec 18 '14 at 22:14
  • $\begingroup$ 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. $\endgroup$ – Ross Millikan Dec 18 '14 at 23:05

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.