Questions tagged [simplex-method]

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

Filter by
Sorted by
Tagged with
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 ...
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{...
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 & ...
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(...
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^...
user avatar
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 ...
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 - ...
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 ...
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): ...
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 $...
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 ...
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 ...
user avatar
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 ...
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 ...
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 ...
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,...