Proprietà dei vertici

* per "vertice ammissibile" si intende un vertice che non sia su un segmento che collega soluzioni ammissibili. Quando un vertice riporta un asterisco, si intende vertice ammissibile.

In programmazione lineare, i vertici hanno le seguenti proprietà:

  1. Se esiste una sola soluzione ottima, questa sarà un vertice. Se esistono più soluzioni, almeno due di queste sono vertici* adiacenti.
  2. Il numero di vertici ammissibili è finito.
  3. Se un vertice ammissibile non ha vertici adiacenti migliori, allora non ci sono vertici migliori. Quindi se il problema ha una soluzione ottima, questo vertice è la soluzione ottima.

La 1. si dimostra per assurdo. Se esiste una soluzione ottima che non è un vertice, significa che la soluzione è compresa tra due vertici*, ma in questo caso, poiché i vertici* sono ammissibili, anche essi sono soluzioni ammissibili, il che contraddice il fatto che la soluzione sia unica.

La 2. è dimostrabile perché il conteggio dei vertici è dato da una formula che restituisce solo risultati finiti, che è (n = numero di equazioni, m = numero di vincoli):

(n+mn)

La 3. è una diretta conseguenza della convessità del problema. Se il problema è convesso, ogni spostamento verso un vertice "migliore" è una garanzia che anche il risultato sarà migliore; viceversa se il problema non fosse convesso, sarebbe necessario calcolare ogni singolo punto e cercare per tentativi il risultato migliore.