# Questions tagged [linear-programming]

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

3,561 questions
Filter by
Sorted by
Tagged with
28 views

### Prove that any hyperplane and halfspace in $\mathbb{R}^n$ is a convex set

$a)$ Prove that a hyperplane in $\mathbb{R}^n$ is convex. Recall that a hyperplane is a set of the form $\{x\in\mathbb{R}:a^Tx= b\}$ for some vector $a$ and scalar $b$. $b)$ Prove that a ...
36 views

### Expressing a norm as an LP

Let $\mathbf{x}\in \mathbb{R}^n$, and let $\|\mathbf{x}\|_L$ be the sum of the $L$ largest absolute components of $\mathbf{x}$. That is to say, write the (absolute values of) components of $\mathbf{x}$...
21 views

42 views

55 views

### Linear Program such that Simplex (w/ any pivot rule) takes exponential time?

I had this exam question last semester, and it's still bothering me: For every natural number $n$, you want an LP (not necessarily with $n$ inequalities) such that simplex cannot solve it in ...
13 views

### How to tell if linear programming dictionary is unbounded using ratios?

I don't really get how they got negative for the ratio 2/5. Is it because if they make $x3$ a leaving variable it'll become $x3$ = -5/2 + (3/2)$x1$? How does non-positive ratios make a problem ...
28 views

### Linear Program Modelling Coinset pay amount $k$

You are given a coinset ov values c1,...,cn and a target value of k you need to pay. For each i element {1,...,n} let ni be the number of coins of value ci in your wallet. You want to pay (or overpay) ...
$x_{t}$ is a decision variable bounded by some constraints and $t=1,2,3..24$ If at some point in t, the value of $x_{t}$ changes then the value must not change for ATLEAST the next 3 hours. After ...