Dtjytyk

Who can trigger ship-wide alerts in Star Trek?

Biased dice probability question

What's the point in a preamp?

Determine whether f is a function, an injection, a surjection

What can I do if my MacBook isn’t charging but already ran out?

How many things? AとBがふたつ

Simulating Exploding Dice

Why use gamma over alpha radiation?

Can smartphones with the same camera sensor have different image quality?

How does modal jazz use chord progressions?

I'm having difficulty getting my players to do stuff in a sandbox campaign

Passing functions in C++

New Order #5: where Fibonacci and Beatty meet at Wythoff

Classification of bundles, Postnikov towers, obstruction theory, local coefficients

Choo-choo! Word trains

Is there a service that would inform me whenever a new direct route is scheduled from a given airport?

Is it possible to ask for a hotel room without minibar/extra services?

Autumning in love

When communicating altitude with a '9' in it, should it be pronounced "nine hundred" or "niner hundred"?

Jazz greats knew nothing of modes. Why are they used to improvise on standards?

Estimate capacitor parameters

Can a monk deflect thrown melee weapons?

Area of a 2D convex hull

Why is "Captain Marvel" translated as male in Portugal?

Proof verification for simplex method problems

0

$begingroup$

I was studying simplex method in LPP from "Introduction to Linear Optimization by Bertsimas and Tsitsiklis", and came across this problem:

Consider the simplex method applied to a standard form problem and
assume that the rows of the matrix $A$ are linearly independent . For
each of the statements that follow, give either a proof or a
counterexample. Take $ngeq m$, where $A$ is $m*n$ and $b$ is $m*1$ matrix.

(a) An iteration of the simplex method may move the
feasible solution by a positive distance while leaving the cost
unchanged.

(b) If there is a
nondegenerate optimal basis , then there exists a unique optimal
basis.

(c) If $x$ is an optimal solution, no more than $m$ of its
components can be positive.

I tried this question, and was able to solve some of them. But, I'm not sure if my solutions are correct. It'd be really helpful if someone could tell if I solved these correctly and tell the solutions/hints for the unsolved ones.

My try:

I considered a tableau while solving all of these problems.

a) False. Let $c$ and $bar{c}$ be the initial and final costs. When we update the tableau, we'll apply row transformation to go from $c$ to $bar{c}$. But since $c=bar{c}$, for the cost to remain the same after an iteration, the basic variable that is exiting the basis has to be zero. Let $k$ be the index of the variable entering the basis and $B(l)$ be that of leaving the basis. When we move from $x_{B(l)}$ to $x_k$, whatever we multiply by, $x_{B(l)} (=x_k)$ will remain the same ($0$). So, we are still at the same point.

b) I was unable to understand it clearly. What does "basis" mean? The basis matrix $B$ or the vector of basic variables $x_B$? I've no idea on how to proceed in any of those two way either.

c) This is true since $x$ being an optimal solution is a bfs.

Please note that I don't even need full solutions, even hints will do. Thanks!

proof-verification optimization linear-programming two-phase-simplex

share|cite|improve this question

edited Mar 24 at 12:36

Ankit Kumar

asked Mar 23 at 12:41

Ankit KumarAnkit Kumar

1,542221

$endgroup$

add a comment | 

0

$begingroup$

I was studying simplex method in LPP from "Introduction to Linear Optimization by Bertsimas and Tsitsiklis", and came across this problem:

Consider the simplex method applied to a standard form problem and
assume that the rows of the matrix $A$ are linearly independent . For
each of the statements that follow, give either a proof or a
counterexample. Take $ngeq m$, where $A$ is $m*n$ and $b$ is $m*1$ matrix.

(a) An iteration of the simplex method may move the
feasible solution by a positive distance while leaving the cost
unchanged.

(b) If there is a
nondegenerate optimal basis , then there exists a unique optimal
basis.

(c) If $x$ is an optimal solution, no more than $m$ of its
components can be positive.

I tried this question, and was able to solve some of them. But, I'm not sure if my solutions are correct. It'd be really helpful if someone could tell if I solved these correctly and tell the solutions/hints for the unsolved ones.

My try:

I considered a tableau while solving all of these problems.

a) False. Let $c$ and $bar{c}$ be the initial and final costs. When we update the tableau, we'll apply row transformation to go from $c$ to $bar{c}$. But since $c=bar{c}$, for the cost to remain the same after an iteration, the basic variable that is exiting the basis has to be zero. Let $k$ be the index of the variable entering the basis and $B(l)$ be that of leaving the basis. When we move from $x_{B(l)}$ to $x_k$, whatever we multiply by, $x_{B(l)} (=x_k)$ will remain the same ($0$). So, we are still at the same point.

b) I was unable to understand it clearly. What does "basis" mean? The basis matrix $B$ or the vector of basic variables $x_B$? I've no idea on how to proceed in any of those two way either.

c) This is true since $x$ being an optimal solution is a bfs.

Please note that I don't even need full solutions, even hints will do. Thanks!

proof-verification optimization linear-programming two-phase-simplex

share|cite|improve this question

edited Mar 24 at 12:36

Ankit Kumar

asked Mar 23 at 12:41

Ankit KumarAnkit Kumar

1,542221

$endgroup$

add a comment | 

$begingroup$

I was studying simplex method in LPP from "Introduction to Linear Optimization by Bertsimas and Tsitsiklis", and came across this problem:

Consider the simplex method applied to a standard form problem and
assume that the rows of the matrix $A$ are linearly independent . For
each of the statements that follow, give either a proof or a
counterexample. Take $ngeq m$, where $A$ is $m*n$ and $b$ is $m*1$ matrix.

(a) An iteration of the simplex method may move the
feasible solution by a positive distance while leaving the cost
unchanged.

(b) If there is a
nondegenerate optimal basis , then there exists a unique optimal
basis.

(c) If $x$ is an optimal solution, no more than $m$ of its
components can be positive.

I tried this question, and was able to solve some of them. But, I'm not sure if my solutions are correct. It'd be really helpful if someone could tell if I solved these correctly and tell the solutions/hints for the unsolved ones.

My try:

I considered a tableau while solving all of these problems.

a) False. Let $c$ and $bar{c}$ be the initial and final costs. When we update the tableau, we'll apply row transformation to go from $c$ to $bar{c}$. But since $c=bar{c}$, for the cost to remain the same after an iteration, the basic variable that is exiting the basis has to be zero. Let $k$ be the index of the variable entering the basis and $B(l)$ be that of leaving the basis. When we move from $x_{B(l)}$ to $x_k$, whatever we multiply by, $x_{B(l)} (=x_k)$ will remain the same ($0$). So, we are still at the same point.

b) I was unable to understand it clearly. What does "basis" mean? The basis matrix $B$ or the vector of basic variables $x_B$? I've no idea on how to proceed in any of those two way either.

c) This is true since $x$ being an optimal solution is a bfs.

Please note that I don't even need full solutions, even hints will do. Thanks!

proof-verification optimization linear-programming two-phase-simplex

share|cite|improve this question

edited Mar 24 at 12:36

Ankit Kumar

asked Mar 23 at 12:41

Ankit KumarAnkit Kumar

1,542221

$endgroup$

share|cite|improve this question

edited Mar 24 at 12:36

Ankit Kumar

asked Mar 23 at 12:41

Ankit KumarAnkit Kumar

1,542221

share|cite|improve this question

edited Mar 24 at 12:36

Ankit Kumar

asked Mar 23 at 12:41

Ankit KumarAnkit Kumar

1,542221

asked Mar 23 at 12:41

Ankit KumarAnkit Kumar

1,542221

asked Mar 23 at 12:41

Ankit KumarAnkit Kumar

1,542221