# Linear Programming problem of accepting reservations on different fare classes to maximize revenue

this question has my stuck, I am unsure on how to incorporate the some of the information into constraints and without them the answer seems a bit silly. Below is the question, please let me know how you would go about formulating it:

Two aircraft, each with a capacity of 156 seats. The daily schedule of these aircrafts is shown in Table 1.

The company offers discounted (D-class) and full-fare class (F-class). D-class must be purchased two weeks in advance of flight departure and are non-refundable, non-changeable. F-class tickets can be purchased anytime and fully refundable and changeable. The prices and demands for both classes are given in Table 2.

The task is to formulate the problem of accepting reservations on different fare classes to maximize revenue as a linear programme.

I'm not even sure if table 1 has any useful information to this task.

• Table $1$ indeed seems irrelevant. – Shubham Johri Dec 12 '19 at 17:04
• That is exactly my thoughts. I don;t see how that has any relevance to the problem. – FrosT Dec 12 '19 at 17:52
• The main issue I am having is that if I don't include the fact that class F can cancel somehow (but no cancellation statistics are given) it isn't really a linear programming issue as it is as simple as fill the demand of D and then the rest of the capacity should be F as it has a higher profit. – FrosT Dec 12 '19 at 17:53

Table $$2$$ gives $$8$$ possible journeys between various cities. Let the number of $$D$$ and $$F$$ class reservations for the $$i^{\text{th}}$$ journey be $$d_i,f_i\ge0$$. Then the first set of constraints is the upper-bound on $$d_i,f_i$$:$$d_1\le25,f_1\le20\\d_2\le55,f_2\le40$$and so on.

Both planes have a capacity of $$156$$, so on each stretch out of the $$8$$ stretches$$(A\to B,B\to C,C\to B,B\to A;D\to B,B\to E,E\to B,B\to D)$$, there must be $$\le156$$ passengers on either plane. For example, a passenger travels on the stretch $$A\to B$$ iff he/she takes any one of journeys $$1,2,3$$ and thus, $$(d_1+d_2+d_3)+(f_1+f_2+f_3)\le156$$.

Similarly, passengers travel on stretch $$B\to C$$ iff they undertake any one of journeys $$2,5,7$$; stretch $$D\to B$$ iff they undertake journeys $$4,5,6$$; stretch $$B\to E$$ iff they undertake journeys $$3,6,8$$.

The objective function to maximize is quite obviously the revenue given by $$150d_1+200f_1+270d_2+400f_2+...+200d_8+300f_8$$.

I solved the LPP in Excel and the solution I got is:

• Perfect, for some reason I couldn't put together the fact that journey A-C requires A-B and B-C flights and so on. Much appreciated. – FrosT Dec 13 '19 at 0:01
• @FrosT If you are satisfied with this answer, consider accepting it by pressing the tick mark button on the left. – Shubham Johri Dec 13 '19 at 9:48
• I added the Excel solution. – Shubham Johri Dec 13 '19 at 10:27
• Great, I got the same answer in excel solver however using other solvers like LINDO and online optimizer I got different answers. Those two got the same answers but were lower than the one in Excel. I inputed the values given by the other software in excel and I get the same answer so the equasions seem to be correct but it isn't reaching as high of a revenue. Any idea why that might be the case? – FrosT Dec 13 '19 at 10:40
• Other than checking the cost coefficients and conditions inputted again, I don't think I can comment on the other solutions. – Shubham Johri Dec 13 '19 at 11:06