Multiparametric Linear Programming

The multiparametric linear programming (MLP) problem for the right-hand sides (RHS) is to maximize z = c T x subject to Ax = b ( ), x 0, where b( ) be expressed in the form The multiparametric linear programming (MLP) problem for the prices or objective function coefficients (OFC) is to maximize z =...

Full description

Saved in:
Bibliographic Details
Published in:Management science 1972-03, Vol.18 (7), p.406-422
Main Authors: Gal, Tomas, Nedoma, Josef
Format: Article
Language:English
Subjects:
Algorithms
Constant coefficients
Linear programming
Matrices
Objective functions
Optimal solutions
Polyhedrons
Scalars
Simplex method
Tableaux
Theorems
Citations: Items that cite this one
Online Access:Get full text
Tags: Add Tag
No Tags, Be the first to tag this record!
Description
Summary:The multiparametric linear programming (MLP) problem for the right-hand sides (RHS) is to maximize z = c T x subject to Ax = b ( ), x 0, where b( ) be expressed in the form The multiparametric linear programming (MLP) problem for the prices or objective function coefficients (OFC) is to maximize z = c T ( v ) x subject to Ax = b , x 0, where c (I) can be expressed in the form c ( v ) = c * + Hv , and where H is a matrix of constant coefficients, and v a vector-parameter. Let B i be an optimal basis to the MLP-RHS problem and R i be a region assigned to B i such that for all R i the basis B i is optimal. Let K denote a region such that K = U i R i provided that the R i for various I do not overlap. The purpose of this paper is to present an effective method for finding all regions R i that cover K and do not overlap. This method uses an algorithm that finds all nodes of a finite connected graph. This method uses an algorithm that finds all nodes of a finite connected graph. An analogus method is presented for the MLP-OFC problem.
ISSN:0025-1909
1526-5501
DOI:10.1287/mnsc.18.7.406