Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
0 votes
1 answer
42 views

Is my method equivalent to my lecturers?

In lectures we were shown how to 'breakdown' a piece-wise linear function so that it can be used as part of a linear program. Now, my lecturer wrote the function as $a=f(x)=\max(0,55x-11000)$ and in ...
user avatar
0 votes
1 answer
19 views

Is $\{ x \in \mathbb{R}^2 \mid x \ge 0, v^Tx \le 1 \quad (\forall v \in \mathbb{R}^2 : \lvert\lvert v \rvert\rvert = 1) \}$ a polyhedron?

I am working on the following exercise: Consider $$P := \{ x \in \mathbb{R}^2 \mid x \ge 0, v^Tx \le 1 \quad (\forall v \in \mathbb{R}^2 : \lvert\lvert v \rvert\rvert = 1) \}$$ Is $P$ a polyhedron? ...
user avatar
  • 2,462
1 vote
0 answers
8 views

Is there a result on the maximum value of the dual variable for a parametric LP in terms of the parameters of the LP?

I am working with a linear program of the following kind: \begin{array}[t]{l} \min c^{\top} x\\ s.t.\\ \quad A x = b\\ \quad 0 \le x \le x^{u} \end{array} Can I find out the upper limit of the shadow ...
user avatar
  • 11
1 vote
1 answer
20 views

Theorem of Alternatives proof only one of the systems is solvable

Let $ A \in R^{nxm}$, $x \in R^n$, $c,y \in R^m$ show that, either I) $Ax=c$ II) $A^Ty=0, c^Ty=1$ is solvable I'm completely new to the theorem of alternatives, so my attempt is: If I is solvable ...
user avatar
1 vote
0 answers
29 views

The effect that slightly increasing a variable has on the optimal solution

I am going through a past exam paper that doesn't have a mark scheme provided. I am struggling to figure out how you would do part b. Can anyone explain how you would go about getting an answer for ...
user avatar
1 vote
1 answer
51 views

how can I linearize a constraint of the form sum(min(x(i),y(i))) for a linear optimisation problem?

I have an linear optimisation problem and I'd like to impose a constraint of the following form: $∑_{i=0}^N min⁡(x_i,y_i)≥C$ where x_i,y_i are rational numbers greater or equal to 0. how can I ...
user avatar
2 votes
0 answers
21 views

In this simplex algorithm tableau, what are the basic variables?

At some point while running the simplex algorithm, we find this tableau: Would I be correct in saying that at this stage, our basic variables are $x_4,x_3,x_6$ as they are the only ones not equal to ...
user avatar
0 votes
1 answer
57 views

Proof that markov chain equilibrium using Farkas' lemma

Given a transition matrix for markov chain $ P \in \mathbb R^{dxd} $ such that $$ P_{i,j} \geq 0,\quad 1 \leq (i,j) \leq d, \quad \sum_{j=1 \in d }P_{i,j} $$ and $i=1,....,d$. Let $ x_{0}$ be ...
user avatar
0 votes
0 answers
22 views

How to find such a Markov matrix?

Suppose $A$ is a $m\times n$ Markov matrix, and $C$ is a $m\times k$ Markov matrix. How to decide (analytically or numerically) whether there is a $n\times k$ Markov matrix such that $AB=C$? I feel ...
user avatar
  • 175
-3 votes
0 answers
36 views

code a program in matlab (or python) that: [closed]

generate 10 random values ​​from 0 to 100 Place these 10 values ​​(in order) on the diagonal of a square matrix that we will call A. Generate a 10x10 matrix C with random values. In the problem, each ...
user avatar
0 votes
0 answers
22 views

a set of linear constraints defines a smaller and smaller set, to what extent?

Let's say I have a set of linear constraints over $x \in \mathbb{R}^d$ in the form of $Ax \le b$. Is there a way to know the ``volume'' of the feasible set (in the sense that every two points in the ...
user avatar
  • 143
0 votes
0 answers
36 views

How to graph an interval of real numbers?

Assume that intergers $m$ and $n$ satisfy $2|m|+3|n-1|\leq 7$. $m+n$ is maximum when $(m,n) = (3,?), (?,?)$ and its maximum value is $?$ given the above question the first thing i tried was ...
user avatar
  • 47
1 vote
0 answers
17 views

Stochastic Portfolio Optimization with Recourse

I am given the following problem from a tutorial in my course: (Portfolio Optimization with Recourse). You have £10,000 to invest (without short selling) in a portfolio composed of eight leading ...
user avatar
0 votes
2 answers
34 views

Finding containment between convex polytopes

Given 2 polytopes, either by their H-representations: $p_1: Ax\le b, p_2: Cx\le d$, where $b,d$ are real-valued vectors, $A,C$ are real-valued matrices, or by their V-representations: $p_1 = conv(p_{...
user avatar
0 votes
1 answer
27 views

Find intersection of two lines

I have two lines and i have coordinates of starting point and ending point of both lines. I need to find the intersection point on four different case. These are the four cases:- From image below, I ...
user avatar
0 votes
1 answer
14 views

Integer linear Programming - CVRP

I am dealing with a CVRP with multiple vehicles. I am struggling to come up with a formula for the constraint that each node with a non zero demand must be visited by one vehicle, once. Im trying to ...
user avatar
0 votes
0 answers
28 views

How to find the dual of the curve fitting

I am given the following curve fitting function: $b(a_{i1},...,a_{in}) = \Sigma_{i=1}^{n}a_ix_i$ so that for several inputs, the output $b(a_{i1},...,a_{in})$ is approximately equal to a given value $...
user avatar
1 vote
1 answer
32 views

Computing the dual of an LP with equality constraints

I am having a linear program in the form : \begin{cases} \min_x\ \ -5x_1 + 27.5x_2 + 4.5x_3 + 12x_4\ \ \mathrm{s.t.}\ \\ \ \\ \qquad\qquad 0.25x_1 − 2.75x_2 − 1.25x_3 + 4.5x_4 + 0.5x_5 = 0\\ \...
user avatar
0 votes
0 answers
31 views

Solving a linear programming problem with 26 variables - is it possible?

I need to minimise two equations with 26 variables relative to some constraints. I am not very familiar with linear programming, but understand that it is probably the correct way to approach my ...
user avatar
  • 11
0 votes
1 answer
45 views

Polyhedra intersection

If $A$ and $B$ are polyhedra, how do we show that the intersection $A ∩ B$ is a polyhedron. Does the same apply if they are both polytopes, will the intersection $A ∩ B$ also be a polytope? The ...
user avatar
  • 47
0 votes
0 answers
27 views

How to assign vertices to graph to minimize total weight?

I'll preface by saying this is probably an easy question, have mercy! We have an unweighted simple graph $G \in (V, E)$ and a complete weighted graph $K \in (V', E')$ with the same number of nodes as $...
user avatar
  • 33
2 votes
1 answer
33 views

Convex hull and optimal solutions

Consider the LP problem: $max$ $3x_1 + 2x_2+x_3$ $s.t$ $3x_1 + 4x_2 + x_3 ≤ 6 $ $2x_1+x_2 + 3x_3 ≤ 5 $ $x_1,x_2,x_3 ≥0$ I have solved the problem and found that the optimal value is 6 at $x=(2,0,0)$. ...
user avatar
  • 47
4 votes
2 answers
169 views

one linear programming problems and solutions

we have a linear programming problem with following constraint: $x_1-x_4 \leq -1$ $x_2-x_1 \leq -4$ $x_2-x_3 \leq -9$ $x_3-x_1 \leq 5$ $x_4-x_3 \leq -3$ I solve this question until: $1 \leq x_4-x_1 \...
user avatar
0 votes
1 answer
30 views

fractional coloring of a matroid

Given a matroid $M$, a fractional coloring $f$ is a function from the collection $I(M)$ of independent sets of $M$ to non-negative real numbers such that for any $v$ in the ground set, $$\sum_{A\in I(...
user avatar
  • 2,069
0 votes
0 answers
21 views

Looking for reference for minimax solution of 2p zero-sum game, NxN choices

The game in this wikipedia section https://en.wikipedia.org/wiki/Minimax#Example, also see here at Math.SE Minimax solution for Zero-Sum Game, is easily generalized to an NxN game. Let A be an NxN ...
user avatar
0 votes
0 answers
35 views

$\min\{200x+100y\}$ such that $x+3y\geq12$, $3x+2y\geq12$, $x\geq0,y\geq0$

$\min\{200x+100y\}$ such that $2x+3y\geq12$, $3x+2y\geq12$, $x\geq0,y\geq0$ Attempt. I am using the lagrangian approach to attack this problem and I know the optimal solution is $(0,6)$, but I cannot ...
user avatar
  • 787
-2 votes
1 answer
18 views

Duality optimisation

enter image description here Questions. what does that symbol mean between Ax and b? he has moved the b to Ax-b in the subject too section is this because all constraints have to be on one side ? if ...
user avatar
0 votes
1 answer
28 views

On the non-sufficiency of total unimodularity of the constraint matrix in the definition of an integer polytope

Crossposted at Operations Research SE Is there an example of an $m\times n$ integer matrix $A$ and an integer vector $b\in \mathbb {Z}^{m}$ such that the polyhedron $P := \{ x\in \mathbb {R}^{n} \mid ...
user avatar
1 vote
1 answer
147 views

Point in Polytope?

Context: This question is somewhat identical to this on MathOverflow, it’s different in that it only focuses on the formula of the solution to the underlying problem. Suppose I have a convex hull $H$ ...
user avatar
  • 177
0 votes
0 answers
18 views

Simplex: LP with equality constraints : do I need slack variables?

I am confused about simplex method : I have read from various resources that I need my LP to be in standard form. Then when we have the standard form, we introduce slack variables to turn inequality ...
user avatar
0 votes
1 answer
22 views

Excel Solver Linear Optimization : Formula Debugging

I am trying to get a optimization model to work correctly. The background is to use the solver to find a circuit (AC or DC) that would minimize cost. I am trying to use binary variables so the ...
user avatar
  • 1
2 votes
2 answers
51 views

L1 Objective as a Linear Program

I am trying to determine how the following simple L1 objective can be written as a linear program: Minimize $(\| Mx - p \|_1) + (\| Mx - q \|_1)$ wrt to $x$ such that $\| x \|_1 = 1$ and all elements ...
user avatar
0 votes
0 answers
15 views

Sign of last row in tableau

In a previous exam I have the question: The solution given is: Can someone please explain to me why the last row in the tableau is z, instead of -z? I'm under the impression that if I leave the last ...
user avatar
0 votes
0 answers
45 views

Discrete Optimization Problem: What is the optimal course schedule?

Linda Johansen, an incoming first-year MBA student, would like to determine her course schedule for her first two semesters of business school. Linda has created a list of twenty potential courses ...
user avatar
0 votes
0 answers
24 views

Primal and Dual Linear Program

Consider the linear program (P) and its dual (D) \begin{align*} \text{(P) minimize} &\quad \textbf{c}^T\textbf{x} &\text{(D) maximize} &\quad \textbf{b}^T\textbf{y}\\ \text{subject to} &...
user avatar
0 votes
1 answer
18 views

Why is $Ax \leq b$ is equivalent to $A'x' = b'$ and $x'\geq 0$

I am getting confused in LP conversion from one form to another. Say, I have an LP of the form $Ax\leq b$ and I want to convert it into the form $A'x'=b', x'\geq 0$, how to do this? For example let's ...
user avatar
  • 106
2 votes
1 answer
27 views

Equivalent representation of a system of linear (in)equalities

I am reading about the equivalence between zero-sum games and LPs from Adler's 2012 paper. Right after lemma 3, he writes that it is equivalent to represent $$ (\mathsf{A}) := \{x:Ax=b\} = \{x:Ax\geq ...
user avatar
  • 2,370
0 votes
1 answer
22 views

How can I convert non-linear constraint to linear one?

Problem: Suppose I have $n$ finished products and each product has its own completion time, such as C$_i$ (C$_i$=completion time of product $i$, where $i=\{1,2,...,n\}$). These products will be ...
user avatar
  • 15
0 votes
0 answers
17 views

dual of a LP constraint

Consider the minimization problem minax1+bx2 s.t: x1(i,j)-sum(i,x1(i,j))<=0 for each j that both varibales in the constraint is equivalent. so what is the constraint for x in the dual problem? how ...
user avatar
0 votes
0 answers
24 views

Reduce minmax problem to linear problem

A is mxn matrix, c is n vector and b is m vector. Convert following problem to linear problem $$max_{x \ge 0} min_{y \ge 0} (c^Tx - y^TAx + b^Ty)$$ I think I can write min to max by just changing sign ...
user avatar
1 vote
1 answer
60 views

Linear Programming - Motivation behind the Dual Simplex Method

I am trying to understand the motivation behind the Dual Simplex Method. However, I have run into some roadblocks while understanding the rationale behind the Dual Simplex Method. This is my current ...
user avatar
  • 8,444
3 votes
2 answers
61 views

How many slack variables need to be introduced?

So I was trying to solve this exercise (from DPV book) I modeled the problem as such: minimize : $4x_1 + x_2 + 2x_3 + 3x_4 $ s.t: $ x_1 + x_2 = 8 $ (Mexico's production) $ x_3 + x_4 = 15 $ (Cansa's ...
user avatar
0 votes
1 answer
20 views

two linear programs, one unbounded, one feasible and bounded

I've been biting my teeth out, trying to find an example of the following. Is it even possible? Consider two LPs $$ (P1) \ \max \{c^Tx|Ax\leq b, x\geq 0\} \\ (P2)\ \max \{c^Tx|Ax\leq \tilde{b}, x\geq ...
user avatar
0 votes
0 answers
14 views

Linear optimization problem with affine subspaces

I have this fun linear optimization problem for you! Let $u$ and $v$ in ${\mathbb R^n}$ be two non-collinear vectors where $\|\vec u\|=1$ and $\|\vec v\|=1$ and let $\alpha$ and $\beta$ two real ...
user avatar
  • 1
0 votes
1 answer
20 views

Projection onto union of two affine subsets

Let $\ C_1=\{\ x\in {R^n} \ |\ \langle u,x\rangle\leq\alpha\ \}\ $ and $\ C_2=\{\ x\in {R^n} \ |\ \langle u,x\rangle\leq\beta\ \}. $ Give the orthogonal projection of $x\in{R^n}$ onto $\ C_1\cup C_2....
user avatar
  • 1
1 vote
2 answers
64 views

Minimize sum of absolute value with linear constraint

Consider a minimization problem: $$ \begin{aligned} & \min \sum_{i=1}^n |x_i|,\\ & A x = b, \end{aligned} $$ where $A$ is an $m\times n$ matrix of rank $m$. I know that the minimum points ...
user avatar
0 votes
0 answers
46 views

Representation theorem linear programming

What I have read is: The General Representation Theorem states that every point in a convex set can be represented as a convex combination of extreme points, plus a nonnegative linear combination of ...
user avatar
  • 1,424
0 votes
0 answers
13 views

What is a general way to find Direction of unboundedness of a linear program.

One of the way I know is Ad=0 then d is direction of unboundedness where A is the constraint matrix and Ax=b. In my exam there was question, to first convert problem into standard form, determine 2 ...
user avatar
0 votes
0 answers
26 views

1-norm maximization - is this a linear program?

I have two conditional probability distributions $\tilde{Q}_{Y|X}$ and $Q_{Y|X}$ and I am trying to find the probability distribution $P_X$ that maximizes the quantity below $$\|(\tilde{Q}_{Y|X}(y|x) -...
user avatar
  • 1,528
0 votes
0 answers
44 views

Summation Linear programming Problem

Im trying to solve the following problem First I write out the objective function with t=1=October,...,4=January: $x_t=$ no. of units produced during month t $i_t=$ the amount of inventory at the ...
user avatar

1
2 3 4 5
93