Programmation linéaire des solutions optimales admissibles. Solutions admissibles et optimales. Un exemple de compilation d'un modèle mathématique

Présentation générale du problème programmation linéaire(ZLP). Exemples de PLP

La programmation linéaire est une branche des mathématiques qui étudie les méthodes de résolution de problèmes extrêmes caractérisés par une relation linéaire entre les variables et un critère d'optimalité linéaire. Quelques mots sur le terme même de programmation linéaire. Cela nécessite une compréhension correcte. Dans ce cas, programmer n'est bien sûr pas compiler des programmes informatiques. Ici, la programmation doit être interprétée comme la planification, la formation de plans, l'élaboration d'un programme d'action. Les problèmes mathématiques de la programmation linéaire comprennent l'étude de situations de production et économiques spécifiques, qui, sous une forme ou une autre, sont interprétées comme des problèmes d'utilisation optimale de ressources limitées. L'éventail des problèmes résolus à l'aide des méthodes de programmation linéaire est assez large. C'est par exemple :

• - le problème de l'utilisation optimale des ressources dans la planification de la production ;
• - le problème des mélanges (planification de la composition des produits) ;
• - le problème de trouver la combinaison optimale diverses sortes produits destinés à être stockés dans des entrepôts (gestion des stocks ou "problème de sac à dos");
• - tâches de transport (analyse de la localisation de l'entreprise, circulation des marchandises). La programmation linéaire est la section la plus développée et la plus utilisée de la programmation mathématique (en plus, cela inclut : la programmation entière, dynamique, non linéaire, paramétrique). Cela s'explique comme suit :
• - les modèles mathématiques d'un grand nombre de problèmes économiques sont linéaires par rapport aux variables requises ;
• - type donné Les tâches sont actuellement les plus étudiées. Pour lui, des méthodes spéciales ont été développées à l'aide desquelles ces problèmes sont résolus, ainsi que les programmes informatiques correspondants;
• - de nombreux problèmes de programmation linéaire, en cours de résolution, ont trouvé une large application ;
• - certains problèmes qui ne sont pas linéaires dans la formulation d'origine, après un certain nombre de restrictions et d'hypothèses supplémentaires, peuvent devenir linéaires ou être réduits à une forme telle qu'ils peuvent être résolus par des méthodes de programmation linéaire. Le modèle économique et mathématique de tout problème de programmation linéaire comprend : une fonction objectif dont il faut trouver la valeur optimale (maximale ou minimale) ; des restrictions sous la forme d'un système d'équations linéaires ou d'inégalités ; exigence de non négativité des variables. En général, le modèle s'écrit comme suit :
• - fonction objectif :

C1x1 + c2x2 + ... + cnxn > max(min);- restrictions :

a11x1 + a12x2 + ... + a1nxn(?=?)b1,

a21x1 + a22x2 + ... + a2nxn(?=?)b2

am1x1 + am2x2 + ... + amnxn (? = ?) bm;

Exigence de non-négativité :

Dans ce cas, aij, bi, cj () reçoivent des constantes. Le problème est de trouver la valeur optimale de la fonction (2.1) sous les contraintes (2.2) et (2.3). Le système de contraintes (2.2) est appelé les contraintes fonctionnelles du problème, et les contraintes (2.3) sont dites directes. Un vecteur qui satisfait les contraintes (2.2) et (2.3) est appelé solution réalisable (plan) d'un problème de programmation linéaire. Le plan pour lequel la fonction (2.1) atteint sa valeur maximale (minimale) est dit optimal.

Ensuite, nous donnons des exemples de problèmes typiques résolus à l'aide de méthodes de programmation linéaire. Ces tâches ont un réel contenu économique. Maintenant, nous ne les formulerons qu'en termes de LLP, et nous examinerons ci-dessous des méthodes pour résoudre ces problèmes.

1. Le problème de l'utilisation optimale des ressources dans la planification de la production. Sens général Les problèmes de cette classe se réduisent aux suivants. Une entreprise fabrique n produits différents. Leur production nécessite différents types de ressources (matières premières, matériaux, temps de travail, etc.). Les ressources sont limitées, leurs réserves dans la période de planification sont, respectivement, b1, b2,..., bm unités conventionnelles. On connaît également les coefficients technologiques aij, qui indiquent combien d'unités de la i-ème ressource sont nécessaires pour produire une unité d'un produit du j-ème type (). Le bénéfice reçu par l'entreprise de la vente du produit du jème type est égal à cj. Dans la période de planification, les valeurs de aij, bi et cj restent constantes. Il est nécessaire d'élaborer un tel plan pour la production de produits, dans la mise en œuvre duquel le profit de l'entreprise serait le plus grand. Ci-dessous, nous donnons un exemple simple d'un problème de cette classe.

L'entreprise se spécialise dans la production de bâtons de hockey et de jeux d'échecs. Chaque bâton rapporte à l'entreprise un bénéfice de 2 $ et chaque jeu d'échecs - 4 $. Il faut quatre heures de travail sur le site A et deux heures de travail sur le site B pour fabriquer un club -heures par jour, section B - 72 heures-n et section C - 10 heures-n. Combien de clubs et de jeux d'échecs une entreprise doit-elle produire quotidiennement pour maximiser ses profits ?

Les conditions des problèmes de cette classe sont souvent présentées sous forme de tableau (voir tableau 2.1).

Sous cette condition, nous formulons un problème de programmation linéaire. Notons : x1 - le nombre de bâtons de hockey produits quotidiennement, x2 - le nombre de jeux d'échecs produits quotidiennement. Formule PLP :

4x1 + 6x2 ? 120

Nous soulignons que chaque inégalité dans le système de contraintes fonctionnelles correspond dans ce cas à l'un ou l'autre site de production, à savoir : le premier - à la section A, le deuxième - à la section B, le troisième - à la section C.

Le système de variables dans le problème d'optimisation de la structure des surfaces ensemencées, en tenant compte des rotations culturales

Un problème de programmation linéaire (LPP) est le problème de trouver la plus grande (ou la plus petite) valeur d'une fonction linéaire sur un ensemble polyédrique convexe.

La méthode du simplexe est une méthode de résolution d'un problème de programmation linéaire. L'essence de la méthode est de trouver le plan réalisable initial, 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 le problème soit insoluble.

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

Méthode de base artificielle

Comme mentionné ci-dessus, pour un problème écrit sous forme canonique, si parmi les vecteurs colonnes de la matrice UNE il y a m unitaire et linéairement indépendant, vous pouvez spécifier directement le plan de référence. Or, pour de nombreux problèmes de programmation linéaire écrits sous forme canonique et ayant des plans de support, parmi les vecteurs colonnes de la matrice UNE pas toujours là m singulier et linéairement indépendant. Considérons la tâche suivante :

Soit demandé de trouver le maximum de la fonction

sous conditions

où sont les premiers n les éléments sont nuls. variables qualifié d'artificiel. Vecteurs colonnes

(28)

forment la soi-disant base artificielle m espace vectoriel de dimension.

Puisque le problème étendu a un plan de support, 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 , ensuite est le plan optimal pour le problème (21)−(23).

Ainsi, si dans le plan optimal trouvé du problème étendu, les valeurs des variables artificielles sont égales à zéro, alors le plan optimal du problème original 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 avec le plan de référence (27) :

Nous remarquons que F(X) et se composent de deux parties indépendantes, dont l'une dépend de M, tandis que l'autre ne l'est pas.

Après calcul F(X) et leurs valeurs, ainsi que les données initiales du problème étendu, sont entrées dans le tableau simplex, comme indiqué ci-dessus. La seule différence est que ce tableau contient une ligne de plus qu'un tableau simplex normal. Dans le même temps, en ( m+1)-ième ligne mettre les coefficients qui ne contiennent pas M, et en ( m+2)ème ligne − coefficients à M.

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

Le processus itératif est m+2 rangée tant que les éléments m+2 lignes correspondant aux variables ne deviendra pas négatif. Dans ce cas, si des variables artificielles sont exclues de la base, alors le plan trouvé du problème étendu correspond à un plan de base du problème original.

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 l'élément m+2 lignes, colonnes X 0 est égal à zéro, alors le plan support du problème d'origine est dégénéré et la base contient au moins un des vecteurs de base artificiels.

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

Si lors des itérations m+2 ligne ne contient plus d'éléments négatifs, alors le processus itératif continue avec m+1 ligne, jusqu'à ce que le plan optimal pour le problème étendu soit trouvé ou que le problème soit insoluble.

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

• Composer le problème étendu (24)−(26).
• Trouvez la ligne de base pour la tâche étendue.
• En utilisant la méthode du simplexe, les vecteurs artificiels sont exclus de la base. En conséquence, le plan de base du problème initial est trouvé ou son insolvabilité est corrigée.
• En utilisant le plan de support trouvé LLP (21)−(23), soit trouver le plan optimal du problème original, soit établir son insolvabilité.

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

Les modèles mathématiques sont à la base de la résolution des problèmes économiques.

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

• sélection de variable de tâche
• l'élaboration d'un système de restrictions
• choix de la fonction objectif

Variables de tâche sont appelées grandeurs X1, X2, Xn, qui caractérisent pleinement le processus économique. Ils s'écrivent généralement sous la forme d'un vecteur : X=(X 1 , X 2 ,...,X n).

Le système des restrictions les tâches sont un ensemble d'équations et d'inéquations qui décrivent les ressources limitées dans le problème considéré.

fonction cible tâche est appelée une fonction de variables de tâche qui caractérise la qualité de la tâche et dont il faut trouver l'extremum.

En général, un problème de programmation linéaire peut être écrit comme suit :

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

Solution acceptable(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 les conditions de non-négativité.

L'ensemble des solutions réalisables (plans) des formes du problème éventail de solutions réalisables(ODR).

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

Un exemple de compilation d'un modèle mathématique

La tâche d'utiliser des ressources (matières premières)

État: Pour la fabrication de n types de produits, m types de ressources sont utilisées. Faire un modèle mathématique.

Connu:

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

Il est nécessaire d'élaborer un plan de production de produits qui offre un profit maximal avec des restrictions données sur les ressources (matières premières).

Solution:

On introduit un vecteur de variables X=(X 1 , X 2 ,...,X n), où xj (j = 1,2,...,n) est le volume de production du j-è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 , par conséquent, la restriction à l'utilisation des ressources pour la production de tous les types de produits a la forme :
Le bénéfice de la vente du j-ième type de produit est égal à c j x j , donc la fonction objectif est égale à :

Réponse- 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 équations et les inégalités sont des contraintes, et les variables peuvent être non négatives ou changer 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 est une matrice de colonnes de variables de tâche
• Ao est la matrice-colonne des parties droites du système de contraintes

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

Réduction d'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 la compilation de modèles de problèmes économiques, les contraintes sont principalement formées sous la forme d'un système d'inégalités, il est donc nécessaire de pouvoir passer d'un système d'inégalités à un système d'équations.

Prenez une inégalité linéaire a 1 x 1 +a 2 x 2 +...+anxn ≤b et ajoutez une valeur x n+1 à son côté gauche, de sorte que l'inégalité devienne l'égalité a 1 x 1 +a 2 x 2 + ...+anxn +x n+1 =b. De plus, cette valeur x n+1 est non négative.

Considérons tout avec un exemple.

Réduisez le problème de programmation linéaire à la forme canonique :

Solution:
Passons au problème de la recherche du maximum de la fonction objectif.
Pour ce faire, on change les signes des coefficients de la fonction objectif.
Pour convertir 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 (cette opération est repérée par la lettre D sur le modèle mathématique).
La variable x 4 est inscrite du côté gauche de la deuxième inégalité avec un signe "+", puisque l'inégalité a la forme "≤".
La variable x 5 est inscrite du 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.

Test dans la discipline "Operations Research"

(les bonnes réponses sont les premières)

1. Le terme « recherche opérationnelle » a été inventé…

pendant la Seconde Guerre mondiale

dans les années 50 du XXe siècle

dans les années 60 du XXe siècle

dans les années 70 du XXe siècle

dans les années 90 du XXe siècle

au début du 21e siècle

2. La recherche opérationnelle est comprise comme (sélectionnez l'option la plus appropriée) ...

un ensemble de méthodes scientifiques pour résoudre les problèmes de gestion efficace des systèmes organisationnels

un ensemble de mesures prises pour mettre en œuvre certaines opérations

un ensemble de méthodes pour mettre en œuvre le plan

méthodes scientifiques d'allocation des ressources dans l'organisation de la production

3. Énumérez les étapes par lesquelles passe généralement toute recherche opérationnelle :

formulation du problème

construction d'un modèle signifiant (verbal) de l'objet (processus) considéré

construire un modèle mathématique

solution de problèmes formulés sur la base du modèle mathématique construit

vérification des résultats obtenus quant à l'adéquation de la nature du système étudié

mise en œuvre de la solution obtenue dans la pratique

4. En recherche opérationnelle, une opération est comprise comme ...

tout événement (système d'actions), uni par un plan unique et visant à atteindre un objectif

tout événement non géré

un ensemble de mesures techniques qui assurent la production de produits de consommation

5. La solution est dite optimale, ...

s'il est plus préférable que d'autres pour une raison ou une autre

si c'est rationnel

si cela est convenu avec les autorités

s'il est approuvé par l'assemblée générale

6. Programmation mathématique...

traite de l'étude des problèmes extrêmes et du développement de méthodes pour leur solution

est le processus de création de programmes informatiques sous la direction de mathématiciens

s'occupe de Problèmes mathématiques sur l'ordinateur

7. La tâche de la programmation linéaire est ...

trouver la plus grande (la plus petite) valeur d'une fonction linéaire en présence de contraintes linéaires

création programme linéaire dans le langage de programmation choisi, conçu pour résoudre la tâche

la description algorithme linéaire résoudre un problème donné

8. Dans le problème de la programmation quadratique...

la fonction objectif est quadratique

la zone de solution réalisable est un carré

les contraintes contiennent des fonctions quadratiques

9. Dans les problèmes de programmation en nombres entiers...

les inconnues ne peuvent prendre que des valeurs entières

la fonction objectif doit nécessairement prendre une valeur entière, et les inconnues peuvent être quelconques

la fonction objectif est une constante numérique

10. Dans les problèmes de programmation paramétrique...

fonction objectif et/ou contrainte contient paramètre(s)

le domaine des solutions réalisables est un parallélogramme ou un parallélépipède

le nombre de variables ne peut être que pair

11. Dans les problèmes de programmation dynamique…

le processus de recherche d'une solution est en plusieurs étapes

il faut rationaliser la production de dynamite

besoin d'optimiser l'utilisation des haut-parleurs

12. Le problème de programmation linéaire suivant est défini :

F(X 1, X 2) = 5X 1 + 6X 2→ maximum

0.2X 1 + 0.3X 2 ≤ 1.8,

0.2X 1 + 0.1X 2 ≤ 1.2,

0.3X 1 + 0.3X 2 ≤ 2.4,

X 1 ≥ 0, X 2 ≥ 0.

Sélectionnez une tâche équivalente à cette tâche.

F(X 1, X 2)= 5X 1 + 6X 2 → maximum,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 6X 1 + 5X 2 → mn,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 50X 1 + 60X 2 → maximum,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

X 1 + X 2 ≤ 8,

X 1 ≥ 0,

X 2 ≥ 0.

F(X 1, X 2)= 5X 12 + 6X 22 → maximum,

2X 1 + 3X 2 ≤ 18,

2X 1 + X 2 ≤ 12,

3X 1 + X 2 ≤ 2.4,

X 1 ≥ 0,

X 2 ≥ 0.

13. La fonction objectif d'un problème de programmation linéaire peut être une fonction :

F=12x1+20x2–3 0x3→min

F= →min

F=→maximum

F=→max.

14. Le système de contraintes pour un problème de programmation linéaire peut être un système :

15. La méthode du simplexe est :

méthode analytique pour résoudre le problème principal de la programmation linéaire

une méthode pour trouver la zone de solutions réalisables pour un problème de programmation linéaire ;

méthode graphique pour résoudre le problème principal de la programmation linéaire ;

une méthode pour réduire un problème général de programmation linéaire à une forme canonique.

16. La tâche de la programmation linéaire est :

trouver la plus grande ou la plus petite valeur d'une fonction linéaire en présence de contraintes linéaires

développement d'un algorithme linéaire et son implémentation sur un ordinateur

compiler et résoudre un système d'équations linéaires

recherche d'une trajectoire linéaire du développement d'un processus décrit par un système de contraintes donné.

17. Domaine des solutions admissibles du problème de programmation linéaire ne peux pas ressemble à ca:

18. La fonction objectif d'un problème de programmation linéaire peut être une fonction :

F=12x1+20x2–3 0x3→min

F= →min

F=→maximum

F=→max.

19. Un système de contraintes pour un problème de programmation linéaire peut être un système :

20. Le domaine des solutions admissibles au problème de la programmation linéaire a la forme :

F(X 1, X 2)= 3X 1 + 5X 2 égale...

21. Le domaine des solutions admissibles au problème de la programmation linéaire a la forme :

Puis valeur maximum les fonctions F(X 1, X 2)= 5X 1 + 3X 2 égale...

22. Le domaine des solutions admissibles au problème de la programmation linéaire a la forme :

Alors la valeur maximale de la fonction F(X 1, X 2)= 2X 1 - 2X 2 égale...

23. Le domaine des solutions admissibles au problème de la programmation linéaire a la forme :

F(X 1, X 2)= 2X 1 - 2X 2 égale...

24. Le domaine des solutions admissibles au problème de la programmation non linéaire a la forme :

Alors la valeur maximale de la fonction F(X 1, X 2)= X 2 – X 12 égale...

25. La valeur maximale de la fonction objectif F(X 1, X 2)= 5X 1 + 2X 2 sous restrictions
X 1 + X 2 ≤ 6,

X 1 ≤ 4,

X 1 ≥ 0, X 2 ≥ 0, égal à ...

26. Une petite entreprise fabrique deux types de produits. Pour la fabrication d'un produit de type A, 2 kg de matières premières sont consommés, pour la fabrication d'un produit de type B - 1 kg. Il y a 60 kg de matières premières au total. Il est nécessaire d'établir un plan de production qui assure le plus grand revenu, si le prix de vente d'un produit de type A est de 3 UM, de type B est de 1 u.m. Autrement dit, les produits de type A ne doivent pas être fabriqués plus de 25 et le type B - pas plus de 30.

Cette tâche est…

problème de programmation linéaire

problème résolu par programmation dynamique

tâche de planification du réseau.

27. Une petite entreprise produit deux types de produits. Pour la fabrication d'un produit de type A, 2 kg de matières premières sont consommés, pour la fabrication d'un produit de type B - 1 kg. Il y a 60 kg de matières premières au total. Il est nécessaire d'établir un plan de production qui assure le plus grand revenu, si le prix de vente d'un produit de type A est de 3 UM, de type B est de 1 u.m. Autrement dit, les produits de type A ne doivent pas être fabriqués plus de 25 et le type B - pas plus de 30.

La fonction objectif de ce problème est la fonction ...

F(x1,x2)=3x1+x2→maximum

F(x1,x2)=25x1+30x2→maximum

F(x1,x2)=2x1+x2→maximum

F(x1,x2)=60-2x1-x2→min

28. Une petite entreprise produit deux types de produits. Pour la fabrication d'un produit de type A, 2 kg de matières premières sont consommés, pour la fabrication d'un produit de type B - 1 kg. Il y a 60 kg de matières premières au total. Il est nécessaire d'établir un plan de production qui assure le plus grand revenu, si le prix de vente d'un produit de type A est de 3 UM, de type B est de 1 u.m. e., et les produits de type A ne doivent pas être fabriqués plus de 25, et le type B - pas plus de 30

Un plan valide pour cette tâche est le plan :

X=(20, 20)

X=(25, 15)

X=(20, 25)

X=(30, 10)

29. En deux points A1 et A2, il y a respectivement 60 et 160 unités de marchandises. Toutes les marchandises doivent être transportées aux points B1, B2, B3 pour un montant de 80, 70 et 70 unités, respectivement. La matrice tarifaire est la suivante : . Prévoyez les transports pour que leur coût soit minimal.

Cette tâche est…

tâche de transport

problème de programmation non linéaire

problème de voyageur de commerce

tâche d'affectation

30. En deux points A1 et A2, il y a respectivement 60 et 160 unités de marchandises. Toutes les marchandises doivent être transportées aux points B1, B2, B3 pour un montant de 80, 70 et 70 unités, respectivement. La matrice tarifaire est la suivante : . Planifier les transports pour que leur coût soit minimal

Le plan de base pour cette tâche est le plan :

;

31. En deux points A1 et A2, il y a respectivement 60 et 160 unités de marchandises. Toutes les marchandises doivent être transportées aux points B1, B2, B3 pour un montant de 80, 70 et 70 unités, respectivement. La matrice tarifaire est la suivante : . Prévoyez les transports pour que leur coût soit minimal.

La fonction objectif de cette tâche est la fonction :

F=4x11+6x12+ 8x13+5x21+8x22+7x23→min

F= →min

F=60x1+160x2+ 80x3+70x4+705 →maximum

F=60x1+160x2– 80x3– 70x4– 705 →min

32. En deux points A1 et A2, il y a respectivement 60 et 160 unités de marchandises. Toutes les marchandises doivent être transportées aux points B1, B2, B3 pour un montant de 80, 70 et 70 unités, respectivement. La matrice tarifaire est la suivante : . Prévoyez les transports pour que leur coût soit minimal.

Le plan optimal pour cette tâche est le plan :

;

.

;

;

33. Tâche de transport

sera fermé si...

34. Tâche de transport

est un…

ouvert

fermé

insoluble

35. Tâche de transport

est un…

fermé

ouvert

insoluble

36. Pour résoudre les problèmes suivants tâche de transport

vous devez entrer...

consommateur fictif

fournisseur fictif ;

tarif effectif

37. Pour résoudre le problème de transport suivant

vous devez entrer...

fournisseur fictif ;

consommateur fictif

tarif effectif

taux d'intérêt effectif.

38. Parmi ces tâches de transport

fermés sont…

39. Le plan de base initial de la tâche de transport peut être établi ...

toutes les méthodes ci-dessus

méthode du coin nord-ouest

méthode du tarif minimum

méthode de la double préférence

Méthode d'approximation de Vogel

40. Si la fonction objectif du problème de programmation linéaire est fixée au maximum, alors ... la fonction objectif du problème dual est fixée au minimum

il n'y a pas de fonction objectif dans le problème dual

problème double n'a pas de solution

le problème dual a une infinité de solutions

41. Étant donné le problème de la programmation linéaire :

F(X 1, X 2)= 2X 1 + 7X 2 → maximum,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

Le dual de ce problème est le suivant…

F*(y1, y2)= 14y1 + 8y2 → min,

3 ans 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

F*(y1, y2)= 2y1 + 7y2 → min,

2y1 + 3y2 ³ 14,

y 1 + y2 ³ 8,

y 1 £ 0, y2 £ 0.

F*(y1, y2)= 2y1 + 7y2 → min,

3 y 1 + y2 ³ 7,

y 1 £ 0, y2 £ 0.

F*(y1, y2)= 14y1 + 8y2 → min,

y 1 + y2 ³ 7,

y 1 ≥ 0, y2 ≥ 0.

42. Si l'un d'une paire de problèmes duaux a un plan optimal, alors ...

et l'autre a un plan optimal

l'autre n'a pas de plan optimal

l'autre n'a pas de solution valide

43. Si l'un d'une paire de problèmes duaux a un plan optimal, alors ...

et l'autre a un plan optimal et les valeurs des fonctions objectifs sous leurs plans optimaux sont égales entre elles

et l'autre a un plan optimal, mais les valeurs des fonctions objectifs pour leurs plans optimaux ne sont pas égales entre elles

un autre problème peut ne pas avoir de plan optimal, mais avoir des solutions réalisables

44. Si la fonction objectif de l'un d'une paire de problèmes duaux n'est pas bornée (pour un problème maximum - d'en haut, pour un problème minimum - d'en bas), alors

une autre tâche n'a pas de plans valides

une autre tâche a des plans valides mais pas de plan optimal

la fonction objectif d'une autre tâche n'est pas non plus limitée

45. Lors de la résolution de certains problèmes de programmation non linéaire, ...

Méthode du multiplicateur de Lagrange

Méthode de Gauss

Méthode d'approximation de Vogel

Méthode Gomory

46. ​​​​Un problème de programmation non linéaire est donné

F(X 1, X 2)= X 12 + X 22 → maximum,

X 1 + X 2 =6,

X 1 ≥ 0, X 2 ≥ 0.

F(X 1, X 2) …

pas réalisable (+ ¥)

47. Un problème de programmation non linéaire est donné

F(X 1, X 2)= X 12 + X 22 → mdans,

X 1 + X 2 =6,

X 1 ≥ 0, X 2 ≥ 0.

F(X 1, X 2) …

48. Un problème de programmation non linéaire est donné

F(X 1, X 2)= X 12 + X 22 → maximum,

X 1 + X 2 =6,

X 1, X 2 - n'importe lequel.

La plus grande valeur de la fonction objectif F(X 1, X 2) …

pas réalisable (+ ¥)

49. Un problème de programmation non linéaire est donné

F(X 1, X 2)= X 12 + X 22 → mdans,

X 1 + X 2 =6,

X 1, X 2 - n'importe lequel.

La plus petite valeur de la fonction objectif F(X 1, X 2) …

pas réalisable (- ¥)

50. Le domaine des solutions admissibles au problème de la programmation non linéaire a la forme :

Alors la valeur maximale de la fonction F(X 1, X 2)= X 12 +X 22 égale...

51. Le domaine des solutions admissibles au problème de la programmation non linéaire a la forme :

Alors la valeur minimale de la fonction F(X 1, X 2)= X 12 +X 22 égale...

52. Pour résoudre le problème de transport peut être utilisé ...

méthode potentielle

Méthode du multiplicateur de Lagrange

Méthode de Gauss

méthode de désorientation

53. Dans le système de contraintes du problème général de la programmation linéaire...

54. Dans le système de contraintes d'un problème de programmation linéaire standard (symétrique) ...

seules les inégalités peuvent être présentes

les équations et les inégalités peuvent être présentes

seules les équations peuvent être présentes

55. Dans le système de contraintes du problème canonique (de base) de la programmation linéaire ...

seules les équations peuvent être présentes (à condition que les variables soient non négatives)

seules les inégalités peuvent être présentes (à condition que les variables soient non négatives)

les équations et les inégalités peuvent être présentes (à condition que les variables ne soient pas négatives)

56. Problème de programmation linéaire

F(X 1, X 2)= 2X 1 + 7X 2 → maximum,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

inscrits dans...

forme standard (symétrique)

forme canonique (de base)

forme verbale

57. Pour enregistrer une tâche

F(X 1, X 2)= 2X 1 + 7X 2 → maximum,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 ≥ 0, X 2 ≥ 0.

sous forme canonique...

58. Pour enregistrer une tâche

F(X 1, X 2)= 2X 1 + 7X 2 → maximum,

2X 1 + 3X 2 ≤ 14,

X 1 + X 2 ≤ 8,

X 1 + 4X 2 ≥ 10,

X 1 ≥ 0, X 2 ≥ 0.

sous forme canonique...

il est nécessaire d'introduire trois variables non négatives supplémentaires

il faut introduire deux variables supplémentaires non négatives

il est nécessaire d'introduire quatre variables non négatives supplémentaires

59. Pour enregistrer une tâche

F(X 1, X 2)= 2X 1 + 7X 2 → maximum,

2X 1 + 3X 2 = 14,

X 1 + X 2 ≤ 8,

X 1 + 4X 2 ≥ 10,

X 1 ≥ 0, X 2 ≥ 0.

sous forme canonique...

il faut introduire deux variables supplémentaires non négatives

il est nécessaire d'introduire trois variables non négatives supplémentaires

il est nécessaire d'introduire quatre variables non négatives supplémentaires

il est nécessaire d'introduire cinq variables non négatives supplémentaires

60. Lors de la résolution de problèmes de programmation en nombres entiers, ...

Méthode Gomory

Méthode du multiplicateur de Lagrange

Méthode de Gauss

Méthode d'approximation de Vogel

61. La base de la résolution de problèmes par la méthode de programmation dynamique est ...

principe du "rasoir d'Occam"

principe « dent pour dent, œil pour œil »

principe de Heisenberg

62 . Une situation dans laquelle des parties participent, dont les intérêts sont totalement ou partiellement opposés, est appelée ...

(conflit, conflit, conflit, conflit)

63. Un conflit réel ou formel dans lequel il y a au moins deux participants (joueurs), chacun cherchant à atteindre ses propres objectifs, est appelé ...

(jeu, jeu)

64. Les actions autorisées de chacun des joueurs visant à atteindre un certain objectif sont appelées ...

(règles du jeu, règles du jeu)

65. L'évaluation quantitative des résultats du jeu s'appelle ...

(paiement, paiement, paiement)

66. Si seulement deux camps (deux personnes) participent au jeu, alors le jeu s'appelle ...

(double, double, double jeu, double jeu)

67. Si, dans un jeu de double, la somme des paiements est égale à zéro, c'est-à-dire que la perte d'un joueur est égale au gain de l'autre, alors le jeu s'appelle un jeu ...

(somme nulle)

68. Une description sans ambiguïté du choix d'un joueur dans chacune des situations possibles dans lesquelles il doit effectuer un coup personnel est appelée ..

(stratégie du joueur, stratégie du joueur, stratégie, stratégie)

69. Si, avec la répétition répétée du jeu, la stratégie fournit au joueur le gain moyen maximum possible (la perte moyenne minimum possible), alors une telle stratégie s'appelle ...

(stratégie optimale, optimale, optimale, stratégie optimale)

70. Soit a le prix le plus bas et b le prix le plus élevé d'un jeu de paires à somme nulle. Alors l'affirmation est vraie...

71. Soit a le prix le plus bas et b le prix le plus haut d'un jeu de paires à somme nulle. Si a = b = v, alors le nombre v est appelé ...

au prix du jeu

point d'équilibre

stratégie optimale

stratégie mixte

72. Soit a le prix le plus bas et b le prix le plus élevé d'un jeu de paires à somme nulle. Si a = b, alors le jeu s'appelle...

jeu de point de selle

conflit insoluble

un jeu sans règles

73. Un vecteur, dont chacune des composantes montre la fréquence relative de l'utilisation par le joueur de la stratégie pure correspondante, est appelé ...

stratégie mixte

vecteur de guidage

vecteur normal

pente

74. Le prix inférieur du jeu matriciel donné par la matrice des gains est…

Plus que le prix bas

égal au prix le plus bas

n'existe pas

81. Jeu matriciel donné par la matrice des gains , …

a un point de selle

n'a pas de point de selle

n'est pas un couple

82. Le prix du jeu donné par la matrice des gains est…

83. Jeu matriciel donné par la matrice des gains , …

est un hammam

a un point de selle

n'est pas un couple

84. Un jeu de paires à somme nulle compte tenu de sa matrice de gains peut être réduit à...

problème de programmation linéaire

problème de programmation non linéaire

problème de programmation linéaire entier

problème d'optimisation classique

85. Le prix inférieur du jeu matriciel donné par la matrice des gains est…

Plus que le prix bas

égal au prix le plus bas

n'existe pas

92. Jeu matriciel donné par la matrice des gains , …

n'a pas de point de selle

a un point de selle

n'est pas un couple

93. Le prix du jeu donné par la matrice des gains est dans les limites de...

94. Si, dans un flux d'événements, les événements se succèdent à des intervalles de temps prédéterminés et strictement définis, alors un tel flux est appelé ...

ordinaire

organisé

95. Si la probabilité qu'un nombre quelconque d'événements frappent un intervalle de temps dépend uniquement de la longueur de cet intervalle et ne dépend pas de la distance qui sépare cet intervalle du début de la référence temporelle, alors le flux d'événements correspondant est appelé :

Stationnaire

flux sans conséquences

le plus simple

Poisson

96. Si le nombre d'événements tombant sur l'un des intervalles de temps choisis arbitrairement ne dépend pas du nombre d'événements tombant sur un autre intervalle de temps également choisi arbitrairement, à condition que ces intervalles ne se coupent pas, alors le flux d'événements correspondant est appelé ...

flux sans conséquences

ordinaire

révélateur

Ordinaire

97. Si la probabilité de toucher deux événements ou plus à la fois pendant une très courte période de temps est négligeable par rapport à la probabilité de ne toucher qu'un seul événement, alors le flux d'événements correspondant est appelé ...

ordinaire

extraordinaire

Ordinaire

Poisson

98. Si le flux d'événements a simultanément les propriétés de stationnarité, de banalité et d'absence de conséquences, alors on l'appelle :

le plus simple (Poisson)

Ordinaire

99. Un CMO monocanal avec pannes est un poste d'entretien quotidien pour un car-wash. La demande - une voiture qui est arrivée à un moment où le poste est occupé - est refusée. L'intensité du flux de voitures λ=1,0 (voiture par heure). Le temps de service moyen est de 1,8 heures. Le flux de voitures et le flux de services sont les plus simples. Alors, en régime permanent, le débit relatif qéquivaut à...

100. Un CMO monocanal avec pannes est un poste d'entretien quotidien pour un car-wash. La demande - une voiture qui est arrivée à un moment où le poste est occupé - est refusée. L'intensité du flux de voitures λ=1,0 (voiture par heure). Le temps de service moyen est de 1,8 heures. Le flux de voitures et le flux de services sont les plus simples. Ensuite, en régime permanent, le pourcentage de voitures qui se voient refuser le service est égal à ...

Composants du modèle mathématique

Les modèles mathématiques sont à la base de la résolution des problèmes économiques.

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

• sélection de variable de tâche
• l'élaboration d'un système de restrictions
• choix de la fonction objectif

Variables de tâche sont appelées grandeurs X1, X2, Xn, qui caractérisent pleinement le processus économique. Ils s'écrivent généralement sous la forme d'un vecteur : X=(X1, X2,...,Xn).

Le système des restrictions les tâches sont un ensemble d'équations et d'inéquations qui décrivent les ressources limitées dans le problème considéré.

fonction cible tâche est appelée une fonction de variables de tâche qui caractérise la qualité de la tâche et dont il faut trouver l'extremum.

En général, un problème de programmation linéaire peut être écrit comme suit :

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

Solution acceptable(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 les conditions de non-négativité.

L'ensemble des solutions réalisables (plans) des formes du problème éventail de solutions réalisables(ODR).

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

État: Pour la fabrication de n types de produits, m types de ressources sont utilisées. Faire 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) - le coût de chaque i-ème type de ressource pour la production d'une unité de volume du jème type de produit ;
• cj (j = 1,2,3,...,n) - profit de la vente d'un volume unitaire du j-ème type de produit.

Il est nécessaire d'élaborer un plan de production de produits qui offre un profit maximal avec des restrictions données 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-ème type de ressources pour la production d'un volume donné xj de produits sont égaux à aijxj, donc la restriction à l'utilisation des ressources pour la production de tous les types de produits a la forme :
Le bénéfice de la vente du j-ème type de produit est égal à cjxj, donc la fonction objectif est égale à :

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

Forme canonique problèmes 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 équations et les inégalités sont des contraintes, et les variables peuvent être non négatives ou changer 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 de coefficients du système d'équations
• X - matrice-colonne de variables de tâche
• A0 - matrice-colonne des parties droites du système de contraintes

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

Réduction d'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 la compilation de modèles de problèmes économiques, les contraintes sont principalement formées sous la forme d'un système d'inégalités, il est donc nécessaire de pouvoir passer d'un système d'inégalités à un système d'équations.

Prenons une inégalité linéaire a1x1+a2x2+...+anxn≤b et ajoutons à sa partie gauche une valeur xn+1, telle que l'inégalité devienne l'égalité a1x1+a2x2+...+anxn+xn+1=b. De plus, cette valeur xn+1 est non négative.

Considérons tout avec un exemple.

Réduisez le problème de programmation linéaire à la forme canonique :

Solution:
Passons au problème de la recherche du maximum de la fonction objectif.
Pour ce faire, on change les signes des coefficients de la fonction objectif.
Pour convertir 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 (cette opération est repérée par la lettre D sur le modèle mathématique).
La variable x4 est inscrite du côté gauche de la deuxième inégalité avec un signe "+", puisque l'inégalité a la forme "≤".
La variable x5 est inscrite du côté gauche de la troisième inégalité avec le signe "-", puisque l'inégalité a la forme "≥".
Les variables x4 x5 sont entrées dans la fonction objectif avec un coefficient. égal à zéro.
On écrit le problème sous forme canonique :