Как настроить временные / временные ограничения линейного программирования, используя PuLP?

Я пытаюсь решить гипотетическую линейную задачу, используя PuLP. Задача состоит в том, чтобы минимизировать затраты на эксплуатацию в течение 5-летнего горизонта при максимальном увеличении формы и состояния продукта. Проблема должна генерировать 5 затрат, по одной на каждый год при оптимизации системы в целом и операций каждого года.

total_cost = [(var_cost[year] + fix_cost[year] + cost_new_sensors[year]) for year in range(0,5)]

total_cost включает в себя обслуживание трех типов датчиков:

                   # units    price_new fixed_cost_per_unit_per_yr   variable_costs_pr_yr_pr_unit
sensor_type_a      300        $50       rent + insurance             power + maint
sensor_type_b      900        $75       rent + insurance             power + maint
sensor_type_c      1500       $90       maint + insurance            -
  • Проблема должна учитывать, что для каждого года датчики находятся в лучшем состоянии, чем годом ранее, а также не может быть более 12% датчиков с состоянием "Very poor",
  • Система должна иметь возможность заменить датчик одного типа на другой или понизить цену покупки нового датчика, если экспозиция не высока. (Это утверждение не связано с этим постом)

За sensor_type_a :

  • Фиксированные расходы:
    • арендная плата за годы от 1 до 5 за единицу [50, 55, 55, 55, 60]
    • страховка на единицу на годы с 1 по 5 [ 1.0, 1.2, 1.2, 1.8, 2.0]
  • Различные цены:
    • мощность зависит от количества предметов, измеренных датчиком: 10+.05*each_measurement, Цена растет на 1% в год
    • техническое обслуживание основано на $500 for the total number of sensors + each_measurement*2.45, Цена растет на 2% в год
  • Индекс экспозиции показывает состояние каждого датчика и основан на следующей таблице:

_

exposure(# of measurements)    category
<=100                          excellent
250                            good
400                            poor
>=400                          very poor

За sensor_type_b :

  • Фиксированные расходы:
    • арендная плата за годы от 1 до 5 за единицу [60, 65, 65, 70, 75]
    • страховка на единицу на годы с 1 по 5 [ 1.1, 1.3, 1.4, 1.7, 2.0]
  • Различные цены:
    • мощность зависит от количества предметов, измеренных датчиком: 10+.08*each_measurement, Цена растет на 1% в год
    • техническое обслуживание основано на $500 for the total number of sensors + each_measurement*2.65, Цена растет на 1,5% в год
  • Индекс экспозиции показывает состояние каждого датчика и основан на следующей таблице:

_

exposure(# of measurements)    category
<=200                          excellent
350                            good
500                            poor
>=500                          very poor

За sensor_type_c :

  • Фиксированные расходы:
    • Техническое обслуживание для всех блоков в течение 1 до 5 лет [5000, 5100, 5200, 5300, 5400]
    • страховка на единицу на годы с 1 по 5 [ 1.1, 1.3, 1.4, 1.7, 2.0]
  • Индекс экспозиции показывает состояние каждого датчика и основан на следующей таблице:

_

exposure(# of measurements)    category
<=300                          excellent
450                            good
600                            poor
>=600                          very poor

Моя целевая функция / уравнение является одной из минимизации:

problem = pulp.LpProblem(’Cost Minimization’, pulp.LpMinimize)

Мои ограничения:

У меня проблемы с настройкой функций ограничения. Вот что я концептуально думаю сделать (смесь псевдо и Python):

problem += sum([fixed_costs[yr][a] + var_costs[yr][a]
                               for a in sensor_type_a
                               for yr in years])

problem += sum([fixed_costs[yr][b] + var_costs[yr][b]
                               for a in sensor_type_b
                               for yr in years])

problem += sum([fixed_costs[yr][c] + var_costs[yr][c]
                               for a in sensor_type_c
                               for yr in years])

problem += sum(sensor_type_[a].condition('very poor') + \
               sensor_type_[b].condition('very poor') + \
               sensor_type_[c].condition('very poor')) <= 12%

problem += sum(sensor_type_[a].average_condition(yr) + \
               sensor_type_[b].average_condition(yr) + \
               sensor_type_[c].average_condition(yr) >=
               sensor_type_[a].average_condition(yr-1) + \
               sensor_type_[b].average_condition(yr-1) + \
               sensor_type_[c].average_condition(yr-1)

Вопрос:

Если я не на правильном пути с моим псевдо +python, как я могу правильно настроить свои ограничения для решения проблемы?

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

Изменить, чтобы отразить комментарии ниже:

Всего необходимо измерить 2700 единиц или мест. У меня есть таблица следующего характера:

   unit_ID  actual_2013   forecasted_2014   forecasted_2015   forecasted_2016   forecasted_2017
         1           25                30                40                35    50
         2          400               430               460               480    50
         n          x_1               x_2               x_3               x_4    x_5

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

Единицы являются взаимозаменяемыми.

Источник

1 ответ

Решение

Вот как я подхожу к этому.

Общие положения

Во-первых, вы хотите отделить формулировку модели от реализации кода в PuLP или иным образом.

Если вы правильно сформулируете формулировку, ее станет намного проще реализовать. (Вы справедливо отмечаете, что в вашей проблеме есть некоторые хитрые ограничения.)

Одно последнее предложение, прежде чем мы рассмотрим формулировку: у вас есть довольно сложный и подробный набор затрат и ограничений. Я предлагаю получить базовую формулировку и решение LP, а затем разделить ограничения и детальные затраты (аренда, обслуживание и т. Д.). В противном случае вы потратите огромное количество времени на отладку и проверку вашей модели.

Формулировка IP

Решающие переменные против входных констант

У нас есть три типа датчиков s = {a, b, c}, У нас есть временной горизонт 5 лет = t = {1..5} У нас около 2700 локаций l = {1..2700}

Основная переменная принятия решения - решение о том, какой сенсорный тип идет в какое место

Let `X_lst` be 1 if the unit at location l gets assigned a sensor of type `s` in year `t`
           0 otherwise

 Let `N_st` be the total number of sensors of type s used in year t

X и N являются переменными решения.

Нам также дают много "констант" (это ваши входные таблицы.)

Let E_lt be the total number of exposures in location l in year t.

(Обратите внимание, что E_lt задан или прогнозируется вне проблемы. Выход IP не решает это.

Нужен один последний набор переменных решения:

Позволять Y_lst_ctype будет 1, если в конце периода времени t тип датчика s в местоположении l окажется в состоянии ctype на основе количества воздействий, которые он почувствовал в этом году.

ctype может быть одним из {Отлично, Хорошо, Плохо, VeryPoor}

В нашей записи Y_2b2_poor представляет переменную решения, которую тип датчика b, подключенный к блоку 2, в конце второго года заканчивается poor состояние.

Ограничения

Теперь давайте начнем моделировать многочисленные ограничения, которые вы упомянули:

Ограничение покрытия Каждое место должно иметь датчик каждый год. (сумма по s) X_lst = 1 для каждого t, для каждого местоположения l.

Ограничение общего количества Для каждого типа датчика в каждом году у нас есть уравнение для общего числа.

N_st = X_1st + X_2st + ... + X_2700st for each sensor type s, and for each time period t

(Эти ограничения иногда называют "определениями". Они обеспечивают внутреннюю согласованность N и X.)

Начальные условия

N_a1 <= 300
N_b1 <= 900
N_c1 <= 1500

Ограничения, связанные с состоянием датчика

Это немного сложно, и поэтому нам пришлось ввести так много 0/1 типа Y переменные.

Каждый датчик может оказаться только в одном состоянии

Y_lst_excellent + Y_lst_good + Y_lst_poor + Y_lst_verypoor = 1

Теперь у нас есть запись ряда линейных ограничений, которые определяют состояние датчика на основе количества воздействий.

Уловка Мы должны использовать метод big-M, чтобы убедиться, что модель назначает ему правильное условие.

Для датчика типа А

E_lt x X_lat <= 100 + M (1- Y_lat_good)

E_lt x X_lat <= 250 + M (1- Y_lat_poor)

E_lt x X_lat <= 400 + M (1- Y_lat_verypoor)

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

Сделайте это также для датчиков типов b и c.

Ограничение процента до очень плохого состояния

Y_1st + Y_2st + Y_3st + ... + Y_2700st <= 0.12 x Nst (for each sensor type s, year t)

Объективная функция

Вы уже перечислили его, поэтому я просто упомяну контур, который примет целевая функция.

Min sum_all_cots x X_lst, где сумма будет иметь компоненты, связанные с арендой, обслуживанием и заменой.

Последнее замечание Чтобы быть сверхточным, вам также нужна переменная решения, которая решает, сохранять ли или заменять новым датчиком в каждом месте.

R_lst = 1 if location l gets a NEW sensor of type s at the end of year t

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

Вы должны перевести на свою модель Python и выписать формулировку, чтобы понять, имеет ли она смысл. Попробуйте это на тривиальной проблеме, и продолжайте добавлять больше ограничений и переменных.

Надеюсь, что это поможет вам двигаться вперед.

Источник
Другие вопросы по тегам