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.

2
votes
0answers
29 views

How to solve simplex problem with x1 + x2 + x3 + x4 =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
21 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
24 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
13 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 $...
0
votes
0answers
56 views

List integer points in fundamental parallelepiped

Assume that we have a fundamental parallelepiped in $\mathbb{R}^3$ $\Pi$ := {$\lambda_1$w$_1$ + $\lambda_2$w$_2$ + $\lambda_3$w$_3$: 0 $\leq$ $\lambda_1,\lambda_2, \lambda_3$ < 1}, w$_1$,w$_2$, w$...
2
votes
1answer
36 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
39 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
23 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
22 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
25 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
23 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
18 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
29 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
33 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
15 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
49 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
39 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
154 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
30 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
45 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 $...
1
vote
1answer
18 views

How can I denote the set of probability distributions over a finite set?

I am trying to refer to the set of probability mass functions over a finite set $A$. If the elements in the set $A$ are numbered, referring to the simplex $\Delta^{|A|-1}$ would describe exactly what ...
0
votes
0answers
31 views

Maximization using dual simplex method - problem

My teacher gave us on a test following problem: Following ILP(Integer linear programming) problem: $ 2x_1 +5x_2+4x_3 ->max $ $ 3x_1 +3x_2 + x_3 \leq 20 $ $ 2x_1+ 3x_2 + 4x_3 \leq 30 $ $ x_1,...
2
votes
0answers
86 views

LP-problem simplex with 3 variables

I have this LP-problem which I need to solve using simplex calculations. $$ \max Z = 12x_1 + 18x_2 + 10x_3 $$ when, \begin{align} 2x_1 + 3x_2 + 4x_3 &= 50\\ -x_1 + x_2 + x_3 &= 0\\ -x_2 + \...
0
votes
1answer
48 views

How to show that a linear program has no maximum?

Suppose you have a standard maximum program, where the constants on the right hand side are nonnegative. Suppose further that a variable 𝑥 occurs on the objective with positive coefficient, but ...
0
votes
0answers
35 views

Find the optimal solution using dual simplex algorithm

Maximize $ z=-5x_1+10x_2+8x_3$ subject to constraints $3x_1+5x_2+2x_3<=60$ $4x_1+4x_2+4x_3>=72$ $x_1<=0$ $x_1,x_2,x_3>=0$ Thanks for help :)
0
votes
0answers
18 views

Discrete Morse Function for $n$-simplex

I am trying to find a "useful" discrete Morse function for the $n$-simplex. According to (https://www.emis.de/journals/SLC/wpapers/s48forman.pdf page 12), a possible discrete Morse function is $f(\...
1
vote
0answers
27 views

Rank of $\ker \partial_i$ for $n$-simplex

Let $K=[v_0,v_1,\dots,v_n]$ be a $n$-simplex, and let $\partial_i$ denote the $i$th boundary map. I am trying to find out the rank of $\ker\partial_i$, for $0\leq i\leq n$. What I have tried so far ...
1
vote
1answer
21 views

Invertible matrix and division (Simplex algorithm)

My book presents the following algebraic construction: LP: $z_{min}=cx$ $s.t. $ $Ax=b$ $x \ge 0$ Where A is a m*n matrix and x is a vector of variables. Beyond the meaning of the simplex ...
1
vote
1answer
78 views

linearization of minimum function

I need to be advised in linear programming design. I have spent on this issue some time, I have reached my goal partially, but I am blocked by my lack of knowledge in some areas to go further. Namely, ...
1
vote
2answers
144 views

What is the difference between a unit simplex and a probability simplex?

The unit simplex is the $n$-dimensional simplex determined by the zero vector and the unit vectors, i.e., $0,e_1, \ldots,e_n\in\mathbf R^n$. It can be expressed as the set of vectors that satisfy $$...
1
vote
1answer
41 views

prooving volume formular for simplices

let $ 1\leq n $ and $a_1,...,a_n \mathbb{R}^{+} $ A simplex $ \sigma $ ist given by $ \sigma := [0,a_1 e^1, .., a_n e^n ] $ I want to proove that $$ \int_ {\sigma } 1= \frac{1}{n!} \prod_{j=1}^n ...
0
votes
0answers
17 views

Linear programming multiplication step at the end for nothing?

I'm new to linear programming and I found a basic example on simplex. It's about producing tablets and phones. the problem The equations are the following: $$1P-7x1-5x2+0s1+0s2=0$$ $$0P+4x1+3x2+1s1+...
1
vote
0answers
19 views

why can we tackle a matrix with linearly dependent rows while driving artificial variables out of the basis?

in introduction to linear programming, section 3.5 driving artificial variables out of the basis, the authors consider the case where that when trying to drive the lth basic variable (which is ...
0
votes
1answer
22 views

Number of faces of dimension p of simplex

How can I prove that the number of faces of dimension p of an an n-dimensions simplex is represented by the binomial coefficient below? ${n+1}\choose{p+1}$
1
vote
0answers
14 views

B&B and simplex algorithm

I'm starting studying OR, I read that when solving PLI problem it's common to use Branch and Bound techinque which "decompose" the problem and solves smaller problems. My question is the following: ...
1
vote
0answers
52 views

Employee Scheduling Problem MIP

I am trying to create a mathematical model for employee scheduling. I have already got an idea on how I should model it but I do not know whether it is the best way to do it so. Take for example a ...
1
vote
1answer
27 views

How to represent reflection of a particle inside a standard simplex?

I am trying to simulate the trajectory of an evolutionary system represented by a vector of probabilities $\vec p = [p_1, p_2,...] $. Values are restricted between 0 and 1. As a result we can think ...
1
vote
1answer
36 views

Is it possible to recover the original objective function from a final simplex tableau?

I have a problem that I couldn't find an answer here. I would like to know if it is possible, given a final simplex tableau for a maximization problem, to recover the original coefficients of the ...
0
votes
0answers
32 views

Why in Big M method there is no nonbasic variables with following condition

Consider following standard form linear optimization problem: P:$\hspace{4 ex}$ min $\hspace{1.5 ex}$ CX s.t. $\hspace{3 ex}$ AX=b $\hspace{7 ex}$ X $\geq$ 0, $\hspace{1 ex}$ b $\geq$ 0, And ...
1
vote
1answer
60 views

Barycentric subdivision preserves geometric realization

I have the following definitions: Definition 1: A simplicial complex $K$ is a family of finite nonempty subsets of a set $V_k$ (the elements of $V_k$ are called vertices) such that: 1) if $v\in V_k$,...
4
votes
1answer
196 views

Integral of a determinant over a unit simplex

Recalling the definition of the unit simplex $$ \Delta^{(n)}=\lbrace (x_1,\dots,x_n)\in \mathbb{R}_+^{n} \; , \sum_{i=1}^n x_i=1 \rbrace,$$ I would like to calculate this integral for all integers ...
2
votes
2answers
50 views

Linear program with parameter $t$ as coefficient of basic variable

Consider the following linear problem $$\max tx_1+x_2\\ s.t. 4x_1+3x_2\le12 \\ 3x_1+4x_2\le12\\ x_1,x_2\ge0$$ where the parameter $t$ grows exponentially $t\in[1,\infty).$ Find the sequence of ...
0
votes
1answer
44 views

standard n-simplex

We know that a n-simplex is a convex hull of n+1 affinely independents points in $\mathbb{R}^n$, i,e, let $ x_0,x_1, \ldots ,x_n $ affinely independents points in $\mathbb{R}^n$ then the n-simplex ...
0
votes
0answers
7 views

given a simplex, and copies from it, can i construct a hyperrectangle?

see this answer: dissecting a hypercube to simplexes and the youtube video within it (no sound): https://www.youtube.com/watch?v=ffnVCEAcOns it is always possible to split a hypercube into simplexes, ...
0
votes
2answers
135 views

Transportation problem into initial simplex tableau

I did (b) . For (a), I got this $$\min 3x_1+2.7x_2+2.9x_3+2.8x_4\\ s.t. x_1+x_2\le 5\\ x_3+x_4\le4\\ x_1+x_3=3\\ x_2+x_4\ge4\\ x_i\ge0$$ The standard form is $$\min 3x_1+2.7x_2+2.9x_3+2.8x_4\\ s.t....
0
votes
1answer
27 views

Singular Homology: every $0$-chain is a $0$-circle

I am having trouble understanding this fact, that is deemed as trivial and thus not proved in most books. First of all, I understand that the boundary operator $\operatorname{Bdy}$ goes from $S_n$ to ...
0
votes
2answers
39 views

Singular $n$-simplex, unknown notation, homology

I would like to know what is denoted in the singular simplices paragraph by $e_0,...,e_n$ here: $$[p_0,p_1,...,p_n]=[\sigma(e_0),...,\sigma(e_n)]$$ ? How this matches with simplicial identities $d_i$...
2
votes
1answer
47 views

Simplex is closed

I define the simplex by $C=C(x_1,\dots,x_n)= \{\sum_{i=1}^{n} \lambda_i x_i : \lambda_i \ge 0 \wedge \sum_{i}^{n} \lambda_i = 1\}$. Now assume that $x_1,\dots,x_n$ are linearly independent in some ...
0
votes
0answers
64 views

Simplex Cycling won't happen if degree of degeneracy is 1

Show that in the simplex method cycling won’t happen if the degree of degeneracy is no more than 1, no matter what pivoting rule is used. Can anyone help me prove this?
0
votes
1answer
47 views

2-Simplex.. filled or not filled?

I've seen some authors define the 2-simplex as the boundary of a triangle and others define it including the interior of the triangle (i.e. filling in the triangle). Does this distinction matter? Are ...