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
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 ...

1
2 3 4 5
82