Помощь в написании студенческих работ
Антистрессовый сервис

Разработка оптимизационных моделей задач составления расписаний для систем конвейерного типа

Диссертация: Разработка оптимизационных моделей задач составления расписаний для систем конвейерного типа
ДиссертацияПомощь в написанииУзнать стоимостьмоей работы

Предложенные в диссертационной работе модели, методы и программное обеспечение использовались при решении задачи оптимизации загрузки оборудования для механических цехов машиностроительного предприятия ОАО «ВЭКС». На основе реальных данных о длительностях обработки и планах выпуска были построены расписания, сокращающие отклонение загрузки приборов от равномерной; Практическая значимость… Читать ещё >

Разработка оптимизационных моделей задач составления расписаний для систем конвейерного типа (реферат, курсовая, диплом, контрольная)

Содержание

  • Глава 1. Задачи теории расписаний для систем конвейерного типа
    • 1. 1. Основные понятия теории расписаний
    • 1. 2. Критерии оценки качества расписаний
    • 1. 3. Постановка задачи Беллмана — Джонсона
  • NP-трудность задач теории расписаний
    • 1. 4. Обзор основных методов решения
    • 1. 5. Выводы, постановка цели и задач исследования
  • Глава 2. Модификации задачи Беллмана — Джонсона
    • 4. Математические модели
      • 2. 1. Математическая модель для классической постановки
      • 2. 2. Задачи с неодновременным поступлением требований в систему
      • 2. 3. Задачи с неодновременным поступлением требований и обязательными задержками между стадиями
      • 2. 4. Задача с директивными сроками завершения обслуживания
      • 2. 5. Задачи с ограничением времени обслуживания
      • 2. 6. Задачи с непрерывным технологическим циклом
      • 2. 7. Задачи с запретом простоев приборов
      • 2. 8. Динамическая задача теории расписаний
      • 2. 9. Задача для системы с циклическим производством
  • Глава 3. Алгоритмы в задачах теории расписаний для конвейерных систем
    • 3. 1. Применение метода к задаче с неодновременным поступлением требований в систему
      • 3. 1. 1. Построение функции Лагранжа
      • 3. 1. 2. Минимизация функции Лагранжа щ при фиксированных двойственных переменных
      • 3. 1. 3. Вычисление субградиента
      • 3. 1. 4. Правила останова. ф 3.1.5. Пересчет двойственных переменных
      • 3. 1. 6. Нижняя оценка длины расписания
      • 3. 1. 7. Формальный алгоритм
      • 3. 1. 8. Различные подходы к оцениванию верхних границ простоев приборов и задержек требований
    • 3. 2. Применение метода к другим задачам
      • 3. 2. 1. Задача с обязательными задержками между стадиями
      • 3. 2. 2. Задача с непрерывным технологическим циклом
      • 3. 2. 3. Задача с непрерывной работой приборов 3.2.4. Задача с директивными сроками завершения обслуживания .104 4 3.2.5. Задачи с ограничением времени обслуживания
      • 3. 2. 6. Задача минимизации суммы моментов завершения обслуживания требований в системе с различными моментами поступления
      • 3. 2. 7. Вычисление нижней оценки суммы моментов завершения обслуживания требований
      • 3. 2. 8. Задача для системы с циклическим производством
  • Глава 4. Расчет календарного плана выпуска деталей в ОАО «ВЭКС»
    • 4. 1. Постановка задачи
    • 4. 2. Модель задачи и метод решения
    • 4. 3. Расчет календарного плана. Результаты

Актуальность темы

исследования. Проблема синхронизации функционирования сложных систем является важной научной и практической задачей. Особенно возросла ее значимость в последнее время в связи с массовой сменой технологий и появлением нового дорогостоящего высокотехнологичного оборудования. Эффективная организация производственных процессов в плане улучшения его использования требует упорядочения во времени определенной совокупности работ, продолжительности которых известны. Задача упорядочения работ является типичной задачей теории расписаний, изучающей распределительные задачи, в которых ограниченным ресурсом является время. Особенностью таких задач являются комбинаторные схемы поиска решений, большое число исследуемых вариантов и допустимость приближенных результатов во многих практических ситуациях. Построение приемлемого расписания равносильно согласованию во времени многих производственных операций, что дает возможность найти расчетные режимы функционирования производственной системы и, тем самым, способствует совершенствованию методов оперативного управления. Заметим, что во многих случаях затраты времени на составление планов превышают допустимые пределы. Поэтому возникает необходимость исследования проблем вычислительной сложности алгоритмов, с одной стороны, а с другой — необходимость разработки таких алгоритмов, которые в максимальной степени учитывали бы особенности производственной системы и позволяли находить приближенное решение за приемлемое время. Таким образом, стремление к достижению большей гибкости системы планирования обусловливает актуальность разработки комплекса моделей и методов составления расписаний выполнения работ для производственных систем определенного типа. Нами рассматривались системы конвейерного типа, поскольку они являются весьма распространенными.

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

Работа выполнена в соответствии с одним из основных научных направлений Воронежского государственного университета «Анализ и математическое моделирование сложных систем».

За ценные идеи, позволившие обозначить круг проблем, определить направления исследования, а также за содействие в его реализации выражаю искреннюю благодарность Лениной А. Я., кандидату технических наук, доценту кафедры ММИО факультета ПММ ВГУ.

Целью работы является разработка комплекса оптимизационных моделей задач теории расписаний для производственных систем конвейерного типа (flow-shop), а также соответствующих алгоритмов.

Для достижения указанной цели в диссертационной работе решаются следующие основные задачи:

— анализ основных разновидностей систем типа flow-shop с целью выявления их особенностей и критериев оценки качества функционирования;

— разработка математических моделей таких систем, учитывающих различные критерии качества функционирования и требования;

— разработка алгоритмов решения задач математического программирования, учитывающих качественные и структурные особенности этих задач;

— разработка компьютерных программ для составления расписаний систем конвейерного типа;

— оценка эффективности разработанных алгоритмов и программ на примере реальных технологических систем.

Объектом исследования являются системы типа flow-shop.

Предметом исследования являются модели таких систем и методы поиска оптимальных решений.

Методы исследования. В диссертационной работе использовались методы математического моделирования, исследования операций, теории расписаний, методы оптимизации и теории двойственности.

Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:

— математические модели составления расписаний для технологических систем конвейерного типа (для систем с обязательными задержками между стадиями обслуживания, с непрерывным технологическим циклом, с непрерывной работой приборов, с циклическим производством и других) в форме задач целочисленного программирования, учитывающие особенности этих систем при формировании целевой функции и/или ограничений, и в силу большой размерности ориентированные на получение приближенных решений;

— теорема о возможности сведения задачи с директивными сроками завершения обслуживания к задаче с неодновременным поступлением требований в систему без директивных сроков;

— алгоритмы получения субоптимальных расписаний, основанные на решении двойственных задач с помощью субградиентной процедуры, при этом учет структуры ограничений позволил существенно упростить вычисление координат субградиента;

— теорема об эквивалентности критерия минимизации суммы моментов завершения обслуживания требований и критерия минимизации суммарного времени пребывания требований в системе;

— априорные нижние оценки длины расписания в задаче с обязательными задержками между стадиями и в задаче с запретами простоев приборов;

— итерационная процедура вычисления априорной нижней оценки суммы моментов завершения обслуживания требований.

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

Реализация и внедрение результатов работы. Предложенные в диссертационной работе модели, методы и программное обеспечение использовались при решении задачи оптимизации загрузки оборудования для механических цехов машиностроительного предприятия ОАО «ВЭКС». На основе реальных данных о длительностях обработки и планах выпуска были построены расписания, сокращающие отклонение загрузки приборов от равномерной.

Материалы диссертации используются в учебном процессе Воронежского государственного университета при обучении студентов специальности «прикладная математика и механика» по дисциплинам «Дополнительные главы теории расписаний» и «Исследование операций».

Апробация работы. Основные результаты работы докладывались и обсуждались на VI, X Международных конференциях женщин-математиков «Математика. Образование. Экономика» (Чебоксары, 1998; Ростов-на-Дону,.

2002) — на VI Международной конференции «Экология и здоровье человека. Экологическое образование. Математические модели и информационные технологии» (Краснодар, 2001) — на 24-й международной школе-семинаре им. Шаталина С. С. «Системное моделирование социально-экономических процессов» (Воронеж, 2001) — на Международной конференции «Математика. Образование. Экология. Тендерные проблемы» (Воронеж, 2000; Пущино, 2001; Воронеж, 2003) — на V, VII, IX, X Международных конференциях «Математика. Компьютер. Образование» (Дубна, 1998, 2000, 2002; Пущино,.

2003) — на международной школе-семинаре «Современные проблемы механики и прикладной математики» (Воронеж, 2004) — на ежегодных научных конференциях Воронежского государственного университета.

Публикации. Основное содержание диссертационной работы отражено в 23 печатных работах.

Структура работы. Диссертация состоит из введения, четырех глав и заключения, изложенных на 152 страницах, списка литературы из 70 наименований и приложений, содержит 10 рисунков и 13 таблиц.

Основные результаты работы:

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

Разработаны математические модели задач составления расписаний для технологических систем конвейерного типа, различающихся дополнительными требованиями к функционированию, в форме задач целочисленного программирования;

Разработаны алгоритмы получения субоптимальных расписаний, основанные на решении двойственных задач с помощью субградиентной процедуры, существенно упрощено вычисление координат субградиента благодаря учету структуры ограничений. Создано программное обеспечение, реализующее эти алгоритмы;

Сформулирована и доказана теорема, обосновывающая возможность сведения задачи с директивными сроками завершения обслуживания к задаче с неодновременным поступлением требований в систему без директивных сроков, получено следствие;

Сформулирована и доказана теорема о математической эквивалентности двух различных по содержательному смыслу критериев: минимизации суммарного времени пребывания требований в системе и минимизации суммы моментов завершения обслуживания требованийполучено следствие;

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

Разработана итерационная процедура вычисления априорной нижней оценки суммы моментов завершения обслуживания требований.

Предложенные в диссертационной работе модели, методы и программное обеспечение использовались при решении задачи оптимизации загрузки оборудования для механических цехов машиностроительного предприятия ОАО «ВЭКС». На основе реальных данных о длительностях обработки и планах выпуска были построены расписания, сокращающие отклонение загрузки приборов от равномерной;

Материалы диссертации используются в учебном процессе Воронежского государственного университета при обучении студентов специальности «прикладная математика и механика» по дисциплинам «Дополнительные главы теории расписаний» и «Исследование операций».

ЗАКЛЮЧЕНИЕ

.

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

Теория расписаний позволяет учитывать временную и технологическую последовательность выполнения работ. Большую ценность имеют результаты, получаемые при исследовании моделей широкого круга задач упорядочения, возникающих в различных областях производства. Для исследования моделей применялись математические методы теории расписаний, теории оптимизации с использованием возможностей современной вычислительной техники.

Показать весь текст

Список литературы

  1. Bellman R. Some Combinatorial Problems Arising in the Theory of Multistage Processes / R. Bellman, O. Gross // J. Soc. 1.dust. and Appl. Math. — 1954. -V.2, № 3. — P. 175−183.
  2. Bellman R. Mathematical Aspects of Scheduling Theory / R. Bellman // J. Soc. Indust. and Appl. Math. 1956. — V.4, № 3. — P. 168−205.
  3. P.B. Теория расписаний / P.B. Конвей, В. Л. Максвелл, Л. В. Миллер. М.: Наука, 1975.
  4. B.C. Введение в теорию расписаний / B.C. Танаев, В. В. Шкурба. -М.: Наука, 1975.
  5. Теория расписаний и вычислительные машины / Под ред. Коффмана Э. Г. М.: Наука, 1984.
  6. Г. Оптимизация в технике / Г. Реклейтис, А. Рейвиндран, К. Рэгсдел. М.: Мир, 1986. — Т.1,2.
  7. В.И. Структурно-логические методы исследования сложных систем с применением ЭВМ / В. И. Левин М.: Наука, 1987.
  8. Исследование операций. Т.2. / Под ред. Моудера Дж., Элмаграби С. М.: Мир, 1981.
  9. B.C. Теория расписаний. Многостадийные системы / B.C. Танаев, Ю. Н. Сотсков, В. А. Струсевич М.: Наука, 1989.
  10. В.И. Задача М станков при поступлении деталей в режиме реального времени / В. И. Левин // Автомат, и телемех. 1989. — № 1. — С. 141 154.
  11. В.И. Оптимизация расписаний в системах с неопределенными временами обработки. 1,11 / В. И. Левин // Автомат, и телемех. 1995. — № 2. -С. 99−110. — № 3. — С. 106−116.
  12. В.А. Определение возможного минимума продолжительности выполнения комплекса работ / В. А. Афанасьев, В. В. Карелин // Кибернетика. 1974.-№ 1.-С. 89−90.
  13. В .Я. О выборе последовательности загрузки станков / В.Я. Бурдюк//Экон. и мат. методы. 1970.-Т.6, № 1.-С. 112−116.
  14. Н.А. К вопросу упорядочения обработки деталей / Н. А. Лепешкинский // Изв. АН БССР. Сер. физ.-мат. наук. 1966. — № 2. — С. 3135.
  15. Н.А. Об одной задаче теории расписаний / Н. А. Лепешкинский // Изв. АН БССР. Сер. физ.-мат. наук. 1966. — № 3. С. 90−96.
  16. В.В. О некоторых обобщениях одномаршрутной задачи календарного планирования /В.В. Доцатов, А. В. Тогер // Машинная обработка информации. Киев, 1970. — Вып.29. — С. 92−98.
  17. Р. Задача календарного планирования для циклически повторяющегося производства / Р. Солих // ЖВМ и МФ. 1973. — Т.13, № 2. — С. 326 342.
  18. Ю.М. Минимизация времени ожидания комплексов работ при двухэтапном обслуживании / Ю. М. Шурайц // Автомат, и телемех. 1977. -№ 12. С. — 138−144.
  19. В.Г. К сложности составления расписания произвольной системы / В. Г. Тимковский // Изв. АН СССР. Техн. кибернетика. 1985. -№ 3.-С. 102−109.
  20. В.Г. Приближенное решение задачи составления расписания циклической системы / В. Г. Тимковский // Экон. и мат. методы. 1986. -Т.22, № 1. — С. 171−174.
  21. Е.В. Задача сетевого планирования в постановке «точно вовремя» и потоковый алгоритм ее решения / Е. В. Левнер, А. С. Немировский // Численные методы оптимизации и анализа. Новосибирск: Сиб. энерг. ин-т, 1992.-С. 18−53.
  22. Ахо А. Построение и анализ вычислительных алгоритмов / А. Ахо, Дж. Хопкрофт, Дж. Ульман М.: Мир, 1979.
  23. М. Вычислительные машины и труднорешаемые задачи / М. Гэри, Д. Джонсон -М.: Мир, 1982.
  24. Э.М. О сравнительной сложности некоторых задач дискретной оптимизации / Э. М. Лившиц, В. И. Рублинецкий // Вычислит, мат. и вычислит. техн. 1972. — Вып.З. — С. 78−85.
  25. В.И. Оптимальное планирование работ в конвейерных системах / В. И. Левин, И. Ю. Мирецкий // Автомат, и телемех. 1996. — № 6. — С. 3−30.
  26. Johnson S.M. Optimal Two and Three Stage Production Schedules with Set Up Times Included / S.M. Johnson // Nav. Res. Log. Quart. 1954. — V. l, № 1. — P. 61−68.
  27. E.H. Некоторые замечания к теореме Джонсона / Е. Н. Хоботов // Автомат, и телемех. 1995. — № 10. — С. 186−187.
  28. Г. Основы исследования операций / Г. Вагнер Т. 1,2. — М.: Мир, 1973.
  29. Р. Прикладные задачи динамического программирования / Р. Беллман, С. Дрейфус М.: Наука, 1965.
  30. В.И. Итеративные алгоритмы определения расписаний в информационно-вычислительных системах / В. И. Хореев // Автоматика и вычислит. техника. 1987. — № 4. — С. 8−14.
  31. В.И. Использование метода переменного базиса для решения непрерывного аналога задачи Джонсона / В. И. Муравьев, И. В. Романовский // Исследование операций и статист, моделирование. Л., 1974. -Вып.2. — С. 27−37.
  32. Giglio R.J. Approximate Solutions to the Three-Machine Scheduling Problems / R.J. Giglio, H.M. Wagner // Oper. Res. 1964. — V.12. № 2. — P. 305−324.
  33. Story A.E. Computational Experience with Integer Programming for Job-Shop Scheduling / A.E. Story, H.M. Wagner Englewood Cliffs, N.J.: Prentice-Hall, 1963. — Ch. 14.
  34. А.Я. Приближенные методы решения задач теории расписаний на основе двойственных оценок / А. Я. Аснина // Экономико-математические модели и методы: Сб. науч. трудов. Воронеж: ВГУД989. — С. 162−168.
  35. А.Я. Об опыте решения задач Джонсона с произвольным числом станков / А. Я. Аснина, Р. А. Тищенкова // Системный анализ и моделирование социально-экономических процессов: Тр. II Всесоюз. семинара. -М., 1981.
  36. А.Я. Использование методов линейного программирования при решении некоторых задач теории расписаний / А. Я. Аснина, JI.A. Черникова // II Всесоюз. школа-семинар по оптимизации и ее приложениям в экономике: Тез. докл. Ашхабад, 1984.
  37. А.Я. Оптимизация гибкого производства БИС на основе модели календарного планирования / А. Я. Аснина, Т. О. Толстых // Модели и алгоритмы оптимизации сложных систем. Воронеж, 1985.
  38. А.Я. Об одном алгоритме решения задачи Джонсона / А. Я. Аснина, Г. Д. Чернышова // Тр. 4-й Междунар. конференции женщин-математиков, Волгоград, 27−31 мая 1996. Н. Новгород, 1997. — Т.4, вып.1 — С. 82−86.
  39. А.А. Математические модели в управлении производством / А. А. Первозванский М.: Наука, 1975.
  40. С.В. Вероятностный алгоритм формирования поисковых функций при решении задач условной оптимизации / С. В. Ворожеева, Г. Д. Чернышова // Алгоритмы моделирования и оптимизации автоматизированных систем. Воронеж, 1990. — С. 115−121.
  41. М. Математическое программирование. Теория и алгоритмы. / М. Мину М.: Наука, 1990.
  42. А .Я. Применение теории двойственности к решению задач теории расписаний / А .Я. Аснина, О. В. Толоконникова // Высокие технологии в технике, медицине и образовании: Межвуз. сб. науч. трудов. Воронеж: ВГТУ, 1997. — Ч. 1. — С. 30−36.
  43. С.Ю. О задаче теории расписаний с различными моментами поступления требований в систему / С. Ю. Балашева // Сб. работ студентов и аспирантов факультета прикладной математики и механики. Воронеж: ВГУ, 1998.-Вып.2.-С. 3−10.
  44. А.Я. Метод решения задачи теории расписаний с директивными сроками завершения обслуживания / А. Я. Ленина, С. Ю. Балашева // Математика. Компьютер. Образование: Сб. трудов VII Международной конференции. М.: Прогресс-Традиция, 2000. — С. 23.
  45. А.Я. Модель конвейерной системы с ограничением времени обслуживания / А. Я. Ленина, С. Ю. Балашева, С. В. Мосьпан // Математика. Компьютер. Образование: Тез. докл. V Междунар. конференции. Дубна, 1998.-С. 12.
  46. А.Я. О двух модификациях задачи Беллмана Джонсона: модели и алгоритм решения / А. Я. Аснина, С. Ю. Балашева // Вестник ВГТУ. Серия «САПР и системы автоматизации производства» — Воронеж: ВГТУ, 2001.-Выпуск3.1 — С. 34−39.
  47. А.Я. Итерационный метод решения одной динамической задачи теории расписаний / А. Я. Аснина, С. Ю. Балашева // Вестник ВГТУ. Серия «Вычислительные и информационно-телекоммуникационные системы». -Воронеж: ВГТУ, 2002. Выпуск 8.2. — С. 24−27.
  48. А.В. К вопросу решения некоторых динамических задач теории расписаний статическими методами / А. В. Куренков Тула: Тул. гос. университет, 1999. — 5 с. — Деп. ВИНИТИ № 1963-В96 17.06.99 г.
  49. С.Ю. Комплекс задач теории расписаний для конвейерных систем / С. Ю. Балашева // Математика. Образование. Экология. Тендерные проблемы: Материалы Международной конференции. Воронеж, 2000. -С. 46−47.
  50. А.Я. О задаче теории расписаний для конвейерной системы с циклическим производством / А. Я. Аснина, С. Ю. Балашева // Математика. Компьютер. Образование: Тез. докл. X Международной конференции. Москва-Ижевск: R&C Dynamics, 2003. — С. 84.
  51. С.Ю. О некоторых подходах к решению задачи Беллмана -Джонсона и ее модификаций / С. Ю. Балашева // Математика. Образование. Экология. Тендерные проблемы: Материалы Международной конференции. М.: Прогресс-Традиция, 2001. — Том 2. — С. 31−37.
  52. А.Я. Некоторые предложения по оцениванию верхних границ простоев приборов и требований для систем конвейерного типа / А.Я.
  53. , С.Ю. Балашева, В.В. Пшеничная // Математика. Компьютер. Образование: Тез. докл. IX Международной конференции. М.: Прогресс-Традиция, 2002. — С. 85.
  54. А.Я. Оптимизация обработки деталей при циклическом производстве / А. Я. Аснина, С. Ю. Балашева // Математика. Образование. Экономика. Тендерные проблемы: Материалы конференции. Москва, 2003. — Том 1.-С. 7−8.
  55. Воронежского зственного университетаи" — ъ-г, -г"у п, И.И. Борисов2005 г. 1. АКТо внедрении результатов диссертационной работы в учебный процесс
  56. Настоящим актом подтверждается:
  57. Декан ф-та ПММ / Шашкин А.И.fise&'16В1. ОТКРЫТОЕ55 5
  58. Платежные реквизиты: ИНН 3 662 063 336, р/сч.40 702 810 213ООО106 482, Центрально-черноземныйбанк СБ РФ, к/сч.30 101 810 600 000 000 000, £ИК 42 007 681
  59. Россия, 394 712, Воронеж Московский пр-т., 11 Тел./факс (0732) 51−21−84 153 912 BOX 890 010 E-mail: tyazhex (cpcomch. rutyazhex® KEX400. vrn.ru200 г. то'о 0A0"B8KG" аватор
  60. СПРАВКА о внедрении результатов диссертационной работы Балашевой Светланы Юрьевны
  61. В соответствии с этим рассчитаем длины расписаний стх, <т2 и <т3.0.1 5 4 1 2 32 3 4 10 15ft 5 11 18 22 27ft 9 18 20 26 29т2 4 1 5 3 21 2 4 9 15ft 7 14 17 22 26ft 14 16 21 24 300.3 4 1 2 5 3ft 1 2 8 10 15ft 7 14 18 21 26ft 14 16 22 26 28
  62. Итак, длины расписаний, полученных с помощью 3 эвристических алгоритмов, равны соответственно 29, 30 и 28. Лучшее из этих расписаний сг3 = (4,1,2,5,3). Его будем считать рекордным, а его длину — начальным рекордом для метода ветвей и границ (R=28).
  63. Дерево перебора изображено на рис. 1.1 (глава 1) и ниже. В кружках-вершинах указаны значения нижних оценок соответствующих подмножеств- рядом со стрелками указаны требования, фиксируемые при ветвлении.
  64. Дерево перебора (метод ветвей и границ для примера).iTi
  65. G54123 5 4 1 2 3 G54132 5 4 1 3 2ft 2 3 4 10 15 ft 2 3 4 9 15ft 5 11 18 22 27 ft 5 11 18 23 27ft 9 18 20 26 29 ft 9 18 20 25 31yt 5 2 0 2 1 yl 5 2 0 3 2
  66. Заметим, что в системах рассматриваемого типа может быть вычислена априорная нижняя оценка длин всех расписаний п1. Yuai + min (б, +Cj), n
  67. F = max-^ min a, — + bj + min, i—.n i~ i-.n nmin (a.j +b})+ с i i=.n /=1
  68. Решение примера закончено.
  69. У Общая схема вычисления коэффициентов су на шаге 3 алгоритма, основанного на вычислении двойственных оценок (глава 1).
  70. Из (1.7) следует, что 0< 1 для A=2.iW-l, J-I.N. Таким образом, 0< Wk, j+ Дш k=2.M, j=.N- и 0< wkj < Wk+, j -1 Для
  71. JW-1, 7=1.TV. Следовательно, если для некоторого /* w *= 1, то и wkj-=l*для всех / у. С другой стороны,*ф если для некоторого к vtg то и wkj-l для всех к>к, а если тои wkj- =0 для всех к< к .
  72. Рассмотрим 7=72. с^ = tMi +? I tkiwk, M 1 • w*/2=1 дляk=2 «k=2с=2, а следовательно и для всех к=2.М. +i =0 для А=2. Если 73 = j2, тоw3, y2+l =з, 7з +1иначе так как w37=l Для7з • Аналогично, для к=4.М wkj2+l= 0 в случае jk=j2 и wkj2+l=l в случае jk>j2
  73. Если l2 нельзя найти (то есть даже jM =j2), то су7 -tj+ t2i +. + tMi (таккак W? j2+i =0 для всех &-=2.М).
  74. Рассмотрим 7=1.-7*2−1 (в случае, если j2>). При всех таких jм мwkj7=&trade-kj2+. =1 для всех к, поэтому с у = tMi + X h-], iwkj ~ X hiwk, j+ =к=2 к=21. М МММ
  75. Mi + X h-, i ~ Yhi = Hhi ~ Л hi =ti ¦ k=2 k=2 k=1 k=2
  76. Для7=72+1 •• 73"1 (в случае, если 7з>72+1) w2j=w2j+l=0> a Для k>21. M МММwkj = wkj+1=1, поэтому Cy = tM + X = Х^/» X'*/ = hi ¦к= 3 *=3 Л=2 ?=31. М МММ
  77. Для 7=73 С1Г1М1 + X ^-1,/ Х^/ = - Х^/ = hi ± + %-где3 ifc=/3 ?=2 jfc=/33 = min {A: >3:jk>j3}, если jM > j3, и /3 =М+1, если jM =j3 .
  78. Итак, общую схему вычисления коэффициентов с у (на Шаге 3 описанного в главе 1 алгоритма) можно представить следующим образом:0. Положить р=2, д=1-
  79. Если jp >q, то для j=q.jp-l положить с у =tpij для z—1 .N-
  80. Haita lB = >p:Jl> JP * еСЛИ ju > -у р М +1, если 1 м = 7лlp-1для 7= jp (=.=7/ .) положить с у = XOt/ Дляг-I.TV-3. Положить д= 7^+1, р=1ресли после этого /?=М+1, то для j=q.N, для z=l.JV положить с у =tMi и закончить вычисления, иначе перейти к 1).
  81. Следуя упрощенной схеме вычисления коэффициентов с^ (в Приложении 2), получим сп =t.i+t2i, С12 — С12 =t2i, С/4 =t2i+t3i, Ci5 =t3i, то есть элементы сц матрицы С будут такими: хi 1 2 3 4 51 8 7 7 9 22 10 4 4 8 43 10 5 5 7 24 7 6 6 13 75 5 3 3 7 4
  82. Ячейки, закрашенные серым, соответствуют базисным переменным Ху. В них ut + Vj = Су и, следовательно Ay-Uj+v j-Cy = 0.
  83. Длина расписания составит 19 + 11 =30. Обновляем рекорд и рекордную перестановку: R=30, 7rR=7r= (4,1,2,3,5). Диаграмма Гантта для расписания: к=3 4 I 2 3 5к=2 4 1 2 3 5 Iк=1 4 1 2 3 5 2 4 6 8 10 12 14 16 18 20 22 24 26 28 30
  84. Коэффициенты Сц будут вычисляться по формулам с л = ti + %> сi2 = С-з = Cj4 = t2j, С/5 = t2j + /3/, то есть элементы Сц матрицы С будут такими:1 2 3 4 51 8 7 7 7 92 10 4 4 4 83 10 5 5 5 74 7 6 6 6 135 5 3 3 3 7
  85. Далее вычисляются потенциалы ui и v-. В таблицах ниже приведены значения (мг+у.) для вычисленных и{ и v.-, а также оценки Ai--=Mf+v---Cy.1. Аи 0 0 0 0 5−5 0 0 0 3−4 0 0 0 50 0 0 0−4 -3 -3 -3 0
  86. Длина расписания составит 19 + 9 = 28. Обновляем рекорд и рекордную перестановку: R=28, 7ГК = 7Г= (4,5,2,3,1). Диаграмма Гантта для расписания: к=3 4 5 2 3 1к=2 4 5 2 3 1 к=1 4 5 2 3 1 2 4 6 8 10 12 14 16 18 20 22 24 26 28w
  87. Коэффициенты с у будут вычисляться по формулам c^-t^+t ci2 = с/3 = ci4 = hi> ci5 = hi + hi' то есть матрица С не изменилась: i 1 2 3 4 51 8 7 7 7 92 10 4 4 4 83 10 5 5 5 74 7 6 6 6 135 5 3 3 3 7
Заполнить форму текущей работой

Сессия? Спокойно!