# Questions tagged [linear-programming]

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

236 questions
Filter by
Sorted by
Tagged with
263 views

### Operations Research - Optimal Transport Routes

I have a problem in which there are 4 vessels available to transport people from 3 different bases back to a main base. Vessel 1 has a capacity of 50, can make 6 round trips and is allowed to visit ...
2k views

15k views

337 views

### Solving a linear program thanks to complementary slackness theorem

Using the complementary slackness theorem, say if the following basis optimal: $$x_1*=0=x_5*,x_2*=4/3,x_3*=2/3,x_4*=5/3$$ \begin{cases} \max & 7x_1 &+6x_2&+5x_3&-2x_4&+...
224 views

### Linear dependence in Carathéodory's theorem (convex hull)

I don't get this step in proof of Carathéodory's theorem (convex hull) Why: Suppose k > d + 1 (otherwise, there is nothing to prove). Then, the points $x_2 − x_1, ..., x_k − x_1$ are linearly ...
173 views

### Linear Optimization/Linear Programming - Vending Machine Problem

I have a question about the formulation of a LP involving fulfilling orders of a vending machine. We have a vending machine which dispenses medicine to its patients. We assume that we have a list of ...
1k views

### Minimization of log-sum-exponential function subject to constraints.

I would like to minimize the following function: $f(x)=log(e^{-x_1}+..+e^{-x_n})$ Subject to: $\sum_{i=1}^{n}{x_i}=1$ $0 \leq x_i \leq 1$ So far I have discovered the following: If all the $x_i$'...
70 views

1k views

### Indicator Variable, Mixed Integer Linear Programming

Assume $x$ is a real variable, and $0\leq x \leq1$. Besides, $y$ is a binary random variable. I need a linear program that: if $y$ is $1$: $x>0$, if $y$ is $0$: $x=0$ I know the following ...
499 views

### Meaning of the bar over $\bf{c}'$ in $\bf{\bar{c}}'=\bf c' -\bf c'_B \bf B^{-1} \bf A\geq \bf 0$?

I am trying to understand the page 87 Bertimas about Linear Programming. The author uses bolding and bars -- now I am starting to think that the bar means something else to vector, bolding apparently ...
163 views

### Selection of Pivotal Elements in SIMPLEX method

I want to solve the following LP problem by using the simplex method $Maximize$ $p = x + y +3z$ subject to $$x + y +z \leq 15$$ $$x + 3y +2z \leq 45$$ $$2x- y -z \leq 15$$ $$2x + y +z = 12$$ 4x ...
97 views

### Trying to set up a linear programming problem

Attempt Let $x_1$ be the number of hours to produce product 1 during assembly and $x_2$ be the number of hours to produce product 1 during finishing. Notice that $\frac{1}{2} x_1 + x_2$ is the ...
### Find an optimal solution to a linear program in $O ( n \log n )$
Problem: Given $c \in \mathbb { R } _ { + } ^ { n } , a \in \mathbb { R } _ { + } ^ { n }$ and $\gamma \in \mathbb { R } _ { + } ,$ design an algorithm which, in $O ( n \log n )$ operations, computes ...
### After Farkas Lemma, transforming $(A, -A)x = b$ into $Ax=b$
Let $A \in \mathbb R^{m\times n}$ and $c \in \mathbb R^{m}$ Show that either (i) $Ax=c$ has a solution or (ii) $c^{T}y=1$ with $A^{T}y = 0$ has a solution. My proof: Let (ii) be satisfied iff ...