JavaSimplex

Istruzioni:

Il tableau si riempie in questo modo:

Dato il problema di PL:                      Il tableau diventa:

min z = -x1  -x2                              0   -1   -1    0    0
        6x1 +4x2  +x3       = 24             24    6    4    1    0
        3x1 -2x2       +x4  = 6               6    3   -2    0    1
         x1,  x2,  x3,  x4 >= 0

Le funzioni dei pulsanti:

Prima di usare le funzioni Passo e -z si devono specificare le variabili in base sulle varie righe. Per fare cio' si puo' ricorrere al pulsante Auto, o si possono specificare manualmente ricorrendo alle liste alla estrema sinistra di ogni riga.

I valori che appaiono nella finestra di stato (a destra del pulsante Passo) hanno i seguenti significati:


A cosa serve?

La programmazione lineare serve a determinare l'allocazione ottimale di risorse disponibili in quantità limitata, per ottimizzare il raggiungimento di un obiettivo prestabilito, in condizioni di certezza.

In pratica, il suo scopo e' di:

Pertanto, una volta formulato il problema e costruito un modello matematico lineare, al fine di ottenere la miglior soluzione si possono utilizzare algoritmi matematici standard. Il più importante è il metodo del simplesso.

Le condizioni da soddisfare per formulare un modello di programmazione lineare sono:

Per costruire un modello di programmazione lineare occorre seguire i seguenti passaggi:
  1. Identificare le variabili di decisione (x1,x2,x3,...);
  2. Identificare tutte le restrizioni o vincoli del problema ed esprimerli come equazioni o disequazioni lineari delle variabili di decisione;
  3. Identificare l'obiettivo e rappresentarlo come una funzione lineare delle variabili di decisione.
Il metodo del simplesso si basa su un processo iterativo di calcolo del valore della funzione obiettivo nei vertici della soluzione ammissibile, fino a quando si trova il valore ottimale (o si verifica che tale valore non esiste). Esso e' potente in quanto riesce a limitare il numero di soluzioni ammissibili di base da considerare.


Esempi

Problema:

Per la produzione di due tipi di stampi, che indicheremo con A e B, una impresa artigianale puo' disporre settimanalmente di 1200 Kg di resina e di 900 ore di lavoro. I dati tecnici relativi alla produzione settimanale sono i seguenti:
  • ogni stampo di tipo A richiede 5 Kg di resina e 5 ore di lavorazione;
  • ogni stampo di tipo B richiede 12 Kg di resina e 2 ore di lavorazione.
I prezzi a cui gli stampi vengono rivenduti sono rispettivamente 800.000 e 500.000 £. Determinare il numero di stampi dei due tipi che è opportuno produrre per avere il massimo ricavo possibile.

Soluzione:

max -z=800000a+500000b          (ricavo)
            5a    +12b <= 1200  (resina)
            5a     +2b <= 900   (ore)
             a,      b >= 0
massimizzare -z equivale a minimizzare z;

inoltre, una disequazione:
   a £ 10
può essere sostituita dalle condizioni:
   a + c = 10
   c ³ 0

nel nostro caso, aggiungiamo 2 variabili (di scarto): c, d

min z=-800000a-500000b
            5a    +12b      +c          = 1200
            5a     +2b              +d  = 900
             a,      b,      c,      d >=0,
Il tableau diventa (termini noti all'inizio):
0     -800000 -500000       0       0
1200        5      12       1       0
900         5       2       0       1
che, risolto con JavaSimplex, fornisce (nella prima colonna, dove x1=a e x2=b):
a=168
b=30	
max -z=149400000

Problema:

Un'azienda agricola ha a disposizione tre tipi di sostanze A, B, C per la preparazione di una miscela fertilizzante. La sostanza A contiene il 10% di azoto e il 20 % di ossido di potassio, la sostanza B contiene il 15% di azoto ed il 50% di ossido di potassio, la C il 25% di azoto ed il 60% di ossido di potassio. Il concime da utilizzare deve contenere almeno il 20% di azoto ed almeno il 40% di ossido di potassio. I costi delle tre sostanze sono rispettivamente di 600£, 750£ e 100£ al Kg. Determinare la composizione percentuale delle tre sostanze che rende minimo il costo della miscela fertilizzante.

Soluzione:

Supponiamo di voler produrre 1Kg di miscela al costo minimo:
min z=600a+750b+100c                        (costo)
  a  +b  +c =1                              (1kg)
10a+15b+25c>=20                             (azoto)
20a+50b+60c>=40                             (potassio)
  a,  b,  c>=0
ossia:
min z=600a+750b+100c                        (costo)
         a   +b   +c =1                     (1kg)
      -10a -15b -25c<=-20                   (azoto)
      -20a -50b -60c<=-40                   (potassio)
         a,   b,   c>=0
in questo caso, il problema e' gia' di minimo;
aggiungiamo 2 variabili (la riga (1kg) e' gia' un'uguaglianza):
min z=600a+750b+100c                        (costo)
         a   +b   +c           =1           (1kg)
      -10a -15b -25c   +d      =-20         (azoto)
      -20a -50b -60c        +e =-40         (potassio)
         a,   b,   c,   d,   e>=0
Il tableau diventa:

che, risolto con JavaSimplex, fornisce (nella prima colonna, dove x1=a, x2=b, x3=c):
c=1
b=0
a=0
min z=100
(infatti la sostanza C e' la piu' economica e rispetta gia' entrambi i vincoli)

Nota: in realta' conviene sfruttare l'uguaglianza (1kg) sostituendo, ad es., a=1-b-c nelle altre.


 Torna alla Home-Page 

HomePage WinBode ClothSim 3GYPT JavaSimplex Unreal Museum Unreal Comic WebMaster