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

learn more… | top users | synonyms

0
votes
1answer
28 views

Integer Points in Simplex

Let $$A_w(d,q):=\left\{{\bf k} \in \mathbb{N}_0^d: \sum_{j=1}^d w_j k_j \leq q\right\}$$ denote the number of non-negative integer points in the $\ell_1$-ellipse with semi-axes of length ...
0
votes
0answers
15 views

Probability Distribution on the Simplex with support on the faces

I am looking for a parametrized distribution on the (probability) $K$-simplex with support on its $(K-1)$-faces. I.e. say $(x_1,...x_{K+1})$ are the coordinates of the simplex with $\sum_jx_j=1$, then ...
1
vote
0answers
32 views

Is it known whether or not the 'Hauptvermutung' is true for finite simplicial complexes in $\mathbb{R}^4$?

If I have two finite simplicial 4-complexes embedded linearly in $\mathbb{R}^4$ (as in all the lines and faces are straight and flat and there are only a finite number of 4-simplices) do they have a ...
0
votes
0answers
9 views

radius-edge ratio for an n-simplex

I need a way of measuring the shape of an n-simplex, i.e., the circumradius divided by the shortest edge length of the simplex. But i have no idea about how to calculate the circumradius of an ...
2
votes
2answers
43 views

Cartesian coordinates for vertices of a regular 16-simplex?

I am using amoeba to solve an optimization problem and want to distribute the initial perturbations uniformly about the initial estimate. With only Excel at my disposal, I cannot figure out how to ...
1
vote
1answer
22 views

p-simplex spanned by elements in the boundary of the unit ball of Thurston norm is in the the boundary of this unit ball.

in completing my thesis I have reached a momentary impass. I am trying to solve an exercise given in the book "Foliations II" by Candel and Conlon. In particular, Exercise 10.4.1, and I can't seem to ...
1
vote
0answers
37 views

Unique solution of LP

Hi I am working on the following question: If $c \in int(N_P(x))$, then $x$ is a unique solution. I have proven that this is true if $x$ is a vertex. Well I am wondering if the following is a ...
0
votes
2answers
32 views

Simplex algorithm with initial negative slack variables

I have the following LP problem: $$\begin{equation*} \begin{aligned} min. & & z = 2x+3y\\ \text{s.t. } & & x & \le 3\\ & & x & \ge 3\\ & & -x + 2y & \le ...
1
vote
1answer
56 views

Number of elements in discrete $n$-dimensional simplex such that $x_1 \leq \ldots \leq x_n$

For positive integers $n,d$, how many elements are there in the set $S = \{(x_1,\ldots,x_n) \in \mathbb{Z}^n\ |\ 0 \leq x_1 \leq \ldots \leq x_n \wedge \sum_i x_i = d \}$? I'm hoping that the order ...
1
vote
1answer
35 views

How to pivot to an adjacent vertex in simplex method

In the simplex method, we need to move from one vertex of the polyhedron to an adjacent one. Suppose the polyhedron is $P=\{x\in\mathbb{R}^n\mid Ax=b,x\geq0\}$ with rank$A=m<n$. For a ...
2
votes
1answer
48 views

triangulation of the cube of whose vertices are in the set $\lbrace (\pm 1 , \pm 1 , \dots , \pm 1)\rbrace$

Take the cube centered at the origin whose vertices are $\lbrace (1 ,1 , 1) , (-1 ,1 , 1) , (1 ,-1 , 1) , (1 ,1 , -1) , (1 ,-1 , -1) , (-1 ,1 , -1) , (-1 ,-1 , 1) , (-1 ,-1 , -1) \rbrace$. We can ...
0
votes
0answers
11 views

Initialization of Network Simplex with known flows

I am trying to figure out how to initialize the network simplex algorithm when you know the flows you want to start with. And I am interested solely in bipartite graphs (partition of nodes in sinks ...
0
votes
1answer
49 views

Obtain Dual Solution from Primal problem using Simplex

I have been looking for an easy answer for this, but I wasnt able to find a strong answer. I will do it with an example: Given this Primal Problem: Max 14A + 7B 2A + 5B <= 18 5A + 2B <= 24 ...
1
vote
2answers
53 views

How to find out whether linear programming problem is infeasible using simplex algorithm

So in http://econweb.ucsd.edu/~jsobel/172aw02/notes3.pdf, there is a mention about finding out whether linear programming (LP) problem is infeasible by simplex algorithm, but it does not actually go ...
1
vote
0answers
53 views

Quadratic optimization problem (inner products) with stochastic constraints

Let the set of feasible solution be the set of all row-stochastic $n \times k$ matrices $P = [p_{ij}]$, that is $\mathcal{P} := \{P \in \mathbb{R}^{n \times k} \ | \ P \mathbf{1} = \mathbf{1}, P \geq ...
1
vote
0answers
194 views

Primal and dual problem (Optimal solution) - Operations research

I'm currently studying operations research and I want to know and understand how we find an optial solution to the dual problem with minimum effort. Lets say we have this primal and dual problem: ...
0
votes
0answers
40 views

how can we explain that the all slack point is feasible

how can we explain that the all slack point is feasible when solving a linear programming problem using the simplex method Thanks in advance, i appreciate all the help.
0
votes
1answer
29 views

n-simplex volume and triangle.

For $n\in N$ let $\sum_n(1)$ be the standard-simplex. Let there be a point $b\in R^n$ and a basis {$a_1,...,a_n$} of $R^n$. The $n-simplex$ set up in this point b by the basis is the set ...
1
vote
1answer
42 views

Expressing problems in canonical form for solving with simplex

The Picnic Hamper Company has a store containing 10,000kg of nuts, 4000 packs of smoked salmon, 2000 bottles of wine and 1500 Victoria sponges. It intends to use these goods to make up three different ...
0
votes
0answers
13 views

Does a simplex uniquely determine an affinely indepedent set which it is a convex hull of?

Let's say you're given an $n$-simplex, and you're told that it is the convex hull of two affinely independent sets $A_1$ and $A_2$. Do $A_1$ and $A_2$ need to be equal? To rephrase the question, given ...
0
votes
1answer
27 views

How to solve Standard minimization problem of a function

I have a minimization problem here: minimize the cost function C= 12x + 40y +30z subject to x + 2y +2z >= 2 -x - y - 3z >= -1 -x +2y + z >= -2 x >=0 ,y >=0 ,z >=0 So i made the matrix out of ...
0
votes
0answers
5 views

orientation induced by embedded simplex

let $\Delta_n$ be an affine simplex, we fix an orientation on it as the ordered set of vertices $\{A_0,\dots , A_n\}$. Now linearly embed it inside $\mathbb{R}^n$. According to Milnor-Stasheff ...
0
votes
1answer
27 views

How to formulate constraints given the following information

The following question was given in one of my class but none of us got the use of the market requirements in the problem: A form produces and sells three products namely Product1, Product2 and ...
1
vote
0answers
29 views

Multiple optimal solutions / LP

In the optimal primal simplex tableau, if we have a non-basic variable with a reduced cost of zero, can we say for sure the primal has multiple optimal solutions? Or can the same thing also happen ...
1
vote
0answers
19 views

Total probability distribution of multiple random lotteries

My question: Imagine $d$ identical lotteries. Each individual lottery picks a cost $c_{i}$ between $0$ and $1$. Picking a costs occurs with probability distribution $f(c)$. The total cost of these ...
0
votes
1answer
47 views

Constructing canonical tableau for a linear programming problem involving SVM

I have the following set of inequalities and equalites $$\begin{align}y_1x_1+\cdots +y_nx_n &= 0\\ x_1 &\geq 0\\\vdots\\x_n&\geq0 \\ x_1&\leq c\\\vdots \\x_n&\leq ...
0
votes
1answer
40 views

A maximization problem within the simplex

Let $\lambda_i$ be an ordered list of $N$ positive numbers, $\lambda_1<\lambda_2<\dots<\lambda_N$. I'm looking for the extrema of the function $$ f=\left(\sum_{i=1}^N p_i \lambda_i ...
0
votes
1answer
21 views

Linear programming with equality constraints

I want to find a solution to the minimisation problem $$ \text{min } c^Tx \qquad \text{subject to } Ax=b $$ I have implemented the parametric self-dual simplex by R. Vanderbei in Matlab and it works ...
0
votes
0answers
29 views

simplex algorithm - minimization

So I get the basic concept of simplex algorithm but I am working on a project where I have to implement any linear programming algorithm (I chose simplex method) to minimize a function, but I don't ...
0
votes
0answers
20 views

Direction in Dual Simplex method

In the dual simplex problem, when primal become inconsistent then dual have direction. How can we find this direction using dual simplex algo ?
2
votes
1answer
38 views

Does a simplex with equal altitudes have to be equilateral?

Consider a simplex in $\mathbb{R}^d$. Assume that all its altitudes have the same length. Does it necessarily mean that the simplex is equilateral, i. e. all distances between its vertices are equal ...
1
vote
1answer
44 views

A proof related to diameter of a simplex S

Question: Prove that the diameter $\mathcal p(S)$ of a simplex $\mathcal S$ equals the greatest Eucledian distance between two vectors in the simplex. My opinion: We all know what every vector in the ...
2
votes
1answer
54 views

Proving that $H_0(X)=\tilde{H_0}(X)\oplus\mathbb{Z}$

In the article about the Reduced Homology it's stated that $$H_0(X)=\tilde{H_0}(X)\oplus\mathbb{Z}$$ but I don't know how to prove that. I know $$H_0(X)=\bigoplus_{\alpha\in ...
3
votes
1answer
57 views

$\arg\max$ of an increasing function grows as the region grows.

$f_1,\dots,f_N:\mathbb{R}^+\rightarrow\mathbb{R}^+$ are strictly increasing, bounded functions whose derivatives monotonically decrease to $0$ as their argument increases. (Picture the shape of the ...
0
votes
2answers
35 views

How to check if point $x \in \mathbb{R}^n$ is in a $n$-simplex?

Is there any universal solution how to check if a point $x \in \mathbb{R}^n$ is in $n$-simplex for any number of dimensions (any $n$)? Is it possible to use Barycentric coordinates for any $n$? I ...
2
votes
0answers
16 views

A Particular Decomposition of the Simplex

Suppose I have a simplex $S_n$ with unit side-lengths. Fix a vertex $V$. Let $A_n$ be the convex polytope whose points are contained within the simplex, where the euclidean distance from each point ...
0
votes
0answers
28 views

Radio factory linear program

I need a help with this exercise. I’m supposed to write a liner program for the problem below and then solve it using simplex method, but I’ don’t know how to include all the factors into variables. ...
0
votes
1answer
57 views

Every point in a simplex is a convex combination of p and a point in $C^{(p)}$

Let's fix an arbitrary point $p \in \Delta_n = \{(x_1, ..., x_n) \in \mathbb{R}^n \ : \ \sum_{i=1}^n x_i = 1 \}$ Could you help me prove that every point in a simplex $\Delta_n$ can be written as a ...
0
votes
0answers
48 views

Simplex method: tableau at some stage, finding objective row

How do I find the objective row for the tableau if all I am given is the tableau values at the certain stage (without RHS)? Here is the tableau $T$ without the objective row: $$ \begin{bmatrix} 0 ...
1
vote
1answer
30 views

Simplex updates for the inequality LP

Consider the task of minimizing $c^Tx$ subject to the constraint that $Ax \leq b$. I had a couple of questions in relation to the simplex algorithm (applied to this problem): How does one ...
0
votes
0answers
37 views

how to solve a simplex with n variables

I don't know how to resolve a simplex with n variables I have this primal problem \begin{cases} \text{min}& z=-x_1 - x_2 -... - x_n\\ &a_1x_1 + a_2x_2 +... + a_nx_n \le 1\\ &x_1... ...
0
votes
1answer
245 views

How to test if a feasible solution is optimal - Complementary Slackness Theorem - Linear Programming

I have this linear program $$\begin{cases} \text{max }z=&5x_1+7x_2-3x_3\\ &2x_1+4x_2-2x_3&\le8\\ &-x_1+x_2+2x_3&\le10\\ &x_1+2x_2-x_3&\le6\\ &x_1,\,x_2,\,x_3\ge0 ...
0
votes
1answer
29 views

Simplex algorithm question with restraints

How to perform simplex algorithm on the following: $$-x_1-2x_2 \rightarrow min \\ 4x_1+4x_2 \le 12 \\ x_1 \le 2 \ , x_2 \le 2 \\ x_1 \ge 0,x_2 \ge0$$ I would appreciate any hints how to solve this ...
0
votes
1answer
49 views

A very simple geometric/visual example of what a simplex looks like

I was trying to understand what a simplex was intuitively by constructing an example. Consider only points in $\mathbb{R}^2$. From wikipedia the definition seems to be: Choose k+1 points $u_0, ..., ...
4
votes
1answer
139 views

Convex hull of canonical basis of $\mathbb{R}^n$, face of a simplex

Let $I_n := \{1,2,...,n \}, \ p \in \Delta_n = \{(p_1, ..., p_n) \ | \ p_i \ge 0, \sum_{i=1}^n =1\}$ $ \text{supp (p)}= \{ i \in I_n \ | \ p_i \neq 0\}$ For a convex set $C$ we define $F$ to be its ...
0
votes
0answers
39 views

simplex algorithm with tableau

in the picture below you can see the tableau representation of a linear programm with a coefficient $b\in \mathbb{R}$. BV stands for basic variable. For which $b$ is $y_1=\frac{1}{2}, ...
0
votes
1answer
26 views

Approximating a binomial sum over a simplex

For partial binomial sums such as $\sum_{k\le\Delta} \binom{n}{k}$ we don't tend to have closed forms. However we still know asymptotic expansions that are easy to work with. Can we do something ...
2
votes
1answer
177 views

How does the Simplex method handle test ratios with zeros?

I've been running into an issue choosing a pivot when there are constraints with an RHS of zero. It appears that sometimes you should include zero test ratios when searching for the minimum test ...
0
votes
1answer
51 views

Can a basic variable be the entering variable in Simplex method?

I have got from my teacher that "the entering variable in a maximization problem is the non-basic variable having the most negative coefficient in the Z- row" I think X1,X2 are non basic and ...
0
votes
1answer
34 views

Trapped volume of (n-1)-sphere inside an n-simplex

Assume that we take an $n$-simplex (with side length of 2 units) and place a unit $(n-1)$-sphere at each vertex. For $n=2$, half of a circle is enclosed inside the $2$-simplex. For $n=3$, solid angle ...