0
$\begingroup$

Excuse me if my question is stupid. I'm seeking the references on the dependence of the (linear) optimization problem on (linear) constraints. Namely, consdier the following optimization problem:

$$P(\alpha)~~:=~~\sup_{p\in\mathcal A(\alpha)}~c^T p,$$

with

$$\mathcal A(\alpha)~~:=~~\big\{p\in\mathbb R^n:~ Ap~=~\alpha\big\},$$

where $\alpha\in\mathbb R^m$, $c\in\mathbb R^n$ and $A\in\mathbb R^{m\times n}$ are given. I'm looking for the references on the map $\alpha\longrightarrow P(\alpha)$. Any suggestions and comments are highly appreciated. Thanks a lot!

PS: Thanks for the reply. Indeed, here we suppose of course that $m>n$ and actually $p_i\ge 0$ and $\sum_{i=1}^np_i=1$. So if the set $\mathcal{A}(\alpha)\neq \emptyset$, then the maximizer always exists.

Improve this question
$\endgroup$

2 Answers 2

Reset to default
1
$\begingroup$

If you consider general linear programming problems and the solution in dependence on changes in the right hand side, you want to look for sensitivity analysis in linear programming and more specifically changes in the right hand side. Most books on linear programming cover this, e.g. chapter 3 in "Applied Mathematical Programming".

Improve this answer
$\endgroup$
0
1
$\begingroup$

The usual linear programming problem requires at least some variables to be nonnegative or has inequality constraints. Here you only have equality constraints and $p \in \mathbb R^n$, so your feasible region (if nonempty) is an affine subspace, and in order for $P(\alpha)$ to be finite your $c^T$ must be a linear combination of the rows of $A$. Then $P(\alpha)$ will be the corresponding linear combination of the entries of $\alpha$. Also, any linear dependency of the rows of $A$ will correspond to a constraint on the entries of $\alpha$ required for feasibility.

Improve this answer
$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .