- Linear Programming (LP) problems: linear constraints and objective function, continuous variables.
- Mixed Integer Programming (MIP) problems: LP problems with some or all variables restricted to taking integral values.
Figure 16.1: Classification of MP problems
Figure 16.2 shows an example of an MP problem. It is a transportation problem where several plants (1-3) have varying product producing capacities that must be transported to various clients (A-D), each requiring various amounts of the product. The per-unit cost of transporting the product to the clients also varies. The problem is to minimise the transportation cost whilst satisfying the demands of the clients.
Figure 16.2: An Example MP Problem
A1 + A2 + A3 | = | 21 |
B1 + B2 + B3 | = | 40 |
C1 + C2 + C3 | = | 34 |
D1 + D2 + D3 | = | 10 |
A1 + B1 + C1 + D1 | ≤ | 50 |
A2 + B2 + C2 + D2 | ≤ | 30 |
A3 + B3 + C3 + D3 | ≤ | 40 |