Решение модифицированных транспортных задач металлургического комплекса с использованием генетических алгоритмов тема диссертации и автореферата по ВАК РФ 05.13.01, кандидат технических наук Дубравина, Татьяна Викторовна

• Дубравина, Татьяна Викторовна
• кандидат технических наук
• 2005

Оглавление диссертации кандидат технических наук Дубравина, Татьяна Викторовна

Введение.

Глава 1. Постановка и методы решения многоиндексных транспортных задач.

1.1. Классическая транспортная задача.

1.1.1. Постановка транспортной задачи.

1.1.1. Свойства транспортной задачи.

1.1.2. Методы решения классической транспортной задачи.

1.1.3. Многокритериальные транспортные задачи.

1.2. Многоиндексные транспортные задачи.

1.2.1. Симметричные трех- и четырехиндексные транспортные задачи.

1.2.2. Уменьшение числа индексов для многоиндексных транспортных задач.

1.2.3. Методы решения многоиндексных задач.

1.3. Генетические алгоритмы.

1.3.1. Эволюционные вычисления и генетические алгоритмы.

1.3.2. Генетический алгоритм (ГА).

1.3.3. Основные генетические операторы и их версии.

1.3.4. Применение генетических алгоритмов для решения задач условной оптимизации.

1.3.5. Применение генетических алгоритмов для решения задач многокритериальной оптимизации.

1.3.6. Генетические алгоритмы для решения транспортных задач.

Глава 2. Методы конструирования генетических алгоритмов для решения модифицированных транспортных задач (МТЗ).

2.1. Объект и цели исследования.

2.2. Выбор алгоритма для решения МТЗ.

2.3. Синонимичные решения.

2.4. Анализ характеристик симметричных транспортных задач и их влияния на реализацию генетического алгоритма.

2.5. Генетические операторы для решения МТЗ.

2.5.1. Использование составных генетических операторов.

2.5.2. Особенности реализации ГО для МТЗ с разным числом индексов.

2.5.3. Генетические операторы репродукции для четырехиндексных транспортных задач.

2.6. Влияние вида ограничений МТЗ на реализацию генетического алгоритма для их решения.

2.6.1. Условия разрешимости многоиндексных транспортных задач.

2.6.2. Общее в генетических алгоритмах для решения задач с ограничениями разного типа.

2.6.3. Различия в генетических алгоритмах для решения задач с ограничениями разного типа: процедура инициализации.

2.6.4. Различия в генетических алгоритмах для решения задач с ограничениями разного типа: генетические операторы.

2.7. Рекомендации по созданию реализации генетического алгоритма для произвольной МТЗ.

Глава 3. Исследование свойств генетических алгоритмов с помощью вычислительного эксперимента.

3.1. Программная реализация.

3.1.1. Объектная структура программного обеспечения (ПО).

3.1.2. Основные возможности ПО.

3.2. Определение параметров ГА.

3.2.1. Постановка задачи определения параметров ГА.

3.2.2. Гибридный алгоритм.

3.2.3. Комбинация операторов мутации и скрещивания.

3.2.4. Синонимичные решения.

Глава 4. Решение прикладных задач на основе предложенных алгоритмов.

4.1. Постановка задачи.

4.1.1. Математическая модель.

4.1.2. Анализ модели.

4.1.3. Исходные данные задачи.

4.2. Решение поставленной задачи.

4.2.1. Настройки генетического алгоритма.

4.2.2. Программная реализация.

4.2.3. Интерпретация результатов.Ill

Введение диссертации (часть автореферата) на тему «Решение модифицированных транспортных задач металлургического комплекса с использованием генетических алгоритмов»

Актуальность

Многие предприятия металлургии работают на привозном сырье, которое, как и их продукция, доставляется в основном железнодорожным транспортом. Затраты на транспортировку составляют до 20% стоимости как привозного сырья, так и продукции, вследствие высоких тарифов на железнодорожные перевозки. Значительное число поставщиков, и покупателей, большая «номенклатура сырья и конечной продукции, нестабильная ситуация» в отрасли - все это приводит к многовариантности решения задачи транспортировки, а также к возможности быстрого его изменения в связи с меняющимися обстоятельствами. Поэтому среди задач1 управления, возникающих на металлургическом производстве, часто встречаются задачи, математическая модель которых представляет собой модифицированную транспортную задачу. Это не только различные задачи транспортировки, но и, например, задачи распределения ресурсов и размещения производства, перспективного планирования и т.п.

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

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

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

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

Цель работы

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

Задачи исследования

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

• Исследование влияния основных особенностей постановки задач класса трех- и четырехиндексных МТЗ на изменения, операторов генетического алгоритма (ГА).

• Построение генетического алгоритма как обобщенного метода решения задач данного класса.

• Разработка ГА для симметричных МТЗ с векторными правыми частями и его модификация для решения симметричных МТЗ с матричными правыми частями.

• Создание на их базе ГА для решения несимметичных МТЗ с соответствующим числом индексов.

• Исследование эффективности различных возможных модификаций полученного ГА.

• Решение с помощью разработанных алгоритмов прикладной МТЗ для металлургического производства на примере условий Выксунского металлургического завода (далее ОАО ВМЗ).

Методы исследования

Для решения поставленных задач были использованы методы системного анализа, исследования операций, теории графов, оптимизации, объектно-ориентированного программирования.

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

•1 Доказана возможность создания семейства эффективных алгоритмов решения для различных постановок-МТЗгна'основе ГА, используемого в качестве общего метода, который построен и программно реализован с использованием нового вида представления структуры генетического алгоритма.

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

• Предложен и реализован гибридный генетический алгоритм для решения МТЗ с векторными правыми частями и исследована эффективность его применения.

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

Апробация результатов. Результаты диссертационной работы докладывались и обсуждались на:

• ежегодных студенческих научно-технических конференциях МИСиС (Москва, 2001 и 2003 гг.);

• семинарах на кафедре автоматизированных систем управления Московского государственного института стали и сплавов (технологический университет).

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

Структура и объем работы. Диссертационная работа состоит из введения, четырех глав, заключения и списка литературы. Общий объем работы 140 стр.

Заключение диссертации по теме «Системный анализ, управление и обработка информации (по отраслям)», Дубравина, Татьяна Викторовна

Основные результаты работы: Доказана возможность создания семейства эффективных алгоритмов для различных постановок модифицированных транспортных задач металлургического комплекса на основе ГА, используемого в качестве общего метода. Исследованы единые механизмы решения разных типов задач. Разработаны алгоритмы реализации специфических для задач с векторными и правыми частями ограничений частей ГА.

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

Предложен и реализован гибридный генетический алгоритм для решения МТЗ с векторными правыми частями.

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

Разработанное программное обеспечение использовано при решении задачи транспортировки сырья для ОАО ВМЗ. Оно применимо на предприятиях, имеющих аналогичную структуру поставщиков и транспортного парка.

Список литературы диссертационного исследования кандидат технических наук Дубравина, Татьяна Викторовна, 2005 год

1. Акулич И.Л. Математическое программирование в примерах и задачах. М.:- Высшая школа, 1986. 317с.

2. Алексеев А.О., Транспортная задача по критерию времени при ограниченном количестве транспортных средств // Математические методы оптимизации и управления в сложных системах. Калинин. КГУ, 1984. с. 60-65

3. Арет Лариса. О решении многоиндексной задачи транспортного типа // Изв. АН ЭССР, Физ.-мат. 1974. т.23. №2. с. 155-159.

4. Астахов Н.Д., Федосеев А.В., Чан Ван Хунг. О применении ускоренных алгоритмов решения задач транспортного типа. М.: ВЦ РАН, 1994. 49с.

5. Басова А.В. Математические модели и генетические методы решения нелинейных задач транспортного типа. Автореф. дис. канд. тех. наук. Ростов-на-Дону , 2004. 15с.

6. Батищев Д.И., Исаев С.А. Оптимизация многоэкстремальных функций с помощью генетических алгоритмов./Межвузовский сборник научных трудов "Высокие технологии в технике, медицине и образовании", Воронеж, ВГТУ, 1997г, стр. 4-17.

7. Батищев Д.И., Коган Д.И., Шахриев К. Многокритериальные транспортные задачи. Изд-во Горьковского Гос. Университета, 1984. 64с.

8. Батищев Д.И., Шапочников Д.Е. Многокритериальный выбор с учетом индивидуальных предпочтений. Нижний Новгород, 1994. 92с.

9. Бирман И.Я. Транспортная задача линейного программирования. М.: Изд-во экономической литературы, 1962. -271с.

10. Бобарыкин В.А. Математические методы решения автотранспортных задач. Л.: СЗПИ, 1986.-83с.

11. Браверман Э.М. Математические модели планирования и управления в экономических системах. М.: Наука, 1976. -368с.

12. Верховский Б.С. Многомерные задачи линейного программирования типа транспортной//ДАН СССР, 1963, т. 151, №3, с.515-518.

13. Верховский Б.С. О многоиндексной транспортной задаче с аксиальными суммами // ДАН СССР, 1964, т. 156, №2, с.282-285.

14. Верховский Б.С. О существовании решения многоиндексной задачи линейного программирования // ДАН СССР, 1964, т. 158, №4, с. 763-767.

15. Глухов В.В., Спасов А.А. Экономико-математические методы в планировании и управлении на металлургическом предприятии. М.: Металлургия, 1992. 223 с.

16. Гвоздев С.Е. Математическое программирование (двойственность, транспортная задача). Новосибирск: НГАСУ, 2001, 96с.

17. Геронимус Б.Л. Экономико-математические методы в планировании на автомобильном транспорте. М.: Транспорт, 1982. 191с.

18. Глейзал ( Gleyzal А.) Алгоритм для решения задачи транспортировки, "Математика", 1958, т.2, №1.

19. Голыитейн Е.Г. Транспортная задача и ее обобщения // Сб. "Методы и алгоритмы решения транспортной задачи". Госстатиздат, 1963.

20. Голыптейн Е.Г., Юдин Д.Б. Задачи линейного программирования транспортного типа. М.: Наука, 1969. - 384 с.

21. Горбачев В.Н. Оптимизация структуры гибридного генетического алгоритма для решения задач синтеза расписаний и распределения ресурсов. Автореф. дис. канд. тех. наук. М., 2001.

22. Горячев Ю.В. Генетические алгоритмы многокритериальной конфликтной оптимизации. М.: 2001. 102с.

23. Гэри М., Джонсон Д. Вычислительные машины и труднорешаемые задачи. М.: Мир, 1982,416с.

24. Данциг Дж. Линейное программирование, его обобщения и применения. М.: Прогресс, 1966. 600с.

25. Диниш Е.А., Карзанов А.В. О сложности алгоритмов решения общей и транспортной задач линейного программирования. В кн. Управление сложными системами, вып.4. М.: ИПУ, 1974, с. 32-41.

26. Дубин А.К., Лобачев В.В., Серебряков В.И. Экономико-математические методы и модели в организации и планировании металлургического производства. М.: ГУУ, 2002. 24с.

27. Емеличев В.А., Кононенко A.M. О многогранниках многоиндексной транспортной задачи // ДАН БССР, 1972, т. 16, №5, с. 418-420.

28. Емеличев В.А., Кононенко A.M. Условие вырожденности многоиндексного транспортного многогранника // ДАН БССР, 1972, т. 16, №6, с. 506-509.

29. Емеличева B.C., Кононенко A.M. О минимальном числе вершин и граней многогранника планарной транспортной задачи // ДАН БССР, 1974, т. 18, №9, с. 781-784.

30. Емеличева B.C., Кононенко A.M. О минимальном числе целочисленных вершин многогранника многоиндексной транспортной задачи // Изв. АН БССР, Физ.-мат., 1974, №3, с. 124-126.

31. Еремеев А.В. Разработка и анализ генетического и гибридного алгоритма для решения задач дискретной оптимизации. Автореф. дис. канд. тех. наук. Омск , 2000. -22с.

32. Журавлева Е.Л. Специальные задачи линейного программирования. Транспортная задача. СПб.: СПбЛТА 2000. 32 с.

33. Жиглявский А.А. Математическая теория глобального случайного поиска. Л.: Изд-во Ленингр. ун-та, 1985, 296с.

34. Зуховицкий С.И., Авдеева Л.И. Линейное и выпуклое программирование. М.:-Наука, 1967. 460с.

35. Калашников Е.А., Дубравина Т.В., Иконникова А.А. «Постановка задачи транспортировки сырья для трубного производства» // Черные металлы, март 2005. с. 2125.

36. Коган Д.И. Дискретные многокритериальные задачи распределительного типа. Нижний Новгород, 1991. 82с.

37. Коган Д.И. Исследование и разработка методов решения многокритериальных задач распределения, обмена, упорядочения в моделях транспортного типа. Автореферат на соискание степени доктора наук. М. 1999. ??

38. Косенко Б. Многоэтапная транспортная задача. JL: Воен. академия тыла и транспорта, 1964, 110с.

39. Кун (Kuhn H.W.) Венгерский метод решения задачи о назначениях. // Сб. "Методы и алгоритмы решения транспортной задачи". Госстатиздат, 1963.

40. Кун (Kuhn H.W.) Некоторые видоизменения венгерского метода для задачи о назначениях. // Сб. "Методы и алгоритмы решения транспортной задачи". Госстатиздат, 1963.

41. Курейчик В.В, Емельянов В.В., Курейчик В.М. . Теория и практика эволюционного моделирования. М.: ФИЗМАТЛИТ , 2003 431 с.ил.

42. Курейчик В.М., Курейчик В.В. Генетические алгоритмы в комбинаторно-логических задачах искусственного интеллекта. Труды конференции КИИ'98. Пущи-но, 1998. С. 720-726.

43. Курейчик В.М. Генетические алгоритмы. Состояние, проблемы, перспективы. // Известия РАН. Теория и системы управления, 1999. №1. С. 144-160.

44. Лейбман Г.Д. Разновидности транспортных задач и решение их на ЭВМ. М.: ВЗИИТ, 1990.- 38 с.

45. Лихачев В.М., Емеличев В.А. К оценке сверху числа вершин транспортного многогранника // Вести АН БССР, 1974, т.З, с. 121-123.

46. Манкерс (Munkers J.) Алгоритм решения задачи выбора и транспортной задачи. // Сб. "Методы и алгоритмы решения транспортной задачи". Госстатиздат, 1963, стр. 73-79.

47. Миронов А.А., Цурков В.И. Открытые транспортные модели с минимаксным критерием. //Докл. РАН 2001, 381, №4, с.448-451.

48. Миронов А.А. Минимакс в транспортных задачах. М.: Наука, 1997. 399с.

49. Мовшович С.М. "Об одной задаче планирования перевозок неоднородных взаимозаменяемых продуктов". // Применение математики в экономических исследованиях, под ред. Немчинова B.C., т.З., М.: Мысль, 1965.

50. Нестеров Е.П. Транспортные задачи линейного программирования. М.:- Транспорт, 1971.- 216с.

51. Никитенков B.JI. Задачи линейного программирования и методы их решения. Сыктывкар: Сыктывкар. Ун-т, 1998. 134с.

52. Николин В.И. Автотранспортный процесс и оптимизация его элементов. М.: Транспорт, 1990. 19с.

53. Оре О. Теория графов. М.: Наука, 1968. 352с.

54. Осыка О.В. Экспериментальное исследование зависимости сходимости генетического алгоритма от его параметров. // Известия РАН // Теория и системы управления, 1997, №5, с. 100-111.

55. Раскин Л.Г., Кириченко И.О. Многоиндексные задачи линейного программирования (теория, методы, приложения).—М.: Радио и связь, 1982. 240с.

56. Редько В.Г. Эволюционная кибернетика. —М.: Наука, 2001. 156с.

57. Рыков А.С. Методы системного анализа: многокритериальная и нечеткая оптимизация, моделирование и экспертные оценки. -М.: Экономика, 1999. 191 с.

58. Скурихин А.Н. Разработка и применение самоадаптирующихся генетических алгоритмов: Автореф. дис. канд. физ.-мат. наук. Пущино, 1996. 19с.

59. Триус Е.Б., Задачи математического программирования транспортного типа. Изд-во "Советское радио", 1967. 208с.

60. Федосенко В.Б. Транспортные задачи. Комсомольск-на-Амуре: Комсомольский-на-Амуре гос. техн. ун-т, 2001. 59 с.

61. Форд, Фулкерсон (Ford L.R., Fulkerson D.R.) Алгоритм для одновременного решения прямой и двойственной задач для проблемы Хичкока с ограниченными пропускными способностями. // Сб. "Методы и алгоритмы решения транспортной задачи". -Госстатиздат, 1963.

62. Форд, Фулкерсон (Ford L.R., Fulkerson D.R.) Решение транспортной задачи. // Сб. "Методы и алгоритмы решения транспортной задачи". Госстатиздат, 1963, стр. 6172.

63. Хачатуров В.Р., Монтлевич В.М. Решение нелинейных производственно-транспортных задач с неделимыми протребителями, М.: ВЦАН СССР, 1987. -22с.

64. Хуцишвили Н.Г., Шарашеидзе Н.М. Решение трехиндексной транспортной задачи методом транспортных сетей // Сообщ. АН ГССР, 1968, т.49, №1, с. 31-36.

65. Штойер Р. Многокритериальная оптимизация: теория, вычисления и приложения. М. Радио и связь. 1992, 504с.

66. Юдин Д.Б., Голыптейн Е.Г., Задачи и методы линейного программирования М.: Советское радио, 1964.- 736с.

67. Юдин Д.Б., Голыптейн Е.Г., Линейное программирование (теория и конечные методы). М.: Физматгиз, 1963.- 775с.

68. Юдин Д.Б., Голыптейн Е.Г., Новые направления в линейном программировании. М.: Советское радио, 1964.- 600с.

69. V.P. Aneja and K.P.K. Nair, Bicriteria transportation problem, Management Sci., vol. 25., pp. 73-78, 1979.

70. T. Back Selective pressure in evolutionary algorithms : a charactirization of selection mechanisms. Proc. 1st IEEE Conf. on Evolutionary Computation (Orlando, FL, 1994) PIS Cataway, NY: IEEE, 1994. pp.57-62.

71. A.K. Bit, M.P. Biswal and S.S. Alam, Fuzzy programming approach to multicriteria decision making transportation problem, Fuzzy Sets and Systems, vol. 50, pp. 135-141, 1992.

72. A.K. Bit, М.Р. Biswal, S.S. Alam, Fuzzy programming approach to multiobjective solid transportation problem. Fuzzy Sets and Systems, vol. 57, pp. 183-194, 1993.

73. Carlos A. Coello Coello. "An Updated Survey of GA-Based Multiobjective Optimization Techniques," ACM Computing Surveys, 32(2), pp. 109-143, June 2000.

74. A.Corban, A multidimentional transportation problem. Rev. Roum. Mat. Pures Appl., 1964, v. 9, № 8.

75. A. Corban On a three-dimentional transportation problem. Three-dimentional problems with interchangeable centers. Rev. Roum. Mat. Pures Appl., 1965, v. 11, № 1.

76. A. Corban On? a three-dimentional transportation problem with partial substitutable sorts. Rev. Roum. Mat. Pures Appl., 1966, v. 11, № 2.

77. A. Corban Transportation problem with intermediate centers. Rev. Roum. Mat. Pures Appl., 1971, v. 16, №9.

78. Das S.K., Goswami A., Alam S.S. Multiobjective transportation problem with interval cost, source and destination parameters. // Eur. J. Oper. Res. 1999, 117, N1, pp. 100-112.

79. Diaz J. Finding a complete description of all efficient solutions to a multipleobjective transportation problem // Economiko-Math. Obzor, 1979, vl5, N1, pp. 62-73.

80. Diaz J.A. Solving multiobjective transportation problem. Ekonomicko-Matematicky Obzor, 1978, 14:267-274.

81. Evolutionary computation. Vol. 1: Basic algorithms and operators / Ed. T. Back, D.B. Fogel, Z. Michalewicz. IOP Publishing, Bristiol and Philadelphia, 2000. 340p.

82. Evolutionary computation. Vol. 2: Advanced algorithms and operators / Ed. T. Back, D.B. Fogel, Z. Michalewicz. IOP Publishing, Bristiol and Philadelphia, 2000. 270p.

83. Carlos M. Fonseca and Peter J. Fleming. An overview of evolutionary algorithms in multiobjective optimization. Evolutionary Computation, 3(1): 1—16, Spring 1995.

84. M.Gen, K. Ida and Y.Z.Li, "Solving Multi-Objective Transportation Problem by Spanning Tree-based Genetic Algorithm," IEICE Trans. Fundamentals, vol.e82-a, no. 12, pp.2802-2810, 1999.

85. Carlos M. Fonseca and Peter J. Fleming. An overview of evolutionary algorithms in multiobjective optimization. Evolutionary Computation, 3(1): 1—16, Spring 1995.

86. Halley K.B. The existence of a solution to the multi-index problem. Oper. Res. Quart., 1965, v.16, № 4.

87. Halley K.B. The solid transportation problem. Oper. Res., 1963, №10, pp.448-463.

88. Hitchcock F.L. Distribution of a product from several sources to numerous localities. J. Math. Phys. 1941, 20, pp. 224-230.

89. Homaifar, A., S. H.-Y. Lai and X. Qi (1994). Constrained Optimization via Genetic Algorithms. Simulation, 62: 242-254.

90. Horn, J. and Nafpliotis, N. Multiobjective Optimization using the Niched Pareto Genetic Algorithm. Technical Report IlliGAl Report 93005, University of Illinois at Urbana-Champaign, Urbana, Illinois, USA, 1993.

91. Iserman H. The enumeration of all efficient solutions for a linear multipleobjective transportation problem // Navall Research Logistics Quarterly, 1979, v26, N1, pp/ 123-139.

92. F. Jimenez and J.L.Verdegay, "Interval multiobjecive solid transportation problem via genetic algorithms", Proc. Of the Sixth Intern. Conf. On Information Processing and Mage-ment of Uncertainty m Knowledge-Based Systems, vol. II, pp. 787-792, 1996.

93. F. Jimenez, J.M. Cadenas (1995). An evolutionary program for the multiobjective solid transportation problem with fuzzy goals. Operations Research and Decision 2:5-20.

94. F. Jimenez, J.L.Verdegay, "On Interval and Fuzzy Solid Transportation Problem," Proc. IEEE Fyzzy Systems, 1997.

95. S.M. Lee and L.J. Moore, Optimizing transportation problem with multiple objectives, AIIE Transactions, 1973, vol. 5, pp. 333-338.

96. Z.Michalewicz, G.A. Viganaux, and M.Hobbs, "A nonstandart genetic algorithm for the nonlinear transportation problem," ORSA Journal on Computing, vol.3, no.4, pp.307316, 1991.

97. Michalewicz, Z. and N. Attia. In Evolutionary Optimization of Constrained Problems. Proceedings of the 3rd Annual Conference on Evolutionary Programming, eds. A.V. Sebald and L.J. Fogel, River Edge, NJ, World Scientific Publishing, 1994, pp.98~108.

98. Michalewicz, Z. and C. Janikow. Handling Constraints in Genetic Algorithms. In Proceedings of the Fourth International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, 1991, pp.151—157.

99. Orvosh, D. and L. Davis. Shall We Repair? Genetic Algorithms, Combinatorial Optimization, and Feasibility Constraints. In Proceedings of the Fifth International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, 1993,

100. Paredis, J. Co-evolutionary Constraint Satisfaction. In Proceedings of the 3rd Conference on Parallel Problem Solving from Nature, New York, Springer-Verlag, 1994, pp. 46--55,

101. Practical Handbook of Genetic Algorithms / Ed. L.D. Chambers. Vol.3. CRC Press, 1999 500p.

102. J.L. Ringuest and D.B. Rinks, Interactive solutions for the Linear multiobjective transportation problem, Eur. J. Oper. Res., vol. 32, pp. 96-106, 1987.

103. Schaffer, J. D. Multiple objective optimization with vector evaluated genetic algorithms. In Genetic Algorithms and their Applications: Proceedings of the First International Conference on Genetic Algorithms , 1985, pp. 93—100. Lawrence Erlbaum.

104. Schell E. Distribution of a product by several properties. Directorate of Management Analysis, Procs. 2nd. Symposium in Linear Programming 2:615-642, DCS/Comptroller H.Q. U.S.A.F., Washington, D.C., 1955.

105. Schoenauer, M., and S. Xanthakis. Constrained GA Optimization. In Proceedings of the Fifth International Conference on Genetic Algorithms, Los Altos, CA, Morgan Kaufmann Publishers, 1993, pp. 573-580.

106. Smith G. Further necessary conditions for the existence of a solution to the multi-index problem. Oper. Res., 1973, v. 21, №1.

107. Smith G. A procedure for determining necessary and sufficient conditions for the existence of a solution to the multi-index problem. Appl. Mat., 1974, v. 19, №3.

108. Srinivas, N. and Deb, K. 1994. Multiobjective Optimization Using Nondominated Sorting in Genetic Algorithms. Evolutionary Computation 2, 3 (fall), 221—248.

109. G.A. Viganaux and Z.Michalewicz, "A genetic algorithm for the linear transportation problem," IEEE Trans. Syst., Man. & Cybern., vol.21, no.3, pp.445-452, 1991.

110. Vlach M. Stanoveni pripustneho peseni trojindexowego dopravmho problemu. Ekon. Mat. Obzor, 1965, bd. 1, №2.

111. Vlach M., Moravek J. Poznamka k-trojindexovemu dopravnimu problemu. Ekon. Mat. Obzor, 1967, bd. 3,№1.

112. Wallet B.C., Marchette D.J., Solka J.L. A matrix representation for genetic algorithms. Proceeding of the SPIE. 2756,1996, pp. 206-214.

113. Дискретные задачи размещения (интернет-библиотека): Оптимизационные алгоритмы. http://math.nsc .rii/ AP/benchmarks/UFLP/uflp alg.html

114. Исаев С. Популярно о генетических алгоритмах, http://saisa.chat.ru/ga/ga-pop.html

115. Carlos A. Coello Coello. A Survey of Constraint Handling Techniques used with Evolutionary Algorithms. http://www.lania.nix/~ccoello/EMOO/coello99survey.ps

116. ПЕРЕЧЕНЬ ИСПОЛЬЗУЕМЫХ И ВВЕДЕННЫХ ТЕРМИНОВ

117. Термин (синоним, аббревиатура)1. ГА

118. Значение см. генетический алгоритм

119. Генетический алгоритм (ГА) метод оптимизации, представляющий собойкомпьютерную модель эволюции искусственных особей

120. Генетический оператор (ГО)1. Гибридный алгоритм1. ГО1. Допустимая особь

121. Задачи с векторными правыми частями

122. Задачи с матричными правыми частями

123. МТЗ, у которых правые части ограничений представляют собой одномерные массивы, например, классическая транспортная задача, задачи типа ТЗ-ЗР и T4-4S

124. МТЗ, у которых правые части ограничений представляют собой многомерные массивы, например, задачи типа ТЗ-ЗА, Т4-4А, Т4-6Р

125. МТЗ, в системе ограничений которых присутствуют как векторные правые части, так и матричные, например, описанная в главе 4 задача типа T4-2P-S1. Инициализациясоздание исходного множества допустимых решений начальной популяции1. Кроссовер, скрещивание

126. ГО, который можно логически разделить на две независимые части, одна из которых предназначена для внесения изменений в хромосому, а вторая для обеспечения допустимости получаемого потомка

127. Специальная задача линей- задача линейного программирования с ог-ного программирования раничениями специального вида: транс-(СЗЛП) портная и распределительная задачи

128. Особь допустимое решение задачи

129. Хромосома представление особи в пространстве переменных. Представляет собой многоиндексную матрицу, содержащую неотрицательные компоненты1. Условия разрешимости МТЗ

130. Теорема П1.1. Для разрешимости трехиндексной трипланарной задачи (Т3—ЗР ) необходимо и достаточно вывполнения условия:т л Р1. Ш.1)1 v=l k=1

131. Теорема П1.2. Для разрешимости четырехиндексной тетрапространственной задачи T4-4S необходимо и достаточно выполнения условия ■т л Р Ч2>.=2>,=2>x=2>i=*- (Ш.2)1=1 7=1 k=1 1=1

132. Наиболее подробно исследованы условия разрешимости для трехиндексной триаксиальной задачи (Т3-ЗА). Этому посвящены работы Хели 92., Смита [115, 116], Моравека и Влаха [120].

133. Теорема П1.3 (условие баланса). Для разрешимости задачи Т3-ЗА необходимо выполненея условия:п р т р т п1. =1Х, IX =IX*> IX =1Х> (ш-3)у=1 А=1 1=1 Ы\ i=l 1т п п Р т рш-4)1=1 J=1 )=1 Jc=t l=t fc=l

134. Кратко указанные последовательсноети называются соответственно минори-рующей и мажорирующей. В соответствии с этим v-й член последовательности m(y>jk (M(v)ljk) называется минорантой (мажорантой) переменной хук.

135. Пределы т1.к и Mljk последовательностей m(v)ljk и M(v)ljk , если они существуют, устанавливают нижнюю и верхнюю границы для переменной xljk.

136. Теорема П1.5 (условие Моравека-Влаха). Для разрештюсти задачи Т3-ЗА необходимо, чтобы выполнялось условие:Щ12cni.13)iel кеК jeJkeK leljeJгде Ido—{I,2, .,m}; JcJ0={I,2, .J, .,n}; KczK0={l,2, .X -p}; K=K0\K.

137. Наиболее жесткими необходимыми условиями разрешимости являются условия Хели-Смита.

138. Теорема П1.6 (условия Хели Смита). Для разрешимости задачи Т3-ЗА необходимо, чтобы выполнялись условия:2>*+Zm« -2Х +!>,* -2>„ +IX* ■ (ШЛ4)1.J JIK IK JK IJ IKJ JIK

139. Условия Хели—Смита объединяют условия Хели и Моравека — Влаха. При этом они являются наиболее сложными. Из всех приведенных условий наибольшее распространение получила рекурсивная процедура Хели для выявления неразрешимых задач 56.

140. Так же сформулированы и два достаточных условия существования решения триаксиальной задачи.

141. Теорема П1.7 (первое достаточное условие). Сбалансированная задача Т3-ЗА разрешима, если условиех. + V о, (П1.15)р п m mn mp пр nmpп р m m Ргде at = ^ ау, bj = ^ bjk, ck = ^ clk, S = ^ ^ ctk, выполняется для всех (ijk) еЕ.7=1 Л=1 1=1 1=1 А=1

142. Теорема П1.8 (второе достаточное условие). Сбалансированная задача Т3-ЗА разрешима, если1. У* + + (П1.16)a,bj a,ck bjci s

143. Аналогично трехиндексной триаксиальной задаче, с каждой переменной ху/,/ связываются две последовательности m^v) , Мци(v), v=l,2,3,., определяемые ре-курентными соотношениями:mvU(0)=0; МуЫ(0)= min{aljk, blkl, cljb djkl }; (П1.23)

144. Кki(y ~ auk-1 M',AV ~I A-/-1 Mii(y ~!) 1>1 /TT1 0 лчтм{у) = таах.\ . , У, (П1.24)lcff/ I My, (y -1) I. djki -1 Щи (У - !) I. }+Mvkl(v-l) Jr , N \Muu (v -1), max{ a k \ m'k (v -1) |, blU - | mJlU (v -1) |,1 Mukl(v) = max\ k (П1.25)

145. K< I mut (v -I'djki ~\тли(У~1) I' } + тчы (У ~ 1) J

146. С каждой переменной связываются две последовательности mljki(у) , Mljkl(v), v=l,2,3,., определяемыерекурентными соотношениями:тцы(0)=0; Mljkl(0)= min{alj3 bjk, с„, djk, ejb gkl}; (П1.37)mljU{v-l),max{ atJ- \< (v -1) \,b,k- \МЦ(у -1) c,;- |MJuk(v -1) |,|

147. Гл/ u (v -1), max { a -1 (v — 1) 6,t | mfk (v -1) - | mf (v -1) j (m M,tki(v) = maxi „ , k vilJ—jyj

148. Теорема П1.12 (условие Хели). Для разрешимости задачи Т4-6Р необходимо сугцествование пределовlim {mykl(v)}=myH;\im\MyU(v)}=Mykl (П1.40)таких, что выполняются условия:myll<MljU,{i,j,k,l)zE■ (П1.41)

149. X !>,,„< яу<Е 1ХИ; (П1.42)1.1 к-1 /-1 *-1£mljkl<bik<£ (П1.43)1. Р Я Р л1. X Xmljkl<ctl<X (П1.44)1. Jfc=l j=l к=1 j=l/и1. Z -djk 2X*; (П1-45)1 1=1 /=1 (=1m P m p1.2Ж*; (Ш.46)i=i i=i 1=1 ft=i1.Ё"»* * * Ё TM^iijkl) G (П1.47)1=1 y=l (=1 7=1

150. Пример транспортной задачи в классической постановке.

151. Результаты расчета задачи транспортировки по данный за апрель 2003