Questions tagged [simplex-method]
Questions that relates to the "simplex algorithm", from the mathematical optimization field
125
questions
2
votes
1
answer
27
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 ...
0
votes
0
answers
19
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 ...
- 73
0
votes
0
answers
33
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 ...
- 15.3k
0
votes
0
answers
24
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 ...
- 1
0
votes
0
answers
46
views
Alternate optima in linear programming
Does the existence of alternate optima indicate that the objective function is parallel to a non-redundant binding constraint at the optima?
Suppose I have the following linear program
$$ \begin{array}...
- 2,623
0
votes
0
answers
38
views
Finding adjacent vertices on a convex polytope, searching among basis exchanges?
My question is about how, in general, to go from one vertex of a convex polytope to an adjacent one. But also I have more conceptual questions about how the simplex method works.
Say I have a linear ...
-1
votes
1
answer
35
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$ & ...
0
votes
1
answer
41
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 ...
- 11
1
vote
0
answers
25
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{...
- 69
0
votes
0
answers
39
views
Simplex Algorithms: Identifying simplex method for a question.
I am just getting started with the basics of simplex algorithms so I don't know much about them except the calculations (and that's all I am focusing on for now). I have studied Big M, 2 Phase, Dual ...
0
votes
0
answers
33
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 ...
0
votes
0
answers
50
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 ...
- 203
3
votes
2
answers
140
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 ...
- 167
0
votes
0
answers
49
views
Optimal strategy for first player in a matrix game with one parameter
I am having trouble with the following problem:
We are given a family of matrix games which is given with the following matrix:
$$\begin{bmatrix}
2 & -1 & 0 & 4\\
-1 & a & 2 & ...
- 515
2
votes
1
answer
74
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+...
- 21
0
votes
0
answers
54
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 ...
- 455
1
vote
0
answers
34
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(...
- 11
2
votes
1
answer
82
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.
- 123
1
vote
2
answers
106
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 ...
- 25
0
votes
1
answer
60
views
Linear programming Simplex method
f(x) = -2x1 + 3x2 -2x4 -4x5 + x6 -> max
constraint:
...
1
vote
0
answers
67
views
What are the Areas of Research that Focuses on Improving the Simplex/Interior-Point Methods?
In lecture recently, it was explained to me that modern areas of research that involve improving the Simplex Method focus on these key points:
Improving the amount of computations needed to update $B^...
user1098096
0
votes
1
answer
95
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}
\...
- 455
2
votes
1
answer
42
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 $...
1
vote
1
answer
449
views
Both primal and dual are infeasible/unbounded
With regards to linear optimization using the simplex method, can someone provide an example:
where both the primal and dual of problem A are infeasible
where both the primal and dual of problem B ...
- 300
0
votes
1
answer
29
views
Questions about some of the simplex method properties
In the 5th page of this book: Principles of Autonomy and Decision Making, I found that these properties are somewhat confusing.
Most often, the optimal point is located at a vertex (corner) of the
...
- 25
0
votes
1
answer
73
views
Existence of multiple optimal solutions in Linear Programming simplex method
Let us suppose the final iteration of the simplex tableau indicates nondegeneracy (no basic variable is at zero level) and the reduced cost of one of the non-basic variables is zero. Are we always ...
- 67
0
votes
1
answer
53
views
First few steps of simplex table for minimization
I saw this simple problem and realized I dont know how the simplex method solves this one in particular -
...
- 300
0
votes
1
answer
122
views
A Cycle of Simplex Method Has At Least Six Iterations
I am studying the cycling of simplex method. In a 1969 paper A Note on Cycling in the Simplex Method by Marshall and Suurballe, the authors mentioned at the beginning of Section 6, page 136 that
...
- 455
0
votes
1
answer
81
views
Construction of Small Cycling Examples in Simplex Method
This is Exercise 3.11 from Introduction to Linear Optimization by Bertsimas and Tsitsiklis.
Exercise 3.11 Construct an example with $n-m=3$ and a pivoting rule under which the simplex method will ...
- 455
1
vote
1
answer
84
views
Simplex method - the purpose of $cx$ or $-cx$ in the table
The following example comes from "Introduction to Linear Optimization" book by Dimitris Bertsimas and John N. Tsitsiklis:
Example $3.5$ Consider the problem
$$\min-10x_1-12x_2-12x_3$$
...
- 528
1
vote
1
answer
87
views
Proof of Strong Duality via Simplex Method
I am study the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis. The proof of strong duality (Theorem 4.4)
Theorem 4.4 (Strong duality) If a linear programming problem has an ...
- 455
1
vote
1
answer
89
views
Connection Between Two Lexicographic Rules in Simplex Method
In my study of the simplex method, I have come across two formulations of the lexicographic pivoting rule. Currently I am having trouble understanding how they are connected to each other.
In Section ...
- 455
1
vote
1
answer
353
views
Nonzero Reduced Cost in Linear Programming Optimal Solution Implies Uniqueness of Optimum?
My questions comes from Exercise 3.9 of the book Introduction to Linear Optimization by Bertsimas and Tsitsiklis, which is about a charaterization of unique optimum.
Exercise 3.9 Consider a linear ...
- 455
1
vote
1
answer
48
views
Alternate Optimal Solution
Is there a linear optimization problem where there is an alternate optimal solution(i.e $z_j-c_j=0$) but all the $y_{ij}$ in the simplex table is negative, i.e $y_{ij}<0$?
In the linear problem of ...
- 123
0
votes
1
answer
141
views
Simplex method: a degenerate case with 0 ratio
Consider the problem
max x
s.t.
x <= 5
-x <= 0
The tableau with the first 2 iterations that continues to cycle infinitely (tableau 1 = 3):
...
- 233
1
vote
1
answer
17
views
Reconfiguration to find other solutions of a Binary Linear Program (NOT ILP)
Assuming we are to optimize 0-1 problem. If we've found the first solutions where multiple solutions might exists. How do we reconfigure the system (maybe through unimodular operations) inorder to ...
1
vote
0
answers
49
views
Linear Algebra > Pablos Problem via Simplex Method
In Pablos problem via Simplex method :
The Conundrum City school board is heavily influenced by the local fruit grower's association. They have stipulated that children eat at least $7$ oranges and $...
- 21
1
vote
1
answer
67
views
Start of solving a minimization linear program using the Simplex method
I am trying to understand and put in application the Simplex method to solve the following LP:
$$ Minimize \qquad c^Tx$$
$$ S.t.: \qquad Ax = b$$
where $A$ is a set of $n$ random 6-dimensional vectors ...
- 21
0
votes
1
answer
172
views
Question regarding pseudocode of the Simplex algorithm
In class I learned the following pseudocode for the simplex algorithm:
However, what is unclear to me about this procedute is the "solve" command in lines 3 and 8. When solving $A_B^Ty = c_B$...
- 3,564
0
votes
1
answer
66
views
Why the terminology “pricing” in the Simplex algorithm?
In the Simplex algorithm, the task of finding a variable with negative reduced cost is often referred to as “pricing”. What is the origin of/intuition behind this terminology?
- 320
2
votes
1
answer
197
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 ...
user999236
0
votes
1
answer
223
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 ...
- 729
1
vote
1
answer
138
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,652
0
votes
1
answer
32
views
Minimize Objective Function
Formulation
Min $z$
subject to constraints
$z \ge x_1+x_2+x_3+x_4-4$
$z \ge x_5+x_6+x_7+x_8-60$
$z \ge x_9+x_{10}+x_{11}+x_{12}$
$x_1+x_5+x_9 \ge 450$
$x_2+x_6+x_{10} \ge 200$
$x_3+x_7+x_{11} \ge ...
2
votes
0
answers
51
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
57
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
1
vote
1
answer
58
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$?
Afterwards, since all my reduced ...
- 11
0
votes
1
answer
98
views
Pivoting: Simplex Algorithm choosing a pivot column for the second time
I found online a set of notes from a university.
I am studying an example of the Simplex algorithm and I am somewhat confused:
We defined the pivot column to be the leftmost column with a negative ...
- 729
1
vote
1
answer
387
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
68
views
Calculating Missing Data Points from the Simplex Tableau
I have a few MCQ questions regarding the tableau Simplex Method. I am having a hard time wrapping my head around the examples with missing data points. Below are some of the examples that I find weird,...
- 259