Questions tagged [linear-programming]

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

Filter by
Sorted by
Tagged with
1
vote
0answers
27 views

farkas' lemma and solution

I know that Farkas' lemma certifies feasibility of a system Ax=b x>=0. Now suppose it's feasible. How do I find a solution x and under what conditions on A and b do I know the solution is unique?
1
vote
1answer
50 views

Reading the primal solution from dual simplex tableau

I was following ptrickJMT's video on how to solve a minimization linear programming problem and he did something that I did not understand why it works. He starts with the following minimization ...
0
votes
0answers
30 views

How to get the Values of an given tableau of the simplex algorithm?

I have some problems with some task of an old exam and i hope u can give me a hint or a way to solve those. Given is the tableau $\begin{equation} \begin{bmatrix} \begin{array}{c|ccccccc} & ...
4
votes
1answer
67 views

Does every compact (not necessarily convex) set have extreme points?

Let $A$ be a set in a normed vector space. Call a point $p$ in $A$ extreme if there do not exist $p_0, p_1$ in $A$, distinct from $p$, such that $\lambda p_0+(1-\lambda)p_1=p$, for $\lambda \in [0,1]$....
1
vote
3answers
75 views

What are the extreme points of this polytope?

Let $n, k$ be positive integers with $n\geq k$. Let $P_{n,k}$ be the set of vectors $x$ in $[0,1]^n$ for which $$ \sum_{i=1}^n x_i = k $$ $P_{n,k}$ is defined by linear equations, so it is a polytope. ...
0
votes
0answers
21 views

Answering questions about a linear system with constraints

Normally, in solving problems with linear systems, one is given a system of constraints and wishes to find a solution, but in my case I am given a solution and want to find a system for which the ...
0
votes
1answer
32 views

What does it mean to set the gradient of a multilinear function to $0$?

When you have a 1D function $f(x)$, the vector $x$ that satisfies $\nabla f(x) = 0$ is a stationary point which is a minimum when $f$ is convex. Consider a multilinear function (linear in all ...
0
votes
1answer
31 views

constraint qualification for linear constraints [closed]

How to formulate conditions under which the LI CQ is fulfilled at arbitrary feasible point of the set of feasible solutions given by linear inequalities $S=(x\in\mathbb{R}^{n}:Ax\le b, x\ge 0)$? I ...
1
vote
0answers
44 views

Finding coloring with no subgraph isomorphism

This is a twist on standard subgraph isomorphism. Say I have two graphs $G(V,E)$ and $H(V',E')$ and the vertices in each graph are colored with one of $t$ colors. The subgraph isomorphism exists if ...
0
votes
0answers
31 views

Integer programming - “the carrier problem”

Motivation: The problem is to find the best solution of which of waiting packages should be packed first to a finite-space bus to deliver as many packages as possible at once. Problem description: Let'...
4
votes
3answers
147 views

Extremal distribution of random variable that averages to a given value

Denote by $\mathcal M$ the set of probability measures over $[0,1]$ that average to $p$. This is a convex set and I am trying to characterize its extreme points. For any $x$, $y$ such that $0\leq x<...
0
votes
1answer
26 views

OLS/LAD on linear/quadratic programming type problem

I have a list of equations that define halfspaces (3 equation list example below) $x_1 + x_2 + x_3 + x_5 < x_4 + x_6 + x_7 \\ x_4 + x_6 + x_7 < x_8 + x_9 + x_{21} + x_{43} + x_1 \\ x_4 + x_6 + ...
2
votes
1answer
28 views

asymmetric Dual of the asymmetric Dual is Primal?

It is known that in Linear Programming the Dual of the Dual is the Primal. In wikipedia I saw that apart from the symmetric Dual I knew, there is also the asymmetric one: https://en.wikipedia.org/wiki/...
0
votes
1answer
76 views

Given an LP problem how to transform the problem?

Given the following problem: $$ \max. -3x_1 -2x_2 - \frac{9}{2}$$ $$ \text{s.t.} -x_1 + x_2 \le 0$$ $$ 5x_1 + 3x_2 \le 8$$ $$ x_1,x_2 \ge 0 $$ When we convert the LP into standard form and then ...
0
votes
0answers
23 views

optimalization problems

I do not understand in the optimization problems the following steps. Let us say we have the problem $$\min(\text{or}\max) f(x)$$ subject to $$p^{t}x=b$$ in some textbooks, I saw the Lagrange function ...
0
votes
2answers
52 views

Find the maximum value of the product of $x_1^1 x_2^2 \cdots x_n^n$ [closed]

Given $n$ positive real numbers $\{x_i\}_{i=1}^n$ satisfying $x_1 + x_2 + \cdots + x_n = n$, find the maximum value of $x_1^1 x_2^2 \cdots x_n^n$. That is, $$\max_{x_1, \cdots, x_n} ~\prod_{i=1}^{n} ...
0
votes
0answers
21 views

Proper objective function implementation

This question is referred to from here. I want to minimize the HD between $x_g$ and $x_h$ bit strings in the objective function in a Mixed Integer Linear Programming problem. That is, Min $\sum_{l=1}^{...
0
votes
1answer
25 views

Linearizing constraint ( multiplication of binary variables)

I am trying to think of contraint(s) that can linearize constraint below. $\sum_{T} \sum_{TR} Z_{(T,D)}* Y_{(TR,T)} \leq CAP_{(D)} \forall D$ Both Z nad Y are Binary Variables and CAP is capacity ...
1
vote
0answers
28 views

Converting a linear program to standard form when x is a matrix?

I have been using An Introduction to Optimization by Chong and Zȧk. In it there is a chapter about standard form and converting to it. This chapter makes sense to me. I think that I understand the ...
1
vote
0answers
47 views

minimize $(1/2)x^TPx+q^tx+r$ subject to $x^tx \le 1$

minimize $(1/2)x^TPx+q^tx+r$ subject to $x^tx \le 1$. The usage of the Lagrangian is not allowed. I view it as a quadratic equation minimisation task. The way I see it I should take the gradient made ...
0
votes
1answer
25 views

Transportation Problem - Handling case of infinite capacity to supply

The problem is - In a standard transportation problem, with destination's demand limited, but each factory has unlimited supply to cater to the needs of destination. How should we modify the problem ...
1
vote
1answer
31 views

The basis for the null space of a linear transformation

I am given the following linear transformation $$f: \begin{bmatrix}x\\ y\\ z \end{bmatrix}\rightarrow\begin{bmatrix}x\\ x \end{bmatrix}$$ and asked to select all answers which provide a basis for the ...
0
votes
1answer
38 views

How to solve this mathematical programming problem?

Suppose each point in the interval $[0,1]$ has some of a set of $N$ properties. The total length of the intervals with property $i$ is $x_i$ ($0\le x_i \le 1$). Questions: What is the maximum and ...
0
votes
1answer
26 views

If origin is not included in an LP problem how do we get a basic feasible solution?

Given the following constraints for an LP problem: \begin{align} x_1 + 2x_2 &\ge 4 \\ -3x_1 + 4x_2 &\ge 5 \\ 2x_1 + x_2 &\le 6 \\ x_1 , x_2 &\ge 0 \end{align} When I draw the feasible ...
0
votes
1answer
83 views

How to declare formulas for banded pricing model? [closed]

I am making an application (using JavaScript) where users should be able to create pricing models with a table. A user will have an ability to choose a table model. The table models are internally ...
1
vote
1answer
33 views

Build a cheaper highway

We consider a non-directed graph, where each vertex is a city and each edge is a possible road connecting two cities. I need to build a cheap highway (a path on a graph) connecting all the cities ...
0
votes
0answers
5 views

How do I implement an aggregate probability constraint with uncertainty?

I am trying to model the following situation: There are N customers and M shops. The demand of each customer is a normally distributed variable $d_{n}$ with mean $\mu_{n}$ and standard deviation $\...
0
votes
1answer
23 views

Square LP. Consider the LP with $A$ square and nonsingular. Minimize $c^Tx$.

Square LP. Consider the LP $$\text{minimize }c^Tx\\ \text{subject to } Ax \le b$$ with $A$ square and nonsingular. Show that the optimal value is given by $p^* = c^TA^{-1}b$ if $A^{-1}c \le 0$, and $p^...
0
votes
0answers
18 views

How to find the values of dual slack variables at the vertex $(w_{1}, w_{2})$?

Max $Z = c_{1}x_{1} + c_{2}x_{2} + c_{3}x_{3} $ Subject to $Ax \leq b$ $x \geq 0$ If eliminate $x_{1}, s_{1}$ from Z, we get $Z = 45 - 2x_{2} + 3x_{3} - 4s_{2}$ What will be the values of the dual ...
0
votes
0answers
14 views

Doubt about notation in Robust Optimization

I'm studying the pricing model under Robust Programming here described from page 41 to page 45. I don't understand what's the meaning of subscripts $i$ and "second" $t$ referred to dual ...
0
votes
0answers
29 views

Linear programming of the Sinkhorn distance (entropy-regularized optimal transport)

\begin{align} \mathcal{W}_\epsilon(\alpha, \beta) =& \min_{\pi\in \Pi(\alpha\beta)} \int c(x,y) \mathrm{d}\pi(x,y) + \epsilon H(\pi) \\ =& \min_{\pi\in \Pi(\alpha\beta)} \int c(x,y) \mathrm{d}\...
0
votes
1answer
47 views

Why is the distance matrix in optimal transport always the same, and doesn't actually measure distances between samples?

Why does the distance matrix computed in the optimal transport linear programming model always look the same (asides from its size changing with the number of histogram bins) no matter how the source ...
2
votes
0answers
35 views

minimal description of polyhedron

I have to find minimal description of a polyhedron $P$ described as follows: \begin{align*}x_1 - x_2 &\leq 0\\-x_1 + x_2 &\leq 1\\2x_2 & \leq 5 \\ 4x_1 - x_2 &\leq 8 \\ x_1 + x_2 &...
0
votes
1answer
29 views

How to solve an optimization problems of this kind?

I have to solve a real-world optimization problem. I am teaching 33 students, a university lesson, and I am attempting to assign them 11 semester projects, based on their preference. I grouped them in ...
0
votes
1answer
63 views

Linear programming with a second decision variable in the constraint vector

Is the following optimization problem feasible (modified optimal transport)? The primary decision variable appears in the objective function as $\mathbf{x}$, whereas the second decision variable $\...
0
votes
0answers
18 views

Fixed Strike Lookback Call Option with Linear Programming - Question about notation

I am aware, given the number of unanswered questions, that the probability that somebody answer is almost zero, but I'll take my chances. I am trying to understand how to evaluate fixed lookback ...
0
votes
1answer
28 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 the ...
0
votes
1answer
32 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
16 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
22 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
32 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
39 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
97 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
2answers
34 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 ...
2
votes
0answers
118 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

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
17 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
1answer
18 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?
0
votes
1answer
36 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
29 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 ...

1
2
3 4 5
83