How to solve an optimization problem that deals with the optimal combination of given ratios?

I'm volunteering for a non-profit, and was asked to write a program for this problem, but I'm having a little trouble tackling it. Here's the problem:

So they're a daycare, and they get paid by the government depending on specific ratio's of staff to children. Here are the possible ratios and their pay:

• one staff to 3 children (3:1). Pays 14.71 dollars per hour
• one staff to 2 children (2:1). Pays 9.10 dollars per hour
• one staff to 1 child (1:1). Pays 7.28 dollars per hour

With every possible number of staff and number of children in the daycare, there is a combination of ratios that will give the maximum profit. How do I find those ratios? Are there any clever ways to approach this problem?

The inputs of this ideal program would be number of staff and number of children, and the output would be the combination of ratios that produces the maximum profit.

• I am volunteering for a special needs daycare/nonprofit. They don't document the ratios I explained above correctly because they don't have the staff to do it and they forget. They have lost a lot of money because of this, and have had to use the little money they make to pay the staff, utilities, and etc. So with a program like this, this problem could be solved. I have tried finding the number of combinations of ratios that make up the total number of kids, however I can only get that: the number of combinations. I'm having trouble extracting the actual ratio combinations. – Alexis Herrera Jan 5 '16 at 0:38
• From there I believe the rest is easy. I just calculate the cost of each combination and then find the one that is the highest. – Alexis Herrera Jan 5 '16 at 0:40
• Follow-up questions: What's the input? What are we given? We are given the number of children, and an upper bound on the maximum number of staff? What is the desired output? Do you want a way to partition the children into classrooms, with one staff member per classroom, that maximizes the profit? How do we derive the profit from the amount paid by the government? Don't we need to know how much each staff member costs, or how the costs depend upon the number of children in each classroom? – D.W. Jan 5 '16 at 0:52
• Sounds like something easily expressed as a linear or integer program (googleable terms). – Raphael Jan 5 '16 at 1:32

If the number of children $n$ is fixed and there is no limit on the number of staff members you can potentially hire, here's one way you can maximize the amount the government pays you:

You can use linear programming (LP). Let $s_1$ denote the number of staff you hire to manage one-child classrooms; $s_2$ the number of staff you hire to manage two-child classrooms; and $s_3$ the number of staff you hire to manage three-child classrooms. The number of children you can handle, with this configuration of staff, is $s_1 + 2s_2 + 3s_3$. Also, the amount paid by the government is $7.28 s_1 + 9.10 s_2 + 14.71 s_3$. You want to maximize the payoff, subject to the constraints $s_1 \ge 0$, $s_2 \ge 0$, $s_3 \ge 0$ and to the constraint $s_1 + 2 s_2 + 3 s_3 \ge n$ (i.e., you have capacity to take care of $n$ children).

Of course, this formulation is silly, because under this formulation the way to maximize your profit is to maximize the number of staff chosen. That's because this formulation doesn't take into account the cost of hiring staff or any other consideration. So you'll need to adjust it to incorporate the additional constraints you have.

Fortunately, this LP formulation makes it easy to incorporate additional constraints. For instance, suppose there are only 100 qualified people who you'd possible be willing to hire as staff, so you simply can't hire more than a total of 100 staff members. That can be handled by adding the additional constraint $s_1 + s_2 + s_3 \le 100$.

In practice there's probably some cost per staff member you hire, so in practice we probably want to maximize not the amount the government pays us, but the amount of "profit" left over after paying the staff members. Suppose each staff member costs 5 dollars per hour. Then you would adjust the above by maximizing the revenue minus the costs, i.e., $(7.28 s_1 + 9.10 s_2 + 14.71 s_3) - (5.00 s_1 + 5.00 s_2 + 5.00 s_3)$.

In practice you want to only hire an integer number of staff, so you might want to use an integer linear programming (ILP) solver rather than a LP solver.

I still question whether this is the right metric for a non-profit to be maximizing. Instead of focusing only on "profit", I would anticipate that a non-profit would care about the benefit to stakeholders or soceity: e.g., the benefit to the children served, or the number of children served, or some combination of benefit and leftover "profit". For instance, all else being equal, is the benefit greater if a child is cared by a single staff member rather than sharing a staff member with two other children? I suspect so, but that isn't incorporated in your "profit maximization" formulation. Thus, I suspect the right objective function to maximize might be something different, chosen to take into account that the goal of a non-profit is not to derive a profit but to accrue some social benefit.

• A non-profit organisation still has to pay their bills. If they can save some money (or earn more) without impeding their goals, they should do so. – Raphael Jan 5 '16 at 1:34

First of all you should specify what is the input and the desired output of the algorithm.

I will assume that the input is the number of staff and the number of children, and the output the desired combinations of children/stuff that maximize the profit. I think it can be expressed as a Knapsack Problem. In the knapsack problem the objective is to choose a combination of objects where each object has a value and a weight, the combination must be choosen such that the sum of the weights doesn't exceed a given maximum weight capacity (The knapsack capacity) and the sum of the values is maximized.

In your problem each object is the combination of staff/children. Here I'm assuming that the amount of money paid by 3:1 is for example the same of the amount to be paid by a 9:3 combination.

The value of each object is the amount of dollars by hour given by the rules you've described above.

The weights are number of staff and children in each item, for example an object could be (4,5) and the weight of the "knapsack" is the maximum staff and children given by the input of the algorithm. Note that this is not the classic version of the Knpasack problem because you have two dimensions in the weight (The number of staff and the number of children), more over in the "classic" version known as 0-1 knapsack every item can be picked only once, I don't really know of if that is your case you should adapt the problem according to your constraints (And not in the inverse way).

Before the edit I said that you may apply the Dynamic Programming algorithm, you should be careful because it applies when the problem is 0-1 i.e. when each object is allowed to be choosen only once. Depending on your final model of the problem an exact algorithm may or me be not used (Remember that Knapsack is NP-Hard).

• You assumed the inputs and the desired output of the algorithm correctly. I just have one question: can you clarify what the weight of the Knaspack is? Is it just the number of staff plus the number of children? – Alexis Herrera Jan 6 '16 at 1:40
• I've edited the answer, if you have any doubts, let me know! – bones.felipe Jan 8 '16 at 1:55