Formulating a problem as linear programming optimization problem

Question

Attempt:

Let $x_{INi}$ be the number of people who travel from Ithaca to Newark in class $i$ where $i=1,2,3$ where each number represents class Y,B, and M, respectively, by simplicity. Similarly, write $x_{NBi}$ and $x_{IBi}$. Our goal is to maximize

$$ z = 300x_{IN1}+220x_{IN2}+100x_{IN3} + 160 x_{NB1} + 130 x_{NB2} + 80 x_{NB3} + 360x_{IB1} + 280 x_{IB2} + 140 x_{IB3} $$

Now, let us focus on the constraints. First of all,

$$ \sum_{i=1}^3 (x_{INi}+x_{NBi}+x_{IBi}) \leq 30 $$

moreover, we must have

$$ 4x_{IN1}+8 x_{IN2} + 22 x_{IN3} \leq 34 $$

$$ 8 x_{NB1} + 13 x_{NB2} + 20 x_{NB3} \leq 41 $$

$$ 3 x_{IB1} + 10 x_{IB2} + 18 x_{IB3} \leq 31 $$

and finally, all the $x's$ must be positive.

Is this a correct formulation?

Answer 1

The following constraints must be respected.

The plane cannot seat more than 30 passengers.

What you know is that:

1. At first, the plane contains passengers that travel from Ithaca to Boston and Ithaca to Newark
2. After landing in Newark, the place will board passengers from Newark to Boston while seating passengers from Ithaca to Boston.

Therefore, $X_{IN} + X_{IB} \le 30$ and $X_{IB} + X_{NB} \le 30$ are necessary constraints. Here, $X_{IN} = X_{IN}^Y + X_{IN}^M + X_{IN}^B$ (and similarly for $X_{IB}$, $X_{NB}$).

Number of available tickets cannot exceed forecasted demand.

As an example, let's take the constraints related to $X_{IN}$.

$$ 0 \le X_{IN}^Y \le 4, \qquad 0 \le X_{IN}^B \le 8, \qquad 0 \le X_{IN}^M \le 22. $$

As pointed out in the comments, it is better to explicitly write down each constraint separately. Indeed, $X_{IN} \le 4 + 8 + 22$ would not contain any information about the upper bound of each fare class.

Maximize revenue.

Similarly to what you already proposed, this gets translated into maximizing

$$ Z := 300X_{IN}^Y + 220X_{IN}^B + 100X_{IN}^M + (\text{amounts related to other variables}) $$

---

Your approach seems to mix 0/1 programming with linear programming, particularly in the last set of equations. How are they meant to be interpreted?

---

Problem encoding in MiniZinc

var 0..4: a;
var 0..8: b;
var 0..22: c;
var 0..8: d;
var 0..13: e;
var 0..20: f;
var 0..3: g;
var 0..10: h;
var 0..18: i;

var int: revenue = 300*a + 220*b + 100*c + 160*d + 130*e + 80*f + 360*g + 280*h + 140*i;

constraint a + b + c + d + e + f <= 30;
constraint a + b + c + g + h + i <= 30;

solve maximize revenue;

Answer 2

$$ \sum_{i=1}^3 (x_{INi}+x_{NBi}+x_{IBi}) \leq 30 $$

This constraint is incorrect. Consider that 30 passengers could enter at Ithaca and leave the airplane at Newark. Now your plane flies empty between Newark and Boston because this constraint disallows the empty seats to be filled.

Your other set of constraints is wrong as well. Right now you allow $5$ $IN1$ customers to book (since $4\cdot 5 \leq 34$), while the airplane can only accommodate $4$.

You really have to think more carefully, and be less inclined to try to "combine" multiple constraints into a single equation.