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

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:

• minimizzare le risorse che devono essere impiegate;
• massimizzare il valore ottenuto dalle risorse impiegate.

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:

• tutte le variabili controllabili da chi assume le decisioni sul modello (variabili di decisione) devono essere non-negative (positive o tutt'al più nulle).
• Il criterio per selezionare il miglior valore delle variabili di decisione può essere espresso da una funzione lineare di queste variabili, in altre parole una funzione matematica che coinvolga solo le prime potenze delle variabili e nessun prodotto tra le stesse. Quest'ultima prende il nome di funzione obiettivo.
• Le limitazioni regolanti il processo, come la scarsità della materia prima, devono essere espresse come un insieme di equazioni o disequazioni lineari; questo insieme prende il nome di insieme dei vincoli.
• La soluzione di un problema di programmazione lineare si ottiene determinando il valore delle variabili di decisione in modo da far assumere alla funzione obiettivo un valore massimo (od un minimo).

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.

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.