45. 동적 기획 - 생산 문제

import random as rd
from pyscipopt import Model, quicksum

def sorting(L1, L2, time_limit):

    n = len(L1)
    model = Model("Plan_sorting")

    #A[i][j] = 1   i      j ， E1[i]-S1[i]   i          
    A = [[model.addVar(vtype="B", name="A[%s,%s]" % (i, j)) for j in range(n)] for i in range(n)]
    S1 = [model.addVar(vtype="I", name="S1[%s]" % (i)) for i in range(n)]
    E1 = [model.addVar(vtype="I", name="E1[%s]" % (i)) for i in range(n)]
    S2 = [model.addVar(vtype="I", name="S2[%s]" % (i)) for i in range(n)]
    E2 = [model.addVar(vtype="I", name="E2[%s]" % (i)) for i in range(n)]

    #          
    model.setObjective(E2[n-1], "minimize")

    #          
    for i in range(n):
        model.addCons(quicksum(A[i][j] for j in range(n)) == 1)
        model.addCons(quicksum(A[j][i] for j in range(n)) == 1)

    #            
    for i in range(n):
        model.addCons(E1[i] - S1[i] - quicksum(L1[j] * A[j][i] for j in range(n)) == 0)
        model.addCons(E2[i] - S2[i] - quicksum(L2[j] * A[j][i] for j in range(n)) == 0)

    #      0
    model.addCons(S1[0] == 0)

    #        1    2，                 
    for i in range(n):
        model.addCons(S2[i] - E1[i] >= 0)
    for i in range(n-1):
        model.addCons(S1[i + 1] - E1[i] == 0)
        model.addCons(S2[i + 1] - E2[i] >= 0)

    #       
    model.setRealParam("limits/time", time_limit)
    model.optimize()
    print("
gap:", model.getGap())

    #    
    S1 = [round(model.getVal(S1[i])) for i in range(n)]
    E1 = [round(model.getVal(E1[i])) for i in range(n)]
    S2 = [round(model.getVal(S2[i])) for i in range(n)]
    E2 = [round(model.getVal(E2[i])) for i in range(n)]

    A1 = [[round(model.getVal(A[i][j])) for j in range(n)] for i in range(n)]
    r = ""
    for j in range(n):
        for i in range(n):
            if A1[i][j] == 1:
                r += str(i+1)
                if j < n-1:
                    r += "-"
                break

    return S1, E1, S2, E2, r


if __name__ == "__main__":

    #   
    n = 6

    #    
    L1 = [int(rd.random() * 10) + 1 for i in range(n)]
    L2 = [int(rd.random() * 10) + 1 for i in range(n)]
    # L1 = [3,10,5,2,9,11]
    # L2 = [8,12,9,6,5,2]
    print("
L1:
", L1)
    print("
L2:
", L2)

    S1, E1, S2, E2, r = sorting(L1, L2, 100)
    print("
S1:
", S1)
    print("
E1:
", E1)
    print("
S2:
", S2)
    print("
E2:
", E2)
    print("
r:
", r)