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

learn more… | top users | synonyms

0
votes
0answers
7 views

Algortihm for Solving Linear equation from a Matrix

I have a set of linear equations from which I have built a matrix below: $M = \begin{bmatrix} p_1 g_1 & - \eta_1 p_2 g_2 & \cdots & - \eta_1 p_n g_n & s_1 & 0 & ...
0
votes
0answers
14 views

Solving large system of Linear equations

I am trying to solve an optimization prob of the below form: $$ \min \sum_{k=0}^{n} p_k$$ subject to : $$0 \leq p_k \leq p_{\max}$$ $$ g_k p_k \leq I_t$$ $$g_k p_k - \eta_k \sum_{j \neq k} p_j ...
0
votes
0answers
20 views

Deduce LP maximization problem from sensitivity analysis

I have the answer to and the sensitivity analysis for a LP maximization problem. (See picture) http://postimg.org/image/xs4iowbrj/ How can I deduce the original LP problem? I have figured out this: ...
4
votes
1answer
2k views

Linear Programming: Three variable graphical solution

A small bank offers three type of loans: housing loans at $8.50$% interest, education loans at $13.75$% interest rates, and loans to senior citizens at $12.25$% interest. Further, it needs to ...
0
votes
2answers
187 views

Transportation problem in supply chain

I understand how to solve transportation problem with only members in the chain, but how can I solve the transport problem with multiple members in the chain? Thank you.
3
votes
1answer
309 views

Converting if else constraints into linear ones

I have the following two constraints: $$ x_1 \leq x_2 \leq x_3 \qquad \mbox{if } x_1 \leq x_3 \\ x_1 > x_2 > x_3 \qquad \mbox{otherwise} $$ Is there a way to get rid of the two conditions and ...
1
vote
0answers
32 views

Can this be expressed in terms of linear constraints?

I'm attempting to find a matrix $X$ that minimizes some function $f(X)$ subject to the constraint that $$ X=W A Z $$ where $A$ is a given non-negative matrix with rows that sum to 1, and $W$ and $Z$ ...
0
votes
2answers
16 views

Single nonzero value constraint formulation in linear programming problem statement

I'm trying to write a linear programming problem statement. Values of the solution vector have a bound constraint: $0 \leq x_i \leq 1$. Another constraint is that if we take a predefined subset of ...
0
votes
1answer
17 views

How to find the point in convex set $C$ that is closest to $y\notin C$?

How to find the point in convex set $C$ that is closest to $y\notin C$? $C=\{ x\in \mathbb{R^2}:(x_1-1)^2+(x_2-1)^2\le1 \}$ and let $y\notin C $ but $y\notin \mathbb{R^2} $.
0
votes
1answer
26 views

Use graphical methods to solve the linear programming problem. Maximize:

Use graphical methods to solve the linear programming problem. Maximize: $z= 4x+2y$ subject to : $x-y\le 7$ $19x+12y\le 228$ $18x+18y \le 324$ $x\ge 0,y\ge 0$ the max is ?? when x= ?? and ...
1
vote
0answers
9 views

best method for solving fully degenerate linear programs

I am looking for efficient computational methods for solving a class of linear programs whose right hand side is zero: $$ \min c^T x \qquad\text{ subject to }\qquad Ax\ge 0 $$ What is the best ...
0
votes
1answer
29 views

Shortest Path Length as mathematical function/expression

I have a graph (unweighted and undirected) of n vertices. My objective is to express the following constraints as inequalities. The degree of any node should be at least 3. The shortest path length ...
4
votes
5answers
3k views

Why maximum/minimum of linear programming occurs at a vertex?

I'm in high-school and I'm told that the maximum/minimum of a linear programming occurs at the vertex.For more info see the chapter here. For convinience I'm putting relevant excerpt here: Now, we ...
2
votes
0answers
18 views

Analytic Center of Convex Polytope

I have a convex polytope defined by $Ax \leq b$. I want to know how to find the "analytic center" of my convex polytope, because my goal is to sample from the polytope using Monte-Carlo Markov ...
2
votes
2answers
382 views

Linear Programming: Breaking Variables Product

Given two sets of binary variables $x_{i...N} \in X$ and $y_{i...M} \in Y$ and another binary variable $\alpha$ how can I linearize the following constraint, i.e break the product of variables? ...
1
vote
1answer
288 views

Binary constraint integer programming problem

Hi I have a question to the folowing question: Explain how to use integer variables and linear inequality constraints to ensure: A) let x and y be integer variables bounded at 1000. How can you ...
3
votes
2answers
97 views

a vector inequality and combinatorics related question

This question is a similar restatement of this question which has been recently closed. Let $$A=\{\ (x,y,z)\in\mathbb{N}^3\ |\ 0\leq x,y,z\leq7\}$$ and $$B\subset A \text{ with } ...
0
votes
1answer
1k views

How to describe minimization of L1 norm error using linear programming?

Given a set of $n$ pair points $(x_1, y_1), ..., (x_n, y_n)$ in the plane, I need to find a line $ax + by = c$ that fits the points of the L1 norm error points as closely as possible. I need a linear ...
4
votes
1answer
2k views

Finding all basic feasible solutions in a linear program

Given the following constraints \begin{equation} \begin{split} x_1 &+&x_2&+&x_3&+&x_4&\le 10 \\ x_1&-&x_2&&&&&\le0\\ ...
2
votes
1answer
1k views

primal to dual solution conversion ??

i have an optimization problem $$\text{ maximize } z=3x+4y$$ $$\text{ such that: } x+y ≤ 450 \text{ and } 2x+y ≤ 600$$ the optimal solution to this problems comes to be $x=0$; $y=450$; $p=150$ ...
1
vote
2answers
672 views

Removing linear redundant constraints using Gauss Elimination

I have a set of linear constraints in the form of $c_i x \ge d_i$ and I need to identify if an additional constraint is redundant with respect of the previously mentioned set. Here I found a similar ...
3
votes
1answer
77 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 ...
-1
votes
0answers
35 views

unable to implement linear programming for min cut max flow problems [on hold]

iam trying to solve codechef problem using linear programming(simplex). https://www.codechef.com/problems/CHEFBOOK i understood the concept of linear programming , but i was unable to implement. I ...
0
votes
1answer
18 views

linear programming : Absolute value in constraint in mathematical model

I have a model have an constraint with evaluation of absolute value , a example can be: function objective : $\max \sum(x_i)$ statement: $x_i\geq |(y_i-t_i)|$ for all $i$ but value absolute ...
0
votes
0answers
27 views

Fundamental Theorem of Linear Programming

I'm reading Dan Stefanica's book "A Linear Algebra Primer for Financial Engineering", which says in pp 92, $\S3.2$ that "...the Fundamental Thorem of Linear Programming, which, informally speacking, ...
1
vote
1answer
198 views

What kind of a problem is this?

The problem can be stated as: I have $m$ liquids ($A_i$ is the amount of the $i$-th liquid) and $n$ tanks ($x_j$ is the volume of the $j$-th tank), and the task is to find the best way to ...
3
votes
1answer
831 views

Linearization of a product of two decision variables

I am trying to solve a problem that involves constraints in which products of two decision variables appear. So far, I read that such products can be reformulated to a difference of two quadratic ...
0
votes
2answers
29 views

Simplex algorithm with initial negative slack variables

I have the following LP problem: $$\begin{equation*} \begin{aligned} min. & & z = 2x+3y\\ \text{s.t. } & & x & \le 3\\ & & x & \ge 3\\ & & -x + 2y & \le ...
-1
votes
1answer
30 views

Linear equations problem [closed]

The Marshall County trash incinerator in Norton burns 10 tons of trash per hour and co-generates 6 kilowatts of electricity, while the Wiseburg incinerator burns 5 tons per hour and co-generates 4 ...
1
vote
0answers
359 views

Can this non-linear optimisation problem be converted to a linear?

I have to minimize the function: $$F(x) = \sum_{i=1}^{M}\left\|x_{i+1} - x_i - K\left(\frac{x_{i+1} + x_i}{2}\right)\right\|^2 + \|x_1-c_1\|^2 + \|x_N-c_2\|^2,$$ where $x$ is a vector of $N$ scalars, ...
0
votes
0answers
11 views

How to Adequately Implement Phase I of Two-Phase Simplex Algorithm on a Computer with Floating Point Error

I'm currently trying to write some code that implements Phase I of the two-phase Simplex Algorithm described here: http://www.statslab.cam.ac.uk/~ff271/teaching/opt/notes/notes8.pdf In order to test ...
1
vote
1answer
1k views

Linear programming: basic solutions?

http://www.math.toronto.edu/kergin/236_t1_2.pdf For number 3(a), I don't get how "any of the last 4 columns are linearly dependent" and how x1 is the basic variable... I thought only the last 2 ...
0
votes
1answer
37 views

Shortest point on a line segment from point outside the line

From the above pic I found the value $x$ from line $(p1,p2)$ and point a using $y=mx+b$ and imaginary red line which is perpendicular to black line having slope $-1/m$ and the intersecting point ...
0
votes
2answers
934 views

Optimal Basic Feasible Solutions

In linear programming, is it true that you can only have at most 2 optimal basic feasible solutions? If so, why?
1
vote
1answer
38 views

Tutorial for Simplex Method with No Slack Variables

I found a nice tutorial here http://www.math.ucla.edu/~tom/LP.pdf for applying the Simplex Method to problems of the form: maximize $c^T x$ with the constraints $Ax\leq b$, $x_i \geq 0$. It suggests ...
1
vote
2answers
60 views

How does one verify if a vector is really recovered?

In compressed sensing, how to verify if a vector is really recovered or how does one plot the figures on recovery rate? Since in numerical experiments, there is always a difference between the ...
0
votes
1answer
50 views

Edges of Hypercube

I may have some problem with this: Given a linear program $$\max{4x_1 + 2x_2 + x_3}$$ under the constraints $$ x_1 \le 5 $$ $$ 4x_1 + 1x_2 \le 25 $$ $$ 8x_1 + 4x_2 + 1x_3 \le 125 $$ $$x_1,x_2,x_3 ...
0
votes
1answer
33 views

how to check whether feasible solutions exist for linear programming

For a linear programming problem, how to decide whether there exists a feasible solution without solving it? For Ax<=B, is there any sufficient and/or necessary condition represented by A and B to ...
0
votes
1answer
358 views

Formulate model

Carter Enterprises is a soybean trading company. Once a month a representative attends a commodity sale where he either buys or sells soybeans in bulk. Carter uses a local warehouse for storing ...
0
votes
1answer
31 views

Solution of linear inequality

I have the following system of linear inequality on $x_1, x_2, \dots, x_n$, $x_i \in \mathbb{R} \; \forall i$ $x_i - 2x_j < b \; \forall i, j$ The right hand side of the inequality ($b \in ...
3
votes
1answer
51 views

Different versions of theorem of the alternative?

I am looking for help to find necessary and sufficient conditions for a solution $x\in \mathbb{R}^n, x>0$ to exist to the following linear system: $Ax = b$ with where $A$ is $m\times n$ and ...
0
votes
0answers
37 views

How to find a formula for ratios?

I don't know if this is the correct section to post this, but here it goes. I recently got involved with hydroponics, and to feed the plants I've installed a system with a pump that delivers a ...
1
vote
1answer
679 views

simplex M-method minimization problem

Solve using the simplex method. Identify the solution of the dual in the final simplex tableau Minimize: $$z=12x_{1}+4x_{2}+2x_{3}$$ **Constraints:**$$ x_{i}\ge 0$$ $$-6x_{1}+3x_{2}\ge 9$$ ...
2
votes
1answer
38 views

How come $Ax\le b$ and $c^Tx\ge \alpha +\epsilon$ has NO nonnegative solution.

Let $\alpha=c^Tx^*$ be the optimum value of the standard form of (LP)(= max $c^Tx$ subject to $Ax\le b$ and $x\ge0$ in $\mathbf{R^n}$) Then we know: $Ax\le b$ and $c^Tx\ge \alpha$ has a nonnegative ...
2
votes
1answer
394 views

Polytopes and matrices

Why do the vertices of a polytope are isomorphic to the matrices that contain 2 ones on each row and col? Why if $M \in P$ is not a $0-1$ matrix then $M$ is ...
0
votes
1answer
39 views

How do I determine the weight to assign to each bucket?

Someone will answer a series of questions and will mark each important (I), very important (V), or extremely important (E). I'll then match their answers with answers given by everyone else, compute ...
0
votes
2answers
40 views

Right coordinates of a slanting line when slope is zero and left coordinates never changed after transformation

I have a line in a program I am developing that I want to remove the slant (slope to zero) then get the new coordinates after transformation that removes the slope. This is how the line with the ...
1
vote
1answer
35 views

How to pivot to an adjacent vertex in simplex method

In the simplex method, we need to move from one vertex of the polyhedron to an adjacent one. Suppose the polyhedron is $P=\{x\in\mathbb{R}^n\mid Ax=b,x\geq0\}$ with rank$A=m<n$. For a ...
1
vote
1answer
26 views

How to have just 3 result variables for this linear programming problem?

I have the following problem: +----------------------+--------------+--------------+----------+ | Process time (hours) | ...
0
votes
1answer
321 views

Linear Programming formulate if then constraint

Consider an LP for which you want to add the restriction that Only if $x_1\geq 3$ then $x_2$ and $x_3$ are allowed to be larger than $0$; otherwise $x_2$ and $x_3$ are $0$. Demonstrate how to ...