Clojure Data Structures and Algorithms Cookbook

Resolving cost and profit optimization problems

For this recipe, we will study optimization problems. For these, you are given a set of constraints on some variables, say:

4x+3y < 30
2x+4y < 10

You are then asked to maximize or minimize a function of these variables, (if constraints are inferior, then you'll have to maximize and vice versa), for example:

max(z=13 x + 7 y)

This is called the objective function. Generally speaking, such problems are called linear programs, and the algorithm used for resolving these is called the simplex algorithm.

However, the simplex algorithm operates on real variables, that is, the variables that take real values. This is problematic if the solution to the problem can only be a compound of natural numbers. For instance, ...