4.1 Linear Programming Applications in Business, Finance, Medicine, and Social Science

4.1.1 Introduction to Real-World Linear Programming

In this section, you'll discover how linear programming powers some of the most critical decisions in business, healthcare, and daily life.

The linear programs we solved in Chapter 3 contained only two variables, \(x\) and \(y\), which allowed us to solve them graphically. In practice, linear programs can contain thousands of variables and constraints.

Context Pause

Why move beyond two variables? Because real-world problems are rarely simple. An airline scheduling hundreds of flights with dozens of aircraft types, or a hospital coordinating organ donations across hundreds of patients—these problems demand computational power beyond what we can draw on a graph.

Later in this chapter, we'll learn to solve linear programs with more than two variables using the simplex algorithm, which is a numerical solution method that uses matrices and row operations. However, to make the problems practical for learning purposes, our examples will still have only several variables.

Now that we understand the main concepts behind linear programming, we can also consider how linear programming is currently used in large-scale real-world applications.

Linear programming is used in business and industry for production planning, transportation and routing, and various types of scheduling. Airlines use linear programs to schedule their flights, taking into account both aircraft scheduling and staff assignments. Delivery services use linear programs to schedule and route shipments to minimize time or cost. Retailers use linear programs to determine how to order products from manufacturers and organize deliveries to their stores. Manufacturing companies use linear programming to plan and schedule production. Financial institutions use linear programming to determine the mix of financial products they offer, or to schedule payments transferring funds between institutions. Health care institutions use linear programming to ensure the proper supplies are available when needed. And as we'll see below, linear programming has also been used to organize and coordinate life-saving health care procedures.

Insight Note

Think of linear programming as the mathematics behind efficiency. Every time you get a package delivered faster than expected, or your flight departs on schedule despite complex logistics—there's likely a linear program working behind the scenes.

4.1.1.1 Beyond Basic Linear Programming

In some applications, the techniques used are related to linear programming but are more sophisticated than the methods we study in this class. One such technique is called integer programming. In these situations, answers must be integers to make sense, and cannot be fractions.

Example: You can't schedule 2.7 airplanes or hire 3.4 employees. You need whole numbers.

Problems where solutions must be integers are more difficult to solve than the standard linear programs we've worked with. In fact, many of our textbook problems have been very carefully constructed for learning purposes so that the answers just happen to turn out to be integers. But in the real world, unless we specify integer restrictions, there is no guarantee that a linear program will produce integer solutions.

There are also related techniques called non-linear programs, where the functions defining the objective function and/or some or all of the constraints may be non-linear rather than straight lines.

4.1.1.2 Who Uses These Techniques?

Many large businesses that use linear programming and related methods have analysts on their staff who can perform the analyses needed, including linear programming and other mathematical techniques. Consulting firms specializing in use of such techniques also aid businesses who need to apply these methods to their planning and scheduling processes.

When used in business, many different terms may be used to describe the use of techniques such as linear programming as part of mathematical business models:

These are among the terms used to describe mathematical modeling techniques that may include linear programming and related methods.

In the rest of this section, we'll explore six real-world applications and investigate what they are trying to accomplish using optimization, as well as what their constraints might represent.

4.1.2 Application 1: Airline Scheduling

Airlines use techniques that include and are related to linear programming to schedule their aircraft to flights on various routes, and to schedule crews to the flights. In addition, airlines also use linear programming to determine ticket pricing for various types of seats and levels of service or amenities, as well as the timing at which ticket prices change.

4.1.2.1 Aircraft Scheduling

The process of scheduling aircraft and departure times on flight routes can be expressed as a model that minimizes cost, of which the largest component is generally fuel costs.

Constraints involve considerations such as:

Context Pause

Why is compatibility critical? A massive Boeing 747 requires a runway over 10,000 feet long and specific gate equipment. A small regional jet can land on much shorter runways. Sending the wrong aircraft to the wrong airport isn't just inefficient—it's physically impossible.

A model to accomplish this could contain thousands of variables and constraints. Highly trained analysts determine ways to translate all the constraints into mathematical inequalities or equations to put into the model.

4.1.2.2 Crew Scheduling

After aircraft are scheduled, crews need to be assigned to flights. Each flight needs a pilot, a co-pilot, and flight attendants. Each crew member needs to complete a daily or weekly tour to return back to his or her home base.

Additional constraints on flight crew assignments take into account factors such as:

When scheduling crews to flights, the objective function would seek to minimize total flight crew costs, determined by the number of people on the crew and pay rates of the crew members. However, the cost for any particular route might not end up being the lowest possible for that route, depending on tradeoffs to the total cost of shifting different crews to different routes.

Insight Note

This is the essence of optimization: sometimes making one route slightly more expensive allows the entire system to be cheaper overall. It's like solving a jigsaw puzzle—individual pieces might not look perfect alone, but they create the best picture together.

4.1.2.3 Emergency Schedule Adjustments

An airline can also use linear programming to revise schedules on short notice on an emergency basis when there is a schedule disruption, such as due to weather. In this case, the considerations to be managed involve:

4.1.3 Application 2: Kidney Donation Chain

For patients who have kidney disease, a transplant of a healthy kidney from a living donor can often be a lifesaving procedure. Criteria for a kidney donation procedure include the availability of a donor who is healthy enough to donate a kidney, as well as a compatible match between the patient and donor for blood type and several other characteristics.

Ideally, if a patient needs a kidney donation, a close relative may be a match and can be the kidney donor. However, often there is not a relative who is a close enough match to be the donor.

Context Pause

Why can't any healthy person donate to any patient? Our immune systems are incredibly sophisticated. If the donor's kidney is too different from the patient's tissue type, the patient's immune system will attack and reject the kidney. Blood type and tissue markers must match closely enough to prevent rejection.

Considering donations from unrelated donors allows for a larger pool of potential donors. Kidney donations involving unrelated donors can sometimes be arranged through a chain of donations that pair patients with donors.

Example of a three-donor chain:

Linear programming is one of several mathematical tools that have been used to help efficiently identify a kidney donation chain. In this type of model, patient/donor pairs are assigned compatibility scores based on characteristics of patients and potential donors. The objective is to maximize the total compatibility scores. Constraints ensure that donors and patients are paired only if compatibility scores are sufficiently high to indicate an acceptable match.

Insight Note

This is mathematics saving lives. By finding the optimal chain of donations, linear programming helps patients who would have died waiting for a compatible kidney receive a transplant. It's one of the most inspiring applications of optimization.

4.1.4 Application 3: Advertisements in Online Marketing

Did you ever make a purchase online and then notice that as you browse websites, search, or use social media, you now see more ads related to the item you purchased?

Marketing organizations use a variety of mathematical techniques, including linear programming, to determine individualized advertising placement purchases.

Instead of advertising randomly, online advertisers want to sell bundles of advertisements related to a particular product to batches of users who are more likely to purchase that product. Based on an individual's previous browsing and purchase selections, he or she is assigned a “propensity score” for making a purchase if shown an ad for a certain product.

The company placing the ad generally does not know individual personal information based on the history of items viewed and purchased, but instead has aggregated information for groups of individuals based on what they view or purchase. However, the company may know more about an individual's history if he or she logged into a website making that information identifiable, within the privacy provisions and terms of use of the site.

The company's goal is to buy ads to present to specified size batches of people who are browsing. The linear program would assign ads and batches of people to view the ads using an objective function that seeks to maximize advertising response modeled using the propensity scores. The constraints are to stay within the restrictions of the advertising budget.

Context Pause

Why use linear programming instead of just showing ads to everyone? Advertising costs money—every click, every impression. Companies want maximum return on their advertising investment. Linear programming helps them spend their budget on the people most likely to actually buy, rather than wasting money showing ads to people who will ignore them.

4.1.5 Application 4: Loans

A car manufacturer sells its cars through dealers. Dealers can offer loan financing to customers who need to take out loans to purchase a car. Here we will consider how car manufacturers can use linear programming to determine the specific characteristics of the loan they offer to a customer who purchases a car. (In a future chapter, we will learn how to do the financial calculations related to loans.)

A customer who applies for a car loan fills out an application. This provides the car dealer with information about that customer. In addition, the car dealer can access a credit bureau to obtain information about a customer's credit score.

Based on this information obtained about the customer, the car dealer offers a loan with certain characteristics, such as:

Linear programming can be used as part of the process to determine the characteristics of the loan offer. The linear program seeks to maximize the profitability of its portfolio of loans.

The constraints limit the risk that the customer will default and will not repay the loan. The constraints also seek to minimize the risk of losing the loan customer if the conditions of the loan are not favorable enough; otherwise, the customer may find another lender, such as a bank, which can offer a more favorable loan.

Insight Note

This is a delicate balancing act. Charge too high an interest rate, and the customer goes to a competitor. Charge too low, and the dealer doesn't make enough profit or takes on too much risk. Linear programming finds the “sweet spot” where the dealer maximizes profit while keeping the customer happy and the risk acceptable.

4.1.6 Application 5: Production Planning and Scheduling in Manufacturing

Consider the example of a company that produces yogurt. There are different varieties of yogurt products in a variety of flavors. Yogurt products have a short shelf life; it must be produced on a timely basis to meet demand, rather than drawing upon a stockpile of inventory as can be done with a product that is not perishable.

Most ingredients in yogurt also have a short shelf life, so cannot be ordered and stored for long periods of time before use; ingredients must be obtained in a timely manner to be available when needed but still be fresh. Linear programming can be used in both production planning and scheduling.

4.1.6.1 The Process

Step 1: Sales forecasts are developed to determine demand to know how much of each type of product to make.

Step 2: There are often various manufacturing plants at which the products may be produced. The appropriate ingredients need to be at the production facility to produce the products assigned to that facility.

Step 3: Transportation costs must be considered, both for obtaining and delivering ingredients to the correct facilities, and for transport of finished product to the sellers.

Context Pause

Why is this so complex? Imagine you have three yogurt factories: one in California, one in Texas, and one in New York. California has cheaper milk, but shipping yogurt to New York costs more. Texas is centrally located for distribution but has higher labor costs. New York is close to major markets but has expensive real estate. Linear programming weighs all these factors simultaneously to minimize total costs.

The linear program that monitors production planning and scheduling must be updated frequently—daily or even twice each day—to take into account variations from a master plan.

4.1.7 Application 6: Bike Share Programs

Over 600 cities worldwide have bikeshare programs. Although bikeshare programs have been around for a long time, they have proliferated in the past decade as technology has developed new methods for tracking the bicycles.

4.1.7.1 How Bikeshare Programs Work

Bikeshare programs vary in the details of how they work, but most typically people pay a fee to join and then can borrow a bicycle from a bike share station and return the bike to the same or a different bike share station.

Over time, the bikes tend to migrate; there may be more people who want to pick up a bike at station A and return it at station B than there are people who want to do the opposite. (In Chapter 9, we'll investigate a technique that can be used to predict the distribution of bikes among the stations.)

4.1.7.2 Redistributing Bikes

Once other methods are used to predict the actual and desired distributions of bikes among the stations, bikes may need to be transported between stations to even out the distribution. Bikeshare programs in large cities have used methods related to linear programming to help determine the best routes and methods for redistributing bicycles to the desired stations once the desired distributions have been determined.

The optimization model would seek to minimize transport costs and/or time subject to constraints of having sufficient bicycles at the various stations to meet demand.

Insight Note

Think of this like a city-wide balancing act. Morning commuters ride from residential neighborhoods to downtown offices. Evening commuters do the reverse. Without optimization, downtown would be flooded with bikes in the morning and empty by evening. Linear programming keeps the system balanced so bikes are where people need them, when they need them.

Problem Set 4.1

Source: Applied Finite Mathematics 3rd Edition

1. Give three examples of industries that use linear programming to improve their operations.

Problem 1 Solution

Three industries using linear programming:

  • Airlines (flight and crew scheduling, ticket pricing)
  • Manufacturing (production planning and scheduling)
  • Healthcare (organ donation matching, resource allocation)

Other acceptable answers include: Financial institutions (loan optimization), Retail (supply chain and delivery), Transportation/Delivery services (routing and scheduling), Online advertising/marketing (ad placement optimization), and Bikeshare programs (bicycle redistribution).

2. What is integer programming, and why is it more difficult to solve than standard linear programming?

Problem 2 Solution

Integer programming is a type of optimization where the decision variables are restricted to integer (whole number) values, rather than allowing any real-number (fractional) values.

Why it is more difficult:

Step 1: In standard linear programming, the feasible region is a continuous convex polytope, and the optimal solution lies at a vertex. Efficient algorithms like the simplex method can move along edges to find this vertex.

Step 2: In integer programming, we cannot simply find the optimal continuous solution and round it. Rounding may violate constraints or move far from the true optimum.

Step 3: Instead, integer programming often requires branch-and-bound or cutting-plane algorithms that systematically explore many possible combinations of integer values. In the worst case, the number of combinations grows exponentially with the number of variables.

Example: You can't schedule 2.5 flights or hire 3.7 employees — the answer must be a whole number, and finding the best combination of whole numbers is fundamentally harder than finding the best point in a continuous region.

3. In airline scheduling, what are two major types of constraints that must be considered when scheduling aircraft?

Problem 3 Solution

Two major aircraft scheduling constraints:

Constraint 1: Tour completion — Each aircraft needs to complete a daily or weekly tour that returns it to its point of origin. Airlines cannot strand planes at the wrong airports; every aircraft must cycle back to its home base.

Constraint 2: Airport compatibility — Aircraft must be compatible with the airports they depart from and arrive at. Not all airports can handle all types of planes. For example, a Boeing 747 requires a runway over 10,000 feet long and specific gate equipment, while a small regional jet can use much shorter runways.

Other acceptable answers: Scheduling sufficient flights to meet passenger demand on each route; scheduling the right type and size of aircraft on each route to match demand levels.

4. Explain how a kidney donation chain works and how linear programming helps maximize successful matches.

Problem 4 Solution

How a kidney donation chain works:

Step 1: A patient needs a kidney transplant, but their willing donor (usually a relative) is not a compatible match for them specifically.

Step 2: Multiple incompatible patient-donor pairs are identified across different hospitals or regions.

Step 3: A chain is organized where each donor gives a kidney to a different patient with whom they are compatible:

  • Donor A (related to Patient A but incompatible) donates to Patient B
  • Donor B (related to Patient B but incompatible) donates to Patient C
  • Donor C (related to Patient C but incompatible) donates to Patient A

This way, every patient receives a compatible kidney even though their own relative couldn't donate directly to them.

How linear programming helps:

Step 4: Patient/donor pairs are assigned compatibility scores based on blood type, tissue markers, and other medical characteristics.

Step 5: A linear program is formulated with the objective function to maximize total compatibility scores across all matches in the chain.

Step 6: Constraints ensure that donors and patients are paired only if their compatibility scores are sufficiently high to indicate an acceptable medical match, reducing the risk of organ rejection.

The result: more patients receive life-saving transplants than would be possible through individual pairings alone.

5. In the context of online advertising, what is a “propensity score” and how is it used in optimization?

Problem 5 Solution

What is a propensity score:

A propensity score is a numerical value assigned to an individual (or group of individuals) that represents the likelihood they will make a purchase if shown an advertisement for a specific product. It is calculated based on the individual's previous browsing history and purchase behavior.

How it is used in optimization:

Step 1: Marketing companies collect aggregated data on user browsing and purchase patterns.

Step 2: Based on this data, each user (or batch of similar users) is assigned a propensity score for various product categories.

Step 3: A linear program is formulated where:

  • Decision variables determine which ads are shown to which batches of users
  • Objective function maximizes the total expected advertising response (using the propensity scores as weights — higher scores mean more likely to respond)
  • Constraints ensure the total advertising spend stays within the company's budget

Result: Instead of showing ads randomly to everyone, the optimization directs ad spending toward users most likely to respond, maximizing return on advertising investment.

6. Why do car dealers use linear programming when offering loans to customers? What are they trying to optimize and what constraints do they face?

Problem 6 Solution

Why car dealers use linear programming for loans:

Car dealers offer financing to customers who purchase vehicles. The characteristics of each loan (interest rate, loan amount, repayment period) must be tailored to each customer to balance profitability against risk and competitiveness.

What they are trying to optimize:

The objective function seeks to maximize the profitability of the dealer's overall portfolio of loans. This involves finding the best combination of loan terms across all customers.

Constraints they face:

Constraint 1: Default risk — The loan terms must limit the risk that the customer will fail to repay. A customer with a lower credit score represents higher default risk, so loan terms must account for this (e.g., higher interest rates, shorter terms, or smaller loan amounts for riskier borrowers).

Constraint 2: Competitive risk — The loan terms must be favorable enough that the customer doesn't seek financing elsewhere (e.g., from a bank or credit union offering better rates). If terms are too unfavorable, the dealer loses the loan customer entirely.

The balancing act: Charge too high an interest rate → customer goes to a competitor. Charge too low → dealer doesn't make sufficient profit or takes on excessive risk. Linear programming finds the optimal balance using the customer's credit score, application information, and market conditions.

7. Why must yogurt production planning be updated daily or even twice daily, unlike production planning for non-perishable goods?

Problem 7 Solution

Why yogurt production planning requires frequent updates:

Reason 1: Perishable product — Yogurt has a short shelf life. Unlike non-perishable goods (canned food, electronics, etc.), yogurt cannot be manufactured in advance and stored in a warehouse for months. It must be produced on a timely basis to match demand, not drawn from a stockpile of inventory.

Reason 2: Perishable ingredients — Most ingredients in yogurt (milk, fruit, cultures) also have a short shelf life. They cannot be ordered in bulk and stored for long periods. Ingredients must be obtained just in time — fresh enough for use, but available when needed for production.

Reason 3: Demand variability — Sales forecasts change based on actual daily sales data, seasonal trends, weather, promotions, and other factors. The production plan must be updated frequently to reflect the latest demand information.

Reason 4: Multi-facility coordination — Products may be produced at various manufacturing plants. Each facility needs the right ingredients at the right time, and finished products must be transported to the right sellers. Any variation from the master plan requires rapid recalculation of the optimal production schedule.

For non-perishable goods, companies can build inventory buffers and update plans weekly or monthly. For perishable goods like yogurt, the linear program must be rerun daily or even twice daily to incorporate the latest data and keep production aligned with rapidly changing conditions.

8. In bikeshare programs, what problem does linear programming help solve, and what is the objective function?

Problem 8 Solution

The problem linear programming helps solve:

In bikeshare programs, bicycles tend to migrate — they accumulate at some stations and become depleted at others due to one-directional commuting patterns. For example, morning commuters ride from residential neighborhoods to downtown offices, causing downtown stations to overflow while residential stations become empty. The reverse happens in the evening.

Once predictive methods determine the desired distribution of bikes across all stations, bikes must be physically transported between stations to rebalance the system. Linear programming helps determine the best routes and methods for redistributing bicycles to achieve the desired distribution.

The objective function:

The objective function seeks to minimize transport costs and/or time for redistributing the bikes.

Subject to constraints:

  • Each station must have sufficient bicycles to meet predicted demand
  • No station should be overstocked beyond its capacity
  • The total number of bikes redistributed must balance (bikes removed from one station must arrive at another)
  • Vehicle/truck capacity constraints for the redistribution fleet

9. List three different terms used in business to describe mathematical modeling techniques that include linear programming.

Problem 9 Solution

Three terms used in business for mathematical modeling techniques that include linear programming:

  1. Operations research — The discipline of applying advanced analytical methods to help make better decisions
  2. Business analytics — Using data analysis and mathematical models to guide business strategy
  3. Data science — Extracting insights from data using statistical and mathematical techniques

Other acceptable answers include:

  • Optimization — Finding the best solution from a set of feasible alternatives
  • Industrial engineering — Designing and improving complex systems and processes
  • Management science — Applying scientific methods to management decision-making

All of these fields may use linear programming and related methods (integer programming, non-linear programming) as part of their toolkit for mathematical business modeling.

10. Choose one of the six applications discussed in this section and explain in your own words why optimization is valuable for that application.

Problem 10 Solution

Application explanation (answers will vary — sample for airline scheduling):

Optimization is valuable for airline scheduling because airlines operate on thin profit margins, and fuel costs are their largest expense. By using linear programming to minimize fuel costs while meeting all constraints (aircraft compatibility with airports, crew rest regulations, passenger demand on each route, etc.), airlines can save millions of dollars annually.

Why it matters in practice:

  • Airlines operate hundreds of aircraft across thousands of routes daily — the number of possible combinations is astronomical
  • Without mathematical optimization, human schedulers would have to rely on experience and intuition, inevitably missing cost-saving opportunities
  • When disruptions occur (weather delays, mechanical issues), optimization helps airlines recover quickly by recalculating optimal rescheduling, minimizing cascading delays across the network
  • This improves customer satisfaction and reduces costs from rebooking, hotel accommodations, and compensation for stranded passengers

Key takeaway: The scale and complexity of airline operations make manual optimization impossible. Linear programming and related techniques allow airlines to find solutions that balance cost, safety, regulations, and customer service simultaneously — something no human planner could achieve for a problem this large.

Note: Other valid application choices include kidney donation chains (saving lives through optimal matching), online advertising (maximizing ROI on ad spend), car loans (balancing profit and risk), yogurt manufacturing (coordinating perishable supply chains), or bikeshare programs (keeping bikes where riders need them).