Как настроить временные / временные линейные ограничения программирования с помощью 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:

  • Fixed costs:
    • the rent for years 1 to 5 per unit are [50, 55, 55, 55, 60]
    • страхование единицы на годы с 1 по 5 составляет [ 1.0, 1.2, 1.2, 1.8, 2.0]
  • Variable costs:
    • power is based on number of items the sensor measured: 10+.05*each_measurement. Price goes up by 1% per year
    • обслуживание основано на $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:

  • Fixed costs:
    • the rent for years 1 to 5 per unit are [60, 65, 65, 70, 75]
    • страхование единицы на период с 1 по 5 год составляет [ 1.1, 1.3, 1.4, 1.7, 2.0]
  • Variable costs:
    • power is based on number of items the sensor measured: 10+.08*each_measurement. Price goes up by 1% per year
    • обслуживание основано на $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:

  • Fixed costs:
    • Maintenance for all units for years 1 to 5 are [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)

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

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

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)

Вопрос:

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

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

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

Всего необходимо измерить 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

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

Единицы взаимозаменяемы.


person dassouki    schedule 12.07.2013    source источник
comment
Вы очень хорошо покрыли стоимость компонентов, но я думаю, что нам не хватает некоторой информации. Сколько экспозиций (измерений) требуется каждый год? Можно ли назначить датчик любого типа на какое-либо измерение? Как только вы получите decision variables прозрачное, составление станет намного проще.   -  person Ram Narasimhan    schedule 13.07.2013
comment
@RamNarasimhan У меня была бы текущая фактическая экспозиция и смоделированные результаты для экспозиции будущего года, что означает, что я буду знать, что при типе датчика у местоположения будет x показаний и так далее. Для текущего года датчики, назначенные для измерений, не могут измениться; однако они могут измениться в будущем.   -  person dassouki    schedule 14.07.2013
comment
Не могли бы вы обновить определение проблемы? Сколько там локаций? Нужно ли использовать все 1500 единиц датчика типа C? Взаимозаменяемы ли эти три типа? Сколько экспозиций ожидается в год? Они нужны нам, чтобы сформулировать ЛП.   -  person Ram Narasimhan    schedule 14.07.2013
comment
@RamNarasimhan Я только что обновил quesiton   -  person dassouki    schedule 15.07.2013


Ответы (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 может иметь одно из следующих значений: {Отлично, Хорошо, Плохо, Очень плохо}.

По нашей нотации Y_2b2_poor представляет переменную решения, которую датчик типа b прикрепил к блоку 2, в конце 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, чтобы убедиться, что модель задает ему правильное условие.

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

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 и написать формулировку, чтобы увидеть, имеет ли она смысл. Попробуйте решить тривиальную задачу и продолжайте добавлять новые ограничения и переменные.

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

person Ram Narasimhan    schedule 15.07.2013
comment
Спасибо Рам за подробный ответ. Это один из тех ответов, который мне придется читать несколько раз, прежде чем я даже начну его понимать. Я действительно ценю твои усилия в этом - person dassouki; 16.07.2013
comment
Добро пожаловать. Пожалуйста, спросите меня, если что-то непонятно. SO - не лучший способ поделиться формулировкой IP. Начните с одного датчика в течение 2 лет, решите эту проблему с помощью PuLP, а затем увеличьте ее, добавив ограничения. - person Ram Narasimhan; 16.07.2013