Постановка транспортной задачи и её решение. 2

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

Институт экономики и антикризисного управления

 

 

 

 

 

 

 

Дисциплина «Логистика»

 

 

 

 

 

Реферат на тему:

 

«Постановка транспортной задачи и её решение.»

 

 

 

 

 

 

 

 

Выполнил:

Студент 3 курса

Группа ЭЗм-31

Шкатула К.Н.

 

Проверил(а):

 

 

 

 

 

 

 

 

 

 

Москва, 2013

Содержание

 

Введение……………………………………………………………………….....3

1. Построение моделей транспортной задачи…………………………………...4

2. Решение транспортной задачи………………………………………………...7

Заключение……………………………………….…………………………….14

Список используемой литературы……………………………………………...15

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение.

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

Транспортная задача (классическая) — задача об оптимальном плане перевозок однородного продукта из однородных пунктов наличия в однородные пункты потребления на однородных транспортных средствах (предопределённом количестве) со статичными данными и линеарном подходе (это основные условия задачи).

Проблема была впервые формализована французским математиком Гаспаром Монжем в 1781[1]. Основное продвижение было сделано на полях во время Великой Отечественной войны советским математиком и экономистом Леонидом Канторовичем[2]. Поэтому иногда эта проблема называется Транспортной задачей Монжа-Канторовича.

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

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

Целью моей работы является постановка транспортной задачи и ее решение. Для достижение поставленной цели мне необходимо решить ряд задач: 1) Дать определение транспортной задачи; 2) Определить постановку транспортной задачи; 3) Найти решение поставленной мною транспортной задачи.

 

 

 

 

1. Построение моделей транспортной задачи

 

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

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

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

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

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

Особенности экономико-математической модели транспортной задачи:

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

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

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

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

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

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

1) n– количество пунктов отправления, m – количество пунктов назначения.

2) ai– запас продукции в пункте отправления Ai (i=1, n) [ед. прод.].

3) bj– спрос на продукцию в пункте назначения Bj (j=1,m) [ед. прод.].

4) cij– тариф (стоимость) перевозки единицы продукции из пункта отправления ai в пункт назначения bj [руб./ед. прод.].

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

1) xij– количество продукции, перевозимой из пункта отправления ai в пункт назначения bj [ед. прод.].

2) L(x)– транспортные расходы на перевозку всей продукции [руб.].

Этапы построения модели

I. Определение переменных.

II. Проверка сбалансированности  задачи.

III. Построение сбалансированной  транспортной матрицы.

IV Задание целевой функции.

V Задание ограничений.

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

 

Таблица 4.1Общий вид транспортной матрицы

Пункты отправления, A1	Пункты потребления, Bj				Запасы, ед. прод.
	B1	B2	…	Bm
A1	c11, [руб./ед. прод.]	c12	…	c1m	a1
A2	c21	c22	…	C2m	a2
…	…	…	…	…	…
An	Cn1	Cn2	…	Cnm	an
Потребность ед. прод.	b1	b2	…	bm

 

 

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

 

.

(

 

 

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

 

.

 

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

 

.

 

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

 Задача о  назначениях – частный случай ТЗ. В задаче о назначениях количество пунктов отправления равно количеству пунктов назначения. Объемы потребности и предложения в каждом из пунктов назначения и отправления равны 1. Примером типичной задачи о назначениях является распределение работников по различным видам работ, минимизирующее суммарное время выполнения работ.

 Переменные задачи о назначениях определяются следующим образом

 

 

 

2. Решение транспортной задачи.

 

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

Имеются следующие исходные данные.

Наличие минеральных удобрений на складах.

 

Склады	Наличие удобрений, т.
Склад №1	200
Склад №2	190
Склад №3	220
Склад №4	145
Склад №5	280

 

 

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

 

Пункты	Потребность в удобрениях, т.
1 пункт	200
2 пункт	150
3 пункт	220
4 пункт	330

 

 

Расстояния между складами и пунктами доставки.

 

	Пункт 1	Пункт 2	Пункт 3	Пункт 4
Склад №1	6	4	5	11
Склад №2	12	6	4	9
Склад №3	15	7	10	4
Склад №4	9	5	12	5
Склад №5	3	7	12	11

 

    

            На пересечении столбца конкретного пункта доставки со строкой склада находится информация о расстояниях между этими пунктом доставки и складом. Например, расстояние между 3 пунктом и складом №3 равно 10 километрам.

Для решения задачи подготовим необходимые таблицы. (рис. 1)

 

Рисунок 1. Изменяемые ячейки

 

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

Например, значение ячейки B4=СУММ(C4:F4)

Значения ячеек по 9 строке по столбцам от С до F определяются суммированием данных ячеек соответствующих столбцов с 4 по 8 строки.

Например, значение ячейки С9=СУММ(C4:C8)

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

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

   

Рисунок 2 Исходная информация

 

В строке 16 по столбцам C-F определим грузооборот по каждому пункту доставки. К примеру для 1 пункта (ячейка С16) это рассчитывается с помощью формулы

 

С16=С4*С11+С5*С12+С6*С13+С7*С14+С8*С15

 

либо можно использовать функцию СУММПРОИЗВ

 

С16=СУММПРОИЗВ(C4:C8;C11:C15)

 

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

В ячейке В16 по формуле =СУММ(С16:F16) будет вычисляться общий объем грузооборота минеральных удобрений.

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

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

 

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

После выбора данной команды появится диалоговое окно (рис. 4).

 

Рисунок 4. Диалоговое окно Поиск решения

    

       Поскольку в качестве критерия оптимизации нами выбрана минимизация грузооборота, в поле Установить целевую ячейку введём ссылку на ячейку, содержащую формулу расчета общего объема грузооборота минеральных удобрений. В нашем случае это ячейка $B$16. Чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек (влияющими, в данном случае это и изменяемые ячейки, являются ячейки, которые предназначены для хранения значений искомых неизвестных), переключатель установите в положение минимальному значению;

В поле Изменяя ячейки введём ссылки на изменяемые ячейки, разделяя их запятыми; либо, если ячейки находятся рядом, указывая первую и последнюю ячейку, разделяя их двоеточием ($С$4:$F$8). Это означает, что для достижения минимального грузооборота перевозок будут меняться значения в ячейках с С4 по F8, то есть будут изменяться количество груза, перевезенного по конкретному маршруту.

Необходимо наложить некоторые ограничения для поиска решения.

В группе полей Ограничения нажмите кнопку Добавить. Появится диалог Добавление ограничения (рис. 5)

 

Рисунок 5. Диалоговое окно Добавление ограничения

 

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

 

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

 

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

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

Первое условие $B$4:$B$8 <=$B$11:$B$12. Оно означает, что значение в ячейке В4 должно быть меньше или равно значению в В11, в В5 меньше или равно, чем в В12, и так далее до В8 и В15.

В ячейках с В4 по В8 на листе находятся объемы поставок с конкретных складов. В ячейках с В11 по В15 - запасы на этих же складах. Так как невозможно вывести со склада больше, чем на нем есть, первое значение должно быть не больше второго.

Второе условие $С$4:$F$8>=0. Оно означает, что объем перевозок не может быть отрицательным, то есть, если на складе не хватает минеральных удобрений, их не везут с пункта доставки, на который эти минеральные удобрения были завезены ранее. Грузопоток имеет только одно направление - от складов к пунктам доставки удобрений.

И. наконец, третье, и последнее условие $С$9:$F$9>=$C$10:$F$10. Оно означает, что значения в ячейках девятой строки должны быть больше или равны значениям в ячейках десятой строки,, то есть запросы пунктов доставки минеральных удобрений должны быть выполнены полностью. Перевыполнение объема поставок допустимо, а недовыполнение - нет.

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

После нахождения решения появляется диалог Результаты поиска решения (рис. 7)

 

Рис. 7. Диалоговое окно Результаты поиска решения

 

Нажав кнопку ОК, занесём вариант решения на рабочий лист (рис. 7).

Рис. 7. Решенная транспортная задача

 

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

 

 

 

 

Заключение.

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

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

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

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

 

Список использованных источников

 

1. Гаджинский А.М. Логистика. М.: Маркетинг, 2006. – 228 с.

2. Дроздов П.А. Основы логистики. Мн.: Изд. Гревцова, 2008. – 208 с.

3. Ермаков Е.И. Общий курс высшей математики для экономистов. М.: Инфра-М, 2000.

4. Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование, Минск: Вышейшая школа, 2001г.

5. Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании, Издательство “Дело”, Москва 2001г.

6. Канке А.А. Кошевая И.П. Логистика. М.: ИНФРА-М, 2007. – 384 с.

7. Сергеев В. И. Логистика в бизнесе: Учебник. М.: ИНФРА-М, 2001.

Размещено на Allbest.ru