A New Procedure for Solving Linear Programming Problem with Sensitivity Analysis

INTRODUCTION

The problem of linear programming (LP) is one of the earliest formulated problems in mathematical programming, where a linear function has to be maximized (or minimized) over a convex constraint polyhedron X. This kind of problem has been widely applied in practically every area of production, economic, social and government planning.

The simplex algorithm was early suggested for solving this problem by moving toward a solution on the exterior of the constraint polyhedron X. In 1984, the area of linear programming underwent a considerable change of orientation when Karmarkar¹ introduced an algorithm for solving (LP) problems which moves through the interior of the polyhedron. The algorithm of Karmarkar's and subsequent additional variants^2,3 established a new class of algorithms for solving linear programming problems known as the interior point methods .While methods based on vertex information may have difficulties as problem's size increases, the interior point methods proved to be less sensitive to problem's size. For more details about interior point methods, the reader is referred to Ye⁴. Also for more recent work concerning interior point solution and conjugate gradient projection method, the reader is recommended to review^5-8. Some time, it is quite important to know the range of parameters for which the solution remains optimal. The investigation that deals with changes in the optimal solution due to changes in the data of the linear programming problems can be found in Arsham⁹, Ghaffari-Hadigheh et al.¹⁰ and Hadigheh et al.¹¹. In this study, an iterative method for solving (LP) problems with sensitivity analysis is given. This analysis presented here permits perturbation in the data of the objective function that maintain the optimality of the problem.

PROBLEM STATEMENT AND THE SOLUTION CONCEPT

The linear programming problem (LP) arises when a linear function is to be maximized over a convex constraint polyhedron X. This problem can be formulated as follows:

(1)

where, p, x∈Rⁿ, A is an (m+n)×n matrix, b∈R^m+n, it pointed out that the nonnegative conditions are included in the set of constraints. This problem can also be written in the form:

(2)

where, represents the ith row of the given matrix A, then it has in the non-degenerate case an extreme point (vertex) of X lies on some n linearly independent subset of X. It shall give an iterative method for solving this problem, this method starts with an initial feasible point then a sequence of feasible directions toward optimality is generated to find the optimal extreme point of this programming, in general if x^k-1 is a feasible point obtained at iteration k-1 (k = 1, 2...) then at iteration k our procedure finds a new feasible point x^k given by:

(3)

where, d^k-1 is the direction vector along which it move and given by:

(4)

where, H_k-1 is an n×n symmetric matrix given by:

(5)

In Eq. 5, I is an n×n identity matrix and q is the number of active constraints at the current point while is defined as follows, for each active constraint s; s = 1, 2... q:

(6)

With, H⁰_k-1 = I. Then H_k-1 is given by H_k-1 = H^q_k-1. The step length α_k-1 is given by:

(7)

The above relation stated that α_k-1 is always positive. Proposition 2-3 shows that such a positive value must exist if a feasible point exists. Also due to the well known Kuhn-Tucker condition^12,6 for the point x^k to be an optimal solution of the linear program (2-1) their must exist u>0 such that:

(8)

where, A_r is an nxn sub-matrix of the given matrix A containing only the coefficients of the set of active constraints at the current point x^k. This fact will act as a stopping rule of our proposed algorithm.

A NEW ALGORITHM FOR SOLVING (LP) PROBLEMS

The algorithm presented on this section for solving (LP) problems consists of the following steps:

Remark 3-1: Assuming that q is the number of active constraints at point x^k then if q<n and relation (Eq. 8) is satisfied this indicates that x^k is an optimal non-extreme point, in this case the objective function can not be improved through any feasible direction and then we have H_k p = 0 at this point x^k, it noted that although the matrix H_k is singular it does not cause the breakdown of this algorithm but indicate that all subsequent search directions d^k+1 will be orthogonal to p.

Remark 3-2: If x^k-1 is an extreme non-optimal i.e., there are n active constrains at point x^k-1 and relation Eq. 8 is not satisfied.

A sub-matrix from the given matrix A_r is chosen (at least one constraint has to be dropped) to define a direction d^k-1 for the new movement. This sub-matrix is normal to a column (a_w) from (A_r)^–1 such that p^T (a_w) is the most negative element in Eq. 8.

Theorem 3-1: Our procedure solves the (LP) problem in at most m+n iterations.

Proof: Since in each iteration it added at least one active constraint, then the optimal point may be reached in n steps and the algorithm terminate in at most n iterations. On the other hand if at any iteration we have non optimal extreme point and at least one constraint has to be dropped from the set of active constraints. Since our allowed directions by (Eq. 4) that improve the value of the objective function lies in the nullity of a subset of the constraint set, then it is moving in the direction parallel to a certain subset of the (m+n) constraints and hence in the worst case the maximum number of iterations required to reach the optimal point is limited by m+n.

SENSITIVITY ANALYSIS FOR LINEAR PROGRAMMING PROBLEM

Introducing a scalar parameter in the objective function coefficient of (LP) problem may affect the optimal solution due to some changes on the data of the objective function.

Now consider the perturbed (LP) problem when changes in the coefficient of the objective function is occurred and is formulated as:

(9)

where, μ is a scalar parameter and p¹∈Rⁿ. Our task of this sensitivity analysis is to find the range of μ that maintain the optimality of the linear programming problem using the same argument then the only change will be in computing:

(10)

and for the optimal point to remain optimal u (μ )>0 has to be satisfied which gives the range of μ for the optimal point to remain optimal for the new perturbed problem (Eq. 9).

An application to production example: A small company manufactures four types of products. The data summarized the production hours per unit in each of three production operations and the profit per each unit is also given:

Assuming that the company wants to maximize profit, how many units of each product should be manufactured . For example suppose that x₁, x₂, x₃ and x₄ represent the number of units for each product, respectively, the above problem can be formulated as a linear programming problem:

Step 0:
	then Eq. 7 gives α0 = 0.1 and we go to step 1
Step 1:	Apply relation (Eq. 3) to get:
Step 2:	For this point x1 the first constraint is the only active constraint and since relation (Eq. 8) is not satisfied indicates this point is not optimal
Step 3:	Set k = 2. Apply relation (Eq. 5, 4 and 7) to get:

Step 1:	Apply relation (3) to get:
Step 2:	For this point x2 the first and the third constraint are the only active constraints and since relation (8) is not satisfied
Step 3:	Set k = 3. Apply relation (Eq. 5, 4 and 7) to get:

Step 1:	Apply relation (Eq. 3) to get:
Step 2:	For this point x3, it has the first, the second and the third constraint are the active constraints, since relation (Eq. 8) is not satisfied we go to step 3
Step 3:	Set k = 4. Apply relation (Eq. 5, 4 and 7) to get:
	we use relation (3) to get:

Since relation (Eq. 8) is satisfied with u^T = 1.1 0.45 0.25 0.35 this indicates that the extreme point x⁴ is the optimal point for the above linear programming problem with optimal value F(x⁴) = 6.5.

Sensitivity analysis has to be done if the given problem to be solved is taken the form:

Since for μ = 0, it has the extreme point x⁴ is the optimal point and relation (Eq. 8) is satisfied with u^T = 1.1 0.45 0.25 0.35, then for the perturbed problem when a scaler parameter μ is added in the objective function we have to apply (Eq. 10) to compute:

u^T(μ) = (1.1-0.9 μ 0.45+0.95 μ 0.25-0.25 μ 1.35-4.15 μ)

which gives the range of μ:

-0.47<μ<0.33

as the range such that the optimal extreme point x⁴ remains optimal for the perturbed problem.