Constrained optimisation with too many degrees of freedom

Question

Say I have some products and their unit price:

Product Name	Product Amount	Price per unit
A	10	2
B	20	6
...	...	...
Z	30	7

The products are financial instruments so they need not be sold in discrete amounts (i.e i can sell 50% of product A for a total price of 0.5102).

I am given a target total demand and a target average price. Say the total demand is 25 and the target price is 5.

There are several product combination that can satisfy the product demand. E.g, choosing all of Product_A and 75% of Product_B:

$10 + 0.75*20 = 25.$

This results in an average price of $(10*2+15*6)/25 = 4.4$

Or I could use $(5/6)$ of product Z:

$(5/6)*30 = 25$

And this gives me an average price of:

$(25*7)/25 = 7$

Since I can choose any positive amount of each product, I am having a hard time thinking of a way of solving this in python. If I had to use whole amounts of the products I could simply check if the weighted sum adds up to my target value. But with continuous amounts I am not sure how or even if this is possible.

Since I only have two constraints: that the sum of products must equal the demand and the average price must equal the target, I have too many variables for the number of unknowns. So my gut feeling is that this cannot be solved.

I thought that instead of checking for an exact match with the target, I could choose product amounts such that I get as close as possible to my target, but again, I feel like this won't be possible because of the number of unknowns.

Has anyone here worked with a similar problem and could provide some ideas?

Answer 1

You can solve this as a linear program. The variables are how much of each instrument to sell. The sole constraint (other than lower and upper bounds on each variable) is the demand constraint (equality). The objective is to minimize the total price (which will automatically minimize the per unit price). You do not need a constraint involving the target price; either the optimal solution has unit price less than or equal to the target, or it cannot be done.

Update: If the objective is to get as close as possible to the target price $P$ while exactly meeting demand $D,$ you can introduce a variable $z \ge 0$ to represent the deviation in average price and minimize $z$ subject to the supply limits, the demand constraint (equation) and a pair of constraints $$z \ge (T - P)/D$$ and $$z \ge (P - T)/D,$$ where $T$ is a placeholder for the expression giving the total price in terms of the other decision variables. If you want to get as close as possible to the target price $P$ without exceeding it, you can replace the second constraint with $$T \le P\cdot D.$$