In this section, we will examine the effect on the optimal solution as a result of the following changes:

i) changes in the cost of non-basic variables
ii) changes in the cost of basic variables
iii) changes in the supply and demand of teachers

Changes in the Cost of Non-Basic Variables:

To determine the effect of changes in the cost of non-basic variables, we have to check the reduced cost of the non-basic variables.

new cn		=	new cn - yAn
		=	old cn + Delta -yAn
		= 	old cn + Delta 

In order for the current solution to remain optimal, the new reduced cost must be less than zero, since there is a maximization problem. Therefore D must be less than the negative of old cn.

The old cn for each of the non-basic variables are listed in the output from GAMS, a software we used to solve the maximization problem. See gams output. Listed under Title "VAR X", in the column "MARGINAL", are the old cn values for each n not basic. For example, for the non-basic variable x11, the reduced cost is -22, and for non-basic variable x12, the reduced cost is -81, etc. The results imply that, say for x11, the combined utility of the teacher 1 on school 1 can only be raised by less than 22 units, or otherwise teacher 1 will be assigned to school 1 in the optimal assignment. Similarly, if the changes in the combined utility of teacher 1 to school 1 is increased by less than 81 units, then the current assignment of teacher 1 to school 9 will remain optimal.

Note that several costs of the non-basic variables can be changed simultaneously, and the effect of these changes on the optimal assignment will be independent of each other.

Changes in the Cost of Basic Variables

To determine the effect of changes in the cost of basic variables, xp we have to check the reduced cost of the non-basic variables.

However the changes in the cost of basic variables will effect the dual solution, since y=CbAb-1.

Consider the effect of the reduced cost for ck where xk is a non-basic variable

	new ck	=	ck - new yAn
		=	ck - (cb + Delta) Ab-1 An
		=	old ck - Delta Ab-1 An
		=	old ck - Delta Apk

for the current solution to remain optimal, the new ck must be greater than 0. Therefore

Delta less than or equal to old ck/Apk		
if Apk	greater than 0

Delta greater than or equal to old ck/Apk				
if Apk	less than 0

Say, for the teacher 1-school 9 pair (teacher 1 is currently assigned to school 9), we can find the restriction on the change of combined utility using the above calculation. Since there are 81 non-basic variables, we will have to examine 81 restrictions (i. e. Examine the ck and A2k for k=1..81). For simplicity, the 81 restrictions are not reproduced, however, based on the mathematical formulation as explained above, the decrease in c19 must be less than 25 for the current solution to remain optimal.

Changes in the Supply and Demand

In order for the problem to remain feasible, the total supply of teachers must equal to the total demand. Therefore, say if we increase the demand for teacher of one of the school, either the demand of the other school must be reduced correspondingly, or the supply of the teachers must increase.

Since the current constraints are linearly dependent, with one redundant constraint, therefore as we change one of the right hand side value, that is, the supply or demand of teachers for a particular node, the offsetting effect is assumed to be accounted for in the redundant constraint. As a result, we only need to examine the change in right hand side of one side of the pair of equations.

In this case, the demand of teacher of school j is increased from bj + Dj, that is the courses at school j requires the present of more than one teacher. For the current assignment to remain optimal, the current basic variables must be greater than 0

Therefore the requirement is that

new xb* = inv(Ab) (b + Delta) 	greater than or equal to 0
	  old xb* + inv(Ab)*Delta greater than or equal to 0

say for k, an element of the basis,

Delta greater than or equal to	(-xb*)k/(Ab-1)kj		
if (Ab-1)kj	greater than 0

Delta less than or equal to	(-xb*)k/(Ab-1)kj		
if (Ab-1)kj	less than 0

suppose the demand of school 1 increased, the range of increase must meet the following criteria:

(xb*)k		(Ab-1)kj	relation	(-xb*)k (Ab-1)kj	
0 		1		greater than or equal	0
1 		-1		less than or equal	1
0 		1		greater than or equal	0
0 		-1		less than or equal	0
0 		1		greater than or equal	0

As from the above analysis, any change in the demand of teacher for school 1 will result in a different optimal assignment solution. This is consistent with our expectation, since with the current solution, there is only one teacher assigned to school 1. If school 1 requires more than one teacher, then another teacher i must be assigned to the school, thereby changing the current optimal basis.

To see an example of change in supply of teachers, see extension 4.
You may also go back to Relaxed and Original Problem or go ahead with other links available on the internet.

Extension 5 Links