Diet problem

The diet problem was the first of some about optimization. The goal was to find the cheapest way to feed the army but insuring at same time some determined nutrition levels.

This kind of problem can be questioned in several ways such as minimizing purchase expenses, diet for the cattle, a slimming diet that obeys some determined calories levels, proteins, carbon hydrates, ...

Example

We want to feed the cattle in a farm using a diet as cheap as possible. Such diet must contains four types of nutrients that will call A, B, C, and D. This components can be found in two kind of fodders, M and N. The quantity, in grams, of every component for kilograme of these fodders is shown in the next board:

An animal's daily diet must be mixed at least with 0.4Kg of A component, 0.6Kg of B component, 2Kg of C component and 1.7Kg of D component. The M fodder cost 0.2€/Kg and the N fodder 0.08€/Kg. What quantities of fodders M and N must be acquired to minimize the cost?

Note: One kilograme (Kg) are 2.205 pounds.

Determining decision variables and expressing them algebraically. In this case:

• X1: quantity of fodder M in Kg
• X2: quantity of fodder N in Kg

Determining the restrictions and expressing them as equations or inequalities in function of the decision variables. Such restrictions can be obteined from required composition to daily diet (in Kg):

• In the A component: 0.1·X1 + 0·X2 ≥ 0.4
• In the B component: 0·X1 + 0.1·X2 ≥ 0.6
• In the C component: 0.1·X1 + 0.2·X2 ≥ 2
• In the D component: 0.2·X1 + 0.1·X2 ≥ 1.7

Expressing all implicit conditions established by the origin of variables: negativeness, integer, only a few allowed values... . In this case, the only restriction is that the quantities of fodder that make the diet can't be negatives:

• X1 ≥ 0
• X2 ≥ 0

Determining objective function:

• Minimize Z = 0.2·X1 + 0.08·X2