Introduzione alla Programmazione Lineare Juan Alberto Huaripuma Vargas

PROBLEMI DI PROGRAMMAZIONE LINEARE

FORMULAZIONE DEI PROBLEMI

1. Una compagnia aerea dispone di due aerei A1 e A2 per coprire un

determinato percorso. L'aereo A1 deve fare più volte il percorso rispetto all'aereo
A2 ma non può superare 120 viaggi. Tra i due aerei devono fare di più
di 60 voli, ma meno di 200. In ogni volo, A1 consuma 900 litri di
combustble y A2 700 litros. En cada viaje del avión A1 la empresa gana $US 30.000
y $US 20.000 per ogni viaggio dell'aereo A2.

a) Quanti viaggi deve fare ogni aereo per ottenere il massimo dei profitti?

b) Quanti voli deve fare ogni aereo affinché il consumo di carburante

sea minimo?

a) Variabili di decisione

X1 = # de vuelos del avión detpo A1

X2 = # di voli dell'aereo del tipo A2

b) Funzione obiettivo

Massimizza Z = 900X1 + 700X2

Min R = 30000X1 + 20000X2

c) Restricciones

60 <= X1 + X2 <= 200

X1 <= 120
X1 >= X2

d) Fasce di esistenza

X1, X2 >= 0

2. Una azienda di costruzioni dispone di due tipi di camion C1 e C2 e vuole

trasportare 100TM di sabbia in un cantiere. Sapendo che dispone di 6 camion
C1 con capacità per 15TM e con un costo di S/. 400 per viaggio e di 10 camion
tpo C2 con una capacità di 5T e con un costo di S/. 300 per viaggio.
Qual è il numero possibile di camion che deve usare affinché il costo sia
mínimo? ¿Cuál es el valor de dicho coste?

a) Variabili decisionali

X1 = # de camiones usados deltpo C1

 Introduzione alla Programmazione Lineare Juan Alberto Huaripuma Vargas

X2 = # di camion usati deltpo C2

b) Funzione obiettivo

Min Z = 400X1 + 300X2

c) Restrizioni

15X1 + 5X2 >= 100

X1 + X2 <= 16
X1 <= 6
X2 <= 10

d) Ranges di esistenza

X1, X2 >= 0

3. Una compagnia di assicurazioni sta introducendo due nuove linee di prodotti:

assicurazione sui rischi speciali e mutui. Il guadagno atteso è 5 per unità
sul’assicurazione dei rischi speciali e 2 per unità sulle ipoteche.
L'amministrazione vuole stabilire le quote di vendita per le nuove linee di
prodotti al fine di massimizzare il guadagno atteso. I requisiti di
il lavoro sono le seguenti:

Dipartimento Ore di lavoro per unità Ore di lavoro

Rischi speciali Mutui disponibili
Elaborazione 3 2 2400
Amministrazione 0 1 800
Reclamazioni 2 0 1200

a) Variabili decisionali

X1 = # de seguros de riesgos especiales

X2 = # de hipotecas

b) Funzione obiettivo

Massimo Z = 5X1 + 2X2

c) Restrizioni

3X1 + 2X2 <= 2400

X2 <= 800
2X1 <= 1200

d) Fasce di esistenza
Introducción a la Programación Lineal Juan Alberto Huaripuma Vargas

X1, X2 >= 0

4. L'azienda ABC produce giocattoli di legno: soldatini e treni.

vende un soldato a 27 dollari e si usano 10 dollari di materia prima. Ogni soldato
quello che si produce aumenta i costi variabili del lavoro e i costi
generali a 14 dollari. Viene venduto un treno a 21 dollari e si usano 9 dollari di
materia prima. Ogni treno prodotto aumenta i costi variabili del lavoro
e i costi generali a 10 dollari. La produzione di soldati e treni di
Il legno necessita di posti di lavoro specializzati: falegnameria e rifinitura.
Il soldato richiede 2 ore di rifinitura e 1 ora di falegnameria. Un treno richiede 1
ora di fine e 1 ora di falegnameria. Ogni settimana, l'azienda ABC può
ottenere tutta la materia prima necessaria, ma ha solo 100
ore di finitura e 80 di falegnameria. La domanda dei treni non ha limiti,
ma si vendono al massimo 40 soldati settimanalmente. Formuli un modello di
programmazione in modo che l'azienda ABC massimizzi il suo guadagno settimanale
L. Winston, Pagina 56

a) Variabili di decisione

X1 = # de soldados
X2 = # de trenes

b) Funzione obiettivo

Massimo Z = (27 - 10 - 14) X1 + (21 - 9 - 10) X2

Massimo Z = 3X1 + 2X2

c) Restrizioni

2X1 + 1X2 <= 100

X1 + 1X2 <= 80
X2 <= 80

d) Range di esistenza

X1, X2 >= 0

5. Il contadino Jonestene che determina quante ettari di mais e di grano ci sono

che seminare quest'anno. Un ettaro di grano produce 25 sacchi di grano e richiede
10 ore settimanali di lavoro. Un ettaro di mais produce 10 sacchi di mais e
richiede 4 ore settimanali di lavoro. Si può vendere tutto il grano a S/40 il sacco
e tutto il mais a S/. 30 il sacco. Si dispone di 7 ettari e di 40 ore settimanali
di lavoro. Le disposizioni governative specificano una produzione di mais di
almeno 30 sacchi durante l'anno in corso. Quanti sacchi di mais e di grano?
che deve produrre questo contadino se desidera massimizzare il suo reddito totale? (Wayne L.
Winston, Pág. 62)
Introduzione alla Programmazione Lineare Juan Alberto Huaripuma Vargas

a) Variabili decisionali

X1 = # de sacos de maíz
X2 = # di sacchi di grano

b) Funzione obiettivo

Massimizza Z = 30X1 + 40X2

c) Restrizioni

2.5X1 + X2 <= 175

0.4X1 + 0.4X2 <= 40
X1 >= 30

d) Ranghi di esistenza

X1, X2 >= 0

6. L'azienda Leary Chemical produce tre prodotti chimici: A, B e C. Questi

I prodotti chimici si ottengono tramite due processi: 1 e 2. Il funzionamento
del processo 1 per un'ora, costa 4 dollari e produce 3 unità del
prodotto A, 1 unità del prodotto B e 1 unità del prodotto C. Il funzionamento
del processo 2 durante un'ora, costa 1 dollaro e produce 1 unità del prodotto A,
y 1 unità del prodotto B. Per soddisfare la domanda dei clienti, è necessario
produrre quotidianamente almeno 10 unità del prodotto A, 5 unità del
prodotto B e 3 unità del prodotto C. Determinare graficamente un piano di
produzione giornaliera che minimizzi il costo di soddisfare le domande quotidiane (Wayne
L. Winston, Pag. 72

a) Variabili decisionali

X1 = Producción diaria según el proceso 1

X2 = Produzione giornaliera secondo il processo 2

b) Funzione obiettivo

Min Z = 4X1 + X2

c) Restrizioni

X1 >= 3
X1 + X2 >= 5
3X1 + X2 >= 10

d) Ranghi di esistenza
Introduzione alla Programmazione Lineare Juan Alberto Huaripuma Vargas

X1, X2 >= 0

7. Una compagnia automobilistica produce automobili e camion. Ogni veicolo ha

che passare per un laboratorio di verniciatura e per un laboratorio di montaggio della carrozzeria. Se il
Il laboratorio di pittura dipingerà solo camion, si potrebbero dipingere 40 camion al giorno.
Se il laboratorio di pittura si occupasse solo di dipingere automobili, potrebbe dipingerne 60.
automobili quotidianamente. Se il carrozziere producesse solamente
automobili, potrebbe fabbricare 50 automobili al giorno. Se l'officina di carrozzeria
produrrebbe solo camion, potrebbe fabbricare 50 camion al giorno. Ogni camion
porta 300 dollari all'utilità, e ogni automobile, 200. Utilizza la programmazione
lineare per determinare la produzione giornaliera che massimizzerà il guadagno del
compagnia. (Wayne L. Winston, Pag. 72)

a) Variabili decisionali

X1 = Producción diaria de automóviles

X2 = Producción diaria de camiones

b) Funzione obiettivo

Massimizza Z = 200X1 + 300X2

c) Restrizioni

4X1 + 6X2 <= 240

X1 + X2 <= 50

d) Rango di esistenza

X1, X2 >= 0

8. Supponiamo che i concessionari di automobili richiedano che la compagnia

l'automotrice della domanda precedente produce almeno 30 camion e 20
automobili. Trova la soluzione ottimale per il nuovo problema lineare. (Wayne
L. Winston, Pag. 73)

a) Variabili decisionali

X1 = Producción diaria de automóviles

X2 = Produzione giornaliera di camion

b) Funzione obiettivo

Max Z = 200X1 + 300X2

c) Restrizioni
 Introduzione alla Programmazione Lineare Juan Alberto Huaripuma Vargas

4X1 + 6X2 <= 240

X1 + X2 <= 50
X1 >= 20
X2 >= 30

d) Ranghi di esistenza

X1, X2 >= 0

9. Una compagnia manifatturiera ha interrotto la produzione di una certa linea di

prodotti non redditizi. Questo ha creato un eccesso considerevole nella capacità di
produzione. La direzione vuole dedicare questa capacità a uno o più dei tre
productos: Llámese 1, 2 y 3. En la siguiente tabla se resume la capacidad
disponibile di ogni macchina che può limitare la produzione:

Tipo de máquina Tempo disponibile

(In ore macchina a settimana)
Fresatrice 500
Torno 350
Rettificatrice 150

Il numero di ore-macchina richieste per ogni unità dei prodotti

rispettivi è:

Tipo di Prodotto 1 Prodotto 2 Prodotto 3

macchina
Fresatrice 9 3 5
Torno 5 4 0
Rettificatrice 3 0 2

Se il guadagno unitario fosse di S/. 50, S/. 20 e S/. 25, rispettivamente, per i
prodotti 1, 2 e 3. Quanti prodotti di ciascuno deve produrre l'azienda per
massimizzare il guadagno?

[Hillier e Lieberman (1997), Pag. 69]

a) Variabili di decisione

X1 = Produzione deltpo 1
X2 = Produzione deltpo 2
X3 = Producción deltpo 3

b) Funzione obiettivo

Z = 50X1 + 20X2 + 25X3

c) Restrizioni
 Introduzione alla Programmazione Lineare Juan Alberto Huaripuma Vargas

9X1 + 3X2 + 5X3 <= 500

5X1 + 4X2 <= 350
X1 + X3 <= 150

d) Ranges di esistenza

X1, X2, X3 >= 0

10. Un rivenditore di ferramenta prevede di vendere pacchetti di dadi e viti

mescolati. Ogni pacchetto pesa almeno 2 libbre. Tre dimensioni di noci e
I bulloni compongono il pacchetto e si acquistano in lotti da 200 libbre. Le dimensioni 1,
2 e 3 costano rispettivamente S/. 20, S/. 8 e S/. 12. Inoltre:

a) El peso combinado de los tamaños 1 y 3 debe ser al menos la mitad del peso
totale del pacchetto
b) Il peso delle dimensioni 1 e 2 non deve essere superiore a 1,6 libbre
c) Qualsiasi dimensione della vite deve essere almeno il 10% del pacchetto totale.

Quale sarà la composizione del pacchetto che comporterà un costo minimo?

[Shamblin e Stevens (1975), Pag. 316]

a) Variabili decisionali

X1 = totale delle libbre del pacchetto di dimensione 1

X2 = total de libras del paquete de tamaño 2
X3 = totale delle libbre del pacchetto di dimensione 3

b) Funzione obiettivo

Max Z = 20X1 + 8X2 + 12X3

c) Restrizioni

X1 >= 2
X2 >= 2
X3 >= 2
X1 + X2 + X3 <= 200
X1 + X3 >= 0.5 (X1 + X2 + X3)
X1 + X2 >= 1.6
X1 >= 0.1(X1 + X2 + X3)
X2 >= 0.1(X1 + X2 + X3)
X3 >= 0.1(X1 + X2 + X3)

d) Ranges di esistenza

X1, X2, X3 >= 0

Introduzione alla Programmazione Lineare Juan Alberto Huaripuma Vargas

11. Uno studente dedica parte del suo tempo alla distribuzione di pubblicità.
l'azienda A le paga 5 Bs. per ogni volantino distribuito e l'azienda B, con i depliant
più grandi, gli paga 7 Bs. per ogni stampato. Lo studente porta due borse: una
per i moduli A, in cui entrano 120, e un'altra per i moduli B, in cui
caben 100. Ha calcolato che ogni giorno è in grado di distribuire 150 stampati come
massimo. Ciò che si chiede allo studente è: Applicando il metodo grafico,
cuantos impresos habrá de repartr de cada clase para que su beneficio diario sea
massimo?

a) Variabili decisionali

X1 = # de impresos A repartdos
X2 = # de impresos B repartdos

b) Funzione obiettivo

Max 5X1 + 7X2

c) Restrizioni

X1<=120
X2<=100
X1 + X2 <= 120

d) Ranges di esistenza

X1, X2 >=0

12. Il Problema della Dieta: (Stgler, 1945).

Consiste nel determinare una dieta in modo efficiente, a partire da un insieme dato
di alimenti, in modo da soddisfare i requisiti nutrizionali. La quantità di
alimenti da considerare, le loro caratteristiche nutrizionali e i costi di questi,
permettono di ottenere diverse varianti estetiche di modelli. Ad esempio:

Latte di legumi Arance Requerimientos

(litros) (1 porción) (unità) Nutrizionali
Niacina 3,2 4,9 0,8 13
Tiamina 1,12 1,3 0,19 15
Vitamina C 32 0 93 45
Costo 2 0,2 0,25

a) Variabili di Decisione:

X1 = Litros de Leche utlizados en la Dieta

Introduzione alla Programmazione Lineare Juan Alberto Huaripuma Vargas

X2 = Porzioni di legumi utilizzate nella dieta

X3 = Unidades de Naranjas utlizadas en la Dieta

b) Función Objetvo: (Minimizar los Costos de la Dieta)

Min 2X1 + 0,2X2 + 0,25X3

c) Restrizioni: Soddisfare i requisiti nutrizionali

Niacina: 3,20 X1 + 4,9 X2 + 0,8 X3 >= 13

Tiamina: 1,12 X1 + 1,3 X2 + 0,19 X3 >= 15
Vitamina C 32X1 + 0 X2 + 93 X3 >= 45

d) Nessuna Negatività:

X3>=0; X2>=0; X3>=0