2
$\begingroup$

I need help understanding the question.

Consider the polyhedron P = {x in R^n | Ax = b x => 0}, where A in R^mxn and b in R^m. Assume that any m columns of A are linearly independent.

(a) Suppose all the basic solutions are nondegenerate. Express the number of basic solutions in terms of m choose n

(b) Suppose that k basic solutions are degenerate, and each of these degenerate solutions have n+1 active constraints. Furthermore, all other basic solutions are nondegenerate. How many basic solutions are there?

(c) Suppose that there is one basic solution that is degenerate, and has n + 2 active constraints. Furthermore, all other basic solutions are nondegenerate. How many basic solutions are there?

for (a), I'm not sure if it is 2m choose n since there are 2m constraints and we need to ensure that there are n constraints to be tight.

Hope someone can enlighten me!

Thanks!

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Browse other questions tagged or ask your own question.