Vista generale del modello di programmazione lineare. Forme dei modelli matematici lineari e loro trasformazione. Formulazione delle principali tipologie di problemi di LP, costruzione dei loro modelli matematici

AGENZIA FEDERALE PER L'EDUCAZIONE

FGOU PO "PSKOV COLLEGIO DI COSTRUZIONE ED ECONOMIA"

Oggetto "Metodi matematici"

Compito programmazione lineare

Lavoro del corso

Gruppo di studenti 315-PO

Andreev Dmitry Alexandrovich

Supervisore dei corsi

Vasilyeva Natalia Anatolyevna

Pskov 2009

introduzione

Capitolo Programmazione lineare

§ 1 Formulazione generale del problema di programmazione lineare

§ 2 Modello matematico del problema di programmazione lineare

§ 3 Forma canonica del problema di programmazione lineare

Capitolo Risoluzione di un problema utilizzando il metodo Simplex

§ 1 Dichiarazione del problema

§ 2 Compilazione di un modello matematico del problema

§ 3 Algoritmi per la risoluzione del problema con il metodo del simplesso

§ 4 Costruzione della soluzione del supporto iniziale con il metodo di Gauss

§ 5 Soluzione del problema

Conclusione

Letteratura

introduzione

Attualmente, molti problemi di pianificazione e gestione in settori dell'economia nazionale, così come un gran volume di problemi applicativi particolari, sono risolti con metodi di programmazione matematica. I più sviluppati nel campo della risoluzione dei problemi di ottimizzazione sono i metodi di programmazione lineare. Questi metodi consentono di descrivere con sufficiente accuratezza un'ampia gamma di compiti delle attività commerciali, come la pianificazione del fatturato; posizionamento della rete commerciale al dettaglio della città; pianificazione della fornitura di beni alla città, distretto; collegare le imprese commerciali ai fornitori; organizzazione del trasporto razionale delle merci; distribuzione degli operai commerciali alle posizioni; organizzazione dell'approvvigionamento razionale dei prodotti alimentari; assegnazione delle risorse; pianificazione degli investimenti; ottimizzazione delle relazioni intersettoriali; sostituzione di attrezzature commerciali; determinazione dell'assortimento ottimale di merci in un'area limitata; definizione di una modalità operativa razionale.

Nei problemi di programmazione lineare, il criterio di efficienza e le funzioni nel sistema di vincoli sono lineari.

Se c'è una variabile temporale in un problema di programmazione matematica e il criterio di efficienza è espresso attraverso equazioni che descrivono il flusso delle operazioni nel tempo, allora tale problema è un problema di programmazione dinamica.

In molti modelli economici, la relazione tra fattori costanti e variabili può essere considerata lineare.

L'uso di metodi di programmazione matematica nelle attività commerciali è associato alla raccolta delle informazioni necessarie da parte di un commerciante, economista, finanziere, ponendo poi un problema insieme alla matematica. Poiché i metodi di programmazione matematica sono già stati implementati su un computer sotto forma di un pacchetto di programmi standard, l'accesso ad essi è solitamente semplice, automatizzato e non presenta particolari difficoltà.

Quindi il funzionamento del modello include la raccolta e l'elaborazione delle informazioni, l'inserimento delle informazioni elaborate in un computer, i calcoli basati sui programmi di pianificazione sviluppati e, infine, l'emissione dei risultati dei calcoli (in una forma conveniente per gli utenti) per il loro impiego nel campo delle attività produttive.

Capitolo Programmazione lineare

§ 1 Formulazione generale del problema di programmazione lineare

La programmazione lineare è una branca della programmazione matematica che studia metodi per risolvere problemi estremi, caratterizzati da una relazione lineare tra variabili e una funzione obiettivo lineare. Per risolvere problemi di programmazione lineare, viene elaborato un modello matematico del problema e viene selezionato un metodo di soluzione.

La formulazione del problema dell'attività commerciale può essere presentata sotto forma di un modello matematico di programmazione lineare, se la funzione obiettivo può essere presentata sotto forma di una forma lineare, e la relazione con risorse limitate può essere descritta mediante equazioni o disuguaglianze. Inoltre, viene introdotta un'ulteriore restrizione: i valori delle variabili devono essere non negativi, poiché rappresentano quantità come fatturato, tempo operativo, costi e altri indicatori economici.

L'interpretazione geometrica dei problemi economici consente di visualizzare la loro struttura, identificare caratteristiche e aprire modi per studiare proprietà più complesse. Un problema di programmazione lineare con due variabili può sempre essere risolto graficamente. Tuttavia, già nello spazio tridimensionale, tale soluzione diventa più complicata, e negli spazi la cui dimensione è maggiore di tre, una soluzione grafica, in generale, è impossibile. Il caso di due variabili non è di particolare importanza pratica, ma la sua considerazione chiarisce le proprietà dei problemi di programmazione lineare, porta all'idea della sua soluzione, rende geometricamente chiare le modalità di risoluzione e le modalità della loro attuazione pratica.

§ 2 Modello matematico del problema di programmazione lineare

Prima di risolvere il problema, componiamo il suo modello matematico.

Un modello matematico è un insieme di relazioni costituito da una funzione obiettivo lineare e vincoli lineari su una variabile.

Il principio della compilazione di un modello matematico.

1. Selezionare le variabili dell'attività.

Le variabili del problema sono le quantità

Che caratterizzano pienamente il processo economico descritto nel compito. Solitamente scritto nella forma di un vettore X = () Inoltre )

2. Creare un sistema per limitare il problema.

Il sistema dei vincoli è un insieme di equazioni e disequazioni che sono soddisfatte dalle variabili del problema e che deriva dalle limitate condizioni economiche del problema.

V vista generale il sistema si scrive come

3. Definire la funzione obiettivo.

La funzione obiettivo è una funzione Z (X) che caratterizza la qualità del compito, il cui estremo deve essere trovato. In generale, la funzione obiettivo si scrive Z (X) =

poi. il modello matematico è trovare le variabili del problema

soddisfare il sistema di restrizioni:

e la condizione di non negatività

0 (j =), che fornisce l'estremo della funzione obiettivo Z (Y) =

Qualsiasi insieme di valori di variabili che soddisfi il sistema di vincoli e non negatività condizionale è chiamato soluzione ammissibile a un problema di programmazione lineare.

L'insieme delle soluzioni fattibili costituisce l'area delle soluzioni fattibili al problema (ODS).

Una soluzione ottima è una soluzione ammissibile a un problema in cui la funzione obiettivo raggiunge un estremo.

§ 3 Forma canonica del problema di programmazione lineare

Il modello matematico del problema deve avere una forma canonica.

Se il sistema di vincoli consiste solo di un'equazione e tutte le variabili soddisfano la condizione di non negatività, allora il problema ha una forma canonica.

Se il sistema ha almeno una disuguaglianza o qualsiasi variabile non è limitata dalla condizione di non negatività, allora il problema ha una forma standard. Per portare l'attività alla forma canonica, è necessario:

passare dalle disequazioni ad un'equazione come segue: a sinistra delle disequazioni introduciamo una variabile aggiuntiva con il coefficiente (+1) per la diseguaglianza (

) e (-1) per la disuguaglianza () le variabili aggiuntive non sono imposte non negative target, quindi viene sostituita dalla differenza di due variabili non negative, ovvero: = - (

Vista generale della forma canonica:

Capitolo Risoluzione di un problema utilizzando il metodo Simplex

Il metodo del simplesso è un metodo di miglioramento sequenziale del piano (soluzione), il più efficace e viene utilizzato per risolvere qualsiasi problema di programmazione lineare.

Il nome del metodo deriva dal latino simplecx - semplice perché dalla regione iniziale delle soluzioni ammissibili del problema aveva vista più semplice... Le idee del metodo sono state proposte dal matematico russo L.V. Kontarovich. nel 1939 e poi questa idea è stata sviluppata e sviluppata da J. Danzig nel 1949.

Il metodo del simplesso permette, in un numero finito di passaggi, di trovare la soluzione ottima o di dimostrare che non esiste.

§ 1 Dichiarazione del problema

L'azienda utilizza 3 tipi di macchine nel processo produttivo: Ι, ІΙ, ІVІ. In questo caso, vengono consumate materie prime, risorse di lavoro e vengono presi in considerazione i costi generali.

Qualsiasi problema di programmazione lineare può essere ridotto a un problema di programmazione lineare in forma canonica. Per fare ciò, nel caso generale, è necessario essere in grado di ridurre il problema della massimizzazione al problema della minimizzazione; passare dai vincoli di disuguaglianza ai vincoli di uguaglianza e sostituire le variabili che non obbediscono alla condizione di non negatività. La massimizzazione di una funzione equivale alla minimizzazione della stessa funzione, presa con il segno opposto, e viceversa.

La regola per ridurre un problema di programmazione lineare alla forma canonica è la seguente:

• se nel problema originale è necessario determinare il massimo funzione lineare, allora dovresti cambiare segno e cercare il minimo di questa funzione;
• se il lato destro dei vincoli è negativo, allora questo vincolo deve essere moltiplicato per -1;
• se ci sono disuguaglianze tra i vincoli, allora introducendo ulteriori variabili non negative si trasformano in uguaglianze;
• se qualche variabile x j non ha restrizioni di segno, allora viene sostituita (nella funzione obiettivo e in tutte le restrizioni) dalla differenza tra due nuove variabili non negative:
  x 3 = x 3 + - x 3 - , dove x 3 +, x 3 - ≥ 0 .

Esempio 1... Riducendo il problema di programmazione lineare alla forma canonica:

minimo L = 2x 1 + x 2 - x 3;
2x 2 - x 3 ≤ 5;
x 1 + x 2 - x 3 ≥ -1;
2x 1 - x 2 ≤ -3;
x 1 ≤ 0; x2 ≥ 0; x 3 ≥ 0.

Introduciamo in ogni equazione del sistema di vincoli le variabili di livellamento x 4, x 5, x 6... Il sistema sarà scritto sotto forma di uguaglianze, e nella prima e nella terza equazione del sistema di restrizioni le variabili x 4, x 6 si inseriscono a sinistra con il segno "+" e nella seconda equazione la variabile x 5 inserito con un segno "-".

2x 2 - x 3 + x 4 = 5;
x 1 + x 2 - x 3 - x 5 = -1;
2x 1 - x 2 + x 6 = -3;
x4 ≥ 0; x5 ≥ 0; x 6 ≥ 0.

I termini liberi in forma canonica devono essere positivi, per questo moltiplichiamo le ultime due equazioni per -1:

2x 2 - x 3 + x 4 = 5;
-x 1 - x 2 + x 3 + x 5 = 1;
-2x 1 + x 2 - x 6 = 3.

Nella forma canonica di scrittura di problemi di programmazione lineare, tutte le variabili incluse nel sistema di vincoli devono essere negative. Supponiamo che x 1 = x 1 '- x 7 , dove x 1 '' ≥ 0, x 7 ≥ 0 .

Sostituendo questa espressione nel sistema di vincoli e nella funzione obiettivo e scrivendo le variabili in ordine crescente dell'indice, si ottiene un problema di programmazione lineare presentato nella forma canonica:

L min = 2x 1 '+ x 2 - x 3 - 2x 7;
2x2 - x3 + x4 = 5;
-x 1 '- x 2 + x 3 + x 5 + x 7 = 1;
-2x 1 '+ x 2 - x 6 + 2x 7 = 3;
x 1' ≥ 0; x i ≥ 0, i = 2, 3, 4, 5, 6, 7.

Condizione di ottimalità per il piano di base del problema canonico di LP. Metodo del simplesso e sua convergenza.

Il metodo del simplesso è universale, poiché consente di risolvere quasi tutti i problemi di programmazione lineare scritti in forma canonica.

L'idea del metodo simplex miglioramento costante del piano, sta nel fatto che, partendo da una prima soluzione di supporto, movimento coerentemente diretto dalle soluzioni di supporto del problema a quella ottimale.

Il valore della funzione obiettivo non diminuisce con questo movimento per compiti al massimo.

Poiché il numero di soluzioni di supporto è finito, dopo un numero finito di passaggi si ottiene la soluzione di supporto ottimale.

Una soluzione di base non negativa è detta soluzione di riferimento.

Algoritmo metodo simplex

1. Il modello matematico del problema dovrebbe essere canonico. Se è non canonico, allora deve essere portato alla forma canonica.

2. Trovare la soluzione di supporto originale e verificarne l'ottimalità.
Per fare ciò, compila la tabella simplex 1.
Compiliamo tutte le righe della tabella del 1° passo in base ai dati del sistema di restrizioni e della funzione obiettivo.

I seguenti casi sono possibili quando si risolvono problemi su massimo:

1. Se tutti i coefficienti dell'ultima riga della tabella del simplesso Dj 0, poi trovato

soluzione ottimale.

2 Se almeno un coefficiente Dj £ 0, ma per la variabile corrispondente non esiste un solo rapporto di valutazione positivo, quindi la soluzione fermiamo i compiti, poiché F (X) ® ¥, cioè, la funzione obiettivo non è limitata nell'area delle soluzioni fattibili.

Se almeno un coefficiente dell'ultima riga è negativo, e per la corrispondente variabile si ha almeno una relazione valutativa positiva, poi devi andare ad un'altra soluzione di riferimento.

E Se ci sono diversi coefficienti negativi nell'ultima riga, quindi alla colonna della variabile di base(Bp) presentalo variabile che corrisponde a il più grande coefficiente negativo in valore assoluto.

5. Se almeno un coefficiente Dk< 0 ,poi k - th colonna accettiamo per l'ospite.

6. Per linea guida accettiamo quello che corrisponde a minimo atteggiamento da membro libero bi a coefficienti positivi leader, k - che colonna.

7. Viene chiamato un elemento situato all'intersezione delle righe iniziali e di una colonna elemento principale.

Popolazione della tabella simplex 2 :

· riempi la colonna di base con zero e uno

· riscrivi la linea principale dividendola per l'elemento principale

Se la riga principale ha zeri, le colonne corrispondenti possono essere trasferite alla successiva tabella simplex

· il resto dei coefficienti si trova con la regola del "rettangolo"

Otteniamo una nuova soluzione di supporto, che controlliamo per l'ottimalità:

Se tutti i coefficienti dell'ultima riga Dj 0, quindi la soluzione trovata massimo.

In caso contrario, compilare l'ottavo passaggio della tabella simplex e così via.

Se la funzione obiettivo F (X) richiede la ricerca valore minimo, allora il criterio ottimalità del problemaè un probabilità non positive D j per ogni j = 1,2,… n.

Convergenza del metodo del simplesso. Degenerazione nei problemi di LP. La proprietà più importante di qualsiasi algoritmo di calcolo è la convergenza, cioè la possibilità di ottenere i risultati desiderati (con una data accuratezza) durante la sua applicazione in un numero finito di passi (iterazioni).

È facile vedere che i problemi con la convergenza del metodo del simplesso possono potenzialmente sorgere nella fase di scelta del valore di r (elemento 2 ") nel caso in cui gli stessi valori minimi del rapporto

verrà raggiunto per più righe della tabella T (q) contemporaneamente. Quindi, all'iterazione successiva, la colonna b (β (q + 1)) conterrà zero elementi.

⇐ Precedente12345Successivo ⇒

Data di pubblicazione: 2015-11-01; Leggi: 4190 | Violazione del copyright della pagina

Studopedia.org - Studopedia.Org - 2014-2018 (0,002 s) ...

Soluzione ottimale - problema - programmazione lineare

Pagina 1

La soluzione ottima del problema di programmazione lineare si ottiene in uno dei punti di riferimento, dove almeno k p, - m variabili sono uguali a zero.

Utilizzando la soluzione ottima del problema di programmazione lineare, è possibile trovare le variazioni ammissibili nel DS, per le quali anche L rimane costante.

Se c'è una soluzione ottima per un problema di programmazione lineare, allora c'è una soluzione ottima di base.

È dimostrato che la soluzione ottimale al problema di programmazione lineare si trova sul confine della regione dei valori ammissibili delle variabili controllate, che è un poliedro nello spazio n-dimensionale ed è determinato da un sistema di vincoli lineari.

Poiché z è una soluzione ottima a un problema di programmazione lineare con m vincoli, questa soluzione contiene al massimo m variabili strettamente positive.

Si dimostra che la soluzione ottima del problema di programmazione lineare è sul confine della regione dei valori ammissibili delle variabili controllate, che è un poliedro nello spazio n-dimensionale definito da un sistema di vincoli lineari. Le coordinate di ogni vertice sono determinate risolvendo un sistema di equazioni (vincoli), e in presenza di n variabili controllate e m vincoli, è necessario risolvere il sistema di m equazioni. La combinazione Cm n (m - n cresce molto velocemente con il tipo crescente, quindi la ricerca di una soluzione richiede un numero molto elevato di calcoli inaccessibili anche per un computer.

Quindi, nel caso D 1, la soluzione ottima del problema di programmazione lineare risulta essere automaticamente intera.

Come mostrato nella Parte 1, la soluzione ottima di un problema di programmazione lineare non è necessariamente integrale, e allo stesso tempo ci sono molti problemi la cui natura richiede una soluzione integrale. Alcuni di questi problemi a prima vista non sono problemi di programmazione intera, ma possono essere formulati come tali.

Ovviamente, non tutte le soluzioni di base sono una soluzione ottima per un problema di programmazione lineare. Tuttavia, la soluzione ottima di un problema non degenere deve essere sempre fondamentale per il sistema di equazioni (VIII, 42), e, quindi, il problema di trovare la soluzione ottima consiste nell'enumerare solo le soluzioni di base del sistema di equazioni ( VIII, 42), tra cui si trova l'ottimo.

Ovviamente, non tutte le soluzioni di base sono una soluzione ottima per un problema di programmazione lineare. Tuttavia, la soluzione ottima di un problema non degenere deve essere sempre fondamentale per il sistema di equazioni (VIII42) e, quindi, il problema di trovare la soluzione ottima consiste nell'enumerare solo le soluzioni di base del sistema di equazioni (VIII42), tra cui si trova quella ottimale.

Dopo aver eseguito diverse iterazioni nel passaggio 3, possono apparire numerose soluzioni ottimali alternative al problema della programmazione lineare.

PROBLEMA DI PROGRAMMAZIONE LINEARE

Questo ciclo è talvolta chiamato degenerazione continua. Sfortunatamente, questo fenomeno si verifica spesso in problemi di PI medi di grandi dimensioni. Ci sono anche molti esempi di problemi a bassa dimensionalità (non più di 10 variabili ed equazioni) che richiedono migliaia di iterazioni per raggiungere la convergenza.

In questi casi viene utilizzato il metodo del simplesso, che è una procedura iterativa (passo-passo) per determinare la soluzione ottima di un problema di programmazione lineare. I calcoli che utilizzano il metodo del simplesso iniziano con la determinazione di una soluzione fattibile, quindi trovano altre soluzioni possibili e verificano le possibilità per il loro miglioramento. Il passaggio da una soluzione all'altra continua fino a quando non sono possibili nuovi miglioramenti. Standard programmi per computer che utilizzano il metodo del simplesso per risolvere problemi di gestione che possono essere rappresentati come problemi di programmazione lineare.

Se il sistema di vincoli lineari ha una struttura speciale, ad esempio, se forma un modello di rete, al passaggio 2, quando si trova la soluzione ottimale al problema di programmazione lineare, è possibile utilizzare questa circostanza.

L'idea della distribuzione proporzionale è stata implementata sotto forma di un algoritmo di calcolo a due stadi proposto da II Dikin, in cui la proprietà del metodo del punto interno è essenzialmente utilizzata per generare un punto relativamente interno dell'insieme delle soluzioni ottimali a un problema di programmazione lineare. Questa proprietà significa che i valori limite in base alle condizioni di disuguaglianza (2.3.2) - (2.3.4) sono raggiunti solo per quelle variabili che hanno questi valori limite per qualsiasi altra soluzione ottimale.

Pagine: 1 2

Un metodo grafico per risolvere un problema di programmazione lineare

Si consideri la LPP in forma standard per il caso di due variabili:

(10)

Lascia che il sistema di disequazioni (10) sia consistente (ha almeno una soluzione). Qualsiasi disuguaglianza di questo sistema definisce geometricamente un semipiano con una linea di confine Le condizioni di non negatività definiscono semipiani con corrispondenti linee di confine e.

Poiché il sistema è consistente, i semipiani, in quanto insiemi convessi, intersecantisi, formano una parte comune, che è un insieme convesso ed è un insieme di punti, le cui coordinate di ciascuno dei quali sono una soluzione a questo sistema. La raccolta di tutti questi punti si chiama soluzioni poligonali. Può essere un punto, un segmento di linea, una semiretta, una retta, un poligono chiuso, un'area poligonale illimitata.

La soluzione della LPP è geometricamente una ricerca di un tale punto del poligono soluzione, le cui coordinate forniscono il valore più grande (più piccolo) alla funzione obiettivo. Inoltre, tutti i punti del poliedro sono una valida soluzione.

Considera il cosiddetto linea di livello funzione obiettivo z, cioè la retta lungo la quale questa funzione assume lo stesso valore fisso: o

Algoritmo per la risoluzione di un problema di programmazione lineare con un metodo grafico (numero di variabili).

1. Si costruisce una regione poligonale di soluzioni ammissibili sul piano in corrispondenza dei vincoli. Quindi viene costruito il gradiente vettoriale

funzione obiettivo z in ogni punto la regione delle soluzioni ammissibili.

2. Linea retta (linea di livello funzione z), perpendicolare al vettore gradiente, si muove parallelamente a se stesso nella direzione del vettore gradiente nel caso del problema massimo (e in direzione opposta - nel caso del problema minimo) fino a lasciare la regione delle soluzioni ammissibili. Il punto (oi punti) limite della regione sono punti ottimali.

3. Per trovare le coordinate del punto ottimale, è necessario risolvere il sistema di equazioni, che corrisponde alle linee rette, la cui intersezione forma questo punto.

Formulazione delle principali tipologie di problemi di LP, costruzione dei loro modelli matematici

Il valore della funzione obiettivo a questo punto sarà ottimale e le coordinate del punto stesse saranno una soluzione al problema LP .

Esempio. Risolvi il problema geometricamente:

Costruisci il poligono di tutte le soluzioni ammissibili OABCD e il vettore di direzione della funzione obiettivo (Fig. 1). La direzione del vettore gradiente indica la direzione di incremento della funzione obiettivo. Poiché il problema in esame è trovare il massimo, spostiamo la retta perpendicolare al vettore nella direzione di questo vettore parallela a se stessa fino a quando questa retta esce dalla regione delle soluzioni ammissibili. Al confine della regione, nel nostro caso al punto INSIEME A, e ci sarà una soluzione al problema. Punto INSIEME Aè all'intersezione di rette e. Di conseguenza, le sue coordinate sono determinate risolvendo il sistema di queste equazioni nell'equazione:

da dove cioè punto INSIEME A ha coordinate (6, 4).

Il massimo (valore massimo della funzione obiettivo) è: Risposta: con una soluzione ottimale, ad es. il massimo profitto si ottiene producendo 6 unità del primo e 4 unità del secondo prodotto.

INTRODUZIONE

La moderna teoria economica, sia a livello micro che a livello macro, include come elemento naturale e necessario modelli matematici e metodi. L'uso della matematica in economia consente, in primo luogo, di evidenziare e descrivere formalmente le relazioni più importanti e significative tra variabili economiche e oggetti: lo studio di un oggetto così complesso richiede un alto grado di astrazione. In secondo luogo, da dati e relazioni iniziali chiaramente formulati, i metodi deduttivi possono essere utilizzati per ottenere conclusioni adeguate all'oggetto in esame nella stessa misura delle precondizioni fatte. In terzo luogo, i metodi della matematica e della statistica consentono di ottenere induttivamente nuove conoscenze sull'oggetto: valutare la forma e i parametri delle dipendenze delle sue variabili, che sono più coerenti con l'osservazione disponibile. Infine, in quarto luogo, l'uso del linguaggio della matematica consente di presentare in modo accurato e compatto le disposizioni della teoria economica, formularne i concetti e le conclusioni.

I modelli matematici utilizzati in economia possono essere suddivisi in classi secondo una serie di caratteristiche legate alle caratteristiche dell'oggetto simulato, allo scopo della modellazione e agli strumenti utilizzati: modelli micro e macroeconomici, teorici e di equilibrio, statistici e dinamici.

L'essenza dei metodi di ottimizzazione sta nel fatto che, in base alla disponibilità di determinate risorse, viene scelto un metodo di utilizzo (distribuzione), che garantisce il massimo (minimo) dell'indicatore di nostro interesse.

Tutte le sezioni principali della programmazione matematica (pianificazione) sono utilizzate come metodi di ottimizzazione in economia.

La disciplina matematica che si occupa dello studio dei problemi estremi (massimi o minimi) di controllo, pianificazione e sviluppo di metodi per la loro soluzione è stata denominata programmazione matematica.

In generale, la formulazione matematica del problema estremale consiste nel determinare il valore più grande o più piccolo della funzione obiettivo
a condizione ,

dove e sono date funzioni, e sono alcuni numeri reali.

A seconda del tipo di funzione obiettivo e dei vincoli, la programmazione matematica è divisa in lineare e non lineare. Maggior parte

la sezione studiata della programmazione matematica è la programmazione lineare.

Definizione.

Problema di programmazione lineare (pagina 1 di 3)

Programmazione lineare - la scienza dei metodi di utilizzo e ricerca dei valori estremi (massimo e minimo) di una funzione lineare, alle cui incognite sono imposti vincoli lineari.

Questa funzione lineare è chiamata obiettivo e i vincoli sotto forma di equazioni o disequazioni sono chiamati sistema di vincoli.

Definizione. L'espressione matematica della funzione obiettivo e dei suoi limiti si chiama modello matematico del problema economico.

Consideriamo alcuni problemi di programmazione lineare (LPP).

1. Il problema dell'uso delle risorse (il problema della pianificazione della produzione).

Per la fabbricazione di vari prodotti l'azienda utilizza tre diverse tipologie di materie prime. Tassi di consumo di materie prime per la produzione di un prodotto , così come il numero totale

le materie prime di ogni tipologia utilizzabili dall'impresa sono riportate in tabella.

Elaborare un piano per la produzione di prodotti, in cui il costo totale di tutti i prodotti fabbricati dall'impresa è massimo.

Costruiamo un modello matematico di questo problema.

Indichiamo attraverso l'output desiderato di prodotti, attraverso - prodotti,

attraverso - prodotti.

Poiché ci sono tassi di costo per ogni tipo di materia prima, possiamo trovare il costo totale di ogni tipo di materia prima per la fabbricazione di tutti i prodotti. Dalla tabella risulta che il volume totale delle materie prime di tipo I sarà, II -
,

III -
... E poiché ci sono restrizioni sullo stock di materie prime, quindi, il volume totale di materie prime di ciascun tipo non dovrebbe essere superiore alla quantità totale di materie prime, ad es.

otteniamo il seguente sistema di disuguaglianze

(1)

Economicamente, le variabili può assumere solo valori non negativi:

(2)

Il costo di tutti i prodotti del tipo sarà – – Di conseguenza, il costo totale dei prodotti fabbricati dall'impresa sarà (3)

dobbiamo trovare questa funzione. Quindi, tra tutte le soluzioni non negative del sistema (1), è necessario trovarne una per la quale la funzione (3) assume il suo valore massimo.

Questo compito può essere facilmente generalizzato al caso del rilascio di tipologie di prodotti utilizzando tipologie di materie prime (risorse).

Indichiamo con - il numero di unità di prodotti previste per la produzione, - stock di risorse - tipo, - consumo specifico di risorse per la produzione - prodotti th. - profitto dalla vendita di una unità del prodotto - il primo tipo.

Quindi il modello economico - matematico del problema dell'uso delle risorse in ambito generale prenderà la forma: trova un tale piano
output che soddisfa il sistema di restrizioni di base

ulteriore sistema di restrizioni

in cui la funzione obiettivo è

assume il valore massimo.

Commento. Per redigere un modello matematico della LPP è necessario:

- inserire la designazione delle variabili;

- sulla base dell'obiettivo della ricerca economica, elaborare una funzione target;

- tenendo conto delle limitazioni nell'uso degli indicatori economici del problema e delle loro leggi quantitative, scrivere il sistema delle limitazioni.

La risoluzione di problemi di programmazione lineare si basa sui concetti della geometria analitica nello spazio vettoriale in-dimensionale.

Portare la LPP generale alla forma canonica.

La visione generale del LPP è la seguente:

(1)

(2)

(3)

dove la relazione (1) è una funzione obiettivo, (2) è un sistema di vincoli di base, (3) è un sistema di vincoli aggiuntivi.

Relazioni (2) e (3) forma sistema completo restrizioni.

La riduzione del sistema dei vincoli di base alla forma canonica si effettua introducendo ulteriori variabili non negative con coefficienti "+1", se le disequazioni sono della forma, e "-1", se le disequazioni sono della forma , a sinistra delle disuguaglianze. Ulteriori variabili entrano nella funzione obiettivo con coefficienti nulli.

Definizione ... Una LPP è detta canonicamente definita se il suo sistema di vincoli di base è rappresentato da equazioni.

Definizione. LPP è chiamato dato nella forma standard della forma canonica se sono soddisfatte le seguenti condizioni:

1) il sistema dei vincoli di base è rappresentato da equazioni e sono tutte linearmente indipendenti;

2) il numero di equazioni è inferiore al numero di variabili;

3) si sta risolvendo il problema della minimizzazione della funzione obiettivo;

4) i membri destri del sistema dei vincoli di base sono non negativi;

5) tutte le variabili sono anche non negative.

Nella maggior parte dei metodi per risolvere problemi di programmazione lineare, si assume che il sistema di vincoli sia costituito da equazioni e condizioni naturali per la non negatività delle variabili.

Tuttavia, quando si compilano modelli di molti problemi, i vincoli si formano principalmente sotto forma di un sistema di disequazioni, quindi è necessario poter passare da un sistema di disuguaglianze a un sistema di equazioni.

Questo può essere fatto come segue:

Prendi la disuguaglianza lineare

e aggiungi alla sua sinistra una quantità tale che la disuguaglianza si trasformi in uguaglianza

Inoltre, questo valore non è negativo.

Esempio

Portare il problema di programmazione lineare alla forma canonica:

Soluzione:

Passiamo al problema di trovare il massimo della funzione obiettivo.

Per fare ciò, cambiamo i segni dei coefficienti della funzione obiettivo.

Per trasformare la seconda e la terza diseguaglianza del sistema di vincoli in equazioni, introduciamo variabili aggiuntive non negative x 4 x 5 (sul modello matematico questa operazione è contrassegnata dalla lettera D).

La variabile x 4 viene introdotta a sinistra della seconda disuguaglianza con il segno "+", poiché la disuguaglianza ha la forma "≤".

La variabile x 5 viene introdotta a sinistra della terza disuguaglianza con il segno "-", poiché la disuguaglianza ha la forma "≥".

Le variabili x 4 x 5 vengono inserite nella funzione obiettivo con un coefficiente. uguale a zero.

Scriviamo il compito nella forma canonica:

METODO SIMPLEX PER RISOLVERE PROBLEMI DI PROGRAMMAZIONE LINEARE

Questo metodo è un metodo di enumerazione mirata delle soluzioni di supporto di un problema di programmazione lineare. Consente, in un numero finito di passaggi, di trovare la soluzione ottima o di stabilire che non esiste una soluzione ottima.

Algoritmo del metodo del simplesso per la risoluzione di problemi di programmazione lineare

Per risolvere il problema utilizzando il metodo simplex, è necessario eseguire le seguenti operazioni:

1. Portare il problema alla forma canonica

Argomento 8. Programmazione lineare

Trova la soluzione di supporto iniziale con una "base unitaria" (se non esiste una soluzione di supporto, il problema non ha soluzione a causa dell'incompatibilità del sistema di vincoli)

3. Calcolare le stime delle espansioni vettoriali in base alla soluzione del supporto e compilare la tabella del metodo del simplesso

4. Se il criterio di unicità della soluzione ottima è soddisfatto, allora la soluzione del problema termina

5. Se la condizione per l'esistenza di un insieme di soluzioni ottimali è soddisfatta, allora con una semplice enumerazione si trovano tutte le soluzioni ottimali

Un esempio di risoluzione di un problema utilizzando il metodo del simplesso

Esempio 1

Risolvi il problema usando il metodo del simplesso:

Riduci valore funzione

F = 10 × 1 - 4 × 3 massimo

In presenza di vincoli sotto forma di disuguaglianze

Portiamo il problema in forma canonica.

Per fare ciò, a sinistra del primo vincolo di disuguaglianza, introduciamo una variabile aggiuntiva x 5 con un coefficiente di +1. La variabile x 5 è inclusa nella funzione obiettivo con coefficiente zero (cioè non è inclusa).

Noi abbiamo:

F = 10 × 1 - 4 × 3 + 0 ∙ x5 max

In presenza di vincoli sotto forma di disuguaglianze

Trova la soluzione di supporto iniziale. Per questo, le variabili libere (non risolte) sono equiparate a zero x1 = x3 = 0.

Otteniamo la soluzione di riferimento X1 = (0,0,0,5,9 / 15,6) con base unitaria B1 = (A4, A5, A6).

Calcoliamo le stime delle espansioni dei vettori di condizioni in base alla soluzione di supporto mediante la formula:

Δ k = C b X k - c k

C b = (s 1, s 2, ..., s m) è il vettore dei coefficienti della funzione obiettivo per le variabili di base

X k = (x 1k, x 2k, ..., x mk) è il vettore di espansione del corrispondente vettore A alla base della soluzione di riferimento

· С ê - coefficiente della funzione obiettivo alla variabile х ê.

Le stime dei vettori inclusi nella base sono sempre zero.

La soluzione di supporto, i coefficienti di espansione e le stime delle dilatazioni dei vettori di condizione in base alla soluzione di supporto sono scritti in una tabella simplex:

Sopra la tabella, per comodità di calcolo delle stime, sono scritti i coefficienti della funzione obiettivo. La prima colonna "B" contiene i vettori inclusi nella base della soluzione di riferimento. L'ordine di scrittura di questi vettori corrisponde ai numeri delle incognite consentite nelle equazioni dei vincoli. La seconda colonna della tabella "C b" registra i coefficienti della funzione obiettivo con le variabili di base nello stesso ordine. Con la corretta collocazione dei coefficienti della funzione obiettivo nella colonna "C b", le stime dei versori inclusi nella base sono sempre uguali a zero.

L'ultima riga della tabella con le stime Δ k nella colonna "A 0" registra i valori della funzione obiettivo sulla soluzione di riferimento Z (X 1).

La soluzione del supporto iniziale non è ottimale, poiché nel problema massimo le stime Δ 1 = -2, Δ 3 = -9 per i vettori А 1 e А 3 sono negative.

Secondo il teorema del miglioramento della soluzione di supporto, se nel problema massimo almeno un vettore ha una stima negativa, allora si può trovare una nuova soluzione di supporto, sulla quale il valore della funzione obiettivo sarà maggiore.

Determiniamo quale dei due vettori porterà ad un incremento maggiore della funzione obiettivo.

L'incremento della funzione obiettivo si trova con la formula:

Calcoliamo i valori del parametro θ 01 per la prima e la terza colonna utilizzando la formula:

Otteniamo θ 01 = 6 con l = 1, θ 03 = 3 con l = 1 (tabella 26.1).

Trova l'incremento della funzione obiettivo quando introduci il primo vettore nella base

ΔZ 1 = - 6 * (- 2) = 12,

e il terzo vettore ΔZ 3 = - 3 * (- 9) = 27.

Pertanto, per una più rapida approssimazione alla soluzione ottima, è necessario introdurre il vettore A3 nella base della soluzione di supporto invece del primo vettore della base A6, poiché il minimo del parametro θ 03 viene raggiunto nella prima riga (l = 1).

Eseguiamo la trasformata di Jordan con l'elemento X13 = 2, otteniamo la seconda soluzione di supporto

X2 = (0,0,3,21,42,0)

con base B2 = (A3, A4, A5).

(tabella 26.2)

Questa soluzione non è ottimale, poiché il vettore A2 ha una stima negativa Δ2 = - 6.

Per migliorare la soluzione, è necessario introdurre il vettore A2 nella base della soluzione di supporto.

Determinare il numero del vettore derivato dalla base. Per fare ciò, calcola il parametro θ 02 per la seconda colonna, è uguale a 7 per l = 2.

Pertanto, dalla base deriviamo il secondo vettore di base A4.

Eseguiamo la trasformata di Jordan con l'elemento x 22 = 3, otteniamo la terza soluzione di supporto

X3 = (0.7.10.0.63.0)

B2 = (A3, A2, A5) (tabella 26.3).

Questa soluzione è l'unica ottima, poiché per tutti i vettori non inclusi nella base della stima, positivo

1 = 7/2, 4 = 2, Δ 6 = 7/2.

Risposta: Z massimo (X) = 201 a X = (0.7,10,0.63).

⇐ Precedente123456789Successivo ⇒

In pratica, i vincoli in un problema di programmazione lineare sono spesso specificati non da equazioni, ma da disuguaglianze.

Mostriamo come possiamo passare dal problema dei vincoli di disuguaglianza al problema principale della programmazione lineare.

Sia un problema di programmazione lineare con variabili, in cui i vincoli imposti alle variabili sono sotto forma di disuguaglianze lineari. In alcuni di essi può essere il segno di disuguaglianza, mentre in altri (il secondo tipo è ridotto al primo da un semplice cambiamento nel segno di entrambe le parti). Pertanto, impostiamo tutti i vincoli di disuguaglianza nella forma standard:

È necessario trovare un insieme di valori non negativi che soddisfino le disuguaglianze (4.1) e, inoltre, minimizzino la funzione lineare:

È facile passare dal compito impostato in questo modo al compito principale della programmazione lineare. Introduciamo infatti la notazione:

dove ci sono alcune nuove variabili che chiameremo "addizionali". Secondo le condizioni (4.1), queste variabili aggiuntive, così come dovrebbero essere non negative.

Quindi, ci troviamo di fronte a un problema di programmazione lineare nella seguente formulazione: trovare tali valori non negativi delle variabili in modo che soddisfino il sistema di equazioni (4.3) e contemporaneamente ridurre al minimo la funzione lineare di queste variabili:

Come puoi vedere, abbiamo davanti a noi nella sua forma pura il compito principale della programmazione lineare (LPP). Le equazioni (4.3) sono fornite nella forma già consentita per le variabili di base che sono espresse in termini di variabili libere Il numero totale di variabili è uguale, di cui "iniziale" e "addizionale". La funzione L è espressa solo in termini di variabili "iniziali" (i coefficienti delle variabili "aggiuntive" in essa contenute sono uguali a zero).

Pertanto, abbiamo ridotto il problema della programmazione lineare con vincoli di disuguaglianza al problema principale della programmazione lineare, ma con un numero di variabili maggiore rispetto a quanto originariamente previsto nel problema.

Esempio 1 Esiste un problema di programmazione lineare con vincoli di disuguaglianza: trova valori non negativi delle variabili che soddisfano le condizioni

e minimizzando la funzione lineare

È necessario portare questo compito nella forma di un OZLP.

Soluzione. Riduciamo le disuguaglianze (4.4) alla forma standard;

Introduciamo ulteriori variabili:

Il compito si riduce a trovare i valori non negativi delle variabili

soddisfacendo le equazioni (4.6) e minimizzando la funzione lineare (4.5).

Abbiamo mostrato come possiamo passare da un problema di programmazione lineare con vincoli di disuguaglianza a un problema con vincoli di uguaglianza (LPPP). La transizione inversa è sempre possibile, dalla LPP al problema dei vincoli di disuguaglianza. Se nel primo caso abbiamo aumentato il numero di variabili, nel secondo lo diminuiamo eliminando le variabili base e lasciando libere solo quelle.

Esempio 2. Esiste un problema di programmazione lineare con vincoli di uguaglianza (LPPP):

e la funzione da minimizzare

È necessario scriverlo come un problema di programmazione lineare con vincoli di disuguaglianza.

Soluzione. Da allora, sceglieremo come libere alcune delle due variabili. Si noti che le variabili non possono essere scelte come variabili libere, poiché sono legate dalla prima delle equazioni (4-7): il valore di una di esse è completamente determinato dal valore dell'altra e le variabili libere devono essere indipendenti

Per lo stesso motivo, è impossibile scegliere variabili come libere (sono collegate dalla seconda equazione). Scegliamo come variabili libere ed esprimiamo tutte le altre attraverso di esse:

Poiché le condizioni (4 9) possono essere sostituite da disuguaglianze:

Passiamo l'espressione della funzione lineare L a variabili libere Sostituendo in L invece delle loro espressioni (4.9). noi abbiamo.

MODELLO DI PROGRAMMAZIONE LINEARE

1 Descrizione matematica del modello di programmazione lineare

2 Metodi per l'implementazione di modelli di programmazione lineare

3 Il problema della programmazione lineare duale

Modello di programmazione lineare(LP) si verifica se nel sistema studiato (oggetto) i vincoli sulle variabili e sulla funzione obiettivo lineare.

I modelli LP vengono utilizzati per risolvere due tipi principali di problemi applicati:

1) pianificazione ottimale in qualsiasi sfera dell'attività umana: sociale, economica, scientifica, tecnica e militare. Ad esempio, con una pianificazione ottimale della produzione: distribuzione di risorse finanziarie, di lavoro e di altro tipo, fornitura di materie prime, gestione delle scorte, ecc.

2) il problema dei trasporti (trovare il piano ottimale per vari tipi di trasporto, il piano ottimale per la distribuzione di vari fondi a oggetti per vari scopi, ecc.)

DESCRIZIONE MATEMATICA DEL MODELLO DI PROGRAMMAZIONE LINEARE

È necessario trovare i valori non negativi delle variabili

soddisfare vincoli lineari sotto forma di uguaglianze e diseguaglianze

,

dove - dati numeri,

e fornendo l'estremo della funzione obiettivo lineare

,

dove sono i numeri dati, che si scrive come

Una valida soluzione qualsiasi insieme è chiamato soddisfacimento delle condizioni.

Dominio delle soluzioni fattibili- l'insieme di tutte le soluzioni ammissibili.

Soluzione ottimale
, per cui .

Osservazioni

1. Il modello LP dato è generale... Distinguere anche standard e canonico forme di modelli LP.

2... Condizioni di esistenza Implementazione del modello LP:

- l'insieme delle soluzioni ammissibili non è vuoto;

- funzione obiettivo delimitato su (almeno dall'alto quando si cerca un massimo e dal basso quando si cerca un minimo).

3.LP si basa su due teoremi

Teorema 1. Molti G definito da un sistema di vincoli della forma è un insieme chiuso convesso ( poliedro convesso dentro con punti d'angolo - picchi.)

Teorema 2. forma lineare definito sul politopo convesso

J=1,2,…,S

io = s+ 1, s + 2, ..., m,

raggiunge un estremo in uno dei vertici di questo poliedro.

Questo teorema è chiamato teorema dell'estremo della forma lineare.

Secondo il teorema di Weierstrass, la soluzione ottima è unica ed è un estremo globale.

Esiste un approccio analitico generale all'implementazione del modello LP - il metodo del simplesso. Quando si risolvono problemi di programmazione lineare, molto spesso non c'è soluzione. Ciò accade per i seguenti motivi.

Illustriamo il primo motivo con un esempio

Per questo motivo, dicono che le restrizioni sono incompatibili. La regione delle soluzioni ammissibili è un insieme vuoto.

Il secondo motivo è commentato dal seguente esempio:

In questo caso, la regione delle soluzioni ammissibili non è limitata dall'alto. L'area delle soluzioni ammissibili non è limitata.

Seguendo le tradizioni della programmazione lineare, diamo al problema LP un'interpretazione economica. Che ci sia a nostra disposizione m tipi di risorse. Numero del tipo di risorsa Jè uguale a . Queste risorse sono necessarie per la produzione n tipi di merci. Indichiamo con simboli la quantità di questi beni rispettivamente. Tipo di articolo unità io costi . Tipo di produzione di merci io dovrebbe essere limitato ai valori rispettivamente. Per la produzione di un'unità del tipo di prodotto io il tipo di risorsa è consumato J... È necessario determinare un tale piano per la produzione di beni ( ) in modo che il loro costo totale sia minimo.

I problemi di programmazione lineare utilizzati per ottimizzare il funzionamento degli oggetti reali contengono un numero significativo di variabili e vincoli. Questo rende impossibile risolverli. metodi grafici... Con un gran numero di variabili e vincoli, vengono utilizzati metodi algebrici, che si basano su procedure computazionali iterative. Nella programmazione lineare sono stati sviluppati molti metodi algebrici che differiscono tra loro nei metodi di costruzione di una soluzione ammissibile iniziale e nelle condizioni per il passaggio da un'iterazione all'altra. Tuttavia, tutti questi metodi si basano su principi teorici generali.

La generalità delle disposizioni teoriche di base porta al fatto che i metodi algebrici per risolvere problemi di programmazione lineare sono per molti aspetti simili tra loro. In particolare, quasi tutti richiedono una riduzione preliminare del problema della programmazione lineare alla forma standard (canonica).

I metodi algebrici per risolvere il problema LP iniziano con la riduzione a forma standard (canonica):

,

,

io=1,..,n;J=1,..,m.

Qualsiasi problema di programmazione lineare può essere ridotto a una forma standard. Il confronto del modello generale con il modello canonico permette di concludere che per ridurre il problema LP alla forma standard è necessario, in primo luogo, passare dal sistema delle disequazioni alle uguaglianze e, in secondo luogo, trasformare tutte le variabili in modo che non sono negativi.

La transizione alle uguaglianze si effettua sommando a sinistra i vincoli di una variabile residua non negativa per le disequazioni del tipo e sottraendo a sinistra della variabile ridondante non negativa per le disequazioni del tipo. Ad esempio, la disuguaglianza si converte in uguaglianza durante la transizione alla forma standard , una disuguaglianza - nell'uguaglianza ... Inoltre, sia la variabile residua che la variabile ridondante sono non negative.

Si assume che il membro destro delle disuguaglianze sia non negativo. Altrimenti, questo può essere ottenuto moltiplicando entrambi i lati della disuguaglianza per "-1" e cambiando il suo segno nell'opposto.

Se nel problema di programmazione lineare originale la variabile non è limitata in segno, può essere rappresentata come la differenza di due variabili non negative , dove .

Una caratteristica importante delle variabili è che per ogni soluzione ammissibile, solo una di esse può assumere un valore positivo. Ciò significa che se , poi e viceversa. Pertanto, può essere considerato come una variabile residuale e - come ridondante.

Esempio Sia dato un problema di programmazione lineare:

,

.

È necessario portarlo in un modulo standard. Si noti che la prima disuguaglianza del problema originale ha un segno, quindi è necessario introdurre in essa una variabile residua. Di conseguenza, otteniamo.

La seconda disuguaglianza ha un segno e per la conversione nella forma standard è necessaria l'introduzione di una variabile ridondante, eseguendo questa operazione, si ottiene.

Inoltre, la variabile non è limitata nel segno. Pertanto, sia nella funzione obiettivo che in entrambi i vincoli, deve essere sostituita dalla differenza ... Eseguita la sostituzione, si ottiene un problema di programmazione lineare in forma standard, equivalente al problema originario:

.

Il problema di programmazione lineare, scritto in forma standard, è il problema di trovare l'estremo della funzione obiettivo sull'insieme dei vettori che sono soluzioni di un sistema di equazioni lineari tenendo conto delle condizioni di non negatività. Come è noto, un sistema di equazioni lineari può non avere soluzioni, avere un'unica soluzione, oppure avere un insieme infinito di soluzioni. L'ottimizzazione della funzione obiettivo è possibile solo se il sistema ha infinite molte soluzioni. Un sistema di equazioni lineari ha un insieme infinito di soluzioni se è consistente (il rango della matrice principale è uguale al rango di quella estesa) e se il rango della matrice principale è minore del numero di sconosciuti.

Sia il rango della matrice del sistema di vincoli m... Ciò significa che la matrice ha almeno un minore m esimo ordine non è uguale a zero. Senza perdita di generalità, possiamo assumere che il minore si trovi nell'angolo in alto a sinistra della matrice. Ciò si può sempre ottenere modificando la numerazione delle variabili. Questo minore di rango diverso da zero mè consuetudine chiamarlo di base. Facciamo un sistema del primo m equazioni del sistema, scrivendolo come segue:

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

I più semplici sono i cosiddetti modelli deterministici lineari. Sono specificati sotto forma di una forma lineare di variabili di controllo ( NS):

W = a 0 + un 1 X 1 + … + un k x k

a vincoli lineari del genere

B 1 j x 1 + B 2 j x 2 + … + b kj x k ³ b j , j = 1,…, Q 1 ;

C 1 j x 1 + C 2 j x 2 + … + c kj x k = c j , j = 1,…, Q 2 ;

D 1 j x 1 + D 2 j x 2 + … + d kj x k £ d j , j = 1,…, Q 3 .

Numero totale di restrizioni m = q 1 + Q 2 + Q 3 può superare il numero di variabili (m> K). Inoltre, viene solitamente introdotta la condizione per la positività delle variabili ( x io 0).

La superficie di risposta per il modello lineare è iperpiano... Ad esempio, si consideri un modello lineare di due variabili della forma seguente:

W =–2X 1 –3X 2 (2.2)

con le seguenti restrizioni

(2.3)

2X 1 + 3X£ 2 18;

X 1 – 4X 2 £ 4;

–2X 1 + X£ 2;

NS 1 ³ 0; X 2 ³ 0.

Intervallo di valori validi (intervallo di definizione) OABCD per il modello (2.2) è formato dai vincoli (2.3) (Fig. 2.2). La superficie di risposta è un poligono piatto OA "B" C "D"(fig. 2.2, B).

Per un certo rapporto di vincoli, l'insieme delle soluzioni ammissibili può essere assente (vuoto). Un esempio di un tale insieme è mostrato in Fig. 2.3. Diretto COME e sole limitare l'intervallo di valori ammissibili dall'alto. Il terzo vincolo taglia l'intervallo di valori consentiti dalla parte inferiore della linea retta AB. Pertanto, non esiste un'area comune che soddisfi tutti e tre i vincoli.

I modelli lineari sono abbastanza semplici e quindi, da un lato, implicano una significativa semplificazione del compito e, dall'altro, consentono lo sviluppo di semplici e metodi efficaci soluzioni.

Nello studio del DLA, i modelli lineari sono usati raramente e quasi esclusivamente per una descrizione approssimativa dei problemi.

I modelli lineari possono essere utilizzati per l'approssimazione graduale di modelli non lineari (linearizzazione del problema). Questa tecnica è particolarmente efficace quando si studiano piccole aree dello spazio indagato. La rappresentazione di singole sezioni della superficie di risposta non lineare con un modello lineare costituisce la base di un ampio gruppo di metodi di ottimizzazione, i cosiddetti metodi con tattica lineare.

Lo studio dei modelli lineari non è difficile. In particolare, l'influenza di ciascuna delle variabili sulle caratteristiche di un modello della forma

W = a 0 + un 1 X 1 + un 2 X 2 + …+ un k x k

dato dai suoi coefficienti:

, io = 1,…, K.

Per trovare il modello lineare ottimale W opt ha sviluppato un metodo simplex efficace.

I modelli di costo più semplici sono talvolta ridotti a quelli lineari, considerati come un insieme di costi sostenuti.

Un esempio di un tale modello è il classico modello di costo del trasporto (problema di trasporto)(figura 2.4).

C'è K punti di produzione
(io = 1,…, K) e m punti di consumo
(J = 1,…, m) di qualche prodotto. La quantità di prodotto prodotto in ciascuno K punti di produzione uguale un io; la quantità di prodotto richiesta in ciascuna delle m punti di consumo è uguale a b j.

Si assume l'uguaglianza della produzione totale e del consumo:

La quantità di prodotto trasportato da io-esimo punto di produzione in J-esimo punto di consumo è uguale a x ij; il costo del trasporto di un'unità di questo prodotto - con ij.

Costo totale del trasporto INSIEME A S è dato modello lineare:

con le seguenti restrizioni

I modelli lineari includono anche modelli sotto forma di equazioni differenziali lineari (derivate ordinarie o parziali).

Equazione differenziale ordinaria lineare n-esimo ordine ha la forma

Le condizioni iniziali si scrivono come

L'equazione differenziale parziale lineare ha la forma

Il modello, dato sotto forma di equazione alle derivate parziali, include condizioni iniziali e al contorno (condizioni al confine del dominio di definizione della funzione F ( T)).

2.3. Studio del modello matematico più semplice
funzionamento del motore a turbina a gas

Il motore a turbina a gas (GTE) è la principale centrale elettrica degli aerei moderni.

Il diagramma GTE ha la forma mostrata in Fig. 2.5.

Qui 1 - diffusore di ingresso; 2 - compressore; 3 - la camera di combustione; 4 - turbina;
5 - ugello di uscita.

Il ciclo di lavoro GTE prevede le seguenti fasi:

1) In arrivo con velocità V il flusso d'aria attraverso il diffusore entra nel compressore.

2) Il compressore, ruotando sullo stesso albero con la turbina, comprime l'aria che entra nella camera di combustione.

3) Nella camera di combustione viene costantemente iniettato carburante (cherosene), che viene miscelato con aria compressa.

4) Il gas generato dalla combustione entra nella turbina, che la accelera alla velocità W.

5) A questa velocità, il gas viene espulso nell'atmosfera attraverso l'ugello.

Per il fatto che W > V, viene generata una forza di trazione R che consente all'aereo di volare nell'atmosfera.

La modifica della spinta viene eseguita modificando la velocità di iniezione del carburante nella camera di combustione spostando la manopola di controllo del motore (acceleratore). Il movimento di spinta dell'acceleratore a un certo angolo d dell'acceleratore viene eseguito manualmente dal pilota o tramite un attuatore in base ai segnali dell'ACS in volo. Un aumento del valore di d acceleratore provoca un aumento della forza R, e una diminuzione è una diminuzione di questa forza.

GTE è un sistema tecnico complesso in cui avviene un numero significativo di processi fisici e chimici. Il motore è dotato di tutti i tipi di dispositivi di automazione, sistemi per la rotazione e il raffreddamento delle pale delle turbine, ecc. Naturalmente, anche la descrizione matematica del funzionamento del GTE sarà piuttosto macchinosa, includendo sistemi di equazioni differenziali alle derivate parziali, equazioni differenziali ordinarie, funzioni trascendentali, algoritmi di un sistema di controllo digitale del motore. Tali modelli sono utilizzati nel processo di progettazione di un motore a turbina a gas.

Per risolvere i problemi di controllo del volo, viene utilizzato un modello GTE più semplice, che è la dipendenza dalla forza di spinta R dall'angolo d dell'acceleratore, la deviazione dell'acceleratore. Il processo di modifica della forza di trazione è descritto da un ordinario equazione differenziale tipo:

, (2.11)

dove t> 0 è la costante di tempo del motore che, oltre alle caratteristiche di progetto, dipende anche dalla temperatura ambiente, dalla sua umidità e da altri fattori esterni; K[kg / deg] - coefficiente di proporzionalità.

La condizione iniziale per l'equazione (2.11) è scritta come

R(0) = R 0 . (2.12)

Pertanto, l'equazione (2.11), insieme alla condizione iniziale (2.12), è il modello matematico più semplice dell'operazione GTE, scritto sotto forma di un'equazione differenziale ordinaria 1esimo ordine.

Per determinare le proporzioni K utilizzati grafici di calibrazione della dipendenza della spinta dall'angolo di rotazione della farfalla, costruiti sulla base di dati sperimentali. La tangente della pendenza del grafico è uguale al coefficiente desiderato.

L'integrazione dell'equazione (2.11) con la condizione iniziale (2.12) permette di scoprire come la forza di spinta cambia nel tempo (Fig. 2.6).

Quando l'acceleratore viene deviato, la spinta R aumenta e poi si stabilizza ad un certo valore limite, cioè GTE è un oggetto inerziale.

Limite della forza di trazione si ottiene dalla (2.11), quando il tasso di variazione è uguale a zero:

. (2.13)

Durata della salita dipende dal valore della costante di tempo del motore t. Il processo è considerato stabile quando t = t bocca, quando la spinta entra nel cosiddetto corridoio del cinque per cento del valore limite della forza di spinta (Fig. 2.6). Maggiore è t, più inerziale è il motore e, quindi, più T bocca

Nella fig. 2.7 mostra il comportamento della forza di spinta in funzione dell'angolo di deflessione della farfalla a t = 0,5.

La forza di spinta durante il decollo, quando l'acceleratore viene deviato di 10°, raggiunge lo stato stazionario nel terzo secondo e raggiunge i 3390 kg. Dieci secondi dopo il decollo, quando l'acceleratore viene deviato di 20°, la forza di spinta è fissata a 6780 kg, e dopo altri dieci secondi, quando l'acceleratore viene deviato di 30°, la spinta è fissata a 10170 kg. Il valore limite della forza di trazione è
14270 chilogrammi.

Informazioni simili.

Concetti di modellazione di base

Nel processo dell'attività umana vengono sviluppate idee su determinate proprietà di oggetti reali e sulle loro interazioni. Queste rappresentazioni sono formate da una persona sotto forma di descrizioni di oggetti per i quali viene utilizzato un linguaggio di descrizione. Questa può essere una descrizione verbale (modelli verbali), disegno, disegno, grafico, layout, ecc. Tutto quanto sopra è riassunto da un concetto modello, e il processo di costruzione dei modelli è modellazione.

modellazioneÈ un modo universale di studiare processi e fenomeni del mondo reale. La modellazione è di particolare importanza quando si studiano oggetti inaccessibili all'osservazione diretta e alla ricerca. Questi includono, in particolare, fenomeni e processi socio-economici.

Lo studio di qualsiasi oggetto, qualsiasi forma di movimento è la divulgazione non solo delle sue leggi qualitative, ma anche quantitative studiate dalla matematica. Quanto precede si applica pienamente all'economia.

Economia- Questo è un sistema di produzione sociale che realizza effettivamente la produzione, la distribuzione, lo scambio e il consumo di beni materiali necessari per la società.

Rispettivamente, modello economico e matematicoÈ un'astrazione economica espressa in termini matematici formali, la cui struttura logica è determinata sia dalle proprietà oggettive del soggetto della descrizione, sia dal fattore obiettivo soggettivo dello studio per il quale tale descrizione viene intrapresa.

I problemi economici e matematici in agricoltura vengono risolti utilizzando metodi matematici. Tra questi, i più sviluppati sono i metodi di programmazione lineare (LP). Tali metodi sono utilizzati per risolvere problemi economici e matematici in cui le relazioni quantitative sono espresse linearmente, ad es. tutte le condizioni sono espresse come un sistema di equazioni e disequazioni lineari, e il criterio di ottimalità è espresso come una funzione lineare tendente al minimo o al massimo (ad un estremo).

Un problema di programmazione lineare consiste in una funzione obiettivo, un sistema di vincoli e una condizione di non negatività per le variabili.

Data una funzione n variabili È necessario trovare il valore più grande o più piccolo di questa funzione, a condizione che l'argomento

Il problema di ottimizzazione così posto è detto problema di programmazione matematica. Molti NSè chiamato l'insieme delle decisioni ammissibili e la funzione è la funzione obiettivo o la funzione obiettivo. La soluzione ammissibile in cui la funzione assume il valore più grande (o più piccolo) è detta soluzione ottima del problema.

Se la funzione obiettivo è lineare e l'insieme NS viene specificato utilizzando un sistema di equazioni e disequazioni lineari, quindi il problema viene chiamato problema di programmazione lineare (LPP). Pertanto, la formulazione generale del problema di programmazione lineare è la seguente:

trova l'estremo della funzione

con restrizioni

in condizioni di non negatività

Introduciamo la notazione:

Azioni io-Il tipo di risorsa;

spese io-Il tipo di risorsa per la produzione J-Il tipo di prodotto;

profitto unitario J-Il tipo di prodotto.

In una forma compatta, il problema di programmazione lineare ha la forma:

La notazione compatta mostra che il modello del problema di programmazione lineare generale include cinque elementi principali:

Variabili, il cui valore si trova nel processo di risoluzione del problema;

Coefficienti tecnici ed economici per le variabili nei vincoli;

Il volume del membro destro delle disuguaglianze, che sono chiamate le costanti del problema;

Coefficienti di variabili nella funzione obiettivo, detti stime variabili;

Indice variabile;

Indice di restrizione.

Funzione di destinazione(funzione obiettivo) è un'espressione matematica per la quale si desidera trovare l'estremo, ovvero il valore massimo o minimo.

Variabili x j denotano tali tipi e metodi di attività, la cui dimensione è sconosciuta e deve essere determinata nel corso della risoluzione del problema. Di solito, nei problemi sull'agricoltura, per variabili si intendono le dimensioni richieste dei rami dell'economia, i tipi di mangime nella dieta, le marche di trattori e macchine agricole, ecc. In base a condizioni specifiche, la stessa coltura o tipologia di bestiame può essere espressa da più variabili. Ad esempio, grano e grano da foraggio; mais da granella, insilato, foraggio verde; erbe perenni per fieno, haylage, foraggio verde, farina d'erba e semi, ecc.

Le variabili possono essere arbitrariamente modificate nelle condizioni del problema in esame. Variabile , i cui coefficienti formano una colonna unitaria sono chiamati di base. Modulo variabili di base base unitaria sistemi. Vengono chiamate le variabili che non sono incluse nella base dell'unità gratuito.

Il numero totale di variabili incluse in un'attività è determinato dalla natura dell'attività, dalle condizioni di produzione specifiche, dalla capacità di raccogliere informazioni, ecc.

Le variabili possono essere espresse in un'ampia varietà di unità: ha, q, kg, pz., Prevalenze, ecc. Per loro natura, le variabili si suddividono in principali, aggiuntive e ausiliarie. Le principali variabili includono le attività ricercate: settori industriali, tipologie di mangimi, marche automobilistiche. Le variabili aggiuntive sono chiamate variabili che si formano nel processo di trasformazione delle disuguaglianze in equazioni. Possono significare una parte sottoutilizzata delle risorse, un eccesso in eccesso lato destro disuguaglianza (se è una disuguaglianza del tipo "non più"). Le variabili ausiliarie sono incluse nell'attività al fine di determinare i valori stimati delle risorse di produzione acquisite, i valori stimati degli indicatori dell'efficienza economica della produzione.

Le variabili aggiuntive e ausiliarie hanno sempre coefficienti unitari (+1 o –1).

Coefficienti tecnici ed economici (a ij) con variabili nel sistema dei vincoli si esprimono i tassi delle risorse produttive o il tasso di output per unità di misura della variabile.

In entrambi i casi è necessario che i coefficienti tecnici ed economici corrispondano esattamente al periodo di pianificazione per il quale si sta risolvendo il problema. Ad esempio, se il problema viene risolto per l'analisi economica e matematica della produzione del periodo passato, i coefficienti verranno calcolati in base ai dati riportati. Se si decide per il futuro, i coefficienti dovrebbero essere calcolati per questa prospettiva.

I tassi di consumo delle risorse sono spesso determinati da libri di riferimento, devono essere adeguati alle condizioni specifiche corrispondenti. I rapporti di resa sono calcolati in base ai raccolti pianificati e alla produttività degli animali.

Nei casi in cui è necessario prevedere relazioni predeterminate tra variabili, coefficienti tecnici ed economici rappresentano coefficienti di proporzionalità. Ad esempio, la quota di colture nella rotazione delle colture o la quota di alcuni mangimi nel gruppo di mangimi totale, ecc.

Lato destro delle restrizioni (b i) sono chiamate costanti, cioè valori costanti. Questi includono il volume delle risorse di produzione: terra, lavoro, macchinari, fertilizzanti, investimenti, ecc. Le risorse di produzione dovrebbero essere determinate tenendo conto del loro stato effettivo ed è imperativo tenere conto del periodo di pianificazione. Inoltre, quelle risorse produttive, il cui utilizzo è disomogeneo nell'arco dell'anno, sono calcolate non solo per l'anno nel suo complesso, ma anche per singoli periodi o mesi intensi (risorse lavoro).

Le risorse di produzione sono determinate in diverse unità: terra - in ettari, risorse di lavoro - in giorni-uomo o in ore-uomo, attrezzature - nel numero di turni macchina, turno o produzione giornaliera, ecc.

Pertanto, determinare la disponibilità delle risorse produttive non è facile. È necessario analizzare attentamente l'attività di produzione dell'economia, l'uso di lavoro, terra, risorse tecniche e di altro tipo e solo dopo includere i loro volumi nelle restrizioni.

Il lato destro delle restrizioni riflette non solo la quantità di risorse, ma anche il volume dei prodotti prodotti al livello superiore o inferiore. Il livello inferiore viene mostrato nei casi in cui il volume di produzione è noto in anticipo, inferiore al quale l'azienda agricola non dovrebbe produrre e il livello superiore non consente la produzione di prodotti al di sopra di un certo volume. Queste restrizioni non sono sempre necessarie. Tuttavia, quasi nessun problema che coinvolge la definizione di una combinazione di industrie non fa a meno delle corrispondenti restrizioni sui prodotti, altrimenti risulterà una soluzione unilaterale. Ciò è dovuto al fatto che l'efficienza delle industrie non è la stessa.

In tutte le altre restrizioni, gli zeri sono posti sul lato destro, poiché formulano condizioni per la produzione e l'uso di prodotti o riflettono restrizioni sulla comunicazione proporzionale.

LimitazioneÈ un'espressione matematica che lega le variabili sotto forma di uguaglianze e disuguaglianze. Modulo per tutte le restrizioni sistema di restrizioni compiti. Il sistema di vincoli in forma matematica caratterizza le condizioni del problema. La completezza della riflessione di queste condizioni dipende dalla composizione delle restrizioni. Pertanto, nel determinare il numero di restrizioni, devono essere prese in considerazione due circostanze:

v riflettere nel compito solo quelle condizioni che realmente limitano le possibilità di produzione;

v troppi vincoli aumentano le dimensioni del problema e ne rendono difficile la risoluzione

Esistono tre tipi di vincoli: uguaglianza (=), disuguaglianza di tipo minore o uguale a (≤), disuguaglianza di tipo maggiore o uguale a (≥). Per esempio,

dove io = 1, 2, … , m... I coefficienti variabili sono indicati un ij dove indice io- numero di restrizione, indice J- numero variabile, sono indicati i membri liberi (lato destro dei vincoli) b io, indice io- numero di restrizione.

I vincoli del primo tipo sono chiamati vincoli superiori, poiché il lato sinistro della disuguaglianza non può essere maggiore di un certo valore (costante). I vincoli del terzo tipo sono chiamati vincoli dal basso, poiché il lato sinistro della disuguaglianza non può essere inferiore a un certo valore (costante).

In termini di significato, tutte le restrizioni possono essere suddivise in principali, aggiuntive e ausiliarie.

Le principali limitazioni sono - questi sono quelli che si sovrappongono a tutte o alla maggior parte delle variabili dell'attività. Di norma, con il loro aiuto, si riflettono le condizioni di base del problema: in termini di terra, lavoro, mangimi, sostanze nutritive, tecnologia, ecc.

Restrizioni aggiuntive sono sovrapposti a una parte di variabili o a una variabile. Tali restrizioni vengono introdotte nei casi in cui sia necessario limitare dall'alto o dal basso la dimensione delle singole variabili, ad esempio tenendo conto delle esigenze di rotazione delle colture o tenendo conto dei limiti fisiologici di saturazione della dieta con i singoli mangimi o loro gruppi. Pertanto, ulteriori vincoli riflettono varie condizioni aggiuntive che si presentano durante la simulazione. Ma ogni ulteriore restrizione restringe l'ambito della libertà di scelta. Pertanto, dovrebbero essere introdotti nel compito con attenzione, entro limiti ragionevoli e quando necessario.

Restrizioni ausiliarie, di regola, non hanno un significato autonomo e vengono introdotti nel problema per formalizzare condizioni individuali. Questi includono vincoli che stabiliscono una relazione proporzionale tra le singole variabili oi loro gruppi.

Stima delle variabili nella funzione obiettivo (con J) sono coefficienti che esprimono l'ammontare del reddito o dei costi totali per unità di misura della variabile. La stima di una variabile, di regola, esprime il criterio di ottimalità accettato. Può essere presentato sia in natura che in contanti, ad es. costi unitari (costi di produzione).

La condizione per la non negatività delle variabili si scrive nella forma

x j≥ 0, j = 1, 2, ..., n.

Nella vita reale della produzione, in base alle condizioni dell'attività, viene compilato un elenco di variabili e restrizioni da questo record del modello economico e matematico strutturale (EMM), vengono preparate le informazioni iniziali, viene costruito un problema EMM dettagliato, che è quindi scritto sotto forma di matrice (tabella), inserito in un computer e secondo il programma corrispondente, viene eseguito il calcolo e l'analisi dei risultati. i = 1, ..., m, (1.5)

J = 1, …, n. (1.6)

Vettore X = (X 1 , X 2 , …, X n), componenti x j che soddisfano i vincoli (1.2) e (1.3) [o (1.5) e (1.6) nel problema di minimo] si chiama decisione accettabile o piano accettabile compiti di LP. La raccolta di tutti i piani validi si chiama molti piani validi.

Canonico la forma del problema di programmazione lineare è caratterizzata dal fatto che contiene una funzione obiettivo, tutte le restrizioni uguaglianza, tutte le variabili sono non negative.

Qualsiasi problema di programmazione lineare può essere ridotto a un problema di programmazione lineare in forma canonica. Per fare ciò, nel caso generale, è necessario essere in grado di ridurre il problema della massimizzazione al problema della minimizzazione; passare dai vincoli di disuguaglianza ai vincoli di uguaglianza e sostituire le variabili che non obbediscono alla condizione di non negatività.

La regola per ridurre un problema di programmazione lineare alla forma canonicaè come segue:

1) se nel problema originario si richiede di determinare il massimo di una funzione lineare, allora il segno va cambiato e va cercato il minimo di questa funzione;

2) se nelle restrizioni il lato destro è negativo, allora questa restrizione deve essere moltiplicata per - 1;

3) se tra i vincoli ci sono disuguaglianze, allora introducendo variabili aggiuntive di variabili non negative, si trasformano in uguaglianze. Ad esempio, variabili aggiuntive S j nei vincoli del tipo minore o uguale a (£) si inseriscono con il segno più:

Variabili aggiuntive S j nei vincoli di tipo maggiori o uguali a (≥) vengono inseriti con il segno meno:

Per eliminare la negatività di variabili aggiuntive - S j introdurre variabili artificiali con segno più + M j con valori molto grandi.