Solving Network Problems using the Power of Duality Theory

Solving Network Problems using the Power of Duality Theory

Francisco Zaragoza Huerta.

ITESM

Abstract:- Every day a large number of problems are studied and analyzed where modeling in the form of networks is a way of being more efficient in the search for efficient results for companies, organizations, associations and even in problems of particular interest, at each moment gradually the number of Study requirements of this type of case are becoming more frequent, this research document tries to show an alternative way of finding a solution to problems that can be very complicated, since they can exponentially increase the modeling as a whole of equations and feasible spaces hence the importance of remembering interesting linear programming algorithms as a source of inspiration for the state of the art that allows it to be viewed by researchers as a useful tool in large-scale network problems, sometimes small prototypes can provide solutions of powerful in a simple way and without a high cost of implementation where creativity is the way to find search solutions.

Key words;- Duality, Complementary Slack, Network.

INTRODUCTION.

The problem originally formulated is known as primal, while its closely related counterpart is known as dual. The relationships are such that each is the dual of the other and finding the optimal solution for one implies immediately finding the optimal solution for the other.

Operations Research aims to determine the best optimal course of action for a decision problem with limited resource constraints, applying mathematical techniques to represent by means of a model and analyze decision problems. (Taha. A..
Hamdy, Prentice Hall, 1998 Operations Research).

A typical application of the dual simplex method is in solving problems with an objective function of minimization, with restrictions of the type greater or equal and where the decision variables are greater than or equal to zero.

The duality theory establishes that a dual linear programming problem originates directly from the original model called the primal problem. The two are closely related, so that the optimal solution of one of them provides the optimal solution of the other.

The dual problem could save a considerable number of calculations, particularly when the primary problem has many restrictions and few variables which will involve a large number of calculations for their resolution by the Simplex method Another advantage of the existence of the dual program is the possibility of reducing the computational effort when solving certain linear programming models. It allows solving linear programming problems more quickly and easily.

Networks.

In a linear programming problem, a set of nodes that are associated with information such as cities, flows, distances, capacities, etc. can be represented. In which different types of solutions can be sought such as minimizing costs, times, distances or maximizing yields, profits or capacities.

Each node would be an equation in the set of the linear programming problem, in which the function the objective will be proposed with the same information provided in the problem in any of its two directions to optimize. It is essential to observe the importance of duality theory to minimize the number of equations, trying to find a feasible solution in time polynomial, the efficiency of the dual problem is significant to establish itself as a potential alternative of systematized efficiency in a global approach to competitiveness, where the state of the art is gradually modeled covering the different combinations and alternatives through which the silhouette moves towards the search for the optimal solution. The amount of real-world information that can be modeled as p the network of networks is infinite and with them the transcendent potential to accelerate solutions in real time

COMPLEMENTARY SLACK THEORY.

Often, linear program constraints are inequalities; this means that they do not necessarily have to be fulfilled as equalities, so there may be a difference between the values of the left and right terms. In PL terms, this difference is the "slack". Conceptually, slack is the amount of idle resources (raw materials, financing, etc. available, but not used). Zero slack constraints are said to be active because they actively constrain the solution; those that have positive slack are said inactive

In the Complementary Slack Theorem. It seeks to guarantee that if the slack of a constraint takes a value other than zero, the corresponding shadow price will be equal to zero. If a shadow price takes a value other than zero, the corresponding slack will take the value zero (the inverse is not necessarily true)

Additionally, it allows us to find the optimal solution of the Dual Problem when we know the optimal solution of the Primal Problem (and vice versa) through the resolution of a system of equations made up of the decision variables (primal and dual) and the restrictions (of the primal and dual model).

The importance of this theorem is that it facilitates the resolution of the linear optimization models, allowing whoever solves them to find the simplest model to approach (from the algorithmic point of view) given that in any case they will be able to obtain the results of the associated equivalent model (be this the primal model.

Network models and the Complementary Slack theorem.

Network models are a necessity to implement real life cases because a large number of problems can be modeled as networks using the Linear programming as a solution tool, however one of the limitations of mathematical programming problems is the explosion of equations when the models are programmed since software is required to work to solve large-scale models, this is where the duality theory and the complementary slack theorem are powerful helpers for reaching solutions in real time.

In the linear program document (Huerta, F.Z. and de Lara, R.G.L., 2015. Comparison of Alternative Solutions in Linear Programming Modeling using the Dual Simplex Method and Duality Method from Primal Problem, Establishing Implementation through the Simplex Methodology) says Many real life problems can be treated using the dual simplex algorithm where an initial optimality to the actual feasibility of resources and goals can be adjusted with the methodologies presented in this investigation is determined

The strong relationship between the primal and dual models can be appreciated, from which the complementary slack theorem is derived as a powerful solver for solving network problems since it minimizes the number of equations and facilitates the programming of models from the computational perspective. , the modeling that can be obtained when the state of the art is glimpsed from the edge of abstraction to execution in real time is truly splendid.

Without a doubt, working using duality and the complementary slack theorem will provide a way of more practical management for administrators to easily visualize the depth and try Adduction of each equation of the models that are represented, providing valuable information for decision-making and for the construction of process reengineering to the operation models where information such as time, money, capacity, efficiency, distance, etc. flows. In these times where efficient results are required in a short time the duality theory is basic, not using it is not only a waste but the loss of optimizing processes that in network odels are configured to explain what happens in them and forecast future scenarios that improve the positioning of organizations and companies. When we can know what should be done to improve current productive actions, we are able to substantially increase profitability or minimize losses, concepts widely linked to operations research.

Development of algorithms and software used.

Chinese Postman Problem (CPP).

Establishment.

In 1962 the mathematician named Kuan Mei-Ko was interested in how postal personnel could deliver letters on a certain number of streets in such a way that the total distance walked by the postman was as short as possible. The CPP is one of the classic problems in discrete mathematics, it is also a problem equivalent to that of the traveling agent (TSP) and is posed in the following terms: A postman must travel a certain number of streets in a city, each one at least once and deliver the mail to later return to their office of origin (Eulerian cycle), it is intended to find a route for the postman that allows minimizing the total distance traveled.

If the network has an Eulerian cycle, it is clear that this will be the solution to the problem in another way; surely some vertex is of an odd degree, which will cause routes through that edge (s) more than once. Recall that an Eulerian cycle is the cycle that goes through all the nodes only once and goes through each edge exactly once. The steps to solve this problem are summarized in the following sections:

Step 1	Identify nodes with odd flow considering the arcs that relate to them.
Step 2	These nodes should appear considering all possible pairs.
Step 3	Find the smallest distance between each pair of odd nodes
Step 4	Choose the set of odd nodes that includes an even node and select the path with the minimum total distance. This even node is added to the sum of all the arcs between odd nodes to give the shortest distance to traverse the network and return to the original starting point.

Example Implementation

Solve the following problem in the delivery of couriers from the Telebachillerato System in Michoacan Mexico, to different work centers applying the CCP algorithm for the following offices, the lines represent the relationship between the dependencies and a number is also shown which is the length of the distances, you can see that the position of the post office (origin) does not affect the solution.

800

5

5

600

6

6

600

300

7

7

400 8

400

500

500

400

4

4

9

9

1	100	2	300	3

1	100	2	300	3

700

800

100

300

10

10

11

Step 1

Step 2

Graphic 1. Data problema.

Node number	Number of edges	Type of node	Node number	Number of edges	Taype of node
6	3	Ord	1	2	Oven
9	3	Odd	3	2	Even
4	3	Odd	5	4	Even
2	3	Odd	7	2	Even
8	3	Odd	11	2	Even
10	3	Odd

Table 1.Odd and Even Nodes in the network

Nodes and name	Relation between work centers	Distances in meters
1.Telebachillerato Office	1-2	100
2. Management Office	1-6	600
3. Particular Office	2-3	300
4. Social Service Office	2-5	800
5. Human Resources Office	3-4	400
6. Computing Center	4-5	500
7. Benefits Office	4-10	300
8. Training Center	5-6	600
9. Legacy Office	5-9	400
10.Audience Office	6-7	300
11Workshop	7-8	400
12.Register Office	8-9	500
13.Social Communication	8-11	800
14.Payroll Office	9-10	700
15.Labor Relations	10-11	100

Table 2. (Data problem and name work center)

Step 3

The odd node graph is made by calculating the minimum distance considering all nodes with even flow (input and output). For example, to get from node number 2 (two) to node number 10 (ten) the shortest distance is following the path:

2 3 4 10 with total flow equal to 300 + 400 + 300 which gives us a total flow of 1000 and it only remains in the network graph

2 10 with total Flow equal to 1000

Which generates a simplification of nodes, for this reason note in the graph that node three (3) only has one inflow and one outflow, then it has a total of two flows and is considered (even), so it is adds the value of its flows and disappears from the network under analysis. Check graph 1.4

Step 4 (algorithm detail Implementation)

Odd Nodes	Matrix of shorter distances between odd nodes
	4	6	8	9	10
2	300+400 =700	100+600=700	100+600+300+400=1400	800+400=1200	300+400+300=1000
4		500+600=1100	300+100+800=1200	500+400=900	300
6			300+400=700	600+400=1000	600+500+300=1400
8				500	800+100=900
9					700
10

Table 4. Matrix shorter distances between odd nodes.

Step 5 (Algorithm detail)

Odd Node	Variables to graphic in the network between odd nodes.
	4	6	8	9	10
2	X1	X2	X3	X4	X5
4		X6	X7	X8	X9
6			X10	X11	X12
8				X13	X14
9					X15
10

2

2

9

9

700x

700x

6

6

14

14

Step 4

2

700x

700×1

1000×5

1400×12

10

300x

2

700x

700×1

1000×5

1400×12

10

300x

6

1100x

700×10 1200×4

15 900x

4

6

1100x

700×10 1200×4

15 900x

4

1000x

3 900x

1000x

3 900x

500×13

500×13

1400x

1400x

8

8

11

11

9

9

8

8

1200x

1200x

7

7

Graph 2. (Algorithm implementation).

Once the minimum distances have been calculated only between nodes with odd flow according to the graph. Note that now all the nodes of the network have an odd degree, which will cause more than one route on some edges, now they are integrated into the objective function as well as the generation of the restrictions for each odd node to proceed to the coding of the model and its subsequent analysis in the results produced by the software. Note that nodes 1, 3, 5, 7 and 11 are considered in the network of graph 1.4 although they as such do not appear; now we are able to establish the linear programming model based on the previous graph.

The linear programming model will be as follows;

, + + + + + + + +

+ + + + + +

,

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

, + + + + + + + +

+ + + + + +

,

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

CODE IN GAMS

*CPP ALGORITHM

*Performance by Dr Francisco Zaragoza Huerta

Sets

j / 1*15 /

i / 1*6/ ;

Parameters

B(i) / 1 1

2 1

3 1

4 1

5 1

6 1/;
Parameters
C(j) / 1 700
2 700
3 1400
4 1200
5 1000
6 1100
7 1200
8 900
9 300
Continuation of the code in GAMS 10 700
11 1000
12 1400
13 500
14 900
15 700 /;
Variables
X(j),z
BINARY variables
X(j) ;
table A(i,j)
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15
2 1 1 1 1 1
4 1 1 1 1 1
6 1 1 1 1 1
8 1 1 1 1 1
9 1 1 1 1 1
10 1 1 1 1 1
Equations
fo
rest(i) ;
fo .. z =e= sum (j, c(j)*x(j));
rest(i).. sum (j,A(i,j)*x(j))=E= b(i);
Model ejerc /all/;
Solve ejerc using MIP Minimizing z;

Results
MODEL STATISTICS
BLOCKS OF EQUATIONS	2	SINGLE EQUATIONS	7
BLOCKS OF VARIABLES	2	SINGLE VARIABLES	16
NON ZERO ELEMENTS	46	DISCRETE VARIABLES	15
GENERATION TIME = 0.047 SECONDS 4 Mb WIN237-237 2011

EXECUTION TIME = 0.047 SECONDS
S O L V E S U M M A R Y
MODEL ejerc OBJECTIVE z
TYPE MIP DIRECTION MINIMIZE
SOLVER CPLEX FROM LINE 50
**** SOLVER STATUS 1 Normal Completion
**** MODEL STATUS 1 Optimal
**** OBJECTIVE VALUE 1500.0000

– VAR x

LOWER LEVEL UPPER MARGINAL
1 . . 1.000 700.000
2 . 1.000 1.000 700.000
3 . . 1.000 1400.000
4 . . 1.000 1200.000
5 . . 1.000 1000.000
6 . . 1.000 1100.000
7 . . 1.000 1200.000
8 . . 1.000 900.000
9 . 1.000 1.000 300.000
10 . . 1.000 700.000
11 . . 1.000 1000.000
12 . . 1.000 1400.000
13 . 1.000 1.000 500.000
14 . . 1.000 900.000
15 . . 1.000 700.000

S O L V E S U M M A R Y
Variable x
Lower	Level	Upper	Marginal
-INF	1500.00	INF	.

The graph shows the results produced by the software and integrated into the graph, the minimum distances of the odd nodes under study.

2

700×2

6

700×1

1000×5

1400×12

1100×6

700×15

10

900×14

300×9

700×10 1200×4

1000×11

1400x

3 900x

4

8

1200x

9 8 7

500×13

Graphic 3. Which is equivalent to the following final graph where the results based on the original network are implemented?

1 100

2 300

3 400

800

5

5

600

6

6

600

7

7

300

400

500

500

9

4

700

300

10

400 8

800

100

11

Graph 4. (Nodes solution after algorithm implementation)

From the previous results and analyzing the previous graph, it is observed that the minimum distance is equal to 1500, so the routes that must be used twice to obtain the minimum time must:

Between node 6 and 1	Telebachillerato Office and Computing Center
Between node 1 and 2	Telebachillerato Office and Management Office
Betweennode 4 and 10	Social Service Office and Workshop
Between node 9 and 8	Audience Office and Register Office

Rute Solution

The personnel must leave node 1, go through all the arches at least once, crossing all the edges and make a double route between nodes (6,1), (1,2), (4,10), and (9,8), in such way that it leaves and returns to the origin.

The path for staff starts and ends at node 1
1	6	7	8	9	8	11	10	4	10	9	5	4	3	2	1	6	5	2	1

(Graphic 5)

• It is very interesting to observe the execution time of 0.047 seconds, a simply spectacular work timer.

• The information that is generated can be translated from time to money to efficiency in general to evaluation of the operation of current systems and continuous improvement scenarios; it is the art of mathematical programming at its best.

Application of the complementary Slack condition to the CPP.

Cx* = w* Aw* = w*b

But ; Cx* = w*b;

Then Cx*= w*Aw*=w*b

therefore we get w* (Ax*-b ) = 0 y (C-w*A) x* = 0

Cx* = w* Aw* = w*b

But ; Cx* = w*b;

Then Cx*= w*Aw*=w*b

therefore we get w* (Ax*-b ) = 0 y (C-w*A) x* = 0

If x * and w * are any pair of solutions to the Primal problem and the Dual problem in canonical form respectively. We have to;

Complementary slack theorem;

( cj-w*aj ) xj* = 0; for j=1,2,…..,n

w*i (ai x* – bi ) = 0, for i =1,2,….,m

In a linear programming problem when optimality is reached. If a variable in any problem is different from zero, then the corresponding equation in the other reciprocal problem must be fitted (Ax-b = 0) and if an equation in a problem cannot be adjusted (Ax-b= 0), then the corresponding variable in the other converse problem must be zero.

Implementation Proposal Given the optimal solution of the Dual problem, find the optimal solution of the Primal problem of the application of the Chinese postman algorithm (previous exercise) using the Complementary Slack Theorem.

Primal Problem of the Chinese Postman (CPP):

, + + + + + + + +

+ + + + + +

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

, + + + + + + + +

+ + + + + +

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

Dual Problem (CPP)

, = + + + +

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

, , , , >=

Dual Problem (CPP)

, = + + + +

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

+ <=

, , , , >=

Results using Lindo Software

Global optimal solution found.
Objective value: 1500.000
Infeasibilities: 0.000000
Total solver iterations: 6
Model Class: LP
Total variables: 6
Nonlinear variables: 0
Integer variables: 0
Total constraints: 16
Nonlinear constraints: 0
Total nonzeros: 35
Nonlinear nonzeros: 0
Variable Value Reduced Cost
Y1 400.0000 0.000000
Y2 300.0000 0.000000
Y3 300.0000 0.000000
Y4 0.000000 1.000000
Y5 500.0000 0.000000
Y6 0.000000 0.000000
Row Slack or Surplus Dual Price
1 1500.000 1.000000
2 0.000000 1.000000
3 0.000000 0.000000
4 1000.000 0.000000
5 300.0000 0.000000
6 600.0000 0.000000
7 500.0000 0.000000
8 900.0000 0.000000
9 100.0000 0.000000
10 0.000000 0.000000
11 0.000000 1.000000
12 200.0000 0.000000
13 1100.000 0.000000
14 0.000000 1.000000
15 900.0000 0.000000
16 200.0000 0.000000

Substituting the solution values in the Dual problem we have:

Eq(1) ;Y1 +y2 <= 700; 400+300<=700; the equation is adjusted

Eq(2) ;Y1 + y3 <=700; 400+300<=700; the equation is adjusted

Eq(3) ;Y1 + y4 <=1400 ;400+0 <=1400 ; the equation is not adjusted

Eq(4) ;Y1 + y5 <= 1200;400 + 500<=1200;the equation is not adjusted

Eq(5) ;Y1 + y6 <=1000; 400 + 0 <= 1000; the equation is not adjusted

Eq(6) ;Y2+y3 <=1100; 300 + 300 <=1100;the equation is not adjusted

Eq(7) ;Y2 + y4 <=1200; 300 +0 <=1200; the equation is not adjusted

Eq(8) ;Y2 + y5 <=900; 300 + 500 <=900; The equation is not adjusted

Eq(9) ;Y2 + y6 <=300; 300 + 0 <= 300 ; the equation is adjusted

Eq(10) ;Y3 + y4 <=700; 300 + 0 <=700 ; the equation is not adjusted

Eq(11) ;Y3 + y5 <=1000; 300 + 500 <=1000; the equation is not adjusted

Eq(12) ;Y3 + y6 <= 1400 ; 300 + 0<=1400; the equation is not adjusted

Eq(13) ;Y4 + y5 <=500 ;0 + 500 <=500 , the equation is adjusted

Eq(14) ;Y4 + y6 <= 900 ; 0 + 0 <=900 ; the equation is not adjusted

Eq(15) ;Y5 + y6 <0 700 ; 500 + 0 <=700 ; the equation is not adjusted

Note: Where it is mentioned that if the equation is adjusted, it refers to exactly reaching the value of the resource on the right side, otherwise it is not reached. Which means: ; That the values that are perfectly fulfilled are equations 1, 2, 9 and 13 Therefore, the variables with this sub index in the primal problem will have a value different from zero and the equations that are not satisfied, it will be assumed that the variables with the sub index number of the equation will have a value of zero in the primal. Let's analyze the equations of the primal where the variables x1, x2, x9 and x13 are immersed, which will have a value different from zero, all the other variables will have a zero value, which allows us to solve and know the value of the variables of the primal that we are looking for.

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

+ + + + <= , (. )

,

;

+ + + + <= , (, )

+ + + + <= , (, )

+ + + + <= , (, )

+ + + + + <= , (, )

<> + + + + <= , (, )

+ + + + <= , (, )

,

;

+ + + + <= , (, )

+ + + + <= , (, )

+ + + + <= , (, )

+ + + + + <= , (, )

+ + + + <= , (, )

+ + + + <= , (, )

We can infer based on the previous equations that the values of x1 = 0, x2 = 1, x9 = 1 and x13 = 1 ;Interesting as x1 apparently should take a value other than zero, however, when performing algebraic operations results with a value equal to zero. Once this detail has been mentioned, the value of the objective function can be obtained by substituting the values of the variables and multiplying them by the respective coefficient, as shown below

, + + + + + + + +

+ + + + + + +

, + + + + + + + +

+ + + + + + +

Z*=700 (x2) + 300(x9) + 500(x13) Z*=700(1)+300(1)+500(1)=1500

Z*=700 (x2) + 300(x9) + 500(x13) Z*=700(1)+300(1)+500(1)=1500

With which the values of the variables of the Primal problem are obtained as well as the optimal solution of the objective function applying the complementary slack conditions of the Dual problem, being able to verify that the same optimal value is obtained in the Primal problem and in the Dual problem being in this case

Z*=W*=1500

Z*=W*=1500

Being then demonstrated the power of this linear programming tool that allows obtaining the value of the objective function in a practical and efficient way, starting from the dual problem with the complementary slack theorem, a fundamental tool in optimization processes.

FINAL CONCLUSIONS.

• It can be seen how network model problems can be programmed in a practical and simple way, avoiding a lot of computational work through creative coding, additionally it can be observed how the treatment of network problems with linear programming algorithms provide optimal solutions in real time.

• The large scale in network problems rather than something complex is an opportunity and challenge to be implemented in states of the art.

• The major problems, no matter how complex they may be within linear programming, are nothing more than a set of equations with algebraic additions and subtractions (Trigos, F notes on linear programming, Itesm Campus Toluca, 2003).

• It is important to consider duality theory as one of the most efficient weapon in solving network problems, since due to its computational structure it drives feasible solution spaces towards optimization.

• Optimization network algorithms are an exceptional complement for modeling and for handling and solving a large number of equations.

• Not using the aforementioned tools complicate the analysis and search for solutions, being a waste to underestimate such valuable alternatives.

• The duality theory with its linear programming algorithms will always be a reference that must be in the researcher's mental and digital library in network problem.

• Programming in some large-scale software such as GAMS is essential to achieve success in the modeling of large-scale network problems, so it is recommended to improve your skills in this area.

• It can be seen how network model problems can be programmed in a practical and simple way, avoiding a lot of computational work through creative coding, additionally it can be observed how the treatment of network problems with linear programming algorithms provide optimal solutions in real time.

• The large scale in network problems rather than something complex is an opportunity and challenge to be implemented in states of the art.

• The major problems, no matter how complex they may be within linear programming, are nothing more than a set of equations with algebraic additions and subtractions (Trigos, F notes on linear programming, Itesm Campus Toluca, 2003).

• It is important to consider duality theory as one of the most efficient weapon in solving network problems, since due to its computational structure it drives feasible solution spaces towards optimization.

• Optimization network algorithms are an exceptional complement for modeling and for handling and solving a large number of equations.

• Not using the aforementioned tools complicate the analysis and search for solutions, being a waste to underestimate such valuable alternatives.

• The duality theory with its linear programming algorithms will always be a reference that must be in the researcher's mental and digital library in network problem.

• Programming in some large-scale software such as GAMS is essential to achieve success in the modeling of large-scale network problems, so it is recommended to improve your skills in this area.

REFERENCES

1. Ahuja R.K.,T.L.,Magnanti, and J.B.Orlin, Networks Flows: Theory, Algorithms,and Applications;Prentice Hall,Englewood Cliffs, NJ,2001.

2. Higle,J..L. and S.W.Wallace, Sensitivity Analysis and Uncertainty in Linear Programming,Interfaces,33(4),pp.53-66,2003.

3. Akgul,M.,A note on Shadow Prices in linear Programming Journal of the Operations Research Society,35(5),pp,425-431,1984

4. Ali A,R,Helgason,J,Kennington,andH,Lall,Primal Simplex Network Codes:state-of-theartImplementation Technology,Networks,8,pp,315- 339,1978

5. Asher,D,T,A Linear Programming Model for the allocationof R and D efforts,IEEE Transactions on Engineering Management,EM-9(4),PP.154- 157,December 1992.

6. Ballinski,M.L.A Competitive (Dual) Simplex Method for Assignment ProblemMathemetical Programming,34(2),pp.125-141,1986).

7. Barnes,J,W,and R.M.Crisp,Linear Programming: A Survey of General Purpose Algorithms,AIIE Transactions,7(3),pp.212-221,September 1975. [8]. Barr,R,S,F,Glover, and D.Klingman,The Alternative Basis Algorithm for Assignment Problems,Mathematical Programming ,13(1),pp.1- 13,1977

1. Ahuja R.K.,T.L.,Magnanti, and J.B.Orlin, Networks Flows: Theory, Algorithms,and Applications;Prentice Hall,Englewood Cliffs, NJ,2001.

2. Higle,J..L. and S.W.Wallace, Sensitivity Analysis and Uncertainty in Linear Programming,Interfaces,33(4),pp.53-66,2003.

3. Akgul,M.,A note on Shadow Prices in linear Programming Journal of the Operations Research Society,35(5),pp,425-431,1984

4. Ali A,R,Helgason,J,Kennington,andH,Lall,Primal Simplex Network Codes:state-of-theartImplementation Technology,Networks,8,pp,315- 339,1978

5. Asher,D,T,A Linear Programming Model for the allocationof R and D efforts,IEEE Transactions on Engineering Management,EM-9(4),PP.154- 157,December 1992.

6. Ballinski,M.L.A Competitive (Dual) Simplex Method for Assignment ProblemMathemetical Programming,34(2),pp.125-141,1986).

7. Barnes,J,W,and R.M.Crisp,Linear Programming: A Survey of General Purpose Algorithms,AIIE Transactions,7(3),pp.212-221,September 1975. [8]. Barr,R,S,F,Glover, and D.Klingman,The Alternative Basis Algorithm for Assignment Problems,Mathematical Programming ,13(1),pp.1- 13,1977