# Tagged Questions

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

46 views

### Maximize system of linear equations

Suppose you have the system $$\begin{bmatrix} 4 & 3\\ 1 & 7\\ 5 & 9\\ 2 & 4\\ \end{bmatrix} \begin{bmatrix} x\\y\end{bmatrix}=\begin{bmatrix}b_1\\b_2\\b_3\\b_4\end{bmatrix}$$ How ...
19 views

### AMPL - Step by Step mode

Is there a way to solve a problem using AMPL in a step by step(or a verbose, or a debug) mode? Preferably showing all basis exchanges? The manuals of AMPL make reference to script development, but i ...
40 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

40 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 ...
31 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}$...
32 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$?
49 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 ...
95 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 ...
39 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 & &...
30 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 ...
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{...