CPLEX - снижение затрат

Question

В настоящее время я работаю с cplex и пытаюсь определить сниженную стоимость LP.Я немного озадачен результатами.Мое текущее понимание уменьшенной стоимости состоит в том, что она описывает величину, на которую коэффициент целевой функции должен улучшиться, прежде чем переменная может стать частью решения (значение = 1).

Таким образом, все основные переменные (ненулевые врешение) сократили расходы на ноль.Я читал, что переменные, которые не являются частью текущего решения, могут также иметь уменьшенную стоимость нуля, если они находятся на одном из своих пределов.Это правда?

Сниженная стоимость следующего LP смущает меня:

minimize 100*x1 + 3*x5
0 <= x0, x1, x2, x3, x4, x5, x6, x7, x8
x0 = 1
x0 - x1 - x2 = 0
x3 = 1
x3 - x4 = 0
x1 - x6 = 0
x2 - x7 = 0
-x4 + x5 - x8 = 0
-x5 + x6 + x7 + x8 = 0

Если я использую cplex для вычисления сниженной стоимости, я получаю следующий результат.

Objective Value = 3
Solution = [1, 0, 1, 1, 1, 1, 0, 1, 0]
Reduced Cost = [0 0 0 0 0 0 100 0 3]

Я не понимаю, почему переменная x1 уменьшила стоимость до нуля, она не является ни частью решения, ни верхним пределом.Если уменьшенное значение x1 не равно 100, как для переменной x7.Если я увеличу значение x1 на единицу, я получу решение, которое на 100 (стоимость) хуже, верно?

Вот мой код C ++:

#include <ilcplex/ilocplex.h>

int main () {
  IloEnv             env;
  IloModel     model(env);
  IloNumVarArray   x(env);
  x.add(IloNumVar(env)); //default: between $0$ and $+\infty$ 
  x.add(IloNumVar(env));
  x.add(IloNumVar(env)); 
  x.add(IloNumVar(env));
  x.add(IloNumVar(env)); 
  x.add(IloNumVar(env));
  x.add(IloNumVar(env));
  x.add(IloNumVar(env));
  x.add(IloNumVar(env));
  model.add(x[0] == 1);
  model.add(x[0]-x[1]-x[2] == 0);
  model.add(x[3] == 1);
  model.add(x[3]-x[4] == 0);
  model.add(x[1]-x[6] == 0);
  model.add(x[2]-x[7] == 0);
  model.add(-x[4]+x[5]-x[8] == 0);
  model.add(-x[5]+x[6]+x[7]+x[8] == 0);
  model.add(IloMinimize(env, 100*x[1] + 3*x[5]));
  IloCplex cplex(model);
  cplex.solve();
  std::cout << "Min=" << cplex.getObjValue() << std::endl;
  IloNumArray v(env);
  cplex.getReducedCosts(v, x);
  std::cout << v << std::endl;
  env.end();
}

Answer 1

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

Да.Если переменные не находятся в своих пределах, то они имеют уменьшенную стоимость нуля.Если они находятся на одном из своих пределов, они все равно могут иметь уменьшенную стоимость, равную нулю, в случае, если существует несколько первичных оптимальных решений.

Тогда ваша проблема может рассматриваться как проблема потока в следующей сети:

Каждая дуга представляет значение переменной узла, в который она входит (например, 1 = x0).Оптимальное решение соответствует пути 0-2-7-5-4-3, который имеет общую стоимость 3.Если вы введете x1 (или x6) равным 1, тогда решение изменится на x0=x1=x6=x5=x4=x3=1.

Теперь двойные значения и теневые цены имеют смысл только тогда, когда оптимальный базис остается прежним,Принудительное принуждение x1=1 изменяет оптимальный базис (поскольку оптимальный путь является оптимальным), и поэтому соответствующие двойные значения могут не иметь смысла.

Альтернативная интерпретация уменьшенной стоимости - думать о ней как о двойной ценеограничения неотрицательности (т. е. показывающие, насколько увеличится целевая функция в случае, если одна единица неосновной или базовой переменной нулевого уровня будет принудительно введена в базу на уровне 1 - при условии, что ограничения неотрицательности).Опять же, его значение может быть неправильным, если это изменение меняет оптимальный базис.

Поскольку уменьшенные затраты являются двойными значениями соответствующих ограничений неотрицательности, можно попробовать еще один эксперимент - добавить явноограничения негативности как ограничения, а затем проверить их двойные значения.Для x6>=0 я получаю двойное значение 100 и допустимое увеличение правой стороны = 1, а для x1>=0 я получаю двойное значение 0 и допустимое увеличение правой стороны 0Это практически означает, что двойное значение (то есть уменьшенная стоимость в данном случае) не имеет смысла.

Надеюсь, это поможет.