In Operational Research (OR), modeling a problem consists in identifying:
- Intrinsic variables
- the different constraints to which these variables are subjected
- the objective (optimization) called objective function.
|Subject to||Ax ≤ b|
|x ≥ 0|
where x is an array (x1, …, xn), c and b avec array of coefficients, A is a matrix of size m*n. The inequalities Ax ≤ b and x ≥ 0 (positivity of variables) are constraints. The domain of definition is a convex polytope. The linear program is said in standard form if it concerns equality constraints.
To summarize, linear programming is composed of four elements:
- decision variables
- an objective function
- constraints about ressources
- constraintes about type of variables
To formulate a problem from a specification, it is necessary to follow the four preceding points in the order.
Example. Either a factory that produces two types of keyboard which are sold 50£ and 70£ per unit. To build a type 1, we need 40 min of labor and 20 min of machining. For the type 2, we need 30 min of labor and 30 min of machining. The workforce works 6 hours a day while the machine is available 8 hours a day. How many units of each type should be produced to maximize profits?