Сущность и использование транспортных задач

Размещено на http://www.allbest.ru/

Министерство образования республики Беларусь

Учреждение образования

«Брестский государственный университет имени А. С. Пушкина»

Физико-математический факультет

Кафедра кафедра алгебры, геометрии и математического моделирования

Курсовая работа

Сущность и использование транспортных задач

Берлягова Анна Борисовна,

студент 4 курса специальности «Бизнес - администрирование»

Волк Татьяна - преподаватель кафедры алгебры

Брест 2014

Содержание

Введение

1. Сущность транспортных задач

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

1.2 Методы решения транспортных задач

2. Использование транспортных задач

2.1 Области применения транспортной задачи

2.2 Использование транспортной задачи для повышения эффективности работы предприятия

3. Решение транспортных задачу с помощью MS Excel

Заключение

Источники



Введение

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

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

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

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

Использование для решение транспортных задачу с MS Excel. Описание работы в MS Excel.

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

Определение понятия и рассмотрение видов решения. Для определения более удобного способа решения и нахождения оптимального результата.

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



1. Сущность транспортных задач

excel математический транспортный

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

Начнем с её содержательной формулировки.

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

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

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

Тогда общие транспортные расходы составят величину .

Из каждого склада весь продукт должен быть вывезен. Это значит, что должно быть выполнено условие .

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

Желание минимизировать транспортные расходы приводит нас к следующей задаче:



являющейся типичной задачей линейного программирования.

Определение 3.1. Транспортная задача называется открытой транспортной задачей, если условие баланса нарушаются; в случае выполнения условия баланса она называется сбалансированной транспортной задачей.

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

Сам же симплекс-метод был бы не эффективен по двум причинам:

1. Большая размерность решаемой задачи. Общее число неизвестных величин равно mn , и даже при n =m = 10 размерность решаемой задачи уже будет равна 100. Даже ЭВМ будет решать такую задачу симплекс-методом достаточно долго.

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

Приведение открытой транспортной задачи к сбалансированной

1. Превышение запасов над потребностями.

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

2. Превышение потребностей над запасами.

Вводим “фиктивного” производителя (склад) с потребностями равными абсолютной величине разности между общим количеством запасов и общим количеством требуемых единиц. Стоимость по доставке будет для производителя равна 0, т.к. поставки фактически нет.[1]

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

Теорема 1. Для любой транспортной задачи существует план (то есть для любой транспортной задачи допустимая область не пуста).

Доказательство

Действительно, по смыслу задачи

Так как

. то возьмем план в виде

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

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

Доказательство

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

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

Теорема 3. Любой опорный план имеет не более положительных компонент.

Доказательство

Действительно, исходная система содержит всего ограничений типа равенств:



,

то есть m ограничений;

то есть n ограничений.

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

а из второй группы сложим первые n- 1 ограничение

.

Вычитая теперь (2) из (1), получим:

,

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

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



1.2 Методы решения транспортных задач

Для начала решения транспортной задачи необходимо иметь какой-то исходный опорный план, то есть оказаться в какой-то вершине допустимой области. Приведем конструктивный прием построения такого опорного плана, получивший название "метод северо-западного угла". Итак, пусть имеется m складов с запасами и n пунктов потребления с потребностями . Пусть запасы и потребности сбалансированы, то есть. Представим это

			...

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

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



	0	0	...	0	0
			...

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

,

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

1. Ну, а в первом складе еще останется запасов продукта. Наша таблица примет вид:

0
0
0
0			...

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

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

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

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

Рассмотрим два примера. С целью экономии места, вся таблица не переписывается, а лишь приписываются последние строки и столбцы.

Пример 1

Пусть

3	3	0	0	6	3	0	0	0	0	0
0	4	4	0	8	8	8	4	0	0	0
0	0	3	6	9	9	9	9	9	6	0
3	7	7	6	В данном случае число
0	7	7	6	складов m =3, число пунктов
0	4	7	6	потребления n =4, так что
0	0	7	6	m+n-1=6. Получившийся
0	0	3	6	опорный план содержит ровно
0	0	0	6	6 компонент, и поэтому являет-
0	0	0	0	ся невырожденным.



Пример 2

Пусть Аналогичная процедура приводит к таблице, изображенной ниже.

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

3	3	0	0	6	3	0	0	0	0
0	4	0	0	4	4	4	0	0	0
0	0	7	6	13	13	13	13	6	0
3	7	7	6	В данном случае число скла-
0	7	7	6	дов m =3, число пунктов потре-
0	4	7	6	бления n =4, так что m+n-1=6.
0	0	7	6	Получившийся опорный план
0	0	0	6	содержит 5 компонент, и поэтому
0	0	0	0	является вырожденным.

произошло потому, что запасы складов и полностью удовлетворили потребности пунктов потребления и и поэтому в тот момент, когда эти сбалансированные потребности удовлетворились (a1+a2=10=b1+b2), обнулились сразу и строка, и столбец.[2]

Метод минимального (максимального) элемента

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

Пример № 2

Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:

2	3	4	15
11	6	10	1
8	9	3	3
4	1	2	21
10	20	10

Решение:

Задача сбалансирована.

Строим первоначальный опорный план методом минимального элемента.

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

2. Вторая и третья перевозки будут осуществляться с пункта производства и в пункт потребления и соответственно и составят максимально возможное число единиц продукта : , ;

3. Четвертая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца и четвертой строки).

4. Пятая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца, третьей и четвертой строки). .

5. Шестая перевозка осуществляется с пункта в пункт потребления т.к. (без учета первого, второго столбца, первой, третьей и четвертой строки).

Опорный план имеет вид;

10	5	0
0	1	0
0	3	0
0	11	10

Метод Фогеля

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

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

Пример

Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи:

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



10	20	10
2 7	3 0	4 8	15	1	1	1
11 0	6 1	10 0	1	4	4	-
8 3	9 0	3 0	3	5	-	-
4 0	1 19	2 2	21	1	1	-
2	2	1
2	2	2
2	2	2
2	-	2
-	-	2
-	-	-

Опорный план имеет вид:

7	0	8
0	1	0
3	0	0
0	19	2

Метод двойного предпочтения то план не оптимален.

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

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

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

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

Затем распределяют перевозки по клеткам с единичной отметкой.

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

Пример

10	20	10
2**	3	4	15
11	6*	10	1
8	9	3*	3
4	1*	2*	21

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

10	20	10
10			15
0			1
0			3
0			21

Заполняем клетки с простым предпочтением, начиная с наименьшей стоимости.

10	20	10
10	0		15
0	0		1
0	0	3	3
0	20	1	21

Заполняем оставшиеся пустыми клетки.

10	20	10
10	0	5	15
0	0	1	1
0	0	3	3
0	20	1	21



Это опорный план составленный методом двойного предпочтения.[5].

Потенциалы. Критерий оптимальности плана

Итак, наша транспортная задача имеет вид:

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

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

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

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



Это и позволяет проверить оптимальность любого опорного плана.

Сам алгоритм выглядит следующим образом:

1. Один из потенциалов задается произвольно, скажем, полагается .

2. Рассматривается система линейных уравнений вида для тех наборов индексов i , j , для которых , и находятся потенциалы и всех складов и всех пунктов потребления.

3. Для всех остальных наборов индексов i , j (для которых ) проверяется условие .

Если это условие выполняется для всех наборов индексов i , j, для которых , то рассматриваемый план является оптимальным. Если же, хотя бы для одной пары , то план не оптимален.

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

1. Одна из величин или задается произвольно, например, полагается .

2. Затем рассматриваются уравнения вида для тех j , для которых . Так как известно, то находятся для некоторого множества

индексов .

3. Для этих индексов рассматриваются уравнения вида:



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

4. Далее повторяются пункты 2 (движение по строкам) и 3 (движение по столбцам), пока не определятся все потенциалы.

Проиллюстрируем этот процесс примером, а заодно покажем форму записи результатов при ручном счете.

Пример

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

Таблица стоимостей перевозок

	Пункты потребления
Склады	3	5	4	5
	1	2	4	3
	1	5	6	3

Построим исходный опорный план методом северо-западного угла. Он имеет вид

2	3.1	0	0
0	3.9	4.2	0
0	0	2.8	6.3

План имеет 6=3+4-1 компонент, поэтому он является невырожденным. Заметим, что для него транспортные расходы равны .

Заготовим матрицу размером (в нашем случае размером 3ґ 4), в которую впишем те коэффициенты , которые соответствуют ненулевым перевозкам нашего плана (смотрите следующую страницу).

Далее действуем следующим образом. Полагаем.



	3	5
		2	4
			6	3

1. Идем по строке.

, следовательно ;

, следовательно .

, следовательно .

2. Идем по строке.

, следовательно 5. Идем по столбцу.

, следовательно .

6. Идем по строке.

, следовательно .

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

3

5

7

4

0

3

5

7

4

-3

0

2

4

1

2

4

6

3

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

Сравнивая с матрицей величин мы видим, что условие оптимальности плана нарушено в двух местах - для и . Следовательно, построенный нами план перевозок не является оптимальным.[6]

Дельта-метод

Рассмотрим алгоритм дельта-метода в общем виде:

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

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

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

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

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

б) минимальное приращение больше приращений нулевой строки;

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

В случае б) составляются цепочки.

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

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

5. Исключаем из рассмотрения отмеченные столбцы. Если занятая клетка избыточной строка стала незанятой или избыточной , то начинаем п.4. В противном случае продолжаем процесс до тех пор, пока все строки не превратятся в нулевые.[7]



2. Использование транспортных задач

2.1 Области применения транспортной задачи

Применение транспортных задач для решения экономических задач.

Задача о размещении производства с учетом транспортных затрат.

Имеется (проектируется) m пунктов производства с объемами производства и n пунктов потребления с объемами потребления . Затраты на производство единицы продукции в каждом i-м пункте производства известны и равны , i=1,2,…,m. Стоимости перевозки единицы груза от каждого i-го производителя каждому j-му потребителю известны и равны , i=1,2,,…,m, j=1,2,…,n. Суммарные объемы производства превосходят суммарные объемы потребления. Требуется составить план сокращения (размещения) производства, обеспечивающий минимальные производственно-транспортные затраты.

Задача решается как транспортная задача, матрица стоимостей которой составляется как сумма матриц:

С=()=(+), i=1,2,,…,m, j=1,2,…,n.

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

Задача о назначениях, или проблема выбора.

Имеется m групп людей (станков) численностью , которые должны выполнять n видов работ (операций) объемом . Известна производительность каждой i-й группы людей (станков) при выполнении каждого j-го вида работ (операций) ,Размещено на http://www.allbest.ru/

i=1,2,,…,m, j=1,2,…,n. . Требуется так распределить людей (станки) для выполнения работ (операций), чтобы суммарный объем производства работ (операций) был максимальным.

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

,

, i=1,2,…,m ,

, j=1, 2, … , n,

, i=1,2,,…,m, j=1,2,…,n.

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

Можно также изменить критерий оптимальности. Например, вместо (i,j) использовать новый критерий оптимальности (i,j). [8].

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

Выделяют два типа транспортных задач: по критерию стоимости - план перевозок является оптимальным, если достигается минимум затрат на его реализацию; по критерию времени - план перевозок оптимален, если на него затрачивается минимальное количество времени. [9] Это ведет к более быстрой доставке товаров, сокращению затрат производства на топливо, ремонт машин, т.е. к сокращению транспортных издержек.

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

2.2 Использование транспортной задачи для повышения эффективности работы предприятия

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

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

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

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

аi - производственные мощности предприятий по производству запасных частей по пунктам размещения i;

bj - потребности в запасных частях в пунктах j;

xij - количество перевозок запасных частей между пунктами производства и пунктами потребления i, j;

Зi- затраты на производство единицы (удельные затраты) запасных частей у предприятий по пунктам i;

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

аi' - загрузка производственных мощностей предприятий по производству запасных частей по пунктам размещения i.

Тогда экономико-математическая модель может быть сформулирована следующим образом: найти совокупность переменных аi', минимизирующих целевую функцию F:

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

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

а1 = 500 т; а2 = 400 т; а3 = 700 т;

З1= 45 тыс. руб.; З2 = 49 тыс. руб.; З3 = 40 тыс. руб.

Потребности в пунктах потребления:

b1 = 350 т; b2 = 320 т; b3 = 190 т; b4 = 270 т; b5 = 230 т.

Затраты на транспортировку одной тонны запасных частей между пунктами производства и потребления представлены в матрице:

Номера пунктов Производства i	Номера пунктов потребления j
	B1	B2	B3	B4	B5
A1	3	5	4	7	6
A2	10	8	11	9	13
A3	8	5	6	7	4

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

Матрица, отражающая особенности решаемой задачи, принимает следующий вид:



Пункты Производства и их мощности	Потребители и их спрос
	В1	В2	В3	В4	В5	ФВ
	350	320	190	270	230	240
А1	500	48	50	49	52	51	0
А2	400	59	57	60	58	62	0
А3	700	48	45	46	47	44	0

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

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

Пункты Производства и их мощности	Потребители и их спрос
	В1	В2	В3	В4	В5	ФВ
	350	320	190	270	230	240
А1	500	35048	50	15049	52	51	0
А2	400	59	57	60	16058	62	2400
А3	700	48	32045	4046	11047	23044	0

Анализ результатов решения показывает следующее. Предприятие А1 отправляет реальным потребителям В1 и В2 соответственно по 350 и 150 т запасных частей, что в сумме составляет 500 т. Иначе говоря, мощности предприятия А1 полностью вошли в оптимальный план. Следовательно, загрузка мощностей этого предприятия равна также 500 т, т. е. 100 %. То же самое имеет место для предприятия А3. Предприятие А2 реальному потребителю В4 отправляет 160 т продукции. Оставшиеся мощности 240 т, как видно из таблицы, приходятся на фиктивного потребителя. Это говорит о том, что мощности А2востребованы не полностью. Следовательно, загрузка А2 составляет 160 т, т. е. 40 %. Предприятия, которые не полностью используют производственную мощность, необходимо переориентировать на выпуск нового вида продукции или закрыть.

Из таблицы видно, что функционал (суммарные производственные и транспортные затраты) составляет 64 960 тыс. рублей. Из них производственная составляющая равна 58 340 (500 • 45 + 400 • 160 + 700 • 40) тыс. рублей, на транспортную составляющую приходится соответственно 6620 тыс. рублей, или 11 %. Высокий удельный вес транспортной составляющей - свыше 5 % - свидетельствует о том, что транспортный фактор оказывает существенное значение на загрузку производственных мощностей для рассматриваемого примера.

Автомобильный транспорт является основой транспортной системы вместе с видами транспорта (железнодорожным, воздушным, трубопроводным, водным). Более того, занимает лидирующие позиции по перевозкам грузов (74…83%) и пассажиров (51…56%), участвует в решении транспортных задач во всех отраслях народного хозяйства страны.

3. Решение транспортных задачу с помощью MS Excel

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

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

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

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

Для решения таких задач Excel имеет специальный инструмент «Поиск решения». Надстройка «Поиск решения» в Microsoft Excel позволяет напрямую находить оптимальное решение транспортной задачи.

Для добавления надстройки «Поиск решения», если на вкладке «Данные» этого пункта нет перейдите: Файл -- Параметры. Слева выберите меню «Надстройки». В основной части выделите «Поиск решения». Затем ниже, нажмите «Перейти». В открывшемся окне отметьте пункт «Поиск решения» и нажмите «Ok». Во вкладке «Данные» появился соответствующий одноименный пункт.

Общее условие транспортной задачи:

Найти m*n неотрицательных чисел Xij- объем перевозок от i-ого поставщика к j-ому потребителю, минимизирующих транспортные затраты по перевозке однородных грузов поставщиков с мощностями (запасами) А1,А2…Ам к потребителям с потребностями В1,В2…Вn, если известны матрица издержек Сij - издержки перевозки единицы груза от i-ого поставщика к j-ому потребителю.

Математическая постановка задачи:

Целевая функция

Ограничения

для i=1,2….m

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

для j=1,2….n

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

Пример задачи и ее решения в Ms Excel.

Условие:

Дано 5 производителей А1, А2, А3, А4, А5, мощность (запасы) которых соответственно равна(равны): 20, 45, 25, 30,20.

И четыре потребителя В1, В2, В3, В4, потребность которых в продукте составляет соответственно: 45, 50, 20, 25.

Также известна матрица издержек Сij - издержки перевозки единицы груза от i-ого поставщика к j-ому потребителю.

Ее можно представить таблицей:

12	9	10	4
4	7	7	6
7	11	5	8
9	6	9	9
10	11	6	5

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

Ai Bj	45	50	20	25
20	12	9	10	4
45	4	7	7	6
25	7	11	5	8
30	9	6	9	9
20	10	11	6	5

Решение:

В интервал ячеек A2:A6 ввести запасы поставщиков -- Ai:



В интервал ячеек B1:E1 ввести количество необходимого груза Bj-го потребителя:

Для дальнейшего удобства выделим ячейки различными цветами и установим жирную границу:

В интервал ячеек B2:E6 ввести матрицу Cij издержек перевозки единицы груза от i-ого поставщика к j-ому потребителю:

В ячейку Н1 введите формулу: СУММAПРОИЗВ(В2:E6;B9:E13)



В ячейку A9 введите формулу СУММ(B9:F9) и растяните её до А13 (как растянуть формулу см. тут --> Тыц) :

В ячейку B8 введите формулу СУММ(B9:B13) и скопируйте ее в диапазон от B8до E8:



Для решения задачи на панели вкладок выберите вкладку «Данные», а затем «Поиск решения»:

Заполните открывшееся окно в соответствие с рисунком и нажмите Найти решение:

В диапазоне B9:E13 Вы получите результат решения транспортной задачи (т.е. значение в ячейке соответствует количеству груза перевезенного от i-ого поставщика к j-ому потребителю).

В диапазоне A9:A13 количество груза, которое необходимо вывезти от поставщиков.

В диапазоне B8:E8 количество которое будет доставлено потребителям согласно найденному решению.

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

Оформим полученный результат и получим следующее:



Заключение

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

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

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

...