La programación lineal con números enteros se basa, como indica su nombre, en la programación lineal, que permite optimizar funciones de primer grado sobre un conjunto definido por inecuaciones de primer grado. El interés de esta técnica reside en que se dispone de algoritmos muy eficaces para resolver cualquier problema que pueda escribirse de esta forma.
Un ejemplo de programación lineal
------------------------------------
La empresa Laivo fabrica productos lácteos al por mayor. El gerente quiere determinar las cantidades de yogur y nata que deben fabricarse antes del cierre anual para maximizar su beneficio en euros (€). La venta de una tonelada (t) de yogur le reporta 500 €, mientras que una tonelada de nata fresca le reporta 450 €. La empresa sabe por experiencia que no venderá más de ocho toneladas de yogur y que la demanda de nata es muy superior a lo que puede producir. El tiempo de producción está limitado a sesenta horas, pues se necesitan seis para producir una tonelada de yogur y cinco para una tonelada de nata. Una vez elaborados, el yogur y la nata se almacenan en un espacio modular limitado a quince unidades de almacenamiento. Se necesita una por tonelada de yogur y dos por tonelada de nata.
