Questions tagged [simplex-method]
Questions that relates to the "simplex algorithm", from the mathematical optimization field
81
questions
2
votes
0
answers
24
views
In this simplex algorithm tableau, what are the basic variables?
At some point while running the simplex algorithm, we find this tableau:
Would I be correct in saying that at this stage, our basic variables are $x_4,x_3,x_6$ as they are the only ones not equal to ...
- 640
0
votes
0
answers
19
views
Simplex: LP with equality constraints : do I need slack variables?
I am confused about simplex method : I have read from various resources that I need my LP to be in standard form. Then when we have the standard form, we introduce slack variables to turn inequality ...
- 605
1
vote
1
answer
60
views
Linear Programming - Motivation behind the Dual Simplex Method
I am trying to understand the motivation behind the Dual Simplex Method. However, I have run into some roadblocks while understanding the rationale behind the Dual Simplex Method. This is my current ...
- 8,464
2
votes
0
answers
35
views
Why do I get different inequalities from the same linear programming system?
This is from section 7.1 of Dasgupta's Algorithm book:
I attempt to arrive at the optimal solution by using the existing inequalities.
$$x_2 \leq 300$$
$$x_1 + x_2 + x_3 \leq 400$$
$$4x_2 + 12x_3 \leq ...
- 31
0
votes
1
answer
18
views
Simplex Method Row Operations
In pictures provided i understand the pivot column is column 2 and pivot row is row 3.
What I don't get is why its $0.25(4R_1 +29R_3)$ and not just $4R_1 +29R_3$.
Isn't the goal to get zeros in column ...
- 11
0
votes
0
answers
20
views
Simplex method Tableau Row operations why can't I multiply reduced cost by -1?
I am a little confused...
Lets say I have this tableau where I have to make sure my reduced cost (Row 3) is non-negative, why can't I simply multiply Row 3 by -1/R3?
Afterwards, since all my reduced ...
0
votes
0
answers
28
views
Simplex Method - Entering/Leaving Variable
Can someone give an example to show that the variable that enters the basis on one iteration of the simplex method, becomes the leaving variable on the next iteration? You must use the smallest ...
- 11
0
votes
0
answers
13
views
Pivoting : Simplex Algorithm choosing a pivot column for the second time
I found online a set of notes from a university http://www.ms.uky.edu/~jack/2010-01-MA162/2010-02-25-MA162Lab.pdf
I am studying the example of simplex algorithm and I am somewhat confused :
We ...
- 605
1
vote
1
answer
79
views
Local optimum simplex algorithm
I'm trying to figure out why the simplex algorithm cannot get stuck in a local optimum. It does not check all vertices, but is confident that the vertex it ends at is the global optimum.
I have ...
0
votes
0
answers
38
views
Simplex tableau form
I have got a few example MCQ questions regarding the tableau Simplex method. While I thought I can deal with normal examples, I am having a hard time wrapping my head around the examples with missing ...
- 249
1
vote
0
answers
48
views
How exactly is the Simplex Method related to the idea of walking along the edges of a polyhedron?
I understand the theoretical foundation of the idea, that when I want to find the minimum of a linear function over a bounded polyhedron that I kind of only need to look at the vertices and if I am ...
- 11
1
vote
1
answer
55
views
Generic doubt about the Simplex Method
Let's say we are working on a LPP in the following form:
\begin{equation*}
\begin{split}
\min \quad &z = f(x) \\[.15cm]
s.a. \quad &Ax \leqslant b \\[.15cm]
&x \geqslant 0
\end{split}
\end{...
- 599
3
votes
0
answers
53
views
Importance of the Klee-Minty Cube in Optimization
Has anyone ever heard of the Klee-Minty Cube in Optimization?
Supposedly, the Klee-Minty Cube shows the "flaws" of the Dantzig's Simplex Algorithm. Supposedly, Dantzig's Simplex Algorithm ...
- 1,688
1
vote
2
answers
45
views
Artificial Variable in Basis in Two-Phase Method in Linear Programming
Suppose we have the following problem:
$$Z = 3 x_{1} + 2 x_{2} + 3 x_{3} \to max$$
$$\begin{cases} 2 x_{1} + x_{2} + x_{3} = 4 \\ x_{1} + 3 x_{2} + x_{3} = 12 \\ 3 x_{1} + 4 x_{2} + 2 x_{3} = 16 \\ x_{...
- 1,957
0
votes
0
answers
15
views
Simplex Method basis
I study the simplex method and its implementation on traveling salesman problem. After some papers on the problem I found "Solution of a large-scale traveling-salesman problem" by the father ...
- 1
-1
votes
1
answer
61
views
Finding parameters of a linear programming problem
I have the following programming problem:
$\min c_1x_1+c_2x_2$ such that $$x_2 \leq x_1$$$$x_1 \leq 2x_2+2$$$$x_1, x_2 \geq 0$$
How do I show that this problem is feasible and how do i find the ...
user986741
5
votes
0
answers
50
views
An Optimal Solution which Does Not Satisfy Optimality Condition
I read this theorem in a book about Linear Optimization:
In the simplex method, for a minimization problem, a BFS is optimal if all of the reduced costs are negative, i.e. $\forall i \quad z_i-c_i \...
- 717
0
votes
2
answers
52
views
Why does this approach fail?
We have the following statement (translated from Spanish to English):
A company manufactures skirts, blouses and pants. To do this, use a machine for each type of clothing. The machine for skirts ...
0
votes
0
answers
27
views
Simplex Method: Why the pivot should be positive?
The pivot shouldn't be negative or 0, but why is this? I'd like to understand the reason.
Also why do we choose the smallest number in the ratio column to choose the pivot row?
0
votes
0
answers
13
views
Linear Program Phase 1 first pivot doesn't provide a starting dictionary
I have the LP and need to solve it using the two phase simplex algorithm, not the dual two phase;
...
- 19
0
votes
0
answers
57
views
How do I set up the initial simplex tableau?
Maximize: Z = x1 + 3x3
Subject to:
x1 + 2x2 + 7x3 = 4
x1 + 3x2 + x3 = 5
x1, x2, x3 $\ge$ 0
I am confused on how to put it into a simplex tableau because the constraints are already equations.
I know ...
1
vote
1
answer
22
views
Query about bounded variable simplex method
Are bounded variable simplex and bounded variable primal simplex method same? If not where does these two differ?
0
votes
0
answers
25
views
Question regarding Primal simplex method
Hi quick question regarding the primal simplex method. How do you use the primal simplex method when you have to start with a specific basis? I'll give a quick example of what I mean. If we wish to ...
- 35
0
votes
0
answers
26
views
Solving a LPP question using BIG-M method
I am trying to solve the following LPP problem using simplex problem:
Max Z= $8x_2$
Subject to:
$x_1-x_2 \geq 0$
and $2x_1+3x_2\leq -6$
$x_1 \& x_2$ are unrestricted
My approach:
Using graphical ...
- 67
0
votes
0
answers
27
views
Minimizing using simplex
I've been asked to minimize: $3x_1 -x_2 +2x_3$ using simplex.
The conditions are:
$x_1 +x_3 \geq 7$
$x_2-x_1\leq 5$
$x_2-2x_3 \leq 8$
$x_1,x_2,x_3\geq 0$
So I started by adding in my slack and '...
- 233
0
votes
0
answers
31
views
If we have a non-degenerate solution to an LP and the minimum ratio test is successful, is the next BFS always non-degenerate too?
To expand on the title:
If an LP (linear program) has a certain basic feasible solution, and it can be improved by removing a variable from the basis, if the minimum ratio test determines which ...
2
votes
0
answers
36
views
understanding Simplex algorithm
I am trying to understand the relation between two different presentations of the simplex algorithm.
Let $x,c \in \mathbb{R}^{n}$, $A \in \mathbb{R}^{n \times m}$, $b \in \mathbb{R}^{m}$. Let us ...
- 75
0
votes
0
answers
19
views
LP - Artifical variable necessary or not for greater than sign
I am current studying LP and also the simplex method. However, the slides from my professor are not that detailed so I was trying to search for online resources. Particularly about how to convert an ...
- 527
2
votes
0
answers
269
views
Show that if $n-m=2$, then the simplex method will not cycle, no matter which pivoting rule is used
Here $n$ is the number of variables and $m$ is the number of constraints. This is the Exercise 3.10 (with asterisk) in the classical textbook Introduction to Linear Optimization by Dimitris Bertsimas ...
- 626
2
votes
0
answers
137
views
Linear programming: Find feasible basic solution for the Simplex Method
My question is related to this question.
Given a Linear Program (LP) $max\{c^Tx: Ax \leq b, x \geq 0\}$ with $x,c \in \mathbb{R}^n$ and $A \in \mathbb{R}^{m \times n}$. The Simplex Method needs a ...
- 1,902
0
votes
0
answers
34
views
How can I find the correlated equilibrium probability distribution with the help of linear programming algorithm?
The following matrix is the so called battle of sexes game, which has two Nash Equilibria in pure strategies, that is $(F,F)$ and $(C,C)$ with payoff $(2,1)$ and $(1,2)$ respectively and one in mixed ...
- 251
1
vote
0
answers
16
views
Connections between two quadratic programming problems with same constraints (over a simplex)
Assume that we have the following two optimization problems with exactly the same constraints but different objective:
P1: $\min_{{\bf u}} {\bf u}^\text{T} {\bf T}_1 {\bf u}$ subject to C1: ${\bf 1}^...
- 43
1
vote
1
answer
94
views
Finding unknown in an optimal simplex tableau
I have a problem about this simplex problem for my Operations Research class.
The following tableau belongs to the optimal solution of a Linear Programming
Problem. Calculate the value of objective ...
- 13
0
votes
1
answer
49
views
Dual Linear Program and Simplex Method
To find the dual for this linear program, I first represent $y = (y+)-(y-)$ to make sure that every decision variable is greater than or equal to $0$. Then I split the second constraint into
\begin{...
- 17
0
votes
0
answers
93
views
Simplex Method Nelder Mead Minimization Algorithm For Local Minimum
I'm trying to code Nelder-Mead algorithm with basic method (without expandsalpha is 2). I'm doing it with Python and also I have an example in book. I'm trying to implement it.
Here is the example:
...
- 33
0
votes
1
answer
63
views
Initial vertex in Simplex algorithm
Conceptually, the simplex algorithm goes from one vertex of a polytope to the next.
However, how is the initial vertex computed ?
If I follow the simplex tableau scheme, it should at some point ...
- 75
0
votes
1
answer
75
views
Two Phase Simplex Method - confusion about the algorithm statement
Sorry for the vague title, wasn't sure quite how to put it.
I'm supposed to implement a two-phase simplex method solver as a part of one course at my faculty. I'm thinking that I either don't ...
- 837
1
vote
1
answer
323
views
Does a nonzero value of artificial variables, after applying simplex method, show infeasible solution?
In linear programming we sometimes use artificial variables for the simplex method when constraints are expressed as equalities. After a certain number of iterations of the simplex method we reach a ...
- 111
2
votes
1
answer
116
views
Linear programming/Simplex method
I have to find a maximum and minimum of this linear programming problem.
$$\begin{align} max\quad x_1+x_2 \end{align}$$
Constrains
$$\begin{align*}
x_1+x_2+x_3 =3 \\ -2x_1+x_2+x_4=5 \\ x_2+x_5=7\\ ...
- 21
1
vote
1
answer
120
views
Why does the simplex algorithm not accept negative decision variables?
I would like to know why the Simplex algorithm does not accept negative decision variables? I read this article on Wikipedia but couldn't find a satisfying answer.
- 371
1
vote
1
answer
197
views
Simplex example to be applied on Zoutendijk method for constrained optimization
The Zoutendijk method of feasible directions for the optimization with non-linear constraints involves a step where a linear program is solved. In a particular example, the linear program is defined ...
- 167
0
votes
1
answer
95
views
How to derive LPP problem from the auxiliary problem using simplex method?
The original LPP: $f = 2x_1+3x_2 \rightarrow \max$. The constrains:
\begin{align}
-x_1-x_2 &\le -1 \\
x_1+x_2&\le 6\\
x_1+2x_2&\le 8\\
x_2&\le 3\\
x_1\ge 0, x_2&\ge 0\\
\end{align}...
- 1,376
0
votes
1
answer
55
views
About cycling in simplex method
First of all I apologize if you find my question silly as I am not a student from math background.
So far I know when the same basic variables reappear in a later iteration, we say that cycling occurs....
- 1
1
vote
1
answer
492
views
How to understand the reduced cost in simplex method?
I’m reading a note on the simplex method. The author mentions a quantity called “reduced cost”, yet no interpretation of it is provided.
Here’s the setup: $c \in \mathbb{R}^n$ is the cost vector, $A \...
- 645
0
votes
1
answer
38
views
Show that either $(x_1,\dots,x_n) = (0,\dots,0)$ is the optimal solution or the LP is unbounded.
\begin{array}{llclccclcl}
\text{maximize} & c_1x_1 & + & c_2x_2 & + & \dots & + & c_nx_n \\\text{subject to} & a_{11}x_1 & + & a_{12}x_2 & + & \...
- 1,513
2
votes
1
answer
72
views
What would happen if in the BigM method we don’t set the penalty for the artificial variables?
The usual line of argument is that since the artificial variables are introduced solely for the purpose of obtaining a basic feasible solution, and have no meaning in the context of the LP, they must ...
- 2,015
3
votes
1
answer
179
views
Starting the simplex method from a given basic feasible solution?
I have the following LP.
\begin{equation*}
\begin{array}{ll@{}ll}
{\text{maximize}} & x_1 + x_2 + x_3 + x_4 \\
\text{subject to}
&
\begin{bmatrix} 1 & -1 & -3 & 1 \\ 2 & 2 &...
- 2,015
0
votes
0
answers
80
views
Simplex Algorithm Cycles
How can I show that the linear program
\begin{align*}&\min -2x-3y+z+12w\\
&s.t.
\\&-2x-9y+z+9w+s=0\\&1/3x+2y-1/3z-2w+t=0\\&x,y,z,w,s,t\geq 0\end{align*}
can induce cycling in the ...
- 4,397
-1
votes
1
answer
82
views
Solving Dual Problem using Simplex Method?
Let's say I have a primal problem as follows:
(P) Max 2x1 + 3x2 + 5x3
s.t
x1 + 2x2 + 3x3 <= 8
x1 - 2x2 + 2x3 <=6
x>=0
Then we obtain the dual as follows:
<...
- 33
0
votes
0
answers
75
views
Shadow price of a variable
So, I was working on my assignment for an online course and there's something I didn't understand very well. The teacher gave us this model:
$$
\begin{matrix}
\max & Z=3x_1 + 4x_2 \\
s.t. & ...
- 213