Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
3,587
questions
0
votes
0answers
19 views
Proof of equivalence of definitions for a vertex of a polyhedron
In these lecture slides from Princeton University I found the following definition of a vertex of a (convex) polyhedron (p. 11).
A point $x\in\mathbb{R}^n$ is a vertex of a polyhedron $P$ if
1)...
0
votes
0answers
11 views
Goal linear-programming in Matlab
$$0v_1 + 0.2v_2 + 0.4v_3 + 0.6v_4 + 0.8v_5 + 1v_6 + 0.8v_7 + 0.6v_8 + 0.4v_9 + 0.2v_{10} + 0v_{11} → 0.46$$
subject to
$$v_1 + v_2 + ···+ v_{11} = 1$$
$$v_1, v_2, . . ., v_{11} ≥ 0 $$
I couldn't ...
0
votes
0answers
13 views
Understanding linear optimization better?
I'm taking a linear optimization class, and I'm having a difficult time formulating an 'integer program' from a problem.
My main problem is taking given information (often tables), how do I declare ...
0
votes
0answers
10 views
Using Matlab for linear programming with unknown objective function [closed]
I'm trying to find the optimal scalar (min) $u$ with an optimal vector $x\in \Re^{k}$ that satisfy:
$A*x<=u*ones(d,1)$
$u>=-1$
Where A is a constraints matrix $A\in \Re^{d*k}$ and some other ...
0
votes
0answers
16 views
Hit-'n-Run Monte Carlo on convex polytope
So, I'm currently trying to implement a MCMC to uniformly sampling hyper-points from the polytope defined as $\mathbb{K}=\{x\in\mathbb{R}^{n}\;\;\text{s.t.}\;\; A\,x=b \}$ in the specific case where, ...
0
votes
1answer
29 views
Conversion of maximin linear program to matrix form [closed]
Ι can't seem to understand how the author converted the problem into such matrix form. Any help? I think i am missing the point of M and u.
Linear Program:
$maximize $$\sum_{i=1}^{|S|} min_{a\in(A\...
1
vote
1answer
30 views
How to solve linear program $\min \langle c, x \rangle$ using Lagrangian?
Given the following linear programming problem
$$
\min \langle c, x \rangle\\
\begin{align}
\text{s.t} \,\,\,\,\,\,\,& \sum_{i=1}^{n}x_i=1\\
&x\geq0
\end{align}
$$
where $x \in \mathbb{R}^n$.
...
0
votes
0answers
18 views
Value of $\alpha$,$\beta$ and $\gamma$ in given LPP problem
By simplex method the optimal table of given LPP problem
$$Maximize\;\;z=\alpha x_1+3x_2$$
subject to
$$\beta x_1+x_2+x_3=8$$
$$2x_1+x_2+x_4=\gamma$$ where $x_1,x_2,x_3,x_4 \geq0$
The ...
0
votes
0answers
46 views
Proving that a polyhedron contains a line if and only if $Ax=0$ has a non-zero solution.
I would like to check if my proof is correct. I do not have much experience of proving stuff so I would appreciate if anyone could point out and fix some mathematical/proving/wording errors if there ...
3
votes
1answer
121 views
+100
Custom Nurse Rostering Problem
I've asked this question also on Operations Research Stack Exchange.
It's a custom nurse rostering problem:
$N$ is a set of nurses;
$S$ is the set of shift-type (morning, afternoon, night, rest)
$...
0
votes
0answers
28 views
This question is related to operation research with a model
I have include the question and can somebody able to help this to find and solve this one with a model. It is somewhat difficult to understand the problem so anyone can help me to solve this problem. ...
1
vote
1answer
42 views
Determine the vertices of $P^{'}=\{ c^{T}x: x \in P\}$ where $P$ is a polytope
Let $P$ be a polytope and $c \in \mathbb R^{n}$, then determine the vertices of $P^{'}=\{ c^{T}x: x \in P\}$
My idea:
Note that since $P$ is a polytope there exists $r > 0$ so that $P\subseteq ...
1
vote
0answers
18 views
A “lifting property” for linear maps on cubes?
Let $L : \mathbb{R}^n \twoheadrightarrow \mathbb{R}^m$ be a linear map that is surjective.
Let $[0,1]^n$ denote the unit cube in $\mathbb{R}^n$,
and let $Z := L([0,1]^n) \hspace{5pt}$ ($Z$ is a ...
-1
votes
1answer
26 views
Operation Research with some recurrence constraints [closed]
I have got this question and i can't think a way to formulate it. So if anyone can help me with this question it will be very helpful
Each year, a shoe manufacturing company faces demands (which ...
0
votes
1answer
51 views
Problem to find the objective function in this problem
I have the next real problem. I have a set of workers $W = \{w_1,\dots,w_{12}\}$ and I have to find the optimal distribution minimizing the jumps of the workers from one jobsite to another jobsite in ...
1
vote
1answer
42 views
Doing a Charnes-Cooper transformation with matrices and an zero-one constraint
I need to solve an assignment problem with the following objective function:
$${\max} \frac{\displaystyle\sum_{i=1}^m\sum_{j=1}^n h_{ij}\cdot x_{ij}}{\displaystyle\sum_{i=1}^m\sum_{j=1}^n c_{ij}\cdot ...
3
votes
1answer
141 views
Does set remain bounded if these integer constraints are removed?
Question:
Let $P$ be a nonempty polyhedron in $\mathbb{R}^n$, and let $l_i, u_i \in \mathbb{R}$ for all $i \in I$, where $I \subseteq \{1,\dots,n\}$.
I'm looking at a problem where the feasible ...
1
vote
1answer
94 views
Find pairs of linearly associated linear combinations
I am trying to figure out if the following problem can be formulated using linear or quadratic programming:
consider a set of $n$ normalized vectors $V = \{V_1,..,V_n\}$ with $V_i \in \mathbb{R}^d$. ...
4
votes
2answers
117 views
A property of a linear image of the cube
Let $[0,1]^3$ denote the unit cube in $\mathbb{R}^3$.
Let $L : \mathbb{R}^3 \to \mathbb{R}^2$ be a surjective linear map,
and let $H := L([0,1]^3)$ (which is generically a hexagon).
Can you provide a ...
0
votes
1answer
48 views
Unboundedness of an LP
Let $(P)$ be an LP of the form
$$\min \{ c^tx\}, \text{ with } Ax \le b,x \ge 0.$$
Show that if $(P)$ is unbounded then there is a vector $d$ such that $Ad=0,d \ge 0$ and $c^td<0$ holds.
...
2
votes
1answer
29 views
A condition for an LP to be unbounded
Let $(P)$ be an LP of the form
$$min \ c^tx \text{ with } Ax \le b,x \ge 0.$$
Show that if there is a vector $d$ such that $Ad=0,d \ge 0$ and $c^td<0$ $(P)$ is unbounded .
Could you help ...
0
votes
1answer
35 views
When does there exists $x\geq,\neq 0$ s.t. $(\sum_{i}A_{i}\alpha_{i})x\neq 0$ $\forall$ $\alpha_{1},…,\alpha_{k}\geq 0$ s.t. $\sum_{i}\alpha_{i}=1$
Let $A_{1},...,A_{k}$ be $n\times n$ matrices. When does there exist a vector $x\geq,\neq 0$ such that $(\sum_{i}A_{i}\alpha_{i})x\neq 0$ for all $\alpha_{1},...,\alpha_{k}\geq 0$ such that $\sum_{i}\...
1
vote
0answers
53 views
Why does standard quadratic programming contain $\dfrac{1}{2}$ in the objective function?
Does the $\dfrac{1}{2}$ provide any of computation convenience?
0
votes
0answers
12 views
Algorithm to solve 'user optimum' 'polygamic' stable marriage problem: Optimally assign travellers to shared rides.
I am looking for inspiration to reformulate the classical assignment problem into something behaviourally richer (closer to Nash equilibrium or or stable marriage problem).
I find it tricky to ...
3
votes
1answer
61 views
Solving for $x_i$ and $y_i$ in this system: $(\mu-x_1)y_1+(x_2-\mu)y_2=d$, $x_1y_1+x_2y_2=\mu$, $y_1+y_2=1$
Suppose we have a system of equations:
\begin{align}
(\mu-x_1)y_1+(x_2-\mu)y_2&=d \\
x_1y_1+x_2y_2&=\mu\\
y_1 + y_2 &=1\\
\end{align}
The decision variables are $x_1$, $x_2$, $y_1$, $...
0
votes
1answer
33 views
Propositions about Multiple Solutions in LP
I'd like to check if the following statements are true about optimizing a linear objective function $f$ over a convex space. For the purpose of the problem, the space over which we are optimizing is ...
0
votes
1answer
32 views
Linear programming: reduce a constraint that includes a minimum
I have an almost linear programme. However one of the constraints has a form $z = min(x,y)$ (all the other things are linear in the model). Is there a way to substitute this with something (or ...
2
votes
1answer
36 views
Converting inequalities into equalities by adding more variables
I was trying to solve a rather large system of equalities and inequalities and was stuck, until I realized that converting the inequalities into equalities by adding more variables showed that zero-...
0
votes
1answer
32 views
Distribute N balls into M bins
Problem 1 :-
There are N bins and M balls. Each Ball have a score. Problem is to distribute M balls into N bins such that -
1. Average score of balls in Bin 1 = Average score of balls in bin 2 and ...
0
votes
0answers
24 views
Resource allocations
There is a certain factory and there is time for which it is necessary to consume a certain amount ($ X $) of a resource. At each specific period of this time (and the time is discrete), a factory can ...
2
votes
1answer
89 views
Convert a Non-Linear Constraint of Integer and continuous variables to a Linear Constraint for programming
I have nonlinear constraints:
\begin{equation}
\sum_{i} \dfrac{X_{ij}^{t}}{r_{ij}} \le T_{disp1} * w_{t} * NN_{j}^{t} * \overline{\mu}_{j} \quad \forall j \ ,\ t
\end{equation}
\begin{equation}
O_{...
3
votes
1answer
27 views
Optimal control problem in non-standard form with many integral constraints
I am trying to solve the following optimization program and I am hoping for some help as I am stuck:
$\min_{R_{t}\in[0,1]}\,\,\int_{0}^{\tau}e^{-t}R_{t}\,dt$
s.t. $e^{-t}R_{t}-\int_{t}^{\tau}e^{-s}...
3
votes
2answers
54 views
Prove that a polyhedron in the $\mathcal{H}$-representation is bounded
Given a polyhedron $P$ specified by a set of linear constraints $P=\{x \in \mathbb{R}^n \mid Ax \le b \}$, what are the conditions on the matrix $A$ such that $P$ is bounded?
I have the following ...
0
votes
0answers
39 views
How to optimize in an assignment problem when the objective function is a quotient?
I know that if I had an assignment problem with an objective function that looked like this
$${\max} \sum_{i=1}^m\sum_{j=1}^n c_{ij}\cdot x_{ij},$$
I could use linear programming to solve it. But ...
1
vote
0answers
27 views
Is there a standard way to see if the solution set to a systems of linear equations crosses a given region?
I'm interested in the following question:
Determine if there exists a solution to linear system $A\vec{x} = \vec{b}$ that lies in region $R$.
Is there a general procedure for doing so? Currently, ...
0
votes
0answers
31 views
Recursive solution of linear optimization with incrementally added dimensions and constraints
I'm interested in understanding whether there is a nice recursive-type relationship between solutions of linear optimizations problems of lower and higher dimensions.
E.g., Fix $a,b,c,d,e,f\in \...
0
votes
1answer
31 views
Nursery wants to maximize the total profit
A nursery planted deciduous and evergreen shrubs in an area of $30,000 \,\rm{m}^2$. An evergreen shrub requires $1 \,\rm{m}^2$ and a deciduous $2 \,\rm{m}^2$. The two types of shrubs have different ...
2
votes
1answer
64 views
When does a given system of linear inequalities form a bounded convex polytope?
We know that a Closed Convex Polytope may be regarded as the set of solutions to the system of linear inequalities:
$$\begin{array}{ccc}{a_{11} x_{1} +a_{12} x_{2}+\cdots+a_{1 n} x_{n}}\leq b_{1} \\ {...
2
votes
0answers
31 views
Theta-Ratio of a Simplex Method for a degenerate solution, are they always equal?
Are the $\theta$-ratios of two degenerate solutions always equal?
So as to say:
If we know two unique points yield the same objective value, must their $\theta$-ratios always be equal?
For two ...
0
votes
0answers
18 views
Special Case of the Two Phase-Method
I'm sorry this question must be slightly vague.
In the two-phase method, my general understanding is that you try to exit your Aritifical Variables to make your Auxillary problem to $0$.
But what ...
0
votes
1answer
50 views
Prove that exactly one of the systems has a solution
Let $A$ be an $m$x$n$ matrix, $B$ $l$x$n$ matrix and $c\in R^n$.
Prove that exactly one of the systems has a solution:
i)$$Ax\leq0,\:\: Bx=0,\:\: c^Tx>0,\:\: x\in R^n$$
ii)$$A^Tp+B^Tq=c,\:\:p\geq0,...
1
vote
1answer
28 views
Linear Programming Price Change After X Units Sold
I have a question regarding writing some formulas for LP. How would you code the price change after X number of units sold.
So lest say the base price for the first X units sold is £5 and then there ...
1
vote
1answer
55 views
Linear Programming problem of accepting reservations on different fare classes to maximize revenue
this question has my stuck, I am unsure on how to incorporate the some of the information into constraints and without them the answer seems a bit silly. Below is the question, please let me know how ...
2
votes
0answers
48 views
Merging two line equations having similar angle into a new one [duplicate]
I would like to merge two lines having a y = mx + b equation with very close angles. I am simply comparing their angle difference, then I create a new line passing ...
0
votes
0answers
9 views
what pivot should I choose when introducing new constraint trying to apply the Dual Simplex Method and all $b_i$ are positive?
There is an LP.
It is already given that $x_1 = 0, x_2 = 1$ is the optimal solution.
First I find the corresponding simplex tableaux. Then what I don't get is how to apply the dual simplex method when ...
1
vote
0answers
27 views
Local branching in Benders Decomposition
I am trying to understand how local branching is used in Benders Decomposition. I was wondering if someone could kindly explain me how exactly local branching works.
If my understanding is correct, ...
0
votes
1answer
71 views
A question on algebraic inequalities [closed]
Given
\begin{align}
X+Y&\leq C_1\\
Y+Z&\leq C_2\\
Z+X&\leq C_3
\end{align}
Find the maximum of $X+Y+Z$, where $X, Y, Z$ are non-negative integers and $C_1, C_2, C_3$ are positive ...
1
vote
1answer
24 views
Asked to find the dual of a given primal problem. (Is my solution wrong? Solutions included)
I'm not understanding how there can be two separate solutions to this problem. I've doubled checked and followed all the steps but I'm assuming my answer is wrong but similar?
Sorry, I don't have ...
2
votes
0answers
24 views
In a Linear Programming Problem, how is Degeneracy affected by the number of variables and constraints?
In an LPP, with m constraints and n variables.
How does the number of constraints and variables affect the degeneracy of the system?
-1
votes
1answer
43 views
Need help formulating this linear program [closed]
A company's pension fund manager must invest a maximum of $300,000 in bonds and stocks in order to obtain the highest possible return on investment. However, in order to obtain a risk-adjusted ...
