La méthode simplexe est universelle. Avec son aide, tout problème de programmation linéaire peut être résolu. Cependant, du fait de sa polyvalence, il n’est pas exempt de certains inconvénients. Dans certains cas, la méthode dite dual est plus adaptée à la résolution de problèmes de programmation linéaire. Cette méthode est basée sur la théorie de la dualité, l’une des composantes les plus importantes de la théorie générale de la programmation linéaire.

La théorie de la dualité est utilisée pour développer des méthodes permettant de résoudre de nombreuses classes pratiquement importantes de problèmes d'optimisation linéaire : problèmes de type transport, problèmes d'entiers linéaires, etc. Considérons les principales dispositions de cette théorie.

À chaque problème de programmation linéaire correspond un autre problème, en un certain sens son contraire. Si le premier problème est dit direct, alors le contraire est appelé double. Puisque le problème dual du problème dual est le problème direct originel, peu importe quel problème est appelé direct et lequel dual. Par conséquent, les problèmes directs et duaux sont appelés problèmes de double paire.

Le problème dual est formulé directement à partir du problème direct en utilisant Certaines règles. Étant donné que les problèmes directs peuvent avoir des restrictions sous forme d'inégalités de type, de type ou sous forme d'égalités, les règles pour obtenir des problèmes doubles s'avèrent différentes pour eux.

Il existe des problèmes duaux symétriques, asymétriques et mixtes. Dans les problèmes symétriques, les contraintes du problème direct ont la forme . Dans les contraintes du problème asymétrique, les contraintes du problème direct utilisent des signes égaux. Dans les problèmes mixtes, les deux types de relations « inférieur ou égal à » et « égal » sont utilisés. Dans les problèmes asymétriques et mixtes, l’exigence de non-négativité n’est pas imposée aux variables nouvellement introduites.

Les calculs basés sur les relations de dualité commencent par réduire les problèmes directs et duaux à une forme standard. Par conséquent, nous pouvons nous limiter à la formulation de règles pour la formation d’un problème dual du problème de programmation linéaire standard. Les règles permettant d'obtenir le problème dual pour d'autres types de problèmes LP peuvent être obtenues à partir de ces règles.

Écrivons le problème LP sous forme standard :

,

,

je=1,..,m; j=1,..,n.

Appelons ce problème direct. La tâche sera alors double par rapport à elle :

,

je=1,..,m; j=1,..,n.

Après avoir analysé les tâches, nous pouvons tirer les conclusions suivantes :

1. Chaque contrainte du problème direct correspond à une variable du problème dual.

2. Chaque variable du problème direct correspond à une contrainte du problème dual.

3. Les coefficients de toute variable dans les contraintes du problème direct deviennent les coefficients de la contrainte du problème dual correspondant à cette variable, et le côté droit de la contrainte générée est égal au coefficient de cette variable dans l'expression du fonction objectif.

4. Le type d'extremum du problème dual est opposé au type d'extremum du problème direct ;

5. Les vecteurs B et C dans les problèmes directs et duaux changent de place ;

6. Matrice UN le problème dual est obtenu en transposant la matrice UN tâche directe;

7. Toutes les restrictions du problème dual ont la forme pour le problème de maximisation et la forme pour le problème de minimisation de forme linéaire.

Pour le cas d’un problème dual symétrique :

Pour le cas d’un problème asymétrique :

Le double problème a la forme :

Les problèmes mixtes contiennent des contraintes sous forme d'égalités et d'inégalités. Lors de la composition d’un problème dual, il est nécessaire d’utiliser des règles de transition pour les problèmes symétriques et asymétriques.

Les exemples ci-dessous servent à illustrer les règles permettant d’obtenir des problèmes doubles.

Exemple Un problème de programmation linéaire est donné (à gauche de chaque contrainte se trouve la variable duale qui lui est associée). Cette tâche fait référence à asymétrique.

,

Formulons un double problème pour ce problème. La fonction objectif du problème dual est une forme linéaire obtenue comme le produit du vecteur b=(10,20,60,80) par le vecteur de variables du problème dual Y =( ). De plus, puisque dans le problème direct la fonction objectif est maximisée, dans le problème dual elle est minimisée. Compte tenu des commentaires formulés, nous obtenons

Le côté gauche de la première contrainte du problème dual est le produit du vecteur du système de contraintes du problème direct associé à la variable , et du vecteur des variables du problème dual. Le membre droit de cette contrainte est égal au coefficient de la variable , dans la fonction objectif du problème direct.

Et comme, en plus, le problème direct est celui de trouver un maximum, la première contrainte a la forme :

En raisonnant de la même manière, on obtient la deuxième contrainte du problème dual : . L’absence de variable dans cette contrainte est due au fait que dans la deuxième contrainte du problème direct il n’y a pas de variable.

La variable associée à la troisième variable du problème dual n'apparaît que dans la première contrainte du problème direct. Pour cette raison, pour la troisième contrainte on obtient . En raisonnant par analogie, nous obtenons les quatrième, cinquième et sixième restrictions : .

Ainsi, bien que la condition de non-négativité n'ait pas été spécifiquement imposée aux variables du problème dual, elle s'est néanmoins avérée remplie pour toutes.

ExempleÉtant donné un problème de programmation linéaire dans formulaire non standard

,

,

,

Signe illimité .

Écrivons ce problème sous forme standard. Pour ce faire, effectuons un changement de variables , introduisons une variable redondante dans la deuxième contrainte, et une variable supplémentaire dans la troisième. On a

,

.

Formulons un double problème. Puisque dans le problème direct la fonction objectif est minimisée, la fonction objectif du problème dual a la forme .

Pour la même raison, les première, deuxième et troisième contraintes du problème dual, associées respectivement aux variables s'écrivent ainsi :

,

Puisque la variable n'apparaît que dans la deuxième et la variable uniquement dans la troisième équation du problème direct, les contraintes associées du problème dual sont :

.

Ainsi, parmi les trois variables du problème dual, l'une s'est avérée être de signe illimité.

En utilisant les théorèmes de dualité, connaissant la solution à l'un des problèmes, vous pouvez trouver la solution optimale à l'autre sans la résoudre.

Considérons un problème mixte.

Le double problème pour cela aura la forme :

Si nous utilisons la forme canonique d’un problème de programmation linéaire, nous avons alors affaire à un problème de programmation linéaire asymétrique.

La forme canonique du problème est :

Le double problème ressemblera à :

Théorème 1. Pour toute paire de solutions réalisables aux problèmes directs et duaux, la valeur de la fonction objectif dans le problème de maximisation ne dépasse pas la valeur de la fonction objectif dans le problème de minimisation.

La valeur pratique de ce théorème est la suivante. En pratique, il est parfois préférable d’obtenir une solution proche de l’optimum, mais en un temps court, que d’obtenir une solution optimale, mais en un temps nettement plus long. Dans ce cas, la dernière inégalité peut servir d'estimation de la proximité de la solution obtenue à l'itération suivante par rapport à l'optimum.

Théorème 2. Si l'un des problèmes duaux a une solution optimale, alors l'autre a également une solution optimale et les valeurs des fonctions objectives pour les deux solutions coïncident. Si l’un des deux problèmes a une fonction objective illimitée, alors l’autre est insoluble, c’est-à-dire qu’il n’a pas de solutions réalisables.

Théorème. Pour que les solutions admissibles soient optimales, il faut et il suffit qu'elles satisfassent au système d'équations

.

Ce théorème signifie que l'une des variables de tout problème est strictement supérieure à zéro, alors la contrainte correspondante dans l'autre problème dual est satisfaite comme une égalité stricte, et, inversement, si avec une solution optimale n'importe quelle contrainte est satisfaite comme une inégalité stricte , alors la variable correspondante dans la solution optimale est nulle.

Exemple Résolvons un problème symétrique. Laissez le problème original avoir la forme

En résolvant graphiquement le problème, nous obtenons

Créons-lui un double problème

Donc les fonctions objectifs au point optimal sont égales, alors

Puisque les variables
, alors les contraintes correspondantes dans le problème dual contiennent un signe égal. Ces restrictions ont la forme

Remplaçons les valeurs dans les restrictions . On a

.

Dans ce système, seule la première inégalité est stricte. Ainsi, . On retrouvera d'autres valeurs des variables du système d'équations

.

En résolvant ce système d'équations algébriques linéaires, nous obtenons

Résolvons le même problème, mais en supposant que la solution soit connue

Puisque les deuxième et troisième variables sont strictement supérieures à zéro, la contrainte correspondante est satisfaite comme une égalité stricte.

.

Décider ce systèmeéquations, on obtient

Si le problème d'origine est résolu à l'aide de la méthode du simplexe et que les coefficients sont obtenus dans la fonction objectif finale - matrice - rangée de coefficients, alors la solution du problème double peut être trouvée à l'aide de la formule où est la matrice des coefficients des variables de base de la fonction objectif dans la solution optimale du problème d'origine.

Considérons l'interprétation économique du double problème.

Théorème. Les valeurs des variables dans la solution optimale du problème dual représentent des estimations de l'influence des termes libres des contraintes du problème d'origine sur la valeur optimale de sa fonction objectif. Parce que

Ensuite, les variables doubles montrent comment la fonction objectif change lorsque la ressource change d'un

Brève théorie

Nous remplissons le tableau simplex de la 0ème itération.

PA Simplexe
relation		 8 6 4 0 0 0 0 520 16 18 9 1 0 0 65/2 0 140 7 7 2 0 1 0 20 0 810 9 2 1 0 0 1 90 0 -8 -6 -4 0 0 0

Puisque nous résolvons le problème au maximum, la présence de nombres négatifs dans la ligne d'index lors de la résolution du problème au maximum indique que nous n'avons pas obtenu la solution optimale et qu'il faut passer du tableau de la 0ème itération au suivant.

On passe à l'itération suivante comme suit :

La première colonne correspond à .

La ligne clé est déterminée par le rapport minimum de termes libres et de membres de la colonne principale (relations simplex) :

A l'intersection de la colonne clé et de la ligne clé, nous trouvons l'élément d'activation, c'est-à-dire 7.

Nous commençons maintenant à compiler la 1ère itération. Au lieu d'un vecteur unitaire, nous introduisons le vecteur .

DANS nouveau tableauà la place de l'élément d'activation, nous écrivons 1, tous les autres éléments de la colonne clé sont des zéros. Les éléments de chaîne clé sont divisés en éléments d'activation. Tous les autres éléments du tableau sont calculés à l'aide de la règle du rectangle.

On obtient le tableau de la 1ère itération :

PA Simplexe
relation		 8 6 4 0 0 0 0 200 0 2 31/7 1 -16/7 0 1400/31 8 20 1 1 2/7 0 1/7 0 70 0 630 0 -7 -11/7 0 -9/7 1 - 160 0 2 -12/7 0 8/7 0

La colonne clé de la 1ère itération correspond à .

On retrouve la ligne clé, pour cela on définit :

A l'intersection de la colonne clé et de la ligne clé, nous trouvons l'élément d'activation, c'est-à-dire 31/7.

Le vecteur est dérivé de la base et le vecteur est introduit.

On obtient le tableau de la 2ème itération :

PA Simplexe
relation		 8 6 4 0 0 0 4 1400/31 0 14/31 1 7/31 -16/31 0 8 220/31 1 27/31 0 -2/31 9/31 0 0 21730/31 0 -195/31 0 11/31 -65/31 1 7360/31 0 86/31 0 12/31 8/31 0

Dans la ligne d'index, tous les termes sont non négatifs, donc la solution suivante au problème de programmation linéaire est obtenue (nous l'écrivons à partir de la colonne des termes libres) :

Ainsi, il faut vendre 7,1 mille roubles. marchandises du 1er type et 45,2 mille roubles. marchandises du 3ème type. Il n'est pas rentable de vendre un produit du 2ème type. Dans ce cas, le bénéfice sera maximum et s'élèvera à 237,4 mille roubles. Si le plan optimal est mis en œuvre, la ressource restante du 3ème type sera de 701 unités.

Problèmes de programmation double linéaire.

Chaque problème de programmation linéaire correspond à un double problème.

Algorithme pour composer un problème double.

Exemple 1.

Composer un double problème

1. Nous ramenons toutes les inégalités du système de contraintes du problème initial à un seul sens

2. Composez une matrice étendue

3. Transposer la matrice

4. Formuler le double problème

Problème d'origine (direct)

Double problème

Un problème de programmation linéaire peut être considéré comme un modèle d'allocation de ressources limitées dans lequel la fonction objectif représentant le profit ou le revenu des activités de production est soumise à une maximisation. Si l’on considère le problème de programmation linéaire de ce point de vue, le double problème correspondant reçoit une interprétation économique intéressante.

variable à je le double problème représente le coût par unité de ressource je. Dans la littérature de recherche opérationnelle, les variables à je le double problème est souvent appelé double prix . De plus, on les appelle parfois prix fictifs Et multiplicateurs simplex .

De même, pour toute paire de solutions admissibles aux problèmes directs et duaux, l’inégalité F < z peut être interprété comme suit :

Revenu< Общая стоимость ресурсов

Cette relation montre que tant que le revenu total de tous les types d’activités est strictement inférieur au coût total de toutes les ressources utilisées, la solution aux problèmes directs et doubles ne peut être optimale. L'optimum (revenu maximum) ne peut être atteint que lorsque toutes les ressources consommées sont pleinement utilisées.

L'interprétation économique du théorème de la seconde dualité, ainsi que ses conséquences sur la non-rigidité complémentaire, sont d'un grand intérêt pratique.

1. Si l'évaluation totale de la ième ressource est positive

alors cette ressource est pleinement utilisée conformément au plan optimal x*

2. Si ième ressource pas entièrement utilisé

alors son estimation optimale est nulle et i-ème contrainte immatériel.

3. Si, conformément au plan optimal x* j-ième produits produit

alors cette production est efficace, puisque le prix d'une unité du j-ième produit

égal au coût de sa production en unités

4. Si la production jième produits non rentable (les coûts réduits sont non nuls

alors, conformément au plan optimal, ce produit n'est pas fabriqué

Ainsi, les estimations doubles sont liées à la conception optimale du problème direct. Tout changement dans les données initiales d'un problème direct affecte son plan optimal et le système d'estimations doubles. À leur tour, les doubles évaluations servent d’outil d’analyse et de prise de décisions appropriées dans des situations commerciales changeantes.

Des règles pour composer des problèmes doubles sont présentées. Les paires symétriques, asymétriques et mixtes sont considérées. Des exemples de composition de problèmes doubles sont analysés.

Contenu

Les problèmes de programmation linéaire duale ou conjuguée ont la propriété qu'à partir de la solution de l'un des problèmes, on peut obtenir une solution à un autre problème. Nous examinerons ici les règles de composition de problèmes doubles.

Problème double symétrique

Considérons un problème de programmation linéaire avec des variables non négatives et des inégalités d'un système de contraintes de la forme suivante :
(1.1) ;
(1.2)
Il y a quelques chiffres ici. Toutes les lignes du système (1.2) sont des inégalités signées.


(2.1) ;
(2.2)
Ici, toutes les lignes du système (2.2) sont des inégalités signées. La matrice des coefficients du système de contraintes (2.2) est la matrice transposée du système (1.2). Il contient des lignes et des colonnes. Le double problème comporte des variables. Toutes les variables sont non négatives.

Le problème initial (1) est souvent appelé problème direct et le problème (2) est appelé problème double. Si nous prenons le problème (2) comme premier, alors le problème (2) sera un problème direct et le problème (1) sera un problème double. Problèmes (1) et (2) sont appelés problèmes duaux symétriques.

Ainsi, un problème dual symétrique ne peut être composé que si toutes les variables du problème d'origine sont non négatives et que le système de contraintes ne contient pas d'égalités. Si le maximum de la fonction objectif est recherché, alors les inégalités doivent être converties sous la forme . Si un minimum est recherché, alors les inégalités doivent être converties sous la forme . Pour changer le signe, il faut multiplier les deux côtés de l'inégalité par -1 .

Un exemple de composition d'un problème dual symétrique


;

Le problème initial est de trouver le minimum. Par conséquent, toutes les inégalités doivent avoir des signes. Les première et troisième inégalités contiennent le signe. Multiplions-les par -1 :




Transposons cette matrice. Autrement dit, nous écrirons la première ligne comme première colonne, la deuxième ligne comme deuxième colonne et la troisième ligne comme troisième colonne.

Le double problème a la forme :
;

;

Double problème asymétrique

Défi maximal

Considérons le problème canonique de programmation linéaire maximale avec des variables non négatives et des égalités du système de contraintes :
(3.1) ;
(3.2)
Il y a quelques chiffres ici. Toutes les lignes du système (3.2) sont des égalités. Toutes les variables sont non négatives.

Le double problème a la forme :
(4.1) ;
(4.2)
Ici toutes les lignes du système (4.2) sont des inégalités signées. La matrice des coefficients du système de contraintes (4.2) est la matrice transposée du système (3.2). Le double problème comporte des variables. Les variables peuvent être positives ou négatives.

La différence entre la paire asymétrique de problèmes (3) et (4) et la paire symétrique (1) et (2) est que le système de contraintes (3.2) ne contient que des égalités, et dans le système (4.2) il n'y a pas de conditions pour la non-négativité des variables.

Tâche minimale

Considérons maintenant le problème canonique de programmation linéaire minimale :
(5.1) ;
(5.2)

Le double problème a la forme :
(6.1) ;
(6.2)

Le système de restrictions (6.2) diffère de (4.2) en ce que les inégalités ont des signes.

Relation avec une paire symétrique de problèmes duaux

Montrons qu'une paire asymétrique de problèmes (3)-(4) peut être obtenue à partir d'une paire symétrique (1)-(2).

Alors, ayons un problème direct avec une fonction objectif
(3.1)
et un système de restrictions
(3.2)
Chaque égalité peut être représentée par deux inégalités :

On multiplie les inégalités avec des signes par -1 :

Le système de restrictions présente des inégalités.

En utilisant les formules (1)-(2), nous obtenons un double problème :
;


le double problème a des variables non négatives :
.
Il est facile de voir que ces variables entrent dans le problème sous forme de différences
.

Faisons des substitutions
.
Puisque et , les variables peuvent être positives ou négatives.

Et nous obtenons le double problème (4) :
(4.1) ;
(4.2)

Si nous prenons (4) comme problème initial, alors, en effectuant toutes les actions dans l'ordre inverse, nous obtenons le double problème (3).

En utilisant la même méthode, on peut obtenir un problème double (6) à partir du problème (5) et un problème double (5) à partir du problème (6).

Problème mixte

Considérons maintenant un problème mixte.

Disons un problème direct (1) pour un maximum, dans le système de contraintes dont la ième ligne est une égalité. Le problème dual a alors la forme (2) à une exception près : la variable peut être positive ou négative. Autrement dit, il n'y a aucune restriction.

La même chose se produira si nous avons un problème direct (2) pour un minimum, dans le système de contraintes dont la ième ligne est une égalité. Le problème dual a la forme (1) à une exception près : la variable peut être de n'importe quel signe.

Ayons maintenant un problème direct (1) pour un maximum, mais il n'y a pas de contrainte. Autrement dit, une variable peut être positive ou négative. Alors le problème dual a la forme (2) à une exception près : la ième ligne du système de contraintes est une égalité.

Et enfin, ayons un problème direct (2) pour un minimum, mais il n'y a pas de contrainte . Alors le problème dual a la forme (1) à une exception près : la ième ligne du système de contraintes est une égalité.

Tout cela nous permet de formuler des règles pour composer des problèmes doubles.

Règles pour composer des problèmes doubles

1. Pour le problème du maximum original, on réduit toutes les inégalités du système de contraintes à la forme :
.
Pour le problème minimum initial, on réduit toutes les inégalités à la forme :
.
Si vous devez changer le signe, multipliez les deux côtés des inégalités par -1 .
2. Nous composons un problème dual de la même manière que pour une paire de problèmes symétriques.
3. Si dans le problème initial, la ième ligne du système de contraintes est une égalité, alors on raye la condition de non-négativité de la ième variable du problème dual.
4. Si dans le problème d'origine, il n'y a pas de condition de non-négativité pour la ème variable, alors dans la ème ligne du problème dual, nous changeons le signe d'inégalité en signe égal.

Un exemple de composition d'un problème dual mixte

Étant donné un problème de programmation linéaire :
;

Créez un double problème.

La fonction objectif a un terme libre 5. Pour l'amener à la forme (2.1), on introduit une variable et on ajoute l'égalité . Le problème prendra alors la forme :

;

Ce problème est un problème de recherche du minimum. Par conséquent, toutes les inégalités doivent avoir des signes. La troisième inégalité contient le signe. Par conséquent, multiplions-le par -1 :

Réécrivons le système de restrictions, en indiquant explicitement les coefficients des variables :

La matrice des coefficients du système de contraintes a la forme :

Transposons cette matrice. Autrement dit, nous écrirons la première ligne comme première colonne, la deuxième ligne comme deuxième colonne, et ainsi de suite.

Créons un double problème comme pour une paire symétrique.
;

Puisque dans le problème initial les 1ère, 2ème et 4ème lignes du système de contraintes sont des égalités, alors dans le problème dual les variables , et peuvent avoir n'importe quel signe. La seule variable non négative est . Ainsi, les conditions de non-négativité des variables sont de la forme :
.

Puisque dans le problème initial les variables et peuvent avoir des signes arbitraires, les 3ème et 4ème lignes du système de contraintes du problème dual sont des égalités.

Ainsi, le double problème a la forme :
;

De la quatrième équation. Remplacez la variable par sa valeur et multipliez la troisième ligne par -1 .

Il convient de noter que les méthodes de résolution des problèmes de programmation linéaire comprennent non pas à l’économie, mais aux mathématiques et à l’informatique. Dans le même temps, l'économiste doit offrir les conditions de dialogue les plus confortables avec le logiciel approprié. À leur tour, de telles conditions ne peuvent être assurées que par des environnements de développement dynamiques et interactifs qui disposent dans leur arsenal d'un ensemble de bibliothèques nécessaires à la résolution de tels problèmes. L'un des environnements de développement logiciel est définitivement Python.

Formulation du problème

Les publications envisageaient des solutions aux problèmes d'optimisation directe à l'aide de la méthode de programmation linéaire et suggéraient un choix raisonnable du solveur scipy. optimiser.

Or, on sait qu'à chaque problème de programmation linéaire correspond un problème dit distingué (dual). Dans celui-ci, par rapport au problème direct, les lignes se transforment en colonnes, les inégalités changent de signe, au lieu d'un maximum, un minimum est recherché (ou vice versa, au lieu d'un minimum, un maximum est recherché). La tâche duale au dual est la tâche originelle elle-même.

La résolution de ce double problème est très importante pour analyser l’utilisation des ressources. Dans cette publication, il sera prouvé que les valeurs optimales des fonctions objectives dans les problèmes original et dual coïncident (c'est-à-dire que le maximum dans le problème original coïncide avec le minimum dans le dual).

Les valeurs optimales des coûts de matériel et de main d'œuvre seront évaluées par leur contribution à la fonction objectif. Le résultat sera des « estimations objectivement déterminées » des matières premières et de la main-d’œuvre qui ne coïncident pas avec les prix du marché.

Solution du problème direct du programme de production optimal

Considérant haut niveau formation mathématique Pour la grande majorité des utilisateurs de cette ressource, je ne présenterai pas d'équations d'équilibre avec des restrictions supérieures et inférieures et l'introduction de variables supplémentaires pour passer aux égalités. Je donnerai donc immédiatement les désignations des variables utilisées dans la solution :
N – nombre de types de produits fabriqués ;
m – nombre de types de matières premières utilisées ;
b_ub - vecteur de ressources disponibles de dimension m ;
A_ub est une matrice de dimension m×N dont chaque élément est la consommation d'une ressource de type i pour la production d'une unité de produit de type j ;
c est le vecteur de profit de la production d'une unité de chaque type de produit ;
x – les volumes requis de produits fabriqués de chaque type (plan de production optimal) garantissant un profit maximum.

Fonction d'objectif
maxF(x)=c×x

Restrictions
A×x≤b

Valeurs numériques des variables :
N=5 ; m = 4 ; b_ub = ; A_ub = [, , ,]; c = .

Tâches
1. Trouvez x pour assurer un profit maximum
2. Recherchez les ressources utilisées lors de l'exécution de l'étape 1
3. Recherchez les ressources restantes (le cas échéant) lors de l'exécution de l'étape 1


Pour déterminer le maximum (par défaut le minimum est déterminé), les coefficients de la fonction objectif doivent s'écrire avec signe négatif c = [-25, -35,-25,-40,-30] et ignorez le signe moins devant profit.

Notations utilisées pour afficher les résultats :
X– un tableau de valeurs variables qui fournissent le minimum (maximum) de la fonction cible ;
mou– valeurs de variables supplémentaires. Chaque variable correspond à une contrainte d'inégalité. Une valeur variable de zéro signifie que la contrainte correspondante est active ;
succès– Vrai, si la fonction a réussi à trouver la solution optimale ;
statut– statut de la décision :
0 – la recherche de la solution optimale s'est terminée avec succès ;
1 – la limite du nombre d'itérations a été atteinte ;
2 – le problème n’a pas de solution ;
3 – la fonction objectif n’est pas limitée.
lente– nombre d'itérations effectuées.

Listage de la solution au problème d'optimisation directe

#!/usr/bin/python # -*- codage : utf-8 -*- import scipy depuis scipy.optimize import linprog # chargement de la bibliothèque LP c = [-25, -35,-25,-40,-30] # liste des coefficients de la fonction objectif b_ub = # liste des volumes de ressources A_ub = [, # matrice de valeurs de ressources spécifiques, , ] d=linprog(c, A_ub, b_ub) # recherche d'une solution pour key,val in d.items(): print(key ,val) # sortie de la solution if key=="x": q=#ressources utilisées print("A_ub*x",q) q1= scipy.array(b_ub)-scipy.array (q) #ressources restantes print(" b_ub-A_ub*x", q1)


Résultats de la résolution du problème
lente 3
statut 0

succès Vrai
x [ 0. 0. 18.18181818 22.72727273 150. ]
A_ub*x
b_ub-A_ub*x [0.0.0.90.90909091]
amusant -5863.63636364
mou [0. 0. 0. 90.90909091]

conclusions

  1. Le plan optimal pour les types de produits a été trouvé
  2. Utilisation réelle des ressources trouvée
  3. Le reste du quatrième type de ressource inutilisé a été trouvé [ 0. 0 0.0 0.0 90.909]
  4. Il n'est pas nécessaire d'effectuer les calculs selon l'étape 3, puisque le même résultat est affiché dans la variable slack

Solution du double problème sur le programme de production optimal

Le quatrième type de ressource dans la tâche directe n'est pas entièrement utilisé. La valeur de cette ressource pour l'entreprise s'avère alors inférieure à celle des ressources qui limitent la production, et l'entreprise est prête à payer un prix plus élevé pour l'acquisition de ressources qui augmentent les profits.

Introduisons un nouvel objectif pour la variable souhaitée x en tant que certain prix « fictif » qui détermine la valeur d'une ressource donnée par rapport au profit de la vente de produits manufacturés.

C – vecteur de ressources disponibles ;
b_ub est le vecteur de profit de la production d'une unité de chaque type de produit ;
A_ub_T – matrice transposée A_ub.

Fonction d'objectif
minF(x)=c×x

Restrictions
A_ub_T ×x≥ b_ub

Valeurs numériques et relations pour les variables :
c = ; A_ub_T transpose(A_ub); b_ub = .

Tâche:
Trouvez x indiquant la valeur pour le producteur de chaque type de ressource.

Fonctionnalités de la solution avec la bibliothèque scipy. optimiser
Pour remplacer les restrictions d'en haut par des restrictions d'en bas, il faut multiplier les deux parties de la contrainte par moins un – A_ub_T ×x≥ b_ub... Pour ce faire, écrivez les données d'origine sous la forme : b_ub = [-25, -35,-25,-40,-30] ; A_ub_T =- scipy.transpose(A_ub).

Listing de la solution au problème de double optimisation

#!/usr/bin/python # -*- codage : utf-8 -*- importer scipy depuis scipy.optimize import linprog A_ub = [, , , ] c= b_ub = [-25, -35,-25,- 40,-30] A_ub_T =-scipy.transpose(A_ub) d=linprog(c, A_ub_T, b_ub) pour key,val dans d.items() : print(key,val)


Résultats de la résolution du problème
lenteur 7
message L'optimisation s'est terminée avec succès.
amusant 5863.63636364
x [ 2,27272727 1,81818182 6,36363636 0. ]
mou [5.45454545 2.27272727 0. 0. 0. ]
statut 0
succès Vrai

conclusions

Le troisième type de ressource a la plus grande valeur pour le fabricant, donc ce type les ressources doivent être achetées en premier, puis les premier et deuxième types. Le quatrième type de ressource a une valeur nulle pour le fabricant et est acheté en dernier.

Résultats de la comparaison des problèmes directs et duaux

  1. Le double problème étend les capacités de planification de produits, mais en utilisant scipy. L'optimisation est résolue en deux fois plus d'itérations directes.
  2. La variable slack affiche des informations sur l'activité des contraintes sous forme d'inégalités, qui peuvent être utilisées, par exemple, pour analyser les bilans de matières premières.
  3. Le problème direct est un problème de maximisation, et le problème dual est un problème de minimisation, et vice versa.
  4. Les coefficients de la fonction objectif dans le problème direct sont des contraintes dans le problème dual.
  5. Les contraintes du problème direct deviennent des coefficients de la fonction objectif du problème dual.
  6. Les signes d’inégalités en matière de restrictions s’inversent.
  7. La matrice du système d’égalités est transposée.
Liens