Stack Exchange Network

Stack Exchange network consists of 174 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.

1
vote
2answers
29 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
32 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
14 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
15 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
15 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
13 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
45 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
24 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
29 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
26 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
38 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
193 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
48 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
0answers
17 views

Compacts and n-simplex

Let $ A \subseteq \mathbb{R}^n$ compact then exists and $n$-simplex $B$ such that $A\subseteq B$. My idea is that, since the set is compact then in particular it is bounded and so it is in some open ...
0
votes
1answer
28 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
24 views

Property of a n-simplex?

Let $A \subseteq \mathbb{R}^n$ a open set. Then there exists a subset $B \subseteq A$ where $B$ is a $n-$ simplex?. Is the condition that $A$ is open necessary?
0
votes
0answers
7 views

Triangulation of a n.simplex

What is the definition of a triangulation of an n-simplex. My intuition tells me that we divide the simplex into smaller simplexes but I do not know what other things should be fulfilled
0
votes
0answers
6 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
122 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
22 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
34 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
32 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
38 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
41 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 ...
1
vote
1answer
53 views

Find the Maximum value using Big M method (algorithm)

Task: I need to write a program, which should calculate the maximum value of the function using Big M method. Here is the problem: $Z(x_1,x_2)=4x_1+3x_2 \rightarrow max$ Subject to: $ \begin{cases}...
0
votes
0answers
28 views

Lower bound for intersection of a ball near the boundary of a bigger ball

Let $\mathbf{x}=(x_0,\ldots,x_k )\in (\mathbb{R}^d)^{k+1}$ where $1\leq k\leq d$ such that the points $\{x_0,\ldots,x_k\}$ are in general position. Thus $\mathbf{x}$ defines a unique $(k-1)$-sphere ...
0
votes
0answers
16 views

Simplex Algorithm to solve inequalities against time

I have an idea, out of nowhere actually, not really related to class but from my random thoughts in a shower. I just read about simplex algorithm in linear algebra and it's really interesting to me, ...
0
votes
0answers
34 views

Dihedral angles of a $k$-simplex

Given a $k$-simplex $(p_0, ..., p_k)$, where $p_i$ are $n$-dimensional points. Define the dihedral angle $\theta_j$ as the angle between the (hyperplanes of the) two $(k-1)$-facets incident to the $(...
0
votes
0answers
32 views

Slack variables insertion in primal-dual couple

Suppose we have the following primal-dual couple: (P1) Min $z_1 = c^Tx$ s.t. $Ax >= b$ $x >= 0$ (P2) Max $z_2 = b^Ty$ s.t. $A^Ty <= c$ $y >= 0$ If we introduce slack ...
1
vote
1answer
33 views

face map $d_i^n:\Delta^{n-1}\to\Delta^n$

I have the following formulas about face maps, which I try to proof. 1) $d_j^{n+1}d_i^n=[e_0,\dotso, \hat{e_i},\dotso, \hat{e_j},\dotso, e_{n+1}]:\Delta^{n-1}\to\Delta^{n+1}$ for $j>i$. 2) $...
0
votes
1answer
20 views

Why does a d-polytope being k-neighborly for 1 <= k <= d imply the polytope is neighborly for all k' such that 1 <= k' <= k?

I'm reading Grunbaum's Convex Polytopes where he cites the following theorem in a proof by contradiction for a larger theorem: "If $P$ is a $k$-neighborly $d$-polytope, and if $1 \le k' \le k$, ...
0
votes
0answers
48 views

About Simplex method in Introduction to Algorithms (CLRS)

I am reading "Introduction to Algorithms 3rd Edition" by CLRS. I think it is obvious that $28$ is the optimal objective value from the objective function $z = 28 - \frac{1}{6} x_3 - \frac{1}{6} x_5 - \...
0
votes
1answer
31 views

Linear programming - optimisation

I am being asked to give an explanation what happens if, when pivoting, we chose the right entering variables and the wrong leaving variables if we chose positive pivot element, and why? and what ...
0
votes
0answers
46 views

Transforming an inequality in another variables via a polynomial relation

Given an inequality through a quadratic polynomial $$ ax_1^2+bx_2^2 +cx_1x_3+dx_2x_4\leq 0,$$ where $c_i\in \mathrm{R}$, $0\leq x_i \leq 1$, $i=1,2,3,4$, can it be somehow transformed into an ...
2
votes
0answers
41 views

Linear programming - one-step jump from interior feasible solution to the nearest improving basic feasible solution

Imagine I have a linear programming problem and somehow I am given an initial feasible non-basic solution. Is there a way to easily transform this solution into a basic feasible one that improves (in ...
0
votes
0answers
17 views

Constructing a basis matrix corresponding to binding constraints in linear programming

I have a question regarding linear programming. Suppose that we have a problem $ \min c^{T} x \quad $ such that $ \quad Ax \leq b $ where $A \in R^{m \times n }$, $ x \in R^{n} $, $ b \in R^{m} $ ...
1
vote
1answer
38 views

On the change of objective function values between Simplex-Iterations

Background (skippable): I asked this question in a lecture quite some time ago and the lecturer couldn't really answer it. This question bothered me since then, since I couldn't be able to answer it. ...
0
votes
0answers
73 views

Proof for a basic feasible solution given the constraint $\xi \geq 0$ or $\xi \leq 0$

I would like to know how I can show this: Consider a nonempty polyhedron P and suppose that for each variable $\xi$ we have either the constraint $\xi \geq 0$ or the constraint $\xi \leq 0$. Is it ...
0
votes
0answers
15 views

Explanation of some aspects of simplex tableau

In a simplex tableau, before proceeding with the optimization of the objective function, the rule is that the row corresponding to objective function say z, can't have the basic variable's ...
0
votes
1answer
48 views

triangulation of a circle and the way to solve a problem

Consider the circle $S^1$ with multiplication given by the complex numbers. Prove that the map $f(x) = x ^n$ , $n$ a positive integer, has degree $n$. What is the degree of the map $g(x) = 1/x$. ...
1
vote
1answer
55 views

Laplace method on a simplex with factorized integrand

I need to obtain an approximation to an integral of the form: $$I = \int_0^1 \mathrm e^{M \sum_i f_i(x_i)} \mathrm \delta\left(\sum_i x_i - 1\right) d\mathbf x$$ where $M$ is a large real number. ...
1
vote
0answers
37 views

Laplace method on a simplex

Can the Laplace (saddle-point) approximation be applied to integrals of the form: $$\int_0^1 \mathrm e^{M f(\mathbf x)} \mathrm \delta\left(\sum_i x_i - 1\right) d\mathbf x$$ where $M$ is a large ...
1
vote
1answer
17 views

General formula for n-Simplex root?

Given a number $k$, is it possible to find which term in the $n$-Simplex sequence it corresponds to? I've only been able to find formulae for the triangular root. Examples: For $k = 10$ in the ...
0
votes
1answer
41 views

Linear programming problem with absolute value

Problem: Maximize $|x|$ under conditions $$-x+y\leq 1\\ x+y\leq2\\y\geq0$$ My solution: So we can write $x$ as $x=x_1-x_2$ and $|x| = x_1+x_2$, where $x_1 = x$ whenever $x\geq0$ and $x_1=0$ whenever $...
0
votes
0answers
53 views

Primal-dual correspondence in the simplex method

I am trying to understand the dual simplex method and after reading a few different books I got stuck when trying to understand the primal variable to dual constraint correspondence. A lot of sources ...
1
vote
1answer
30 views

Simplex in a complex vector space

I feel this may be a stupid question, but when I look up things on convexity, all definitions are in $\mathbb{R}^n$. For example the definition of a simplex or Caratheodory's theorem. I can only find ...
0
votes
1answer
56 views

Volume of $(n-1)$- simplex in $n$-dimension.

This post gives a general way to calculate $k$-simplex in $n$-dimensional space with $k\leq n$. My question is, if $k=n-1$ and give vertices $v_{0}, \cdots, v_{n-1}$ are linearly independent, can we ...
0
votes
1answer
45 views

Local minima and maxima over the simplex

Consider a smooth function $f : \mathbb{R}^n \to \mathbb{R}$, and consider the simplex: $$\Delta_n = \left\{{\bf x} \in \mathbb{R}^n:x_i \in [0,1] \wedge \sum_{i=1}^n x_i = 1\right\}.$$ Suppose that:...
0
votes
0answers
56 views

Proof of the general case of Feynman's integration trick

I want to show that $$\frac{1}{\prod\limits_{i=0}^{i=n}A_{i}}=n!\int\limits_{\mid \Delta^{n}\mid}\frac{d\sigma}{\left( \sum s_i A_i \right)^n}$$ Where $d\sigma$ is the lebesgue measure on the ...
3
votes
1answer
87 views

Gaussian measure of the standard simplex

What is $$\int_{\Delta_n} e^{-(x_1^2 + x_2^2 + \cdots + x_n^2)/2} d x$$ where $\Delta_n = \{(x_1, x_2, \dots, x_n) \in \mathbb{R}^n \mid x_i \geq 0, \sum_{i=1}^n x_i \leq 1\}$ The motivation is ...