4.5 The Simplex Algorithm

The simplex algorithm is a well-known algorithm for solving linear programming problems. These are problems of maximizing a utility function or a cost function subject to a number of linear constraints. The linear programming model is as follows: Maximize

4.40 equation

subject to the set of constraints

4.41 equation

The simplex algorithm searches for vertices of a polytope that defines the accessible region of the solution space. One goes from vertex to vertex to find the solution. The algorithm assumes nonnegativity. Inequalities are converted into equalities by adding slack variables. Let us take the following example. This example is taken from Design and Planning of Engineering Systems [13] (Fig. 4-7). Maximize

4.42 equation

subject to the constraints

4.43 equation

and the nonnegativity constraint c04-math-0345 and c04-math-0346. For each one of the constraints, we add a slack variable , , or . We therefore convert ...

Get Multi-Agent Machine Learning now with O’Reilly online learning.

O’Reilly members experience live online training, plus books, videos, and digital content from 200+ publishers.