6  Systems of Linear Equations

\[ \definecolor{dgray}{rgb}{0.3,0.3,0.3} \definecolor{lgray}{rgb}{0.85,0.85,0.85} \]

6.1 Vectors

6.1.1 Notations

In this section, which marks the start of the important field of Linear Algebra, lists of numbers appear, called vectors. The name vector originally comes from geometry and means arrow. However, we will not deal with the geometric interpretation of Linear Algebra here. Therefore, we simply accept the name as it is.

For us, vectors are nothing more than finite lists of numbers. New for us is that we will write vectors in two different ways. The numbers that form a vector, its components, can be arranged horizontally as a row vector, or vertically as a column vector.

Example 6.1

Vectors that we write as columns, e.g., \[ \begin{gathered} \mathbf a=\left(\begin{array}{r}-1\\2\end{array}\right),\quad \mathbf b=\left(\begin{array}{r}5\\-2\\7\end{array}\right) \end{gathered} \] we call column vectors. We can also write vectors as row vectors, e.g., \[ \begin{gathered} \mathbf c=\left(\begin{array}{rr}3 & -2\end{array}\right), \quad \mathbf d=\left(\begin{array}{rrr}1 & 0 & 4\end{array}\right). \end{gathered} \]

For now, we will not differentiate between column and row vectors and limit ourselves to organizing vectors vertically. But everything we describe for column vectors will also apply analogously to row vectors.

Definition 6.2 A vector (column vector) is an ordered list of real numbers that are arranged vertically. The elements of the list are called the components of the vector. The number of components is called the dimension of the vector.

We denote vectors with bold lowercase letters and their components with the same lowercase letter and an index: \[ \begin{gathered} \mathbf a=\left(\begin{array}{c} a_1\\a_2\\\vdots\\a_n\end{array}\right), \quad \mathbf b=\left(\begin{array}{c} b_1\\b_2\\\vdots\\b_n\end{array}\right). \end{gathered} \] The set of all column vectors of dimension \(n\) is denoted by \(\mathbb R^n\). The \(\mathbb R^2\) is the plane, the \(\mathbb R^3\) the three-dimensional space. We will use vectors from \(\mathbb R^n\) in the future, which we can no longer visually interpret.

A special vector is the zero vector, whose components are all \(0\) \[ \begin{gathered} \boldsymbol{0}=\left(\begin{array}{c}0\\0\\\vdots\\0\end{array} \right). \end{gathered} \]

6.1.2 Vector Arithmetics

Example 6.3

Let \[ \begin{gathered} \mathbf a=\left(\begin{array}{r}1\\-5\\7\\2\end{array}\right),\quad \mathbf b=\left(\begin{array}{r}8\\0\\-4\\1\end{array}\right),\quad \mathbf c=\left(\begin{array}{r}-3\\2\\4\\0\end{array}\right), \end{gathered} \] be vectors in \(\mathbb R^4\). First, we explain how to add vectors and multiply by a number.

Two vectors are added by adding their components, for example: \[ \begin{gathered} \mathbf a+\mathbf b= \left(\begin{array}{r}9\\-5\\3\\3 \end{array}\right). \end{gathered} \] Vectors of different dimensions cannot be added.

A vector is multiplied by a number by multiplying each component by the number: \[ \begin{gathered} 3\mathbf c=\left(\begin{array}{r}-9\\6\\12\\0 \end{array}\right). \end{gathered} \] Multiplication of two vectors that would correspond to the multiplication of two numbers will be introduced later.

Simple arithmetic tasks involving vectors can be conveniently solved by initially simplifying the problem symbolically using the obvious arithmetic laws.

Exercise 6.4 Using the information from example Example 6.3: determine a vector \(\mathbf x\) such that it solves the equation \(3\mathbf a+5\mathbf x=\mathbf b\).

Solution: We solve this problem symbolically first: \[ \begin{gathered} 3\mathbf a+5\mathbf x=\mathbf b\quad\Rightarrow\quad 5\mathbf x=\mathbf b-3\mathbf a\quad\Rightarrow\quad \mathbf x=\frac{1}{5}\left(\mathbf b-3\mathbf a\right). \end{gathered} \] Then we can obtain the numerical solution by substitution: \[ \begin{gathered} \mathbf x=\frac{1}{5}\left(\mathbf b-3\mathbf a\right)= \left(\begin{array}{r}1\\3\\-5\\-1\end{array}\right). \end{gathered} \] □

When we create new vectors from several vectors by adding and by multiplying with numbers, structures are formed that have a special name.

Definition 6.5 (Linear Combination) A linear combination of the vectors \(\mathbf a_1\), \(\mathbf a_2\), \(\ldots\), \(\mathbf a_k\) in \(\mathbb R^n\) is understood to be an expression of the form \[ \begin{gathered} \mathbf z=\gamma_1\mathbf a_1+\gamma_2\mathbf a_2+\cdots+\gamma_k\mathbf a_k, \end{gathered} \] where \(\gamma_1,\gamma_2,\ldots,\gamma_k\) are numbers.

6.2 Solving Linear Equation Systems

6.2.1 Introduction

Solving a single linear equation with one variable is an important but also one of the simplest tasks in linear algebra. However, when you want to solve several linear equations with multiple unknowns at the same time, a more complicated situation arises. Solving such systems of linear equations is of fundamental importance for a variety of advanced tasks, which play a major role in applications. In this section, we will address the resolution of systems of linear equations and the related mathematical concepts.

Notation

A general system of linear equations with \(m\) equations and \(n\) unknowns takes the following form: \[ \begin{gathered} \begin{array}{ccccccc} a_{11}x_1 &+& a_{12}x_2 &+\;\cdots\;+& a_{1n}x_n &=& b_1 \\ a_{21}x_1 &+& a_{22}x_2 &+\;\cdots\;+& a_{2n}x_n &=& b_2 \\ \vdots && \vdots && \vdots && \vdots\\ a_{m1}x_1 &+& a_{m2}x_2 &+\;\cdots\;+& a_{mn}x_n &=& b_m \\ \end{array} \end{gathered} \tag{6.1}\]

The numbers \(a_{ij}\) are the coefficients of the equation system, while the numbers \(b_i\) are the right-hand sides. The set of solutions of the system of equations refers to the set of all vectors \[ \begin{gathered} \mathbf x=\left(\begin{array}{r}x_1\\x_2\\\vdots\\x_n \end{array}\right) \in\mathbb R^n, \end{gathered} \] that solve the equation system.

It is often convenient to replace the detailed equation system with its associated number schemata. A rectangular array of this kind is called a matrix. In connection with systems of linear equations of the form (6.2) there are two such matrices, which will play different roles: \[ \begin{gathered} \begin{array}{c@{\quad}c} \text{Coefficient Matrix}&\text{Equation Matrix}\\ \left( \begin{array}{cccc} a_{11} &a_{12} &\ldots & a_{1n}\\ a_{21} & a_{22} &\ldots &a_{2n}\\ \vdots&\vdots&\ddots&\vdots\\ a_{m1}&a_{m2}&\ldots&a_{mn} \end{array} \right)& \left( \begin{array}{cccc|c} a_{11} &a_{12} &\ldots & a_{1n}&b_1\\ a_{21} & a_{22} &\ldots &a_{2n}&b_2\\ \vdots&\vdots&\ddots&\vdots&\vdots\\ a_{m1}&a_{m2}&\ldots&a_{mn}&b_m \end{array} \right) \end{array} \end{gathered} \]

Example 6.6 (A Macroeconomic Model)

In macroeconomics, models are developed for the analysis of economic activities which, in many cases, can be represented by systems of linear equations. A very simple model, which follows the tradition of the British economist J. M. Keynes (1883–1946), includes the following three equations with five variables: \[ \begin{aligned} \begin{array}{cclcl} C &=& \alpha_1 + \alpha_2 Y &\qquad &\text{Consumption Function} \\[5pt] I &=& \beta_1 + \beta_2 Y + \beta_3 R&&\text{Investment Function}\\[5pt] Y &=& C + I+G&&\text{Equilibrium Condition} \end{array}\end{aligned} \] The variables are: \[ \begin{aligned} \mathit{endogenous}:&\left\{ \begin{array}{cl} Y & \text{Gross Domestic Product}\\ C & \text{Consumer Spending}\\ I & \text{Investments} \end{array} \right.\\ \mathit{exogenous}:&\left\{ \begin{array}{cl} R & \text{Interest Rate}\\ G & \text{Government Spending} \end{array}\right. \end{aligned} \] Endogenous means that these variables are explained by the model, while exogenous variables serve as instruments of economic policy influence. The government can influence GDP, consumption, and investment spending by changing government expenditures \(G\). The same applies to the central bank, which can change the interest rate through appropriate measures. The parameters \(\alpha_1,\alpha_2\) and \(\beta_1,\beta_2, \beta_3\) are determined using methods of econometrics.

In the classical single-period analysis, the system of equations is solved for the endogenous variables. For instance, it can be assessed what effect an increase in government spending has on Gross Domestic Product. It turns out that this multiplier effect can be considerable.

Example 6.7 (Internal Transfer Pricing)

In cost accounting, deliveries and services that are provided within a company from one cost center to another must be evaluated in an appropriate manner. The principle is that no cost center should make a profit or a loss. More precisely, the following identity applies: \[ \begin{gathered} \text{primary costs}+\text{received services}= \\ \text{delivered services} \end{gathered} \tag{6.2}\] Suppose we have three cost centers with the following data: \[ \begin{gathered} \begin{array}{llrr} & \text{Cost Center} &\text{Service Prov.} & \text{Primary Costs}\\ \hline K_1: & \text{Real Estate/Buildings} & 750 ~m^2 & 29,388\\ K_2: & \text{Energy} & 1,450 ~\mathit{kWh} & 3,450\\ K_3: & \text{Maintenance} & 480~\mathit{h} & 9,568 \end{array} \end{gathered} \] During the calculation period, the cost centers received services from the other cost centers:

• \(K_1\): 28 kWh from \(K_2\) and 20 \(h\) from \(K_3\).

• \(K_2\): 40 \(m^2\) from \(K_1\) and 30 \(h\) from \(K_3\).

• \(K_3\): 60 \(m^2\) from \(K_1\) and 8 kWh from \(K_2\).

At what prices should these internally provided services be charged? Let \(p_1,p_2\) and \(p_3\) be these prices. From the condition (6.1), we derive the following three equations: \[ \begin{gathered} \begin{array}{rcrcrcrcr} 29388 &+& & & 28p_2 &+& 20 p_3 &=& 750p_1\\ 3450 &+& 40p_1 & & & +& 30 p_3 &=& 1450p_2\\ 9568 &+& 60p_1 &+ &8p_2 & & &=& 480p_3 \end{array}% \qquad p_1=40, p_2=4, p_3=25 \end{gathered} \] This is a linear system of equations with three equations and three unknowns.

6.2.2 The Elimination Method

When dealing with the solving of linear systems of equations, the focus is mainly on the following questions:

• Is the system of equations solvable at all?

• How many solutions are there?

• How do you find all the solutions?

For the answers to all three questions, there is a systematic solution method, the so-called elimination method. It involves an algorithm, meaning a sequence of calculation steps that can be carried out mechanically.

The basic idea of the elimination method is very simple. It is about systematically simplifying the system of equations while ensuring that the set of solutions does not change. In order for the set of solutions to remain unchanged during the simplification steps, only certain specific, so-called allowed simplification steps can be carried out.

These are:

1. Multiplication of an equation by a nonzero number.

2. Interchanging two equations.

3. Adding a multiple of one equation to another equation.

Using the simplification steps, the original system of equations is modified step by step. The goal is to obtain a a system of equations in a specific form, the so-called row-echelon form. What is meant by this will become clear through the following examples. Once the system of equations is in row-echelon form, it becomes very easy to assess the solvability and to read off the set of solutions. Since the simplification steps do not change the set of solutions, the set of solutions of the system in row-echelon form corresponds to the original system of equations.

We will first explain the elimination method using an example. We want to solve the system of equations \[ \begin{gathered} I: \left\{\begin{array}{lcrcrcrcr} Z_1 &:& x_1 &-& x_2 &-& x_3 &=& 1\\ Z_2 &:& 2x_1&-& 3x_2 &+& x_3 &=& 10\\ Z_3 &:& x_1 &+& x_2 &-& 2x_3 &=& 0 \end{array}\right. \end{gathered} \] using the elimination method. \(Z_1,Z_2\) and \(Z_3\) are labels with which we reference the individual equations; \(I\) indicates that this is the system in its original state.

We start with the first cycle of elimination and aim to ensure that the variable \(x_1\) only appears in equation \(Z_1\). We achieve that by applying step 3 twice. Symbolically: \[ \begin{gathered} \begin{array}{ccl} Z_2&\to & Z_2-2Z_1\\ Z_3&\to & Z_3-Z_1 \end{array} \end{gathered} \] In other words, we subtract twice the first equation from the second, and then the first equation from the third. This yields: \[ \begin{gathered} II:\left\{\begin{array}{lcrcrcrcr} Z_1 &:& x_1 &-& x_2 &-& x_3 &=& 1\\ Z_2 &:& \cellcolor{lgray} &-& x_2 &+& 3x_3 &=& 8\\ Z_3 &:& \cellcolor{lgray} & & 2x_2 &-& x_3 &=& -1 \end{array}\right. \end{gathered} \] We have succeeded in eliminating \(x_1\) from \(Z_2\) and \(Z_3\). We also say we have promoted \(x_1\) to a row-echelon form, highlighted with color.

Now let’s address \(x_2\) and make sure that

• \(x_2\) has the coefficient \(1\) in equation \(Z_2\);

• \(x_2\) is eliminated from \(Z_1\) and \(Z_3\).

We achieve the first goal using step 1: \[ \begin{gathered} Z_2\to(-1)Z_2 \end{gathered} \] After this intermediate step, we have: \[ \begin{gathered} II':\left\{\begin{array}{lcrrcrcr} Z_1 &:& x_1 & -x_2 &-& x_3 &=& 1\\ Z_2 &:& & x_2 &-& 3x_3 &=& -8\\ Z_3 &:& & 2x_2&-& x_3 &=& -1 \end{array}\right. \end{gathered} \] Now, we eliminate \(x_2\) from \(Z_1\) and \(Z_3\). For that we transform: \[ \begin{gathered} \begin{array}{ccl} Z_1&\to& Z_1+Z_2\\ Z_3&\to& Z_3-2Z_2 \end{array} \end{gathered} \] The system of equations now takes on the form: \[ \begin{gathered} III:\left\{\begin{array}{lccccrcr} Z_1 &:& x_1 & & -&4x_3 &=& -7\\ Z_2 &:& \cellcolor{lgray} & x_2 & -&3x_3 &=& -8\\ Z_3 &:& \cellcolor{lgray} & \cellcolor{lgray} & &5x_3 &=& 15 \end{array}\right. \end{gathered} \] After this cycle of elimination, \(x_2\) is also on a row-echelon form: it only appears in equation \(Z_2\) and has a coefficient of 1 there.

Finally, let’s address \(x_3\) and

• ensure that \(x_3\) has the coefficient 1 in equation \(Z_3\),

• eliminate \(x_3\) from equations \(Z_1\) and \(Z_2\).

First, we introduce the intermediate step: \[ \begin{gathered} Z_3\to Z_3/5. \end{gathered} \] This yields: \[ \begin{gathered} III':\left\{\begin{array}{lcccrcr} Z_1 &:& x_1 & & -4x_3 &=& -7\\ Z_2 &:& & x_2 & -3x_3 &=& -8\\ Z_3 &:& & & x_3 &=& 3 \end{array} \right. \end{gathered} \] To conclude, we eliminate \(x_3\) from equations \(Z_1\) and \(Z_2\) by: \[ \begin{gathered} \begin{array}{ccl} Z_1&\to& Z_1+4Z_3\\ Z_2&\to& Z_2+3Z_3 \end{array} \end{gathered} \] After these simplification steps, we get: \[ \begin{gathered} IV:\left\{\begin{array}{lcccccc} Z_1 &:& x_1 & & & = & 5\\ Z_2 &:&\cellcolor{lgray} & x_2 & & = & 1\\ Z_3 &:&\cellcolor{lgray} & \cellcolor{lgray} & x_3 & = & 3 \end{array}\right. \end{gathered} \] IV is, of course, still a linear system of equations, but it has the simplest form imaginable for such a system: the echelon form. From this, we can immediately read off the solutions and form the solution vector: \[ \begin{gathered} x_1=5,\quad x_2=1,\quad x_3=3\implies \mathbf{x}=\left(\begin{array}{c} 5\\1\\3\end{array}\right). \end{gathered} \] The elaborate notation that we used when introducing the elimination process is far too cumbersome. It is much simpler to perform the elimination steps directly in the coefficient matrix.

We begin anew in Phase I and first set up the coefficient matrix: \[ \begin{gathered} I: \left\{\begin{array}{lcrcrcrcr} Z_1 &:& x_1 &-& x_2 &-& x_3 &=& 1\\ Z_2 &:& 2x_1&-& 3x_2 &+& x_3 &=& 10\\ Z_3 &:& x_1 &+& x_2 &-& 2x_3 &=& 0 \end{array}\right. \to \left(\begin{array}{rrr|r} 1 & -1 & -1 & 1\\ 2 & -3 & 1 & 10\\ 1 & 1 & -2 & 0 \end{array} \right) \end{gathered} \] It is important to emphasize that this transformation is not a one-way street. At any stage of the process, we can interpret a row of the coefficient matrix as an equation. For example, the 3rd row: \[ \begin{gathered} (\;1 \quad 1 \quad -2\quad |\;\; 0)\to 1\cdot x_1+1\cdot x_2+(-2)\cdot x_3=0. \end{gathered} \] The first cycle of the elimination process in the coefficient matrix goes like this: \[ \begin{gathered} \left(\begin{array}{rrr|r} 1 & -1 & -1 & 1\\ 2 & -3 & 1 & 10\\ 1 & 1 & -2 & 0 \end{array} \right) \to {\small \left[\begin{array}{ccl} Z_2&\to & Z_2-2Z_1\\ Z_3&\to & Z_3-Z_1 \end{array} \right] } \to \left(\begin{array}{rrr|r} \cellcolor{dgray}{\color{white}\textbf{1}} & -1 & -1 & 1\\ \cellcolor{lgray}0 & -1 & 3 & 8\\ \cellcolor{lgray}0 & 2 & -1 & -1 \end{array} \right) \end{gathered} \] Thus, we have created a first step in our staircase, which is reflected in the coefficient matrix by a column consisting of a 1 with all other components of this column being zeros.

The second cycle: \[ \begin{gathered} \left(\begin{array}{rrr|r} \cellcolor{dgray}{\color{white}\textbf{1}} & -1 & -1 & 1\\ \cellcolor{lgray}0 & -1 & 3 & 8\\ \cellcolor{lgray}0 & 2 & -1 & -1 \end{array} \right)\to {\small \left[\begin{array}{ccl} Z_2&\to & (-1)Z_2\\ Z_1&\to & Z_1+Z_2\\ Z_3&\to & Z_3-2Z_2 \end{array} \right] }\to \left(\begin{array}{rrr|r} \cellcolor{dgray}{\color{white}\textbf{1}} & \cellcolor{lgray}0 & -4 & -7\\ \cellcolor{lgray}0 & \cellcolor{dgray}{\color{white}\textbf{1}} & -3 & -8\\ \cellcolor{lgray}0 & \cellcolor{lgray}0 & 5 & 15 \end{array} \right) \end{gathered} \] A second step has been created, clearly recognizable by the shape of the second column in the coefficient matrix: a 1 followed by only zeros. The third cycle results in: \[ \begin{gathered} \left(\begin{array}{rrr|r} \cellcolor{dgray}{\color{white}\textbf{1}} & \cellcolor{lgray}0 & -4 & -7\\ \cellcolor{lgray}0 & \cellcolor{dgray}{\color{white}\textbf{1}} & -3 & -8\\ \cellcolor{lgray}0 & \cellcolor{lgray}0 & 5 & 15 \end{array} \right)\to {\small \left[\begin{array}{ccl} Z_3&\to & Z_3/5\\ Z_1&\to & Z_1+4Z_3\\ Z_2&\to & Z_2+3Z_3 \end{array} \right] }\to \left(\begin{array}{rrr|r} \cellcolor{dgray}{\color{white}\textbf{1}} & \cellcolor{lgray}0 & \cellcolor{lgray}0 & 5\\ \cellcolor{lgray}0 & \cellcolor{dgray}{\color{white}\textbf{1}} & \cellcolor{lgray}0 & 1\\ \cellcolor{lgray}0 & \cellcolor{lgray}0 & \cellcolor{dgray}{\color{white}\textbf{1}} & 3 \end{array} \right) \end{gathered} \] The matrix that results in the end is called the echelon form of the system of equations. The solution can be directly seen in the right-most column.

The example should not only demonstrate how the simplification steps are applied but also make the strategy of the elimination process clear, namely to produce an echelon form.

Definition 6.8 (Row Echelon Form) By using permitted simplification steps, the system of equations is converted into a row echelon form.

• The first non-zero element of each row is a \(\mathbf{1}\). All other elements in the column of this \(\mathbf{1}\) are zeros. A column of this form is called a pivot position.

• This leading \(\mathbf{1}\) is strictly to the right of the leading \(\mathbf{1}\) in the row above it.

• A row can also consist of all zeros.

The variables of the system of equations that correspond to pivot positions are called basic variables, all the other variables are called non-basic variables.

Example 6.9

(a) This augmented matrix is in row echelon form: \[ \begin{gathered} \left(\begin{array}{ccc|c} 1 & 0 & 1 & 3\\ 0 & 1 & 2 & 4\\ 0 & 0 & 0 & 0 \end{array}\right),\quad\begin{array}{l} \text{$x_1, x_2$ are basic variables}\\ x_3 \text{ is a non-basic variable} \end{array} \end{gathered} \] The third row consists entirely of zeros, but this merely means: \[ \begin{gathered} 0\cdot x_1+0\cdot x_2+0\cdot x_3=0\Leftrightarrow 0=0, \end{gathered} \] a statement that is trivially true. The system of equations was originally overdetermined, with one equation being redundant.

(b) This augmented matrix is not in row echelon form but can be made into one by an additional simplification step: \[ \begin{gathered} \left(\begin{array}{crc|r} 1 & -2 & 1 & -3\\ 0 & 1 & 2 & 4\\ 0 & 0 & 0 & 0 \end{array}\right)\to{\small \left[Z_1\to Z_1+2Z_2\right]\to } \left(\begin{array}{crc|r} 1 & 0 & 5 & 5\\ 0 & 1 & 2 & 4\\ 0 & 0 & 0 & 0 \end{array}\right) \end{gathered} \] Basic variables: \(x_1, x_2\), Non-basic variable: \(x_3\).

(c) This augmented matrix is in row echelon form: \[ \begin{gathered} \left(\begin{array}{ccc|c} 1 & 2 & 0 & 3\\ 0 & 0 & 1 & 4 \end{array}\right) \quad\begin{array}{l} x_1,x_3 \text{ are basic variables}\\ x_2 \text{ is a non-basic variable} \end{array} \end{gathered} \]

(d) This augmented matrix is not in row echelon form, but can be made into one by an additional simplification step. We swap row 1 with row 2: \[ \begin{gathered} \left(\begin{array}{ccc|c} 0 & 0 & 1 & 4\\ 1 & 2 & 0 & 3 \end{array}\right)\to \left[Z_1\leftrightarrow Z_2\right]\to \left(\begin{array}{ccc|c} 1 & 2 & 0 & 3\\ 0 & 0 & 1 & 4 \end{array}\right) \end{gathered} \]

6.2.3 The Case of Inconsistency

It may occur that a system of equations has no solution at all. The system is then called inconsistent.

Typically, it is not apparent at a glance whether a system is solvable or unsolvable. However, once the system has been reduced to a row echelon form, it can be immediately determined if discrepancy exists.

Let’s look at an example. \[ \begin{gathered} \begin{array}{rcrcrcr} x_1 &-&2x_2 &-&9x_3 &=& -2\\ -2 x_1 &+&5x_2 &+&22 x_3&=&1\\ -x_1 & +&2x_2& + &9x_3&=&3 \end{array}\to\left(\begin{array}{rrr|r} 1 & -2 & -9 & -2\\ -2 & 5 & 22 & 1\\ -1 & 2 & 9 & 3 \end{array}\right) \end{gathered} \] Through the simplification steps \[ \begin{gathered} Z_2\to Z_2+2Z_1, \quad Z_3\to Z_3+Z_1 \end{gathered} \] we obtain: \[ \begin{gathered} \left( \begin{array}{rrr|r} 1 & -2 & -9 & -2\\ 0 & 1 & 4 & -3\\ \rowcolor{lgray}0 & 0 & 0 & \cellcolor{dgray}{\color{white}\textbf{1}} \end{array}\right). \end{gathered} \] We could create a second pivot position in the second column, but the third row reveals that this is no longer necessary, because the third row read as an equation implies: \[ \begin{gathered} 0\cdot x_1+0\cdot x_2+0\cdot x_3=1\Leftrightarrow 0=1 \end{gathered} \] This is a contradiction, the third equation is unsatisfiable. In other words: the system has no solution.

Let’s make a note:

Theorem 6.10 (Inconsistency) A linear system of equations is inconsistent if the elimination process yields unsatisfiable equations.

Exercise 6.11 Solve the following linear system of equations: \[ \begin{gathered} \begin{array}{rrrrrrrr} & x_1 & + & x_2 & - & 2x_3 & = & 1\\ - & 6x_1 & - & 4x_2 & + & 18x_3 & = & -5\\ & 3x_1 & + & 2x_2 & - & 9x_3 & = & 3\\ \end{array} \end{gathered} \]

Solution: We set up the equation matrix and begin with the elimination:

\[ \begin{aligned} \left(\begin{array}{rrr|r} 1 & 1 & -2 & 1\\ -6 & -4 & 18 & -5\\ 3 & 2 & -9 & 3 \end{array} \right) \to{\small \left[ \begin{array}{l} Z_2\to Z_2+6Z_1\\ Z_3\to Z_3-3Z_1 \end{array} \right]} &\to \left(\begin{array}{rrr|r} 1 & 1 & -2 & 1\\ 0 & 2 & 6 & 1\\ 0 & -1 & -3 & 0 \end{array} \right)\\[5pt] \to{\small \left[\begin{array}{cl} Z_2&\leftrightarrow Z_3\\ Z_2&\to (-1)Z_2 \end{array}\right]} &\to \left(\begin{array}{rrr|r} 1 & 1 & -2 & 1\\ 0 & \phantom{-}1 & 3 & 0\\ 0 & 2 & 6 & 1 \end{array} \right)\\[5pt] \to{\small \left[\begin{array}{cl} Z_1&\to Z_1-Z_2\\ Z_3&\to Z_3-2Z_2 \end{array}\right]} &\to \left(\begin{array}{rrr|r} 1 & 0 & -5 & 1\\ 0 & \phantom{-}1 & 3 & 0\\ 0 & 0 & 0 & 1 \end{array} \right) \end{aligned} \]

The last row represents the unsatisfiable equation \(0=1\), therefore the system of equations is unsolvable. □

6.2.4 The Case of a Unique Solution

Let’s return to our first example: \[ \begin{gathered} \left(\begin{array}{rrr|r} 1 & -1 & -1 & 1\\ 2 & -3 & 1 & 10\\ 1 & 1 & -2 & 0 \end{array} \right)\quad\to\quad \left(\begin{array}{rrr|r} 1 & 0 & 0 & 5\\ 0 & 1 & 0 & 1\\ 0 & 0 & 1 & 3 \end{array} \right) \end{gathered} \] We see: The system of equations is solvable and in the row-echelon form, each unknown is a basic variable. The values of the basic variables are immediately obtained from the equations of the row-echelon form. Therefore, there is exactly one solution to the system of equations, namely the vector \[ \begin{gathered} \mathbf x=\left(\begin{array}{c}x_1\\x_2\\x_3 \end{array}\right)= \left(\begin{array}{c}5\\1\\3 \end{array}\right) \end{gathered} \] We note:

Theorem 6.12 (Unique Solvability) A linear system of equations is uniquely solvable when:

• the row-echelon form contains no unsatisfiable equations;

• every unknown is a basic variable.

Unique solvability is only possible when the system of equations has at least as many equations as unknowns.

Exercise 6.13 Solve the system of equations \[ \begin{gathered} \begin{array}{rcrcrcr} x_1 &+&2x_2 &+&4x_3&=&0\\ x_1 &+&x_2&+&3x_3&=&0\\ x_1&+&4x_2&+&7x_3&=&-1\\ 2x_1&+&5x_2&+&7x_3&=&2 \end{array} \end{gathered} \]

Solution: We set up the equation matrix and eliminate:

\[ \begin{aligned} \left(\begin{array}{rrr|r} 1 & 2 & 4 & 0\\ 1 & 1 & 3 & 0\\ 1 & 4 & 7 & -1\\ 2 & 5 & 7 & 2 \end{array} \right) & \to {\small \left[\begin{array}{cl} Z_2&\to Z_2-Z_1\\ Z_3&\to Z_3-Z_1\\ Z_4&\to Z_4-2Z_1 \end{array}\right]} \to \left(\begin{array}{rrr|r} 1 & 2 & 4 & 0\\ 0 & -1 & -1 & 0\\ 0 & 2 & 3 & -1\\ 0 & 1 & -1 & 2 \end{array} \right)\\[5pt] &\to{\small \left[ \begin{array}{cl} Z_2&\to(-1) Z_2\\ Z_1&\to Z_1-2Z_2\\ Z_3&\to Z_3-2Z_2\\ Z_4&\to Z_4-Z_2 \end{array}\right]}\to \left(\begin{array}{rrr|r} 1 & 0 & 2 & 0\\ 0 & \phantom{-}1 & 1 & 0\\ 0 & 0 & 1 & -1\\ 0 & 0 & -2 & 2 \end{array}\right)\\[5pt] &\to {\small \left[ \begin{array}{cl} Z_1&\to Z_1-2Z_3\\ Z_2&\to Z_2-Z_3\\ Z_4&\to Z_4+2Z_3 \end{array} \right]}\to \left(\begin{array}{rrr|r} 1 & 0 & 0 & 2\\ 0 & \phantom{-}1 & 0 & 1\\ 0 & 0 & \phantom{-}1 & -1\\ 0 & 0 & 0 & 0 \end{array} \right) \end{aligned} \]

The system of equations is solvable because the row-echelon form contains no unsatisfiable equation. The solution is uniquely determined because every unknown is also a basic variable of the row-echelon form. The solution is \[ \begin{gathered} \mathbf x=\left(\begin{array}{c}x_1\\x_2\\x_3\end{array}\right)= \left(\begin{array}{r}2\\1\\-1\end{array}\right). \end{gathered} \] □

But what if a system of equations is solvable, yet not every unknown can be made into a basic variable?

This situation occurs (provided solvability) certainly when we have more unknowns than equations. But even if the number of unknowns is smaller or equal to the number of equations, this case can occur.

6.2.5 The Case of Infinitely Many Solutions

The structure of solutions in systems of equations becomes really interesting only when they are solvable, but the solution is not uniquely determined. And precisely this happens when non-basic variables appear in the row-echelon form. We agree:

Definition 6.14 (Non-Basis Variable) The system of equations is solvable, but not all variables are basis variables.

The remaining unknowns are non-basis variables and as such freely selectable parameters. Their presence thus causes the equation system to have infinitely many solutions.

Let’s start with a very simple example.

Exercise 6.15 Solve the system of equations: \[ \begin{gathered} \begin{array}{cccrcr} x_1 & &+& 7x_3&=&8\\ &x_2& - &x_3&=&5 \end{array} \end{gathered} \]

Solution: The augmented matrix \[ \begin{gathered} \left(\begin{array}{rrr|r} 1 &0&7 & 8\\ 0 &1&-1& 5 \end{array} \right) \end{gathered} \] is already in echelon form. Basis variables are \(x_1\) and \(x_2\), the unknown \(x_3\) is a non-basis variable. Following Definition 6.14, \(x_3\) is a free parameter. We also express this notationally by setting \[ \begin{gathered} x_3=\alpha,\quad \alpha\in\mathbb R \end{gathered} \] The value \(\alpha\) is completely arbitrary; it can take any value. Now we move the non-basis variable to the right side in the echelon form in each equation. In other words: we express the basis variables as (linear) functions of the non-basis variables: \[ \begin{gathered} \begin{array}{cccrcr} x_1 & &+& 7\alpha&=&8\\ &x_2& - &\alpha&=&5 \end{array}\implies \begin{array}{ccccr} x_1 &=& 8 &-& 7\alpha\\ x_2 &=& 5 &+& \alpha\\ x_3&=& &&\alpha \end{array},\qquad \alpha\in\mathbb R \end{gathered} \tag{6.3}\] This is the parametric form of the general solution. Each choice of \(\alpha\) yields a particular solution to the equation system. E.g., for \(\alpha=0\): \[ \begin{gathered} \begin{array}{ccc} x_1&=&8\\ x_2&=&5\\ x_3&=&0 \end{array}\implies \mathbf x=\left( \begin{array}{c} 8\\ 5\\ 0 \end{array}\right). \end{gathered} \] A further look at (6.3) shows us that the general solution nicely separates into two parts: the particular solution we obtain when we set the non-basis variable \(\alpha=0\), and a solution component whose entries are multiples of \(\alpha\). This gives us the vector form of the general solution: \[ \begin{gathered} \mathbf x=\left( \begin{array}{c} 8\\ 5\\ 0 \end{array}\right) +\alpha\left(\begin{array}{r}-7\\1\\1 \end{array} \right),\quad\alpha\in\mathbb R. \end{gathered} \] Thus, we have written all (infinitely many) solutions of the equation system in a very structured and compact way. □

Exercise 6.16 Solve the system of equations: \[ \begin{gathered} \begin{array}{rcrcrcrcr} x_1 &+& 2x_2 & +& 3x_3 &-& 5x_4 &=& -3\\ -4x_1 &-& 8x_2 & -& 11x_3 &+&17x_4 &=& 7 \end{array} \end{gathered} \]

Solution: We set up the augmented matrix and begin eliminating: \[ \begin{aligned} &\left(\begin{array}{rrrr|r} 1 & 2 & 3 & -5 & -3\\ -4 & -8 & -11 & 17 & 7 \end{array} \right)\to\\[5pt] [Z_2\to Z_2+4Z_1] \to&\left(\begin{array}{rrrr|r} 1 & 2 & 3 & -5 & -3\\ 0 & 0 & 1 & -3 & -5 \end{array}\right)\to\\[5pt] [Z_1\to Z_1-3Z_2] \to&\left(\begin{array}{rrrr|r} 1 & 2 & 0 & 4 & 12\\ 0 & 0 & 1 & -3 & -5 \end{array}\right). \end{aligned} \] There are two basis variables: \(x_1\) and \(x_3\). Thus, \(x_2\) and \(x_4\) are non-basis variables and therefore freely selectable. Hence, we set: \[ \begin{gathered} x_2=\alpha,\quad x_4=\beta,\quad \alpha,\beta\in \mathbb R \end{gathered} \] Now we rewrite the echelon form back into equations and move the non-basis variables to the right side: \[ \begin{gathered} \begin{array}{rcrrcrcr} x_1 & +& 2\alpha & &+&4\beta&=&12\\ & & &x_3&-&3\beta&=&-5 \end{array}\implies \begin{array}{ccrcrcr} x_1 &=& 12&-&2\alpha &-&4\beta\\ x_2 &=& & &\alpha\\ x_3 &=& -5& & &+&3\beta\\ x_4 &=& & & &&\beta \end{array} \end{gathered} \] This yields the vector form of the general solution: \[ \begin{gathered} \mathbf x=\left(\begin{array}{r}12\\0\\-5\\0\end{array}\right) +\alpha\left(\begin{array}{r}-2\\1\\0\\0\end{array}\right)+ \beta\left(\begin{array}{r}-4\\0\\3\\1\end{array}\right). \end{gathered} \]

Exercise 6.17 While solving a system of equations, the following augmented matrix was obtained: \[ \begin{gathered} \left(\begin{array}{rrr|r} 1 & 7 & -10 & 17\\ 0 & 15 & -10 & 28\\ 0 & -45 & \beta & -84 \end{array}\right) \end{gathered} \] Determine the number \(\beta\) such that the system of equations has infinitely many solutions.

Solution: If we calculate \(Z_3\to Z_3+3Z_2\), we get the following augmented matrix: \[ \begin{gathered} \left(\begin{array}{rrr|r} 1 & 7 & -10 & 17\\ 0 & 15 & -10 & 28\\ 0 & 0 & \beta-30 & 0 \end{array}\right) \end{gathered} \] From this we can conclude: if \(\beta\ne 30\), then \(x_3\) can be made into a basic variable (new pivot position) and the system of equations would have a unique solution. If, on the other hand, \(\beta=30\), then a row of zeros is created. The unknown \(x_3\) is a non-basic variable and the system of equations has infinitely many solutions. □

Exercise 6.18 Which of the following statements are correct?

1. A linear system of equations with an all-zero right-hand side is always solvable.

2. A linear system of equations is unsolvable whenever the number of equations is greater than the number of unknowns.

3. Even a system of equations in which all unknowns are basic variables can be unsolvable.

Solution: Statement (1) is correct, since such a system of equations always has the trivial solution \(x_1=x_2=\ldots=x_n=0\).

Statement (2) is incorrect, it is enough to find a counterexample, for instance Exercise 6.13. But be careful: statement (2) is incorrect because of the whenever clause.

Statement (3) is correct. An example is the system of equations in echelon form: \[ \begin{gathered} \left(\begin{array}{cc|c}1 & 0 & 1\\0 & 1 & 2\\0 & 0 & 4\end{array}\right). \end{gathered} \] Here, both unknowns \(x_1\) and \(x_2\) are basic variables, yet the system of equations is unsolvable because the third equation cannot be fulfilled. □

Exercise 6.19 Consider the following augmented matrix: \[ \begin{gathered} \left(\begin{array}{rrrr|r} 1 & -9 & 0 & -3 & -3\\ 0 & 0 & 1 & 6 & 8\\ 0 & 0 & 0 & 0 & \beta \end{array}\right) \end{gathered} \] Which of the following statements are correct?

1. The variable \(x_4\) is free to choose if the system is solvable.

2. The variable \(x_2\) is free to choose if the system is solvable.

3. The system of equations is solvable for any value of \(\beta\).

Solution: The last row of the augmented matrix shows us that the system of equations is only solvable if \(\beta =0\). Therefore, statement (3) is false.

However, if \(\beta=0\) and solvability is guaranteed, then \(x_1\) and \(x_3\) are basic variables, whereas \(x_2\) and \(x_4\) are non-basic variables and thus free to choose. Hence, statements (1) and (2) are correct. □

6.3 Applications of Linear Systems of Equations

6.3.1 Macroeconomics, Finance, and Accounting

We continue Example 6.6, now having econometric estimates of parameters.

Exercise 6.20 A simple macroeconomic model consists of the equations: \[ \begin{aligned} \begin{array}{cclcl} C &=& 500 + 0.8 Y &\qquad &\text{Consumption function} \\[5pt] I &=& 150 + 0.1 Y -80 R&&\text{Investment function}\\[5pt] Y &=& C + I+G&&\text{Equilibrium condition} \end{array} \end{aligned} \]

1. What are the values of \(Y, C\), and \(I\) for an interest rate of \(R=0.05\) and government spending of \(G=5000\)?

2. By how much does the GDP \(Y\) increase if government spending is increased by 1 MU?

Solution:

(a) First, we restate the system of equations so that the endogenous variables are all on the left side, and we insert the given values for the exogenous variables: \[ \begin{gathered} \begin{array}{rcrcrcr} -0.8Y&+&C & & &=&500\\ -0.1Y& & &+&I&=&146 \\ Y &-&C&-&I&=&5000 \end{array}\to \left(\begin{array}{rrr|r} -0.8 & 1 & 0 & 500\\ -0.1 & 0 & 1 & 146\\ 1 & -1 & -1 & 5000 \end{array}\right) \end{gathered} \] After elimination, the row-echelon form is: \[ \begin{gathered} \left(\begin{array}{rrr|r} 1 & 0 & 0 & 56460\\ 0 & 1 & 0 & 45668\\ 0 & 0 & 1 & 5792 \end{array} \right)\implies \begin{array}{ccr} Y&=& 56\,460\\ C&=&45\,668\\ I&=&5\,792 \end{array} \end{gathered} \] (b) If \(G\) is increased to 5001, the same steps of elimination yield: \[ \begin{gathered} \begin{array}{ccr} Y&=& 56\,470\\ C&=& 45\,676\\ I&=& 5\,793 \end{array} \end{gathered} \] An increase in government spending by 1 MU results in an increase in GDP by 10 MU. This is known as the Multiplier Effect. □

We continue Example 6.7.

Exercise 6.21 For three cost centers of a company, the following data are provided: \[ \begin{gathered} \begin{array}{llrr} & \text{Cost Center} &{}{}{\text{Service provided}} & \text{Primary Costs}\\ \hline K_1: & \text{Land/Buildings} & 750 ~m^2 & 29\,388\\ K_2: & \text{Energy} & 1\,450 ~\mathit{kWh} & 3\,450\\ K_3: & \text{Maintenance} & 480~\mathit{h} & 9\,568 \end{array} \end{gathered} \] During the calculation period, the cost centers received services from the other cost centers:

• \(K_1\): 28 kWh from \(K_2\) and 20 h from \(K_3\).

• \(K_2\): 40 \(m^2\) from \(K_1\) and 30 h from \(K_3\).

• \(K_3\): 60 \(m^2\) from \(K_1\) and 8 kWh from \(K_2\).

At what prices should these internally provided services be charged?

Solution: Let \(p_1,p_2\), and \(p_3\) be these prices. From the condition \[ \begin{gathered} \text{Primary Costs}+\text{Received Services}= \text{Provided Services} \end{gathered} \] the following three equations arise: \[ \begin{gathered} \begin{array}{rcrcrcrcr} 29388 &+& & & 28p_2 &+& 20 p_3 &=& 750p_1\\ 3450 &+& 40p_1 & & & +& 30 p_3 &=& 1450p_2\\ 9568 &+& 60p_1 &+ &8p_2 & & &=& 480p_3 \end{array} %\qquad p_1=40, p_2=4, p_3=25 \end{gathered} \] This is a linear system of equations with three equations and three unknowns. We rewrite the system as: \[ \begin{gathered} \begin{array}{rcrcrcr} 750p_1 &-&28p_2 &-&20p_3 &=& 29388\\ -40p_1 &+&1450p_2 &-& 30p_3 &=&3450\\ -60p_1 &-&8p_2&+&480p_3&=&9568 \end{array} \end{gathered} \] By elimination, we obtain the echelon form: \[ \begin{gathered} \left(\begin{array}{rrr|r} 750 & -28 & -20 & 29388\\ -40 & 1450 & -30 & 3450\\ -60 & -8 & 480 & 9568 \end{array}\right)\to\left( \begin{array}{ccc|r} 1 & 0 & 0 & 40\\ 0 & 1 & 0 & 4\\ 0 & 0 & 1 & 25 \end{array}\right) \quad \begin{array}{ccr} p_1&=&40\\ p_2&=&4\\ p_3&=&25 \end{array} \end{gathered} \] □

Exercise 6.22 (Asset Investment) An asset management company offers investors the opportunity to purchase shares in three portfolios with payments of any amount, which are exclusively composed of the three standard securities \(A,B\) and \(C\). In this way, it is possible to invest in the three securities at significantly more favorable conditions than through direct purchase on the stock exchange.

In portfolio \(P_1\), the value proportions of securities \(A,B\) and \(C\) are 40%, 20% and 40%, in \(P_2\) 0%, 30% and 70%, and in \(P_3\) 10%, 60% and 30%. An investor wants to invest 950,000 monetary units (MU) at 24%, 37% and 39% in securities \(A,B\) and \(C\). How much does he have to invest in the three portfolios to achieve the planned distribution of his funds across the three securities?

Solution: We denote by \(x_1,x_2\) and \(x_3\) the shares to be purchased in the portfolios \(P_1, P_2\) and \(P_3\).

24% of 950,000 should be invested in paper \(A\), which amounts to 228,000 currency units (CU). This security is included in \(P_1\) by 40%, in \(P_2\) by 0% and in \(P_3\) by 10%. This results in a first equation: \[ \begin{gathered} \text{Paper A}: \quad 0.4x_1+0.1x_3=228000. \end{gathered} \] Likewise, we obtain two additional equations for the proportions of \(B\) and \(C\): \[ \begin{gathered} \begin{array}{lcccccccrr} \text{B} &\quad & 0.2x_1 & + & 0.3x_2 &+& 0.6x_3 &=& 351500 &(=\text{ 37 \% von 950000})\\ \text{C} &\quad & 0.4x_1 & + & 0.7x_2 &+& 0.3x_3 &=& 370500 &(=\text{ 39 \% von 950000})\\ \end{array} \end{gathered} \] Finally, we have the sum condition: \[ \begin{gathered} x_1+x_2+x_3=950000. \end{gathered} \] The associated augmented matrix has the following echelon form: \[ \begin{gathered} \left(\begin{array}{rrr|r} 0.4 & 0.0 & 0.1 & 228000\\ 0.2 & 0.3 & 0.6 & 351500\\ 0.4 & 0.7 & 0.3 & 370500\\ 1 & 1 & 1 & 950000 \end{array} \right)\to \left(\begin{array}{rrr|r} 1 & 0 & 0 &475000 \\ 0 & 1 & 0 & 95000\\ 0 & 0 & 1 & 380000\\ 0 & 0 & 0 & 0 \end{array} \right) \end{gathered} \] Therefore, the investment sums are: \[ \begin{array}{lr} \text{Portfolio}~ P_1: & 475\,000\\ \text{Portfolio}~ P_2: & 95\,000\\ \text{Portfolio}~ P_3: & 380\,000 \end{array} \]

□

6.3.2 Planning Calculation

Demand Vectors

A manufacturing company produces products \(A, B,\ldots\) from the production factors (raw materials, subproducts, capital, labor, cultivation area, etc.) \(R_1\), \(R_2\),…, \(R_n\).

For one unit of product \(A\), the amount \(a_1\) of the production factor \(R_1\), the amount \(a_2\) of the production factor \(R_2\), etc., are required. The list of the amounts of production factors (Input) required for the production (the Output) of one unit of \(A\) can be written as a vector: \[ \begin{gathered} \begin{array}{l|l} & A \\ \hline R_1 & a_1 \\ R_2 & a_2 \\ \vdots & \vdots \\ R_n & a_n \end{array} \quad\to\quad \begin{array}{c} \\ \mathbf a= \left( \begin{array}{c} a_1\\ a_2\\ \vdots\\ a_n \end{array} \right). \end{array} \end{gathered} \] The vector \(\mathbf a\) is called the demand vector of product \(A\). Similarly, we define demand vectors \(\mathbf b, \mathbf c,\ldots\) for products \(B, C,\ldots\).

Demand vectors are a very important concept for the following application examples. Therefore, we emphasize the definition once more.

Definition 6.23 (Demand Vectors) A single demand vector of a product is identical with the Input needed for the Output of one unit of the product.

In industrial production, demand vectors are also known as parts lists. In applications, these lists often have many thousands of components. For example, a midsize car is made up of more than 30,000 individual parts.

The production (Output) of certain quantities of goods \(A\) and \(B\) requires the use (Input) of certain amounts of production factors. Suppose \(\alpha\) units of good \(A\) and \(\beta\) units of good \(B\) are to be produced. Then \[ \begin{gathered} \mathbf x=\left(\begin{array}{c}\alpha\\\beta\end{array}\right) \end{gathered} \] is the planned Output vector of production. The list of amounts of production factors required for this output is called Input vector. It follows that: \[ \begin{gathered} \text{Planned Output }\mathbf x=\left(\begin{array}{c}\alpha\\\beta\end{array}\right) \implies \text{Required Input }\mathbf y=\alpha\mathbf a +\beta\mathbf b \end{gathered} \tag{6.4}\] Thus, the required Input is a Linear Combination of the demand vectors \(\mathbf a\) and \(\mathbf b\), see Definition 6.5.

Exercise 6.24 A furniture store offers, among other things, two types of DIY bookshelves. Type A has a height of 200 cm, Type B is the smaller version with a height of 110 cm. For Type A, 5 \(m^2\) of veneered boards are used per piece, for Type B, 3 \(m^2\) of boards are needed. The production (cutting of the boards, drilling, and packaging) is done automatically. With Type A, the production takes 8 minutes of machine time, with Type B it takes 6 minutes. Set up the demand vectors for one Type A shelf and for one Type B shelf, and calculate the Input vector for the Output of 50 Type A and 20 Type B shelves.

Solution: The requirement vector for a shelf of Type A reads:

\[ \begin{array}{l|l} & \text{Type A}\\ \hline \text{Boards} & 5 ~m^2\\ \text{Machine time} & 8 ~\text{min} \end{array}\quad\implies \mathbf a=\left(\begin{array}{c}5\\8 \end{array}\right), \]

and for a shelf of Type B:

\[ \begin{array}{l|l} & \text{Type B}\\ \hline \text{Boards} & 3 ~m^2\\ \text{Machine time} & 6 ~\text{min} \end{array}\quad\implies \mathbf b=\left(\begin{array}{c}3\\6 \end{array}\right). \]

For 50 shelves of Type A and 20 shelves of Type B, the input vector is therefore: \[ \begin{gathered} 50\mathbf a+20\mathbf b= 50\left(\begin{array}{c}5\\8 \end{array}\right)+ 20\left(\begin{array}{c}3\\6 \end{array}\right)= \left(\begin{array}{c}310\\520 \end{array}\right). \end{gathered} \] □

Requirements equations

We explain the concepts using a typical application example.

Example 6.25 (Demand planning)

The raw material requirements for three products \(A_1, A_2, A_3\) are given by the requirement vectors: \[ \begin{gathered} \mathbf a_1=\left(\begin{array}{r} 3\\3\\5 \end{array}\right),\; \mathbf a_2=\left(\begin{array}{r} 0\\2\\5 \end{array}\right),\; \mathbf a_3=\left(\begin{array}{r} 1\\3\\1 \end{array}\right) \end{gathered} \] In total, 70 units of the raw material \(R_1\), 100 units of the raw material \(R_2\), and 135 units of \(R_3\) are available. Is it possible to produce such quantities of \(A_1, A_2\) and \(A_3\) that all raw material quantities are completely consumed?

If \(\mathbf b\) denotes the vector of raw material capacities, i.e., \[ \begin{gathered} \mathbf b=\left(\begin{array}{r} 70\\100\\135 \end{array}\right), \end{gathered} \] and \(x_1,\,x_2,\,x_3\) represent the quantities of products being produced \(A_1,\,A_2,\,A_3\), then the question is: Is there a linear combination of the requirement vectors that generates the capacity vector, i.e., \[ \begin{gathered} x_1\mathbf a_1+x_2\mathbf a_2+x_3\mathbf a_3=\mathbf b~? \end{gathered} \tag{6.5}\] For the solution to be economically viable, it must also be required that \(x_1 \ge0,\; x_2 \ge0,\; x_3\ge 0\). However, for simplicity, we will not consider this condition here.

When writing equation (6.5) not in vector form, but in component notation, it reads \[ \begin{gathered} x_1\left(\begin{array}{r} 3\\3\\5 \end{array}\right)+ x_2\left(\begin{array}{r} 0\\2\\5 \end{array}\right)+ x_3\left(\begin{array}{r} 1\\3\\1 \end{array}\right)= \left(\begin{array}{r} 70\\100\\135 \end{array}\right), \end{gathered} \] and if you write out each component separately, you get a linear system of equations: \[ \begin{gathered} \begin{array}{ccccccr} 3x_1&&&+&x_3&=&70\\ 3x_1&+&2x_2&+&3x_3&=&100\\ 5x_1&+&5x_2&+&x_3&=&135 \end{array} \end{gathered} \] With the elimination method, we find for this planning problem the unique solution, the so-called production possibilities: \[ \begin{gathered} \mathbf x=\left(\begin{array}{r}20\\5\\10 \end{array}\right). \end{gathered} \] Indeed, it is even an economically viable solution, as it meets the non-negativity condition \[ \begin{gathered} x_1\ge 0,\; x_2\ge 0,\;x_3\ge 0. \end{gathered} \]

Exercise 6.26 Two raw materials, \(A_1\) and \(A_2\), are used to produce three products \(E_1, E_2\), and \(E_3\). The demand for \(A_1\) and \(A_2\) per unit of the final products and the available inventory levels of \(A_1\) and \(A_2\) can be taken from the following table:

\[ \begin{array}{|c|rrr|r|} \hline & E_1 & E_2 & E_3 & \text{Stock}\\ \hline A_1 & 7 & 30 & 13 & 5865\\ A_2 & 18 & 6 & 10 & 4624\\ \hline \end{array} \]

For technical reasons, the quantities produced must be in the ratio 10 : 7 : 5. What quantities of \(E_1, E_2\), and \(E_3\) can be manufactured if the inventory levels of \(A_1\) and \(A_2\) are completely used up?

Solution: We denote by \(x_1,x_2,x_3\) the desired production quantities of the final products \(E_1,E_2,E_3\). Since the inventory of initial products is to be completely used up, we obtain the demand equations \[ \begin{gathered} \begin{array}{rcrcrcr} 7x_1 & + & 30 x_2 & + & 13x_3 & = & 5865\\ 18x_1 & + & 6x_2 & + & 10x_3 & = & 4624 \end{array} \end{gathered} \] The production quantities should be in the ratio \(10:7:5\). This means \[ \begin{gathered} x_1:x_2:x_3=10:7:5 \;\implies\; x_1:x_2=10:7 \;\text{and}\; x_2:x_3=7:5 \end{gathered} \] From this we obtain the equations \[ \begin{gathered} \begin{array}{lclclclclcl} x_1:x_2 & = & 10:7 & \implies & 7x_1 & = & 10x_2 & \implies & 7x_1-10x_2 & = & 0 \\ x_2:x_3 & = & 7:5 & \implies & 5x_2 & = & 7x_3 & \implies & 5x_2-7x_3 & = & 0 \end{array} \end{gathered} \] We are therefore dealing with 4 equations in 3 unknowns.

We now apply the elimination method to the equation matrix: \[ \begin{gathered} \left(\begin{array}{rrr|r} 7 & 30 & 13 & 5865\\ 18 & 6 & 10 & 4624\\ 7 & -10 & 0 & 0\\ 0 & 5 & -7 & 0 \end{array} \right) \to \text{Elimination}\to \left(\begin{array}{rrr|r} 1 & 0 & 0 & 170\\ 0 & 1 & 0 & 119\\ 0 & 0 & 1 & 85\\ 0 & 0 & 0 & 0 \end{array} \right) \end{gathered} \] Obviously, the system of equations has the unique solution: \[ \begin{gathered} \mathbf x=\left(\begin{array}{r}170\\119\\85 \end{array}\right). \end{gathered} \] □

Exercise 6.27 In the production of the two products \(E_1\) and \(E_2\), raw material \(A\) (ME) and machine time \(M\) (h) are used. There is a stock of 8 ME of \(A\) in inventory, and machine time is available for a maximum of 25 hours. \(E_1\) requires 1 ME of \(A\) and 3 hours of machine time per unit, while \(E_2\) requires 2 ME of \(A\) and 5 hours of machine time. The machine time capacity does not have to be fully utilized, but the entire inventory of \(A\) should be used.

1. How much machine time is left over at the minimum, maximum?

2. What is the maximum amount (sum of the quantities \(E_1\) and \(E_2\)) that can be produced?

Solution: (a) Let \(x_1\ge 0\) and \(x_2\ge 0\) be the quantities to be produced by \(E_1\) and \(E_2\), respectively. Consumption of raw material \(A\) leads to a first equation: \[ \begin{gathered} \text{Consumption A}:\quad x_1+2x_2=8,\quad x_1,x_2\ge 0.\qquad \mbox{(A)} \end{gathered} \] Regarding the consumption of machine time, we have not an equation but an inequality: \[ \begin{gathered} \text{Machine time}:\quad 3x_1+5x_2\le 25. \end{gathered} \] The discrepancy between the left and right side of this inequality is the extent of unused machine time. Let’s call this quantity \(y\). Then the inequality can be written as an equation: \[ \begin{gathered} 3x_1+5x_2+y=25,\qquad y\ge 0.\qquad \mbox{(B)} \end{gathered} \] Thus, (A) and (B) form a linear system of equations with two equations and three unknowns: \[ \begin{gathered} \begin{array}{rcrcrcr} x_1 &+& 2x_2 & & &= &8\\ 3x_1 &+& 5x_1 &+& y &=& 25 \end{array} \end{gathered} \] We bring the equation matrix into stair-step form: \[ \begin{gathered} \left(\begin{array}{rrr|r} 1 & 2 & 0 & 8\\ 3 & 5 & 1 & 25 \end{array} \right)\to\left(\begin{array}{rrr|r} 1 & 0 & 2 & 10\\ 0 & 1 & -1 & -1 \end{array}\right), \end{gathered} \] and recognize that the system of equations is solvable but not uniquely solvable, because \(y\) is a non-basic variable. So we set \(y=\beta\) and formulate the parametric representation of the solution set: \[ \begin{gathered} \begin{array}{ccl} x_1 &=& 10-2\beta\\ x_2 &=& -1+\beta\\ y&=&\beta \end{array} \end{gathered} \tag{6.6}\] Now, \(x_1, x_2\) and \(\beta\ge 0\) must all be fulfilled. From the requirement \(x_2\ge 0\), it follows from the second equation of the parametric representation: \[ \begin{gathered} -1+\beta\ge 0\implies \beta\ge 1. \end{gathered} \] From \(x_1\ge 0\), we get: \[ \begin{gathered} 10-2\beta\ge 0\implies \beta \le 5. \end{gathered} \] From the requirements \(\beta\ge 0, \beta\ge 1\), and \(\beta\le 5\), which all must be satisfied simultaneously, we get the permissible range of \(\beta\): \[ \begin{gathered} 1\le \beta\le 5. \end{gathered} \] Therefore, at least one hour and at most 5 hours of machine time remain unused. If the process is run with the minimal time reserve \(\beta=1\), then \(x_1=8\) and \(x_2=0\) units are produced.

Conversely, if we produce in a way that maximizes the amount of machine time left over (potentially usable for other processes), then \(\beta=5\) and \(x_1=0\) and \(x_2=4\) units are produced.

(b) The sum \(x_1+x_2\) is to be maximized. From (6.6), it follows: \[ \begin{gathered} x_1+x_2=9-\beta\to\max \end{gathered} \] This is achieved at the smallest possible permissible value of \(\beta\), which is \(\beta=1\), so that \(x_1=8, x_2=0\) and \(x_1+x_2=8\). □

6.3.3 Further Applications

Exercise 6.28 (Credit Allocation) A bank is planning a credit campaign totaling 25 million GE (currency units). The following conditions apply:

\[ \begin{array}{lcc} \text{Type of credit} & \text{Interest rate} & \text{Risk}\\ \hline \text{Private} & 0.14 & 0.12\\ \text{Auto} & 0.14 & 0.10\\ \text{Housing} & 0.06 & 0.02\\ \hline \end{array} \]

Furthermore, the volume of private loans should be exactly twice that of loans for car purchases. If the bank calculates a total credit risk of 5%, how should the allocated funds be divided among the three types of credit? What annual interest income can be expected from this distribution?

Solution: We denote by \(x_1, x_2, x_3\) the averages for personal loans, auto loans, and construction loans. Then we set up the equations given by the loan conditions.

The first equation concerns the total volume: \[ \begin{gathered} x_1 + x_2 + x_3 = 25. \end{gathered} \] The volume for personal loans is supposed to be twice as high as for auto loans, thus: \[ \begin{gathered} x_1 = 2x_2 \quad\implies x_1 - 2x_2 = 0. \end{gathered} \] The third equation is about the credit risk. The sum of the risk amounts (i.e., the amount by which the balance sheet must be adjusted) should be 5 percent of the total volume: \[ \begin{gathered} 0.12x_1 + 0.1x_2 + 0.02x_3 = 0.05(x_1 + x_2 + x_3),\\ \implies \quad 0.07x_1 + 0.05x_2 - 0.03x_3 = 0. \end{gathered} \] In this way, a linear system of equations with 3 equations and 3 unknowns is created: \[ \begin{gathered} \begin{array}{rcrcrcr} x_1 & + & x_2 & + & x_3 & = & 25\\ x_1 & - & 2x_2 & & &=& 0\\ 0.07x_1 & + & 0.05x_2 & - & 0.03x_3 &=& 0 \end{array} \end{gathered} \] By the elimination method, we bring the system of equations to row echelon form: \[ \begin{gathered} \left(\begin{array}{rrr|r} 1 & 0 & 0 & 5.357\\ 0 & 1 & 0 & 2.679\\ 0 & 0 & 1 & 16.964 \end{array}\right) \end{gathered} \] The unique solution is thus \(x_1 = 5.357\text{ million}, x_2 = 2.679\text{ million}, x_3 = 16.964\text{ million}\). This results in the expected annual interest income: \[ \begin{gathered} E = 0.14 \cdot 5.357 + 0.14 \cdot 2.679 + 0.06 \cdot 16.964 = 2.143\text{ million}. \end{gathered} \] □

Exercise 6.29 (Polynomial Curve Fitting) A quadratic cost function passes through the points \(P_0=(1,132)\), \(P_1=(2,168)\) and \(P_3=(3,208)\). Determine the equation of the cost function.

Solution: Since the cost function is quadratic, it must have the form: \[ \begin{gathered} C(x) = a_0 + a_1x + a_2x^2, \end{gathered} \] where \(a_0, a_1,\) and \(a_2\) are unknowns to be determined.

\(C(x)\) passes through the point \(P_0=(1,132)\), therefore: \[ \begin{gathered} 132 = a_0 + a_1 + a_2. \qquad \mbox{(A)} \end{gathered} \] It also runs through the point \(P_1=(2,168)\): \[ \begin{gathered} 168 = a_0 + 2a_1 + 4a_2. \qquad \mbox{(B)} \end{gathered} \] Finally, the point \(P_3=(3,208)\) also lies on \(C(x)\): \[ \begin{gathered} 208 = a_0 + 3a_1 + 9a_2. \qquad \mbox{(C)} \end{gathered} \] Equations (A), (B), and (C) form a linear system of equations with the augmented matrix and its echelon form: \[ \begin{gathered} \left(\begin{array}{ccc|r} 1 & 1 & 1 & 132\\ 1 & 2 & 4 & 168\\ 1 & 3 & 9 & 208 \end{array} \right) \to \left(\begin{array}{ccc|r} 1 & 0 & 0 & 100\\ 0 & 1 & 0 & 30\\ 0 & 0 & 1 & 2 \end{array} \right) \end{gathered} \] The equation of the cost function is therefore: \[ \begin{gathered} C(x) = 100 + 30x + 2x^2. \end{gathered} \] □

Remark 6.30 If we had a fourth point \(P_3\) given through which the cost function \(C(x)\) must pass, where \(C(x)\) is still a quadratic polynomial, then \(P_3\) may lie on \(C(x)\) but does not have to. In this case, our system of equations would have four equations. In the first case, it would be uniquely solvable; in the second case, the system of equations would be unsolvable. This is the case of practical interest. To determine a polynomial of degree \(n\), we need \(n+1\) points. However, if more than \(n+1\) points are given for a polynomial of degree \(n\), then the resulting system of equations is typically unsolvable with empirical data. In this case, one aims to find a good approximation solution. This leads to an entire class of interesting optimization problems.

6.4 Additional Exercises

1. Solve the following system of linear equations: \[ \begin{gathered} \begin{array}{rcrcr} 2x_1 & - & x_2 & =& 9\\ x_1 & + & 3x_2 & =& -13\\ 3x_1 & + & x_2 & =& 1\\ 4x_1 & + & 5x_2 & =& -17\\ 5x_1 & + & 8x_2 & =& -30 \end{array} \end{gathered} \]

   Solution: \(x_1=2, x_2=-5\)

2. Solve the following system of linear equations: \[ \begin{gathered} \begin{array}{rrrrrrrr} & 2x_1 & + & 3x_2 & + & 14x_3 & = & 89\\ & 3x_1 & + & x_2 & + & 9x_3 & = & 74\\ & x_1 & & & + & 2x_3 & = & 20\\ \end{array} \end{gathered} \]

   Solution: \(x_1=6, \;x_2=-7,\;x_3=7\)

3. Solve the following system of linear equations: \[ \begin{gathered} \begin{array}{rrrrrrrr} - & x_1 & + & x_2 & + & 7x_3 & = & 29\\ & x_1& - & x_2 & - & 7x_3 & = & -29\\ - & 6x_1 & + & 7x_2 & + & 45x_3 & = & 191\\ \end{array} \end{gathered} \]

   Solution: \[ \begin{gathered} \mathbf x=\left(\begin{array}{r} -12\\ 17\\ 0\\ \end{array}\right)+\alpha\left(\begin{array}{r} 4\\ -3\\ 1\\ \end{array}\right),\qquad \alpha\in\mathbb R \end{gathered} \]

4. Solve the following system of linear equations: \[ \begin{gathered} \begin{array}{rrrrrrrr} - & x_1 & - & 7x_2 & - & 11x_3 & = & 0\\ - & x_1 & - & 12x_2 & - & 21x_3 & = & 0\\ & x_1 & + & 13x_2 & + & 23x_3 & = & 0\\ \end{array} \end{gathered} \]

   Solution: \[ \begin{gathered} \mathbf x=\alpha\left(\begin{array}{r} 3\\ -2\\ 1\\ \end{array}\right),\quad \alpha\in\mathbb R \end{gathered} \]

5. Solve the following system of linear equations: \[ \begin{gathered} \begin{array}{rrrrrrrr} & x_1& - & x_2 & - & 6x_3 & = & 0\\ & 2x_1 & - & 2x_2 & - & 12x_3 & = & 1\\ - & 17x_1 & + & 18x_2 & + & 106x_3 & = & -7\\ \end{array} \end{gathered} \]

   Solution: unsolvable

6. Solve the following system of linear equations: \[ \begin{gathered} \begin{array}{rrrrrrrr} & 3x_1 & + & 2x_2 & - & 24x_3 & = & -25\\ - & x_1& - & x_2 & + & 11x_3 & = & 11\\ \end{array} \end{gathered} \]

   Solution: \[ \begin{gathered} \mathbf x=\left(\begin{array}{r} -3\\ -8\\ 0\\ \end{array}\right)+\alpha\left(\begin{array}{r} 2\\ 9\\ 1\\ \end{array}\right),\quad \alpha\in\mathbb R \end{gathered} \]

7. Solve the system of equations \[ \begin{gathered} \begin{array}{rrrrrrrr} & x_1 & + & 3x_2 & + & 3x_3 & = & 36\\ - & 2x_1 & - & 3x_2 & + & 4x_3 & = & 3\\ & 4x_1 & - & 5x_2 & - & 4x_3 & = & -37\\ & 2x_1 & + & x_2 & & & = & 11\\ \end{array} \end{gathered} \]

   Solution: \(x_1=3,\;x_2=5,\;x_3=6\)

8. While solving a system of linear equations, the following augmented matrix was obtained: \[ \begin{gathered} \left(\begin{array}{rrr|r} 1 & 7 & 3 & -16\\ 0 & -32 & \beta & -4\\ 0 & 8 & -2 & 1 \end{array}\right) \end{gathered} \] Determine the number \(\beta\) such that the system of equations has infinitely many solutions.

   Solution: \(\beta=8\)

9. Given is the following augmented matrix: \[ \begin{gathered} \left(\begin{array}{rrr|r} 1 & 4 & 0 & -1\\ 0 & 1 & 0 & 5\\ 0 & 0 & 1 & -10\\ 0 & 0 & 1 & \beta \end{array}\right) \end{gathered} \] Which of the following statements are true?

   1. If the system of equations is solvable, it even has a unique solution.

   2. The variable \(x_3\) can be freely chosen if the system is solvable.

   3. The system of equations is only solvable if \(\beta=-10\).

   Solution: (1) and (3)

10. Which of the following statements are true?

    1. A system of linear equations has infinitely many solutions if the echelon form contains no contradictory equations and the number of unknowns is greater than the number of basic variables.

    2. A system of linear equations is uniquely solvable if the number of equations is equal to the number of unknowns.

    3. A system of linear equations always has infinitely many solutions if the number of equations is greater than the number of unknowns.

    Solution: Only (1).

11. The coefficient matrix of a linear system of equations has been reduced to the following echelon form: \[ \begin{gathered} \left(\begin{array}{rrr|r} 1 & -10 & 0 & 10\\ 0 & 0 & 1 & 19 \end{array}\right) \end{gathered} \] Determine the complete set of solutions for the system of equations.

    Solution: \[ \begin{gathered} \mathbf x=\left(\begin{array}{r} 10\\ 0\\ 19\\ \end{array}\right)+\alpha\left(\begin{array}{r} 10\\ 1\\ 0\\ \end{array}\right),\quad \alpha\in\mathbb R \end{gathered} \]

12. The coefficient matrix of a linear system of equations has been reduced to the following echelon form: \[ \begin{gathered} \left(\begin{array}{rrrr|r} 1 & 0 & 9 & -10 & 19\\ 0 & 1 & -6 & -7 & -1\\ 0 & 0 & 0 & 0 & 0 \end{array}\right) \end{gathered} \] Determine the complete set of solutions for the system of equations.

    Solution: \[ \begin{gathered} \mathbf x=\left(\begin{array}{r} 19\\ -1\\ 0\\ 0\\ \end{array}\right)+\alpha\left(\begin{array}{r} -9\\ 6\\ 1\\ 0\\ \end{array}\right)+\beta\left(\begin{array}{r} 10\\ 7\\ 0\\ 1\\ \end{array}\right),\qquad \alpha,\beta\in\mathbb R \end{gathered} \]

13. At the end of the years 2010, 2011, and 2012, an employee received payments as a token of appreciation, amounting to a total of 160,000 GE. The employee invested the money at an interest rate of 4.5 percent and had a total of 167,791.75 GE by the end of 2012. If she had received 9 percent interest, it would have been 175,867 GE. What amounts had she received?

    Solution: \(70,000\), \(30,000\), and \(60,000\) GE

14. An investment company offers investors the opportunity to purchase shares in three portfolios consisting exclusively of the three standard values \(A,B\) and \(C\). In portfolio \(P_1\), the value share of papers \(A,B\) and \(C\) is 40%, 10%, and 50%, in \(P_2\) it is 60%, 20%, and 20%, and in \(P_3\) it is 0%, 40%, and 60%. An investor wants to invest 700,000 GE at 26%, 28%, and 46% in the values \(A,B\), and \(C\). How much must be invested in \(P_{1}\), \(P_2\), and \(P_3\) to achieve this goal?

    Solution: \(P_1=140,000, P_2=210,000, P_3=350,000\) GE

15. A bank is planning a credit campaign amounting to 38 million GE. The following conditions apply:

    \[ \begin{array}{lcc} \text{Type of loan} & \text{Interest rate} & \text{Risk}\\ \hline \text{Private} & 0.15 & 0.06\\ \text{Auto} & 0.13 & 0.09\\ \text{Housing} & 0.08 & 0.04\\ \hline \end{array} \]

    Furthermore, the volume of private loans must exactly double the volume of auto loans. If the bank calculates a total credit risk of 6.8%, how should the funds be allocated to the three types of loans? What is the expected interest income (million GE) with this allocation?

    Solution: Income = \(5.2862\) million GE.

16. Chemical analyses of soil samples from a gardening business have determined that for optimal fertilization, the fertilizer should consist of 50% potassium (Kali), 23% nitrate, and 27% phosphate. For cost reasons, the company wants to use commercially available fertilizer mixtures. Three products are considered: fertilizer type \(A_1\) contains 30% potassium, 10% nitrate, and 60% phosphate; type \(A_2\) has a percentage composition of 70%, 20%, and 10%; and type \(A_3\) contains 30% potassium, 50% nitrate, and 20% phosphate. The nursery needs 800 kg of their special mixture. Calculate how much of the fertilizer types \(A_1, A_2\), and \(A_3\) must be purchased for the mixture to have the optimal composition.

    Solution: \(A_1=240\) kg, \(A_2=400\) kg, \(A_3=160\) kg

17. From the two initial products \(A_1\) and \(A_2\), the three final products \(E_1, E_2\), and \(E_3\) are manufactured. The requirements of \(A_1\) and \(A_2\) per unit of the final products and the available stock levels of \(A_1\) and \(A_2\) can be found in the following table:

    \[ \begin{array}{|c|rrr|r|} \hline & E_1 & E_2 & E_3 & \text{Stock}\\ \hline A_1 & 9 & 19 & 28 & 7480\\ A_2 & 8 & 19 & 17 & 5729\\ \hline \end{array} \]

    For technical reasons, the quantities produced must be in the ratio 4:8:9. What quantities can be produced if the stock levels of \(A_1\) and \(A_2\) are completely used up?

    Solution: \(E_1=68, E_2=136, E_3=153\)

18. A company manufactures the end products \(E_1,E_2\), and \(E_3\) from the three initial products \(A_1,A_2\), and \(A_3\). The requirements for initial products per unit of a finished end product and the stock level of \(A_1,A_2\), and \(A_3\) can be found in the following table:

    \[ \begin{array}{|c|rrr|r|} \hline & E_1 & E_2 & E_3 & \text{Inventory}\\ \hline A_1 & 13 & 4 & 6 & 470\\ A_2 & 14 & 6 & 19 & 661\\ A_3 & 1 & 1 & 12 & 170\\ \hline \end{array} \]

    What quantities can be produced if the inventory is completely used up?

    Solution: \(E_1=28, E_2=10, E_3=11\)

19. A company produces the final products \(E_1, E_2\) and \(E_3\) from two initial products \(A_1\) and \(A_2\). The demand for initial products per unit of a finished end product as well as the inventory of \(A_1\) and \(A_2\) can be seen in the following table:

    \[ \begin{array}{|c|rrr|r|} \hline & E_1 & E_2 & E_3 & \text{Inventory}\\ \hline A_1 & 16 & 10 & 16 & 19906\\ A_2 & 15 & 11 & 19 & 18928\\ \hline \end{array} \]

    Due to technical reasons, 22 units of \(E_1\) have to be produced for each unit of \(E_2\). What quantities can be produced if the inventory is completely used up?

    Solution: \(E_1=1166, E_2=53, E_3=45\)

20. In a factory, there are three machines \(M_1, M_2\) and \(M_3\) in use, which are used to produce two products \(P_1\) and \(P_3\). The production coefficients of these machines, i.e. the number of units they can produce per minute, can be found in the following table:

    \[ \begin{array}{|c|rrr|} \hline & M_1 & M_2 & M_3\\ \hline P_1 & 15 & 5 & 12\\ P_2 & 11 & 8 & 11\\ \hline \end{array} \]

    Due to technical reasons, \(M_1\) can only run for half as long as \(M_3\). If 3854 units of \(P_1\) and 3932 units of \(P_2\) have to be produced, what machine times need to be scheduled?

    Solution: \(M_1=76, M_2=178, M_3=152\)

21. A quadratic cost function goes through the points \((1,1620)\), \((4,486)\), and \((10,8100)\). Determine the function term of the cost function.

    Solution: \(C(x)= 2730-1293x+ 183x^2\).

22. For two cost centers \(K_1\) and \(K_2\) of a company, the internally provided services are to be evaluated. The following information is available from the operating accounting sheet:

    \[ \begin{array}{c|cc|rr} \text{Services} & \text{Cost Center} & & \text{Total Performance} & \text{Primary}\\ \text{from/to} & K_{1} & K_{2} & \text{Total} & \text{Costs}\\ \hline K_{1} & - & 70 & 140 & 560\\ K_{2} & 70 & - & 80 & 710\\ \hline \end{array} \]

    The performances are valued in performance units, the primary costs in currency units. Calculate the internal transfer prices.

    Solution: \(p_1=15, p_2=22\)

23. A simple macroeconomic model consists of the equations: \[ \begin{aligned} \begin{array}{cclcl} C &=& 120000 + 0.6 Y &\qquad &\text{Consumption function} \\[5pt] I &=& 400 + 0.12 Y -480 R&&\text{Investment function}\\[5pt] Y &=& C + I+G&&\text{Equilibrium condition} \end{array} \end{aligned} \] What are the values of \(Y, C\), and \(I\) at an interest rate \(R=0.07\) and government spending \(G=42,000\)?

    Solution: \(Y= 579,880, C=467,928, I= 69,952\)