Muoversi dai vincoli di un modello matematico lineare. Creare un modello matematico di un problema di programmazione lineare. Scelta del volume di ridistribuzione

Lezione 2

V forma canonica

decisione accettabile del LPP(piano accettabile).

la soluzione ottimale per il LPP.

Necessitano

Esempio.

Scriviamo il compito forma canonica

Situazioni particolari della soluzione grafica del LPP

Tranne quando il problema ha l'unica soluzione ottimale per e forse situazioni speciali:

1. problema ha numero infinito di soluzioni ottime - si raggiunge l'estremo della funzione sull'intervallo ( ottimo alternativo)- Figura 2;

2.compito non risolvibile a causa dell'illimitatezza dell'IDT, oppure - Figura 3;

3. SDT - punto singolo Ah, allora;

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

UN

Immagine 2 Immagine 3

Se la linea di livello è parallela al lato della regione delle soluzioni ammissibili, l'estremo viene raggiunto in tutti i punti del lato. Il problema ha innumerevoli soluzioni ottimali - ottimo alternativo ... La soluzione ottimale si trova dalla formula

dov'è il parametro Per qualsiasi valore da 0 a 1 è possibile ottenere tutti i punti del segmento, per ognuno dei quali la funzione assume lo stesso valore. Da qui il nome - ottimo alternativo.

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

Domande per l'autocontrollo

1. Annotare un problema di programmazione lineare in forma generale.

2. Scrivete il problema della programmazione lineare nelle forme canoniche e standard.

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

4. Fornire la definizione delle soluzioni ammissibili e ottimali al problema della programmazione lineare.

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

6. Quale delle soluzioni è la “migliore” per il problema della massimizzazione di una funzione, se ?

7. Annotare 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 in due variabili ?

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

1) ha una soluzione unica;

2) ha un numero infinito di soluzioni;

3) non ha un'unica soluzione.

10. Prendi nota per funzione lineare gradiente vettoriale, denominare il tipo di linee di livello. Come sono posizionate le linee del gradiente e del livello l'una rispetto all'altra?

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

12. Come trovare le coordinate ei valori della soluzione?

13. Tracciare l'area delle soluzioni fattibili, linee di pendenza e 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'ODR, e.

14. Fornire un'illustrazione geometrica del LPP, se è:

1) ha le uniche soluzioni ottimali per e;

2) ha molte soluzioni ottimali per.

Lezione 2

metodo grafico trovare la soluzione ottimale

1. Forme dei modelli matematici lineari e loro trasformazione

2. Un metodo grafico per risolvere un problema di programmazione lineare

3. Situazioni particolari della soluzione grafica del LPP

4. Soluzione grafica di problemi economici di programmazione lineare

Forme dei modelli matematici lineari e loro trasformazione

Il modello matematico del problema di programmazione lineare (LPP) può essere scritto in una di tre forme.

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

V forma canonica il modello matematico è necessario per trovare il massimo della funzione obiettivo; il sistema dei vincoli è costituito solo da 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.

Viene chiamata una soluzione ad un sistema di vincoli che soddisfa le condizioni di non negatività delle variabili decisione accettabile del LPP(piano accettabile).

Viene chiamato l'insieme delle soluzioni ammissibili l'area delle soluzioni ammissibili del LPP.

Viene chiamata una soluzione fattibile in cui la funzione obiettivo raggiunge un valore estremo la soluzione ottimale per il LPP.

Le tre forme di scrittura LPP sono equivalenti nel senso che ciascuna di esse può essere ridotta a una forma diversa mediante trasformazioni matematiche.

Necessitano passaggio da una forma di modello matematico a un'altraè associato a metodi di risoluzione dei problemi: ad esempio, il metodo simplex, 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 forma canonica di scrittura ZLP.

Esempio.

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

Il significato economico di varie variabili aggiuntive potrebbe non essere lo stesso: dipende dal significato economico dei vincoli 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 - il tempo inutilizzato dell'impresa per una determinata tecnologia; nel problema del taglio: il rilascio di spazi vuoti di una determinata lunghezza sul piano, ecc.

Definizione. Programmazione Lineare (LP) - la scienza dei metodi di ricerca e trovare i valori estremi (più grandi e più piccoli) di una funzione lineare, le cui incognite sono soggette a vincoli lineari.

Questa funzione lineare viene chiamata obbiettivo, e vengono chiamati i vincoli che sono scritti matematicamente sotto forma di equazioni o disequazioni sistema di restrizioni.

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

V vista generale il modello matematico di un problema di programmazione lineare (LP) è scritto come

con restrizioni:

dove xj- sconosciuto; un ij, b io, cj- dati valori costanti.

Tutte o alcune delle equazioni del sistema di vincoli possono essere scritte sotto forma di disuguaglianze.

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

con restrizioni:

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

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

Definizione. Una soluzione fattibile in cui la funzione obiettivo raggiunge il suo valore estremo è chiamata soluzione ottima al problema di programmazione lineare ed è indicata con opt.

Soluzione praticabile di base (X 1 , X 2 , ..., X R , 0, …, 0) è la soluzione di riferimento, dove R - il rango del sistema di restrizioni.

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

7.Soluzione di problemi di programmazione lineare con metodo grafico... Grafici di vincoli di funzione. Linee di livello.

Un metodo grafico per la risoluzione di problemi di programmazione lineare

Il metodo più semplice ed intuitivo di programmazione lineare è il metodo grafico. Viene utilizzato per risolvere problemi LP con due variabili date in forma non canonica e molte variabili in forma canonica, purché contengano al massimo 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, a cui si raggiunge la linea di livello più alta (più bassa), situata più lontano (più vicino) di gli altri nella direzione della crescita più rapida.

Per trovare il valore estremo della funzione obiettivo nella soluzione grafica di problemi LP, utilizzare il vettore l() in superficie X 1 OH 2 , che indichiamo . Questo vettore mostra la direzione del cambiamento più rapido 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. Trova la regione delle soluzioni fattibili al sistema di vincoli del problema.

2. Costruire un vettore .

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

4. Sposta la linea del livello nella direzione del vettore per le attività al massimo e nella direzione opposta , per i compiti al minimo.

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 al problema LP, sarà il punto estremo.

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

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

Il problema LP può essere irrisolvibile quando i vincoli che lo definiscono si rivelano contraddittori.

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

Esempio 3. Selezione dell'opzione di rilascio del prodotto ottimale

L'azienda produce 2 tipi di gelato: cremoso e al cioccolato. Per la fabbricazione del gelato vengono utilizzati due prodotti iniziali: latte e ripieni, i cui costi per 1 kg di gelato e forniture giornaliere sono riportati nella tabella.

Lo studio del mercato di vendita ha mostrato che la domanda giornaliera di gelato 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. Prezzo al dettaglio di 1 kg di gelato cremoso 16 rubli, cioccolato - 14 rubli.

Quanto gelato di ogni tipo dovrebbe produrre l'azienda per massimizzare il reddito dalla vendita dei prodotti?

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

Facciamo un modello matematico del problema.

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

Stabiliremo dei limiti al latte per il gelato. Il suo consumo per gelato cremoso - 0,8 kg, per cioccolato - 0,5 kg. Brodo di latte 400 kg. Pertanto, la prima disuguaglianza sarà simile a:

0,8x 1 + 0,5x 2 ≤400 - la prima disuguaglianza è una limitazione. Il resto delle disuguaglianze è composto in modo simile.

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

Figura OABDEF - campo delle soluzioni ammissibili. Costruiamo un 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 riga L 0, viene selezionato un certo numero positivo diverso da zero. Tutte le linee di livello sono parallele tra loro. Vettore normale della linea di livello.

Sposta la linea di livello nella direzione del vettore. Punto di uscita l 0 dalla regione delle soluzioni fattibili è il punto D, le sue coordinate sono determinate come intersezione di 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 dovrebbe produrre 312,5 kg di gelato e 300 kg di gelato al cioccolato al giorno, mentre il reddito delle vendite ammonterà a 9.200 rubli.

8. Riduzione di un problema di programmazione lineare arbitraria al problema principale. Converti i vincoli di disuguaglianza nelle equazioni corrispondenti.

9. Metodo semplice... Descrizione e algoritmo del metodo, sua applicabilità.

Per risolvere il problema utilizzando il metodo simplex, è necessario:

1. Indicare un modo per trovare la soluzione di supporto ottimale

2. Indicare il metodo di transizione da una soluzione di supporto all'altra, in corrispondenza della quale il valore della funzione obiettivo sarà più vicino a quello ottimale, ad es. indicare un modo per migliorare la soluzione di supporto

3. Stabilire i criteri che consentono di interrompere tempestivamente la ricerca di soluzioni di supporto sulla soluzione ottimale o di trarre una conclusione sull'assenza di una soluzione ottimale.

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

1. Portare il problema nella forma canonica

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

3. Calcolare le stime delle espansioni vettoriali sulla base della soluzione di supporto e compilare la tabella del metodo simplex

4. Se il criterio dell'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 con una semplice enumerazione si trovano tutte le soluzioni ottime

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

Il problema del trasporto è uno dei problemi di programmazione lineare più comuni. Il suo obiettivo è sviluppare le modalità e i mezzi più razionali per il trasporto delle merci, eliminando le spedizioni eccessivamente lunghe, in arrivo e ripetute.

1. Trovare la soluzione di supporto iniziale;

2. Verifica dell'ottimalità di questa soluzione;

3. Passaggio da una soluzione di supporto all'altra.

3.1. Problema generale di programmazione lineare

Programmazione lineare- questa è la sezione più sviluppata programmazione matematica, con l'aiuto del quale l'analisi e la soluzione di problemi estremi con collegamenti di linea e restrizioni.

La programmazione lineare include una serie di metodi di soluzione euristica (approssimativa) che consentono, in determinate condizioni, di tutto opzioni possibili per scegliere la soluzione migliore e ottimale per i problemi di produzione. Questi metodi includono quanto segue: metodo grafico, simplex, potenziale (metodo di distribuzione modificato - MODI), Hitchkova, Kreko, metodo di approssimazione Vogel e altri.

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

La culla 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 è dedito alla risoluzione dei problemi di trasporto, si può considerare che il Premio Nobel specificato riconosce anche i meriti della scienza dei trasporti russa.

Nel trasporto su strada, i metodi di programmazione lineare sono stati utilizzati sin dagli anni '60 per risolvere un gran numero dei più importanti problemi di produzione, ovvero: ridurre la distanza del trasporto merci; elaborare uno schema di trasporto ottimale; selezione delle vie di movimento più brevi; compiti di trasporto di merci diverse, ma intercambiabili; pianificazione giornaliera del turno; pianificazione del trasporto di merci di piccole dimensioni; distribuzione di autobus su percorsi e altro.

Le caratteristiche del modello di programmazione lineare sono le seguenti:

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

Il numero delle dipendenze è sempre inferiore al numero delle 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) con vincoli del tipo seguente:

Questi vincoli minimizzano (o massimizzano) la funzione obiettivo

La forma standard di scrittura di un modello di programmazione lineare è il sistema equazioni lineari registrato in 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 = b 1;

a 21 x 1 + a 22 x 2 + ... + a 2 n x n = 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

a 11 x 1 + a 12 x 2 + ... + a 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 questo record viene ridotto a canonico forma (3.1) introducendo variabili aggiuntive x n +1> 0 (io=1,2…m) a sinistra della disuguaglianza (o cancellazione del numero di variabili, se il segno di disuguaglianza è diretto nell'altra direzione). Ulteriori variabili costituiscono la base.

La forma standard per risolvere un problema di programmazione lineare è trovare soluzioni a un sistema di equazioni lineari in numeri non negativi che minimizzino la funzione obiettivo. In questo caso, la funzione obiettivo ha la forma

L = s 1 x 1 + s 2 x 2 ... s n x n → min, (3.3)

dove s 1, s 2 ... s n- coefficienti della funzione obiettivo l con variabili X J.

Ulteriori variabili entrano nella funzione obiettivo con coefficienti zero.

Nel caso di massimizzare la funzione obiettivo l i segni delle variabili della funzione obiettivo dovrebbero essere invertiti, e torniamo al problema della minimizzazione, cioè un compito è ridotto a un altro per sostituzione l sul - l o max l= minimo (- l).

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

Si dice ammissibile una soluzione di base in cui le variabili incluse nella base sono non negative.

Una soluzione ottima è una soluzione fattibile che massimizza (o minimizza) la funzione obiettivo (3.3).

Ogni problema di programmazione lineare corrisponde a un altro, chiamato problema di programmazione lineare duale. Il problema originario in relazione al duale si chiama diretto. I problemi diretti e doppi formano una coppia, chiamata doppia coppia nella programmazione lineare. La coppia diretta e doppia formano una coppia asimmetrica quando il problema diretto è scritto in forma canonica e una coppia simmetrica quando le condizioni del problema sono scritte da disuguaglianze.

Le regole per compilare 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 grafoanalitico è uno dei metodi più semplici di programmazione lineare. Rivela chiaramente l'essenza della programmazione lineare, la sua interpretazione geometrica. Il suo svantaggio è che consente di risolvere problemi con 2 o 3 incognite, ovvero è applicabile per 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 nel senso 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 primo sistema di coordinate del quadrante

Consideriamo il metodo della soluzione usando un esempio specifico.

Esempio 3.1. Ci sono 300 tonnellate di prodotti in calcestruzzo espanso e 200 tonnellate di acciaio nel magazzino. L'azienda automobilistica deve consegnare questi prodotti alla struttura in costruzione. L'azienda 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 della corsa sarà di 4 mila rubli. ZIL-4314 fornisce 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 garantire il massimo profitto all'azienda automobilistica.

Costruiamo un modello matematico del problema. Indichiamo con x 1 il numero richiesto di piloti KamAZ-5320 e attraverso X 2 il numero richiesto di piloti ZIL-4314.

Carrozza totale in t di prodotti in calcestruzzo espanso è 6 x 1 + 2x 2, e dall'acciaio 2 x 1 + 4x 2... Le restrizioni di trasporto in base al numero di articoli disponibili sono 6 x 1 + 2x 2 ≤ 300 t per calcestruzzo espanso e 2 x 1 + 4x 2 ≤ 200 t 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, quindi, si presenta come il seguente. È necessario massimizzare la funzione obiettivo

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

Considera l'equazione 6 x 1 + 2x 2 = 300. Per costruire una retta descritta da questa equazione, troviamo due punti che giacciono su questa retta. A x 1= 0 dall'equazione della retta troviamo 2 x 2 = 300, da cui x 2 = 150. Pertanto, il punto A con coordinate (0,150) giace sulla retta desiderata. A x 2= 0 abbiamo 6 x 1= 300, da cui x 1 = 50, e punto D con coordinate (50,0) si trova anche sulla linea ricercata. Traccia una linea retta attraverso questi due punti ANNO DOMINI(fig. 3.1).

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

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

Il sistema dei vincoli problematici richiede che piani ( x 1; x 2) soddisfano tutte e quattro le disuguaglianze, ovvero i progetti ammissibili sono punti ( x 1; x 2) deve trovarsi contemporaneamente in tutti e quattro i semipiani. Questo requisito è soddisfatto solo da punti situati all'interno e sul bordo del poligono. OECD, che è il poligono delle soluzioni ammissibili.

I vertici del poligono delle soluzioni ammissibili sono i punti O, E, K, D, segmenti di linea OE, EK, KD, OD- le sue costole. Qualsiasi punto del poligono OECDè il piano del problema, soddisfacendo tutte le sue condizioni. I vertici del poligono sono formati dall'intersezione di due rette e corrispondono ai piani base del problema, tra i quali c'è il piano migliore (ottimale). Pertanto, ci saranno tante piante di base quanti sono i vertici nel poligono delle soluzioni fattibili.

Una chiara rappresentazione geometrica può essere ottenuta anche per la funzione obiettivo. l = 4x 1 + 6x 2... Fissiamo un valore della funzione obiettivo, per esempio l= 120.equazione 4 x 1 + 6x 2 = 120 definisce una retta passante per un punto V con coordinate (x 1 = 0; x 2 = 20) e punto l con coordinate (( X 1 = 30; X 2 = 0). Sezione BL si trova all'interno del poligono OECD... Pertanto, per tutti i piani (punti) di questo segmento, il valore della funzione obiettivo è lo stesso e pari a 120. Assegnando altri valori alla funzione obiettivo, otteniamo rette parallele, che prendono il nome di linee di livello funzione obiettivo.

Muoversi dritto 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 della retta BL a destra determina l'incremento della funzione obiettivo che stiamo massimizzando. Lo facciamo fintanto che il rettilineo BL avrà almeno un punto in comune con il poligono delle soluzioni ammissibili OECD... Dalla fig. 3.1 ne consegue che l'ultimo punto attraversato dalla retta del livello di funzione obiettivo sarà il punto A... Questo significa che il punto A determina il piano di attività ottimale.

Viene chiamata la direzione ascendente perpendicolare alla linea di livello direzione di maggior incremento la funzione obiettivo e ne determina la massima crescita. Questa direzione può essere impostata senza disegnare linee di livello. Per questo è necessario sugli assi x 1 e x 2 posticipare i segmenti uguali ai coefficienti della funzione obiettivo, e da essi, come coordinate, costruire il vettore di maggior incremento della funzione obiettivo. In matematica si chiama pendenza e indichiamo con grad. Gradiente per funzione l = 4x 1 + 6x 2 ci sarà un vettore n| 4; 6 | ... Per comodità della sua costruzione, aumenteremo le coordinate, ad esempio 10 volte, ad es. n | 40; 60 | ... Costruiamo il gradiente della funzione obiettivo l, per cui colleghiamo il punto con le coordinate (40; 60) con l'origine. Le linee del livello della funzione obiettivo sono tracciate perpendicolarmente alla direzione del gradiente.

Quindi, in un modo o nell'altro è stato stabilito che il punto A determina il piano ottimo del problema, 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:

6x 1 + 2x 2= 300;

2x 1 + 4x 2= 200.

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

6x 1+ 2X · 30 = 300,

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

Pertanto, per ottenere il massimo profitto, l'impresa automobilistica deve completare 40 viaggi sul KamAZ-5320 e 30 viaggi sullo ZIL-4314. Il profitto massimo in questo caso sarà

l = 4x 1 + 6x 2= 4 40 + 6 30 = 340 mila rubli.

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

1) nello spazio bidimensionale, la regione 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) ad ogni valore della funzione obiettivo corrisponde una retta;

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

In generale, i problemi di ottimizzazione hanno un'interpretazione geometrica simile. L'insieme dei piani problematici rappresenterà un poliedro i cui vertici corrispondono ai piani di riferimento. Quando si risolve il problema, viene eseguita una 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 sta proprio nel fatto che la ricerca dei vertici (iterazione) viene effettuata solo nella direzione del maggior incremento della funzione obiettivo. Pertanto, non vengono considerati tutti i picchi, di cui ce n'è un numero enorme, ma solo quelli più vicini all'estremo.

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

Per definizione, l'insieme è chiamato 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.

Nella fig. 3.2b raffigura insiemi non convessi. Negli insiemi non convessi si possono indicare almeno due punti del segmento AB che non appartengono all'insieme in esame.

3.3. Metodo Simplex

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

Il metodo simplex prevede l'ottenimento di una soluzione di base non negativa di un sistema di equazioni lineari canoniche del tipo (3.1), la successiva minimizzazione (massimizzazione) della funzione obiettivo (3.3) e trovare in questo modo i valori ottimi delle variabili ricercate x 1, x 2 ... x n.

L'idea del metodo simplex è che nel processo di calcolo si passa in sequenza dalla prima soluzione di base alla seconda, terza, ecc. attraverso il cosiddetto semplice trasformazioni. Le conversioni vengono eseguite sotto forma di tabelle simplex, il che semplifica e velocizza 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 che i termini liberi delle equazioni rimangano non negativi in ​​tutte le fasi del processo. In questo caso bisogna essere guidati dalla seguente regola: qualsiasi variabile libera con 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 per la variabile introdotta nella base. Tali trasformazioni sono chiamate convertitori simplex.

Questo è molto importante, poiché per trovare una particolare soluzione non negativa corrispondente al valore più grande possibile di qualsiasi variabile libera a valori zero di altre variabili libere, invece di determinare l'intervallo della variabile specificata e sostituirne il massimo possibile valore nella soluzione generale, basta prendere questa variabile come quella di base e sottoporre il sistema ad una trasformazione simplex, passando ad una nuova base, che semplifica enormemente i calcoli.

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

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

Sia necessario ridurre al minimo la forma lineare

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

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

1x 1+ 0x 2 + ... 0x m + a 1 m + 1x m + 1 ... + a 1n x n = b 1;

0x 1 + 1x 2 +… 0x m + a 2m + 1x m + 1 ... + a 2n x n = b 2;

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

0x 1+ 0x 2 + ... 1x m + un mm + 1x m +1 ... + un mn x n = b m.

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

Risolviamo le equazioni per le variabili di base:

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

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

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

x m = b m - (un mm + 1x m + 1 ... + un mn x n),

ed esprimiamo la funzione obiettivo in termini di variabili libere, sostituendo le loro espressioni in termini di variabili libere al posto delle variabili di base:

L = c 1 b 1 + c 2 b 2 + cmbm - (c 1 a 1m + c 2 a 2m + 1 +… + cma mn + 1) x m + 1 -… - (c 1 a 1n + c 2 a 2n +… + cma mn) xn… + cnx 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 - libero. Ci dovrebbero sempre essere tante variabili di base quante sono le equazioni nel sistema. In base alla condizione di non negatività, il valore più piccolo delle variabili libere è zero. La soluzione di base ottenuta del sistema di equazioni è la sua soluzione iniziale ammissibile, cioè x 1 = b 1, x 2 = b 2, ... x m = b m, x m +1 = 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.

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

Le tabelle Simplex sono composte come segue (vedi tabella 3.1). Tutte le variabili sono posizionate 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 c ioè costituito dal coefficiente della funzione obiettivo per le variabili incluse nella base. Segue una colonna di variabili di base e termini di equazioni liberi. Gli elementi delle restanti colonne della tabella rappresentano i coefficienti delle variabili con cui queste ultime sono incluse 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 definire

∆j = zj - cj,

dove cj- i coefficienti per le corrispondenti variabili nella funzione obiettivo; zj - la somma dei prodotti dei coefficienti della funzione obiettivo per le variabili di base per le variabili - elementi corrispondenti J-Th colonna della tabella.

tavolo 3.1

Tabella Simplex con iniziale valida

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

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

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

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

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

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

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

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

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

Esempio 1 Esiste un problema di programmazione lineare con vincoli di disuguaglianza: trovare valori non negativi di variabili che soddisfino le condizioni

e minimizzare la funzione lineare

È necessario portare questo compito nella forma di un OZLP.

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

Introduciamo variabili aggiuntive:

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

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

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

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

e la funzione da minimizzare

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

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

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

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

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

Concetti di modellazione di base

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

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

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

Economia- Si tratta di un sistema di produzione sociale che realizza concretamente la produzione, la distribuzione, lo scambio e il consumo dei beni materiali necessari alla società.

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

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

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

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

Il problema di ottimizzazione posto in questo modo è chiamato problema di programmazione matematica. Un mucchio di Xè chiamato l'insieme delle decisioni fattibili e la funzione è la funzione obiettivo o la funzione obiettivo. La soluzione ammissibile alla quale la funzione assume il valore più grande (o più piccolo) è chiamata soluzione ottima del problema.

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

trova l'estremo della funzione

con restrizioni

in condizioni di non negatività

Introduciamo la notazione:

Azioni io-Il tipo di risorsa;

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

profitto unitario J-Il tipo di prodotto.

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

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

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

Coefficienti tecnici ed economici per variabili nei vincoli;

Il volume del lato destro delle disuguaglianze, che sono dette costanti del problema;

Coefficienti di variabili nella funzione obiettivo, detti stime variabili;

Indice variabile;

Indice di restrizione.

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

Variabili x j denotano tali tipi e metodi di attività, la cui dimensione è sconosciuta e deve essere determinata nel corso della risoluzione del problema. Solitamente, nei problemi di agricoltura, le variabili indicano le dimensioni richieste dei rami dell'economia, i tipi di mangimi nella dieta, le marche di trattori e macchine agricole, ecc. A seconda delle condizioni specifiche, la stessa coltura o tipologia di bestiame può essere espressa da più variabili. Ad esempio, grano e mangime; mais per cereali, insilati, foraggi verdi; graminacee perenni per fieno, haylage, foraggio verde, farina d'erba e semi, ecc.

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

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

Le variabili possono essere espresse in varie unità di misura: ha, q, kg, pz., Teste, ecc. Per loro natura, le variabili sono suddivise in principali, aggiuntive e ausiliarie. Le principali variabili comprendono le attività ricercate: settori industriali, tipologie di mangimi, marchi automobilistici. Le variabili che si formano nel processo di trasformazione delle disuguaglianze in equazioni sono dette complementari. Possono significare una parte sottoutilizzata delle risorse, un eccesso sul lato destro della disuguaglianza (se questa è una disuguaglianza del tipo “non più”). Le variabili ausiliarie sono incluse nell'attività al fine di determinare i valori stimati delle risorse di produzione acquisite, i valori stimati degli indicatori dell'efficienza economica della produzione.

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

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

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

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

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

Lato destro delle restrizioni (b i) sono dette costanti, cioè valori costanti. Questi includono il volume delle risorse di produzione: terra, manodopera, macchinari, fertilizzanti, investimenti di capitale, ecc. Le risorse di produzione dovrebbero essere determinate tenendo conto del loro stato attuale ed è indispensabile tenere conto del periodo di pianificazione. Inoltre, le risorse di produzione il cui impiego è disomogeneo durante tutto l'anno, sono calcolate non solo per l'intero anno, ma anche per singoli periodi o mesi intensi (risorse di lavoro).

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

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

Il lato destro delle restrizioni riflette non solo la quantità di risorse, ma anche il volume di produzione al livello superiore o inferiore. Il livello inferiore è indicato nei casi in cui il volume di produzione è noto in anticipo, inferiore a quello che l'azienda non dovrebbe produrre, e il livello superiore non consente la produzione di prodotti al di sopra di un determinato volume. Queste restrizioni non sono sempre richieste. Tuttavia, quasi nessun problema relativo alla definizione di una combinazione di settori non fa a meno di corrispondenti restrizioni sui prodotti, altrimenti si rivelerà una soluzione unilaterale. Ciò è dovuto al fatto che l'efficienza delle industrie non è la stessa.

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

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

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

v troppi vincoli aumentano la dimensione del problema e lo rendono difficile da risolvere

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

dove io = 1, 2, … , m... Si indicano coefficienti variabili un ij dove indice io- numero di restrizione, indice J- numero variabile, soci gratuiti ( parte destra restrizioni) sono indicati b io, indice io- numero di restrizione.

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

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

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

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

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

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

La condizione per la non negatività delle variabili è scritta nel form

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

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

J = 1, …, n. (1.6)

Vettore X = (X 1 , X 2 , …, X n), componenti xj che soddisfano i vincoli (1.2) e (1.3) [o (1.5) e (1.6) nel problema minimo] si dice decisione accettabile o piano accettabile Compiti LP. Viene chiamata la raccolta di tutti i piani validi molti piani validi.

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

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

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

1) se nel problema originario si richiede di determinare il massimo di una funzione lineare, allora occorre cambiarne il segno e ricercare il minimo di tale funzione;

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

3) se tra i vincoli ci sono disuguaglianze, allora introducendo variabili aggiuntive di variabili non negative, queste vengono trasformate in uguaglianze. Ad esempio, variabili aggiuntive Sj nei vincoli di tipo minore o uguale a (£) sono inseriti con il segno più:

Variabili aggiuntive Sj nel tipo i vincoli maggiori o uguali a (≥) sono inseriti con un segno meno:

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