Cos'è un programma lineare. Brevemente sulla programmazione lineare. Programmi lineari con array

Sopra, abbiamo considerato vari compiti pratici che si riducono allo schema programmazione lineare... In uno di questi compiti vincoli lineari sembrava disuguaglianza, in altri - uguaglianze, in altri - entrambi.

Qui considereremo un problema di programmazione lineare con vincoli di uguaglianza - il cosiddetto problema di programmazione lineare di base (0PLP).

In quanto segue, mostreremo come si può passare da un problema con vincoli di disuguaglianza a un LPLP e viceversa.

Il compito principale della programmazione lineare è il seguente.

Ci sono un certo numero di variabili

È necessario trovare tali valori non negativi di queste variabili che soddisfino il sistema equazioni lineari:

e, inoltre, minimizzerebbe funzione lineare

Ovviamente il caso in cui una funzione lineare debba essere girata non al minimo, ma al massimo, si riduce facilmente al precedente, se cambiamo segno alla funzione e consideriamo invece la funzione

Accettiamo di chiamare qualsiasi insieme di variabili

equazioni soddisfacenti (2.1).

La soluzione ottima è quella delle soluzioni ammissibili per le quali la funzione lineare (2.2) diventa minimo.

Il problema di programmazione lineare di base non deve avere una soluzione.

Può risultare che le equazioni (2.1) si contraddicano a vicenda; potrebbe risultare che hanno una soluzione, ma non nella regione dei valori non negativi. Quindi l'OZLP non ha soluzioni praticabili. Infine, può risultare che esistono soluzioni ammissibili della DLP, ma tra queste non ce n'è una ottima: la funzione L nella regione delle soluzioni ammissibili è illimitata dal basso.

Faremo conoscenza con esempi di tali caratteristiche dell'OZLP in futuro.

Consideriamo, anzitutto, la questione dell'esistenza di soluzioni ammissibili alla LPLP.

Quando si risolve questa domanda, possiamo escludere dalla considerazione la funzione lineare L, che deve essere minimizzata: la presenza di soluzioni ammissibili è determinata solo dalle equazioni (2.1).

Quindi, sia un sistema di equazioni (2.1). Esistono valori non negativi che soddisfano questo sistema? Questa domanda è considerata in una sezione speciale della matematica: l'algebra lineare.

Facciamo un breve riassunto di alcuni enunciati di algebra lineare, senza soffermarci sulle dimostrazioni dei corrispondenti teoremi

La matrice del sistema di equazioni lineari

si chiama tabella composta da coefficienti at

La matrice estesa di un sistema di equazioni lineari è la stessa matrice, integrata da una colonna di termini liberi:

Il rango di una matrice è il massimo ordine di un determinante diverso da zero che si può ottenere cancellando alcune righe e alcune colonne dalla matrice.

In algebra lineare si dimostra che perché il sistema di equazioni lineari (2.1) sia compatibile è necessario e sufficiente che il rango della matrice del sistema sia uguale al rango della sua matrice estesa.

Esempio 1. Viene fornito un sistema di tre equazioni con quattro incognite:

Determinare se il sistema è collaborativo?

Soluzione. Matrice di sistema:

Matrice estesa:

Determiniamo il rango della prima matrice. Non può essere più di 3 (poiché il numero di righe è 3). Componiamo un determinante eliminando alcune colonne dalla matrice, ad esempio l'ultima. Noi abbiamo

Calcolando questo determinante secondo la ben nota regola, si ottiene:

Tale determinante non è uguale a zero, il che significa che il rango della matrice del sistema è 3. Ovviamente anche il rango della matrice estesa è uguale a 3, poiché lo stesso determinante può essere ricavato dagli elementi della matrice estesa. Dall'uguaglianza dei ranghi delle matrici segue che il sistema di equazioni è consistente.

Esempio 2. Indagare la compatibilità di un sistema di due equazioni con tre incognite:

Soluzione. Matrice di sistema estesa:

(il suo lato sinistro è la matrice del sistema).

Troviamo il rango della matrice del sistema componendo tutti i possibili determinanti del secondo ordine:

Quindi, tutti i possibili determinanti del secondo ordine, composti dagli elementi della matrice del sistema, sono uguali a zero; quindi, il rango di questa matrice del sistema

Trova il rango della matrice estesa. determinante

Quindi, il rango della matrice estesa non è uguale al rango della matrice del sistema: Грфг, quindi, il sistema di equazioni è incoerente.

Esempio 3. Per indagare la consistenza del sistema di tre equazioni con quattro incognite:

Soluzione Matrice di sistema estesa (insieme alla matrice di sistema):

Troviamo il rango della matrice del sistema. Prendi un determinante di terzo ordine composto dai suoi elementi, ad esempio:

È noto che se una riga del determinante è una combinazione lineare di due delle sue altre righe, allora il determinante è uguale a zero. Nel nostro caso la terza riga è una combinazione lineare delle prime due: per ottenerla è sufficiente sommare la prima riga con la seconda raddoppiata.

È facile verificare che ogni determinante del terzo ordine composto dagli elementi della matrice di sistema ha la stessa proprietà, di conseguenza il rango della matrice di sistema.

Poiché esiste un determinante diverso da zero del secondo ordine, ad esempio,

allora il rango della matrice del sistema è

Utilizzando lo stesso ragionamento, ci assicureremo che il rango della matrice estesa sia uguale a due: di conseguenza, il sistema di equazioni è coerente

Nota che le tre equazioni questo esempio non sono indipendenti: la terza si ottiene dalle prime due moltiplicando la seconda per due e sommando alla prima. Quindi, la terza equazione è una semplice conseguenza delle prime due. Ci sono solo due equazioni indipendenti nel sistema: questo si riflette nel fatto che il rango della matrice del sistema

Quindi, se il sistema di equazioni-vincoli del LPLP è consistente, allora la matrice del sistema e la sua matrice estesa hanno lo stesso rango.

Questo rango complessivo è chiamato rango del sistema; non è altro che il numero di equazioni linearmente indipendenti tra i vincoli imposti.

Ovviamente, il rango del sistema non può essere maggiore del numero di equazioni:

È anche ovvio che il rango del sistema non può essere maggiore del numero totale di variabili:

Infatti, il rango della matrice del sistema è definito come l'ordine più grande del determinante composto dagli elementi della matrice; poiché il numero delle sue linee è uguale, allora; poiché il numero delle sue colonne è uguale, allora.

La struttura del problema di programmazione lineare dipende essenzialmente dal rango del sistema di vincoli (2.1).

Consideriamo innanzitutto il caso in cui, cioè, quando il numero di equazioni linearmente indipendenti comprese nel sistema (2.1) è uguale al numero di variabili n. Scartiamo le equazioni "non necessarie" che sono combinazioni lineari di altre. Il sistema di equazioni-vincoli della LPLP assume la forma:

Poiché il determinante, composto da coefficienti,

non è zero. È noto dall'algebra che in questo caso il sistema (2.4) ha un'unica soluzione. Per trovare il valore è sufficiente sostituire la colonna del determinante con la colonna dei membri liberi e dividere per.

Quindi, per il sistema di equazioni-vincoli, il LPLP ha un'unica soluzione:

Se in questa soluzione almeno una delle quantità è negativa, significa che la soluzione ottenuta è inaccettabile e, quindi, lo ZZLP non ha soluzione.

Se tutte le quantità sono non negative, la soluzione trovata è ammissibile. È, ovviamente, anche ottimale (perché non ce ne sono altri).

Ovviamente questo banale caso non può interessarci.

Pertanto, nel seguito considereremo solo il caso in cui, cioè quando il numero di equazioni indipendenti che devono essere soddisfatte dai numeri variabili delle variabili stesse. Se poi il sistema è compatibile, ha innumerevoli soluzioni. In questo caso, possiamo assegnare valori arbitrari alle variabili (le cosiddette variabili libere), e il resto delle variabili sarà espresso attraverso di esse (chiameremo queste variabili di base).

I programmi lineari sono programmi costituiti da semplici comandi (operatori).
I comandi semplici (semplici istruzioni dell'algoritmo) sono chiamati comandi che non utilizzano condizioni nella loro esecuzione. Gli operatori semplici includono comandi di assegnazione, input e output (operatori), chiamando un algoritmo ausiliario (subroutine).

Operatore di assegnazione. Imposta o modifica il valore corrente di alcune variabili. Questo cambia il contenuto di uno specifico elemento di memoria allocato per questa variabile. Poiché l'obiettivo di qualsiasi algoritmo è raggiungere una posizione di memoria specifica valore desiderato, quasi tutti i programmi contengono questo operatore. Operatori I/O. Le procedure standard di inserimento dati vengono utilizzate per determinare i valori iniziali di alcune variabili e sono costituite da un nome di procedura e da una lista di input contenente i nomi delle variabili i cui valori verranno inseriti da tastiera o da file, ad es. alle variabili verranno assegnati dei valori specifici.
Più spesso, è più conveniente utilizzare il comando di input per determinare i valori iniziali, piuttosto che il comando di assegnazione, perché se è necessario utilizzare il programma con altri dati di origine, non è necessario modificare il testo del programma.
Se è presente un comando di input nel record dell'algoritmo, la sua esecuzione viene interrotta e il controllo viene trasferito al programma che può eseguire l'immissione dei dati. Dopo aver inserito i dati, il controllo viene trasferito al comando successivo dell'algoritmo.
In Pascal, la procedura di inserimento dei dati è:
LEGGI (elenco voci);
READLN (Elenco voci).
Quando vengono eseguite le procedure READ e READLN, il programma entra in uno stato di attesa dell'immissione dei dati. Se nella lista di inserimento sono specificate più variabili, queste possono essere inserite in una riga, separate tra loro da uno spazio, oppure in righe separate (in una colonna), completando l'immissione di ogni valore con il tasto Invio.
La procedura non terminerà fino all'inserimento dei valori per tutte le variabili della lista. Il tipo di valori di input deve corrispondere a quello della variabile corrispondente.
L'istruzione READLN differisce dall'istruzione READ in quanto dopo aver immesso la quantità di dati richiesta, il cursore si sposta sulla riga successiva.
Se i dati vengono immessi dalla tastiera, l'elenco di input è un elenco di variabili, ad es. una sequenza di nomi di variabili separati da virgole. Se l'input proviene da un file, la prima variabile nell'elenco degli input è file, associato al nome del file reale.
Le procedure standard per l'output dei risultati dei calcoli vengono utilizzate per emettere i loro valori su uno schermo, una stampante o un file. In Pascal, le procedure di inferenza sono:
SCRIVI (lista output);
SCRIVI (elenco uscite).
L'elenco degli elementi di output è molto più ampio rispetto alle procedure di input. Può includere:
identificatori di quantità, i cui valori verranno emessi sul dispositivo corrispondente o su un file;
espressioni, il cui valore verrà prima calcolato e poi inviato al dispositivo;
sono diventate quantità (numeriche, caratteri, stringhe).
La differenza tra WRITE e WRITELN è che l'istruzione WRITE inizia nella posizione corrente del cursore sullo schermo del monitor e il cursore rimane sulla stessa riga dopo la fine dell'output. L'istruzione WRITELN stampa i valori dalla posizione corrente, quindi il cursore si sposta sulla riga successiva. È possibile utilizzare l'istruzione WRITELN senza un elenco di output per spostare il cursore su una nuova riga.
Se l'output viene eseguito sullo schermo del monitor, l'elenco di output è un elenco di variabili o una sequenza di nomi di variabili, costanti o espressioni, separati da virgole. Se l'output viene eseguito su un file, la prima variabile nell'elenco di output è una variabile di file associata al nome del file reale.
Nel comando output, dopo l'elemento dell'elenco di output, separato da due punti, è possibile specificare il formato di output, ad es. la larghezza dello schermo su cui saranno posizionati i valori. Quando si visualizzano dati validi, è anche possibile specificare il numero di cifre decimali nella parte frazionaria da visualizzare.
Esempio: scrivere (A: 10: 3, B: 8).
Operatore per chiamare un algoritmo ausiliario. In Pascal vengono implementate routine-procedure e routine-funzioni. La subroutine viene chiamata con il suo nome con i parametri attuali. In questo caso, al posto degli argomenti effettivi, possono esserci valori specifici, nomi di variabili effettive, espressioni e al posto dei risultati, solo nomi di variabili effettive. In questo caso, il numero, i tipi e lo scopo dei parametri formali e effettivi negli elenchi di parametri corrispondenti devono essere gli stessi.

Lavoro di laboratorio n. 1

Argomento: "Programmazione algoritmi lineari... Lavorare con il debugger "

scopo del lavoro

1.1 Padroneggiare la struttura più semplice di un programma C.

1.2 Acquisire competenze nell'organizzazione input-output in linguaggio C.

Supporto tecnico

2.1 Personal computer

2.2 Tastiera.

2.3 Visualizzazione.

2.4 Dispositivo di stampa.

Software

3.1 Sala operatoria Sistema Windows

3.2 Il sistema di programmazione Visual C++ versione 6.0 o Borland C++ versione 3.1 e successive.

Formulazione del problema

Scrivere il programma più semplice con il trattamento dei dati.

5.1 Tema e scopo dell'opera.

5.2 Enunciazione del problema.

5.3 Testo del programma.

5.4 Risultati dell'esecuzione del programma.

5.5 Schemi dell'algoritmo dei programmi.

Informazione Generale

Programma lineare

Se in un programma tutte le istruzioni vengono eseguite in sequenza, una dopo l'altra, tale programma viene chiamato lineare. Si consideri, ad esempio, un programma che calcola il risultato utilizzando una data formula.

Compito 1.1. Calcolo per formula

Scrivi un programma che converta la temperatura in gradi Fahrenheit in gradi Celsius usando la formula:

dove C è la temperatura Celsius e F è la temperatura Fahrenheit.

Prima di scrivere qualsiasi programma, è necessario definire chiaramente cosa deve essere inserito in esso e cosa dovremmo ottenere come risultato.

In questo caso:

Il dato iniziale è un numero reale, che rappresenta la temperatura in gradi Celsius,

Il risultato è un altro numero reale.

Prima di scrivere il programma, apriamo l'ambiente integrato Visual C++:

Start / Programmi / Microsoft Visual Studio / Microsoft Visual C ++ 6.00

1) File > Nuovo...

2) Nella finestra che si apre:

Selezionare il tipo Applicazione console Win32;

Immettere un nome per il progetto nella casella di testo Nome progetto;

Immettere (selezionare con il pulsante ...) il nome della directory in cui si trovano i file di progetto nella casella di testo Posizione, ad esempio G: / ASOIZ /

Fare clic con il pulsante sinistro del mouse sul pulsante OK.

3) si apre la finestra di dialogo Applicazione console Win32 - Passaggio di 1 e in essa:

Seleziona il tipo Un progetto vuoto;

Fare clic sul pulsante Fine.

4) Dopo aver cliccato, apparirà la finestra Nuovo Progetto, nella quale cliccare sul pulsante OK.

1) File > Nuovo .... Questo aprirà la finestra di dialogo Nuovo.

2) Nella scheda File:

Seleziona il tipo di file (in questo caso: File sorgente C++);

Nella casella di testo Nome file, inserisci il nome del file desiderato;

La casella Aggiungi al progetto deve essere abilitata;

Fare clic sul pulsante OK.

Digitiamo il seguente testo di programma:

Consideriamo ogni riga del programma separatamente.

All'inizio del programma viene scritta una direttiva per il preprocessore, secondo la quale il file di intestazione è collegato al codice sorgente del programma ... Questo è il file che contiene le descrizioni degli operatori di I/O cin e cout.

Qualsiasi programma C++ è costituito da funzioni, una delle quali deve avere il nome main, indicando che è da questa funzione che inizia il programma. Dopo le parentesi, il corpo della funzione è scritto tra parentesi graffe (), ad es. quelle istruzioni che si desidera eseguire.

Quando si scrive un programma, qualsiasi modello ha questo aspetto:

#includere<…>

dichiarazione di variabili;

inserimento dei dati iniziali;

calcolo del risultato;

uscita del risultato;

Per memorizzare i dati e i risultati iniziali, è necessario allocare spazio sufficiente in memoria ad accesso casuale... Per questo viene utilizzato l'operatore 2. Nel nostro programma, abbiamo bisogno di memorizzare due valori: temperatura in Celsius e temperatura in Fahrenheit, quindi due variabili sono definite nell'operatore. Uno, per mantenere la temperatura in Fahrenheit, si chiama fahr, l'altro (Celsius) - cels. I nomi delle variabili sono dati dal programmatore, in base al loro scopo. Il nome può essere composto solo da lettere latine, numeri e un carattere di sottolineatura e non deve iniziare con un numero.

Quando si descrive una variabile, è necessario specificarla tipo di. Poiché la temperatura può assumere non solo valori interi, per le variabili viene scelto il tipo reale galleggiante.

Tipi di base:

int (breve, senza segno) - interi,

float (doppio, doppio lungo) - reale

char - carattere

bool - booleano

Affinché l'utente del programma possa sapere in quale momento è necessario inserire i dati dalla tastiera, viene applicata la cosiddetta richiesta di input (operatore 3). Sullo schermo viene visualizzato il valore specificato nell'operatore. cout una riga di caratteri e il cursore si sposta sulla riga successiva. Per passare alla riga successiva, utilizzare fine.

L'istruzione 4 esegue l'input da tastiera

Per questo, viene utilizzato un oggetto standard cin e l'operazione di estrazione (lettura) >>. Se è richiesto più di un valore, viene utilizzata la catena di operazioni >>.

L'istruzione 5 valuta l'espressione scritta a destra di operazioni di assegnazione(indicato dal segno =) e il risultato viene assegnato alla variabile cels, ovvero viene memorizzato nella memoria assegnata a questa variabile. Primo totale la costante 5 sarà divisa per bacio costante 9, quindi il risultato di questa operazione viene moltiplicato per il risultato della sottrazione di 32 dalla variabile fahr.

Per visualizzare il risultato nell'istruzione 6, viene utilizzato l'oggetto cout. Viene visualizzata una catena di cinque elementi. Questa è la linea "Fahrenheit:", il valore della variabile fahr, linea ", in gradi Celsius:", il valore della variabile cels e l'operatore di interruzione di riga fine

L'ultima affermazione (affermazione 7) di questo programma ha lo scopo di tornare da esso e trasferire il valore all'ambiente esterno.

Successivamente, compiliamo il programma. Per fare ciò, premi il pulsante sulla barra degli strumenti o la combinazione di tasti Ctrl + F7. La finestra di output (nella parte inferiore dello schermo) dovrebbe visualizzare il messaggio 0 errore (s), 0 avviso (s) (0 errori, 0 avvisi). Se ci sono errori, controlla con l'originale.

Per avviare il programma, premere il pulsante sulla barra degli strumenti o la combinazione di tasti Ctrl + F5.

All'avvio del programma, invece dei caratteri russi, vediamo ???, che è causato da standard diversi per la codifica dei caratteri cirillici in sistemi operativi MS-DOS e Windows. Per risolvere il problema, aggiungi la funzione CharToOem al programma (le aggiunte sono evidenziate in rosso per chiarezza)

#includere

char * RUS (const char * testo)

CharToOem (testo, buf);

galleggiante fahr, cels;

cout<

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

cout<

Funzione Russia () non può essere utilizzato più di una volta in una catena di operazioni<< для одного объекта cout quindi lo dividiamo in due.

Come puoi vedere, il risultato dell'esecuzione del programma con stabilità è zero! Ciò è dovuto al modo in cui viene valutata l'espressione. Torniamo all'operatore 4. Le costanti 5 e 9 sono di tipo intero, quindi anche il risultato della loro divisione è intero. Naturalmente, il risultato di ulteriori calcoli non può essere altro che zero. È facile correggere questo errore: è sufficiente scrivere almeno una delle costanti come numero reale, ad esempio:

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