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

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

sotto i vincoli lineari della forma

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

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

D 1 jx 1 + D 2 jx 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, la condizione di positività delle variabili ( x io³ 0).

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

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

alle seguenti restrizioni

(2.3)

2X 1 + 3X 2 £ 18;

X 1 – 4X 2 £ 4;

–2X 1 + X 2 £ 2;

X 1³0; X 2³ 0.

Intervallo valido (ambito 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"(figura 2.2, B).

Per una certa relazione di vincolo, l'insieme delle soluzioni ammissibili può essere assente (vuoto). Un esempio di tale insieme è mostrato in Fig. 2.3. Diretto AU E sole limitare l'intervallo di valori consentiti dall'alto. Il terzo vincolo taglia fuori dalla retta la regione dei valori ammissibili sottostante AB. Pertanto, non esiste un'area comune che soddisfi tutti e tre i vincoli.

I modelli lineari sono piuttosto semplici e quindi, da un lato, implicano una significativa semplificazione del problema, e dall'altro consentono lo sviluppo di metodi di soluzione semplici ed efficaci.

Nello studio del DLA, i modelli lineari sono usati raramente e quasi esclusivamente nella descrizione approssimata di problemi.

I modelli lineari possono essere utilizzati per l'approssimazione passo-passo di modelli non lineari (linearizzazione del problema). Questa tecnica è particolarmente efficace quando si studiano piccole aree dello spazio studiato. La rappresentazione delle singole sezioni della superficie di risposta non lineare da parte di un modello lineare è alla base grande gruppo metodi di ottimizzazione, i cosiddetti metodi con tattiche lineari.

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

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

è dato dai suoi coefficienti:

, io = 1,…, K.

Trovare l'ottimo del modello lineare W opt ha sviluppato un efficiente metodo simplex.

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

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

Disponibile K punti di produzione
(io = 1,…, K) E M punti di consumo
(J = 1,…, M) di un prodotto. La quantità di prodotto prodotto in ciascuno K punti di produzione, un io; la quantità di prodotto necessaria in ciascuno M punti di consumo, bj.

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

Quantità di prodotto trasportato da io-esimo punto di produzione in J-esimo punto di consumo, pari a xij; il costo del trasporto di un'unità di questo prodotto - con ij.

Costo totale del trasporto CON S è dato modello lineare:

alle seguenti restrizioni

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

Equazione differenziale ordinaria lineare N L'ordine ha la forma

Le condizioni iniziali sono scritte come

Un'equazione alle derivate parziali lineare ha la forma

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

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

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

Lo schema GTE ha la forma mostrata in Fig. 2.5.

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

Il ciclo di lavoro GTE comprende 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 della turbina, comprime l'aria che entra nella camera di combustione.

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

4) Il gas generato dalla combustione entra nella turbina, che lo accelera a una velocità W.

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

A causa del fatto che W > v, viene generata la forza di trazione R, che consente all'aereo di volare nell'atmosfera.

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

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

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

, (2.11)

dove t > 0 è la costante di tempo del motore, che dipende, oltre che da caratteristiche progettuali 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 del motore a turbina a gas, scritto sotto forma di un'equazione differenziale ordinaria 1-esimo ordine.

Per determinare il fattore di proporzionalità K vengono utilizzate curve di calibrazione della dipendenza della spinta dall'angolo di rotazione delle farfalle, costruite 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) consente 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 di spinta otteniamo dalla (2.11) quando il tasso della sua variazione è uguale a zero:

. (2.13)

Ora di alzarsi dipende dal valore della costante di tempo del motore t. Il processo è considerato costante quando t = t bocca, quando la spinta entra nel cosiddetto corridoio del cinque percento del valore limite della forza di spinta (Fig. 2.6). Più grande t, più inerziale è il motore e, di conseguenza, più T bocca

Sulla fig. 2.7 mostra l'andamento della forza di spinta in funzione dell'angolo di deflessione dell'acceleratore a t = 0,5.

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

Informazioni simili.

3.1. Compito generale programmazione lineare

Programmazione lineare- questa è la sezione più sviluppata della programmazione matematica, con l'aiuto della quale vengono eseguite l'analisi e la soluzione di problemi estremi con connessioni e restrizioni lineari.

La programmazione lineare include una serie di metodi di soluzione euristici (approssimativi) che consentono, in determinate condizioni, da tutti opzioni soluzioni ai problemi di produzione per scegliere il meglio, ottimale. Questi metodi includono i seguenti: metodo grafico, simplex, potenziale (metodo di distribuzione modificato - MOD), metodo di approssimazione Khichkov, Kreko, Vogel e altri.

Alcuni di questi metodi sono accomunati da un nome comune: metodo di distribuzione o trasporto.

Il luogo di nascita della programmazione lineare è la Russia. I primi lavori sulla programmazione lineare del futuro accademico L.V. Kantorovich furono pubblicati nel 1939. Nel 1975 ricevette il premio Nobel per l'economia per lo sviluppo di metodi di programmazione lineare. Poiché la maggior parte delle opere dell'accademico L.V. Kantorovich si dedica alla risoluzione dei problemi di trasporto, si può ritenere che il citato Premio Nobel segni anche i meriti della scienza dei trasporti russa.

Nel trasporto su strada, i metodi di programmazione lineare sono stati utilizzati dagli anni '60 per risolvere un gran numero dei più importanti problemi di produzione, vale a dire: ridurre la distanza del trasporto merci; elaborare uno schema di trasporto ottimale; selezione dei percorsi di movimento più brevi; compiti di trasporto di carichi diversi, ma intercambiabili; pianificazione giornaliera dei turni; pianificazione del trasporto di piccoli lotti; distribuzione di autobus lungo i percorsi e altro.

Le caratteristiche del modello di programmazione lineare sono le seguenti:

La funzione obiettivo ei vincoli sono espressi dipendenze lineari(uguaglianze o disuguaglianze);

Il numero di dipendenze è sempre inferiore al numero di incognite (condizione di incertezza);

Non negatività delle variabili richieste. La forma generale di scrittura di un modello di programmazione lineare in forma abbreviata è la seguente:

Trovare X ij ≥ 0 (j = 1, 2…n) sotto il seguente tipo di vincoli:

Questi vincoli minimizzano (o massimizzano) la funzione obiettivo

La forma standard di scrittura di un modello di programmazione lineare è un sistema di equazioni lineari scritte canonico forma, cioè sotto forma di uguaglianze lineari, in numeri non negativi:

a 11 x 1 + a 12 x 2 + ... + a 1 n x n \u003d b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n \u003d b 2 ; (3.1)

……………………………..

a m x 1 + a m 2 x 2 + ...+ a mn x n = b m ..

Se il modello è scritto sotto forma di disuguaglianze in numeri non negativi, cioè ha la forma

un 11 x 1 + un 12 x 2 + ... + un 1 n x n ≤ b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n ≤ b 2 ; (3.2)

……………………………..

a m x 1 + a m 2 x 2 + …+ a mn x n ≤ b m ,..

quindi questa voce è ridotta a canonico forma (3.1) introducendo variabili aggiuntive xn+1> 0 (io=1,2…M) a sinistra della disuguaglianza (o riduzione del numero di variabili se il segno della disuguaglianza è diretto nella direzione opposta). Variabili aggiuntive costituiscono la base.

La forma standard per risolvere un problema di programmazione lineare consiste nel trovare soluzioni a un sistema di equazioni lineari in numeri non negativi che minimizzino la funzione obiettivo. La funzione obiettivo ha quindi la forma

L = c 1 x 1 + c 2 x 2 ... c n x n → minimo, (3.3)

Dove s 1 , s 2 … s n sono coefficienti di funzione obiettivo l con variabili X J .

Variabili aggiuntive entrano nella funzione obiettivo con zero coefficienti.

Nel caso di massimizzazione della funzione obiettivo l i segni delle variabili della funzione obiettivo dovrebbero essere invertiti, e torneremo di nuovo al problema di minimizzazione, cioè un compito è ridotto a un'altra sostituzione l SU - l o massimo l=minuto(- l).

Una soluzione di base di un sistema di equazioni lineari (3.1) è una soluzione in cui vengono dati valori zero a variabili non di base.

Una soluzione di base si dice ammissibile in cui le variabili incluse nella base sono non negative.

Una soluzione ammissibile che massimizza (o minimizza) la funzione obiettivo (3.3) si dice ottima.

Ogni problema di programmazione lineare ne corrisponde un altro, chiamato problema di programmazione lineare duale. Il problema originario rispetto a quello duale si chiama problema diretto. I problemi primali e duali formano una coppia, chiamata doppia coppia nella programmazione lineare. La coppia primale e duale formano una coppia asimmetrica quando il problema primale è scritto in forma canonica, e una coppia simmetrica quando le condizioni dei problemi sono scritte come disuguaglianze.

Le regole per la compilazione di un modello matematico di un problema duale si basano sulle regole del calcolo matriciale.

Il concetto di dualità è ampiamente utilizzato nell'analisi dei problemi di programmazione lineare. La proprietà della dualità è considerata in dettaglio in ogni caso specifico.

3.2. Metodo grafico-analitico

Il metodo grafico-analitico è uno dei metodi più semplici di programmazione lineare. Rivela chiaramente l'essenza della programmazione lineare, la sua interpretazione geometrica. Il suo svantaggio è che ti consente di risolvere problemi con 2 o 3 incognite, cioè è applicabile a una gamma ristretta di problemi. Il metodo si basa sulle regole della geometria analitica.

Risolvere un problema con due variabili x 1 E x 2, che, secondo il significato del problema, non dovrebbe essere negativo, viene eseguito nel sistema di coordinate cartesiane. Equazioni x 1=0 e x 2= 0 sono gli assi del sistema di coordinate del primo quadrante

Consideriamo il metodo di soluzione utilizzando un esempio specifico.

Esempio 3.1. Ci sono 300 tonnellate di prodotti in calcestruzzo espanso e 200 tonnellate di prodotti in acciaio in magazzino. L'impresa automobilistica deve consegnare questi prodotti alla struttura in costruzione. La casa automobilistica ha camion KAMAZ - 5320 e

ZIL-4314. Per un viaggio, KamAZ-5320 può fornire 6 tonnellate di calcestruzzo espanso e 2 tonnellate di acciaio e il profitto del viaggio sarà di 4 mila rubli. ZIL-4314 consegna 2 tonnellate di calcestruzzo espanso e 4 tonnellate di acciaio in un viaggio, il profitto del viaggio è di 6 mila rubli. È necessario organizzare il trasporto in modo tale da fornire all'impresa automobilistica il massimo profitto.

Costruiamo un modello matematico del problema. Indica con x 1 il numero desiderato di viaggi KamAZ-5320 e attraverso X 2 numero richiesto di motociclisti ZIL-4314.

Il trasporto totale in tonnellate di prodotti in calcestruzzo espanso è 6 x1+ 2x 2, e dall'acciaio 2 x1+ 4x 2. Il limite di spedizione, in base al numero di articoli disponibili, è di 6 x1+ 2x2≤ 300t per calcestruzzo espanso e 2 x1+ 4x2≤ 200t per l'acciaio.

Profitto totale in migliaia di rubli. espresso come 4 X 1 + 6X 2 , che deve essere massimizzato e che è il criterio di ottimalità nel problema in esame. Il modello matematico del problema si presenta quindi come il seguente. È necessario massimizzare la funzione obiettivo

l = 4x1+ 6x 2 → max in condizioni: 6 x1+ 2x2≤ 300; 2x1+ 4x2≤ 200; x 1 ≥ 0;x 2 ≥ 0.

Considera l'equazione 6 x1+ 2x 2 = 300. Per costruire una retta descritta da questa equazione, troviamo due punti giacenti su questa retta. A x 1= 0 dall'equazione di una retta troviamo 2 x 2 = 300, da cui x 2 \u003d 150. Pertanto, il punto A con coordinate (0,150) si trova sulla linea desiderata. A x 2= 0 abbiamo 6 x 1\u003d 300, da dove x 1 \u003d 50, e il punto D con le coordinate (50,0) si trova anche sulla riga desiderata. Disegna una linea attraverso questi due punti ANNO DOMINI(figura 3.1).

Disuguaglianza lineare 6 x1+ 2x2≤ 300 è un semipiano situato su un lato della linea costruita 6 x1+ 2x 2 = 300. Per scoprire da che parte di questa linea si trovano i punti del semipiano desiderato, sostituiamo nella disuguaglianza 6 x1+ 2x2≤ 300 coordinate di un punto che non giace sulla linea di confine. Ad esempio, l'origine è 0-(0,0). Soddisfa la disuguaglianza 6∙0 + 2∙0 = 0< 300. Это значит, что начало координат лежит в области допустимых значений, которая находится слева от прямой ANNO DOMINI e nella fig. 3.1 è ombreggiato.

Equazione 2 x1+ 4x 2= 200 sarà costruito da due punti. A x 1 = 0 4x 2 = 200 da dove x 2 = 50. Poi punto E ha coordinate (0,50) e appartiene alla linea desiderata. A x 2= 0, 2x 2 = 200 punti Conè sulla linea data con le coordinate (100,0). Sostituendo nella disuguaglianza le coordinate del punto Con(0,0), otteniamo 2∙0 + 4∙0 = 0< 200. Значит, начало координат находится в области допустимых значений от прямой 2x 1+ 4x 2= 200.

Il sistema di vincoli delle attività richiede che i piani ( x 1; x 2) soddisfano tutte e quattro le disuguaglianze, cioè i disegni ammissibili sono punti ( x 1; x 2) deve trovarsi simultaneamente in tutti e quattro i semipiani. Questo requisito è soddisfatto solo da punti situati all'interno e sul bordo del poligono. OEKD, che è il poligono delle soluzioni ammissibili.

I vertici del poligono delle soluzioni ammissibili sono i punti O, MI, RE, RE segmenti di linea OE, EK, KD, OD- le sue costole. Qualsiasi punto del poligono OEKDè il piano del compito, soddisfacendo tutte le sue condizioni. I vertici del poligono sono formati dall'intersezione di due rette e corrispondono ai piani base del problema, tra cui il piano migliore (ottimale). Ci saranno quindi tanti piani di riferimento quanti sono i vertici nel poligono delle soluzioni ammissibili.

Una rappresentazione geometrica visiva può essere ottenuta anche per la funzione obiettivo l = 4x1+ 6x 2. Ad esempio, fissiamo un valore della funzione obiettivo l= 120. equazione 4 x1+ 6x 2 = 120 definisce una linea passante per un punto IN con coordinate (x 1 \u003d 0; x 2 \u003d 20) e un punto l con coordinate (( X 1 = 30; X 2 = 0). Segmento BL si trova all'interno del poligono OEKD. Pertanto, per tutti i piani (punti) di questo segmento, il valore della funzione obiettivo è uguale e pari a 120. Dando altri valori della funzione obiettivo, si ottengono rette parallele, che si chiamano linee di livello funzione bersaglio.

Spostare la linea l parallelamente a se stesso in una direzione, otteniamo un aumento della funzione obiettivo e, nella direzione opposta, la sua diminuzione. In questo esempio, il movimento di una linea retta BL a destra determina l'aumento della funzione obiettivo che stiamo massimizzando. Lo facciamo fino alla linea BL avrà almeno un punto in comune con il poligono delle soluzioni ammissibili OEKD. Dalla fig. 3.1 ne consegue che l'ultimo punto che interseca la retta del livello della funzione obiettivo sarà il punto A. Ciò significa che il punto A determina il piano di attività ottimale.

Viene chiamata la direzione di aumento perpendicolare alla linea di livello direzione di maggior incremento funzione obiettivo e ne determina il massimo guadagno. Questa direzione può essere impostata senza tracciare linee di livello. Per questo, è necessario sugli assi x 1 E x 2 metti da parte segmenti uguali ai coefficienti della funzione obiettivo e usandoli, come nelle coordinate, costruisci un vettore del massimo aumento della funzione obiettivo. In matematica si chiama pendenza e denotato dal segno grad. Gradiente per una caratteristica l = 4x1 + 6x2 vettore N| 4; 6 | . Per comodità della sua costruzione, aumentiamo le coordinate, ad esempio, di 10 volte, ad es. n | 40; 60| . Costruiamo il gradiente della funzione obiettivo l, per cui colleghiamo il punto con coordinate (40; 60) con l'origine. Le linee del livello della funzione obiettivo sono disegnate perpendicolarmente alla direzione del gradiente.

Quindi, in un modo o nell'altro, è stabilito che il punto A determina il piano di attività ottimale, i cui valori delle variabili corrispondono alle coordinate del punto dato. Per stabilire le coordinate è necessario risolvere il sistema di equazioni delle rette che formano questo vertice:

6x1+ 2x 2= 300;

2x1+ 4x 2= 200.

Uguagliamo i coefficienti in x 1 moltiplicando la seconda equazione per 3 e sottraiamo la prima dalla seconda equazione. Prendiamone 10 x 2= 300,x 2 = 30. Sostituendo il valore x 2 \u003d 30 in una qualsiasi delle equazioni, ad esempio nella prima, determiniamo il valore X 1:

6x 1+ 2X · 30 = 300,

da cui 6 x 1 = 300 - 60 = 240, quindi, x 1 = 40.

Pertanto, per ottenere il massimo profitto per un'azienda automobilistica, è necessario completare 40 viaggi a KamAZ-5320 e 30 viaggi a ZIL-4314. Il profitto massimo in questo caso sarà

l = 4x1+ 6x 2\u003d 4 40 + 6 30 \u003d 340 mila rubli.

Sulla base dell'esempio considerato e dell'interpretazione geometrica del problema di ottimizzazione con due variabili, possiamo trarre le seguenti conclusioni:

1) nello spazio bidimensionale, l'area delle soluzioni ammissibili è un poligono;

2) ogni lato del poligono corrisponde al valore di una variabile uguale a zero;

3) ogni vertice del poligono delle soluzioni ammissibili corrisponde ai valori di due variabili uguali a zero;

4) ogni valore della funzione obiettivo corrisponde a una retta;

5) la soluzione ottima del problema corrisponde al vertice del poligono, in cui la funzione obiettivo acquista il valore ottimo, mentre le variabili ottime sono le coordinate di questo vertice.

Nel caso generale, i problemi di ottimizzazione hanno un'interpretazione geometrica simile. L'insieme dei piani di attività sarà un poliedro i cui vertici corrispondono ai piani di riferimento. Quando si risolve il problema, viene eseguita la transizione da un vertice del poliedro a un altro con un valore elevato della funzione obiettivo fino a ottenere il suo valore ottimale. Si noti che l'efficienza dei metodi di ottimizzazione risiede proprio nel fatto che l'enumerazione dei vertici (iterazione) viene eseguita solo nella direzione del massimo incremento della funzione obiettivo. Pertanto, non vengono considerati tutti i vertici, di cui esiste un numero enorme, ma solo quelli più vicini a quello estremo.

Quando si determina una classe di problemi di ottimizzazione e si sceglie un metodo per risolverlo, è necessario sapere se l'insieme delle soluzioni ammissibili è convesso o non convesso, una funzione obiettivo lineare o non lineare.

Per definizione, viene chiamato un insieme convesso se per due punti qualsiasi l'intero segmento che collega questi punti appartiene a questo insieme. Esempi di insiemi convessi sono, ad esempio, un segmento (Fig. 3.2, a), un piano a forma di cerchio, un cubo, un parallelepipedo, nonché poligoni che si trovano interamente su un lato di ciascuno dei suoi lati , eccetera.

Sulla fig. 3.2b mostra insiemi non convessi. Negli insiemi non convessi si possono indicare almeno due punti del segmento AB che non appartengono all'insieme considerato.

3.3. Metodo del Simplesso

Metodo del simplessoè un metodo comune per risolvere problemi di programmazione lineare. Il metodo prende il nome dalla parola "simplex", che denota il poligono convesso più semplice, il cui numero di vertici è sempre uno in più rispetto alla dimensione dello spazio. Il metodo del simplesso è stato sviluppato negli Stati Uniti dal matematico J. Dantzig alla fine degli anni '40.

Il metodo del simplesso prevede l'ottenimento di una soluzione di base non negativa di un sistema di equazioni lineari canoniche di tipo (3.1), la successiva minimizzazione (massimizzazione) della funzione obiettivo (3.3) e, in tal modo, la ricerca dei valori ottimali della variabili sconosciute x 1, x 2… x n.

L'idea del metodo del simplesso sta nel fatto che nel corso del calcolo si passa sequenzialmente dalla prima soluzione di base alla seconda, terza, ecc. attraverso il cosiddetto simplex trasformazioni. Le trasformazioni vengono effettuate sotto forma di tabelle simplex, che semplificano e accelerano notevolmente i calcoli.

Per ottenere soluzioni di base non negative di un sistema di equazioni lineari, è necessario condurre il processo di eliminazione delle incognite in modo tale che i termini liberi delle equazioni rimangano non negativi in ​​tutte le fasi del processo. In questo caso, si dovrebbe essere guidati dalla seguente regola: qualsiasi variabile libera per la quale esiste almeno un coefficiente positivo viene presa come nuova variabile di base; dalla base si ricava una variabile, che corrisponde al più piccolo rapporto tra i termini liberi delle equazioni ei corrispondenti coefficienti positivi delle equazioni con la variabile introdotta nella base. Tali trasformazioni sono chiamate convertitori simplex.

Questo è molto importante, perché per trovare una particolare soluzione non negativa che corrisponda al valore più grande possibile di una variabile libera con valori zero di altre variabili libere, invece di determinare l'intervallo della variabile specificata e sostituirne il valore più grande possibile valore in decisione comune basta prendere questa variabile come quella base e sottoporre il sistema ad una trasformazione in simplesso, passando ad una nuova base, che semplifica notevolmente i calcoli.

I calcoli vengono eseguiti convenientemente utilizzando tabelle simplex. Il passaggio da una tabella all'altra corrisponde a un'iterazione, cioè il passaggio da una base all'altra, mentre il valore della funzione obiettivo diminuisce. Per un certo numero di iterazioni passano alla base per la quale si ottiene il valore ottimale (minimo o massimo) della funzione obiettivo. Consideriamo il metodo del simplesso in forma generale.

Il compito generale della programmazione lineare è minimizzare (massimizzare) la funzione obiettivo, le cui variabili sono interconnesse da un sistema di equazioni lineari, soggetto alla condizione di non negatività.

Sia necessario minimizzare la forma lineare

l = c 1 x 1 + c 2 x 2 + ... c n x n.

Nelle seguenti condizioni (per chiarezza, nelle equazioni vengono mantenuti i coefficienti zero e unità):

1x 1+ 0x 2 +... 0x m + a 1m+ 1x m+1 ... + a 1n x n \u003d b 1;

0x1+ 1x2+… 0x m + a 2m+ 1x m+1 ... + a 2n x n \u003d b 2;

……………………………………………

0x 1+ 0x 2 + ... 1x m + a mm + 1x m +1 ... + a mn x n \u003d b m.

Questo sistema di equazioni ha già una base già pronta, poiché ogni equazione di vincolo contiene un'incognita con un coefficiente uguale a uno, che non è in altre equazioni, cioè dai coefficienti delle variabili X 1 , X 2 …, x mè possibile creare una matrice identità.

Risolviamo le equazioni per le variabili di base:

x 1 \u003d b 1 - (a 1m + 1 x m + 1 ... + a 1n x n);

x 2 \u003d b 2 - (a 2m + 1 x m + 1 ... + a 2n x n);

………………………………

x m \u003d b m - (a mm + 1x m + 1 ... + a mn x n),

e esprimeremo la funzione obiettivo in termini di variabili libere, sostituendo in essa, al posto delle variabili base, le loro espressioni in termini di variabili libere:

L=c 1 b 1 +c 2 b 2 +c m b m –(c 1 a 1m +c 2 a 2m+1 +…+c m a mn+1)x m+1 -…-(c 1 a 1n +c 2 a 2n +…+c m a mn)x n …+c n x n..

Variabili x 1, x 2 ..., x m, con l'aiuto del quale si trova il primo piano di base, sono di base e il resto x m +1 , x m +2 ,…x n – gratuito. Dovrebbero esserci sempre tante variabili di base quante sono le equazioni nel sistema. Sulla base della condizione di non negatività, il valore più piccolo delle variabili libere è uguale a zero. La risultante soluzione di base del sistema di equazioni è la sua soluzione ammissibile iniziale, cioè x 1 \u003d b 1, x 2 \u003d b 2, ... x m \u003d b m, x m +1 \u003d 0,…, x n = 0.

Questa soluzione corrisponde al valore della funzione obiettivo

l = c 1 b 1 + c 2 b 2 + ... c m b m.

Viene verificata l'ottimalità della soluzione iniziale. Se non è ottimale, allora introducendo variabili libere nella base, si trovano le seguenti soluzioni ammissibili con un valore minore della funzione obiettivo. Per fare ciò, viene determinata una variabile libera che deve essere inserita nella base, nonché una variabile che deve essere rimossa dalla base. Quindi passano dal sistema precedente al successivo sistema equivalente. Questo viene fatto usando tabelle simplex. La soluzione del problema continua fino ad ottenere il valore ottimo della funzione obiettivo.

Le tabelle Simplex sono compilate come segue (vedi Tabella 3.1). Posiziona tutte le variabili in cima alla tabella X 1 , X 2 …, x n e coefficienti cj, con cui le variabili corrispondenti sono incluse nella funzione obiettivo. Prima colonna ci consiste nel coefficiente della funzione obiettivo per le variabili incluse nella base. Questo è seguito da una colonna di variabili di base e termini liberi delle equazioni. Gli elementi delle restanti colonne della tabella sono i coefficienti delle variabili con cui queste ultime entrano nel sistema di equazioni. Pertanto, ogni riga della tabella corrisponde all'equazione del sistema, risolta rispetto alla variabile di base. La tabella mostra anche una variante del piano che corrisponde alla funzione obiettivo per una data base.

Viene chiamata la riga inferiore della tabella indice. Ciascuno dei suoi elementi (stima) ∆ J determinare

∆j = z j – c j ,

Dove cj sono i coefficienti per le variabili corrispondenti nella funzione obiettivo; zj – la somma dei prodotti dei coefficienti della funzione obiettivo con le variabili di base e le corrispondenti variabili - elementi J-esima colonna della tabella.

Tavolo 3.1

Tabella simplex con iniziale valida

1.

2. istruzioni per l'uso tappetino. modelli in economia.

I modelli matematici consentono di determinare i valori ottimali di parametri sconosciuti sistemi economici che è importante nel processo decisionale. La programmazione matematica fornisce solo un apparato che consente di ottimizzare il processo di selezione le migliori opzioni piani nel processo di gestione nei sistemi economici.

Utilizzato in statistica matematica, metodi di ottimizzazione, metodi economici. cibernetica, problemi sperimentali.

Quando si studiano processi e fenomeni complessi nell'economia, viene spesso utilizzata la modellazione, una visualizzazione concreta ben definita delle caratteristiche considerate dell'oggetto in esame. La sua essenza sta nel fatto che il fenomeno in esame viene riprodotto in condizioni sperimentali utilizzando un modello su una diversa scala temporale e spaziale. Un modello è un oggetto appositamente creato con l'aiuto del quale vengono riprodotte alcune caratteristiche del sistema in esame per studiarlo. Modellazione matematicaè il metodo più perfetto e allo stesso tempo efficace per ottenere informazioni sull'oggetto in esame. È un potente strumento per l'analisi in economia. I risultati della ricerca che utilizza i modelli saranno di interesse pratico quando il modello costruito è sufficientemente adeguato al fenomeno in esame, vale a dire abbastanza bene da riflettere la situazione reale.

2. la programmazione matematica come scienza, la sua struttura. Problemi di ottimizzazione. Difficoltà nell'applicare i classici metodi di ottimizzazione alla soluzione di problemi economici.

Programmazione matematicaè una branca della matematica applicata che si sviluppa base teorica e metodi per risolvere problemi estremi.

La programmazione matematica comprende una serie di sezioni, le principali delle quali sono le seguenti:

1. Programmazione lineare. Questa sezione include problemi in cui variabili sconosciute sono incluse in relazioni matematiche di primo grado.

2. Programmazione non lineare. Questa sezione include problemi in cui la funzione obiettivo e (o) i vincoli possono essere non lineari.

3. Programmazione dinamica. Questa sezione include attività in cui il processo di soluzione può essere suddiviso in fasi separate.

4. Programmazione intera. Questa sezione include attività in cui le variabili sconosciute possono assumere solo valori interi.

5. Programmazione stocastica. Questa sezione include attività che contengono variabili casuali nella funzione obiettivo o nei vincoli.

6. Programmazione parametrica. Questa sezione include problemi in cui i coefficienti di variabili sconosciute nella funzione obiettivo o nei vincoli dipendono da alcuni parametri.

Per risolvere problemi di programmazione matematica, è difficile utilizzare metodi classici per trovare un estremo, poiché nei problemi di programmazione matematica la funzione obiettivo raggiunge il suo valore estremo al confine della regione dei valori accettabili di variabili sconosciute e le derivate non esistono nei punti di confine. Un'enumerazione completa dei punti ammissibili è impossibile a causa del loro numero significativo.

3. Il concetto di modello matematico, tipi di tappeto. Modelli

Modello matematicoè un'astrazione di un fenomeno o processo reale scritto in simboli ed espressioni matematiche. Modelli matematici processi economici ei fenomeni sono chiamati modelli economici e matematici

I modelli si dividono in:

1. lineare, in cui tutte le dipendenze sono descritte da relazioni lineari,

2. non lineare, in cui esistono relazioni non lineari;

3. Stocastico, che tengono conto della natura casuale dei processi oggetto di studio,

4. deterministico, che tengono conto dei valori medi di tutti i parametri.

5. dinamico modelli in cui i sistemi in studio sono considerati in evoluzione su più periodi,

6. statico, in cui il fattore tempo non viene preso in considerazione.

7. ottimizzazione modelli in cui la scelta viene effettuata in base a estremizzazione qualche criterio,

8. non ottimizzazione, in cui non esiste un criterio di ottimalità.

9. macromodelli(per tutta la famiglia)

10. micromodelli(singoli collegamenti o processi dell'economia).

Tipi di modelli matematici: lineari, non lineari, quadratici, interi, discreti, parametrici, lineari frazionari, dinamici, stocastici

4. Enunciato generale dei problemi di programmazione matematica.

Considera l'affermazione generale del problema della programmazione matematica.

Il problema generale della programmazione matematica è determinare il valore ottimale della funzione obiettivo, e i valori delle variabili devono appartenere a un certo intervallo di valori ammissibili. Matematicamente, la definizione della soluzione ottima si esprime nel trovare l'estremo (max o min) di una funzione di molte variabili

Z = f(x1, x2, …, xn)

nel dato intervallo di cambiamento di queste variabili

gi (x1, x2,…, xn)Ribi (i = 1, 2,…, m),

dove Ri è uno dei segni ≥, =, ≤.

5. Il problema dell'ottimizzazione del piano di produzione. Formulazione economica e costruzione di un modello matematico dei problemi.

Contesto economico:

L'azienda produce N tipi di prodotti che utilizzano M tipi di materie prime. Per la produzione di un'unità di produzione viene utilizzata una quantità rigorosamente definita di materie prime di un tipo o dell'altro. Le materie prime di ogni tipo nell'impresa sono limitate. L'azienda riceve un certo profitto dalla vendita di un'unità di produzione. È necessario trovare un tale piano di produzione in cui l'impresa riceverà il massimo profitto totale.

Ambiente matematico:

Sia j l'indice del tipo di prodotto j = 1, n

i - indice del tipo di risorsa i = 1, m

e ij sono i costi delle materie prime io-esimo tipo per la produzione di un'unità di produzione J-esimo tipo;

Аi è un dato limite sul volume disponibile di risorse del tipo i-esimo;

Pj - profitto ricevuto dalla vendita di un'unità di produzione del tipo j-esimo;

xj è il volume di output del tipo j-esimo.

z \u003d P1x 1 + P2x 2 + ... + Pnx n → max

a11x 1 + a12x 2 +…+ a1nx n ≤ A1

a21x 1 + a22x 2 +…+ a2nx n ≤ A2

…………………………….

a m1x1 + a m2x2 +…+ a m n x n ≤ Am

xj ≥ 0, j = 1, n

6. Il compito della dieta. Formulazione economica e costruzione di un modello matematico del problema.

Contesto economico

Alcune fattorie danno da mangiare agli animali. Utilizzato per l'ingrasso N tipi di alimentazione. Il contenuto di nutrienti (calcio, fosforo, ecc.) è noto per unità di mangime di ciascuna specie. Per una corretta alimentazione degli animali, è necessario consumare sostanze nutritive non inferiori alle quantità specificate. Il costo unitario di ciascun feed è noto. È necessario determinare la dieta dell'alimentazione degli animali, in cui il costo totale dell'ingrasso sarà minimo.

Ambiente matematico:

j è l'indice del tipo di feed, j = 1, n

i – indice del tipo di nutriente, i = 1, m

Аi è l'apporto giornaliero richiesto dell'i-esimo tipo di nutriente;

Сj è il costo di un'unità di alimentazione del tipo j-esimo.

Introduciamo le variabili sconosciute:

хj - volume giornaliero di alimentazione animale j-esima vista poppa.

In termini di notazione introdotta dato compito sarà scritto dopo

a11x1 + a12x2 +…+ a1nxn ≥ A1

a21x1 + a22x2 +…+ a2nxn ≥ A2

…………………………….

am1x1 + am2x2 +…+ e mnxn ≥Am

xj ≥ 0, j = 1, n

7. Attività di trasporto . Formulazione economica e costruzione di un modello matematico del problema.

Contesto economico :

Disponibile M fornitori di prodotti omogenei e N consumatori di questo prodotto. Costi unitari noti per la consegna di un'unità di produzione da ciascun fornitore a ciascun consumatore. Le scorte dei fornitori sono limitate. Sono note anche le esigenze dei prodotti di ciascun consumatore.

È necessario determinare un tale piano per il trasporto di prodotti dai fornitori ai consumatori, in cui il costo totale del trasporto sarà minimo.

Ambiente matematico :

Introduciamo la notazione impostare i parametri:

j – indice dei consumatori, j = 1, n

i – indice fornitore, i = 1, m

Аi è il volume dei prodotti disponibili presso l'i-esimo fornitore;

Bj - il volume della domanda per i prodotti del j-esimo consumatore;

Cij è il costo unitario del trasporto di un'unità di prodotto dall'i-esimo fornitore al j-esimo consumatore.

Introduciamo le variabili sconosciute:

хij è il volume di trasporto dei prodotti dall'i-esimo fornitore al j-esimo consumatore.

z = С11x11 + С12x12 +…+С1nx1n + С21x21 +…+ Сm(n -1)xm (n-1) + Сmnxmn → min

Restrizioni del compito.

I. Da ciascun fornitore puoi ritirare prodotti non superiori alla quantità disponibile:

x11 + x12 +…+ x1n ≤ A1

x21 + x22 +…+ x2n ≤ A2 (2)

…………………….

xm1 + xm2 +…+ xmn ≤ Am

II. Il bisogno di ogni consumatore per i prodotti deve essere soddisfatto

x11 + x21 +…+ xm1 ≥B1

x12 + x22 +…+ xm2 ≥B2

……………………. (3)

x1n + x2n +…+ xmn ≥Bn

III. Condizione di non negatività: xij ≥0, i = 1, m ; j = 1, n

Spesso è conveniente scrivere l'enunciato matematico in forma ripiegata:

, io = 1, m , j = 1, n

8. Il problema della scelta di incarichi o incarichi. Formulazione economica e costruzione di un modello matematico del problema.

Contesto economico :

Disponibile N tipi di lavoro e N esecutori. Ciascuno degli artisti può eseguire qualsiasi, ma solo un lavoro. Viene stabilito il costo dell'esecuzione di ogni opera da parte di ciascun esecutore. È necessario assegnare gli artisti a lavorare in modo tale che il costo totale per il completamento del lavoro sia minimo.

Ambiente matematico .

Introduciamo la notazione per i parametri dati.

i – indice delle opere, i = 1, m

j è l'indice degli esecutori, j = 1, n

Cij è il costo dell'esecuzione dell'i-esimo lavoro da parte del j-esimo esecutore.

Introduciamo le variabili sconosciute. In questo problema, le variabili sconosciute possono assumere solo due valori, 0 o 1. Tali variabili sono chiamate variabili nulle.

1 - se il j-esimo esecutore è assegnato all'i-esimo lavoro;

0 - altrimenti.

In termini di notazione introdotta, questo problema può essere scritto come segue:

z = С11x11 + С12x12 +…+С1nx1n + С21x21 …+ С(n-1)(n-1)x(n-1)(n-1) + Сnnxnn → min

I gruppo di restrizioni.

Ad ogni opera deve essere assegnato un solo esecutore:

x11 + x12 +…+ x1n = 1

x21 + x22 +…+ x2n = 1

……………………..

xn1 + xn2 +…+ xnn = 1

II. gruppo di restrizione.

Ogni esecutore può eseguire un solo lavoro:

x11 + x21 +…+ xn1 = 1

x12 + x22 +…+ xn2 = 1

……………………..

x1n + x2n +…+ xnn = 1

x ij = ( 0,1) io = 1, n ; j = 1, n

9. Il problema del taglio dei materiali. Formulazione economica e costruzione di un modello matematico del problema.

Contesto economico .

La materia prima della stessa dimensione viene fornita per il taglio. È necessario tagliarlo in spazi vuoti di una determinata dimensione in una determinata quantità, in modo che lo spreco totale sia minimo.

Ambiente matematico .

Introduciamo la notazione:

i è l'indice degli spazi vuoti,

Аi - il numero richiesto di spazi vuoti dell'i-esimo tipo;

j - indice delle opzioni di taglio,

Cj è la dimensione dei rifiuti durante il taglio di un'unità di materiale iniziale secondo l'opzione j;

e ij è il numero di grezzi dell'i-esimo tipo quando si taglia un'unità di materiale iniziale secondo l'opzione j.

Introduciamo la notazione delle variabili incognite.

xj è la quantità di materia prima tagliata secondo l'opzione j.

In termini di notazione introdotta, questo problema può essere scritto come segue:

z \u003d С1x1 + С2x2 + ... + Сnxn → min

a11x1 + a12x2 +…+ a1nxn = A1

a21x1 + a22x2 +…+ a2nxn = A2

…………………………….

am1x1 + am2x2 +…+ amnxn =Am

xj ≥ 0, j = 1, n

L'utilizzo di modelli matematici consente di risparmiare fino al 20% di materie prime.

Il modello matematico del taglio è costruito in due fasi.

Nella prima fase vengono costruite le opzioni di taglio, a seguito delle quali i valori del numero di opzioni n, il numero di spazi vuoti di ciascun tipo ottenuti con diverse opzioni di taglio (aij), nonché i valori di rifiuti (Cj).

La costruzione delle opzioni per il taglio di un'unità di materiale di partenza viene eseguita nella forma della seguente tabella:

numero di opzione

Vuoto i1

i2 vuoto

vuoto im

Gli spazi vuoti sono disposti in ordine non crescente delle loro dimensioni. La costruzione delle varianti viene eseguita con il metodo dell'enumerazione completa.

10. Forma generale del modello del problema di PL e sue caratteristiche

La forma generale del LLP è:

z \u003d С1x1 + ... + Сnxn max (min)

a11 X1 + a12 X2 + … + a1n Xn R1 a1

a21 X1 + a22 X2 + … + a2n Xn R2 a2

………………………………………………….

am1 X1 + am2 X2 +…+ amnxn Rm am

xj ≥ 0, j = 1, k, k ≤ n

In forma generale, ogni simbolo R1 , R2 ,…, Rm significa uno dei segni: ≥, = o ≤ .

La forma generale del modello del problema LP ha le seguenti caratteristiche.

1. Il sistema di vincoli è presentato sotto forma di equazioni (condizioni rigide) e disuguaglianze (condizioni non rigide).

2. Le condizioni di non negatività non sono imposte a tutte le variabili

3. La funzione obiettivo tende al massimo o al minimo.

11. Forma standard del modello del problema di PL e sue caratteristiche

Il modulo standard è il seguente.

Trova il massimo o il minimo della funzione obiettivo z:

z = С1x1 + … + Сnxn → max (min) (1)

Soggetto alle seguenti restrizioni:

a11 X1 + a12 X2 + … + a1n Xn ≤ a1

a21 X1 + a22 X2 + ... + a2n Xn ≤ a2

…………………………………………..

am1 X1 + am2 X2 +… + amn Xn ≥ am

xj ≥ 0, j = 1, k, k ≤ n

Le caratteristiche della forma standard del modello del problema LP sono le seguenti:

1. il sistema di restrizioni è presentato sotto forma di disuguaglianze (condizioni non rigide)

2. condizioni di non negatività sono imposte a tutte le variabili

3. la funzione obiettivo tende al massimo o al minimo

12. Forma canonica del modello del problema di PL e sue caratteristiche

La forma canonica è:

Trova il minimo della funzione obiettivo z:

z = С1x1 + … + Сnxn → min

Soggetto alle seguenti restrizioni:

a11 X1 + a12 X2 + ... + a1n Xn = a1

a21 X1 + a22 X2 + ... + a2nxn = a2

…………………………

am1x1 + am2 X2 +… + amn Xn = am

Xj ≥0, j = 1, n

Le caratteristiche della forma canonica sono le seguenti:

1. Il sistema di restrizioni è presentato sotto forma di equazioni (condizioni rigorose).

2. Le condizioni di non negatività si applicano a tutte le variabili

3. La funzione obiettivo tende a

In alcune fonti, la funzione oggettiva del problema di PL, presentata in forma canonica, tende al massimo. Questo viene fatto per comodità di risolvere il problema secondo l'algoritmo sviluppato per la massima funzione obiettivo.

13. Piano di attività di base possibile, ammissibile, ottimale, ODZ dell'attività LP

Definizione 1. Vengono chiamati valori di variabili sconosciute che soddisfano tutti i vincoli di un problema di programmazione lineare ammissibile valori variabili o piani .

Definizione 2. L'insieme di tutti i piani per un problema di programmazione lineare è chiamato dominio dei valori ammissibili delle variabili ( ODZ ).

Definizione 3. Si chiama il piano del problema di programmazione lineare, in cui la funzione obiettivo assume il valore minimo (o massimo) sull'ODZ ottimale .

14. Tipi di record di attività LP: espanso, piegato, matrice, vettore.

I modelli di problema LP possono essere scritti in varie forme.

1. Vista espansa del record del modello

Z = c1 X1 + c2 X2 + … + cn Xn → min

a11 X1 + a12 X2 + … + a1n Xn = a1,

a21 X1 + a22 X2 + … + a2n Xn = a2,

……………………………………………

a m1 X1 + am2 X2 + … + amn Xn = am,

Xj ≥ 0, j = 1, n.

2. Vista compressa:

,

Xj ≥ 0, j = 1, n.

3. Modello del problema di PL in forma matriciale:

X ≥ 0

Dove

a11 a12 … a1n X1 a1

A= a21 a22 … a2n , X= X2 , A0 = a2

… … … … … …

am1 am2 … amn X3 am

4. Modello del problema LP in forma vettoriale:

Dove

X1 a11 a12 a1n a1

X2 , a21 , a22 , a2n , a2

… … … … …

Хn am1 am2 am2 am

15. Transizione dalla forma standard e generale dei problemi di PL a quella canonica. Teorema di connessione

Per passare da una forma generale o standard a una canonica si utilizzano le seguenti tecniche.

1. Conversione variabile. Se qualche variabile Xk è non positiva (Xk ≤ 0), allora viene introdotta una nuova variabile Xk ", così che Xk " = –Xk . Ovviamente, Xk " ≥ 0. Dopodiché, in ogni vincolo e funzione obiettivo, la variabile Xk è sostituita da [ – Xk "].

Se qualche variabile Xt può assumere qualsiasi valore, allora viene sostituita dalla differenza di due variabili non negative Xt' e Xt'', cioè si presume che xt = Xt' – Xt'', dove Xt' 0 ≥ e Xt'' ≥ 0.

2. Trasformazione dei vincoli. Se uno qualsiasi dei vincoli nel modello ha la forma di una disuguaglianza, viene convertito in uguaglianza aggiungendo (se la disuguaglianza è di tipo ≤) o sottraendo (se la disuguaglianza è di tipo ≥) dal suo lato sinistro. Queste variabili sono chiamate variabili di equilibrio. Le variabili di equilibrio sono incluse nella funzione obiettivo con zero coefficienti. La variabile balance assume il valore dell'indice in sequenza dopo quelli già esistenti. Se, ad esempio, il sistema di restrizioni ha 5 variabili, la prima variabile di saldo sarà X6 e la seconda X7, ecc.

16. Transizione dalla forma canonica del modello ZLP allo standard

Per passare dalla forma canonica alla forma standard, ciascuna di

equazioni da sostituire con un sistema di disequazioni:

Un altro modo è portare il sistema di equazioni in una forma speciale ed eliminare ulteriormente alcune variabili.

Utilizzando il metodo Jordan-Gauss, selezioniamo la variabile di base in ciascuna equazione. Tale selezione viene effettuata con l'ausilio di trasformazioni gaussiane (elementari) equivalenti. Questi includono:

a) moltiplicazione di qualsiasi equazione per una costante diversa da zero;

b) aggiunta a qualsiasi equazione di qualsiasi altra equazione, moltiplicata per qualsiasi costante.

È conveniente scrivere il sistema iniziale di equazioni lineari prima della trasformazione sotto forma di matrice o tabella:

Scriviamo il problema in forma standard.

17. Il concetto di un iperpiano di un semipiano, un iperpiano di supporto.

18. Geometrico. interpretazione del sistema di vincoli e della funzione obiettivo nei problemi di PL

19. Insieme convesso: punti estremi (angolo) dell'insieme. Poliedro convesso

Definizione Un insieme M si dice convesso se, assieme a due punti qualsiasi appartenenti a dato insieme, contiene anche un segmento che li collega.

insieme convesso

Definizione Un punto x di un insieme M si dice angolo o punto estremo se non è interno ad alcun segmento che appartiene interamente all'insieme dato.

Teorema 1. Qualsiasi punto di un segmento può essere rappresentato come una combinazione convessa dei suoi vertici.

x \u003d λ 1 A + λ 2 B

λ 1 , λ 2 ≥ 0 combinazione convessa dei vertici A e B

λ1 + λ2 = 1

Teorema 2. Qualsiasi punto di un insieme chiuso convesso può essere rappresentato come una combinazione convessa dei suoi vertici.

20. Algoritmo del metodo grafico per la risoluzione di problemi di PL

1. Viene verificato se l'LPP originale è nel modulo standard, in caso contrario, l'attività deve essere convertita nel modulo standard.

2. Viene controllato il numero di variabili sconosciute. Se questo numero è superiore a tre, il problema non può essere risolto con un metodo grafico (esistono altri metodi efficaci per risolvere tali problemi).

3. La regione dei valori ammissibili delle variabili per ZLP è in costruzione.

4. Si sta costruendo un vettore guida C .

5. L'isocel iniziale viene tracciato attraverso l'ODZ (perpendicolare al vettore di direzione).

6. Viene eseguito il movimento mentale dell'isocele iniziale nella direzione del vettore C, se viene determinato il valore massimo della funzione obiettivo, o in direzione opposta, se viene determinato il suo valore minimo, fino a quando l'isoobiettivo diventa un riferimento all'ODZ. I punti di intersezione dell'isocoel di riferimento e dell'ODZ saranno i punti ottimali del problema.

7. Per determinare le coordinate del punto ottimale, è necessario risolvere il sistema di equazioni lineari corrispondenti.

8. Per trovare il valore ottimale della funzione obiettivo, è necessario sostituire i valori ottimali delle variabili nella funzione obiettivo e calcolarne il valore.

20. algoritmo grafico. Metodo di risoluzione dei problemi LP

Algoritmo del metodo grafico.

1. Per costruzione successiva di ciascuna delle condizioni del sistema di vincoli del problema, viene eseguita la costruzione dell'ODZ.

2. Il vettore direttivo C è costruito dai coefficienti per le variabili della funzione obiettivo.

3. L'isocoel iniziale è tracciato perpendicolarmente al vettore di direzione attraverso l'origine.

4. L'isoobiettivo iniziale viene spostato mentalmente nella direzione dei valori crescenti del vettore C, se viene determinato il valore massimo della funzione obiettivo, o nella direzione opposta, se viene determinato il suo valore minimo, fino a quando l'isoobiettivo diventa un riferimento all'ODZ. I punti di intersezione dell'isocoel di riferimento e dell'ODZ saranno i punti ottimali del problema.

5. Per determinare le coordinate del punto ottimale, è necessario risolvere il sistema di equazioni lineari corrispondenti di quelle condizioni all'intersezione delle quali si trova il punto ottimale.

6. Per trovare il valore ottimo della funzione obiettivo, è necessario sostituire le coordinate del punto ottimale nella funzione obiettivo e calcolarne il valore.

23. teoremi sull'intervallo di valori ammissibili del problema di PL e sulla funzione obiettivo

Il teorema ODZ. Il dominio delle soluzioni ammissibili del problema di PL è un insieme convesso (chiuso e limitato nello spazio n-dimensionale)

Teorema 2. Sulla funzione obiettivo di un problema di programmazione lineare.

La funzione obiettivo LLP assume il suo valore ottimale in uno dei punti d'angolo della regione dei valori accettabili delle variabili. Se la funzione obiettivo assume il suo valore ottimale in diversi punti d'angolo, assume lo stesso valore in qualsiasi punto che sia una combinazione convessa di questi punti d'angolo.

24. Il teorema sul vertice. Sufficiente e condizione necessaria

25. Corollari dal teorema sulle proprietà delle soluzioni ai problemi di PL e conclusioni. Il concetto di linea di base.

Conseguenze dai teoremi.

Definizione. Piano = (х1,х2,…,хn), le cui coordinate positive corrispondono a vettori linearmente indipendenti, è chiamato piano di base PLP .

Conseguenza 1. Il piano di riferimento non ha più di m coordinate positive.

Se ha esattamente m coordinate positive, un tale progetto di supporto è chiamato non degenere, altrimenti degenere.

Conseguenza 2. Ogni punto d'angolo ODZ è il piano di base.

27. Algoritmo del metodo del simplesso.

Quando si risolvono problemi di LP con il metodo simplex, è necessario eseguire la seguente sequenza di azioni.

1. Viene verificato se il problema LP è in forma canonica. In caso contrario, è necessario convertire il modello originale in una forma canonica.

2. Il piano di riferimento iniziale e il valore della funzione obiettivo sono selezionati per questo piano di riferimento.

3. Viene costruita la tabella simplex iniziale.

4. Vengono controllati i valori delle stime di ottimalità nella linea dell'indice. Se non ci sono stime positive, viene scritta la soluzione ottimale e l'algoritmo termina il suo lavoro. In caso contrario, il punto 5 è soddisfatto.

5. Nella base viene introdotto un vettore, che corrisponde alla massima stima positiva. Questa colonna è chiamata colonna di abilitazione.

6. Un vettore è derivato dalla base, che corrisponde al rapporto simplex calcolato dalla formula 0< Ө ≤ . Linea data chiamato la stringa di abilitazione.

7. Viene creata una nuova tabella simplex. Le colonne B e C B vengono modificate di conseguenza.Il resto della tabella viene riempito dalla precedente utilizzando trasformazioni gaussiane, con la riga dell'indice considerata come m+1 righe e anch'essa trasformata utilizzando trasformazioni gaussiane. Procediamo all'implementazione del paragrafo 4 di questo algoritmo.

Dopo aver costruito ciascuna tabella, è possibile verificare la correttezza dei calcoli utilizzando le formule per il calcolo delle stime riportate nel paragrafo precedente.

28. Scelta di una base e costruzione di un primo piano di riferimento per la risoluzione di problemi con il metodo del simplesso.

29. Tabelle Simplex, loro riempimento. Formule per il calcolo dei coefficienti di riga dell'indice.

30 . Il teorema di ottimalità per il piano di un problema di programmazione lineare è una conseguenza del teorema di stima dell'ottimalità per la risoluzione di problemi con il metodo del simplesso.

Teorema 1: If per qualche vettore  j nel sistema

X 1 + a 1 m +1 X m +1 + a 1 m +2 X m +2 + ... + a 1 n X n \u003d a 1

X 2 + a 2 m +1 X m +1 + a 2 m +2 X m +2 + ... + a 2 n X n \u003d a 2

…………………………………………………..

X m + a mn +1 X m +1 + a mn +2 X m +2 + ... + a mn X n = a m

La relazione Z j – c j > 0 è soddisfatta, allora il piano X B0 non è ottimale ed è possibile passare al piano X B1 tale che Z (X B1) ≤ Z (X B0).

Qui Z j = (С, À j) è il prodotto scalare di vettori.

C è un vettore costituito da coefficienti alle variabili di base della funzione obiettivo Z

 j è un vettore costituito dai coefficienti di espansione del corrispondente vettore in termini di vettori di base.

c j è il coefficiente della funzione obiettivo Z con variabile X j

Conseguenza da teoremi: Se per tutti i vettori  1 ,  2 , …,  n di qualche piano di riferimento Х la relazione Z j – c j< 0, то опорный план Х является оптимальным. Величины (Z j – c j) – называются оценками оптимальности соответствующих векторов.

Pertanto, il teorema e il corollario ci consentono di stabilire se il prossimo piano di supporto è ottimale e, in caso contrario, è necessario passare a un altro piano di supporto, in cui il valore della funzione obiettivo sarà inferiore.

Commento. Il teorema e il corollario presuppongono che il problema sia in forma canonica con una funzione obiettivo minima. Tuttavia, il metodo del simplesso può essere utilizzato anche per risolvere problemi con una funzione obiettivo massima. In questo caso, quando si analizzano i valori delle stime, viene utilizzato il loro significato opposto, ovvero il piano sarà ottimale se tutte le stime di ottimalità sono non negative (positive o negative).

31. Scelta di un vettore che entra nella base e deriva dalla base. Relazione simplex.

Per passare a un nuovo piano di riferimento, è necessario uno dei vettori liberi entra nella base e restituisce alcuni dei vettori di base. Per introdurre nella base, scegliamo un vettore che abbia almeno una coordinata positiva. Sia il vettore A m+1 un tale vettore.

decomposizione -

resp. vettore, gatto. sarà un piano di riferimento se le sue coordinate sono non negative e il numero di coordinate positive sarà uguale a m.

Le coordinate del vettore X1 devono essere non negative, ovvero .

Se , allora questa coordinata sarà non negativa.

Si ottenga il minimo nella relazione (5) in i =1, allora se prendiamo

quindi la prima coordinata del vettore 1 X diventerà zero.

Viene chiamata la relazione (6). relazione simplex. Pertanto, ci siamo spostati dalla linea di base originale 0 X(vettori base A1, A2, ... Am) al piano di riferimento 1 X(vettori base А2,А3,…,Аm, Am+1).

32. elemento permissivo della tavola, la sua scelta. Regola di eliminazione completa di Jordan per il ricalcolo della tabella simplex.

33. Regola del quadrilatero per il ricalcolo delle tabelle simplex

34. Un segno dell'unicità del piano ottimale, dell'insieme dei piani ottimali e dell'assenza di un piano ottimale quando si risolve il problema LP con il metodo del simplesso.

Quando si risolvono problemi con il metodo del simplesso, sono possibili i seguenti tipi di soluzioni ottimali:

1. Unicità . Se le stime di tutti i vettori liberi sono strettamente negative, allora il progetto di supporto ottenuto è ottimale e unico. (vedi l'esempio nel paragrafo precedente).

2. Ottimo alternativo (insieme di soluzioni ottime).

Se tra le stime non positive dei vettori liberi vi è almeno una stima nulla, allora il disegno di supporto ottenuto sarà ottimale, ma non l'unico. In questo caso si può passare ad altri piani di appoggio (vengono introdotti nella base i vettori che corrispondono a stime nulle) e, quindi, scrivere la soluzione ottima generale come combinazione convessa dei piani di appoggio ottimi ottenuti.

3. LLP non ha una soluzione ottima, poiché la funzione obiettivo non è limitata dal basso . Se la tabella simplex ha un punteggio positivo e tutti gli elementi data colonna sono negativi e nulli, allora dato vettore possono essere inclusi nella base. Tuttavia, nessuno dei vettori di base può essere dedotto dalla base. Ne consegue che è possibile un'ulteriore diminuzione della funzione obiettivo quando si passa a un piano non di supporto.

4. LLP non ha una soluzione ottima, poiché il sistema dei vincoli è incoerente. Poiché quando si risolve l'LLP, il solito metodo del simplesso dovrebbe essere il piano di riferimento iniziale, il sistema di equazioni lineari non è certamente incoerente. Pertanto, un caso del genere non può verificarsi quando si risolve con il solito metodo del simplesso.

5. Se l'ODZ è costituito da un punto, la soluzione di tale problema è banale e può essere ottenuta senza utilizzare il metodo del simplesso.

35. Quando viene utilizzato il metodo della base artificiale?

artificiale.

36. Costruzione del problema M nel metodo della base artificiale

Se il problema di programmazione lineare è in forma canonica, tuttavia, non tutte le equazioni contengono variabili di base, cioè non esiste una linea di base originale. In questo caso, in quelle equazioni in cui non ci sono variabili di base, è necessario aggiungere qualche variabile non negativa con un coefficiente di +1. Tale variabile è chiamata artificiale.

Una variabile artificiale deve essere aggiunta alla funzione obiettivo con un numero positivo molto grande (poiché la funzione obiettivo è trovare il minimo). Questo numero è indicato Lettera latina M. Può essere considerato uguale a +∞. A questo proposito, a volte il metodo della base artificiale è chiamato metodo M. Tale trasformazione del problema originario è detta costruzione del problema esteso. Se stai risolvendo un problema con una funzione obiettivo per trovare una variabile artificiale, devi aggiungere alla funzione obiettivo un numero positivo molto grande (poiché la funzione obiettivo è trovare il minimo). Questo numero è indicato dalla lettera latina M. Può essere considerato uguale a +∞. A questo proposito, a volte il metodo della base artificiale è chiamato metodo M. Tale trasformazione del problema originario è detta costruzione del problema esteso. Se un problema viene risolto con una funzione obiettivo per trovare il massimo, allora le variabili artificiali entrano nella funzione obiettivo con un coefficiente -M.

Quindi, nel problema esteso, abbiamo una linea di base (sebbene alcune delle variabili di base siano artificiali).

Viene costruita la tabella simplex iniziale.

37. costruzione di una linea di indice nel metodo della base artificiale

Viene costruita una tabella simplex iniziale, in cui la riga dell'indice è divisa in due righe, poiché le stime sono costituite da due termini. La riga superiore contiene il termine della stima senza M, la riga inferiore mostra i coefficienti in M. Il segno della stima è determinato dal segno del coefficiente in M, indipendentemente dal valore e dal segno del termine senza M, poiché M è un numero positivo molto grande.

Pertanto, per determinare il vettore introdotto nella base, è necessario analizzare la linea dell'indice inferiore. Se un vettore artificiale è derivato dalla base, la colonna corrispondente nelle successive tabelle simplex può essere omessa se non è necessario ottenere una soluzione al problema duale (vedere l'argomento successivo).

Dopo che tutti i vettori artificiali sono stati tolti dalla base, la riga inferiore avrà tutti elementi zero, ad eccezione delle stime corrispondenti ai vettori artificiali. Saranno uguali a -1. Tale linea può essere rimossa dalla considerazione e l'ulteriore soluzione può essere eseguita con il solito metodo del simplesso, se non è necessario ottenere una soluzione al problema duale (vedere l'argomento successivo).

38. Criterio di ottimalità nel metodo delle basi artificiali. Il segno è la costruzione del piano di base iniziale del compito originario.

39. Algoritmo del metodo dual simplex

Algoritmo del metodo dual simplex:

1. compilare la prima tabella simplex nel solito modo, indipendentemente dai segni dei membri liberi. Si ritiene che un tale problema dovrebbe avere una base unitaria iniziale.

2. Seleziona la linea guida dal più grande elemento negativo assoluto della colonna di membri liberi A0

3. La colonna guida viene selezionata in base al valore assoluto più piccolo del rapporto tra gli elementi della linea dell'indice e gli elementi negativi della linea guida.

4. Ricalcolare la tabella del simplesso secondo la regola delle eliminazioni complete di Jordan

5. verificare l'ammissibilità del progetto ricevuto. Un segno dell'ottenimento di un piano di riferimento accettabile è l'assenza di elementi negativi nella colonna A0. Se ci sono elementi negativi nella colonna A0, vai al secondo paragrafo. Se non ce ne sono, procedono a risolvere il problema nel solito modo.

6. Un segno dell'ottenimento di una soluzione ottima con il metodo del simplesso duale è il criterio di ottimalità per il metodo del simplesso ordinario.

41. Modelli di trasporto aperti e chiusi. Transizione da un modello di trasporto aperto a uno chiuso.

Tipi di attività di trasporto.

Disponibile M fornitori di prodotti omogenei con scorte note di prodotti e N consumatori di questi prodotti con determinati volumi di bisogni. Sono noti anche i costi unitari di trasporto.

Se la somma dei volumi delle scorte di prodotti è uguale al volume dei bisogni di tutti i consumatori, viene chiamato un tale problema compito di trasporto chiuso

(cioè se ∑ Ai = ∑ Bj), altrimenti si chiama il problema del trasporto aprire. Per risolvere il problema del trasporto, è necessario che sia chiuso.

Un'attività di trasporto aperta può essere convertita in un'attività chiusa nel modo seguente.

Sia ∑Ai > ∑Bj. In questo caso, è necessario introdurre un consumatore fittizio n + 1 con un volume di bisogni ∑Ai – ∑Bj I costi unitari per il trasporto dai fornitori al consumatore fittizio sono assunti pari a 0, poiché di fatto tale trasporto non sarà effettuato e una parte dei prodotti rimarrà presso i fornitori.

Se ∑Bj > ∑Ai . In questo caso è necessario introdurre un fornitore fittizio m + 1 con volume di inventario ∑Bj – ∑Ai . Si presume che i costi unitari di trasporto da un fornitore fittizio ai consumatori siano pari a 0, poiché in realtà tale trasporto non verrà effettuato e i consumatori non riceveranno alcuni dei prodotti.

42. Metodi per costruire la distribuzione iniziale nel problema del trasporto: metodo dell'angolo nord-ovest e metodo dell'elemento minimo nella matrice.

Tecnica nordoccidentale per la costruzione di un piano di riferimento. Secondo questa tecnica, la formazione dei valori di traffico inizia con la s.-z. angolo del tavolo, ad es. dalla cella x11. Secondo questo metodo, prima di tutto, vengono distribuiti i beni del primo fornitore. Inoltre, il primo fornitore prima soddisfa il più possibile il primo consumatore. Quindi, se il fornitore ha ancora la merce,

Il metodo dell'elemento più piccolo nella matrice.

L'essenza del metodo sta nel fatto che nella cella viene sempre inserita la massima offerta possibile, che corrisponde alla tariffa più bassa della matrice.

Innanzitutto, segniamo (ad esempio, con il segno ▼) in quelle celle delle linee in cui si osserva il prezzo più basso per la linea. Quindi giriamo intorno alla tabella per colonne e prendiamo le stesse note nelle celle in cui il prezzo più basso è per colonne.

L'ulteriore distribuzione viene prima effettuata il più possibile su celle con due segni, quindi - con uno, quindi il problema viene ribilanciato in (m + n - 1) riempimenti. Organizziamo i ripieni passando il tavolo da sinistra a destra e dall'alto verso il basso.

43. Proprietà delle attività di trasporto

Il problema del trasporto ha alcune proprietà che possono essere riflesse nei seguenti teoremi.

Teorema 1. Un problema di trasporto chiuso ha sempre una soluzione.

Teorema 2. Se il volume delle scorte di prodotti e il volume dei bisogni sono interi, anche la soluzione del problema del trasporto sarà intera.

Teorema 3. il sistema di vincoli di un problema di trasporto chiuso è sempre linearmente dipendente.

Da questo teorema segue che la distribuzione di un problema di trasporto chiuso ha sempre m + n – 1 variabili di base e (m – 1) (n – 1) variabili di tempo libero.

44. Distribuzione degenerata nei problemi di trasporto, eliminando la degenerazione. Combinazione barrata.

La distribuzione è detta degenere se il numero di celle è minore di m + n - 1.

45. Teoremi di ottimalità per il problema del trasporto.

Teorema. Se per una certa distribuzione del compito di trasporto tu

le condizioni sono soddisfatte:

UN). ui+vj = cij per celle occupate

B) ui+vj ≤ ñij, per celle libere,

allora questa distribuzione è ottimale.

I valori ui sono chiamati potenziali di riga e i valori vj sono chiamati potenziali di colonna.

46. ​​​​Potenziali e metodi del loro calcolo.

Per trovare i potenziali di righe e colonne si utilizza il seguente ragionamento, basato sulla condizione a) del teorema di ottimalità.

Il numero di equazioni basate su questa condizione è m + n – 1, e il numero di incognite ui e vj è m + n. Quello. il numero di variabili è maggiore del numero di equazioni e tutte le equazioni sono linearmente indipendenti. La soluzione di un tale sistema di equazioni lineari è indefinita, quindi a uno dei potenziali deve essere assegnato un valore qualsiasi. In pratica ui = 0. Si ottiene un sistema di m + n – 1 equazioni con m + n – 1 incognite. Questo sistema può essere risolto con qualsiasi metodo. In pratica, per calcolare i potenziali, si considerano le celle occupate, per le quali si conosce un loro potenziale, e in base alla condizione a) del teorema, si calcolano i valori dei restanti potenziali sconosciuti.

47. Calcolo delle stime dell'ottimalità della distribuzione dei compiti di trasporto e del criterio di ottimalità.

Sulla base della relazione b) del teorema, possiamo scrivere la seguente formula per il calcolo delle stime: δ ij= ui + vj – ñij. Per non confondere le stime con i volumi di traffico, esse (le stime) sono racchiuse tra cerchi.

Le stime di ottimalità nelle cellule TK libere sono un criterio di ottimalità che controlla l'ottimalità della distribuzione. Se le stime di tutte le celle libere sono minori o uguali a zero, allora questa distribuzione è ottimale.

48. ridistribuzione delle forniture nel problema dei trasporti

Se la distribuzione non è ottimale, è necessario ridistribuire le forniture.

Per la ridistribuzione, viene creato un ciclo di ricalcolo. La cella con il punteggio positivo più alto viene selezionata come cella. Questa cella è contrassegnata da un segno "+", ovvero è necessario registrare una certa quantità di consegna al suo interno. Ma poi l'equilibrio in questa colonna sarà disturbato, quindi una delle celle occupate di questa colonna deve essere contrassegnata con un segno "-", ovvero il volume dell'offerta dovrebbe essere ridotto della stessa quantità. Ma poi il saldo per questa linea cambierà, quindi, alcune celle occupate di questa linea devono essere contrassegnate con un segno "+". Questo processo continua fino a quando il segno "-" non viene inserito nella riga in cui si trovava la cella originale.

Per ogni cella libera esiste un ciclo di ricalcolo e, inoltre, l'unico.

49. catene di ridistribuzione, loro tipi.

Lascia che il piano di trasporto in esame non sia ottimale, ad es. ci sono stime relative positive. Quindi viene presa una cella sfavorevole (una di quelle sfavorevoli) e per essa viene costruito un ciclo di ricalcolo, in base al quale viene quindi ridistribuito il trasporto pianificato. Il ciclo è costruito sotto forma di una linea spezzata chiusa, i cui segmenti corrono lungo la colonna o lungo la linea. In uno degli angoli della linea tratteggiata c'è una cella sfavorevole che rivendica il prodotto, e negli altri angoli le celle sono piene, ad es. quando si costruisce un ciclo, si parte dalla cella candidata e si ritorna ad essa lungo una linea tratteggiata, ma si possono fare giri solo in celle piene (corrispondenti alle variabili di base). Lascia che una cella sfavorevole rivendichi il prodotto Q. Per evitare uno squilibrio nella tabella, è necessario

sommare e sottrarre Q al traffico disponibile. Poiché esiste un numero pari di angoli, Q verrà aggiunto in metà delle celle e sottratto nell'altra metà. Il ciclo viene avviato in senso orario o antiorario a partire dalla cella candidata, posizionando lì il buon Q, quindi Q viene sottratto dalla cella vicina, quindi aggiunto e così via. Il valore di Q stesso viene scelto in modo che una delle celle venga svuotata, ma nessuna delle scorte diventi negativa.

Per fare ciò, Q deve essere scelto uguale al più piccolo riducibile delle celle in cui Q è sottratto. Nella seguente fig. 7.1 e 7.2 mostreremo esempi di cicli e la regola di calcolo.

In questo caso, vengono svuotate due celle. Ma è necessario che solo una cella diventi reciprocamente vuota. Fanno questo: una delle celle di svuotamento viene resa vuota nella nuova tabella e zero viene inserito nell'altra cella di svuotamento. Questa cella è considerata di base (riempita) nella nuova tabella.

50. La scelta del volume di redistribuzione.

Determinazione del volume dei prodotti trasportati. Nel determinare il volume dei prodotti spostati attraverso il ciclo di conteggio, dobbiamo procedere dalle seguenti due considerazioni:

a) dopo la trasformazione nelle celle della tabella non si devono ottenere numeri negativi;

b) una delle celle occupate deve liberarsi.

Affinché queste condizioni siano soddisfatte, è necessario selezionare il volume dei prodotti trasportati come segue: θ=min (хij) -, dove (хij) è il volume del trasporto dalle celle del ciclo di ricalcolo contrassegnato con “ -" cartello.

θ = min(20;30)=20

θ viene aggiunto ai valori delle celle contrassegnate da un segno "+". θ viene sottratto dai valori delle celle contrassegnate con un segno "-". Il valore di fornitura delle restanti celle viene sovrascritto senza modifiche. Di conseguenza, otteniamo la seguente tabella.

53. Algoritmo del metodo dei potenziali.

Algoritmo:

1. Controlla se l'equazione è soddisfatta per l'attività in caso contrario, viene inserito nell'incarico un fornitore o un consumatore fittizio

2. La condizione dell'attività è scritta sotto forma di transport.table

3. Si sta costruendo una linea di base iniziale

4. Si determinano i potenziali di approvvigionamento e consumatori

5. Vengono calcolati i punteggi delle celle libere. Se non sono tutti negativi, il piano è ottimale e devi scrivere la risposta. La matrice di trasporto X e determinare l'ammontare dei costi di trasporto. Se il piano non è ottimale, ad es. tra le stime ce ne sono di negative, scegli una cella promettente con il valore negativo più grande. stimare e passare in grandezza al successivo.

6. Caricare una cella prospettica. Prepara un nuovo piano di base sotto forma di un tavolo di trasporto. Vai al punto 4.

54. Contabilizzazione dei costi di produzione e trasporto dei prodotti. Attività di trasporto con divieti di approvvigionamento.

Quando si risolvono alcuni problemi, è necessario tenere conto dei costi non solo per il trasporto delle merci, ma anche per la produzione dei prodotti trasportati. Per fare ciò, nella matrice trasp. compiti

Dove Cij ' è il costo ridotto di produzione di un'unità di output.

Cij “- il costo del trasporto di un'unità di produzione.

Compiti con divieti di approvvigionamento.

In alcune situazioni non è possibile trasportare i prodotti su nessuna tratta.

Per fare ciò, nella matrice dell'attività di trasporto, il trasporto attraverso il quale è vietato, viene inserita una tariffa proibitiva M. Inoltre, l'attività viene risolta nel solito modo, tuttavia questa cella corrisponderà sempre a un punteggio di cella negativo.

55. tenendo conto delle restrizioni sul throughput delle rotte, tenendo conto della natura obbligatoria di alcune consegne nel problema del trasporto.

tenere conto delle restrizioni sul throughput delle rotte.

In alcune attività di trasporto, su alcuni percorsi, uno più piccolo portata di quanto è necessario per soddisfare la domanda del punto di consumo.

tenendo conto della natura obbligatoria di alcune consegne nel problema del trasporto.

In alcuni casi, l'incarico richiede che, ad esempio, lungo il percorso Ak Bs, debba essere effettuata la consegna in unità di volume A. In questo caso la fornitura obbligatoria viene detratta dal volume di produzione del punto A e dal volume S Bs e il problema è risolto rispetto alla fornitura facoltativa. Dopo aver ottenuto la soluzione ottimale, l'offerta viene necessariamente aggiunta al volume presente nella cella Ak Bs.

56. Possibili conclusioni economiche. interpretazione della distribuzione ottima per problemi di trasporto aperti.

Al ricevimento della distribuzione ottimale, è necessario tornare al problema originale e rendere l'appropriato economico. conclusioni. Sono i seguenti:

1. L'introduzione di un punto di consumo significa che nel sistema analizzato sono presenti volumi di produzione eccessivi ed è possibile, fermo restando il sistema considerato, ridurre le capacità di tali punti di produzione della quantità di vincolante che sono legati al punto fittizio di consumo.

2. Se viene introdotto un punto di produzione fittizio, ciò significa che le capacità dei punti di produzione reali non sono sufficienti e devono essere aumentate. Viene incrementata la capacità dei punti di produzione più vicini ai punti di consumo legati al punto di produzione fittizio. La capacità del produttore è aumentata del valore vincolante. Per fare ciò, considera la colonna del punto di consumo, che è legato al punto di produzione fittizio, e trova la tariffa più bassa in essa. È più efficiente aumentare la capacità del punto di produzione corrispondente a questa tariffa dell'importo del legame.

57. Il concetto di dualità. Formulazione economica di problemi duali sull'esempio del problema dell'ottimizzazione del piano di produzione.

Il problema duale è un problema ausiliario della programmazione lineare formulato utilizzando determinate regole direttamente dalle condizioni del problema originale o diretto.

Lascia che ci sia un compito di ottimizzare il piano di produzione. Sembra così:

Compito iniziale:

a 11 x 1 + a 12 x 2 +…+ a 1p x p ≤v 1 | 1

a 21 x 1 + a 22 x 2 +…+ a 2p x p ≤v 2 | alle 2

……………….. |.. (1)

UN T 1 x 1 +a T 2 x 2 + ... + a T n x n ≤ v 1 | A T

x j ≥0, j = 1,n(2)

z = c 1 x 1 +c 2 x 2 +…+c n x n ->max(3)

X \u003d (x 1, x 2, ..., x n)

a ij - il numero di materie prime dell'i-esimo tipo, spese per la produzione del j-esimo tipo di prodotto

Doppio problema

Lascia che l'impresa per qualsiasi motivo non sia in grado di produrre prodotti. Per ridurre il costo dei tempi di inattività, l'azienda può vendere le materie prime di cui dispone. A quale prezzo dovrebbero essere vendute le materie prime?

i - il prezzo dell'i-esimo tipo di materia prima disponibile presso l'impresa.

a 11 y 1 + a 21 y 2 + ... + a T 1 anno T≥s 1

a 12 x 1 + a 22 y 2 + ... + a T 2 x n ≥s 2

……………….. (1’)

UN 1p si 1 +a 2p si 2 +…+ a tp A T≥s P

i ≥0, j = 1,m(2’)

F = b 1 y 1 +b 2 y 2 +…+b m y m ->min(3’)

58. Corrispondenza tra gli elementi strutturali dei problemi diretti e duali

Ogni problema di programmazione lineare può essere associato

duplice compito secondo le seguenti regole:

1. In tutti i vincoli del problema originario, i termini liberi devono

essere a destra e termini con incognite a sinistra.

2. I vincoli-disuguaglianze del problema originario devono avere segni,

diretto in una direzione.

3. Se la funzione obiettivo nel problema originario è minimizzata, i vincoli di disuguaglianza vanno scritti con il segno "≤", allora nel problema duale la funzione obiettivo sarà minimizzata ei segni dei vincoli di disuguaglianza saranno "≥".

4. Ogni vincolo del problema originale corrisponde a una variabile in

duplice compito. Se una variabile corrisponde a una disuguaglianza, è non negativa, se corrisponde a un'uguaglianza, allora la variabile è senza restrizioni sul segno ("arbitraria").

5. I coefficienti delle variabili nei vincoli del problema duale si ottengono trasponendo la matrice composta da

coefficienti per le variabili del problema originale.

6. I termini liberi del problema originale sono i coefficienti a

variabili nella funzione obiettivo del problema duale e libere

termini nel problema duale sono i coefficienti delle variabili in

funzioni del problema originale Notiamo anche che la relazione di dualità è reciproca, cioè il compito duale rispetto a quello duale coincide con quello originario Le coppie duali di compiti si dividono in simmetriche e asimmetriche. In una coppia simmetrica, i vincoli dei problemi primale e duale sono disuguaglianze non strette e, pertanto, le variabili di entrambi i problemi possono assumere solo valori non negativi.

59. Costruzione di problemi duali ai problemi originali scritti nella forma standard, canonica e generale del modello (costruzione di problemi duali simmetrici e asimmetrici)

Modulo standard (originale)

Σ a ij x j ≤ b io , i=1,n(1)

xj ≥0, j=1,n(2)

z = Σ c j x j ->max(3)

Doppio standard

Σ a ij y i ≤ c j , j=1,n(1)

yi ≥0, j=1,m(2)

F = Σ b io y io ->min(3)

Il problema originale in forma canonica:

Σ a ij x j = b io , i=1,m(1)

xj ≥0, j=1,n(2)

z = Σ c j x j ->min(3)

Doppio canonico

Σ a ij y i ≤ c j , j=1,n(1)

si io - qualsiasi (2)

F = Σ b io y io ->max(3)

Diamo un'interpretazione economica di un paio di problemi duali. Consideriamo il problema dell'uso razionale delle risorse. Lascia che l'impresa disponga delle risorse b1,b2,…bm che possono essere utilizzate per produrre n-tipi di prodotti. Conosciamo anche il costo unitario del j-tipo di prodotto cj (j=1,n) e il tasso di consumo della risorsa i-esima (i=1,m) per la produzione unità j-esima prodotti - aij. È necessario determinare il volume di produzione di ciascun tipo xj (j=1,n), massimizzando il costo totale

f= c1x1+…+cnxn (1)

Allo stesso tempo, il consumo di risorse non dovrebbe superare la loro disponibilità:

a11x1+…+a1nxn<=b1 }

…………………….. } (2)

am1x1+…+amnxn<=bm }

Tutti noti nel loro senso economico sono non negativi:

Xj>=0 (j=1,n). (3)

Si noti che questo problema forma un problema duale simmetrico.

Problemi duali asimmetrici.

Portiamo la ZLP al massimo nella forma canonica:

Max Z=(n;j=1)Σcj*xj

(n;j=1)Σaij*xj=bi (i=1,m)

Xj>=0 (j=1,n).

60. Principale e secondo teorema di dualità (indicare i teoremi e spiegare)

Il primo teorema di dualità.

Teorema: se uno dei problemi duali ha un piano ottimo, allora l'altro è risolvibile, cioè ha un piano opt. In questo caso i valori estremi delle funzioni obiettivo coincidono (j=da 1 a n) Σcjxj*= (i=da 1 a m)Σbiyi* se nell'originale. problema la funzione obiettivo è illimitata sull'insieme dei piani, allora nel problema duale il sistema dei vincoli è inconsistente.

Secondo teorema di dualità e sua interpretazione economica.

Affinché le soluzioni ammissibili di una coppia di problemi duali siano ottime, è necessario e sufficiente che sia soddisfatta la seguente condizione: xj*(∑aij yi*-cj)=0, j da 1 a n, yi*( ∑aij xj*-bi)=0, I da 1 a m. Queste sono condizioni di allentamento complementare. Ne consegue: se qualsiasi restrizione del problema duale viene convertita dal piano ottimale in rigorosa uguaglianza, allora il componente corrispondente dell'opt. piano del problema duale dovrebbe essere uguale a zero Se qualche componente opt. plan è uguale a zero, allora la corrispondente restrizione del problema duale è convertita dall'opt.plan in un'uguaglianza stretta xj*>0, quindi (i= da 1 a m)Σaij yi*=cj opt.plan, allora se costi>prezzi, volume di produzione=0 Σaij yi* >cj quindi xj*=0

yi*>0 quindi (j=da 1 a n) Σaij xj*=bi (razze di risorse = stock di risorse).

(j=1 an) Σaij xj*

Il significato del teorema è il seguente:

Se la stima del costo del consumo di risorse per la produzione di un'unità di prod-ii \u003d prezzo, allora questo tipo di prod-ii è incluso nel piano ottimale;

Se i costi superano il prezzo, allora il prod-yu non dovrebbe essere prodotto;

Se consumo di risorse = scorte, la stima del costo di questa risorsa è positiva. Una tale risorsa è chiamata scarsa. Il più carente.res-s ha il punteggio più alto;

Se la risorsa non è completamente spesa, allora la sua stima dei costi = 0.

61. Costruzione del piano di appoggio ottimo per il problema duale a partire dalla tavola del simplesso del problema originario

Informazioni dalle colonne della matrice inversa delle trasformazioni lineari che hanno portato al risultato ottimale. Le colonne della matrice D-1 forniscono informazioni molto utili.

Colonna A3: il prezzo "ombra" della risorsa S2 è y01=0, la colonna rimane

singolo e dalla prima riga si legge che x3=9, cioè quando si implementa il piano ottimale trovato, la prima risorsa sarà in eccesso e questo eccesso (sottoutilizzo) ammonterà solo a 9 unità convenzionali.

Colonna A4: il prezzo "ombra" della risorsa S2 è pari a y02=1, la risorsa sarà completamente utilizzata e il suo eventuale aumento porterà ad un aumento della funzione obiettivo (ie reddito). E perché y02=1, allora l'aumento della risorsa S2 di 1 c.u. darà un'aggiunta in termini di reddito di.Z = y02· .w2 = = 1.1 = 1 (mille UAH) (qui.w2 è l'incremento della risorsa S2 e .Z è il corrispondente incremento del reddito). Con tale incremento della risorsa S2, il reddito massimo sarà già Zmax=58mila UAH. + 1 mila UAH = 59 mila UAH. Sulla fig. 6.2 illustra questa situazione, il cui commento verrà fornito di seguito. Dalla colonna A4 risulta anche che con un incremento della risorsa S2 di 1 c.u. per il nuovo punto ottimale, la produzione dei beni T1 diminuirà di ½ tonnellata (all'intersezione della riga della variabile di base x1 e della colonna A4 è "-1/2"), e la produzione dei beni T2 aumenterà di 3 /2 tonnellate (perché nella riga con la variabile base x2 nella colonna A4 abbiamo "3/2". Quanto detto sulla colonna A4 verrà commentato in seguito mediante costruzioni grafiche (Fig. 6.2). Colonna A5: l'"ombra " il prezzo della risorsa S3 è pari a y03=2. Ciò significa che un aumento della risorsa S3 di 1 c.u. porterà un'addizione in Z to.Z = y03 · .v3 = 2.1 =2(mille grivna) e sarà Zmax=58 mila grivna. + 2mila UAH = 60mila UAH. Allo stesso tempo, come segue dalla colonna A5 della tabella. 3, la produzione di T1 aumenterà di ½ tonnellata e T2 diminuirà di ½ tonnellata. Lo stock di materie prime S1 (vedi rigo 1) aumenterà di 3/2 c.u.

62. L'idea del metodo di programmazione dinamica e la sua interpretazione geometrica. Principio di ottimalità di Bellman.

La soluzione ottima del problema con il metodo della programmazione dinamica si trova sulla base dell'equazione funzionale

Per definirlo occorre:

1. annotare l'equazione funzionale per l'ultimo stato del processo (corrisponde a l \u003d n-1)

fn-1(Sl-1)=ottimale(Rn(Sn-1,Un)+f0(Sn))

2. trovare Rn(Sn-1,Un) da un insieme discreto dei suoi valori per alcuni Sn-1 e Un fissi dalle corrispondenti aree ammissibili (poiché f0(Sn)=0, allora f1(Sn-1)= ottimo(Rn(Sn-1,Un)

Di conseguenza, dopo il primo passo, si conosce la soluzione Un e il corrispondente valore della funzione f1(Sn-1)

3. Diminuire il valore di l di uno e annotare l'equazione funzionale corrispondente. Per l=n-k (k= 2,n) sembra

fk(Sn-k)=ottimale(Rn-k+1(Sn-k,Un-k+1)+fk-1(Sn-k+1)) (2)

4. trovare una soluzione condizionatamente ottimale basata sull'espressione (2)

5. verificare a quanto è uguale il valore di l Se l=0, il calcolo delle soluzioni condizionalmente ottimali è completato e si trova la soluzione ottima del problema per il primo stato del processo. Se l non è uguale a 0, vai al passaggio 3.

6. Calcolare la soluzione ottimale del problema per ogni fase successiva del processo, passando dalla fine dei calcoli all'inizio.

Il metodo del dinamismo dei programmi consente di sostituire un problema con molte variabili con un numero di problemi successivamente risolti con un numero minore di variabili. La decisione viene presa passo dopo passo. Il principio principale su cui si basa l'ottimizzazione di un processo a più fasi, nonché le caratteristiche del metodo computazionale, è il principio di ottimalità di Bellman.

Il comportamento ottimo ha la proprietà che qualunque siano lo stato iniziale e la decisione iniziale, le decisioni successive devono essere ottimali rispetto allo stato risultante dalla decisione iniziale.

Matematicamente, è scritto come espressione della forma:

fn-1(Sl)=ottimale(Rl+1(Sl,Ul+1)+fn-(l+1)(Sl+1)) (1)

(l=0,n-1)Ottimo nell'espressione indica il massimo o il minimo a seconda della condizione del problema.

63. Requisiti per problemi risolti con il metodo DP

La programmazione dinamica è un metodo matematico per trovare soluzioni ottimali a problemi in più passaggi. Un processo in più fasi è un processo che si sviluppa nel tempo e si scompone in una serie di passaggi o fasi.

Una delle caratteristiche del metodo di programmazione dinamica è che le decisioni prese in relazione a processi a più fasi non sono considerate come un singolo atto, ma come un intero complesso di decisioni correlate. Questa sequenza di decisioni interconnesse è chiamata strategia.L'obiettivo della pianificazione ottimale è scegliere una strategia che fornisca il miglior risultato in termini di un criterio preselezionato. Tale strategia è chiamata ottimale.

Un'altra importante caratteristica del metodo è l'indipendenza dalla preistoria della decisione ottimale presa nella fase successiva, cioè su come il processo da ottimizzare ha raggiunto il suo stato attuale. La soluzione ottimale viene scelta solo tenendo conto dei fattori che caratterizzano il processo al momento.

Il metodo dei programmi dinamici è anche caratterizzato dal fatto che la scelta della soluzione ottimale ad ogni passo dovrebbe essere fatta tenendo conto delle sue conseguenze nel futuro. Ciò significa che durante l'ottimizzazione del processo in ogni singolo passaggio, in nessun caso dovresti dimenticare tutti i passaggi successivi.

64. Formulazione economica e costruzione di un modello matematico del problema risolto con il metodo DP (sull'esempio del problema della distribuzione degli investimenti di capitale). Relazione di ricorrenza di Bellman.

Spieghiamo preliminarmente che il metodo di programmazione dinamica si applica principalmente a quei problemi in cui il processo (o la situazione) da ottimizzare è dispiegato nello spazio o nel tempo, o in entrambi.

Lascia che il processo (situazione) stesso sia così complicato che non c'è modo di ottimizzarlo utilizzando metodi noti. Quindi, secondo il metodo della programmazione dinamica, un processo COMPLESSO (operazione, situazione) viene suddiviso (partizionato) in una serie di fasi (passi). Questa rottura è in molti casi naturale, ma nel caso generale è introdotta artificialmente. . Ad esempio, quando si considera una partita a scacchi, qualsiasi mossa di ciascuno dei giocatori serve solo

suddividere l'intero lotto in passaggi separati (fasi). E in un'operazione militare per inseguire un missile contro un altro, l'intero processo continuo deve essere suddiviso artificialmente in fasi, ad esempio ogni secondo di osservazione. Il metodo di programmazione dinamica consente di sostituire l'ottimizzazione dell'intero processo complesso con l'ottimizzazione condizionale per ciascuna delle fasi

(fasi) seguita dalla sintesi del controllo ottimale dell'intero processo. Allo stesso tempo, il metodo prevede che l'ottimizzazione condizionale in una fase separata (fase) venga eseguita nell'interesse, prima di tutto, dell'intera operazione.

Tutti i calcoli che consentono di trovare il valore ottimale dell'effetto ottenuto in n passaggi, fn(S0), vengono eseguiti secondo la formula (1), che è chiamata equazione di Bellman funzionale di base o relazione di ricorrenza. Quando si calcola il valore successivo della funzione fn-1, viene utilizzato il valore della funzione fn-(l+1) ottenuto nel passaggio precedente e il valore diretto dell'effetto Rl+1(Sl,Ul+1), raggiunto come risultato della scelta della soluzione Ul+1 per un dato stato dei sistemi Sl. Il processo di calcolo del valore della funzione fn-1(l=0,n-1)

Viene eseguito nella condizione iniziale naturale f0(Sn)=0, il che significa che al di fuori dello stato finale del sistema, l'effetto è nullo.

65. Il problema della distribuzione degli investimenti di capitale (esempio).

Per risolvere il problema della distribuzione ottimale degli investimenti di capitale, utilizzeremo l'equazione funzionale di Bellman. Per prima cosa, utilizzando la situazione più semplice, illustreremo la derivazione dell'equazione funzionale di Bellman, quindi, utilizzando un esempio, dimostreremo come utilizzare questa equazione per risolvere il problema che ci interessa.

Cominciamo con la distribuzione ottimale degli investimenti di capitale assegnati nella quantità di K tra due imprese. I dipartimenti di pianificazione delle imprese, sulla base dei loro calcoli, hanno formato le funzioni reddituali q(x) per l'impresa P1 e h(x) per l'impresa P2. Queste funzioni indicano che se la prima o la seconda impresa riceve un investimento pari a x, allora la prima impresa

si riceverà il reddito q(x), e il secondo h(x), e il valore di x potrà assumere valori discreti continui o noti da 0 a K.

Quindi, lascia che la società P1 abbia allocato investimenti di capitale per l'importo x, quindi alla società P2 viene assegnato l'importo K - x. In questo caso, il reddito q(x) sarà percepito dalla prima impresa e h(K - x) dalla seconda. Se gli investimenti K sono stati allocati per un periodo di pianificazione, allora il reddito totale delle due imprese sarà R(K, x) = q(x) + h(K - x). Ovviamente, x e, di conseguenza, K - x devono essere scelti in modo tale che R(K, x) assuma il suo valore massimo, che indichiamo con F(K):

Questa voce è come uno scheletro per voci più complete.

equazione funzionale di Bellman. COMPLICARE il nostro compito distribuendo gli investimenti di capitale su due periodi di pianificazione (due fasi) . Si decida inizialmente di destinare l'importo x alla prima impresa P1 e x alla seconda impresa P1. In generale, il reddito sarebbe pari a R(K, x) = q(x) +

h(K-x). Se teniamo presente che gli investimenti sono distribuiti su 2 periodi (2 fasi), nella prima impresa il saldo degli investimenti sarà x, dove , e nella seconda - .(K - x), dove Di conseguenza, il reddito per il il secondo periodo sarà q( .x) - secondo la prima struttura e h[.(K - x)] - secondo la seconda. L'ottimizzazione della programmazione dinamica, di norma, inizia dalla fase finale. Partiamo quindi dalla seconda fase, indicando F1 il massimo reddito possibile da due imprese nella seconda

palcoscenico. Ottenere

Quindi, all'ultima fase considerata (nel nostro caso, la seconda), in un certo senso aggiungiamo la fase precedente (nel nostro caso, la prima) e troviamo il reddito massimo delle due fasi insieme:

Allo stesso modo, per n stadi, otteniamo

dove Fn-1 è la funzione obiettivo che dà il miglior risultato per le ultime (n - 1) fasi. L'equazione di Bellman funzionale risultante è ricorrente, cioè associa il valore Fn al valore Fn-1.

Più in generale, l'equazione di Bellman ha la forma

dove , Fn-1 - reddito massimo per (n - 1) ultime fasi, Fn -

reddito massimo per tutte le n fasi.

66. Il concetto di risoluzione di problemi di programmazione non lineare

Poniamo il problema della programmazione non lineare nella seguente forma generale: trova tali valori delle variabili x1, x2, ..., xn che soddisfano le condizioni:

e portare l'estremo richiesto (massimo o minimo) della funzione obiettivo

f = f(x1, x2,…, xn), (13.2)

dove f(х1, …, хn) e qi(х1, …, хn) (m , 1 i =) sono reali non lineari,

funzioni regolari di n variabili reali.

Secondo le loro proprietà generali, i problemi di programmazione non lineare possono

significativamente diverso da quelli lineari. Ad esempio, il dominio delle soluzioni ammissibili può già essere non convesso e l'estremo della funzione obiettivo può essere osservato in qualsiasi punto del dominio ammissibile. Anche i metodi per risolvere problemi non lineari differiscono in modo significativo. Consideriamo solo alcuni approcci per risolvere questi problemi.

Innanzitutto l'approccio grafico è valido anche per risolvere i problemi più semplici della programmazione non lineare. Quindi, se le variabili x1 e x2 sono gli argomenti del problema, prima viene costruita l'area delle soluzioni ammissibili sul piano di queste variabili, quindi viene determinato il punto ottimale nell'area utilizzando i livelli della funzione obiettivo f(x1,x2).

Nella programmazione non lineare, un approccio gradiente viene utilizzato per risolvere molti problemi. Esistono numerosi metodi del gradiente, la cui essenza è trovare il risultato ottimale utilizzando il gradiente della funzione obiettivo, un vettore che indica la direzione del massimo aumento dell'obiettivo per il punto considerato. Nel caso generale, la procedura di ricerca viene eseguita in modo iterativo dal punto selezionato inizialmente ai punti con l'indicatore migliore. Lasciamo, per esempio, . - dominio delle soluzioni ammissibili

problema considerato, e il processo iterativo dei calcoli parte dal punto

Inoltre, prima viene effettuata una transizione lungo il gradiente della funzione obiettivo, quindi un ritorno all'area. lungo il gradiente fino al confine disturbato della regione O2 O3. 13.3 è mostrato in modo che Ai con indici dispari appartengano all'area., mentre i punti Ai con indici pari no.Quando ci avviciniamo al punto ottimo Q, le direzioni dei gradienti di lavoro convergono. Pertanto, il criterio ideale per arrestare il processo sarà la collinearità del gradiente target e del gradiente di confine interrotto.

67. Il concetto di programmazione parametrica e intera .

Enunciato e modello matematico di ZCLP.

Nei problemi con oggetti indivisibili, le condizioni intere sono imposte alle variabili. A volte queste condizioni si applicano a tutte le variabili, a volte ad alcune variabili.Si consideri un problema completamente intero

f=(n,j=1)∑CjXi max

(n,j=1)∑AijXj=bi, i=1,m

xi-intero,j=1,n

Ora, a differenza del problema di programmazione lineare generale, il piano ottimo non sarà necessariamente al vertice del poliedro del piano.Ci sono i seguenti metodi per risolvere i problemi interi:

1. Metodi di ritaglio

2.Combinatorio

3.Metodi approssimati..

La programmazione parametrica è una branca della programmazione matematica dedicata allo studio di problemi di ottimizzazione in cui le condizioni di ammissibilità e la funzione obiettivo dipendono da alcuni parametri deterministici.

Definizione. Programmazione lineare (PL) - la scienza dei metodi di ricerca e la ricerca di valori estremi (massimi e minimi) di una funzione lineare, sulle incognite di cui sono imposte restrizioni lineari.

Questa funzione lineare è chiamata bersaglio, e vengono chiamati vincoli che sono scritti matematicamente come equazioni o disuguaglianze sistema di restrizioni.

Definizione. Viene chiamata l'espressione matematica della funzione obiettivo e dei suoi vincoli modello matematico del problema economico.

In generale, il modello matematico di un problema di programmazione lineare (PL) è scritto come

con limitazioni:

Dove x j- sconosciuto; aij, b io, cj sono date delle costanti.

Tutte o alcune equazioni del sistema di vincoli possono essere scritte come disuguaglianze.

Il modello matematico in una notazione più breve ha la forma

con limitazioni:

Definizione. Una soluzione ammissibile (piano) di un problema di programmazione lineare è un vettore = ( X 1 , X 2 ,..., xp), soddisfacendo il sistema di restrizioni.

L'insieme delle soluzioni ammissibili forma la regione delle soluzioni ammissibili (ODD).

Definizione. Una soluzione ammissibile, in cui la funzione obiettivo raggiunge il suo valore estremo, è detta soluzione ottima del problema di programmazione lineare ed è indicata con opt.

Soluzione di base ammissibile (X 1 , X 2 ,...,X R , 0, …, 0) è una soluzione di riferimento, dove R- il rango del sistema di vincoli.

Il modello matematico del problema di PL può essere canonico e non canonico.

7. Risoluzione di problemi di programmazione lineare con metodo grafico. Grafici delle funzioni di vincolo. Linee di livello.

Metodo grafico per risolvere problemi di programmazione lineare

Il metodo più semplice e più visivo della programmazione lineare è il metodo grafico. Viene utilizzato per risolvere problemi di PL con due variabili date in forma non canonica e molte variabili in forma canonica, purché contengano non più di due variabili libere.

Da un punto di vista geometrico, in un problema di programmazione lineare, si cerca un tale punto d'angolo o un insieme di punti da un insieme ammissibile di soluzioni in cui si raggiunge la linea di livello più alta (più bassa), situata più lontano (più vicino) rispetto alla altri nella direzione della crescita più rapida.

Per trovare il valore estremo della funzione obiettivo nella soluzione grafica dei problemi di PL, viene utilizzato il vettore l() in superficie X 1 OH 2 , che indichiamo . Questo vettore mostra la direzione del cambiamento più veloce nella funzione obiettivo. In altre parole, il vettore è la normale della linea di livello l()

Dove e 1 e e 2 - vettori unitari lungo gli assi BUE 1 e BUE 2 rispettivamente; quindi = (∂L/∂х 1 , ∂L/∂х 2 ). Le coordinate del vettore sono i coefficienti della funzione obiettivo L(). La costruzione della linea di livello sarà considerata in dettaglio quando si risolvono problemi pratici.

Algoritmo per la risoluzione dei problemi

1. Troviamo l'area delle soluzioni ammissibili per il sistema di vincoli del problema.

2. Costruire un vettore .

3. Disegna una linea di livello l 0 , che è perpendicolare .

4. Spostiamo la linea di livello nella direzione del vettore per le attività al massimo e nella direzione opposta , per compiti minimi.

La linea di livello viene spostata fino ad avere un solo punto in comune con l'area delle soluzioni ammissibili. Questo punto, che determina l'unica soluzione del problema di PL, sarà il punto estremo.

Se risulta che la linea di livello è parallela a uno dei lati dell'ODT, in questo caso l'estremo viene raggiunto in tutti i punti del lato corrispondente e il problema LP avrà un numero infinito di soluzioni. Si dice che abbia un tale problema di LP ottimo alternativo e la sua soluzione è data dalla formula:

Dove 0 ≤ T≤ 1, 1 e 2 - soluzioni ottimali ai punti d'angolo dell'ODS.

Un problema di PL può essere irrisolvibile quando i vincoli che lo definiscono si rivelano contraddittori.

5. Troviamo le coordinate del punto estremo e il valore della funzione obiettivo in esso.

Esempio 3 Scegliere la migliore opzione di rilascio del prodotto

L'azienda produce 2 tipi di gelato: alla crema e al cioccolato. Per la produzione del gelato vengono utilizzati due prodotti iniziali: il latte e le farciture, i cui costi per 1 kg di gelato e forniture giornaliere sono riportati in tabella.

Le ricerche di mercato hanno dimostrato che la domanda giornaliera di gelato al burro supera la domanda di gelato al cioccolato, ma di non più di 100 kg.

Inoltre, è stato riscontrato che la domanda di gelato al cioccolato non supera i 350 kg al giorno. Il prezzo al dettaglio di 1 kg di gelato cremoso è di 16 rubli, cioccolato - 14 rubli.

Quanto di ciascun tipo di gelato dovrebbe produrre l'azienda per massimizzare i suoi ricavi di vendita?

Soluzione. Denota: X 1 - volume giornaliero di produzione di gelato cremoso, kg; X 2 - produzione giornaliera di gelato al cioccolato, kg.

Facciamo un modello matematico del problema.

I prezzi del gelato sono noti: 16 rubli e 14 rubli, rispettivamente, quindi la funzione obiettivo sarà simile a:

Stabilisci dei limiti sul latte per il gelato. Il suo consumo per il gelato alla crema è di 0,8 kg, per il gelato al cioccolato - 0,5 kg. Stock di latte 400kg. Pertanto, la prima disuguaglianza sarà:

0.8x 1 + 0.5x 2 ≤400 - la prima disuguaglianza è una restrizione. Le altre disuguaglianze sono costruite in modo simile.

Il risultato è un sistema di disuguaglianze. qual è l'area della soluzione di ciascuna disuguaglianza. Questo può essere fatto sostituendo le coordinate del punto O(0:0) in ciascuna delle disuguaglianze. Di conseguenza, otteniamo:

Figura OABDEF- dominio delle soluzioni ammissibili. Costruiamo il vettore (16; 14). linea di livello l 0 è dato dall'equazione 16x 1 +14x 2 =Cost. Scegliamo un numero qualsiasi, ad esempio il numero 0, quindi 16x 1 +14x 2 =0. Nella figura, per la retta L 0 viene scelto un numero positivo, diverso da zero. Tutte le linee di livello sono parallele tra loro. Il vettore normale della linea di livello.

Sposta la linea di livello nella direzione del vettore. punto di uscita l 0 dalla regione delle soluzioni ammissibili è il punto D, le sue coordinate sono definite come l'intersezione delle rette date dalle equazioni:

Risolvendo il sistema, otteniamo le coordinate del punto D(312.5; 300), in cui ci sarà una soluzione ottima, cioè

Pertanto, l'azienda deve produrre 312,5 kg di gelato al burro e 300 kg di gelato al cioccolato al giorno, mentre il reddito dalle vendite sarà di 9.200 rubli.

8. Riduzione di un problema di programmazione lineare arbitrario al problema principale. Conversione di vincoli dati da disuguaglianze in equazioni corrispondenti.

9.Metodo del simplesso. Caratteristiche e algoritmo del metodo, sua applicabilità.

Per risolvere il problema con il metodo del simplesso, è necessario:

1. Indicare un metodo per trovare la soluzione di riferimento ottimale

2. Specificare il metodo di transizione da una soluzione di riferimento a un'altra, su cui il valore della funzione obiettivo sarà più vicino all'ottimale, ad es. indicare un modo per migliorare la soluzione di riferimento

3. Stabilire criteri che consentano di interrompere tempestivamente l'enumerazione delle soluzioni di riferimento sulla soluzione ottimale o passare una conclusione sull'assenza di una soluzione ottimale.

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

1. Portare il problema alla forma canonica

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

3. Calcola le stime delle espansioni vettoriali in termini della base della soluzione di riferimento e compila la tabella del metodo del simplesso

4. Se il criterio per l'unicità della soluzione ottima è soddisfatto, la soluzione del problema termina

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

10. Attività di trasporto. Definizione, tipi, metodi per trovare la soluzione iniziale del problema del trasporto.

Il problema del trasporto è uno dei più comuni problemi di programmazione lineare. Il suo obiettivo è sviluppare i modi e i mezzi più razionali per trasportare le merci, eliminando i trasporti eccessivamente lunghi, in arrivo e ripetuti.

1. Trovare la soluzione di riferimento iniziale;

2. Verifica dell'ottimalità di questa soluzione;

3. Transizione da una soluzione di base a un'altra.

Lezione 2

IN forma canonica

soluzione ammissibile del PLP(piano accettabile).

soluzione ottima del LLP.

Necessità

Esempio.

Scriviamo il problema forma canonica

Situazioni particolari della soluzione grafica della ZLP

Tranne quando il compito è l'unica soluzione ottimale per e , può essere situazioni speciali:

1. compito ha un numero infinito di soluzioni ottimali – si raggiunge l'estremo della funzione sul segmento ( ottimo alternativo)- Figura 2;

2. compito non risolvibile a causa dell'illimitatezza dell'ODR, o - Figura 3;

3. ODR - punto singolo Ah, allora;

4. compito non risolvibile se l'ODR ha un'area vuota.

UN

Figura 2 Figura 3

Se la linea di livello è parallela al lato dell'area delle soluzioni ammissibili, l'estremo viene raggiunto in tutti i punti del lato. Il problema ha un numero infinito di soluzioni ottime: ottimo alternativo . La soluzione ottima si trova con la formula

dove è il parametro Per qualsiasi valore compreso tra 0 e 1, puoi ottenere tutti i punti del segmento, per ciascuno dei quali la funzione assume lo stesso valore. Da qui il nome: ottimo alternativo.

Esempio. Risolvere graficamente il problema di programmazione lineare ( ottimo alternativo):

Domande per l'autocontrollo

1. Scrivi il problema della programmazione lineare in forma generale.

2. Scrivere il problema della programmazione lineare in forma canonica e standard.

3. Quali trasformazioni possono essere utilizzate per passare dalla forma generale o standard di un problema di programmazione lineare a quella canonica?

4. Dare una definizione di soluzioni ammissibili e ottime al problema della programmazione lineare.

5. Quale delle soluzioni è la “migliore” per il problema di minimizzare la funzione if ?

6. Quale delle soluzioni è la “migliore” per il problema di massimizzare la funzione if ?

7. Scrivere la forma standard del modello matematico di un problema di programmazione lineare con due variabili.

8. Come costruire un semipiano dato da una disuguaglianza lineare a due variabili ?

9. Come si chiama la soluzione di un sistema di disuguaglianze lineari con due variabili? Costruire sul piano il dominio delle soluzioni ammissibili di un tale sistema di disequazioni lineari, che:

1) ha una soluzione unica;

2) ha un insieme infinito di soluzioni;

3) non ha soluzione.

10. Scrivi per una funzione lineare gradiente vettoriale, denominare il tipo di linee di livello. Come si trovano le linee del gradiente e del livello l'una rispetto all'altra?

11. Formulare un algoritmo per un metodo grafico per risolvere un LLP standard con due variabili.

12. Come trovare le coordinate e i valori della soluzione, ?

13. Costruire l'area delle soluzioni ammissibili, gradiente e rette di livello, per problemi di programmazione lineare in cui:

1) è raggiunto in un unico punto, e - sul segmento ODR;

2) è raggiunto in un unico punto dell'ODS, e .

14. Fornire un'illustrazione geometrica del LLP se:

1) ha soluzioni ottime uniche per e ;

2) ha un insieme di soluzioni ottime per .

Lezione 2

Metodo grafico per trovare la soluzione ottima

1. Forme di modelli matematici lineari e loro trasformazione

2. Metodo grafico per la risoluzione di un problema di programmazione lineare

3. SITUAZIONI PARTICOLARI DELLA SOLUZIONE GRAFICA DI LLP

4. Soluzione grafica di problemi economici di programmazione lineare

Forme di modelli matematici lineari e loro trasformazione

Un modello matematico di un problema di programmazione lineare (LPP) può essere scritto in una delle tre forme.

IN forma generale del modello matematicoè necessario trovare il massimo o il minimo della funzione obiettivo; il sistema di vincoli contiene disuguaglianze ed equazioni; non tutte le variabili possono essere non negative.

IN forma canonica il modello matematico deve trovare il massimo della funzione obiettivo; il sistema di vincoli consiste solo di equazioni; tutte le variabili sono non negative.

Nella forma standard di un modello matematico, è necessario trovare il massimo o il minimo di una funzione; tutti i vincoli sono disuguaglianze; tutte le variabili sono non negative.

Si chiama la soluzione del sistema di vincoli che soddisfa le condizioni di non negatività delle variabili soluzione ammissibile del PLP(piano accettabile).

Si chiama l'insieme delle soluzioni ammissibili l'area delle soluzioni ammissibili del LLP.

Viene chiamata una soluzione ammissibile, in cui la funzione obiettivo raggiunge un valore estremo soluzione ottima del LLP.

Le tre forme del LLP sono equivalenti nel senso che ciascuna di esse può essere ridotta a una forma diversa con l'aiuto di trasformazioni matematiche.

Necessità transizione da una forma di modello matematico a un'altra associato a metodi per la risoluzione di problemi: ad esempio, il metodo del simplesso, ampiamente utilizzato nella programmazione lineare, viene applicato a un problema scritto in forma canonica e il metodo grafico viene applicato alla forma standard di un modello matematico.

Transizione alla notazione canonica ZLP.

Esempio.

Scriviamo il problema forma canonica, introducendo una variabile aggiuntiva (di saldo) con il segno “+” nella parte sinistra della prima disuguaglianza del sistema di vincoli, e una variabile aggiuntiva con il segno “meno” nella parte sinistra della seconda disuguaglianza.

Il significato economico di varie variabili aggiuntive può non essere lo stesso: dipende dal significato economico delle restrizioni in cui queste variabili sono incluse.

Quindi, nel problema dell'uso delle materie prime, mostrano il resto delle materie prime, e nel problema della scelta delle tecnologie ottimali, mostrano il tempo inutilizzato dell'impresa che utilizza una certa tecnologia; nel problema del taglio - il rilascio di spazi vuoti di una determinata lunghezza in eccesso rispetto al piano, ecc.