Особенность решения транспортных задач

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

МИНИСТЕРСТВО ТРАНСПОРТА РОСИЙСКОЙ ФЕДЕРАЦИИ

ФЕДЕРАЛЬНОЕ АГЕНТСТВО ЖЕЛЕЗНОДОРОЖНОГО ТРАНСПОРТА

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

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПУТЕЙ СООБЩЕНИЯ»

Кафедра «Экономика и логистика на транспорте»

ТРАНСПОРТНАЯ ЛОГИСТИКА

Методические указания для выполнения лабораторных работ студентами очной и заочной форм обучения направления «Менеджмент»

Составитель

Ю.В. Федоров

Самара - 2014

УДК (075.8) 658.5

Логистика: методические указания для выполнения практических работ студентами очной и заочной форм обучения направления «Менеджмент»/ составитель Ю.В.Федоров. - Самара: СамГУПС, 2014. - с.

Утверждены на заседании кафедры «Экономика и логистика на транспорте» 4 февраля 2014 г., протокол № 6

Печатается по решению редакционно - издательского совета университета.

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

Составитель: Федоров Юрий Владимирович

Рецензент:

к.т.н.доцент каф. БППГ СамГУПС, И.И. Кононов

Компьютерная верстка: Е.А.Ковалева

Подписано в печать формат 60х90х1/16

Усл. печ. л. Тираж 25 экземпляров Заказ

©Самарский государственный университет путей сообщения, 2014

Лабораторная работа 1

Задача оптимальной организации поставки грузов от поставщиков к потребителям (транспортная задача)

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

Задача. Перевозится однородный груз из трех пунктов А1, А2, А3 к четырем местам назначения В1, В2, В3, В4. Из пункта А1 может быть направлено 50 т, из А2 - 40 т, из А3 - 20 т. В пункты назначения должен поступить груз: в пункт В1 - 30 т., в В2 - 25 т, в В3 - 35 т, в В4 - 20 т. Расстояния сij, i = 1, 2, 3., j = 1, 2, 3, 4., от i - поставщика j - потребителю приведены в углах клеток рис. 1.

Рис.1. Исходные данные

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

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

Решение. Построим экономико - математическую модель задачи. Обозначим через хij - количество груза, которое будет доставлено от i - пункта отправления в j - пункт назначения, i = 1, 2, 3, j = 1, 2, 3, 4. Необходимо минимизировать целевую функцию.

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

,

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

Xij ? 0, i = 1,2,3, j = 1,2,3,4

На рис 2. показано представление транспортной задачи в виде графа с m пунктами отправления и n пунктами назначения, которые показаны в виде узлов сети:

Предложения Спрос дуги, соединяющие узлы сети, соответствуют маршрутам, связывающим пункты отправления и назначения. С дугой ( i, j ), соединяющей пункт отправления i с пунктом назначения j, соотносятся два вида данных: пробег транспорта сij из пункта i в пункт j и количество перевозимого груза хij. Объем грузов в пункте отправления i равен аi, а объем грузов в пункте назначения j равен bj. Задача состоит в определении неизвестных величин хij, минимизирующих суммарные транспортные расходы и удовлетворяющих ограничениям, накладываемым на объем грузов в пунктах отправления ( предложение) и пунктах назначения ( спрос).

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

Исходные данные для решения классической транспортной задачи представляются в виде двух таблиц ( рис. 3 ), в первой из которых представлены: 1) переменные хij, первоначально принимающие значения, равные единице ( матрица перевозок или изменяемые ячейки В3:Е5 ); 2) значения предложения каждого поставщика ( с учетом условия, что весь груз от поставщика должен быть вывезен, в ячейках А3:А5 первоначально помещаем суммы содержимых ячеек строк матрицы перевозок, т.е. 4,4,4); 3) значения спроса каждого потребителя, т.е. в ячейках В6:Е6 тройки, как суммы содержимых ячеек соответствующих столбцов матрицы перевозок - это учет того обстоятельства, что все потребности должны быть удовлетворены.

Во второй таблице представляются значения стоимости перевозок единицы товара сij от i - поставщика к j - потребителю В10:Е12, а также мощности поставщиков А10:А12 и мощности потребителей В9:Е9. Целевая ячейка Е14 должна содержать формулу, выражающую целевую функцию Е14=СУММПРОИЗВ(В10:Е12;В3:Е5)

Рис. 3. Исходные данные

Используя меню Данные Поиск решения, открываем диалоговое окно. Поиск решения ( рис.4 ), в котором устанавливаем целевую ячейку равной минимальному значению, определяем диапазон изменяемых ячеек и ограничения. Запускаем процедуру вычислений, щелкнув по кнопке Выполнить.

Рис. 4. Окно Поиск решения с введенными ограничениями

Не забудьте также с помощью окна «Параметры» ввести условия решения оптимизационных задач: в нашем случае следует установить флажок «линейная модель» и флажок «неотрицательные значения». Затем нажать кнопку «ОК», а после нее кнопку «Выполнить». На экране появится окно «Результаты поиска решения»(рис.5)

Рис. 5. Решение найдено

В результате решения получен оптимальный план перевозок:

Рис. 6. Оптимальный план перевозок

Х11 = 5 ед. груза следует перевезти от 1-го поставщика 1-му потребителю;

Х12 = 25 ед. груза следует перевезти от 1-го поставщика 2-му потребителю;

Х13 = 20 ед. груза следует перевезти от 1-го поставщика 4-му потребителю;

Х21 = 5 ед. груза следует перевезти от 2-го поставщика 1-му потребителю;

Х23 = 35 ед. груза следует перевезти от 2-го поставщика 3-му потребителю;

Х31 = 20 ед. груза следует перевезти от 3-го поставщика 1-му потребителю.

Общая стоимость перевозок = 190 денежных единиц.

Задания к лабораторной работе

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

Вариант 1

	150	40	110	50
70 80 90 110	9 11 7 6	5 8 6 4	10 9 5 3	7 6 4 2

Вариант 2

	25	10	20	30	15
40 20 40	5 3 4	3 4 6	4 10 9	6 5 3	4 7 4

Вариант 3

	100	140	100	60
100 60 80 160	5 2 3 4	4 3 2 1	3 5 4 2	2 6 3 4

Вариант 4

	150	350	200	100	100
500 300 100	3 4 3	3 3 7	5 2 5	3 4 4	1 5 1

Вариант 5

	60	40	120	100
70 80 90 80	4 3 2 1	8 5 6 4	1 3 4 5	6 4 3 3

Вариант 6

	40	30	90	80	50
60 90 140	4 2 6	2 4 5	3 3 4	4 5 6	1 6 2

Вариант 7

	8	9	13	8	12
9 11 14	5 23 30	15 8 1	3 13 5	6 27 24	10 12 25

Вариант 8

	40	30	20	50
60 70 50	2 2 8	4 3 4	5 9 2	1 4 5

Вариант 9

	11	11	11	16	11
15 15 15	3 19 20	4 2 27	5 22 1	15 4 17	24 13 19

Вариант 10

	7	7	7	7	2
4 6 10 10	16 20 13 3	30 27 4 1	17 26 22 5	10 9 3 4	16 23 1 24

Лабораторная работа 2

Задача поставки двух видов продукции.

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

Пример. Менеджер отдела логистики составляет план перевозок продукции фирмы с трех её складских комплексов: база 1, база 2, база 3 к четырем потребителям Х, Y, Z, W. Грузы включают продукцию двух видов: А и В. Стоимость перевозок для каждого вида продукции, исходя из расстояний и других факторов, приведена в таблице 1.

Таб. 1. Стоимость перевозок.

		Потребитель Х	Потребитель Y	Потребитель Z	Потребитель W
		А	В	А	В	А	В	А	В
База 1	А	595		480		455		430
	В		780		665		640		815
База 2	А	435		530		480		485
	В		735		735		680		585
База 3	А	545		465		525		440
	В		715		755		815		795

Потребители заказывают следующие объемы товаров А и В:

Таб. 2

	Клиент Х	Клиент Y	Клиент Z	Клиент W
	А	В	А	В	А	В	А	В
Заказы, шт	15	20	22	26	12	22	32	42

На базах же в настоящий момент имеются следующие запасы товаров:

Таб. 3

	База 1	База 2	База 3
	А	В	А	В	А	В
Запасы, шт	21	21	33	43	17	57

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

Для решения задачи, разделяем ее на две, по числу продуктов, предназначенных для перевозок. Каждая из этих задач будет решаться обычным способом (смотрите практическое занятие 1). При этом необходимо учесть, что продукта А в запасах имеется 71 единица, а заказано клиентами 81 единица; продукта В в запасах 120 единиц, а заказано клиентами 110 единиц. Таким образом, продукта А не хватает для удовлетворения клиентов, значит, нужно ввести фиктивного поставщика с запасом продукта А в 10 единиц. Продукт В имеется в избытке, поэтому нужен дополнительный потребитель, который закажет оставшиеся 10 единиц.

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

Отметим, что рассматриваемую задачу можно решить и как одну задачу, решая её ( поставленную в исходном варианте задачу ) целиком. При этом, если в однопродуктовой модели паре база - клиент (поставщик - потребитель) на рабочем листе Excel соответствует одна ячейка, то в нашем случае это будут четыре ячейки, например, в матрице стоимостей перевозок паре база 1 - клиент Х соответствуют ячейки С3:Д4:

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

Приведем лишь окончательные цифры результата, полученные с помощью программы «Поиск решения»:

Минимальная общая стоимость перевозок = 104760 ( руб. )

Клиенту Х будет поставлено 15 единиц товара А с базы 2, 20 единиц товара В с базы 3;

Клиенту Y будет поставлено 12 единиц товара А с базы 3, 26 единиц товара В с базы 3;

Клиенту Z будет поставлено 12 единиц товара А с базы 2, 21 единица товара В с базы 1 и 1 единица с базы 3;

Клиенту W будет поставлено 21 единица товара А с базы 1, 6 единиц с базы 2, 5 единиц с базы 3, весь товар В (42 единицы) будет доставлен с базы 2.

Наихудший план отличается от лучшего почти на 20% ( суммарная стоимость перевозок здесь возрастет до 122930 руб. ). Он получается путем замены цели поиска на максимум, а высоких тарифов (+9999 ) на очень низкие ( -9999 ) - только так можно реализовать запрет на некоторые маршруты.

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

Лабораторная работа 3

Частный случай транспортной задачи: «Задача о назначениях»

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

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

Общая задача назначения работников на их работы представлена ниже:

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

Коэффициент cij равен стоимости назначения работника i на работу j (i, j =1, 2,…, n). То, что количество работников равно количеству работ, не является ограничением общности, поскольку всегда можно ввести в модель фиктивных работников или фиктивные работы.

Как уже указывалось, задача о назначениях является частным случаем транспортной задачи, в которой работники соответствуют пунктам отправления, а работы - пунктам назначения. В данном случае все величины спроса и предложения равны 1. Стоимость «транспортировки» рабочего i на работу j равна cij. Задачу о назначениях можно эффективно решить точно так же, как и транспортную задачу.

Можно сказать о только что прочитанном Вами несколько иначе: в задаче о назначениях от каждого поставщика к каждому потребителю поставляется только одна единица «груза» (только одного рабочего можно назначить на выполнение данной работы) или ни одной. Поэтому все «запасы» и все «заказы» равны 1. Понятно, что все переменные в задаче о назначениях могут принимать значения 1 или 0. Такие значения получаются при решении автоматически, явно требовать целочисленности переменных (их равенства только нулю или единице) не требуется.

Задача.

Заместитель директора по персоналу фирмы «Data mark» должен составить 6 пар-команд из техника-программиста и специалиста по маркетингу для установки компьютерных сетей по индивидуальным требованиям клиентов. Пары составляются из вновь набранных сотрудников, среди которых проведен специальный психологический тест на взаимную совместимость. Индекс совместимости варьируется от 20 (выраженная враждебность) до 1 (возможность дружеских отношений) и для каждой потенциальной пары приведен в таблице.

	Аня	Маша	Катя	Лиза	Ольга	Софья
Иван	3	4	9	18	9	6
Михаил	16	8	12	13	20	4
Павел	8	6	13	1	6	9
Николай	16	9	6	8	1	11
Алексей	8	12	17	5	3	5
Петр	2	9	1	10	5	17

Найти такое распределение по парам, которое обращает в минимум суммарный индекс совместимости.

Решение.

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

Переменные в итоге должны принять какое-либо из двух возможных значений: 0 или 1. Значение переменной 1 в ячейке В12, например, означает, что будет создана команда из программиста Михаила и специалиста по маркетингу Ани. Если же в ячейки, находящейся на пересечении некоторого столбца или некой строки, содержится 0, то это означает, что данная команда не будет создана. При этом, если найти суммы переменных по столбцам или строкам, как это сделано выше, то все они в правильном решении должны оказаться равными 1. Это будет означать, что каждый из программистов назначен только в одну команду, как и каждый из специалистов по маркетингу.

В ячейке I8 записываем формулу =СУММПРОИЗВ(B2:G7;B11:G16), которая будет рассчитывать суммарный индекс совместимости команд. В ячейке I2 с помощью формулы =СУММПРОИЗВ(B2:G2;B11:G11) вычисляем индекс пары, которую программист Иван составит с кем-либо из специалистов по маркетингу. Протягивая эту формулу вниз, на ячейки I3:I7, получаем индекс совместимости для всех остальных пар.

Можно было бы вычислить индексы и для пар, составляемых специалистами по маркетингу с кем-либо из программистов. Для этого в строке В9 нужно было ввести формулу =СУММПРОИЗВ(B11:В16;B2:В7) и протянуть ее вправо. Результат в смысле составляемых пар в обоих случаях один и тот же.

Далее вызываем Поиск решения и указываем целевую ячейку I8. В качестве указываем поиск минимума. Переменные задачи размещены в ячейках B11:G16. В Параметрах отмечаем, что подразумевается линейная модель и переменные неотрицательные. Ограничений здесь всего 2 (групповых): ограничение Н11:Н16= Н2:Н7 требует, чтобы каждый из программистов был назначен только один раз (столбец Н2:Н7 содержит только единицы), а ограничение B17:G17= B8:G8 требует того же для специалистов по маркетингу.

Результатом решения будет следующая таблица:

Суммарный индекс совместимости равен 19. Таблица переменных дает распределение по парам: Иван - Аня, Михаил - Маша, Павел - Лиза, Николай - Ольга, Алексей - Софья, Петр - Катя.

Задания к лабораторной работе

1. 8 команд с проблемой

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

	Федина	Урванова	Тулеев	Сажин	Ремеева	Павлов	Ольгерд	Ненашев
Яров	13	10	7	9	9	12	13	10
Юмашев	10	10	11	12	10	11	11	11
Энеев	13	15	15	14	12	16	16	16
Щукин	13	18	14	14	11	9	18	14
Шишкин	8	6	7	8	12	11	9	8
Чубайс	16	15	17	17	11	11	16	13
Цетлин	7	6	12	8	11	6	9	7
Хрюкин	17	15	12	14	12	17	14	15

a. Найдите оптимальное распределение людей по парам.

b. Каков наихудший индекс в отобранных парах? Какова величина суммарного индекса?

c. Есть ли у задачи альтернативные решения? Какое из решений лучше? Почему?

d. Из-за семейных проблем бригадир Шишкин вынужден просить не объединять его в одну команду с Урвановой. Найдите такое разбиение людей по командам, которое соответствовало бы этому условию. Насколько вырос суммарный индекс совместимости?

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

2.9 команд

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

	Калинин	Ларин	Михеев	Носов	Оболенский	Петров	Разумов	Степанов	Тювалев
Агеев	13	11	16	14	17	13	18	15	13
Басов	6	4	7	5	6	6	4	5	4
Валиев	9	7	12	11	11	10	10	9	6
Григорьев	7	12	13	8	10	12	10	8	6
Данин	14	12	12	14	13	11	12	11	12
Ерастов	8	18	10	17	13	13	11	10	14
Жажин	13	9	14	10	13	6	14	14	10
Зиновьев	16	11	17	18	19	10	17	20	17
Ипатьев	13	8	14	19	18	10	16	18	9

a. Найдите оптимальное распределение людей по парам.

b. Каков наихудший индекс в отобранных парах? Какова величина суммарного индекса?

c. Есть ли у задачи альтернативные решения? Какое из решений лучше? Почему?

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

3. Олимпийские игры

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

Этап	Карл	Крис	Дэвид	Тони	Кен
1	37,7	32,9	33,8	37,0	35,4
2	43,4	33,1	42,2	34,7	41,8
3	33,3	28,5	38,9	30,4	33,6
4	29,2	26,4	29,6	28,5	31,1

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

b. Каков этот гипотетический наилучший результат?

4. Назначение слесарей

Мастер должен назначить 7 слесарей (А, В,…, Н) для ремонта сельскохозяйственной техники (К-701, Т-150М и т. д.), имеющей разного рода неисправности после окончания уборочной.

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

	К-701	Т-150М	Т-150М	МТЗ-80	МТЗ-40	Т-100	Дон-1500
А	12	14	14	10	9	15	21
В	15	13	12	10	8	21	23
С	-	16	11	10	11	21	-
D	16	-	-	8	9	-	21
Е	13	11	13	9	8	15	21
F	13	13	11	11	9	22	28
Н	12	13	13	9	10	22	27

a. Каково минимальное суммарное рабочее время, требующееся на выполнение ремонта?

b. Есть ли у задачи альтернативные решения? Приведите все решения, которые сможете найти.

c. Выяснилось, что слесарь В из-за болезни рук не может сейчас выполнить ремонт К-701 и МТЗ-40, так как требуется переборка и промывка двигателя. Составьте новый план назначений с учетом этого
обстоятельства. Приведите все решения, которые сможете найти.

5.Отбор специалистов и составление команд

Заместитель директора фирмы по персоналу должен отобрать и составить 6 пар-команд из 8 техников-программистов (D1, D2,…,D8) и 7 специалистов по маркетингу (S1, S2,…,S7)для работы по установке компьютерных сетей по индивидуальным требованиям клиентов. Пары составляются из вновь набранных сотрудников, среди которых проведен специальный психологический тест на взаимную совместимость. Индекс совместимости варьирует от 1 (возможность дружеских отношений) до 20 (выраженная враждебность) и для каждой потенциальной пары приведен в таблице.

	D1	D2	D3	D4	D5	D6	D7	D8
S1	15	12	16	6	2	9	11	15
S2	11	13	15	10	2	14	6	20
S3	12	8	16	10	1	13	4	11
S4	16	7	14	7	1	10	6	19
S5	12	6	13	12	1	10	5	16
S6	13	11	12	11	1	9	5	17
S7	13	11	13	6	4	13	12	15

Определите такое распределение по парам, при котором суммарный индекс совместимости был бы минимальным. Примите во внимание просьбу S2 не объединять его в команду с его женой D1.

6. Выбор места для складов

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

Транспортные издержки на всю продукцию каждого завода для всех возможных маршрутов приведены в таблице. Назначьте каждому заводу (завод А, завод B,…, завод D) свой склад (склад 1, склад 2,…, склад 8) так, чтобы минимизировать транспортные издержки

Издержки, ед.	Склад 1	Склад 2	Склад 3	Склад 4	Склад 5	Склад 6	Склад 7	Склад 8
Завод А	185	185	210	200	200	195	185	190
Завод В	180	165	180	165	170	190	165	195
Завод С	170	170	180	210	200	170	235	210
Завод D	200	190	190	220	195	220	190	190

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

7. Распределение оптовиков

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

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

Время доставки заказа от центра до оптовика представлено в таблице ниже.

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

b. Транспортный отдел просит не назначать оптовику данный центр, если время доставки превышает 10 ч. Можно ли удовлетворить эту
просьбу? Как изменится суммарное время доставки?

c. Полученное решение не удовлетворяет отдел сбыта, потому что наиболее ценные для компании клиенты -- оптовики ОС7 и ОС8 -
оказались приписаны "не к тому центру". Время доставки у них
соответственно 10 и 9 ч. Они требуют, чтобы это время не превышало 5 ч. Можно ли удовлетворить это требование? Попробуйте ослабить какие-нибудь другие условия (не снимая полностью), чтобы
получить нужное решение.

d. Попробуйте вообще снять ограничение на число клиентов в каждом центре. Объясните полученный результат.

	Время доставки на оптовый склад
№ ОС	1	2	3	4	5	6	7	8	9	10	11	12	13	14
ДЦ 1	3	4	5	5	4	10	9	11	8	10	10	13	19	20
ДЦ 2	16	14	15	21	20	17	18	19	16	15	19	22	15	17
ДЦ 3	11	9	11	8	10	10	13	19	20	18	15	16	14	15
ДЦ4	19	16	15	19	22	3	4	5	5	4	3	4	5	5
№ ОС	15	16	17	18	19	20	21	22	23	24	25	26	27	28
ДЦ 1	18	15	16	14	15	21	20	17	18	19	16	15	19	22
ДЦ 2	3	4	5	5	4	3	4	5	3	10	10	13	18	16
ДЦ 3	21	20	17	18	21	20	17	18	19	3	4	5	5	4
ДЦ4	4	10	9	11	8	10	10	13	10	9	11	8	10	10

8. Назначение центров снабжения

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

Генеральный директор продвигает идею открытия региональных складов, которые могли бы снабжать отдельные подсети магазинов. Отдел развития сети предложил семь мест для создания таких складов, все они, разумеется, расположены в тех городах, где уже есть магазин сети. Однако 7 складов на 24 региональных магазина явно очень много. Из соображений разумного размещения складов, не требующего сложного управления (для которого и персонал то в регионах найти сложно), директор складского комплекса предлагает остановиться на 3 складах, каждый из которых мог бы снабжать не менее 6 и не более 9 магазинов.

Менеджер отдела логистики подготовил руководству следующие данные о времени подъезда с каждого из семи региональных складов к каждому из 24 магазинов:

	Ml	М2	М3	М4	М5	М6	М7	М8	М9	М10	М11	М12
РС1	3,9	10	18,5	6,7	17,2	13,6	10,8	7	5,9	12,4	0	12
РС2	8,1	0	9,5	12	11,8	9	17,6	11,8	12	6,4	7,2	18,9
РС3	13,6	15,3	19,1	0	14,9	18,6	1,8	10,7	15,3	9,4	5,1	12,6
РС4	12,8	11,4	10,4	6,3	15	9	6,1	15,3	0	16,3	5,3	14,7
РС5	9,1	3,6	12,4	12	11,9	7,2	15,4	2,5	8,1	12,6	8,2	0
РС6	11,7	12,1	15,8	14,7	8,4	10,5	13,2	0	10,3	17,8	18,4	14,7
РС7	10,7	10,7	14,2	13,2	10,7	9	12,7	8,1	11,7	5,7	16,4	12,4
	М13	М14	М15	М16	М17	М18	М19	М20	М21	М22	М23	М24
РС1	10,4	9,5	11,8	13,4	9,6	7,8	16,2	15,5	9,4	12,9	6,7	15,5
РС2	12,8	2,5	10,8	16,7	10,9	8,8	4,8	7,1	15,8	13,2	16,7	16,7
РС3	13,7	13,6	10	13,3	19,5	16	14,7	9,4	14,8	15,7	12	4,2
РС4	14,5	9,1	9,5	11,6	10,1	10	11	14,9	13,8	12	14,4	14,3
РС5	13,6	13,2	7,3	11,4	10,6	10,4	8,9	15,7	9	7,1	13,1	11,3
РС6	16,1	13	7,1	8,4	14,8	15,3	9,2	11,9	16,3	12,6	19,6	9,9
РС7	12,2	8,8	15,2	16	9,4	16,1	0	10,8	5,3	7,6	17,7	14,6

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

b. Добавьте ограничения, позволяющие отобрать из 7 предложенных складов 3 лучших. Как выросло при этом суммарное время в пути? Выполнено ли условие о том, что на каждый склад должно приходиться от 6 до 9 магазинов?

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

9. Сделать назначение в следующих задачах:

Матрица производительности (22)	Матрица эффективности (24)
Матрица эффективности (33)	Матрица эффективности (44)
Матрица эффективности

Лабораторная работа 4

Транспортная модель с промежуточными пунктами

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

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

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

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

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

Пример. Два автомобильных завода Р1 и Р2 связаны с тремя дилерами Д1, Д2, Д3 имеющими два ( транзитных ) перевалочных центра Т1 и Т2. Заводы Р1 и Р2 производят 1000 и 1200 автомобилей. Заказы дилеров составляют соответственно 800, 900 и 500 автомобилей. Стоимость перевозки одного автомобиля ( в сотнях долларов ) показана возле соответствующей дуги.

Рис. 7 Транспортная модель с промежуточными пунктами.

Перевозки транзитом могут осуществляться здесь через любой пункт ( в соответствии с направлением дуг на рисунке ), даже через некоторые пункты назначения. Поэтому пункты, которым соответствуют как входящие, так и выходящие дуги, назовем транзитными ( Т1, Т2, Д1, Д2 ). Оставшиеся будут либо истинными пунктами отправления ( Р1, Р2 ), либо истинными пунктами назначения ( Д3 ). Эту модель можно преобразовать в обычную транспортную модель с шестью пунктами отправления ( Т1, Т2, Д1, Д2, Р1, Р2 ) и пятью пунктами назначения ( Т1, Т2, Д1, Д2, Д3 ). Объемы спроса и предложения, соответствующие этим пунктам отправления и назначения, вычисляются следующим образом:

Объем предложения истинного пункта отправления = объем исходного предложения;

Объем предложения транзитного пункта = объем исходного предложения + объем буфера;

Объем спроса истинного пункта назначения = объем исходного спроса;

Объем спроса транзитного пункта = объем исходного спроса + объем буфера;

Объем буфера должен быть таким, чтобы вместить объем всего предложения ( или спроса ).

Обозначим через В объем буфера. Тогда

В = общий объем предложения ( или спроса ) = 1000 + 1200 или ( 800 + 900 + 500 ) = 2200 автомобилей.

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

В рисунке 8 приведены исходные данные нашей задачи как классической транспортной задачи. Здесь слева ( столбцом ) указаны Т1, Т2, Д1, Д2, Р1, Р2 - пункты отправления: истинные Р1, Р2, а так же транзитные Т1, Т2, Д1, Д2. Справа - тоже столбцом и тоже вне таблицы - объемы их предложения. Сверху - над таблицей пункты: Т1, Т2, Д1, Д2, Д3, из которых Т1, Т2, Д1, Д2 - транзитные, а Д3 - истинный. Снизу, под таблицей, соответственно, объемы их спроса. М - достаточно большое число ( например 100 ), показывающее, что, например, прямой связи между Р1 и Д1, Д2, Д3 нет.



Рис. 8. Исходные данные эквивалентной транспортной задачи

Далее, используя уже описанную в предыдущей работе технологию решения классической транспортной задачи в среде Excel ( с программой «Поиск решения» ), получаем следующие результаты:

Рис. 9. Оптимальный план перевозок

Нанесем полученные таким образом оптимальные объемы перевозок на представленную в самом начале сеть:

Рис. 10. Решение транспортной задачи с промежуточными пунктами

«Транзитный» эффект решения здесь таков, что дилер Д2, получая 1400 автомобилей, оставляет 900 для удовлетворения своего спроса, а 500 отправляет дилеру Д3.

Задания к лабораторной работе

1. На рисунке 11 показана сеть нефтепроводов. Узлы этой сети соответствуют насосным и принимающим станциям. Расстояния ( в км ) между станциями приведены на схеме сети. Стоимость транспортировки одного галлона нефти между двумя станциями пропорциональна длине нефтепровода, соединяющего эти станции. Сформулируйте транспортную задачу с промежуточными пунктами и найдите ее оптимальное решение для перекачки нефти из пунктов 1 и 3 в пункты 2 и 4.

Рис. 11.

2. Две фабрики снабжают определенной продукцией три магазина. Объемы производства фабрик равны 200 и 300 единиц продукции, а потребности магазинов составляют 100, 200 и 50 единиц продукции. Исследуется возможность перевозок продукции через промежуточные пункты. Основываясь на величинах стоимости перевозок ( в долларах ), приведенных ниже, найдите оптимальный план перевозок.

	Фабрики	Магазины
	1	2	1	2	3
Фабрики	1	0	6	7	8	9
	2	6	0	5	4	3
Магазины	1	7	2	0	5	1
	2	1	5	1	0	4
	3	8	9	7	6	0

3. На рисунке 12 показана транспортная сеть перевозок автомобилей между тремя заводами ( 1, 2, 3 ) и тремя дилерами ( 6, 7, 8 ) через два распределительных центра ( 4 и 5 ). Стоимость перевозок ( в сотнях долларов ) представлена на рисунке возле соответствующих дуг.

Рис. 12.

а) сформулируйте задачу как транспортную задачу

б) предположим, распределительный центр ( 4 ) может продать 240 автомобилей самостоятельно. Найти оптимальное решение.

4. В транспортной сети осуществляются перевозки из пунктов 1 и 2 в пункты 5 и 6 через транзитные пункты 3 и 4. Стоимость перевозок показана на рисунке 13.

Рис. 13.

Решите транспортную задачу ( с промежуточными пунктами ).

5. Пусть в предыдущей задачи пункты 1 и 2 связаны транспортной магистралью со стоимостью перевозки в 1 доллар, а стоимость перевозки из пункта 1 в пункт 3 возросла до 5 долларов. Найдите оптимальную схему перевозок.

Лабораторная работа 5

Задача поиска кратчайшего пути.

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

1. Поиск кратчайшего маршрута между двумя городами по существующей сети дорог.

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

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

4. Определение максимальной пропускной способности трубопровода для транспортировки угольной пульпы от угольных шахт к электростанциям.

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

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

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

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

Пусть задан некоторый граф транспортной сети ( рис. 14 ), каждой ориентированной дуге ( i, j ) которого соответствует определенное расстояние.

Рис. 14. Граф транспортной сети

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

Чтобы численно решить задачу, представим исходные данные на рабочем листе Excel. Это должно быть сделано в виде двух матриц, озаглавленных «Таблица кратчайших расстояний» и «План перевозок товара по кратчайшему пути» ( рис. 15 ). Причем в таблице кратчайших расстояний факт отсутствия возможности перевозки товара ассоциируется с тем, что в соответствующие ячейки таблицы заносится любое большое число ( например 100, темные ячейки ). В таблице кратчайших расстояний ( С4:I10 ) указываются конкретные значения расстояний Сij, а в ячейки второй матрицы изначально заносятся нули ( изменяемые ячейки ). В целевую ячейку ( К8 ) заносится формула = СУММПРОИЗВ(С4:I10;С16:I22).

Рис. 15. Исходные данные.

Используя меню «Данные» «Поиск решения», открываем диалоговое окно «Поиск решения» ( рис. 16 ), в котором устанавливаем целевую ячейку, равной минимальному значению, указываем диапазон изменяемых ячеек и ограничения и запускаем процедуру вычисления кнопкой «Выполнить».

Рис. 16. Окно «Поиск решения» с введенными ограничениями.

Результат решения задачи представлен на рисунке 17.

Рис. 17. Результат решения задачи поиска кратчайшего пути

Таким образом, кратчайший путь перевозки товара таков:

127658. Расстояние перевозки составляет 8км.

Задания к лабораторной работе.

1. Найти кратчайший путь между пунктами 1 и 7.

Рис. 18. Транспортная сеть.

Чтобы найти кратчайший путь между пунктами 1 и 7 транспортной сети, сформулируйте транспортную задачу с промежуточными пунктами

Рекомендация: пусть в пункте 1 есть предложение в одну единицу, а в пунктах 6 и 7 - спрос такой же величины.

2. На рисунке 19 показана транспортная сеть, соединяющая восемь городов и расстояния между ними. Найдите кратчайшие маршруты между городами:

А. города 1 и 8

Б. города 1 и 6

В. города 4 и 8

Г. Города 2 и 6

Рис. 19. Транспортная сеть.

3. Найдите кратчайшие пути между узлом 1 и всеми остальными узлами сети, представленной на рисунке 20.

Рис. 20. Транспортная сеть.

Библиографический список

1. Шапиро Дж. Моделирование цепи поставок / Пер. с англ. - СПб : Питер, 2006

2. Леоненков А.В. Решение задач оптимизации в среде MS Excel. - СПб : БХВ-Петербург, 2005.

3. Бочкарев А.А. Транспортная логистика. Решение транспортных задач в MS Excel: Учебное пособие - СПб : издательство Политехнического университета, 2006

4. Грешилов А.А. Математические методы принятия решения : Учебное пособие. - М.: издательство МГТУ им. Н.Э. Баумана, 2006

5. Зайцев М.Г. Методы оптимизации управления для менеджеров. - М.: Дело, 2002

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