This is a resource allocation problem I am attempting to formulate myself, so bear with me this isn't from the 12th edition of some math book.
A miner is selecting 'rocks' from amongst his mine to haul back to the top. There are three components, or attributes, that define a rock; mineral_1, mineral_2, and mineral_3, location.
Example Rock A) 50 units mineral_1, 20 units mineral_2, 0 units mineral_3
Example Rock B) 10 units mineral_1,10 units mineral_2,10 units mineral_3
Example Rock C) 0 units mineral_1,0 units mineral_2, 95 units mineral_3
His cart can hold about** 300 units of rock, and at the top he wants to have about** 100 units of each rock component.
Example Cart 1)
Contains Rock A and C.
Holding 165 units total.
50 units mineral_1,
20 units mineral_2,
95 units mineral_3
His rocks are generally scattered about the caverns of the mine. Their removal comes at a cost of manpower. The manpower required to move a particular rock can be easily calculated as a (,say, linear) function of distance from the location of the cart.
One rock 100 yards away requires 100 rupees of man power, 99 yards, 99 rupees ... 98, 98...[nevermind other things like how much the rock weighs for example.]
**Now about the "about." Think of the cart like a grocery cart. There really is no hard limit on how much it can be stacked. For each case, choose an arbitrary limit "L" and an arbitrary minimum "M" > 0.
*For the individual components, there is a limit "l" for too many of a type of mineral, and a minimum "m" < 0 for too few of a type of mineral.
* The goal being always to get as close to the ideal 100,100,100 composition.
I want to know, given full knowledge of the composition of every rock in the cave, and its location, what is the best choice of rocks to haul back to the surface on this trip which minimizes cost.
Help translate to math? I want to avoid a subjective element, meaning I don't want to have to consider any more variables or elements, particularly as it pertains to a propensity to choose 'closeness' over cost. If this is unavoidable, I need help capturing its essence concisely.
The algorithm I've roughed out it Like this:
Divide each element of each rock by the cost associated with obtaining the whole rock. Now I have the rocks in terms of their elements per unit cost, calling them "Rc"
Assume no one rock alone can overflow any element. Meaning, no rock contains more than 100 of any mineral.
Cart = [mineral_1,mineral_2,mineral_3] = [0,0,0]
Choose the Rc with the greatest sum, and add it to the cart.
Cart = [0+Rc1,0+Rc2,0+Rc3]
Here is a difficulty in choosing. Simply adding the previous rock again will most likely (though not certainly) lead to an unbalance.
...
- So I decided to create a scaler. scaler = [(100-Cart1)/100,(100-Cart2)/100,(100-Cart3)/100]
To decide on the next rock to choose, I examine each Rc and do the dot product with scaler. I choose the Rc/rock that has the greatest dot product in this case.
And so on until I get reasonably close to the goal.
One thing I am issues with in this case is respecting both the cart boundary and the element boundaries.
