Azizah, Mariyatul (2010) Equivalence of primal and dual simplex algorithms for the maximum flow problem. Undergraduate thesis, Universitas Islam Negeri Maulana Malik Ibrahim.

Text (Fulltext)
06510010.pdf  Accepted Version Available under License Creative Commons Attribution Noncommercial No Derivatives. Download (1MB)  Preview 
Abstract
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 wakematrix 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 GaussJordan 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. GaussJordan 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 equationentering 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.
Item Type:  Thesis (Undergraduate) 

Supervisor:  Rahman, Hairur and Barizi, Ahmad 
Keywords:  Simplex Primal; Simplex Dual; Maximum Flow 
Departement:  Fakultas Sains dan Teknologi > Jurusan Matematika 
Depositing User:  Ika Nur Khasana 
Date Deposited:  19 May 2017 02:21 
Last Modified:  19 May 2017 02:21 
URI:  http://etheses.uinmalang.ac.id/id/eprint/6683 
Actions (login required)
View Item 