Determinación de la intersección entre una hipercaja y un hiperplano basada en la modificación al método Simplex

Abstract

This project presents an application that allows solving the problem to determine the intersections between a hyper-box and a hyper-plane; For this, an implementation is proposed using linear programming tools, based on the simplex method. This method is modified by changing some of the principles that govern the Simplex, such as the criterion of optimality, gain, feasibility and the criterion of unemployment, according to the particular needs presented in this work, the solution method will take By name HHI (by its acronym in English Hyperbox and Hyperplane Inter- section). The ultimate goal of HHI is to determine all intersection vertices between the two geometric bodies according to the modified criteria. For the above, the proposed algorithm is based on an elimination process that is generated on the basis of a DFS algorithm on a blind search, so it is used to move between the intersecting vertices that are associated To the feasible basic solutions of the problem. As a first step the proposal of this project is to use the simplex method (MSVNB), to reach a first point of intersection between a hyper-box and a hyper-plane for this uses a table containing only non-basic variables in its columns, In addition to an auxiliary unitary column to carry out the operations. This implies that the number of operations that are commonly performed in the simplex method decrease.

En este proyecto se presenta una aplicación que permite resolver el problema para determinar las intersecciones entre una híper caja y un híper plano; para ello se propone una implementación mediante herramientas de programación lineal, tomando como base el método simplex. Dicho método se modifica cambiando algunos de los principios por los que se rige el Simplex, como lo son el criterio de optimalidad, ganancia, factibilidad y el criterio de paro, de acuerdo a las necesidades particulares que se presentan en este trabajo el método solución llevara por nombre HHI (por sus siglas en inglés Hyperbox and Hyperplane Inter- section). El objetivo final de HHI es determinar todos los vértices de intersección entre los dos cuerpos geométricos de acuerdo a los criterios modificados. Para lo anterior, el algoritmo propuesto se basa en un proceso de eliminación que se genera en base a un algoritmo recorrido de grafos a profundidad (DFS) sobre una búsqueda ciega, por lo que es utilizado para trasladarse entre los vértices de intersección que están asociados a las soluciones básicas factibles del problema. Como primer paso la propuesta de este proyecto consiste en utilizar el método simplex (MSVNB), para llegar a un primer punto de intersección entre una híper caja y un híper plano para esto utiliza una tabla que contenga únicamente las variables no básicas en sus columnas, además de una columna unitaria auxiliar para realizar las operaciones. Esto implica que el número de operaciones que comúnmente se llevan a cabo en el método simplex disminuyan.