The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
27 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
27 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
9 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
18 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
33 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
54 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$ ...
0
votes
1answer
28 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 ...
1
vote
1answer
35 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
62 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
71 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
34 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
26 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
10 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
53 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
21 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
50 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
32 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
46 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
39 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
18 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
33 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
36 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
20 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. ...
1
vote
1answer
23 views

Geometry of leaving variable in simplex method

Why can't a leaving variable in a simplex method iteration be the entering variable in the next iteration, in terms of the geometry?
0
votes
0answers
78 views

What are canonical vectors?

I just begun with linear programming. Given an objective function $z$ and certain restrictions defined by $Ax = b$, we got to find the values necessary to maximise or minimise that function's ...
1
vote
1answer
51 views

Cycling in Simplex Method - Smallest Subscript Rule

Could someone explain to me how using the smallest subscript rule causes a cycling LP to terminate? At the moment it looks to me that a program would use it to determine whether the matrix from the ...
0
votes
1answer
331 views

Dual Simplex Method Example Problem

I have tried to solve this Linear Program: max z = −2*x1 − x2 s.t. −2*x1 + x2 + x3 ≤ −4 x1 + 2x2 − x3 ≤ −6 x1,x2,x3≥0 Choosing -6, ...
0
votes
1answer
49 views

$k$-dimensional volume of the simplex spanned by $(k+1)$ vectors in $\mathbb{R}^n$ for $k<n$

My question is about the $k$-dimensional volume of the simplex spanned by the origin together with $k$ vectors stored in an $k \times d$-matrix A. I found two references saying that this volume is ...
0
votes
1answer
37 views

The Simplex in $\mathbb{R}^n$ is convex

Problem: Show that $S:= \lbrace v \in \mathbb{R}^m \mid v=\displaystyle \sum_{j=1}^n a_j v_j, \text{ with } a_1, \dots , a_m \in [0,1], \ \sum_{j=1}^m a_j=1 \rbrace$ the Simplex of $\mathbb{R}^n$ ...
1
vote
0answers
22 views

Reduced Cost in Network Simplex Algorithm

On page 5 of the slide, [T]he reduced cost of a non-basic arc $(i, j)$ is the sum of the costs of the arcs forming a cycle with $(i, j)$ in the current tree solution. Why is that the case?
3
votes
1answer
54 views

simplex method standard form

i am unable to understand algebraic formulation of simplex method.when we add slack variables, and solve for finding basic feasible solution we put free variables equal to zero. My question is why ...
0
votes
0answers
18 views

Primal solution and basic solution in Simplex

From: http://www.stats.ox.ac.uk/__data/assets/pdf_file/0016/5830/e3-chap2_pdf.pdf Suppose we have a (primal) dictionary like in the picture above. Primal Solution: $(0,0,11,18,14)$ and Basic ...
1
vote
0answers
54 views
1
vote
1answer
46 views

Convex Functions and their maximums?

Show that the maximum of a convex function on a convex polytope occurs at one of the extreme points of the polytope. I am really stuck here and don't know where to begin.
-1
votes
1answer
65 views

The number of ways to get N as the sum of R elements with constraints

The number of ways to get N as the sum of R elements, except my solution must have no repetition (3+2 and 2+3 counts for only 1), and 0 cannot be used. For example: N=8, R=2, should return 4. The ...
0
votes
1answer
38 views

Maximization with the Dual using the Simplex Method.

I have an exam in a few hours. I need to understand the solution to the following question Find the Maximal to the the following $2 x_1 + 3 x_2$ is the objective function. The constraints are ...
2
votes
1answer
28 views

Choosing pivot while solving Linear Programming in case the constraints are lesser than the available variables.

I am trying to solve a LP with simplex method which says like. Suppose, Maximize $$10x_1+20x_2+20x_3$$ subject to \begin{align} \tfrac{2}{3}x_1+4x_2+x_3&\leq 50&& (I)\\[0.5em] x_1 + ...
1
vote
0answers
42 views

Prove that A has a geometric realization in $\mathbb{R}^d.$

A flag in a simplical complex K in $\mathbb{R}^d$ is a nested sequence of proper faces, $\sigma_0 < \sigma_1 < ... < \sigma_k$. The collection of flags forms an abstract simplical complex A ...
0
votes
1answer
19 views

Determine Number of Simplex Iterations

I have an assignment, which asks me to determine the least number of simplex iterations necessary to solve different optimization problems. One problem is: a model with 1150 constraints and 2340 ...
0
votes
0answers
41 views

What is the Surface Vector and Volume of a Multidimensional Simplex?

I assume a simplex is a triangle of points in $d$ dimensions. I said that given $d+1$ points $p_{ij}$ in $d$ dimensions: The volume of the simplex is $$ \begin{equation} V = \left|\frac{\det( ...
2
votes
0answers
38 views

Representing four-dimensional pyramids [closed]

I'm trying to mentally represent four-dimensional pyramids with different bases (like tetrahedra and triangular prisms). Can't do that in my head.
0
votes
0answers
54 views

Using Polya's Theorem to check positivity of a multivariate polynomial

I wish to check if a homogeneous polynomial of total degree 4 is positive definite. The polynomial is of the form $$P(u,v,x,y) = \sum_i\alpha_iu^{i_1}v^{i_2}x^{i_3}y^{i_4}$$ with $0 \le i_j \le 2$, ...
7
votes
0answers
100 views

More approximately orthogonal vectors than the dimension of the space

It is impossible to find $n+1$ mutually orthogonal unit vectors in $\mathbb{R}^n$. However, a simple geometric argument shows that the central angle between any two legs of a simplex goes as $\theta ...
0
votes
0answers
79 views

Maximizing a single variable objective in a many variable simplex with a known basic feasible solution

I'm new to LP so please excuse any obvious mistakes. I have a linear program with N+1 variables, these are represented below as $x$, which is a vector of length $N$, plus the single variable $p$. ...
2
votes
1answer
63 views

Solutions of the LP problem

I am asked to find all the solutions of the following linear programming problem using the simplex method. $$\min(2x + 3y + 6z + 4w)$$ $$\begin{aligned} x+2y+3z+w &\geq 5\\ x+y+2z+3w ...
0
votes
1answer
150 views

Choosing pivot row in Simplex - slack variables allowed?

I have a question concerning the Simplex method to solve linear optimization problems. I have the following problem: $$ f(x,y,z) = x+2y+3z$$ Constraints: $$x+y+z \leq 3$$ $$2x+2y+z \geq 4$$ So my ...
2
votes
1answer
56 views

What are the optimal strategies for the “prime-game”?

A and B are playing the following game : A and B choose a number from 1 to 100, not knowing the number chosen by the opponent. A wins if the sum of the chosen numbers is prime, otherwise B wins. ...
2
votes
0answers
138 views

Is simplex method weaker than other methods?

Given linear program: $$ \text{min } x_1 - x_2 + 2 x_3 $$ s.t.: $$ -3x_1 + x_2 + x_3 = 4 $$ $$ x_1 - x_2 + x_3 = 3 $$ $$ x_i \geq 0; i = \{1,2,3\} $$ solution by simplex method (with double pass) is ...
1
vote
0answers
38 views

The difference between an affine k-simplex and a rectilinear k-simplex

The notion of rectilinear k-simplex appears in Theorem 10.27 of Rudin's book "Principles of Mathematical analysis", then what is the definition of a rectilinear k-simplex? I read the proof of Theorem ...
1
vote
1answer
79 views

Uniformly distributed points over the surface of the standard simplex

I would like to generate points that are uniformly distributed over the SURFACE of a standard $k$-simplex ($k$ dimensions, $k+1$ vertices). One way to efficiently generate points that are uniformly ...