The tag has no wiki summary.

learn more… | top users | synonyms

1
vote
0answers
21 views

product of barycentric coordinates over a simplex

Show that: $$\int_K \eta_0^{\alpha_0}(x)\cdots\eta_n(x)^{\alpha_n}dx=\frac{{\alpha_0}!\cdots{\alpha_n}!n!|K|}{(\alpha_0+\cdots+\alpha_n+n)!}$$ where $\eta_i$ barycentric coordinates and $K$ is a ...
2
votes
1answer
45 views

Integral over a simplex

Let $C_k$ be the $k$-simplex. I know that $$\int_{C_k} \prod_{i=1}^k x_i^{\alpha_i-1} dx_i = \frac{\prod_{i=1}^k \Gamma(\alpha_i)}{\Gamma\left(\sum_{i=1}^k \alpha_i\right)} \equiv ...
1
vote
0answers
11 views

Computing the Optimal Simplex Tableau for Linear Programming

I am learning in my class about computing the optimal simplex tableau. I learned that, if you have an initial basic feasible solution, you can apply a series of formulas to compute the optimal ...
0
votes
0answers
12 views

Degeneracy in Simplex Algorithm

According to my understanding, Degeneracy in a linear optimization problem, occurs when the same extreme point of a bounded feasible region $X$ can be represented by more than one basis, that is not ...
0
votes
0answers
14 views

When can i solve simplex tableau

I saw exercises where they give an objective function ( without restrictions ) and a simplex tableau to be completed , if you can solve How do I know when it may solve the tableau ? What are the ...
0
votes
1answer
48 views

Prove max f(x) = -min -f(x)

How do I prove : $$max f(x)= - min -f(x)$$ I am trying to prove this, and have tried to use my book but I am stuck.
2
votes
1answer
20 views

Singular chain complex for integration - pinching on boundary

Singular chain complex, as far as topology are concerned, is just continuous map from standard simplex, and the choice of using simplex over other shape is immaterial. But for integration on manifold, ...
1
vote
0answers
21 views

Explanations about the volume of a regular simplex

I'm really sorry, this may sound ridiculous but I can't understand the Wikipedia explanation about the volume of regular n-dimensional simplices, here. In particular, these two sentences make no ...
0
votes
0answers
21 views

Pachner moves for graph of 4-valent nodes

For 3-simplices (i.e. tetrahedra), I understand the basic idea behind the Pachner moves 1 $\leftrightarrow$ 4, which takes one tetrahedron and replaces it with four (or vice versa), and 2 ...
0
votes
0answers
32 views

Shadow Prices in relation to a Simplex Tableau

I've solved the maximisation problem $z = 5x_1+6x_2+2x_3$ subject to $x_2 + 0.5x_3 \leq 2000$ $20x_1+20x_2+12x_3 \leq 100000$ $x_1 \geq 2000$ $x_3 \geq 2000$ using long-hand Simplex Method ...
0
votes
1answer
42 views

Big-M Simplex Method Returns Unfeasible Solution

Consider the following linear programming problem: "Minimize 2x1 + 3x2 subject to the constraints 2x1 + x2 ≥ 4 2x1 - x2 ≥ -1 x1,x2 ≥ 0" Since there are ≥ signs in both ...
0
votes
0answers
47 views

Chains and associated delta complexes (Algebraic Topology, Allen Hatcher)

Why does the fact of a 2-chain being a cycle imply that in its associated delta complex every 1-simplex comes from exactly 2 different 2-simplices? (it appears in the last paragraph of page 108, where ...
0
votes
1answer
32 views

Solve this linear program using 2 phase simplex

Minimize $2x_1 + 3x_2 + 3x_3 + x_4 − 2x_5$ Subject to $x_1 + 3x_2 + 4x_4 −x_5 = 2$ $x_1 + 2x_2 − 3x_4 +x_5 = 2$ $−x_1 − 4x_2 +3x_3 = 1$ $x_1, x_2, x_3, x_4, x_5 \geq 0$ Im not sure if im doing ...
0
votes
0answers
20 views

Simplex Method Geometrically

Suppose that at some iteration of the simplex method the slack variable $x_s$ is basic in the $i$th row. Show that $$ \large y_{ij\leq 0, j =1,\ldots, n, j \neq s } $$ then the constraint ...
0
votes
0answers
18 views

Solve equation with simplex method

I have equation below and I'm newbie to this method. Can you help me with tutorial or maybe with steps to solve this equation? I know I can use simplex tables, but I don't know a good explanation of ...
1
vote
0answers
14 views

How is distance between two points defined in barycentric coordinates?

Hope someone can help. I have this 3-d simplex (a tetrahedron) and its vertexes have barycentric coordinates defined as follow: $A_1=(1,0,0,0), A_2=(0,1,0,0), A_3=(0,0,1,0), A_4=(0,0,0,1)$. I am ...
0
votes
0answers
16 views

Revised Simplex - What should I do if the objective function has no negative coefficient in the beginning?

I need to solve a problem with revised simplex method, but following the steps from an example, the first step is to find the most negative reduced cost (i.e. the most negative coefficient in the ...
0
votes
1answer
57 views

Linear programming and the simplex method

I am trying to solve this system of equations. My approach would be to introduce slack variables and then somehow use the simplex algorithm to solve this. Can anyone show me how this is done?
1
vote
0answers
39 views

Proof of Simplex Method, Adjacent CPF Solutions

I was looking at justification as to why the simplex method runs and the basic arguments seem to rely on the follow: i)The optimal solution occurs at some vertex of the feasible region (CPF points) ...
0
votes
0answers
34 views

Volume of the set of solutions of two linear inequalities on the simplex

I need an analytical formula for the volume of the set of solutions of two linear inequalities on the N-dimensional simplex $\Omega$. Two be more precise, if $u$ and $v$ are two vectors of ...
0
votes
1answer
33 views

Simplex method - infeasible basic variables

I am working on an optimization problem right now, and I am using the simplex method on the initial tableau. At first, the basic variables are all non-negative and are equal to the slack variables. ...
0
votes
1answer
37 views

Dual simplex doubt (unrestricted)

I have this two problems and i only want to find the dual form: $\begin{gather} max\hspace{.1cm}z =5x_1+6x_2\\ s.t\hspace{.1cm}x_1+2x_2=5\\ -x_1+5x_2 \ge 3\\ x_2 \ge 0\\ x_1\hspace{.1cm} ...
1
vote
0answers
32 views

Least square / Linear regression over a simplex

I have to solve the following least square problem: $$\hat{x} = \arg \min_{x \in S} \|Ax - b\|^2$$ If $S = \mathbb{R}^n$, then the solution is given by $$\hat{x} = (A^TA)^{-1}A^Tb$$ having posed ...
0
votes
0answers
19 views

Quadratic programming over a simplex

I have to solve the following problem: $$\left\{\begin{array}{l}\hat\theta = \arg \min_{\theta} \theta^TQ\theta + \theta^Tl\\ \text{s.t.}\\ \sum_{i=1}^n \theta_i = M\\ \theta_i \in [0, M] ~ \forall i ...
0
votes
0answers
19 views

Maximize Net Profit with Simplex Tableau

I have a profit maximization problem and have been asked to solve it using the simplex tableau method. The thing is as far as I can tell there are no constraints present, so I'm really not quite sure ...
1
vote
0answers
26 views

simplex in MAPLE

I am trying to solve a large system of linear inequalities (about 500 variables) subject to the nonnegativity condition on the variables.Call this system500 for future reference. I do not need to ...
1
vote
1answer
47 views

simplex M-method minimization problem

Solve using the simplex method. Identify the solution of the dual in the final simplex tableau Minimize: $$z=12x_{1}+4x_{2}+2x_{3}$$ **Constraints:**$$ x_{i}\ge 0$$ $$-6x_{1}+3x_{2}\ge 9$$ ...
0
votes
0answers
32 views

Least squares and simplex

I am interested in the linear least square problem with the solution with the following constraints : $$ \min_x \|Ax-b\|^2$$ subject to $0 \le x_i \le 1$ and $\Sigma_{i=1}^n x_i= 1$. Because of the ...
0
votes
0answers
36 views

Simple enumeration of discrete simplex

I'm looking for a computationally nice enumeration of the $n$-dimensional discrete simplex $$\Delta^n_N = \{ x \in Z^{n} | 0 \leq x_i \leq N \, \text{and} \, x_1 + \cdots x_n = N \}$$ I have an easy ...
1
vote
0answers
23 views

Executing Branch and Bound using a Simplex tableau

I'm studying the branch and bound method and how it is used in conjunction with a simplex tableau. The issue I'm struggling with is how you incorporate the branches in your tableau to find out ...
0
votes
0answers
23 views

sensitivity analysis - help!

Hi guys I am doing a quesetion on simplex method and am stuck on the second part of the sensitbity analysis question: I am stuck on the part that is asking for 12 + n. I know that I am changing ...
0
votes
0answers
73 views

Casio fx-83gt - help! Linear Programming

Hi guys I'm studying a module called Operational Research and in particular linear programming. I am doing the simplex method and as anyone who studies linear programming would know, you need to ...
2
votes
1answer
68 views

Prove vertices of a simplex are affinely independent

I'm given that the definition of a simplex $T$ is $x \in\mathbb R^n$ such that $x$ satisfies $n+1$ linear inequalities: $(u_k, x) \lt c_k$ for $k = 1,\ldots,n+1$ (i.e. $T$ is the intersection of $n+1$ ...
1
vote
1answer
34 views

Above what order of magnitude a pure cutting-plane algorithm must be forgotten in favour of branch-and-cut?

Crawling the web on the subject of the cutting-plane algorithm, I have seen everywhere that a pure cutting-plane method cannot be used for numerical instability reasons after some iterations. But do ...
2
votes
1answer
55 views

Can Gomory's cutting plane be used to solve Mixed Integer Linear Programs?

Do you know if Gomory's cut can be used to solve MILP problems ? I have read that Gomory's cut is useful when all variables are integer, but what if just some of them are integer ? Is is necessary ...
0
votes
0answers
83 views

The dual simplex algorithm

Following is the dual simplex algorithm, adapted from p. 283 of Daniel Solow's "Linear Programming, An Introduction to Finite Improvement Algorithms", Elsevier Science Publishing Co., Inc., 1984. I ...
1
vote
2answers
84 views

Forbidden range for a linear programming variable

I would like to express a linear program having a variable that can only be greater or equal than a constant $c$ or equal to $0$. The range $]0; c[$ being unallowed. Do you know a way to express this ...
0
votes
1answer
48 views

Linear programming alternate optimum solutions

**Q- The Optimum of a linear programming problem occurs at (1,2,3) and (-1,0,7) then the optimum also occurs at? a)(2,4,6) b)(0,3,5) c)(0,1,5) d)(3,2,1) e) None of the above. When we are given two ...
1
vote
1answer
37 views

linear inequalities using LP solutions not from simplex

I am trying to solve a set of inequalities using linear programming (LP) with objective function set as a constant. Usually this set of inequalities would have many solutions all of them in the ...
0
votes
0answers
11 views

Using the simplex to define a probability distribution

I am reading a paper where a probability distribution with n categories is being defined in terms of a vector $\mu = <m_1, m_2, ... m_n>$. The authors define this as a vector $\mu \in ...
0
votes
1answer
107 views

Network simplex method, leaving and entering variables

Could someone give me a hint on this question, which is a past exam question: Under what circumstances will an entering variable in the network simplex method be the same as the leaving variable? ...
0
votes
0answers
32 views

How do I show uniqueness of an optimal solution given by simplex?

Looking at a past paper for combinatorial optimisation... ``Show that if $\bar{c_i}$ > $0$ for all $i \notin I$ at some stage of the simplex algorithm then the basic feasible solution $x$ ...
0
votes
1answer
115 views

Can someone explain the effects of degenerate basic feasible solutions in the simplex algorithm?

I was given this on an assignment sheet, and am now using it to revise from...I cannot remember the issues that arise from degeneracy of basic feasible solutions... Let $P$ =$\{x\in \mathbb{R}^n ...
1
vote
1answer
35 views

Why is this simplex procedure not working? $\min z = y - x + 1$

I have read of two ways to solve this program with the Simplex algorithm. One worked and the other didn't. The only difference is that, in the one that didn't work, I rewrote the function. I will ...
2
votes
2answers
53 views

What is the point of triangulating topological spaces?

In a general sense, what is the purpose to triangulating, for example, a 3-dimensional topological space? What advantages does it give if we can triangulate a Seifert-Weber space into 23 tetrahedra? ...
0
votes
1answer
40 views

How can I verify my linear program solutions?

I started solving linear programs with the Simplex algorithm, however it is unclear to me how can I verify my solutions. I have heard about geometrical solutions easy to check visually, but I'd ...
1
vote
1answer
19 views

What to do if the righthand of a constraint is a variable when solving Linear programs?

I'm starting to solve linear program exercises with the Simplex method. $$max \ (3x_1-x_2)$$ $$\begin{cases} x_1-x_2 \le 3\\ 2x_1\le x_2\\ x_1+x_2\ge 12\\ x_2 \le 10\\ x_1,x_2 \ge 0 \end{cases}$$ I ...
0
votes
1answer
71 views

Simplex - Help with a proof

I am trying to prove the following (basic) claim about simplex. If you check my proof and help me with the part where I stuck, I would appreciate it very much. Let $X$ be a finite set and define ...
1
vote
0answers
49 views

How to use the simplex method for linear programs?

I believe to be missing something important in the Simplex algorithm, because I can't get it to work. From what I gather, there are three steps per iteration, given a matrix for a linear program in ...
0
votes
0answers
26 views

How to practically perform reinversion in PFI (Product Form of Inverse) Simplex.

While doing Revised Simplex using Product Form of Inverse. We have product of set of Eta Vectors(Elementary Matrix) to describe the Basis Inverse after certain number of steps in simplex. ...