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

learn more… | top users | synonyms

2
votes
0answers
24 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 ...
0
votes
0answers
20 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
18 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. What I tried: The short version is that unbounded primal means a column ...
1
vote
0answers
56 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 ...
1
vote
0answers
16 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] : ...
0
votes
1answer
13 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
45 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
42 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
15 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 ...
2
votes
1answer
43 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
13 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
65 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
10 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
31 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
19 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
24 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
1answer
54 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 ...
0
votes
0answers
44 views

What values make the solutions in the optimal? infeasible? degenerate? etc

Note that $c_i$'s in the $z_j-c_j$ row are not coefficients of the $x_i$'s. We can use instead $r_1, r_2, r_3$ (r for row). I'm assuming there's a non-negativity constraint. we need to state ...
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 ...
11
votes
1answer
158 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
35 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
39 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
31 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
49 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 ...
0
votes
1answer
40 views

Canonical form simplex method

In 2-phases simplex method what kind of operations must be done to get the canonical form tableau? In this step(phase 2 of 2-phases method) after the remotion of artificial variables columns of ...
0
votes
1answer
54 views

Solve a linear programming minimization problem with greater-than-equal sign in the constraints using the Simplex method

I need to solve the following linear programming minimization problem using the Simplex method: ...
3
votes
1answer
91 views

Degeneracies of simplex $y$ which appears as any face of some simplex $x$

Let $K$ be simplicial set and $d_i:K_n\rightarrow K_{n-1}$, $s_i: K_n\rightarrow K_{n+1}$ ($i = 0,...,n$) face and degeneracy maps respectively. Suppose we have some $x\in K_n$ with $d_0x = ... = ...
0
votes
1answer
35 views

Definition of Optimality test - Simplex method

To clarify, this is not a question about how to conduct test of optimality or about what is the test good for. Nor am I asking for mathematical proof supporting it. I am asking specifically for ...
0
votes
0answers
15 views

Triangulation of simplotope (Cartesian product of simplices)

Let $s,n\in\mathbb{N}$ and $\mathcal{S}_{s,n}=\operatorname{conv}\left(\{\mathbf{0}\}\cup\{\mathbf{e}_{s,i}\mid i\in\{1,\ldots,s\}\}\right)^n\subseteq\mathbb{R}^{sn}$ where $\mathbf{0}$ is the zero ...
0
votes
0answers
29 views

Linear programming duality problem

I need to solve this problem linear programming task using dual graphical solution. Task I tried creating it's dual form using those rules: Rules And I got my dual task as follows: \begin{align} ...
2
votes
1answer
111 views

Simplex method - identity matrix

I want to solve the following linear programming problem: $$\min (5y_1-10y_2+7y_3-3y_4) \\ y_1+y_2+7y_3+2y_4=3 \\ -2y_1-y_2+3y_3+3y_4=2 \\ 2y_1+2y_2+8y_3+y_4=4 \\ y_i \geq 0, i \in \{ 1, \dots, 4 ...
1
vote
1answer
84 views

Wrong optimal solution

If we have a linear programming problem that is of the form as the following: The initial tableau is the following: Then we get this: $\begin{matrix} B & b & P_1 & P_2 & P_3 ...
0
votes
0answers
13 views

How to graph polygon rising at an angle in 3D space from the origin of the coordinate axes with shaded region on the $x$-$y$ plane?

I am trying to obtain a graph just like this one that visually shows that an objective function is maximised in z-direction at a certain point and where the “ground” of the graph is the $x$-$y$ ...
0
votes
1answer
30 views

How to represent 2D lines (i.e. on $x$ and $y-axis$) on a 3D graph using either Cartesian ($z=f(x,y)$) or Parametric $(x,y,z)=f(u,v)$

How to represent 2D lines (i.e. on $x$ and $y-axis$) on a 3D graph using either Cartesian ($z=f(x,y)$) or Parametric $(x,y,z)=f(u,v)$ Hi, I've been working on a Simplex problem and would like to ...
1
vote
1answer
42 views

What is an invariant Simplex

Let $$\Delta=\{x_i\in\mathbb{R}^k_+: \sum_{i=1}^kx_i=1\}$$ where k is a positive integer. I've read in a book the following: The simplex $\Delta \subset \mathbb{R}^k$ can be shown to be invariant ...
3
votes
1answer
26 views

How to create an example with exponential running time for a given implementation of the simplex algorithm?

Say I have a black box implementation of the simplex algorithm given. Even though the worst case complexity is exponential, the implementation is fast for all cases I have tried. Is there a ...
0
votes
1answer
27 views

MIP Solver with Sensitivity option

I need a MIP Solver with Sensitivity Analysis option. So far i have found LPSolve IDE, and it has Sensitivity Analysis, but it is not supported for Mixed Integer Programming, only for the decimals. ...
0
votes
1answer
53 views

Linear Programming Problem with odd objective function

I have the linear problem as it follows. I have 3 different types of devices. Type A, Type B, Type C. At any given moment, there is exactly one type of each device installed. So one device A, one ...
1
vote
0answers
23 views

How do I show that the given matrix can be decomposed?

Suppose $P\subseteq\mathbb R^n$ is a polyhedron given by $m$ constraints $\langle a_i,x\rangle\leq b_i, i=1,2,...,m$ and let $w_1,w_2,...w_n$ be its vertices. Define $S=(s_{ij})$ by ...
3
votes
1answer
60 views

Simplicial Homology Does Not Depend on the Orientation

Let $K$ be a simplicial complex and denote by $K_1$ and $K_2$ the complexes obteined from $K$ with two different orientations. I want to prove that the simplicial homology groups of $K_1$ and $K_2$ ...
2
votes
1answer
97 views

How can I determine B-inverse from an optimal tableau of a LP?

(This is NOT a homework question, I am reviewing for my upcoming exam) Given this linear program: and this optimal tableau: I am attempting to determine $B$ inverse using the table above. From ...
1
vote
1answer
26 views

Relative $0$-homology of $(\Delta^n, \partial \Delta^n)$

Let $\Delta^n$ be the standard $n$-simplex, with $n>0$. Denote with $H_0$ the (simplicial) $0$-homology. In my book it is written that $H_0(\Delta^n, \partial \Delta^n)=\mathbb{Z}$. But ...
-1
votes
1answer
71 views

Simplex algorithm reaches optimal solution but with negative slack variables [closed]

I am working on a VBA algorithm that will solve simple versions (single stock length, <1000 patterns) of the Cutting Stock problem, and after a lot of research I have managed to write a VBA program ...
1
vote
2answers
34 views

Simplex method: Third iteration has same pivot row as earlier

I have the following minimization problem: $F(x)=-5x_1-4x_2$ Subject to: $4x_1+x_2<20$ $3x_1+2x_2<18$ $x_2<6$ And of course $x_1,x_2>0$. ...
1
vote
0answers
27 views

Show entropy bound unit simplex

Let $\mathcal{S}_d$ be the $d$-dimensional unit simplex. Then for the norm $||x||_1 = \sum_i |x_i|$ and $0 < \varepsilon \leq 1$, $$N(\varepsilon, \mathcal{S}_d, ||\cdot||_1) \leq ...
0
votes
1answer
51 views

How to read Linear Program from an optimal tableau

Suppose we are given an optimal tableau and the objective function. How can we determine the RHS of constraints or if possible the constraint equations? For example consider the given tableau with ...
0
votes
1answer
22 views

Extend simplicial homeomorphism in a PL surface

Let $S$ be a connected PL closed surface. How can I show that, given a 2-simplex $\Delta$ in $S$ and a simplicial homeomorphism $g:\Delta\to \Delta$ that preserves orientation, this can be extended to ...
0
votes
1answer
67 views

How to solve this operation research problem using dual simplex method?

Maximize $$ z = 2x_1 -x_2 +x_3$$ Subject to constraints $$2x_1 + 3x_2 -5x_3 \ge 4$$ $$-x_1 +9x_2 -x_3 \ge 3$$ $$4x_1 ...
1
vote
1answer
29 views

Simplex Method : Entering variable and leaving variable

i have a homework question and i am not sure if a understood the first part correctly ( english is not my native language ). For the entering variable : I guess $ 10x_1 - 32x_2 + 8x_3 + 5x_4$ is ...