Questions tagged [simplex-method]

Questions that relates to the "simplex algorithm", from the mathematical optimization field

Filter by
Sorted by
Tagged with
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
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 ...
user avatar
  • 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{...
user avatar
  • 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 ...
user avatar
  • 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_{...
user avatar
  • 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 ...
user avatar
-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 ...
user avatar
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 \...
user avatar
  • 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 ...
user avatar
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?
user avatar
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; ...
user avatar
  • 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 ...
user avatar
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?
user avatar
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 ...
user avatar
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 ...
user avatar
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 '...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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}^...
user avatar
  • 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 ...
user avatar
  • 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{...
user avatar
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: ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
  • 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 ...
user avatar
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\\ ...
user avatar
  • 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.
user avatar
  • 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 ...
user avatar
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}...
user avatar
  • 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....
user avatar
  • 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 \...
user avatar
  • 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 & + & \...
user avatar
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 ...
user avatar
  • 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 &...
user avatar
  • 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 ...
user avatar
  • 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: <...
user avatar
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. & ...
user avatar