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

1 Пояснительная  записка

 Введение

1 Исходные данные

2 Математическая  модель исходной задачи (транспортная)

3 Построение опорного плана методом наименьшего элемента

4 Построение  опорного плана методом северо-западного  угла

5 Определение  оптимального плана перевозок методом потенциалов

6 Решение транспортной  задачи с использованием программы Microsoft Exel

7 Отчеты по  результатам устойчивости пределам  исходной задачи

Заключение

Литература

2 Графическая  часть проекта

1 Диаграмма  обьема производства

2 Диаграмма использования ресурсов

3 Диаграмма  транспортных издержек по каждому  потребителю

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

Каждый человек  ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Не трудно выиграть сражение, имея армию в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся “на глазок”. В середине XX века был создан специальный математический аппарат, помогающий это делать “по науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование" здесь и в аналогичных терминах (“линейное программирование, динамическое программирование” и т.п.) обязано отчасти историческому недоразумению, отчасти неточному переводу с английского. По-русски лучше было бы употребить слово “планирование”. С программированием для ЭВМ математическое программирование имеет лишь то общее, что большинство возникающих на практике задач математического программирования слишком громоздки для ручного счета, решить их можно только с помощью ЭВМ, предварительно составив программу. Временем рождения линейного программирования принято считать 1939 г., когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”.

Под названием  “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

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

Цель транспортной деятельности считается достигнутой при выполнении шести условий:

1. нужный товар;
2. необходимого качества;
3. в необходимом количестве доставлен;
4. в нужное время;
5. в нужное место;
6. с минимальными затратами.

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

 

1 Исходные данные

Экономическая часть

Требуется произвести перевозки однородного груза  из пунктов отправления (склады) А₁ … А_m , содержащих соответственно а₁ , а₂ , …, а_m единиц груза, в пункт назначения (магазины) В₁ , В₂ ,…, В_n количествах b₁ , b₂ , … b_n соответственно, при этом суммарные транспортные затраты должны быть наименьшими.

Известны C_ij – затраты на перевозку 1 единицы груза из пункта A_i в B_j.

Исходные данные оформлены в таблице  1.

 

Таблица 1 –  Исходные данные

Склады	Магазины
	В1	В2	В3	В4	В5
А1	4	2	1	3	2
А2	3	6	4	3	2
А3	1	5	6	3	4
А4	8	9	3	2	3

Количество  груза имеющегося в пунктах отправления

А1	А2	А3	А4
60	50	40	20

Количество  груза имеющегося в пунктах отправления

В1	В2	В3	В4	В5
40	25	30	35	40

 

 

 

 

 

 

 

2 Математическая  модель исходной задачи

 

Математическая  модель исходной задачи (транспортная задача)

Переменным (неизвестными) транспортной задачи являются x_ij, i=1,2, … , m, j=1,2, … , n – объемы перевозок от  каждого i-го поставщика, каждому j-му потребителю.

Так как произведение c_ijx_ij  определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны :

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

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

Вторая группа из n уравнений выражает требование полностью удовлетворит запросы всех n потребителей :

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

Необходимое и  достаточное условие разрешимости транспортной задачи

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

Определим математическую модель исходя из исходных данных:

Для спроса

Для предложения

 

 

Таким образом

 

 

 

 

 

4 Построение  опорного плана методом северо-западного  угла

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

Рассмотрим маршрут доставки от поставщика A₁ к потребителю B_1.

Запасы поставщика A₁ к потребителю B₁ составляют 60 единиц продукции, потребность потребителя B₁ составляет 40 единиц продукции. От поставщика A₁ к потребителю B₁ будем доставлять min=40 единиц продукции.

Поместим в  ячейку A₁B₁ значение 40

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

Склады	Магазины
	B1	B2	B3	B4	B5
A1	404	202	1	3	2	60
A2	3	56	304	153	2	50
A3	1	5	6	203	204	40
A4	8	9	3	2	203	20
	40	25	30	35	40

 

F=40*4+20*2+5*6+30*4+15*3+20*3+20*4+20*3 = 595

 

 

 

 

 

 

3 Построение опорного плана методом наименьшего элемента

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

Минимальный элемент  матрицы тарифов находится в  ячейке A₁B₃ и равен 1.Запасы поставщика A₁ составляют 60 единиц продукции. Потребность потребителя B₃ составляет 30 единиц продукции. От поставщика A₁ к потребителю B₃ min=30 единиц продукции. Разместим в ячейку A₁B₃ значение равное 30. Мы полностью удовлетворили потребность потребителя B₃.Вычеркиваем столбец 3 таблицы, т.е. исключаем из дальнейшего рассмотрения. Следующие действия производим аналогично взяв за основу следующий наименьший элемент таблицы который находится в ячейке A₃B₁ и равен 1…

Склады	Магазины
	B1	B2	B3	B4	B5
A1	4	252	301	3	52	60
A2	03	6	4	153	352	50
A3	401	5	6	3	4	40
A4	8	9	3	202	3	20
	40	25	30	35	40

 

      

F =30*1+40*1+25*2+5*2+35*2+20*2+15*3=285

 

 

 

 

 

Заключение

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

Алгоритм и  методы решения транспортной задачи могут быть использованы при решении  некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие: оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком; оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности; задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции; увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность; решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким-то причинам не может быть отправлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки. Таким образом, важность решения данной задачи для экономики несомненна. Приятно осознавать, что у истоков создания теории линейного программирования и решения, в том числе и транспортной задачи, стоял русский ученый - Леонид Витальевич Канторович.