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

learn more… | top users | synonyms

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
73 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
80 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
146 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
194 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
48 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
20 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
118 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
60 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
37 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
180 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
47 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
97 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
65 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
74 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
124 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
552 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
202 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
95 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
40 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
59 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
75 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
64 views

How to solve a linear program with OR constraints

I have $n$ people. I want assign them to $c$ jobs. A job may be not assigned at all or there must be a minimum and maximum number of people assigned to it. $n$ is about 4000 and $c$ is about 1000. ...
1
vote
2answers
2k 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
1answer
42 views

Primal simplex algorithm

I have the following linear program: $f(x)=2x_{1}+18x_{2} -> min$ $80x_{1}+100x_{2}>=100$ $20x_{1}+200x_{2}>=300$ $80x_{1}>=1.5$ $x_{1},x_{2}>=0$ In standard form: ...
0
votes
0answers
21 views

totally uni modular matrices with binary variables

I have this problem A*X<=B A is totally uni modular matrix, X is binary vector { 0 , 1} values . any help for finding polynomial algorithm for solving this problem?
2
votes
1answer
154 views

comparison of simplex and shortest path method

In mathematical optimization, Dantzig's simplex algorithm (or simplex method) is a popular algorithm for linear programming. The journal Computing in Science and Engineering listed it as one of the ...
-1
votes
1answer
43 views

Linear programming problem-optimal solution

I'm having the following linear programming problem: $$\begin{align} \max \quad & 2x_{1}+6x_{2}+3x_{3}, & \\ \text{s.t.} \quad & -3x_{2}+a x_{3} \geq2, \\ & x_{1}+5x_{2}+2x_{3} =2, \\ ...
0
votes
0answers
250 views

How to linearize the product of two continuous variables in linear programming

I have a question when I deal with a linear programming model. The situation is that: I have some constraints in the model. All the constraints are linear, except some terms, which is the product of ...
5
votes
2answers
137 views

Almost a linear program. How to solve efficiently?

How can one go about solving this optimization problem efficiently? Unfortunately it is a maximization instead of a minimization, which stymied my attempts at converting it into an LP. $$ ...
1
vote
0answers
22 views

Reference for a Linear Programming result

I would like to know some reference for a result from Linear Programming. The function $F(s)$ to be maximized depends linearly on the m+1 values, say $x_i$, and the constraints for $x_i$ are linear ...
0
votes
0answers
130 views

finding the minimum number of lines to cover all zeros in an assignment probem

I have been trying to follow the following steps to find the minimum number of horizontal and vertical lines that cover all the zeros in an assignment problem using Hungarian method: Tick all ...
0
votes
1answer
103 views

Are my linear program equations correct?

Here's the problem: "An electronics company has a contract to deliver 21,475 radios within the next four weeks. The client is willing to pay 20 dollars for each radio delivered by the end of the first ...