Questions tagged [simplex-method]

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

Filter by
Sorted by
Tagged with
2
votes
1answer
22 views

Determine basic feasible solutions in LP

Consider a linear programming problem \begin{align*} \min_x \; &c^Tx\\ \text{s.t. } & Ax \leq b. \end{align*} Assuming the constraints form a polyhedron, is there any way we can group the ...
2
votes
1answer
44 views

Find at least one solution of system of equations with constraints

Consider the system of equations with constraints $$ \begin{cases} x+y+z+t+u+v=3(a+b), \\ x+y+2(z+t)+3u=6b\\ 0 \leq x,y,z,t,u,v \leq 1, \end{cases} $$ here $0 \leq a,b \leq 1$ are fixed parameters....
0
votes
0answers
12 views

Simplex algorithm and extreme points

For this question my short-hand is LP = linear program, BFS = basic feasible solution, SEF = standard equality form. Since the Simplex algorithm iterates from extreme point to extreme point (...
4
votes
1answer
49 views

Why has the objective function changed from $M=x+y$ to $-M = -16 + 4x + 4y - S_3 - S_4$?

I am studying optimisation and have come across an example of a maximisation problem: maximise $$M=x+y$$ subject to $$x+3y \leq 32 \\ 2x+y \leq 24 \\x+3y \geq 6 \\ 3x+y \geq 10 \\ x,y \geq 0 $$ ...
1
vote
1answer
42 views

Struggling on how to go about performing the Simplex Method with mixed constraints

I am struggling to understand how to perform the Simplex Method when the constraints are not what is expected. For example, the problem min $-6x-4y+2z$ subject to $x + y + 4z \leq 20$ $-5y + 5z \leq ...
1
vote
1answer
32 views

How to proceed with the simplex tableau?

I'm relearning the simplex method and doing this minimization example with variables $y_1,y_2$, but got confused at the following simplex tableau step: $$\begin{array}{|c|c|c|c|c|c|c|} \hline BV &...
0
votes
0answers
79 views

Show that if n-m=2, then the simplex method will not cycle

this problem is from the book Bertsimas Triskis- Introduction to linear optimization. Exercise 3.10. Let $P=\{x\in \mathbb{R}^{n}|Ax=b, x\geq 0\}$ a non-empty polyhedron in standard form. Assume that $...
0
votes
0answers
20 views

Alternative Optimal Solution Using Simplex Algorithm

So first I re-wrote the question in standard form: $Max\ z = x_1 + x_2 $ s.t. $x_1 + x_2 + x_3 + s_1 = 1 $ $x_1 + 2x_3 + s_2 = 1 $ $ all \ x_i \ and \ s_i \geq 0 $ So first I created rows: ...
0
votes
0answers
37 views

How to prove a solution not optimal using duality?

I have been given an LPP problem and asked to prove the basic solution (x1, x2) is not optimal. But every time I am solving it using simplex and the duality method the objective function keeps coming ...
1
vote
1answer
84 views

Why do we have to add slack variables and artificial variables in Simplex method at Linear programming?

I learn why we have to use these variable in lectures. Slack variable : Make linear inequalities to linear equalities Artificial variable : Know whether the basic feasible solution exist or not But ...
1
vote
1answer
57 views

Finding Linear programming optimal solution.

Consider the following linear program: max $z = 4x_1+x_2+5x_3+3x_4$ subject to $x_1-x_2-x_3+3x_4 \le 1$ $5x_1+x_2+3x_3+8x_4\le55$ $-x_1+2x_2+3x_3-5x_4\le3$ It is claimed that the solution $x^*=(0,...
0
votes
0answers
7 views

How do I reduce the number of iterations for a Nelder-Mead downhill simplex?

I have written some C code for a downhill simplex algorithm using the Nelder-Mead method to find the minimum of a function. Currently it finds the minimum in $80$ iterations, but I believe it may be ...
0
votes
0answers
29 views

Trying to learn Simplex Method

I'm trying to learn the simplex method. It is very unclear to me, how to do it, as every textbook and video I look at explains it entirely different. I was looking at the tableau method, but how would ...
0
votes
0answers
8 views

Identifying lower and higher bound for $c_1$ and $c_2$ without changing solvability of BigM

Find $\max Z = 8x_1 + 6x_2$ subject to $x_1 + x_2 \le 80$, $2x_1 + x_2 \le 140$, $x_1 + 4x_2 \le 100$, and $x_1,x_2 \le 0$. Even though I searched around, I couldn't find anything about this ...
0
votes
0answers
86 views

Is the standard Simplex Method scale-invariant?

I am not able to find whether a method is scale invariant or not. In the book Linear Programming 1 by M. Thapa and B. Dantzig, scale invariance is defined as : "A pivoting method is scale-...
0
votes
1answer
87 views

Solving Quadratic Programming Problem using Linear Programming Solver

I have a qudratic programming problem $$J_{min} : \frac {1}{2}x^TQx + c^Tx \\ S.T \\ Ax \leq b \\ x \geq 0$$ But I have only a solver for linear programming using simplex method. $$J_{max} : c^Tx \...
1
vote
0answers
23 views

How to implement ratio test if all entries in the pivot column are negative?

I am trying to find the adjacent bfs for the following tableau. So far I understand that it has an alternative solution because there is $x_4$ a nonbasic decision variable that has a 0 coefficient in ...
0
votes
0answers
28 views

Entering and exiting variables' relation to the value of the objective function in the Simplex method

Consider a maximisation LP problem. In the Simplex method, one of the rules for choosing which non-basic variable enters the new basis is too look at which one of the non-basic variables will give the ...
2
votes
0answers
37 views

Theta-Ratio of a Simplex Method for a degenerate solution, are they always equal?

Are the $\theta$-ratios of two degenerate solutions always equal? So as to say: If we know two unique points yield the same objective value, must their $\theta$-ratios always be equal? For two ...
0
votes
0answers
13 views

what pivot should I choose when introducing new constraint trying to apply the Dual Simplex Method and all $b_i$ are positive?

There is an LP. It is already given that $x_1 = 0, x_2 = 1$ is the optimal solution. First I find the corresponding simplex tableaux. Then what I don't get is how to apply the dual simplex method when ...
3
votes
1answer
131 views

Show that if Phase I of the two-phase method ends with an optimal cost of zero then the reduced cost vector will always take the form $(0, 1)$

Consider a linear programming problem of the form: minimize $c^Tx$ subject to: $Ax=b$, $x\geq0$ where $A$ is an $m\times n$ matrix with linearly independent rows. Show that if Phase I of the two-...
0
votes
0answers
25 views

LPP: Simplex Method - Interpreting Solutions

Having trouble keep all the cases straight in my head for the Simplex method in Linear programming problems. What does it mean for a Simplex table solution to be feasible but not optimal? Both ...
1
vote
1answer
249 views

Why would you choose Simplex over Lagrange/KKT multipliers methods?

I was revising my notes from an optimization class I did a few years ago. After reading a bit, I started questioning myself about the benefit of using Simplex over other optimization methods. The ...
1
vote
0answers
64 views

Big “M” Method and Dual Simplex give me the different answer.

Please help, I have an exam in 2 hours.... And it has 1 iteration only... I have this problem : Maximize : $Z=2x_1+x_2$ Constraints : $$\begin{aligned} 10x_1+10x_2&\leq 9\\ 10x_1+...
1
vote
1answer
74 views

Simplex Method - Why is my answer wrong?

I know that the bottom row can't have any zeros and I didn't. Yet I still got this wrong? Is it because my RHS column has a negative?
2
votes
2answers
311 views

Simplex Method gives multiple, unbounded solutions but Graphical Method gives unique soution

I'm taking an undergraduate course on Linear Programming and we were asked to solve the following problem using the Simplex Method:$$\max:~Z=3x+2y\\\text{subject to}\begin{cases}x+y\le20\\0\le x\le15\\...