Линейная оптимизация с штрафами

[dzbarts]

Здравствуйте, помогите придумать идею решения.
Имеется классическая задача линейной оптимизации (транспортная с минимизацией стоимости поставок). Необходимо дополнить функцию, задав в ней систему штрафов (если некоторая переменная не равна 0, то за каждую надо заплатить свою уникальную сумму).

[пианист]

В такой постановке, боюсь, только целочисленная Вам поможет.

[dzbarts]

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

Я думал использовать функцию "позитивный ли" от аргумента, умноженный на штраф. Но такая булева функция вряд ли является линейной

[пианист]

Похоже, я ошибся, ЦЛП тут тоже не поможет. Неравенство нулю "плохое" условие ;(
Вот если заменить ноль на малую величину $\alpha$, то можно так: для каждой переменной $x$ добавляем binary $b$ и пару условий:
$\alpha(b-1) \ge x \ge \alpha(1-b)$

[пианист]

Добавлю: конечно, если сами $x$ integer, то все просто, аналогично добавляем binary $b$ и условия $b-1 \ge x \ge 1-b$

[Евгений Машеров]

dzbarts в сообщении #1573064 писал(а):

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

Замечательное свойство транспортной задачи состоит в том, что матрица там абсолютно унимодулярна (т.е. определитель равен $\pm 1$), и поэтому решение при целочисленных объёмах поставок тоже будет целочисленным. Введение дополнительных ограничений это нарушает, даже линейных. А тут вообще нелинейные. Притом дискретные (в классической ТЗ нам дико везёт, дискретность получается "сама собой", вообще же говоря это чудовищное усложнение).
Кстати, штрафы за перевозку по определённому маршруту ($x_{i,j}\ne 0$) или за привлечение определённого поставщика? (далее принимаю первое).
Можно рассматривать задачу, как задачу ЦЛП общего вида, добавив к nm целочисленным переменным $x_{i,j}$, соответствующим перевозкам от i-того поставщика к j-тому потребителю столько же "штрафных" $y_{i.j}$, так же целочисленных, связанных с основными неравенствами $My_{i,j}\ge x_{i,j}$, где M - достаточно большое число (т.е. игрек равен нулю, только если х равен нулю), в ЦФ игреки входят с коэффициентами, равными штрафам. Размерность задачи огромная, и целочисленное решение может потребовать много времени.
У Триуса "Задачи математического программирования транспортного типа" рассмотрен вариант нелинейных функций потерь, но в данной задаче это не более чем аппроксимация. Может, смотреть в сторону сетевых алгоритмов. Но в любом случае такая функция, с "порогом", сильно усложняет дело.

[dzbarts]

Евгений Машеров
пианист
Спасибо большое за ответы, но оказалось, что составитель задач некорректно задал условие и подразумевал более простой вариант. Но тем не менее было очень интересно поразбираться и в сложном варианте.