Добро пожаловать, гость
:: алгоритмы  и методы :: :: олимпиадные задачи :: :: связь :: :: о сайте :: :: форум ::

Форум работает в режиме архива, только для чтения и поиска.
Архив 2004 Архив 2007 Архив 2013

 
 
Опции темы Поиск в этой теме Опции просмотра
  #1  
Старый 27.05.2010, 14:10
Новичок

Отправить личное сообщение для k0balt Посмотреть профиль Найти все сообщения от k0balt
 
Регистрация: 27.05.2010
Сообщений: 2

Поток минимальной стоимости
Доброго времени суток!
Попробую сформулировать задачу, надеюсь, подскажете метод.
Есть N видов деталей, в каждом по много деталей, которые необходимо изготовить.
Есть M станков, на которых можно изготавливать детали.
Любая деталь может быть изготовлена на любом станке. Время изготовления каждого вида деталей на каждом станке разное (Выглядит как Tп + Ти*n, где Тп - время подготовки станка к изготовлению деталей данного вида на данном станке, Ти - время изготовления одной детали данного вида на этом станке, количество деталей данного вида, необходимых для изготовления на данном станке).
При этом есть ограничение, в какой последовательности должны изготовиться детали, т.е. первыми должны изготовиться все детали 1-го вида, затем 2-го и т.д. Хотя возможна и параллельная обработка разных видов (т.е. сколько-то станков изготавляют детали 1-ого вида, одновременно сколько-то второго и т.д.)
Необходимо распределить детали по станкам так, чтобы суммарное время изготовления оказалось минимальным.

Я думал можно решить как задачу нахождения потока минимальной стоимости, но у меня выходит N потоков, и для такого случая методов решения я не нашел. Нужна помощь

Последний раз редактировалось k0balt, 27.05.2010 в 14:16. Причина: дополнил
  #2  
Старый 27.05.2010, 15:48
гость

 
Сообщений: n/a

Откуда задача?

Цитата:
При этом есть ограничение, в какой последовательности должны изготовиться детали, т.е. первыми должны изготовиться все детали 1-го вида, затем 2-го и т.д. Хотя возможна и параллельная обработка разных видов (т.е. сколько-то станков изготавляют детали 1-ого вида, одновременно сколько-то второго и т.д.)
Ну, рассмотрим какое-то решение задачи без этого ограничения, и какой-то станок. Все детали которые обрабатывает этот станок ведь можно просто отсортировать по типу, и это не ухудшит времени обработки? Таким образом, получается, ваше ограничение и не ограничение вовсе?
  #3  
Старый 27.05.2010, 15:55
Новичок

Отправить личное сообщение для k0balt Посмотреть профиль Найти все сообщения от k0balt
 
Регистрация: 27.05.2010
Сообщений: 2

Сообщение от гость Посмотреть сообщение
Откуда задача?
Курсовик пишу...
Сообщение от гость Посмотреть сообщение
Ну, рассмотрим какое-то решение задачи без этого ограничения, и какой-то станок. Все детали которые обрабатывает этот станок ведь можно просто отсортировать по типу, и это не ухудшит времени обработки? Таким образом, получается, ваше ограничение и не ограничение вовсе?
Да, согласен, получается для решения принципиально важно только какой станок какие детали будет изготавливать.
  #4  
Старый 27.05.2010, 16:50
гость

 
Сообщений: n/a

Сообщение от k0balt Посмотреть сообщение
Выглядит как Tп + Ти*n, где Тп - время подготовки станка к изготовлению деталей данного вида на данном станке, Ти - время изготовления одной детали данного вида на этом станке, количество деталей данного вида, необходимых для изготовления на данном станке
Из-за этого пункта не получится сформулировать в потоках. Если бы Tn=0, то да, это по сути сводится к классической транспортной задаче.

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


Опции темы Поиск в этой теме
Поиск в этой теме:

Расширенный поиск
Опции просмотра


Похожие темы
Тема Автор Раздел Ответов Последнее сообщение
Элементарый путь, с ограничением по весу и стоимости гость Графы 2 03.05.2009 23:18
Гамильтонов путь минимальной длины гость Графы 5 24.02.2009 01:27
Найти путь, с минимальной суммой расстояний и пошлин гость Графы 6 19.12.2008 08:52
Покрытие минимальной мощности Marat Galeyev Графы 5 03.01.2008 18:36
максимальны поток минимальной стоимости незарегистрированный Графы 1 28.12.2006 17:37