Или условие в линейното програмиране с GLPSOL AMPL/MathProg

Искам да напиша оптимизационен модел, който избира по-малката от двете задачи, в зависимост от някакво ограничение.

minimize obj: (doT1 * T1) + (doT2*T2) + (additional variables)

Сега T1 и T2 представляват продължителността на задачите, а doT1 представлява флаг за изпълнение на тези задачи. Искам тази оптимизация да избере само един от тях, ако е необходимо.

Когато поставям ограничението

s.t. c15: 0<= doT1 <= 1;
s.t. c15: 0<= doT2 <= 1;

Получавам съобщение за грешка, което в glpsol казва, че умножаването на линейни форми не е разрешено.

Възможно ли е да се изрази условието ИЛИ в линейното програмиране?


glpk ampl linear-programming mathprog
person Asif Shiraz    schedule 19.03.2014    source източник

Отговори (1)


arrow_upward
1
arrow_downward

gplsol най-вероятно се оплаква от произведението на променливи doT1 * T1 и doT2 * T2.

Предполагам, че doT1 и doT2 са двоични променливи, а T1 и T2 са непрекъснати променливи (представляващи продължителността на задачите). (Имайте предвид, че това означава, че ще трябва да използвате програма за решаване на смесено целочислено програмиране, а не програма за решаване на чисто линейно програмиране. Може също да искате да опитате да използвате мощна програма за решаване на MIP като Гуроби).

Можете да конструирате вашия модел, като пренапишете вашите ограничения и цел като

  minimize  T1 + T2 + (additional variables)

   st        T1 <= UT1*doT1
             T2 <= UT2*doT2
             doT1 + doT2 <= 1
             doT1, doT2 binary
             (plus any additional constraints)

където UT1 е горна граница на продължителността на задача T1 и UT2 е горна граница на продължителността на задача T2. Ако doT1 = 0, тогава T1 <= 0, така че задачата няма да бъде изпълнена. Ако doT1 = 1, тогава T1 <= UT1, което означава, че на задача T1 е разрешено да отнеме известно време. Същото важи и за T2.

Условието ИЛИ се изразява чрез ограничението doT1 + doT2 <= 1. Това ограничение означава, че doT1 и doT2 не могат и двете да бъдат 1. Това означава, че може да бъде избрано само едно задание. Имайте предвид, че ограничението <= също ви позволява да не изпълнявате нито една от задачите. Ако поне една задача трябва да бъде изпълнена, искате да използвате ограничението doT1 + doT2 == 1.

person codehippo    schedule 10.04.2014