This page has been robot translated, sorry for typos if any. Original content here.

Programmation mathématique - Nakonechny S.І.

2.6 La méthode graphique de développement des tâches du programme linéaire

Pour développer des tâches en deux dimensions d'un programme linéaire , résoudre des tâches de deux tâches et prendre trois tâches triviales, utilisez la méthode graphique , qui peut être utilisée pour effectuer des tâches de programmation géométrique. Obmezhene, la méthode graphique victorieuse en faisant des zooms avant et arrière, encourage la baguette à être attachée dans un espace trivial (pour les tâches avec trois tâches d'hiver) et l'image graphique pour les tâches qui sont meilleures que trois fois.

Nous considérons la tâche.

Savoir

(2.17)

par drain:

(2.18)

. (2.19)

Il est permis que le système (2.18) du drain (2.19) soit la somme et le bagatokutnik des échanges rozv'yazkіv.

Avec l'interprétation géométrique du problème de programmation linéaire (§ 2.4), la peau est entrelacée et déséquilibrée dans (2.18) est la désignation de la ligne de démarcation ( i = 1, 2, ..., t ). En utilisant le système de réticulation (2.18), il est possible de représenter graphiquement la partie scindée, ainsi que de réaffirmer la signification des carrés, en tant que points, coordonnées de toutes sortes, vous pouvez satisfaire à toutes les tâches de la section transversale - bagatokutnik rozv'yazkіv .

Signification de Umv (2.19) nevid'mnosti, le domaine des solutions admissibles au problème consiste à poser le premier quadrant du système de coordonnées de l’espace bidimensionnel. La tâche principale de la programmation linéaire est d’interpréter géométriquement les lignes parallèles avec 1 x 1 + c 2 x 2 = const.

Skoristaєmosia pour le développement graphique des tâches d'un programme de pouvoir linéaire par les autorités imposées au § 2.5:

En fait, la tâche du programme linéaire est le plan optimal, alors la valeur extrême de la fonction fonctionnelle est l’un des sommets du bagatokutnik rozv'yazkіv. Généralement, la fonction de la valeur extrême est plus grande à un sommet du bagatokutnik, alors il n’ya aucune chance que ce soit au point le plus élevé, mais avec une combinaison linéaire de sommets.

Désormais, compléter graphiquement la tâche de programmation linéaire signifie connaître le sommet du rozv'yazkіv bagatokutnik, le résultat de la reconstruction des coordonnées est identique à la fonction (2.17) linéaire de la valeur la plus importante (la plus importante).

L'algorithme de la méthode graphique de développement des tâches du programme linéaire est stocké dans les catégories suivantes:

1. Je serai simple, rіvnyannya yakih dіstєmo zamіnoyu dans obmezhennyam tasks_ (2.18) des signes d'irrégularités pour des signes d'égalité.

2. Viznachaєmo pіvploschini, scho vіdpovіdayut tâches de séparation de la peau dermique_.

3. Tâches bagokutnik rozv'yazkіv connues dans le programme linéaire.

4. Sera un vecteur , nous augmentons directement la valeur des fonctions function.

5. Je serai directement avec 1 x 1 + c 2 x 2 = const, perpendiculaire au vecteur .

6. Ruhayuchi directement à partir de 1 x 1 + c 2 x 2 = const dans le vecteur direct (pour les tâches de maximisation), mais dans le domaine de la saillie (pour les tâches de minimisation), on connaît le pic de la fonction bagatokutz rozv'yazkіv, de tsіlova de gain de valeur extrême.

7. La valeur des coordonnées du point, dans la fonction yakie, est la collection de la valeur maximale (minimale), et i désigne la valeur extrême de la fonction dans le prix.

Au moment de capturer la méthode graphique pour développer les tâches du programme linéaire, vous pouvez avoir de tels problèmes:

1. Le prix est fonction de l'obtention de la valeur maximale sur le pic A du bagatokutnik rozv'yazkіv (figure 2.5).

2. La valeur maximale de la fonction de fonction du dossier au point de départ du yak de la banque AV (Fig. 2.6). La tâche du programme linéaire est le plan optimal alternatif.

3. La tâche du programme linéaire n'est pas du type optimal: pour l'essentiel, la fonction n'est pas interconnectée avec le feu (Fig. 2.7), mais le système consiste en un échange de tâches du total (Fig. 2.8).

Fig. 2.5 Fig. 2.6

Fig. 2,7 Fig. 2.8

4. La tâche du programme linéaire est le plan optimal pour les zones non interrompues de différences autorisées (Fig. 2.9 et 2.10). Sur la fig. 2,9 en des points Au maximum, sur la fig. 2.10 au point A - minumum, sur la fig. 2.11 il est montré que, dans différentes zones de plans acceptables non interconnectés, la fonction peut collecter le nombre maximal de valeurs minimales au dernier point de l'échange.

Fig. 2.9 Fig. 2.10

En utilisant la méthode graphique, les tâches suivantes sont possibles: programme linéaire n -vimirny space, en règle générale, lorsque le système de problèmes est réduit au système de trivialité, la première étape consiste à introduire les nombres les plus significatifs de n points sur deux, le nombre de sections étant m , à .

Todi, comme dans le cours de mathématiques environnementales, vous pouvez avoir deux leçons, par exemple x 1 ta x 2, faire vibrer le chemin, et apprendre les bases et le chemin à suivre. C'est permis, mais c'est testé. Otrimaєmo Rivnyan viglyadu:

Oskilki tout valeur puis roule autour, pense:

.

(2.19.1)

Jetons un coup d’œil, car il est possible de décrire l’esprit génétiquement. En gros, par exemple, je leur ai écrit:

Après avoir reconnu la valeur x 3 de son extrême extrême - zéro, il est clair que c’est:

.

Le prix est simple. Pour simple d'un côté et pour un ami - . Vіdmіtimo de l'autre côté droit de .

De la même manière, je vous encouragerai à recevoir toutes les informations nécessaires: ; ; ...; En vain pour les maladies cutanées dermiques, le taux de cancer de la peau est supérieur à zéro.

Avec une telle méthode, n - 2 coordonnées directes et deux axes ( . ) La peau d'entre eux est le signe de povploschtina, de vikonuetsya umova . Une partie de la place en régler l'heure de l'eau pour toutes les terres, en affirmant le bagatutnik de roses autorisées.

Il est permis que dans une tâche il soit nécessaire de connaître la valeur maximale de la fonctionnelle:

.

Présenter virazi pour . . , ...; h (2.19.1) pour toutes les fonctions, de sorte que vous puissiez sélectionner les première et deuxième lignes de fonctions F toutes ont moins de deux à deux fois cela :

.

de - un membre fort, qui n’a pas été victime d’intimidation dans une vue en cob de la fonction.

De toute évidence, les fonctions de lecture la portée de leur valeur maximale pour la valeur silencieuse cela qui . Désormais, la procédure pour compléter le plan optimal avec la pluralité de distances admissibles consiste à suivre l'algorithme pour l'ordre de deux d'entre elles.

En utilisant la méthode graphique, la tâche de la programmation linéaire

.

Razv'yazannya . Maєmo n = 7 - significations kichliques, m = 5 - significations kichliques. Viberemo yak vіlnі zmіnnі x 1 que x 2 en virazimo à travers eux tous нная de base Змінні. Depuis le premier maımo de rіvnyannya:
(2.19.2)

Z troisième rivnyannya:

(2.19.3)

et à partir du quatrième:

. (2.19.4)

Pіdstavlyayuchi (2.19.2) dans un autre système de rivnanny à (2.19.4) dans le reste, rozv'yazuєmo ikh leur présentement x 4 que x 7. Otrimaєmo:

;

.

Loin derrière l'algorithme, il faut x 1 = 0 et x 2 = 0 - axe des coordonnées; Il est clair qu'ils savent qu'ils reconnaissent x 3 = 0, x 4 = 0, x 5 = 0, x 6 = 0, x 7 = 0. Le bagatokutnik des liens autorisés est illustré à la Fig. 2.12.

Fig. 2.12

Nous connaissons la vue fonctionnelle, tournée de x 1 ta x 2. Pour la meilleure chose connue, vous pouvez toujours sélectionner x 3, x 4, x 5, x 6 ta x 7 en passant par les valeurs correctes x 1 et x 2, il est possible de sélectionner la valeur souhaitée pour la fonction, : . Відкидаючи вільний maximum, maman: . Vecteur de Bu векторmo (–5, –2), perpendiculaire au fond - droite F ' . Ruhayuchi straight F ' dans la ligne droite (il est nécessaire de connaître la valeur minimale de la fonction F ), le point minimal est le minimum - A (Fig. 2.13).

Fig. 2.13

Au point A, il y a deux droites obliques: x 6 = 0 et x 7 = 0. A partir de maintenant, pour que les coordonnées se coordonnent, il est nécessaire d’échanger le système de niveaux:

Système Rosv'yazkoy и = 8,5; = 5. Après avoir donné la valeur pour le virazi, nous connaissons la valeur optimale des valeurs de base:

= 0,5; = 16,5; = 17,5; = 0; = 0.

Pіdstanovkoy valeur cela dans la fonction linéaire F, la valeur de la fonction est claire:

.

2.7 Rassemblez les tâches en utilisant la méthode graphique

Jetons un coup d’œil à la méthode graphique pour le développement de certaines tâches économiques.

La société est spécialisée dans l’accès viral aux meubles de bureau. On voit deux façons de voir les deux commis comptables - et c’est-à-dire V. Les policiers des deux types travaillent sur les versets 1 et 2. Trivialité du traitement des échantillons d’un poste de police pour modèles en cuir. (2.4).

Tableau 2.4

La banalité des policiers comptables

Verstat

Traitement banal des modèles de police, hv.

Ressource d'une heure de travail verstativ, année. sur tijden

Un

Dans

1

30

15

40

2

12

26

36

Le côté de la société est l’un des véritables modèles de police A 50 ans. sur., et le modèle В - 30 à. à propos. Vivchennya rinku zbutu a montré que Schweezee buvait de la boisson sur des livres pour les modèles de police. Je ne dépasse pas les nichols pour le modèle B en big yak pour 30 unités, et les ventes du modèle de police B ne dépassent pas 80 livres par jour.

Signifie nécessairement la surveillance du virobnost de la police du livre de ces deux modèles, qui maximisent les profits de l'entreprise. Afin d'encourager un modèle économique et mathématique de la tâche à accomplir, il est nécessaire d'utiliser des graphiques.

Modèle mathématique de Pobudova . Dans le modèle об underwear, la surveillance du livre de notes de police des modèles A et V. Nehai x 1 correspond au nombre de policiers A, au nombre de firmes pour la semaine et x 2 au nombre maximum de modèles de police. Mathématiquement, vas comme ça:

.

Combinant les tâches de trivialité des robots verstativ 1 et 2 pour la production de produits et de boissons sur des modèles de police.

Séparation des robots triviaux verstatіv 1 et 2 peut afficher:

pour la version 1:

30 x 1 + 15 x 2 ≤ 2400 (hv);

pour la version 2:

12 x 1 + 26 x 2 ≤ 2160 (xb).

Obmejennya en boisson enregistré comme suit:

x 1 - x 2 ≤ 30 ta x 2 ≤ 80.

Avec un modèle zagalom ekonomiko-mathématique, les tâches peuvent être écrites comme suit:

max Z = 50 X 1 + 30 X 2 (2.20)

par drain:



Le modèle économique et mathématique est model le modèle des tâches du programme linéaire, qui peut être plus du double, et qui peut être expliqué graphiquement.

Razv'yazannya . Tout d'abord, en utilisant la méthode graphique de dessin, dans l'image géométrique des plans de tâches admissibles, dans une telle région, l'ensemble du modèle est visible. Les signes d'irrégularités sont concevables avec des signes d'empressement strict et d'encouragement aux graphiques de lignes droites (Fig. 2.14). La peau est en train de forcer des lignes droites vers la zone du système de coordonnées à deux endroits. Les coordonnées d'un des points de satisfaction sont satisfaites du manque d'attention, et le point de vue n'est rien. Si vous avez besoin de pivploschtinu (dans Fig. 2.14, directement indiqué par une ligne droite), vous devez prendre le point be-yak comme point de départ, le sens coordonné étant noté obmezhenennya. En fait, c’est une légère planéité dans laquelle se trouve un point vibran, точка pour les images géométriques d’irrégularités. Нак таким з таким таким ображ ображ п п п п п п п п п п п п п.

Fig. 2.14

Umova nevid'єmnosti de x 1 ≥ 0, x 2 ≥ 0 significatif intersectant la zone des plans admissibles pour le problème avec le premier quadrant du système de coordonnées. Pererіz usіkh pіvploschtin viznachaє la zone de plans admissibles pour les tâches - OABCDE à six membres. Les coordonnées du point sont satisfaites du système de tâches et de celui du plus important. La tâche sera définie à cet effet, car il est possible de voir le point du bagatokutnik OABCDE , dans la fonction principale Z de la valeur la plus significative.

Pour tsoyu je vais векторmo vector , les coordonnées d'un certain facteur при avec les fonctions continues des tâches. Vecteur attendez pour entrer du cob de coordonnées et contraintes au point avec des coordonnées ( x 1 = s 1; x 2 = s 2). Notre vecteur de tâches . L'affectation des gains est directement liée à la valeur de la fonction Z et le vecteur qui vous est directement associé est le changement direct.

Par exemple, la valeur Z = 0. Le prix sera droit 50 x 1 + 30 x 2 = 0, le yak est perpendiculaire au vecteur passer à travers l'épi de coordonnées. Les fragments de cette application doivent être délimités pour la valeur la plus significative de la fonction, elle est alors trop simple 50 x 1 + 30 x 2 = 0 en parallèle avec le signal auto-généré du vecteur direct sur le sol, docks pas sensiblement le haut de la bagatokutnik, yak vіdpovіdaє le plan optimal des tâches.

Picз pic. 2.14 on peut voir que le point stable restant de la fonction directe et de l'OABCDE bagatutnik est le point C. Coordonnez le point є avec le plan optimal des tâches, par exemple avec un si grand nombre de registres de policiers et de ceux qui souhaitent obtenir le maximum de visibilité possible.

Les coordonnées du point C є système d'interconnexion rivnien (2.17) en (2.18):

zvidsi maєmo: x 1 = 50; x 2 = 60.

Otzhe, X * = (50; 60);

Cela signifie que si l’entreprise compte 50 petits livres, les modèles A et 60 étant des modèles B, le bénéfice maximum est de 4 300. à propos. Tse povrebuvatime povnorostnya tizhnevyh ressources en heures de travail verstatіv 1 que 2.

Pour les petits ptahofermi, il est presque nécessaire de donner la ration de fourrage optimale pour 1000 poules, qui peut varier de 4 à 8 fois. Nehtuyuchi tim, nourriture de merde à nourrir pour que le kurchat se couche au milieu de la journée, et chérie, pour 4 poules Tuchny, ce n’est pas moins de 500 grammes. En outre, la race fourragère kurchat ma udovolennosti chantant la vie de vimogi schodo. Je vais formuler le prix de la simplicité pour la simplicité de la personne surveillée, les boucles d'oreille pour le meilleur de votre opinion: des mots de plus en plus vivants: un petit et un petit oiseau et deux sortes de céréales pour prendre leur place à la poupe - grains et haricots. La liste des kystes vivants dans l'alimentation de la peau et celle de la mère à la table. 2.5.

Tableau 2.5

VIE ET ​​VARITY FOOD

Nourrir

Liste des vaches vivantes dans 1 kg de nourriture,%

Vartіst 1 kg de nourriture, à. à propos.

Bilku

Klitkovini

Grain

10

2

0,40

Sobi Bobi

50

8

0.90

Je suis prêt à nourrir la quantité totale de viande pas moins de 20% et pas 5% de la classe.

Visitez le masu de la peau pour deux types de nourriture, qui approuvera la somme de nourriture du minimum de verrue, l'heure de l'eau de la satisfaction de la nourriture pour le montant total de la somme de nourriture des frais de subsistance.

Modèles économiques et mathématiques de Pobudova. Nekhay x 1 - grain de masa et x 2 - soja (en kg) dans la somme d'aliments prêts à l'emploi.

Plus de détails sur ce produit x 1 + x 2 ma liste de prix 500 kg, tobto

x 1 + x 2 ≥ 500.

Jetons un coup d'œil à la durée de vie de la quantité d'aliments.

Sum_must_mest_n’t moins de 20% de la facture:

10 x 1 + 50 x 2 ≥ 20 ( x 1 + x 2),

ainsi que pas plus de 5% de klitkovini:

2 x 1 + 8 x 2 ≤ 5 ( x 1 + x 2).

Zagalom modèle mathématique de la tâche d'optimiser la ration alimentaire d'un tel vigoureusement:

min Z = 0,40 x 1 + 0,90 x 2 (2,26)

par drain:

(2.30)

Razv'yazannya . Le graphique de l'interprétation des tâches est présenté à la Fig. 2.15. Beaucoup de розї rozv'yazkіv admissibles est ininterrompu. Pour vecteur = (0.4; 0.9) il est possible d’échelle, par exemple, = (200; 450). La valeur la plus importante de la fonction Z est le point A , qui devrait être situé sur les lignes droites de la frontière, de manière à faire la distinction entre (2.27) et (2.28). Apparemment, les coordonnées sont:

Otzhe, X * = (375; 125); min Z = 0,4 • 375 + 0,9 • 125 = 262,5.

Il est clair que nous disposons du plan de travail optimal pour pouvoir prendre 500 kg de nourriture au total (262,50 dollars) et 375 kg de céréales et 125 kg de haricots. Pour une telle composante liée du montant du salaire jusqu'à l'espérance de vie:

0,10 • 375 + 0,50 • 125 = 100 kg de nourriture, il faut devenir égal à 20% de la somme totale;

0,02 • 375 + 0,08 • 125 = 17,5 kg de klіtkovini dans la quantité d'aliment, mais pour devenir 3,5% du marché de masse et je ne pas écraser 5%.

Firma vigotovlyaє d'un type de syrovini deux produits A et B, qui sont vendus séparément à 8 et 15 kopecks par paquet. Le rhinocéros zbutu pour le derme en eux est une non-médiation pratique. Syrovine pour le produit A peut être testé avec la version 1 et pour le produit B avec la version 2. Les produits potentiellement dangereux sont emballés dans des usines. Le schéma des produits A et B de virobnitz est décrit à la Fig. 2.16.

Fig. 2.16. Schéma de câblage du produit

Le prix de 1 kg de syrovini - 6 kopecks. Verstat 1 a été testé pour 5 tonnes de syrovini par an et verstat de 2 à 4 tonnes de syrovini à un taux inférieur à 10% et 20%. Verstat 1 mozhe praciuvati 6 ans par jour, la raison en est є 288 UAH / an; verstat 2-5 ans par jour, scho koshtu 336 UAH / an.

Masa pour le produit A dans un emballage est de 1/4 kg et pour le produit B - de 1/3 kg. L'usine moghe pratsuvati 10 ans par jour, les shchogodini emballent 12 000 unités, et même 8 000 unités, les robots V. Wartіst du produit s'étirant sur 1 an pour devenir 360 UAH.

Nécessairement vidshukati telle valeur x 1 que x 2 obyag_v vikoristannya sirovini pour les produits et A et B (en tonnes), afin de garantir le plus grand voyage disponible.

Modèles économiques et mathématiques de Pobudova . Nekhay x 1 ta x 2 - vіdpovіdno serments de sirovini, vikoristovuvanі pour le produit de vigotovlennya A ta B en un jour, t

Tâches obmezhdennya écrites. C’est une question de partage mental des ressources - trivialité des œuvres 1 et 2, mais aussi des trivialités du robot d’une usine avec le conditionnement des produits A et V.

1. Obmejennya on vikoristannya verstata 1.

La manière économique de procéder est la suivante: la trivialité du lieu de travail est de 1% de l’échantillon de syrovini pour le produit, mais pas de 6 ans, car:

Mathématiquement, écrivez comme suit:

x 1/5 ≤6 ou x 1 ≤ 30.

2. Obmezhdennya shchodo vikoristannya verstata 2 virazimo de la même manière:

x 2/4 ≤ 5 ou x 2 ≤ 20.

3. Obmezhdennya shchodo trivialosti robots de l'usine avec des produits d'emballage Et que B.

Le coût économique d'un tel échange est le suivant: l'heure réelle est consacrée au conditionnement des produits A et B, mais pas 10 ans par jour:

Mathématiquement, écrivez comme suit:

de toute façon:

0,3 x 1 + 0,3 x 2 ≤ 10,

3 x 1 + 3 x 2 ≤ 100.

Je vais demander la fonction des tâches. Le gain de revenu d'entreprise est un revenu provenant de la vente de produits et une prime pour la vente de biens.

1. Dokhid vid virobnitzstva products Et ce B est comme suit:

abo

.

Zagalny dokhid dorіvnyuє 288 x 1 + 360 x 2.

2. Vitrati for sirovina visnozhaєmo ya zagalu kilkіst syrovini en tonnes, vikoristovuvano pour les produits virobniztva Et que B, multiplié par verrue 1 t sirovini hryvnia

60 ( x 1 + x 2) = 60 x 1 + 60 x 2.

3. Vitrati, en raison des versions 1 et 2, du nombre d'essais réels des robots verstat avec le traitement de sirovini pour des robots de verbosité d'un an:

.

4. Vitrati, povyazanі avec l'emballage des produits Et que V, pour augmenter la qualité des robots de l'usine réelle (0,3 x 1 + + 0,3 x 2) pour la première année de robot, yak deviennent 360 UAH:

360 (0,3 x 1 + 0,3 x 2) = 108 x 1 + 108 x 2.

Bereuchi pour le respect de tous les entrepôts de la fonction entière, vous pouvez enregistrer un viraz mathématique pour quelques jours par jour:

Z = (288 x 1 + 360 x 2) - (60 x 1 + 60 x 2) - (288/5 x 1 + 84 x 2) - (108 x 1 + 108 x 2) = 12/5 • ( 26 x 1 + 45 x 2).

Otzhe, le seul enregistrement du modèle économico-mathématique de ce type:

Z maxi = 12/5 • (26 x 1 + 45 x 2) (2,31)

par drain:

(2,35)

Il est indépendant d’un processus de pliage varié de la modélisation. Mathématiquement, la tâche est simple et facile à communiquer graphiquement.

Signature: Fig. 2,17 Razv'yazannya. Graphique de la tâche de la tâche fig. 2.17.

Le domaine des plans admissibles, qui peuvent être assimilés par un système de tâches, є bagatokutnik ABCDO . Найбільшого значення цільова функція досягає у вершині В. Координати цієї точки визначаються розв'язанням системи рівнянь:

Оптимальний план задачі: Х * = (40/3; 20); max Z = 2992 грн.

Отже, для того, щоб отримати найбільший денний прибуток 2992 грн, фірма має обробляти 40/3 тис. кг сировини, виробляючи продукт А, і 20 тис. кг — виробляючи продукт В. За такого оптимального плану випуску продукції верстат 2 працюватиме 20/4 = 5 год на день, тобто з повним навантаженням, а верстат 1 працюватиме лише 40/15 = 2 год 20 хв щодня.