- •Введение
- •Запишем их в соответствующие клетки (табл. 7). Третья строка и третий столбец становятся закрытыми и их клетки в дальнейших поисках не участвуют.
- •Последовательное улучшение допустимого решения методом потенциалов
- •Для всех небазисных клеток определим невязки:
- •Решение задачи в excel
- •Определение разницы между наилучшим и наихудшим планами перевозок
- •Ответы на вопросы.
- •Решение задачи
Министерство образования и науки Российской Федерации Федеральное государственное бюджетное образовательное учреждение высшего
профессионального образования
НАЦИОНАЛЬНЫЙ МИНЕРАЛЬНО-СЫРЬЕВОЙ УНИВЕРСИТЕТ «ГОРНЫЙ» Кафедра информатики и компьютерных технологий
«ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ
В ЛОГИСТИКЕ»
Методические указания к выполнению курсовой работы для студентов специальности 080506 (логистика и управление цепями поставок)
Квалификация выпускника - специалист
САНКТ-ПЕТЕРБУРГ
2012
УДК 519.872.339 (075.8)
ЭКОНОМИКО-МАТЕМАТИЧЕСКИЕ МЕТОДЫ И МОДЕЛИ В ЛОГИСТИКЕ. Методические указания к выполнению курсовой работы для студентов специальности 080506 / Национальный минерально-сырьевой университет «Горный». Сост.: Н.М. Петухова - СПб, 2012. 34 с.
Подробно рассматривается решение логистических задач, входящих в курсовую работу. В процессе выполнения курсовой работы студенты должны научиться составлять математические модели задач оптимизации транспортных поставок, решать их, используя методы линейной оптимизации и теории графов (транспортную задачу и задачу о кратчайшем пути), и выполнять их расчет, используя надстройку «Поиск решения» Excel и математический пакет Maple.
Методические указания предназначены для студентов специальности 080506 (логистика и управление цепями поставок).
Габл. 29. Ил. 17.
@ Национальный минерально-сырьевой университет «Горный».
Введение
В соответствии с учебным планом по дисциплине «Экономикоматематические методы и модели в логистике» студенты должны выполнить курсовую работу. Курсовая работа состоит в выполнении двух задач.
Первая из них - транспортная задача, связанная с оптимизацией издержек при перевозках. По условию дается классическая транспортная задача линейной оптимизации закрытого типа. Студентам предлагается построить математическую модель задачи, убедиться, что она является сбалансированной, и решить, используя для отыскания допустимого решения или метод северо-западного угла, или метод наименьшей стоимости, а для получения оптимального решения метод потенциалов. В дальнейшем ручной расчет модели будет использоваться в качестве контрольного примера. Следующий этап - построение на основании математической модели электронной модели Excel и выполнение расчета модели, используя надстройку «Поиск решения». Сравнить результаты расчетов, полученные при ручном счете и средствами Excel. Предлагается сравнить наилучший и наихудший план перевозок, используя поиск решения. Учитывая, что на практике редко встречаются задачи закрытого типа, студентам предлагается рассмотреть варианты, когда имеется излишек запасов или дефицит запасов, сбалансировать транспортную задачу и выполнить расчет уже сбалансированной модели средствами Excel. То есть акцент делается на возможности многократного использования компьютерной модели при небольших ее корректировках для быстрого выполнения расчетов модели и анализа.
Вторая задача - задача выбора оптимального плана перевозки груза от одного поставщика к нескольким потребителям. Такого типа задачи легко решаются методами теории графов. В данном случае задача сводится к задаче определения кратчайшего пути на графе. Для ее решения предлагается использовать метод Дейкстры. После выполнения расчета модели «вручную», студентам предлагается решить задачу, используя математический пакет Maple.
Целью выполнения курсовой работы является развитие у студентов навыков построения математических моделей типовых задач, нахождение оптимального решения путем использования математических методов, реализация расчетов моделей на компьютере, анализ модели. Защита курсовой работы должна выявить степень понимания используемых математических метод, умение строить математические модели выполнять их расчет.
В методических указаниях подробно разбираются примеры выполнения указанных задач (все перечисленные этапы).
Нумерация рисунков, таблиц и формул при описании выполнения каждой задачи автономная.
Каждый студент выполняет индивидуальное задание, выдаваемое преподавателем.
Курсовая работа выполняется на листах формата А4.
ЗАДАЧА 1
УСЛОВИЕ ЗАДАЧИ
Менеджер транспортного отдела составляет план перевозок продукции с трех складов фирмы четырем ее клиентам на следующий месяц. Цены перевозок на одну машину (у.е), запасы продукции и заказы клиентов показаны в таблицах 1, 2, 3.
Табл. 1. Цены перевозок
|
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
Склад 1 |
300 |
500 |
200 |
200 |
Склад 2 |
600 |
100 |
400 |
300 |
Склад 3 |
200 |
300 |
100 |
400 |
Табл. 2. Запасы продукции
|
Склад 1 |
Склад 2 |
Склад 3 |
Запасы |
25 |
45 |
30 |
Табл. 3. Заказы клиентов
|
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
Заказы |
30 |
10 |
30 |
30 |
Составить план транспортных перевозок продукции, при котором издержки будут минимальными.
Задания:
Составьте транспортную таблицу.
Постройте математическую модель задачи.
Выполните расчет модели, используя для получения допустимого решения метод северо-западного угла (или наименьшей стоимости), а для получения оптимального решения метод потенциалов.
Выполните расчет модели в Excel, используя надстройку Поиск решения. Проверьте, совпадают ли ответы, полученные при ручном расчете модели и расчете модели, выполненном в Excel.
Найдите разницу между наилучшим и наихудшим планом перевозок.
Ответьте на вопросы, подтверждая ответы расчетами, выполненными с помощью надстройки Поиск решения:
а) Возможны ли альтернативные решения?
б) После составления плана перевозок выяснилось, что, возможно, Поставщик 1 сможет поставлять на 10 машин продукции больше, чем планировал. Каким будет тогда план перевозок?
с) Выяснилось, что Поставщик 1 не сможет поставлять продукции больше, планировал, к тому же Поставщик 3 сможет поставлять на 5 машин продукции
меньше, чем планировал. Каким будет тогда план перевозок? Какой клиент недополучит продукцию?
ПОСТРОЕНИЕ МАТЕМАТИЧЕСКОЙ МОДЕЛИ На основании исходных таблиц составим транспортную таблицу (табл. 4).
Табл. 4
Запасы продукции |
Заказы клиентов |
||||
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
||
30 |
10 |
30 |
30 |
||
Склад 1 |
25 |
300 |
500 |
200 |
200 |
Склад 2 |
45 |
600 |
100 |
400 |
300 |
Склад 3 |
30 |
200 |
300 |
100 |
400 |
Для наглядности и простоты вычислений «вручную», стоимости перевозок, представленные в залитых цветом клетках таблицы, уменьшим в 100 раз, таким образом, они будут иметь единицу измерения, равную 100 у.е. (табл. 4-а).
Табл. 4-а
Запасы продукции |
Заказы клиентов |
|||||
Клиент 1 |
Клиент 2 |
Клиент 3 |
Клиент 4 |
|||
30 |
10 |
30 |
30 |
|||
Склад 1 |
25 |
3 |
5 |
2 |
2 |
|
Склад 2 |
45 |
6 |
1 |
4 |
3 |
|
Склад 3 |
30 |
2 |
3 |
1 |
4 |
Пусть Xij - количество продукции, отправляемой со склада i к клиенту j, i
= \,т , j =1,и, а сц- стоимость перевозки единицы продукции. Отрицательные значения Ху и с у не имеют смысла, поэтому ху > 0 и Су> 0.
Тогда общая стоимость перевозки равна
3 4
z=E2>rV (d
/=1 7=1
Z-=3 -X11 +5 -X12+2 -X! 3+2 -X14+6 -Х21 +1-Х22+4 'Х23+3 -х24+1 -х31 +3 -Х32+1 -х3 3+4 -х3.
В силу ограничений на возможность поставок продукции со склада и спрос на него клиентов должны выполняться следующие условия (ограничения):
на количество продукции, которую надо вывезти с каждого склада:
•^п + Х]2 + Х]з + Х]4 = 25;
*21 + *22 + х23 + *24 ~ 45; (2)
*31 + *32 + *33 + *34 = 30;
- на количество продукции, которую надо доставить клиентам:
*11 +*21 + *31 = 30;
*12 +*22 + *32 = Ю;
*13+*23+*зз =30; (3) *14 + *24 + *34 = 30.
Суммарное количество продукции на складах:
з
=25 + 45 + 30 = 100, (4)
(=1
Суммарное количество продукции, заказанное клиентами:
4
Y^Pj =30 + 10 + 30 + 30 = 100.
7=1
Так как имеет место равенство:
2>. = Ел=100 (5),
*=1 j=1
транспортная задача является закрытой (с балансом).
Задача формулируется следующим образом: определить такие неотрицательные значения переменных *,у, / =\,т , j — \,п, которые удовлетворяют ограничениям (2) и обращают в минимум целевую функцию (1).
РЕШЕНИЕ ЗАДАЧИ
Решение транспортной задачи состоит из двух этапов:
Определение допустимого решения (базисного решения).
Определение оптимального решения путем последовательного улучшения допустимого решения методом потенциалов.
Определение допустимого решения методом наименьшей стоимости
На основе транспортной таблицы (табл. 4) построим вспомогательную таблицу (табл. 5), в верхнем правом углу каждой клетки которой будем записы-
вать стоимости перевозки. Введем в таблицу вспомогательную строку и столбец для записи остатков.
Определим клетку таблицы (табл. 5), которой соответствует наименьшая стоимость перевозки. Таких клеток две: С2г ~ 1 и С33 = 1, поэтому выберем любую из этих клеток, например, С22 и запишем в нее значение
х\2 = min (1S2, Р2) = min (45, 10) = 10.
Рассуждаем так: в S2 имеется 45 единиц товара, в К2 требуется 10. Организуем перевозку из S2 в К2, т.е. запишем в клетку значение х22 = Ю (табл. 6). В S2 осталось 45-10 = 35 ед. товара, спрос К2 полностью удовлетворен. Остатки по строке и столбцу запишем в соответствующие клетки столбца и строки остатков: в S2 - 35, а в К2 — О.Так как в столбце К2 остаток равен нулю, этот столбец закрывается и далее не рассматривается (табл. 6).
Табл. 5
Остатки |
Ki |
|
|
|
|
Склады |
Магазины |
||||
Si |
Кх =30 |
К2 =10 |
^з = 30 |
£ II U) о |
|
|
S, = 25 |
3 |
5 |
2 |
2 |
|
S2 = 45 |
6 |
1 |
4 |
3 |
|
S3 = 30 |
2 |
3 |
1 |
4 |
Табл. 6
Остатки |
Ki |
|
0 |
|
|
Склады |
Магазины |
||||
Si |
о m I' |
0 11 |
II
|
^4 = 30 |
|
|
S, =25 |
3 |
5 |
2 |
2 |
35 |
S2 = 45 |
6 |
1 10 |
4 |
3 |
|
S3 = 30 |
2 |
3 |
1 |
4 |
В табл. 6 ищем клетку, в которой записана наименьшая стоимость перевозки (за исключением клеток закрытого столбца К2). Это клетка С33. В нее запишем значение Х33 = min (30, 30) = 30. Определим остатки для строки S3 и столбца К?,. Остаток по строке S3 равен 30-30 = 0, остаток по столбцу К3 30-30 =