Объясните как решать следующую задачу: Есть некоторые группы станков : N1 станков 1-ого типа,N2 станков 2-ого типа, …. NN станков N-ого типа. Станки стоят в цехе известны расстояния между любыми двумя станками, а также между входом цеха и любым станком, выходом из цеха и любым станком. Есть технологические маршруты (далее ТМ), описывающие , какие группы станков и в каком порядке должна пройти заготовка (пример ТМ: вход- станок 7 типа – станок 2 типа – станок 5 типа - выход). Все ТМ начинаются со входа и заканчиваются выходом. Таких ТМ несколько, они все известны,также известно количество заготовок, которые должны пройти по данному ТМ, а также масса заготовки для данного ТМ (считается, что в процессе обработки на станке масса заготовки не меняется).Когда заготовка проходит по ТМ через какой-то станок, это называется операция. Каждая операция занимает некоторое время, величина этого времени для каждой операции каждого ТМ известна. Каждый отдельный станок может работать не более , чем некоторое время Т (это время одинаково для всех станков независимо от их группы). Необходимо выполнить все заданные ТМ. Предложите алгоритм для такого распределения ТМ по станкам, чтобы при этом величина мощности грузопотока по цеху была минимальна. Мощность грузопотока для одной заготовки равна произведению ее массы на расстояние, ей пройденное. Мощность грузопотока для цеха – сумма мощностей грузопотока для всех деталей, прошедших через цех. Считать, что все расстояния, время каждой операции каждого ТМ и время Т – рациональные положительные числа.
Алгоритм по возможности должен быть быстрым, но если не можете придумать такой, дайте хоть какой-нибудь
Я так понял, что если ТМ один, то получается классическая задача о поиске потока минимальной стоимости. Но из-за того , что ТМ несколько, у меня не получается решить задачу. Более того, я даже не могу сформулировать эту задачу как задачу линейного программирования (возможно у меня просто кривые руки).

в общем мне удалось сформулировать эту задачу ка к задачу линейного программирования. для этого я пронумеровал все операции, (например, если есть 5 ТМ по 10 операций в каждом, то получается всего 50 операций), и придумал граф, чьи вершины- это станки, и они соединяются несколькими ребрами Bijk , если на итом станке выполняется катая операция, и после нее заготовка идет на джитый станок. Поставив каждой такой дуге в соответствие количество заготовок, по ней прошедшее, получим переменные величины, чье значение однозначно определяет весь поток по графу. Накладывая на эти переменные ограничения , следующие из условия, получаем задачу линейного программирования. У меня, как у человека, никогда ничего не программировавшего, есть вопрос - на каком языке программирования мне ,новичку, будет проще всего реализовать такой алгоритм? Так же буду рад если кто-то предложит более быстрый алгоритм решения описанной выше задачи

задан 22 Янв '14 18:54

изменен 23 Янв '14 15:20

10|600 символов нужно символов осталось
Знаете, кто может ответить? Поделитесь вопросом в Twitter или ВКонтакте.

Ваш ответ

Если вы не нашли ответ, задайте вопрос.

Здравствуйте

Математика - это совместно редактируемый форум вопросов и ответов для начинающих и опытных математиков, с особенным акцентом на компьютерные науки.

Присоединяйтесь!

отмечен:

×155

задан
22 Янв '14 18:54

показан
474 раза

обновлен
23 Янв '14 15:20

Отслеживать вопрос

по почте:

Зарегистрировавшись, вы сможете подписаться на любые обновления

по RSS:

Ответы

Ответы и Комментарии

Дизайн сайта/логотип © «Сеть Знаний». Контент распространяется под лицензией cc by-sa 3.0 с обязательным указанием авторства.
Рейтинг@Mail.ru