Let us understand what linear programming is. In order to remand a company, you need resources such as manpower, raw materials, funds, equipment, etc. All of these resources are generally available in limited quantities to the company. With this limitation or constraint, the company would like to maximize their profit or reduce the cost. Hence, the company’s management has to decide the most efficient manner in which these limited resources should be used to achieve the desired objective of profit maximization or cost minimization. 

Linear programming is a technique that can help management in this decision-making process. So linear programming is a mathematical technique for allotting limited resources to a company in an optimal manner. Some of the examples where linear programming can help find solutions. 

  1. Diet mix—what do we mean by this? Linear programming can help us find the cheapest combination of foods that will satisfy all our nutritional requirements.
  2. Investment decisions: Linear programming can help minimize the risk in your investment portfolio, subject to achieving a certain return.
  3. Product mix: Linear programming can help in deciding the product mix to be manufactured in order to generate more profit.
  4. Linear programming can also help us in deciding on the advertising that is determining the number of revising units of different realizing media. For example, newspapers, radio, and television are used to ensure maximum exposure.
  5. Crew scheduling: airlines have to assign crews to their flights so as to make sure that each flight is covered. Each pilot can fly only a certain amount each day, and so on. Now the airlines run on a small profit margin, so saving a few percent through good scheduling can make an enormous difference in terms of profitability.
  6. Traveling salesman: Linear programming can help in selecting the shortest route for a salesman starting from a given city, visiting each of the specified cities, and then returning back to the starting city.

In subsequent videos, we will cover details of how linear programming can help in each of these examples. There are multiple other applications of linear programming where linear programming can help us decide in order to optimize the use of resources.

Each LP problem involves three stages.

Stage 1: Problem identification. This is the stage where you identify the problem that you want to solve. You could have a problem at work, at home, or at play that you want to identify and then solve using the LP method. In this stage, you would identify and specify the problem. You would establish relations between the variables, and then you would identify the constraints. This could involve identifying the available hours or defying the constraints with regards to space, material, or money. So once you have identified the problem that you want to solve, the next stage is problem formulation.

Stage 2: Once you have collected all the data in this stage of problem identification, in problem formulation, you will construct a mathematical model from the available data. In order to construct the mathematical model, first you have to identify the decision variables, then you have to identify the objective function, and you also have to set up mathematical equations for the constraints. Once you have formulated the problem, the next step is to solve it.

Stage 3: In this stage, you will identify the method that you will use to solve this problem. Then you would obtain the solution to the problem with the help of the selected method, and then you would test the solution for optimality. Generally, these methods would be either graphical or simplex methods. The graphical method uses graphs to solve the problem and find the optimal solution. This you would use generally when there are two decision variables.
The simplex method is more of an iterative process involving a series of automatic steps. This method can be used for solving complicated programming problems involving two or more decision variables. Out of these three stages of an LP problem, generally stage number two is the most important because, once you have correctly formulated the problem, you can easily solve it using the graphical or simplex method.

Let us understand some of the terminology of linear programming. 

Let us consider a hypothetical case just in order to understand these terms in an easier manner. Let’s say you want to buy a car. Your requirement is to have the car within a budget of $20000, and you also think that the car should have a mileage of at least 30 miles per gallon. So the question in your mind is, which car should you buy in order to maximize its value?

Decision variable: The unknown which you’d be finding by solving the problem (which car to buy).

Constraint: Represents mathematical equations of the limitations (price and mileage) imposed by the problem. 

Objective function: It represents a mathematical equation of the major goals of the system in terms of unknowns (which car for maximum value)?

Let’s take 4 different cars and see which car satisfies the problem.

  1. Car 1: Sonata. Price – $18000, mileage – 28 miles per gallon.
  2. Car 2: Honda city. Price – $22000, mileage – 25 miles per gallon.
  3. Car 3: Corolla. Price – $16000, mileage – 35 miles per gallon.
  4. Car 4: Civic. Price – $16000, mileage – 32 miles per gallon.

With this data, you now want to analyze which of these cars meets your constraints. For the Sonata, the price is $18,000, which definitely meets our budget, but the mileage is 28 miles per gallon, which does not meet our second constraint. So this doesn’t meet the constraint.

For our selection, the next car, the Camry, costs $22,000, which is more than 20,000 under our constraint, and the mileage is 25 miles per gallon, which
again doesn’t meet our mileage constraint, so this car also cannot be selected.

The next car is a Corolla. The price is $16,000, and the mileage is 35 miles per gallon. So this meets our criteria for the constraints. The price of a Civic is $16,000, which meets the first constraint, and the mileage is 32 miles per gallon, which also meets the second constraint. So this car also meets both constraints.

So this is our feasible solution, and in this feasible solution, we have two cars: one is a Corolla and one is a Civic. However, our objective is to maximize the value, so we have to optimize the value that we get out of the car that we are purchasing. And out of these 2 cars, the Corolla gives better mileage at the
same price. Hence, Corolla becomes our optimal solution.

A feasible solution is a set of values for the decision variables that satisfy all the constraints and non-negative restrictions. Non-negative restriction means that none of the decision variables can be less than 0. It has to be 0 or more than 0.

So a feasible solution that optimizes the objective function is called an optimal solution. So our objective function in this example that we saw was to maximize the value. So a feasible solution that optimizes the objective function is called an optimal solution.