Prot ines

Aliment

0.02

0.09

Orge

0.06

0.60

Arachide

Co t

(EUR / kg)

1.5

4.5

x1 = grammes dorge par portion

x2 = grammes darachide par portion

Objectif

min z = 0.0015x1 + 0.0045x2

Contraintes

Quantit totale : x1 + x2 e 400

Prot ines : 0.09x1 + 0.6x2 e 0.3(x1 + x2)

Fibres : 0.02x1 + 0.06x2 d 0.05(x1 + x2)

Non-n gativit : x1, x2 e 0

7

3.3 Forme standard et forme canonique dun programme lin aire

Forme standard

D nition 5 (Forme standard). Un programme lin aire est sous forme standard lorsque toutes ses contraintes sont

des galit s et toutes ses variables sont non-n gatives.

Repr sentation matricielle

max

cT x

s.c. Ax = b

x e 0

n variables, m contraintes, m < n, c, x Rn,

b Rm, A Rm n.

Forme canonique

D nition 6 (Forme canonique). Un programme lin aire est sous forme canonique lorsque toutes ses contraintes

sont des in galit s et toutes ses variables sont non-n gatives.

Repr sentation matricielle

max

cT x

s.t. Ax d b

x e 0

n variables, m contraintes, c, x Rn,

Th or me 1 (Equivalence des formes standard et canonique). Tout programme lin aire peut s crire sous forme

standard et sous forme canonique.

b Rm, A Rm n.

D monstration.

Une containte din galit aT x d b peut tre transform e en galit par lintroduction dune variable d cart :

Une contrainte d galit aT x = b peut tre remplac e par deux in galit s :

aT x + s = b,

s e 0.

aT x d b

aT x d b

aT x e b aT x d b.

min cT x = max cT x.

Variable x non restreinte : substitution par deux variables (partie positive et n gative)

Il existe toujours une solution optimale telle que x+ = 0 ou x = 0.

x = x+ x

x+, x e 0.

8

Forme standard du probl me de production de peinture

max z = 5x1 + 4x2

s.c.6x1 + 4x2 d 24

x1 + 2x2 d 6

x2 d 2

x2 x1 d 1

x1, x2 e 0

Forme standard

max z = 5x1 +4x2

s.c.

6x1 +4x2 +s1

x1 +2x2

+s2

= 24

= 6

= 2

+s4 = 1

s1, s2, s3, s4 e 0

+s3

x2

x1 +x2

x1, x2,

Forme matricielle

max

cT x

s.t. Ax = b

x e 0

c =

5

4

0

0

0

0

, x =

x1

x2

s1

s2

s3

s4

, A =

6

1

0

1

4

2

1

1

1

0

0

0

0

1

0

0

0

0

1

0

0

0

0

1

, b =

24

6

2

1

Variables pouvant prendre des valeurs n gatives

Exemple 5 (Vente de hamburgers).

Un fast-food vend des hamburgers et des cheeseburgers. Un hamburger utilise 125 g. de viande alors quun

cheeseburger nen utilise que 100 g.

Le fast-food d marre chaque journ e avec 10 kg de viande mais peut commander de la viande suppl mentaire

avec un co t additionnel de 2 EUR par kg pour la livraison.

Le prot est de 0.02 EUR pour un hamburger et 0.015 EUR pour un cheeseburger.

La demande ne d passe pas 900 sandwiches / jour, et les surplus de viande sont donn s au Restos du Coeur.

Combien le fast-food doit-il produire de sandwiches de chaque type par jour ?

Variables

x1 = nombre de hamburgers / jour x2 = nombre de cheeseburgers / jour

Contraintes

Commande de viande suppl mentaire :

Le co t pour la viande suppl mentaire appara t seulement si x3 < 0.

125x1 + 100x2 + x3 = 10000,

x3non restreint

9

Substitution de x3 par 2 variables non-n gatives :

x3 = x+

3 x

125x1 + 100x2 + x+

3 , x+

3 , x

3 x

3 e 0

3 = 10000

Borne sup rieure sur les ventes : x1 + x2 d 900.

Mod le complet

max z = 0.02x1 + 0.015x2 0.002x

3

3 x

3

125x1 + 100x2 + x+

s.c.

x1 + x2

x1, x2, x+

3 , x

3

= 10000

d 900

e 0

Remarque : Il existe une solution optimale telle que x+

3 = 0 ou x

3 = 0.

3.4 R solution de programmes lin aires

3.4.1 R solution graphique

Repr sentation graphique

Production de peinture

sous les contraintes :

max z = 5x1 + 4x2

6x1 + 4x2 d 24

x1 + 2x2 d 6

x2 d 2

x2 x1 d 1

x1 e 0

x2 e 0

10

(1)

(2)

(3)

(4)

(5)

(6)

(5)(1)(2)(6)(4)(3)G om trie des solutions

Ensemble des solutions admissibles

Poly dre (ABCDEF)

Courbes de niveaux de lobjectif

Ensemble de solutions ayant un prot (valeur de lobjectif) donn : intersection entre une droite et le poly dre.

Am lioration de la solution

Recherche dune direction dans laquelle le prot z augmente.

R solution graphique (Production de peinture)

Recherche de la solution optimale

La droite mobile doit garder une intersection avec lensemble des solutions admissibles.

Solution optimale : x1 = 3, x2 = 1.5 (E)

La solution optimale est un sommet du poly dre.

Cette observation est la base de lalgorithme du simplexe.

11

ABCDEFz=10ABCDEFz=21R solution graphique (Diet problem)

Diet problem

sous les contraintes

Solution optimale

min z = 0.0015x1 + 0.0045x2

x1 + x2 e 400

0.21x1 0.30x2 d 0

0.03x1 0.01x2 e 0

x1 e 0

x2 e 0

x1 =

4000

17

(cid:39) 235.3 x2 =

2800

17

(cid:39) 164.7

z =

186

170

(cid:39) 1.094

3.4.2 La m thode du simplexe

Id es de base

Solution optimale : sommet (point extr me).

Id e fondamentale du simplexe : d placement de sommet en sommet adjacent de mani re am liorer la fonction

objectif.

Transformation des in galit s en galit s : forme standard du programme lin aire - syst me de m quations

n inconnues (m < n).

Identication alg brique des sommets : correspondance avec les bases dun syst me d quations.

Solutions de base

Syst me de m quations lin aires n inconnues (m < n) : innit de solutions.

Si on xe z ro n m variables : syst me de m quations m inconnues poss dant une solution unique (si la

matrice est inversible). Cest une solution de base.

D nition 7 (Solution de base). Une solution de base dun programme lin aire est la solution unique du syst me

de m quations m inconnues obtenu en xant z ro n m variables (pourvu que la matrice du syst me soit

inversible).

Les variables x es z ro sont appel es variables hors base et les autres variables en base.

12

Exemple 6 (Production de peinture). Prenons B = {s1, s2, s3, s4}.

z = 0 +5x1 +4x2

s1 = 24 6x1 4x2

s2 = 6 x1 2x2

s3 = 2

x2

s4 = 1 +x1 x2

Si x1 = x2 = 0, alors s1 = 24, s2 = 6, s3 = 2, s4 = 1. Toutes ces valeurs sont non-n gatives et la solution est

r alisable.

D nition 8 (Solution de base r alisable). Une solution de base telle que toutes les variables prennent des valeurs

non-n gatives est appel e solution de base r alisable.

G om trie des solutions de base

Prenons B = {s1, s2, s3, s4} x1 = x2 = 0, s1 = 24, s2 = 6, s3 = 2, s4 = 1.

Cette solution de base r alisable correspond au sommet (0, 0).

Base

{s1, s2, s3, s4}

{x1, s2, s3, s4}

{s1, x1, s3, s4}

{x1, x2, s3, s4}

Solution Objectif

(0, 0)

(4, 0)

(6, 0)

(3, 1.5)

0

20

21

Sommet

A

F

Non r alisable

E

Th or me 2. Toute solution de base r alisable correspond un sommet du poly dre.

D termination de la solution de base optimale

n!

Nombre maximum de solutions de base :

m!(nm)!

Algorithme "b te et m chant" : num ration de toutes les bases.

M thode du simplexe : partir dune solution de base admissible et passer une solution de base voisine qui

am liore la valeur de lobjectif.

Solution voisine : changement dune variable en base.

3 etapes :

1. D termination de la variable entrante.

2. D termination de la variable sortante.

3. Pivotage.

Lalgorithme du simplexe

Variable entrante

z = 0 +5x1 +4x2

s1 = 24 6x1 4x2

s2 = 6 x1 2x2

s3 = 2

x2

s4 = 1 +x1 x2

Si x1 (ou x2) augmente (entre en base), la valeur de la fonction objectif z augmente.

Quelle est la valeur maximale de x1 ?

13

ABCDEF Contraintes : les autres variables doivent rester positives.

Variable sortante

s1 = 24 6x1 e 0 x1 d 4

s2 = 6 x1 e 0 x1 d 6

e 0 2 e 0

s3 = 2

s4 = 1 +x1 e 0 x1 e 1

x1 d 4

toujours!

toujours!

Pivotage

Si x1 = 4, alors s1 = 0.

x1 entre en base, s1 sort de la base.

Substitution :

Nouveau syst me :

x1 = 4

1

6

s1

2

3

x2

z = 20 5

x1 = 4 1

s2 = 2 + 1

s3 = 2

s4 = 5 1

6 s1 + 2

6 s1 2

6 s1 4

3 x2

3 x2

3 x2

x2

3 x2

6 s1 5

Equations du simplexe

B = indices des variables en base, N = indices des variables hors base.

Notation :

z = z +

xl = bl

(cid:88)

kN

(cid:88)

kN

ckxk

alkxk

l B

ck : prot marginal ou co t r duit.

R gles de pivotage

Variable entrante

Choisir la variable k hors base avec le prot marginal maximum (max z) ou le co t r duit minimum (min z).

max z k = arg max

iN

min z k = arg min

iN

ci

ci

Si ck d 0 (max) ou ck e 0 (min) pour tout k N , solution optimale, STOP.

Variable sortante

Choisir la variable l en base telle que

z = 0 +5x1 +4x2

s1 = 24 6x1 4x2

s2 = 6 x1 2x2

s3 = 2

x2

s4 = 1 +x1 x2

l = arg min

jB:ajk>0

bj

ajk

Si alk d 0 pour tout l B, probl me non born , STOP.

14

z = 0 +5x1 +4x2

s1 = 24 6x1 4x2

s2 = 6 x1 2x2

x2

s3 = 2

s4 = 1 +x1 x2

aij

(cid:48) =

(cid:48)

bi

=

alj

alk

aij

bl

alk

bi

i = l

i (cid:54)= l

aikalj

alk

i = l

i (cid:54)= l

aikbl

alk

z = 20 5

x1 = 4 1

s2 = 2 + 1

s3 = 2

s4 = 5 1

6 s1 + 2

3 x2

6 s1 2

3 x2

4

3

x2

6 s1 5

3 x2

6 s1

x2

Pivotage

z = 0 +5x1 +4x2

s1 = 24 6x1 4x2

s2 = 6 x1 2x2

s3 = 2

x2

s4 = 1 +x1 x2

z = 21 3

x1 = 3 1

2 + 1

x2 = 3

2 1

s3 = 1

2 3

s4 = 5

4 s1 1

4 s1 + 1

8 s1 3

8 s1 + 3

8 s1 + 5

2 s2

2 s2

4 s2

4 s2

4 s2

15

Pr sentation en tableau

Pr sentation compacte pour effectuer les calculs sans r p ter les syst mes d quations.

It ration 1

It ration 2

It ration 3

s2

0

0

1

0

0

s2

0

0

1

0

0

s3

0

0

0

1

0

s3

0

0

0

1

0

s4 Solution

0

0

0

0

1

0

24

6

2

1

s4 Solution

0

0

0

0

1

20

4

2

2

5

Var. en base

z

s1

s2

s3

s4

x1

z

5

1

6

0

1

0

0

0

0 1

x2

4

4

2

1

1

s1

0

1

0

0

0

x1 x2

2

0

1

0

0

0

2

3

4

s1

3 5

6

1

6

3 1

6

0

1

1

5

6

3

Var. en base

z

x1

s2

s3

s4

z

1

0

0

0

0

Var. en base

z

x1

x2

s3

s4

z

1

0

0

0

0

2

x1 x2

0

1

0

0

0

s1

s2

0 3

4 1

4 1

1

0

1 1

8

1

0

0

8 3

8 5

3

4

4

2

4

3

s3

0

0

0

1

0

s4 Solution

0

0

0

0

1

21

3

3

2

1

2

5

2

3.4.3 La m thode des deux phases

Solution initiale articielle

Une solution de base admissible nest pas toujours connue a priori.

Certains probl mes nadmettent pas de solution admissible, donc il est impossible de trouver une base de d part.

La m thode des deux phases va permettre de d terminer une base admissible ou prouver que le probl me est

impossible.

Exemple 7 (M thode des 2 phases).

min z = 4x1 +x2

3x1 +x2

= 3

s.c.

4x1 +3x2 e 6

x1 +2x2 d 4

x1,

e 0

x2

Introduction des variables d cart

min z = 4x1 +x2

3x1 +x2

s.c.

4x1 +3x2 x3

x1 +2x2

x2,

x1,

x3,

= 3

= 6

+x4 = 4

x4 e 0

16

Pas de base admissible "triviale".

On voudrait voir appara tre une matrice identit .

Introduction de variables articielles.

+x2

Introduction des variables articielles

min z = 4x1

min r =

min r = 7x1 4x2 +x3

3x1

+x2

s.c.

4x1 +3x2 x3

+2x2

x1

x2,

x1,

R1 +R2

+R1

+R2

x3, R1, R2,

+9

= 3

= 6

+x4 = 4

x4 e 0

R1, R2 et x4 peuvent tre utilis es comme base de d part admissible.

Base pour le syst me de d part si R1 = R2 = 0 (hors base).

R crire lobjectif en fonction des variables hors base !

3.4.4 Cas particuliers

Solutions optimales multiples

Si la fonction objectif est parall le une contrainte active pour la solution optimale, la m me valeur de lobjectif

peut tre prise par plusieurs solutions admissibles.

Il y a une innit de solutions optimales dans ce cas (toutes les combinaisons convexes de sommets optimaux).

Cela se traduit par un prot marginal nul pour une ou plusieurs variables hors base.

Exemple 8 (Solutions optimales multiples).

max z = 2x1 +4x2

s.c.

x1 +2x2 d 5

d 4

x1 +x2

e 0

x2

x1,

Var. en base

z

x1 x2

s1

s2

Solution

z

s1

s2

z

x2

s2

z

x2

x1

1

0

0

1

0

0

1

0

0

2

1

1

0

1

2

1

2

0

0

1

4

2

1

0

1

0

0 2

1

1

2

0 1

2

0 2

0

0

1

0

0

1

0

1

0 1

1 1

2

0

5

4

10

5

2

3

2

10

1

3

Solution optimale :

x1 = 0 + 3(1 ) = 3 3

3

2

2 + 1(1 ) = 1 +

x2 = 5

(0 d d 1)

Probl mes non born s

Certains probl mes sont non born s dans une direction donn e.

Si cette direction est une direction dam lioration de la fonction objectif, celle-ci peut prendre une valeur arbi-

trairement grande !

17

Exemple 9 (Probl mes non born s).

max z = 2x1 +x2

s.c.

x1 x2 d 1

d 4

2x1

x1,

x2 e 0

Var. en base

z

z

s1

s2

1

0

0

x1

2

x2

1

1 1

0

2

s1

s2

Solution

0

1

0

0

0

1

0

1

4

Tous les coefcients (sauf le prot maginal) dans la colonne de x2 sont n gatifs ou nuls.

Cela signie que toutes les contraintes de non-n gativit sont satisfaites quelle que soit la valeur de x2.

Lobjectif peut donc augmenter ind niment.

Probl mes impossibles

Le syst me de contraintes peut navoir aucune solution.

G n ralement, provient dune mauvaise formulation du probl me.

Exemple 10 (Probl mes impossibles).

max z = 3x1 +2x2

2x1 +x2

d 2

s.c.

3x1 +4x2 e 12

x1,

e 0

x2

18

4 Dualit

4.1 Le probl me dual

Probl me primal et probl me dual

Probl me primal

max

cT x

s.c. Ax = b

x e 0

n variables, m contraintes, m < n, c, x Rn,

b Rm, A Rm n.

Probl me dual

min

s.c.

bT y

AT y e c

(y non restreint)

m variables, n contraintes, m < n, c Rn,

Exemple 11 (Probl me primal et dual - forme standard).

b, y Rm, A Rm n.

Probl me primal :

Probl me dual :

max z = x1 +x2

s.c.

2x1 +x2 = 5

3x1 x2 = 6

x2 e 0

x1,

(y1)

(y2)

min w = 5y1 +6y2

s.c

2y1 +3y2 e 1

y1 y2 e 1

(x1)

(x2)

Propri t s et r gles de construction du dual

Th or me 3. Le probl me dual du probl me dual est le probl me primal.

R gles de construction

Probl me max

Contrainte

d

=

Variable

e 0

non restreinte

Probl me min

Variable

e 0

non restreinte

Contrainte

e

=

Exemple 12 (Probl me primal et dual - forme g n rale).

Probl me primal :

max z = 5x1 +12x2 +4x3

s.c.

x1 +2x2 +x3 d 10

2x1 x2 +3x3 = 8

e 0

x1,

x2,

x3

(y1)

(y2)

19

Probl me dual :

min w = 10y1 +8y2

s.c

y1 +2y2 e 5

2y1 y2 e 12

y1 +3y2 e 4

e 0

y1

(x1)

(x2)

(x3)

4.2 Relations primal/dual

Th or me 4 (Dualit faible). Consid rons la paire primale-duale :

max

cT x

s.c. Ax = b

x e 0

bT y

min

s.c. AT y e c

Si x est une solution admissible du primal et y une solution admissible du dual, alors

cT x d bT y

Sil y a galit , alors x est une solution optimale du primal et y une solution optimale du dual.

Th or me 5 (Dualit forte). Consid rons la paire primale-duale :

max

cT x

s.c. Ax = b

x e 0

bT y

min

s.c. AT y e c

Si le primal et le dual admettent tous les deux une solution admissible, ils ont tous deux une solution optimale

nie et la m me valeur objectif optimale.

Si le primal (dual) est non born , le dual (primal) nadmet pas de solution admissible.

Th or me 6 (Compl mentarit ). Consid rons la paire primale-duale :

max

cT x

s.c. Ax = b

x e 0

bT y

min

s.c. AT y e c

20

Si x est une solution optimale du primal et y une solution optimale du dual, alors

o ai est la i- me colonne de A.

En dautres termes :

xi(aT

i y ci) = 0.

xi > 0 aT

aT

i y > ci xi = 0.

i y = ci,

Exemple 13 (R solution du dual par les r gles de compl mentarit ).

Primal (P ) :

max z = 5x1 +12x2 +4x3

s.c.

x1 +2x2 +x3 d 10

2x1 x2 +3x3 = 8

e 0

x1,

x2,

x3

(y1)

(y2)

Dual (D) :

Solution optimale de (P ) :

min w = 10y1 +8y2

s.c

y1 +2y2 e 5

2y1 y2 e 12

y1 +3y2 e 4

e 0

y1

(x1)

(x2)

(x3)

(x1, x2, x3) =

z =

(cid:19)

,

12

5

, 0

(cid:18) 26

5

274

5

x1 > 0 y1 + 2y2 = 5

x2 > 0 2y1 y2 = 12

Solution optimale de (D) :

(y1, y2) =

,

(cid:19)

2

5

(cid:18) 29

5

274

5

w =

4.3

Interpr tation conomique de la dualit

La forme canonique dun programme lin aire peut tre interpr t e comme un probl me dallocation de res-

sources.

Paire primale-duale :

max

cT x

s.c. Ax d b

x e 0

bT y

min

s.c. AT y e c

y e 0

21

Donn es :

cj : prot par unit dactivit j.

bi : disponibilit de la ressource i.

aij : consommation de la ressource i par unit dactivit j.

Variables :

xj : niveau de lactivit j.

yi : valeur dune unit de la ressource i.

Interpr tation de la dualit faible

z d w :

prot d valeur des ressources

Interpr tation de la dualit forte

Le prot maximal est atteint si les ressources ont t exploit es compl tement, i.e. jusqu puisement de leur

valeur.

Exemple 14 (Dualit dans le probl me de production de peinture).

max z = 5x1 +4x2

s.c

6x1 +4x2 d 24

x1 +2x2 d 6

d 2

x2

x1 +x2 d 1

e 0

x2

x1,

min w = 24y1 +6y2 +2y3 +y4

6y1 +y2

y4 e 5

4y1 +2y2 +y3 +y4 e 4

y4 e 0

y3,

y1,

y2,

x1 = 3, x2 = 1.5, z = 21

y1 = 0.75, y2 = 0.5, y3 = y4 = 0, w = 21

Le prot augmente de 0.75 par augmentation dune tonne de M1 et de 0.5 par tonne de M2. (Localement. Dans

quelles limites ? Voir analyse de sensibilit )

Les "ressources" 3 et 4 sont abondantes, augmenter ces ressources napporte aucun prot suppl mentaire.

22

5 Solveurs et langages de mod lisation

Exemple 15 (Production de jouets).

Une soci t de jouets produit des trains, des camions et des voitures, en utilisant 3 machines.

Les disponibilit s quotidiennes des 3 machines sont 430, 460 et 420 minutes, et les prots par train, camion et

voiture sont respectivement EUR 3, EUR 2 et EUR 5.

Les temps n cessaires sur chaque machine sont :

Machine

1

2

3

Train Camion Voiture

2

0

4

1

3

1

1

2

0

Primal

max z = 3x1 +2x2 +5x3

s.c.

x1

3x1

x1

x1,

+2x2 +x3 d 430

+2x3 d 460

d 420

e 0

+4x2

x2,

x3

Dual

x1 = 0

x2 = 100

x3 = 230

z = 1350

min w = 430y1 +460y2 +420y3

s.c.

y1

2y1

y1

y1,

+3y2

+2y2

y2,

+y3

e 3

+4y3 e 2

e 5

e 0

y3

y1 = 1

y2 = 2

y3 = 0

Var. en base

z

x2

x3

s3

x1

z

1 4

0 1

4

3

0

2

2

0

x2 x3

0

1

0

0

s2

s1

0 1 2

2 1

1

0

0

1

0 2

1

2

1

4

s3 Solution

0 1350

0

0

1

100

230

20

Base : B = {x2, x3, s3}.

Solveurs

Logiciels pour r soudre des programmes lin aires :

Ind pendants :

Commerciaux : CPLEX (www.ilog.com), XPRESS-MP (www.dash.co.uk), . . .

Gratuits : PCx, lpsolve, glpk, . . .

Tableurs : La plupart des tableurs int grent un outil de r solution de programmes lin aires (Excel, Gnumeric,

. . .)

Langages de mod lisation (ampl, GNU MathProg, mpl, OPL studio, mosel, . . .) : langages de haut niveau

permettant la s paration mod le/donn es, se chargeant de linterface avec un solveur.

23

NAME

ROWS

L

L

L

N

R0001

R0002

R0003

R0004

COLUMNS

C0001

C0001

C0001

C0001

C0002

C0002

C0002

C0003

C0003

C0003

RHS

B

B

B

ENDATA

toys

R0001

R0002

R0003

R0004

R0001

R0003

R0004

R0001

R0002

R0004

R0001

R0002

R0003

1

3

1

3

2

4

2

1

2

5

430

460

420

FIGURE 1 Exemple de production de jouets au format MPS

Solveurs ind pendants

Avantages

Puissance, efcacit

Int grables dans des applications via des librairies

D savantages

Formats de chiers (MPS)

Pas de s paration mod le / donn es

R -utilisation difcile des mod les

Solveurs int gr s aux tableurs

Avantages

Disponibles sur (quasi) tous les ordinateurs

Interface facile dutilisation

Pr sentation des donn es / r sultats

D savantages

Difcult dimpl menter de grands mod les

S paration mod le / donn es difcile

Solveurs moins efcaces (en g n ral)

Langages de mod lisation

Avantages

S paration mod le / donn es

R -utilisabilit des mod les

Ind pendance mod le / solveur

24

#

Data definition

#

set Toys;

param nMachines;

set Machines := 1..nMachines;

param profit {Toys};

param time {Machines,Toys};

param avail {Machines};

#

Variables

#

var prod {Toys} >= 0;

#

Objective

#

maximize total_profit:

sum{t in Toys} profit *prod ;

#

Constraints

#

subject to machine_usage {m in Machines}:

sum{t in Toys} time * prod <= avail ;

FIGURE 2 Exemple de production de jouets au format AMPL (mod le)

D savantages

Apprentissage du langage

Prix des versions commerciales

Limitation en taille des versions dessai gratuites

Moindre efcacit (actuellement) des solveurs gratuits

25

#

Data

#

data;

set Toys := Trains, Trucks, Cars ;

param nMachines := 3;

param profit :=

Trains

Trucks

Cars

3

2

5 ;

param time : Trains Trucks Cars :=

1 1 2 1

2 3 0 2

3 1 4 0 ;

430

param avail :=

1

2 460

3 420 ;

end;

FIGURE 3 Exemple de production de jouets au format AMPL (donn es)

26

Troisi me partie

Programmation en nombres entiers et optimisation

combinatoire

6 D nitions et exemples

Programmation en nombres entiers

Programmes lin aires dans lesquels certaines (ou toutes les) variables sont restreintes des...