0

enter image description here

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?

Community
  • 1
James
  • 3,997

2 Answers2

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;
0

$$ \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.

orlp
  • 10,508
  • To fix the first constraint, would it be better if we put $\sum x_{INi} \leq 30$, $\sum x_{NBi} \leq 30$ and $x_{IBi} \leq 30$ ? – James Aug 29 '18 at 03:41
  • @JimmySabater That's still not correct. The passengers from $IB$ are always on the airplane, only $IN$ and $NB$ can board/deboard halfway through. This exercise is intentionally being tricky, you have to think carefully. – orlp Aug 29 '18 at 03:42
  • I think I have the fix now: $\sum (IN_i + NB_i) \leq 30 $ and $\sum IB_i \leq 30 $ – James Aug 29 '18 at 03:53
  • @JimmySabater No, that's still not correct, hint: IN + IB and NB + IB, as those passengers are on the plane simultaneously. But I'm not here to verify your every attempt. I'm not responding to future comments, sorry. – orlp Aug 29 '18 at 03:54