Equivalence of primal and dual simplex algorithms for the maximum flow problem

ENGLISH:

Simplex algorithm is a mathematical procedure for solving linear programming problems over and over with a way to test the angle points that meet the constraints to find the extreme point of the corner points that will maximize or minimize the objective function.

Mathematical model of linear programming problems must first be modified in order to wake-matrix contains the identity of mathematics must be solved by using simplex algorithm. Building a slack variable is formed by bringing mathematics, surplus variables and variables in the form of artificial constraints that limit the need and requirement. In this case, the presence of an artificial variable as a variable which is zero at the optimal solution requires the use of a number M, ie a very large number of often called "Big M, the coefficient of artificial variables in the objective function. If the objective function is maximized, then - M is the coefficient of artificial variables. Conversely, if the objective function is minimized, then + M is the coefficient.

Optimality condition: Entering Variable in maximizing (minimize) is a variable coefficient non basis the most negative (positive) in the equation destination z. Coefficient with the same value can be chosen arbitrarily. Optimum value is achieved if all the coefficients in the equation z non basic nonnegative (non positive). Feasibility conditions: either to maximize or minimize problem, the leaving variable is the current basic variables that have the smallest cut point (the minimum ratio in the denominator is strictly positive) to the variable entries. The same value can be chosen arbitrarily.

Pivot variable can be determined using Gauss-Jordan elimination. This method begins by identifying the columns under variable was included as an entry field (trespassing colomn). Lines associated with the variable of the equation called the pivot and elements in the intersection between the entrance and common pivot column called pivot elements. Gauss-Jordan method to make a change on the basis of the use of two types of calculations:
1. pivot equation:
new pivot equation= last pivot equation/ pivot element
2. all other equations including z
new equation= (last equation-entering colomn coefisien) x new pivot equation
Both types of calculations are basically looking for a new basic solution by substituting out the variables included in all equations, except in the pivot variable.