Tagged Questions
1
vote
1answer
34 views
How to construct an LP problem that makes a (partial) theorem fail?
I am following a course on linear programming, and one of the exercises calls for an example, that may show that a theorem fails, if a assumption is omitted from the theorem.
The theorem is Theorem ...
1
vote
1answer
83 views
Directly from primal to dual when primal not in standard form
This is a simple problem, but after spending some hours with linear programs in the primal and its dual form, I still can't do it quite intuitively for LPs which are not in the standard form. I know, ...
2
votes
3answers
80 views
Dual of a Linear Program
\begin{align}
\min_{x} c^Tx \\
s.t.~Ax=b
\end{align}
Note that here $x$ is unrestricted. I need to prove that the dual of this program is given by
\begin{align}
\max_{\lambda} \lambda^Tb \\
...
0
votes
0answers
156 views
Dual of max-flow
I have a hard time understanding dual of max flow problems. Can experienced thinkers solve the problems below and possibly give reasoning? Thank you.
$$S\rightarrow A\quad 1$$
$$S\rightarrow B ...
2
votes
0answers
113 views
intuitive explanation of Primal-Dual algorithms
I've recently heard of Primal-Dual algorithms and I was wondering if someone could give me an intuitive explanation of it. I searched online, but did not find an intuitive explanation. I'd be glad if ...
0
votes
1answer
174 views
Underlying assumption in a Primal/Dual table
I just read in one of the questions answered by @MikeSpivey that the following table is provided in Sierksma's Linear and Integer Programming: Theory and Practice, Volume 1, page 144.
...
1
vote
1answer
95 views
Multiple solutions for both primal and dual
If matrix $A$ in an LP (or $A^T$ in its dual) has full row (column- in dual) rank, is it possible that both primal and dual have multiple solutions?
6
votes
1answer
140 views
Difficulties in Writing the Dual of a Primal Program
I am a student and I am studying the following problem during my spare time. Your comments and suggestions would be helpful.
Given the following primal program:
(Decision variables are $\xi_{v}$, ...
1
vote
1answer
183 views
Questions about weak duality theorem
Following are some corollaries regarding the weak duality theorem.
Consider a constrained problem,
$\min_{x \in X} f(x),$ subject to
$g(x) \leq 0$ and $h(x) =0$.
Its dual problem is $\sup_{u \geq ...
1
vote
1answer
345 views
Weak duality theorem and false corollary
Let $A\in\mathbb{R}^{m\times n}, \ c\in \mathbb{R}^n, \ b\in\mathbb{R}^m$ and consider the linear program $$\max \{ c^Tx : Ax\le b\} \ (1)$$
Its dual is $$\min \{ b^Ty : A^Ty=c, \ y\ge 0\} \ (2)$$ The ...
