In the simplex algorithm in linear programming,

what are conditions for a variable to leave a basis (not necessarily basis for the/an optimal solution)?

I'm supposed to list as many sufficient and necessary conditions as possible for some basic variable \( x_q\) which could be slack, artificial or non-slack and non-artificial.


Let \( x_q\) be the s-th basic variable. Suppose the s-th row of some current simplex tableau has 1 in the column of \( x_q\) and 0's everywhere else. Under what circumstances, if any, might \( x_q\) leave the basis? Can any of the values in the s-th row of the tableau ever change?


Well since it's a basic variable, I'm guessing the $x_q$ column already has 0's everywhere except in the s-th row. Now, the $x_q$ row has 0's everywhere in the column of $x_q$ like:

enter image description here

This is in the context of the Big M Method and artificial variables. I'm not quite sure what the relationship is exactly, though.


What I tried:

\(x_q\) leaves if there is some non-basic variable \(x_r\) that enters because

  1. \(z_r - c_r < 0\)

  2. \(z_r - c_r = \min_j (z_j - c_j)\)

  3. $$\frac{b_q'}{a_{qr}'} = \min_i \{\frac{b_i'}{a_{ir}'} | a_{ir}' > 0 \}$$

Is that right? Any other sufficient or necessary conditions? What is the relevance of the 0's in the row?


Also, how do I approach the last question? I have no clue.

asked 07 May '16, 07:21

BCLC's gravatar image

BCLC
8311
accept rate: 0%

Be the first one to answer this question!
toggle preview

Follow this question

By Email:

Once you sign in you will be able to subscribe for any updates here

By RSS:

Answers

Answers and Comments

Markdown Basics

  • *italic* or _italic_
  • **bold** or __bold__
  • link:[text](http://url.com/ "Title")
  • image?![alt text](/path/img.jpg "Title")
  • numbered list: 1. Foo 2. Bar
  • to add a line break simply add two spaces to where you would like the new line to be.
  • basic HTML tags are also supported

Tags:

×231
×20
×7
×6
×4

Asked: 07 May '16, 07:21

Seen: 7,508 times

Last updated: 07 May '16, 07:21

OR-Exchange! Your site for questions, answers, and announcements about operations research.