Linear programming problem

You are a factory manager of a manufacturing company that makes different types of computer chips. One of your most important responsibilities is to devise manufacturing plans that maximize profits for your company. Your chips sell at various prices, so there are so are a lot of costs to consider: raw materials, shipping, and processing. Demand for your chips and the supply of raw materials are also subject to change. You can imagine what such a complex decision entails. The difference between success and failure may come down to a single variable.

Linear programming is an optimization technique used to determine the optimal solution to such a complex problem out of many possibilities. In this topic, we will learn how to compose linear programming models. We will focus on the following linear programming concepts: objective function, decision variables, and constraints.

Formal definition and examples

Linear programming is an optimization method that represents complex relationships as simple linear functions and then finds the best possible outcome. What started as an attempt to solve the complex planning problems during wartime operations in the 1940s, is utilized to allocate limited resources optimally from automobile manufactures to big pharmaceutical industries today.

A linear program can be described in the following way:

$$Maximize \ or \ minimize: \ Linear \ objective \ function \\Subject \ to: \ Some \ linear \ constraints$$The main goal of linear programming is to find the values for variables in the constraints that give the best outcome for the objective function. Let's illustrate this concept with the following examples:

Example 1

A manufacturing company makes two types of laptop stands – foldable and compact. It costs $$10$ per unit to produce a foldable stand and $$7$ per unit to produce a compact stand. Foldable and compact stands are sold at $$14$ and $$10$ per unit, respectively. There are 120 units of raw materials available to manufacture both stands. While a foldable requires $3$ units of raw materials, a compact stand requires only $1$ unit of raw materials. The company has a total of $80$ manhours for manufacturing operations. A foldable stand and a compact stand take $2$ and $1$ manhours, respectively. Moreover, the company's storage is limited. There are only $60$ units of space is available. Both laptop stands take $1$ unit of storage space. Taking into account all this information, what is the optimal production bundle of foldable and compact stands for this manufacturing facility?

Example 2

A wood processing company buys two brands of paints – Deluxe and Classic. Deluxe paint contains $15$ kg of pigment A and $10$ kg of pigment B. Classic paint contains $9$ kg of pigment A and $16$ kg of pigment B. Deluxe paint costs $$10$ per unit, while Classic paint costs $$8.5$ per unit. The company needs at least $220$ kg of pigment A and $180$ kg of pigment B to complete a project. How many units of Deluxe and Classic paints should the company buy to minimize the costs?

The objective function

The objective function is the linear function that we maximize or minimize depending on the problem. Optimizing the objective function is the goal of any linear program. In a transportation problem, the goal may be to minimize the cost of transporting goods from one location to another. The goal can also be to maximize the area covered by our transport fleet. In a scheduling problem, the goal may be to minimize the total number of employees required for a given task. A manufacturing company may set an objective to minimize the cost of its operations or to maximize profit.

Coming back to our first example, what do you think is the goal of the manufacturing company? Is it to minimize the costs of stand production? Is the company's main goal to maximize the revenue from sales or maximize the profit? It is not explicitly stated in the example, but the goal of the company is to maximize profit. The problem accounts both for the revenue generated and the costs of producing a unit of each stand – and remember that the profit per unit is the revenue per unit minus the costs per unit. By choosing profit maximization as the objective function, the company would be maximizing revenue from sales and minimizing costs of operations. For our second example, the wood processing company aims to minimize the costs of purchasing the two brands of paints to meet its project needs. In choosing the objective function, we need to have a sense of our main business objective. Losing sight of this would lead to sub-optimal results.

The decision variables in a linear optimization problem are those variables that a decision-maker is allowed to choose. In our first example, the decision variables are the quantities of foldable and compact stands. The decision variables should be under the control of a decision-maker. The coefficients of the decision variables are the rates that the decision variables are multiplied with. In our example, the rate is the profit per unit. Depending on the type of problem, the rate may be the cost per unit, the revenue per unit, the area per unit, and so on.

The coefficients of the decision variables from our first example are calculated in the following way:

$$Profit \ per\ unit \ of \ foldable \ stand = \$14/unit \ - \ \$10/unit \ = \$4/unit\\Profit \ per\ unit \ of \ compact\ stand = \$10/unit \ - \ \$7/unit \ = \$3/unit$$Let the units of foldable and compact stands, which we are going to produce, be represented as $x_1$ and $x_2$, respectively. Therefore, the objective function is mathematically represented as:

$$Maximize \ z = 4x_1 + 3x_2$$

The decision variables for our second example are the units of Deluxe and Classic paints that the company should buy for the project. The coefficients of the decision variables are the unit costs of both brands of paints. Therefore, the objective function can be written as:

$$Minimize \ z = 10y_1 + 8.5y_2$$ Where $y_1$ and $y_2$ represent the units of Deluxe and Classic paints that should be bought respectively.

The general formula for objective function is represented mathematically as:

$$Maximize \ or \ minimize\ z = \displaystyle\sum_{i=1}^{N}c_ix_i$$Where $z$ is the objective function, $c_i$ is the coefficient of the decision variable, and $x_i$ is the decision variable for $i = 1, 2, ..., N$.

The constraints

Constraints are the bottlenecks that we face in our decision-making process. We encounter these bottlenecks because of the limited nature of our resources. These constraints may be economical, logical, or physical, depending on the nature of the problem.

Coming back to our first example, the constraints are the limited amount of raw materials, the storage space capacity, and the labor available. We cannot use more raw materials than we have available unless we make an additional purchase or when we use too much more labor or we produce more than we can store.

Linear programming constraints are represented by linear inequalities. The storage capacity constraint equation is given as:

$$x_1 + x_2 \leq 60$$The sum of the storage capacity for foldable and compact stands should be less than or equal to the maximum storage capacity. The labor constraint equation is given as:

$$2x_1 + x_2 \leq 80$$The total labor in hours to produce the foldable and compact stands should be less than or equal to the total hours available. The raw material constraint equation is given as:

$$3x_1+x_2 \leq 120$$The total number of units of raw materials used to produce both stands should be less than the units of raw materials available.

The constraints for our second example are the units of pigments A and B required for the project. The constraint equation for pigment A is given as:

$$15y_1+9y_2 \geq 220$$This means that the sum of pigment A in the units of Deluxe and Classic paints should be greater than or equal to the amount of pigment A required for the project. While the constraint equation for pigment B is given as:

$$10y_1+16y_2 \geq 180$$Similarly, the sum of pigment B in the units of Deluxe and Classic paints bought should be greater than or equal to the amount of pigment B required for the project.

Mathematically, constraints can take the following general form:

• If a constraint cannot exceed a certain value of B:

$$\displaystyle\sum_{j=1}^N b_ix_i \leq B$$

• If a constraint cannot be less than a certain value of B:

$$\displaystyle\sum_{j=1}^N b_ix_i \geq B$$

• If a constraint is equal to the value of B:

$$\displaystyle\sum_{j=1}^N b_ix_i = B$$We can state the linear programming model from our first example in the following way:

$$Maximize \ z = 4x_1 + 3x_2$$

It is subject to the following constraints:

$$x_1 + x_2 \leq 60 \\ 2x_1 + x_2 \leq 80 \\ 3x_1+x_2 \leq 120 \\ x_1, x_2 \ge 0$$The linear program from our second example is:

$$Minimize \ z = 10y_1 + 8.5y_2$$It is subject to the following constraints:

$$15y_1+9y_2 \geq 220 \\ 10y_1+16y_2 \geq 180 \\ y_1, y_2 \ge 0$$

We have used the letters $x$ and $y$ to represent the decision variables in our examples. You may use any alphabet letter to represent the decision variables in a problem as long as you remain consistent with your notation.

Non-negative decision variables

We are a laptop stand manufacturing company, and our goal is to produce a product mix ($x_1$ and $x_2$) that maximizes profit. If any decision variable coefficient has a negative sign, we produce a stand with a loss. We suffer more losses when we sell more of that particular stand. It might be an easy business decision to discontinue the production of such a stand. But what if a decision variable ($x_1$ or $x_2$) takes negative values? Recall that the decision variables are variables that the decision-maker has control over and, in our example, these are the units of stands that should be produced. The decision variables cannot take negative values and are referred to as non-negative constraints: $x_1, x_2 \ge 0$.

Conclusion

In this topic, we learned some of the basics of linear programming: decision variables, coefficients of decision variables, objective functions, and constraints. Here are the most important insights:

• Linear programming helps us with optimization problems;
• To set up the problem, we introduce decision variables. These variables represent the options that we can control and adjust to reach our optimization goals;
• Constraints lie in the heart of optimization. These constraints are usually related to manpower, resources, and time and are represented as linear inequalities;
• As optimization problems are tightly related to the real world, by default, we say that the decision variables are non-negative as we can't produce a negative amount of goods or buy a negative amount of raw materials.