So, among all are real values x1 until xn,

and we require that all should be greater or equal zero.

We want to find the maximal value of

a linear goal function and they should

satisfy k linear constraints expressed in a way like this.

Here the v, and s,

and c's and b's are given fixed real values and

the requirement here is that the b's are greater or equal zero.

That means, we always have a solution namely,

the axis all have value zero.

Then, it satisfies that all constraints.

So, choosing all values x to be zero,

we have a solution and this is called, the basic solution.

But probably, this is not the solution with the maximal value for the goal function.

So, now the approach of the simplex method is,

start from this solution,

in which all x is a value zero and then try to do steps by which

the value of the goal function increases and the steps are called pivots.

This applies to a more general format.

For instance, if the inequality is not less or equal but greater or

equal then we can simply multiply both sides by minus one.

Here we see in example.

If we have an equality rather than an inequality,

we can replace the equality by two inequalities A

is B is replaced by A less or equal B and B less or equal A.

If one wants to minimize rather than maximize,

just multiply the goal function by minus one.

If a variable x runs over all reals,

positive and negative, we are

required that all variables should be greater or equal zero.

Well, then such a variable x is replaced by x1 minus x2,

for fresh variables x1 and x2,

satisfying x1 and x2 greater or equal zero.

We get an extra variable,

but the tools can deal with it so we should not worry about it.

A less trivial issue is how to deal if there is

no trivial start solution as we had in our case where the b's are greater or equals zero.

That's less trivial and that we will consider later.

Now, we focus on the situation where all

b's are greater or equal zero and we have a trivial start solution.

The first step before we really apply

the simplex algorithm is that we bring it to slack form.

With slack form, dealing with equalities is easier than for inequalities.

So, for our inequality,

we introduce a fresh variable y_i greater or equal zero,

and we replace it by the following equality.

We just say, the part which is greater or equals zero is renamed to y_i,

and we have the requirement y_i greater or equals zero

and together with requirement y_i is greater or equal zero.

This is equivalent to the original inequality.

This format with equalities is called the slack form.

Let's give some terminology on a slack form with equations.

We say that the solution where the values of the

y's isn't b's and all x's have value zero,

that's called the basic solution.

Y variables, the variables left from

the equality sign are called the basic variables and the x variables,

right from the equality sign,

are called non-basic variables.

Now, the simplex algorithm consists of repetition of pivots in which

pivot chooses a basic variable and a non-basic variable and swaps their roles.

So the basic variable becomes non-basic and the other way around.

Then the result is brought to slack form

again and the slack form which is equivalent to the original one,

but with a higher value of the goal function.

The idea is we repeat this until a further increase

is not possible anymore and then we have found the optimal value.

How this works in detail,

we will see in an example in the next lecture. Thank you.