Search in book...
Toggle Font Controls
Create new playlist

Name your new playlist

Playlist description (optional)
Sign In

Email address

Password

Forgot Password?

or

Continue with Facebook

Continue with Google
Sign Up

Full Name

Email address

Confirm Email Address

Password

or

Continue with Facebook

Continue with Google

Chapter 16

Introduction to Optimization Models: General Formulations and Business Modeling

Abstract

This chapter introduces and shows the main concepts related to optimization models, focusing especially on the modeling of linear programming problems. First of all, we identify the main elements contained in a linear programming model. The general formulation of a linear programming model is then described, as well as the standard and canonical forms. The hypotheses of a linear programming model are also presented. Finally, several business problems are modeled by linear programming.

Keywords

Optimization models; Linear programming; General formulation; Standard form; Canonical form; Business modeling

Education is the most powerful weapon which you can use to change the world.

Nelson Mandela

16.1 Introduction to Optimization Models

Optimization models are being used to solve problems in several industrial and commercial sectors (strategy, marketing, finance, operations and logistics, human resources, among others), to make decisions on the most effective use of resources.

This chapter describes how optimization models can help researchers and managers in the decision-making process.

First of all, it is important to study the main concepts involved in this process.

There are many definitions for the concept of decision. One of them is that decision making refers to the analysis process of many alternatives available of the course of action the person will have to follow, or rather, the process resulting in the selection of a belief or a course of action among several alternative possibilities. Some examples of decisions can be listed here: choosing one location among many others that are available, determining the best stock portfolio, choosing one among several alternatives that balance the company’s production resources, such as, personnel available, hiring, firing, and inventory.

Thus, we can see that the organization’s goals are directly linked to the decision-making process. In order to minimize the uncertainties, risks, and complexities that are inherent to the process and aiming at making the most effective decision among the several alternatives available, the value and quality of the information available becomes essential. Communication among the stakeholders involved in the process, during the information collection phase, as well as when defining the objective and the reasoning of the group, also influence the decisions to be made. And it is exactly with greater focus on an effective decision-making process, considering the several interfaces and exogeneities of systems and markets, that optimization models insert themselves as a field of knowledge, in order to provide to the decision-making agent a greater foundation and better knowledge of the problem being analyzed, be it in finance, economics, logistics, or marketing.

On the other hand, according to Lisboa (2002), a model is a simplified representation of a real system. It can be an existing project or a future project. In the former, we intend to replicate the operations of a real existing system, in order to increase productivity. In the latter, the main goal is to define the ideal structure of the future system.

The behavior of a real system is influenced by several variables involved in the decision-making process. Due to the high complexity of this system, it becomes necessary to simplify it, from a model, in such a way that the main variables involved in the system or project that we aim to understand or control are considered in its construction, as shown in Fig. 16.1.

Fig. 16.1 Modeling from a real system. Source: Andrade, E.L., 2015. Introdução à Pesquisa Operacional: Métodos e Modelos Para Análise de Decisões, fifth ed. LTC, Rio de Janeiro.

A model is made of three main elements: (a) decision and parameter variables; (b) an objective function, and (c) constraints.

(a) Decision and parameter variables:

Decision variables are unidentified, or unknown values, which will be determined by solving the model. The optimization models studied consider the following decision variable measurement and precision scales: continuous, discrete, or binary. Decision variables should assume non-negative values. The types of variables and their respective measurement and precision scales were studied in Chapter 2.

Parameters are the previously known fixed values of the problem. As examples of parameters within a mathematical model, we can mention the: (a) demand for each product for a production mix problem; (b) variable cost to produce a certain kind of furniture; (c) profit or cost per unit of product manufactured; (d) cost per employee hired; (e) unit contribution margin whenever a certain electrical appliance is manufactured and sold.

(b) Objective function:

The objective function is a mathematical function that determines the target value that we intend to achieve or the quality of the solution, based on decision variables and on parameters. It can be a maximization function (profit, revenue, usefulness, service level, wealth, life expectancy, among other attributes) or a minimization function (cost, risk, error, among others).

As examples, we can mention the: (a) minimization of the total production cost of several types of chocolates; (b) minimization of the credit risk in a client portfolio; (c) minimization of the number of employees involved in a certain service; (d) maximization of the return on investment in stock and fixed income funds; (e) maximization of the net profit in the production of several types of soft drinks.

Constraints can be defined as a set of equations (mathematical expressions of equality) and inequalities (mathematical expressions of inequality) that the decision variables of the model should meet. Constraints are added to the model in order to consider the system’s physical limitations, and they impact the values of the decision variables directly.

As examples of constraints to be considered in a mathematical model, we can mention: (a) maximum production capacity; (b) maximum risk a certain investor is willing to take; (c) maximum number of vehicles available; (d) minimum acceptable demand for a product.

Modeling a decision-making process has the advantage of forcing decision makers to clearly define their goals. Furthermore, it facilitates the identification and storing of the different decisions that impact the goals, it allows us to define the main variables involved in the decision-making process and the system’s own limitations, besides allowing greater interaction among the work group.

Optimization models can be divided into: linear programming, network programming, integer programming, nonlinear programming, goal or multiobjective programming, and dynamic programming (see Fig. 16.2). In this chapter, we will discuss the modeling of linear programming problems. The solution of linear programming models will be presented in Chapter 17. Now, network programming and integer programming models will be studied in Chapters 18 and 19, respectively. Nonlinear programming, multiobjective programming, and dynamic programming models are not the focus of this book, but can be found in Belfiore and Fávero (2012, 2013).

Fig. 16.2 Classification of optimization models.

16.2 Introduction to Linear Programming Models

In a linear programming problem (LP), the model’s objective function and all its constraints are represented by linear functions. Moreover, all the decision variables must be continuous, that is, they should assume any values in an interval with real numbers. The main goal is to maximize or minimize a certain linear function of decision variables, subject to a set of constraints represented by linear equations or inequalities, including the non-negativity ones of the decision variables. After constructing the mathematical model that represents the real LP problem being studied, the next step is to determine the optimal solution for the model, which is the one with the highest value (if it is a maximization problem) or the lowest value (if it is a minimization problem) in the objective function and meets the linear constraints established. Many algorithms or methods can be applied to find the optimal solution for the model; however, the Simplex method is the most well known and the most common.

Since George B. Dantzig developed the Simplex method in 1947, LP has been used to optimize real problems in several sectors. As examples, we can mention trade, services, banking, transportation, automobile, aviation, naval, food, beverages, agriculture and livestock, health, real estate, metallurgy, mining, paper and cellulose, electrical energy, oil, gas and fuels, computers, and the communication sector, among others.

Therefore, the use of linear programming techniques in organizational environments has been helping several industries in many countries save millions and sometimes even billions of dollars. According to Winston (2004), a survey with the largest 500 American companies listed by Fortune magazine reported that 85% of the respondents used or had already used the linear programming technique.

16.3 Mathematical Formulation of a General Linear Programming Model

Linear programming problems try to determine optimal values for the decision variables x₁, x₂, …, x_n, which must be continuous, in order to maximize or minimize linear function z, subject to a set of m linear constraints of equality (equations with an = sign) and/or of inequality (inequalities with a ≤ or a ≥ sign).

The solutions that meet all the constraints, including the non-negativity ones of the decision variables, are called feasible solutions. The feasible solution that presents the best value of the objective function is called optimal solution.

The formulation of a general linear programming model can be mathematically represented as:

$\begin{array}{l} max or min z = f (x_{1} x_{2} \dots x_{n}) = c_{1} x_{1} + c_{2} x_{2} + ⃛ + c_{n} x_{n} \\ subject to : \\ a_{11} x_{1} + a_{12} x_{2} + ⃛ + a_{1 n} x_{n} \{\leq = \geq\} b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + ⃛ + a_{2 n} x_{n} \{\leq = \geq\} b_{2} \\ ⋮ ⋮ ⋮ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + ⃛ + a_{mn} x_{n} \{\leq = \geq\} b_{m} \\ x_{1}, x_{2}, \dots, x_{n} \geq 0 (non - negativity constraint) \end{array}$

si1_e (16.1)

where:

z is the objective function;
x_j are the decision variables, main or controllable, j = 1, 2, …, n;
a_ij is the constant or coefficient of the ith constraint of the jth variable, i = 1, 2, …, m, j = 1, 2, …, n;
b_i is the independent term or quantity of resources available of the ith constraint, i = 1, 2, …, m; and
c_j is the constant or coefficient of the jth variable of the objective function, j = 1, 2, …, n.

16.4 Linear Programming Model in the Standard and Canonical Forms

The previous section presented the general formulation of a linear programming problem. This section discusses the formulation in the standard and canonical forms, in addition to elementary operations that can change the formulation of linear programming problems.

16.4.1 Linear Programming Model in the Standard Form

To solve a linear programming problem, be it by the analytical method or by the Simplex algorithm, the formulation of the model should be in the standard form, that is, it must meet the following requirements:

• The independent terms of the constraints must be non-negative;
• All the constraints must be represented by linear equations and presented as an equality;
• The decision variables must be non-negative.

The standard form can be mathematically represented as:

$\begin{array}{l} max or min z = f (x_{1} x_{2} \dots x_{n}) = c_{1} x_{1} + c_{2} x_{2} + ⃛ + c_{n} x_{n} \\ subject to : \\ a_{11} x_{1} + a_{12} x_{2} + ⃛ + a_{1 n} x_{n} = b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + ⃛ + a_{2 n} x_{n} = b_{2} \\ ⋮ ⋮ ⋮ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + ⃛ + a_{mn} x_{n} = b_{m} \\ x_{j} \geq 0, j = 1, 2, \dots, n \end{array}$

si2_e (16.2)

The standard linear programming problem can also be written in matrix form:

$\begin{array}{l} min f (x) = c x \\ subject to : \\ Ax = b \\ x \geq 0 \end{array}$

si3_e

where:

$A = [\begin{array}{c} a_{11} & a_{12} & \dots & a_{1 n} \\ a_{21} & a_{22} & \dots & a_{2 n} \\ ⋮ & ⋮ & ⋮ \\ a_{m 1} & a_{m 2} & \dots & a_{mn} \end{array}], x = [\begin{array}{c} x_{1} \\ x_{2} \\ ⋮ \\ x_{n} \end{array}], b = [\begin{array}{c} b_{1} \\ b_{2} \\ ⋮ \\ b_{m} \end{array}], c = [c_{1} c_{2} \dots c_{n}], 0 = [\begin{array}{c} 0 \\ 0 \\ 0 \\ 0 \end{array}]$

si4_e

16.4.2 Linear Programming Model in the Canonical Form

In a linear programming model in the canonical form, the constraints must be presented as inequalities, and z can be a maximization or a minimization objective function. If z is a maximization function, all the constraints must be represented with a ≤ sign. If z is a minimization function, the constraints should have a ≥ sign.

For a maximization problem, the canonical form can be mathematically represented as:

$\begin{array}{l} max z = f (x_{1} x_{2} \dots x_{n}) = c_{1} x_{1} + c_{2} x_{2} + ⃛ + c_{n} x_{n} \\ subject to : \\ a_{11} x_{1} + a_{12} x_{2} + ⃛ + a_{1 n} x_{n} \leq b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + ⃛ + a_{2 n} x_{n} \leq b_{2} \\ ⋮ ⋮ ⋮ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + ⃛ + a_{mn} x_{n} \leq b_{m} \\ x_{j} \geq 0, j = 1, 2, \dots, n \end{array}$

si5_e (16.3)

Now, if it is a minimization problem, the canonical form becomes:

$\begin{array}{l} min z = f (x_{1} x_{2} \dots x_{n}) = c_{1} x_{1} + c_{2} x_{2} + ⃛ + c_{n} x_{n} \\ subject to : \\ a_{11} x_{1} + a_{12} x_{2} + ⃛ + a_{1 n} x_{n} \geq b_{1} \\ a_{21} x_{1} + a_{22} x_{2} + ⃛ + a_{2 n} x_{n} \geq b_{2} \\ ⋮ ⋮ ⋮ ⋮ \\ a_{m 1} x_{1} + a_{m 2} x_{2} + ⃛ + a_{mn} x_{n} \geq b_{m} \\ x_{j} \geq 0, j = 1, 2, \dots, n \end{array}$

si6_e (16.4)

16.4.3 Transformations Into the Standard or Canonical Form

In order for a linear programming problem to have one of the forms presented in Sections 16.4.1 and 16.4.2, some elementary operations can be carried out from a general formulation, as described here.

(1) A standard maximization problem can be transformed into a minimization linear programming problem:
$max z = f (x_{1} x_{2} \dots x_{n}) \Leftrightarrow min - z = - f (x_{1} x_{2} \dots x_{n})$

(16.5)

Analogously, a minimization problem can be transformed into a maximization problem:
$min z = f (x_{1}, x_{2}, \dots, x_{n}) \Leftrightarrow max - z = - f (x_{1}, x_{2}, \dots, x_{n})$

(16.6)

(2) An inequality constraint of the ≤ type can be transformed into another one of the ≥ type by multiplying both sides by (− 1):
a_i1x₁ + a_i2x₂ + ⋯ + a_inx_n ≤ b_i is equivalent to
$- a_{i 1} x_{1} - a_{i 2} x_{2} - \dots - a_{in} x_{n} \geq - b_{i}$

(16.7)

Analogously, an inequality constraint of the ≥ type can be transformed into another one of the ≤ type:
a_i1x₁ + a_i2x₂ + ⋯ + a_inx_n ≥ b_i is equivalent to
$- a_{i 1} x_{1} - a_{i 2} x_{2} - \dots - a_{in} x_{n} \leq - b_{i}$

(16.8)

(3) An equality constraint can be transformed into two inequality constraints:
a_i1x₁ + a_i2x₂ + ⋯ + a_inx_n = b_i is equivalent to
$\{\begin{cases} a_{i 1} x_{1} + a_{i 2} x_{2} + \dots + a_{in} x_{n} \leq b_{i} \\ a_{i 1} x_{1} + a_{i 2} x_{2} + \dots + a_{in} x_{n} \geq b_{i} \end{cases}$

(16.9)

(4) An inequality constraint of the ≤ type can be rewritten as an expression of equality, considering the inclusion of a new non-negative variable on the left-hand side (LHS), x_k ≥ 0, called a slack variable:
$a_{i 1} x_{1} + a_{i 2} x_{2} + \dots + a_{in} x_{n} \leq b_{i}$ is equivalent to
$a_{i 1} x_{1} + a_{i 2} x_{2} + \dots + a_{in} x_{n} + x_{k} = b_{i}$

(16.10)

Analogously, an inequality constraint of the ≥ type can also be transformed into an expression of equality by subtracting a new non-negative variable from the left-hand side, x_k ≥ 0, called a surplus variable:
a₁₁x₁ + a₁₂x₂ + ⋯ + a_1nx_n ≥ b₁ is equivalent to
$a_{i 1} x_{1} + a_{i 2} x_{2} + \dots + a_{in} x_{n} - x_{k} = b_{i}$

(16.11)

(5) An x_j variable that is unrestricted in sign, called a free variable, can be expressed as the difference between two non-negative variables:
$x_{j} = x_{j}^{1} - x_{j}^{2}, x_{j}^{1}, x_{j}^{2} \geq 0$

(16.12)

Example 16.1

For the following linear programming problem, rewrite it in the standard form, starting from a minimization objective function.

$\begin{array}{l} max z = f (x_{1}, x_{2}, x_{3}, x_{4}) = 5 x_{1} + 2 x_{2} - 4 x_{3} - x_{4} \\ subject to : \\ x_{1} + 2 x_{2} - x_{4} \leq 12 \\ 2 x_{1} + x_{2} + 3 x_{3} \geq 6 \\ x_{1} free, x_{2}, x_{3}, x_{4} \geq 0 \end{array}$

si16_e

Solution

In order for the model to be rewritten in the standard form, the inequality constraints must be expressed as an equality (Expressions 16.10 and 16.11), and free variable x₁ can be expressed as the difference between two nonnegative variables (Expression 16.12). Considering a minimization objective function, we have:

$\begin{array}{l} min - z = - f (x_{1}, x_{2}, x_{3}, x_{4}) = - 5 x_{1}^{1} + 5 x_{1}^{2} - 2 x_{2} + 4 x_{3} + x_{4} \\ subject to : \\ x_{1}^{1} - x_{1}^{2} + 2 x_{2} - x_{4} + x_{5} = 12 \\ 2 x_{1}^{1} - 2 x_{1}^{2} + x_{2} + 3 x_{3} - x_{6} = 6 \\ x_{1}^{1}, x_{1}^{2}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6} \geq 0 \end{array}$

si17_e

Example 16.2

Convert the following problem into the canonical form.

$\begin{array}{l} max z = f (x_{1}, x_{2}, x_{3}) = 3 x_{1} + 4 x_{2} + 5 x_{3} \\ subject to : \\ 2 x_{1} + 2 x_{2} + 4 x_{3} \geq 320 \\ 3 x_{1} + 4 x_{2} + 5 x_{3} = 580 \\ x_{1}, x_{2}, x_{3} \geq 0 \end{array}$

si18_e

In order for the maximization model to be written in the canonical form, the constraints must be expressed as an inequality of the ≤ type. In order to do that, the expression of equality must be transformed into two inequality constraints (Expression 16.9) and the inequalities with the ≥ sign must be multiplied by (− 1), as specified in Expression (16.8). The final model in the canonical form is:

$\begin{array}{l} max z = f (x_{1}, x_{2}, x_{3}) = 3 x_{1} + 4 x_{2} + 5 x_{3} \\ subject to : \\ - 2 x_{1} - 2 x_{2} - 4 x_{3} \leq - 320 \\ - 3 x_{1} - 4 x_{2} - 5 x_{3} \leq - 580 \\ 3 x_{1} + 4 x_{2} + 5 x_{3} \leq 580 \\ x_{1}, x_{2}, x_{3} \geq 0 \end{array}$

si19_e

16.5 Assumptions of the Linear Programming Model

In a linear programming problem, the objective function and the model constraints must be linear, the decision variables must be continuous (divisible, and they can assume fractional values) and non-negative, and the model parameters must be deterministic, in order to satisfy the following assumptions:

1. Proportionality
2. Additivity
3. Divisibility and non-negativity
4. Certainty

16.5.1 Proportionality

The proportionality assumption requires that, for each decision variable considered in the model, its contribution regarding the objective function and the model constraints be directly proportional to the value of the decision variable.

Let’s imagine the following example. A company tries to maximize its production of chairs (x₁) and tables (x₂), and the profit per chair and per table is 4 and 7, respectively. So, objective function z is expressed as max z = 4x₁ + 7x₂. Fig. 16.3, adapted from Hillier and Lieberman (2005), shows the contribution of variable x₁ to objective function z. We can see that, in order for the proportionality assumption to be respected, for every chair produced, the objective function must increase $4.

Fig. 16.3 Contribution of variable x₁ to objective function z.

Let’s imagine that an initial set-up cost of $20 is considered (case 1) until the production of chairs (x₁) begins. In this case, the contribution of variable x₁ in relation to the objective function would be written as z = 4x₁ − 20, instead of z = 4x₁, not meeting the proportionality assumption. On the other hand, imagine that there are economies of scale, in a way that production costs diminish and, consequently, the marginal contribution increases, as the total amount produced grows (case 2), also violating the proportionality assumption. In this case, the profit function becomes nonlinear.

In the same way, regarding the constraints, we assume that the a_ij coefficients or constants are proportional to production level x_j.

16.5.2 Additivity

The additivity assumption states that the total value of the objective function or of each constraint function of a linear programming model is expressed by the sum of the individual contributions of each decision variable. Thus, the contribution of each decision variable does not depend on the contribution of the other variables, in a way that there are no crossed terms, both in the objective function and in the model constraints.

Considering the previous example, the objective function is expressed as max z = 4x₁ + 7x₂. Through the additivity assumption, the total value of the objective function is obtained through the sum of individual contributions of x₁ and x₂, that is, z = 4 + 7 = 11. If the objective function is expressed as max z = 4x₁ + 7x₂ + x₁x₂, the additivity assumption is violated (z = 4 + 7 + 1 = 12 for x₁, x₂ = 1), since the model’s decision variables are interdependent.

In the same way, regarding each model constraint, we assume that the function’s total value is expressed by the sum of each variable’s individual contributions.

16.5.3 Divisibility and Non-negativity

Each one of the decision variables considered in the model can assume any non-negative value within an interval, including fractional values, as long as it meets the model’s constraints. When the variables being studied can only be integers, the model is called integer (linear) programming (ILP or simply IP).

16.5.4 Certainty

This assumption states that the objective function coefficients, the constraint coefficients, and the independent terms of a linear programming model are deterministic (constants and known with certainty).

16.6 Modeling Business Problems Using Linear Programming

This section discusses the description and modeling of the main resource optimization problems that are being studied in linear programming in the fields of engineering, business management, economics, and accounting. They are the production mix problem, capital budgeting, investment portfolio selection, production inventory, and aggregated planning.

16.6.1 Production Mix Problem

The production mix problem aims to find the ideal quantity of certain lines of products to be manufactured that will maximize the company’s results (net profit, total profit, etc.) or minimize the production costs, respecting its limitations as regards productive and market resources (raw materials constraints, maximum production capacity, availability of human resources, maximum and minimum market demand, among others).

When the amount of a certain product to be manufactured can only be an integer (cars, electrical appliances, electronic devices, etc.), we have an integer programming problem (IP). An alternative solution for this kind of problem is to relax or to eliminate the decision variables’ integrality constraint, using a linear programming problem. Luckily, sometimes, the optimal solution to the relaxed problem corresponds to the optimal solution of the original model, that is, it meets the decision variables’ integrality constraints. When the solution of the relaxed problem is not an integer, rounding up or integer programming algorithms must be applied to find the solution for the original problem. Further details can be found in Chapter 19 that discusses integer programming.

Example 16.3

Venix is a toy company and it is reviewing its toy cars and tricycles production planning. The net profit per toy car and tricycle unit produced is US$ 12.00 and US$ 60.00, respectively. The raw materials and input necessary to manufacture each one of these products are outsourced, and the company is in charge of the machining, painting, and assembly processes. The machining process requires 15 minutes of specialized labor per car unit and 30 minutes per tricycle unit produced. The painting process requires 6 minutes of specialized labor per car unit and 45 minutes per tricycle unit produced. Now, the assembly process needs 6 and 24 minutes per car unit and tricycle produced, respectively. Per week, the time available for machining, painting, and assembly is 36, 22, and 15 hours, respectively. The company would like to determine how much it should produce of each product per week, respecting its resource limitations, in order to maximize its weekly net profit. Formulate the linear programming problem that maximizes the company’s net profit.

Solution

First of all, we define the model’s decision variables:

x_j = amount of product j to be manufactured per week, j = 1, 2.

Therefore, we have:

x₁ = amount of cars to be manufactured per week.
x₂ = amount of tricycles to be manufactured per week.

Therefore, we can see that the decision variables should be integers (it is impossible to produce fractional amounts of toy cars or tricycles), so, this is an integer programming (IP) problem. Luckily, in this problem, the integrality constraints can be relaxed or eliminated, since the relaxed problem’s optimal solution still meets the integrality conditions. Thus, the formulation of the problem will be presented as a linear programming (LP) model.

The net profit per toy car unit produced is US$ 12.00, while the net profit per tricycle is US$ 60.00. We are trying to maximize the weekly net profit generated from the amount of cars and tricycles manufactured. Therefore, the objective function can be written as follows:

$F_{obj} = max z = 12 x_{1} + 60 x_{2}$

Considering that for the machining process, to produce one car and/or one tricycle, we need 15 minutes (0.25 hours) and 30 minutes (0.5 hours) of specialized labor, respectively (0.25x₁ + 0.50x₂). However, the total labor time for the machining activity cannot be higher than 36 hours/week, which generates the following constraint:

$0.25 x_{1} + 0.5 x_{2} \leq 36$

Analogously, for the painting activity, one car and/or one tricycle produced requires 6 minutes (0.1 hours) and 45 minutes (0.75 hours) of specialized labor, respectively (0.1x₁ + 0.75x₂). However, the maximum limit of labor available for this activity is 22 hours/week:

$0.1 x_{1} + 0.75 x_{2} \leq 22$

Now, the assembly process, to produce one toy car and/or one tricycle, requires 6 minutes (0.1 hours) and 24 minutes (0.4 hours) of labor, respectively (0.1x₁ + 0.4x₂). The availability of human resources for this activity is 15 hours/week:

$0.1 x_{1} + 0.4 x_{2} \leq 15$

Finally, we have the non-negativity constraints of the decision variables.

All the model’s constraints are:

(1) Labor availability constraints for all three activities:
$0.25 x_{1} + 0.5 x_{2} \leq 36 (machining)$

$0.1 x_{1} + 0.75 x_{2} \leq 22 (painting)$

$0.1 x_{1} + 0.4 x_{2} \leq 15 (assembly)$

(2) Non-negativity constraint of the decision variables:
$x_{j} \geq 0, j = 1, 2$

The model’s complete formulation can be represented as:

$\begin{array}{l} max z = 12 x_{1} + 60 x_{2} \\ subject to : \\ 0.25 x_{1} + 0.50 x_{2} \leq 36 \\ 0.10 x_{1} + 0.75 x_{2} \leq 22 \\ 0.10 x_{1} + 0.40 x_{2} \leq 15 \\ x_{j} \geq 0, j = 1, 2 \end{array}$

si28_e

The optimal solution can be obtained in graphical form, in analytical form, through the Simplex method, or directly from some software, such as, Solver (in Excel), as presented in the next chapter. The current model’s optimal solution is x₁ = 70 (toy cars per week) and x₂ = 20 (tricycles per week) with z = 2040 (a weekly net profit of US$ 2040.00).

Example 16.4

Naturelat is a dairy company that manufactures the following products: yogurt, fresh white cheese, Mozzarella, Parmesan, and Provolone. Due to some strategic changes resulting from the competition in the market, the company is redefining its production mix.

To manufacture each one of these five products, three types of raw materials are necessary: raw milk, cream line, and cream. Table 16.E.1 shows the amount of raw materials necessary to manufacture 1 kg of each product.

The daily amount of raw materials available is limited (1200 L of raw milk, 460 L of cream line, and 650 kg of cream).

A daily availability of specialized labor is also limited (170 hours/employee/day). The company needs 0.05 hours/employee to manufacture 1 kg of yogurt, 0.12 hours/employee to manufacture 1 kg of fresh white cheese, 0.09 hours/employee for making Mozzarella, 0.04 hours/employee for Parmesan, and 0.16 hours/employee for Provolone cheese.

Due to contractual clauses, the company needs to produce a minimum daily quantity of 320 kg of yogurt, 380 kg of fresh white cheese, 450 kg of Mozzarella, 240 kg of Parmesan, and 180 kg of Provolone.

The company’s commercial department guarantees that there is enough demand to absorb any production level, regardless of the product.

Table 16.E.2 shows the net profit per unit per product (US$/kg), which is calculated as the difference between the sales price and the total variable costs.

The company aims to determine the quantity of each product it has to manufacture in order to maximize its results. Formulate the linear programming problem that maximizes the result expected.

Table 16.E.1

Raw Materials Necessary to Manufacture 1 kg of Each Product
Product	Raw Milk (l)	Cream-Line (l)	Cream (kg)
Yogurt	0.70	0.16	0.25
Fresh white cheese	0.40	0.22	0.33
Mozzarella	0.40	0.32	0.33
Parmesan	0.60	0.19	0.40
Provolone	0.60	0.23	0.47

Unlabelled Table

Table 16.E.2

Net Profit Per Product Unit (US$/kg)
Product	Sales Price (US$/kg)	Total Variable Costs (US$/kg)	Contribution Margin (US$/kg)
Yogurt	3.20	2.40	0.80
Fresh white cheese	4.10	3.40	0.70
Mozzarella	6.30	5.15	1.15
Parmesan	8.25	6.95	1.30
Provolone	7.50	6.80	0.70

Unlabelled Table

Solution

First of all, we define the model’s decision variables:

x_j = amount of product j (in kg) to be manufactured per day, j = 1, 2, …, 5.

Therefore, we have:

x₁ = amount of yogurt (in kg) to be manufactured per day.

x₂ = amount of fresh white cheese (in kg) to be manufactured per day.

x₃ = amount of Mozzarella (in kg) to be manufactured per day.

x₄ = amount of Parmesan (in kg) to be manufactured per day.

x₅ = amount of Provolone (in kg) to be manufactured per day.

The total net profit per product is the result obtained by multiplying the net profit per unit (in this case US$/kg) by the respective quantities sold. The problem’s objective function tries to maximize the total net profit of all the company’s products, which is obtained by adding the total net profits of each product:

$F_{obj} = max z = 0.80 x_{1} + 0.70 x_{2} + 1.15 x_{3} + 1.30 x_{4} + 0.70 x_{5}$

Regarding the raw materials availability constraints, let’s first consider the amount of raw milk (liters) used daily to manufacture each product. To manufacture 1 kg of yogurt, the company needs 0.7 L of raw milk (0.70x₁ represents the total amount of raw milk used every day to manufacture yogurt). The amount of raw milk (liters) used daily to manufacture fresh white cheese is represented by 0.40x₂. Analogously, their daily use of raw milk to manufacture Mozzarella is 0.40x₃, 0.60x₄ to manufacture Parmesan cheese and 0.60x₅ to make Provolone. The total amount of raw milk (liters) used daily to manufacture all of these products can be represented by 0.70x₁ + 0.40x₂ + 0.40x₃ + 0.60x₄ + 0.60x₅. However, this total cannot be higher than 1200 L (daily amount of raw milk available) and this constraint is represented by:

$0.70 x_{1} + 0.40 x_{2} + 0.40 x_{3} + 0.60 x_{4} + 0.60 x_{5} \leq 1200$

Likewise, the quantity of cream line (in liters) used daily to manufacture yogurt, fresh white cheese, Mozzarella, Parmesan, and Provolone cheese cannot be higher than the maximum amount available, which is 460 L:

$0.16 x_{1} + 0.22 x_{2} + 0.32 x_{3} + 0.19 x_{4} + 0.23 x_{5} \leq 460$

Still with regard to the raw materials availability constraints, in the case of cream, the quantity (kg) used daily to manufacture the five products cannot be higher than the maximum quantity available, which is 650 kg:

$0.25 x_{1} + 0.33 x_{2} + 0.33 x_{3} + 0.40 x_{4} + 0.47 x_{5} \leq 650$

We must also take the daily availability of specialized labor into consideration. Each kilo of yogurt manufactured requires 0.05 hours-employee, so, 0.05x₁ represents the total of hours-employee used daily in the manufacturing of yogurt. The number of hours-employee used daily to manufacture fresh white cheese is represented by 0.12x₂. Similarly, 0.09x₃ hours-employee are used daily to make Mozzarella. 0.04x₄ to produce Parmesan and 0.16x₅ to make Provolone. The total number of hours-employee used daily to manufacture all these products can be represented by 0.05x₁ + 0.12x₂ + 0.09x₃ + 0.04x₄ + 0.16x₅. However, this total cannot be higher than 170 hours-employee, which is the availability of specialized human resources per day:

$0.05 x_{1} + 0.12 x_{2} + 0.09 x_{3} + 0.04 x_{4} + 0.16 x_{5} \leq 170$

We must finally consider the daily minimum market demand constraint for each product: 320 kg for yogurt (x₁ ≥ 320), 380 for fresh white cheese (x₂ ≥ 380), 450 for Mozzarella cheese (x₃ ≥ 450), 240 for Parmesan (x₄ ≥ 240), and 180 for Provolone (x₅ ≥ 180), besides the non-negativity constraint of the decision variables.

All the constraints of the model can be represented as:

(1) Amount of raw materials used daily to produce yogurt, fresh white cheese, Mozzarella, Parmesan, and Provolone:

$0.70 x_{1} + 0.40 x_{2} + 0.40 x_{3} + 0.60 x_{4} + 0.60 x_{5} \leq 1200 (raw milk)$

$0.16 x_{1} + 0.22 x_{2} + 0.32 x_{3} + 0.19 x_{4} + 0.23 x_{5} \leq 460 (cream line)$

$0.25 x_{1} + 0.33 x_{2} + 0.33 x_{3} + 0.40 x_{4} + 0.47 x_{5} \leq 650 (cream)$

(2) Daily availability of specialized labor for producing yogurt, fresh white cheese, Mozzarella, Parmesan, and Provolone:

$0.05 x_{1} + 0.12 x_{2} + 0.09 x_{3} + 0.04 x_{4} + 0.16 x_{5} \leq 170$

(3) Daily minimum demand for each product:

$x_{1} \geq 320 (yogurt)$

$x_{2} \geq 380 (fresh white cheese)$

$x_{3} \geq 450 (Mozzarella)$

$x_{4} \geq 240 (Parmesan)$

$x_{5} \geq 180 (Provolone)$

(4) Non-negativity constraints of the decision variables:

$x_{j} \geq 0, j = 1, 2, \dots, 5$

The complete problem is modeled here:

$\begin{array}{l} max z = 0.80 x_{1} + 0.70 x_{2} + 1.15 x_{3} + 1.30 x_{4} + 0.70 x_{5} \\ subject to : \\ 0.70 x_{1} + 0.40 x_{2} + 0.40 x_{3} + 0.60 x_{4} + 0.60 x_{5} \leq 1200 \\ 0.16 x_{1} + 0.22 x_{2} + 0.32 x_{3} + 0.19 x_{4} + 0.23 x_{5} \leq 460 \\ 0.25 x_{1} + 0.33 x_{2} + 0.33 x_{3} + 0.40 x_{4} + 0.47 x_{5} \leq 650 \\ 0.05 x_{1} + 0.12 x_{2} + 0.09 x_{3} + 0.04 x_{4} + 0.16 x_{5} \leq 170 \\ x_{1} \geq 320 \\ x_{2} \geq 380 \\ x_{3} \geq 450 \\ x_{4} \geq 240 \\ x_{5} \geq 180 \\ x_{j} \geq 0, j = 1, \dots, 5 \end{array}$

si44_e

On Solver (in Excel), the model’s optimal solution is x₁ = 320 (kg/day of yogurt), x₂ = 380 (kg/day of fresh white cheese), x₃ = 690.96 (kg/day of Mozzarella), x₄ = 329.95 (kg/day of Parmesan), and x₅ = 180 (kg/day of Provolone) with z = 1871.55 (total daily contribution margin of US$ 1871.55).

16.6.2 Blending or Mixing Problem

The blending or mixing problem aims to find the solution with the minimum cost or maximum profit, starting from the combination of several ingredients in order to produce one or many products. The raw materials can be ore, metals, chemical products, oil or crude oil, water, while the final products can be metal ingots, steel, paint, gasoline, or other chemical products.

Among several mixing problems, we can mention a few examples:

1. Mixing many types of oil or crude oil to produce different types of gasoline.
2. Mixing chemical products to create other products.
3. Mixing different types of paper to generate recycled paper.

Example 16.5

Petrisul is an oil refinery that uses three types of crude oil (oil 1, oil 2, and oil 3) to produce three types of gasoline: regular, super, and extra.

To ensure its quality, each type of gasoline requires certain specifications based on the composition of several types of crude oil, as shown in Table 16.E.3.

In order to meet its clients’ demands, the refinery needs to produce at least 5000 barrels a day of regular gasoline and 3000 barrels a day of super and extra gasoline. The daily capacity available is 10,000 barrels of oil 1; 8000 of oil 2; and 7000 of oil 3. The refinery can produce up to 20,000 barrels of gasoline a day.

The refinery makes a profit of $5 per barrel of regular gasoline produced, $7 per barrel of super gasoline, and $8 per barrel of extra gasoline. The costs per barrel of crude oil 1, 2, and 3 are $2, $3, and $3, respectively. Formulate the linear programming problem aiming to maximize the company’s daily profit.

Table 16.E.3

Specifications for Each Type of Gasoline
Type of Gasoline	Specifications
Regular	Not more than 70% of oil 1
Super	Not more than 50% of oil 1 Not less than 10% of oil 2
Extra	Not more than 50% of oil 2 Not less than 40% of oil 3

Solution

First of all, we must define the model’s decision variables:

x_ij = barrels of crude oil i used daily to produce gasoline j, i = 1, 2, 3; j = 1, 2, 3.

Therefore, we have:

Daily production of regular gasoline = x₁₁ + x₂₁ + x₃₁
Daily production of super gasoline = x₁₂ + x₂₂ + x₃₂
Daily production of extra gasoline = x₁₃ + x₂₃ + x₃₃

Barrels of crude oil 1 used daily = x₁₁ + x₁₂ + x₁₃
Barrels of crude oil 2 used daily = x₂₁ + x₂₂ + x₂₃
Barrels of crude oil 3 used daily = x₃₁ + x₃₂ + x₃₃

The problem’s objective function tries to maximize the refinery’s daily profit (revenue—costs). The model constraints should guarantee that the minimum specifications required for each type of gasoline are taken into consideration, that its clients’ demands are being met, and that the gasoline production and the crude oil supply capacities are being respected.

The daily revenue per barrel of gasoline produced is:

$= 5 \cdot (x_{11} + x_{21} + x_{31}) + 7 \cdot (x_{12} + x_{22} + x_{32}) + 8 \cdot (x_{13} + x_{23} + x_{33})$

On the other hand, the daily costs per barrel of crude oil purchased are:

$= 2 \cdot (x_{11} + x_{12} + x_{13}) + 3 \cdot (x_{21} + x_{22} + x_{23}) + 3 \cdot (x_{31} + x_{32} + x_{33})$

The objective function can be written as:

$F_{obj} = max z = (5 - 2) x_{11} + (5 - 3) x_{21} + (5 - 3) x_{31} + (7 - 2) x_{12} + (7 - 3) x_{22} + (7 - 3) x_{32} + (8 - 2) x_{13} + (8 - 3) x_{23} + (8 - 3) x {}_{33}$

si47_e

All the model’s constraints are:

(1) The regular gasoline should contain a maximum of 70% of oil 1:
$\frac{x_{11}}{x_{11} + x_{21} + x_{31}} \leq 0.70$

which can be rewritten as:
$0.30 x_{11} - 0.70 x_{21} - 0.70 x_{31} \leq 0$

(2) The super gasoline should contain a maximum of 50% of oil 1:

$\frac{x_{12}}{x_{12} + x_{22} + x_{32}} \leq 0.50$

si50_e

which can be rewritten as:

$0.50 x_{12} - 0.50 x_{22} - 0.50 x_{32} \leq 0$

(3) The super gasoline should contain at least 10% of oil 2:
$\frac{x_{22}}{x_{12} + x_{22} + x_{32}} \geq 0.10$

which can be rewritten as:
$- 0.10 x_{12} + 0.90 x_{22} - 0.10 x_{32} \geq 0$

(4) The extra gasoline should contain a maximum of 50% of oil 2:
$\frac{x_{23}}{x_{13} + x_{23} + x_{33}} \leq 0.50$

which can be rewritten as:
$- 0.50 x_{13} + 0.50 x_{23} - 0.50 x_{33} \leq 0$

(5) The extra gasoline should contain at least 40% of oil 3:
$\frac{x_{33}}{x_{13} + x_{23} + x_{33}} \geq 0.40$

which can be rewritten as:
$- 0.40 x_{13} - 0.40 x_{23} + 0.60 x_{33} \geq 0$

(6) The daily demands for regular, super, and extra gasoline must be met:

$x_{11} + x_{21} + x_{31} \geq 5000 (regular)$

$x_{12} + x_{22} + x_{32} \geq 3000 (super)$

$x_{13} + x_{23} + x_{33} \geq 3000 (extra)$

(7) The maximum number of barrels of crude oil 1 (10,000), crude oil 2 (8000), and crude oil 3 (7000) available daily must be respected:

$x_{11} + x_{12} + x_{13} \leq 10, 000 (crude oil 1)$

$x_{21} + x_{22} + x_{23} \leq 8000 (crude oil 2)$

$x_{31} + x_{32} + x_{33} \leq 7000 (crude oil 3)$

(8) The refinery’s daily production capacity is 20,000 barrels of gasoline a day:
$x_{11} + x_{21} + x_{31} + x_{12} + x_{22} + x_{32} + x_{13} + x_{23} + x_{33} \leq 20, 000$

(9) The model’s decision variables are non-negative:
$x_{ij} \geq 0, i = 1, 2, 3; j = 1, 2, 3$

The complete problem is modeled here:
$\begin{array}{l} F_{obj} = max z = 3 x_{11} + 2 x_{21} + 2 x_{31} + 5 x_{12} + 4 x_{22} + 4 x_{32} + 6 x_{13} + 5 x_{23} + 5 x_{33} \\ subject to : \\ 0.30 x_{11} - 0.70 x_{21} - 0.70 x_{31} \leq 0 \\ 0.50 x_{12} - 0.50 x_{22} - 0.50 x_{32} \leq 0 \\ - 0.10 x_{12} + 0.90 x_{22} - 0.10 x_{32} \geq 0 \\ - 0.50 x_{13} + 0.50 x_{23} - 0.50 x_{33} \leq 0 \\ - 0.40 x_{13} - 0.40 x_{23} + 0.60 x_{33} \geq 0 \\ x_{11} + x_{21} + x_{31} \geq 5000 \\ x_{12} + x_{22} + x_{32} \geq 3000 \\ x_{13} + x_{23} + x_{33} \geq 3000 \\ x_{11} + x_{12} + x_{13} \leq 10, 000 \\ x_{21} + x_{22} + x_{23} \leq 8000 \\ x_{31} + x_{32} + x_{33} \leq 7000 \\ x_{11} + x_{21} + x_{31} + x_{12} + x_{22} + x_{32} + x_{13} + x_{23} + x_{33} \leq 20, 000 \\ x_{11}, x_{21}, x_{31}, x_{12}, x_{22}, x_{32}, x_{13}, x_{23}, x_{33} \geq 0 \end{array}$

By using Solver, the model’s optimal solution is x₁₁ = 1300, x₂₁ = 3700, x₃₁ = 0, x₁₂ = 1500, x₂₂ = 1500, x₃₂ = 0, x₁₃ = 7200, x₂₃ = 0, x₃₃ = 4800 with z = 92,000 (a total daily profit of US$ 92,000.00).

16.6.3 Diet Problem

The diet problem is a classic linear programming problem that tries to determine the best food combinations to be ingested per meal, with the lowest cost possible, meeting a person’s nutritional needs.

Several nutrients can be analyzed as, for example: calories, protein, fat, carbs, fibers, calcium, iron, magnesium, phosphorus, potassium, sodium, zinc, copper, manganese, selenium, vitamin A, vitamin C, vitamin B1, vitamin B2, vitamin B12, niacin, folic acid, cholesterol, among others (Pessôa et al., 2009).

Example 16.6

Anemia is a disease caused by low levels of hemoglobin in the blood, protein is responsible for carrying oxygen. According to Dr. Adriana Ferreira, a hematologist, iron-deficiency anemia is the most common kind of anemia, and it is caused by the lack of iron in the body. In order to prevent it, we must adopt a diet that is rich in iron, vitamin A, vitamin B12 and folic acid. These nutrients can be found in several kinds of food, such as, spinach, broccoli, watercress, tomatoes, carrots, eggs, beans, chickpeas, soybeans, beef, liver, and fish. Table 16.E.4 shows the daily needs of each nutrient, the respective quantity in each one of the food items, and their price. In order to prevent its patients from having this kind of anemia, Hospital Metropolis is studying a new diet. The goal is to choose the ingredients with the lowest possible costs. These ingredients will be a part of both main daily meals (lunch and dinner), in a way that 100% of a person’s daily needs of each of these nutrients will be met in both meals. In addition, the total amount ingested in both meals cannot be higher than 1.5 kg.

Table 16.E.4

Nutrients, Daily Needs, and Cost Per Food Item
	100 g Servings
	Iron (mg)	Vitamin A (IU)	Vitamin B12 (mcg)	Folic Acid (mg)	Price (US$)
Spinach	3.00	7400	0	0.400	0.30
Broccoli	1.20	138.8	0	0.500	0.20
Watercress	0.20	4725	0	0.100	0.18
Tomatoes	0.49	1130	0	0.250	0.16
Carrots	1.00	14,500	0.10	0.005	0.30
Eggs	0.90	3215	1.00	0.050	0.30
Beans	7.10	0	0	0.056	0.40
Chickpeas	4.86	41	0	0.400	0.40
Soybeans	3.00	1000	0	0.080	0.45
Beef	1.50	0	3.00	0.060	0.75
Liver	10.00	32,000	100.00	0.380	0.80
Fish	1.10	140	2.14	0.002	0.85
Daily intake	8	4500	2	0.4

Unlabelled Table

Solution

First of all, we have to define the model’s decision variables:

x_j = quantity (kg) of food j consumed daily, j = 1, 2, …, 12.

Therefore, we have:

x₁ = quantity (kg) of spinach consumed daily.
x₂ = quantity (kg) of broccoli consumed daily.
x₃ = quantity (kg) of watercress consumed daily.
$⋮$
x₁₂ = quantity (kg) of fish consumed daily.

The model’s objective function tries to minimize the total costs spent with food and it may be written as follows:

$F_{obj} = min z = 3 x_{1} + 2 x_{2} + 1.8 x_{3} + 1.6 x_{4} + 3 x_{5} + 3 x_{6} + 4 x_{7} + 4 x_{8} + 4.5 x_{9} + 7.5 x_{10} + 8 x_{11} + 8.5 x_{12}$

The constraints related to the minimum daily intake of each nutrient must be met. Furthermore, we must consider the maximum weight constraint allowed in both meals.

(1) The minimum daily intake of iron must be met:
$30 x_{1} + 12 x_{2} + 2 x_{3} + 4.9 x_{4} + 10 x_{5} + 9 x_{6} + 71 x_{7} + 48.6 x_{8} + 30 x_{9} + 15 x_{10} + 100 x_{11} + 11 x_{12} \geq 80$

(2) The minimum daily intake of vitamin A must be met:
$74, 000 x_{1} + 1388 x_{2} + 47, 250 x_{3} + 11, 300 x_{4} + 145, 000 x_{5} + 32, 150 x_{6} + 410 x_{8} + 10, 000 x_{9} + 320, 000 x_{11} + 1400 x_{12} \geq 45, 000$

(3) The minimum daily intake of vitamin B12 must be met:
$x_{5} + 10 x_{6} + 30 x_{10} + 1000 x_{11} + 21.4 x_{12} \geq 20$

(4) The minimum daily intake of folic acid must be met:
$4 x_{1} + 5 x_{2} + x_{3} + 2.5 x_{4} + 0.05 x_{5} + 0.5 x_{6} + 0.56 x_{7} + 4 x_{8} + 0.8 x_{9} + 0.6 x_{10} + 3.8 x_{11} + 0.02 x_{12} \geq 4$

(5) The total amount consumed in both meals cannot be higher than 1.5 kg:
$x_{1} + x_{2} + x_{3} + x_{4} + x_{5} + x_{6} + x_{7} + x_{8} + x_{9} + x_{10} + x_{11} + x_{12} \leq 1.5$

(6) The model’s decision variables are nonnegative:
$x_{1}, x_{2}, x_{3}, x_{4}, x_{5}, x_{6}, x_{7}, x_{8}, x_{9}, x_{10}, x_{11}, x_{12} \geq 0$

The complete model can be described as follows:

$\begin{array}{l} F_{obj} = min z = 3 x_{1} + 2 x_{2} + 1.8 x_{3} + 1.6 x_{4} + 3 x_{5} + 3 x_{6} + 4 x_{7} + 4 x_{8} + 4.5 x_{9} + 7.5 x_{10} + 8 x_{11} + 8.5 x_{12} \\ s . t . \\ 30 x_{1} + 12 x_{2} + 2 x_{3} + \dots + 15 x_{10} + + 100 x_{11} + 11 x_{12} \geq 80 \\ 74, 000 x_{1} + 1388 x_{2} + 47, 250 x_{3} + \dots + + 320, 000 x_{11} + 1400 x_{12} \geq 45, 000 \\ + \dots + 30 x_{10} + 1000 x_{11} + 21.40 x_{12} \geq 20 \\ 4 x_{1} + 5 x_{2} + x_{3} + \dots + 0.6 x_{10} + 3.8 x_{11} + 0.02 x_{12} \geq 4 \\ x_{1} + x_{2} + x_{3} + \dots + x_{10} + x_{11} + x_{12} \leq 1, 5 \\ x_{j} \geq 0, j = 1, \dots, 12 \end{array}$

si75_e

The model’s optimal solution is x₂ = 0.427 (kg of broccoli), x₇ = 0.698 (kg of beans), x₈ = 0.237 (kg of chickpeas), x₁₁ = 0.138 (kg of liver), x₁, x₃, x₄, x₅, x₆, x₉, x₁₀, x₁₂ = 0 with z = 5.70 (total cost of US$ 5.70).

16.6.4 Capital Budget Problems

Optimization models, including linear programming, are being widely used to solve several financial investment problems, such as, the capital budgeting problem, investment or portfolio selection, cash flow management, risk analysis, among others. This section discusses a linear programming model that can be used to solve a capital budgeting problem. In the following section, we will discuss the investment portfolio selection problem.

The capital budgeting problem aims at selecting, from a set of alternatives, financially feasible investment projects, respecting the investing company’s budgetary constraints.

The capital budgeting problem uses the concept of NPV (net present value) that aims to define which investment is the most attractive. NPV is defined as the present value (period t = 0) of the cash inflows (receivables) minus the cash outflows (payables/investment) for each period t = 0, 1, …, n. Considering different investment projects, the most attractive is the one that has the highest net present value.

The calculation of the NPV is:

$NPV = \sum_{t = 1}^{n} \frac{{CIF}_{t}}{{(1 + i)}^{t}} - \sum_{t = 1}^{n} \frac{{COF}_{t}}{{(1 + i)}^{t}}$

si76_e (16.13)

where:

CIF_t = cash inflow at the beginning of the period t = 1, …, n
COF_t = cash outflow at the beginning of the period t = 1, …, n
i = rate of return

We will analyze two types of investment (A and B) in order to determine which one is the most attractive. Investment A requires an initial investment of US$ 100,000 plus a US$ 50,000 investment in 1 year, with a US$ 200,000 return in 2 years. The interest rate is 12% per year. The calculation of the NPV of investment A is:

$\begin{array}{l} NPV = - 100, 000 - \frac{50, 000}{{(1 + 0.12)}^{1}} + \frac{200, 000}{{(1 + 0.12)}^{2}} \\ NPV = 14, 795.92 \end{array}$

si77_e

Investment B requires an initial investment of US$ 150,000 plus a US$ 70,000 investment in 2 years, with a US$ 130,000 return in 1 year, and US$ 120,000 in 3 years. The interest rate is 12% per year. The NPV of investment B is:

$\begin{array}{l} NPV = - 150, 000 + \frac{130, 000}{{(1 + 0.12)}^{1}} - \frac{70, 000}{{(1 + 0.12)}^{2}} + \frac{120, 000}{{(1 + 0.12)}^{3}} \\ NPV = - 4318.51 \end{array}$

si78_e

Therefore, we can see that investment B is not profitable. So, investment A is the most attractive.

The example showed us how to calculate the NPV of one or more investments and, from that, how to determine which one was the most attractive. However, many times, the resources available are limited, so, to choose one or more investment projects, a linear programming or a binary programming model should be used.

Example 16.7

A farmer is analyzing five types of investment based on different crops (soybeans, cassava, corn, wheat, and beans) for his new farm, which has a total of 1000 hectares available. Each crop requires capital investments that will result in future benefits. The initial investment and the payables in the following 3 years for each crop are specified in Table 16.E.5. The return expected in the following 3 years for each crop investment is specified in Table 16.E.6. The farmer has limited resources that he can invest in each period (last column of Table 16.E.5), and he expects a minimum cash flow each period (last column of Table 16.E.6). The interest rate for each crop is 10% per year. From the total area available for the investment, the farmer would like to determine how much he should invest in each crop (in hectares), in order to maximize the NPV of the set of investment projects being analyzed, respecting the minimum expected flows and the maximum outflows in each period. Elaborate the farmer’s linear programming problem.

Table 16.E.5

Cash Outflow for Each Year
Year	Initial Investment/Payables for Each Year (US$ Thousands Per Hectare)					Maximum Cash Outflow (US$ Thousands)
Year	Soybeans	Cassava	Corn	Wheat	Beans	Maximum Cash Outflow (US$ Thousands)
0	5.00	4.00	3.50	3.50	3.00	3800.00
1	1.00	1.00	0.50	1.50	0.50	3500.00
2	1.20	0.50	0.50	0.50	1.00	3200.00
3	0.80	0.50	1.00	0.50	0.50	2500.00

Unlabelled Table

Table 16.E.6

Cash Inflow for Each Year
Year	Expected Return for Each Year (US$ Thousands Per Hectare)					Minimum Cash Inflow (US$ Thousands)
Year	Soybeans	Cassava	Corn	Wheat	Beans	Minimum Cash Inflow (US$ Thousands)
1	5.00	4.20	2.20	6.60	3.00	6000.00
2	7.70	6.50	3.70	8.00	3.50	5000.00
3	7.90	7.20	2.90	6.10	4.10	6500.00

Unlabelled Table

Solution

First of all, we have to define the model’s decision variables:

x_j = total area (in hectares) to be invested in planting crop j, j = 1, 2, …, 5.

Therefore, we have:

x₁ = total area (in hectares) to be invested in planting soybeans.
x₂ = total area (in hectares) to be invested in planting cassava.
x₃ = total area (in hectares) to be invested in planting corn.
x₄ = total area (in hectares) to be invested in planting wheat.
x₅ = total area (in hectares) to be invested in planting beans.

The model’s objective function tries to maximize the NPV (US$ thousands) of the set of investments in the crops being analyzed, that is, the sum of the NPV of each crop (US$ thousands per hectare) multiplied by the total area to be invested in the respective crop (hectares). The calculation of the soybean crop NPV (US$ thousands/hectare), according to Expression (16.13), is:

Soybean crop (US$ thousands per hectare)

$\begin{array}{l} NPV = \frac{5.0}{{(1 + 0.10)}^{1}} + \frac{7.7}{{(1 + 0.10)}^{2}} + \frac{7.9}{{(1 + 0.10)}^{3}} - 5.0 - \frac{1.0}{{(1 + 0.10)}^{1}} - \frac{1.2}{{(1 + 0.10)}^{2}} - \frac{0.8}{{(1 + 0.10)}^{3}} \\ NPV = 9.343 (US $ 9342.60 / hectare) \end{array}$

si79_e

The calculation of the NPV of the other crops, taking the same procedure into consideration, is listed in Table 16.E.7.

Table 16.E.7

Net Present Value (NPV) of Each Crop
Net Present Value—NPV (US$ Thousands Per Hectare)
Soybeans	Cassava	Corn	Wheat	Beans
9.343	8.902	2.118	11.542	4.044

Unlabelled Table

Thus, objective function z can be described as follows:

$F_{obj} = max z = 9.343 x_{1} + 8.902 x_{2} + 2.118 x_{3} + 11.542 x_{4} + 4.044 x_{5}$

The maximum and minimum cash flow constraints for each year, besides the total area available, must be considered and are shown here.

(1) Maximum capacity available (hectares) for planting the crops:
$x_{1} + x_{2} + x_{3} + x_{4} + x_{5} \leq 1000$

(2) Minimum cash inflow for each year (US$ thousands):
$5.0 x_{1} + 4.2 x_{2} + 2.2 x_{3} + 6.6 x_{4} + 3.0 x_{5} \geq 6000 (1 st year)$

$7.7 x_{1} + 6.5 x_{2} + 3.7 x_{3} + 8.0 x_{4} + 3.5 x_{5} \geq 5000 (2 nd year)$

$7.9 x_{1} + 7.2 x_{2} + 2.9 x_{3} + 6.1 x_{4} + 4.1 x_{5} \geq 6500 (3 rd year)$

(3) Maximum outflow for each year (US$ thousands):
$5.0 x_{1} + 4.0 x_{2} + 3.5 x_{3} + 3.5 x_{4} + 3.0 x_{5} \leq 3800 (initial investment)$

$1.0 x_{1} + 1.0 x_{2} + 0.5 x_{3} + 1.5 x_{4} + 0.5 x_{5} \leq 3500 (1 st year)$

$1.2 x_{1} + 0.5 x_{2} + 0.5 x_{3} + 0.5 x_{4} + 1.0 x_{5} \leq 3200 (2 nd year)$

$0.8 x_{1} + 0.5 x_{2} + 1.0 x_{3} + 0.5 x_{4} + 0.5 x_{5} \leq 2500 (3 rd year)$

(4) Non-negativity constraints of the decision variables:
$x_{j} \geq 0, j = 1, 2, \dots, 5 .$

The complete model can be formulated as follows:

$\begin{array}{l} max z = 9.343 x_{1} + 8.902 x_{2} + 2.118 x_{3} + 11.542 x_{4} + 4.044 x_{5} \\ subject to : \\ x_{1} + x_{2} + x_{3} + x_{4} + x_{5} \leq 1000 \\ 5.0 x_{1} + 4.2 x_{2} + 2.2 x_{3} + 6.6 x_{4} + 3.0 x_{5} \geq 6000 \\ 7.7 x_{1} + 6.5 x_{2} + 3.7 x_{3} + 8.0 x_{4} + 3.5 x_{5} \geq 5000 \\ 7.9 x_{1} + 7.2 x_{2} + 2.9 x_{3} + 6.1 x_{4} + 4.1 x_{5} \geq 6500 \\ 5.0 x_{1} + 4.0 x_{2} + 3.5 x_{3} + 3.5 x_{4} + 3.0 x_{5} \leq 3800 \\ 1.0 x_{1} + 1.0 x_{2} + 0.5 x_{3} + 1.5 x_{4} + 0.5 x_{5} \leq 3500 \\ 1.2 x_{1} + 0.5 x_{2} + 0.5 x_{3} + 0.5 x_{4} + 1.0 x_{5} \leq 3200 \\ 0.8 x_{1} + 0.5 x_{2} + 1.0 x_{3} + 0.5 x_{4} + 0.5 x_{5} \leq 2500 \\ x_{j} \geq 0, j = 1, 2, \dots, 5 \end{array}$

si90_e

The optimal solution of the linear programming model is x₁ = 173.33 (hectares for soybeans), x₂ = 80 (hectares for cassava), x₃ = 0 (hectares for corn), x₄ = 746.67 (hectares for wheat), x₅ = 0 (hectares for beans) with z = 10, 949.59 (US$ 10,949,590.00).

The example used a linear programming model (LP) to solve the respective capital budgeting problem. However, many times and given a set of investment project alternatives, we try to analyze which project i will be approved (x_i = 1) or rejected (x_i = 0), which becomes a binary programming (BP) problem since the decision variables are binary. This last case will be discussed in Chapter 19.

16.6.5 Portfolio Selection Problem

Markowitz (1952) developed a mathematical model to optimize portfolios that tries to choose, among a set of financial investments, the best combination that maximizes the portfolio’s expected return and minimizes its risk. The model is a quadratic programming problem that tries to find the portfolio’s efficient frontier. The risks of the portfolio are measured by using the variance of the return on assets, calculated as the sum of the individual variances of each asset and the covariances between the pairs of assets.

Sharpe (1964) proposed a simplified portfolio optimization model aiming at facilitating the calculation of the covariance matrix. Similar to Markowitz’s model, Sharpe’s model also tries to determine the portfolio’s optimal composition that will result in the highest return possible with the lowest risk.

Markowitz’s model requires the extensive calculation of the covariance matrix, so, it is highly complex. In order to facilitate its application, alternative models to Markowitz’s original model have been proposed.

From Markowitz’s (1952) and Sharpe’s (1964) theory, we can develop a linear programming model that determines the investment portfolio’s optimal composition and that minimizes the risks, with an expected level of return. Similarly, we can search for the best portfolio composition that maximizes the portfolio’s expected return, subject to the requirement of a minimum level of this value and to the maximum risk allowed.

Model 1: Maximization of an Investment Portfolio’s Expected Return

A linear programming model that maximizes an investment portfolio’s expected return, subject to the requirement of a minimum level of this value and to a given risk, is proposed.

Model parameters:

E(R) = investment portfolio’s expected return
μ_j = expected return of asset j, j = 1, …, n
ρ = minimum level required by the investor regarding the portfolio’s expected return
x_j^max = maximum percentage allowed of asset j to be allocated in the portfolio, j = 1, …, n
σ_j = standard deviation of asset j, j = 1, …, n
$\bar{σ}$ = the portfolio’s standard deviation or average risk

Decision variables:

x_j = percentage of asset j allocated in the portfolio, j = 1, …, n

General formulation:

$\begin{array}{l} max E (R) = \sum_{j = 1}^{n} μ_{j} x_{j} \\ s . t . \\ \sum_{j = 1}^{n} x_{j} = 1 (1) \\ \sum_{j = 1}^{n} μ_{j} x_{j} \geq ρ (2) \\ x_{j} \leq x_{j}^{\max}, j = 1, \dots, n (3) \\ \sum_{j = 1}^{n} σ_{j} x_{j} \leq \bar{σ} (4) \\ x_{j} \geq 0, j = 1, \dots, n (5) \end{array}$

si92_e (16.14)

The model’s objective function tries to maximize the average return of an investment portfolio with n financial assets.

Constraint 1 guarantees that all the capital will be invested.

Constraint 2 guarantees that the portfolio’s average return will achieve the minimum limit required by the investor in the value of ρ.

Constraint 3 states that the percentage of asset i allocated in the portfolio cannot be higher than x_j^max, so that the portfolio can be diversified and its risk minimized. It is important to mention that some expected return maximization models do not consider this constraint.

An alternative to constraint 3 can be represented by Equation (4) of Expression (16.14) that ensures that the portfolio’s average risk cannot be higher than $\bar{σ}$ . The risks of each asset and of the portfolio are measured by the standard deviation.

Finally, the decision variables should meet the non-negativity condition.

Model 2: Investment Portfolio Risk Minimization

An alternative to Markowitz’s model was proposed by Konno and Yamazaki (1991) that introduced the mean absolute deviation (MAD) as a risk measure. The model that minimizes the MAD is shown now.

Model parameters:

MAD = the portfolio’s mean absolute deviation
r_jt = return of asset j in period t, j = 1, …, n, t = 1, …, T
μ_j = expected return of asset j, j = 1, …, n
ρ = minimum level required by the investor regarding the portfolio’s expected return
x_j^max = maximum percentage allowed of asset j to be allocated in the portfolio, j = 1, …, n

Decision variables:

x_j = percentage of asset j allocated in the portfolio, j = 1, …, n.

General formulation:

$\begin{array}{l} min MAD = \frac{1}{T} \sum_{t = 1}^{T} |\sum_{j = 1}^{n} (r_{jt} - μ_{j}) x_{j}| \\ s . t . \\ \sum_{j = 1}^{n} x_{j} = 1 (1) \\ \sum_{j = 1}^{n} μ_{j} x_{j} \geq ρ (2) \\ 0 \leq x_{j} \leq x_{j}^{\max}, j = 1, \dots, n (3) \end{array}$

si94_e (16.15)

The model’s objective function tries to minimize the portfolio’s mean absolute deviation.

Constraint 1 guarantees that all the capital will be invested.

Constraint 2 guarantees that the portfolio’s average return will achieve the minimum limit required by the investor in the value of ρ.

Constraint 3 states that the positive percentage of asset i allocated in the portfolio cannot be higher than x_j^max.

Example 16.8

Investor Paul Smith operates daily on Forinvest’s home broker system. Paul wants to select a new investment portfolio that maximizes its expected return with a certain risk. Based on a historical analysis of the most highly negotiable and representative assets in the Brazilian stock market, Forinvest’s financial analyst selected a set of 10 stocks trading on B3 (Brazilian Stock Exchange) that could form Paul’s portfolio, as shown in Table 16.E.8. The financial analyst tried to select a set of stocks from many different sectors, which were chosen according to Paul’s preferences. Table 16.E.9 shows a partial history of the daily return of each stock during 247 days. The complete data can be found in the file Forinvest.xls.

In order to diversify the portfolio and, consequently, minimize the portfolio’s risks, the financial analyst advised Paul to invest 30%, at the most, in each stock. Besides, the portfolio’s risks, measured by the standard deviation, could not be greater than 2.5%. Elaborate the linear programming model that maximizes Paul’s portfolio’s expected return.

Table 16.E.8

Stocks That Could Be in Paul’s Portfolio
	Stocks	Code
1	Banco Brasil ON	BBAS3
2	Bradesco PN	BBDC4
3	Eletrobras PNB	ELET6
4	Gerdau PN	GGBR4
5	Itausa PN	ITSA4
6	Petrobras PN	PETR4
7	Sid Nacional ON	CSNA3
8	Telemar PN	TNLP4
9	Usiminas PNA	USIM5
10	Vale PNA	VALE5

Table 16.E.9

Partial History of the Assets’ Daily Return
Period	BBAS3 (%)	BBDC4 (%)	ELET6 (%)	GGBR4 (%)	ITSA4 (%)	PETR4 (%)	CSNA3 (%)	TNLP4 (%)	USIM5 (%)	VALE5 (%)
1	− 6.74	− 6.04	− 1.47	− 4.48	− 6.50	− 2.71	− 2.06	− 3.19	− 4.40	− 3.93
2	6.31	3.05	4.23	5.00	2.14	3.43	4.34	0.22	3.42	2.72
3	− 4.00	− 2.08	1.47	1.67	− 3.27	0.75	2.45	− 2.19	3.06	0.76
4	0.28	0.14	− 3.66	− 1.64	0.81	− 1.85	1.01	1.29	− 0.63	− 0.79
5	− 6.86	− 5.28	− 3.79	− 4.76	− 5.50	− 3.23	− 6.66	− 0.11	− 4.87	− 4.13
6	2.23	4.87	2.96	3.25	3.69	5.20	7.05	0.97	3.89	2.65
7	− 1.45	− 0.90	− 1.04	− 4.12	− 2.47	− 2.56	− 0.92	0.07	0.41	− 0.46
8	− 1.85	1.05	− 1.17	− 1.77	2.39	− 0.21	− 2.82	3.67	− 4.13	1.74
9	6.09	0.14	1.39	0.90	− 0.82	0.89	1.42	3.75	− 2.90	2.47
10	1.70	− 1.94	− 1.21	− 3.44	− 1.38	0.42	2.34	− 0.14	0.40	3.64

Unlabelled Table

Solution

First of all, we calculated the average return and the standard deviation of the daily returns of each investment during the period analyzed, as shown in Table 16.E.10.

Table 16.E.10

Average Return and Standard Deviation of Each Stock During the Period Analyzed
	BBAS3 (%)	BBDC4 (%)	ELET6 (%)	GGBR4 (%)	ITSA4 (%)	PETR4 (%)	CSNA3 (%)	TNLP4 (%)	USIM5 (%)	VALE5 (%)
Average return	− 6.74	− 6.04	− 1.47	− 4.48	− 6.50	− 2.71	− 2.06	− 3.19	− 4.40	− 3.93
Standard deviation	6.31	3.05	4.23	5.00	2.14	3.43	4.34	0.22	3.42	2.72

Unlabelled Table

The second step consists of defining the model’s decision variables:

x_j = percentage of stock j to be allocated in the portfolio, j = 1, …, 10.

Therefore, we have:

x₁ = percentage of stock BBAS3 to be allocated in the portfolio.

x₂ = percentage of stock BBDC4 to be allocated in the portfolio.

x₃ = percentage of stock ELET6 to be allocated in the portfolio.

x₄ = percentage of stock GGBR4 to be allocated in the portfolio.

x₅ = percentage of stock ITSA4 to be allocated in the portfolio.

x₆ = percentage of stock PETR4 to be allocated in the portfolio.

x₇ = percentage of stock CSNA3 to be allocated in the portfolio.

x₈ = percentage of stock TNLP4 to be allocated in the portfolio.

x₉ = percentage of stock USIM5 to be allocated in the portfolio.

x₁₀ = percentage of stock VALE5 to be allocated in the portfolio.

The model’s objective function tries to maximize Paul’s portfolio’s expected return during the period analyzed. Therefore, the objective function can be expressed as:

$\begin{array}{l} F_{obj} = max z = 0.0037 x_{1} + 0.0024 x_{2} + 0.0014 x_{3} + 0.0030 x_{4} + 0.0024 x_{5} + 0.0019 x_{6} \\ + 0.0028 x_{7} + 0.0018 x_{8} + 0.0025 x_{9} + 0.0024 x_{10} \end{array}$

si95_e

The model’s constraints are described now.

(1) The first constraint guarantees that 100% of the capital will be invested, that is, the sum of the composition of the stocks is equal to 1:
$x_{1} + x_{2} + \dots + x_{10} = 1$

(2) Constraint 2 states that the maximum percentage to be invested in each stock is 30% of the total capital invested:
$x_{1}, x_{2}, \dots, x_{10} \leq 0.30$

(3) Constraint 3 guarantees that the portfolio’s risks, for the period analyzed, will not be greater than the maximum risk stipulated, that is, 2.5%:
$0.0248 x_{1} + 0.0216 x_{2} + \dots + 0.0247 x_{10} \leq 0.0250$

(4) Finally, the non-negativity conditions of the decision variables must be met:
$x_{1}, x_{2}, \dots, x_{10} \geq 0$

The complete model can be formulated as follows:

$\begin{array}{l} max E (R) = 0.0037 x_{1} + 0.0024 x_{2} + 0.0014 x_{3} + 0.0030 x_{4} + 0.0024 x_{5} + 0.0019 x_{6} + \\ 0.0028 x_{7} + 0.0018 x_{8} + 0.0025 x_{9} + 0.0024 x_{10} \\ s . t . \\ x_{1} + x_{2} + \dots + x_{10} = 1 (1) \\ x_{1}, x_{2}, \dots, x_{10} \leq 0.30 (2) \\ 0.0248 x_{1} + 0.0216 x_{2} + \dots + 0.0247 x_{10} \leq 0.0250 (3) \\ x_{1}, x_{2}, \dots, x_{10} \geq 0 (4) \end{array}$

si100_e

The optimal solution of the linear programming model is x₁ = 30% (Banco do Brasil ON—BBAS3), x₂ = 30% (Bradesco PN—BBDC4), x₄ = 18.17% (Gerdau PN—GGBR4), x₇ = 21.83% (Sid Nacional ON—CSNA3), and x₃, x₅, x₆, x₈, x₉, x₁₀ = 0 with z = 0.3% (daily average return of 0.3%).

Example 16.9

Consider the same portfolio optimization problem as Paul Smith’s problem described in Example 16.8. Now, in this case, instead of maximizing the expected return, we want to minimize the portfolio’s mean absolute deviation (MAD). Different from the previous example, instead of considering the maximum risk allowed constraint, we will consider a minimum limit of the portfolio’s expected daily return in the value of 0.15%. Analogous to the previous example, we must invest 30% of the capital total, at the most, in each asset. Consider the same assets (Table 16.E.9) and the same history of daily returns (Table 16.E.10) of the previous example (see file Forinvest.xls). Elaborate the linear programming problem that minimizes the portfolio’s MAD.

Solution

First of all, we must calculate the MAD of each asset in the portfolio.

Let’s consider the first stock (BBAS3). The first step is to calculate the absolute deviation in each period. As calculated in Example 16.8, we can see that the average return of stock BBAS3, for the period analyzed, is 0.37%. Since the return of the first period is − 6.74%, we can conclude that | r₁₁ − μ₁ | = |−0.0674 − 0.0037 | = 0.0711. Now, for period 2, we have | r₁₂ − μ₁ | = | 0.0631 − 0.0037 | = 0.0594. Then, we do the same for the other periods. For the last period, we have | r₁₂₄₇ − μ₁ | = | 0.0128 − 0.0037 | = 0.0091. The second step consists in calculating the mean absolute deviation of BBAS3, that is, the arithmetic mean of the absolute deviations for each period:

$\frac{1}{247} \times (0.0711 + 0.0594 + \dots + 0.0091) = 0.0187$

si101_e

Then, we do the same for the other stocks. Table 16.E.11 shows the mean absolute deviation of each asset.

Table 16.E.11

Mean Absolute Deviation of Each Stock
	BBAS3 (%)	BBDC4 (%)	ELET6 (%)	GGBR4 (%)	ITSA4 (%)	PETR4 (%)	CSNA3 (%)	TNLP4 (%)	USIM5 (%)	VALE5 (%)
MAD	1.87	1.65	1.47	2.28	1.69	1.50	1.99	1.66	2.11	1.79

Unlabelled Table

The objective function tries to minimize the portfolio’s MAD, and it can be written as follows:

$F_{obj} = min MAD = 0.0187 x_{1} + 0.0165 x_{2} + 0.0147 x_{3} + 0.0228 x_{4} + 0.0169 x_{5} + 0.0150 x_{6} + 0.0199 x_{7} + 0.0166 x_{8} + 0.0211 x_{9} + 0.0179 x_{10}$

si102_e

The constraint that the portfolio’s daily average return should achieve the minimum limit required by the investor must be considered:

$0.0037 x_{1} + 0.0024 x_{2} + \dots + 0.0024 x_{10} \geq 0.0015$

The complete model can be formulated as follows:

$\begin{array}{l} min MAD = 0.0187 x_{1} + 0.0165 x_{2} + 0.0147 x_{3} + 0.0228 x_{4} + 0.0169 x_{5} + 0.0150 x_{6} \\ + 0.0199 x_{7} + 0.0166 x_{8} + 0.0211 x_{9} + 0.0179 x_{10} \\ s . t . \\ x_{1} + x_{2} + \dots + x_{10} = 1 (1) \\ 0.0037 x_{1} + 0.0024 x_{2} + \dots + 0.0024 x_{10} \geq 0.0015 (2) \\ 0 \leq x_{1}, x_{2}, \dots, x_{10} \leq 0.30 (3) \end{array}$

si104_e

The optimal solution of the linear programming model is x₂ = 30% (Bradesco PN—BBDC4), x₃ = 30% (Eletrobras PNB—ELET6), x₆ = 30% (Petrobras PN—PETR4), x₈ = 10% (Telemar PN—TNLP4), and x₁, x₄, x₅, x₇, x₉, x₁₀ = 0 with z = 1.55% (the portfolio’s mean absolute deviation).

16.6.6 Production and Inventory Problem

In this section, we will consider a linear programming model that integrates production and inventory decisions. The period of time can be short, medium, or long.

A general linear programming model to solve the production and inventory problem, based on Taha (2010, 2016) and Ahuja et al. (2007), will be presented, for a case with m products (i = 1, …, m) and T periods (t = 1, …, T).

Model parameters:

D_it = demand for product i in period t
c_it = production cost per unit of product i in period t
i_it = inventory cost per unit of product i in period t
x_it^max = maximum production capacity of product i in period t
I_it^max = maximum inventory capacity of product i in period t

Decision variables:

x_it = amount of product i to be produced in period t
I_it = final inventory of product i in period t

General formulation:

$\begin{array}{l} min z = \sum_{t = 1}^{T} \sum_{i = 1}^{m} (c_{it} x_{it} + i_{it} I_{it}) \\ s . t . \\ I_{it} = I_{i, t - 1} + x_{it} - D_{it}, i = 1, \dots, m; t = 1, \dots, T (1) \\ x_{it} \leq x_{it}^{\max}, i = 1, \dots, m; t = 1, \dots, T (2) \\ I_{it} \leq I_{it}^{\max}, i = 1, \dots, m; t = 1, \dots, T (3) \\ x_{it}, I_{it} \geq 0 i = 1, \dots, m; t = 1, \dots, T (4) \end{array}$

si105_e (16.16)

The model’s objective function is trying to minimize the sum of the production and inventory costs for T periods of time.

For each product, constraint 1 represents the inventory balance expression, that is, the final inventory in period t is the same as the final inventory in the previous period, added to the total produced in the same period, subtracted the demand for the current period. So, in order for the demand for product i to be met in period t, the inventory level of the same product in the previous period, added to what was produced in the same period, must be greater than or equal to the demand. This condition is implied in the model since decision variable I_it can only assume non-negative values.

Constraint 2 guarantees that the maximum production capacity will not be exceeded.

Constraint 3 guarantees that the maximum inventory capacity will not be exceeded.

Finally, the non-negativity conditions of the model’s decision variables must also be met. Similar to the production mix problem, in which the decision variables can only assume integer values (i.e., the manufacturing and storing of products cannot be fractioned, such as, cars, electrical appliances, electrical devices, etc.), we have an integer programming (IP) problem.

Example 16.10

Fenix & Furniture is launching their new collection of sofas and armchairs for next semester. This new collection includes 2- and 3-seat sofas, sofa-beds, armchairs, and poufs. Table 16.E.12 shows the data on the production and inventory costs and capacity for each product, which are constant for all the periods. The demand for each product for next semester is listed in Table 16.E.13. The initial inventory for all the products is 200 units. Determine the optimal production and inventory control planning that minimizes the total production and storage costs, meets the intended demand, and respects the production and storage capacity limitations.

Table 16.E.12

Production and Inventory Costs and Capacity for Each Product
	2-Seat Sofa	3-Seat Sofa	Sofa-Bed	Armchair	Pouf
Production cost (US$/unit)	320	440	530	66	48
Inventory cost (US$/unit)	8	8	9	3	3
Production capacity (units)	1800	1600	1500	2000	2000
Inventory capacity (units)	20,000	18,000	15,000	22,000	22,000

Unlabelled Table

Table 16.E.13

Demand Per Product and Period
	Jan.	Feb.	March	April	May	Jun.
2-Seat sofa	1200	1250	1400	1860	2000	1700
3-Seat sofa	1250	1430	1650	1700	1450	1500
Sofa-bed	1400	1500	1200	1350	1600	1450
Armchair	1800	1750	2100	2000	1850	1630
Pouf	1850	1700	2050	1950	2050	1740

Unlabelled Table

Solution

The mathematical formulation of Example 16.10 is similar to the general formulation of the production and inventory problem presented in Expression (16.16). The complete model is shown now.

First of all, we have to define the model’s decision variables:

x_it = number of pieces of furniture i to be produced in month t (units), i = 1, …, 5, t = 1, …, 6
I_it = final inventory of piece of furniture i in month t (units), i = 1, …, 5, t = 1, …, 6

Therefore, we have:

x₁₁ = number of 2-seat sofas to be produced in January.

$⋮$

x₁₆ = number of 2-seat sofas to be produced in June.

x₂₁ = number of 3-seat sofas to be produced in January.

$⋮$

x₂₆ = number of 3-seat sofas to be produced in June.

x₃₁ = number of sofa-beds to be produced in January.

$⋮$

x₃₆ = number of sofa-beds to be produced in June.

x₄₁ = number of armchairs to be produced in January.

$⋮$

x₄₆ = number of armchairs to be produced in June.

x₅₁ = number of poufs to be produced in January.

$⋮$

x₅₆ = number of poufs to be produced in June.

I₁₁ = final inventory of 2-seat sofas in January.

$⋮$

I₁₆ = final inventory of 2-seat sofas in June.

I₂₁ = final inventory of 3-seat sofas in January.

$⋮$

I₂₆ = final inventory of 3-seat sofas in June.

I₃₁ = final inventory of sofa-beds in January.

$⋮$

I₃₆ = final inventory of sofa-beds in June.

I₄₁ = final inventory of armchairs in January.

$⋮$

I₄₆ = final inventory of armchairs in June.

I₅₁ = final inventory of poufs in January.

$⋮$

I₅₆ = final inventory of poufs in June.

Since the decision variables are discrete, we have an integer programming (IP) problem. Luckily, in this problem, the integrality constraints can be relaxed or eliminated, since the relaxed problem’s optimal solution still meets the integrality conditions. Thus, the formulation of the problem will be presented as a linear programming (LP) model.

The objective function can be written as:

$\begin{array}{l} min z = 320 (x_{11} + x_{12} + x_{13} + x_{14} + x_{15} + x_{16}) + 8 (I_{11} + I_{12} + I_{13} + I_{14} + I_{15} + I_{16}) \\ + 440 (x_{21} + x_{22} + x_{23} + x_{24} + x_{25} + x_{26}) + 8 (I_{21} + I_{22} + I_{23} + I_{24} + I_{25} + I_{26}) \\ + 530 (x_{31} + x_{32} + x_{33} + x_{34} + x_{35} + x_{36}) + 9 (I_{31} + I_{32} + I_{33} + I_{34} + I_{35} + I_{36}) \\ + 66 (x_{41} + x_{42} + x_{43} + x_{44} + x_{45} + x_{46}) + 3 (I_{41} + I_{42} + I_{43} + I_{44} + I_{45} + I_{46}) \\ + 48 (x_{51} + x_{52} + x_{53} + x_{54} + x_{55} + x_{56}) + 3 (I_{51} + I_{52} + I_{53} + I_{54} + I_{55} + I_{56}) \end{array}$

si116_e

The model’s constraints are described here.

(1) Inventory balance equations, for each piece of furniture i (i = 1, …, 5), each month t (t = 1, …, 6):
$\begin{array}{l} I_{11} = 200 + x_{11} - 1200 \\ I_{12} = I_{11} + x_{12} - 1250 \\ I_{13} = I_{12} + x_{13} - 1400 \\ I_{14} = I_{13} + x_{14} - 1860 \\ I_{15} = I_{14} + x_{15} - 2000 \\ I_{16} = I_{15} + x_{16} - 1700 \end{array}$

$\begin{array}{l} I_{21} = 200 + x_{21} - 1250 \\ I_{22} = I_{21} + x_{22} - 1430 \\ I_{23} = I_{22} + x_{23} - 1650 \\ I_{24} = I_{23} + x_{24} - 1700 \\ I_{25} = I_{24} + x_{25} - 1450 \\ I_{26} = I_{25} + x_{26} - 1500 \end{array}$

$\begin{array}{l} I_{31} = 200 + x_{31} - 1400 \\ I_{32} = I_{31} + x_{32} - 1500 \\ I_{33} = I_{32} + x_{33} - 1200 \\ I_{34} = I_{33} + x_{34} - 1350 \\ I_{35} = I_{34} + x_{35} - 1600 \\ I_{36} = I_{35} + x_{36} - 1450 \end{array}$

$\begin{array}{l} I_{41} = 200 + x_{41} - 1800 \\ I_{42} = I_{41} + x_{42} - 1750 \\ I_{43} = I_{42} + x_{43} - 2100 \\ I_{44} = I_{43} + x_{44} - 2000 \\ I_{45} = I_{44} + x_{45} - 1850 \\ I_{46} = I_{45} + x_{46} - 1630 \end{array}$

$\begin{array}{l} I_{51} = 200 + x_{51} - 1850 \\ I_{52} = I_{51} + x_{52} - 1700 \\ I_{53} = I_{52} + x_{53} - 2050 \\ I_{54} = I_{53} + x_{54} - 1950 \\ I_{55} = I_{54} + x_{55} - 2050 \\ I_{56} = I_{55} + x_{56} - 1740 \end{array}$

(2) Maximum production capacity:
$x_{11}, x_{12}, x_{13}, x_{14}, x_{15}, x_{16} \leq 1800$

$x_{21}, x_{22}, x_{23}, x_{24}, x_{25}, x_{26} \leq 1600$

$x_{31}, x_{32}, x_{33}, x_{34}, x_{35}, x_{36} \leq 1500$

$x_{41}, x_{42}, x_{43}, x_{44}, x_{45}, x_{46} \leq 2000$

$x_{51}, x_{52}, x_{53}, x_{54}, x_{55}, x_{56} \leq 2000$

(3) Maximum inventory capacity:
$I_{11}, I_{12}, I_{13}, I_{14}, I_{15}, I_{16} \leq 20, 000$

$I_{21}, I_{22}, I_{23}, I_{24}, I_{25}, I_{26} \leq 18, 000$

$I_{31}, I_{32}, I_{33}, I_{34}, I_{35}, I_{36} \leq 15, 000$

$I_{41}, I_{42}, I_{43}, I_{44}, I_{45}, I_{46} \leq 22, 000$

$I_{51}, I_{52}, I_{53}, I_{54}, I_{55}, I_{56} \leq 22, 000$

(4) Non-negativity constraints:

$x_{it}, I_{it} \geq 0 i = 1, \dots, 5; t = 1, \dots, 6$

The production and inventory model’s optimal solution is shown in Table 16.E.14.

Table 16.E.14

Production and Inventory Model’s Optimal Solution
Solution	Jan.	Feb.	March	April	May	Jun.	z
x_1t	1000	1250	1660	1800	1800	1700	US$ 12,472,680.00
x_2t	1050	1580	1600	1600	1450	1500
x_3t	1200	1500	1200	1450	1500	1450
x_4t	1600	1850	2000	2000	1850	1630
x_5t	1650	1750	2000	2000	2000	1740
I_1t	0	0	260	200	0	0
I_2t	0	150	100	0	0	0
I_3t	0	0	0	100	0	0
I_4t	0	100	0	0	0	0
I_5t	0	50	0	50	0	0

Unlabelled Table

..................Content has been hidden....................

You can't read the all page of ebook, please click here login for view all page.

Table of Contents for Chapter 16: Introduction to Optimization Models: General Formulations and Business Modeling

Create new playlist

Sign In

Sign Up

16.1 Introduction to Optimization Models

16.2 Introduction to Linear Programming Models

16.3 Mathematical Formulation of a General Linear Programming Model

16.4 Linear Programming Model in the Standard and Canonical Forms

16.4.1 Linear Programming Model in the Standard Form

16.4.2 Linear Programming Model in the Canonical Form

16.4.3 Transformations Into the Standard or Canonical Form

16.5 Assumptions of the Linear Programming Model

16.5.1 Proportionality

16.5.2 Additivity

16.5.3 Divisibility and Non-negativity

16.5.4 Certainty

16.6 Modeling Business Problems Using Linear Programming

16.6.1 Production Mix Problem

16.6.2 Blending or Mixing Problem

16.6.3 Diet Problem

16.6.4 Capital Budget Problems

16.6.5 Portfolio Selection Problem

Model 1: Maximization of an Investment Portfolio’s Expected Return

Model 2: Investment Portfolio Risk Minimization

16.6.6 Production and Inventory Problem

Table of Contents for
Chapter 16: Introduction to Optimization Models: General Formulations and Business Modeling