Questions on linear programming, the optimization of a linear function subject to linear constraints.
0
votes
0answers
15 views
Suppose I have the tableau below for a maximization problem. For the tableau to be optimal what are values for c1, c2, and b?
Suppose I have the tableau below for a maximization problem. For the tableau to be optimal what are values for c1, c2, and b?
z x1 x2 x3 x4 x5 x6 RHS
1 c1 c2 0 0 0 0 10
...
0
votes
2answers
39 views
Linear Programming Problem?
You are about to take a test that contains computation problems worth 6 points each and word problems worth 10 points each. You can do a computation problem in 2 minutes and a word problem in 4 ...
0
votes
2answers
21 views
LP: An algorithm to decide whether a polyhedron is a subst of another polyhedron
I've encountered the following question which I am unable to solve:
$$
P = \{\vec x | A\vec x \geq \vec a\} \\
Q = \{\vec x | B\vec x \geq \vec b\}\\
P, Q \subseteq R^n
$$
Find an algorithm to ...
0
votes
1answer
26 views
Almost linear programming problem
I have a problem that is almost the typical in linear programming, but not quite. All variables take real non-negative values. Certain simple linear inequalities and equalities should hold. But what ...
0
votes
1answer
34 views
Linear Programming?
An agriculture company has 80 tons of fertilizer Alpha and 120 tons of fertilizer Bravo. The company mixes these fertilizer into two products. Product Super requires 2 parts of fertilizer A and 1 part ...
0
votes
0answers
14 views
Conic programming duality - relative interior
Consider the primal/dual conic programming problems
$$
\newcommand{\ip}[1]{\left< #1 \right>}
\newcommand{\myvec}[1]{\mathbf{#1}}
\newcommand{\bvec}[0]{\mathbf{b}}
...
0
votes
1answer
19 views
Disjunction of conjunction in linear programming
I'm trying to get my model working with less variable/constraints possible. I want the binary variable $R$ to store the result of this Boolean expression:
R = (a1 and b1) or (a2 and b2) or (a3 and ...
0
votes
0answers
10 views
Justification for discarding constraints in Fourier Motzkin elimination
In the Fourier Motzkin elimination method, constraints are separated into three categories:
1) Constraints with positive coefficients for the dimension to be projected out.
2) Constraints with ...
0
votes
0answers
43 views
The dual simplex algorithm
Following is the dual simplex algorithm, adapted from p. 283 of Daniel Solow's "Linear Programming, An Introduction to Finite Improvement Algorithms", Elsevier Science Publishing Co., Inc., 1984. I ...
0
votes
0answers
21 views
Linear assignment problem - would this constraint also be correct?
In the linear assignment problem, could the constraint $\sum_i x_{ij} = 1$ also be replaced by $\sum_j \sum_i x_{ij} = n$? Because I think this also ensures that all tasks are executed, and the ...
2
votes
1answer
29 views
Does the Duality Theorem of Linear Programming hold only in closed convex cones
I've just read the the Duality Theorem of Linear Programming. Here is the proof from my book (and my questions after it):
Duality Theorem of Linear Programming: If the primal or dual linear ...
3
votes
0answers
28 views
Rayleigh Quotient variant?
If $A$ is a covariance matrix and I want to get
$\max X^TAX$ where each value of $x$ is between -1 and 1.
Is there a closed-form solution for this?
I understand when $X^TX = 1$ this becomes the ...
1
vote
2answers
62 views
Forbidden range for a linear programming variable
I would like to express a linear program having a variable that can only be greater or equal than a constant $c$ or equal to $0$. The range $]0; c[$ being unallowed.
Do you know a way to express this ...
0
votes
0answers
48 views
Linear Programming with percentage constraints
I need some guidance with this Linear Programming problem,
I want to maximize profits subject to different constraints, the problem is
Maximize Goods subject to Min and Max Percentage Volume and ...
0
votes
0answers
7 views
How is stochastic optimization accomplished by GAMS solvers?
I'm looking for a quick description of how stochastic optimization is done by numerical solvers. It was explained to me that for a stochastic programming problem, GAMS 1. simulated draws from each ...
1
vote
2answers
43 views
linear programing : maximize $\sum \limits_{i=1}^{n} C_i$ where $C_i$ is circumference of circle with center at $\{x_i,y_i\}$
given n points on $\mathbb{R^2}$ $\{(x_1,y_1),(x_2,y_2),\dots,(x_n,y_n)\}$
formulate a linear program to maximize the sum of the circumference of all circles so any two circles won't intersect (two ...
0
votes
1answer
24 views
Linear programming alternate optimum solutions
**Q- The Optimum of a linear programming problem occurs at (1,2,3) and (-1,0,7) then the optimum also occurs at?
a)(2,4,6) b)(0,3,5) c)(0,1,5) d)(3,2,1) e) None of the above.
When we are given two ...
0
votes
0answers
31 views
Exam Review Homework: Geometry and Algebra of Linear Programs
I have two connected problems:
7.6 Given the solutions $P = \{(1,1),(2,5),(3,3),(4,6),(5,2),(6,3)\}$ what linear inequalities describe the convex hull of $P$? What are its extreme points?
My ...
1
vote
0answers
17 views
Check feasibility of a system of integer linear equations
I'm currently working on a very large integer linear programme which cannot be solved within any reasonable time.
The initial set of linear equations S={Ax<=b) is feasible.
I want to add more ...
2
votes
1answer
44 views
Linearization of a product of two decision variables
I am trying to solve a problem that involves constraints in which products of two decision variables appear.
So far, I read that such products can be reformulated to a difference of two quadratic ...
1
vote
1answer
33 views
Why $(1,\textbf{0}) \not\in \{(r,\textbf{w}): r=tz_0-\textbf{c}^T\textbf{x}, \textbf{w}=t\textbf{b}-\textbf{Ax}, \;\textbf{x}\geq\textbf{0}, t\geq0\}$
I'm learning about linear and nonlinear programming and on the chapter about duality I have the following statement and proof I can't understand:
minimize $\textbf{c}^T\textbf{x}$
subject to ...
1
vote
1answer
17 views
linear inequalities using LP solutions not from simplex
I am trying to solve a set of inequalities using linear programming (LP) with objective function set as a constant.
Usually this set of inequalities would have many solutions all of them in the ...
0
votes
0answers
21 views
Proving equivalence between basic feasible solution and vertex
I stumbled upon this proof of the Bertimas book on Linear optimization and I don't see what the "key ingredient" is that makes it work.
Baxic feasible solution $\implies$Vertex
Let $x^*$ be a ...
0
votes
0answers
20 views
Linear Optimization: Minimizing number of CDs
I have 16 files I need to put on CDs with a capacity of 780 MBs.
(240, 462, 117, 560, 379, 110, 341, 294, 503, 469, 90, 63, 617, 493, 524, and 396)
How do i make a linear program to minimize the total ...
0
votes
1answer
8 views
What if objective function $Z$ is also in the constraints?
What if objective function $Z$ is in the constraints?
To construct the dual form for this problem? how do I approach to this problem?
Maximize $\;\;\;\;\;\;\; z$
subject to $$\;\;\;z - ...
0
votes
0answers
14 views
Finding segment between between beginning and ending point
I have y ax that starts at position 20 and ends at position 150
Now to get the segment of ...
1
vote
0answers
6 views
Symbol or name for Basismatrix of Linear Programming
This question is about the Basismatrix in the context of Linear Programming.
Basically (haha!) we have the Matrix of the standard (or normal) form, which consists of (A|E) with the coefficient matrix ...
0
votes
1answer
16 views
Writing an unconstrained variable as an equality
I am working on some problems on the Simplex Algorithm for Linear Programming. In order to apply the simplex algorithm, the LP must be in standard form. If the constraint is an inequality with a ...
1
vote
1answer
40 views
Minimum distance of extreme points of polyhedra
Let $P = \{x \in \mathbb{R}_{\geq0}^n \colon Ax \leq b\}$ with $A \in \mathbb{R}^{m \times n}$ and $b \in \mathbb{R^m}$. Let $E \subseteq P$ be the extreme points of $P$.
Can anything be said about ...
0
votes
0answers
29 views
Approximation of optimum for two linear programs
Suppose you got two linear programs.
They are the same except that one has a shifted objective by a positive constant
(1)
$$\min c^Tx$$
(2)
$$\min c^Tx + d$$
For (2) there exists a ...
3
votes
1answer
35 views
Trouble seeing why this is the dual of an LP
$A$ is an $m \times n$ matrix. Using the notation $x=(x_1, \ldots, x_n)$, $z=(z_1, \ldots, z_m)$, and $y=(y_1, \ldots, y_m)$, I'm reading that if the primal LP is
$$
\min 0x_1 + 0x_2 + \cdots + 0x_n ...
0
votes
0answers
15 views
Perturbation factor terminology
This is a question about usage of English. I have an inequality $a^\textsf{T}x \leq b$, where $a$, $b$, and $x$ are vectors in $\mathbb{R}^n$. Now, I want to perturb this inequality by a small amount ...
2
votes
2answers
39 views
How can I calculate if a given point is wrapped inside a pentagon?
If I have a pentagon and I know the coordinates of it's nodes, how do I calculate if a point is wrapped inside it?
An example to clarify what I mean:
Assume that we know the coordinates of the ...
0
votes
0answers
17 views
Name search for special Linear Mixed Integer Programm
I am looking for a name for the following question in literature!
(and if you know it, then it would be great)
I couldn't find it and due to wide audience here, presumably you know more. Thank you
...
0
votes
0answers
7 views
Feasability of infinite number of linear inequalities
Consider a continuous function $f:A\to\mathbb{R}^N$ for a closed interval $A\subset \mathbb{R}$. Are there suffieint or necessary conditions for the existence of a solution $w\in\mathbb{R}^N$ such ...
0
votes
0answers
36 views
Prove solution does not exist for inequalities system
I have an inequalities sytem like the following:
Example
> x+y+z <= A
> x+y <= B
> x+z > C
> y+z > D
> x >= E
Let A,B,C,D,E be any ...
0
votes
1answer
31 views
Projection onto Polyeder
I know how to projects onto a linear subspace of $\mathbb R^3$, but how to project a point $x$ onto an polyhedron given as the intersection of three halfspaces
$$
\langle y_1, x \rangle \ge c_1 ...
0
votes
1answer
31 views
Can someone explain the effects of degenerate basic feasible solutions in the simplex algorithm?
I was given this on an assignment sheet, and am now using it to revise from...I cannot remember the issues that arise from degeneracy of basic feasible solutions...
Let $P$ =$\{x\in \mathbb{R}^n ...
1
vote
0answers
24 views
Why is this simplex procedure not working? $\min z = y - x + 1$
I have read of two ways to solve this program with the Simplex algorithm. One worked and the other didn't.
The only difference is that, in the one that didn't work, I rewrote the function. I will ...
0
votes
1answer
10 views
Is there relations between earth mover's distance and vector norms?
Say I have two vectors $a$ and $b$. Can I estimate $\mbox{EMD}(a,b)$ via some combination of things like $\|a-b\|_p$ and such?
0
votes
1answer
11 views
Linear programming: Maximize minimum of linear functions
For a project I need something solved, it screams linear programming.
If I get the problem in "standard" form I should be able to solve it using the simplex method. But I don't see how to get it in ...
2
votes
1answer
74 views
Linear Algebra 101 - Optimizing inequalities
I am considering the region contained in $\mathbb{R}^2$ consisting of all the points that satisfy all the following inequality:
$-4 \leq y < 4 \\
-9 \leq 2x + y \leq 9 \\
-9 \leq x + 2y \leq 9 \\
...
0
votes
0answers
12 views
Deterministic equivalent construction
I have a 4-stage scenario tree. At each stage , i have two branches. So in total I have 15 nodes.
I solve this problem in its node-variable formulation and it takes a lot of time.
Also the ...
1
vote
1answer
25 views
linear systems&normalize
suppose $f: \mathbb{R}^n \rightarrow \mathbb{R}^n$ be a linear function which can be represented by a $n \times n$ matrix. Then the jacobian of $f$ is the same as the function for $f$. But I now want ...
2
votes
0answers
19 views
The importance of the full-row-rank assumption for the simplex method
Consider a linear programming model in the usual form ready for applying the simplex method. I understand that having the constraint equations' coefficient matrix $A$ be of full row rank means not ...
0
votes
0answers
27 views
Union of all sets of optimal solutions to a perturbed linear programming problem
Please let me know if you have some ideas on how to approach this proof? I got stuck part-way through.
The following linear program is a function of $\theta$,
$
\begin{array}{ll}
\min & c^\top x ...
1
vote
1answer
13 views
the differences and relationship between linear independent and affinely independent
When learning optimization, I heard the two related concepts on linear algebra:
linearly independent and affinely independent. ...
0
votes
1answer
24 views
Linear Programming : Alternative to summation of absolutes in constraints
I am solving a placement problem, i.e. map $integers\ i\ from\ 0\ to\ 6$ to $(x_i,y_i)\ st\ 1 \le x_i,y_i\le 3$ such that :
$ \sum\limits_{i=0}^6 \sum\limits_{j=0}^6 Cost(i,j)*(|x_i - x_j | + | y_i ...
0
votes
1answer
30 views
Need help with minimum cost network flow problems
Consider the tree solution for the following minimum cost network flow
problem:
The numbers on the tree arcs represent primal flows while numbers on the
nontree arcs are dual slacks.
(a) Using the ...
0
votes
2answers
39 views
Maximize $\ x+\frac32 y\ $ subject to…
I am stuck on the following problem:
Consider the linear programming problem:
Maximize $x+\frac32 y$
subject to $$2x+3y \le 16, \\ x+4y \le18,\\ x \ge 0,y \ge0.$$
If $S$ ...
