Как подсчитать различное количество переменных решения - линейное программирование

Question

У меня есть 5 переменных решения (скажем) x1 - x5, нижняя граница для каждого = 5 и верхняя граница для каждого = 30, и им разрешено принимать только целые значения. Эти переменные решения используются для расчета валовой прибыли (с помощью некоторой функции), а целевая функция - максимизировать валовую прибыль.

Теперь, выбирая оптимальные значения для x1 - x5, у меня есть ограничение, что у меня не должно быть более 2 (скажем) различных значений для x1 - x5.

Кто-нибудь, пожалуйста, помогите мне в том, как я могу сформулировать указанное выше ограничение, то есть количество различных значений переменных решения <= 2. Я пытаюсь построить программу на pyomo. </p>

Спасибо .

Answer 1

Есть разные способы смоделировать это. Вот простой подход. Сначала введите двоичные переменные:

  y(i,k) = 1  if x(i)=k    i=1,..,5, k=5,...,30
           0  otherwise

Это означает, что мы можем написать:

  x(i) = sum(k, k*y(i,k))
  sum(k, y(i,k)) = 1       for all i

, чтобы связать x и y. Теперь представьте двоичную переменную:

  z(k) = 1   if some x(i)=k
         0   otherwise  (actually we will allow 0 or 1 when all x(i)<>k, see below)

Мы хотим, чтобы максимум 2 из них равнялся 1. Это можно кратко сформулировать как:

  z(k) >= y(i,k)       for all i,k
  sum(k, z(k)) <= 2 

Обратите внимание, что это всего лишь граница. У нас есть

  y(i,k) = 1  ==> z(k) = 1

, но на самом деле нам не требуется:

  y(i,k) = 0  ==> z(k) = 0

, но этого достаточно для данного конкретного случая. Поэтому при выводе z рекомендуется интерпретировать его значения.

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

* обновление: добавлено отсутствующее ограничение