CHAPTER 3: LINEAR PROGRAMMING: ALGEBRAIC SOLUTION

Lesson Objectives – The student should understand the following:

• The basic rules for implementing the simplex algorithm.
• How to find an initial basic feasible solution for a linear program.
• Differentiate between feasible and non-feasible solution, optimal and non optimal solution.

3.1 Simplex Method

As discussed earlier, graphical solution procedures are applicable only for linear Programming
problems involving two variables. Since most realistic applications of linear programming
involve for more than two variables, there is a need for a solution procedure other than the
graphical method. The most popular non -graphical procedure is called the simplest method .The
simplest method is an algebraic procedure for solving systems of equations where an objective
function is to be optimized .It is an iterative process, which identifies a feasible starting solution.
Iterative process because a specified set of solution steps are repeated until a conclusion is
reached regarding the solution of the problem. The procedure then searches to see whether there
exists a better solution. "Better" is measured by whether the value of the objective function can
be improved. If a better solution is signaled, the search resumes .The generation of each
successive solution requires solving a system of linear equations. The search continues until no
further improvement is possible in the objective function.

3.2 Requirements of the simplex method

In all of the graphical model solutions we have looked at so far we can see that the optimal
solution to an LP is located at an extreme (or corner) point of the solution space. This
observation is the foundation of the general algebraic solution algorithm for LPs. This algorithm
is called the Simplex Method. In order to facilitate the algebraic identification of the extreme
points in a solution space we will need to write our LP models in a standard form.
The standard form for LPs requires that all constraints be stated as equations. To convert
inequality constraints to equations we will introduce slack and/or surplus variables in our starting
solution. We are interested in obtaining a basic solution for an LP. A basic solution is a feasible
solution located at one of the extreme points. The Simplex algorithm will identify the optimal
solution from among the basic solutions

3.3 The Standard form of the LP

This section provides the first step of solving the LP model, which is the conversion of the model
to the so-called “standard form”. In formulation of the LP model one may have much variety in
the form of the model.
For example, the objective function could be maximized or minimized, and the constraints could
be equalities or inequalities of either type. In this module we show how to change the general
structure into the special form called “standard form” required for solution by the simplex
method.

1
In standard form:
There are some requirements for solving linear programming problem by the simplex method .
• The objective function is of the maximization or minimization type. Minimization of a
function is equivalent to the maximization of the negative expression of this function.
• All constraints must be stated/expressed as equations accept the non-negativity
constraints.
• The right hand sides of the constraints are non-negative.
• All decision variables are restricted to non-negative values.

To convert a minimization problem to maximization problem, simply multiply the function to be

minimized by − 1 and maximize this function.

We show how to make all constraints equalities. In order to do this the inequality constraints of
both “types” must be converted to equalities.
The inequality constraints are changed to equality constraints by adding or subtracting a non-
negative variable from the left – hand side of such constraints.
For Type I ( ≤ ) inequalities
In ( ≤ ) constraints, the right-hand side can be thought of as representing the limit on the
availability of a resource, in which case the left-hand side would represent the usage of this
limited resource by the activities (variables) of the model.
For each "less than or equal to "( ≤ ) constraint a non-negative variable, called a slack variable
is added to the left side of the constraint. This variable serves the function by balancing the two
sides of the equation .It represents unused amount of the resource.

Example 1:
A manufacturing firm produces two products A and B. Each of these products must be processed
through two different machines. One machine has 24 hours of available capacity, and the second
machine has 16 hours of available capacity. Each unit of product A requires 2 hours of time on
both machines. Each unit of B requires 3 hours on the first machine and 1 hour on the second
machine. The incremental profit is $6 per unit of product A and $7 per unit of product B, and the
firm can sell as many units of each product as it can manufacture. Determine how many units of
product A and B should be produced within the limits of available machine capacities.
The final formulation of the model
Maximixe: Z = 6x 1 +7x 2
Subject to : 2x 1 +3x 2 ≤ 24 (available hour capacity for machine 1)
2x 1 +x 2 ≤ 16 (available hour capacity for machine 2)
x1 , x 2 ≥ 0

Consider the two constraints for product mix model

2x 1 +3x 2 ≤ 24 (available hour capacity for machine 1)
2x 1 +x 2 ≤ 16 (available hour capacity for machine 2)
Where x 1 , x 2 represent the number of units produced and sold of product A and B respectively.
The two constraints represent limited hour availability for the two machines. The right hand
sides of the constraints represent the number of hours available for each machine per day .

2
The treatment of these constraints is to add a slack variable to the left side of each i.e
2x 1 +3x 2 + S 1 = 24 (machine 1)
2x 1 + x 2 + S 2 =16 (machine 2)
The slack variables S 1 and S 2 represent the number of unused hrs for each machine
For Example: if x 1 = 6 and x 2 =2, suggests, we produce 6 units of product A and 2 units of
product B. If we substitute these values in the constraints, we have

2x 1 +3x 2 + S 1 = 24 (machine 1)
(2*6)+(3*2)+ S 1 = 24
12 + 6 + S 1 = 24
S1 = 6 (machine 1)

2x 1 + x 2 + s 2 =16 (machine 2)
(2*6)+ (1*2)+ s 2 =16
12 + 2 + S 2 = 16
S2 = 2 (machine 2)

18 hrs would be used for production in machine 1 and14hrs in machine 2 .The slack variables
would assume values of
s 1 = 6hrs and s 2 = 2hrs to balance the equations.
The interpretation of these values is that producing 6 units of product A and 2 units of Product
B will result in 6 hrs being left over (unutilized) in machine 1 and 2hrs in machine 2 unutilized .

Exercise
Suppose x 1 = 3 and x 2 = 4. What values must s 1 and s 2 assume ? Discuss the interpretation of
this result

Example 2
A firm manufactures two products, each of which must be processed through departments X and
Y. The table below summarizes labor- hour requirements per unit for each product in each
department. Also presented are weekly labor- hour capacities in each department and respective
profit margins for the two products. The problem is to determine the number of units to produce
of each product so as to maximize total contribution to fixed cost and profit.

3
 Product A Product B Weekly labor
capacity
Department X 3hr per unit 2hr per unit 120 hours
Department Y 4hr per unit 6hr per unit 260 hours
Profit margin $5 $6

Final formulation
Maximixe: Z = 5x 1 +6x 2
Subject to : 3x 1 +2x 2 ≤ 120
4x 1 +6x 2 ≤ 260
x1 , x 2 ≥ 0

Consider the two constraints for product mix model

3x 1 +2x 2 ≤ 120 (Dept A)
4x 1 +6x 2 ≤ 260 (Dept B)
Where x 1 , x 2 represent the number of units produced and sold of product 1and2 respectively .
The two constraints represent limited labor availability in the two departments. The right hand
sides of the constraints represent the number of hrs available in each department per week .
The treatment of these constraints is to add a slack variable to the left side of each i.e
3 x 1 +2 x 2 + S 1 =120 (Dept A)
4 x 1 +6 x 2 + S 2 =260 (Dept B)
The slack variables s 1 and s 2 represent the number of unused hrs in each dept
For Example: if x 1 =10 and x 2 =30 suggest producing 10 units of product 1 and 30 units of
product 2. If we substitute these values in the constraints , we have
3(10)+2(30)+ S 1 =120
90+ s 1 =120
s 1 =30 (Dept A)

4(10)+6(30)+ S 2 =260
220+ s 2 =260
s 2 = 40 (Dept B)
90 hrs would be used for production in department A and 220 in department B .The slack
variables would assume values of
s 1 =30 and s 2 = 40 to balance the equations.
The interpretation of these values is that producing 10 units of product 1 and 30 units of 2 will
result in 30 hrs being left over in department A and 40 hrs being left over in department B .

Exercise
Suppose x 1 =30 and x 2 =15 .What values must s 1 and s 2 assume ? Discuss the interpretation
of this result.

4
Solution
If 30 units of product 1 and15 units of product 2 are produced, all hrs will be used in department
A while all but 50 will be used in depart B.

For Type II ( ≥ ) inequalities

For each “greater than or equal to” ( ≥ ) constraint a non-negative variable E, called a surplus
variable is subtracted from the left side of the constraint. This variable serves the function by
balancing the two sides of the equation .It represents the values that exceed the minimum
requirements.
In addition to subtracting a surplus variable, a non-negative variable A, called an artificial
variable is added to the left side of the constraint.
The artificial variable has no real meaning in the problem, its only function is to provide a
convenient starting point (initial solution) for the simplex.
Example 3
Assume in Example 1, that combined production of the two products must be at least 6 units.
Then: x1 + x 2 ≥ 6
in standard form (subtracting a surplus variable and adding an artificial variable) we have:
x1 + x 2 − E1 + A1 = 6
if we combine the three constraints in standard form we have
2x 1 +3x 2 + S 1 = 24 (machine 1)
2x 1 + x 2 + S 2 =16 (machine 2)
x1 + x 2 − E3 + A3 = 6 (Minimum requirements of units produced)
The subscript E 3 indicates the constraint (equation) number. That is each of the variable (slack,
surplus, artificial) is assigned a subscript that corresponds to the constraint number.
If x 1 = 6 and x 2 =2, suggests, we produce 6 units of product A and 2 units of product B. If we
substitute these values in the constraints, we have
x1 + x 2 − E3 + A3 = 6
6 + 2- E 3 = 6
E3 =2
The interpretation of the surplus variable E 3 is that combined production of 6 units of product A
and 2 units of product B exceeds the minimum requirement by 2 units.

Exercise
Assume in Example 2, that combined production of the two products must be at least 25 units.
Then: x1 + x 2 ≥ 25
in standard form (subtracting a surplus variable and adding an artificial variable) we have:
x1 + x 2 − E1 + A1 = 25
if we combine the three constraints in standard form we have
3 x 1 +2 x 2 + S 1 =120 (Dept A)
4 x 1 +6 x 2 + S 2 =260 (Dept B)

5
 x1 + x 2 − E3 + A3 = 25 (Minimum requirements of units produced)
The subscript E 3 indicates the constraint (equation) number. That is each of the variable (slack,
surplus, artificial) is assigned a subscript that corresponds to the constraint number.

If x 1 = 10 and x 2 =30, suggests, we produce 10 units of product 1 and 30 units of product 2. If

we substitute these values in the constraints, we have
x1 + x 2 − E3 + A3 = 25
10 + 30- E 3 = 25
E 3 = 15
The interpretation of the surplus variable E 3 is that combined production of 10 units of product 1
and 30 units of product 2 exceeds the minimum requirement by 15 units.

For Type III (=) equalities

For each "equal to " (=) constraint, an artificial variable is added to the left side of the constraint.
If a constraint has a negative right side value, the constraint can be multiplied by -1 to make the
right side positive. Notice for inequality constraints, the sense of the inequality reverses when
multiplied by a negative number.
Example:
Transform the following constraint set into the standard form required by the simplex method .
x 1 + x 2 ≤100
2x 1 + 3x 2 ≥ 40
x 1 -2 x 2 = 25
x1, x 2 ≥ 0
Solution
x 1 + x 2 + S 1 = 100
2x 1 + 3x 2 - E 2 + A 2 = 40
x 1 -2 x 2 + A 3 = 25
x1, x 2 , s1, E 2 , A 2 , A 3 ≥ 0

Example 2
Transform the following LP into the standard form required by the simplex method .

Max: z = 3 x 1 +2 x 2 +5 x 3
S/t : 2 x 1 -3 x 2 ≤ 3
x 1 +2 x 2 +3 x 3 ≥ 5
3 x 1 +2 x 3 ≤ 2
x1, x 2 , x 3 ≥ 0
The slack and surplus variables introduce no profit, so their coefficients in the profit equation
(objective function) is zero
Max : z = 3 x 1 + 2 x 2 + 5 x 3 + 0 S 1 + 0 E 2 + 0 A 2 + 0 S 3

6
S/t 2 x 1 -3 x 2 + S 1 = 3
x 1 +2 x 2 +3 x 3 - E 2 + A 2 = 5
3 x 1 +2 x 3 + S 3 = 2
x 1 , x 2 , x 3 , S 1 , E 2 ,A 2 ,S 3 ≥ 0

Variables which are unrestricted in sign can be represented as the difference between two non-
negative variables; thus if x1 is unrestricted replace it with:
x1 = x 1'' − x1' , where both x1' and x1'' are ≥ 0 .
After solving the problem in terms of x 'j and x ''j the value of x j is obtained through back
substitution.

When LP problems have been converted to the standard form where all constraints are restated
as equalities and supplemental variables have been added the resulting system of constraint
equations has more variables than equations.
An LP in standard from includes m simultaneous linear equations in terms of n unknowns
(variables) where m < n. The n variables can be considered in two sets.

1. n – m variables which are assigned the value of 0.

2. The remaining m variables whose values can be determined by solving the m
equations simultaneously.

If the m equations yield a unique solution, then the associated m variables are referred to as basic
variables and the remaining n-m zero variables are referred to as non-basic variables. The
unique solution from the m equations is called a basic solution. If all the variables have non-
negative values in the basic solution, then the basic solution is feasible. Otherwise, it is an
infeasible solution.

Example:
Consider, again the two - variable product -mix problem
Maximixe: Z = 6x 1 +7x 2
Subject to : 2x 1 +3x 2 ≤ 24 (2*2) system
2x 1 +x 2 ≤ 16
x1 , x 2 ≥ 0
In standard form the constraints are :
2x 1 +3x 2 + S 1 = 24 (machine 1)
2x 1 + x 2 + S 2 =16 (machine 2)
This is a (2*4) system of equations ,with more variables than equations .

We shall illustrate the concept of:

7
 • Feasible solution
• Basic solution
• Feasible basic solution
3.3.1 FEASIBLE SOLUTION
Feasible solution is any set of values for the n variables which satisfies the standard equations
and the non-negative constraints .

For the standard equations .

2x 1 +3x 2 + S 1 = 24 (machine 1)
2x 1 + x 2 + S 2 =16 (machine 2)

Suppose x 1 = 5 and x 2 = 2 then we have (substituting) in the equations .

S 1 = 8 and S 2 = 4
One feasible solution for the system is x 1 = 5, x 2 = 2 , S 1 = 8 , S 2 = 4

3.3.2 BASIC SOLUTION

Basic solution is any solution obtained by setting (n-m) variables equal to zero (0) and solving
the system of equations for the values of the remaining m variables .
The m variables solved for are called basic variables .The remaining (n-m) variables ,or those
which have been assigned value zero (0), are called non basic variables .
Example
For our former example:
2x 1 +3x 2 + S 1 = 24 (machine 1)
2x 1 + x 2 + S 2 =16 (machine 2)
Number of equations =2 = m
Number of variables = 4 = n ( 2*4) system
Number of the variables to be assigned value zero .
(n-m) = 4 - 2 = 2.
Suppose x 1 and S 1 are set equal to zero ,then
2(0) +3x 2 + 0= 24 (machine 1)
3x 2 = 24
x2 = 8
2(0)+ x 2 + S 2 =16 (machine 2)
8 + S 2 = 16
S2 = 8
The basic solution for the system is
x 1 = 0, S 1 = 0, x 2 = 8, S 2 = 8
With x 1 , S 1 non basic variables and
x 2 , S 2 basic variables.

Suppose x 1 and S 2 are set equal to zero ,then

8
 2(0) +3x 2 + S 1 = 24 (machine 1)
3x 2 + S 1 = 24 (i)
2(0)+ x 2 + 0 =16 (machine 2)
x 2 = 16 (ii)
using equation (ii) in (i) we have
S 1 = -24
The basic solution for the system is
x 1 = 0, S 1 = -24, x 2 = 16, S 2 = 0
With x 1 , S 2 non basic variables and
x 2 , S 1 basic variables.

3.3.3 BASIC FEASIBLE SOLUTION

A basic feasible solution is a basic solution which satisfies the non negativity
constraint/restriction.
Example1
Setting x 1 , x 2 equal to zero we have .
S 1 = 24 and S 2 = 16
Therefore x 1 = x 2 = 0, S 1 = 24, S 2 = 16
is a basic solution. Since all four variables satisfy the non negativity restrictions, this is a basic
feasible solution .
Suppose x 1 and S 1 are set equal to zero ,then
2(0) +3x 2 + 0= 24 (machine 1)
3x 2 = 24
x2 = 8
2(0)+ x 2 + S 2 =16 (machine 2)
8 + S 2 = 16
S2 = 8
x 1 = 0, S 1 = 0, x 2 = 8, S 2 = 8
is a basic solution. Since all four variables satisfy the non negativity restrictions, this is a basic
feasible solution

With x 1 , S 1 non basic variables and

x 2 , S 2 basic variables.

Suppose x 1 and S 2 are set equal to zero ,then

2(0) +3x 2 + S 1 = 24 (machine 1)
3x 2 + S 1 = 24 (i)
2(0)+ x 2 + 0 =16 (machine 2)
x 2 = 16 (ii)

9
using equation (ii) in (i) we have
S 1 = -24
x 1 = 0, S 1 = -24, x 2 = 16, S 2 = 0
is a basic solution. Since S 1 does not satisfy the non-negativity restrictions, this solution is a
basic but not feasible solution (infeasible).
Example 2
Consider the model
Maximize: Z=$40x1 + 50x2
subject to: 1x1 + 2x2 ≤ 40
4x2 + 3x2 ≤ 120
x1, x2 ≥ 0

in standard form we have

maximize: Z=$40x1 + 50x2 + 0s1 + 0s2

subject to: 1x1 + 2x2 + s1 = 40
4x2 + 3x2 + s2 = 120
x1,x2,s1,s2 = 0
where s1, s2 are slack variables
Solutions at
points A, B,
and C with
slack values

10
Thus the optimal solution can be found by performing a search of the set of basic feasible
solution. This is what the simplex method accomplishes. It begins with a basic feasible solution
consisting of two pools of variables, m basic variables and (n- m) non-basic variables. The
simplex method determines whether the objective function can be improved by exchanging a
basic variable and a non-basic variable. If an exchange will result in an improvement, an existing
basic variable is set equal to zero (0)
(becoming a non basic variable ), an existing non basic variable is included in the pool of basic
variables and the system of equations is re-solved with the new set of basic variables to form a
new basic feasible solution. A determination is made again regarding whether a better solution
exists .If so, another exchange takes place and the process repeats itself.

The basic - non basic variable interchange process gives rise to two suggestive names. The
entering variable is a current non basic variable that will "enter" the set of basic variables at the
next (adjacent extreme point) iteration. The leaving variable is a current basic variable that will
"leave" the basic solution in the next iteration.

3.4 SIMPLEX METHOD ALGORITHM:

The steps of simplex algorithm follows:
1) Using the standard form, determine a starting basic feasible solution by setting (n-m) non-
basic variables at zero level.
2) Select an entering variable from among the current (zero) non basic variables which, when
increased above zero, can improve the value of the objective function
• if non exists, stop;- the current basic solution is optimal.
• Otherwise, go to step 3
• If there are several possible entering variables, we usually choose
one with the most negative coefficient (this is the most negative coefficient rule); but
other choices are possible.
• In case of a tie for most negative, choose arbitrary (we'll choose the one farthest left).
3) Select a leaving variable from among the current basic variables that must be set to zero (non
basic) when the entering variable becomes basic.

11
 • For each positive entry in the entering variable's column, calculate the Ratio:
right hand side entry
coefficient of entering var iable
• Choose the smallest ratio. The basic variable for the row where this occurs is the
leaving variable.
• If there are no ratios to calculate, because all entries in the entering variable's column
are negative or zero, stop: the problem is unbounded.
• In case of a tie for smallest ratio, choose arbitrary (we'll choose the one highest up in
the tableau).
• The pivot row and pivot column are the row and column labeled by the leaving and
entering variables respectively. The pivot entry is the entry
in the tableau in the pivot row and pivot column.

4) Determine the new basic solution by making the entering variable basic and the leaving
variable non-basic.
• Divide the pivot row by the pivot entry.
• Add the appropriate multiple of the pivot row to each other row to
make the entry in the pivot column for that row 0.
• Relabel the pivot row by the entering variable.
5) Go to step 1

Fig1: Simplex method algorithm

Initial Simplex
Tableau

YES Take solution off

Optimum?
Indicators are final tableau
all positive or
zero

At least one indicator

is negative. NO
This determines
the pivot column.

Pick the most

negative indicator

Get a better NO
The problem has
solution? no solution.
All entries above this
indicator are zero or
negative 12
At least one value above
this indicator is positive
YES
Repeat the process for optimal solution
In a maximization problem having all ( ≤ ) constraints, the starting solution will have a set of
basic variables consisting of the slack variables in the problem.
Example 1:
Solve the problem
Maximixe: Z = 5x 1 +6x 2
Subject to : 3x 1 +2x 2 ≤ 120
4x 1 +6x 2 ≤ 260
x1 , x 2 ≥ 0

Solution:
In standard form :
Max : z = 5 x 1 + 6 x 2 + 0 S 1 + 0 S 2
S/t 3 x 1 + 2 x 2 + S 1 = 120
4x 1 + 6 x 2 + S 2 = 260
x1, x 2 , S 1 , S 2 ≥ 0
The simplex operations are performed in a tabular format

13
 System of equations :
z -5 x 1 -6 x 2 - 0 S 1 - 0 S 2 = 0
3 x 1 + 2 x 2 + S 1 = 120
4x 1 + 6 x 2 + S 2 = 260

By setting x 1 and x 2 equal to zero, we have initial solution S 1 = 120, S 2 = 260, Z = 0. The
basic variables are noted in the first column of the tableau (basic column ) and their Values are
read from the last column.

Basic Z x1 x2 S1 S2 solution
variables
z 1 -5 -6 0 0 0
S1 0 3 2 1 0 120
S2 0 4 6 0 1 260

In the current Z row (row zero), variables x 1 and x 2 , both have negative coefficients , since we
are maximizing Z, the value of Z can be improved by increasing either x 1 or x 2 above zero
level.

14
 However, we always select the variable with the most negative objective coefficient
because computational experience has shown that such a selection is more likely to lead
to the optimum solution rapidly. The above observation is the basis for what we call the
optimality condition of the simplex method. It states that:
In the case of maximization, if all the non basic variables have non negative coefficients
in z column of the current tableau , the current solution is optimal. Other wise, the non
basic variable with the most negative coefficient is selected as the entering variable.
In our example , we select x 2 as the entering variable At this point , the leaving
variable must be one of the current basic variables S 1 or S 2 .
In the tableau, the column representing the new basic variable will be called the key
column (pivot column).
To determine the leaving basic variable, we take row associated with

bi
Min ( ) i = 1,2,…….
aik
Where aik >0
That is the leaving basic variable is the minimum ratio of the right hand side (solution
column ) of the constraint equation to the associated positive coefficient of the entering
variable x 2
Therefore in our case:
120 260 260
Min ( , )=
2 6 6

The row associated with the leaving variable will be called the pivot equation ( row) and
the element at the intersection of the entering ( pivot) column and the pivot equation will
be called the pivot element.

Basic Z x1 x 2* S1 S2 solution
variables
z 1 -5 -6 0 0 0
S1 0 3 2 1 0 120
S2 0 4 6* 0 1 260

We make the pivot element equal to 1 and the other elements in the pivot column zero
using gaussian elimination procedures.

To make the pivot element equal to 1, we multiply the pivot row by 1/6.

2006: R. Waema Linear programming: Algebraic solution 15

Basic Z x1 * x2 S1 S2 solution
variables
z 1 -1 0 0 1 260
S1 0 5 0 1 1 1
* - 33
3 3 3
x2 0 4 1 0 1 1
43
6 6 3

100 3 130 6
Min ( * , * ) = (20, 65) = 20*
3 5 3 4

Basic Z x1 * x2 S1 S2 solution
variables
z 1 0 0 3 4 280
5 5
x1 0 5 0 1 1 20
* -
3 3
x2 0 4 1 0 1 30
6 6

Note that x 1 has replaced S 1 and x 2 replaced S 2 with S 1 and S 2 becoming the non
basic variables. Values of Z, x 1 , x 2 are read from the (solution) column as
Z =2 80
x 1 = 20
x 2= 3 0
S1= S 2 = 0
Since all row zero (0) z coefficients are non negative, this solution is optimal, which
agrees with our graphical solution .

Example 2
Solve the problem
Max: Z = 20x 1 +30 x 2
S/t : x 1 +2 x 2 ≤ 10
3x 1 +2 x 2 ≤ 18
x1, x 2 ≥ 0

solution

2006: R. Waema Linear programming: Algebraic solution 16

In standard form we have

Max: Z = 20x 1 +30 x 2 + 0S 1 +0S 2

S/t : x 1 +2 x 2 +S 1 = 10
3x 1 +2 x 2 +S 2 = 18
x1, x 2 ≥ 0

Initial Basic feasible solution

x1, x 2 = 0 (non-basic variables)
S 1 = 10 , S 2 = 18 (basic variables)
Initial simplex tableau with basic variables S1, S2, Z and nonbasic variables x1, x2. Initial
basic feasible solution: x1 = 0,x2 = 0, Z=0 (s1 = 10,s2 = 18)

Basic Z x1 x 2* S1 S2 solution
variables
Z 1 -20 -30 0 0 0
S1 0 1 2* 1 0 10
S2 0 3 2 0 1 18

Pivot column is x2 column (indicator = -30). Entering basic variable is x2

10 18
Min ( , ) = (5, 9) = 5*
2 2
Pivot row is S1 row (smallest positive quotient is 5)
Exiting basic variable is S1
Pivot element is 2

We make the pivot element equal to 1 and the other elements in the pivot column zero
using gaussian elimination procedures.

To make the pivot element equal to 1, we multiply the pivot row by 1/2.

Basic Z x1 * x2 S1 S2 solution
variables
z 1 -5 0 15 0 150
x2 0 1 1 1 0 5
2 2
S2 0 2* 0 -1 1 8

Basic feasible solution: x1 = 0, x2 = 5, Z = 150 (s1 = 0,s2 = 8)

Pivot column is x1 column (indicator = -5). Entering basic variable is x1

2006: R. Waema Linear programming: Algebraic solution 17

 8
Min ( 5 * 2, ) = (10, 4) = 4*
2
Pivot row is S2 row (smallest positive quotient is 4)
Exiting basic variable is S2
Pivot element is 2

Basic Z x1 x2 S1 S2 solution
variables
z 1 0 0 1 1 170
12 2
2 2
x2 0 0 1 3 1 3
-
4 4
x1 0 1 0 1 1 4
-
2 2

All indicators are positive or zero – STOP

Basic feasible solution: x1 = 4, x2 = 3, max. Z = 170 (s1 = 0,s2 = 0)

SUMMARY
Optimality condition: the entering variable in maximization (minimization) is the non
basic variable with the most negative (positive) coefficient in the z equation.
A tie is broken arbitrarily. When all the non basic coefficients in the z- equation are (non-
negative)(positive) the optimum is reached.
Feasibility condition: for both the maximization and minimization problems, the leaving
variable is selected to be any of the basic variable having the smallest ratio (with positive
denominator). A tie is broken arbitrary.

2006: R. Waema Linear programming: Algebraic solution 18

3.5 MAXIMIZATION PROBLEMS WITH MIXED

2006: R. Waema Linear programming: Algebraic solution 19

 CONSTRAINTS
3.5.1 Artificial Variables
The previous example problem contained only Type I ( ≤ ) inequalities. When other
constraint types are present (Type II and equality constraints), the set-up is necessarily
different. When other types of constraints are present we must add “artificial variables”
to form a starting basic solution (identity matrix). The complete set-up of the simplex
method including artificial variables follows.
The variables added to Type II inequalities and equality constraints are called “artificial
variables” because they have no real physical meaning. Their only purpose is to
provide a convenient starting basic solution. Note that the only value they can take on is
zero if the equations are to truly represent the actual constraints. Thus the original basic
solution (in which the artificial variables are positive) is not really feasible in terms of the
original constraints. Therefore, in the subsequent iterations of the simplex method the
artificial variables must be forced to become zero so that the solution becomes feasible
in terms of the true problem constraints. There are several ways to do this. The classical
method is referred to as the “Big-M method”, which will be discussed next.

3.5.2 The Big-M Method

Returning to the problem of forcing the artificial variables to be zero, one way which you
could insure that these variables become zero is to attach a large penalty in the objective
function for positive values. To do this we simply assign these artificial variables large
negative coefficients (-M) in maximization problems and a large positive coefficients
(+M) in minimization problems. Thus the objective function becomes in the
maximization case:
n m
Max: ∑C j X j − ∑ MRi
j =1 i =1

And in the minimization case:

n m
Min: ∑ C j X j + ∑ MRi
j =1 i =1

Where the M is some large number in comparison to the C j .

To illustrate, consider the following example problem:

Example 1
Max: Z = 2 X 1 + 3 X 2 − 5 X 3
St: X1 + X 2 + X 3 = 7
2 X 1 − 5 X 2 + X 3 ≥ 10
X 1 ≥ 0, X 2 ≥ 0, X 3 ≥ 0 .
Introducing Surplus and artificial variables, the constraints become:

X 1 + X 2 + X 3 + A1 = 7
2 X 1 + 5 X 2 + X 3 − E 2 + A2 = 10

2006: R. Waema Linear programming: Algebraic solution 20

We can penalize A1 and A2 in the objective function by assigning them very large
negative coefficient.
Let M be a very large positive value, The objective should then be modified to become:

Max: Z = 2 X 1 + 3 X 2 − 5 X 3 + E 2 − MA1 − MA2 .

In standard form we have
Max: Z = 2 X 1 + 3 X 2 − 5 X 3 + E 2 − MA1 − MA2 .
S/t : X 1 + X 2 + X 3 + A1 = 7
2 X 1 + 5 X 2 + X 3 − E 2 + A2 = 10
X 1 , X 2 , X 3 , A1 , A2 , E 2 ≥ 0
initial starting basic feasible solution
X 1 , X 2 , X 3 , E2 = 0
A1 = 7 A2 = 10

Putting the problem in tableau format it becomes:

Basic Z X1 X2 X3 E2 A1 A2 Solution
Z 1 -2 -3 5 0 M M 0
A1 0 1 1 1 0 1 0 7
A2 0 2 -5 1 -1 0 1 10

We must make the coefficients of the artificial variables in the Z row equal to Zero.
The M’s in the A1 and A2 columns must then be changed to zeros using row
operations. So you multiply Row 1 and Row 2 by –M and add them to Row 0 to obtain:

Basic Z X1 X2 X3 E2 A1 A2 Solution
-2 -3 5
Z 1 -3M +4M -2M M 0 0 -17M
A1 0 1 1 1 0 1 0 7
A2 0 2 -5 1 -1 0 1 10

−
Entering variable is X 1 , to get the leaving variable we have θ = MIN {7/1, 10/2}=5.
Hence leaving variable is A2

Basic Z X1 X2 X3 E2 A1 A2 Solution
-8 6 -1 1
X0 1 0 -7M/2 -M/2 -M/2 0 +3M2 10-2M
A1 0 0 7/2 1/2 1/2 1 -1/2 2
X1 0 1 -5/2 1/2 -1/2 0 1/2 5

2006: R. Waema Linear programming: Algebraic solution 21

In the next iteration X 2 enters and A1 leaves, yielding:

Basic Z X1 X2 X3 E2 A1 A2 Solution
16/7 -1/7
Z 1 0 0 50/7 1/7 +M +M 102/7
X2 0 0 1 1/7 1/7 2/7 -1/7 4/7
X1 0 1 0 6/7 -1/7 5/7 1/7 45/7

which is optimal since all Z ≥ 0 .

The optimal solution is
Z = 102/7 , X 1 = 45/7, X 2 = 4/7
X 3 = E2 = A1 = A2 =0
Example 2
Solve the following problem using simplex method
Maximixe: Z = 4x 1 +x 2
Subject to : 3x 1 +x 2 =3
4x 1 +3x 2 ≥ 6
x 1 +2x 2 ≤ 4
x1 , x 2 ≥ 0
in standard form we have:

Max : Z = 4x 1 +x 2 + 0 E 2 +0 S 3 -M A1 - M A2
S/t : 3x 1 +x 2 + A1 =3
4x 1 +3x 2 - E 2 + A2 = 6
x 1 +2x 2 + S 3 = 4
x1, x 2 , A 1 , A 2 , E 2 , E 2 ≥ 0
Initial starting basic solution
x1= x 2 = E 2 = 0
A 1 = 3, A 2 = 6 , S3 = 4
In tableau form we have

Basic Z x1 x2 S3 E2 A1 A2 solution
variabl
es
Z 1 -4 -1 0 0 M M 0
A1 0 3 1 0 0 1 0 3
A2 0 4 3 0 -1 0 1 6
S3 0 1 2 1 0 0 0 4

2006: R. Waema Linear programming: Algebraic solution 22

We want to make the coefficients of A 1 and A 2 equal to zero. So we multiply Row 1 and
Row 2 by –M and add them to Row 0 to obtain:

Basic Z x1 * x2 S3 E2 A1 A2 solutio
variabl n
es
Z 1 -4-7M -1-4M 0 M 0 0 -9M
A1 * 0 3* 1 0 0 1 0 3
A2 0 4 3 0 -1 0 1 6
S3 0 1 2 1 0 0 0 4

The entering variable is x 1 and the leaving variable is A 1 which gives us the following
tableau.

Basic Z x1 x 2* S3 E2 A1 A2 solutio
variabl n
es
Z 1 0 1 − 5M 0 M 4 + 7M 0 4-2M
3 3

X1 0 1 1 0 0 1 0 1
3 3
A 2* 0 0 5 0 -1 4 1 2
* −
3 3
S3 0 0 5 0 0 1 0 3
−
3 3

Since the Z row contains some negative coefficients then we have not reached the
optimal solution. The entering variable is x 2 and the leaving variable is A 2 giving us the
following tableau.

Basic Z x1 x2 S3 E2 A1 A2 solutio
variabl n
es
Z 1 0 0 0 1 8 + 5M − 1 + 5M 18
5 5 5 5

X1 0 1 0 0 1 3 1 3
−
5 5 5 5
x2 0 0 1 0 3 4 3 6
− −
5 5 5 5
S3 0 0 0 1 1 1 -1 1

2006: R. Waema Linear programming: Algebraic solution 23

Since all the values in the Z row are or positive or zero, the optimal solution is reached
The optimal solution is:
E 2 = A1 = A 2 = 0
18 3 6
Z= x1= x 2= S3 = 1
5 5 5

3.5.3 Minimization problem

Example

Suppose the problem above was a minimization problem then we have:

Minimixe: Z = 4x 1 +x 2
Subject to : 3x 1 +x 2 =3
4x 1 +3x 2 ≥ 6
x 1 +2x 2 ≤ 4
x1 , x 2 ≥ 0
in standard form we have:

Min : Z = 4x 1 +x 2 + 0 E 2 +0 S 3 +M A1 + M A2
S/t : 3x 1 +x 2 + A1 =3
4x 1 +3x 2 - E 2 + A2 = 6
x 1 +2x 2 + S 3 = 4
x1, x 2 , A 1 , A 2 , E 2 , E 2 ≥ 0

Initial starting basic solution

x1= x 2 = E 2 = 0
A 1 = 3, A 2 = 6 , S3 = 4

In tableau form we have

Basic Z x1 x2 S3 E2 A1 A2 solutio
variabl n
es
Z 1 -4 -1 0 0 -M -M 0
A1 0 3 1 0 0 1 0 3
A2 0 4 3 0 -1 0 1 6
S3 0 1 2 1 0 0 0 4

We want to make the coefficients of A 1 and A 2 equal to zero. So we multiply Row 1 and
Row 2 by M and add them to Row 0 to obtain:

2006: R. Waema Linear programming: Algebraic solution 24

Basic Z x1 * x2 S3 E2 A1 A2 solutio
variabl n
es
Z 1 -4+7M -1+4M 0 -M 0 0 9M
A1 * 0 3* 1 0 0 1 0 3
A2 0 4 3 0 -1 0 1 6
S3 0 1 2 1 0 0 0 4

The entering variable is x 1 and the leaving variable is A 1 which gives us the following
tableau.

Basic Z x1 x 2* S3 E2 A1 A2 solutio
variabl n
es
Z 1 0 1 + 5M 0 -M 4 − 7M 0 4+2M
3 3

X1 0 1 1 0 0 1 0 1
3 3
A 2* 0 0 5 0 -1 4 1 2
* −
3 3
S3 0 0 5 0 0 1 0 3
−
3 3

Since the Z row contains some positive coefficients then we have not reached the optimal
solution.
The entering variable is x 2 and the leaving variable is A 2 giving us the following
tableau.
Basic Z x1 x2 S3 E2 A1 A2 solutio
variabl n
es
Z 1 0 0 0 1 8 − 5M − 1 − 5M 18
5 5 5 5

X1 0 1 0 0 1 3 1 3
−
5 5 5 5
x2 0 0 1 0 3 4 3 6
− −
5 5 5 5
S3 0 0 0 1 1 1 -1 1

In this tableau not all variables have negative or zero coefficients in the Z row so we do
another iteration.

2006: R. Waema Linear programming: Algebraic solution 25

The entering variable is E 2 and the leaving variable is S 3 , giving the following tableau
Basic Z x1 x2 S3 E2 A1 A2 solutio
variabl n
es
Z 1 0 0 1 0 7 − 5M -M 17
−
5 5 5

x1 0 1 0 1 0 2 0 2
5 5 5
x2 0 0 1 3 0 1 0 9
−
5 5 5
E2 0 0 0 1 1 1 -1 1

Since all the coefficients in the Z row are either negative or zero, we have reached our
optimal solution.
The optimal solution is
A1 = A 2 = S 3 = 0
2 9
x1 = x 2= E2 = 1
5 5

Exercise
Solve the following problems
Maximixe: Z = 8x 1 +6x 2 Minimixe: Z = 10x 1 +10x 2
Subject to : 2x 1 +x 2 ≥ 10 Subject to : x 1 +x 2 ≥ 12
3x 1 +8x 2 ≤ 96 4x 1 + x 2 ≥ 24
x1 , x 2 ≥ 0 5x 1 + 4x 2 ≤ 120
x1 ≥ 3
Minimixe: Z = 5x 1 +6x 2 x 2 ≤ 18
Subject to : x 1 +x 2 ≥ 10 x1 , x 2 ≥ 0
2x 1 +4x 2 ≥ 24 Minimixe: Z = 2x 1 +5x 2
x1 , x 2 ≥ 0 Subject to : x 1 + x 2 ≤ 16
x 1 ≤ 12
Minimixe: Z = 3x 1 +8x 2
x1 ≥ 8
Subject to : x 1 +x 2 ≥ 8
x 2 ≤ 10
3x 1 - x 2 ≥ 0
x2 ≥ 4
2x 1 - 3x 2 ≤ 0
x1 , x 2 ≥ 0
x 1 +2x 2 ≤ 30
x2 ≥ 9
x 1 ≤ 10
x1 , x 2 ≥ 0

2006: R. Waema Linear programming: Algebraic solution 26

Maximixe: Z = 30x 1 +20x 2
Subject to : x 1 + x 2 ≤ 12 x2 ≥ 5
3x 1 +x 2 ≤ 18 x1 , x 2 ≥ 0
x1 ≥ 2

The Big-M method suffers from two important shortcomings.

You must go all the way to the final tableau before discovering that the problem has no feasible
solutions (artificial variables at positive level in final tableau).
The use of the constant M is cumbersome and if a very large number is substituted for M it can
cause numerical round-off problems on the digital computer.
3.5.4 Two Phase Method
Another artificial variable technique called the Two Phase Method removes these difficulties.
The name of the method comes from the fact that computations proceed in two distinct phases
(The linear problem is solved in two phases). The first phase merely attempts to drive the
artificials out of the basic solution using the simplex method and thereby form a feasible
starting solution without artificials for the second phase. The second phase merely moves
from this new feasible starting solution to optimality using the simplex method. The two phase
method is summarized as follows:

Phase I – Formulate the problem as you did for the Big-M method, i.e., adding artificials to
Type II and equality constraints, however you replace the actual objective function with:

K
Minimize: R 0 = ∑ Ai
i =1

Where the Ai are the K artificial variables. Now you solve this “artificial problem” by the
simplex algorithm. If the optimal objective function is greater than zero when the simplex
method terminates, stop! This indicates the problem has no feasible solution.
However, if the objective function is zero when the simplex method terminates, then all the
artificials have all been driven to zero (a true feasible solution) and you proceed to Phase II.
Phase II – You now restore the original objective function into the Z row of the tableau and
drop all non-basic artificial variables (and their columns) from the tableau. Then Finally, you
again apply the simplex method to move to the optimal solution which must exist.
To illustrate, the prior example is resolved using the two phase method. Recall the problem was:
Max: Z = 2 X 1 + 3 X 2 − 5 X 3
St: X1 + X 2 + X 3 = 7
2 X 1 − 5 X 2 + X 3 ≥ 10
X1, X 2 , X 3 ≥ 0
Phase I: The phase one problem is

Min: R 0 = A1 + A2
St: X 1 + X 2 + X 3 + A1 = 7

2005: R. Waema Linear programming: Algebraic solution 27

 2 X 1 − 5 X 2 + X 3 − E 2 + A2 = 10

Putting in the tableau form:

Basic R0 X1 X2 X3 E2 A1 A2 Solution
R0 1 0 0 0 0 -1 -1 0
A1 0 1 1 1 0 1 0 7
A2 0 2 -5 1 -1 0 1 10

Since A1 and A2 are the initial basic variables you must first get 0’s in the A0 row for them
before beginning the simplex method. You do this by row operations just like we did in the Big-
M method (add row 1 and 2 to row 0).
Adding the first and second rows to the R0 row gives us:

Basic R0 X1 X2 X3 E2 A1 A2 Solution
R0 1 3 -4 2 -1 0 0 17
A1 0 1 1 1 0 1 0 7
A2 0 2 -5 1 -1 0 1 10

Now use the simplex method to minimize R0 so select largest positive coefficient which is X 1 ’s
−
and θ = MIN {7 / 1,10 / 2} = 5 ( A2 leaves).

Performing row operations the next tableau is:

Basic R0 X1 X2 X3 E2 A1 A2 Solution
R0 1 0 7/2 1/2 1/2 0 -3/2 2
A1 0 0 7/2 1/2 1/2 1 -1/2 2
X1 0 2 -5/2 1/2 -1/2 0 1/2 5

−
Next select X 2 as the entering variable since it has the largest R0 row coefficient, θ = MIN
{2 /(7 / 2), ∞} 4/7 and A1 leaves. Performing the row operations yields the next tableau.
Basic R0 X1 X2 X3 E2 A1 A2 Solution
R0 1 0 0 0 0 -1 -1 0
x2 0 0 1 1/7 1/7 2/7 -1/7 4/7
x1 0 1 0 6/7 -1/7 5/2 1/7 45/7

2005: R. Waema Linear programming: Algebraic solution 28

Inspecting the R0 row, note that this solution is optimal. Since the value of the objective
function is zero, you know this problem has a feasible solution so proceed to Phase II.

Phase II: First you rewrite the tableau with the true original objective function, note that you
drop A1 and A2 and their columns.

Basic Z X1 X2 X3 E2 Solution
Z 1 -2 -3 5 0 0
X2 0 0 1 1/7 1/7 4/7
X1 0 1 0 6/7 -1/7 45/7

Again, this tableau is not in correct form since you do not have zeros for the basic variables in
the Z row. So you must apply row operations (multiply first row by 3 and second by 2 and add
to the Z row).

Basic Z X1 X2 X3 E2 Solution
Z 1 0 0 5 0/7 1/7 102/7
X2 0 0 1 1/7 1/7 4/7
X1 0 1 0 6/7 -1/7 45/7

When you examine the Z row you find this is optimal (if it were not you would continue with
the simplex method).
Question
What if there were Type I equalities, since they don’t have artificial variables, could they be left
out of Phase I? e.g., say the constraint X 1 + X 2 ≤ 6 was also included in the model.
Answer
All constraints must be included in Phase I, otherwise the solution obtained in Phase I may not
be feasible. Note that would be the case here, since the solution has X 1 + X 2 = 7 ! So whether
they have artificial variables or not ALL constraints are included in Phase I.

2005: R. Waema Linear programming: Algebraic solution 29

Exercise
Solve the following problem using the two phase method:
Minimixe: Z = 4x 1 +x 2
Subject to : 3x 1 +x 2 =3
4x 1 +3x 2 ≥ 6
x 1 +2x 2 ≤ 4
x1 , x 2 ≥ 0

3.6 SPECIAL CASES IN SIMPLEX METHOD APPLICATION

We consider special cases that can arise in the application of the simplex method, which include:
• Degeneracy
• Alternative optima
• Unbounded solutions
• Non-existing (or infeasible ) solutions

3.6.1 DEGENERACY:
Denerate solution to a linear program is one in which atleast one of the basic variables have the
value zero (0).
We indicated that in the application of the feasibility condition, a tie for the minimum ratio may
be broken arbitrarily for the purpose of determining the leaving variable. When this happens,
however, one of the basic variables will necessarily equal to zero in the next iteration. In this
case we say that the new solution is degenerate. The condition (degeneracy) reveals that the
model has at least one redundant constraint. Graphical illustrations give a better understanding of
this situation.

Example 1 (degenerate optimal solution)

Maximize: z = 3x 1 + 9x 2 (objective function)

Subject to: x 1 + 4x 2 ≤ 8
x 1 + 2x 2 ≤ 4
x1 , x 2 ≥ 0

The optimal final tableau is :

Basic z x1 x2 s1 s2 Solution
z 1 0 0 3/2 3/2 18
x 0 0 1 1/2 -1/2 2
2
x1 0 1 0 -1 2 0

When degeneracy disappears as the iterations are carried out, then we say that the solution is
temporarily degenerate
Example 2 (temporarily Degenerate solution)

2005: R. Waema Linear programming: Algebraic solution 30

Maximize: z = 3x 1 + 2x 2 (objective function)
Subject to: 4x 1 + 3x 2 ≤ 12
4x 1 + x 2 ≤ 8
4x 1 - x 2 ≤ 8
x1 , x 2 ≥ 0

Example 3 (Degenerate solution)

Maximize: z = 2x 1 + x 2 (objective function)

Subject to: 3x 1 + x 2 ≤ 6
x1- x 2 ≤ 2
x2 ≤ 3
x1 , x 2 ≥ 0

3.6.2 ALTERNATIVE OPTIMA:

When the objective function is parallel to a binding constraint, the objective function will assume
the same optimal value at more than one solution point. For this reason they are called
alternative optima.
When using simplex method, alternative optimal solutions are indicated when an optimal
solution has been identified, and in the z row (row (0)), coefficient for a non-basic variable
equals zero. The presence of a 0 in row (0) for a non-basic variable indicates that the non-basic
variable can become a basic variable and the current value of the objective function will not
change.
That is if the optimal tableau shows one or more nonbasic variables with zero coefficients in row
0 (z row), then there are alternative optimal solutions.

Example 1 (infinity of solutions)

Maximize: z = 2x 1 + 4x 2 (objective function)

Subject to: x 1 + 2x 2 ≤ 5
x1+ x 2 ≤ 4
x1 , x 2 ≥ 0

Example 2 (infinity of solutions)

2005: R. Waema Linear programming: Algebraic solution 31

 1
Maximize: z = x1+ x 2 (objective function)
2
Subject to: 2x 1 + x 2 ≤ 4
x 1 + 2x 2 ≤ 3
x1 , x 2 ≥ 0

3.6.3 INFEASIBLE SOLUTION:

If the constraints cannot be satisfied simultaneously. The model is said to have no feasible
solution. This situation occurs when the constraints in the same LP problem are of the type ≤ and
≥.
The condition of no feasible solution is signaled in the simplex method when an artificial
variable appears in an optimal basis at a positive level (value). (that is this condition is detected
in simplex method when an artificial variable remains positive in the final tableau).

Example 1 (infeasible solution space)

Maximize: z = 3x 1 + 2x 2 (objective function)

Subject to: 2x 1 + x 2 ≤ 2
3x 1 + 4x 2 ≥ 12
x1 , x 2 ≥ 0

3.6.4 UNBOUNDED SOLUTION:

A linear program has an unbounded solution if all entries in the pivot column are all zero or
negative (non - positive). This means that increasing a current variable whose value is zero will
result in all the current basic variables increasing.
In some LP models, the values of the variables may be increased indefinitely without violating
any of the constraints, meaning that the solution space is unbounded in at least one direction. As
a result, the objective value increase (maximization case) or decrease (minimization case)
indefinitely. In this case we say that both the solution space (feasible region) and the “optimum”
objective value are unbounded. Unboundedness in a model can point to one thing only. The
model is poorly constructed. The most likely irregularities in such models are:

(i) One or more non-redundant constraints are not accounted for

(ii) The parameters (constants) of some constraints are not estimated correctly.

2005: R. Waema Linear programming: Algebraic solution 32

If at any iteration of the simplex method, the a ik values are all 0 or negative for the variable
selected to become the new basic variable (entering variable) that is, elements in the pivot
column, there is an unbounded solution for the LP problem.

Exercise 1 (unbounded objective value)

Maximize: z = 2x 1 + x 2 (objective function)

Subject to: x 1 - x 2 ≤ 10
2x 1 ≤ 40
x1 , x 2 ≥ 0

2005: R. Waema Linear programming: Algebraic solution 33

Exercise 2 (unbounded objective value)

Maximize: z = -2x 1 + 3x 2 (objective function)

Subject to: 2x 1 - x 2 ≤ 30
x 1 ≤ 10
x1 , x 2 ≥ 0

Exercise 3 (unbounded objective value)

Maximize: z = 2x 1 + x 2 (objective function)

Subject to: -x 1 + x 2 ≤ 1
x 1 - 2x 2 ≤ 2
x1 , x 2 ≥ 0

2005: R. Waema Linear programming: Algebraic solution 34