Преобразование условных операторов в линейные ограничения

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

Производитель рассматривает возможность производства трех продуктов a, b, c. Материалы, труд и прибыль для каждого продукта следующие.

продукт: (количество входного материала, рабочее время, прибыль)

a: (3,6,200)

b: (6,5,300)

c: (10,8,400)

В настоящее время доступно 12 000 единиц исходного материала и 12 000 часов рабочей силы. Установлены следующие дополнительные ограничения.

  1. Если компания решает производить «а», то она должна произвести не менее 100 единиц.

  2. Если компания решает производить автомобили категории «В», то она должна произвести не менее 80 единиц.

  3. Если компания решает производить «с», то она может произвести в общей сложности не более 120 единиц «а» и «b» (что я интерпретирую как а + b ‹ = 120, если производится «с», и а + b). в зависимости от материалов и трудовых ограничений в противном случае).

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

До сих пор я сделал следующее.

Я определяю Xa, Xb и Xc как произведенные количества a, b и c. Я ввожу бинарные переменные следующим образом:

Ya = 1, если Xa > 0, 0 в противном случае.

Yb = 1, если Xb > 0, 0 в противном случае.

Yc = 1, если Xc > 0, 0 в противном случае.

Тогда проблема:

максимизировать 200Xa + 300Xb + 400Xc

s.t.

Xa >= 0, Xb >= 0, Xc >= 0

Ya in {0,1}, Yb in {0,1}, Yc in {0,1}

3Xa + 6Xb + 10Xc < = 12,000

6Xa + 5Xb + 8Xc < = 12,000

Xa >= 100Ya

Xb >= 80Yb

Как сформулировать последнее дополнительное ограничение?

Обновлять:

После еще нескольких исследований. Ха + Xb ‹= 120 + M(1-Yc). Где M достаточно велико, чтобы Xa + Xb не было искусственно ограничено за пределами материалов и трудовых ограничений. Оставьте это на случай, если кому-то еще это может помочь.


optimization mixed-integer-programming linear-programming convex-optimization
person DeeeeRoy    schedule 24.04.2018    source источник
comment
После еще нескольких исследований. Ха + Xb ‹= 120 + M(1-Yc). Где M достаточно велико, чтобы Xa + Xb не было искусственно ограничено за пределами материалов и трудовых ограничений.   -  person DeeeeRoy    schedule 25.04.2018
comment
Пожалуйста, опубликуйте свое обновление в качестве ответа и примите его (это правильно). Обратите внимание, что традиционно значение M выбирается как минимальное значение, которое не отсекает никаких возможных решений. Фактическое значение зависит от вашей структуры проблемы. Здесь M = min{12000/3, 12000/5} - 120 является хорошим кандидатом (почему?) Современные решатели в настоящее время довольно хорошо справляются с уточнением больших значений M, но все же формулировка задачи с использованием маленького большого M никогда не помешает.   -  person Ioannis    schedule 25.04.2018
comment
Также обратите внимание, что в вашей текущей формулировке у вас могут быть Ya = Yb = 0 и Xa, Xb > 0 в оптимальном решении. Вы применили это Ya = 1 --> Xa >= 100, но не применили Ya = 0 --> Xa = 0. Я надеюсь, вы это поймете :) Наконец, кажется, что вы не можете произвести все A , B и C на положительных уровнях, поэтому мы могли бы также добавить Ya + Yb + Yc <= 2 (если вы не ожидаете, что ваши данные изменятся).   -  person Ioannis    schedule 25.04.2018

Ответы (1)


arrow_upward
1
arrow_downward

После еще нескольких исследований. Ха + Xb ‹= 120 + M(1-Yc). Где М >= 12000/5 - 120 = 2280.

Дополнительно добавить:

Ya + Yb + Yc <= 2

Поскольку постановка задачи ограничивает одновременное производство Xa, Xb и Xc.

person DeeeeRoy    schedule 25.04.2018