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

learn more… | top users | synonyms

4
votes
1answer
299 views

Writing a linear program in standard form

Usually I have been asked to write problems in standard form that have inequalities involved. However, this problem has none and I was wondering if anyone had insight on how to go about solving it. ...
0
votes
0answers
114 views

Linear Programming with Matrix Game

It seems from an easy google of "learning linear programming" that a common way of learning it is to work with Matrices that represent "games" for two players. Here is one I have stumbled across. We ...
3
votes
2answers
1k views

Can a non-extreme point be an optimal solution of a Linear Programming problem?

Consider a linear programming problem. Is it possible for an optimal solution to exist, but not at an extreme point? According to Bertsimas & Tsitsikalis ("Introduction to Linear Optimization", ...
2
votes
1answer
930 views

Adjacent basic solutions and adjacent bases

I'm reading chapter 2, "The geometry of linear programming", in Bertsimas & Tsitsiklis's "Introduction to Linear Optimization" (Athena Scientific, 1997). I'm having some difficulty with the ...
0
votes
1answer
100 views

primal and dual lp optimal?

I have a simple assignment problem. I have four tasks that can be assigned to two persons. It is possible that not every task is assigned to a person due to capacity limitations. Each task requires: ...
2
votes
1answer
155 views

Linear Programming Transformations

What is the process of performing a transformation from a given problem to another linear programming problem such that the transformed problem has an optimal solution iff the initial problem has a ...
0
votes
1answer
86 views

Recommendations of programming language / software for computer-assisted mathematics

I have always used R and Python for statistical analyses and object-oriented programming. Now, I have to perform relatively demanding (long to perform) mathematical analyses such as derivations and ...
0
votes
2answers
47 views

Enquiry to Linear Programming.

I came across this Theorem on Optimum solution to a Linear programming problem: " If $S$ is the feasible region of some linear program with objective function $ z=c^{T}\textbf{x}$ then 1) $z$ ...
0
votes
1answer
109 views

Polyhedron's Representations and spanning the Euclidian space

Let's say you have to different representations of the same polyhedron $P\neq \emptyset$: $$P=\{x\in \mathbb{R}^n\;|\;h_i^Tx\leq c_i, i=1,...,k \} =\{x\in \mathbb{R}^n\;|\;g_j^Tx\leq d_i, j=1,...,l ...
0
votes
2answers
34 views

Reduce occurrence of $x$, retain definition at $x=0$

I need to apply a gamma curve to render an output variable $(x)$, to make better use of screen real estate, and it has me scratching my head with what is probably a simple math question. For $0 <= ...
2
votes
0answers
129 views

Big M constraint question

I have a question regarding using Big M constraints to solve the following problem: Given: $a, b \ge 0$ and integers. $$2a + 5b \le 17\\ a + b \le 5\\ 3a + 6b \le 20$$ For at least two of the ...
3
votes
1answer
1k views

optimal basis and optimal solution

Determine which of the following is true: a) Consider a maximization LP in SEF. Suppose $x$ is a basic feasible solution for which all nonbasic variables have strictly negative reduced costs. Then ...
1
vote
1answer
43 views

Finding $\max_{||x||_2=1} \min_i |(Ax)_i|$

Let us define for $x \in \mathbb{R}^n$ $$M(x)=\min_i|x_i|$$ Is there a way to solve the following optimization problem: $$\max_{||x||_2=1}M(Ax)$$ for a given $A$?
3
votes
1answer
745 views

Absolute values in linear programming

Suppose I have an objective function in my LP as follows $max$ $|x|$ Based on some googling, I have found there are two ways to convert this into a standard LP. Method 1. $|x|$ = $ x^+ + x^-$ $x ...
0
votes
1answer
644 views

Sum of two polyhedra is a polyhedron

I'm reviewing for a midterm next week in an optimization course. Currently, I'm having a great deal of trouble with a review problem. The problem is as follows: Let $P$ and $Q$ be polyhedra in ...
0
votes
1answer
63 views

Can a feasible region have many 'parts'?

For example, could my constraints ever give me a feasible region composed of the unit square and a triangle with vertices (2,1), (3,1), (2,3)? (Edit: obviously this would never happen, but I am using ...
2
votes
0answers
222 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 ...
1
vote
1answer
770 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 ...
2
votes
2answers
56 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}$$ ...
3
votes
1answer
2k 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
77 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
60 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
178 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
1k 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
80 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
48 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 ...
4
votes
1answer
1k 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
28 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
1k 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
124 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
2answers
1k 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 ?
4
votes
1answer
3k 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
90 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
177 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 ...
2
votes
1answer
120 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
34 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
78 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
102 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
54 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
45 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
217 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
163 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 $, $ ...
1
vote
0answers
34 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
2answers
258 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
533 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 ...
1
vote
1answer
59 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
88 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} + ...
5
votes
1answer
560 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 ...
7
votes
1answer
2k 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
71 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 ...