Suppose for example you need exactly 136 apples, 235 oranges, 34 peaches and 167 bananas.
These items can only be purchased in predefined groups such as: {2,3,1,1}, {0,5,0,1}, {1,1,3,1}, {2,2,0,0}, ... where each number corresponds to the number of each type of fruit purchased in each transaction.
Ideally, you want the exact number of each fruit, but if the number you ultimately purchase is over the goal there is some predefined penalty for buying too much of any given fruit, so it would be good to know close approximate answers if the reaching the exact total is impossible. I was hoping to know the general case where there are x types of fruit and y combinations in which they are sold.
Is there some simple way to know how many of each combination should be purchased in order to reach the totals? If it cannot be easily figured out by hand is there a known algorithm to solve this problem?
I think this might be a problem that can be solved with linear algebra or vectors but I only have a basic understanding of those topics.
Thank you for your help.
You can solve the problem via mixed integer linear programming as follows. Let $I$ be the set of items, and let $G$ be the set of groups. Let $d_i$ be the demand for item $i$, and let $p_i$ be the penalty per excess unit of item $i$. Let $a_{i,g}$ be the number of copies of item $i$ in group $g$. Let nonnegative integer decision variable $x_g$ be the number of copies purchased of group $g$, and let nonnegative decision variable $s_i$ represent the surplus of item $i$. The problem is to minimize $\sum_{i\in I} p_i s_i$ subject to linear constraints $$\sum_{g\in G} a_{i,g} x_g - s_i = d_i \quad \text{for $i\in I$}$$
For your sample data and assuming $p=(1,1,1,1)$, an optimal solution is $x=(0, 31, 136, 0)$, with $s=(0,56,374,0)$, yielding objective value $430$.