Question

You are given the following points in the plane:

$\mathbf{(}\mathbf{1}\mathbf{,}\mathbf{3}\mathbf{)}\mathbf{,}\mathbf{(}\mathbf{2}\mathbf{,}\mathbf{5}\mathbf{)}\mathbf{,}\mathbf{(}\mathbf{3}\mathbf{,}\mathbf{7}\mathbf{)}\mathbf{,}\mathbf{(}\mathbf{5}\mathbf{,}\mathbf{11}\mathbf{)}\mathbf{,}\mathbf{(}\mathbf{7}\mathbf{,}\mathbf{14}\mathbf{)}\mathbf{,}\mathbf{(}\mathbf{8}\mathbf{,}\mathbf{15}\mathbf{)}\mathbf{,}\mathbf{(}\mathbf{10}\mathbf{,}\mathbf{19}\mathbf{)}$

.You want to find a line$\mathbf{ax}\mathbf{+}\mathbf{by}\mathbf{=}\mathbf{c}$ that approximately passes through these points (no line is a perfect fit). Write a linear program (you don’t need to solve it) to find the line that minimizes the maximum absolute error,$\underset{\mathbf{1}\mathbf{\le }\mathbf{i}\mathbf{\le }\mathbf{7}}{\mathbf{max}}\mathbf{|}{\mathbf{ax}}_{\mathbf{i}}\mathbf{+}{\mathbf{by}}_{\mathbf{i}}\mathbf{-}\mathbf{c}\mathbf{|}$

Short answer

Linear Program:

$\begin{array}{l}\mathrm{k}\ge {\mathrm{ax}}_{\mathrm{i}}+{\mathrm{by}}_{\mathrm{i}}-\mathrm{c}\\ \mathrm{k}\ge -{\mathrm{ax}}_{\mathrm{i}}-{\mathrm{by}}_{\mathrm{i}}+\mathrm{c}\\ \mathrm{k}\ge 0\end{array}$

Step-by-step solution

Step 1:Explain Linear program

Linear program is used for optimization tasks that has constraints and the optimization criterion as linear functions. A linear program has the set of variables that needs to be assign with the real values to satisfy the linear inequalities and to minimize or maximize a given linear objective function.

Step 2:Give the linear program that maximum absolute error.

Let us assume a variable$\mathrm{z}$as the maximum absolute error such that:

$\mathrm{k}=\underset{1\le \mathrm{i}\le 7}{\max }|{\mathrm{ax}}_{\mathrm{i}}+{\mathrm{by}}_{\mathrm{i}}-\mathrm{c}|$

To minimize the maximum absolute error $\left(\mathrm{k}\right)$, so we consider,

$\mathrm{k}\ge \underset{1\le \mathrm{i}\le 7}{\max }|{\mathrm{ax}}_{\mathrm{i}}+{\mathrm{by}}_{\mathrm{i}}-\mathrm{c}|$ for $0<i\le 7$

To get absolute value we will remove modulus sign and split expression into two such that:

$k\ge a{x}_i+b{y}_i-c$ and $k\ge -a{x}_i-b{y}_i+c$

Since variable$k$is greater than some absolute value, add a constrain $k\ge 0$

Thus, the linear program is as follows,

Maximize: $-z$or Minimize:$z$

$\begin{array}{l}\mathrm{k}\ge {\mathrm{ax}}_{\mathrm{i}}+{\mathrm{by}}_{\mathrm{i}}-\mathrm{c}\\ \mathrm{k}\ge -{\mathrm{ax}}_{\mathrm{i}}-{\mathrm{by}}_{\mathrm{i}}+\mathrm{c}\\ \mathrm{k}\ge 0\end{array}$

Therefore, the linear program that finds the maximum absolute error has been obtained.