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

learn more… | top users | synonyms

0
votes
1answer
285 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
177 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
55 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
49 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
27 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
58 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
34 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
22 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
75 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
82 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
30 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
47 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
150 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
202 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
59 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
122 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
61 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
84 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
182 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
48 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 ...
0
votes
0answers
47 views

Open loop minimization for a inventory control system

I have read in a book (dynamic programming and optimal control by Bertsekas) that in case of inventory control system, with open loop minimization of the cost, we select all orders $u_0, \dots, ...
1
vote
1answer
50 views

Solving a three variable LP graphically to show a case where there is no feasible solution

John will spend £5 of his Christmas money on plain and milk chocolates. He can buy boxes at £2 each. These contain 25 plain and 25 milk chocolates. He can buy single plain chocolates ...
0
votes
2answers
103 views

Minimizing the sum of absolute values with a linear solver

I need a linear program to minimize the sum of several absolute values, but the inclusion of an absolute value means the linear solver won't work. I know there are ways around using an absolute value, ...
1
vote
1answer
67 views

Fitting Vogel's formula for phyllotaxis to an actual plant.

A simple model for the arrangement of florets in a sunflower was given by Vogel: $r = c\sqrt{n}$ $\theta = 137.508 n$ Where $r$ and $\theta$ are polar coordinates, $c$ is some constant and $n$ is ...
0
votes
1answer
75 views

How to enforce a constraint that a decision variable can only take 1 of $k$ integer values?

How would you enforce the constraint that $x$, a decision variable, can only take values -3, 7, or 19? I think I probably need to introduce a binary variable here but not sure where to start. Thanks. ...
2
votes
0answers
125 views

Is simplex method weaker than other methods?

Given linear program: $$ \text{min } x_1 - x_2 + 2 x_3 $$ s.t.: $$ -3x_1 + x_2 + x_3 = 4 $$ $$ x_1 - x_2 + x_3 = 3 $$ $$ x_i \geq 0; i = \{1,2,3\} $$ solution by simplex method (with double pass) is ...
0
votes
2answers
560 views

Solving a 2*3 game with graphical method in game theory

Solve the following game. $$ \begin{pmatrix} 1 & 2& 3 \\ 4 & 2 & 1 \\ \end{pmatrix} $$ Since this is a $2\times3$ matrix I used the graphical method ...
0
votes
1answer
46 views

Designing an algorithm to determine if a linear combination of k-1 sets is contained in the k-th set .

I am trying to solve the following problem - given $k$ sets : $A_1,A_2,...,A_k$ containing $O(n)$ integers each I need to design an algorithm that will determine if there is such a group of elements ...
3
votes
1answer
203 views

Solving special boolean equation set

I have boolean equation sets that look like this (where ^ means xor): eq 1: x1^x3^x5^x6^x9^x10^x11^x13^x17^x18 = 0 eq 2: 1^x1^x3^x10^x12^x17 = 0 eq 3: 1^x2^x3^x5^x8^x10^x14^x16 = 0 ...
0
votes
1answer
96 views

Linear programing: Multiple slack variables

I have to convert folloving problem: $$ min\{|x_1| + |x_2| + |x_3|\ |\ \text{conditions..}\} $$ to linear program (if it is possible). Since $|x_1| = max\{x_1,-x_1\}$, i have: $$ x_1 \leq z_1 $$ $$ ...
0
votes
2answers
49 views

A linear programming to obtain “canonical basis of convex cone”

In my research a I need to solve the linear equation (getting its null space) under some constraints. The matrix is given below: The constraints shall be (x1...x[16]>0, x[17]...x[20] arbitary...) ...
2
votes
0answers
78 views

Higher dimensional Euclidean geometry problem

In my engineering/physics research, I am facing one math problem which I believe should be well established in mathematics... I have a linearly spanned space given by the column vectors of the ...
0
votes
0answers
134 views

linear program-Simplex method-Dual problem

At an exercise I am asked to solve a linear program using the simplex method(in Matlab).Then I have to formulate the dual of this problem and read off an optimal solution of the dual problem from the ...
2
votes
1answer
42 views

How to show two linear programs are equivalent?

We know that 1-norm is defined as $\|v \|_1 = |v_{1}| + \dots + |v_{n}|$ for the vector $v = \left(v_1, \dots, v_n\right)^T$. Suppose we have program (a) $$ \min\limits_{x} \|Ax-b\|_1 $$ and ...
4
votes
0answers
60 views

Minimizing the distance between points in two sets

Given two sets $A, B\subset \mathbb{N}^2$, each with finite cardinality, what's the most efficient algorithm to compute $\min_{u\in A, v\in B}d(u, v)$ where $d(u,v)$ is the (Euclidean) distance ...
1
vote
1answer
78 views

First-order necessary condition for relative minimum point

I'm studying linear and nonlinear programming and I came across with the following proposition : given $\rm x\in\Omega$ we are motivated to say that a vector $\mathbf d$ is a feasible direction at ...