Un constructeur automobile possède trois usines situées à Paris, Strasbourg et Lyon. Les métaux nécessaires à la fabrication des automobiles arrivent dans les ports du Havre et de Marseille. Les quantités hebdomadaires de métal nécessaires à chaque usine sont respectivement de 400, 300 et 200 tonnes. La quantité hebdomadaire qui arrive au Havre est de 350 tonnes et elle est de 550 tonnes à Marseille. Les coûts de transport d'un port à une usine sont donnés dans le tableau suivant :

Coûts de transport (en euro par tonne)

Le but est de déterminer les poids de métal à envoyer à chaque usine depuis chaque port afin que :

• chaque usine reçoive, au moins, la quantité de métal qu'elle demande

• les quantités demandées à chaque port n'excèdent pas les quantités disponibles

• le coût total de transport soit minimum

C'est typiquement un Problème de Transport.

Si l'on appelle xij le tonnage de métal envoyé depuis le port i jusqu'à l'usine j, les ports et les usines étant numérotés de haut en bas et de gauche à droite on a :

Les contraintes concernant la demande de chaque usine imposent :

Les contraintes sur les ports sont :

Et la fonction à minimiser est :