Questions tagged [simplex-method]
Questions that relates to the "simplex algorithm", from the mathematical optimization field
26
questions
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\\...
