In this post, we will discuss the Farmer’s Problem as an example of formulating primal and dual problems in linear programming.

The application case comes from the Operations Research course at Les Mines Nancy (France) by Bernardetta Addis.

Application Case: Farmer’s Problem

A farmer has 12 hectares of land to cultivate tomatoes and/or potatoes.
He also has 70 kg of tomato seeds, 18 t of tubers, and 160 m³ of water.

  • Profit:
    • Tomatoes: 3000 € per hectare
    • Potatoes: 5000 € per hectare
  • Resource Usage per hectare:
    • Tomatoes: 7 kg of seeds, 10 m³ of water
    • Potatoes: 3 t of tubers, 20 m³ of water
  • Resource Availability:
    • 12 hectares of land
    • 160 m³ of water
    • 70 kg of tomato seeds
    • 18 t of potato tubers

The farmer wants to decide how many hectares of tomatoes ((x_t)) and potatoes ((x_p)) to cultivate in order to maximize the total profit.

veg avail profit/hectare seeds/hectare water/hectare
tomatoes 70 kg 3000 € 7 kg 10 m³
potatoes 18 t 5000 € 3 t 20 m³

Primal Problem Formulation

Original Formulation (in €/hectare, with actual units)

Variables

  • \(x_t \ge 0\) : number of hectares of tomatoes
  • \(x_p \ge 0\) : number of hectares of potatoes

Objective function (in €):

\[\max \; 3000 x_t + 5000 x_p\]

Constraints:

\[\begin{aligned} &x_t + x_p \leq 12 &&\text{(Land)} \\ &10x_t + 20x_p \leq 160 &&\text{(Water)} \\ &7x_t \leq 70 &&\text{(Tomato seeds)} \\ &3x_p \leq 18 &&\text{(Potato seeds)} \\ &x_t, x_p \geq 0 &&\text{(Non-negativity)} \end{aligned}\]

Rescaled Formulation

As the profit in € per hectare is quite high, it is more convenient to rescale the problem by dividing all the coefficients by 1000, turning the profit into k€. Similarly, we can rescale the constraints:

Objective function (in k€):

\[\max \; 3x_t + 5x_p\]

Constraints:

\[\begin{aligned} &x_t + x_p \leq 12 &&\text{(Land)} \\ &x_t + 2x_p \leq 16 &&\text{(Water: dividing by 10)} \\ &x_t \leq 10 &&\text{(Tomato seeds: dividing by 7)} \\ &x_p \leq 6 &&\text{(Potato seeds: dividing by 3)} \\ &x_t, x_p \geq 0 &&\text{(Non-negativity)} \end{aligned}\]

Graphical Representation

Since we have only two variables (\(x_t\), \(x_p\)), we can plot the problem in a 2D graph with a tool like GeoGebra.

In the graph below, \(x\) represents \(x_t\) and \(y\) represents \(x_p\). You can activate or deactivate the constraints by clicking on the corresponding circle on the left. The value of the objective function is represented by the variable \(profit\) that you can modify with the slider. When the objective function is maximized, at the intersection of the two constraints land and water, the optimal solution is the point (8,4) with a profit of 44k€.

Primal AMPL Code

We can also solve this problem with AMPL, a modeling language for mathematical programming. See the tutorial to install it.

File: farmer_primal.mod

# Variables
var x_T >=0;
var x_P >=0;

# Objective function
maximize profit: 3*x_T + 5*x_P;

# Constraints (s.t. = subject to)
s.t. land: x_T + x_P <=12;
s.t. water: x_T + 2*x_P <= 16;
s.t. tomato_seed: x_T <= 10;
s.t. potato_seed: x_P <= 6;

File: farmer_primal.run

reset;

# Load the model
model farmer_primal.mod;

# Use the Gurobi solver and solve the problem
option solver gurobi;
solve;

# Display the results (variables, constraints, objective function)
display 
    x_T,
    x_P,
    land.body,
    land.slack,
    land.dual,
    water.body,
    water.slack,
    water.dual,
    tomato_seed.body,
    tomato_seed.slack,
    tomato_seed.dual,
    potato_seed.body,
    potato_seed.slack,
    potato_seed.dual,
    profit;

AMPL output :

include "farmer_primal.run";
ampl: Gurobi 12.0.0: optimal solution; objective 44
2 simplex iterations
x_T = 8
x_P = 4
land.body = 12
land.slack = 0
land.dual = 1
water.body = 16
water.slack = 0
water.dual = 2
tomato_seed.body = 8
tomato_seed.slack = 2
tomato_seed.dual = 0
potato_seed.body = 4
potato_seed.slack = 2
potato_seed.dual = 0
profit = 44

Primal optimal solution : $x_T = 8$, $x_P = 4$ with a profit of 44 (44k€).

Notice the output:

  • land.body = 12 means the total used land is 12 hectares.
  • land.slack = 0 means there is no leftover land.
  • land.dual = 1 is the shadow price for the land constraint (see dual problem below).

Dual Problem Formulation

We now look at the dual of the Farmer’s Problem.

If the primal is in the form

\[\max \; c^T x \quad \text{ subject to } \quad Ax \leq b, \quad x \geq 0\]

then its dual is

\[\min \; b^T y \quad \text{ subject to } \quad A^T y \geq c, \quad y \geq 0.\]

Note:

For more details about the duality and the different forms of the primal and dual problems, as well as the conversion between them, you can look at the course or in the book “Understanding and Using linear programming” by Jiří Matoušek and Bernd Gärtner (or any other book on linear programming, there are many).

From the primal:

\[\max \; 3x_t + 5x_p\]

Subject to:

\[\begin{aligned} &x_t + x_p \leq 12 &&\text{(Land)} \\ &x_t + 2x_p \leq 16 &&\text{(Water)} \\ &x_t \leq 10 &&\text{(Tomato seeds)} \\ &x_p \leq 6 &&\text{(Potato seeds)} \\ &x_t, x_p \geq 0 &&\text{(Non-negativity)} \end{aligned}\]

We rewrite it in matrix form:

\[\max \; c^T x\] \[Ax \leq b\] \[x \geq 0\]

Where

\[c = \begin{bmatrix} 3 \\ 5 \end{bmatrix} A = \begin{bmatrix} 1 & 1 \\ 1 & 2 \\ 1 & 0 \\ 0 & 1 \end{bmatrix} b = \begin{bmatrix} 12 \\ 16 \\ 10 \\ 6 \end{bmatrix}\]

The corresponding dual is:

\[\min \; b^T y\]

Subject to:

\[A^T y \geq c\] \[y \geq 0\]

We obtain:

Variables:

  • \(y_1\) : dual variable for the land constraint
  • \(y_2\) : dual variable for the water constraint
  • \(y_3\) : dual variable for the tomato seeds constraint
  • \(y_4\) : dual variable for the potato seeds constraint

Objective function :

\[\min \; 12y_1 + 16y_2 + 10y_3 + 6y_4\]

Subject to:

\[\begin{aligned} &y_1 + y_2 + y_3 \geq 3 &&\text{(Constraint for tomato variable)} \\ &y_1 + 2y_2 + y_4 \geq 5 &&\text{(Constraint for potato variable)} \\ &y_1, y_2, y_3, y_4 \geq 0 &&\text{(Non-negativity)} \end{aligned}\]

Dual AMPL Code

We can write the AMPL code for the dual problem:

File: farmer_dual.mod

# Variables
var y_1 >=0;
var y_2 >=0;
var y_3 >=0;
var y_4 >=0;

# Objective function
minimize cost: 12*y_1 + 16*y_2 + 10*y_3 + 6*y_4;

# Constraints
s.t. tomato_constraint: y_1 + y_2 + y_3 >= 3;
s.t. potato_constraint: y_1 + 2*y_2 + y_4 >= 5;

File: farmer_dual.run

reset;

model farmer_dual.mod;
option solver gurobi;
solve;

display 
    y_1,
    y_2,
    y_3,
    y_4, 
    tomato_constraint.body,
    tomato_constraint.slack,
    tomato_constraint.dual,
    potato_constraint.body,
    potato_constraint.slack,
    potato_constraint.dual,
    cost;

AMPL output :

ampl: include "farmer_dual.run";
Gurobi 12.0.0: optimal solution; objective 44
3 simplex iterations
y_1 = 1
y_2 = 2
y_3 = 0
y_4 = 0
tomato_constraint.body = 3
tomato_constraint.slack = 0
tomato_constraint.dual = 8
potato_constraint.body = 5
potato_constraint.slack = 0
potato_constraint.dual = 4
cost = 44

We obtain:

  • Dual optimal solution: \((y_1, y_2, y_3, y_4) = (1, 2, 0, 0)\)
  • Dual Objective: 44 (same as the primal’s optimal value, strong duality).

Primal-Dual Relationship

When AMPL solves the primal problem, it automatically computes the dual values. In the primal output, for instance:

  • land.dual = 1 corresponds to \(y_1 = 1\).
  • water.dual = 2 corresponds to \(y_2 = 2\).
  • tomato_seed.dual = 0 corresponds to \(y_3 = 0\).
  • potato_seed.dual = 0 corresponds to \(y_4 = 0\).

Similarly, when solving the dual, AMPL can display the dual of the dual problem, which actually corresponds to the primal variables:

  • tomato_constraint.dual = 8 corresponds to \(x_T = 8\).
  • potato_constraint.dual = 4 corresponds to \(x_P = 4\).

To better understand the values of the dual variables (shadow prices/dual prices), keep in mind that:

  1. Each dual variable corresponds to a primal resource (or constraint):
    • \(y_1\) corresponds to Land
    • \(y_2\) corresponds to Water
    • \(y_3\) corresponds to Tomato seeds
    • \(y_4\) corresponds to Potato seeds
  2. Its value indicates the marginal worth of that resource:
    • If \(y_i > 0\), it means the corresponding resource is fully utilized (the constraint is tight). Adding one more unit of that resource will increase the primal objective (the profit) by \(y_i\) units.
    • If \(y_i = 0\), it means there is some slack in the corresponding resource, not all of it is used. Adding more of that resource will not increase the objective, so its marginal worth is zero.

    They help decision-makers identify which resources are the most critical or limiting in the optimization problem.

    In the graphical representation above, if you modify the constraint on the land from 12 to 16 (so 4*1k€ = 4k€) and the water constraint from 16 to 22(so 6*2k€ = 12k€), you will see that the optimal solution changes to (10, 6) with a profit from 44 to 60k€ (44 + 4 + 12).

  3. Connecting primal and dual solutions (complementary slackness):
    • If a primal constraint has a positive dual value (\(y_i > 0\)), that primal constraint is binding (slack = 0).
    • If a primal constraint is not binding (has some leftover resource), then the corresponding dual variable must be 0.
  4. Example from the Farmer’s Problem solution:
    • \(y_1 = 1\): The land resource is fully used (slack = 0). One more hectare of land would allow an increase of 1 k€ in the total profit.
    • \(y_2 = 2\): The water resource is also fully used. One more unit of (rescaled) water would allow an increase of 2 k€ in total profit—meaning water is twice as valuable (marginally) compared to land in this setup.
    • \(y_3 = 0\): The tomato seeds resource has slack (we are not using all of them). Hence adding more tomato seeds won’t help.
    • \(y_4 = 0\): The potato seeds resource also has slack, so it is not a limiting factor and has zero marginal worth.

In short, the dual variables tell you how much your objective (profit) would improve if you relaxed (increased) one of the limiting resources. If the dual price is zero, that resource is non-limiting. This is the key economic or operational interpretation behind dual variable values in linear programming.

Interpreting Slack and Body

Slack in a constraint represents the unused portion of that resource. Slack measures leftover capacity in each constraint. Zero slack means you are at the limit of that resource.

  • In the primal, land.slack = 0 means that all 12 hectares of land are used.
  • In the dual, the “slack” in tomato_constraint is how much bigger the left-hand side is compared to 3. When it’s zero, it indicates that constraint is exactly tight.

Body in AMPL typically shows the current value of the left-hand side of the constraint.

  • In the primal, land.body = 12 means the farmer is using all 12 hectares of land.
  • In the primal, tomato_seed.body = 8 means \(x_t = 8\). That satisfies the constraint \(x_t \leq 10\), hence the slack is \(10-8=2\).

Conclusion

Primal problem: Maximize profit by deciding how many hectares of tomatoes and potatoes to plant.

Dual problem: Minimizes the total cost of resources (land, water, tomato seeds, and potato seeds) required to “cover” the profit coefficients of tomatoes and potatoes.

By strong duality, the two problems have the same optimal objective value of 44k€ :

  • Primal solution: \((x_t, x_p) = (8, 4)\).
  • Dual solution: \((y_1, y_2, y_3, y_4) = (1, 2, 0, 0)\).

Strong Duality guarantees that the maximum profit in the primal problem equals the minimum resource cost in the dual problem.