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

problèmes de programmation linéaire

2.1. Définition et formes d'enregistrement

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 appelé canonique. Il peut être présenté sous forme de notation coordonnée, vectorielle ou matricielle.

a) le problème canonique LP sous forme de coordonnées a la forme :

,
.

Ce problème peut être écrit en utilisant le signe de sommation :

,

,

,
,
.

b) le problème canonique LP sous forme vectorielle a la forme : ,

,

Où
;
;

,
;;
.

c) le problème canonique LP sous forme matricielle a la forme :

,
,

Où
,,.

2.2. Réduction du problème linéaire général

programmation sous forme canonique

Lors de l'élaboration de modèles mathématiques de problèmes économiques, les contraintes sont principalement transformées en systèmes d'inégalités. Il faut donc pouvoir passer d'eux à des systèmes d'équations. Par exemple, considérons l'inégalité linéaire

et ajoutez à son côté gauche une certaine valeur
de telle sorte que l’inégalité se transforme en égalité.

Variable non négative
appelée variable supplémentaire. Le théorème suivant fournit la base de la possibilité d’une telle transformation.

Théorème 2.2.1. Chaque décision
l'inégalité (2.2.1) correspond à une unique solution de l'équation (2.2.2) et de l'inégalité
, et, inversement, à chaque solution de l’équation (2.2.2)c
correspond à la solution
inégalités (2.2.1).

Preuve. Laisser
solution de l’inégalité (2.2.1). Alors. Prenons un numéro
. Il est clair que
. En substituant dans l'équation (2.2.2), on obtient

La première partie du théorème a été prouvée.

Soyons maintenant un vecteur satisfait l’équation (2.2.2) avec
, c'est-à-dire en supprimant la valeur non négative du côté gauche de la dernière égalité
, nous recevons, etc.

Ainsi, le théorème prouvé établit en fait la possibilité de donner à tout problème LP une forme canonique. Pour ce faire, il suffit d'introduire dans chaque contrainte ayant la forme d'une inégalité sa propre variable supplémentaire non négative. De plus, dans les inégalités de forme (1.2.1) ces variables apparaîtront avec le signe « + », et dans les inégalités de forme (1.2.2) – avec le signe « – ». Des variables supplémentaires sont introduites dans la fonction objectif avec des coefficients nuls et n'affectent donc pas sa valeur.

Commentaire. À l’avenir, nous présenterons la méthode simplexe pour le problème canonique LP lors de l’étude de la fonction objectif pour un minimum. Dans ces problèmes où il faut trouver le maximum
, il suffit de considérer la fonction
, trouve-la valeur minimum, puis, en changeant le signe à l'opposé, déterminez la valeur maximale souhaitée
.

3. Méthode graphique pour résoudre des problèmes

programmation linéaire

3.1. Concepts généraux, exemples

Dans les cas où il n'y a que deux variables dans le problème LP, vous pouvez utiliser méthode graphique. Soit il faut trouver la valeur maximale (minimale) de la fonction
sous restrictions

(3.1.1)

Cette méthode est basée sur la possibilité de représenter graphiquement la région des solutions réalisables à un problème, c'est-à-dire satisfaire le système (3.1.1), et trouver la solution optimale parmi eux. La région des solutions réalisables au problème est construite comme l’intersection (partie commune) des régions de solutions de chacune des contraintes données (3.1.1). Chacun d’eux définit un demi-plan de frontière
,
. Pour déterminer lequel des deux demi-plans est le domaine de solution, il suffit de substituer dans l'inégalité les coordonnées de tout point ne se trouvant pas sur la droite : si elle est satisfaite, alors le domaine de solution est le demi-plan contenant ce point, si l'inégalité n'est pas satisfaite, alors le domaine de solution est un demi-plan qui ne contient pas le point donné.

L’intersection de ces demi-plans forme une certaine zone appelée polygone solution, qui est un ensemble convexe. (Supposons que le système de contraintes est cohérent et que le polygone de ses solutions est limité.) Pour trouver la solution optimale parmi les solutions réalisables, des lignes de niveau et des lignes droites de référence sont utilisées.

Ligne de niveau s'appelle une droite sur laquelle la fonction objectif prend une valeur constante. L'équation de la ligne de niveau a la forme

, Où
. Toutes les lignes de niveau sont parallèles les unes aux autres. Leur normal
.

Ligne de référence est appelée une ligne de niveau qui a au moins un point commun avec la région des solutions réalisables, par rapport à laquelle cette région est située dans l'un des demi-plans (Fig. 1).

Valeurs
augmentation dans la direction du vecteur
. Il est donc nécessaire de déplacer la ligne de niveau
dans la direction de ce vecteur parallèle à lui-même à la ligne de référence L 1 dans la tâche maximale et dans le sens opposé - dans la tâche minimale (jusqu'à la ligne de référence L 2).

Donnons la solution de l'exemple 1.1. Rappelons qu'il faut trouver le maximum de la fonction
sous restrictions

Solution. Nous construisons une région de solutions réalisables. Nous numérotons les contraintes du problème. Dans un système de coordonnées cartésiennes rectangulaires (Fig. 2), nous construisons une ligne droite

, correspondant à la contrainte (1). Nous trouvons lequel des demi-plans en lesquels cette ligne droite divise tout le plan de coordonnées est le domaine des solutions à l'inégalité (1).

Pour ce faire, il suffit de substituer dans l'inégalité les coordonnées de tout point qui ne se trouve pas sur la droite. Puisque c'est droit ne passe pas par l'origine, substituer
à la première limitation. On obtient une inégalité stricte
. Par conséquent, le point
se situe dans le demi-plan des solutions. De même, on construit une droite

et le domaine de solution de la contrainte (2). On retrouve la partie commune des demi-plans de solutions, en tenant compte des restrictions (3). Nous mettons en évidence la région résultante des solutions réalisables en couleur foncée sur la figure 2.

Construire une ligne de niveau
et vecteur
, qui indique le sens d'augmentation de la fonction et perpendiculaire à la ligne

. Ligne de niveau
se déplacer parallèlement à lui-même dans la direction
à la ligne de référence. Nous constatons que la fonction objectif atteint son maximum au point
point d'intersection des lignes Et . Résoudre un système d'équations de ces droites
, on obtient les coordonnées du point
. Par conséquent, et
,
solution optimale.

Exemple 3.1. Trouver le minimum d'une fonction
sous un système de restrictions

Solution. Nous construisons la région des solutions réalisables (voir Fig. 3), vecteur
et une des lignes de niveau
. Déplacez la ligne de niveau dans la direction opposée
, puisque le problème de trouver le minimum d'une fonction est en train d'être résolu. Dans ce cas, la ligne de référence passe par le point A (Fig. 3), dont les coordonnées seront trouvées à partir de la solution du système

Donc,
. Calculons.

Commentaire. En fait, cela dépend du type de domaine de solutions réalisables et de la fonction objectif
Un problème LP peut avoir une solution unique, un nombre infini de solutions ou aucune solution du tout.

Exemple 3.2. Trouver le minimum d'une fonction
sous restrictions

Solution. Construire la région des solutions réalisables, la normale des lignes de niveau
et une des lignes de niveau , qui présente des points communs avec ce domaine. Déplacer la ligne de niveau dans la direction opposée à la direction normale , puisque le problème de trouver le minimum d'une fonction est en train d'être résolu. Normale des lignes de niveau
et la normale de la ligne frontière , dans la direction dans laquelle se déplacent les lignes de niveau, sont parallèles, puisque leurs coordonnées sont proportionnelles
. Par conséquent, la ligne de référence coïncide avec la ligne de démarcation région de solutions réalisables et passe par deux points d’angle de cette région Et (Fig. 4).

Le problème a un nombre infini de solutions optimales, qui sont des points du segment
. Ces points
,
on trouve en résolvant les systèmes d'équations correspondants :

;
;

,
;
,
;

;
.

Calculons.

Répondre:
à
,
.

Exemple 3.3. Résoudre un problème de programmation linéaire

Solution. Nous construisons la région des solutions réalisables, la normale
et une des lignes de niveau. Dans ce problème il faut trouver le maximum de la fonction objectif, donc la ligne de niveau avancer dans le sens de la normale. Du fait que dans cette direction la gamme de solutions réalisables n'est pas limitée, la ligne de niveau va vers l'infini (Fig. 5).

Le problème n’a pas de solution en raison du caractère illimité de la fonction objectif.

Répondre:
.

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 objectif 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é).