 Open Access
 Authors : Francisco Zaragoza Huerta
 Paper ID : IJERTV11IS010212
 Volume & Issue : Volume 11, Issue 01 (January 2022)
 Published (First Online): 07022022
 ISSN (Online) : 22780181
 Publisher Name : IJERT
 License: This work is licensed under a Creative Commons Attribution 4.0 International License
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 largescale 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 realworld 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 largescale 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 decisionmaking 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 MeiKo 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 
12 
100 
2. Management Office 
16 
600 
3. Particular Office 
23 
300 
4. Social Service Office 
25 
800 
5. Human Resources Office 
34 
400 
6. Computing Center 
45 
500 
7. Benefits Office 
410 
300 
8. Training Center 
56 
600 
9. Legacy Office 
59 
400 
10.Audience Office 
67 
300 
11Workshop 
78 
400 
12.Register Office 
89 
500 
13.Social Communication 
811 
800 
14.Payroll Office 
910 
700 
15.Labor Relations 
1011 
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 WIN237237 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 (Cw*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 (Cw*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;
( cjw*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 (Axb = 0) and if an equation in a problem cannot be adjusted (Axb= 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 largescale software such as GAMS is essential to achieve success in the modeling of largescale 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 largescale software such as GAMS is essential to achieve success in the modeling of largescale network problems, so it is recommended to improve your skills in this area.
REFERENCES

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

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

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

Ali A,R,Helgason,J,Kennington,andH,Lall,Primal Simplex Network Codes:stateoftheartImplementation Technology,Networks,8,pp,315 339,1978

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

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

Barnes,J,W,and R.M.Crisp,Linear Programming: A Survey of General Purpose Algorithms,AIIE Transactions,7(3),pp.212221,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

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

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

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

Ali A,R,Helgason,J,Kennington,andH,Lall,Primal Simplex Network Codes:stateoftheartImplementation Technology,Networks,8,pp,315 339,1978

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

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

Barnes,J,W,and R.M.Crisp,Linear Programming: A Survey of General Purpose Algorithms,AIIE Transactions,7(3),pp.212221,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