## Methods:

## Definition

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.

Maximize |
c^{T} x |

Subject to |
Ax ≤ b |

x ≥ 0 |

where x is an array **(x _{1}, …, x_{n})**,

**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.

**Positivity**. If in context, we have a lower nonzero bound

**x ≥ k**, from

**y = x-k**and

**y ≥ 0**. If there is no lower bound, we can always ask

**x = y-z**with

**y ≥ 0**and

**z ≥ 0**.

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?

**LP:**

maximum 50x + 70yS.C 40x +30y ≤ 36020x + 30y ≤ 480x,y≥ 0

## Solutions

Only four cases can occur:

- If the definition domain is empty, the problem is not realizable;
- otherwise: the problem is unbounded, the optimum does not exist;
- or: the problem has a unique optimal solution coinciding with an extreme point (a vertex) of the definition domain;
- or: the problem has an infinity of solutions forming a face or an edge of the definition domain.