оптимальное решение или заполнение пустого пространства python - PullRequest
Новая
       52

оптимальное решение или заполнение пустого пространства python

0 голосов
/ 04 марта 2020

у меня есть список пустого 1D пространства с другими двумя списками элементов и его запасом этот список содержит элементы, которые заполняют пустые пробелы **: 

liste_empty_space=[[324.08,
   132.0,
   133.84,
   303.0,
   303.0,
   314.08],
  [314.0, 143.0, 143.0, 292.0, 293.84, 324.16]]

fillers=[100]+[50]+[40]+[30]+[20]+[10]+[9]+[8]+[7]+[6]+[5]+[4]+[3]+[2]+[2.02]+[2.05]+[2.1]+[2.2]+[2.3]+[2.4]+[2.5]+[2.6]+[2.7]+[2.8]+[2.9]
stock_fillers=[10]*2+[14]*12+[10]+[14]*10

filler=[]
filler.append(fillers)
filler.append(stock_fillers)

Итак, я хочу алгоритм, который заполняет все пустые места, принимая во внимание элементы, которые у нас есть, и с ограничением чисел, которые у нас есть в наличии.

, поэтому мое решение вот так: я использовал жадный подход с MIP-программой, с помощью инструмента оптимизации Google 'or-tools', но иногда он заканчивается без каких-либо решений: 

from __future__ import print_function
from ortools.linear_solver import pywraplp
from itertools import islice 

D=liste_empty_space
separetor=filler

def combination(D,separetor):

    Solutions_final=[]

    for sep in range(len(D)):

        Solutions=[]
        if len(D[sep])>10:
            inputt=iter(D[sep])
            D_sep=[list(islice(inputt, elem)) for elem in [10]*(len(D[sep])//10)+[len(D[sep])-(10*(len(D[sep])//10))]]
        else:
            D_sep=[D[sep]]
        for k in range(len(D_sep)):

            solver = pywraplp.Solver('simple_mip_program',
                             pywraplp.Solver.CBC_MIXED_INTEGER_PROGRAMMING)
            infinity = solver.infinity()
            x=[]

            for i in range(len(D_sep[k])):
                x.append([])
                for j in range(len(separetor[0])):
                    globals()['x%s%s' % (i,j)] = solver.IntVar(0.0, infinity, "x{}{}".format(i,j))
                    x[i].append(globals()['x%s%s' % (i,j)])

            for num in range(len(separetor[0])):
                constraint=0
                for asbly in range(len(x)):
                    constraint+=x[asbly][num]
                solver.Add( constraint <= separetor[1][num] )

            for i in range(len(x)):
                constraint1=0
                for j in range(len(x[i])):
                    constraint1+=x[i][j]*separetor[0][j]
                solver.Add( constraint1 == D_sep[k][i])

            Objectif=0
            for i in range(len(x)):
                for j in range(len(x[i])):
                        Objectif += x[i][j]
            solver.Minimize(Objectif)

            result_status = solver.Solve()
            # The problem has an optimal solution.
            assert result_status == pywraplp.Solver.OPTIMAL
            assert solver.VerifySolution(1e-7, True)
            # Show system solution.
            X=[]
            for i in range(len(x)):
                X.append([])
                for j in range(len(x[i])):
                    X[i].append(globals()['x%s%s' % (i,j)].solution_value())

            Solutions_sep=[]
            for i in range(len(X)):
                Solutions_sep.append([])
                for j in range(len(X[i])):
                    if X[i][j]!=0:
                        separetor[1][j] -= X[i][j]
                        l=[]
                        l.append(separetor[0][j])
                        Solutions_sep[i] += l*int(X[i][j])

            Solutions+=Solutions_sep            
        Solutions_final.append(Solutions)
    return(Solutions_final)
...