Методы оптимизации

[shukshin]

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

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

[whitefox]

shukshin в сообщении #1070405 писал(а):

б) нет идей, прошу у вас помощи.

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

[iifat]

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

[shukshin]

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

-- 08.11.2015, 10:20 --

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

[iifat]

shukshin в сообщении #1071258 писал(а):

так это фактически перебор

Это не перебор, это итерация Мне просто лень думать, как распределить штрафы, чтоб гарантированно. Подозреваю, можно попасть с первого раза.

shukshin в сообщении #1071258 писал(а):

неужели в линейном виде как-то нельзя задачу поставить?

А у меня в каком, по-вашему?

shukshin в сообщении #1071258 писал(а):

или хотя бы решать этот вопрос за хорошее время?

И с чего вы взяли, что время моим способом будет непременно плохим?

[whitefox]

shukshin в сообщении #1071258 писал(а):

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

Если максимум какого-нибудь низкоприоритетного потребителя уменьшить на единицу, то тем самым будет отменено требование полного удовлетворения всех более приоритетных потребителей.

[shukshin]

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

[mserg]

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

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

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

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

[whitefox]

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)$ уменьшены на единицу, а у остальных потребителей оставлены без изменения. Будет ли известное нам оптимальное решение первой задачи оптимальным и для второй? А наоборот — любое ли оптимальное решение второй задачи будет оптимальным решением и для первой?

[shukshin]

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
ваш метод кажется мне самым изящным. Жаль, что он подвергся критике.

[Karan]

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

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

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

-- 10.11.2015, 10:07 --

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

[Karan]

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

[whitefox]

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$, то есть последнее решение не оптимально, что противоречит предположению о его оптимальности.

[iifat]

shukshin в сообщении #1071944 писал(а):

С какой разницы начинать?

С достаточной же ж!
Я ж предупредил, что надо подумать, что мне лень.
Нам надо, чтобы единицу товара было выгоднее отправить высокоприоритетному потребителю в ущерб низко. То бишь, проигрыш в отправке, равный разнице в ценах доставки высоко- и низкоприоритетным потребителям, был меньше штрафа.
Итак: берём максимальную цену доставки. Удваиваем — нет смысла мелочиться. Это и будет шаг штрафа.
Вводим фиктивного поставщика, который будет поставлять недостачу. Упорядочиваем потребителей по возрастанию приоритета. Цена доставки от нашего фиктивного поставщика до самых низкоприоритетных (равного, минимального приоритета) поставщиков определяем нуль; поставщикам приоритетом повыше — наш шаг, ещё повыше — удвоенный шаг и т.д.
И никаких итераций.

shukshin в сообщении #1071944 писал(а):

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

Согласен, как по мне, этот метод самый изящный, хотя парочка вопросов там возникнет. Хотя, что его жалеть, не понял. Изящные методы не стесняются подвергаться критике, нимало не теряя от того своего изящества.

[shukshin]

iifat
спасибо большое! это идея!

-- 15.11.2015, 15:54 --

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