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

learn more… | top users | synonyms

0
votes
0answers
24 views

Using the simplex method to find the minimum cost

A local food bank puts together complementary gift packages for its donors during their pledge drives. The bank's costs for each package are $\$4$ dollars for the Bronze level package, $\$7$ dollars ...
2
votes
0answers
32 views

Definite integral of absolute values over a simplex

I'm attempting to evaluate the following integral (note that $v_n=1-v_1-v_2-\dots -v_{n-1}$, and assume $n$ is even): $$ I_n=(n-1)! \int_{v_1=0}^1 \int_{v_2=0}^{1-v_1} \cdots \int_{v_{n-1}=0}^{1-v_1-\...
0
votes
1answer
24 views

All-sizes Network Simplex

I am currently using Network Simplex to find the min-cost flow to send $x$ units of goods from source $s$ to sink $t$ given a capacitated graph. I would now like to solve the problem for all $x \in [...
0
votes
1answer
20 views

Will the slack variables always have coefficients of zero in the objective function?

I've been following this video: https://www.youtube.com/watch?v=M8POtpPtQZc Will the CBi values (slack variable coefficients) ever not be zero? When?
0
votes
0answers
30 views

How to define a transported version of the simplex $X = \{x \in \mathbb{R}^n_{+}| \sum\limits_{i = 1}^n x_i = 1\}$?

Let the simplex in $\mathbb{R}^n$ be denoted as $$X = \{x \in \mathbb{R}^n_{+}| \sum\limits_{i = 1}^n x_i = 1\}$$ So it looks like: I want to take a point $\bar x \in X$ (red dot) And drag it to ...
3
votes
3answers
31 views

Tetrahedron: Signed distance between circumcenter and face

In a triangle, the signed distance between the edge $e_1$ and the circumcenter of the triangle can be written as $$ d_1 = \frac{\langle e_2, e_3\rangle}{\langle e_1\times e_2, e_1\times e_3\rangle}...
1
vote
0answers
11 views

Simplex Method -why does Gauss Elimination produce a new better solution?

In the simplex method, a tableau is created. An entering variable is generated and then using a criteria the exiting variable is also selected. This gives a pivot column and row and pivot element. The ...
0
votes
0answers
20 views

Solve linear system with $A_{i,j} = \langle e_i, e_j\rangle^2$, edges of a tetrahedron

I have six vectors in $e_i\in\mathbb{R}^3$ that are the edges of a tetrahedron. Let us consider now the linear equation system $Ax=b$ with $$ A_{i,j} = \langle e_i, e_j\rangle^2,\\ b_i = \langle e_i, ...
4
votes
2answers
65 views

Solve linear system with $A_{i,j} = \langle e_i, e_j\rangle^2$, edges of a triangle

I have three vectors in $e_i\in\mathbb{R}^3$ that form a triangle. Let us consider now the linear equation system $Ax=b$ with $$ A_{i,j} = \langle e_i, e_j\rangle^2,\\ b_i = \langle e_i, e_i\rangle. $$...
0
votes
1answer
26 views

Determine all solutions of a linear program

I have the following linear optimization model: $$\begin{array}{ll} \text{maximize} & x_1 + 2 x_2\\ \text{subject to} & 3x_1+2x_2 \leq 12\\ & x_1+3x_2 \leq 9\\ &2x_2\leq2\end{array}$$ ...
0
votes
1answer
25 views

Linear Programming: Transportation Problem with alternatives

Could someone please explain how to solve such task by linear programming: Let's say there is a starting point $A$ and two end points $B$ and $C$. $A$ is connected to $B$ and $C$ and the connections ...
0
votes
1answer
9 views

Linear Programming: LP-Model

Let's say there are 2 types of TV shows. The first one S1 is usually watched by 2 women and 1 man. The second one S2 is watched by 1 women and 3 men. A company wants to show commercials to reach at ...
0
votes
1answer
41 views

What vectors can be generated by permuting and halving?

$x$ is a vector in the unit simplex in $\mathbb{R}^n$, i.e: $$x = (x_1,\dots,x_n)\,\,\,\,\,\,\,\,;\,\,\,\,\forall i: x_i\geq 0\,\,\,\,;\,\,\,\,\,\,\,\,\sum_{i=1}^n x_i = 1$$ Initially, $x=(0,0,\dots,0,...
1
vote
0answers
15 views

Two phase method in linear programming

suppose following tableau came after one iterations in first phase of a two phase method problem, here $s_1$ is a surplus variable and $s_2$ is a slack variable $w$ is a artificial variable. i tried ...
0
votes
0answers
33 views

Complicated situation in the simplex method?

I am having a problem with the simplex method and here is my tableau section $$\begin{array}{|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|l|} \hline x1 & x2 & x3 & x4 &...
0
votes
0answers
33 views

Joint pdf of two uniform random variables on a unit line segment

Let $X$ be a standard uniform random variable, define $Y=1-X$. Then supposedly $X$ and $Y$ are uniform over a 1-simplex, so their joint distribution should be Dirichlet of order $K=2$, and $\alpha_1=\...
0
votes
0answers
17 views

Generating equations for this Optimisation problem

Minimize : $ |(Ax + B) - (Cy + D)| $ Such that: $ x \geqslant 0 $ $ y \geqslant 0 $ $a,b,c, d $ are fixed natural numbers and $ x,y $ have integral solutions. I just can't figure out if this can ...
0
votes
1answer
32 views

The standard n-simplex is compact set

$ " Let \ K\subseteq \mathbb R^n \ be \ a \ compact \ set,\ then\ the\ convex \ hull \ of\ K\ is\ also\ compact \ set\ " $ In order to prove this we use that the standard n-simpex as defined ...
0
votes
0answers
11 views

Several unknowns in simplex tableau

I have the following Simplex Tableau: $$\begin{array}{r|ccccc|c}&350&300&0&0&0\\\hline A&0&1&20&D&-30&45\\B&0&0&J&E&5&H\\C&1&...
2
votes
0answers
17 views

Is a simplex with permuted vertices $\pm$homologous to the original?

Take a singular $n$-simplex $\sigma: \Delta^n \to X$, where $\Delta^n\subset \mathbb{R}^{n+1}$ is the convex hull of the standard basis, with the obvious vertex ordering. Then one can obtain $(n+1)!$ ...
0
votes
0answers
16 views

Checking if vector crosses the simplex

Let assume that I have a point in $x \in \mathbb{R}^n$ Also I have a non-zero vector defined by it's endpoint attached to this point. The third thing I have is a simplex of $\dim=n$, such that the ...
-1
votes
1answer
92 views

Linear Programming - The Big M Method - Proof questions [closed]

I'm having difficulties on answering the following questions (first time I'm trying to prove something), any help would be awesome! Thanks in advance. Q: It is possible to combine the two phases of ...
0
votes
0answers
14 views

maximal volume/diameter of a set of simplexes

I am trying to develop a simplicial integral in $R^n$ and I am faced with the problem of controlling the "compacity" of a set of simplexes: Let $S$ be a finite set of n-d simplexes in $R^n$. Define ...
2
votes
1answer
42 views

maximal volume/diameter of polyhedron

I am trying to develop an integral in $R^n$ and I am faced with the following problem: Given a polyhedron $P$ in $R^n$ of diameter d, define the "compactness" of $P$ as the quotient of the volume of $...
2
votes
0answers
23 views

Linear programming: choosing entering variable

maximize 10𝑥1 + 12𝑥2 +12𝑥3 subject to 𝑥1 + 2𝑥2 + 2𝑥3 + 𝑥4= 20 2𝑥1 + 𝑥2 + 2𝑥3+𝑥5= 20 2𝑥1 + 2𝑥2 + 𝑥3 +𝑥6= 20 𝑥1, … , 𝑥6 ≥ 0 This is my first step for simplex tableau x1 x2 ...
2
votes
0answers
40 views

Distributions on the simplex with beta marginals

Consider a random vector $(X_1,X_2,\ldots,X_n)$ such that 1) $\; X_i\sim\text{Beta}(a_i,\sum_{j\neq i}a_j)\qquad i=1,2,\ldots,n$, 2) $\; X_1+X_2+\ldots+X_n=1$. Can we conclude that $(X_1,X_2,\ldots,...
0
votes
0answers
21 views

Hatcher's notation and definition for the boundary of a singular chain complex

I have a hard time following Hatcher in general, but especially his notation in this case with the bar (page 108 in my pdf copy): For the boundary of a singular $n$-simplex, $\sigma$,he writes: $\...
0
votes
0answers
37 views

If the primal is unbounded, then the dual is infeasible.

In the context of duality in linear programming, prove that If the primal is unbounded, then the dual is infeasible. My book says that this is a corollary to complementary slackness. What's ...
1
vote
0answers
59 views

When does a variable goes out with the revised Simplex method?

Let be the following linear program. \begin{cases} \max & 3x_1& +x_2\\ &x_1&-x_2 &\le -1\\ &-x_1 &-x_2&\le -3\\ &2x_1 &+x_2 &\le4\\ x_1,x_2\ge 0 \end{...
1
vote
0answers
20 views

Why is are the simplicial 1-chains $[A,B] \neq -[B,A]$?

This is a really simple question that I think I have answered, but I'm not altogether satisfied and would like confirmation or an alternative. We define the simplices $$ \begin{align} [A,B] : \Delta^...
0
votes
1answer
25 views

Volume of $k$-simplex in $n$-dimensions ($n \ne k$)?

A simplex is the convex hull of a set of vertices. In $\mathbb{R}^n$, the $k$-simplex with vertices $\vec{x}_0,\dots,\vec{x}_k$, $\vec{x}_i \in \mathbb{R}^n$, is the set of points: $$S = \left\{ \...
0
votes
2answers
60 views

Questions about simplex algorithm

I'm trying to understand how simplex algorithm works, and here are my questions: 1. Why we choose the entering variable as that with the most negative entry in the last row? My understanding is that ...
0
votes
0answers
51 views

Prove that optimal Solution exist without solving.

![1]: http://i.stack.imgur.com/Osa3G.jpg Without solving the problem, show that it has an optimal solution.
1
vote
0answers
18 views

What is the initial tableau for simplex method with big M method for this problem?

I have an optimization problem with formulation: min f = x1+x2+x3 subject to: x1+2*x2+x3=8 2*x1+x2+x3=12 x1,x2,x3>=0 I should solve it by Big M method. For this I added two extra variables (a1,...
2
votes
1answer
48 views

Intuition for volume of a simplex being 1/n!

Consider the simplex determined by the origin, and $n$ unit basis vectors. The volume of this simplex is $\frac{1}{n!}$, but I am intuitively struggling to see why. I have seen proofs for this and am ...
0
votes
0answers
16 views

Definition of a “n-”simplex

I have a simple question about the definition of a simplex. In this paper by Jonathan Huang he notes that every point on the simplex can be expresed as a linear combination $$x=\sum\limits_{i=0}^n \...
3
votes
1answer
67 views

Bland's Ratio Details

Bland's Finite Pivoting Method is often used as the standard pivoting rule in simplical optimization for linear programs. However, some literature conflicts - for maximization, some state that only ...
0
votes
0answers
15 views

Fitting coordinate system transformation

Everything in my question relates to 2D Cartesian coordinate systems. I am programmer and not a great mathematician, so please help me out if my description is inaccurate. I have coordinates for a ...
2
votes
1answer
55 views

Simplicial complex not locally finite, then not locally compact

This is question 3b) of exercises on page 14 of Munkres Algebraic Topology. Show that, in general, if a simplicial complex $K$ is not locally finite, then the space $\vert K \vert$ is not locally ...
0
votes
0answers
20 views

Formulation of LP Problem with three constraints

I have an assignment in a Linear Programming course that I'm having some trouble with understanding. The problem is, or should be, pretty simple, but for the life of me I can't seem to be able to get ...
1
vote
0answers
26 views

How to know in the matrix form when a linear program isn't feasible and what to do from it?

Good morning, I'm preparing my exam first exam in linear programing and try to sharpen my skills over how to handle such programs. I want to know when can we know that a linear program isn't feasible ...
1
vote
2answers
73 views

Find the optimal solution without going through the ERO's

All I got is that $$12y_1 + 7y_2 + 10y_3 = 2(0) + 4(10.4) + 3(0) + 1(0.4)$$ and $y_2 = 0$ because $x_6$ is in basis. How do I find $y_1$ and $y_3$ without going through the simplex method? I took ...
0
votes
0answers
60 views

optimal, infeasible, degenerate solutions

Note that $c_i$'s in the $z_j-c_j$ row are not coefficients of the $x_i$'s. I use instead: $r_1, r_2, r_3$. I'm assuming there's a non-negativity constraint. we need to state necessary ...
0
votes
0answers
21 views

Linear program solved with Simplex out of given bound

I believe to be missing something important in the Simplex algorithm because it goes beyond the given objective. Let be the following linear programming program: \begin{cases} \max Z(x,y,z)=&x&...
11
votes
1answer
159 views

Volume of the intersection of two simplexes

Let $S_n$ be the interior of the unitary $n$-simplex, i.e $ S_n =\{{\bf x} \in \mathbb{R}^n \mid x_i\ge0 \wedge \sum_{i=1}^n x_i\le1\}$ Let $T_n({\bf y})$ be the reversed simplex with origin at ${\...
0
votes
0answers
24 views

What are the lawful operations in the simplex method?

Having the following: \begin{equation*} \begin{cases} \max& 3 x_1 & + 2x_2 & +4x_3\\ &x_1 &+ x_2 &+ 2 x_3 &\le 4\\ &2x_1 & &+3 ...
2
votes
0answers
38 views

Number of 0-simplices after second barycentric subdivision of a standard simplex [closed]

What is the number of 0-simplices of a standard $n$-simplex after its second barycentric subdivision? By the way of counting, this number is 1, 5 and 25 for 0-, 1- and 2-simplices, respectively. ...
0
votes
1answer
47 views

Barycentric subdivisions and labeling of $(d-1)$-simplex

I am trying to prove that it is always possible to label the vertices of the $k$-th barycentric subdivision of a $(d −1)$-dimensional simplex with labels $1, 2, . . . , d$ such that each simplex ...
1
vote
0answers
43 views

Primal/Dual Simplex methods clarification

I have several questions regarding these methods. Primal Simplex Method Does the pivot element always have to be a positive entry in the table? Does the RHS always have to be positive in the pivot ...
0
votes
1answer
53 views

How to configure simplex method to start from a specific point

If I have a linear programming problem e.g. $$\max 2x_1 + x_2$$ with these constraints $$x_1-2x_2 \leq 14$$ $$2x_1-x_2\leq 10$$ $$x_1-x_2 \leq 3$$ And I want to solve the problem starting from a ...