Résolution de problèmes MOP (méthodes d'optimisation). Base méthodologique pour l'élaboration des décisions de gestion La solution est dite optimale

Programmation linéaire est une branche des mathématiques qui étudie les méthodes permettant de trouver le minimum ou le maximum d'une fonction linéaire d'un nombre fini de variables, à condition que les variables satisfassent un nombre fini de contraintes sous la forme d'équations linéaires ou d'inégalités linéaires.

Ainsi, la tâche générale programmation linéaire(ZLP) peut être formulé comme suit.

Trouver les valeurs des variables réelles pour lesquelles fonction objectif

prend une valeur minimale sur l'ensemble des points dont les coordonnées satisfont système de restrictions

Comme on le sait, une collection ordonnée de valeurs n Les variables , , … sont représentées par un point dans un espace à n dimensions. Dans ce qui suit nous désignerons ce point X=( , , … ).

Sous forme matricielle, le problème de programmation linéaire peut être formulé comme suit :

, UN– matrice de taille,

Point X=( , , … ), satisfaisant toutes les conditions, est appelé point valable . L'ensemble de tous les points admissibles est appelé zone valide .

Solution optimale (plan optimal) un problème de programmation linéaire s'appelle une solution X=( , , … ), appartenant à la région admissible et pour laquelle la fonction linéaire Q prend la valeur optimale (maximale ou minimale).

Théorème. L'ensemble de toutes les solutions réalisables au système de contraintes d'un problème de programmation linéaire est convexe.

L'ensemble des points est appelé convexe , s'il contient, avec deux de ses points, leur combinaison linéaire convexe arbitraire.

Point X appelé combinaison linéaire convexe points si les conditions sont remplies

L’ensemble de toutes les solutions réalisables à un problème de programmation linéaire est une région polyédrique convexe, que nous appellerons désormais polyèdre de solutions .

Théorème. Si le ZLP a une solution optimale, alors la fonction objectif prend la valeur maximale (minimale) à l'un des sommets du polyèdre de solution. Si la fonction objectif prend une valeur maximale (minimale) en plus d'un point, alors elle prend cette valeur en tout point qui est une combinaison linéaire convexe de ces points.

Parmi les nombreuses solutions du système m on distingue les équations linéaires décrivant le polyèdre des solutions, on distingue les solutions dites de base.

Solution de base du système m les équations linéaires à n variables sont une solution dans laquelle tous n-m les variables non essentielles sont nulles. Dans les problèmes de programmation linéaire, ces solutions sont appelées solutions de base admissibles (plans de référence).

Théorème. Chaque solution de base admissible à un problème de programmation linéaire correspond à un sommet du polyèdre solution, et inversement, à chaque sommet du polyèdre solution correspond une solution de base admissible.

Un corollaire important découle des théorèmes ci-dessus :

Si un problème de programmation linéaire a une solution optimale, alors elle coïncide avec au moins une de ses solutions de base réalisables.

Par conséquent, l’optimum de la fonction linéaire du but d’un problème de programmation linéaire doit être recherché parmi le nombre fini de ses solutions de base réalisables.

La base pour résoudre les problèmes économiques repose sur des modèles mathématiques.

Modèle mathématique le problème est un ensemble de relations mathématiques qui décrivent l’essence du problème.

• sélection des variables du problème
• élaborer un système de restrictions
• choix de la fonction objectif

Variables de tâche sont appelées les quantités X1, X2, Xn, qui caractérisent complètement le processus économique. Ils s'écrivent généralement sous forme de vecteur : X=(X 1, X 2,...,X n).

Système de restrictions les problèmes sont un ensemble d’équations et d’inégalités qui décrivent les ressources limitées du problème considéré.

Fonction objectif les tâches sont appelées fonction de variables de tâche qui caractérisent la qualité de la tâche et dont l'extremum doit être trouvé.

DANS cas général Le problème de programmation linéaire peut s’écrire comme suit :

Cette entrée signifie ce qui suit : trouver l'extremum de la fonction objectif (1) et les variables correspondantes X=(X 1 , X 2 ,...,X n) à condition que ces variables satisfassent au système de restrictions (2) et au conditions de non-négativité (3) .

Solution valide(plan) d'un problème de programmation linéaire est tout vecteur à n dimensions X=(X 1 , X 2 ,...,X n) qui satisfait le système de contraintes et de conditions de non-négativité.

L'ensemble des solutions réalisables (plans) des formes de problèmes région de solutions réalisables(ODR).

La solution optimale(plan) d'un problème de programmation linéaire est une solution (plan) admissible du problème dans laquelle la fonction objectif atteint un extremum.

Exemple de compilation d'un modèle mathématique

Le problème de l'utilisation des ressources (matières premières)

Condition: Pour produire n types de produits, m types de ressources sont utilisés. Créez un modèle mathématique.

Connu:

• b i (i = 1,2,3,...,m) — réserves de chaque i-ème type de ressource ;
• a ij (i = 1,2,3,...,m; j=1,2,3,...,n) - les coûts de chaque i-ème type de ressource pour la production d'une unité de volume du j-ième type de produit ;
• c j (j = 1,2,3,...,n) - profit de la vente d'une unité de volume du j-ème type de produit.

Il est nécessaire d'élaborer un plan de production garantissant un profit maximum dans des conditions données de restrictions sur les ressources (matières premières).

Solution:

Introduisons un vecteur de variables X=(X 1, X 2,...,X n), où x j (j = 1,2,...,n) est le volume de production du j-ième type de produit.

Les coûts du ième type de ressource pour la production d'un volume donné x j de produits sont égaux à a ij x j , donc la restriction sur l'utilisation des ressources pour la production de tous types de produits a la forme :
Le bénéfice de la vente du jème type de produit est égal à c j x j, donc la fonction objectif est égale à :

Répondre- Modèle mathématique a la forme :

Forme canonique d'un problème de programmation linéaire

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 appelé canonique.

Il peut être représenté en notation coordonnée, vectorielle et matricielle.

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

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

• A est la matrice des coefficients du système d'équations
• X : colonne matricielle de variables de tâche
• Ао — colonne-matrice des parties droites du système de restrictions

On utilise souvent des problèmes de programmation linéaire, appelés symétriques, qui en notation matricielle ont la forme :

Réduire un problème général de programmation linéaire à une 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 de problèmes économiques, les contraintes se forment principalement sous la forme d'un système d'inégalités, il faut donc pouvoir passer d'un système d'inégalités à un système d'équations.

Prenons l'inégalité linéaire a 1 x 1 +a 2 x 2 +...+a n x n ≤b et ajoutons à son côté gauche une certaine valeur x n+1 telle que l'inégalité se transforme en l'égalité a 1 x 1 +a 2 x 2 + ...+une n x n +x n+1 =b. De plus, cette valeur x n+1 est non négative.

Regardons tout à l'aide d'un exemple.

Amenez le problème de programmation linéaire sous forme canonique :

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, on introduit des variables supplémentaires non négatives x 4 x 5 (dans le modèle mathématique cette opération est marquée de la lettre D).
La variable x 4 est introduite dans le côté gauche de la deuxième inégalité avec le signe « + », puisque l'inégalité a la forme « ≤ ».
La variable x 5 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 x 4 x 5 sont entrées dans la fonction objectif avec un coefficient. égal à zéro.
Nous écrivons le problème sous forme canonique.

Recherche opérationnelle est une discipline mathématique complexe qui traite de la construction, de l'analyse et de l'application de modèles mathématiques pour prendre des décisions optimales pendant les opérations.

Sujet de recherche opérationnelle- des systèmes de gestion organisationnelle ou des organisations constituées d'un grand nombre d'unités en interaction qui ne sont pas toujours cohérentes les unes avec les autres et peuvent être opposées.

Objectif de la recherche opérationnelle- justification quantitative des décisions prises sur la gestion des organisations

Opération- un système d'actions contrôlées, unies par un plan unique et visant à atteindre un objectif précis.

L'ensemble des paramètres de contrôle (variables) lors d'une opération est appelé décision. La solution s'appelle acceptable , s’il satisfait à un ensemble de certaines conditions. La solution s'appelle optimal

, s'il est acceptable et, selon certains critères, préférable à d'autres, ou du moins pas pire. Signe de préférence

appelé critère d’optimalité. Critère d'optimalité

comprend une fonction objectif, une direction d'optimisation ou un ensemble de fonctions objectifs et des directions d'optimisation correspondantes. Fonction objectif

est un indicateur quantitatif de la préférence ou de l’efficacité des solutions. Sens de l'optimisation

- c'est le maximum (minimum) si la valeur la plus grande (la plus petite) de la fonction objectif est la plus préférable.

Par exemple, le critère peut être de maximiser les profits ou de minimiser les coûts.

Le modèle mathématique du problème IO comprend :

1) description des variables à trouver ;

2) description des critères d'optimalité ;– justifier quantitativement et qualitativement la décision prise. La décision finale est prise par la personne ou le groupe de personnes responsable appelé décideur.

Un vecteur qui satisfait un système de contraintes est appelé solution acceptableou plan ZLP. L’ensemble de tous les plans s’appelle zone valide oudomaine des solutions réalisables. Le plan qui fournit le maximum (minimum) de la fonction objectif est appeléplan optimal ousolution optimale pour ZLP. Ainsi,résoudre le PIL – signifie trouver son plan optimal.

Il est très simple d'amener le ZLP général au principal, en utilisant les règles évidentes suivantes.

Minimiser la fonction objectif féquivaut à maximiser la fonction g = – f.

Une contrainte d'inégalité équivaut à une équation à condition d'ajouter la variable supplémentaire.

Si pour une variable x j la condition de non-négativité n'est pas imposée, alors un changement de variable est effectué.

Ligne de niveau fonctions f, c'est-à-dire la ligne le long de laquelle cette fonction prend la même valeur fixe Avec, c'est-à-dire f(x 1 , x 2)= c

L'ensemble des points est appelé convexe, s'il contient, avec deux de ses points quelconques, le segment entier reliant ces points.

Dans le cas de deux variables, l'ensemble des solutions d'une inégalité linéaire (équation) est un demi-plan (droite).

L'intersection de ces demi-plans (et des droites, si le système de contraintes a des équations) représente la région réalisable. S’il n’est pas vide, alors c’est un ensemble convexe et s’appelle.

polygone de solution Dans le cas de trois variables, la région admissible du ZLP est l'intersection de demi-espaces et, éventuellement, de plans, et est appelée

polyèdre de solutionsLe système d'équations linéaires s'appelle, système avec base si chaque équation contient une inconnue de coefficient égal à 1, qui est absente dans les autres équations du système. Ces inconnues sont appelées, basique – repos.

gratuit Nous appellerons le système d'équations linéaires, canoniquesi c'est un système avec une base et c'est tout b je ≥ 0. La solution de base dans ce cas s'avère être un plan, puisque ses composantes sont non négatives. Appelons-le basique (ou) plan justificatif

système canonique. Nous appellerons le système d'équations linéaires Nous l'appellerons OZLP

(KZLP), si le système d'équations linéaires de ce problème est canonique et que la fonction objectif n'est exprimée qu'en termes d'inconnues libres. Si dans le tableau simplex il y a au moins un élément positif parmi les coefficients pour toute inconnue libre, alors une transition vers un nouveau problème canonique est possible, équivalent à celui d'origine, dans lequel l'inconnue libre spécifiée s'avère être basique (en ce cas, une des inconnues de base devient libre) .

Théorème 2. (sur l'amélioration de la ligne de base) j , et dans la colonne x j S'il y a au moins un élément positif et que la relation clé est >0, alors une transition vers un problème canonique équivalent avec une conception de base non pire est possible.

Théorème 3. (condition suffisante pour l'optimalité). 0 Si tous les éléments de la ligne d'index de la table simplexe d'un problème de maximisation sont non négatifs, alors la conception de base de ce problème est optimale, et avec

il y a un maximum de fonction objectif sur l'ensemble des plans-problèmes.. Théorème 4(cas de fonction objectif illimitée) j . j Si la ligne d'index de la table simplex d'un problème de maximisation contient un élément négatif avec

, et dans la colonne inconnue x

tous les éléments sont non positifs, alors sur l'ensemble des plans-problèmes, la fonction objectif n'est pas bornée par le haut.

Méthode simplexe :

Nous écrivons ce KZLP dans la table simplex originale.

Si tous les éléments de la ligne d'index de la table simplexe sont non négatifs, alors le plan de base du problème est optimal (Théorème 3).

Si la ligne d'index contient un élément négatif sur lequel il n'y a pas d'élément positif dans le tableau, alors la fonction objectif n'est pas bornée par le haut sur l'ensemble des plans et le problème n'a pas de solution (Théorème 4).

S'il y a au moins un élément positif dans le tableau au-dessus de chaque élément négatif de la ligne d'index, alors vous devez passer à une nouvelle table simplex pour laquelle le plan de base n'est pas pire que le précédent (théorème 2). A cet effet (voir preuve du théorème 1) si c'est un système avec une base et c'est tout b sélectionner une colonne clé dans le tableau, à la base de laquelle se trouve tout élément négatif de la ligne d'index ;

sélectionner la relation clé (la plus petite des relations

Lorsque l’on considère le tableau simplex résultant, l’un des trois cas décrits dans les paragraphes se présentera certainement. 2, 3, 4. Si des situations surviennent dans les paragraphes. 2 ou 3, alors le processus de résolution du problème se termine, mais si la situation de l'étape 4 se présente, le processus continue.

Si l’on tient compte du fait que le nombre de plans de base différents est fini, alors deux cas sont possibles :

après un nombre fini d'étapes, le problème sera résolu (les situations 2 ou 3 se présenteront) ;

à partir d'une certaine étape apparaît boucle(répétition périodique des tableaux simplex et des plans de base).

Ces tâches sont appelées problèmes doubles symétriques.

Notons les caractéristiques suivantes reliant ces tâches :

L’un des problèmes est un problème de maximisation et l’autre un problème de minimisation.

Dans le problème de maximisation, toutes les inégalités sont ≤, et dans le problème de minimisation, toutes les inégalités sont ≥.

Le nombre d’inconnues d’un problème est égal au nombre d’inégalités de l’autre.

Les matrices de coefficients pour les inconnues dans les inégalités des deux problèmes sont mutuellement transposées.

Les termes libres des inégalités de l'un des problèmes sont égaux aux coefficients des inconnues correspondantes dans l'expression de la fonction objectif de l'autre problème.

Algorithme de construction d'un problème dual.

1. Ramenez toutes les inégalités du système de contraintes du problème initial à un seul sens - à la forme canonique.

2. Créez une matrice étendue du système A, qui comprend la colonne b i et les coefficients de la fonction objectif F.

3. Trouvez la matrice transposée A T.

4. Notez le double problème. Théorème 5.

f(x) ≤ g(La valeur de la fonction objectif du problème de maximisation pour aucun de ses plans ne dépasse la valeur de la fonction objectif de son problème de double minimisation pour aucun de ses plans, c'est-à-dire que l'inégalité suivante est vraie :),

oui appelé.

inégalité fondamentale de la dualité (Théorème 6.condition suffisante pour l'optimalité

). (Si pour certains plans de problèmes duaux les valeurs des fonctions objectifs sont égales, alors ces plans sont optimaux.Théorème 7. théorème fondamental de la dualité).

Si un ZLP a un optimal fini, alors son dual a également un optimal fini, et (valeurs optimalesles fonctions cibles coïncident. Si la fonction objective de l’un des problèmes duaux n’est pas limitée, alors les conditions de l’autre problème sont contradictoires.

Théorème 8.

Les composantes de la solution optimale du dual ZLP sont égales aux éléments correspondants de la ligne d'index de la table simplexe optimale du problème direct, correspondant aux variables supplémentaires.

Théorème 11.(critère d'optimalité d'un plan de problème de transport). Pour que le plan de transport) soit optimal, il est nécessaire et suffisant qu'il existe des nombres () et () qui satisfont aux conditions suivantes :

a) pour toutes les cellules de base du plan (>0) ;

b) pour toutes les cellules libres (=0).

Méthode potentielle

Étape 1. Vérifiez si cette tâche de transport est clôturée. Si oui, passez à la deuxième étape. Sinon, réduisez-le à un problème fermé en introduisant soit un fournisseur fictif, soit un consommateur fictif.

Étape 2. Trouver la solution de référence initiale (plan de référence initial) du problème de transport fermé.

Étape 3. Vérifiez l'optimalité de la solution de support résultante :

calculer le potentiel des fournisseurs pour cela toi je et les consommateurs v j

pour toutes les cellules libres ( b, j) calculer des estimations ;

si toutes les estimations sont non positives (), alors la solution du problème est terminée : le plan de référence original est optimal. Si parmi les évaluations il y en a au moins une positive, alors nous passons à la quatrième étape.

Étape 4. Sélectionnez une cellule ( b * ,j * ) avec l'estimation la plus positive et pour cela construire un cycle fermé de redistribution des marchandises. Le cycle commence et se termine dans la cellule sélectionnée. b * , j * On obtient une nouvelle solution de support dans laquelle la cellule (

) sera occupé. Revenons à la troisième étape.

Après un nombre fini d'étapes, une solution optimale sera obtenue, c'est-à-dire un plan optimal de transport des produits des fournisseurs aux consommateurs. Un point s'appelle un point maximum local

, s'il existe un voisinage de ce point tel que

Conditions nécessaires à l’optimalité x * Pour qu'une fonction d'une variable ait en un point

extremum local, il faut que la dérivée de la fonction en ce point soit égale à zéro,

Pour qu’une fonction ait un extremum local en un point, il faut que toutes ses dérivées partielles en ce point disparaissent x * Si au point x * la dérivée première de la fonction est égale à zéro, et la dérivée seconde >0, alors la fonction au point<0 то функция в точке x * a un minimum local si 2 produits,

a un maximum local. Théorème 4. x * Si une fonction d'une variable a en un point n - dérivés jusqu'à (

1) l'ordre est égal à zéro, et la dérivée de l'ordre n n'est pas égale à 0, alors, n Si x * même, alors point final

est un point minimum si,fn(x)>0<0.

point maximum si fn(x) n Si x * bizarre, alors pointe du doigt

– point d'inflexion. matrice de forme quadratique .

La forme quadratique (5) est appelée positif défini, si pour Q(X) >0 et défini négativement, si pour.Q(X)<0

Matrice symétrique UN appelé positif défini, si la forme quadratique (5) construite à partir de celle-ci est définie positive.

Une matrice symétrique s'appelle défini négativement, si la forme quadratique (6) construite à partir de celle-ci est définie négative.

Critère de Sylvester : une matrice est définie positive si tous ses mineurs angulaires sont supérieurs à zéro.

Une matrice est définie négative si les signes des mineurs du coin alternent.

Pour qu'une matrice soit définie positive, toutes ses valeurs propres doivent être supérieures à zéro.

Valeurs propres– racines du polynôme.

Une condition suffisante d’optimalité est donnée par le théorème suivant.

Théorème 5. Si en un point stationnaire la matrice hessienne est définie positive, alors ce point est un point minimum local, si la matrice hessienne est définie négative, alors ce point est un point maximum local.

Conflit est une contradiction causée par les intérêts opposés des parties.

Situation de conflit- une situation dans laquelle des parties dont les intérêts sont totalement ou partiellement opposés.

Jeu - il s'agit d'un conflit réel ou formel dans lequel il y a au moins deux participants, chacun s'efforçant d'atteindre ses propres objectifs

Règles du jeu nommer les actions autorisées de chaque joueur visant à atteindre un certain objectif.

Par paiement s'appelle l'évaluation quantitative des résultats du jeu.

Jeu de double– un jeu auquel seulement deux parties (deux joueurs) participent.

Jeu à somme nulle ou antagoniste - un jeu de double dans lequel le montant du paiement est nul, c'est-à-dire si la perte d'un joueur est égale au gain de l'autre.

Le choix et la mise en œuvre d'une des actions prévues par le règlement sont appelés le tour du joueur. Les mouvements peuvent être personnels et aléatoires.

Déménagement personnel est un choix conscient par un joueur d'une des actions possibles (par exemple, un coup dans une partie d'échecs).

Déplacement aléatoire est une action choisie au hasard (par exemple, choisir une carte dans un jeu mélangé).

Stratégie joueur - c'est le choix sans ambiguïté du joueur dans chacune des situations possibles où ce joueur doit effectuer un coup personnel.

Stratégie optimale- c'est la stratégie d'un joueur qui, lorsque le jeu est répété plusieurs fois, lui procure le gain moyen maximum possible ou le minimum de perte moyenne possible.

Matrice de paiement– la matrice résultante A ou, en d'autres termes, matrice de jeu s.

Jeu fini de dimension(m  n) est un jeu défini par une matrice A de dimension (m  n).

Maximin ou le prix le plus bas du jeu appelons le nombre alpa = max(i)(min aij)(j)

et la stratégie correspondante (string) maximin.

Minimax ou prix le plus élevé du jeu appelons le nombre Beta = min(j)(max aij)i

et la stratégie correspondante (colonne) minimax.

Le prix inférieur du jeu ne dépasse toujours pas le prix supérieur du jeu.

Jeu avec un point de selle appelé le jeu pour lequel. Alp = bêta

Au prix du jeu est appelée la quantité v si.v = alp = beta

Stratégie mixte Le joueur est un vecteur dont chacune des composantes montre la fréquence relative d’utilisation par le joueur de la stratégie pure correspondante.

Théorème 2 .

Le théorème principal de la théorie des jeux matriciels.

Chaque jeu matriciel à somme nulle a une solution dans les stratégies mixtes.3

T

Si l'un des joueurs utilise une stratégie mixte optimale, alors son gain est égal au coût du jeu  quelle que soit la fréquence à laquelle le deuxième joueur utilise ses stratégies (y compris les stratégies pures).

jouer avec la nature - un jeu dans lequel nous n'avons aucune information sur le comportement du partenaireRisque r je

Risque r = si c'est un système avec une base et c'est tout j - joueur lors du choix d'une stratégie A i dans des conditions H j s'appelle la différence b ,

un si c'est un système avec une base et c'est tout j Où j- élément maximum dans

- ème colonne.

Un graphe est une collection d’ensembles non vides appelés

l'ensemble des sommets du graphe et l'ensemble des paires de sommets, appelés

bords du graphique.

Si les paires de sommets considérées sont ordonnées, alors le graphe

est appelé orienté (digraphe), sinon –

désorienté.

DANS

Un itinéraire (chemin) dans un graphe reliant les sommets A et B est appelé

séquence d'arêtes dont la première provient du sommet A, commençant

la suivante coïncide avec la fin de la précédente, et la dernière arête est incluse dans

en haut V.

Un graphe est dit connecté si pour deux de ses sommets il existe un chemin

les reliant. Sinon, le graphe est dit déconnecté.

Un graphe est dit fini si le nombre de ses sommets est fini.

Si un sommet est le début ou la fin d’une arête, alors le sommet et l’arête

sont appelés incidents. Le degré (ordre) d'un sommet est le nombre d'arêtes qui lui sont incidentes.

Un chemin d'Euler (chaîne eulérienne) dans un graphe est un chemin passant par tout

bords du graphique et, de plus, une seule fois.

Un cycle eulérien est un chemin eulérien qui est un cycle.

Un graphe eulérien est un graphe contenant un cycle eulérien.

Un cycle d'Euler existe si et seulement si le graphe est connexe et qu'il

il n'y a pas de sommets de degré impair.

Théorème. Un chemin d'Euler dans un graphe existe si et seulement si le graphe

connecté et le nombre de sommets de degré impair est zéro ou deux.

Un arbre est un graphe connexe sans cycles qui a un sommet initial

(racine) et sommets extrêmes (degré 1); les chemins allant du sommet source aux sommets externes sont appelés branches.

Un réseau (ou diagramme de réseau) est un espace fini orienté

un graphe connecté qui a un sommet initial (source) et un sommet final (puits).

Le poids d’un chemin dans un graphe est la somme des poids de ses arêtes.

Le chemin le plus court d’un sommet à un autre sera appelé chemin

poids minimum.

Le poids de ce chemin sera appelé la distance entre

des sommets.

Le travail est un processus long qui nécessite des ressources,

ou une dépendance logique entre deux ou plusieurs emplois

Un événement est le résultat de l'exécution d'un ou plusieurs jobs

Un chemin est une chaîne d'ouvrages successifs reliant

sommets de début et de fin.

La durée du trajet est déterminée par la somme des durées

ses travaux constituants.

Règles d'élaboration des schémas de réseau.

1. Il ne doit y avoir aucun événement de blocage dans le diagramme de réseau (sauf

final), c'est-à-dire ceux qui ne sont suivis d'aucun travail.

2. Il ne devrait y avoir aucun événement (à l'exception du premier) qui ne soit précédé par bien que

juste un travail.

3. Il ne doit y avoir aucun cycle dans le diagramme de réseau.

4. Deux événements ne sont reliés que par un seul travail.

5. Le schéma de réseau doit être ordonné.

Tout chemin dont le début coïncide avec l'événement initial et dont la fin coïncide avec

la terminaison est appelée un chemin complet. Chemin complet avec maximum

la durée du travail s'appelle le chemin critique

La hiérarchie est un certain type de système basé sur l'hypothèse que les éléments du système peuvent être regroupés en ensembles non liés.

Description de la méthode d'analyse hiérarchique

Construction de matrices de comparaison par paires

Trouvez lambda max et résolvez le système par rapport au vecteur de poids

Synthèse des priorités locales

Vérification de la cohérence des matrices de comparaison par paires

Synthèse des priorités mondiales

Évaluer la cohérence de l’ensemble de la hiérarchie

La méthode simplexe est une méthode permettant de résoudre un problème de programmation linéaire. L'essence de la méthode est de trouver un plan initial réalisable, puis d'améliorer le plan jusqu'à ce que la valeur maximale (ou minimale) de la fonction objectif dans un ensemble polyédrique convexe donné soit atteinte ou que l'insolvabilité du problème soit déterminée.

Considérons le problème de programmation linéaire suivant sous forme canonique :

Méthode de base artificielle

Comme indiqué ci-dessus, pour un problème écrit sous forme canonique, si parmi les vecteurs colonnes de la matrice UN Il y a m unitaire et linéairement indépendant, vous pouvez directement préciser le plan de référence. Cependant, pour de nombreux problèmes de programmation linéaire écrits sous forme canonique et disposant de plans de référence, parmi les vecteurs colonnes de la matrice UN pas toujours disponible m unité et linéairement indépendante. Considérez le problème suivant :

Supposons que nous devions trouver le maximum d'une fonction

dans des conditions

où sont les premiers n les éléments sont nuls. Variables sont dits artificiels. Colonnes de vecteurs

(28)

former une base dite artificielle m espace vectoriel dimensionnel.

Puisque le problème étendu possède un plan de référence, sa solution peut être trouvée par la méthode du simplexe.

Théorème 4. Si dans le plan optimal problème étendu (24)−(26) valeurs des variables artificielles , Que est le plan optimal pour le problème (21)−(23).

Ainsi, si dans le plan optimal trouvé pour le problème étendu, les valeurs des variables artificielles sont égales à zéro, alors le plan optimal pour le problème d'origine est obtenu. Arrêtons-nous plus en détail sur la recherche d'une solution au problème étendu.

La valeur de la fonction objectif pour le plan de référence (27) :

Nous remarquons que F(X) et se compose de deux parties indépendantes, dont l'une dépend de M., et l'autre - non.

Après calcul F(X) et leurs valeurs, ainsi que les données initiales de la tâche étendue, sont saisies dans un tableau simplex, comme indiqué ci-dessus. La seule différence est que ce tableau contient une ligne de plus qu'un tableau simplex classique. En même temps dans ( m La +1)ème ligne contient des coefficients qui ne contiennent pas M., et dans ( m+2)ème ligne − coefficients pour M..

Lors du passage d'un plan de référence à un autre, un vecteur correspondant au plus grand nombre négatif en valeur absolue ( m+2) lignes. Un vecteur artificiel exclu de la base n’a pas de sens d’être réintroduit dans la base. Lors du passage à un autre plan de référence, il peut arriver qu'aucun des vecteurs artificiels ne soit exclu de la base. Le recalcul du tableau simplex lors du passage d'un plan de référence à un autre s'effectue selon les règles habituelles de la méthode simplex (voir ci-dessus).

Le processus itératif est réalisé selon m+2 ligne tant que les éléments m+2 lignes correspondant aux variables ne deviendra pas non négatif. De plus, si les variables artificielles sont exclues de la base, alors le plan trouvé du problème étendu correspond à un plan de référence du problème d'origine.

m+2 lignes, colonnes x 0 est négatif, alors le problème initial n’a pas de solution.

Si toutes les variables artificielles ne sont pas exclues de la base et de l'élément m+2 lignes, colonnes x 0 est égal à zéro, alors le plan de référence du problème d'origine est dégénéré et la base contient au moins un des vecteurs de la base artificielle.

Si le problème initial contient plusieurs vecteurs unitaires, ils doivent alors être inclus dans la base artificielle.

Si lors des itérations m La ligne +2 ne contient plus d'éléments négatifs, puis le processus d'itération se poursuit avec m Ligne +1, jusqu'à ce que le plan optimal pour le problème étendu soit trouvé ou que l'insolvabilité du problème soit révélée.

Ainsi, le processus de recherche d'une solution au problème de programmation linéaire (21)−(23) à l'aide de la méthode des bases artificielles comprend les étapes principales suivantes :

• Composez le problème étendu (24)−(26).
• Trouvez le plan de référence du problème étendu.
• En utilisant la méthode simplexe, les vecteurs artificiels sont exclus de la base. En conséquence, le plan de référence du problème d'origine est retrouvé ou son insolvabilité est enregistrée.
• En utilisant le plan de référence trouvé du ZLP (21)−(23), soit ils trouvent le plan optimal du problème d'origine, soit ils établissent son insolvabilité.

Pour résoudre des problèmes de programmation linéaire en ligne, utilisez une calculatrice

Composantes du modèle mathématique

La base pour résoudre les problèmes économiques repose sur des modèles mathématiques.

Modèle mathématique le problème est un ensemble de relations mathématiques qui décrivent l’essence du problème.

• sélection des variables du problème
• élaborer un système de restrictions
• choix de la fonction objectif

Variables de tâche sont appelées les quantités X1, X2, Xn, qui caractérisent complètement le processus économique. Ils s'écrivent généralement sous forme de vecteur : X=(X1, X2,...,Xn).

Système de restrictions les problèmes sont un ensemble d’équations et d’inégalités qui décrivent les ressources limitées du problème considéré.

Fonction objectif les tâches sont appelées fonction de variables de tâche qui caractérisent la qualité de la tâche et dont l'extremum doit être trouvé.

De manière générale, un problème de programmation linéaire peut s’écrire comme suit :

Cette entrée signifie ce qui suit : trouver l'extremum de la fonction objectif (1) et les variables correspondantes X=(X1, X2,...,Xn) à condition que ces variables satisfassent au système de restrictions (2) et à la non-négativité conditions (3).

Solution valide(plan) d'un problème de programmation linéaire est tout vecteur à n dimensions X=(X1, X2,...,Xn) qui satisfait le système de contraintes et de conditions de non-négativité.

L'ensemble des solutions réalisables (plans) des formes de problèmes région de solutions réalisables(ODR).

La solution optimale(plan) d'un problème de programmation linéaire est une solution (plan) admissible du problème dans laquelle la fonction objectif atteint un extremum.

Condition: Pour produire n types de produits, m types de ressources sont utilisés. Créez un modèle mathématique.

Connu:

• bi (i = 1,2,3,...,m) - réserves de chaque i-ème type de ressource ;
• aij (i = 1,2,3,...,m; j=1,2,3,...,n) - les coûts de chaque i-ème type de ressource pour la production d'une unité de volume de le j-ième type de produit ;
• cj (j = 1,2,3,...,n) - profit de la vente d'une unité de volume du jème type de produit.

Il est nécessaire d'élaborer un plan de production garantissant un profit maximum dans des conditions données de restrictions sur les ressources (matières premières).

Solution:

Introduisons un vecteur de variables X=(X1, X2,...,Xn), où xj (j = 1,2,...,n) est le volume de production du j-ème type de produit.

Les coûts du i-ième type de ressource pour la production d'un volume donné xj de produits sont égaux à aijxj, donc la restriction sur l'utilisation des ressources pour la production de tous types de produits a la forme :
Le bénéfice de la vente du jième type de produit est égal à cjxj, donc la fonction objectif est égale à :

Répondre- Le modèle mathématique ressemble à :

Forme canonique d'un problème de programmation linéaire

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 appelé canonique.

Il peut être représenté en notation coordonnée, vectorielle et matricielle.

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

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

• A - matrice des coefficients du système d'équations
• X - colonne matricielle de variables de tâche
• Ао - matrice-colonne des parties droites du système de restrictions

On utilise souvent des problèmes de programmation linéaire, appelés symétriques, qui en notation matricielle ont la forme :

Réduire un problème général de programmation linéaire à une 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 de problèmes économiques, les contraintes se forment principalement sous la forme d'un système d'inégalités, il faut donc pouvoir passer d'un système d'inégalités à un système d'équations.

Prenons l'inégalité linéaire a1x1+a2x2+...+anxn≤b et ajoutons à son côté gauche une certaine valeur xn+1, telle que l'inégalité se transforme en l'égalité a1x1+a2x2+...+anxn+xn+1=b . De plus, cette valeur xn+1 est non négative.

Regardons tout à l'aide d'un exemple.

Amenez le problème de programmation linéaire sous forme canonique :

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, on introduit des variables supplémentaires non négatives x4 x5 (dans le modèle mathématique cette opération est marquée de la lettre D).
La variable x4 est introduite dans le côté gauche de la deuxième inégalité avec le signe « + », puisque l'inégalité a la forme « ≤ ».
La variable x5 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 x4 x5 sont saisies dans la fonction objectif avec un coefficient. égal à zéro.
Nous écrivons le problème sous forme canonique :