ABSTRACT

The solutions of Linear Programming Problems by the segmentation of the cuboidal response surface through the Super Convergent Line Series methodologies were obtained. The cuboidal response surface was segmented up to four segments, and explored. It was verified that the number of segments, S, for which optimal solutions are obtained is two (S = 2). Illustrative examples and a real-life problem were also given and solved.

Keywords:

Average Information Matrix, Experimental Space, Line Search Algorithm, Support Points, Optimal Solution

1. Introduction

Linear Programming (LP) problems belong to a class of constrained convex optimization problems which have been widely discussed by several authors: see [1] [2] [3] . The commonly used algorithms for solving Linear Programming problems are: the Simplex method which requires the use of artificial variables and surplus or slack variables, and the active set method which requires the use of artificial constraints and variables. Over the years, a variety of line search algorithms have been employed in locating the local optimizer of response surface methodology (RSM) problems: see [4] and [5] . Similarly, the active set and simplex methods which are available for solving linear programming problems also belong to the class of line search exchange algorithms.

The line search algorithm, which is built around the concept of super convergence, has several points of departure from the classical, gradient-based line series. These gradient-based line series do often times fail to converge to the optimum but the Super Convergent Line Series (SCLS) which are also gradient- based techniques locate the global optimum of response surfaces with certainty. Super Convergent Line Series (SCLS) was introduced by [6] , and later used by [7] and [8] . [9] modified the Super Convergent Line Series (SCLS) and used it to solve Linear Programming Problems, [10] applied Quick Convergent Inflow Algorithm to solve Constrained Linear Programming Problems on Segmented region, and [11] modified the “Quick Convergent Inflow Algorithm” and used it to solve Linear Programming Problems based on variance of predicted response. In [12] , it was verified and established that the best number of segments is two (S = 2) for Linear Programming Problems, four (S = 4) for Quadratic Programming Problems, and eight (S = 8) for Cubic Programming Problems, for non-over- lapping segmentation of the response surface. The above algorithms compared favourably with other Line Search algorithms that utilize the principles of experimental design.

Other recent studies on line search algorithms for optimization problems are: [13] in which a modified version of line search for global optimization was proposed. The line search here uses a technique for the determination of random- generated values for the direction and step-length of the search. Some numerical experiments were performed using popular optimization functions involving fifty dimensions; comparison with standard line search, genetic algorithms and differential evolution were performed. Empirical results illustrate that the modified line search algorithm performs better than the standard line search and other techniques for three or four test functions considered. [14] focused on line search algorithms for solving large-scale unconstrained optimization problems such as quasi-Newton methods, truncated Newton and conjugate gradient. [15] proposed a line search algorithm based on the Majorize-Minimum principle; here, a tangent majorant function is built to approximate a scalar criterion containing a barrier function, which leads to a simple line search ensuring the convergence of several classical descent optimization strategies, including the most classical variants of non-linear conjugate gradient. [16] presented the fundamental ideas, concepts and theorems of basic line search algorithm for solving linear programming problems which can be regarded as an extension of the Simplex method. The basic line search algorithm can be used to find an optimal solution with only one iteration. [17] presented a performance of a one-dimensional search algorithm for solving general high-dimensional optimization problems which uses line search algorithm as subroutines.

In all the aforementioned works, none has gone beyond solving problems in two-dimensional spaces with segmentation. This paper is basically on obtaining optimal solutions and segmentation of Linear Programming Problems in three dimensional spaces of a cuboidal region.

2. Preliminaries

2.1. Three Dimensional Non-Overlapping Segmentation of the Response Surface

The space, $\widehat{X}$ , (the shape of a cube) is partitioned into subspaces called segments. These segments are non-overlapping with common boundaries. The space, $\widehat{X}$ , is partitioned into S non-overlapping segments as follows:

In Figure 1(a), the cube (experimental space) is partitioned into two segments, S₁ and S₂, while in Figure 1(b) and Figure 1(c), the cubes are partitioned into three and four segments, respectively. From the above Figures and their respective segments, support points will be picked to form their respective design matrices. The number of support points per segment, according to [18] , should not exceed $1/2p\left(p+1\right)+1$ , where p is the number of parameters of the regression model under consideration. Therefore, $p\le n\le 1/2p\left(p+1\right)+1$ , where n is

the maximum number of support points per segment. The number of support points per segment as given by [6] is $n+1\le N_k\le 1/2n\left(n+1\right)+1$ , where n is the number of variables in the model, N_k is the number of support points in N_k segment. The support points per segment are arbitrarily chosen provided they satisfy constraint equations and do not lie outside the feasible region.

2.2. Rationale of the Segmentation

Design matrices are formed from the support points obtained from each of the segments created above. The segmentation of the response surface according to [6] is a rapid way of improving the average information matrix and obtaining the optimum direction vector. This is achieved by obtaining the linear combination of the information matrices from the different segments. The improved average information matrix (resultant matrix) is used to compute the optimum direction vector, which locates the optimum direction and the optimizer in a very short period or with one iteration. Without segmentation, information leading to the optimizer would have been obtained from only a fraction of the entire response surface.

With segmentation, more support points are available at the boundary of the feasible region. [18] [19] [20] have shown that a design formed with support points taken at the boundary of the feasible region is better than any other design with support points taken at the interior of the feasible region.

Theorem: The average information matrix resulting from pooling the segments using matrices of coefficients of convex combination is

$M\left({\zeta }_n\right)={\displaystyle \sum _{k=1}^s{H}_k{X}_k^{\text{T}}{X}_k{H}_k^{\text{T}},}$

Proof:

$\begin{array}{c}{\underset{\_}{X}}^{\text{T}}\underset{\_}{X}=\text{diag}\left\{X_1^{\text{T}}{X}_1,X_2^{\text{T}}{X}_2,\cdots ,X_S^{\text{T}}{X}_S\right\}\\ =\left[\begin{array}{cccc}{X}_1^{\text{T}}{X}_1& 0& \cdots & 0\\ 0& X_2^{\text{T}}{X}_2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & X_S^{\text{T}}{X}_S\end{array}\text{}\text{}\right],\end{array}$

where H_k is the matrix of coefficient of convex combination, $X_K^{\text{T}}{X}_K$ is the information matrix

$H_K=\left[\begin{array}{cccc}{h}_{0k}& 0& \cdots & 0\\ 0& h_{1k}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & h_{nk}\end{array}\text{}\text{}\right]$ , $H_K^{\text{T}}=\left[\begin{array}{cccc}{h}_{0k}& 0& \cdots & 0\\ 0& h_{1k}& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & h_{nk}\end{array}\text{}\text{}\right]$ and

$H_K{H}_K^{\text{T}}=\left[\begin{array}{cccc}{h}_{0k}^2& 0& \cdots & 0\\ 0& h_{1k}^2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & h_{nk}^2\end{array}\text{}\text{}\right]$ .

Thus,

$\begin{array}{c}{\displaystyle \sum _{k=1}^s{H}_K{H}_K^{\text{T}}}=H_1{H}_1^{\text{T}}+H_2{H}_2^{\text{T}}+\cdots +H_S{H}_S^{\text{T}}\\ =\left[\begin{array}{cccc}{h}_{01}^2& 0& \cdots & 0\\ 0& h_{11}^2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & h_{n1}^2\end{array}\text{}\text{}\right]+\left[\begin{array}{cccc}{h}_{02}^2& 0& \cdots & 0\\ 0& h_{12}^2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & h_{n2}^2\end{array}\text{}\text{}\right]+\cdots +\left[\begin{array}{cccc}{h}_{0s}^2& 0& \cdots & 0\\ 0& h_{1s}^2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & h_{ns}^2\end{array}\text{}\text{}\right]\\ =\left[\begin{array}{cccc}{h}_{01}^2+h_{02}^2+\cdots +h_{0s}^2& 0& \cdots & 0\\ 0& h_{11}^2+h_{12}^2+\cdots +h_{1s}^2& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & h_{n1}^2+h_{n2}^2+\cdots +h_{ns}^2\end{array}\text{}\text{}\right]\end{array}$

Therefore, ${\displaystyle \sum _{k=1}^s{H}_K{H}_K^{\text{T}}}=\left[\begin{array}{cccc}1& 0& \cdots & 0\\ 0& 1& \cdots & 0\\ ⋮& ⋮& \ddots & ⋮\\ 0& 0& \cdots & 1\end{array}\right]=1$ , since ${\displaystyle \sum _{i=0}^n{\displaystyle \sum _{k=1}^s{h}_{ik}^2}}=1$

Therefore, $M\left({\zeta }_n\right)={\displaystyle \sum _{k=1}^s{H}_K{X}_K^{\text{T}}{X}_K{H}_K^{\text{T}}}$

3. Methodology

3.1. The Theory of Super Convergent Line Series

3.1.1. Definitions and Preliminaries

The Super Convergent Line Series (SCLS) is defined by [6] as

$\underset{\_}{X}=\overline{\underset{\_}{X}}-\rho \underset{\_}{d}$ (1.1)

$\underset{\_}{X}$ is the vector of the optimal values,

$\overline{\underset{\_}{X}}={\displaystyle \sum _{m=1}^N{w}_m{x}_m}$ is the optimal starting points, where $w_m>0$ ; ${\displaystyle \sum _{m=1}^N{w}_m=1}$ , $w_m=\frac{a_m^{-1}}{{\displaystyle \sum _{m=1}^N{a}_m^{-1}}}$ ,

$a_m=X_m^{\text{T}}{X}_m,m=1,2,\cdots ,N.$

$\underset{\_}{d}$ is the direction vector defined as $\underset{\_}{d}=M_A^{-1}\left({\zeta }_N\right)\underset{\_}{Z}(.)$ , where $\underset{\_}{Z}(.)={\left(Z_0,Z_1,\cdots ,Z_n\right)}^{\text{T}}$ is an n-component vector of responses; $Z_i=f\left(m_i\right)$ , is the ith row of the average information matrix, $M_A\left({\zeta }_N\right)$ , where $M_A^{-1}\left({\zeta }_N\right)$ is the inverse of the average information matrix;

$\rho$ is the step-length defined as $\rho =\min \left\{\frac{{\underset{\_}{C}}_i^{\text{T}}\underset{\_}{\overline{X}}-b_i}{{\underset{\_}{C}}_i^{\text{T}}\underset{\_}{d}}\right\}$ , where $\underset{\_}{d}$ is the di-

rection vector; ${\underset{\_}{C}}_i^{\text{T}}$ is the vector which represents the parameter of linear inequalities; $\underset{\_}{\overline{X}}$ is the starting point and $b_i$ is a scalar of the linear inequalities;

${\zeta }_N$ is an N-point design measure whose support points may or may not have equal weights;

Support points are pairs of points marked on the boundary and interior of the partitioned space which are picked to form design matrices;

$\tilde{X}$ is the experimental space of the response surface that can be partitioned into segments such that every pair of support points in the segment is a subset of $\tilde{X}$ ;

$M\left({\zeta }_{nk}\right)=\left(X_k^{\text{T}}{X}_k\right)$ is the information matrix, $M^{-1}\left({\zeta }_{nk}\right)={\left(X_k^{\text{T}}{X}_k\right)}^{-1}$ is the inverse information matrix;

S₁ is segment 1, S₂ is segment 2,

$\det M\left({\zeta }_{nk}\right)$ is the determinant of the information matrix;

H_i is the matrix of the coefficients of convex combination and is defined as

$H_i=\text{diag}\left(h_{i1},h_{i2},\cdots ,h_{i,n+1}\right),i=1,2,\cdots ,k;$

With i = 1, 2 segments, the coefficients of convex combinations, H_i, of the segments are:

$H_1=\text{diag}\left\{\frac{V_1{}_{11}}{V_{111}+V_{211}},\frac{V_{122}}{V_{122}+V_{222}},\frac{V_{133}}{V_{133}+V_{233}}\right\}=\text{diag}\left\{h_{11},h_{12},h_{13}\right\}$ (1.2)

for the inverse information matrix in segment 1,

$H_2=\text{diag}\left\{\frac{V_2{}_{11}}{V_{111}+V_{211}},\frac{V_{222}}{V_{122}+V_{222}},\frac{V_{233}}{V_{133}+V_{233}}\right\}=\text{diag}\left\{h_{21},h_{22},h_{23}\right\}$ (1.3)

for the inverse information matrix in segment 2,

where V₁₁₁, V₁₂₂, V₁₃₃ are the variances of the inverse information matrix of segment 1 and V₂₁₁, V₂₂₂, V₂₃₃ are variances of the inverse information matrix of segment 2, respectively.

The average information matrix, $M_A\left({\zeta }_N\right)$ , is the sum of the product of the k information matrices and the k matrices of the coefficients of convex combinations, thus

$M_A\left({\zeta }_N\right)={\displaystyle \sum _{k=1}^s{H}_k{X}_k^{\text{T}}{X}_k{H}_k^{\text{T}}};$ see [6] (1.4)

Segmentation is the partitioning of the experimental space, $\tilde{X}$ , into segments. Segmentation can be non-overlapping and overlapping, and support points are selected from each segment to form design matrices.

An unbiased response function is defined by

$f\left(x_1,x_2\right)=a_{00}+a_{10}{x}_1+a_{20}{x}_2$ (1.5)

3.1.2. Algorithm for Super Convergent Line Series

The algorithm follows the following sequence of steps:

1) Partition the experimental space (Cube) into $k=1,2,\cdots ,s$ segments and select N_k support points from the kth segment; hence, make up an N-point design,

${\zeta }_N^{\left(1\right)}=\left\{\begin{array}{c}{\underset{\_}{x}}_1,{\underset{\_}{x}}_2,\cdots ,{\underset{\_}{x}}_n,\cdots ,{\underset{\_}{x}}_n,\\ w_1,w_2,\cdots ,w_n,\cdots ,w_n\end{array}\right\};N={\displaystyle \sum _{k=1}^s{N}_k.}$

2) Compute the vectors, ${\overline{\underset{\_}{X}}}^{\ast },d^{\ast },{\rho }^{\ast }.$

3) Move to the point, ${\underset{\_}{X}}^{\ast }={\overline{\underset{\_}{X}}}^{\ast }-{\rho }^{\ast }{d}^{\ast }.$

4) Is $X^{\ast }=X{f}^{\ast }$ ? (where $X{f}^{\ast }$ is the optimizer of $f(\cdot )$ ).

Yes: stop,

No: then go back to 1) above until the optimal solution is obtained.

5) Identify the segment in which the optimal solution is obtained.

3.2. The Average Information Matrix, the Direction Vector, the Starting Point and the Step-Length

3.2.1. The Average Information Matrix

The average information matrix, $M\left({\zeta }_n\right)$ , is the sum of the product of the k information matrices, and the k matrices of the coefficients of convex combina-

tions given by $M\left({\zeta }_n\right)={\displaystyle \sum _{k=1}^s{H}_K{X}_K^{\text{T}}{X}_K{H}_K^{\text{T}}},$

for two segments, the average information matrix is $M_A\left({\zeta }_N\right)=H_1^{\ast }{X}_1^{\text{T}}{X}_1{H}_1^{\ast \text{T}}+H_2^{\ast }{X}_2^{\text{T}}{X}_2{H}_2^{\ast \text{T}}=\left(\begin{array}{ccc}{m}_{11}& m_{21}& m_{31}\\ m_{12}& m_{22}& m_{32}\\ m_{13}& m_{23}& m_{33}\end{array}\right)$ .

3.2.2. The Direction Vector

The direction vector defined in Section 3.1.1 is computed as follows:

If f(x) is the response function, then the response vector, Z, is given by

$Z=\left(\begin{array}{c}{z}_0\\ z_1\\ z_2\\ ⋮\\ z_n\end{array}\right)$ , where

$\begin{array}{l}{z}_0=f\left(m_{12},m_{13},\cdots ,m_{1,n+1}\right),\\ z_1=f\left(m_{22},m_{23},\cdots ,m_{2,n+2}\right),\\ ⋮\\ z_n=f\left(m_{n+1,2},m_{n+1,3},\cdots ,m_{2,n+1}\right).\end{array}$

Hence, the direction vector defined in Section 3.1.1 is computed as

$\underset{\_}{d}=M_A^{-1}\left({\zeta }_N\right)Z=\left(\begin{array}{c}\underset{\_}{d_0}\\ d_1\\ d_2\\ ⋮\\ d_n\end{array}\right)$ .

By normalizing such that $d^{*\text{T}}{d}^{*}=1$ , we have $d^{*}=\left(\begin{array}{c}\frac{d_1}{\sqrt{d_1^2+d_2^2+\cdots +d_n^2}}\\ \frac{d_2}{\sqrt{d_1^2+d_2^2+\cdots +d_n^2}}\\ ⋮\\ \frac{d_n}{\sqrt{d_1^2+d_2^2+\cdots +d_n^2}}\end{array}\right)$ ,

where d₀ = 1 is discarded.

3.2.3. Optimal Starting Point

The optimal starting point is obtained from the design matrices of the segments considered. The optimal starting point defined in Section 3.1.1 is obtained as follows:

$\overline{\underset{\_}{X}}={\displaystyle \sum _{m=1}^N{w}_m{x}_m};w_m\ge 0;{\displaystyle \sum _{m=1}^N{w}_m}=1.w_m=\frac{a_m^{-1}}{{\displaystyle \sum _{m=1}^N{w}_m}},m=1,2,\cdots ,N.$

$a_m=x_m^{\text{T}}{x}_m,m=1,2,\cdots ,N.$

Using a 4-point design matrix, $\overline{\underset{\_}{X}}={\displaystyle \sum _{m=1}^8{w}_m{x}_m},w_m=\frac{a_m^{-1}}{{\displaystyle \sum _{m=1}^8{a}_m^{-1}}},m=1,2,\cdots ,8.$

3.2.4. The Step-Length

The step-length is defined by

${\rho }^{\ast }=\min \left\{\frac{{\underset{\_}{C}}^{\prime }{}_i^{\text{T}}{\underset{\_}{\overline{X}}}^{\ast }-b_i}{{\underset{\_}{C}}^{\prime }{}_i^{\text{T}}{\underset{\_}{d}}^{\ast }}\right\}$ , where ${\rho }^{\ast }$ is the optimal step-length and ${\underset{\_}{d}}^{\ast }$ is the

normalized direction vector, ${\underset{\_}{C}}_i^{\text{T}}$ is the vector which represent the parameter of linear inequalities, ${\underset{\_}{\overline{X}}}^{\ast }$ is the starting point while $b_i$ is a scalar of linear inequalities.

4. Results and Discussion

4.1. Comparison of Results Obtained Using the Segmentation Procedure with Existing

Results in the Literature

Problem 1: [ [21] , Problem 7.2B, Question 2b, pp. 304]

Maximize $Z=2x_1+x_2+2x_3$

Subject to $4x_1+3x_2+8x_3\le 12$

$4x_1+x_2+12x_3\le 8$

$4x_1-x_2+3x_3\le 8$

$x_1,x_2,x_3\ge 0$

Support points are picked from the boundaries of the partitioned segments (Figure 2) provided they do not violate the constraint equations.

Thus $X_1=\left\{\left(0,1,0\right),\left(0,1,1\right),\left(0,0,1\right),\left(1/2,0,0\right),\cdots ,\left(1/4,0,0\right)\right\}$ and

$X_2=\left\{\left(1,0,1\right),\left(0,0,1/2\right),\left(1,0,0\right),\left(1,1/2,0\right),\left(1,1,0\right),\cdots ,\left(1/2,0,0\right)\right\}$ ,

where X₁ and X₂ is obtained from S₁ and S₂ respectively.

Thus, the design and inverse matrices are given as follows (from Figure 2):

$X_1=\left(\begin{array}{cccc}1& 0& 1& 0\\ 1& 0& 0& \frac{1}{2}\\ 1& 0& \frac{1}{2}& 0\\ 1& \frac{1}{2}& 0& 0\end{array}\right)$ ; $X_2=\left(\begin{array}{cccc}1& 1& 1& 0\\ 1& 1& \frac{1}{2}& 0\\ 1& \frac{1}{2}& 0& 0\\ 1& 0& 0& \frac{1}{2}\end{array}\right)$ ,

${\left(X_1^{\text{T}}{X}_1\right)}^{-1}=\left(\begin{array}{cccc}5& -10& -6& -10\\ -10& 24& 12& 20\\ -6& 12& 8& 12\\ -10& 20& 12& 24\end{array}\right)$ ; ${\left(X_2^{\text{T}}{X}_2\right)}^{-1}=\left(\begin{array}{cccc}9& -14& 6& -18\\ -14& 24& -12& 28\\ 6& -12& 8& -12\\ -18& 28& -12& 40\end{array}\right)$

The direction vector, $\underset{\_}{d}=\left(\begin{array}{c}2.000\\ 1.000\\ 2.000\end{array}\right)$ ; by normalizing $\underset{\_}{d}$ , we get ${\underset{\_}{d}}^{\ast }=\left(\begin{array}{c}0.8944\\ 0.4472\\ 0.8944\end{array}\right)$ ,

(See Section 3.2.2)

${\overline{\underset{\_}{X}}}^{\ast }={\displaystyle \sum _{i=1}^N{w}_i{x}_i}=\left(\begin{array}{c}0.2990\\ 0.2758\\ 0.1516\end{array}\right)$ , the step-length, ${\rho }^{\ast }=-1.1396$ , ${\underset{\_}{X}}^{\ast }={\underset{\_}{\overline{X}}}^{\ast }-{\rho }^{\ast }{d}^{\ast }=\left(\begin{array}{c}1.318\\ 0.7854\\ 1.1709\end{array}\right)$ .

Therefore, Max Z = 5.46.

With S = 2 (2 Segments), the value of Z is Max. Z = 5.46 (in one iteration) which is close to the optimal value obtained by [21] , problem 7.2b, Question 2b, pp. 304, as Max Z = 5.00 (in 3 iterations). The maximum values of Z for this problem using 3 and 4 segments are: 5.81 for (x₁, x₂, x₃) = (1.265, 0.7891, 1.2431), and 5.77 for (x₁, x₂, x₃) = (1.0008, 0.6606, 1.5523). These values are not optimal because they do not compare favourably with the existing solution got by [21] using the simplex method.

Problem 2: [ [22] , Ex. 2.4, Q. 14(ii), p. 215]

Maximize $Z=5x_1+3x_2+7x_3$

Subject to $x_1+x_2+2x_3\le 26$

$3x_1+2x_2+x_3\le 26$

$x_1+x_2+x_3\le 18$

$x_1,x_2,x_3\ge 0$

Support points are picked from the boundaries of the partitioned segments (from Figure 3) provided they do not violate the constraint equations.

Thus $X_1=\left\{\left(0,1,0\right),\left(0,1,1\right),\left(0,0,1\right),\left(1/2,0,0\right),\cdots ,\left(1/4,0,0\right)\right\}$ and

$X_2=\left\{\left(1,0,1\right),\left(0,0,1/2\right),\left(1,1,1\right),\left(1,1/2,0\right),\left(1,1,0\right),\cdots ,\left(1/2,0,0\right)\right\}$ ,

Thus, the design and inverse matrices are given as follows (from Figure 3):

$X_1=\left(\begin{array}{cccc}1& 0& 1& 0\\ 1& 0& 1& 1\\ 1& \frac{1}{4}& 0& 0\\ 1& 0& 0& 1\end{array}\right)$ ; $X_2=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 0& 1\\ 1& 1& \frac{1}{2}& 0\\ 1& \frac{1}{2}& 0& 0\end{array}\right)$ ,

${\left(X_1^{\text{T}}{X}_1\right)}^{-1}=\left(\begin{array}{cccc}3& -12& -2& -2\\ -12& 64& 20& 8\\ -2& 8& 2& 1\\ -2& 8& 1& 2\end{array}\right)$ ; ${\left(X_2^{\text{T}}{X}_2\right)}^{-1}=\left(\begin{array}{cccc}9& -14& 6& 5\\ -14& 24& -12& -10\\ 6& -12& 8& 6\\ 5& -10& 6& 6\end{array}\right)$

The direction vector, $\underset{\_}{d}=\left(\begin{array}{c}5.0002\\ 2.9998\\ 6.9999\end{array}\right)$ , by normalizing $\underset{\_}{d}$ , we get ${\underset{\_}{d}}^{\ast }=\left(\begin{array}{c}0.5488\\ 0.3293\\ 0.7683\end{array}\right)$

(See Section 3.2.2) ${\overline{\underset{\_}{X}}}^{\ast }={\displaystyle \sum _{i=1}^N{w}_i{x}_i}=\left(\begin{array}{c}0.3812\\ 0.3318\\ 0.2787\end{array}\right)$ , the step-length ${\rho }^{\ast }=-10.3306$ , ${\underset{\_}{X}}^{\ast }={\underset{\_}{\overline{X}}}^{\ast }-{\rho }^{\ast }{d}^{\ast }=\left(\begin{array}{c}6.0506\\ 3.7337\\ 8.2157\end{array}\right)$ .

Therefore, Max Z = 98.96.

With S = 2 (2 Segments), the value of Z is Max Z = 98.96 which is close to the

optimal value (in one iteration) obtained by [22] , Ex. 2.4, Q 14(ii), p. 215, as Max Z = 98.80 (in two iterations), using the simplex method. The maximum value of Z for this problem using 3 and 4 segments are: 99.06 for (x₁, x₂, x₃) = (6.0213, 3.725, 8.2537) and 99.15 for (x₁, x₂, x₃) = (6.0746, 3.675, 8.2503).

4.2. Illustrative Problem and Application

A producer of leather shoes makes three types of shoes, X, Y and Z, which are processed on three machines, K₁, K₂ and K₃. The daily capacities of the machines are given in Table 1 as follows.

The profit gained from shoe X is ₦3 per unit, shoe Y is ₦5 per unit and shoe Z is ₦4 per unit. What is the maximum profit for the three types of shoe produced?

Solution: Let X₁ be the unit of type X, X₂ be the unit of type Y and X₃ be the unit of type Z.

Maximize $Z=3x_1+5x_2+4x_3$

Subject to $2X_1+3X_2\le 8$

$2X_2+5X_3\le 10$

$3X_1+2X_2+4X_3\le 15$

$X_1,X_2,X_3\ge 0$

In a similar manner, the design and inverse matrices are given as follows [from Figure 4].

$X_1=\left(\begin{array}{cccc}1& 0& 1& 0\\ 1& 0& 1& 1\\ 1& \frac{1}{4}& 0& 0\\ 1& 0& 0& 1\end{array}\right)$ ; $X_2=\left(\begin{array}{cccc}1& 1& 1& 1\\ 1& 1& 0& 1\\ 1& 1& \frac{1}{2}& 0\\ 1& \frac{1}{2}& 0& 0\end{array}\right)$ ,

${\left(X_1^{\text{T}}{X}_1\right)}^{-1}=\left(\begin{array}{cccc}3& -12& -2& -2\\ -12& 64& 8& 8\\ -2& 8& 2& 1\\ -2& 8& 1& 2\end{array}\right)$ ; ${\left(X_2^{\text{T}}{X}_2\right)}^{-1}=\left(\begin{array}{cccc}9& -14& 6& 5\\ -14& 24& -12& -10\\ 6& -12& 8& 6\\ 5& -10& 6& 6\end{array}\right)$ .

The direction vector, $\underset{\_}{d}=\left(\begin{array}{c}3\\ 5\\ 4\end{array}\right)$ ; by normalizing $\underset{\_}{d}$ , we get ${\underset{\_}{d}}^{\ast }=\left(\begin{array}{c}0.4243\\ 0.7071\\ 0.5657\end{array}\right)$ , ${\overline{\underset{\_}{X}}}^{\ast }={\displaystyle \sum _{i=1}^N{w}_i{x}_i}=\left(\begin{array}{c}0.3027\\ 0.2953\\ 0.2483\end{array}\right)$ , step-length ${\rho }^{\ast }=-2.1916$ , ${\underset{\_}{X}}^{\ast }={\underset{\_}{\overline{X}}}^{\ast }-{\rho }^{\ast }{d}^{\ast }=\left(\begin{array}{c}1.2326\\ 1.845\\ 1.4881\end{array}\right)$ . Therefore, the maximum value of Z is

₦18.88. This value in one iteration is close to the optimum value got by using the simplex method approach (in three iterations). When 3 and 4 segments were used, the maximum values of Z for this problem are ₦21.25 with corresponding values (X₁, X₂, X₃) = (1.37, 2.08, 1.68) and ₦21.03 with corresponding values (X₁, X₂, X₃) = (1.43, 2.01, 1.67). These values are not optimal because they do not compare favourably with the simplex method solution which is Max Z = ₦18.66.

5. Conclusion

Three dimensional Linear Programming problems have been solved using the line search equation, ${\underset{\_}{\overline{X}}}^{\ast }-{\rho }^{\ast }{d}^{\ast }$ , of the Super Convergent Line Series, by segmenting the cuboidal response surface into 2, 3 and 4 segments. A real-life problem was also used to achieve the desired result. It was found that the optimal solution is attained at 2 segments (S = 2) and in one iteration or move even though up to 4 segments (S = 4) were considered. But comparing the solution with the simplex method’s result, a close result was obtained in 2 and 3 iterations. Hence, as the name implies, the Super Convergent Line Series (SCLS) locates the optimizer in one iteration and better still with segmentation.

Cite this paper

Ugbe, T. and Chigbu, P. (2017) On Optimal Non-Overlapping Segmentation and Solutions of Three-Dimen- sional Linear Programming Problems through the Super Convergent Line Series. American Journal of Operations Research, 7, 225-238. https://doi.org/10.4236/ajor.2017.73015

References