Trying to sell the most batches of animals using linear programming

Question

I'm trying to sell the most batches of animals...

Let's say I have 200 dogs, 100 cats, and 100 ferrets.

Person A will give me $10 for a batch of: (1 dog, 1 cat, and 10 ferret).
Person B will give me $10 for a batch of: (1 dog, 20 cats, and 1 ferret).
Person C will give me $10 for a batch of: (20 dogs, 1 cat, and 1 ferret).


For person A, I can sell 10 batches (10 dogs, 10 cats, and 100 ferrets).
For person B, I can sell 5 batches (5 dogs, 100 cats, 5 ferrets).
For person C, I can sell 10 batches (200 dogs, 10 cats, and 10 ferrets).

Meaning, if I sell only to A, I'll get \$100, person B: \$50, person C: \$100.

BUT! I can actually sell more batches i.e. 9 batches to A and 9 batches to C.

If I sell 9 batches to person A (I'll use 9 dogs, 9 cats, and 90 ferrets), then I can also sell 9 batches to person C (using 18 dogs, 9 cats, and 9 ferrets).

I sell A:9 and C:9, I get the best income and most batches sold.

This is probably extremely simple in terms of optimization and a simple matrix, but it's been a while since algebra.

I obviously don't want to try every possible combination and see which gives me the most money.

Question: Assuming that each batch always has the same income, is there a way to find out which combination of batches A/B/C will give the highest yield?

Answer 1

I still suggest watching the tutorial video I linked in the comments to understand how linear programming works. That being said, you can formulate your problem as trying to maximize

$$Profit=10A+10B+10C$$

subject to the constraints on your number of dogs to sell ($A+B+20C \leq 200$), number of cats to sell ($A+20B+C \leq 100$), number of ferrets to sell ($10A+B+C \leq 100$), and that the number of batches sold must be positive ($A\geq0$, $B\geq0$, and $C\geq0$).

Linear programming tells us that the maximum occurs on a point at the endpoints of the polyhedron formed by all of our constraints. Integer programming tells us that the maximum will be an integer point inside the endpoints (if they're not already integers). Thus, we only have to check a few endpoints.

In your case:

$$\begin{aligned} (A,B,C) = (0,0,0)&\text{ yields Profit}=\$0\\ (A,B,C) = (10,0,0)&\text{ yields Profit}=\$100\\ (A,B,C) = (0,5,0)&\text{ yields Profit}=\$50\\ (A,B,C) = (0,0,10)&\text{ yields Profit}=\$100\\ (A,B,C) = (9.5,4.5,0)&\text{ yields Profit}=\$130\\ (A,B,C) = (9.0,0,9.5)&\text{ yields Profit}=\$180\\ (A,B,C) = (0,4.5,9.7)&\text{ yields Profit}=\$130\\ (A,B,C) = (8.7,4.1,9.4)&\text{ yields Profit}=\$210\\ \end{aligned}$$

Therefore, selling 8 batches to person A, 4 batches to person B, and 9 batches to person C will yield \$210, only requiring 192 dogs, 97 cats, and 93 ferrets.

Answer 2

Let the integer decision variables $x_1, x_2, x_3 \geq 0$ denote the number of batches of animals sold to customers $A$, $B$ and $C$, respectively. Since we have a finite number of dogs, cats and ferrets, we have three inequality constraints

$$\begin{array}{cc} x_1 + x_2 + 20 x_3 \leq 200\\ x_1 + 20 x_2 + x_3 \leq 100\\ 10 x_1 + x_2 + x_3 \leq 100\end{array}$$

Each batch that is sold brings in $\$10$. Hence, the total revenue is $10 x_1 + 10 x_2 + 10 x_3$. Assuming that our goal is to maximize revenue, we have the following integer linear program

$$\begin{array}{ll} \text{maximize} & 10 x_1 + 10 x_2 + 10 x_3\\ \text{subject to} & x_1 + x_2 + 20 x_3 \leq 200\\ & x_1 + 20 x_2 + x_3 \leq 100\\ & 10 x_1 + x_2 + x_3 \leq 100\\ & x_1, x_2, x_3 \geq 0\\ & x_1, x_2, x_3 \in \mathbb{Z}\end{array}$$

Observing the inequality constraints, we conclude that

$$x_1 \leq 10 \qquad \qquad x_2 \leq 5 \qquad \qquad x_3 \leq 10$$

Hence, the feasible region is a subset of

$$\{0,1,\dots,10\} \times \{0,1,\dots,5\} \times \{0,1,\dots,10\}$$

whose cardinality is only $(1+5) \cdot (1+10)^2 = 726$. One can use brute force to find the optimal solution. Using Haskell,

λ let triples =  [ (x1,x2,x3) | x1 <- [0,1..10], x2 <- [0,1..5], x3 <- [0,1..10] ]
λ let f (x1,x2,x3) = 10 * (x1 + x2 + x3)
λ let g1 (x1,x2,x3) = (x1 + x2 + 20*x3 <= 200)
λ let g2 (x1,x2,x3) = (x1 + 20*x2 + x3 <= 100)
λ let g3 (x1,x2,x3) = (10*x1 + x2 + x3 <= 100)
λ let triples' = filter g1 triples
λ let triples'' = filter g2 triples'
λ let triples''' = filter g3 triples''
λ maximum $ map f triples'''
210
λ filter (\(x1,x2,x3)->(f (x1,x2,x3) == 210)) triples'''
[(8,4,9)]

The optimal sale is $(8,4,9)$, which yields a revenue of $\$210$.