9.1: Introduction to Linear Programming Applications in Business, Finance, Medicine, and Social Science

Learning Objectives

In this section, you will learn about real-world applications of linear programming and related methods.

The linear programs we solved in Chapter 7 contain only two variables, \(x\) and \(y\), allowing us to solve them graphically. In practice, linear programs can contain thousands of variables and constraints. Later in this chapter, we’ll learn to solve linear programs with more than two variables using the simplex algorithm, a numerical solution method that utilizes matrices and row operations. However, to make the problems practical for learning purposes, our problems will still have only a few variables. Now that we understand the main concepts behind linear programming, we can also consider how it is currently applied in large-scale, real-world applications.

Linear programming is utilized in business and industry for production planning, transportation and routing, as well as various types of scheduling. Airlines use linear programming to schedule their flights, taking into account both the scheduling of aircraft and staff. Delivery services utilize linear programs to schedule and route shipments, aiming to minimize either shipment 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 utilize linear programming to determine the optimal mix of financial products to offer or to schedule payments and transfer funds between institutions. Healthcare institutions use linear programming to ensure the proper supplies are available when needed. As we’ll see below, linear programming has also been used to organize and coordinate lifesaving healthcare procedures.

In some of the 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 can not be fractions. Problems, where solutions must be integers, are more difficult to solve than the linear programs we’ve worked with. In fact, many of our problems have been carefully constructed for learning purposes, so that the answers happen to turn out to be integers. However, in the real world, unless we specify that as a restriction, there is no guarantee that a linear program will produce integer solutions. There are also related techniques known as non-linear programs, where the functions defining the objective function and/or some or all of the constraints may be non-linear rather than linear.

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

When used in business, various terms may be employed to describe the application of techniques such as linear programming within mathematical business models. Optimization, operations research, business analytics, data science, industrial engineering, and management science 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.

Airline Scheduling

Airlines employ techniques related to linear programming to schedule their aircraft for flights on various routes and to schedule crews for these 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 of ticket price changes.

The process of scheduling aircraft and departure times on flight routes can be modeled to minimize costs, with the largest component typically being fuel costs.

Constraints involve considerations such as:

• Each aircraft needs to complete a daily or weekly tour to return to its point of origin.
• Scheduling sufficient flights to meet demand on each route.
• Scheduling the right type and size of aircraft on each route to be appropriate for the route and the demand for a number of passengers.
• Aircraft must be compatible with the airports from which they depart and to which they arrive - not all airports can handle all types of planes.

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 that can be incorporated into the model.

After aircraft are scheduled, crews must be assigned to the corresponding 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 to their home base. Additional constraints on flight crew assignments take into account factors such as:

• Pilot and co-pilot qualifications to fly the particular type of aircraft they are assigned to.
• Flight crews have restrictions on the maximum amount of flying time per day and the length of mandatory rest periods between flights, which must meet certain minimum rest time regulations.
• The number of crew members required for a particular type or size of aircraft.

When scheduling crews for flights, the objective function aims to minimize total flight crew costs, which are determined by the number of crew members and their respective pay rates. However, the cost for any particular route might not ultimately be the lowest possible for that route, depending on the tradeoffs made to the total cost of shifting different crews to different routes.

An airline can also use linear programming to revise schedules on short notice in emergencies, such as when a schedule disruption occurs due to adverse weather conditions. In this case, the considerations to be managed involve:

• Getting aircraft and crews back on schedule as quickly as possible.
• Moving aircraft from storm areas to areas with calm weather to keep the aircraft safe from damage and ready to come back into service as quickly and conveniently as possible.
• Ensuring crews are available to operate the aircraft and that crews continue to meet mandatory rest period requirements and regulations.

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 healthy donor and a compatible match between the patient and donor in terms of blood type and several other characteristics. Ideally, if a patient needs a kidney donation, a close relative may be a suitable match and can serve as the kidney donor. However, often there is not a relative who is a close enough match to be the donor. 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. For example, a kidney donation chain with three donors might operate as follows:

• Donor A donates a kidney to Patient B.
• Donor B, who is related to Patient B, donates a kidney to Patient C.
• Donor C, who is related to Patient C, donates a kidney to Patient A, who is related to Donor A.

Linear programming is one of several mathematical tools 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.

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 utilize a range of mathematical techniques, including linear programming, to determine personalized advertising placement and 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 purchasing selections, they are assigned a “propensity score” indicating their likelihood of purchasing a product if shown an ad for that product. The company placing the ad generally does not know individual personal information based on the history of items viewed and purchased. Instead, it has aggregated information for groups of individuals based on what they view or purchase. However, the company may have more information about an individual’s history if they 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 budget restrictions.

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 previous chapter, we will learn how to perform 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 the information obtained about the customer, the car dealer offers a loan with specific characteristics, including the interest rate, loan amount, and length of the loan repayment period.

Linear programming can be used as part of the process to determine the characteristics of the loan offer. The linear program aims to maximize the profitability of its loan portfolio. The constraints limit the risk that the customer will default and not repay the loan. The constraints also aim to minimize the risk of losing the loan customer if the loan conditions are not favorable enough; otherwise, the customer may seek another lender, such as a bank, which can offer more favorable loan terms.

Production Planning and Scheduling in Manufacturing

Consider the example of a company that produces yogurt. There are various varieties of yogurt products available in a range of flavors. Yogurt products have a short shelf life; they 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 they 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, yet still be fresh. Linear programming can be used in both production planning and scheduling.

To initiate the process, sales forecasts are developed to determine demand and the quantity of each product type to manufacture.

There are often various manufacturing plants at which the products may be produced. The appropriate ingredients must be available at the production facility to produce the products assigned to that facility. Transportation costs must be considered, both for obtaining and delivering ingredients to the correct facilities and for transporting the finished product to the sellers.

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

Bike Share Programs

Over 600 cities worldwide have bike share programs. Although bike share 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.

Bike share programs vary in the details of how they operate, but most typically, people pay a fee to join and then can borrow a bicycle from a bike share station, returning it to the same station or a different one. 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.

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. Bike share programs in large cities have employed methods related to linear programming to determine the optimal routes and methods for redistributing bicycles to the desired stations once the desired distributions have been established. The optimization model seeks to minimize transport costs and/or time, subject to the constraint of having sufficient bicycles at the various stations to meet demand.