Research in the library, the textbook, and/or online to find a business example of linear programming.
You may use any business-related example you desire as long as it contains the information you need to show your knowledge of linear programming to complete the paper successfully.
In your paper,
Describe how and why your chosen business example deployed linear programming.
Analyze the method of linear programming used by your chosen company. Did it work in their favor? Would you recommend a different methodology?
Explain how the business used linear programming to optimize resources like budget, time, people, and/or machinery.
List the benefits that this business received as a result of deploying linear programming.
How Deployed: The airline first develops a long-term flight schedule. Then, it uses LP to solve the problem in two stages:
Crew Pairing: This is the massive LP model that groups individual flights into valid, multi-day sequences (pairings) that begin and end at a crew base.
Crew Rostering (Assignment): A subsequent model assigns these pairings to individual crew members for a month, respecting seniority, vacation, and training constraints.
Analysis of the Linear Programming Method
The specific method used for crew scheduling is often a complex variation of standard LP, specifically a Set Partitioning Problem or a Set Covering Problem.
Method Used: Set Partitioning Problem
Model: The airline defines an Objective Function to minimize the total cost of all selected pairings (including flying costs and layover costs). The Constraints ensure that every single scheduled flight leg is covered by exactly one crew pairing.
Worked in their Favor? Absolutely. The deployment of large-scale LP, solved by sophisticated algorithms like the Simplex Method or Interior Point Methods tailored for this specific structure, revolutionized airline efficiency. It allowed airlines to reduce operating costs by millions of dollars annually by finding more efficient pairings that minimized deadheading (flying a crew member as a passenger) and optimized layover locations.
Recommendation: I would not recommend a different methodology for the core problem. LP, specifically integer linear programming (as crew pairings must be whole, indivisible units), remains the most robust and mathematically proven method for finding the true optimal solution to this kind of large-scale assignment problem. The key is in using decomposition techniques (like column generation) to handle the billions of potential variables, which is a method within the LP framework.
Sample Answer
Linear Programming in Airline Crew Scheduling
One of the most complex and successful business applications of Linear Programming (LP) is Airline Crew Scheduling and Crew Rostering. Major airlines use sophisticated LP models to assign flight crew (pilots and flight attendants) to a massive, predetermined flight schedule while adhering to numerous contractual, regulatory, and logistical constraints.
How and Why Linear Programming Was Deployed
Airlines deployed Linear Programming to solve the dual problem of minimizing cost and maximizing efficiency in their crew operations.
Why Deployed: The cost of crew salaries, benefits, and layover expenses represents a significant portion of an airline's operating budget. Moreover, crew assignments are strictly governed by Federal Aviation Administration (FAA) regulations (e.g., maximum flight hours, minimum rest periods) and union contracts. Manually creating schedules that satisfy millions of variables (flights, crew members, time, location) and thousands of rules while