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

СОДЕРЖАНИЕ 

ВВЕДЕНИЕ ……………………………………………………………………...2

1. ОБЩАЯ ЧАСТЬ………………………………………………………………5

1.1. Математическая постановка задачи……………………………….5

1.2.  Арифметическое преобразование…………………………………7

1.3. Модели…………………………………………………………………......8

       1.3.1. Открытая модель…………………………………………………8

       1.3.2. Закрытая модель…………………………………………………8

1.4. Составление опорного  плана транспортной  задачи. Методы составления  опорного плана………………………………………………9

      1.4.1. Метод северо-западного угла…………………………………..9

     1.4.2. Метод наименьшей стоимости…………………………………11

1.5. Методы решения транспортной задачи……………………………13

      1.5.1  Метод потенциалов……………………………………………….13

          1.5.1.1  Пример решения методом потенциалов………………14

      1.5.2  Метод прямоугольников……………………………………….16

          1.5.2.1  Пример решения методом прямоугольников.………..18

2. Описание решения  Транспортной задачи  с использованием                стандартных программных средств……………………………………20

3. Описание входной  информации…………………………………......24

4. Описание выходной информации………………………………......24

5. Описание программных средств решения задачи………………25

6. Инструкция для пользователя……………………………………......26

7. Инструкция для программиста……………………………………......27

ЗАКЛЮЧЕНИЕ…………………………………………………………………28

СПИСОК  ИСПОЛЬЗОВАННЫХ ИСТОЧНИКОВ……………………......29

ПРИЛОЖЕНИЕ  А………………………………………………………………30

 

      ВВЕДЕНИЕ

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

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

     Хорошо  сказал об этом Галилей:

     «Философия (на нашем языке- физика) написана в  величайшей книге, которая постоянно  открыта вашему взору, но понять ее может лишь тот, кто сначала научится понимать ее язык и толковать знаки, которыми она написана. Написана же она на языке математики».

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

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

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

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

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

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

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

     Один  из классов математических моделей- задачи линейного программирования. Одной из задач линейного программирования является транспортная задача- задача составления оптимального плана перевозок, позволяющего минимизировать суммарный километраж. Транспортная задача, как и задача линейного программирования была впервые поставлена советским экономистом А.Н.Толстым в 1930 году. Разработка общих методов решения задачи линейного программирования и их математическое исследование связано с именем советского ученого Л.В.Канторовича. В 1939 году методам решения задачи линейного программирования посвящено также большое число работ зарубежных ученых. Основной метод решения задачи линейного программирования –симплекс метод- был опубликован в 1949 году Дандигом. Симплекс метод дает решение любой задачи линейного программирования, но если переменных очень много, то решение весьма затруднительно и для более сложных задач симплекс метод стали модифицировать.

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

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

1. ОСНОВНАЯ ЧАСТЬ

 

     1.1  МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ 

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

     Транспортная  задача – это задача линейного  программирования, которая ставится как задача отыскания оптимального плана  перевозки грузов из М пунктов отправления в  N пунктов назначения. При этом тарифы перевозки грузов из i - пункта отправления в j – пункт назначения поставлены и известны.

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

Таблица 1

 

А1, А2 … и.т.д. – количество грузов вывозимых из пункта отправления.

В1,В2… и.т.д. – количество принимаемых в пунктах назначения.

С(I,j) – это стоимость перевозки грузов из i - пункта отправления в j – пункт назначения.

В задаче требуется  отыскать значение

такие, что  Целевая  функция S будет равна:

S=C1,1X1,1+C1,2X1,2+……+ Cn,mXn,m   будет минимальной

 
 

⁴Теорема.

Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение. 
 
 
 

1.2 Арифметическое преобразование 

Если ко всем элементам таблицы тарифов Транспортной задачи находящихся в  k-ом столбце прибавить такое число h, а ко всем элементам i-ой строки прибавить число l, то говорят что проведено арифметическое  преобразование таблицы тарифов по k-му столбцу на число h и по i-ой строке на число l . 

теорема

        Если таблица  транспортной задачи получена  из другой таблицы путем арифметического  преобразования  k-того столбца на  число h, и i-ой строки на число l, то решение первой таблицы будет решением и второй таблицы, а целевая функция второй таблицы( ) будет равна:

                                               

                                                 k=2; h=5;

      i=1; l=2; 

 

             
 

     Следствие из теоремы об арифметическом преобразовании таблицы  тарифов:

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

     Теорема о достаточном  условии оптимальности  транспортной таблицы:

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

     Чтобы решение транспортной задачи было оптимальным  достаточно, чтобы существовало ноль преобразование таблицы тарифов этой задачи. 

1.3 Модели:

1.3.1 Закрытая модель:

 Обозначим количество груза, имеющегося на каждой из баз (запасы), соответственно ,а общее количество имеющегося в наличии груза– :     ;

заказы  каждого из потребителей (потребности) обозначим соответственно , а общее количество потребностей :

, Тогда при условии мы имеем закрытую модель.  
 

1.3.2Открытая модель:  

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

1)суммарные  запасы превышают суммарные потребности  ;

2)суммарные  потребности превышают суммарные  запасы  .