Questions on linear programming, the optimization of a linear function subject to linear constraints.

learn more… | top users | synonyms

1
vote
0answers
65 views

computing dual LP in graph matchings

I'm having a trouble converting the following LP to a dual LP. Help on some starting steps would be greatly appreciated!
1
vote
0answers
157 views

simplified Linear programming model with time constraints

Based on my other question, here is a simpler hypothetical exercise that isolates that time constraint issue all together: A farmer has 1000 ha forest that is already at a mature age assumed to be ...
1
vote
1answer
1k views

Will the feasible region always be convex in linear programming? [duplicate]

In linear programming we find a feasible region , is this region always convex? . if a concave region is found where objective is minimization , I think then a solution exists . Advance thanks. ...
1
vote
0answers
323 views

Showing a dual LP solves a primal LP

I originally asked this question: Does solving the LP dual SOLVE the primal LP? It was answered using an example of how the primal and dual solve each other (because of knowledge from strong ...
1
vote
1answer
118 views

Linear programming duality theorem

As far as I know, there are 2 versions of this theorem: 1) $\max \{xc^T: xA \le b, x \ge 0, x \in R^n\} = \min \{by^T: Ay^T \ge c^T, y \ge 0, y \in R^m\}$ 2) $\max \{xc^T: xA \ge b, x \in R^n\} = ...
1
vote
1answer
333 views

Meaning of the bar over $\bf{c}'$ in $\bf{\bar{c}}'=\bf c' -\bf c'_B \bf B^{-1} \bf A\geq \bf 0$?

I am trying to understand the page 87 Bertimas about Linear Programming. The author uses bolding and bars -- now I am starting to think that the bar means something else to vector, bolding apparently ...
1
vote
2answers
592 views

Invertability of submatrix?

If I have a matrix $A \in R^{(m \times n)}$ with $m \leq n$. All rows in matrix a are linearly independent and therefore $A$ has a full row rank. I can decompose matrix $A$ such that $A = [B|N]$ with ...
1
vote
0answers
160 views

1s surpassing 0s in binary strings of odd length

Let $A(k)$ be the number of distinct binary strings of length $2k+1,$ for which the number of $1$s surpasses the number of $0$s for the first time at digit number $2k +1$, i.e., in the final digit in ...
1
vote
2answers
621 views

Sign restriction on the Lagrange multiplier? Why?

Say we are given a linear program where the goal is to minimize $c^Tx$ with the constraints $Ax\ge b$. Why is there a sign restriction on the Lagrange multiplier associated with the active constraints ...
1
vote
1answer
323 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
334 views

Sudoku mathematically, MILP?

My homework contains a word (freely-translated) "target-function" that I should generate somehow for 9x9 sudoku solver with some MILP problem. But I am bit lost what they mean. I have sofar described ...
1
vote
0answers
53 views

A question about $n\times n$ matrix [duplicate]

Possible Duplicate: For every matrix $A\in M_{2}( \mathbb{C}) $ there's $X\in M_{2}( \mathbb{C})$ such that $X^2=A$? Square root of a matrix Let $A$ be $n\times n$ matrix on $\mathbb ...
1
vote
2answers
809 views

Optimizing with Absolute Value Objective Function

max : $w = |q^T y|$ subject to $A y \leq b$ $y \geq 0$ Please describe how one could solve the non-linear programming prob. above by using linear programming methods. I tried changing $y$ to $y' ...
1
vote
1answer
248 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 ...
0
votes
1answer
36 views

How do I convert this into a linear programming problem?

A farmer is planning to raise wheat and barley. Each acre of wheat yields a profit of \$50 and each acre of barley yields a profit of \$70. To sow the crop, two machines, a tractor and tiller, are ...
0
votes
2answers
41 views

LP: An algorithm to decide whether a polyhedron is a subst of another polyhedron

I've encountered the following question which I am unable to solve: $$ P = \{\vec x | A\vec x \geq \vec a\} \\ Q = \{\vec x | B\vec x \geq \vec b\}\\ P, Q \subseteq R^n $$ Find an algorithm to ...
0
votes
0answers
95 views

Linear Programming with Matrix Game

It seems from an easy google of "learning linear programming" that a common way of learning it is to work with Matrices that represent "games" for two players. Here is one I have stumbled across. We ...
0
votes
1answer
2k views

Finding the number of basic/zero variables at an optimal corner point in linear programming

Draw a graph of the following problem $$\begin{align}4x+3y &\leq 180 \\ 7x+4y &\leq 280 \\ y &\leq 40 \\ x &\geq 0 \\ y &\geq 0\end{align}$$ a) If the problem is to ...
0
votes
2answers
690 views

GameTheory, Solve for optimal strategies by solving a system of linear equations

In a book on game theory I saw the following example of a game, a modified version of Roshambo (or Rock-paper-scissors), which is described by the following payoff-matrix: $$ \begin{array}{c|c|c} ...