# Tagged Questions

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

38 views

### Trying to sell the most batches of animals using linear programming

I'm trying to sell the most batches of animals... Let's say I have 200 dogs, 100 cats, and 100 ferrets. ...
43 views

36 views

20 views

### Has $\max\{cx:Ax\le b\}$ an optimal solution $x_1=\sqrt 2$ with $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$?

Let be $A\in \{-1,0,1\}^{m*n}$ with exactly one $1$ and one $-1$ and zeroes at each line. $c\in\mathbb{Z}^n$ such that $\sum\limits_{j=1}^{j=n}c_j=0$. $b\in\mathbb{Z}^m$ positive. How to start to ...
29 views

### Extreme Points, BFS, Extreme Directions

I'm trying to prove the two theorems below. 1) Every basic feasible ray of standard-form (P) is an extreme ray of its feasible region. 2) Every extreme ray of the feasible region of standard-form (P)...
27 views

### All faces of the n-dimensional hypercube

I am asked to determine all faces of the $n$-dimensional hypercube $$C_n = \left\lbrace x\in\mathbb R^n \;|\;\forall i\in\lbrace1\ldots n\rbrace : |x_i|\leq1\right\rbrace$$ I already know that the ...
37 views

### Linear Programming, with slack variables [closed]

I'm trying to prove the following statement Show that the set ${\{(x,w) \in \mathbb R^n\times \mathbb R^m \mid Ax \leq0, c^T x >0,w^TA=c, w\geq0 \}}$ is empty, where $A\in \mathbb R^{m\times n}$...
29 views

### Solving Linear Optimization Problem with Shortest path Algorithm

A little while ago I read a wiki about alternating between linear programming and shortest path problem (https://en.wikipedia.org/wiki/Shortest_path_problem#Linear_programming_formulation). I'm just ...
9 views

### Three variable linear diophantine.

Assume I know $a,b,c,d\in\Bbb N$ in $ax+by+cz=d$ and I know there is an unique $x,y,z>0$ such that this holds can I find such $x,y,z$ in $O((\log (abcd))^\alpha)$ time for some fixed $\alpha>0$?
36 views

### Transforming a worded problem into a Linear Problem system of equation

(Advertising problem) Show & Sell can advertise its products on local radio and television (TV). The advertising budget is limited to $£10,000$ a month. Each minute of radio advertising costs $£15$...
8 views

### Why $x_B=\tilde b +\tilde A x_{\bar B};c^Tx=\psi+\tilde c^Tx_{\bar B}$ doesn't describe an optimal solution iif $\tilde c_i\le 0,\forall i$

How to counterprove the assertion that if a feasible dictionnary in the type \begin{cases} x_B=\tilde b +\tilde A x_{\bar B}\\c^Tx=\psi+\tilde c^Tx_{\bar B} \end{cases} describe an optimal ...
72 views

### Linear Programming - The Big M Method - Proof questions [closed]

I'm having difficulties on answering the following questions (first time I'm trying to prove something), any help would be awesome! Thanks in advance. Q: It is possible to combine the two phases of ...
38 views

### piecewise linear minimization equivalent to linear programming

Why is \begin{aligned} & \min\max_{i=1,\ldots,n} & &a_i^Tx+b_i\\ \end{aligned} equivalent to an LP \begin{aligned} & \min & &...
29 views

### Max-Flow Min-Cut

So I have worked out that there is a Max Flow of 10, which therefore means there is a minimum cut also of 10 however how do I draw a minimum cut of 10 on this image? (Something like this - image)
15 views

### Basic Linear Algebra/Root finding question

What is the general method for solving this problem? $\theta_n.1_T'.z_T=0_n$ where $\theta_n$ is a n x 1 vector of parameters that are free to vary, $1_T'$ is a 1 x T vector of ones, $z_T$ is a T x ...
23 views

### Linear programming: choosing entering variable

maximize 10𝑥1 + 12𝑥2 +12𝑥3 subject to 𝑥1 + 2𝑥2 + 2𝑥3 + 𝑥4= 20 2𝑥1 + 𝑥2 + 2𝑥3+𝑥5= 20 2𝑥1 + 2𝑥2 + 𝑥3 +𝑥6= 20 𝑥1, … , 𝑥6 ≥ 0 This is my first step for simplex tableau x1 x2 ...
32 views

### Write the dual LP of the primal LP problem

I have to find the dual of the lp problem given below Minimise $$z=-x_1+\frac43 x_2$$ subject to∶ \begin{array}[t]{l} 2x_1+4x_2\le16\\ -\frac{1}2 x_1-x_2\le4\\ -3x_1+4x_2\ge-24\\ x_1≥0,x_2≤0 \end{...
### $\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ iif it exists $j\in\{1,…,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$
Show a vector $\vec c$ exists such that $\max\{c^Tx:Ax\le b,x\ge 0\}=+\infty$ if and only if it exists $j\in\{1,...,n\}$ such that $\max \{x_j:Ax\le b, x\ge 0\}=+\infty$ I'm only asking for a hint ...
### $\{x\in R^n | Ax \leq b\} \cap \{x \in R^n | Dx \leq d\}= \emptyset$ iff there is a vector $c \in R^n$ such that $c^Tx < c^T y$
Consider two non-empty polyhedra $P := \{x\in R^n | Ax \leq b\}$ and $Q := \{x \in R^n | Dx \leq d\}$. Show that $P \cap Q = \emptyset$ if and only if there is a vector $c \in R^n$ such that \$c^Tx <...