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

Министерство образования  и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

ИМЕНИ Н. Г. ЧЕРНЫШЕВСКОГО»

Колледж радиоэлектроники имени П. Н. Яблочкова

 

 

 

 

МАТЕМАТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ 

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

О ПОЛУЧЕНИИ ОПТИМАЛЬНОГО ПЛАНА 

прописными  буквами

ПЕРЕВОЗОК (ТРАНСПОРТНОЙ ЗАДАЧИ) 

 

 

 

курсоваЯ РАБОТА

 

Специальность    230105 «Программное обеспечение вычислительной 

техники и автоматизированных систем» 

шифр, полное наименование

 

Студента        курса группы       .

                                                                                     

 

 

фамилия, имя, отчество

 

 

Руководитель,

     преподаватель               _________________              .

                                                                           подпись, дата                                            инициалы, фамилия

 

Председатель

предметной

     (цикловой) комиссии    __________________              .

                                                                            подпись, дата                                           инициалы, фамилия

 

 

 

 

Саратов   2012  .

                                                                                                       год 

Министерство образования  и науки Российской Федерации

ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ

ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ 
ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САРАТОВСКИЙ ГОСУДАРСТВЕННЫЙ  УНИВЕРСИТЕТ

ИМЕНИ Н. Г. ЧЕРНЫШЕВСКОГО»

Колледж радиоэлектроники имени П. Н. Яблочкова

 

 

 

 

                                     ПРИНЯТО

                                                                              на  заседании цикловой

                              (предметной) комиссии

                                                                Протокол от _____ №____

 

 

 

ЗАДАНИЕ

на курсовую работу

 

Специальность        230105    «Программное обеспечение вычислительной .

техники и автоматизированных систем» 

шифр, полное наименование

Тема            МАТЕМАТИЧЕСКИЕ МЕТОДЫ РЕШЕНИЯ ЗАДАЧИ 

полное наименование темы, прописными буквами

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

(ТРАНСПОРТНОЙ ЗАДАЧИ) 

 

студента      курса группы          .

 

   

фамилия, имя, отчество

 

 

 

 

 

 

 

                                                                  Саратов    2012   .

        год 

СОДЕРЖАНИЕ

ВВЕДЕНИЕ   3

1 ТРАНСПОРТНАЯ ЗАДАЧА КАК ЧАСТНЫЙ СЛУЧАЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ   5

1.1 Постановка транспортной задачи   5

1.2 Метод северо-западного угла нахождения опорного решения   8

1.3 Метод потенциалов нахождения оптимального решения   8

2 РЕШЕНИЕ ЗАДАЧИ О ПОЛУЧЕНИИ ПЛАНА ГРУЗОПЕРЕВОЗОК 11

2.1 Математическая  модель задачи 11

2.2 Получение опорного плана грузоперевозок 14

2.3 Получение оптимального плана грузоперевозок 15

3 РЕШЕНИЕ ЗАДАЧИ С ПОМОЩЬЮ НАДСТРОЙКИ EXCEL «ПОИСК РЕШЕНИЯ» 24

3.1 Табличное  представление модели 24

3.2 Настройка  модели 26

3.3 Решение  задачи 28

3.4 Анализ  решения 28

ЗАКЛЮЧЕНИЕ 30

СПИСОК ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ 31

 

 

 

 

 

Срок выполнения курсовой работы              ________________

                                                                                                                                            число, месяц, год

 

Руководитель,

преподаватель            ________________           .

           подпись, дата                                инициалы, фамилия

 

Председатель

предметной

(цикловой) комиссии  ________________           .

          подпись, дата                                 инициалы, фамилия

 

 

 

ВВЕДЕНИЕ

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

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

Внедрение математических методов оптимального планирования перевозок грузов на автомобильном транспорте начато в середине XX века. Большая заслуга в разработке и внедрении математических методов на транспорте принадлежит отечественному ученому Л.В.Кантаровичу и его последователям.

Целями настоящей курсовой работы являются:

- систематизация и закрепление  полученных теоретических знаний  и практических умений по дисциплине «Математические методы»;

- углубление теоретических знаний по теме «Транспортная задача»;

- формирование умений  использовать справочную литературу;

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

- подготовка к итоговой  государственной аттестации.

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

 

1 ТРАНСПОРТНАЯ ЗАДАЧА КАК ЧАСТНЫЙ СЛУЧАЙ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ

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

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

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

Нужно составить  такой план перевозок от поставщиков  к потребителям, при котором:

1. суммарные затраты на перевозку груза будут минимальны;
2. по возможности будут задействованы все мощности поставщиков;
3. по возможности будет удовлетворен весь спрос потребителей.

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

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

Обозначим общее количество имеющегося в наличии  груза

,

а потребности в грузе – 

.

В зависимости  от значений a и b различают два типа транспортных задач:

Если a = b, имеем закрытую модель, или модель, удовлетворяющую условию баланса. В этой модели суммарный объем груза у поставщиков (суммарная мощность поставщиков) равен суммарному спросу потребителей.

Если – открытую модель или модель с нарушенным балансом. Здесь различают два случая.

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

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

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

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

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

Пункты отправления	Пункты назначения				Запасы
Потребности					a = b

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

 

и удовлетворяют системе ограничений:

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

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

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

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

 

1.2 Метод северо-западного угла нахождения опорного решения

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

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

1.3 Метод потенциалов нахождения оптимального решения

Метод потенциалов является модификацией симплекс - метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого опорного решения, получить оптимальное решение за конечное число итераций.

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

 – базисные переменные (заполненные клетки);

  – свободные переменные (незаполненные клетки).

 

 

Функция стоимости перевозок выражается через свободные переменные следующим  образом:

                                                 (*)

здесь – номер итерации

Для нахождения коэффициентов  каждому пункту отправления ставится величина , – потенциал пункта .

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

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

Далее для  каждой свободной клетки находим  относительные оценки

 

Если  все величины будут неотрицательными, то исходное решение является оптимальным.

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