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

learn more… | top users | synonyms

3
votes
1answer
19 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 ...
1
vote
1answer
56 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 ...
2
votes
1answer
31 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
52 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
0answers
71 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\\ ...
5
votes
1answer
113 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 ...
0
votes
0answers
22 views

Converting an LP to a standard form

I have an LP that is : $ max_{x,y,z} 3x -y +z $ subject to $-1\leq x \leq 1 $ $-1 \leq y\leq 1 $ $x+y+z =1 $ The answer seems to be : Substitute $x:=a-1 $ $ y:= b-1 $ $ z:= c-d $ where $ ...
1
vote
2answers
745 views

Simplex algorithm - primal or dual?

As far as I know there are two simplex algorithms - primal and dual. They have different halting criteria etc. Before using simplex I have to make a standarization of the LP. So when do I use ...
1
vote
0answers
35 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
32 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 ...
1
vote
1answer
69 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]_+ - ...
1
vote
1answer
764 views

Linear Programming Inventory Problem

I'm still trying to get used to the nature of these problems and I'd appreciate some further explanation. ...
1
vote
1answer
28 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 ...
0
votes
1answer
23 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
46 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, ...
-8
votes
1answer
70 views

Question on linear programming problem

Maximize $Z=4x-2y-z$, subject to constraints $x+y+z\le3$, $2x+2y+z<=4$, $x-y<=0$ $x\ge0,y\ge0,z\ge0$. I can't find the ans of this question please someone help me
0
votes
1answer
221 views

Finding the number of basic/zero variables at an optimal corner point in linear programming

Draw a graph of the following problem $$\begin{align}4x+3y &\leq 180 \\ 7x+4y &\leq 280 \\ y &\leq 40 \\ x &\geq 0 \\ y &\geq 0\end{align}$$ a) If the problem is to ...
2
votes
1answer
117 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
1answer
32 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
45 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, ...
0
votes
1answer
47 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
0answers
32 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
21 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
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". ...
0
votes
1answer
65 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
0answers
40 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
36 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
0answers
76 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
66 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$. ...
0
votes
1answer
64 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 ...
0
votes
0answers
42 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 ...
2
votes
1answer
53 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 ...
6
votes
1answer
74 views

Why is there n-1 different objects in a n by n matrix game like Bejeweled?

For games that consists of a grid, and is similar to the concept like bejeweled: has an n by n matrix and n-1 different objects. What is the reason for this? Why not have more than n-1 different ...
1
vote
1answer
78 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 ...
3
votes
2answers
649 views

Financial Linear Programming Problem

I'm very new at linear programming and I'm trying to figure out a way to approach this problem below: ...
1
vote
1answer
27 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
13 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 ...
1
vote
0answers
50 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 ...
0
votes
1answer
81 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 ...
1
vote
1answer
34 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
0answers
34 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
38 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, ...
4
votes
0answers
50 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 ...
7
votes
2answers
243 views

Finding the payoff matrix of a game

A two player zero-sum game can be represented by a $m\times n$ payoff matrix $M$ having $m$ rows and $n$ columns with values in $[0,1]$. The value $M(x,y)$ represent the payoff given to player $1$ ...
1
vote
1answer
43 views

Fitting Vogner'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 ...
1
vote
1answer
43 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
62 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
63 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 ...
0
votes
1answer
46 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. ...