The NEM Problem

The No Empty Mule Problem

by SolarStar

Introduction

Imagine you sit in a cave with both iron ore and coal to harvest inside. You and your friend start harvesting at the same time. There are two bags, one with iron ore and the other one with coal. At some point you will look into the bags and count.
The easiest thing to do would be to bring both bags together into one and start mixing. But here begins the problem. Your inventory is empty half of the time. Now think about this: Each time you walk you take as much iron ore to the coal and as much coal to the iron ore as you can carry. In the end, the right amount of ingredients to make iron or steel bars have to be in the bags. You also want to bring Fire Essences and food to both bags.
Every time you bring FE and Food into the cave you also take iron ore and coal from the bag and bring it to storage. The question is, how much iron ore and coal needs to be harvested in each place ? Let the carry capacity of the mule be variable.

Solving

To solve the problem it soon becomes clear, that all locations and the amounts of ingredients in the bags and in storage need to be taken into account. To simplify the math it is also advisable to calculate in a common unit, which is in this case emu. We do not want to intruduce numbers too soon but work with variables to make it work for a wide application. For the conversion we introduce a matrix Y, which we will use in the end to reverse the process and return to the number of items. While analysing the problem, it seemed logical to generate a seperate Transport Matrix for each way. The numbers "-1" and "1" mean to take or to put something from and in a bag respectively. As a thought experiment one can imagine that there are two mules with identical mule capacity and same pathlength and same speed starting from opposite bags. This progress we will define as one turn. e,f and g remain variables. Matrix T is used to balance the ingredients in each bag. We regard the transport as finished and look at the bags again to calculate how many more iron ore and coal need to be harvested in each place. It is important to note that the number of foreign ingredients do not change at this point anymore. This is only in theory. For practical use, harvesting and transporting ingredients can happen at the same time. At last we want to introduce a vector N which contains the multiplictors for the ingredients for the final product. Please read paper from 11.06.15 NEMv2.pdf