The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
18 views

Conversion into linear program

I have an optimisation problem with decision variables that are multiplied with another (a weighted average is calculated). I'd like to convert it into a linear program. I found this link that ...
0
votes
1answer
17 views

Beginner Simplex problem

Good evening, I have started studying the simplex method for some examinations I would like to take, and to be perfectly honest, I am stuck really bad. The basic examples and exercises are simple, ...
0
votes
1answer
19 views

Lexicographic Pivoting Rule: Why does that work?

On purpose, I do not write details about it, because I am interested in the intuition and not the details. But if someone asks for it, I can do that. So my question: Could anyone help me with the ...
1
vote
2answers
36 views

Represent if-else or OR condition in a linear equation (optimisation with simplex algorithm)

I would like to write some linear equations and inequations to state that the sum of all possive x - C is smaller than L. As my ...
0
votes
0answers
19 views

Find all optimal solutions by Simplex

Let "stable operation" be an operation on a simplex tableau such that the entering variable has a reduced cost of 0. Recall that a pivoting operation will not change the objective value if either the ...
0
votes
0answers
17 views

General formula for n-Simplex side-lenghts given n-volume and angles

Given a flat triangle's three angles $\phi_i $, and its area $A$, you can calculate the $i$th sidelenght $s_i$ (using Einstein's sum-convention) like so: $$ s_i=\frac{\sqrt{2A} \sin \left(\phi ...
3
votes
1answer
41 views

Simplexes in $\mathbb R^n$ have at most $n+1$ points

This is an exercise from the book Espaços Métricos (metric spaces) by Elon Lima. I'm translating it (the part of it that I'm having trouble with): Show that if $X\subset\mathbb R^n$ is such that ...
1
vote
0answers
25 views

Two-phase simplex

The upper part of the image attached is the question and lower part is the solution. I did the exact same table as table4 in the picture, yet I put the ratio of [2] as 0.5/0.5=1 instead. Could ...
1
vote
1answer
35 views

Can number of constraints be less than number of variables in Linear Programming?

In standard form of LP we have $n$ variable and $m$ constraint. In simplex algorithm we set all non-basic variable to zero and at most $m$ basic variable have positive value. if $m < n$, then at ...
0
votes
1answer
44 views

solving LP problem : no optimal solution exists?

$$\max[Z(x,y)=3x+2y]$$ $$-x+y\le 1$$ $$-x+2y\le4$$ When I tried to solve the above maximization LP problem using the simplex method, from the first iteration, all basic variables became negative. ...
1
vote
2answers
29 views

Correlation between Binary and N-dimensional simplexes

I found an interesting correlation between binary numbers and $n$-dimensional simplexes and I'm trying to find where I can find more information on the subject. I noticed that binary representations ...
0
votes
1answer
62 views

Linear programming algorithm that minimizes number of non-zero variables?

I have real world problems I'm trying to programmatically solve in the form of $$Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$$ Subject to \begin{align} & a_{11} x_1 + a_{21} x_2 + \cdots + a_{n1} ...
1
vote
0answers
35 views

product of barycentric coordinates over a simplex

Show that: $$\int_K \eta_0^{\alpha_0}(x)\cdots\eta_n(x)^{\alpha_n}dx=\frac{{\alpha_0}!\cdots{\alpha_n}!n!|K|}{(\alpha_0+\cdots+\alpha_n+n)!}$$ where $\eta_i$ barycentric coordinates and $K$ is a ...
2
votes
1answer
54 views

Integral over a simplex

Let $C_k$ be the $k$-simplex. I know that $$\int_{C_k} \prod_{i=1}^k x_i^{\alpha_i-1} dx_i = \frac{\prod_{i=1}^k \Gamma(\alpha_i)}{\Gamma\left(\sum_{i=1}^k \alpha_i\right)} \equiv ...
1
vote
0answers
20 views

Computing the Optimal Simplex Tableau for Linear Programming

I am learning in my class about computing the optimal simplex tableau. I learned that, if you have an initial basic feasible solution, you can apply a series of formulas to compute the optimal ...
0
votes
0answers
16 views

Degeneracy in Simplex Algorithm

According to my understanding, Degeneracy in a linear optimization problem, occurs when the same extreme point of a bounded feasible region $X$ can be represented by more than one basis, that is not ...
0
votes
0answers
15 views

When can i solve simplex tableau

I saw exercises where they give an objective function ( without restrictions ) and a simplex tableau to be completed , if you can solve How do I know when it may solve the tableau ? What are the ...
0
votes
1answer
52 views

Prove max f(x) = -min -f(x)

How do I prove : $$max f(x)= - min -f(x)$$ I am trying to prove this, and have tried to use my book but I am stuck.
2
votes
1answer
24 views

Singular chain complex for integration - pinching on boundary

Singular chain complex, as far as topology are concerned, is just continuous map from standard simplex, and the choice of using simplex over other shape is immaterial. But for integration on manifold, ...
1
vote
0answers
27 views

Explanations about the volume of a regular simplex

I'm really sorry, this may sound ridiculous but I can't understand the Wikipedia explanation about the volume of regular n-dimensional simplices, here. In particular, these two sentences make no ...
0
votes
0answers
25 views

Pachner moves for graph of 4-valent nodes

For 3-simplices (i.e. tetrahedra), I understand the basic idea behind the Pachner moves 1 $\leftrightarrow$ 4, which takes one tetrahedron and replaces it with four (or vice versa), and 2 ...
0
votes
1answer
50 views

Big-M Simplex Method Returns Unfeasible Solution

Consider the following linear programming problem: "Minimize 2x1 + 3x2 subject to the constraints 2x1 + x2 ≥ 4 2x1 - x2 ≥ -1 x1,x2 ≥ 0" Since there are ≥ signs in both ...
0
votes
0answers
50 views

Chains and associated delta complexes (Algebraic Topology, Allen Hatcher)

Why does the fact of a 2-chain being a cycle imply that in its associated delta complex every 1-simplex comes from exactly 2 different 2-simplices? (it appears in the last paragraph of page 108, where ...
0
votes
1answer
36 views

Solve this linear program using 2 phase simplex

Minimize $2x_1 + 3x_2 + 3x_3 + x_4 − 2x_5$ Subject to $x_1 + 3x_2 + 4x_4 −x_5 = 2$ $x_1 + 2x_2 − 3x_4 +x_5 = 2$ $−x_1 − 4x_2 +3x_3 = 1$ $x_1, x_2, x_3, x_4, x_5 \geq 0$ Im not sure if im doing ...
0
votes
0answers
24 views

Simplex Method Geometrically

Suppose that at some iteration of the simplex method the slack variable $x_s$ is basic in the $i$th row. Show that $$ \large y_{ij\leq 0, j =1,\ldots, n, j \neq s } $$ then the constraint ...
0
votes
0answers
23 views

Solve equation with simplex method

I have equation below and I'm newbie to this method. Can you help me with tutorial or maybe with steps to solve this equation? I know I can use simplex tables, but I don't know a good explanation of ...
1
vote
0answers
17 views

How is distance between two points defined in barycentric coordinates?

Hope someone can help. I have this 3-d simplex (a tetrahedron) and its vertexes have barycentric coordinates defined as follow: $A_1=(1,0,0,0), A_2=(0,1,0,0), A_3=(0,0,1,0), A_4=(0,0,0,1)$. I am ...
0
votes
1answer
70 views

Linear programming and the simplex method

I am trying to solve this system of equations. My approach would be to introduce slack variables and then somehow use the simplex algorithm to solve this. Can anyone show me how this is done?
1
vote
0answers
56 views

Proof of Simplex Method, Adjacent CPF Solutions

I was looking at justification as to why the simplex method runs and the basic arguments seem to rely on the follow: i)The optimal solution occurs at some vertex of the feasible region (CPF points) ...
0
votes
0answers
38 views

Volume of the set of solutions of two linear inequalities on the simplex

I need an analytical formula for the volume of the set of solutions of two linear inequalities on the N-dimensional simplex $\Omega$. Two be more precise, if $u$ and $v$ are two vectors of ...
0
votes
1answer
39 views

Simplex method - infeasible basic variables

I am working on an optimization problem right now, and I am using the simplex method on the initial tableau. At first, the basic variables are all non-negative and are equal to the slack variables. ...
0
votes
1answer
43 views

Dual simplex doubt (unrestricted)

I have this two problems and i only want to find the dual form: $\begin{gather} max\hspace{.1cm}z =5x_1+6x_2\\ s.t\hspace{.1cm}x_1+2x_2=5\\ -x_1+5x_2 \ge 3\\ x_2 \ge 0\\ x_1\hspace{.1cm} ...
1
vote
0answers
36 views

Least square / Linear regression over a simplex

I have to solve the following least square problem: $$\hat{x} = \arg \min_{x \in S} \|Ax - b\|^2$$ If $S = \mathbb{R}^n$, then the solution is given by $$\hat{x} = (A^TA)^{-1}A^Tb$$ having posed ...
0
votes
0answers
21 views

Quadratic programming over a simplex

I have to solve the following problem: $$\left\{\begin{array}{l}\hat\theta = \arg \min_{\theta} \theta^TQ\theta + \theta^Tl\\ \text{s.t.}\\ \sum_{i=1}^n \theta_i = M\\ \theta_i \in [0, M] ~ \forall i ...
0
votes
0answers
31 views

Maximize Net Profit with Simplex Tableau

I have a profit maximization problem and have been asked to solve it using the simplex tableau method. The thing is as far as I can tell there are no constraints present, so I'm really not quite sure ...
1
vote
0answers
27 views

simplex in MAPLE

I am trying to solve a large system of linear inequalities (about 500 variables) subject to the nonnegativity condition on the variables.Call this system500 for future reference. I do not need to ...
1
vote
1answer
71 views

simplex M-method minimization problem

Solve using the simplex method. Identify the solution of the dual in the final simplex tableau Minimize: $$z=12x_{1}+4x_{2}+2x_{3}$$ **Constraints:**$$ x_{i}\ge 0$$ $$-6x_{1}+3x_{2}\ge 9$$ ...
0
votes
0answers
34 views

Least squares and simplex

I am interested in the linear least square problem with the solution with the following constraints : $$ \min_x \|Ax-b\|^2$$ subject to $0 \le x_i \le 1$ and $\Sigma_{i=1}^n x_i= 1$. Because of the ...
0
votes
0answers
40 views

Simple enumeration of discrete simplex

I'm looking for a computationally nice enumeration of the $n$-dimensional discrete simplex $$\Delta^n_N = \{ x \in Z^{n} | 0 \leq x_i \leq N \, \text{and} \, x_1 + \cdots x_n = N \}$$ I have an easy ...
1
vote
0answers
36 views

Executing Branch and Bound using a Simplex tableau

I'm studying the branch and bound method and how it is used in conjunction with a simplex tableau. The issue I'm struggling with is how you incorporate the branches in your tableau to find out ...
0
votes
0answers
27 views

sensitivity analysis - help!

Hi guys I am doing a quesetion on simplex method and am stuck on the second part of the sensitbity analysis question: I am stuck on the part that is asking for 12 + n. I know that I am changing ...
0
votes
0answers
87 views

Casio fx-83gt - help! Linear Programming

Hi guys I'm studying a module called Operational Research and in particular linear programming. I am doing the simplex method and as anyone who studies linear programming would know, you need to ...
2
votes
1answer
73 views

Prove vertices of a simplex are affinely independent

I'm given that the definition of a simplex $T$ is $x \in\mathbb R^n$ such that $x$ satisfies $n+1$ linear inequalities: $(u_k, x) \lt c_k$ for $k = 1,\ldots,n+1$ (i.e. $T$ is the intersection of $n+1$ ...
1
vote
1answer
39 views

Above what order of magnitude a pure cutting-plane algorithm must be forgotten in favour of branch-and-cut?

Crawling the web on the subject of the cutting-plane algorithm, I have seen everywhere that a pure cutting-plane method cannot be used for numerical instability reasons after some iterations. But do ...
2
votes
1answer
60 views

Can Gomory's cutting plane be used to solve Mixed Integer Linear Programs?

Do you know if Gomory's cut can be used to solve MILP problems ? I have read that Gomory's cut is useful when all variables are integer, but what if just some of them are integer ? Is is necessary ...
1
vote
0answers
92 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 ...
1
vote
2answers
89 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
1answer
56 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 ...
1
vote
1answer
42 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
13 views

Using the simplex to define a probability distribution

I am reading a paper where a probability distribution with n categories is being defined in terms of a vector $\mu = <m_1, m_2, ... m_n>$. The authors define this as a vector $\mu \in ...