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

learn more… | top users | synonyms

0
votes
0answers
19 views

Perturbation factor terminology

This is a question about usage of English. I have an inequality $a^\textsf{T}x \leq b$, where $a$, $b$, and $x$ are vectors in $\mathbb{R}^n$. Now, I want to perturb this inequality by a small amount ...
2
votes
2answers
124 views

How can I calculate if a given point is wrapped inside a pentagon?

If I have a pentagon and I know the coordinates of it's nodes, how do I calculate if a point is wrapped inside it? An example to clarify what I mean: Assume that we know the coordinates of the ...
0
votes
0answers
131 views

Prove solution does not exist for inequalities system

I have an inequalities sytem like the following: Example > x+y+z <= A > x+y <= B > x+z > C > y+z > D > x >= E Let A,B,C,D,E be any ...
0
votes
1answer
69 views

Projection onto Polyeder

I know how to projects onto a linear subspace of $\mathbb R^3$, but how to project a point $x$ onto an polyhedron given as the intersection of three halfspaces $$ \langle y_1, x \rangle \ge c_1 ...
0
votes
1answer
575 views

Can someone explain the effects of degenerate basic feasible solutions in the simplex algorithm?

I was given this on an assignment sheet, and am now using it to revise from...I cannot remember the issues that arise from degeneracy of basic feasible solutions... Let $P$ =$\{x\in \mathbb{R}^n ...
1
vote
1answer
58 views

Why is this simplex procedure not working? $\min z = y - x + 1$

I have read of two ways to solve this program with the Simplex algorithm. One worked and the other didn't. The only difference is that, in the one that didn't work, I rewrote the function. I will ...
0
votes
1answer
25 views

Is there relations between earth mover's distance and vector norms?

Say I have two vectors $a$ and $b$. Can I estimate $\mbox{EMD}(a,b)$ via some combination of things like $\|a-b\|_p$ and such?
0
votes
1answer
376 views

Linear programming: Maximize minimum of linear functions

For a project I need something solved, it screams linear programming. If I get the problem in "standard" form I should be able to solve it using the simplex method. But I don't see how to get it in ...
2
votes
1answer
138 views

Linear Algebra 101 - Optimizing inequalities

I am considering the region contained in $\mathbb{R}^2$ consisting of all the points that satisfy all the following inequality: $-4 \leq y < 4 \\ -9 \leq 2x + y \leq 9 \\ -9 \leq x + 2y \leq 9 \\ ...
1
vote
1answer
27 views

linear systems&normalize

suppose $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$ be a linear function which can be represented by a $n \times n$ matrix. Then the jacobian of $f$ is the same as the function for $f$. But I now want ...
3
votes
0answers
104 views

The importance of the full-row-rank assumption for the simplex method

Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix $A$ be of full row rank means not ...
1
vote
1answer
64 views

the differences and relationship between linear independent and affinely independent

When learning optimization, I heard the two related concepts on linear algebra: linearly independent and affinely independent. ...
0
votes
1answer
221 views

Linear Programming : Alternative to summation of absolutes in constraints

I am solving a placement problem, i.e. map $integers\ i\ from\ 0\ to\ 6$ to $(x_i,y_i)\ st\ 1 \le x_i,y_i\le 3$ such that : $ \sum\limits_{i=0}^6 \sum\limits_{j=0}^6 Cost(i,j)*(|x_i - x_j | + | y_i ...
0
votes
1answer
183 views

Need help with minimum cost network flow problems

Consider the tree solution for the following minimum cost network flow problem: The numbers on the tree arcs represent primal flows while numbers on the nontree arcs are dual slacks. (a) Using the ...
0
votes
2answers
56 views

Maximize $\ x+\frac32 y\ $ subject to…

I am stuck on the following problem: Consider the linear programming problem: Maximize $x+\frac32 y$ subject to $$2x+3y \le 16, \\ x+4y \le18,\\ x \ge 0,y \ge0.$$ If $S$ ...
0
votes
2answers
105 views

Game Theory - Setting Up Column Player's Optimal Stategy

Above is my question. Could someone please help me with the first part? I should be ok once I have set up the linear programming problem, but I don't even know what $x_1, x_2 \ \text{and} \ x_3$ are ...
1
vote
1answer
37 views

Linear Optimization Study Material

I've recently enrolled in a linear optimization course, and it's been a while since I've taken linear algebra. I do not yet have access to the book for the course or I would skim it to see what I need ...
0
votes
1answer
42 views

What's wrong with this linear program formulation?

You have two item factories, $A$ and $B$, and there are two clients that buy such item. Each client has a demand - the first one needs $400$, and the second $300$. Each factory has a ...
4
votes
1answer
50 views

Is a System of Linear Equations the Right Way to Solve This Optimization Problem?

This is kind of a high-level question, in that I'm not sure which mathematical approach might be best for solving my problem. I'm trying to automate a painful, error prone, and time consuming process ...
1
vote
2answers
49 views

What is wrong with this linear program $\max z = 3x_1+2x_2$?

I solved a linear program. It is wrong. The answer is that $(x_1,x_2) = (50,75)$ and the maximum value is $300$, but instead I am getting $(x_1,x_2) = (50,100)$ and the maximum being $350$. Why is ...
1
vote
0answers
36 views

Solving $\max z = (3x_1 - x_2)$ linear program

I am trying to solve this linear programming exercise using the Simplex method. First of all, I detail every step, so it is pretty long, but the real question (the part where I'm stuck at) is at the ...
0
votes
1answer
47 views

Robust LP question using box uncertainty model

I am trying to solve this robust LP problem by writing it as a QP $$\min_x x^TSx : \mu \leq r^T x , Ax \leq b$$ Under Box uncertainty model: $$R = \{r : \| r - \hat{r}\|_\infty \leq \rho\}$$ Here ...
1
vote
0answers
50 views

How do we determine the saddle point in game theory?

I am a little confused of why this works. If a$_i$$_j$ is positive, row player pays the column, and vice versa. \begin{bmatrix} 3 & -5 & 6\\ -2 & 1 & 8 \\ 3 & -6 & ...
0
votes
1answer
77 views

Math Constraint Problems

This is a homework problem of mine. The professor said we can use any resource to help us solve and I cannot get up with anyone from class. Please help. I'm not looking for a direct answer, I ...
0
votes
1answer
50 views

How can I verify my linear program solutions?

I started solving linear programs with the Simplex algorithm, however it is unclear to me how can I verify my solutions. I have heard about geometrical solutions easy to check visually, but I'd ...
2
votes
1answer
27 views

What to do if the righthand of a constraint is a variable when solving Linear programs?

I'm starting to solve linear program exercises with the Simplex method. $$max \ (3x_1-x_2)$$ $$\begin{cases} x_1-x_2 \le 3\\ 2x_1\le x_2\\ x_1+x_2\ge 12\\ x_2 \le 10\\ x_1,x_2 \ge 0 \end{cases}$$ I ...
1
vote
1answer
144 views

Explicit solution of linear program: minimize $c^T x$ subject to $Ax = b$

This is the given question in a textbook I am following. I will paste the solution below which I do not understand: I am a little hazy on linear algebra theory, so I don't fully understand how the ...
3
votes
1answer
189 views

Formula for position in an upper triangular matrix

I'm currently working on the Travelling Salesman's Problem in a computer science module. I have implemented some linear programming techniques using the software lp_solve. I've ended up with an upper ...
2
votes
2answers
62 views

Which mathematical programming method is good for solving the described problem?

I need to solve the following problem. Let's say that there are 3 clients with different time windows. For simplicity let's say that travel distance is always 10 minutes and service time is 30 ...
0
votes
1answer
17 views

Finding the corresponding constrained subspace under a over determined mapping Ax=b, where b is constrained

Suppose that $A$ is a $m\times n$ matrix with m>n, $Ax=b$, and $b$ is constrained in every component, $b_\min^i<b_i<b_\max^i$ for $i=1,\dots,m$. There should be a similar set of constraints for ...
2
votes
1answer
109 views

How to use the simplex method for linear programs?

I believe to be missing something important in the Simplex algorithm, because I can't get it to work. From what I gather, there are three steps per iteration, given a matrix for a linear program in ...
1
vote
0answers
64 views

Matrix multiplication in game theory doesn't add up? Min y^T*Ax

I'm studying game theory and something seems weird to me. My book says y is the probability of the row player and x is the probability of column player, both x and y are vectors. A = [a$_i$$_j$] is ...
0
votes
1answer
48 views

Semi-Infinite Linear Programming: Why is the infimum attained?

I have an optimization problem of the following form: $$\min c^T \lambda\\ \text{s.t. } f(x)^T \lambda \ge g(x) \text{ for all } x \in E,$$ where $E$ is an arbitrary set, $c \in \mathbb{R}^n, f ...
1
vote
5answers
173 views

Ok, I know what does linear independence mean but why should I care?

I understand that for a set of vectors to be linearly independent, none of the vectors in the set should be a linear combination of some other vectors in that set. But why on earth should I care about ...
0
votes
1answer
34 views

Computation time

I am implementing a mixed-integer linear programming problem, and I am dealing with an huge number of constraints. Does anyone know what the linear relation is between the number of constraints of ...
3
votes
1answer
67 views

How to reformulate this Set covering problem?

I am trying to solve the following implementation of the set covering problem of a crew rostering problem. Here constraint (19), meant to create a 12-hour break between the different shifts taken by ...
1
vote
2answers
319 views

Minimization of log-sum-exponential function subject to constraints.

I would like to minimize the following function: $f(x)=log(e^{-x_1}+..+e^{-x_n})$ Subject to: $\sum_{i=1}^{n}{x_i}=1$ $0 \leq x_i \leq 1$ So far I have discovered the following: If all the ...
0
votes
0answers
35 views

Mixed Interprogramm remodeling

for example i have the following problem min z 5 x_1a + 6 x_1b - 3 x_2a + 0 x_2b <= z -3 x_1a + 0 x_1b - 1 x_2a + 2 x_2b <= z x_1a + x_1b = 1 (Constraint say of this group only one variable ...
0
votes
1answer
34 views

About canonical linear programs.

Starting out with linear programming, I'm having some questions about canonical linear programs: Do all linear programs have a canonical form? So far I couldn't figure an example stating otherwise. ...
1
vote
0answers
53 views

On the injection of exactly two artificial variables into the Phase I of a two-phase simplex

I am relatively new still to linear optimization and as I understand it, the two phase method is a common practice for finding the bfs before using the simplex or a simplex like solver (a solver ...
0
votes
1answer
105 views

Reference request: optimal solution for linear program is rational

From various lecture notes and such that are floating around, I get the impression that if a linear program has rational coefficients and has a finite optimal solution, then that solution will be ...
0
votes
0answers
1k views

What are canonical vectors?

I just begun with linear programming. Given an objective function $z$ and certain restrictions defined by $Ax = b$, we got to find the values necessary to maximise or minimise that function's ...
1
vote
0answers
76 views

Minimising waste in a cutting problem.

I have three possible board sizes: $8$, $10$ and $12$ feet long. I want to make some number of cuts to these, say, $3, 2,1,1,1,6,5,3,4,2,1$ feet cuts and I want to minimize waste. I've done a quick ...
1
vote
1answer
124 views

Linear Programming - Simplex Method

Let, $\begin{array}{lcl}Min: z =10x_{1}+5x_{2} \\ \\ 20x_{1}+50x_{2} \geq 200 \\ 50x_{1}+10x_{2} \geq 150 \\30x_{1}+30x_{2} \geq 210 \\x_{1},x_{2} \geq 0\end{array}$ a linear programming problem. ...
1
vote
1answer
168 views

can I get help in solving this equation using simplex method big-M method

Objective: $\max Z= 100x_1+300x_2+400x_3$ s.t. $10x_1+20x_2+30x_3≤1600$ $\;\,\quad10x_1+15x_2+20x_3≤1500$ $\;\,\quad x_2+x_3≤50$ $\;\,\quad x_1+x_2+x_3=70$ $\;\,\quad x_1,x_2,x_3≥0$
1
vote
1answer
319 views

Cycling in Simplex Method - Smallest Subscript Rule

Could someone explain to me how using the smallest subscript rule causes a cycling LP to terminate? At the moment it looks to me that a program would use it to determine whether the matrix from the ...
1
vote
0answers
462 views

How do I convert max min problem into a linear programming problem?

Let $A$ be a given $m \times n$ matrix, $c$ a given $n$-vector, and $b$ a given $m$-vector. Show that this problem $$\max \min (c^T x - y^T Ax + b^Ty) \text{ such that } x,y \ge 0$$ can be reduced ...
1
vote
0answers
534 views

Transportation problem: optimal solution

So I have an issue with finding the optimal solution (the lowest costs) to a transportation problem. Given the following problem, with $A$ the depots, $B$ the destinations and $C$ the $(i,j)$ matrix ...
2
votes
0answers
146 views

Post-optimality analysis: Change in one of the constraints

Consider the LP: \begin{array}{rccc} \max& \quad -3x_1&-x_2& & \\ \text{s.t.}& \quad 2x_1&+x_2 &\leq 3 \\ & -x_1&+x_2 &\geq 1 \\ &&x_1,x_2 &\geq ...
2
votes
2answers
106 views

How do I solve max min (x − y) and min max (x − y) such that y≥0 and x≥0?

solve max min (x − y) and min max (x − y) such that y≥0 and x≥0 I don't have a clue where to start.