Questions tagged [simplex-method]

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

Filter by
Sorted by
Tagged with
0 votes
0 answers
11 views

Optimal Table may change in LPP

If we solve a LPP with let's say 2 constraints with all slack starting variables with non negative right hand side. We get the optimal table. Now suppose we change the constraint coefficient of a ...
Upstart's user avatar
  • 2,635
0 votes
1 answer
34 views

Initial basic feasible solution for LPP with 'greater than' constraints

While solving a linear programming problem with n variables in m equations (n > m) using the simplex method, an initial feasible solution is found by setting n - m variables to zero. Mostly when ...
Hari's user avatar
  • 1
1 vote
0 answers
13 views

Linear programming dual simplex method problem [closed]

enter image description here I've this question and I changed the sign for the max Z and then found the dual of primal. But here the problem is that now I have -ve values in ratio. I am thinking of ...
user avatar
0 votes
0 answers
31 views

Python Native Implementation of Mixed Integer Linear Programming

Is it possible to have pure Python implementation of Mixed Integer Linear Programming, something similar to mip, pulp, cvxpy, etc. - but such simple as https://github.com/ispaneli/lippy - it is ...
Kamil Islamov's user avatar
0 votes
0 answers
25 views

Finding possible values of entries of a simplex tabeau

While solving a standard form problem, we arrive at the following tableau, with $x_3, x_4, and x_5$ being the basic variables: The entries α, β, γ, δ, η are unknown parameters. We have to determine ...
abc's user avatar
  • 493
1 vote
1 answer
73 views

Unbounded slack variables in linear programming problem

I have a linear programming problem: Maximise, $z = x_1 + x_2$ Subject to: $$ x_1 + x_2 \ge 10 $$ $$ 2x_1 + x_2 \le 40 $$ $$ x_1, x_2 \ge 0 $$ When I construct the simplex tableau adding 2 slack ...
PythonIsBae's user avatar
0 votes
0 answers
19 views

Representation of polytopes as intersection of halfspaces

Let $A \in \mathbb R^{m \times n}$ have rank $m < n$ On the way to showing that the condition (for $x \in \mathbb R^n$) $A x = b$ $x \geq 0$ is equivalent to (intersection of halfspaces) $\...
Mark's user avatar
  • 389
0 votes
0 answers
20 views

Bijection between basis of a constraint matrix and vertices of the feasible polytope

The Wikipedia article for the revised simplex method states A vertex of the feasible polytope can be identified as a basis for $B$ for the matrix $A$, chosen from the columns of $A$ Here, the ...
Mark's user avatar
  • 389
0 votes
0 answers
42 views

Linear Programming Simplex method issue with basis

I'm working on what I think is a fairly basic LP problem, the objective function and constraints are seen in the attached image. The task also specifies that the starting basis should be x1, x2, x3, ...
Peter Robertsson's user avatar
0 votes
0 answers
37 views

Trouble with Implementing Dual Simplex Algorithm

For a homework problem I am asked to implement the dual simplex algorithm on the following linear program: $$ \min -25x_1 -30x_2 \\ \\ s.t. 5x_1 +4x_2 \leq 120 \\ \\ 20x_1 +30x_2 \leq 690 \\ \\ x_i \...
AnotherPerson's user avatar
1 vote
0 answers
76 views

Linear programming, simplex method.

Why the requirement that variables must be non-negative isn't written in the corresponding tableau? Isn't this kind of constraint equivalent to others? For instance consider some LP with 2 variables $...
Dmitry_IT_03's user avatar
1 vote
1 answer
122 views

Proof of the ratio test for dual simplex

I am familiar and know the proof of the ratio test for normal simplex algorithm (with this I mean the test used to know which variables enter and leave the basis). I also know the ratio test for dual ...
Pedro García's user avatar
1 vote
0 answers
90 views

How to determine that the problem is unbounded when using Dual Simplex Method? How to prove infeasibility of problem using dual simplex method?

This is how we got the dual simplex method explained: With this method we solve a primary problem, not a dual one, in the primary simplex method (that is, in the standard method for the minimization ...
Zam's user avatar
  • 17
0 votes
0 answers
31 views

How should I set variables when using Big-M method in simplex method.

Problem Image I tried to solve this, but this was slightly different. I set, $A =\begin{equation} \begin{bmatrix} 1 & 4 & 2 & -1 & 0\\ 3 & 2 & 0 & 0 & -1\\ ...
Jinha Chang's user avatar
0 votes
0 answers
44 views

Simplex method: finding the next vertex?

I am quite new to the simplex algorithm, but I have been following the explanation of this excellent video. Unfortunately, I believe that there are some cases not discussed in the video that I'd like ...
J.Galt's user avatar
  • 961
0 votes
0 answers
59 views

Problem with the simplex method in a cost accounting problem

I have the following problem in my business class. I have done an error in my solutions but I don't know where it is. Can Someone help me? It's October, and the new management of Elektronik AG is ...
Marco Di Giacomo's user avatar
2 votes
1 answer
185 views

Gomory Cut combined with Duality in Integer Programming

Let's say we apply dual simplex method in the process of doing a gomory cut in integer programming. Is the "algorithm" the same when working with the dual problem? I ask this because we ...
Ronald's user avatar
  • 61
3 votes
1 answer
130 views

Intuition behind duality in linear programming

I'm looking for an intuitive explanation of the duality principle in Linear Programming. About having a solution or not: Farkas' Lemma: $A x=b ; x \geq 0$ has a solution <=> $A^T y \geq 0 ; b^T ...
Ronald's user avatar
  • 61
3 votes
1 answer
101 views

What after Gomory Cut in Linear Programming?

After applying Gomory Cut (to remove the non-integer solution) in Linear Programming, I don't really know what to do with the new constraint that I get as a result. I have tried to add the new ...
Ronald's user avatar
  • 61
1 vote
0 answers
33 views

Enumerating all edges from a vertex in an H-representation of a polytope?

Description Let's say I give you a convex polytope in $h-$representation, i.e. $Ax \leq b$, with $A \in \mathbb{R}^{m \times d}$. For now let's assume $d=3$. A vertex $v$ is non-degenerate if there ...
Makogan's user avatar
  • 3,309
1 vote
0 answers
85 views

Why do some implementations of the simplex method use an identity matrix while others don't?

I am working on an implementation of the simplex method. Ferguson's notes$^\color{magenta}{\star}$ don't include the identity matrix in the simplex tableau. My algorithm$^\color{magenta}{\dagger}$ ...
Tilo RC's user avatar
  • 11
0 votes
0 answers
20 views

How to select non-singular new basis in revised simplex

In revised simplex, as described here (relevant pdf pages 21-23), after pricing phase is done and entering column is known, the ratio test phase is performed by considering non-zero rows of column $$\...
koromo's user avatar
  • 1
2 votes
1 answer
122 views

Finding different solutions to Linear programming problems

I'm working on a program where I want to solve problems of the type: $$Ax\leq b $$ Where $A$ is a $m\times n$ matrix with $a_{ij} \in \mathbb{R}$, $x \in \mathbb{R^n} $ and $b \in \mathbb{R^m} $. ...
Blueman's user avatar
  • 23
0 votes
0 answers
22 views

Dual simplex computational feasibility when applied to primal problems with many bound variables

Assuming primal simplex problem in form of $$ \displaylines{ \begin{align} (P) & \\ \text{min} \ & c^Tx \\ \text{s.t.} \ & Ax = b \\ & -\infty \lt l \le x \le u \lt \infty \\ A \ \...
koromo's user avatar
  • 1
0 votes
0 answers
103 views

Is there any cycling example for steepest edge pivoting rule in Simplex method, when there is a finite optimal solution

First, the steepest edge pivot rule is the rule in A practicable steepest-edge simplex algorithm , and Steepest-edge simplex algorithms for linear programming. The cycling examples founded, are all ...
Chen Deng-Ta's user avatar
1 vote
0 answers
31 views

Help with solving minimisation problems using primal simplex method

I am trying to understand how to solve minimisation problems using primal simplex method and somehow I understand the steps, just that the final result is not correct. Maybe I am doing something wrong....
Everything Pro's user avatar
0 votes
0 answers
31 views

How to start the second iteration of the revised simplex algorithm?

I converted the question into standard form by adding three slacks. And I computed my first iteration: I want to start my next iteration (iteration two, but I have problems) I need to compute the ...
AliceRathbone's user avatar
1 vote
1 answer
48 views

How to extract a solution from simplex method's tableu while non-stack variables are non-basic?

Take a look at the following simplex tableu: The pivot element is at (1,1) with a value of 2. Eliminating other rows I get the next tableu: That is the last step since there is no negative values in ...
g00dds's user avatar
  • 187
1 vote
0 answers
52 views

Interpretation of solutions in simplex

Suppose we have problem of maximizing some cost function $c'x$ subjecto to $Ax = b$ and $x \geq 0$. The optimal solution is given by a basis $B$ (subset of $A$'s columns) such that $$\mathbf{x}_B = B^{...
opt's user avatar
  • 41
0 votes
1 answer
60 views

Determine the daily production program that maximizes the company's output

Crossposted at Operations Research SE The mechanical workshop can produce $600$ units of part #1 or $1200$ units of part #2 per shift. The production capacity of the thermal workshop, where these ...
Bohdan's user avatar
  • 3
0 votes
1 answer
87 views

Does there exist a “Klee-Minty variant” for the Network Simplex method?

The Network Simplex method works much faster than the traditional Simplex method for min/max flow problems. However, the Simplex algorithm struggles to handle the Klee-Minty cube because most pivoting ...
Miss Mae's user avatar
  • 1,028
0 votes
0 answers
40 views

Transform an inequality system into the input for the simplex algorithm

I have a problem that the simplex algorithm was not discussed in the course, but a sample solution uses the simplex algorithm in order to obtain a Gomory Mixed Integer Cut. The dual problem to my ...
jupiter_jazz's user avatar
2 votes
1 answer
121 views

Reducing artificial variable needed for LPP

Given that I have a question of an objective function to minimize or maximize and I have a constraint for the same such that when converting to equation form for using simplex method would require an ...
STRIKING THUNDER's user avatar
0 votes
0 answers
21 views

How to solve minimisation using dual and simplex method

How would I minimise $2y_1 + y_2$ using the simplex method? subject to: $ 10y1 + y2 \ge 10 $ $ 2y1 + y2 \ge 8 $ $ y1 + y2 \ge 6 $ $ y1 + 2y_2 \ge 10 $ $ y1 + 12y_2 \ge 12 $ $ y1,y2 \ge 0 $ I have got ...
MPP's user avatar
  • 75
0 votes
0 answers
56 views

Finding the second most optimal point using a modification of the simplex method

So I was playing around with the simplex method and basically I was interested in solving the problem "find the second most optimal vertex" for maximizing a given objective function, to be ...
Sidharth Ghoshal's user avatar
0 votes
0 answers
112 views

Why can surplus variables not be negative in Linear Programming?

For a bit of background, I was investigating non-standard form Simplex Method, where you have constraints containing $\ge$ symbols, for example $2x+3y \ge 14$. I understand that when rewriting such an ...
fahoom's user avatar
  • 1
0 votes
1 answer
63 views

Is there a way to find optimal solution of an LPP problem with an optimal solution for dual which is found using graphical method?

For the following LPP problem, $$ \text{Minimise} \quad 12x+8y+8z \\ \text{s.t} \quad 2x+2y+2z ≥ 1 \\ 3x+ y- z ≥ 1\\ \text{Where} \quad x, y, z ≥ 0 $$ I converted it to dual with variables $r$ & ...
Dvaavimshathihi's user avatar
0 votes
1 answer
58 views

How to approach a LP problem with Upper bounds

I need to solve the following problem: $$\max: x_1+12x_2+65x_3; $$ $$x_2+4x_3 \leq 200;$$ $$x_1+10x_2+60x_3 \leq 750; $$ $$x_1,x_2,x_3 \leq 50 $$ To solve it efficiently by hand, I have tried to make ...
Tiranex's user avatar
  • 11
1 vote
0 answers
81 views

Relationship between vertices in standard form and basic feasible solutions in canonical form LP

Please check if my thoughts is correct. Let we have the following linear programing problem $$max\, c^Tx$$ $$Ax\leq b,$$ $$x\geq 0,$$ where $A$ is a matrix with $m$ rows and $n$ columns, $x\in\mathbb{...
Иван Петров's user avatar
0 votes
0 answers
59 views

Do i have to add an auxiliary variable when adding a new equality constraint at a LP?

For example I have the following problem: \begin{align} &\textrm{min z} = -2x_1 -x_2 +x_3 \\ &\textrm{s.t.} \\ & \qquad x_1 +2x_2 +x_3 \leq 8 \\ & \\ &\quad -x_1 +x_2 -2x_3 \leq 4 ...
user1130062's user avatar
0 votes
0 answers
85 views

How does the Simplex method actually work?

I learned about the simplex method, how to pivot by hand before commercial grade solvers were introduced. And I’m still a little foggy on what slack variables and objectives are actually doing. My ...
jbuddy_13's user avatar
  • 229
3 votes
2 answers
299 views

Why can't we solve a LP problem just by finding all vertices of feasible region and testing the objective function at each vertex?

Why can't we solve a problem just by finding all vertices of the convex polytope of feasible solutions and testing the objective function at each vertex? My guess is basic solution of LP may not be ...
Jesse Jin's user avatar
  • 159
2 votes
1 answer
153 views

How do you solve minimization LP problem with dual method?

So i just started with the linear programming topic in my university. And while I was practicing, I found the next question: $$\min Z=3x_1+4x_2-x_3$$ $$\text{Subject to: }x_1+3x_2-x_3\ge1$$ $$2x_1+x_2+...
Maria M's user avatar
  • 21
1 vote
1 answer
209 views

Initialization of the Network Simplex Method

I am studying Chapter 7 (Network Flow Problems) of the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis. On page 286 the authors briefly describe a way to deal with the ...
Marlovo's user avatar
  • 689
1 vote
0 answers
40 views

How is the term for the change of the cost vector in the simplex method derived?

Given a minimilization problem of the form: $min \ c^t x$ ($c, x \ \in \mathbb{R}^n$) where the following constraints have to be met $Ax = b$ (A has dimensions mxn) $x \ge 0$ (in every entry) $rank(...
pana pana's user avatar
2 votes
1 answer
290 views

Is the Simplex Method an exact, approximate or a heuristic method?

I'd like to understand whether the simplex method is an exact method (like Branch&Bound, Branch&Cut...), an approximate method or a heuristic method.
tail's user avatar
  • 171
1 vote
2 answers
364 views

How to add a constraint to the final phase of simplex tableau?

How does one go about adding a new constraint in the final phase of the simplex tableau? In the case where our optimal solution satisfies the constraint, we can conclude that the optimal solution ...
shape's user avatar
  • 25
0 votes
1 answer
147 views

Linear programming Simplex method

f(x) = -2x1 + 3x2 -2x4 -4x5 + x6 -> max constraint: ...
Sunnyknight's user avatar
1 vote
2 answers
271 views

Adjacency of Optimal Basic Feasible Solutions in Linear Programming

I am studying linear optimization from the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis and came up with the following question: If a standard form problem $$ \begin{align} \...
Marlovo's user avatar
  • 689
2 votes
1 answer
48 views

Existence of pivots that strictly improves the objective value in presence of degeneracy

Consider a degenerate LP problem: $$\min c^Tx \\\text{subject to: }\qquad\qquad\qquad\qquad\qquad$$ $$Ax=1\quad a_{i,j} \in \{0,1\}$$ $$x\ge0$$ Is it safe to assume given an non-optimal initial basis $...
someone random's user avatar