Comments 9
Странно что автора до сих пор не спросили, собирается ли он заимплементить это решение, вопрос «висит в воздухе»…
Может я чего-то не понимаю, но по-моему эта задача похожим образом решается во всяких методичках, достаточно просто принять, что мы перевозим не товары, а партии, а затем снимая ограничение на целочисленность находим тем же МВГ допустимое решение, а потом ищем ближайшее к нему целочисленное.
Честно, год назад я потратил много времени, чтоб найти какие-нибудь материалы по решению такой задачи. Если Вы сможете такими материалами поделиться, буду Вам очень признателен.
Решение, о котором Вы говорите — это классическое решение задачи целочисленного программирования(задача линейного программирования+ограничение на целочисленность переменных). Попробуйте формализовать эту задачу в партиях(то есть теперь переменные будут означать не товары, а партии, как Вы и говорите) — не получится задача целочисленного программирования. По-моему, формализовать эту задачу в партиях мне удавалось лишь как задачу параметрического программирования, но это я точно не помню. Хотя бы если посмотреть на описанный мной пример, b1=2, а партия размера 3. Как вы целочисленной переменной, обозначающей количество партий, зададите ограничение о том, что надо привезти 2 товара?
Решение, о котором Вы говорите — это классическое решение задачи целочисленного программирования(задача линейного программирования+ограничение на целочисленность переменных). Попробуйте формализовать эту задачу в партиях(то есть теперь переменные будут означать не товары, а партии, как Вы и говорите) — не получится задача целочисленного программирования. По-моему, формализовать эту задачу в партиях мне удавалось лишь как задачу параметрического программирования, но это я точно не помню. Хотя бы если посмотреть на описанный мной пример, b1=2, а партия размера 3. Как вы целочисленной переменной, обозначающей количество партий, зададите ограничение о том, что надо привезти 2 товара?
При чем тут целочисленные ограничения? Еще раз:
1) СНИМАЕМ ограничение на целочисленность
2) Решаем любым способом на континууме возможных значений оптимальную точку, можно методами нелинейного программирования: Розенброк вполне подходит, если доп. ограничения какие-то — стандартно введем штрафную/барьерную функцию. Получим точку. Можем повторить несколько раз для различных точек, чтобы быть уверенными, что мы попали в глобальный экстремум.
3) Очевидно, что оптимальное целочисленное решение будет находится в окрестности нецелого решения. Т.О. расширяем область до тех пор, пока на окружности не будет лежать хотя бы одной точки с целочисленными координатами.
4) записываем ответ.
У меня был пример одной из лабораторок, где решалась эта задача, но к сожалению за давностью не смог найти.
1) СНИМАЕМ ограничение на целочисленность
2) Решаем любым способом на континууме возможных значений оптимальную точку, можно методами нелинейного программирования: Розенброк вполне подходит, если доп. ограничения какие-то — стандартно введем штрафную/барьерную функцию. Получим точку. Можем повторить несколько раз для различных точек, чтобы быть уверенными, что мы попали в глобальный экстремум.
3) Очевидно, что оптимальное целочисленное решение будет находится в окрестности нецелого решения. Т.О. расширяем область до тех пор, пока на окружности не будет лежать хотя бы одной точки с целочисленными координатами.
4) записываем ответ.
У меня был пример одной из лабораторок, где решалась эта задача, но к сожалению за давностью не смог найти.
Я Вам про Фому, а Вы мне про Ерёму.
На простейшем примере k=3, С={{2,2},{4,5}}, a={2,3}, b={2,3}, пожалуйста, приведите своё решение
На простейшем примере k=3, С={{2,2},{4,5}}, a={2,3}, b={2,3}, пожалуйста, приведите своё решение
И ещё, извините, что позволяю себе давать Вам советы, но всё же не раскидывайтесь словом очевидно.
Ничего страшного, видимо, привычка у меня пошла еще со времен учебников, где половина формул приводится со словами «очевидно» и «доказательство оставим для тренировки читателю».
Решение может приведу, ближе к выходным. Пока рабочая неделя, нет сил на детализированное доказательство, а концепцию я расписал выше.
Решение может приведу, ближе к выходным. Пока рабочая неделя, нет сил на детализированное доказательство, а концепцию я расписал выше.
«Очевидный» — самое опасное слово в математике. (Эрик Темпл Белл)
Я прошу Вас продемонстрировать решение на этом + возможно, ещё одном примере, для того, чтобы доказать Вашу неправоту. Про то, что Вы назвали концепцией, я Вам ответил в своём первом ответе, очень жаль, что Вы не поняли.
1) «СНИМАЕМ ограничение на целочисленность» — Вы их сначала снимаете, а потом добавляете, когда «расширяем область до тех пор, пока на окружности не будет лежать хотя бы одной точки с целочисленными координатами». Так вот, если Вы в качестве переменных возьмёте партии, у Вас не получится формализовать задачу так, чтобы эти переменные были целочисленными
2) без комментариев
3) «Очевидно, что оптимальное целочисленное решение будет находится в окрестности нецелого решения. Т.О. расширяем область до тех пор, пока на окружности не будет лежать хотя бы одной точки с целочисленными координатами.» — это неверно
Sign up to leave a comment.
Транспортная задача с партионными перевозками(«с трейлерами»)