2014 dxdy logo

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

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




Начать новую тему Ответить на тему
 
 Линейная оптимизация с штрафами
Сообщение08.12.2022, 00:55 


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

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


03/06/08
2147
МО
В такой постановке, боюсь, только целочисленная Вам поможет.

 Профиль  
                  
 
 Re: Линейная оптимизация с штрафами
Сообщение08.12.2022, 10:16 


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

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

 Профиль  
                  
 
 Re: Линейная оптимизация с штрафами
Сообщение08.12.2022, 10:35 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Линейная оптимизация с штрафами
Сообщение08.12.2022, 11:38 
Заслуженный участник
Аватара пользователя


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

 Профиль  
                  
 
 Re: Линейная оптимизация с штрафами
Сообщение10.12.2022, 10:00 
Заслуженный участник
Аватара пользователя


11/03/08
9491
Москва
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 


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

 Профиль  
                  
Показать сообщения за:  Поле сортировки  
Начать новую тему Ответить на тему  [ Сообщений: 7 ] 

Модераторы: Модераторы Математики, Супермодераторы



Кто сейчас на конференции

Сейчас этот форум просматривают: нет зарегистрированных пользователей


Вы не можете начинать темы
Вы не можете отвечать на сообщения
Вы не можете редактировать свои сообщения
Вы не можете удалять свои сообщения
Вы не можете добавлять вложения

Найти:
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group