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

learn more… | top users | synonyms

2
votes
0answers
63 views

Up and Downtime Constraints - An Optimization Problem

I am working on a project and have run into a roadblock, any help will be greatly appreciated: We are trying to minimize cost of running a series of generators. Each generator has a unique cost of ...
0
votes
1answer
75 views

Minimized sum of the distances with street distance

This exercise comes from Bazaraa Linear Programming and Network Flows book : Consider the problem of locating a new machine to an existing layout consisting of four machines. These machines are ...
0
votes
0answers
19 views

Generalization of size reduction of Linear Assignment Problems

It is well known, that the LAP has super linear complexity. Hence, problem-size reduction is a viable optimization strategy. For instance, if one task is incident to exactly two workers, one can ...
0
votes
0answers
10 views

way to find angle of objective function and constraint in lp

I want to find the angle between objective function plane and hyperplane in LP problem . For example , let I have the following LP problem: $ \text{minimize } 10x_1-57x_2-9x_3-24x_4 $ $$\\$$ $ ...
2
votes
2answers
40 views

Howto solve $\min |x_1| + |x_2|$ with linear programming?

Consider this optimization problem: $$\begin{matrix}\min & |x_1| + |x_2| && \\ s.t & a_{11}x_1 + a_{12}x_2 & = b_1 \\ & a_{21}x_1 + a_{22}x_2 & = b_2 \end{matrix}$$ ...
1
vote
1answer
188 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$ ...
2
votes
1answer
28 views

Choosing pivot while solving Linear Programming in case the constraints are lesser than the available variables.

I am trying to solve a LP with simplex method which says like. Suppose, Maximize $$10x_1+20x_2+20x_3$$ subject to \begin{align} \tfrac{2}{3}x_1+4x_2+x_3&\leq 50&& (I)\\[0.5em] x_1 + ...
1
vote
1answer
50 views

Solve linear algebra equations

I have following question that I kindly need assistance: 2 Products; $x$ and $y$ For every $x$ units sold profit$= 20$ For every $y$ units sold profit$= 50$ Therefore profit function$= (20*x) + ...
1
vote
1answer
48 views

Linear program with bounded feasiblity set

Hey guys I've been stuck on this problem and was wondering if anyone could help. Consider a linear programming problem in standard form with a bounded feasible set. Furthermore, suppose that we know ...
1
vote
2answers
196 views

Finite Math Word Problem

I have been having trouble with this word problem for a while. A bicycle manufacturer builds one-, three-, and ten-speed models. The bicycles need both aluminum and steel. The company has available ...
1
vote
1answer
49 views

Exploiting structure of linear equations to solve them

So I have a bunch of linear equations $Ax=y : A \in R^{m,m}, y \in R^{m}$. Note that $A$ is a square matrix. The question is if I can decompose $A$ as $$A = D + uv^T$$ where $D$ is diagonal, ...
1
vote
1answer
38 views

Constrained Minimization Problem derived from a Directed Graph

I'm looking for a solution the following graph problem for data analysis purposes. Basically, I have a directed graph of $N$ nodes where I know the following: The sum of the weights of the ...
2
votes
1answer
119 views

Converting sum of infinity norm and L1 norm to linear programming

So I'm trying to convert this minimization problem, min $\parallel Ax-y \parallel_{\infty}$ + $\parallel x \parallel_{1}$ where $A$ is $m$ by $n$, $y$ is $m$ by $1$ and $x$ is $n$ by $1$. into a ...
3
votes
1answer
21 views

Linear Optimization Problem with a constraint on the cost functin

Is there a known algorithm ( similar to simplex algorithm) that solves the following problem: Maximize $c^Tx$ subject to the constraints $Ax\leq b$ and $c^Tx\leq \alpha$. It would be nice if you can ...
0
votes
1answer
146 views

Minimizing shipping cost under given constraints

I have a question that has been bugging me for about a day now. A manufacturing company receives orders for engines from two assembly plants. Plant I needs at least 45 engines and Plant II needs at ...
2
votes
1answer
42 views

Linear Programming - Handling $\max(x,0)$ in the objective function

Hello I have to solve the following problem $\min_P (\max (K_1+P,0)+ K_2 P)$, s.t. $P \in \mathcal{P}$. Is there a any trick to convert the $\max(\bullet,0)$ and convert it into a linear programming ...
0
votes
1answer
353 views

Minimize LPP using graphical method [ operational research ]

Question: Minimize z = 2x + 6y Subject to 2x + y >= 2; 3x + 4y <= 12 x,y >=0 Is min z = 2 the right answer ? if not how do i solve this ?
3
votes
1answer
209 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\\ ...
1
vote
1answer
59 views

Solving linear programming problems

Find the smallest value of the function $f=21x+14y$ considering only those values of $x$ and $y$ that satisfy the constraints \begin{eqnarray*} 15x + 22.5y &\geq& 90, \\ 810x + 270y ...
1
vote
0answers
65 views

Help solving this linear (?) programming problem with odd integer constraints.

I would like some help writing the following linear (integer? quadratic?) programming problem in matrix form including the application of the constraints. I am drawing a dashed line around the ...
1
vote
1answer
50 views

Dual of an equality constraint in MIP

In a mixed integer programming question how one may find the dual of the equality constraint? As example: $min \quad C^T X$ $s.t. \quad aX\leq b$ $\qquad eX=d$ $\qquad X\in integers$ How to find ...
0
votes
1answer
28 views

For which values of $a$ does the following LP problem have an optimal solution?

Let $a \in R$. For which values of $a$ does the following LP problem have an optimal solution? $$max(2x_1+6x_2+3x_3)$$ $$-3x_2+ax_3 \geq 3$$ $$x_1+5x_2+2x_3=4$$ $$x_1, x_2, x_3 \geq 0$$ I solved it ...
1
vote
1answer
72 views

Is finding the maximum of a polynomial of degree one a linear programming problem?

Is the following problem expressible as a linear program \begin{align} \textbf{P1} \\ \mathrm{maximize} \; \; \; &\left[\left(a_1x+a_2y,b_1x+b_2y\right)_+ - \left(c_1x+c_2y\right)\right]_+ - ...
0
votes
1answer
79 views

Stock cutting and column generation giving suboptimal answers?

I'm doing a stock cutting implementation. I use the delayed column generation approach. I'm getting suboptimal answers with the following simple case: raws length: 630 in. demands: 10 x ...
1
vote
1answer
47 views

Maximization of a function defined with $\max$

Define the function $$ f(a,b,c,\alpha,\beta,\gamma,x) = \max\!\bigg(0 , \, \max\!\big( \left(a+x\right)\alpha,\left(b+x\right)\beta \big) - \left(c+x\right)\gamma\bigg), $$ where $$ a,b,c,\alpha, ...
1
vote
1answer
34 views

Is there a name for this type of optimization problem?

I want to optimize a linear function of $(x_{1}, x_{2})$ subject to constraints that look like $1(x_{2} \geq x_{1})(b_{1}x_{1} + b_{2}x_{2}) \geq 0$ $1(x_{2} \leq x_{1})(b_{1}x_{1} + ...
1
vote
1answer
59 views

Computationally proving a linear programming solution is unique?

I have a simple linear programming problem min $c^{T}x$ subject to $Ax\leq b$. That gives me the solution I am looking for when solving in maple. My only problem is that I do not know how to check, ...
2
votes
1answer
135 views

Previous table of simplex algorithm

I have this problem of simplex method which shows cycle . Problem : Maximize $Z=10x_1-57x_2-9x_3-24x_4$ Constraint to : $ 0.5x_1-5.5x_2-2.5x_3+9x_4<=0 $, $ ...
0
votes
0answers
35 views

Searching for a matrix that yields a nonnegative solution to a linear program

Suppose I have a system of linear equations $Az=b$, where $A$ has a Vandermonde structure of the form \begin{equation} A = \left(\begin{array}{cccc} 1 & 1 & \dots & 1 \\ x_1 & x_2 ...
1
vote
0answers
23 views

Highest (lowest) index of positive time-indexed variable

I have a simple problem involving a variable $x_{it}$ representing the amount of a resource allotted to a task $i$ in time $t$. The quantity of the (renewable) resource is constrained at a value $R$ ...
0
votes
1answer
77 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.
0
votes
1answer
89 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 ...
0
votes
0answers
25 views

linear programming if then constraint [duplicate]

Can someone help me with the question below? Consider an LP for which you want to add the restriction that "onl if x1[>=]3 then x2 and x3 are allowed to be larger than 0; otherwise x2 and x3 are 0". ...
1
vote
1answer
32 views

Linear Programming Problem about optimal solution

Let $X_1$ and $X_2$ are the optimum solutions of LPP, then (a) $X = λX_1+(1- λ)X_2$, $λ \in \Bbb R$ is also an optimal solution (b) $X = λX_1+(1-λ)X_2$, $0 \leq λ \leq 1$ gives an optimal ...
1
vote
0answers
51 views

Linear programming: inequality constraints, constrain domain of weights, constrain # of non-zero weights

$x$ is a known matrix, $y$ is a known vector, solve for $w$ (weights vector) given the following constraints. $w_1 x_{1,1} + w_2 x_{2,1} + \dots + w_n x_{n,1} = y_1$ $w_1 x_{1,2} + w_2 x_{2,2} + ...
0
votes
0answers
38 views

Help with following construction of solution to a Linear Program

I need to find vector $f$ such that $(I-\rho A)f$ is an increasing vector. Some of the properties of the different parameters are: 1) $f \in R^N$ 2) $0\le\rho\le1$ 3) $A$ is a stochastic matrix ...
1
vote
1answer
164 views

Linear Programming with One Quadratic Equality Constraint

I have a problem which can be formulated as a Linear Programming with One Quadratic Equality Constraint: where variable x is n-dimensional vector and H is a Semi-Positive Definite n-by-n matrix. I ...
0
votes
0answers
14 views

Did i formulate this Linear Optimization Problem right?

My Problem is to formulate a linear optimization problem (LOP, or Linear Programming) out of the following given Information. "Let $a_1, a_2$ be given Numbers. Find Numbers $x_1, x_2$ that differ ...
0
votes
0answers
78 views

Maximizing a single variable objective in a many variable simplex with a known basic feasible solution

I'm new to LP so please excuse any obvious mistakes. I have a linear program with N+1 variables, these are represented below as $x$, which is a vector of length $N$, plus the single variable $p$. ...
6
votes
1answer
235 views

Linear Programming: More variables or more constraints; which one is better?

This is more of a practical question, rather than Math question. I have an LP which has $n$ variables and $m$ constrains, where $ n << m $. If I convert this into its dual form, I will have ...
2
votes
1answer
61 views

Solutions of the LP problem

I am asked to find all the solutions of the following linear programming problem using the simplex method. $$\min(2x + 3y + 6z + 4w)$$ $$\begin{aligned} x+2y+3z+w &\geq 5\\ x+y+2z+3w ...
0
votes
0answers
49 views

Given a set of inequalities, use what algorithm to minimize one variable?

I have the following set of inequalities: $$C_1 \le y-T_1x_1 \lt C_1+D_1$$ $$C_2 \le y-T_2x_2 \lt C_2+D_2$$ $$C_3 \le y-T_3x_3 \lt C_3+D_3$$ where $x_1, x_2, x_3$ and $y$ are non-negative integer ...
1
vote
1answer
29 views

Binary integer programming problem of a very specific form

The specificity of the problem lies in the fact that the objective function coincides with the left side of the only constraint. In other words: $$ \sum\limits_{i=0}^n a_i x_i \to \max, $$ $$ ...
0
votes
0answers
21 views

how to map the unit hypercube to area that $Ax=b$, $Cx<d$?

Let $x$ be the vector in $\mathbb{R}^n$. Define a constraint area $S$ that $$S \triangleq \{x:A x=b, C x < d\}$$ , where $A$, $C$ are constant matrix and $b$, $d$ constant vectors. Now, how ...
0
votes
1answer
132 views

Choosing pivot row in Simplex - slack variables allowed?

I have a question concerning the Simplex method to solve linear optimization problems. I have the following problem: $$ f(x,y,z) = x+2y+3z$$ Constraints: $$x+y+z \leq 3$$ $$2x+2y+z \geq 4$$ So my ...
1
vote
0answers
64 views

Integral Farkas Lemma

The context of this question is commutative algebra, however the question itself is more related to convex geometry. All necessary information is given. In the proof of Lemma 3.1.1 in the book ...
1
vote
1answer
38 views

Minimise Total $x$, Maximum $x$ or $|x|$ in integer/linear programming

Suppose we have a linear program (it may be integer, it probably doesn't matter). Suppose the variables $t_j$ give the tardiness for job $j$, and we want to minimise something to do with this ...
0
votes
1answer
86 views

Maximize $ax + by + c$

Working on a problem of comparative advantage of the economist David Ricardo, I've gone into solving a more general case of that study in which I stumbled over this question : how do we maximize the ...
0
votes
1answer
193 views

feasible region of a linear programming problem convex and concave

will the feasible region of a linear programming problem with linear mathematical relations and linear constraints, always be a convex polygon? will concave feasible regions have optimal value at ...
0
votes
0answers
51 views

Basic feasible solutions of a linear program in equational form

I'm trying to understand the simplex algorithm. For a polytope $P \subseteq \mathbb{R}^n$ of full dimension given by a set of inequalities $Ax \leq b$, there are several equivalent ways to define a ...