Given some input, find the optimal weightings for edges of a graph to maximize some output-CodePudding

I have a directed graph that describes the relationship between items (nodes) via recipes (edges).
Simple example of a recipe: 2 Iron Ore => 1 Iron Ingot.

I want to find a weighting for each recipe (that is to say the number of times each recipe should be applied) such that given some starting number of items, it produces the maximum amount of a specified item.

How can I go about finding this weighting for each recipe?

Note: All weightings must be non-negative (they can be decimal). No weightings can result in more input being required than the amount available.

That's the main problem I'm trying to solve, but following that, the next thing I want to then solve is taking energy usage into account. Each recipe will either use some amount of energy or produce some amount of energy.

How can I ensure that when finding the weightings, the energy production minus the energy consumption is non-negative?

Thanks in advance for any advice :)

CodePudding user response：

I've managed to solve this by abandoning the graph structure and treating the problem as a linear programming problem.

The graph structure might be able to be used if treating the problem as a max flow problem but I haven't look into that.

Here's a small example of the LP to solve for max iron ingots:

Maximize
 iron_ingot: 30 recipe_iron_ingot   50 recipe_iron_alloy_ingot   65 recipe_pure_iron_ingot

Subject To
 iron_ore: 30 recipe_iron_ingot   20 recipe_iron_alloy_ingot   35 recipe_pure_iron_ingot <= 70380
 copper_ore: 20 recipe_iron_alloy_ingot <= 28860

Bounds
 0 <= recipe_iron_ingot
 0 <= recipe_iron_alloy_ingot
 0 <= recipe_pure_iron_ingot

End

This represents an input of 70380 iron ore per minute, 28860 copper ore per minute and unlimited water. It analyses 3 different recipes that make iron ingots.

The result being:

0 × iron ingot recipe
1443 × iron alloy ingot recipe
1186.29 × pure iron ingot recipe

which equants to 149258.85 iron ingots per minute.

This isn't yet taking into account power production / consumption but that should be easy to add by just treating power as an input/output like how items are treated.