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