Stack Exchange Network

Stack Exchange network consists of 175 Q&A communities including Stack Overflow, the largest, most trusted online community for developers to learn, share their knowledge, and build their careers.

Visit Stack Exchange

Questions tagged [simplex]

For questions on the $n$-simplex, an $n$-dimensional polytope with $n+1$ points.

0
votes
0answers
23 views

LP - Simplex - Two Phase Method - Multiple Solutions

Given the following lp: MIN Z = x1 + 2x2 + 3x3 s.t. x1 + x2 + x3 = 1.0 x3 <= 0.8 x2 = 0.5 x1 >= 0.0 x2 >= 0.0 x3 >= 0.5 The single optimal solution ...
0
votes
1answer
13 views

How to get $B^{-1}$ from simplex table?

In each iteration of the simplex method the table has the form: I'm reading "Introduction to linear optimization" by Bertsimas and given the following example of a linear program: An optimal table ...
0
votes
1answer
12 views

Dihedral angle of a regular simplex in $n$ dimensions

For the regular simplex on $(n+1)$ points in $n$ dimensions, what is the dihedral angle i.e. the angle between two of the faces?
0
votes
1answer
20 views

Explicit affine transformation between simplex and subsimplex

Take a simplex $\mathcal P_{n}$ with corner points $[00\dots00]$, $[10\dots00]$,$\dots$,$[11\dots11]$ in $\mathbb R^{n+1}$. Slicing by a hyperplane $\sum_{i=1}^{n+1}x_i=t$ where $0\leq t\leq n$ gives ...
0
votes
0answers
49 views

Simplex method: why x >= 0

I'm using the simplex method for quadratic optimization using Gurobi tool in R. I found this paper: The simplex method for Quadratic programming. In this paper they say for convex programming, we ...
1
vote
1answer
11 views

What is the characteristic cone of a system with infinite linear inequalities?

Suppose that I have a system of linear equations for a variable $x\in\mathbb{R}^n$: $$a_i^Tx\ge b_i,\quad i\in I,\quad (1)$$ where $a_i\in\mathbb{R}^n$ and $b_i\in\mathbb{R}$ for all $i\in I$, and $...
0
votes
1answer
13 views

All regular simplexes are congruent

In n dimensional Euclidean space, I read that the definition of the regular simplex is the convex hull of n+1 points such that: (i) the distance from any of the points to their centroid is constant. ...
0
votes
1answer
26 views

Terminating condition of Simplex Method - Stronger termination conditon

My textbook states "If there are no negative values in the top row of the Simplex tableau, then we have reached optimality" That seems intuitive enough. However, I am wondering if the following, ...
0
votes
0answers
10 views

Independence of Vertex Ordering in (Combinatorial) Fundamental group

A combinatorial definition for the fundamental group is to introduce generators $g_{ij}$ for each pair of vertices $v_i,v_j$ for which $i<j$. And $g_{ij}g_{jk}=g_{ik}$ whenever $v_i,v_j,v_k$ span a ...
0
votes
1answer
28 views

Degeneracy Condition

I understood that when plotting the feasible area there had to be an intersection with more than two lines. In the case of: $$\text{Max } z=2x_1+x_2$$ S.T $$ \begin{cases} 4x_1+3x_2\leq 12\\ ...
-1
votes
1answer
25 views

Basic Columns In Simplex

On the following note it says that if a non basic column has no positive coefficient so this is the case of unboundedness. What non basic column refer to?
1
vote
1answer
22 views

Hint wanted: Any order-preserving $\phi:[m] \to [n]$ can be decomposed uniquely as composition of an injective and a surjective function

Let $[n]=\{0,1,...,n\}$. I would like to show that that Any order-preserving (meaning if $i \leq j$, then $\phi(i) \leq \phi(j))$ $\phi:[m] \to [n]$ can be decomposed uniquely as composition of an ...
0
votes
1answer
31 views

How to prove the following homology group isomorphism?

I am new in this part. Can anyone help me to solve this question? Thanks! Let $K=K_1\cup K_2$. $K_1 \cap K_2$ is $r$-dimension. Here $K, K_1 $ and $K_2$ are all simplicial complex. Then the ...
0
votes
2answers
71 views

How to calculate minimax value with simplex method?

For the LP problems with only inequality constraints, I know how to use simplex method to give an optimal solution. However, when I want to calculate the minimax value, how should I use the simplex ...
0
votes
0answers
16 views

Volume of a simplex: Specific case

I'm trying to see why for $x \in [0,1]$ the following holds: Let $v(x)$ represent the volume of the $(k-2)$-dimensional simplex $ \{ (X_1,\ldots,X_k):X_i > 0, X_2+ \cdots+X_k = 1-x\}$.Then $v(x) = ...
1
vote
2answers
46 views

Elementary proposition on triangulations

I have a question on triangulations. Let T be a triangulation of a d-dimensional cross-polytope. Let s be a (d-1)simplex that does not lie on the boundary of the cross-polytope. How can we show that ...
1
vote
1answer
113 views

Help in understanding proof of lexicographic rule's role in terminating the simplex method

Theorem: The simplex method terminates as long as the leaving variable is selected by the lexicographic rule in each iteration. I am reading through the proof of this theorem and understand all but ...
0
votes
1answer
31 views

Why do we need (or use) identity matrix while proceeding simplex method

I've been studying for operational research recently.I did comprehend how the algorithm works.However I could not figure out why do we need identity matrix and why do we need to create it while ...
-1
votes
1answer
37 views

Predicates and mathematical objects

I'm reflecting about mathematical objects as numbers, sets/classes, graphs and so on. Any class correspond to a predicate in one variable and any graph correspond to a predicate in two variables. ...
1
vote
0answers
25 views

Geometric meaning of r-cycles, r-boundaries and homology groups for a geometric simplicial complex.

I just started learning about algebraic topology, and some things are already not so clear to me. If I consider a geometric simplex $K$, I kind of understand what $H_0(K)$ is. it is a set of ...
0
votes
1answer
37 views

How to find initial optimal(dual feasible) basis which may not be primal feasible.

I am studying the dual simplex method from Lieberman - 10e. An approach called dual simplex method was described that is "applied" on the "primal table" itself, i.e., We do not convert it into its ...
2
votes
1answer
42 views

Dual Simplex Method

Suppose that in a Linear Programming problem in the dual Simplex Method there is a first element (in the first column) negative. If there are in that pivot row some negative numbers we take $\max$ ...
2
votes
1answer
43 views

How to get an equation system from a Simplex table

Let's assume I already have a simplex table (with an optimal solution): $$\left(\begin{array}{ccccc|c} & x_1 & x_2 & S_1 & S_2 & \\ S_1 & 0 & 2 & 0 & 1 & 2 \\ ...
0
votes
4answers
71 views

Volume of a 3D simplex

I want to find the volume of the following simplex $$B := \{ (x,y,z) \in \mathbb{R^3} \mid x \geq 0, y \geq 0, z \geq 0, x+y+z \leq 2 \}$$ I tried to do it by evaluating a double integral but I'm ...
0
votes
1answer
26 views

Pairings of Simplex Edges

This is an open-ended question. If you'll allow, I'd like to keep its origins vague for the moment, so as not to bias responses. I am interested in any and all thoughts. There are three pairings of ...
2
votes
1answer
37 views

Simplex algorithm calculation time exponential rise

I am building an energy-system-model with python/pyomo. It is basically creating an optimization problem (LP) in following form: ...
1
vote
2answers
66 views

Finite element heat equation on a single simplex?

I am currently trying to learn the finite element method. Ultimately, I want to solve the heat equation in arbitrary dimensions. For the purpose of this question, however, assume that I am interested ...
0
votes
0answers
13 views

Difference of two Topologies on Simplicial Complex

In spanier, there are two different topologies on a simplicial complex $K$. (I don't know if this is also the case in other books, Spanier is the only book I am reading.) First topology is a metric ...
1
vote
2answers
27 views

recovering the information of the vertices from a simplex

It seems quite obvious that, when given a simplex, its set of vertices is uniquely determined by the simplex. The formal formulation of this intuition is as follows: Suppose that the points $\{v_0,...
2
votes
1answer
32 views

Revised simplex method: keep basis matrix non-singular

In revised simplex method, the basis matrix should never be singular so we can inverse it. But in real programming cases, it's often the case that the selected basis matrix is singular (after crashing ...
0
votes
1answer
32 views

Dual simplex method when initial reduced costs are negative

I have the following problem which I'm trying to solve by dual simplex method: $$min -6x_1-14x_2-13x_3$$ s.t $$0.5x_1+2x_2+x_3 \le 24$$ $$x_1+2x_2+4x_3 \le 60$$ $$x_1+x_2 \ge 40$$ $$x_1, x_2, x_3 \ge ...
3
votes
2answers
81 views

How to solve simplex problem with $x_1 + x_2 + x_3 + x_4 =1$ as restriction?

So, there's this problem: maximize $$6x_1 + 8x_2 + 5x_3 + 9x_4$$ subject to $$x_1+x_2+x_3+x_4 = 1 \;\text{ knowing that }\; x_1, x_2, x_3, x_4\geq0$$ The solution is obvious: since the sum of ...
0
votes
1answer
26 views

Can the simplex method be used for general monotonically increasing objective functions?

The simplex method relies on the fact that if you have a linear objective function and linear constraints, the optima must lie on one of the vertices of the simplex formed by the constraints. Let's ...
0
votes
0answers
28 views

Lemma for Hurewicz Theorem (Bredon)

I am trying to understand the following lemma: If $f,g:I\rightarrow X$ are paths s.t. $f(1)=g(0)$ then the 1-chain $f*g-f-g$ is a boudary. Proof: On the standard 2-complex (should it say simplex?) $...
0
votes
0answers
15 views

Solving this LP with Dual simplex method

I'm trying to solve this LP using dual simplex method. Max $z=-x_1-3x_2-x_3$ subject to $x_1+x_2-x_3\geq6$ $x_1-2x_2+4x_3\geq9$ $x_1,x_2,x_3\geq0$ I tried solving it on my own but got optimal $...
2
votes
1answer
37 views

How is the homomorphism $b: LC_n(Y) \to LC_{n+1}(Y)$ where $b[w_0\cdots w_n] \mapsto [bw_0\cdots w_n]$ well-defined?

This is on page $121$ of Hatcher's Algebraic Topology. $Y$ is a convex subset in some Euclidean space. The linear maps $\Delta^n \to Y$ generate the subgroup of linear $n$-chains on $Y$, $LC_n(Y) \...
0
votes
2answers
40 views

Is this a non-example of a $\Delta$-complex?

I know this is not a simplicial complex, but is it a $\Delta$-complex? Here is the definition of $\Delta$-complex from Hatcher: I don't believe any of the rules are broken.
3
votes
0answers
26 views

Computing hyper area of a contrained simplex

Let $D_n [r , (a_1, b_1 ) , \ldots , (a_n, b_n) ] = \{ (x_1 , \ldots , x_n ) \in \mathbb R^n \mid \sum_i x_i = r \mbox{ and } b_i \geq x_i \geq a_i \, \forall i \}$, where $r \geq b_i \geq a_i \geq 0$...
0
votes
1answer
26 views

Isometric embedding of standard simplex

The standard $n$-simplex is the subset of $\mathbb R^{n+1}$ given by $\Delta^n = \left\{(t_0,\dots,t_n)\in\mathbb{R}^{n+1}~\big|~\sum_{i = 0}^n t_i = 1 \text{ and } t_i \ge 0 \text{ for all } i\...
0
votes
0answers
53 views

How To Use The Simplex Method When Having More Variables Than Constraints

I have been learning the Simplex Method for solving minimization and maximization problems, but came across a small problem with every resource I have found online. They all seem to imply that ...
0
votes
1answer
26 views

How to find an extreme feasible point in a linear polytope (set $\{x : Ax \leq b\}$ defined by halfspaces)?

The set $$\mathcal P = \{x : Ax \leq b\}$$ is a linear polytope (or, more precisely, an $H$-polytope) and is defined as the intersection of a finite number of halfspaces. The simplex method for the ...
1
vote
0answers
23 views

Simplex method, amount to reduce basic by when non-basic is entered.

Where I've written the vector with $x_B, x_N$ here that should be considered as a partition between them (there should be a horizontal dashed lines or something between them). \begin{align*} f(x_{...
1
vote
1answer
37 views

Simplex Algorithm, determining Two Phase is required and choice of artificial variables

Given the following system : \begin{align*} \text{minimise } z = &2x_1 &+ 3x_2 &+ 3x_3 &+ x_4 &- 2x_5& \\ \end{align*} Subject to \begin{align*} &...
0
votes
0answers
44 views

Optimal basis generation using simplex

Given the objective function $\sum_{i=0}^{i=n} t_i$ (which I want to minimize), constraints $At = u, t \geq 0$ where $A \in m \times n$, and $ n>m$, I'm trying to determine all of the possible ...
0
votes
0answers
17 views

Simplex - does the matrix for tableau contains $I$ or have $I$ attached

I'm getting a bit mixed up with what these notes are referring to for $A$. Here's an example : This is expressed in tableau as follows Which, I think, should be found from the following : But in ...
7
votes
0answers
59 views

Can a regular $n$-simplex have vertices in $\mathbb Z^n$ for $n > 1$?

Trivially, a regular $0$-simplex (point) and $1$-simplex (line segment) can have integer vertices in $0$ and $1$ dimensional Euclidean space respectively. On the other hand, a regular $2$-simplex (...
0
votes
1answer
65 views

How is a standard $2$-simplex oriented? How is a standard $n$-simplex oriented?

If we have the standard $2$-simplex (pictured below from Hatcher), why is there an arrow from $v_2$ to $v_0$? Why not from $v_0$ to $v_2$? We have $\partial([v_0,v_2])=[v_2]-[v_0]$, so shouldn't ...
1
vote
2answers
182 views

How to solve the following equations using simplex method?

Software Engineer here, I am trying to find an algorithm to solve the following problem, basically I have 3 equations that you can see bellow, and all values of X, Y, Z, and Xi, Yi, Zi's are known. ...
0
votes
1answer
51 views

simplex method - full tableau negative coefficients for basic variable

Minimize -10𝑥1−12x2-12x3 Subject to : x1+2x2+2x3+x4=20 2x1+x2+2x3+x5 =20 2x1+2x2+x3+x6 =20 xi >= 0 With x4,x5,x6 the slack variables which we take as our basic variable and all equal to 20 ...
0
votes
0answers
58 views

Gale's evenness condition applied to cyclic polytopes and simplices

Please give your comment on the following problem. In our class we use the following definitions and the following version of the Gale's evenness condition. My analysis of part a is that, the graph $...