Questions tagged [linear-programming]
Questions on linear programming, the optimization of a linear function subject to linear constraints.
4,075
questions
0
votes
0answers
9 views
How to derive the dual for LP like this?
I know how to derive dual for normal LPs, but what if we are unlikely to have something like this:
maximize z
s.t. z < 3y-2
1 < y < 2
, where ...
0
votes
1answer
14 views
Filling a piecewise continuous linear shape with a constant volume of liquid
We have a piecewise continuous linear function (representing topography). The shape is to be filled with a constant volume of liquid (representing an ocean). How can we find the 'sea level', and where ...
0
votes
1answer
13 views
Converting set of inequalities to LP
I have a problem where I have a bunch of inequalities in the form:
$a_{1,1}b_{1,1} + a_{1,2}b_{1,2} + ... + a_{1,n}b_{1,n} >
a_{2,1}b_{2,1} + a_{2,2}b_{2,2} + ... + a_{2,n}b_{2,n}$
$a_{2,1}b_{...
0
votes
0answers
21 views
Where did we use Ax=c to prove local min is global min
Prove that a local min is also a global min
I understood all the steps in this problem and I was able to prove a, b and c in the hint. But I don't understand where did we use the fact that Ax=c. I ...
2
votes
0answers
26 views
Can this dual LP be solved?
The primal problem is as follows:
$\min w=2x+4y+5z+3q$
subject to
$$
\begin{split}
-x - 2y + 2z &\geq 40\\
-3x - 2z - q &\geq -100\\
x - 2y - z + 4q &\geq 50
\end{split}
$$
I have ...
0
votes
0answers
36 views
Why is it that a 3x3 math puzzle can have no more than 5 unknowns?
I'm going through the Brillient.org Algebra 1 course, and I came across a problem that I don't think was well explained, and I'm hoping I can find more insight here.
So this type of problem, for some ...
2
votes
0answers
50 views
Pools of problems
Using a pool of problems, 16 tests will be formed.
Every test should have the same number of problems.
Any problem should be included in at most 8 tests.
For every 4 tests, there should be at least 1 ...
0
votes
0answers
19 views
structured least square optimization [closed]
I want to solve the following optimization
How to solve this problem?
0
votes
1answer
23 views
Assigning tasks to minimize cost
I have a set of jobs that must be done on a given day in sequence. $J_1, J_2, J_3$, with deadlines $D_1, D_2, D_3$. There are three workers $W_1, W_2, W_3$ that can execute the tasks each one with ...
0
votes
0answers
31 views
The transportation problem with uncertain (and, in general, linearly interdependent) supply- and demand values
I'm looking at a transportation problem:
$$\min_{x_{ij}} \sum_{i=1}^{m}\sum_{j=1}^{n} c_{ij}x_{ij}$$
subject to
$$\sum_{j=1}^nx_{ij} = s_i, \mbox{ for all } i=1,...,m.$$
and
$$\sum_{i=1}^mx_{ij} = d_j,...
0
votes
0answers
28 views
Lower-bound for distance between origin and polyhedron
Let $x_1,\ldots,x_n \in \mathbb R^d$ (assumed to be linearly independent) and let $y_1,\ldots,y_n \in \mathbb \{-1,+1\}$. Define $\Delta \ge 0$ by
$$
\Delta := \inf_{w \in \mathbb R^d,\;b \in \mathbb ...
0
votes
0answers
27 views
Transbordo Localización
If someone could help I will thank him or her a lot, its a problem of linear programming, im taking a course in Spanish, but I don't understand it , they are using Excel solver and want me to use ...
-1
votes
1answer
12 views
What is the upper bound for edges that are not going in or out of node 1 in this graph?
I have the following graph with the following problem:
We want to obtain a Hamiltonian cycle by supplying all nodes with 1 unit of flow. Initially the node 1 will send 4 units of flow through one and ...
0
votes
0answers
19 views
Prove that the feasible area has one or two extreme point. [closed]
min $z = cx$
s.t. $Ax = b$;
$x$ $\ge$ $0_n$
Suppose that $rank(A)= n-1$. Prove that the feasible area has one or two extreme point
0
votes
1answer
17 views
Is it possible to know if the feasible region is unbounded without drawing it?
Given the following set:
$$ -x_1 + x_2 = 4$$
$$ x_1 - 2x_2 + x_3 <= 6 $$
$$ x_3 >= 1 $$
$$ x_1,x_2,x_3 >= 0 $$
Without drawing the feasible region can I know if it is bounded or unbounded?
-2
votes
0answers
11 views
How to identify the constraints of this exercise on linear programming? [closed]
A salmon industry must provide food to its fish
with a diet that considers a minimum of 24 ml. of a component A and 25
ml. of a component B. Two types of pellets are marketed on the market
(Salmon ...
0
votes
1answer
32 views
How do you enter a variable>variable inequality constraint into a Simplex method calculator?
In 2-variable linear programming problems, constraints can take the form of either $aX+bY < C$ or $mX > nY$. Both lines graph to form linear bounds so the graphical solution applies. But in 3+ ...
0
votes
0answers
28 views
solve the linear problem with graphic method.
\begin{equation}
2x_1 + 3x_2 \geq 6
\\-5x_1 + 9x_2 \leq 12
\\ 2x_1 - 3x_2 \leq 6
\\ x_1 + x_2 \leq 5
\\ 0 \leq x_1 \leq 4
\\ 0 \leq 2x_2 \leq 5
\\ \min z = -3x_1 - 2x_2
\end{equation}
solve the ...
0
votes
0answers
17 views
Take the dual of this LP and provide an economic interpretation of the dual. [closed]
Elon Auto is a new company manufacturing electric cars and trucks. To reach customers, Elon
has embarked on an ambitious advertising campaign and has decided to purchase 1-minute
commercial spots on ...
0
votes
1answer
50 views
Convert Sums of absolute values in Linear program
Ihave the following problem and it needs to be converted into LP form.
\begin{align}
\max\> & z = c^T x\\
& Ax \leq B \\
& \sum_{i=1}^{n}|x_i|=1
\end{align}
I know that $c^...
0
votes
1answer
25 views
converting con-convex region to convex [closed]
I'm trying to model a problem using Linear Programming theory, though the feasible region of the problem is non-convex. Yet, I think using Big-M and some binary variables this region can be converted ...
-1
votes
0answers
21 views
Can we solve bimatrix game using linear programming like zero-sum games?
Why can we not use linear programs to solve bi-matrix games like the prisoner's dilemma or the peace-war game? Can you provide a counter example?
1
vote
1answer
46 views
Doubts in a textbook lemma
There is a lemma in the book saying:
"If the primal basic solution is an optimal solution of a linear
program (P), B is not necessarily an optimal basis."
I don't understand because, by ...
0
votes
0answers
14 views
Construct satisfiable solution to a bunch of constraints
I have to determine a problem is feasible or not, but I am not sure how to categorize my problem. It's not LP, or other standard forms of feasibility problems I've encountered. The specific problem is ...
2
votes
0answers
30 views
When are Chebyshev centroids and “analytic” centroids equivalent?
Let $A\in \mathbb{R}^{m \times n}$ and $x,b \in \mathbb{R}^n$.
The intersection of a finite number of halfplanes in $n$ dimensions can be expressed as the solution set to a system of linear ...
1
vote
0answers
15 views
Terminology for Linear Programs without Objective Functions
I have a linear program without an objective function. That is, I am looking for a feasible solution to a given set of linear constraints. Is there a specific term for such problems? Likewise, for ...
0
votes
1answer
38 views
If one system has a feasible solution then other does not have
If we have 2 linear equality and inequatlity systems:
$(1)$ $A x < = b $ $ x >= 0$.
$(2)$ $b^T y < 0, A^T y > = 0, y >= 0$
where A $in$ $R^mxn$ and c $in$ $R^n$ are given and x $in$ $R^...
0
votes
1answer
23 views
Duality in robust optimization
I only know that:
for an LP standard primal $\left\{\begin{matrix}
\underset{x}{\operatorname{max}}[c^Tx]\\
Ax \leq b\\
x \geq 0
\end{matrix}\right.$ corresponds the LP dual $\left\{\begin{matrix}
\...
0
votes
0answers
22 views
Duality in optimization [duplicate]
I know that:
for a standard primal $\left\{\begin{matrix}
\underset{x}{\operatorname{max}}[c^Tx]\\
Ax \leq b\\
x \geq 0
\end{matrix}\right.$ corresponds the dual $\left\{\begin{matrix}
\underset{y}{...
0
votes
0answers
12 views
Uncertainty modelled constraint-wise
I need help to understand the sense of proof E.4 described here at page 3.
Text says that, if we have an LPs problem under uncertainty $\left\{\begin{matrix}
x_1+d_1 \leq 0\\
x_2+d_2 \leq 0
\end{...
0
votes
0answers
27 views
Bellman Equation Proof and Dynamic Programming
I wondered if someone would be able to provide proof of the existence of the Bellman equation in the dynamic optimisation problem below?
Suppose we have the planning problem:
$\ max \Sigma\beta^s U(...
0
votes
0answers
15 views
How to efficiently formulate constraints in a linear programming model?
I'm studying a few example cases of LP from my book to practice but I am having a lot of difficulties when it comes to formulating the constraints for my model.
I have particular problems with two ...
3
votes
0answers
38 views
Proximal operator of the function $w \mapsto \max_{i=1}^k a_i^Tw$, for fixed $a_1,\ldots,a_k \in \mathbb R^n$
Let $a_1,\ldots,a_k \in \mathbb R^n$ and consider the convex function $F:\mathbb R^n \to \mathbb R$ defined by $F(w) := \max_{i=1}^k a_i^\top w $.
Question. What is the proximal operator of $F$ ? ...
0
votes
1answer
37 views
integer programming with indicators
I have the following question, and I need to write it as an integer programming problem:
A manager of a company wants to give presents to his 1000 employers. He can buy the presents from two different ...
1
vote
2answers
20 views
Linearizing the product of a binary and a continuous variable
I have an MIP optimization problem that has a constraint $p\geq xy$, where $x$ is a binary variable, $p$ and $y$ are non-negative continuous variables.
I tried the Big-M method. However, the upper ...
-1
votes
1answer
25 views
How to linearize the following optimization exercises with absolute values?
I have a problem with non-linear variables and I have to present a way for linearizing such a situation.
$\min |x_1| - |x_2-1| \quad \mathrm{s.t.} \quad 3x_1 + 2x_2 \geq 1,
\quad x_2 \geq 1$
$\...
1
vote
1answer
32 views
Different linear programming versions of optimal transport
What is the difference between these two different versions of the linear programming optimization set-up for optimal transport (OT)? how to reconcile them mathematically to show that they are ...
0
votes
0answers
19 views
Linearization of a Max-Max Function
I need help in the linearization of this maxmax function:
max max {2x1+3x2, x1+4x2, 5x1+8x2} subject to: x Ļµ X.
I already started it by:
Ī± = max {2x1+3x2, x1+4x2, 5x1+8x2}
max Ī±
Ī± ā„2x1+3x2
Ī± ā„x1+...
0
votes
0answers
33 views
Prove : The variable that becomes non-basic in one iteration of the simplex cannot become basic in the next iteration.
I am aksed for giving short proof for this statement. I know the working of Simplex and also that this statement is correct.
Once any basic variable becomes non-basic, it has a negative coefficient ...
0
votes
1answer
36 views
Optimization question on a function $𝑢(𝑥, 𝑦, 𝑧, 𝑤) = \min\{𝑥, 2𝑦\} + \max \{3𝑧, 4𝑤\}$
I have the following utility function
$$š¢(š„, š¦, š§, š¤) = \min\{š„, 2š¦\} + \max \{3š§, 4š¤\}$$
I want to find its demand function.
For that
$$\operatorname{Max}š¢(š„, š¦, š§, š¤) = \min\{š„, 2š¦\} ...
1
vote
1answer
33 views
Linear programming - Objective function is a multiple of one of the constraints
I wondered if someone could explain to me the intuition of what it would mean if the objective function in a Linear Programme is a multiple of one of the constraints?
I am thinking it means that the ...
1
vote
0answers
21 views
Is this equivalent to the matroid exchange axiom for closure operators?
Given any set $X$ and some closure operator $\text{cl}:2^X\to 2^X$ on $X$, suppose we define $\psi:2^X\to 2^X$ so that $\psi(Q)=\{q\in Q:q\in\text{cl}(Q\setminus\{q\})\}$ for all $Q\subseteq X$, now ...
0
votes
0answers
15 views
How to find an intial basic solution (partial tree) for the simplex method of a graph if you know the maximum flow?
Let's say I have a graph and I know that the maximum flow that can be pushed into this graph. What are the main guidelines of making a partial tree out of this graph that will be a feasible initial ...
0
votes
1answer
15 views
Minimal cost flow problem - How to balance supply and demand by adding a node and edges? [closed]
I have the following graph for a minimal cost flow problem. Usually in this type of problem the demand = supply. However here we have 30 of supply and only 16 of demand.
I'm tasked with adding a node ...
0
votes
0answers
25 views
infeasibility of primal LP problem
Let's say we have an LP problem
\begin{align*}
\text{minimize} \quad &c^Tx\\
\text{subject to} \quad & Ax \preceq b
\end{align*}
If this problem is infeasible, then $p^* = \infty$. In ...
0
votes
0answers
25 views
How to find the other x,y points of one segment AC knowing the angle and the base
How to find the other x,y points of one segment AC knowing the angle and the base length (can be any angle in the example). Having the base segment line, in this case, is the red line knowing the A(x, ...
1
vote
1answer
47 views
Looking for ONLY a hint on how to do this question
"Consider the polytope in $\mathbb{R}^4$ generated by taking the convex hull of the points $(\pm 1,0,0,0),(0,\pm 1,0,0),(0,0,\pm 1,0),$ and $(0,0,0,\pm 1)$. Describe all of its faces. How many ...
0
votes
1answer
24 views
How to relax an Integer Linear Programming model and describe it as a minimal cost flow problem?
I have the following Integer Linear Programming model:
$\text{min} Z = 6x_{1,3} + 5x_{1,4} + 2x_{1,2} + 3x_{2,3} + 5x_{2,4} + 2x_{3,5} + 4x_{4,5} + 100(y_{1,3} + y_{1,4} + y_{1,2} + y_{2,3} + y_{2,4} +...
2
votes
0answers
43 views
Optimization Modelling: Formulating an Optimal Revenue Strategy With Multiple Constraints
I'm working on a project where the goal is to develop a scheme that computes the optimal solution to the following problem:
Consider a non-virtual loot box; a fix-priced bundle of distinct merchandise ...
0
votes
0answers
37 views
How do I apply the Ford-Fulkerson to a minimal cost flow problem?
I have the following graph :
What is in red is the demand/supply.
When positive -> Supply
When negative -> Demand
When $0$ -> Transfer
On each arc there is residual capacity/given flow.
The ...
