Формулировка задания линейного программирования в пульпе

Итак, вот контекст того, что я пытаюсь решить:

Я хочу разделить единицы затрат на две или более компании. Теперь я решил его для двух компаний со следующей целевой функцией:

20*x1 + 30*x2 + 100*x3 + 20*x4 + 30*x5

с переменными двоичного типа.

Предположим, я получил оптимизированное решение как:

x1 = 1
x2 = 0
x3 = 0
x4 = 1
x5 = 0

это означает, что компания A будет нести ответственность за удельные затраты x1 и x4, а компания B - за остальные затраты.

Это работает нормально, и я правильно закодировал целлюлозу. Я также могу использовать ограничения, чтобы ограничить максимальную стоимость для конкретной компании, с которой начинается все это. Сумма коэффициентов представляет собой общую стоимость данного проекта. Поэтому я использую эту сумму в качестве ограничения целевой функции, чтобы ограничить стоимость компании А.

Теперь то же самое я хочу сделать с 3 или более компаниями. Я понятия не имею, как сформулировать целевую функцию или функции, поскольку я думаю, что это может привести к проблеме с несколькими целевыми функциями, но на самом деле я не уверен.

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

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

Большое спасибо за любую помощь.


person Valberto Enoc Rodrigues    schedule 26.03.2018    source источник
comment
Он очень широкий. Но если двоичная природа двоичных переменных вызывает у вас проблемы, рассмотрите company * X матрицу, описывающую, какая компания обслуживает какие единицы затрат (для вышеприведенного: матрица двоичных переменных 2 x 5). (и нет: это не многокритериальная оптимизация)   -  person sascha    schedule 26.03.2018
comment
Как бы вы реализовали ограничение, которое применяется только к строке матрицы?   -  person Valberto Enoc Rodrigues    schedule 26.03.2018
comment
Это немного похоже на проблему с назначением. На самом деле это не имеет ничего общего с многокритериальной оптимизацией.   -  person Erwin Kalvelagen    schedule 27.03.2018
comment
Да, я согласен, если исходный постер @ValbertoEnocRodrigues мог бы изменить заголовок вопроса на «Формулировка задачи назначения целиком». Это будет лучше для будущих людей, ищущих ответ.   -  person Stuart Mitchell    schedule 28.03.2018


Ответы (1)


Вы можете определить двоичную переменную следующим образом:

x_{i,j} = 1 if Company i is responsible for Unit Cost j

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

# data
companies = ["company1", "company2", ...]
products = ["prod1", "prod2", ...]
cost = {"prod1": cost1, "prod2": cost2, ...}

x = pulp.LpVariable.dicts("responsability",[(company, product) for company in companies for product in products], cat=pulp.LpBinary)    
prob = pulp.LpProblem("ilp", pulp.LpMinimize)

# objective function - assuming the cost is the same for all the companies
prob += pulp.LpSum(cost[product] * sum(x[(company, product)] for company in companies) for product in products)

# each product assigned to one company
for product in products:
   prob+= pulp.LpSum(x[(company, product)] for company in companies) == 1

# additional constraints
...
person abc    schedule 26.03.2018
comment
Я не знаю, правильно ли я понял это, назначает ли код удельные затраты для каждой компании в соответствующем ограничении? Моя цель здесь - заставить оптимизатор найти наилучшее распределение удельных затрат для каждой компании при определенных ограничениях затрат для них. Прошу прощения, если я неправильно это понял. - person Valberto Enoc Rodrigues; 26.03.2018
comment
в этом примере затраты на единицу продукции называются продуктами. В случае только двух компаний достаточно двоичной переменной. В случае 3 или более компаний вам необходимо знать, какой компании присвоена удельная стоимость. Это цель переменных (company_i, unit_cost_j), которые имеют значение 1, если unit_cost_j присвоено company_i. Ограничение гарантирует, что каждая стоимость единицы будет назначена ровно одной компании. - person abc; 27.03.2018
comment
Я безуспешно пытался приспособить это к моей проблеме, извините, что настаиваю, но когда вы говорите, что должны знать, какой компании назначена стоимость единицы (в случае более чем двух компаний), вы имеете в виду что я должен предварительно назначить unit_costs перед оптимизацией? потому что это то, что я хочу, чтобы оптимизатор делал. Мне также нужно установить ограничения, основанные на стоимости, например: company1 должна иметь общие затраты ‹= 50% от возможных общих затрат. - person Valberto Enoc Rodrigues; 28.03.2018
comment
Большое спасибо @newbie. Такой подход мне очень помог. Мне все еще нужно немного подправить ограничения, но это, по сути, решило мою проблему. - person Valberto Enoc Rodrigues; 03.04.2018