Blox - Donde la lógica se vuelve natural

Nombre

resolver_two_phase - Resuelve un problema de minimizacion usando Two-Phase Simplex.

Sinopsis

ret = simplex2ph.resolver_two_phase(A, b, sense, c, tol, maxIter)

Descripcion

Ejecuta la Fase 1 para encontrar factibilidad y, si la encuentra, pasa a la Fase 2 para optimizar el objetivo original.

Internamente trabaja con un simplex de maximizacion sobre -c^T x, por lo que el costo minimo real se recupera como el negativo del valor final del objetivo en Fase 2.

Formula:

$\max c^Tx\quad\mathrm{s.a.}\quad Ax\le b$

Comportamiento

Construye el tableau inicial de Fase 1.
Ejecuta simplex_iterar() sobre Fase 1 y comprueba factibilidad con el valor objetivo z1.
Limpia artificiales si todavia quedaron en la base.
Construye el tableau inicial de Fase 2.
Ejecuta simplex_iterar() sobre Fase 2.
Extrae la solucion original y calcula min_cost.
Retorna una tabla con ok, status, msg, x y min_cost.

Funciones API relacionadas

simplex2ph.construir_fase1()
simplex2ph.limpiar_artificiales()
simplex2ph.construir_fase2()
simplex2ph.simplex_iterar()
simplex2ph.extraer_solucion_original()

Parámetros

Parámetro	Tipo	Descripción
A	MATRIZ	Coeficientes de restricciones.
b	MATRIZ	RHS de restricciones.
sense	STRING	Sentido de cada restriccion: `<=`, `=` o `>=`.
c	VECTOR	Costos del objetivo original.
tol	NUMERICO	Tolerancia numerica.
maxIter	NUMERICO	Maximo de iteraciones permitidas por llamada a `simplex_iterar()`.

Valor de retorno

TABLA - Tabla con los resultados estructurados de la resolucion.

Ejemplo

ejemplo.blox

INCLUIR "matrices.api"
INCLUIR "vectores.api"
INCLUIR "simplex2ph.api"   

// =========================================================
// PRINCIPAL + LOADER del LP (2 mezclas, 3 insumos, 4 semanas)
// Variables originales: 21 (9 pedidos + 12 inventarios)
// Restricciones: 33 (12 "=" y 21 "<=")
// =========================================================
FUNCION PRINCIPAL
INICIO
    NUMERICO m, n, i, j
    NUMERICO tol, maxIter

    m = 33      // Cant de restricciones (12 "=" y 21 "<=")
    n = 21      // Cant de variables (9 pedidos x + 12 inventarios I)

    MATRIZ A[33][21]
    MATRIZ b[33][1]
    VECTOR c[21]
    STRING sense[33]        // OJO: STRING es 1-based en BLOX (1..33)

    // --------------------------------------------
    // Inicializar A y b en 0
    // --------------------------------------------
    PARA i = 0 HASTA m-1 PASO 1 HACER
        b[i,0] = 0
        PARA j = 0 HASTA n-1 PASO 1 HACER
            A[i,j] = 0
        FIN_PARA
    FIN_PARA

    // --------------------------------------------
    // sense[1..33]
    // Filas 1..12 "=" ; filas 13..33 "<="
    // --------------------------------------------
    PARA i = 1 HASTA 12 PASO 1 HACER
        sense[i] = "="
    FIN_PARA
    PARA i = 13 HASTA 33 PASO 1 HACER
        sense[i] = "<="
    FIN_PARA

    // =========================================================
    // ORDEN DE VARIABLES (columnas 0..20)
    // 0 x_CEM1, 1 x_CEM2, 2 x_CEM3,
    // 3 x_ARE1, 4 x_ARE2, 5 x_ARE3,
    // 6 x_ARI1, 7 x_ARI2, 8 x_ARI3,
    // 9 I_CEM1,10 I_CEM2,11 I_CEM3,12 I_CEM4,
    // 13 I_ARE1,14 I_ARE2,15 I_ARE3,16 I_ARE4,
    // 17 I_ARI1,18 I_ARI2,19 I_ARI3,20 I_ARI4
    // =========================================================

    // =========================================================
    // 1) BALANCES (filas 0..11)  -- todas "="
    // =========================================================

    // Fila 0: I_CEM1 = 7
    A[0, 9] = 1
    b[0,0]  = 7

    // Fila 1: I_CEM1 + x_CEM1 - I_CEM2 = 35.5
    A[1, 9]  =  1
    A[1, 0]  =  1
    A[1,10]  = -1
    b[1,0]   = 35.5

    // Fila 2: I_CEM2 + x_CEM2 - I_CEM3 = 37.5
    A[2,10]  =  1
    A[2, 1]  =  1
    A[2,11]  = -1
    b[2,0]   = 37.5

    // Fila 3: I_CEM3 + x_CEM3 - I_CEM4 = 42
    A[3,11]  =  1
    A[3, 2]  =  1
    A[3,12]  = -1
    b[3,0]   = 42

    // Fila 4: I_ARE1 = 12
    A[4,13] = 1
    b[4,0]  = 12

    // Fila 5: I_ARE1 + x_ARE1 - I_ARE2 = 80
    A[5,13]  =  1
    A[5, 3]  =  1
    A[5,14]  = -1
    b[5,0]   = 80

    // Fila 6: I_ARE2 + x_ARE2 - I_ARE3 = 88.5
    A[6,14]  =  1
    A[6, 4]  =  1
    A[6,15]  = -1
    b[6,0]   = 88.5

    // Fila 7: I_ARE3 + x_ARE3 - I_ARE4 = 94.5
    A[7,15]  =  1
    A[7, 5]  =  1
    A[7,16]  = -1
    b[7,0]   = 94.5

    // Fila 8: I_ARI1 = 12
    A[8,17] = 1
    b[8,0]  = 12

    // Fila 9: I_ARI1 + x_ARI1 - I_ARI2 = 118
    A[9,17]  =  1
    A[9, 6]  =  1
    A[9,18]  = -1
    b[9,0]   = 118

    // Fila 10: I_ARI2 + x_ARI2 - I_ARI3 = 127.5
    A[10,18] =  1
    A[10, 7] =  1
    A[10,19] = -1
    b[10,0]  = 127.5

    // Fila 11: I_ARI3 + x_ARI3 - I_ARI4 = 139.5
    A[11,19] =  1
    A[11, 8] =  1
    A[11,20] = -1
    b[11,0]  = 139.5


    // =========================================================
    // 2) CAPACIDAD DE INVENTARIO (filas 12..23)  -- "<="
    // =========================================================

    // Cemento cap 60: I_CEM1..4
    A[12, 9] = 1    b[12,0] = 60
    A[13,10] = 1    b[13,0] = 60
    A[14,11] = 1    b[14,0] = 60
    A[15,12] = 1    b[15,0] = 60

    // Arena cap 150: I_ARE1..4
    A[16,13] = 1    b[16,0] = 150
    A[17,14] = 1    b[17,0] = 150
    A[18,15] = 1    b[18,0] = 150
    A[19,16] = 1    b[19,0] = 150

    // Áridos cap 200: I_ARI1..4
    A[20,17] = 1    b[20,0] = 200
    A[21,18] = 1    b[21,0] = 200
    A[22,19] = 1    b[22,0] = 200
    A[23,20] = 1    b[23,0] = 200


    // =========================================================
    // 3) LIMITE DE PEDIDO (filas 24..32) -- "<="
    // =========================================================

    // Cemento U=50 para x_CEM1..3
    A[24,0] = 1     b[24,0] = 50    // 50
    A[25,1] = 1     b[25,0] = 50
    A[26,2] = 1     b[26,0] = 50

    // Arena U=120 para x_ARE1..3
    A[27,3] = 1     b[27,0] = 120    // 120
    A[28,4] = 1     b[28,0] = 120
    A[29,5] = 1     b[29,0] = 120

    // Áridos U=160 para x_ARI1..3
    A[30,6] = 1     b[30,0] = 160   // 160
    A[31,7] = 1     b[31,0] = 160
    A[32,8] = 1     b[32,0] = 160


    // =========================================================
    // VECTOR DE COSTOS c (MINIMIZACION) en el orden 0..20
    // =========================================================
    // pedidos
    //c[0] = 100   c[1] = 100   c[2] = 100
    //c[3] = 20    c[4] = 20    c[5] = 20
    //c[6] = 15    c[7] = 15    c[8] = 15

    c[0] = 1028000      c[1] = 1028000      c[2] = 1028000  // Cemento
    c[3] = 40000        c[4] = 40000        c[5] = 40000    // Arena
    c[6] = 120000       c[7] = 120000       c[8] = 120000   // Aridos

    // mantenimiento de inventarios
    c[9]  = 200000  c[10] = 20000   c[11] = 200000  c[12] = 200000
    c[13] = 2000    c[14] = 2000    c[15] = 2000    c[16] = 2000
    c[17] = 20000   c[18] = 20000   c[19] = 20000   c[20] = 20000


    IMPRIMIR("\nLP cargado. Llamando a Two-Phase Simplex...\n")

    // --------------------------------------------
    // Resolver
    // --------------------------------------------
    tol = 1E-6
    maxIter = 500

    TABLA sol
    sol = simplex2ph.resolver_two_phase(A, b, sense, c, tol, maxIter)

    SI (sol.ok == FALSO) ENTONCES
        IMPRIMIR("\nFallo. Status = ", sol.status, "\n")
        SI (!IGUAL(sol.msg, "")) ENTONCES
            IMPRIMIR(sol.msg, "\n")
        FIN_SI
    SINO
        IMPRIMIR("\nOK. Costo minimo = ", sol.min_cost, "\n")
        IMPRIMIR("\nSolucion (21 variables originales):\n")

        PARA i = 0 HASTA 20 PASO 1 HACER
            IMPRIMIR("x[", i, "] = ", sol.x[i], "\n")
        FIN_PARA

        IMPRIMIR("\n(Recordatorio: x[0..8] son pedidos; x[9..20] son inventarios)\n")
    FIN_SI

FINAL

resolver_two_phase(A,b,sense,c,tol,maxIter)\texttt{resolver\_two\_phase}(A, b, sense, c, tol, maxIter)resolver_two_phase(A,b,sense,c,tol,maxIter)

Parámetros

Valor de retorno

Ejemplo

$\texttt{resolver\_two\_phase}(A, b, sense, c, tol, maxIter)$