Variables de tâche

Construisons un modèle du problème.

Solution

Avant de construire modèle mathématique tâches, ᴛ.ᴇ. écris-le en utilisant symboles mathématiques, il est extrêmement important de bien comprendre la situation économique décrite dans la condition. Pour cela, il est extrêmement important du point de vue de l'économie, et non des mathématiques, répondre aux questions suivantes:

1) Quelles sont les quantités requises du problème ?

2) Quel est le but de la décision ? Quel paramètre du problème sert de critère pour l'efficacité (optimalité) de la solution, par exemple le profit, le coût, le temps, etc. Dans quel sens la valeur de ce paramètre doit-elle évoluer (vers max ou vers min) pour obtenir les meilleurs résultats ?

3) Quelles conditions doivent être remplies concernant les quantités et les ressources requises pour la tâche ?

Ces conditions établissent comment les différents paramètres du problème doivent être liés les uns aux autres, par exemple la quantité de ressource dépensée en production et son stock dans l'entrepôt ; la quantité de produits fabriqués et la capacité de l'entrepôt où ils seront stockés ; quantité de produits fabriqués et demande du marché pour ces produits, etc.

Ce n’est qu’après avoir trouvé la réponse économique à toutes ces questions que l’on pourra commencer à écrire ces réponses sous forme mathématique, ᴛ.ᴇ. pour enregistrer le modèle mathématique.

Le problème nécessite de déterminer la quantité de peinture de chaque type à produire. Pour cette raison, les quantités requises, et donc les variables du problème, sont les volumes de production journaliers de chaque type de peinture :

x1 – volume de production quotidien de peinture du 1er type, [t peinture/jour] ;

x2 – volume de production quotidien de peinture du 2ème type, [t peinture/jour].

L'énoncé de tâche énonce l'objectif - atteindre revenu maximum provenant des ventes de produits. Ceux. Le critère de performance est le paramètre du revenu journalier, qui doit tendre vers le maximum. Pour calculer le montant du revenu quotidien provenant de la vente de peintures des deux types, il est extrêmement important de connaître le volume de production de peinture, ᴛ.ᴇ. x1 et x2 tonnes de peinture par jour, ainsi que Prix ​​de gros pour les peintures des 1er et 2e types - selon les conditions, respectivement 3 et 2 000 roubles. pour 1 tonne de peinture. Τᴀᴋᴎᴍ ᴏϬᴩᴀᴈᴏᴍ, les revenus provenant de la vente du volume de production quotidien de peinture du 1er type sont égaux à 3 x 1 mille roubles. par jour, et de la vente de peinture du 2ème type - 2x 2 000 roubles. par jour. Pour cette raison, nous écrivons la fonction objectif comme la somme des revenus de la vente de peintures du 1er et du 2ème types (en supposant l'indépendance des volumes de vente de chaque peinture)

Fonction objectif - concept et types. Classement et caractéristiques de la catégorie « Fonction cible » 2017, 2018.

- Concepts de base. Critère de performance. Fonction objectif

CHAPITRE 16. EFFICACITÉ DES QUESTIONS DE CONTRÔLE DE GESTION 1. Qu'est-ce qui a causé la nécessité d'une activité économique étrangère de l'entreprise ? 2. Qu'est-ce qui favorise l'activité économique étrangère d'une entreprise ? 3. Qu'est-ce qui constitue un obstacle à... .

- Dans notre exemple, la fonction objectif a la forme

F(X) = 75X1 + 800/X1 + 78X2 + 1600/X2. La fonction est convexe si F"(x)>0 pour tout x. Vérifions : ; ; ; . Cela signifie que la fonction est convexe car "x>0. Par conséquent, choisir le nombre optimal de trains sur deux tronçons s'avère être un problème de programmation convexe qui peut être résolu... .

- Fonction cible de la consommation et modélisation du comportement du consommateur

Dans les conditions d'un système de marché pour gérer les activités de production et de vente des entreprises et des firmes, la base de la prise de décisions commerciales est l'information sur le marché, et la validité des décisions est vérifiée par le marché lors de la vente de biens et de services. Avec cette approche...

Une fonction objectif est une fonction avec certaines variables dont dépend directement l'atteinte de l'optimalité. Il peut également agir comme plusieurs variables qui caractérisent un objet particulier. Nous pouvons dire qu’en substance, cela montre comment nous avons progressé vers la réalisation de notre objectif.

Un exemple de telles fonctions est le calcul de la résistance et du poids de la structure, de la capacité d'installation, du volume de production, des coûts de transport, etc.

La fonction objectif permet de répondre à plusieurs questions :

Que tel ou tel événement soit bénéfique ou non ;

Le mouvement va-t-il dans la bonne direction ?

Dans quelle mesure le choix a-t-il été fait, etc.

Si nous n'avons pas la possibilité d'influencer les paramètres de la fonction, alors nous pouvons dire que nous ne pouvons rien faire, sauf peut-être simplement tout analyser. Mais pour pouvoir changer quelque chose, il existe généralement des paramètres de fonction mutables. la tâche principale- il s'agit de changer les valeurs pour celles auxquelles la fonction devient optimale.

Les fonctions objectives ne peuvent pas toujours être présentées sous la forme d'une formule. Cela pourrait être un tableau, par exemple. En outre, la condition peut prendre la forme de plusieurs fonctions objectives. Par exemple, si vous souhaitez garantir une fiabilité maximale, coûts minimaux et une consommation matérielle minimale.

Les problèmes d’optimisation doivent avoir la condition initiale la plus importante : une fonction objective. Si nous le faisons, nous pouvons alors supposer que l’optimisation n’existe pas. En d’autres termes, s’il n’y a pas d’objectif, alors il n’y a aucun moyen de l’atteindre, et encore moins de conditions favorables.

Les tâches d'optimisation peuvent être conditionnelles ou inconditionnelles. Le premier type implique des restrictions, c'est-à-dire certaines conditions lors de la définition du problème. Le deuxième type consiste à trouver le maximum ou avec des paramètres existants. Ces problèmes impliquent souvent la recherche d’un minimum.

Dans la compréhension classique de l'optimisation, de telles valeurs de paramètres sont sélectionnées pour lesquelles la fonction objectif satisfait les résultats souhaités. Cela peut également être décrit comme le processus de sélection du plus Meilleure option des possibles. Par exemple, choisir la meilleure allocation de ressources, la meilleure option de conception, etc.

Il existe une optimisation incomplète. Cela peut se former pour plusieurs raisons. Par exemple:

Le nombre de systèmes qui atteignent le point maximum est limité (un monopole ou un oligopole a déjà été établi) ;

Il n'y a pas de monopole, mais il n'y a pas de ressources (manque de qualifications dans tout concours) ;

L'absence de la plus grande partie ou plutôt « l'ignorance » de celui-ci (un homme rêve d'un certain belle femme, mais on ne sait pas si une telle chose existe dans la nature), etc.

Dans les conditions des relations marchandes pour la gestion des activités de vente et de production des entreprises et des entreprises, la base de la prise de décision est l'information sur le marché, et la validité de cette décision est vérifiée lors de l'entrée sur le marché avec le produit ou le service correspondant. Dans ce cas, le point de départ est d’étudier la demande des consommateurs. Pour trouver des solutions, une fonction d’objectif de consommation est établie. Il montre la quantité de biens consommés et le degré de satisfaction des besoins des consommateurs, ainsi que la relation entre eux.

La fonction objectif est une représentation mathématique de la dépendance du critère d'optimalité sur les variables souhaitées.

2. Dégradé de la fonction.

Un vecteur dont les composantes sont les valeurs des dérivées partielles, c'est-à-dire un vecteur

est appelé le gradient de la fonction calculé en ce point.

3. Problème général de programmation linéaire.

Formulation mathématique standard du problème général programmation linéaire ressemble à ceci : il faut trouver la valeur extrême de l'indicateur d'efficacité ( fonction objectif)

(fonction linéaire des éléments de solution) sous des conditions restrictives linéaires imposées aux éléments de solution :

où sont donnés des nombres.

4. Problème LP standard.

Sous forme standard, un problème de programmation linéaire est un problème de maximum (minimum) pour une fonction objectif linéaire. Son système de restrictions est constitué uniquement d'inégalités linéaires du type «<= » или « >= " Toutes les variables du problème sont non négatives.

Tout problème de programmation linéaire peut être formulé en forme standard. La conversion d'un problème minimum en problème maximum, ainsi que la garantie que les variables ne sont pas négatives, se font de la même manière que précédemment. Toute égalité dans un système de restrictions équivaut à un système d'inégalités mutuellement opposées :

Il existe d'autres manières de transformer un système d'égalités en un système d'inégalités, c'est-à-dire Chaque problème de programmation linéaire peut être formulé sous une forme standard.

Option de réponse 2 :

Problème LP standard. ou, en notation matricielle, où est la matrice des coefficients. Un vecteur est appelé vecteur de coefficients de forme linéaire, vecteur de contraintes.

5. Problème canonique de LP.

DANS Forme canonique le problème est un problème pour le maximum (minimum) de certains fonction linéaire F , son système de restrictions n'est constitué que d'égalités (équations). Dans le même temps, les variables de tâche X 1 , X 2 , ..., X n sont non négatifs :

À Forme canonique Vous pouvez transformer n’importe quel problème de programmation linéaire.

Entrée courte problème canonique PL :

X = (x1, x2, ..., xn), C = (c1, c2, ..., cn).

Option de réponse 2 :

Problème canonique LP. ou, en notation matricielle,

6. Problèmes doubles symétriques et asymétriques.

Problème de programmation double linéaire. Considérez le problème LP (1) ou, en notation matricielle, (2) Le problème dual de (1) (problème dual) est appelé problème LP en variables de la forme (3) ou, en notation matricielle, (4) où . Les règles de construction du problème (3) selon la forme d'écriture du problème (1) sont les suivantes : dans le problème (3)

Il y a autant de variables qu'il y a de lignes dans la matrice du problème (1). La matrice de contraintes dans (3) est une matrice transportée. Le vecteur du membre droit des contraintes dans (3) sert de vecteur des coefficients de la forme linéaire maximisée dans (1), et les signes des inégalités se transforment en égalité. Au contraire, la fonction objectif dans (3) est forme linéaire, dont les coefficients sont spécifiés par le vecteur du membre droit des contraintes du problème (1), tandis que la maximisation se transforme en minimisation. La condition de non-négativité est imposée aux variables duales. Problème (1), contrairement à double problème(3) est appelé droit. Théorème de la dualité. Si les problèmes doubles (2), (4) sont admissibles, alors ils ont tous deux une solution et la même valeur.

Problèmes doubles symétriques

Une variété de double problèmes linéaires, la programmation sont des problèmes symétriques duaux, dans lesquels le système de contraintes du problème original et du problème duel est spécifié par des inégalités, et la condition de non-négativité est imposée aux variables duales.

Programmation linéaire.

Bref informations théoriques

Fixer des objectifs

La résolution d'un problème de programmation linéaire directe répond à la question suivante :

à quelles intensités n processus lucratifs (fournissant diverses prestations, processus de production), dans lequel ils sont utilisés m types de ressources (facteurs de production) avec une intensité maximale connue d'utilisation de ces ressources, le chiffre d'affaires (bénéfice) sera maximum dans le cas où l'intensité de consommation de chaque ressource et l'intensité du profit (revenu) dans chacun des processus dépendent linéairement de l’intensité de ce processus.

La solution à son double problème répond à la question suivante :

à quoi prix les plus bas par unité de ressource, il ne sera pas rentable pour un agent économique d'étendre davantage le processus de profit par l'acquisition de nouveaux volumes de ressources rares dans les conditions actuelles de l'activité économique.

Un problème de programmation linéaire directe peut être lié à la situation suivante. Disponible n moyens de réaliser un profit (en fournissant n types de services) avec des volumes x je (nombre de pièces je services rendus). Dans ce cas, ils sont utilisés m types de ressources, stock j -ième dont est égal à bj . Dans le même temps, la consommation de chaque ressource j et le montant du profit dans chacun des processus je dépendent linéairement du nombre de services fournis je -ième type avec coefficients un ji Et c je , respectivement. Matrice UN=(un ji )m'n la signification est similaire à celle de la première partie et est également appelée matrice des coefficients technologiques ou structurels. Ensuite, le plan optimal selon le critère du profit maximum peut être obtenu en résolvant le problème de programmation linéaire directe suivant :

Ce problème peut être associé à une matrice étendue de la forme suivante :

(4.1)

Le problème dual du problème (4) a la forme suivante ( zj – prix limites requis) :

Avec cette formulation du double problème, (5.1) et (5.3) découlent de la condition de minimisation des prix, et de la condition de non-rentabilité de la poursuite de l'activité, surgit directement la condition d'excédent ou d'égalité des coûts sur le chiffre d'affaires.

Concepts de base du modèle

Décision (plan, programme) - ensemble, vecteur de valeurs spécifiques de tous paramètres variables contrôle du modèle - ces quantités qui peuvent être modifiées à la volonté du gestionnaire de l'objet de modélisation. Les solutions peuvent être acceptables (mises en pratique), inacceptables (non réalisables en raison des limitations existant dans le modèle) et optimales (la meilleure des solutions acceptables).

Fonction objectif L(x) – une expression mathématique reliant les facteurs (paramètres) du modèle. La signification économique de la fonction objectif reflète critère d'optimalité– un indicateur qui a un contenu économique et sert de formalisation d'un objectif de gestion spécifique, par exemple : maximiser le profit (ligne 1 en (4)), maximiser la qualité du produit ou minimiser les coûts (5.1).

Système de restrictions modèles - limites qui limitent plage acceptable(acceptable, réalisable) solutions, enregistrant les principales propriétés internes et externes de l'objet associées à l'objectif d'optimisation. Équations de communication(taper fj(x) ) – formalisation mathématique du système de restrictions (lignes 2 et 3 de (4), (5.2, 5.3)). Le système de restrictions reflète la signification économique des équations de communication.

Un système composé d'une fonction objectif et d'équations de communication - problème de modélisation économique et mathématique (EMM). Dans le cas où la fonction objectif et les équations de couplage sont linéaires et les variables de contrôle changent continuellement, le problème EMM est appelé problème de programmation linéaire (LP). La propriété principale de l’ensemble des plans admissibles (SAP) du problème LP est qu’il s’agit d’un polyèdre convexe. Un ensemble est dit convexe s’il contient tous les segments reliant deux points quelconques de cet ensemble. Si le problème LP a une solution, alors elle est située au sommet du MDP. Les plans situés aux sommets du MDP sont dits basiques. Les problèmes de programmation linéaire sont divisés en problèmes avec contraintes sous forme d'inégalités (problème LP général) et sous forme d'égalités (problème LP canonique). Lors de la formalisation mathématique de problèmes économiques à l'aide d'un modèle linéaire, des problèmes généraux LP sont obtenus - par exemple (4), (5). Tout problème général peut être associé à un problème canonique en introduisant des variables supplémentaires. Ainsi, au problème (4) en introduisant dans chaque inégalité du type « consommation de ressources £ réserve de ressources » (ligne 2 dans (4)) une variable supplémentaire xn+j (solde non dépensé j ème ressource), la canonique suivante est comparée :

Dans le même temps, la dimension du problème (6) - le nombre de variables de conception - par rapport à (4) a augmenté avec n avant n+m .

Lors de la résolution du problème (4), les coefficients d'efficacité des ressources sont importants, parmi lesquels les coefficients différentiels et incrémentaux seront utilisés ici. Coefficient différentiel d’efficacité des ressources k ji montre le coût du rendu lors de l'utilisation d'une unité j la ressource je -s services. Ces types de services pour lesquels tout k ji s'avèrent être les plus petits pour tous les types de services et les moins rentables. Ils ne devraient pas être présents dans le plan optimal. Cela permet, en réduisant à zéro le volume de fourniture de tels services, de réduire l'ampleur du problème et, ainsi, de simplifier sa solution. Ils sont calculés comme suit - k ji =c je /a ji .

coefficient d'efficacité incrémental des ressources K j est le coefficient de proportionnalité entre l'incrément de la valeur de la fonction objectif du plan optimal et la variation de stock qui a provoqué cet incrément j -ème ressource. On peut considérer que À j montrer de combien la valeur de la fonction objectif du problème d'origine dans le plan optimal augmentera avec une augmentation de la marge j -ème ressource par unité. D'un point de vue mathématique, c'est la dérivée complète de la valeur optimale de la fonction objectif en termes de valeur de marge j -ième ressource : À j =dL opt/dbj .

27 août 2017 à 14h20

Résoudre des problèmes de programmation linéaire directe et double à l'aide de Python

Introduction

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 sans aucun doute 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

Compte tenu du haut niveau de formation mathématique de 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 être écrits avec un signe négatif c = [-25, -35,-25,-40,-30] et ignorer le signe moins devant le 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 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 cela, écrivez les données initiales 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, ce type de ressource doit donc être acheté 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