Un esempio svolto...
Il codice "C" del programma è ANSI, quindi può essere compilato ed eseguito tranquillamente su qualsiasi piattaforma (LINUX, WINDOWS ecc...).
Andiamo a vedere passo passo un esercizio svolto attraverso input ed output al programma in esecuzione.
L'ESERCIZIO E' IL SEGUENTE:
min
Z = -X1 - X2
2X1 + X2 <= 8
X1 - X2 <= 2
X1 + 2X2 <= 10
LO RIDUCIAMO A TUTTE UGUAGLIANZE:
min
Z = -X1 - X2
2X1 + X2 + X3 = 8
X1 - X2 + X4 = 2
X1 + 2X2 + X5 = 10
E DIAMO GLI INPUT AL PROGRAMMA...
L'ESEMPIO E' STATO SVOLTO IN AMBIENTE LINUX
"prial@linux:~ > a.out [INVIO]"
RISOLUZIONE DI PROBLEMI DI POGRAMMAZIONE LINEARE:
*** Metodo delle due fasi ***
-Release 0.1 - Novembre 2000-
Inserisci i dati del problema ridotto alla seguente forma:
===================
Zmin = Cx
Ax = b
b >= 0;
===================
Tieni presente che le matrici sono sempre indicizzate come:
matrice[riga][colonna]
Quindi i dati vanno inseriti per riga:
elemento (1,2) è l'elemento sulla riga 1 colonna 2...
ATTENZIONE: un valore (-1) nel vettore b/Yk, indica che
il rapporto in quella posizione, non è ammissibile!!!
*** I N I Z I A M O P U R E... ***
Dammi le dimensioni del problema (m = vincoli) - (n = variabili):
m = 3
n = 5
Adesso inserisci i costi unitari per il vettore "C":
(1,1) = -1
(1,2) = -1
(1,3) = 0
(1,4) = 0
(1,5) = 0
Questo è il vettore dei costi unitari "C":
|----1----|----2----|----3----|----4----|----5----|
1 -1.00 | -1.00 | 0.00 | 0.00 | 0.00 |
|---------|---------|---------|---------|---------|
Questo è il vettore dei costi unitari per le DUE FASI:
|----1----|----2----|----3----|----4----|----5----|----6----|----7----|----8----|
1 0.00 | 0.00 | 0.00 | 0.00 | 0.00 | 1.00 | 1.00 | 1.00 |
|---------|---------|---------|---------|---------|---------|---------|---------|
Adesso inserisci i termini noti per il vettore "b":
(1,1) = 8
(2,1) = 2
(3,1) = 10
Questo è il vettore dei termini noti "b":
|----1----|
1 8.00 |
|---------|
2 2.00 |
|---------|
3 10.00 |
|---------|
Adesso inserisci dati per la matrice dei vincoli "A":
(1,1) = 2
(1,2) = 1
(1,3) = 1
(1,4) = 0
(1,5) = 0
(2,1) = 1
(2,2) = -1
(2,3) = 0
(2,4) = 1
(2,5) = 0
(3,1) = 1
(3,2) = 2
(3,3) = 0
(3,4) = 0
(3,5) = 1
Questa è la matrice dei vincoli del problema iniziale:
|----1----|----2----|----3----|----4----|----5----|
1 2.00 | 1.00 | 1.00 | 0.00 | 0.00 |
|---------|---------|---------|---------|---------|
2 1.00 | -1.00 | 0.00 | 1.00 | 0.00 |
|---------|---------|---------|---------|---------|
3 1.00 | 2.00 | 0.00 | 0.00 | 1.00 |
|---------|---------|---------|---------|---------|
Questa è la matrice dei vincoli per le DUE FASI:.
|----1----|----2----|----3----|----4----|----5----|----6----|----7----|----8----|
1 2.00 | 1.00 | 1.00 | 0.00 | 0.00 | 1.00 | 0.00 | 0.00 |
|---------|---------|---------|---------|---------|---------|---------|---------|
2 1.00 | -1.00 | 0.00 | 1.00 | 0.00 | 0.00 | 1.00 | 0.00 |
|---------|---------|---------|---------|---------|---------|---------|---------|
3 1.00 | 2.00 | 0.00 | 0.00 | 1.00 | 0.00 | 0.00 | 1.00 |
|---------|---------|---------|---------|---------|---------|---------|---------|
----------- BASE ATTUALE: -----------
B1 = {6, 7, 8}; N1 = {1, 2, 3, 4, 5};
Con XB1:
x6 = 8.00
x7 = 2.00
x8 = 10.00
E con N1 = 0..
Testiamo l'ottimalità della base XB1:
p0 = 20.00
MAX Zj-Cj (per 1 <= j <= N) = {4.00, 2.00, 1.00, 1.00, 1.00}
MIN+ b/Yk ................. = {4.00, 2.00, 10.00}
Entra.: X1; Esce.: X7
-------------------------------------
Premi [I N V I O] per continuare.....
----------- BASE ATTUALE: -----------
B2 = {6, 1, 8}; N2 = {7, 2, 3, 4, 5};
Con XB2:
x6 = 4.00
x1 = 2.00
x8 = 8.00
E con N2 = 0..
Testiamo l'ottimalità della base XB2:
p0 = 12.00
MAX Zj-Cj (per 1 <= j <= N) = {-4.00, 6.00, 1.00, -3.00, 1.00}
MIN+ b/Yk ................. = {1.33, -1.00, 2.67}
Entra.: X2; Esce.: X6
-------------------------------------
Premi [I N V I O] per continuare.....
----------- BASE ATTUALE: -----------
B3 = {2, 1, 8}; N3 = {7, 6, 3, 4, 5};
Con XB3:
x2 = 1.33
x1 = 3.33
x8 = 4.00
E con N3 = 0..
Testiamo l'ottimalità della base XB3:
p0 = 4.00
MAX Zj-Cj (per 1 <= j <= N) = {0.00, -2.00, -1.00, 1.00, 1.00}
MIN+ b/Yk ................. = {-1.00, 10.00, 4.00}
Entra.: X4; Esce.: X8
*** TUTTE LE VBL ARTIFICIALI SONO USCITE DALLA BASE ***
*** INIZIAMO LA SOLUZIONE DEL PROBLEMA ORIGINARIO.. ***
-------------------------------------
Premi [I N V I O] per continuare.....
----------- BASE ATTUALE: -----------
B4 = {2, 1, 4}; N4 = {3, 5};
Con XB4:
x2 = 4.00
x1 = 2.00
x4 = 4.00
E con N4 = 0..
Testiamo l'ottimalità della base XB4:
Z0 = -6.00
MAX Zj-Cj (per 1 <= j <= N) = {-0.33, -0.33}
*** SOLUZIONE OTTIMA ASSOLUTA!!! ***
Powered by Alfonso PRISCO