2014 dxdy logo

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

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


Правила форума


В этом разделе нельзя создавать новые темы.

Если Вы хотите задать новый вопрос, то не дописывайте его в существующую тему, а создайте новую в корневом разделе "Помогите решить/разобраться (М)".

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

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

Обязательно просмотрите тему Правила данного раздела, иначе Ваша тема может быть удалена или перемещена в Карантин, а Вы так и не узнаете, почему.



Начать новую тему Ответить на тему
 
 Методы оптимизации
Сообщение05.11.2015, 08:37 


20/10/12
233
Здравствуйте, уважаемые участники форума!
Вот такая задачка вызвала у меня некоторые затруднения:
Решить стандартную транспортную задачу с усложнениями ($n$ - поставщиков, $m$ - потребителей)
[нужно соблюсти а) и б)]
а) штраф за недопоставку 1 ед. груза - $ \operatorname{const} $ для любого пункта назначения из m
б) шкала приоритетов, нельзя поставить все в $i$ пункт и недопоставить в $j$, ежели $prior(i) < prior(j)$
(даны, видимо, как массив длины $m$)

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

 Профиль  
                  
 
 Re: Методы оптимизации
Сообщение05.11.2015, 15:51 
Заслуженный участник
Аватара пользователя


19/12/10
1546
shukshin в сообщении #1070405 писал(а):
б) нет идей, прошу у вас помощи.

Можно использовать редуцированные максимальные потребности для низкоприоритетных потребителей.

 Профиль  
                  
 
 Re: Методы оптимизации
Сообщение05.11.2015, 16:42 
Заслуженный участник


16/02/13
3899
Владивосток
Постоянный штраф не привносит в задачу ничего нового, по-моему. Случай, когда ресурсов больше, вы рассмотрели совершенно верно; если ресурсов меньше, то суммарный штраф совершенно предопределён (недостача ресурсов умножить на штраф), так что водим фиктивного поставщика с нулевой ценой перевозки и решаем полученную задачу.
Вторую задачу, может быть, стоит решать как раз вводя фиктивного поставщика с разной ценой перевозки, для высокоприоритетных потребителей сильно больше, чем для низкоприоритетных. Если полученное решение не устраивает (недопоставка высокоприоритетному потребителю несмотря на штраф), увеличить эту самую разницу и повторить.

 Профиль  
                  
 
 Re: Методы оптимизации
Сообщение08.11.2015, 10:19 


20/10/12
233
iifat,
так это фактически перебор. неужели в линейном виде как-то нельзя задачу поставить? или хотя бы решать этот вопрос за хорошее время?

-- 08.11.2015, 10:20 --

whitefox
а ваш метод немножко не понял. :-) можно для танкистов сформулировать?

 Профиль  
                  
 
 Re: Методы оптимизации
Сообщение08.11.2015, 11:00 
Заслуженный участник


16/02/13
3899
Владивосток
shukshin в сообщении #1071258 писал(а):
так это фактически перебор
Это не перебор, это итерация :wink: Мне просто лень думать, как распределить штрафы, чтоб гарантированно. Подозреваю, можно попасть с первого раза.
shukshin в сообщении #1071258 писал(а):
неужели в линейном виде как-то нельзя задачу поставить?
А у меня в каком, по-вашему?
shukshin в сообщении #1071258 писал(а):
или хотя бы решать этот вопрос за хорошее время?
И с чего вы взяли, что время моим способом будет непременно плохим?

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


19/12/10
1546
shukshin в сообщении #1071258 писал(а):
а ваш метод немножко не понял. :-) можно для танкистов сформулировать?
Если максимум какого-нибудь низкоприоритетного потребителя уменьшить на единицу, то тем самым будет отменено требование полного удовлетворения всех более приоритетных потребителей.

 Профиль  
                  
 
 Re: Методы оптимизации
Сообщение08.11.2015, 22:26 


20/10/12
233
whitefox
есть небольшое продвижение, я понял что значит "редуцированные максимальные потребности для низкоприоритетных потребителей". дальше продвижения нет.
ну вот есть два потребителя A и B с I и II приоритетами, с потребностями $p, q$.
возьмем и присвоим B потребность $q - 1$. Сие означает, что даже если мы найдем в оптимальном решении $ p - 1$ (не полностью), $q - 1 $(полностью) - несоответствия приоритетов, в действительности, не будет. Но это если $ p - 1$, а вот если $p - 2$? Еще уменьшать?

 Профиль  
                  
 
 Re: Методы оптимизации
Сообщение08.11.2015, 22:38 


17/10/08

1313
Предположим, что поставщики имеют 10 единиц товара. А шесть потребителей (в порядке убывания приоритета) хотят получить 2 5 4 3 1 2 единиц товара.

Редукция спроса должна уменьшить их до 10:
2 5 3 0 0 0

Дальше транспортная задача со спросом и предложение по 10.

Что здесь не так?

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


19/12/10
1546
shukshin в сообщении #1071454 писал(а):
Но это если p - 1, а вот если p - 2? Еще уменьшать?
Э-э-э . . . а смысл? Ведь редуцированная задача это обычная транспортная задача без всяких приоритетов, и условие
shukshin в сообщении #1070405 писал(а):
нельзя поставить все в i пункт и недопоставить в j, ежели prior(i) < prior(j)
для потребителей A и B будет удовлетворено в нередуцированной задаче автоматически независимо от величины недопоставки высокоприоритетному потребителю.

mserg в сообщении #1071459 писал(а):
Что здесь не так?
Возможно, что оптимальным решением нередуцированной задачи будет: 2 5 1 1 0 1.

Предположим, что оптимальное решение нередуцированной задачи нам известно. И пусть в этом решении потребитель $A$ и все более приоритетные потребители удовлетворены полностью, а все менее приоритетные — нет. Рассмотрим следующую редуцированную задачу (обычную транспортною задачу без приоритетов): максимальные потребности потребителей с приоритетом меньшим $\operatorname{prior}(A)$ уменьшены на единицу, а у остальных потребителей оставлены без изменения. Будет ли известное нам оптимальное решение первой задачи оптимальным и для второй? А наоборот — любое ли оптимальное решение второй задачи будет оптимальным решением и для первой?

 Профиль  
                  
 
 Re: Методы оптимизации
Сообщение10.11.2015, 09:59 


20/10/12
233
whitefox,
Возможно, что оптимальным решением нередуцированной задачи будет: $2 5 1 1 0 1$? Наверное, редуцированной.

По вопросам:
(попробуем пример посмотреть)
Пусть т.з. $2 5 4 3 1 2$, 10 ед. товара
Пусть опт.$2 5 3 0 0 0$
Редуцированная задача:
$2 5 3 2 0 1$
Будет ли известное нам оптимальное решение первой задачи оптимальным и для второй?
видимо нет? если редуцированная задача - обычная т.з. без приоритетов, решение $2 5 3 0 0 0$ оптимальным быть не обязано.

А наоборот — любое ли оптимальное решение второй задачи будет оптимальным решением и для первой?
тоже нет, решение второй задачи может игнорировать приоритеты? (она же обычная тз? ну хотя бы без приоритетов?)

-- 10.11.2015, 10:02 --

iifat, может быть время и не будет плохим для этой задачи.
Но во всяком случае, когда мы не знаем после какой итерации остановимся - это перебор, во всех смыслах. С какой разницы начинать? Где итерации закончить?

-- 10.11.2015, 10:04 --

mserg
ваш метод кажется мне самым изящным. Жаль, что он подвергся критике. :-)

 Профиль  
                  
 
 Posted automatically
Сообщение10.11.2015, 12:06 
Модератор


19/10/15
1198
 i  Тема перемещена из форума «Помогите решить / разобраться (М)» в форум «Карантин»
по следующим причинам:

- неправильно набраны формулы (краткие инструкции: «Краткий FAQ по тегу [math]» и видеоролик Как записывать формулы);

Исправьте все Ваши ошибки и сообщите об этом в теме Сообщение в карантине исправлено.
Настоятельно рекомендуется ознакомиться с темами Что такое карантин и что нужно делать, чтобы там оказаться и Правила научного форума.


-- 10.11.2015, 10:07 --

shukshin, наберите формулы в TeX.

 Профиль  
                  
 
 Posted automatically
Сообщение11.11.2015, 13:14 
Модератор


19/10/15
1198
 i  Тема перемещена из форума «Карантин» в форум «Помогите решить / разобраться (М)»
Тема возвращена

 Профиль  
                  
 
 Re: Методы оптимизации
Сообщение11.11.2015, 13:34 
Заслуженный участник
Аватара пользователя


19/12/10
1546
shukshin в сообщении #1071944 писал(а):
Наверное, редуцированной.
Нет, именно нередуцироованной, с приоритетами.

shukshin в сообщении #1071944 писал(а):
Пусть т.з. $2 5 4 3 1 2$, 10 ед. товара
Пусть опт.$2 5 3 0 0 0$
Редуцированная задача:
$2 5 3 2 0 1$
Для редуцированной задачи нужно взять максимумы $2\ 5\ 4\ 2\ 0\ 1.$

shukshin в сообщении #1071944 писал(а):
Будет ли известное нам оптимальное решение первой задачи оптимальным и для второй?
видимо нет? если редуцированная задача - обычная т.з. без приоритетов, решение $2 5 3 0 0 0$ оптимальным быть не обязано.
Предположим, что одним из оптимальных решений редуцированно задачи будет $2\ 5\ 2\ 1\ 0\ 0$ и, что оно лучше чем $2\ 5\ 3\ 0\ 0\ 0$, но тогда оно также будет решением и исходной нередуцированной задачи (возможно и не оптимальным) и также лучше чем $2\ 5\ 3\ 0\ 0\ 0$, то есть последнее решение не оптимально, что противоречит предположению о его оптимальности.

 Профиль  
                  
 
 Re: Методы оптимизации
Сообщение11.11.2015, 15:16 
Заслуженный участник


16/02/13
3899
Владивосток
shukshin в сообщении #1071944 писал(а):
С какой разницы начинать?
С достаточной же ж!
Я ж предупредил, что надо подумать, что мне лень.
Нам надо, чтобы единицу товара было выгоднее отправить высокоприоритетному потребителю в ущерб низко. То бишь, проигрыш в отправке, равный разнице в ценах доставки высоко- и низкоприоритетным потребителям, был меньше штрафа.
Итак: берём максимальную цену доставки. Удваиваем — нет смысла мелочиться. Это и будет шаг штрафа.
Вводим фиктивного поставщика, который будет поставлять недостачу. Упорядочиваем потребителей по возрастанию приоритета. Цена доставки от нашего фиктивного поставщика до самых низкоприоритетных (равного, минимального приоритета) поставщиков определяем нуль; поставщикам приоритетом повыше — наш шаг, ещё повыше — удвоенный шаг и т.д.
И никаких итераций.
shukshin в сообщении #1071944 писал(а):
mserg, ваш метод кажется мне самым изящным. Жаль, что он подвергся критике
Согласен, как по мне, этот метод самый изящный, хотя парочка вопросов там возникнет. Хотя, что его жалеть, не понял. Изящные методы не стесняются подвергаться критике, нимало не теряя от того своего изящества.

 Профиль  
                  
 
 Re: Методы оптимизации
Сообщение15.11.2015, 15:53 


20/10/12
233
iifat
спасибо большое! это идея!

-- 15.11.2015, 15:54 --

и спасибо всем, кто меня наставлял в этой теме :D

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

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



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

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


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

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