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

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

БЛИНОВ Иван Владимирович

МОДЕЛИРОВАНИЕ ПРОЦЕССА РАЗВОЗКИ ОДНОРОДНОГО ГРУЗА ОТ ОДНОГО ОТПРАВИТЕЛЯ НЕСКОЛЬКИМ ПОЛУЧАТЕЛЯМ

Специальность: 05.13.18 - математическое моделирование, численные методы и комплексы программ

Автореферат

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

2 2 тол 2010

Воронеж - 2010

004607169

Работа выполнена в ГОУ ВПО «Воронежская государственная технологическая академия».

Научный руководитель: доктор физико-математических наук,

Бугаев Юрий Владимирович;

Официальные доктор физико-математических наук, оппоненты: профессор

Меньших Валерий Владимирович;

кандидат технических наук, доцент

Курченкова Татьяна Викторовна

Ведущая организация: ГОУ ВПО «Воронежская государствен- .

ная лесотехническая академия»

Защита диссертации состоится 5 июля 2010 г. в -Ну10\\а. заседании диссертационного совета Д 212.038.20 в ГОУВПО «Воронежский государственный университет» по адресу: 394006, г. Воронеж, Университетская пл.1, ВГУ, ¿2 ¿А?. 33 0_

С диссертацией можно ознакомиться в библиотеке ГОУ ВПО «Воронежский государственный университет».

Автореферат разослан « Н » иЮНЛ 2010 г.

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

к.ф.-м..н., доц. В.В.Провоторов

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

Актуальность проблемы. Современная экономическая ситуация в России характеризуется все возрастающей конкуренцией на рынке товаров и услуг. Одним из следствий этого является повышение уровня требований клиентов. В таких условиях развитие любой компании, ориентированной на обслуживание большого числа потребителей, должно быть очень динамичным. Целью этого развития является предоставление услуг такого качества и в таком объеме, которые будут соответствовать ожиданиям клиентов. Известно, что затраты на производство некоторых товаров составляют лишь около 10% их стоимости, в то время как доля расходов на доставку может достигать 50%, а в ряде случаев и больше.

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

Научной основой задачи оптимального планирования грузоперевозок является классическая транспортная задача. Разнообразие целей и критериев при ее постановке в применении к различным практическим областям привело к появлению большого класса «развозочных» задач, решением которых в разное время занимались такие ученые как Дж. Литл, Р. Беллман, С. Уоршалл, Р. Флойд, И. X. Сигал, Э. Дейкст-ра, В. А. Житков, A.B. Ефремов. Однако, существующие подходы к решению задачи развозки исходят из ее упрощенной постановки, не в полной мере соответствующей реальным условиям.

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

Диссертационная работа выполнена в рамках госбюджет-ной НИР по теме «Математическое и компьютерное моделирование в задачах проектирования и оптимизации функционирования информационных и технологических систем» (№ госрегистрации 01.2006.05298), а также гранта РФФИ 06 - 07 - 89189-а по теме «Разработка информационных технологий выбора на необозримом для ЛПР

множестве альтернатив».

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

Поставленная цель достигается посредством решения следующих задач.

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

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

3. Синтез базового варианта модели процесса развозки.

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

5. Создание программного обеспечения, реализующего разработанные алгоритмы.

6. Проведение вычислительных экспериментов и практическая реализация результатов исследования в производственных условиях.

Объект исследований. Транспортные перевозки, осуществляемые по схеме «один ко многим» с преобладанием маршрутизации по схеме коммивояжера.

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

Научная новизна работы состоит в следующем.

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

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

возки без привлечения экспертов.

3. Разработан и исследован многокритериальный вариант алгоритма Флойда-Уоршалла, позволяющий найти между всеми парами вершин графа общего вида множество путей, недоминируемых по отношению Парето.

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

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

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

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

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

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

4. Многокритериальный вариант алгоритма Флойда-Уоршалла, позволяющий найти между всеми парами вершин графа общего вида множество путей, недоминируемых по отношению Парето.

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

6. Программный комплекс для решения задачи развозки.

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

работы докладывались и обсуждались

- на II международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, с 11 по 16 декабря 2007 г.);

- на Международной научной конференции «Математические методы в технике и технологиях» (Саратовский государственный технический университет, 27 - 31 мая 2008 г., ММТТ-21);

- на III Международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, с 2 по 7 февраля 2009 г.);

- на Всероссийской научной конференции студентов, аспирантов и молодых ученых (Воронеж, с 12 по 13 ноября 2009 г.).

Публикации. Основное содержание работы изложено в 7 публикациях, приведённых в конце текста автореферата, из них 3 [1,2,3] - в изданиях, рекомендуемых ВАК РФ. В публикациях, изданных в соавторстве [1-6], личный вклад соискателя состоит в следующем: [1], [4], [5] - разработка модели; [2] - разработка алгоритма; [3], [6] - разработка прямого хода алгоритма и пакета программ.

Программное средство, реализующее разработанные алгоритмы, зарегистрирвано в • Государственном информационном фонде ФГНУ «Центр информационных технологий и систем органов исполнительной власти» под номером №50200901019 от 20.10.2009г.

Объем и структура работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 120 наименований и приложения. Основной текст изложен на 174 страницах. Работа содержит 11 таблиц и 13 рисунков.

ОСНОВНОЕ СОДЕРЖАНИЕ РАБОТЫ

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

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

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

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

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

Платежи, в т.ч. за эксплуатацию ТС

Конкуренция|Другие

предприятия

Цены на услуги

Предложения

ПРЕДПРИЯТИЕ

"Заказы:

КЛИЕНТЫ

Использование ТС на другие Маршруты.' • нужды расписание движения ТС

грузы, сроки___

Развозка

Ограничения

Транспортная сеть

Рис. 1. Структурная модель проблемосодержащей системы

В результате анализа

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

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

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

Дано: С ={с\ , ..., сп} - множество получателей грузов, сд — база;

t[c¡, Cj] - время проезда от c¡ к с,-; Qj - масса груза, заказанного_/-м получателем; P¡ - грузоподъемность транспортного средства (ТС) г-го типа А„ i = 1,.., т\ E¡ - величина постоянных расходов на эксплуатацию каждого ТС; 0(с;, у) ~ время, которое потребуется, чтобы в j-м пункте разгрузить у кг фуза; Т- срок доставки груза.

Требуется найти общее количество N единиц ТС, набор значений zkj >0 - количество груза, доставляемого к-м ТС j-му получателю, к =

1,.., N, и такие упорядоченные наборы C¡. = {cjk Q ,cjk t ,Cjk 2,.. .,cJk },

Jk,0 = 0 пунктов, обслуживаемых к-м ТС, при которых

А,с{ 1,.., N}; = Qj ; 14j £ P¡. keA¡ к j

и при этом число неравенств вида

u=0

(число опозданий - 1-й критерий) и значение функции суммарных затрат ,q(z) = £ zkj > 0)(2-й критерий) минимальны. Число еди-

I, кеА,

ниц ТС не ограничено.

Задачу развозки в данной постановке следует рассматривать как сложную композицию нескольких задач. Иерархические уровни процесса ее решения отражает системная модель, приведенная на рис. 2.

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

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

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

В работе при выборе стратегии решения задачи был принят сле-

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

Поиск набора подходящих путей между всеми парами ТТ

Поиск подходящих маршрутов объезда всех ТТ

--------4. ^ -

Выбор состава колонны ТС в _зависимости от груза '

2Е

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

Определение порядка движения каждого ТС по маршруту

О

Определение оптимальной загруженности каждого ТС при движении по маршруту

-и---------

Традиционная задача развозки

Выбор способа использования одного ТС в нескольких рейсах

Рис. 2. Иерархические уровни процесса решения задачи развозки

Реализация этого плана представлена в 3-й и 4-й главах.

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

На первом этапе решения сеть автодорог, по которой происходит перемещение ТС, задается в виде графа. Вершины графа - множество вида:

где V'' - подмножество промежуточных вершин (точки пересечение автодорог); V ^ - подмножество точек назначения (торговые точки (ТТ), обслуживаемые ТС). В полученном графе С=(У, Е), каждая дуга е & Е характеризуется набором весов р(е). Решение можно ассоциировать с некоторым путем g на графе (маршрут объезда основных и

вспомогательных вершин). На множестве решений {g} определена векторная функция p(g) = (p,(g), ... ph(g)\ где pk(g) = (*)>

eeg

k = \,h - к-й критерий эффективности каждого решения, аддитивный в силу специфики рассматриваемого класса задач.

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

Имеем следующую задачу. На множестве весов дуг и путей графа G задано некоторое бинарное отношение предпочтения R. Требуется найти между всеми парами вершин (г, у) пути, недоминируемые в смысле отношения R (Л-оптимальные пути).

В результате проведенного анализа альтернативных вариантов решения данной задачи выбран, разработанный в рамках данного исследования, векторный вариант алгоритма Флойда-Уоршалла, как наиболее эффективный. На неформальной версии языка Pascal предлагаемый алгоритм можно представить в виде:

for к:-1 ton do ■ for i\=l to n do for j:=l to rt do

for q 6 {D[i, к]} do forp e {D[k,j}} do

{D[i,j]}:= CR( {D[i,J]}u{q+p });

Здесь D[i, j] - векторный вес Л-оптимального пути из i-й вершины графа ву'-ю;

С:R{X) = {хеХ | VyeX (у, x)£R}

- функция выбора Л-оптимальных альтернатив из множества X.

Корректность алгоритма определяется следующей теоремой.

Теорема 1. Пусть выполнены следующие условия.

1. В графе G каждая пара вершин может соединяться не более, чем одной дугой.

2. Отношение R транзитивно, асимметрично и не зависит от смещения. Последнее свойство означает, что для любой пары точек (х, у) и любого вектора Ъ следующие отношения эквивалентны: xRy и (х + b)R(y + b).

3. Векторный вес любого контура, имеющегося в графе, доминиру-ется нулевым вектором.

Тогда предлагаемый алгоритм позволяет найти все Я-оптимальные пути между всеми парами вершин в графе б, и обратно, все пути, найденные алгоритмом, являются й-оптимальными.

Поскольку отношение Парето удовлетворяет условию 2 теоремы 1, алгоритм можно использовать для поиска Парето-оптимальных путей в графе.

Оценка вычислительной сложности алгоритма составляет 0(Ь3п3), меньшую, чем у известного метода Форда-Беллмана, также применимого к решению данной задачи. Здесь п - число вершин графа; Ь -максимальное количество й-оптимальных путей среди всех пар вершин 2 и

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

Фактор 1. Степень неопределённости, присутствующей в задаче поиска оптимальных путей на графе.

В работе проанализированы следующие ситуации.

1.1. Задача содержит неопределённость, т.к. расход топлива и прочие переменные затраты в условиях города не связаны однозначно со значениями критериев дуг графа.

1.2. Неопределенность отсутствует.

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

В четвертой главе рассматриваются задачи составления оптимального маршрута объезда ТТ и составления оптимального расписания.

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

Фактор 2. Отношение грузоподъемности используемых ТС к массе заказанных грузов.

ЕЗ работе проанализированы следующие варианты.

2.1. Величина отношения близка к единице или меньше 1.

2.2. Величина отношения лежит в пределах от 1 до п (число клиентов) и далека от этих граничных значений.

2.3. Величина отношения близка к п или больше п.

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

Фактор 3. Вариабельность расстояний и/или времени переезда между ТТ и базой.

Проанализированы следующие альтернативные варианты.

.3.1. Расхождение протяженностей пренебрежимо мало.

3.2. Расхождение существует, но не очень значительно.

3.3. Расстояния и/или времена существенно различаются.

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

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

Теорема 2. При сделанных предположениях задача поиска оптимального маршрута развозки сводится к детерминированной задаче коммивояжера, причём результат решения не зависит от численного значения параметра Р.

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

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

Фактор 4. Характер перевозимого груза.

Рассмотрены следующие альтернативные варианты.

3.1. Груз можно делить на части в любой пропорции.

3.2. Груз однородный мелкогабаритный и его можно делить на мелкие порции.

3.3. Груз неоднородный - набор блоков разной массы.

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

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

Задача 1. Генерируются варианты комплектации ТС, т.е. способы использования имеющихся в наличии различных по грузоподъемности ТС, необходимых для выполнения заказов. Формальная постановка задачи имеет следующий вид.

В условиях общей задачи развозки требуется найти все подмноже-

п

ства Л/с{1,..., ш} и целые числа п1 >0, г е М, что

у /еЛ/ у ,еМ

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

Дано: множество А, содержащее т различных типов элементов: А = {си, аь ..., а\, аг,..., аг> ат), (ТС в заданной комплекта-

т

ции) и количества > 0 элементов каждого типа, = К ■

/=1

Требуется найти все упорядоченные ^-выборки из элементов множества Л.

Задача 3. Для каждого способа упорядочения определяются варианты загруженности каждого ТС и вычисляется время окончания заказа. Отбираются решения, удовлетворяющие временным ограничениям.

Дано: Ск = {с^0,сукус^2 }, Л,0 = вариант маршрута

движения каждого к-го ТС.

В условиях общей задачи развозки требуется найти значения гщ > 0

- количество груза, доставляемого к-м ТС у'-му получателю, при которых соблюдаются ограничения

Yzkj=Qj\ X 2kj ^ Pt , кеА,-

к j

X кеА,.

и=О

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

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

Дано: множество U= {и\, ..., ип} ТС одинаковой грузоподъёмности и время s(u), которое требуется каждому ТС для объезда своих получателей груза.

Требуется найти такое разбиение множества U на непересекающиеся подмножества U\, ...,[/*, чтобы при этом число

ueUj

подмножеств было минимально.

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

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

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

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

ОСНОВНЫЕ РЕЗУЛЬТАТЫ РАБОТЫ

Основные результаты диссертационного исследования заключаются в следующем.

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

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

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

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

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

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

7. Создан программный комплекс «ОРв» для решения задачи развозки.

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

Список основных публикаций по теме диссертации Публикации в изданиях, рекомендованных ВАК РФ

1. Модели оптимального планирования перевозок грузов собственным автотранспортом на предприятиях [Текст] / Блинов И.В., Бугаев Ю.В. // Вестник ВГТУ. - 2007. - т. 3. № 8. - С. 170-173.

2. Алгоритм решения задачи развозки с участием несколь-ких транспортных средств [Текст] / Блинов И.В., Бугаев Ю.В. // Вестник ВГТУ. - 2008. - т. 4. № 6. - С.57-60.

3. Обобщение алгоритма Флойда-Уоршалла на случай нескольких критериев [Текст] / Блинов И.В., Бугаев Ю.В., Чикунов C.B. // Вестник ТГТУ. - 2009. - т. 15. № 4. - С.885-892.

Статьи и материалы конференций

4. Оптимальное планирование грузоперевозок собствен-ным автотранспортом на предприятиях [Текст] / Блинов И.В., Бугаев Ю.В. // Материалы междунар. науч. конф. «Современные проблемы прикладной математики и математического моделирования». -Воронеж: Воронеж гос. унив., 2007. - с.46.

5. ■ Оптимальное планирование грузоперевозок собствен-ным автотранспортом на предприятиях [Текст] / Блинов И.В., Бугаев Ю.В. // Материалы междунар. науч. конф. «Математи-ческие методы в технике и технологиях - ММТТ-21». - Саратов: Саратов гос. унив., 2008. ч. 8. - С.86-88.

6. Векторный алгоритм Флойда [Текст] / Блинов И.В., Бугаев Ю.В. Киселева Н.В., Солодова Е.Д. // Материалы III междунар. науч. конф. «Современные проблемы прикладной математики и математического моделирования». - Воронеж: ВГУ, 2009. - ч. 2. - С. 53 - 55.

7. Моделирование развозки продукции по потребителям предприятия пищевой промышленности [Текст] / Блинов И.В. // Материалы всероссийской науч. конф. студентов, аспирантов и молодых ученых. - Воронеж: Воронеж, гос. технол. акад., 2008. -С.223-226.

Подписано в печатьQ2 .Q5.2010 г. Формат 60 х 84/16

■ Усл. печ. л. 1,0. Тираж 100 экз. Заказ № уд 2 ГОУВПО «Воронежский государственный университет» (ГОУ ВПО «ВГУ») Отдел полиграфии ГОУ ВПО «ВГУ» Адрес ГОУ ВПО «ВГУ» и отдела полиграфии 394006, г. Воронеж, Университетская пл., 1

Введение.

Глава 1. Модели и методы решения задачи развозки.

1.1. Проблемные ситуации, приводящие к необходимости решения задачи развозки в производственных условиях.

1.2. Системный анализ, как метод решения слабоструктурированных проблем.

1.3. Подходы к решению дискретных многокритериальных задач.

1.4. Методы решения классических прототипов задачи развозки.

1.4.1. Транспортная задача.

1.4.2. Задача коммивояжера.

1.4.3. Задача поиска оптимального пути в графе.

1.4.4. Задача о наименьшем покрытии.

1.4.5. Понятие вычислительной сложности.

1.5. Существующие варианты формальной постановки задачи развозки и подходы к их решению.

1.6. Выводы, цели и задачи исследований.

Глава 2. Системный анализ проблемы.

2.1. Вводные положения.

2.2. Анализ проблемы.

2.2.1. Модель проблемной ситуации.

2.2.2. Анализ целей.

2.2.3. Формирование критериев.

2.2.4. Определение ограничений и формирование допущений.

2.3. Формальная постановка задачи.

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

2.5. Размерные (количественные) допущения.

2.6. Выводы по главе.

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

3.1. Формализация транспортной сети.

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

3.3. Анализ векторного алгоритма Флойда-Уоршалла.

3.3.1. Корректность алгоритма.

3.3.2. Оценка вычислительной сложности.

3.4. Пример применения алгоритма Флойда-Уоршалла.

3.5. Окончательный выбор оптимальных путей.

3.6. Выводы по главе.

Глава 4. Модели процесса развозки и алгоритмы составления плана перевозок.

4.1. Алгоритм формирования маршрута обхода ТТ.

4.2. Перебор вариантов комплектации ТС.

4.3. Перебор вариантов порядка следования ТС по маршруту.

4.4. Функции развозки.

4.5. Перебор вариантов загрузки каждого ТС при данном упорядочении.

4.6. Поиск способа использования одного ТС в нескольких рейсах.

4.7. Система допущений в модели задачи развозки и формирование базовой модели развозки.

4.7.1. Допущения с вариациями.

4.7.2. Безвариантные допущения.

4.8. Сводный алгоритм решения базовой задачи развозки.

4.9. Выводы по главе.

Глава 5. Описание программного комплекса и решение практической задачи развозки.

5.1. Структура специального программного обеспечения.

5.2. Вычислительный эксперимент решения практической задачи развозки.

5.3. Выводы по главе.

Актуальность проблемы. Современная экономическая ситуация в России характеризуется все возрастающей конкуренцией на рынке товаров и услуг. Следствием этого является повышение уровня требований клиентов. В таких условиях развитие любой компании, ориентированной на обслуживание большого числа потребителей, должно быть очень динамичным. Целью этого развития является предоставление услуг такого качества и в таком объеме, которые будут соответствовать ожиданиям клиентов. Известно, что затраты на производство некоторых товаров составляют лишь около 10% их стоимости, в то время как доля расходов на доставку может достигать 50%, а в ряде случаев и больше.

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

Научной основой задачи оптимального планирования грузоперевозок является классическая транспортная задача. Разнообразие целей и критериев при ее постановке в применении к различным практическим областям привело к появлению большого класса «развозочных» задач», решением которых в разное время занимались такие ученые как Дж. Литл, Р. Беллман, С. Уор-шалл, Р. Флойд, И. X. Сигал, Э. Дейкстра, В. А. Житков, А.В. Ефремов. Однако, существующие подходы к решению задачи развозки исходят из ее упрощенной постановки, не в полной мере соответствующей реальным условиям.

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

Диссертационная работа выполнена в рамках госбюджетной НИР, «Математическое и компьютерное моделирование в задачах проектирования и оптимизации функционирования информационных и технологических систем» № госрегистрации 01.2006.05298, а также гранта РФФИ 06 - 07 - 89189-а по теме «Разработка информационных технологий выбора на необозримом для J11 IP множестве альтернатив».

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

Поставленная цель достигается посредством решения следующих задач.

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

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

3. Синтез базового варианта модели процесса развозки.

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

5. Создание программного обеспечения, реализующего разработанные алгоритмы.

6. Проведение вычислительных экспериментов и практическая реализация результатов исследования в производственных условиях.

Объект исследований. Транспортные перевозки, осуществляемые по схеме «один ко многим» с преобладанием маршрутизации по схеме коммивояжера.

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

Научная новизна работы состоит в следующем.

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

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

3. Разработан и исследован многокритериальный вариант алгоритма Флойда-Уоршалла, позволяющий найти между всеми парами вершин графа общего вида множество путей, недоминируемых по отношению Парето.

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

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

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

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

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

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

4. Многокритериальный вариант алгоритма Флойда-Уоршалла, позволяющий найти между всеми парами вершин графа общего вида множество путей, недоминируемых по отношению Парето.

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

6. Программный комплекс для решения задачи развозки.

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

- на II международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, с 11 по 16 декабря 2007 г.);

- на Международной научной конференции «Математические методы в технике и технологиях» (Саратовский государственный технический университет, 27-31 мая 2008 г., ММТТ-21);

- на III Международной научной конференции «Современные проблемы прикладной математики и математического моделирования» (Воронеж, с 2 по 7 февраля 2009 г.);

- на Всероссийской научной конференции студентов, аспирантов и молодых ученых (Воронеж, с 12 по 13 ноября 2009 г.).

Публикации. Основное содержание работы изложено в 7 публикациях, из них 3 [1, 2, 3] - в изданиях, рекомендуемых ВАК РФ. В публикациях, изданных в соавторстве [1-6], личный вклад соискателя состоит в следующем: [1], [4], [5] - разработка модели; [2] - разработка алгоритма; [3], [6] - разработка прямого хода алгоритма и пакета программ.

Программное средство, реализующее разработанные алгоритмы, зарегистрирвано в Государственном информационном фонде ФГНУ «Центр информационных технологий и систем органов исполнительной власти» под номером №50200901019 от 20.10.2009 г. (прил. 3).

Объем и структура работы. Диссертационная работа состоит из введения, пяти глав, заключения, списка литературы из 120 наименований и приложения. Основной текст изложен на 174 страницах. Работа содержит 11 таблиц и 13 рисунков.

5.3. Выводы по главе

1. Создан программный комплекс «OPG» для решения общей задачи развозки в выбранной постановке.

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

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

Заключение

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

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

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

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

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

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

7. Создан программный комплекс «OPG» для решения задачи развозки.

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

1. АгЪерман, М.А. Выбор вариантов: основы теории Текст. / М. А. Ай-зерман, Ф. Т. Алескеров. М.: Наука, 1990. - 240с.

2. Антонов, А. В. Системный анализ Текст. : учеб. пособие для вузов. -М.: Высшая школа, 2006. 454с.

3. Банды, Б. Основы линейного программирования Текст. / Б. Банди. — Пер. с англ. — М.: Радио и связь, 1989. — 176с.

4. Беллман, Р. Динамическое программирование Текст. / Р. Беллман. — М.: ИЛ, 1960.-400с.

5. Беспалов, Р. ГТранспортная логистика. Новейшие технологии построения эффективной системы доставки Текст. / Р. Г. Беспалов. — М.: Вершина, 2007.-384 с.

6. Борисов, А. Н. Диалоговые системы принятия решений на базе мини-ЭВМ: Информационное, математическое и программное обеспечение Текст. / А. Н. Борисов, Э. Р. Вилюмс, Л. Я. Сукур — Рига: Зинатне, 1986. — 195с.

7. Борисов, А. Н. Методы интерактивной оценки решений Текст. / А. Н. Борисов, А. С. Левченков. Рига: Зинатне, 1982. - 139с.

8. Бояринов, А. И. Методы оптимизации в химической технологии Текст. / А. И. Бояринов, В. В. Кафаров. М.: Химия, 1975. - 576с.

9. Бритавский, Г. М. Метод "ветвей и границ" для оптимизации параметров структуры автоматических линий Текст. / Г. М. Бритавский, Б. И. Юхименко // Кибернетика. 1976. -N2. - с. 102-104.

10. Бугаев, Ю. В. Алгоритм поиска оптимальных путей в бесконтурном графе Текст. / Ю. В. Бугаев, С. В. Чикунов // Математическое моделирование технологических систем: Сб. науч. тр. Вып.З / Воронежская гос. тех-нол. акад. Воронеж, 1999. - с.58-61.

11. Бугаев, Ю. В. Векторный вариант алгоритма Форда-Беллмана Текст. / Ю. В. Бугаев, В. В. Сысоев // Искусственный интеллект в технич. системах: Сб. тр. М.: ИФТП, 1999. - с.33-41.

12. Бугаев, Ю. В. Комплекс программных средств для поэтапного принятия решений Текст. / Ю. В. Бугаев, С. В. Чикунов // Материалы XXXVI отчетной научной конференции за 1997 год: В 2-х ч. / Воронеж, гос. технол. акад. Воронеж, 1998. - 4.2. - 186с.

13. Бугаев, Ю. В. Многокритериальное динамическое программирование Текст. / Ю. В. Бугаев, В. В. Сысоев, С. В. Чикунов // Материалы XXXV отчетной научной конференции за 1996 год: В 2-х ч. / Воронеж, гос. технол. акад. Воронеж, 1997. - 4.1. - 149с.

14. Бугаев, Ю.В. Поиск R оптимальных путей на графах Текст. / Ю. В. Бугаев, С. В. Чикунов // Понтрягинские чтения - IX: Тезисы докладов. -Воронеж: ВГУ, 1998. - с.35.

15. Бугаев, Ю. В. Применение прямого обобщения скалярных алгоритмов в векторной оптимизации на графах Текст. / Ю. В. Бугаев // Дискретная математика. 2001. Т. 13. Вып. 3. - с.110 - 124.

16. Венгерова, И. В. К вопросу об эффективности метода ветвей и границ Текст. / И. В. Венгерова, Ю. Ю. Финкельштейн // Экономика и математические методы, Вып.1, 1975.-с.186-193.

17. Вентцелъ, Е. С. Исследование операций Текст. / Е. С. Вентцель. -М.: Сов.радио,1972 551с.

18. Вермишев, Ю. X Методы автоматического поиска решений при проектировании сложных технических систем Текст. / Ю.Х. Вермишев М.: Радио и связь, 1982. - 152с.

19. Волкова, В. Н. Искусство формализации Текст. / В. Н. Волкова. — СПб: Изд-во СПбГТУ, 2000. 199с.

20. Гайндрик, КВ. Оптимальное решение упрощенной задачи развозки Текст. / К. В. Гайндрик, В. А. Житков // Математические методы решения экономических задач — 1969. — Вып. 1-е. 67-75.

21. Геминтерн, В. И. Методы оптимального проектирования Текст. / В. И. Геминтерн, Б. М. Каган. М.: Энергия, 1980. - 160с.

22. Гермейер, Ю. Б. Введение в теорию исследования операций Текст. / Ю. Б. Гермейер. М.: Наука, 1971. - 383с.

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

24. Дауэрсокс, Б. Логистика. Интегрированная цепь поставок Текст. / Б. Дауэрсокс. М.: Олимп-Бизнес, 2008. - 640 с.

25. Емеличев, В. А. Лекции по теории графов / В. А. Емеличев, О. И. Мельников, В. И. Сарванов, Р. И. Тышкевич. М.: Наука, 1990. - 384с.

26. Емельянов, С. В. Логика рационального выбора Текст. / С. В. Емельянов, Э. Л. Наппельбаум // Техническая кибернетика. М.: ВИНИТИ, 1977. -Т.8. - с. 5-101.

27. Емельянов, С. В. Модели и методы векторной оптимизации Текст. / С. В. Емельянов, В. И. Борисов, А. А. Малевич и др. // Итоги науки и техники. Техническая кибернетика. М.: ВИНИТИ, 1973. - Т.5. - с.З86-448.

28. Ермаков, С. М. Курс статистического моделирования Текст. / С. М. Ермаков, Г. А. Михайлов. М.: Наука, 1976. - 320с.

29. Ермольев, Ю. М. Математические методы исследования операций Текст. / [Ю. М. Ермольев, И. И. Ляшко, В. С. Михалевич и др.]. Киев: Ви-ща школа. Головное изд-во, 1979. - 312с.

30. Ефремов, А. В. Модельно-эвристический метод сменно-суточного планирования и оптимального управления грузовыми автомобильными перевозками Текст. / А. В. Ефремов // Сборник научных трудов Московского автомобильно-дорожного института, 1980.-Вып. l-c.3-17.

31. Житков, В. А., Планирование автомобильных перевозок грузов мелкими партиями Текст. / В. А. Жидков. М: Транспорт, 1976. - 1 Юс.

32. Житков, В. А. Методы оперативного планирования грузовых автомобильных перевозок Текст. / В. А. Житков, К. В. Ким. М: Транспорт, 1982.- 183с.

33. Зимин, Ю. М. Методология системного подхода к разработке организационных структур управления большими системами: Учебное пособие Текст. / Ю. М. Зимин, Ю. Д. Умрихин, Ю. Н. Черкасов. -М.Мир, 1981. -287с.

34. Казакова, Е. А. Алгоритм решения полиматричной задачи коммивояжера Текст. / Е. А. Казакова // Математические методы решения экономических задач: Сб. науч. тр. Вып.1 / М.:Наука, 1969. 176с.

35. Карлин, С. Математические методы в теории игр, программировании и экономики Текст. / С. Карлин / Пер. с англ. М.: Мир, 1964. 838 с.

36. Качала, В. В. Основы теории систем и системного анализа Текст. : учеб. пособие для вузов. М.: Горячая линия — Телеком, 2007. - 216с.

37. Кини, Р. Принятие решений при многих критериях: замещения и предпочтения Текст. / Р. Кини, X. Райфа // Пер. с англ. М.: Радио и связь, 1981.-560с.

38. Кини, Р. Функции полезности многомерных альтернатив Текст. / Р. Кини // Вопросы анализа и процедуры принятия решений. М.: Мир, 1976. - с.59-79.

39. Ковалев, К. Ю. Логистика в розничной торговле: как построить эффективную сеть Текст. / С.А. Уваров, П.Е. Щеглов СПб: Питер, 2006. -272с.

40. Корбут, А.А. Об эффективности комбинаторных методов в дискретном программировании Текст. / А.А. Корбут, И.Х. Сигал, Ю.Ю. Фин-келыптейн // Современное состояние теории исследования операций / Под ред. Н.Н. Моисеева. М.: Наука, 1979. - с.283-310.

41. Кофман, А. Введение в прикладную комбинаторику Текст. / А. Кофман // Пер. с фр. М.: Наука, 1975. - 479с.

42. Кофман, А. Методы и модели исследования операций Текст. / А. Кофман, А. Анри-Лабордер М.: Мир, 1977. - 432с.

43. Кравцов, М. К. Неразрешимость задач векторной дискретной оптимизации в классе алгоритмов линейной свертки критериев Текст. / М. К. Кравцов // Дискр. матем. 1996. - 8, вып. 2. - С. 89-96.

44. Краснощекое, П. С. Математические модели в исследовании операций Текст. / П. С. Краснощеков . М.: Наука, 1984. — 213с.

45. Краткий биографический справочник (ученые и специалисты капиталистических стран, занимающиеся проблемами управления и системными исследованиями). М.: ВНИИСИ, 1980. - 148с.

46. Кристофидес, Р. Теория графов. Алгоритмический подход Текст. / Р. Кристофидес. М.: Мир, 1978. - 432с.

47. Ларичев, О. И. Методы многокритериальной оценки альтернатив / О. И. Ларичев. Тр. ВНИИСИ, 1978. - Вып.5. - с.5-30.

48. Ларичев, О. И. Наука и искусство принятия решений Текст. / О. И. Ларичев. М.: Наука, 1979. - 200с.

49. Ларичев, О. И. Объективные модели и субъективные решения Текст. / О. И. Ларичев. М.: Наука, 1987. - 144с.

50. Ларичев, О. И. Человеко-машинные процедуры принятия решений многокритериальных задач математического программирования Текст. / О. И. Ларичев, О. А. Поляков // Экономика и мат. методы, 1980. Вып.1, Т. 16. -с.127-145.

51. Липский, В. Комбинаторика для программистов Текст. / В. Лип-ский. М.: Мир, 1988. - 213с.

52. Литтл, Дж. Алгоритм решения задачи о коммивояжере Текст. / Дж. Литтл, К. Мурти, Д. Суини, К. Кэрел // Экономика и математический методы. 1965. - т.1., вып.1- с. 81-83.

53. Магрупов, Т. М. Графы, сети, алгоритмы и их приложения Текст. / Т. М. Магрупов // Под ред. Ф. Б. Абуталиева. Ташкент: Фан, 1990. - 120с.

54. Макаров, И. М. Теория выбора и принятия решений Текст. / [И. М. Макаров, Т. М. Виноградская, А. А. Рубчинский и др.] М.: Наука, 1982. -328с.

55. Марченко, А. И. Программирования в среде Turbo Pascal 7.0 Текст. / А. И. Марченко // Под ред. В. П. Тарасенко. 7-е изд. - К.:ВЕК+, 2003.-464с.

56. Меламед, И. И. Теория и алгоритмы решения многокритериальных задач комбинаторной оптимизации Текст. / И. И. Меламед, И. X. Сигал. -М.: Изд-во ВЦ РАН, 1996. 51с.

57. Михалевич, В. С. Алгоритмы последовательного анализа и отсеивания вариантов в задачах дискретной оптимизации Текст. / В. С. Михалевич, В. JI. Волкович, А. Ф. Волошин и др. // Кибернетика, 1980. N3. - с.76-85.

58. Моисеев, Н. Н. Математические задачи системного анализа Текст. / Н. Н. Моисеев. М.: Наука, 1981. - 156с.

59. Нейман, Д. Теория игр и экономическое поведение Текст. / Д. Нейман, О. Моргенштерн. — М.: Наука, 1970. 707с.

60. Новиков, Ф. А. Дискретная математика для программистов Текст. / Ф. А. Новиков. СПб. Литер, 2002. - 304с.

61. Озерной, В. М. Теоретико-множественный подход к задачам принятия решений при векторном критерии Текст. / В. М. Озерной, М. Г. Гафт // VI симпозиум по кибернетике. Тбилиси, 1972. - 4.2. - с.82-87.

62. Окулов, С. М. Программирование в алгоритмах Текст. / С. М. Окулов // Изд. 2-е. М.:БИНОМ. Лаборатория знаний, 2006. - 383с.

63. Орлов, В. А. Теория графов и комбинаторика Текст. / В. А. Орлов. Томск: Томск, политехи, инст-т, 1988. - 95с.

64. Перегудов, Ф. И. Введение в системный анализ Текст. : учеб. пособие для вузов / Ф. И. Перегудов, Ф. П. Тарасенко М.: Высшая школа, 1989.-367 с.

65. Подиновский, В. В. Аксиоматическое решение проблемы оценки важности критериев в многокритериальных задачах Текст. / В. В. Подиновский // Современное состояние теории исследования операций / Под ред. Н. Н. Моисеева. М.: Наука, 1979. - с.117-145.

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

67. Текст. / В. В. Подиновский. Вып.1. Эффективные планы. М.: 1971. - 314с.

68. Подиновский, В. В. Оптимизация по последовательно применяв- • мым критериям Текст. / В. В. Подиновский, В. М. Гаврилов. М.: Сов. радио, 1975.- 192с.

69. Подиновский, В. В. Парето-оптимальные решения многокритериальных задач Текст. / В. В. Подиновский, В. Д. Ногин. М.: Наука, 1982. -256с.

70. Растригин, JI. А. Адаптивные методы многокритериальной оптимизации Текст. / JI. А. Растригин, Я. Ю. Эйдук // Автоматика и телемеханика.- 1985.-Nl.-c.5-25.

71. Рейнгольд, Э. Комбинаторные алгоритмы. Теория и практика Текст. / Э. Рейнгольд, Ю. Нивергельт, Н. Део. М.: Мир, 1980. - 480с.

72. Сергиенко, И. В. О некоторых направлениях в развитии методов дискретной оптимизации и их программного обеспечения Текст. / И. В. Сергиенко // Кибернетика. 1982. - N6. - с.45-53.

73. Сергиенко, И. В. Приближенные методы решения дискретных задач оптимизации Текст. / И. В. Сергиенко, Т. Т. Лебедева, В. А. Рощин. -Киев: Наукова думка, 1980. 273с.

74. Сивохина, Н. П. Логистика: Учебное пособие / Н. П. Сивохина, В. Б. Родионов, Н. М. Горбунов М: ООО «Издательство ACT», РИК «Русанова», 2000. - 224с.

75. Сигал, И. X. Последовательный анализ вариантов при решении экстремальных задач Текст. / И. X. Сигал // Системы распределения ресурсов на графиках 1970. - Вып. 1-е. 5-12.

76. Сысоев, В. В. Автоматизированное проектирование линий и комплектов оборудования полупроводникового и микроэлектронного производства Текст. / В. В. Сысоев. М.: Радио и связь, 1982. - 120с.

77. Сысоев, В. В. Конфликт. Сотрудничество. Независимость. Системное взаимодействие в структурно-параметрическом представлении Текст. / В. В. Сысоев. -М.: МАЭП, 1999. 151с.

78. Сысоев, В. В. Построение моделей принятия проектных решений по ранее проведенным экспертизам Текст. / В. В. Сысоев, М. С. Чирко // Автоматизация проектирования технологии и оборудования электронной промышленности. Воронеж: ВПИ, 1982. - с.71-74.

79. Сысоев, В. В. Принятие решений в многокритериальных задачах Текст. / В. В. Сысоев, А. А. Кадет. Воронеж: ВТИ, 1982, Деп. в ВИНИТИ 1982, N416-82.

80. Сысоев, В. В. Системное моделирование многоцелевых объектов Текст. / В. В. Сысоев // Методы анализа и оптимизации сложных систем. -М.: ИФГП РАН, 1993. с.80-88.

81. Сысоев, В. В. Системное моделирование Текст. : учеб. пособие для вузов / В. В. Сысоев. Воронеж: ВТИ, 1991. - 80с.

82. Сысоев, В. В. Структурные и алгоритмические модели автоматизированного проектирования производства изделий электронной техники Текст. / В. В. Сысоев. Воронеж: ВТИ, 1993. - 207с.

83. Тангян, А. С. Модели социального выбора с конечным и бесконечным числом участников Текст. / А. С. Тангян. М.: Препринт ЦЭМИ АН СССР, 1979.-162с.

84. Триггер, Д. Я. Введение в системный анализ Текст. / Д. Я. Триггер. -М.: МИФИ, 1978.-220с.

85. Фаронов, В. В. Турбо Паскаль 7.0. Практика программирования Текст. : учебное пособие / В. В. Фаронов. Изд. 7-е. - М.: «Нолидж», 2001. — 416с.

86. Финкелъштейн, Ю. Ю. Приближенные методы и прикладные задачи дискретного программирования Текст. / Ю. Ю. Финкелыптейн. М.: Наука, 1976.-264с.

87. Фишберн, П. С. Многомерные функции полезности в теории ожидаемой полезности Текст. / П. С. Фишберн // Статистические модели и многокритериальные задачи принятия решений. М.: 1979. - с.11-25.

88. Фишберн, 77. С. Обобщенная независимость по полезности и некоторые смежные вопросы Текст. / П. С. Фишберн, Р. Кини // Статистические модели и многокритериальные задачи принятия решений. М.: 1979. - С. 2644.

89. Фишберн, П. С. Теория полезности для принятия решений Текст. / Пер. с англ. М.: Наука, 1978. - 352с.

90. Чикунов, С. В. Сравнительный анализ методов векторной оптимизации на графах Текст. / С. В. Чикунов // Материалы XXXVII отчетной научной конференции за 1998 год: в 2-х ч. Воронеж: Воронеж, гос. технол. акад., 1999.-Ч.1.-С.216.

91. Шаракшанэ, А. С. Сложные системы Текст. : учеб. пособие для вузов / А. С. Шаракшанэ. М.: Высш. шк., 1977. - 247с.

92. Шоломов, Л. А. Логические методы исследования дискретных моделей выбора Текст. / Л. А. Шоломов. М.: Наука. Гл. ред. физ.-мат. лит., 1989.-288с.

93. Штонер, Р. Многокритериальная оптимизация. Теория, вычисления и приложения Текст. / Р. Штонер. М.: Радио и связь, 1992. - 360с.

94. Экенроде, Р. Т. Взвешенные многомерные критерии Текст. / Р. Т. Экенроде // Статистическое измерение качественных характеристик. М.: 1972. - с.139-154.

95. Юдин, Д. Б. Вычислительные методы теории принятия решений Текст. / Д. Б. Юдин. -М.: Наука, 1989. 316с.

96. Bellman, R. Е. On a routing problem Text. / R. E. Bellman // Quart. Appl. Math. Ed. Est. Publ.: 1958. ch.16. - P.87-90.

97. Cohon, J. L. Multiobjective programming and planning Text. / J. L. Cohon. NY Academic Press: 1978. - 344 p.

98. Dijbtra, E. W. A note on two problems in connection with graphs Text. / E. W. Dijkstra // Numer. Math. NY Academic Press: 1959. - P.269-271.

99. Floyd, R. W. Algorithm 97 shortest path Text. / R. W. Floyd. -Comm. of ACM: 1962. - 345 p.

100. Ford, L. R. Network flow theory Text. / L. R. Ford // The Rand Corp. Ed. Est. Publ.: 1956. - on august. - p.923.

101. Garfinkel, R. S. The set partitioning problem: set covering with equality constraints Text. / R. S. Garfinkel, G. L. Nemhauser Ops. Res.: 1969. -p.848.

102. Gimpel, J. F. A reduction technique for prime implicant tables Text. / J. F. Gimpel.- IEEE Trans.: 1965. -p.535.

103. Jensen, P. A. Optimal networks partitioning Text. / P.A. Jensen. -Ops. Res.: 1971.-p.916.

104. Karwan, M. H. On finding starting feasible solutions for some specially structured linear programming problems Text. / M. H. Karwan, S. Zionts // Working Paper №445 School of Management. State University of New York at Buffalo: 1980.-p. 45.

105. Little, J. D. C. An Algorithm for the traveling salesman problem Text. / J. D. C. Little, K. G. Murty, D. W. Sweeney, C. Karel. Op. Research: 1963. - №11. — P.972-989.

106. Michadu, P. Exact implicit enumeration method for solving the set partitioning problem Text. / P. Michadu. IBM J. of Res. and Dev.: 1972. -p.573.

107. Pierce, J. F. Application of combinatorial programming algorithmsfor a class of all-zero-one integer programming problems Text. / J. F. Pierce. -Man. Sci.:1968. -p.191.

108. Pierce, J. F. Improved combinatorial programming algorithms for a class of all-zero-one integer programming problems Text. / J. F. Pierce, J. S/. Lasky. Man. Sci. - 1973. - p.528.

109. Pyne, J. B. An essay on prime implicant tables Text. / J. В. Pyne, E. J. Jr. McCluskey. J. of SIAM (Appl. Math.): 1961. - p.604.

110. Quine, W. V. The problem of simplifying truth functions Text. / W. V. Quine. American Mathematical Monthly: 1952. - p.521.

111. Rosencrantz, D. J. An analysis of several heuristics for the traveling salesman problem Text. / D. J. Rosencrantz, R. E. Stearns, P. M. Lewis // SIAM J. Comput.: 1977. -№6. -P.563-581.

112. Saska, J. Linearni multiprogramovani Text. / J. Saska. Debr. Vest.: Ekon.-mat. obz., 1968. -Roc.3, P.357-373.

113. Villareal, B. Branch and bound approach to interactive multicriteria integer linear programming Text. / B. Villareal, M. H. Karwan, S. A Zionts // Paper presented at Joint National Meeting TIMS. ORSA, Washington, D.C.: 1980. -P.71-78.

114. Warshall, S. A theorem on Boolean matrices Text. / S. Warshall. J. ACM: 1962.-P. 11-12.

115. Zionts, S. Multiple criteria decision making for discrete alternatives with ordinal criteria Text. / S. Zionts I I Working Paper №299 School of Management. NY State University of New York at Buffalo: 1977. - p.38.

116. Zionts, S. Multiple criteria problem solving Text. / S. Zionts. Berlin Springer: 1978.-481 p.