The tag has no wiki summary.

learn more… | top users | synonyms

0
votes
0answers
26 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
22 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
19 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
11 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
25 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
3 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
21 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
17 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
29 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
37 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
14 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 ...
-1
votes
0answers
14 views

Transform a Matrix Variable get lost?

I have the following problem. I have a Simplex exercise where I need to minimize the objective function. Therefore I need to transpose the initial matrix. However when I transpose the matrix my third ...
0
votes
0answers
24 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
14 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
36 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
23 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
52 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
48 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
32 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
15 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
0answers
65 views

How to Solve this maximization Problem?

You are given two s: N and K. Lun the dog is interested in strings that satisfy the following conditions: The string has exactly N characters, each of which is either 'A' or 'B'. The string s ...
0
votes
0answers
26 views

How to Solve this Linear Programming Problem?

$$\max[Z(x,y)=x+y]$$ $$-x+y\le 1$$ $$x\ge 0$$ $$y\ge 0$$ What i have done so far ? I tried simplex method , but i can't stop iterating . It really seems like a live lock . So how can i solve ...
0
votes
1answer
50 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
24 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
29 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
35 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
84 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
28 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
38 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
135 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
33 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
18 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
71 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
28 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
30 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 ...
0
votes
1answer
43 views

Explain initial basic feasible solution

Let us write x = (x$_0$, x$_s$)$^T$, where x$_0$ contains the original variables and x$_s$ contains the $m$ slack variables. Then it is obvious that by setting x$_0$ = 0, we have Ix$_s$ = b. ...
1
vote
0answers
92 views

Conversion into linear program

I have an optimisation problem with decision variables that are multiplied with another (a weighted average is calculated). I'd like to convert it into a linear program. I found this link that ...
0
votes
1answer
33 views

Beginner Simplex problem

Good evening, I have started studying the simplex method for some examinations I would like to take, and to be perfectly honest, I am stuck really bad. The basic examples and exercises are simple, ...
0
votes
1answer
31 views

Lexicographic Pivoting Rule: Why does that work?

On purpose, I do not write details about it, because I am interested in the intuition and not the details. But if someone asks for it, I can do that. So my question: Could anyone help me with the ...
1
vote
2answers
60 views

Represent if-else or OR condition in a linear equation (optimisation with simplex algorithm)

I would like to write some linear equations and inequations to state that the sum of all possive x - C is smaller than L. As my ...
0
votes
0answers
37 views

Find all optimal solutions by Simplex

Let "stable operation" be an operation on a simplex tableau such that the entering variable has a reduced cost of 0. Recall that a pivoting operation will not change the objective value if either the ...
0
votes
0answers
32 views

General formula for n-Simplex side-lenghts given n-volume and angles

Given a flat triangle's three angles $\phi_i $, and its area $A$, you can calculate the $i$th sidelenght $s_i$ (using Einstein's sum-convention) like so: $$ s_i=\frac{\sqrt{2A} \sin \left(\phi ...
3
votes
1answer
46 views

Simplexes in $\mathbb R^n$ have at most $n+1$ points

This is an exercise from the book Espaços Métricos (metric spaces) by Elon Lima. I'm translating it (the part of it that I'm having trouble with): Show that if $X\subset\mathbb R^n$ is such that ...
2
votes
1answer
68 views

Two-phase simplex

The upper part of the image attached is the question and lower part is the solution. I did the exact same table as table4 in the picture, yet I put the ratio of [2] as 0.5/0.5=1 instead. Could ...
1
vote
1answer
47 views

Can number of constraints be less than number of variables in Linear Programming?

In standard form of LP we have $n$ variable and $m$ constraint. In simplex algorithm we set all non-basic variable to zero and at most $m$ basic variable have positive value. if $m < n$, then at ...
1
vote
1answer
74 views

solving LP problem : no optimal solution exists?

$$\max[Z(x,y)=3x+2y]$$ $$-x+y\le 1$$ $$-x+2y\le4$$ When I tried to solve the above maximization LP problem using the simplex method, from the first iteration, all basic variables became negative. ...
1
vote
2answers
36 views

Correlation between Binary and N-dimensional simplexes

I found an interesting correlation between binary numbers and $n$-dimensional simplexes and I'm trying to find where I can find more information on the subject. I noticed that binary representations ...
1
vote
1answer
122 views

Linear programming algorithm that minimizes number of non-zero variables?

I have real world problems I'm trying to programmatically solve in the form of $$Z = c_1 x_1 + c_2 x_2 + \cdots + c_n x_n$$ Subject to \begin{align} & a_{11} x_1 + a_{21} x_2 + \cdots + a_{n1} ...