Или условие в линейном программировании с 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