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

learn more… | top users | synonyms

1
vote
0answers
15 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
42 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
26 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
28 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
86 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
21 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
8 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
23 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
105 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
81 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
12 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
28 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
36 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
23 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
25 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
48 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
49 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
61 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
24 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
61 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
32 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
18 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
38 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
21 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
48 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 ...
0
votes
1answer
17 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 ...
2
votes
1answer
43 views

Bounding solid angle of tetrahedron

Let $K\subset \mathbb R^3$ be a non-degenerate tetrahedron. This tetrahedron has the property that the ratio between diameter and radius of insphere is bounded, $$ d \le \kappa r\ \text{ for some } \ ...
0
votes
0answers
6 views

Partitioning a simplex to simplices with orthogonal corner

Can every $n$-simplex be partitioned to simplices with orthogonal corner(that is, simplex with vertices $\{ 0, a_i \mathbf e_i (i=1, \cdots, n) \}$)? I think this hold if $n=2$, but I do not know in ...
2
votes
0answers
30 views

Find a metric on the simplex so that every transposed positive stochastic matrices becomes a contraction.

A stochastic matrix $P$ is a $n \times n-$matrix with entries $p_{ij} \in [0,1]$ so that $\sum_{k=1}^n p_{ik} = 1$ for every $i \in \{1,...,n\}$. The matrix $P$ is called positive, if no entry ...
0
votes
1answer
81 views

Why are the quantities equal to 0?

I am looking at the general form of the Simplex algorithm with the use of tableaux. $\overline{x_0}$ is a basic non degenarate feasible solution and thus the columns $P_1, \dots, P_m$ are linearly ...
1
vote
1answer
20 views

assigning artifical variables positive or negative

I'm struggling on determining when to assign an artifical variable a positive or a negative value. The example I have at hand is: Max: $x_1+x_2$ St. $$\begin{align}3x_1+2x_2\le5\\ x_1-x_2\le1\\ ...
0
votes
1answer
38 views

Show that convex hull of a finite set is compact

I refer to the answer here by Mariano Suárez-Alvarez. Question: $(1)$ Why the set $S = \{ (t_1,t_2,...,t_n) \in \mathbb{R}^n | t_1,t_2,...,t_n \geq 0, t_1 + t_2 + ... + t_n = 1\}$ closed? $(2)$ ...
0
votes
2answers
56 views

Homeomorphism of $\Delta^n$ into itself that switches interior points

Let $\Delta^n$ be the standard $n$-symplex. Let $x, y$ two interior points of $\Delta^n$. How can I prove that there exists an homeomorphism of $\Delta^n$ into itself that maps $x$ to $y$? I can see ...
0
votes
1answer
17 views

Finding feasible solution s.t. value of objective function is greater than $248$.

I was asked the following question in examination : Using the simplex method ,verify that following problem is unbounded and hence find a feasible solution for which the value of the ...
1
vote
1answer
70 views

Simplex method - multiple optimal solutions?

I have to solve this optimization problem: $\min \space\space z= x_1 - x_2 + 3x_3 $ $\text{s.t.}\space\space x_1-x_2+x_3-x_4=2$ $\space\space\space\space\space\space\space\space\space ...
4
votes
1answer
113 views

Find the basic feasible solutions

Find the basic feasible solutions of the system of restrictions: $$2x_1+x_2+x_3=10 \\ 3x_1+8x_2+x_4=24 \\ x_2+x_5=2 \\ x_i \geq 0, i=1,2,3,4,5$$ We notice that the rank of the matrix ...
2
votes
1answer
109 views

Description of the Simplex algorithm

I am looking at the description of the Simplex algorithm. Let $\overline{x_0}$ be a non degenerate basic feasible solution. We suppose that $\overline{x_0}=(x_{10}, x_{20}, \dots, x_{m0},0, \dots,0)$ ...
0
votes
0answers
111 views

Simplex Method and Unrestricted Variables

I was hoping someone here could explain this issue: say you are working with a set of linear equations in standard form ($a_1 x_1 + a_2 x_2 + a_3 x_3 + \ldots + a_n x_n= c$ where $c$ is the constant), ...
0
votes
1answer
27 views

How to read the Dual optimal solution from the terminal tableau.

I have a terminal tableau and I know that it is easy to get the primal optimal solution but how can i get a dual optimal solution from the tableau. My tableau is below: My notation is slightly ...
0
votes
0answers
14 views

Simplex Method, why must we select a pivot point and why is row-reducing different than linear algebra row-reducing?

Why is it that in the Simplex Method for Finite Mathematics that we must select a pivot point? Moreover, why is it that when we row-reduce, we don't aim to get it into this form ...
0
votes
0answers
39 views

How to solve this linear programming problem with simplex method?

I am trying to solve the following problem with simplex method, but the problem I have encountered is that it is doesn't have any inequalities to introduce slack variables. Please suggest me on how to ...
0
votes
0answers
13 views

cosine similarity among multiple sets

my background is not mathematics, so I will try to do my best to describe. I have multiple sets of elements A0 = {... }, A1 ={..}, .., An ={} I want to: 1. compute a similarity (here cosine for ...
0
votes
0answers
35 views

simplex method with two indices - transportation/allocation problem

EDITED: I have problem with finding some described examples with simplex for double indices. In one book I have example of problem with only solution given (it is written that by simplex method), but ...
0
votes
0answers
19 views

Compute the simplex which projects to a polytope

Given a polytope $P=\{\vec{x}\mid A\vec{x}\leq b\}$, it is known that $P$ can be represented as an affine projection of a simplex. The question is, how do I come up with the affine projection and ...
0
votes
1answer
37 views

polytope vs simplex

It is stated that any polytope is an affine projection of a simplex. I do not quite understand this: on the plane, a simplex has exactly 3 vertices, but let's consider a polytope $P=\{(x,y)\mid ...
0
votes
1answer
28 views

General question about new objective function W using the simplex method

In regards to the two-phase simplex method; When creating a new objective function that consists the sum of the constraint(s) with artificial variables, I am told that if the Min value of (wmin) w is ...
0
votes
1answer
29 views

Can every simplex be a regular simplex by pointwise scaling?

There is a $n$-simplex with $n+1$ vertices $\{\mathrm P_i\} \quad (i=0, \cdots, n).$ (That is, P_i are not co-hyperplanar points.) And the origin $O$ is inside of the simplex. Is there a collection of ...
1
vote
1answer
26 views

Boundary/interior of $0$-simplex

In a $1$-simplex, it's clear that the boundary is the set of the two $0$-simplices and that the interior is all the points in between them. But what about in a $0$-simplex? I'm asking because I know ...
0
votes
0answers
9 views

Maximal volume of pedal simplex

Let $P$ be point inside the $n$-simplex with unit volume, and $P_1,P_2, \cdots ,P_{n+1}$ be the projections of $P$ on the faces. What is the maximum volume of a simplex $P_1P_2\cdots P_{n+1}$ we can ...