1. Consider an LP with n decision variables and linearly independent constraints. Suppose a dictionary of this LP has k basic variables that are equal to zero. Show that the number of dictionaries that have the same basic feasible solution as this one is (kn+k?)?1???????Justify your answer.

Perhaps this is a similar question

In Rⁿ, degeneracy occurs when more than n linearly independent hyperplanes intersect at a single point. In that case, there are multiple dictionaries that share the same basic solution. Find the number of degenerate dictionaries at a degenerate vertex that is the intersection of n+k linearly independent hyperplanes. Justify your answer.

The answer to this question is

The uniqueness of a dictionary is defined by which variables are basic and which are non-basic. At this degenerate vertex, there are n+k variables that are equal to 0, but a dictionary only has n non-basic variables (which are thus equal to 0). So the number of possible dictionaries at that vertex is the choice of n variables as non-basic, among a total of n+k variables, which is(nn+k?)=n!k!(n+k)!?

Please answer the question at the top.

this note may help

THEOREM 3.1. If the simplex method fails to terminate, then it must cycle. PROOF. A dictionary is completely determined by specifying which variables are basic and which are nonbasic. There are only n | m _ (n + m)! different possibilities. This number is big, but it is nite. If the simplex method fails to terminate, it must visit some of these dictionaries more than once. Hence, the algo- rithm cycles. CI Note that, if the simplex method cycles, then all the pivots within the cycle must be degenerate. This is easy to see, since the objective function value never decreases. Hence, it follows that all the pivots within the cycle must have the same objective function value, i.e., all of the these pivots must be degenerate. In practice, degeneracy is common because a zero right-hand side value crops up frequently in real-world problems. Cycling is not as common, but it can happen and therefore must be addressed. Computer implementations of the simplex method in which numbers are represented as integers or as simple rational numbers are at risk of cycling and one of the techniques described in the following sections must be used to avoid the problem. But, most implementations of the simplex method are written with oating point numbers (the computer approximation to a full set of real numbers). With oating point computation there is inevitable round-off error. Hence, a zero ap- pearing as a righthand side value generally shows up not as an exact zero but rather as a very small number. The result is that the dictionary appears to be slightly off from actually being degenerate and therefore cycling is usually avoided