Please use this identifier to cite or link to this item:
https://hdl.handle.net/2445/178481
Title: | Introducción a la programación lineal y entera: métodos del Sı́mplex y de B&B |
Author: | Elizalde Masiá, Arturo |
Director/Tutor: | Romano Rodríguez, Susana |
Keywords: | Programació lineal Treballs de fi de grau Programació en nombres enters Linear programming Bachelor's theses Integer programming |
Issue Date: | 21-Jun-2020 |
Abstract: | [en] Since Dantzig published the simplex method in 1949 for the solution of linear programming problems (area of optimization) a great interest was sparked that allowed a vast theoretical growth, opening the door to the development of new methods and algorithms that are widely used today. The main goal of this work is to address, at an introductory level, the simplex method and the Branch and Bound method (or $\mathrm{B\&B}$ ). If $x=\left(x_{B}, x_{N}\right)$ is a basic feasible solution of a linear programming problem $\min \{f(x) \mid A x=b, x \geq 0\}$ with no degenerate solutions, throughout the iterative algorithm of the simplex it is determined through a finite quantity of steps whether the problem is already within an optimal solution, whether a finite optimal solution does not exist, or whether it determines the optimal solution. The Branch and Bound method is used for solving linear programming problems in which the solution (or part of it) must be an integer. The algorithm follows a binary tree structure and under ideal conditions finishes in a finite quantity of steps. |
Note: | Treballs Finals de Grau de Matemàtiques, Facultat de Matemàtiques, Universitat de Barcelona, Any: 2020, Director: Susana Romano Rodríguez |
URI: | https://hdl.handle.net/2445/178481 |
Appears in Collections: | Treballs Finals de Grau (TFG) - Matemàtiques |
Files in This Item:
File | Description | Size | Format | |
---|---|---|---|---|
178481.pdf | Memòria | 639.98 kB | Adobe PDF | View/Open |
This item is licensed under a
Creative Commons License