Introducción suave a ideas fundamentales para resolver problemas de programación lineal en enteros por medio de matemáticas recreativas

Abstract

THE CUTTING ALGORITHMS OF GOMORY FOR SOLVING LINEAR INTEGER PROGRAMS FIND AN INTEGER SOLUTION TO A LINEAR PROGRAM OBTAINED FROM THE ORIGINAL PROBLEM TO WHICH SOME ""CUTS"" HAVE BEEN ADDED. THE PRESENTATIONS GIVEN IN THE TEXT BOOKS THAT INTRODUCE THESE ALGORITHMS ARE GENERALLY ABSTRACT AND DIFFICULT TO VISUALISE, OFTEN BECAUSE THE TEXTS DO NOT PROVIDE DE TAILED EXAMPLES IN WHICH THE READER CAN SEE CLEARLY WHAT EACH CUT DOES. IN THIS ARTICLE WE USE RECREATIONAL MATHEMATICS (MATH PUZZLES) AND GIVE SEVERAL EXAMPLES OF INCREASING COMPLEXITY TO GETHER WITH THEIR DETAILED SOLUTIONS FOR PROBLEMS IN WHICH POSITIVE INTEGER SOLUTIONS ARE REQUIRED, AS MEANS TO EXPLAINING WHAT IS GOING ON WITH THE CUTS. THE EXAMPLE PROBLEMS ARE SOLVED BY SHOWING THE USEFULNESS OF SOME SIMPLE IDEAS THAT FORCE  THE SOLUTIONS TO BE INTEGERS. SINCE THIS IS THE FUNDAMENTAL NEW IDEA OF GOMORY´S CUTTING ALGORITHMS, GIVEN THAT THE OTHER IDEAS ARE THOSE ALREADY IN USE BY THE SIMPLEX ALGORITHM, THE ARTICLE SHOULD BE USEFUL TO HELP STUDENTS UNDERSTAND BETTER THE CUTTING ALGORITHMS BY ELIMINATING THE MYSTERY GENERATED BY THE EXCESSIVE ABSTRACTION AND THE COMPLEX NOTATION OF THE CORRESPONDING TEXT BOOKS.