7.3: 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 the last section contain only two variables, \(x\) and \(y\), so that we could 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, which is a numerical solution method that uses matrices and row operations. However, in order to make the problems practical for learning purposes, our problems 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 in production planning, transportation and routing, and various types of scheduling. Airlines use linear programs to schedule their flights, taking into account both scheduling aircraft and scheduling staff. Delivery services use linear programs to schedule and route shipments to minimize shipment time or minimize cost. Retailers use linear programs to determine how to order products from manufacturers and organize deliveries with 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.

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 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 that as a restriction, there is no guarantee that a linear program will produce integer solutions. There are also related techniques that are 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.

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. Optimization, operations research, business analytics, data science, industrial engineering hand management science are among the terms used to describe mathematical modelling techniques that may include linear programming and related met

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 use techniques that include and are related to linear programming to schedule their aircrafts 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.

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:

• Each aircraft needs to complete a daily or weekly tour to return back 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 for the demand for number of passengers.
• Aircraft must be compatible with the airports it departs from and arrives at - 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 to put into the model.

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:

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

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.

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:

• Getting aircrafts 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 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. Considering donations from unrelated donor 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 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.

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 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 modelled using the propensity scores. The constraints are to stay within the restrictions of the advertising budget.

Loans

A car manufacturer sells its cars though 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 interest rate, loan amount, and length of loan repayment period.

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.

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 can not 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.

To start the process, sales forecasts are developed to determine demand to know how much of each type of product to make.

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. Transportation costs must be considered, both for obtaining and delivering ingredients to the correct facilities, and for transport of finished product to the sellers.

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.

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.

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.

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 desire 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.