How do you maximise 2x₁ + 3x₂ under the given linear constraints?

Question

Maximise f(x₁, x₂) = 2x₁ + 3x₂ subject to:

• 4x₁ + 5x₂ ≤ 7;
• 7x₁ + 4x₂ ≤ 8;
• 9x₁ + 8x₂ ≤ 9;
• x₁ ≥ 0;
• x₂ ≥ 0.

Explanation

Since x₁ ≥ 0:

2x₁ + 3x₂ ≤ (3/8)(9x₁ + 8x₂) ≤ 27/8.

The first inequality follows from 2 ≤ 27/8 and x₁ ≥ 0; the second follows from 9x₁ + 8x₂ ≤ 9.

Check that the bound is attained at (0, 9/8):

• 4x₁ + 5x₂ = 45/8 ≤ 7;
• 7x₁ + 4x₂ = 9/2 ≤ 8;
• 9x₁ + 8x₂ = 9;
• both variables are nonnegative.

The point is feasible and its objective value is 27/8. The upper bound is therefore the maximum.