6.54.6  Résolution d’un problème d’optimisation linéaire : lpsolve

lpsolve a au plus 4 arguments qui sont dans l’ordre :

• obj : expression symbolique representant la fonction objectif,
• constr (optionnel) : liste des contraintes linéaires qui sont soit des équalités, soit des inéequalités, soit des expressions bornées définies par expr=a..b,
• bd (optionnel) : séquence d’expressions du type var=a..b specifiant que la variable var est comprise entre a et b,
• opts (optionnel) : séquence de paramètres option=value pour le solver, où option est choisi parmi assume, lp_maximize, lp_variables, lp_integervariables, lp_binaryvariables or lp_depthlimit.

lpsolve résout un problème d’optimisation linéaire de fonction objectif obj sous contraintes optionnelles constr.
lpsolve trouve le maximum ou le minimum d’une fonction linéaire de plusieurs variables assujétit à vérifier des contraintes qui sont égalités ou des inégalités linéaires mixed integer problems

La valeur renvoyée est de la forme [optimum,soln] où optimum is est la valeu du minimum/maximum de la fonction objectif et soln est la liste des coordonnées correspondant au point pour lequel la valeur optimale est atteinte. Si il n’y a pas de solution, If there is no feasible solution,une liste vide est is retournée. Lorsque la the fonction objectif n’est pas bornée, optimum est +infinity (pour les problèmes de maximisation) ou -infinity (pour les problèmes de minimisation), soln est généralement sans signification.

If obj is given as constant (for example, zero) then only a feasible point is returned as a list, if one exists. If the problem is infeasible, an empty list is returned. This may be used as a test to check whether a set of linear constraints is feasible or not.

The given objective function is minimized by default. To maximize it, include the option lp_maximize=true or simply lp_maximize.

By default, all variables are considered continuous and unrestricted in sign.

The solver combines the two-phase simplex method and the dual simplex method to find the optimal solution.

Problèmes à variables continues

Par exemple, pour résoudre le problem définit en (1), On tape :

On obtient :

Donc, le minimum de f(x,y,z)=2 x+y−z+4 est egal à −4 lorsqu’on impose comme contraintes x leq 1,y geq 2,x+3y−z=2,3x−y+z leq 8,−x+y leq 5 .
La valeur minimum est atteinte au point (x,y,z)=(0,5,13).

Les Contraintes peuvent aussi s’écrire expr=a..b pour des expressions linéaires et bornées.
On tape :

On obtient :

On utilise l’option assume=lp_nonnegativecomme 3ième argument pour spécifier que toutes les variables sont nonnegatives : ce qui est plus simple que d’entrer explicitement des contraintes nonnegatives.
On tape :

On obtient :

Les bornes peuvent être ajoutées séparément pour certaines variables.
On les met alors en 3ième argument. On tape :

On obtient :

Integer programming

Use the assume=integer or assume=lp_integer option to solve integer programming problems. The function lpsolve uses branch and bound method in such cases. The total number of investigated nodes is printed out before the function returns. To limit branch and bound tree depth, use the option :

In that case optimality of the solution can’t be guaranteed. Dans ce cas optimisation de la solution n’est pas garantie.
On tape :

On obtient :

On utilise l’option assume=lp_binary pour spécifier que toutes les variables are binaires, i.e. les seules valeurs autorisées sont 0 et 1.
Généralement, les variables binaires representent vrai et faux, ce qui est compréhensible en logique. On tape :

On obtient :

Options

and

are used for specifying mixed integer/binary programming problems. Also, the

option may be used, which overrides integer and binary settings. For example, a linear programming problem with mostly integer variables may be specified using the option assume=integer and specifying continuous variables with lp_variables, which overrides the global integer setting.

On tape :

On obtient :

Use the assume=lp_nonnegint or assume=nonnegint option to get nonnegative integer values.

On tape :

On obtient :

Entering linear programs in matrix form

The function lpsolve supports entering linear programming problems in matrix form, which is convenient for problems with relatively large number of variables and/or constraints.

To enter a problem in matrix form, the parameter obj must be a vector of coefficients c and constr, which is mandatory this case, must be a list [A,b,A_eq,b_eq] , where A,A_eq are matrices and b,b_eq are vectors of real numbers. Without any other parameters, this minimizes c^T x under conditions A x≤b and A_eq x=b_eq . If a problem does not contain equality constraints, parameters A_eq and b_eq may be omitted. For a problem that does not contain inequality constraints, empty lists must be passed as A and b . Also, constr may be an empty list.

The parameter bd is entered as a list of two vectors b_l and b_u of the same length as the vector c such that b_l≤x≤b_u . For unbounded variables use +infinity or -infinity.

When specifying mixed problems in matrix form, variables are entered as the corresponding indexes, which are 1-based, i.e. the first variable has index 1, the second variable has index 2 and so on. Other options for lpsolve are passed to a problem in matrix form in the same way as if it was in symbolic form.

Input :

Output :

Input :

Output :

Input :

Output :

Input :

Output :