Back to the on-screen lesson ·
A corner written as a choice of columns: basic variables, the zeros that pin the point, and the sign test.
Paper packet. Every task here also exists on screen, where it is checked automatically; answers written on paper are not assessed by Nydus. When you are back at a device, enter your answers there.
By the end of this lesson you will be able to form the basic solution belonging to a chosen basis by zeroing the non-basic variables and solving the square system, write the basis matrix of a named basis, decide whether a basic solution is feasible from the signs of its values, and say why basic feasible solutions and corners of the feasible region are the same points.
You can put a program into standard form, and you know from unit 2 that an optimum sits at a corner. This lesson gives the corner an algebraic description, so that an algorithm can hold one without drawing anything.
A basis is a set of $m$ columns of the constraint matrix whose square matrix is invertible. The variables of those columns are basic; every other variable is non-basic and set to zero. Solving the remaining square system gives the basic solution, and it is a basic feasible solution when every value comes out non-negative.
In standard form there are $m$ equations and $n > m$ variables, so the system is underdetermined and its solutions form a space. To pick a single point out of it, choose $m$ columns whose matrix $B$ is invertible, set the other $n - m$ variables to zero, and solve $Bx_B = b$. The result is a basic solution, and it is determined entirely by which columns were chosen.
Each variable set to zero is one constraint held with equality — a decision variable at zero means an axis, a slack at zero means its constraint is binding. Holding $n - m$ of them at once is what pins the point to a corner. Basic feasible solutions and corners of the feasible region are the same thing, seen algebraically and geometrically, and that identity is what lets an algorithm search a shape.
Basic does not imply feasible. The algebra will happily return a negative value, and that is a crossing of boundary lines outside the region.
Another way: steps
Another way: example
$2x_1 + 5x_2 + s_1 = 100$, $3x_1 + 2x_2 + s_2 = 60$. The basis $\{s_1, s_2\}$ gives $x = 0$, $s_1 = 100$, $s_2 = 60$: the origin, feasible, and free of any work at all — which is why the slacks are where the method starts.
Basic and feasible are run together, so a negative basic value looks like an arithmetic error rather than a point outside the region. The second habit is thinking a basis is a set of values; it is a set of columns, and the values follow from it with no freedom at all.
$x + y \le 6$, $x, y \ge 0$, standard form $x + y + s = 6$. Take the basis $\{x\}$.
One equation, one basic variable.
Then $y = 0$ and $s = 0$, so $x = 6$: the basic solution $(6, 0, 0)$.
Algebra.
$y = 0$ is the $x$ axis and $s = 0$ is the line $x + y = 6$. The point is where they cross — the corner $(6, 0)$.
Geometry, same point.
No. A basic solution sets every non-basic variable to zero, and $x$ is non-basic here, so $x$ must be $0$.
The zeros are not optional.
The basis $\{y\}$ gives $x = 0$, $s = 0$ and $y = 6$.
In standard form the program is $x + y + s = 11$ with $x, y, s \ge 0$: one equation, three variables. Fill in the basic solution for each choice of basic variable.
| $x$ | $y$ | $s$ | |
|---|---|---|---|
| Basic variable $x$ | |||
| Basic variable $y$ | |||
| Basic variable $s$ |
The program $x + y \le 13$, $x, y \ge 0$ has standard form $x + y + s = 13$. Plot its basic feasible solutions in the $x$-$y$ plane.
Plot your answer on the grid:
Standard form gives $2x + 2y + s_1 = k$ and $7x + 7y + s_2 = m$. Write the basis matrix for the basis $\{x, s_2\}$, in that order.
This task has no paper form; do it on a device.
A choice of basis solves the equations and gives the basic variable in the second row the value $-2$. What is that solution?
A standard-form program has $5$ equations and $7$ variables. Complete the description of one of its basic solutions.
A basic solution sets z variables to zero and solves for the remaining b.
A standard-form program has $2$ equations and $9$ variables. At most how many bases does it have?
Answer:
Lesson test: one question per skill, one attempt each, no hints. Your answers are checked when you submit.
In standard form the program is $x + y + s = 11$ with $x, y, s \ge 0$: one equation, three variables. Fill in the basic solution for each choice of basic variable.
| $x$ | $y$ | $s$ | |
|---|---|---|---|
| Basic variable $x$ | |||
| Basic variable $y$ | |||
| Basic variable $s$ |
You can form a basic solution from a basis and decide whether it is feasible. Say in your own words why a variable set to zero corresponds to a constraint held with equality.
7. Your turn: in $x + y + s = 6$, is the basis $\{y\}$ with $x = 8$ a basic solution?, step 2