Я работаю над проблемой моделирования на основе ограничений. Чтобы начать с примера, ниже приведен вывод, полученный из кода, который удовлетворяет всем ограничениям модели, кроме одного:
col1 col2 col3 col4 col5 col6 col7
et1 0.0 0.0 0.0 0.0 100.5 0.0 327.2
et2 0.0 0.0 0.0 0.0 0.0 0.0 12.2
et3 0.0 129.1 0.0 0.0 0.0 223.6 0.0
et4 0.0 0.0 0.0 0.0 0.0 58.3 0.0
et5 0.0 0.0 0.0 0.0 0.0 0.0 22.7
et6 0.0 0.0 0.0 0.0 0.0 31.9 0.0
et7 0.0 0.0 0.0 380.0 16.4 0.0 0.0
et8 0.0 0.0 0.0 0.0 0.0 29.4 0.0
et9 0.0 0.0 0.0 0.0 171.5 0.0 0.0
et10 0.0 0.0 372.9 0.0 101.6 0.0 0.0
et11 0.0 0.0 0.0 0.0 0.0 0.0 27.9
et12 0.0 170.9 0.0 10.0 0.0 0.0 0.0
5 ограничений выходной матрицы:
1) Сумма столбца должна быть между 300 и 390, оба значения включительно.
2) Сумма строки должна быть равна заданным пользователем значениям в строке.
3) Нет ненулевого значения в матрица должна быть меньше 10.
4) Количество ненулевых значений в данном столбце не должно превышать 4.
5) Столбцы должны быть расположены в указанном c порядок, который я определю ниже.
Как видно из выходной матрицы, соблюдаются ограничения с 1 по 4. Столбец 1 не соответствует ограничению № 1, но это нормально, и мы можем отфильтровать его из матрицы, чтобы удовлетворить все ограничения.
Это подводит нас к ограничению № 5, которое сложнее реализовать. Чтобы привести пример решения, которое также удовлетворяет ограничению № 5, см. Следующий пример:
col1 col2 col3 col4 col5 col6 col7
et1 305.5 122.2 0.0 0.0 0.0 0.0 0.0
et2 0.0 12.2 0.0 0.0 0.0 0.0 0.0
et3 0.0 165.6 187.1 0.0 0.0 0.0 0.0
et4 0.0 0.0 58.3 0.0 0.0 0.0 0.0
et5 0.0 0.0 22.7 0.0 0.0 0.0 0.0
et6 0.0 0.0 31.9 0.0 0.0 0.0 0.0
et7 0.0 0.0 0.0 300.0 96.4 0.0 0.0
et8 0.0 0.0 0.0 0.0 29.4 0.0 0.0
et9 0.0 0.0 0.0 0.0 171.5 0.0 0.0
et10 0.0 0.0 0.0 0.0 23.3 360.0 91.2
et11 0.0 0.0 0.0 0.0 0.0 0.0 27.9
et12 0.0 0.0 0.0 0.0 0.0 0.0 180.9
Как показано выше, ниже приведен желаемый вывод, который удовлетворяет ограничению № 5. Несколько вещей, которые определяют это из вывода видно:
1) Значение первого столбца и первой строки должно быть ненулевым.
2) Если значение в паре ненулевое, то значение в следующий столбец в той же строке или в следующей строке также должен быть ненулевым.
3) Если значение столбца равно нулю, все значения в столбце под нулем также должны быть равны нулю.
Я пытаюсь выяснить, как наилучшим образом реализовать 5-е ограничение, но врезался в стену. Ниже приведен код Python pyomo, с которым я работаю, удовлетворяет 4 из 5 ограничений. Было бы здорово получить информацию по этому вопросу. Спасибо.
from pyomo.environ import *
import pandas as pd
import sys
import math
import numpy as np
# Define the path of glpk solver on local computer
solver = SolverFactory('glpk')
maxlen = 390
minlen = 300
npiece = 4
piecelen = 10
# Input data: E&T Ticket values
etinput = [427.7,12.2,352.7,58.3,22.7,31.9,396.4,
29.4,171.5,474.5,27.9,180.9]
# Create data structures to store values
etnames = ['et'+str(e) for e in list(range(1,len(etinput)+1))]
colnames = ['col'+str(e) for e in list(range(1,math.ceil(sum(etinput)/minlen)))] #+1 as needed
et_val = dict(zip(etnames, etinput))
lowerlimit = [minlen]*len(colnames)
upperlimit = [maxlen]*len(colnames)
npiecelist = [npiece]*len(colnames)
# Dictionaries containing upper, lower limit and number of pieces in each column
col_val_dict_lower = dict(zip(colnames, lowerlimit))
col_val_dict_upper = dict(zip(colnames, upperlimit))
col_piece_dict = dict(zip(colnames, npiecelist))
# Instantiate Concrete Model
model2 = ConcreteModel()
# define variables and set upper bound to 390
model2.vals = Var(etnames, colnames, domain=NonNegativeReals,bounds = (0, maxlen), initialize=0)
# Create Boolean variables
bigM = 10000
model2.y = Var(colnames, domain= Boolean)
model2.z = Var(etnames, colnames, domain= Boolean)
# Minimizing the sum of difference between the E&T Ticket values and rows
model2.minimizer = Objective(expr= sum(et_val[r] - sum(model2.vals[r, c] for c in colnames)
for r in etnames ),
sense=minimize)
model2.reelconstraint = ConstraintList()
for c in colnames:
model2.reelconstraint.add(sum(model2.vals[r,c] for r in etnames) <= bigM * model2.y[c])
# Set constraints for row sum equal to ET values
model2.rowconstraint = ConstraintList()
for r in etnames:
model2.rowconstraint.add(sum(model2.vals[r, c] for c in colnames) <= et_val[r])
# Set contraints for upper bound of column sums
model2.colconstraint_upper = ConstraintList()
for c in colnames:
model2.colconstraint_upper.add(sum(model2.vals[r, c] for r in etnames) <= maxlen)
# Set contraints for lower bound of column sums
model2.colconstraint_lower = ConstraintList()
for c in colnames:
model2.colconstraint_lower.add(sum(model2.vals[r, c] for r in etnames) + bigM * (1-model2.y[c]) >= minlen)
#each cell needs to have a decision to use or not use
model2.bool = ConstraintList()
for c in colnames:
for r in etnames:
model2.bool.add(model2.vals[r,c] <= bigM * model2.z[r,c])
#each cell we use needs to be >= peicelen
model2.min_cut = ConstraintList()
for c in colnames:
for r in etnames:
model2.min_cut.add(model2.vals[r,c] >= piecelen - bigM *(1- model2.z[r,c]))
#each col needs to have at most npiece decisions (only 4 pieces on each reel)
model2.npienceconstraint = ConstraintList()
for c in colnames:
model2.npienceconstraint.add(sum(model2.z[r, c] for r in etnames) <= npiece)
# Create dataframe of output
solver.solve(model2)
pdtest = pd.DataFrame([[model2.vals[r, c].value for c in colnames]
for r in etnames],
index=etnames,
columns=colnames)
display(pdtest)
# Evaluate column sums
pdtest.sum(axis=0)
print("total scrap produced")
print(round(model2.minimizer(),0))