# Tagged Questions

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

70 views

140 views

### Proving that Unit Intersection is NP-complete

I am extremely stuck on how to go about this problem and any help would be so appreciated. We are told to consider the following combinatorial problem: Unit Intersection: Let X = {1, 2,...,n}. ...
90 views

### Degeneracy in Simplex Algorithm

According to my understanding, Degeneracy in a linear optimization problem, occurs when the same extreme point of a bounded feasible region $X$ can be represented by more than one basis, that is not ...
67 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!
238 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 ...
445 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 ...
121 views

965 views

31 views

### Formulating the Dual of a linear program

I have a linear program: Maximize 18x + 12y subject to: x+y <= 20 x <= 12 y <= 16 x,y >=0 I have found ...
28 views

### Use graphical analysis to solve a parameterised LP problem

For $c < 0$, we have no feasible solutions and hence no optimal solutions. For $c=0$, our only feasible solution is $z=0$ obtained by $(0,0)$. For $c > 0$, well... I graphed the ...
70 views

Derive the following variant of Farkas' lemma: For each $mxn$ matrix A and vector $b\in\mathbb{R^m}$ one of the following statements is true: $\exists x\in\mathbb{R^n}$ such that $Ax=b$ $\exists ... 0answers 23 views ### Find if an integer can be written as a sum of n positive integers with only k unique integers k<=10 Given a set of$n$positive integers$A$($n \leq 10^4$), where the number of unique integers is$k$($k \leq 10$), I need to find if a positive integer$W$can be written as a sum of a subset of the ... 1answer 32 views ### Integer Points in Simplex Let $$A_w(d,q):=\left\{{\bf k} \in \mathbb{N}_0^d: \sum_{j=1}^d w_j k_j \leq q\right\}$$ denote the number of non-negative integer points in the$\ell_1$-ellipse with semi-axes of length ... 1answer 89 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 ...
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 ...
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 ...