По направлению «технология траспортных процессов и систем»

МЕТОДИЧЕСКИЕ РЕКОМЕНДАЦИИ

ПО ВЫПОЛНЕНИЮ И ЗАЩИТЕ КУРСОВОЙ РАБОТЫ (ПРОЕКТА) ПО ДИСЦИПЛИНЕ «МОДЕЛИРОВАНИЕ ТРАНСПОРТНЫХ ПРОЦЕССОВ И СИСТЕМ» ДЛЯ СТУДЕНТОВ

ПО НАПРАВЛЕНИЮ «ТЕХНОЛОГИЯ ТРАСПОРТНЫХ ПРОЦЕССОВ И СИСТЕМ»

Г. Челябинск, 2015 г.

I Основные положения

Дисциплина «Моделирование транспортных процессов» предназначена для реализации Федерального государственного стандарта Высшего профессионального образования по направлению 190700.62 «Технология транспортных процессов» и является единой для всех форм обучения.

1 Цели и задачи изучаемой дисциплины

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

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

Задачами преподавания дисциплины являются:

- освоение и использование аппарата математического моделирования производственных процессов на транспорте на основе методов математического программирования;

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

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

2 Входные требования и место дисциплины в структуре ООП бакалавриата

«Моделирование транспортных процессов» является дисциплиной, формирующей у студентов общее представление о взаимодействии различных видов транспорта. Базируется на таких дисциплинах, как: «Математика», «Информатика», «Информационные технологии на транспорте», «Теория транспортных процессов и систем», «Прикладная математика», «Вычислительная математика», «Компьютерная математика», подготовка к производственной практике.

Изучение дисциплины необходимо для дальнейшего изучения таких дисциплин, как: «Городской транспортный комплекс», «Пассажирские транспортные системы», «Основы транспортно-экспедиционного обслуживания», «Международная транспортная экспедиция», «Международные перевозки», «Грузовые перевозки», «Пассажирские перевозки». Выполнение ВКР.

 

II Требования к курсовой работе

Курсовая работа (проект) по дисциплине ставит перед собой основную цель - подготовить студента к выполнению выпускной квалификационной работы по специальности 190700.62 "Технология транспортных процессов".

Подготовка курсовой работы (проекта) включает этапы:

- выбор темы, варианта;

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

– исследование теоретических аспектов проблемы;

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

– оформление курсовой работы (проекта).

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

Курсовая работа (проект) должна соответствовать следующим критериям:

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

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

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

 

Выбор темы, варианта курсовой работы (проекта)

Выбор темы

Выбор темы определяется студентами в инициативном порядке или с помощью руководителя курсовой работы (проекта).

Темы курсовой работы (проекта) утверждается преподавателем кафедры, ведущим дисциплину.

Тематика курсовых работ приведена в приложении 1.

Выбор варианта

Номер своего задания студент выбирает по следующей схеме: из таблицы №1 Исходные данные курсовой работы (проекта) выбирается вариант по последней цифре студенческого билета, из таблицы №3 Нормативы для расчета маршрутов выбирается вариант по предпоследней цифре студенческого билета.

Методические рекомендации по выполнению курсовой работы (проекта) даны в приложении 2.

 

Структура и содержание курсовой работы (проекта)

Структура курсовой работы (проекта) по теме

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

Титульный лист оформляется на стандартном бланке и содержит название темы, фамилию, имя, отчество студента; фамилию, имя, отчество, ученую степень и ученое звание (должность) руководителя курсовой работы. Титульный лист является первой страницей проекта.

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

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

Введение. Это общая характеристика курсовой работы (проекта), ее “визитная карточка”, резюме. В нем обосновывается актуальность темы исследования, степень ее проработанности, определяются цель и задачи, методологические и теоретические основы исследования. Помимо этого во введении должна быть показана структура курсовой работы (проекта), назван объект, на примере которого проводились конкретные исследования. Объем введения 3 - 5 стр.

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

Глава первая. Может состоять из двух основных разделов − теоретического и аналитического. Наличие аналитического раздела является обязательным.

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

В теоретическом разделе могут быть рассмотрены:

– понятие и сущность изучаемого явления или процесса;

– краткий исторический обзор;

– тенденции развития тех или иных процессов;

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

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

Назначением этого раздела является подробное раскрытие практического состояния проблемы (темы исследуемого процесса или явления). Раскрываются конкретные методы принятия решения той или иной проблемы.

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

Величина первой главы - примерно 20 - 30% от общего объема рукописи.

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

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

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

Таким образом, заключение должно содержать все существенное и новое, что составляет итог исследования и выносится на защиту. Заключение может занимать 2-3 страницы.

Список использованных источников научной информации является составной частью курсовой работы (проекта) и показывает степень изученности проблемы. Минимальный список должен содержать не менее 10 источников.

В приложения выносится вспомогательный материал, который облегчит восприятие основной части курсовой работы (проекта). Наличие приложения не является обязательным.

Работа по сбору и обработке информации является одним из наиболее ответственных и сложных этапов выполнения курсовой работы (проекта).

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

1) фактические данные о работе предприятия, взятого в качестве объекта исследования (основной и главный источник);

2) публикации в специализированных периодических изданиях;

3) специальная литература – научные публикации (книги, статьи) по выбранной теме. Они могут подбираться студентом самостоятельно, а также рекомендоваться руководителем курсовой работы (проекта);

4) учебные пособия. Студент должен использовать те учебные пособия, которые указаны в списках литературы по программам конкретных дисциплин. Эти материалы служат основой подготовки теоретической части курсовой работы (проекта);

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

Структура курсовой работы (проекта) по варианту

Курсовая работа (проект) должна включать следующие разделы:

1. Постановка и математическая модель задачи.

2. Алгоритм и метод решения задачи.

3. Решение задачи маршрутизации методом потенциалов. Определение оптимального плана движения автомобилей без груза.

4. Определение маршрутов движения автомобилей методом совмещенных планов. Графическое представление маршрутов.

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

6. Сводные показатели составленного сменно-суточного плана: объем перевозок, количество автомобилей с грузом и без груза, коэффициент использования пробега.

 

Оформление курсовой работы (проекта)

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

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

Оформление должно соответствовать следующим требованиям.

Курсовая работа (проект) выполняется машинным способом, с применением печатающих устройств ЭВМ, на одной стороне листа белой бумаги формата А4 (210х297) через 1,5 интервала 14 шрифтом с соблюдением следующих размеров отступа от края листа: левое поле – 30 мм; правое поле – 15 мм; верхнее и нижнее поля – по 20 мм. Нумерация страниц – внизу посередине страницы; на титульном листе, на бланке задания и на листе с содержанием номера страниц не проставляются, но они входят в общую нумерацию страниц работы (проекта).

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

Главы основной части работы должны иметь порядковую нумерацию, например, 1., 2., 3. и т.д. Параграфы должны иметь порядковую нумерацию внутри каждой главы, например, 1.1., 1.2., 1.3., при более дробном делении 1.1.1., 1.1.2., 1.1.3. Если параграф имеет только один пункт, то выделять и нумеровать его не следует.

Каждый раздел курсовой работы (проекта) (введение, каждая глава, заключение) должен начинаться с новой страницы, параграфы (подразделы) располагаются друг за другом вплотную. Заголовки структурных элементов и разделов основной части следует располагать в середине строки без точки в конце и печатать с заглавной буквы строчными буквами, не подчеркивая. Если заголовки содержат несколько предложений, их разделяют точками. Переносы слов в заголовках не допускаются. Расстояние между заголовками структурных элементов и разделов основной части и текстом должно быть не менее 3-4 интервалов.

Сокращение слов в тексте и в подписи под иллюстрациями не допускается. Исключения составляют сокращения, установленные государственным стандартом (ГОСТ 2.216-68), а также общеизвестные сокращения, как например, РФ и др. Сокращение слов осуществляется по способу оставления только первой буквы, например: “год” – “г.”, “том” – “т.”, “рубль” – “р.”, “копейка” – “к.”, и т.п. Сокращать слова “тысяча”, “миллион” следует: “тыс.”, “млн.”. Не рекомендуется вводить собственные сокращения обозначений и терминов.

Ссылка на первоисточник. Цитаты выделяются кавычками и снабжаются ссылками на источники. При цитировании допустимо использовать современные орфографию и пунктуацию, опускать слова, обозначая пропуск многоточием, если мысль автора не искажается. Ссылка на литературный источник дается по номеру в списке литературы, например, [13. C.15]. Недословное приведение выдержки из какого-либо произведения не выделяется кавычками, но обязательно отмечается в конце фразы [12. С.5]. Нельзя пользоваться порядковыми номерами списка литературы проекта как словами для построения фраз, например: “ в 25 дается определение...”. Правильное построение предложения будет: “В учебнике [25] дается определение...”.

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

Иллюстрации (чертежи, рисунки, графики, схемы, диаграммы, фотоснимки) и таблицы следует располагать в работе непосредственно после текстов, в которых они упоминаются впервые, или на следующей странице. На все иллюстрации и таблицы должны быть ссылки в работе. Оформление чертежей, графиков, диаграмм, схем должно соответствовать требованиям государственных стандартов ЕСКД.

Иллюстрации должны иметь название, которое помещают под иллюстрацией. Наименования, приводимые в тексте и в иллюстрациях, должны быть одинаковыми. При необходимости под иллюстрацией помещают поясняющие данные (подрисуночный текст). Иллюстрация обозначается общим словом “Рисунок 1 – название рисунка».

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

Разрывать таблицу и переносить ее на другую страницу можно только в том случае, если она не умещается на одной странице. При переносе части таблицы на другой лист заголовок помещают только над первой частью. Слово “Таблица”, порядковый номер и заголовок указывают один раз над первой частью таблицы, над последующими частями пишут “Продолжение табл.__”.

Графу “№ п/п” в таблицу не включают. При необходимости нумерацию показателей параметров или других данных порядковые номера указывают в боковике таблицы перед их наименованием. Для облегчения ссылок в тексте допускается нумерация граф. Если цифровые данные в графах таблицы выражены в различных единицах физических величин, то их указывают в заголовке каждой графы. Если все параметры выражены в одной и той же единице физической величины, ее сокращенное обозначение помещают над таблицей.

Нумерация таблиц, рисунков (отдельно для таблиц и рисунков) должна быть сквозной для всей курсовой работы (проекта). Слово “таблица”, ее порядковый номер и название пишутся слева направо следующим образом:

Таблица 1 - Основные показатели деятельности предприятия.

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

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

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

Формулы следует располагать на середине строки, а связывающие их слова “где”, “следовательно”, “откуда”, “находим”, определяем” – в начале строк. Формулы в работе (проекте) следует нумеровать, особенно, если в тексте приходится на них ссылаться, порядковой нумерацией по всей работе (проекту) арабскими цифрами в круглых скобках в крайнем правом положении на строке, например: (21).

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

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

Интервалы величин в виде “от и до” записываются через черточку. Например, 8-12% или стр. 5-7 и т.д.

При величинах, имеющих два предела, единица измерения пишется только при цифровых или буквенных величинах, в тексте их следует писать только словами; “номер”, “процент”. Математические знаки “+”, “-”, “=“, “>“, “<“ и другие используются только в формулах. В тексте их следует писать словами: “плюс”, “минус”, “равно”, “меньше”, “больше”.

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

Источники располагаются в алфавитном порядке (по первой букве первого слова). В авторских источниках первым словом считается фамилия автора. Все источники в перечне нумеруются. Для каждого источника указываются: фамилия и инициалы автора (авторов); полное название книги, статьи; название журнала или сборника статей (для статей); название города Москва и Санкт-Петербург – сокращенно, соответственно М. и Спб., остальные полностью; название издательства (если имеется в выходных данных) – для книг год издания (для статей – номер журнала и год). Общее количество страниц в книге (например, 206 с.) или конкретные страницы (например, С. 15). Сведения об источниках приводятся в соответствии с требованиями ГОСТ 7.1.

Список литературы располагается после раздела “Заключение”.

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

Приложение располагается непосредственно за списком литературы. Каждое приложение должно начинаться с новой страницы и иметь содержательный заголовок, напечатанный строчными буквами. В правом верхнем углу над заголовком прописными буквами должно быть напечатано слово “ПРИЛОЖЕНИЕ”.

Если приложений в работе более одного, их следует нумеровать арабскими цифрами порядковой нумерацией. Имеющиеся в тексте приложения иллюстрации, таблицы, формулы и уравнения следует нумеровать в пределах каждого приложения с добавлением буквы "П", например: "Таблица 1П".

Нумерация страниц. Все страницы работы, включая список использованной литературы и приложения, нумеруются арабскими цифрами по порядку. Номер страницы проставляют внизу посередине страницы без точки в конце. Первой страницей считается титульный лист. На нем цифра “ 1 “ не ставится. За титульным листом помещается задание на курсовую работу (проект), затем страница с "Содержанием” на которых цифры "2", "3" также не проставляются. Нумерация начинается со страницы “Введение” на которой ставится цифра. Иллюстрации и таблицы, расположенные на отдельных листах, и распечатки ЭВМ включаются в общую нумерацию страниц проекта.

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

 

Задание на курсовую работу

Основные понятия моделирования транспортных систем

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

В задачах линейного программирования критерий оптимальности (т. е. показатель качества) линейно зависит от параметров задачи и формулируется в виде уравнений или неравенств первой степени. Таким образом, имеет место линейная зависимость, откуда происходит и название метода "линейное программирование".

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

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

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

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

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

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

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

На автомобильном транспорте методы линейного программирования применяются уже более 40 лет (с начала 1960-х годов) для решения следующих задач:

1. Сокращение дальности перевозок грузов по критерию минимальной суммы тонно-километров.

2. Составление оптимальной схемы перевозок грузов по критерию минимальных затрат времени.

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

4. Задачи перевозки разных (но взаимозаменяемых) продуктов - угля, нефти, мазута, цемента разных марок и т. д.

5. Сменно-суточное планирование перевозок помашинных отправок грузов.

6. Планирование перевозок мелкопартионных грузов.

7. Распределение автобусов по маршрутам и т. д.

Матрица условий

Количество тонн груза для доставки в пункт В_j, из всех пунктов отправления равно

где Х_ij - количество тонн груза предназначенного к отправке из А_i, в В_j, а так как потребность пункта В_j, составляет b_j тонн, то

Сказанное справедливо для любого пункта В_j, поэтому получаем систему п- уравнений:

С другой стороны общее количество груза, отправляемого из пункта А_i, во все пункты назначения В_j, составит

По условиям задачи эта сумма равна наличию груза в пункте А_i.

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

(2)

Более компактно уравнения (1) и (2) записываются в форме

Суммарная транспортная работа Р из условий, таким образом, равна

Таким образом, в математической форме транспортная задача требует определения значений переменных Х_ij, минимизирующих линейную формулу

При этом суммарное количество груза у отправителей должно быть равно количеству, требуемому получателю

Матрица условий

Рассмотрим решение задачи на конкретном примере.

Потребителям В₁, В₂, В₃ и В₄ требуется песок в количестве 30, 70, 40 и 30 тонн. На складах поставщиков А₁ А₂, и А₃ имеется соответственно 80, 50 и 40 тонн. Расстояния 1_ij между ними указаны в таблице-матрице, которую составляем.

В правых верхних углах записаны расстояния между поставщиками и потребителями. Каждая из клеток представляет собой реальные маршруты перевозок груза в процессе решения задачи. В средней части этих клеток будут записываться значения Х_ij>0, где Х_ij объём поставок, в крайних случаях в эти клетки могут записываться и не основные поставки Х_ij =0.

Значения Х_ij делятся на основные Х_ij >0 и не основные Х_ij <0. Основные Х_ij, записанные в матрице, обычно называют загрузками, а клетки, в которых они записаны, называются занятыми. Клетки матрицы без загрузок называют незанятыми. В матрице также предусмотрены вспомогательные столбцы U и столбцы V.

Для удобства подсчётов тонны заявленного груза переводят в ездки (для существа задачи это безразлично).

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

- полное обеспечение всех потребностей;

- полный вывоз всего груза;

- неотрицательность любой поставки.

Если все эти требования не выполняются, то задача не решается.

1. Сначала планируем перевозки с первого склада (А₁) ближайшим потребителям.

2. Затем со второго склада (А₂) ближайшим потребителям и т. д. заполняем таблицу.

Проводится это способом минимального элемента по строке следующим образом вначале планируем перевозки грузов с первого склада, записывая их в клетки с ближайшим расстоянием к потребителю. Клетке А₁ В₃, которая находится на расстоянии 5 км от склада А₁ требуется 40 тонн, а на складе 80 тонн. Запрос удовлетворяется полностью на складе остаётся ещё 40 тонн, которые направляем к следующему ближайшему потребителю. Им оказывается потребитель В₄, которому требуется 30 тонн груза. Полностью удовлетворяем запрос и этого потребителя, а на складе А₁ остаётся 10 тонн, которые направляем к следующему ближайшему (последнему) потребителю В₁ которому требуется 30 тонн груза, таким образом весь груз со склада А₁ вывезен полностью.

Переходим к перераспределению груза со склада А₂. В первую очередь, удовлетворяем ближайшего, ещё не удовлетворённого потребителя. Им является потребитель В₁ (4 км), которому требуется 30 тонн груза (10 тонн было завезено со склада А₁), поэтому со склада А₂ мы можем поставить 20 тонн груза, полностью удовлетворив потребителя В₁.

На складе А₂ осталось 30 тонн груза, следующий ближайший потребитель является В₂, которому требуется 70 тонн груза. Оставшиеся 30 тонн получает потребитель В₂. Со склада А₃ направляем оставшиеся 40 тонн потребителю В₂. Таким образом, потребности всех потребителей полностью удовлетворены, а со всех складов полностью вывезены все запасы груза.

На этом этапе вычисления закончены.

3. Вычисляется транспортная работа, которая будет равна

Р=10-9+40-5+30-8+204+30-9+4022=1760тонно-км.

В таблице 3 представлен исходный допустимый план перевозок.

Таблица 3

Исходный допустимый план перевозок

Проверяем заполненность матрицы, т. е. число заполненных клеток по критерию m+n-1. Если число клеток отличается от числа по критерию и матрица является вырожденной, по ней проводить дальнейшие расчёты невозможно.

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

Если клетки лишние, то их число уменьшаем методом, описанным ниже.

Проверка разработанного плана на оптимальность состоит из двух этапов: на первом этапе вычисляются вспомогательные индексы - U_i и V_j, а на втором этапе исследуются незанятые клетки на потенциальность с целью определения суммы индексов . Рассчитываем на матрице специальные индексы U и V и заносим их в строку и столбец матрицы. Для определения индексов используются следующие правила:

вспомогательный индекс U₁ всегда равен нулю,

- для каждой занятой клетки матрицы сумма, соответствующей ей индексов U и V, равна расстоянию в данной клетке, т. е.

U_i + V_j = L_ij, где L_ij - расстояние в клетке.

Это даёт возможность при известном одном индексе определить значение другого.

(5)

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

L_ij ≥ U_i + V_j,

т. е. расстояния должны быть больше или равны сумме индексов.

Запишем в матрицу (табл. 3) U_j = 0, тогда в соответствии с формулами:

Далее

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

Эта проверка заключается в сравнении расстояния каждой незанятой клетки матрицы с суммой соответствующих ей индексов с целью выявления U_i + V_j>L_ij.

 

Проверка показывает, что у незанятых клеток A₃Bi и А₃В₃ расстояние меньше суммы индексов, следовательно, составленный допустимый исходный план не является оптимальным и подлежит улучшению. Выявленные клетки являются резервом улучшения плана, и поэтому их называют потенциальными, почему и рассматриваемый метод называют "методом потенциалов".

Полученные потенциалы обозначим в матрице цифрой в квадратике (цифра - превышение индекса над расстоянием).

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