System Engineering 3(3+0)

LESSON 3. Linear Programming – Basic Ideas

Maximize (or) Minimize Z = c₁x₁ + c₂x₂ + c₃x₃ + ....... c_nx_n

          subject to the constraints

                   a₁₁x₁ + a₁₂x₂ + ... + a_1n x_n £ or = or ³ b₁

                   a₂₁x₁ + a₂₂x₂ + ... + a_2n x_n £ or = or ³ b₂

                   a₃₁x₁ + a₃₂x₂ + ... + a_3n x_n £ or = or ³ b₃

                   ................................

                   a_m1x₁ + a_m2 x₂ + ... + a_mn x_n £ or = or ³ b_m

and the non-negativity restrictions   

                   x₁, x₂, x₃, ... x_n ³ 0.

Note : Some of the constraints may be equalities, some others may be inequalities of (£) type or (³) type or all of them are of same type.

Solution: A set of values x₁, x₂ ...x_n which satisfies the constraints of the LPP is called its solution.

Feasible solution:  Any solution to a LPP which satisfies the non-negativity restrictions of the LPP is called its feasible solution.

Optimum Solution or Optimal Solution:  Any feasible solution which optimizes (maximizes or minimizes) the objective function of the LPP is called its optimum solution or optimal solution.

Slack Variables:  If the constraints of a general LPP be

                      ............(1)

then the non-negative variables s_i which are introduced to convert the inequalities (1) to the equalities  are called slack variables.  The value of these variables can be interpreted as the amount of unused resource.

Surplus Variables:  If the constraints of a general LPP be

                      ............(2)

then the non-negative variables s_i which are introduced to convert the inequalities (1) to the equalities

are called surplus variables.  The value of these variables can be interpreted as the amount over and above the required level.

 3.2 Canonical and Standard forms of LPP :

After the formulation of LPP, the next step is to obtain its solution.  But before any method is used to find its solution, the problem must be presented in a suitable from.  Two forms are dealt with here, the canonical form and the standard form.

The canonical form : The general linear programming problem can always be expressed in the following form :

       Maximize Z = c₁ x₁ + c₂ x₂ + c₃ x₃ +  ... c_n x_n

      subject to the constraints

                   a₁₁x₁ + a₁₂x₂ + .... + a_1n x_n ≤ b₁

                   a₂₁x₁ + a₂₂x₂ + .... + a_2n x_n ≤ b₂

                   .................................

                   a_mlx₁ + a_m2 x₂ + ... + a_mn x_n ≤  b_m

and the non-negativity restrictions   

                   x₁, x₂, x₃, ... x_n ≥ 0.

This form of LPP is called the canonical form of the LPP.

In matrix notation the canonical form of LPP can be expressed as :

Maximize Z       =   CX (objective function)

Subject to AX    ≤  b (constraints)

and      X       ≥   0 (non-negativity restrictions)

where C         =   (c₁  c₂ …c_n),

3.2.2 Characteristics of the Canonical form :

(i) The objective function is of maximization type.

Min f(x)    =   - Max {-f(x) } (or)

Min Z       =   - Max (-Z)

 (ii)  All constraints are of (≤) type, except for the non-negative restrictions.

An inequality of  “≥” type can be changed to an inequality of the type “≤” type by multiplying both sides of the inequality y -1.

             For example, the linear constraint

                   a_1lx₁ + a₁₂ x₂ + ... + a_1n x_n ≥   b_i

is equivalent to

                   -a_ilx₁ - a_i2 x₂ - ... - a_in x_n ≤ -  b_i

An equation may be replaced by two weak inequalities in opposite directions.

For example

a_ilx₁ + a_i2 x₂ + ... + a_in x_n =  b_i

is equivalent to

a_ilx₁ + a_i2 x₂ + ... + a_in x_n ≥   b_i

and  a_ilx₁ + a_i2 x₂ + ... + a_in x_n ≤  b_i

 (iii) All variables are non-negative.

A variable which is unrestricted in sign is equivalent to the difference between two non-negative variables. Thus if x_j is unrestricted in sign, it can be replaced by (x_j^l- x_j^ll), where x_j^land x_j^ll are both non-negative,

 i.e.,  x_j = x_j^l- x_j^ll, where x_j^l  ≥ 0 and  x_j^{l l}≥ 0

 The Standard From :

The general linear programming problem in the form

       Maximize or Minimize

        Z = c₁ x₁ + c₂ x₂ + …….. + c_n x_n

Subject to the constraints

                   a₁₁x₁ + a₁₂x₂ + ....................... + a_1n x_n = b₁

                   a₂₁x₁ + a₂₂x₂ + ....................... + a_2n x_n = b₂

                   .....................................................................

                   a_mlx₁ + a_m2 x₂ + ............... + a_mn x_n  =  b_m

                                    and x₁, x₂, ....................... x_n ≥ 0 is known as standard form

In matrix notation the standard form of LPP can be expressed as :

Maximize or Minimize Z = CX (objective function)

Subject to constraints  AX  = b and X ≥ 0

Where, c =  (c₁,c₂,…,c_n),

3.2.3 Characteristics of the standard form :

1. All the constraints are expressed in the form of equations, except for the non-negative restrictions.

2. The right hand side of each constraint equation is non-negative.

The inequalities can be changed into equation by introducing a non-negative variable on the left hand side of such constraint. It is to be added (slack variable) if the constraint is of “ ≤ ” type and subtracted (surplus variable) if the constraint is of “ ≥ ” type.

Basic Solution.: Given a system of m simultaneous linear equations with n variables (m < n).  

                Ax=b, x^T ε Rⁿ

where A is an m x n matrix of rank m. Let B be any m x m sub matrix, formed by m linearly independent columns of A. Then a solution obtained by setting n-m variables not associated with the columns of B, equal to zero, and solving the resulting system, is called a basic solution to the given system of equations.

The m variables, which may be all different from zero, are called basic variables. The m x m non-singular sub matrix B called a basis matrix with the columns of B as basis vectors. The (n-m) variables which are put to zero are called as non-basic variables.

Example:

Obtain all the basic solutions to the following system of linear equation:

x₁ + 2x₂ + x₃ = 4

2x₁ + x₂ + 5x₃ = 5

Solution:

The given system of equations can be written in the matrix form

Ax=b

where,
  

since rank of A is 2, the maximum number of linearly independent columns of A is 2. Thus we can take any of the following, 2x 2 sub-matrices as basis matrix B:

 

The variables not associated with the columns of B are x₃, x₂ and x₁ respectively, in the three different cases.

  

A basic solution to the given system is now obtained by setting x₃ = 0, and solving the system

         

Thus a basic (non-basic) solution to the given system is

(Basic) x₁= 2, x₂ = 1;                       (Non-basic) x₃ = 0,

(Basic) x₁= 5, x₃ = -1;                      (Non-basic) x₂ = 0,

(Basic) x₂ = 5/3, x₃ = 2/3;                 (Non-basic) x₁ = 0.

We observe that all the above three basic solutions are non-degenerate solution.

Degenerate Basic Solution:  A basic solution is said to be a degenerate basic solution if one or more of the basic variables are zero.

Basic Feasible Solution:  A feasible solution to a LPP., which is also a basic solution to the problem is called a basic feasible solution to the LPP.