2014 dxdy logo

Научный форум dxdy

Математика, Физика, Computer Science, Machine Learning, LaTeX, Механика и Техника, Химия,
Биология и Медицина, Экономика и Финансовая Математика, Гуманитарные науки




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

 
 
 
 Re: Линейная оптимизация с штрафами
Сообщение08.12.2022, 10:11 
Аватара пользователя
В такой постановке, боюсь, только целочисленная Вам поможет.

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

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

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

 
 
 
 Re: Линейная оптимизация с штрафами
Сообщение08.12.2022, 11:38 
Аватара пользователя
Добавлю: конечно, если сами $x$ integer, то все просто, аналогично добавляем binary $b$ и условия $b-1 \ge x \ge 1-b$

 
 
 
 Re: Линейная оптимизация с штрафами
Сообщение10.12.2022, 10:00 
Аватара пользователя
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 - достаточно большое число (т.е. игрек равен нулю, только если х равен нулю), в ЦФ игреки входят с коэффициентами, равными штрафам. Размерность задачи огромная, и целочисленное решение может потребовать много времени.
У Триуса "Задачи математического программирования транспортного типа" рассмотрен вариант нелинейных функций потерь, но в данной задаче это не более чем аппроксимация. Может, смотреть в сторону сетевых алгоритмов. Но в любом случае такая функция, с "порогом", сильно усложняет дело.

 
 
 
 Re: Линейная оптимизация с штрафами
Сообщение10.12.2022, 11:36 
Евгений Машеров
пианист
Спасибо большое за ответы, но оказалось, что составитель задач некорректно задал условие и подразумевал более простой вариант. Но тем не менее было очень интересно поразбираться и в сложном варианте.

 
 
 [ Сообщений: 7 ] 


Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group