Quel programme est linéaire en c. En bref sur la programmation linéaire

Maison / Routeurs

Si toutes les instructions d'un programme sont exécutées séquentiellement, les unes après les autres, un tel programme est appelé linéaire. Considérons comme exemple un programme qui calcule le résultat à l'aide d'une formule donnée.

Tâche 1.1. Calcul par formule

Écrivez un programme qui convertit la température en degrés Fahrenheit en degrés Celsius en utilisant la formule :

où C est la température en Celsius et F est la température en Fahrenheit.

Avant d'écrire un programme, nous devons clairement définir ce qui doit y être entré et ce que nous devrions obtenir en conséquence.

DANS dans ce cas:

Les données initiales sont une nombre réel, qui est la température en Celsius,

Le résultat est un autre nombre réel.

Avant d'écrire le programme, ouvrons l'environnement intégré Visual C++ :

Début/Programmes/Microsoft Visual Studio/Microsoft Visual C++ 6.00

1) Fichier > Nouveau...

2) Dans la fenêtre qui s'ouvre :

Sélectionnez le type d'application console Win32 ;

Entrez un nom pour le projet dans la zone de texte Nom du projet ;

Saisissez (sélectionnez à l'aide du bouton ...) le nom du répertoire où se trouvent les fichiers du projet dans le champ de texte Emplacement, par exemple G:/ASOIZ/

Faites un clic gauche sur le bouton OK.

3) la boîte de dialogue Application console Win32 - Étape 1 s'ouvre et s'y trouve :

Sélectionnez le type Un projet vide ;

Cliquez sur le bouton Terminer.

4) Après avoir cliqué, la fenêtre Nouveau projet apparaîtra, dans laquelle cliquez sur le bouton OK.

1) Fichier > Nouveau.... Cela ouvrira la boîte de dialogue Nouveau.

2) Dans l'onglet Fichiers :

Sélectionnez le type de fichier (dans ce cas : fichier source C++) ;

Dans la zone de texte Nom du fichier, entrez le nom du fichier souhaité ;

La case Ajouter au projet doit être cochée ;

Cliquez sur OK.

Nous tapons le texte de programme suivant :

Examinons chaque ligne du programme séparément.

Au début du programme, une directive de préprocesseur est écrite, selon laquelle un fichier d'en-tête est connecté au texte source du programme . Il s'agit d'un fichier qui contient des descriptions des opérateurs d'E/S cin et cout.

Tout programme C++ est constitué de fonctions, dont l'une doit porter le nom main, indiquant que c'est là que commence l'exécution du programme. Après les parenthèses, le corps de la fonction est écrit entre accolades ( ), c'est-à-dire ces déclarations qui doivent être exécutées.

Tout modèle lors de l'écriture d'un programme a la forme :

#inclure<…>

déclaration de variables ;

saisie des données initiales ;

calcul du résultat ;

afficher le résultat ;

Pour stocker les données sources et les résultats, vous devez allouer suffisamment d'espace dans BÉLIER. Cela se fait à l'aide de l'instruction 2. Notre programme doit stocker deux valeurs : la température en Celsius et la température en Fahrenheit, l'instruction définit donc deux variables. L’un, pour stocker les températures en Fahrenheit, s’appelle fahr, l’autre (en Celsius) s’appelle cels. Le programmeur donne des noms aux variables en fonction de leur objectif. Le nom ne peut être composé que de lettres latines, de chiffres et d'un trait de soulignement et ne doit pas commencer par un chiffre.

Lorsque vous décrivez une variable, vous devez l'indiquer taper. Puisque la température peut prendre non seulement des valeurs entières, le type réel est choisi pour les variables flotter

Principaux types :

int (court, non signé) – entiers,

float (double, long double) – réel

char – caractère

bool – logique

Pour que l'utilisateur du programme sache à quel moment il est nécessaire de saisir des données à l'aide du clavier, ce que l'on appelle l'invite de saisie est utilisée (opérateur 3). Le spécifié dans l'opérateur est affiché à l'écran. cout ligne de caractères et le curseur passe à la ligne suivante. Pour passer à la ligne suivante, utilisez fin.

Dans l'instruction 4, un seul nombre est saisi au clavier dans une variable fahr. A cet effet, un objet standard est utilisé cin et l'opération d'extraction (lecture) >>. Si vous devez saisir plusieurs valeurs, utilisez la chaîne d'opérations >>.

L'opérateur 5 évalue l'expression écrite à droite de opérations d'affectation(indiqué par le signe =), et le résultat est affecté à la variable cels, c'est-à-dire stocké dans la mémoire allouée à cette variable. D'abord entier la constante 5 sera divisée par baiser constante 9, alors le résultat de cette opération est multiplié par le résultat de la soustraction du nombre 32 de la variable fahr.

Pour afficher le résultat dans l'opérateur 6, un objet est utilisé cout. Une chaîne composée de cinq éléments s'affiche. C'est la ligne « Fahrenheit : », valeur variable fahr, doubler ", en degrés Celsius :", valeur variable cellules et l'opérateur de nouvelle ligne fin.

La dernière instruction (instruction 7) de ce programme est destinée à en revenir et à transférer la valeur à l'environnement externe.

Ensuite, nous compilons le programme. Pour ce faire, appuyez sur le bouton de la barre d'outils ou sur la combinaison de touches Ctrl+F7. La fenêtre de sortie (en bas de l'écran) doit afficher le message 0 erreur(s), 0 avertissement(s) (0 erreur, 0 avertissement). S'il y a des erreurs, vérifiez avec l'original.

Pour démarrer le programme, appuyez sur le bouton de la barre d'outils ou sur la combinaison de touches Ctrl+F5.

Au démarrage du programme, au lieu des caractères russes, nous voyons ???, ce qui est dû à des normes différentes d'encodage des caractères cyrilliques dans systèmes d'exploitation MS DOS et Windows. Pour résoudre ce problème, ajoutez la fonction CharToOem au programme (les ajouts sont surlignés en rouge pour plus de clarté)

#inclure

char* RUS(const char* texte)

CharToOem(texte, buf);

flotteur fahr, cellules ;

cout<

cels=5/9 * (fahr - 32) ;

cout<

Fonction Russie() ne peut pas être utilisé plus d’une fois dans une chaîne d’opérations<< для одного объекта cout, nous l'avons donc divisé en deux.

Comme vous pouvez le voir, le résultat de l’exécution du programme avec stabilité est nul ! Cela se produit en raison de la manière dont l'expression est évaluée. Regardons à nouveau l'opérateur 4. Les constantes 5 et 9 sont de type entier, donc le résultat de leur division est également un entier. Naturellement, le résultat de calculs ultérieurs ne peut être autre que zéro. Corriger cette erreur est simple : il suffit d'écrire au moins une des constantes sous forme de nombre réel, par exemple :

cellules = 5. / 9 * (fahr - 32) ;

Travail de laboratoire n°1

Sujet : « Programmation d'algorithmes linéaires. Travailler avec le débogueur"

But du travail

1.1 Maîtriser la structure de programme la plus simple en langage C.

1.2 Acquérir des compétences dans l'organisation des entrées/sorties en langage C.

Assistance technique

2.1 Ordinateur personnel

2.2 Clavier.

2.3 Affichage

2.4 Dispositif d'impression.

Logiciel

3.1 Système d'exploitation Windows

3.2 Système de programmation Visual C++ version 6.0 ou Borland C++ version 3.1 et versions ultérieures.

Énoncé du problème

Ecrire un programme simple avec traitement de données.

5.1 Thème et objectif du travail.

5.2 Énoncé du problème.

5.3 Texte des programmes.

5.4 Résultats de l'exécution du programme.

5.5 Diagrammes d'algorithme du programme.

informations générales

Programme linéaire

Tâche 1.1. Calcul par formule

Écrivez un programme qui convertit la température en degrés Fahrenheit en degrés Celsius en utilisant la formule :

où C est la température en Celsius et F est la température en Fahrenheit.

Avant d'écrire un programme, nous devons clairement définir ce qui doit y être entré et ce que nous devrions obtenir en conséquence.

Dans ce cas:

La donnée initiale est un nombre réel représentant la température en Celsius,

Le résultat est un autre nombre réel.

Avant d'écrire le programme, ouvrons l'environnement intégré Visual C++ :

Début/Programmes/Microsoft Visual Studio/Microsoft Visual C++ 6.00

1) Fichier > Nouveau...

2) Dans la fenêtre qui s'ouvre :

Sélectionnez le type d'application console Win32 ;

Entrez un nom pour le projet dans la zone de texte Nom du projet ;

Saisissez (sélectionnez à l'aide du bouton ...) le nom du répertoire où se trouvent les fichiers du projet dans le champ de texte Emplacement, par exemple G:/ASOIZ/

Faites un clic gauche sur le bouton OK.

3) la boîte de dialogue Application console Win32 - Étape 1 s'ouvre et s'y trouve :

Sélectionnez le type Un projet vide ;

Cliquez sur le bouton Terminer.

4) Après avoir cliqué, la fenêtre Nouveau projet apparaîtra, dans laquelle cliquez sur le bouton OK.

1) Fichier > Nouveau.... Cela ouvrira la boîte de dialogue Nouveau.

2) Dans l'onglet Fichiers :

Sélectionnez le type de fichier (dans ce cas : fichier source C++) ;

Dans la zone de texte Nom du fichier, entrez le nom du fichier souhaité ;

La case Ajouter au projet doit être cochée ;

Cliquez sur OK.

Nous tapons le texte de programme suivant :

Examinons chaque ligne du programme séparément.

Tout modèle lors de l'écriture d'un programme a la forme :

#inclure<…>

déclaration de variables ;

saisie des données initiales ;

calcul du résultat ;

afficher le résultat ;

Pour stocker les données sources et les résultats, vous devez allouer suffisamment d'espace dans la RAM. Cela se fait à l'aide de l'instruction 2. Notre programme doit stocker deux valeurs : la température en Celsius et la température en Fahrenheit, l'instruction définit donc deux variables. L’un, pour stocker les températures en Fahrenheit, s’appelle fahr, l’autre (en Celsius) s’appelle cels. Le programmeur donne des noms aux variables en fonction de leur objectif. Le nom ne peut être composé que de lettres latines, de chiffres et d'un trait de soulignement et ne doit pas commencer par un chiffre.

Lorsque vous décrivez une variable, vous devez l'indiquer taper. Puisque la température peut prendre non seulement des valeurs entières, le type réel est choisi pour les variables flotter

Principaux types :

int (court, non signé) – entiers,

float (double, long double) – réel

char – caractère

bool – logique

L'instruction 4 effectue une saisie au clavier

A cet effet, un objet standard est utilisé cin et l'opération d'extraction (lecture) >>. Si vous devez saisir plusieurs valeurs, utilisez la chaîne d'opérations >>.

La dernière instruction (instruction 7) de ce programme est destinée à en revenir et à transférer la valeur à l'environnement externe.

Pour démarrer le programme, appuyez sur le bouton de la barre d'outils ou sur la combinaison de touches Ctrl+F5.

Au démarrage du programme, au lieu des caractères russes, nous voyons ???, ce qui est dû aux différentes normes d'encodage des caractères cyrilliques dans les systèmes d'exploitation MS DOS et Windows. Pour résoudre ce problème, ajoutez la fonction CharToOem au programme (les ajouts sont surlignés en rouge pour plus de clarté)

#inclure

char* RUS(const char* texte)

CharToOem(texte, buf);

flotteur fahr, cellules ;

cout<

cels=5/9 * (fahr - 32) ;

cout<

Fonction Russie() ne peut pas être utilisé plus d’une fois dans une chaîne d’opérations<< для одного объекта cout, nous l'avons donc divisé en deux.

cellules = 5. / 9 * (fahr - 32) ;

Les programmes constitués de commandes simples (opérateurs) sont appelés linéaires.
Les commandes simples (instructions simples de l'algorithme) sont des commandes qui n'utilisent pas de conditions lors de leur exécution. Les opérateurs simples comprennent des commandes (opérateurs) d'affectation, d'entrée et de sortie, ainsi que l'appel d'un algorithme auxiliaire (sous-programme).

Opérateur d'affectation. Il définit ou modifie la valeur actuelle d’une variable. Cela modifie le contenu d'un élément de mémoire spécifique alloué à cette variable. Puisque le but de tout algorithme est d'obtenir la valeur souhaitée dans un certain emplacement mémoire, presque tous les programmes contiennent cet opérateur. Opérateurs d'E/S. Les procédures standard de saisie de données sont utilisées pour déterminer les valeurs initiales de certaines variables et consistent en un nom de procédure et une liste d'entrée contenant les noms des variables dont les valeurs seront saisies à partir du clavier ou à partir d'un fichier, c'est-à-dire Les variables se verront attribuer des valeurs spécifiques.
Le plus souvent, pour déterminer les valeurs initiales, il est plus pratique d'utiliser la commande de saisie plutôt que la commande d'affectation, car si vous devez utiliser le programme avec des données initiales différentes, vous n'avez pas besoin de modifier le texte du programme.
Si l'enregistrement de l'algorithme contient une commande d'entrée, son exécution est interrompue et le contrôle est transféré à un programme capable de saisir des données. Après avoir saisi les données, le contrôle est transféré à la commande suivante de l'algorithme.
En Pascal, la procédure de saisie des données ressemble à ceci :
READ (liste d'entrée);
READLN (liste d'entrée).
Lorsque les procédures READ et READLN sont exécutées, le programme entre dans l'état d'attente de saisie de données. Si plusieurs variables sont spécifiées dans la liste de saisie, elles peuvent alors être saisies sur une seule ligne, séparées les unes des autres par un espace, ou sur des lignes séparées (dans une colonne), en complétant la saisie de chaque valeur avec la touche Entrée.
La procédure ne se terminera que lorsque les valeurs auront été saisies pour toutes les variables de la liste. Le type de valeurs saisies doit correspondre à celles de la variable correspondante.
L'instruction READLN diffère de l'instruction READ en ce sens qu'une fois la quantité de données requise saisie, le curseur passe à la ligne suivante.
Si les données sont saisies à partir du clavier, alors la liste de saisie est une liste de variables, c'est-à-dire une séquence de noms de variables séparés par des virgules. Si l'entrée provient d'un fichier, alors la première variable de la liste d'entrée est la variable de fichier, associée au nom du fichier réel.
Des procédures standard de sortie des résultats de calcul sont utilisées pour afficher leurs valeurs sur un écran, une imprimante ou un fichier. En Pascal, les procédures d'inférence ressemblent à ceci :
WRITE(liste de sortie);
WRITELN (liste de sortie).
La liste des éléments de sortie est beaucoup plus large que dans les procédures d'entrée. Cela peut inclure :
identifiants de grandeurs dont les valeurs seront sorties sur l'appareil ou le fichier correspondant ;
des expressions dont les valeurs seront d'abord calculées puis transmises à l'appareil ;
sont devenus des valeurs (numériques, symboliques, chaîne).
La différence entre WRITE et WRITELN réside dans le fait que la sortie de l'instruction WRITE commence à l'emplacement actuel du curseur sur l'écran du moniteur et que le curseur reste sur la même ligne une fois la sortie terminée. L'instruction WRITELN imprime les valeurs de la position actuelle, puis le curseur passe à la ligne suivante. Vous pouvez utiliser l'instruction WRITELN sans liste de sortie pour déplacer le curseur vers une nouvelle ligne.
Si la sortie s'effectue sur un écran de contrôle, la liste de sortie est une liste de variables ou une séquence de noms de variables, de constantes ou d'expressions séparées par des virgules. Si la sortie est vers un fichier, alors la première variable de la liste de sortie est la variable de fichier, associée au nom du fichier réel.
Dans la commande de sortie, après l'élément de liste de sortie, vous pouvez spécifier le format de sortie, séparé par deux points, c'est-à-dire la largeur de l'écran sur lequel se situeront les valeurs. Lors de l'affichage de données réelles, vous pouvez également spécifier le nombre de chiffres décimaux dans la partie fractionnaire que vous souhaitez afficher.
Exemple : écrire (A : 10 : 3, B : 8).
Opérateur pour appeler un algorithme auxiliaire. Pascal implémente des sous-programmes de procédure et des sous-programmes de fonction. Un sous-programme est appelé par son nom indiquant les paramètres réels. Dans ce cas, à la place des arguments réels, il peut y avoir des valeurs spécifiques, des noms de variables réelles, des expressions, et à la place des résultats, uniquement des noms de variables réelles. Dans ce cas, le nombre, les types et l'objectif des paramètres formels et réels dans les listes de paramètres correspondantes doivent correspondre.

Ci-dessus, nous avons examiné divers problèmes pratiques pouvant être réduits à un schéma de programmation linéaire. Dans certains de ces problèmes, les contraintes linéaires avaient la forme d'inégalités, dans d'autres - d'égalités, dans d'autres - les deux.

Nous considérerons ici un problème de programmation linéaire avec des contraintes d'égalité - ce qu'on appelle le problème de programmation linéaire de base (BLP).

À l’avenir, nous montrerons comment passer d’un problème de contraintes d’inégalité à un OPLP, et vice-versa.

Le problème principal de la programmation linéaire s’énonce comme suit.

Il existe un certain nombre de variables

Il est nécessaire de trouver de telles valeurs non négatives de ces variables qui satisferaient le système d'équations linéaires :

et, en outre, minimiserait la fonction linéaire

Évidemment, le cas où une fonction linéaire doit être tournée non pas vers un minimum, mais vers un maximum, peut facilement être réduit au précédent, si nous changeons le signe de la fonction et considérons plutôt la fonction

Acceptons d'appeler tout ensemble de variables une solution admissible de l'OLP

satisfaisant les équations (2.1).

Nous appellerons la solution optimale celle des solutions admissibles pour lesquelles la fonction linéaire (2.2) devient un minimum.

Le problème de base de la programmation linéaire n’a pas nécessairement de solution.

Il se peut que les équations (2.1) se contredisent ; il se peut qu'ils aient une solution, mais pas dans la région des valeurs non négatives. L’OLP n’a alors aucune solution recevable. Enfin, il se peut que des solutions admissibles de l'OLP existent, mais parmi elles il n'y en a pas de optimale : la fonction L dans la région des solutions admissibles est illimitée par le bas.

Nous nous familiariserons plus tard avec des exemples de telles fonctionnalités d'OPLP.

Considérons tout d'abord la question de l'existence de solutions admissibles à l'OLP.

Lors de la résolution de ce problème, nous pouvons exclure de la considération la fonction linéaire L qui doit être minimisée - la présence de solutions réalisables n'est déterminée que par les équations (2.1).

Soit donc un système d'équations (2.1). Existe-t-il des valeurs non négatives qui satisfont à ce système ? Cette question est abordée dans une branche particulière des mathématiques : l'algèbre linéaire.

Présentons brièvement quelques dispositions de l'algèbre linéaire, sans nous attarder sur les preuves des théorèmes correspondants

Matrice d'un système d'équations linéaires

est un tableau composé des coefficients de

Une matrice étendue d'un système d'équations linéaires est la même matrice complétée par une colonne de termes libres :

Le rang d'une matrice est l'ordre le plus élevé d'un déterminant non nul pouvant être obtenu en supprimant certaines lignes et certaines colonnes de la matrice.

En algèbre linéaire il est prouvé que pour que le système d’équations linéaires (2.1) soit cohérent, il faut et il suffit que le rang de la matrice du système soit égal au rang de sa matrice étendue.

Exemple 1. Étant donné un système de trois équations à quatre inconnues :

Déterminer si ce système est collaboratif ?

Solution. Matrice du système :

Matrice étendue :

Déterminons le rang de la première matrice. Il ne peut pas être supérieur à 3 (puisque le nombre de lignes est de 3). Créons un déterminant en supprimant une colonne de la matrice, par exemple la dernière. Nous obtenons

En calculant ce déterminant selon la règle bien connue, on obtient :

Ce déterminant n'est pas égal à zéro, ce qui signifie que le rang de la matrice système est égal à 3. Évidemment, le rang de la matrice étendue est également égal à 3, puisque le même déterminant peut être composé des éléments de la matrice étendue. De l'égalité des rangs des matrices il résulte que le système d'équations est cohérent.

Exemple 2. Étudier la compatibilité d'un système de deux équations à trois inconnues :

Solution. Matrice du système étendu :

(son côté gauche est la matrice système).

Trouvons le rang de la matrice du système en composant tous les déterminants du second ordre possibles :

Ainsi, tous les déterminants possibles du second ordre composés d'éléments de la matrice système sont égaux à zéro ; Cela signifie que le rang de cette matrice du système est

Trouvons le rang de la matrice étendue. Déterminant

Ainsi le rang de la matrice étendue n'est pas égal au rang de la matrice système : Grfg, donc le système d'équations est incohérent.

Exemple 3. Étudier la cohérence d'un système de trois équations à quatre inconnues :

Solution Matrice système étendue (avec la matrice système) :

Trouvons le rang de la matrice système. Prenons par exemple un déterminant du troisième ordre composé de ses éléments :

On sait que si une ligne d’un déterminant est une combinaison linéaire de ses deux autres lignes, alors le déterminant est égal à zéro. Dans notre cas, la troisième ligne est une combinaison linéaire des deux premières : pour l'obtenir, il suffit d'ajouter la première ligne au double de la seconde donc.

Il est facile de vérifier que tout déterminant du troisième ordre composé d'éléments de la matrice système a la même propriété. Par conséquent, le rang de la matrice système est .

Puisqu’il existe un déterminant du second ordre non nul, par exemple,

alors le rang de la matrice système est égal à

En utilisant le même raisonnement, on s'assure que le rang de la matrice étendue est égal à deux : Le système d'équations est donc compatible

Notez que les trois équations de cet exemple ne sont pas indépendantes : la troisième peut être obtenue à partir des deux premières en multipliant la seconde par deux et en l'ajoutant à la première. Cela signifie que la troisième équation est une simple conséquence des deux premières. Il n'y a que deux équations indépendantes dans le système : cela se reflète dans le fait que le rang de la matrice du système

Ainsi, si le système d’équations-contraintes de l’OLP est cohérent, alors la matrice du système et sa matrice étendue ont le même rang.

Ce rang global est appelé rang du système ; il ne représente rien de plus que le nombre d'équations linéairement indépendantes parmi les contraintes imposées.

Évidemment, le rang du système ne peut pas être supérieur au nombre d’équations :

Il est également évident que le rang du système ne peut être supérieur au nombre total de variables :

En effet, le rang d'une matrice système est défini comme l'ordre le plus élevé du déterminant composé d'éléments matriciels ; puisque le nombre de ses lignes est égal à , alors ; puisque le nombre de ses colonnes est égal à , alors .

La structure d'un problème de programmation linéaire dépend significativement du rang du système de contraintes (2.1).

Considérons d'abord le cas où , c'est-à-dire lorsque le nombre d'équations linéairement indépendantes incluses dans le système (2.1) est égal au nombre de variables n. Écartons les équations « supplémentaires » qui sont des combinaisons linéaires d'autres. Le système d'équations-contraintes de l'OZLP prend la forme :

Puisque le déterminant, composé de coefficients,

pas égal à zéro. L’algèbre sait que dans ce cas le système (2.4) a une solution unique. Pour trouver la quantité, il suffit de remplacer la colonne du déterminant par une colonne de termes libres et de diviser par.

Ainsi, lorsque le système d’équations de contraintes de l’OLP a une solution unique :

Si dans cette solution au moins une des quantités est négative, cela signifie que la solution résultante est inacceptable et donc l’OPLP n’a pas de solution.

Si toutes les quantités sont non négatives, alors la solution trouvée est admissible. C’est aussi, évidemment, optimal (car il n’y en a pas d’autres).

Évidemment, ce cas trivial ne peut pas nous intéresser.

Par conséquent, à l'avenir, nous ne considérerons que le cas où, c'est-à-dire lorsque le nombre d'équations indépendantes que les variables doivent satisfaire sont les nombres des variables elles-mêmes. Alors, si le système est cohérent, il a une infinité de solutions. Dans ce cas, nous pouvons attribuer des valeurs arbitraires aux variables (les variables dites libres), et les variables restantes seront exprimées à travers elles (nous appellerons ces variables basiques).

Choix de l'éditeur