Как Эластичная Подзадача в PuLP может использоваться как ограничение?

В Python PuLP ограничение линейного программирования можно превратить в упругую подзадачу.

http: //www.coin-or. орг /Pulp /pulp.html? выделить = lpsum # упругих ограничений

Решение подзадачи оптимизирует расстояние от целевого значения.

Конечно, целевое значение является оптимальным решением этой подзадачи, но весь смысл упругости заключается в том, что мы считаем, что это решение может быть недостижимым.

Как подзадача может быть включена в общую проблему? Я попытался добавить это к проблеме, как вы добавили бы ограничение, и это привело к ошибке типа. Я попытался поместить его в целевую функцию, и это тоже не сработало.

Я не могу найти ничего в документации выше или в примерах, размещенных здесь:

https://code.google.com/p/целлюлозно-или /вики /OptimisationWithPuLP? тм = 6

Вот подзадача, которую я сформулировал:

capacity = LpConstraint(e=lpSum([ x[m][n] * len(n.items) for n in N ]),
    sense=-1, rhs=30, name=str(random.random()))
stretch_proportion = 30/50
elasticCapacity = capacity.makeElasticSubProblem(penalty=50,
    proportionFreeBoundList=[1,stretch_proportion])

Вот наиболее близкая вещь, которую я думаю, я должен включить в LP Objective:

def sub(m):
    capacity = LpConstraint(e=lpSum([ x[m][n] * len(n.items) for n in N ]),
        sense=-1, rhs=30, name=str(random.random()))
    stretch_proportion = 30/50
    elasticCapacity = capacity.makeElasticSubProblem(penalty=50,
        proportionFreeBoundList=[1,stretch_proportion])
    elasticCapacity.solve()
    return elasticCapacity.isViolated()

...

prob += lpSum( [ x[m][n] * reduce(op.add, map(D2, [i.l for i in n.items], [j.l for j in n.items]))\
    for n in N for m in M ] ) + 50 * sub(m)
7 голосов | спросил Bret Fontecchio 3 WedEurope/Moscow2014-12-03T21:10:23+03:00Europe/Moscow12bEurope/MoscowWed, 03 Dec 2014 21:10:23 +0300 2014, 21:10:23

1 ответ


0

Вот краткий ответ в виде эскиза рабочего примера:

Создайте проблему, добавьте жесткие ограничения и цель.

prob = LpProblem("My Problem", LpMinimize)
....

После того как вы это сделали, определите мягкое (эластичное) ограничение и добавьте его к проблеме с помощью pulp.prob.extend(), например так:

c_e_LHS = LpAffineExpression([(var1,coeff1), (var2,coeff2)])   # example left-hand-side expression
c_e_RHS = 30   # example right-hand-side value
c_e_pre = LpConstraint(e=el_constr_LHS, sense=-1, name='pre-elastic', rhs=c_e_RHS)   # The constraint LHS = RHS
c_e = c_e_pre.makeElasticSubProblem(penalty=100, proportionFreeBoundList=[.02,.02])   # The definition of the elasticized constraint 
prob.extend(c_e)   # Adding the constraint to the problem

На данный момент проблема была изменена, чтобы включить мягкое (эластичное) ограничение, и вы можете решить его. $ \ Ч.т.д. $.

Вот более длинный ответ: на этот вопрос отвечает группа «Целлюлозно или обсуждай» в разделе добавление эластичного ограничения . Я создал следующий пример для своих собственных целей на основе этого обсуждения и на более длинная формулировка проблемы смешивания на веб-сайте документации PuLP.

Сначала вы создадите проблему:

from pulp import *
prob = LpProblem("The Whiskas Problem", LpMinimize)

Создайте список ингредиентов:

Ingredients = ['CHICKEN', 'BEEF', 'MUTTON', 'RICE', 'WHEAT', 'GEL']

Создан словарь затрат на каждый из ингредиентов:

costs = {'CHICKEN': 0.013, 
         'BEEF': 0.008, 
         'MUTTON': 0.010, 
         'RICE': 0.002, 
         'WHEAT': 0.005, 
         'GEL': 0.001}

Создан словарь процентного содержания белка в каждом из ингредиентов:

proteinPercent = {'CHICKEN': 0.100, 
                  'BEEF': 0.200, 
                  'MUTTON': 0.150, 
                  'RICE': 0.000, 
                  'WHEAT': 0.040, 
                  'GEL': 0.000}

Создан словарь процентного содержания жира в каждом из ингредиентов:

fatPercent = {'CHICKEN': 0.080, 
              'BEEF': 0.100, 
              'MUTTON': 0.110, 
              'RICE': 0.010, 
              'WHEAT': 0.010, 
              'GEL': 0.000}

Создан словарь процента волокон в каждом из ингредиентов:

fibrePercent = {'CHICKEN': 0.001, 
                'BEEF': 0.005, 
                'MUTTON': 0.003, 
                'RICE': 0.100, 
                'WHEAT': 0.150, 
                'GEL': 0.000}

Создан словарь процентного содержания соли в каждом из ингредиентов:

saltPercent = {'CHICKEN': 0.002, 
               'BEEF': 0.005, 
               'MUTTON': 0.007, 
               'RICE': 0.002, 
               'WHEAT': 0.008, 
               'GEL': 0.000}

Создайте переменную 'prob' для хранения данных о проблемах:

prob = LpProblem("The Whiskas Problem", LpMinimize)

Создан словарь под названием "component_vars", содержащий переменные, на которые есть ссылки:

ingredient_vars = LpVariable.dicts("Ingr",Ingredients,0)

Добавьте цель.

prob += lpSum([costs[i]*ingredient_vars[i] for i in Ingredients]), "Total Cost of Ingredients per can"

Создайте жесткие ограничения ( здесь мой пример начинает отличаться от приведенного в документации ):

c1 = lpSum([ingredient_vars[i] for i in Ingredients]) == 100, "PercentagesSum"
c2 = lpSum([proteinPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 8.0, "ProteinRequirement"
c3 = lpSum([fatPercent[i] * ingredient_vars[i] for i in Ingredients]) >= 6.0, "FatRequirement"
c4 = lpSum([fibrePercent[i] * ingredient_vars[i] for i in Ingredients]) <= 2.0, "FibreRequirement"
c5 = lpSum([saltPercent[i] * ingredient_vars[i] for i in Ingredients]) <= 0.4, "SaltRequirement"

Добавьте жесткие ограничения.

for con in [c1,c2,c3,c4,c5]:
    prob += con

Определите левое выражение ограничения для эластичности:

c6_LHS = LpAffineExpression([(ingredient_vars['GEL'],1), (ingredient_vars['BEEF'],1)])

Определите ограничение для эластичности: общее количество геля и говядины составляет менее 30%.

c6= LpConstraint(e=c6_LHS, sense=-1, name='GelBeefTotal', rhs=30)

Определите эластичное ограничение:

c6_elastic = c6.makeElasticSubProblem(penalty = 100, proportionFreeBoundList = [.02,.02])

И это - это способ добавить эластичное (то есть мягкое) ограничение к проблеме:

prob.extend(c6_elastic)

Решите проблему.

prob.writeLP("WhiskasModel.lp")
prob.solve()

Выведите оптимальное решение:

for v in prob.variables():
    print v.name, "=", v.varValue

Если вы играете со штрафом и ограничениями, вы можете убедиться, что он работает так, как рекламируется.

PS, я понимаю, что название вопроса может вводить в заблуждение. Добавление эластичной подзадачи сводится к добавлению некоторых стоимостных терминов к цели, соответствующих «мягкому ограничению». Мягкое ограничение не является ограничением - это сокращение для набора терминов стоимости в цели.

ответил GrayOnGray 18 FebruaryEurope/MoscowbSat, 18 Feb 2017 00:12:34 +0300000000amSat, 18 Feb 2017 00:12:34 +030017 2017, 00:12:34

Похожие вопросы

Популярные теги

security × 330linux × 316macos × 2827 × 268performance × 244command-line × 241sql-server × 235joomla-3.x × 222java × 189c++ × 186windows × 180cisco × 168bash × 158c# × 142gmail × 139arduino-uno × 139javascript × 134ssh × 133seo × 132mysql × 132