I have here what I think is a classical O.R. (operations research) problem. I'm looking to formulate it mathematically and look at the options available to solve it.
We have a list of say 100 recipes.
These recipes combined use 400 ingredients.
The quantity of ingredients required for all the recipes could be defined by a matrix dimension 100 x 400.
We can combine recipes into meal plans, so that the ingredients required for a meal plan is the total of the ingredients required for each recipe in the meal plan.
Each ingredient has an associated cost, that varies depending on the quantity bought.
Say the cost variations can be expressed with no more than 5 cost buckets per ingredient. Eg.
Bucket, Cost / kg
< 1kg, £4.00
> 100kg, £2.50
The ingredient costs can be expressed in two matrices each of dimension 400 x 5:
a) One matrix 400 x 5 giving the buckets for each ingredient
b) Another matrix 400 x 5 giving the unit costs per ingredient and bucket number (1 to 5)
A given meal plan will have a given ingredient requirement, with associated total cost determined via the above matrices.
Suppose we constrain the number of meals in the meal plan to say 4 meals, and these 4 meals must be different recipes. For simplicity (!) we have no other constraints for now.
Our objective is to choose our meal plan (4 meals) such that the total cost is minimised.
1. How do we formulate this problem?
2. How can we solve it efficiently (ie least processing power)?
eg could I use simplex?