Linear programming

Methods:


All lectures and exercises can be found at the following link: Lessons, tutorials, etc.

 

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.
In a linear programming problem (PL) the constraints and the objective are linear functions. We note them in the following way (pure canonical form):
Maximize    cT x
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.

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.
Any standard problem can be written in canonical form and vice versa. An equality constraint is broken down into two inequality constraints. An inequality constraint is written in the form of equality by adding a variance variable.
A solution x’ is feasible if it satisfies all the constraints.

To summarize, linear programming is composed of four elements:

  1. decision variables
  2. an objective function
  3. constraints about ressources
  4. 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 ≤ 360    20x + 30y ≤ 480    x,y≥ 0

Solutions

Only four cases can occur:

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