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

На правах рукописи

Дубравина Татьяна Викторовна

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

Специальность 05.13.01 «Системный анализ, управление и обработка информации (металлургия)»

АВТОРЕФЕРАТ

диссертации на соискание ученой степени кандидата технических наук

I

Москва 2005

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

Научный руководитель:

кандидат технических наук, профессор Калашников Евгений Александрович

Официальные оппоненты:

доктор технических наук, профессор Рожков Игорь Михайлович;

- кандидат технических наук, ст. научн. сотрудник Власов Станислав Александрович

Ведущее предприятие:

ОАО "Черметавтоматика'

Защита диссертации состоится «

2005 г. в

часов на заседании

диссертационного совета Д.212.132.07 в Московском государственном институте стали и сплаво\\г«'в (технологическом университете) по адресу: 119049, г. Москва, Ленинский проспект, д. 4.

С диссертацией можно ознакомиться в библиотеке Московского государственного института стали и сплавов (технологического университета). Автореферат разослан « » ноября 2005 г.

Ученый секретарь диссертационного совета

д.т.н., проф. Фомин С.Я.

Шл

ОБЩАЯ ХАРАКТЕРИСТИКА РАБОТЫ

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

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

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

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

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

РОС

• "<:КА

г

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

Цель работы

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

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

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

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

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

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

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

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

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

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

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

Научная новизна состоит в следующем:

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

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

который построен и программно реализован с использованием нового вида представления структуры генетического алгоритма.

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

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

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

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

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

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

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

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

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ Во введении представлены обоснование актуальности выбранной темы, формулировка цели исследований, содержание поставленных задач; определяются научная новизна и практическая значимость полученных результатов.

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

Классическая транспортная задача - это задача о нахождении наиболее экономного

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

Многоиндексные транспортные задачи возникают, например, тогда, когда транспортные издержки зависят не только от объемов перевозимых грузов, но также и от вида грузов, типа транспорта и других факторов. Приведем одну из возможных записей модели многоиндексной транспортной задачи в общем виде. Рассматриваются элементы мерной матрицы, каждая ячейка которой определяется 5 координатами (индексами) 1\, ..., /¡, причем к-я координата принимает значения гк=\, пк; все /г=1, 5 . Пусть М - множество номеров всех координат; Я - семейство подмножеств множества М\ М/е Я -у-е подмножество, а |Л^|=/и(/) - число его элементов; j =\, 1 , Рассмотрим произвольную ячейку

Обозначим через ¡{ц, . , /а) те координаты ячейки, номера которых не являются элементами М}. Многоиндексной транспортной задачей, является задача о нахождении всех элементов матрицы {д^ , }, удовлетворяющих условиям

кем,

,,2:0 (2)

и доставляющих минимум функционалу

*еЛ/

Все а1(11 , > 0 задаются. Далее будут рассматриваться многоиндексные транспортные

задачи со значением 5 =3 или л =4

Многоиндексные транспортные задачи можно классифицировать по количеству индексов, виду и количеству ограничений. По последнему критерию можно выделить подмножества постановок - симметричных и несимметричных; однородных и неоднородных. Симметричные задачи содержат ограничения только одного типа, и число групп ограничений равно максимально возможному для данного числа индексов и вида ограничений, то есть, 1<т(1)=. .=т(() < 5-1, где /=С"0). Постановки симметричных

транспортных задач, возникающих в металлургии, с числом индексов 2, 3 и 4 показаны на рис. 1.

Классическая задача (Т)

т п

¿С*// =°/

т

2л=ь,

Х^О

Тетрааксиальная задача(Т4-4А)

2 X £ ¿1 с'/и ^¡да

- "(у* >

у-1

и ~ с!й>

Л1

У^.Хцч = ^¡а >

1=1

Хцм^О

Триаксиальная задача(Тз-ЗА)

X X Ё С!» *»

у-1 А-]

* = 1 т

/=1

IX*=с*-

х,,к>0

Гексапланарная задача(Т4-6Р)

/«I

/«1 ы

й-

/=1 »»1

££

•

(=1 у=1

хщ£0

Трипланарная задача(Тз-ЗР)

£ Ё1] сй *»«■ /»I

у=1 4-1 да р

/=1 XI,к

Тетрапространств. задача (Т4-45)

±±Цс ЦЫлуь

(«I J*\

ЕЁЕ =

4-1 /=1

/«1 *=1 п т ч

2-12-, хт ~ск

1- 1 1=1 /-1

т я р 1=1 у=1 Ц=1

Хщ>0

Рис. 1. Постановки симметричных трех- и четырехиндексных задач

-7-

Несимметричные задачи - это частные случаи симметричных задач, в которых отсутствует одна или несколько групп ограничений. Системы ограничений неоднородных задач состоят из сумм по различному числу индексов. В свою очередь, все подмножество однородных и неоднородных задач можно разделить на подмножества сводимых и несводимых задач.

Существует несколько подходов к решению отдельных постановок многоиндексных транспортных задач. Объединение областей применимости этих подходов не покрывает все множество многоиндексных задач. Кроме того, многие из методик ограничены одним критерием оптимальности линейного вида.

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

Генетический алгоритм - это компьютерная модель эволюции популяции искусственных особей. Множество особей на каждом шаге алгоритма - поколении, называется популяцией. Каждая особь характеризуется своей хромосомой St, которая

определяет приспособленность (пригодность) особи F(Sk), к=1, К, К - численность популяции. Задача алгоритма состоит в максимизации функции приспособленности F(Sk). Эволюция состоит из последовательности поколений, хромосомы особей в каждом из которых скрещиваются и подвергаются мутациям. Затем для следующего поколения отбираются особи с большими значениями функции приспособленности. Условием останова поиска может быть прекращение роста максимальной приспособленности в популяции, достижение числом поколений t заданного предела и т.п.

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

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

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

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

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

Второй путь состоит в отыскании множества решений равнозначных или достаточно близких по значению критериев исходной модели, чтобы затем на этом множестве решить задачу выбора лучшего относительно усложнений модели решения Задача выбора может решаться как с помощью методов принятия решений, так и с привлечением ЛПР. Этот путь является более универсальным, так как применим для решения задач с широким диапазоном изменений относительно исходной постановки.

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

Генетический алгоритм лишен перечисленных недостатков. Кроме возможности решения различных постановок МТЗ он также позволяет отыскать для них множество субоптимальных решений. Эта способность ГА к нахождению некоторого множества решений определяется следующими особенностями его реализации:

1. В теории ГА существует понятие «сохранение разнообразия популяции», для обеспечения которого разработан ряд приемов. Разнообразие популяции в конечном поколении необходимо дает множество решений, близких к лучшему, но отличных от него и различных между собой, то есть искомое множество субоптимальных решений

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

Решение транспортных задач с помощью генетических алгоритмов позволяет ввести понятие синонимичных решений. Пусть Х\ и Х2 - решения некоторой МТЗ, тогда Р(Х\) и

р(Хт) - соответствующие им значения функции приспособленности (критерия МТЗ) Будем называть решения Х\ и Х^ синонимичными, если

Таким образом, синонимичные решения МТЗ появляются тогда, когда одной точке в критериальном пространстве соответствует несколько точек в пространстве переменных

Синонимичные решения являются следствием сочетания специфики поискового пространства транспортных задач и особенностей генетического алгоритма.

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

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

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

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

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

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

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

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

Рис 2 Графическое представление перехода версий ГА при изменении постановки решаемой задачи

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

Размер популяции Условие останова

Создание начальной популяции;

Вычисление пригодности для веек особей

Сортировка популяции (по возростанию пригодности)

Выбор родителей для мутации и кроссовера

Мутация

г

Кроссовер

Рис 3 Структура генетического алгоритма для решения многоиндексных транспортных задач

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

Таблица 1

Зависимость основных процедур генетического алгоритма от характеристик решаемой транспортной задачи

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

Основные этапы От каких частей симметричных МТЗ зависит Число различных вариантов

Задание начальной популяции Число индексов, число и вид ограничений 6

Вычисление значения критерия Критерии оптимальности 3

Отбор решений для "размножения" 1

Мутация Число индексов 3

Скрещивание Число индексов 3

Замещение "плохих" решений новыми 1

Выделим три подгруппы операторов и частей ГА, как это показано на рис. 4. При этом вычисление приспособленности зависит от вида задания целевой функции решаемой задачи.

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

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

Будем называть генетические операторы (ГО) составными, если они имеют структуру, показанную на рис. 5.

Генетический оператор

Часть 1. Манипуляция с хромосомой

+

Часть 2.

Обеспечение допустимости потомка (вычисление невязок; построение опорного плана)

Рис. 5 Структура составного генетического оператора -13-

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

1. Для разных операторов, предназначенных для решения одной и той же задачи, первая часть ГО является уникальной, а вторая - общей.

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

Эти свойства были использованы при создании множества реализаций ГА для решения различных МТЗ. общие части ГО, "ответственные" за манипуляции с хромосомой, для задач с одинаковым числом индексов реализованы один раз в некотором внешнем классе; а части ГО, "ответственные" за допустимость, создаются для каждой постановки

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

Для четырехиндексного случая был построен и реализован оператор скрещивания типа "обменом генами". Так же для указанного типа задач был реализован "арифметический оператор скрещивания", который создает из двух родительских хромосом оператор потомков по следующему правилу покомпонентного преобразования хромосом. Пусть матрицы АЛ и Л*г - хромосомы особей, выбранных в качестве родителей, а матрицы ХП\ и Л^'г- хромосомы потомков. Тогда их компоненты связаны следующими соотношениями:

X," Щк1)=а Х,е (ук1}+( 1-а}Х\ {¡¡к1), (5)

А\п(ук!)=(!-а) X?(ук!)+аХ\(ук!), (6)

где ае[0;1]сЯ.

В диссертационной работе приведено доказательство допустимости получаемых потомков Для целочисленного случая арифметический оператор скрещивания является составным Частным случаем арифметического оператора скрещивания является оператор, называемый "Усреднение". Здесь параметр арифметического скрещивания а фиксирован и равен 0,5.

Мутации типа "перераспределение" и "внесение минимальных распределений" были модифицированы автором на случай четырех индексов и реализованы для различных постановок Подробное описание работы этих ГО приведено в диссертационной работе Кроме них была также предложена и реализована мутация типа "внесение переменных изменений" Её идея состоит в том, что выбираются две ненулевые компоненты решения:

и уменьшаются на некоторую величину, скажем, Д:

х,, :=х!иМ :=д:'гМЛ(2-1 >

где Д равна

Д=гапсЬт(ттЦ,/М) ;х„м,Л}). (8)

Затем эта же величина присваивается двум другим, отличным от исходных, компонентам решения Схематичное изображение механизма мутации для внесения изменений приведено на рис. 6.

Родитель Потомок

Х^Х) Мутация 1 Т

' Х'Л>0 У Хы+Л < 1

Рис б Механизм мутации "внесения изменений" (вариант присваивания № 1)

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

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

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

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

Для задач с векторными правыми частями ограничений предлагается использовать процедуру нахождения допустимого решения со случайным выбором ведущего элемента Блок-схема этой процедуры для сбалансированной задачи типа Т4-45 показана на рис. 7. Здесь а/, с*, - значения правых частей ограничений, при /=1, п; у'=1, т; к~\, р, /=1, ц Множества индексов /о, Л, Ко, Ц в начальный момент времени равны /о={ 1,2,..,«},

В случае задач с матричными правыми частями процедура нахождения допустимого плана со случайным выбором ведущего элемента имеет меньшую эффективность, чем при решении задач с векторными правыми частями. В связи этим в алгоритм были внесены изменения, в результате которых выбор ведущего элемента осуществляется с использованием минорирующей и мажорирующей последовательности Хели. Структура процедуры нахождения допустимого плана с использованием последовательностей Хели для задачи типа Т4-6Р показана на рис. 8. Обозначения: Е^Е - множество "ячеек" матрицы решения, соответствующих неизвестным значениям переменных; Яу, сц, с!1к, е^, -значения правых частей ограничений, при /=1, п; у=1, т; к=1, р, /=1, д. Для четырехиндексной гексапланарной задачи последовательности Хели определяются следующими рекуррентными соотношениями:

ЩьЩ-0; А*„й(0)=п"п{а//, Ьц, сц, фь е;,, g^l}■ (9)

кс - ')'тах{ аг I - о 1 <("-1) 1.С,-1 м?(V -1) 1,1 %!') = п»*1 , „ „1 к (10)

Мт(У)=твх{ , ' ' , V

Рис. 7. Процедура отыскания Рис. 8. Процедура отыскания

допустимого плана со случайным допустимого плана с использова-

выбором ведущею элемента нием последовательностей Хели

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

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

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

Программная реализация системы для решения класса трех- и четырехиндексных транспортных задач с ГА создана согласно результатам, полученным во второй главе. Приводится ее структура, объектная модель, описывается пользовательский интерфейс. Программное обеспечение создано в среде программирования Borland Delphi 7.0 на языке Object Pascal. Оно предназначено для решения различных типов МТЗ и исследования свойств как постановок, так и алгоритмов решения. Кроме соответствующих модификаций генетического алгоритма для сводимых МТЗ реализован метод решения, основанный на понижении числа индексов.

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

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

Для синонимичных решений МТЗ проведено исследование о влиянии параметров ГА и свойств численной постановки задачи на их количество.

В четвертой главе на основе предложенных во второй главе алгоритмов решена

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

Решается задача транспортировки для трубного завода, который пользуется в основном привозным сырьем, например Выксунского металлургического завода или Московского трубного завода. Завод, далее именуемый "потребитель", закупает сырье исходя из имеющихся заказов на продукцию в текущем периоде В этом случае решается задача минимизации времени и затрат по оборачиваемости сырья. Есть множество поставщиков, которым соответствуют станции отгрузки, имеющие индивидуальный (в рассматриваемой задаче) номер, совпадающий с индексом ;=1, N. Известны тарифы РЖД,

состав транспортного парка завода, количество вагонов арендуемых у РЖД; грузоподъемность используемых вагонов, типы которых (сочетание грузоподъемность-принадлежность) соответствуют индексу V, у=1, IV . Плановым отделом ОАО ВМЗ предоставлены объемы заказов по 11 наиболее ходовым маркам стали, пронумерованным 5=1, 50, для девяти месяцев 2003 года, а также информация о наличии

каждой из марок стали в сортаменте заводов-поставщиков Величина скидки, предоставляемой РЖД при доставке грузов сформированным составом с числом вагонов не менее т,=50, составляет 6% Индекс р=1, Р1 - число поездок груженых составов от 1-го поставщика; £2 - множество всех поездок груженых составов в планируемом периоде, ото

N

всех поставщиков, Тогда х,„р - количество тонн 5-й марки стали, доставляемое от /-

/=1

го поставщика в вагоне у-го типа р-м составом. Известны также следующие величины:

• количество стали 5-ой марки, необходимое потребителю в данном периоде,

• 5,е ,9 - подмножество марок стали, производимых на 1-м заводе;

• - максимальная грузоподъемность состава, направляемого от г-го поставщика (зависит от вида перевозки и наличия мостов);

• К,, - количество вагонов у-го типа в транспортном парке потребителя, Поскольку в реальности при каждой отгрузке ;-ым поставщиком некоторого количества вагонов ему направляется точно такое же количество пустых вагонов, то, следовательно, мы располагаем только половиной транспортного парка при планировании перевозок и поэтому будем для определенности считать величину К, - число доступных вагонов у-го типа равной половине числа вагонов данного типа в транспортном парке,

c/v - транспортные издержки при доставке сырья от 1-го поставщика вагоном v-ro типа, которые можно вычислить по формуле

Civ=l,*(l-d)*tarjgv, (12)

где I, - величина, отражающая расстояние от потребителя до г'-го поставщика, выраженная в днях следования состава, так как именно эта величина, устанавливаемая РЖД, умножается на тариф для каждого из видов вагонов - (tar„); gv - константа, для обозначения грузоподъемности вагона; d - величина скидки в процентах, предоставляемая РЖД при следовании состава с числом вагонов не меньше т,\ максимальное число поездок по всем направлениям - глубину по 4-му индексу матрицы перевозок можно оценить так:

max

ле

en,«) Щ

max Р, <-iSi^-, (13)

где, т, - это минимальная желаемая грузоподъемность составов, которая одинакова для всех направлений и определяется политикой предоставления скидок РЖД, а в числителе правой части стоит максимальный из возможных объемов заказа, который зависит от сортамента продукции, производимого /-м поставщиком.

Система ограничений задачи:

__л1пр

/=1 val ре а

, (14)

1

- (15)

м i-i w

. de)

0 (17)

формулируется исходя из следующих соображений: необходимо, чтобы были удовлетворены запросы потребителя по всем маркам стали (14); общее количество стали, перевозимое в период планирования, не должно превышать возможности транспортного парка завода-потребителя (15); значения x,lvp неотрицательны (17). Нужно также учитывать двустороннее ограничение на пропускные способности: во-первых, длина состава не должна превышать допустимую Mi длину состава; во-вторых, менее выгодно отправлять составы длиной меньшей т/. Формула (16) - ограничение на пропускные способности справа.

Ограничение по пропускным способностям слева преобразовали в штрафную функцию. Если длина состава меньше чем т„ то состав рассматривается как "группа

вагонов" и на него не распространяется скидка РЖД в размере с1%. В этом случае мы "дополнительно" оплачиваем величину неполучаемой скидки

(18)

ш

умноженную на количество вагонов в "группе", которое равно Поэтому сумму,

1-1165,

которую мог бы сэкономить завод, если бы в плане перевозок по /-му направлению при р-м заходе не содержалось "групп вагонов", можно выразить так:

I ^ 1С к

если^^х^кт,, О, в противном случае

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

(20)

Ы рчП

Так как целевая функция имеет смысл минимизации транспортных расходов:

» 4 »

(21)

(=1 л=<1 у-1 ре а

и измеряется в тех же единицах, что и штрафная функция, то их можно объединить в одну функцию:

(22)

/.1 ,.1 К-1 реа М реО

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

К особенностям модели (14)-(17), (22) относятся:

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

2. Несимметричность и неоднородность данной задачи исключают возможность использования метода потенциалов.

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

(поставщика, типа вагона, дополнительного состава). Также невозможно воспользоваться методикой решения интервальных задач.

5. Данная модель открытая, следовательно, решение зависит от глубины по четвертому индексу. При "неудачном" выборе пределов изменения четвертого индекса задача может не иметь решения.

6. Размерность матрицы решения для условий ОАО ВМЗ равна NxSxfVxPe [3000; 5000], где Р = шах Р,. При этом число допустимых решений, оцениваемое по известной формуле,

.N

составляет 2*1017 при Р=13.

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

Как и ранее, генетический алгоритм имеет матричное представление хромосом, для работы с которыми используются модификации разработанных и описанных в гл. 2 генетических операторов: арифметический оператор скрещивания и мутация типа "перераспределение". В основе процедуры создания начальной популяции лежит процедура нахождения опорного плана задачи со случайным выбором ведущего элемента. Алгоритмически эта процедура аналогична описанной ранее процедуре нахождения допустимого решения для МТЗ с векторными правыми частями. Отличие состоит в том, что на каждом шаге величина перевозки xlsvp, назначаемая ведущему элементу, выбирается по правилу

*„„= min {Z, М¥<I G,}, (23)

где ZjS„ - объем заказа стали типа s у поставщика номер /; M,PGV - возможное число вагонов, с точки зрения максимальной длины состава, типа v по направлению к поставщику i на р-м обороте, КуРОу - число вагонов типа v в наличии на р- м обороте. Именно эти величины уменьшаются на величину перевозки, назначаемую ведущему элементу. Критерием останова в данном случае является полное распределение всего объема заказов.

Задача (14)-(17), (22) была решена в рамках разработанной системы; реализация ГА для ее решения, описанная в п. 4.2.2, была выделена в отдельный программный модуль с целью передачи на ОАО ВМЗ. Он построен согласно принципам объектного представления ГА для решения МТЗ, описанным в гл. 2. Его отличием является использование справочников поставщиков, типов вагонов и марок стали, а также наличие интерпретации решения на форме вывода результатов поиска.

С помощью программного обеспечения, разработанного для решения задачи (14)-(17), (22), был проведен расчет, для которого использовались данные за 9 месяцев 2003, предоставленные плановым отделом ОАО ВМЗ, его результаты за март и апрель приведены в приложении к диссертации.

Решение задачи (14)—(17), (22) представляет собой четырехиндексную разреженную матрицу, которая содержит 3-5 тысяч компонент. Для оценки получаемых решений и сравнения их между собой кроме значения целевой функции (22) используются показатели качества решения:

• матрица Y(1> - служит для представления информации о том, какие из марок стали поставляются каждым из поставщиков; ее компоненты рассчитываются по формуле:

(24)

M р-1

• матрица Y® служит для представления информации о числе вагонов, направляемых от каждого из поставщиков; ее компоненты рассчитываются по формуле:

l-l

• поскольку объемы заказов некратны грузоподъемностям вагонов, то вычисляется также и число незаполненных вагонов:

®=±1±Жг, (26)

M J€ï, l'=l рс il

где

il, если (xUv mod g: )>0,

<Mn (27)

О, в противном случае

Показатели Ym, Y(2! и 0 используются при решении проблемы выбора, возникающей, когда в результате решения находится множество субоптимальных решений. Определение относительной важности этих показателей предоставляется ЛПР.

На рис. 9 показаны экранные формы, содержащие два субоптимальных решения задачи (14)—(17), (22) Показатели Y(n, Y<2> выведены на форму программного модуля, а значение 0 в первом случае равно 11 (рис. 9,а), во втором - 15 (рис. 9,6). Приведенные решения имеют много общего значения целевой функции (22) для них отличаются на 0,2 %, различаются поставщики некоторых марок сталей, а также время, необходимое на выполнение выполнение плана перевозок

- |-|| шит............. I.........И11111111П ГГГГГ^ГГГ'"-^^^ щнпш><■ I\\<ыш«<т<ж<«т««<*<<««<(тш

б)

Рис. 9 Пример субоптимальных решений задачи (14)—(17), (22)

Поэтому далее уже ЛПР выбирает наиболее предпочтительное решение, принимая во внимание вышеуказанные параметры и их интерпретации.

В заключении формулируются основные результаты работы:

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

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

различных постановок МТЗ и исследовать сравнительную эффективноть его различных модификаций.

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

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

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

1. Калашников Е.А., Дубравина Т.В. О создании универсальной системы для решения многоиндексных несимметричных транспортных задач // Сб. науч тр. МИСиС "Экономика, информационные технологии и управление в металлургии". М,- МИСиС, 2003. С. 58-61.

2. Калашников Е А., Дубравина Т.В., Иконникова А А Постановка задачи транспортировки сырья для трубного производства//Черные металлы 2005 №3. С.21-25.

3 Калашников Е А , Дубравина Т В, Кожитов С Л Применение генетического алгоритма для решения модифицированных специальных задач линейного программирования с множеством квазиоптимальных решений // Металл, оборудование, инструмент. 2005. Май/август. С.57-59.

4. Калашников Е А , Дубравина ТВ Генетический алгоритм как универсальная структура для решения множества многоиндексных транспортных задач" // Металл, оборудование, инструмент. 2005. Май/август. С.52-56.

5. ПрокопчукЮ.Ю, Широков А И, Дубравина ТВ Дискретная математика. Основные теоретико-множественные конструкции Ч I.: Учеб. пособие М/ МИСиС, 2003. 117 с.

СПИСОК ПУБЛИКАЦИЙ

Соискатель

Дубравина Т.В

Формат 60 х 90 '/16 Тираж 100 экз.

Объем 1,6 п.л. Заказ 924

Отпечатано с готовых оригинал-макетов в типографии Издательства «Учеба» МИСиС, 117419, Москва, ул. Орджоникидзе, 8/9 ЛР №01151 от 11.07.01

Sr? S Я

РНБ Русский фонд

2007-4 8190

2 9 ЙЕН 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 стр.

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

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

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

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

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

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