Dismiss
InnovationQ will be updated on Sunday, Oct. 22, from 10am ET - noon. You may experience brief service interruptions during that time.
Browse Prior Art Database

Solution Property of Parametric Linear Programs

IP.com Disclosure Number: IPCOM000128575D
Original Publication Date: 1983-Dec-31
Included in the Prior Art Database: 2005-Sep-16
Document File: 6 page(s) / 19K

Publishing Venue

Software Patent Institute

Related People

X.S. Zhang: AUTHOR [+3]

Abstract

This paper shows that if a parametric linear program problem, with a parameter 8 linearly appearing in the r.h.s. of the constraint equations, has an optimal solution in La, bI, then it has an optimal solution X(Q) that is a continuous function of 8 in Ca, b7. The algorithm used to obtain the continuous solution in this paper is a commonly used method. The parametric linear program problem to be considered takes the form: [Equation ommitted] where A is mxn, bl, b2 are m-dimensional vectors and A is a. parameter, [Equation ommitted] . ale assume that problem (1) has a feasible solution at 80, It is well-knozm Cll, that if (1) has an optimal solution x(A) in COO, 91, then the objective function is a continuous, piecewise linear, concave function of the r.h.s.. What is to be shown in this note is that if an algorithm is specified. to solve (1), the solution x(A) itself is a continuous vector function of A. It w:11 be seen that the specified algorithm in this note is .a commonly used method to solve problem (1), i.e.,, the dual simplex method. This discussion 'is motivated by t'rof. J.B.Posen's recent paper E21'. In his paper an upper bound function *[Equation ommitted] is defined and proved as a piecewise concave function of A. If the solution of problem (1) is continuous in A, then the upper bound function y'ub(A) is also a continuous function of A. We will first specify the algorithm and subsequently verify that the solution given by this algorithm is continuous. We will use the standard notation x > y to denote a vector x that is lexicographically greater than y. Notation _ Lex-max will also be used-in the obvious way. Algorithm: Step 1. Let i = 0. Solve problem (1) with A = 8o by using the simplex method. Let the solution be x(Ao) and the current optimal basis be B = B(Bo). ,de will adopt the following notations: al

This text was extracted from a PDF file.
This is the abbreviated version, containing approximately 37% of the total text.

Page 1 of 6

THIS DOCUMENT IS AN APPROXIMATE REPRESENTATION OF THE ORIGINAL.

Solution Property of Parametric Linear Programs

by X.S. Zhang

Computer Science Department Institute of Technology 136 Lind Hall University of Minnesota Minneapolis, Minnesota 55455 Technical Report 83-7 March 4, Computer Science Dept. Univ. of Minnesota, U.S.A.

Institute of Applied Mathematics Academia Sinica, P.R.C.

ABSTRACT

This paper shows that if a parametric linear program problem, with a parameter 8 linearly appearing in the r.h.s. of the constraint equations, has an optimal solution in La, bI, then it has an optimal solution X(Q) that is a continuous function of 8 in Ca, b7. The algorithm used to obtain the continuous solution in this paper is a commonly used method. The parametric linear program problem to be considered takes the form:

(Equation Omitted)

where A is mxn, bl, b2 are m-dimensional vectors and A is a. parameter,

(Equation Omitted)

. ale assume that problem (1) has a feasible solution at 80, It is well-knozm Cll, that if (1) has an optimal solution x(A) in COO, 91, then the objective function is a continuous, piecewise linear, concave function of the r.h.s.. What is to be shown in this note is that if an algorithm is specified. to solve (1), the solution x(A) itself is a continuous vector function of A. It w:11 be seen that the specified algorithm in this note is .a commonly used method to solve problem (1), i.e.,, the dual simplex method. This discussion 'is motivated by t'rof. J.B.Posen's recent paper E21'. In his paper an upper bound function *

(Equation Omitted)

is defined and proved as a piecewise concave function of A. If the solution of problem (1) is continuous in A, then the upper bound function y'ub(A) is also a continuous function of A. We will first specify the algorithm and subsequently verify that the solution given by this algorithm is continuous. We will use the standard notation x > y to denote a vector x that is lexicographically greater than y. Notation _ Lex-max will also be used-in the obvious way.

Algorithm: Step 1. Let i = 0. Solve problem (1) with A = 8o by using the simplex method. Let the solution be x(Ao) and the current optimal basis be B = B(Bo). ,de will adopt the following notations: al

(Equation Omitted)

_ 1 _ and the current simplex tableau:

University of Minnesota Page 1 Dec 31, 1983

Page 2 of 6

Solution Property of Parametric Linear Programs

(Equation Omitted)

(Equation Omitted)

can be abridged into either

(Equation Omitted)

dimensional cola vectors and

(Equation Omitted)

Step 2. With reference to tableau (2) and (3) we define

(Equation Omitted)

where aio is an element in the zeroth column of the tableau..

We will use aij as a general element in the tableau. (i). If

(Equation Omitted)

Problem (1) has a solution

(Equation Omitted)

where B is the current basis. The computation is terminated.

( ii ) . If

(Equation Omitted)

go t o Step 3 .

(iii). If

(Equation Omitted)

go to Step 4. (iv). If

(Equation Omitted)

, the co...