Page 1

La forme canonique du problème est caractérisée par les trois caractéristiques suivantes : 1) un système homogène de contraintes sous la forme d'un système d'équations ; 2) des conditions homogènes de non-négativité qui s'appliquent à toutes les variables impliquées dans le problème, et 3) la maximisation, fonction linéaire. Dans ce problème, ces trois fonctionnalités sont violées.

La forme canonique du problème est caractérisée par les trois caractéristiques suivantes : 1) un système homogène de contraintes sous la forme d'un système d'équations ; 2) des conditions homogènes de non-négativité qui s'appliquent à toutes les variables impliquées dans le problème, et 3) la maximisation d'une fonction linéaire. Dans ce problème, ces trois fonctionnalités sont violées.

Forme canonique du problème programmation linéaire est pratique dans la mesure où le sommet initial de la région réalisable peut être facilement trouvé.

Considérons la forme canonique du problème de programmation linéaire et la méthode d'élimination de Jordan-Gauss.

La forme canonique d’un problème de programmation linéaire est souvent pratique.

Lors de la transformation du système de contraintes en Forme canonique problèmes de programmation linéaire, les inégalités (12) et (13) doivent être remplacées par des égalités. Pour ce faire, des variables supplémentaires non négatives sont introduites.

Montrer que les matrices réelles commutant par paires sont simultanément réduites à la forme canonique du problème 1128 par une transformation de similarité utilisant une matrice orthogonale.

Essentiellement (4) - (5) peuvent être considérés comme la forme canonique du problème de programmation non linéaire, puisque les méthodes décrites au Chap. Habituellement, dans les problèmes de programmation non linéaire, il n'est pas nécessaire que les variables soient entières.

Types de restrictions et méthodes pour leur transformation.

La forme canonique du problème est caractérisée par l'homogénéité du système de contraintes sous la forme d'un système d'équations ; maximiser la fonction objectif; la condition de non-négativité de toutes les variables impliquées dans le problème.

Aucun caractéristiques supplémentaires la forme canonique des problèmes n’ajoute rien au schéma informatique considéré.

Considérons d’abord la deuxième forme canonique du problème minimum.

L’algorithme simplex-mete peut être divisé en deux étapes. Dans un premier temps, une solution de base est trouvée en éliminant les variables. Si elle est trouvée, alors nous avons la forme canonique du problème pour passer à la deuxième étape. La deuxième étape consiste à vérifier s’il existe un optimum borné. Si elle existe, alors les solutions de base admissibles sont déterminées et parmi lesquelles la solution optimale est sélectionnée.

Si le problème est résolu sous forme canonique, alors seule une partie des opérations introduites dans le deuxième paragraphe est utilisée. Ainsi, pour le problème du minimum canonique, seul le cas du paragraphe 3.4.1 est réalisé, et seules les opérations de réarrangement cyclique des colonnes, le passage de la colonne à travers la zone de bordure verticale, la correction des violations structurelles et une partie de l'opération de troncature sont nécessaires. Symétriquement, lors de la résolution du problème du maximum canonique, seul le cas du paragraphe 3.4.2 est réalisé, et les opérations de réarrangement cyclique des chaînes, le passage d'une chaîne à travers la zone de bordure horizontale, la correction des violations structurelles et une autre partie de l'opération de troncature sont nécessaire. Autrement, la forme canonique du problème n’ajoute aucune spécificité supplémentaire.

Le premier paragraphe de l’introduction montre comment un problème général de programmation linéaire peut être réduit à l’une des formes canoniques. Pour les problèmes canoniques, la description de la méthode d'amélioration séquentielle est formellement simplifiée, puisqu'il n'est pas nécessaire de considérer deux options pour violer les conditions d'optimalité et deux options pour atteindre le sommet suivant. matrice de base A [ /, J ], qui déterminent principalement la complexité d'un chat. Cependant, dans de nombreux cas, appliquer la méthode aux formes canoniques du problème s'avère préférable, et dans cette section nous nous attarderons sur des variantes de la méthode obtenue pour des problèmes de programmation linéaire particuliers.

Pages :      1

: Problèmes de programmation linéaire (LPP)

1. Programmation linéaire

2. Types de problèmes de programmation linéaire

3. Formulaires d'enregistrement des PAP

4. Forme canonique des problèmes de programmation linéaire

Programmation linéaire

La programmation linéaire est une branche de la programmation mathématique utilisée dans le développement de méthodes permettant de trouver l'extremum des fonctions linéaires de plusieurs variables sous des restrictions linéaires supplémentaires imposées aux variables.

En fonction du type de problèmes qu'elles résolvent, les méthodes LP sont divisées en universelles et spéciales. En utilisant méthodes universelles Tous les problèmes de programmation linéaire (LPP) peuvent être résolus. Les modèles spéciaux prennent en compte les caractéristiques du modèle de problème, sa fonction objective et son système de contraintes.

La principale caractéristique des problèmes de programmation linéaire est que l’extremum de la fonction objectif se trouve à la limite de la région des solutions réalisables.

Figure 1 - Extremum de la fonction objectif

Le modèle mathématique du ZLP s’écrit comme suit :

max (ou min) Z=z(X),(1)

L'ODR peut être représenté par un système équations linéaires ou des inégalités.

Le vecteur X = (x 1, x 2, .... x p) est un vecteur de contrôle ou un effet de contrôle.

Un plan admissible X, dans lequel le critère d'optimalité Z=z(X) atteint une valeur extrême, est dit optimal et est noté X*, la valeur extrême de la fonction objectif par Z*=z(X*).

Types de problèmes de programmation linéaire

Les méthodes de programmation linéaire sont largement utilisées dans les entreprises industrielles pour optimiser le programme de production, le répartir dans les ateliers et dans les intervalles de temps, lors du chargement des assortiments d'équipements, de la planification des flux de marchandises, de la détermination du plan de chiffre d'affaires, etc.

Le type de tâches le plus courant est tâche utilisation optimale ressources. Supposons qu'une unité de production (atelier, entreprise, association, etc.), en fonction des conditions du marché, des capacités techniques et des ressources disponibles, soit capable de produire n divers types produits connus sous les numéros j.

Lors de la production de produits, l'entreprise est limitée par les ressources disponibles, dont la quantité sera notée m, et le vecteur de ressources B = (b 1, b 2, ..., b t). Des coefficients technologiques a ij sont également connus, qui montrent le taux de consommation de la ième ressource pour la production d'une unité du j-ième produit. Efficacité de la version unités j-i la production est caractérisée par le profit p j .

Il est nécessaire de déterminer le plan de production X = (x 1, x 2, ..., x p), maximisant le profit de l'entreprise avec des ressources données.

La fonction objectif ressemble à ceci

sous restrictions

Souvent la gamme de produits est établie par une organisation supérieure, c'est-à-dire ses volumes doivent être contenus dans certaines limites D en j et D en j : alors la restriction suivante est fixée :

Le modèle du problème de l'utilisation optimale des ressources sous-tend modèles d'optimisation du programme de production annuel de l'entreprise. Le modèle inclut des restrictions sur la durée de fonctionnement des équipements.

En gardant la même notation, on écrit respectivement par b j et c j le prix de vente et le coût unitaire jième produits. Les critères suivants peuvent être considérés comme critères d’optimalité :

1) profit maximum

2) coûts de production minimaux

3) production maximale en termes de valeur (revenus des ventes de produits)

Exemple. L'entreprise peut fabriquer quatre types de produits 1, 2, 3 et 4. Les ventes de tout volume sont garanties. Au cours du trimestre, l'entreprise dispose d'un effectif de 100 équipes, de produits semi-finis pesant 260 kg et d'un équipement de machines de 370 équipes. Les taux de consommation de ressources et le profit par unité de chaque type de produit sont présentés dans le tableau 1.

Nécessaire:

a) élaborer un modèle mathématique du problème de la détermination du plan de production selon lequel le profit maximum est atteint ;

b) résoudre le problème de l'exigence d'emballage afin que le nombre d'unités du troisième produit soit 3 fois plus de quantité les unités en premier ;

c) découvrir l'assortiment optimal pour conditions additionnelles: produire au moins 25 unités du premier produit, pas plus de 30 unités du troisième, et le deuxième et le quatrième dans un rapport de 1:3.

Tableau 1

Donnée initiale

Modèle mathématique du problème :

fonction objectif :

max : Z=40x 1 +50x 2 +100x 3 +80x 4

avec restrictions :

a) pour les ressources en main-d'œuvre :

2,5x 1 +2,5x 2 +2x 3 +1,5x 4 ? 100 ;

pour les produits semi-finis :

4x1 +10x2 +4x3 +6x4 ? 260 ;

pour les machines-outils :

8x1 +7x2 +4x3 +10x4 ? 370 ;

condition de non-négativité :

b) l'exigence supplémentaire pour la configuration sera exprimée par la condition

3x 1 =x 3, soit 3x 1 x 3 =0 ;

c) présentons les conditions aux limites et la condition de configuration comme suit : x 1 ? 25,

x 3?30, 3*x 2 = x 4.

Le problème de la passation des commandes ou du chargement de groupes d'équipements interchangeables. Il s'agit de la répartition des commandes entre m (i=1,..., m) entreprises (magasins, machines, interprètes) ayant des caractéristiques de production et technologiques différentes, mais interchangeables en termes d'exécution des commandes. Il est nécessaire d'établir un plan de passation des commandes dans lequel la tâche serait accomplie et l'indicateur d'efficacité atteindrait une valeur extrême.

Formulons le problème mathématiquement. Supposons que n types de produits doivent être fabriqués à l’aide de m groupes homogènes d’équipements. Plan de production pour chaque type de produit certaine période donné par l'ensemble x j (j=1,2, …n). La puissance de chaque type d'équipement est limitée et égale à b i. La matrice technologique A=||a ij || est connue, où a ij est le nombre d'unités du j-ième produit produites par unité de temps pour i-ème équipement. La matrice C est une matrice de coûts, où c ij sont les coûts associés à la production d'une unité du j-ème produit sur le i-ème équipement. X est un vecteur du volume de sortie.

Le modèle de problème prendra la forme suivante :

fonction objectif - minimiser les coûts de mise en œuvre de toutes les commandes

avec restrictions :

a) par puissance de l'équipement

b) pour la production

c) condition de non-négativité

Ce problème est appelé problème distributif ou de distribution.

Si pour certains types de produits le plan peut être dépassé, alors la limitation (b) prendra la forme

Les éléments suivants peuvent également être considérés comme bénéfice cible :

a) profit maximum

b) coût minimum du temps machine

Parce que Tout modèle contient des prémisses simplificatrices ; pour l'application correcte des résultats obtenus, une compréhension claire de l'essence de ces simplifications est nécessaire, ce qui permet finalement de tirer une conclusion sur leur admissibilité ou leur inadmissibilité. La simplification la plus significative des modèles considérés est l'hypothèse d'une relation directement proportionnelle (linéaire) entre les volumes de consommation de ressources et les volumes de production, qui est spécifiée à l'aide de normes de coût a ij . Évidemment, cette hypothèse n’est pas toujours vérifiée. Ainsi, les volumes de consommation de nombreuses ressources (par exemple, les immobilisations) changent brusquement - en fonction des changements dans le programme de production X. D'autres prémisses simplificatrices incluent des hypothèses sur l'indépendance des prix j des volumes x j, qui n'est valable que pour certaines limites de leur changement. Il est également important de connaître ces points « vulnérables » car ils indiquent des orientations fondamentales pour améliorer le modèle.

Formulaires d'enregistrement PAP

Il existe 3 formes d'enregistrement du PAP :

1) sous forme de fonctions

max(ou min)Z=,max(ou min)Z=,

2) forme vectorielle

(produit scalaire de vecteurs)

sous restrictions

A 1 x 1 +A 2 x 2 +..+A n x n = B

Où sont les vecteurs

C = (C 1, C 2 .. C n), X = (X 1, X 2 .. X n), et.

3) forme matricielle

sous restrictions

où C = (c 1, c 2,...c n),

Forme canonique des problèmes de programmation linéaire

Si toutes les contraintes d'un problème de programmation linéaire sont des équations et que des conditions de non-négativité sont imposées sur toutes les variables x j, alors on parle de problème de programmation linéaire sous forme canonique ou de problème de programmation linéaire canonique (CLP).

sous restrictions

Pour passer du ZLP au CLLP, il faut passer des restrictions d'inégalité aux restrictions d'égalité et remplacer les variables qui n'obéissent pas aux conditions de non-négativité.

Règles pour amener les PAP à Forme canonique:

1) s'il y a des restrictions partie droite négatif, alors cette limite doit être multipliée par -1 ;

2) s'il existe des inégalités entre les restrictions, alors en introduisant des variables supplémentaires non négatives, elles sont transformées en égalités ;

3) si une variable xk n'a aucune restriction de signe, alors elle est remplacée dans la fonction objectif et dans toutes les restrictions par la différence entre deux nouvelles variables non négatives : xk=x * k - xl, où l est l'indice récapitulatif, x * k>=, xl >=0.

Regardons un exemple. Ramenons-le à la forme canonique :

Introduisons les variables de nivellement x 4, x 5, x 6 dans chaque équation du système de contraintes. Le système s'écrira sous forme d'égalités, et dans les première et troisième équations du système de restrictions, les variables x 4, x 6 sont inscrites à gauche avec le signe « + », et dans la deuxième équation x 5 est saisi avec le signe « - ».

Les termes libres à la forme canonique doivent être positifs ; pour cela, multipliez les deux dernières équations par -1 :

Dans la forme canonique d'écriture de problèmes de programmation linéaire, toutes les variables incluses dans le système de contraintes doivent être non négatives. Supposons que

En substituant cette expression au système de restrictions et fonction cible et en écrivant les variables par ordre d'index croissant, on obtient un problème de programmation linéaire présenté sous forme canonique :

optimisation programmation linéaire simplexe

Tout problème de programmation linéaire peut être réduit à un problème de programmation linéaire sous forme canonique. Pour ce faire, dans le cas général, il faut pouvoir réduire le problème de maximisation au problème de minimisation ; passer des contraintes d'inégalité aux contraintes d'égalité et remplacer les variables qui n'obéissent pas à la condition de non-négativité. Maximiser une certaine fonction équivaut à minimiser la même fonction prise avec le signe opposé, et vice versa.

La règle pour amener un problème de programmation linéaire sous forme canonique est la suivante :

• si dans le problème initial il est nécessaire de déterminer le maximum d'une fonction linéaire, alors vous devez changer le signe et rechercher le minimum de cette fonction ;
• si le côté droit des restrictions est négatif, alors cette restriction doit être multipliée par -1 ;
• s'il existe des inégalités entre les restrictions, alors en introduisant des variables supplémentaires non négatives, elles sont transformées en égalités ;
• si une variable xj n'a pas de restrictions de signe, alors il est remplacé (dans la fonction objectif et dans toutes les restrictions) par la différence entre deux nouvelles variables non négatives :
  x 3 = x 3 + - x 3 - , Où x 3 + , x 3 - ≥ 0 .

Exemple 1. Réduire le problème de programmation linéaire à une forme canonique :

min L = 2x 1 + x 2 - x 3 ;
2x 2 - x 3 ≤ 5 ;
x 1 + x 2 - x 3 ≥ -1 ;
2x 1 - x 2 ≤ -3 ;
x 1 ≤ 0 ; x2 ≥ 0 ; x 3 ≥ 0.

Introduisons des variables de nivellement dans chaque équation du système de contraintes x4 , x5 , x6. Le système s'écrira sous forme d'égalités, et dans les première et troisième équations du système de contraintes les variables x4 , x6 sont inscrits dans la partie gauche avec un signe «+», et dans la deuxième équation la variable x5 est saisi avec le signe "-".

2x 2 - x 3 + x 4 = 5 ;
x 1 + x 2 - x 3 - x 5 = -1 ;
2x 1 - x 2 + x 6 = -3 ;
x4 ≥ 0 ; x5 ≥ 0 ; x6 ≥ 0.

Les termes libres à la forme canonique doivent être positifs ; pour cela, multipliez les deux dernières équations par -1 :

2x 2 - x 3 + x 4 = 5 ;
-x 1 - x 2 + x 3 + x 5 = 1 ;
-2x 1 + x 2 - x 6 = 3.

Dans la forme canonique d'écriture de problèmes de programmation linéaire, toutes les variables incluses dans le système de contraintes doivent être négatives. Supposons que x1 = x1" - x7 , Où x 1 "≥ 0, x 7 ≥ 0 .

En substituant cette expression dans le système de contraintes et la fonction objectif et en écrivant les variables par ordre d'indice croissant, on obtient un problème de programmation linéaire présenté sous forme canonique :

L min = 2x 1" + x 2 - x 3 - 2x 7 ;
2x 2 - x 3 + x 4 = 5 ;
-x 1" - x 2 + x 3 + x 5 + x 7 = 1 ;
-2x 1" + x2 - x6 + 2x7 = 3 ;
x 1 "≥ 0 ; x je ≥ 0, je=2, 3, 4, 5, 6, 7.

Condition d'optimalité pour le plan de base du problème canonique LP. Méthode simplexe et sa convergence.

Méthode simplexe est universel, puisqu'il vous permet de résoudre presque tous les problèmes de programmation linéaire écrits en Forme canonique.

L'idée de la méthode simplexe amélioration constante du plan, est-ce que, à partir d'une solution de référence initiale, mouvement dirigé de manière séquentielle des solutions de référence du problème à la solution optimale.

La valeur de la fonction objectif ne diminue pas lors de ce mouvement pour les problèmes au maximum.

Puisque le nombre de solutions de support est fini, alors après un nombre fini d’étapes, nous obtenons la solution de support optimale.

Une solution de référence est une solution de base non négative.

Algorithme de la méthode simplexe

1. Le modèle mathématique du problème doit être canonique. S'il n'est pas canonique, il doit alors être amené à une forme canonique.

2. Trouvez la solution de référence initiale et vérifiez son optimalité.
Pour ce faire, remplissez le tableau simplex 1.
On remplit toutes les lignes du tableau de la 1ère étape en fonction des données du système de restrictions et de la fonction objectif.

Les cas suivants sont possibles lors de la résolution de problèmes sur maximum:

1. Si tous les coefficients de la dernière ligne du tableau simplex Dj³ 0, puis trouvé

solution optimale.

2 Si au moins un coefficient Dj€ 0, mais pour la variable correspondante il n'y a pas une seule relation d'évaluation positive, alors la solution nous arrêtons les tâches, puisque F(X) ® ¥ , c'est-à-dire que la fonction objectif n'est pas limitée dans le domaine des solutions réalisables.

Si au moins un coefficient de la dernière ligne est négatif, et pour la variable correspondante il y a au moins une attitude d'évaluation positive, alors vous devez bouger vers une autre solution de référence.

4.E si il y a plusieurs coefficients négatifs dans la dernière ligne, alors à la colonne de variables sous-jacente(BP) introduisez que variable, ce qui correspond à le plus grand coefficient négatif en valeur absolue.

5. Si au moins un coefficient Dk< 0 ,Que k - ème colonne accepter pour le présentateur.

6. Pour ligne directrice nous acceptons celui qui correspond le minimum ratio de membres gratuits bià coefficients positifs en tête, k – celui-là colonne.

7. L'élément situé à l'intersection des premières lignes et colonnes est appelé élément principal.

Remplir le tableau simplex 2 :

· remplir la colonne de base avec des zéros et des uns

· réécrivez la ligne principale en la divisant par l'élément principal

· si la première ligne contient des zéros, les colonnes correspondantes peuvent être déplacées vers la table simplex suivante

· on trouve les coefficients restants en utilisant la règle du « rectangle »

On obtient une nouvelle solution de référence, que l'on vérifie pour l'optimalité :

Si tous les coefficients de la dernière ligne Dj³ 0, alors la solution trouvée maximum.

Sinon, remplissez le tableau simplex de la 8ème étape et ainsi de suite.

Si la fonction objectif F(X) nécessite de trouver valeur minimum, alors le critère optimalité du problème est coefficients non positifs D j pour tout j = 1,2,...n.

Convergence de la méthode du simplexe. Dégénérescence dans les problèmes LP. La propriété la plus importante de tout algorithme de calcul est la convergence, c'est-à-dire la possibilité d'obtenir les résultats souhaités lors de son application (avec une précision donnée) en un nombre fini d'étapes (itérations).

Il est facile de voir que des problèmes de convergence de la méthode du simplexe peuvent potentiellement survenir au stade du choix de la valeur de r (section 2") dans le cas où le même valeurs minimales relation

sera réalisé pour plusieurs lignes du tableau T(q) simultanément. Puis à l'itération suivante, la colonne b(β(q+1)) contiendra zéro élément.

Dans le cas général, un problème de programmation linéaire est écrit de telle manière que les contraintes sont à la fois des équations et des inégalités, et que les variables peuvent être soit non négatives, soit varier arbitrairement. Dans le cas où toutes les contraintes sont des équations et toutes les variables satisfont à la condition de non-négativité, le problème de programmation linéaire est dit canonique. Il peut être représenté en notation coordonnée, vectorielle ou matricielle.

1. Le problème de programmation linéaire canonique en notation de coordonnées a la forme

.

Sous une forme plus compacte, ce problème peut être écrit en utilisant le signe de sommation,

(1.7)

2. Le problème de programmation linéaire canonique en notation vectorielle a la forme

(1.8)

Où ,

.

3. Le problème de programmation linéaire canonique en notation matricielle a la forme

(1.9)

, .

Ici UN– matrice des coefficients du système d'équations, X– matrice-colonne des variables de tâche, – matrice-colonne des membres droits du système de contraintes.

Des problèmes de programmation linéaire sont souvent utilisés, appelés symétrique, qui en notation matricielle ont la forme

(1.10)

(1.11)

1.4. Réduction d'un problème général de programmation linéaire
à la forme canonique

Dans la plupart des méthodes de résolution de problèmes de programmation linéaire, on suppose que le système de contraintes est constitué d'équations et de conditions naturelles pour la non-négativité des variables. Cependant, lors de l'élaboration de modèles mathématiques de problèmes économiques, les contraintes se transforment principalement en systèmes d'inégalités, il est donc nécessaire de pouvoir passer d'un système d'inégalités à un système d'équations. Pour cela, nous démontrons le théorème suivant.

Théorème 1.1. Sur le remplacement d'une inégalité par une équation. Chaque décision inégalités

correspond à une unique solution de l’équation

et inégalités

, (1.14)

et, inversement, chaque solution de l'équation (1.13) et de l'inégalité (1.14) correspond à une unique solution de l'inégalité (1.12).

Preuve. Laisser est la solution de l’inégalité (1.12), alors . Notons la différence entre les côtés droit et gauche de cette inégalité par , c'est-à-dire

Évidemment . Remplaçons plutôt dans l'équation (1.13) valeurs variables , on a

Ainsi, satisfait l’équation (1.13) et l’inégalité (1.14). Cela signifie que la première partie du théorème a été prouvée.

Satisfions maintenant l'équation (1.13) et l'inégalité (1.14), c'est-à-dire que nous avons

ET

En écartant la valeur non négative du côté gauche de la dernière égalité, nous obtenons

c'est à dire. satisfait l’inégalité (1.12). Le théorème a été prouvé.

Si l'inégalité est , alors une variable supplémentaire non négative doit être introduite dans son côté gauche avec un signe moins, c'est-à-dire

Les variables non négatives introduites dans les contraintes d'inégalité pour les transformer en équations sont appelées variables supplémentaires. Des variables supplémentaires sont introduites dans la fonction objectif avec des coefficients nuls et n'affectent donc pas sa valeur.

Dans le cas où le problème comporte des variables qui changent arbitrairement, alors toute variable de ce type est remplacée par la différence de deux variables non négatives, c'est-à-dire , Où Et .

Parfois, il devient nécessaire de passer de la recherche du minimum à la recherche du maximum, ou vice versa. Pour ce faire, il suffit de changer les signes de tous les coefficients de la fonction objectif en signes opposés, sinon laisser le problème inchangé. Les solutions optimales des problèmes maximum et minimum ainsi obtenus coïncident, et les valeurs des fonctions objectifs solutions optimales ne diffèrent que par le signe.

Exemple 1.1. Amenez le problème de programmation linéaire sous forme canonique.

D

Solution. Passons au problème de trouver le maximum de la fonction objectif. Pour ce faire, on change les signes des coefficients de la fonction objectif. Pour transformer les deuxième et troisième inégalités du système de contraintes en équations, nous introduisons des variables supplémentaires non négatives (sur modèle mathématique cette opération est marquée de la lettre D). La variable est introduite dans le côté gauche de la deuxième inégalité avec un signe « + », puisque l'inégalité a la forme . La variable est introduite dans le côté gauche de la troisième inégalité avec le signe « - », puisque l'inégalité a la forme . Les variables sont introduites dans la fonction objectif avec un coefficient égal à zéro. La variable sur laquelle la condition de non-négativité n'est pas imposée est remplacée par la différence , . Nous écrivons le problème sous forme canonique

Dans certains cas, il devient nécessaire de réduire le problème canonique à un problème symétrique. Regardons un exemple.

Exemple 1.2. Amener un problème de programmation linéaire à une forme symétrique

L'enregistrement de la fonction objectif et du système de contraintes dans divers problèmes de programmation linéaire n'est pas le même : dans certains problèmes, il est nécessaire de trouver le minimum de la fonction objectif, et dans d'autres, le maximum ; dans certains cas, les variables recherchées dépendent d'un indice, dans d'autres de deux ; dans certains problèmes, les contraintes sont spécifiées sous la forme d'un système d'inégalités linéaires, et dans d'autres, sous la forme d'un système d'équations linéaires. En pratique, il est également possible d’avoir des problèmes dans lesquels certaines contraintes se présentent sous la forme d’inégalités linéaires et d’autres sous la forme d’équations linéaires. De plus, tous les problèmes ne nécessitent pas la non-négativité des variables.

La prise en compte d'une telle variété de problèmes de programmation linéaire nécessite le développement de méthodes spéciales pour résoudre des classes individuelles d'entre eux. Nous concentrerons notre attention sur l'étude des propriétés générales et des méthodes de programmation linéaire, écrites sous la forme dite canonique.

Si dans un problème de programmation linéaire le système de contraintes initiales prend la forme d'équations comme

et vous devez trouver le maximum de la fonction objectif linéaire

alors le problème de programmation linéaire est considéré comme écrit sous forme canonique.

Tout problème de programmation linéaire peut être facilement réduit à une forme canonique. Dans le cas général, il suffit pour cela de pouvoir, d'une part, réduire le problème de la minimisation de la fonction objectif au problème de sa maximisation, d'autre part, passer des contraintes d'inégalité aux contraintes d'égalité, et troisièmement, modifier les variables qui sont non soumis à la condition de non-négativité.

Dans le cas où il faut trouver le minimum d'une fonction , on peut procéder à la recherche du maximum de la fonction , puisque la déclaration suivante est vraie :
.

La contrainte d’inégalité du problème original, qui a la forme « ", peut être transformé en contrainte d'équation en ajoutant une variable non négative supplémentaire à son côté gauche et une contrainte d'inégalité de la forme " » – en soustrayant une variable supplémentaire non négative de son côté gauche.

Notez que le nombre de variables non négatives supplémentaires introduites est toujours égal au nombre d’inégalités dans le système de contraintes d’origine.

Les variables supplémentaires introduites ont une signification économique très spécifique. Ainsi, si les contraintes du problème de programmation linéaire original reflètent les coûts et la disponibilité des ressources de production, alors la valeur numérique de la variable supplémentaire montre la quantité de ressource inutilisée correspondante.

Notez également que si une variable n'obéit pas à la condition de non-négativité, alors il doit être remplacé par deux variables non négatives Et , ayant accepté
.

Exemple. Écrivez le problème d'optimisation linéaire suivant sous forme canonique : trouver le minimum de la fonction
sous restrictions

Solution

Dans ce problème, il faut trouver le minimum de la fonction objectif, et le système de contraintes comprend quatre inégalités. Pour l'écrire sous forme canonique, il faut passer des contraintes d'inégalité aux contraintes d'équation, et également transformer la fonction objectif.

Le nombre d'inégalités incluses dans le système de contraintes du problème étant égal à quatre, cette transition doit s'effectuer avec l'introduction de quatre variables supplémentaires non négatives. De plus, dans les deuxième et quatrième inégalités il y a un signe « ", nous ajoutons donc des variables supplémentaires à leur côté gauche. Dans les première et troisième inégalités il y a un signe « ", ce qui signifie que nous soustrayons des variables supplémentaires de leur côté gauche.

Nous transformons également la fonction objectif, en changeant tous les signes à l'opposé, et trouvons son maximum.

Ainsi, cette tâche la programmation linéaire s’écrira sous la forme canonique suivante :

trouver le maximum d'une fonction

sous restrictions