# Questions tagged [linear-programming]

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

3,588 questions
Filter by
Sorted by
Tagged with
226 views

### Need help defining a Quadratic Programming problem

I have an optimization problem which should be solvable with Quadratic Programming: There are $n$ multiplication coefficients $c_i$ for which optimized values are searched. The coefficients are ...
19 views

### How to find the $K$-nearest neighbor vertexs in a polyhedron defined by a set of linear inequalities?

Consider a polyhedron $\mathcal{P}$ defined by a set of linear inequalities, i.e., $$\mathcal{P} = \left\{ x \in \{0,1\}^N \mid Ax\le b \right\}$$ Suppose $\mathcal{P}\neq \emptyset$. If I have a ...
751 views

### Cycling in Simplex Method - Smallest Subscript Rule

Could someone explain to me how using the smallest subscript rule causes a cycling LP to terminate? At the moment it looks to me that a program would use it to determine whether the matrix from the ...
83 views

46 views

### Solving Ax=b with matrices (bigger than 2 by 2 matrices)

I have been working on creating a program that solves linear systems of equations for the Jacobi and Gauss-Seidel iterative methods. (Link to the methods: https://www.cis.upenn.edu/~cis515/cis515-12-...
19 views

### How to solve linear equations with structured matrices?

Suppose $\mathbf{x}\in R^{m\times 1}$, $\mathbf{X} = [\mathbf{x}\, \mathbf{x}\, \cdots]^\top\in R^{nm\times 1}$ and $\mathbf{b}\in R^{nm\times 1}$ and $\mathbf{A}\in R^{nm\times nm}$. How to solve \...
26 views

### Linear independence and simplex

Let $X:=\{x \in R^n |Ax=b \}$ and $I \subset \{1,...,n\}$ such that, $b\in C([\{a_i\}_{i \in I}$]). Prove that for every set $B \subset \{1,...,n\}$, such that $\{a_i\}_{i \in B}$ is linearly ...
31 views

### Optimize absolute value $\min |x| + |y|$

How do you convert $\min |x| + |y|$ to a linear program? Is this method correct? $$\min w + z$$ $$w >= x$$ $$w >= -x$$ $$z >= y$$ $$z >= -y$$
50 views

### Show that if Phase I of the two-phase method ends with an optimal cost of zero then the reduced cost vector will always take the form $(0, 1)$

Consider a linear programming problem of the form: minimize $c^Tx$ subject to: $Ax=b$, $x\geq0$ where $A$ is an $m\times n$ matrix with linearly independent rows. Show that if Phase I of the two-...
19 views

### Prove that the Basis Solutions of a Linear Programming Problem are the Extreme Points of the Polyhedron of Allowed Solutions

Given a system of $$(\text{P})\ \begin{cases} Ax=b \\ x \ge 0\end{cases}$$ where $A \in \Bbb{R}^{m \times n}, m \le n, \ \text{rank}(A) = m, b \in \Bbb{R}^m, x \in \Bbb{R}^n$. By $x \ge 0$, we mean ...
226 views

### Help solving linear programming problem with simplex method

My friend needs this problem solved, but she doesn't know how. She asked for my help, but the problem is - I don't know either. Could somebody guide me through the process, please?
996 views

### How can I linearize the distance from two points?

I'm studying Operations Resarch and the professor give us the following problem: • There is a 10*10 matrix in which there are 20 villages on random coordinates. • We have to drop two supply packages (...
57 views

### An Application of Farkas' Lemma

The Farkas' lemma I know is: Exactly one of the following systems has a solution. \left\{ \begin{array}{l} Ax=b,\ x\geq0 \\ A^Ty\geq0, \ y^Tb<0 \end{array}...
47 views

### Formulate the mathematical model to find the optimal solution

A, B, C and D are standing on the east bank of a river and wish to cross to the west side using a boat. The boat can hold at most two people at a time. A, being the most athletic, can row across the ...
18 views

### total unimodularity of a matrix

Let G be the node-arc incidence matrix of a given directed network (rows of $G$ correspond to nodes and its columns correspond to arcs). Let $B_1,\dots, B_K$ denote a partition of the nodes of the ...
19 views

### LPP: Simplex Method - Interpreting Solutions

Having trouble keep all the cases straight in my head for the Simplex method in Linear programming problems. What does it mean for a Simplex table solution to be feasible but not optimal? Both ...
40 views

31 views

### Linear program with unknown constraints(just extreme points)

Suppose you are given a set $F$ consisting of $n$ mutually distinct bounded points in $\mathbb{R}^d$. We can define a linear program \begin{align}\max \ c^Tx \\\text{s.t.}\ \ x \in \text{Hull}(F)\...
18 views

843 views

### Conditions for uniqueness of solution to a linear system of equation

Consider a $n\times n$ M-Matrix $\mathbf{A}$ and a $n\times n$ non-negative and non-zero matrix $\mathbf{B}$. Also, let $\mathbf{x}$ and $\mathbf{b}$ be two (non-zero) n-column vectors. I am looking ...
64 views

### Formulating Linear Program: Separating Hyperplane

Consider a polyhedron $P$ that has at least one extreme point. Suppose that we are given the extreme points $x^i$ and a complete set of extreme rays $w^j$ of P. Create a linear programming problem ...
72 views

### Breakdown an integer value to an array of integer maintaining the sum

I am working on a project where I need to breakdown an integer value according to an array of percentage values. My end array must contain integer value and the sum of the array must be equal to the ...
50 views

### Simple Linear Algebra/ Linear Programming Proof: Proving Existence of Vector that satisfies Properties

Hi, I've proved parts a and parts b, but I'm confused on how to prove part c. I think it should really follow directly from parts a and parts b but I'm lost. In part c, are we assuming that $x_j$ is ...
1k views

### Blotto game variation

My smart friend ZWX challenged me to solve the "brainteaser" below, but to my surprise, the problem seems highly nontrivial as I took a closer look. Anyway, the question goes: In a game, both you ...
Not sure how to go on about finding this constraint. The constraint asks for; either both or neither of $x_1$ and $x_2$ should appear. What I have so far is that y can be either binary values $0$ or ...
### How to prove that $c^Tx(\mu)$ is strictly decreasing with $\mu$ in interior point method for LP
Consider the Primal-Dual problem, (P)min $c^Tx$ s.t. Ax = b, x $\geq 0$ (D) max $b^Ty$ s.t. $A^Ty + s = c$, s $\geq 0$ The log-barrier function for (P) is : min \$c^Tx - \mu \sum_{i=1}^n ln(x_i)...