## 6 Reduction to the Parametric Assignment Problem  
In this section, we reduce the fractional assignment problem **FAP** with the objective function \(P\) defined above to a parametric assignment problem. Let us introduce a parameter \(\lambda\) that, for each assignment \(A\) from the set \(\mathbf{C}\) of all assignments, satisfies the following inequality:  
\[\sum_{(i,j)\in A}e_{ij}/\sum_{(i,j)\in A}k_{ij}\leq\lambda,\text{for all }A\in\mathbf{C}. \tag{6}\]Since the sum \(\sum_{(i,j)\in A}\,k_{ij}\) is positive in any assignment \(A\), inequalities (6) can be rewritten as follows:  
\[\sum_{(i,j)\in A}\,e_{ij}\leq\lambda\,\sum_{(i,j)\in A}\,k_{ij}\]  
or  
\[0\leq\lambda\,\sum_{(i,j)\in A}\,k_{ij}-\sum_{(i,j)\in A}\,e_{ij}\]  
and, finally,  
\[0\leq\sum_{(i,j)\in A}\,(\lambda\,k_{ij}-e_{ij})\text{ for all }A\in\mathbb{C}. \tag{7}\]  
Thus, problem **FAP** of finding the maximum average profit \(P^{*}\) presented in the previous section takes the following form:  
To find the minimum \(\lambda\) that satisfies (6), or, equivalently, to find the minimum \(\lambda\) that satisfies (7). Consider the matrix \(\mathbf{W}(\lambda)=\lambda\cdot\mathbf{K}-\mathbf{E}\) with entries \(w_{ij}=(\lambda\cdot k_{ij}-e_{ij})\), called _arc costs_, or simply _costs_. Consider some fixed value of \(\lambda\). Let \(A^{*}(\lambda)\) denote the assignment with the minimum cost across all the assignments \(A\in\mathbb{C}\), defined as follows:  
\[\sum_{(i,j)\in A^{*}(\lambda)}\,(\lambda\cdot k_{ij}-e_{ij})=\min_{A\in \mathbb{C}}\sum_{(i,j)\in A}\,(\lambda\cdot k_{ij}-e_{ij}), \tag{8}\]  
and denote the latter function, called the _minimum-cost function_, by \(L(\lambda)\):  
\[L(\lambda)=\sum_{(i,j)\in A^{*}(\lambda)}\,(\lambda\cdot k_{ij}-e_{ij}). \tag{9}\]  
Proposition 4 below states that the assignment problem of finding the maximum average fleet profit \(P^{*}\), defined in problem **FAP**, can be reduced to the following parametric minimum-cost assignment problem **PAP**:  
**Problem 6 (PAP). **_Find the value of the parameter \(\lambda=\lambda^{*}\) for which the minimum-cost function \(L(\lambda)\) is equal to zero:_  
\[L(\lambda)=\sum\,(i,j)\in A^{*}(\lambda)\,\,(\lambda\cdot k_{ij}-e_{ij})=0, \tag{10}\]  
_and, further, together with the optimal value of the parameter \(\lambda^{*}\), find the corresponding minimum-cost assignment \(A^{*}(\lambda^{*})\) for the matrix \(\mathbf{W}(\lambda^{*})\); for the simplicity of notation, we denote the latter assignment by \(\Phi^{*}\): \(\Phi^{*}=A^{*}(\lambda^{*})\)._  
**Proposition 4**. : _Let \(\lambda^{*}\) be the optimal solution to the problem **PAP**, and \(\Phi^{*}=A^{*}(\lambda^{*})\) be the corresponding minimum-cost assignment for the matrix \(\mathbf{W}(\lambda^{*})\). Then,_  
\[\lambda^{*}=P^{*}=\sum_{(i,j)\in A^{*}}\,e_{ij}/\sum_{(i,j)\in A^ {*}}\,k_{ij}=\max_{A\in\mathbb{C}}\sum_{(i,j)\in A}\,e_{ij}/\sum_{(i,j)\in A }\,k_{ij},\] \[\text{ and }\Phi^{*}=A^{*},\]  
_that is, in meaningful terms, (i) the value of \(\lambda=\lambda^{*}\) defined by expression (10) is equal to the optimal profit value \(P^{*}\), which we are looking for, and (ii) the assignment \(\Phi^{*}\), which is optimal for the problem **PAP**, coincides with the optimal assignment \(A^{*}\) for the maximum average fleet profit in the problem **FAP**._  
Proof. : From Equation (10), we have:  
\[L(\lambda^{*})=\sum\,(i,j)\in A^{*}(\lambda^{*})\,(\lambda^{*}\cdot k_{ij}-e_ {ij})=0. \tag{11}\]  
In addition, from (8), we have:  
\[\sum_{(i,j)\in A}\,e_{ij}\leq\lambda\,\sum_{(i,j)\in A}\,k_{ij}\]0  
Then,  
\[\sum_{(i,j)\in A}\,e_{ij}\leq\lambda\,\sum_{(i,j)\in A}\,k_{ij}\]1Thus, from (11), we obtain that  
\[\sum_{(i,j)\in A}\,e_{ij}\leq\lambda\,\sum_{(i,j)\in A}\,k_{ij}\]2  
and from (12), we have  
\[\sum_{(i,j)\in A}\,e_{ij}\leq\lambda\,\sum_{(i,j)\in A}\,k_{ij}\]3  
that is, \(\lambda^{\star}=P^{\star}\) and \(\Phi^{\star}=A^{\star}\), which completes the proof.