N'importe quelle tâche programmation linéaire peut être réduit à un problème de programmation linéaire dans 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 le problème initial nécessite de déterminer le maximum fonction linéaire, alors vous devez changer le signe et rechercher le minimum de cette fonction ;
• s'il y a des restrictions partie droite est négatif, alors cette limite 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.

La 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. Modèle mathématique les tâches devraient ê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.

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 d'une 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.

La forme canonique du problème de programmation linéaire est pratique dans la mesure où il est facile de trouver le sommet initial de la région réalisable.

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 d'un système de contraintes vers la forme canonique d'un problème 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

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 é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

Forme canonique de ZLP- problème de programmation linéaire de la forme ax = b où a est la matrice des coefficients, b est le vecteur de contraintes.

Objet de la prestation. Le calculateur en ligne est conçu pour la transition d'un PPP vers un KZLP. Amener le problème sous forme canonique signifie que toutes les contraintes auront la forme d'égalités en introduisant des variables supplémentaires.
Si une contrainte n'est imposée sur aucune variable x j, alors elle est remplacée par la différence de variables supplémentaires, x j = x j1 - x j2, x j1 ≥ 0, x j2 ≥ 0.

Instructions. Sélectionnez le nombre de variables et le nombre de lignes (nombre de contraintes). La solution résultante est enregistrée dans un fichier Word.

Nombre de variables 2 3 4 5 6 7 8 9 10
Nombre de lignes (nombre de restrictions) 2 3 4 5 6 7 8 9 10

Comment réduire un problème de programmation linéaire à une forme canonique

Le modèle mathématique du ZLP s'appelle basique, si les contraintes qu'il contient sont présentées sous forme d'équations à condition que les variables soient non négatives.

Le modèle mathématique s'appelle canonique, si son système de contraintes se présente sous la forme d'un système de m équations linéairement indépendantes (rang du système r=m), le système est attribué base unitaire, les variables libres sont définies et la fonction objectif est exprimée en termes de variables libres. Dans ce cas, les membres droits des équations sont non négatifs (b i ≥ 0).

Les variables incluses dans l'une des équations du système avec un coefficient de un et absentes dans d'autres équations sont appelées inconnues fondamentales, et tous les autres - gratuit.

La solution du système s’appelle basique, si les variables libres qu'il contient sont égales à 0, et qu'il a la forme :
X bases = (0, 0; b 1 , …, b m), f(X bases) = c 0

Solution basique est le point angulaire de l’ensemble des solutions du système, c’est-à-dire définit le sommet du polygone de solution du modèle. Parmi ces solutions, il y a celle dans laquelle la fonction objectif prend valeur optimale.

Une solution de base est appelée solution de référence si elle est admissible, c'est-à-dire tous les membres droits des équations du système (ou inégalités) sont positifs b je ≥ 0.

La forme compacte du modèle canonique est :
AX = b
X ≥ 0
Z = CX(max)

La notion de solution admissible, le domaine des solutions admissibles, solution optimale problèmes de programmation linéaire.
Définition 1. Un vecteur X qui satisfait le système de contraintes ZLP, y compris les conditions de non-négativité, le cas échéant, est appelé une solution admissible du ZLP.
Définition 2. L’ensemble de toutes les solutions admissibles forme la région des solutions admissibles (ADA) du PLP.
Définition 3. Une solution réalisable pour laquelle la fonction objectif atteint un maximum (ou un minimum) est appelée solution optimale.

Exemple n°1. Réduisez le problème LP suivant à la forme canonique : F(X) = 5x 1 + 3x 2 → max sous les restrictions :
2x1 + 3x2 ≤20
3x 1 + x 2 ≤15
4x1 ≤16
3x2 ≤12
Le modèle est écrit sous forme standard. Introduisons les variables d'équilibre non négatives x 3 , x 4 , x 5 , x 6 , que nous ajoutons aux côtés gauches des contraintes d'inégalité. Nous introduisons toutes les variables supplémentaires dans la fonction cible avec des coefficients égaux à zéro :
Dans la première inégalité de sens (≤), nous introduisons la variable de base x 3 . Dans la 2ème inégalité de sens (≤) nous introduisons la variable de base x 4 . Dans la troisième inégalité, nous introduisons la variable de base x 5 . Dans la 4ème inégalité - la variable de base x 6. On obtient la forme canonique du modèle :
2x 1 + 3x 2 + 1x 3 + 0x 4 + 0x 5 + 0x 6 = 20
3x 1 + 1x 2 + 0x 3 + 1x 4 + 0x 5 + 0x 6 = 15
4x 1 + 0x 2 + 0x 3 + 0x 4 + 1x 5 + 0x 6 = 16
0x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 1x 6 = 12
F(X) = 5x 1 + 3x 2 + 0x 3 + 0x 4 + 0x 5 + 0x 6 → max

Exemple n°2. Trouver deux solutions de référence du système
x1 + 2x4 - 2x5 = 4
x3 + 3x4 + x5 = 5
x2 + 3x5 = 2

Problème de programmation linéaire de la forme ax = b où a est la matrice des coefficients, b est le vecteur de contraintes.
Exemple:

Dans chaque problème LP, les valeurs des variables sont recherchées à la condition que :

• ces valeurs satisfaisaient à un système d'équations linéaires ou d'inégalités ;
• à ces valeurs, la fonction objectif se tournerait vers un minimum ou un maximum.

Instructions. Sélectionnez le nombre de variables et le nombre de lignes (nombre de contraintes). La solution résultante est enregistrée dans un fichier Word.

Un des méthodes universelles LP est méthode simplexe, qui peut cependant être utilisé si le problème LP a une forme canonique.

Définition. Le problème LP a une forme canonique si toutes les contraintes du système sont constituées uniquement d'équations (à l'exception des inégalités exprimant la non-négativité des variables) et que la fonction objectif doit être minimisée.
Un exemple d'un tel problème LP sous forme canonique est le problème 1 – un problème de transport équilibré avec un système de contraintes (1) et fonction cible (2).
Cependant, dans la plupart des problèmes économiques, le système de contraintes comprend le plus souvent initialement non seulement des équations, mais aussi des inégalités.

Déclaration. Tout problème LP général peut être réduit à une forme canonique.
Apportant tâche commune LP à la forme canonique est obtenu en introduisant de nouvelles variables (on les appelle supplémentaires).
Le système de contraintes (3) de ce problème est constitué de quatre inégalités. En introduisant des variables supplémentaires oui 1 ≥ 0, oui 2 ≥ 0, oui 3 ≥ 0, oui 4 ≥ 0, on peut passer au système de restrictions :

Ces variables supplémentaires oui j'ai une signification économique absolument claire, à savoir la quantité de temps de travail non utilisé (temps d'arrêt de la machine je-ème type).
Par exemple, si les machines du premier type ont fonctionné pendant les 18 heures, alors x + y = 18, donc y 1 = 0. Mais nous admettons la possibilité d'une utilisation incomplète du temps de fonctionnement de la première machine X + oui<18. В этом случае oui 1 prend une valeur positive et peut être considéré comme un délai non utilisé. Par exemple, connaissant la solution à ce problème du paragraphe 3.3.2, X = 12, oui= 6, on peut conclure du système de restrictions (3.9) que oui 1 = oui 2 = oui 3 = 0, et oui 4 = 12 – 6 = 6. Autrement dit, les machines des premier, deuxième et troisième types utilisent pleinement leur temps de travail. Mais la quatrième machine n'est qu'à moitié chargée, 6 heures, et, compte tenu du plan optimal, est inactive. Peut-être qu'après de telles conclusions, le chef d'entreprise voudra-t-il le charger d'autres travaux, le louer pour cette période, etc.
Ainsi, en introduisant des variables supplémentaires, nous pouvons réduire toute contrainte de type inégalité à une équation.

Considérons le problème du mélange. Le système de restrictions a la forme :
Les inégalités ont été tournées vers « plus », donc, en introduisant des variables supplémentaires y 1, y 2, y 3 ≥ 0, elles doivent être soustraites du côté gauche afin de l'égaliser avec le droit. On obtient un système de restrictions sous forme canonique :
Les variables y i auront également un sens économique. Si vous vous souvenez du contenu pratique du problème, alors la variable y 1 signifiera la quantité de substance en excès A dans le mélange, y 2 signifiera la quantité de substance en excès DANS dans le mélange oui 3 – excédent AVEC dans le mélange.
La tâche de trouver la valeur maximale de la fonction objectif peut être réduite à trouver le minimum de la fonction - F en raison de l'évidence de l'énoncé max F = –min (– F). Regardez l'image : si à un moment donné X= X 0 fonction oui= F(X) atteint son maximum, alors la fonction oui= –F(X), symétrique à celui-ci par rapport à l'axe BŒUF, au même moment X 0 atteindra un minimum, et F maximum = – (– F minutes) à X = X 0 .

Conclusion. Pour représenter le problème LP sous forme canonique il faut :

• transformer les inégalités incluses dans le système de contraintes du problème en équations en introduisant des variables supplémentaires ;
• si la fonction objectif F→max (maximise), il est remplacé par la fonction – F→ min (qui est minimisé).