2.3. Методические указания для выполнения практической части работы
Практическое задание, которое необходимо выполнить во второй части работы, является комплексом объединенных общей темой задач по управлению цепями поставок в логистических системах. Для их выполнения необходимо изучить методы и модели линейного, целочисленного программирования и сетевой оптимизации, а также методики решения задач оптимального планирования перевозок, производственного планирования, выбора маршрута транспортировки грузов, управления запасами при интегрированном планировании цепей поставок. Далее приводится краткое описание основных методик решения задач в управлении цепями поставок с использованием доступного программного продукта Microsoft Excel.
2.3.1 Методика решения задачи по определению кратчайшего пути
доставки материальных средств в логистических цепях
А) Исходные данные
Задача о кратчайшем пути состоит в нахождении связанных между собой транспортных коммуникаций на транспортной сети, которые в совокупности имеют минимальную длину от исходного пункта до пункта назначения. В данном разделе рассматриваются различные случаи в логистических цепях, которые можно промоделировать и решить как задачу о кратчайшем пути.
Пусть задана транспортная сеть (рисунок 1), состоящая из станций А0, А1 и т.д. и коммуникаций, соединяющих некоторые из этих станций.
Рисунок 1 – Принципиальная схема транспортной сети.
Длины коммуникаций предполагаются известными и равными Cij. Если станции Аi и Аj непосредственно не соединены друг с другом, предполагаем что Сij равна бесконечности. Из начальной станции А0 на конечную станцию Аn+1 можно попасть через большое количество путей, проходящих через разные промежуточные станции. Требуется выделить из всех путей путь наименьшей длины. Поясним, что длины коммуникаций могут означать время движения, стоимость перевозок от станции до станции, вероятности своевременной перевозки груза от станции до станции и др.
Б). Экономико-математическая модель решения задачи
Приведем в соответствии каждой паре пунктов Аi и Аj величины Хij.
Если участок АiАj принадлежит кратчайшему пути Хij=1 и, Хij =0 в противном случае. Задача о кратчайшем пути в таком случае может быть сведена к выбору чисел Хij, для которых сумма произведений длины дуг на искомые переменные Хij стремится к минимуму при условиях:
(1)
(2)
(3)
(4)
(5)
Условие (2) соответствует тому, что число коммуникаций, принадлежащих критическому пути и в ходящих в любой промежуточный пункт равно числу коммуникаций исходящих из этого пункта и принадлежащих критическому пути.
Условие (3) означает, что количество коммуникаций из исходного пункта А0 превышает на единицу число коммуникаций входящих в исходный пункт.
Аналогичным образом условие (4) свидетельствует о том, что в конечный пункт Аn+1 входит на одну коммуникацию больше, чем выходит.
Вместе с условием (2) и требованием минимизации целевой функции (1) условия (3) и (4) означают, что на каждую станцию Аi приходит ровно одна коммуникация и из каждой станции Аi исходит ровно одна коммуникация.
Условие (5) в задаче эквивалентно требованию, согласно которому все значения Хij равны нулю или единице.
Таким образом, соотношения (1)-(5) определяет кратчайший путь в сети. Необходимо еще раз отметить, что в качестве длин дуг могут быть не только километры, но и другие показатели, например стоимости, время и т.д.
В). Решение задачи по определению кратчайшего пути
Подготовительный этап
1). Преобразуем граф сети к матричной форме
С этой целью строим две таблицы – «Дуги» и «Узлы» (рисунок 2).
В таблице «Дуги» выделяем 4 столбца:
1-й столбец – «дуга», предназначен для заполнения значениями искомых переменных Хij.
2-й столбец – «начало», обозначает исходные и промежуточные узлы сети, из которых выходят коммуникации (например, из узла 1 выходят 3 коммуникации).
3-й столбец – «конец», предназначен для обозначения узлов промежуточных и конечных пунктов или станций, в которые входят коммуникации.
4-й столбец – «длина», предназначен для указания протяженности дуг, соединяющих узлы друг с другом.
В таблице Узлы:
1-й столбец – «узел», в нем размещается информация о номерах всех узлов, последовательно от исходного пункта до пункта стока или конечного пункта.
Рисунок 2 – Исходные таблицы «дуги» и «узлы».
2-й столбец – «входят», заполняется автоматически в процессе решения задачи. Алгоритм решения основан на выборе кратчайшего расстояния до следующего узла с учетом суммы расстояний до предыдущего узла и длины коммуникаций до узла, следующего за предыдущим.
Тоже самое относится и к 3-му столбцу – «выходят».
4-й столбец – «сумма», предназначен для расчета значений ограничений.
5-й столбец – ограничение – предназначен для обозначения исходного, конечного и промежуточных пунктов. Соответствующему номеру узла присваивается значение, 1 - если этот узел является исходным пунктом, 0 - если узел является промежуточным пунктом и -1 - если узел является конечным пунктом (условия (2), (3), (4)).
2). Заполняем формулами таблицу «Дуги» для вычисления длины кратчайшего пути. С этой целью:
выделяем ячейку, в которой мы хотим разместить значения длины кратчайшего пути, а затем вызываем «мастер функций» нажав на иконку fx на панели инструментов. В открывшемся окне в категории математические выбираем функцию СУММПРОИЗВ (рисунок 3);
Рисунок 3 – Работа в окне «Мастер функций»
в строку Массив 1 (рисунок 4) вводим значения длин дуг, выделив столбец «длина» в таблице «дуги»;
Рисунок 4 – Ввод аргументов функции СУММПРОИЗВ
устанавливаем курсор в строку «массив 2» в окне Аргументы функции и вводим значения столбца – «Дуга» из таблицы «Дуги» и нажимаем ОК.
На этом ввод формул для таблицы «Дуги» закончен.
3). Заполняем формулами таблицу «Узлы». С этой целью:
для расчета значений в столбце «Входят», устанавливаем курсор в ячейку на пересечении соответствующего узла 1 и столбца «Входят» и активируем ее, щелкнув левую кнопку мыши;
вызываем мастер функций и в категории «математические» выбираем функцию «СУММЕСЛИ»;
заполняем строку «Диапазон» в аргументах функции (рисунок 5) для чего вводим в эту строку значение массива конец из таблицы «Дуги»;
Рисунок 5 – Заполнение аргументов функции «СУММЕСЛИ»
переводим курсор в строку «критерии» в окне «Аргументы функции» и вводим значение, соответствующее номеру узла в строке таблицы «Узлы» (в нашем случае это значение ячейки F3;
устанавливаем курсор в строку «диапазон суммирования» и вводим значения столбца «Дуга» (А3:А13) из таблицы «Дуги» (рисунок 5);
нажимаем ОК и переходим к вводу формулы «СУММЕСЛИ» в столбце «входят» следующего второго узла, при этом Аргументы функции, за исключением критерия, остаются прежними, а критерий соответствует следующему номеру узла. Аналогично вводим формулу для всех оставшихся узлов в столбце «Входят».
Переходим к заполнению формулами столбца «Выходят», для чего:
устанавливаем курсор и выделяем ячейку на пересечении строки, соответствующей узлу 1 и столбцу «Выходят»;
вызываем мастер функций и в категории математические выбираем функцию «СУММЕСЛИ»;
в появившемся окне «Аргументы функции» устанавливаем курсор в строку диапазон и вводим значения столбца (массива) «Начало» из таблицы «Дуги»;
устанавливаем курсор в строку «Критерий» в окне «Аргументы функции» и вводим значение критерия, которое соответствует значению номера узла 1 из таблицы «Узлы»;
устанавливаем курсор в «Диапазон суммирования» в окне «Аргументы функции» и вводим значение диапазона суммирования, соответствующее значениям столбца «Дуга» из таблицы «Дуги». Нажимаем ОК. Аналогично вводим формулы в оставшиеся ячейки столбца «Выходят». При этом все аргументы функции, за исключением критерия, остаются прежними. Меняется лишь численное значение критерия, которое соответствует номеру следующего узла (рисунок 6).
Рисунок 6 – Ввод формул в столбец «Выходят»
Переходим к заполнению формулами столбца «сумма». С этой целью:
выделяем ячейку на пересечении строки, соответствующей узлу 1 и столбцу «Сумма». Нажимаем знак «=», устанавливаем курсор в этой же строке в столбце «Выходят» и нажимаем знак «минус»;
устанавливаем курсор в этой же строке в столбце «Входят», нажимаем «ENTER» (рисунок 7);
копируем формулу в остальные ячейки столбца «Сумма». Для этого выделяем ячейку, в которую мы только что вводили формулу и нажимаем «Копировать» на панели инструментов. Затем выделяем остальные ячейки в столбце «Сумма» и нажимаем «Вставить» на панели инструментов.
Далее заполняем данными столбец «Ограничения» (рисунок 8). При этом в ячейке на пересечении столбца «Сумма» и строки, соответствующей каждому узлу, проставляем значение 1, если этот узел является исходным пунктом, значение 0, если узел является промежуточным и -1, если пункт будет конечным узлом (стоком).
На этом ввод формул в таблицу «Узлы» считается завершенным.
Рисунок 7 – Ввод формул в столбец «Сумма»
Рисунок 8 – Ввод данных в столбец «Ограничения»
Вычислительный этап
1). Устанавливаем курсор в ячейку, в которую будет помещено значение кратчайшего пути.
2). Запускаем программу «Поиск решения» командой Данные/Анализ/Поиск решения (Excel 2007) или Сервис/Поиск решения (Excel 2003 и ниже).1
3). В окне поиск решения (рисунок 9) устанавливаем целевую ячейку, соответствующую номеру ячейки, в которой будет помещена длина кратчайшего пути.
4). Выбираем равенство этой ячейки минимальному значению и устанавливаем курсор в строку «изменяя ячейки».
5). Вводим в строку «изменяя ячейки» столбец (массив) «Дуга» из таблицы «Дуги».
Рисунок 9 – Работа в окне «Поиск решения»
5). Устанавливаем курсор в окно «Ограничения» и справа от этого окна нажимаем кнопку «Добавить» (рисунок 9).
6). В окно «Ссылка на ячейку» (рисунок 10) вводим значения столбца «Сумма» из таблицы «Узлы».
7). В следующем окне (справа) выбираем знак «<=» и устанавливаем курсор в окно «Ограничения».
Рисунок 10 – Работа в окне «Добавление ограничения»
8). Вводим ограничения, выделив столбец «Ограничения» в таблице «Узлы».
9). Нажимаем кнопку ОК.
10). В окне «Поиск решения» нажимаем кнопку «Параметры», оставляем стандартные условия без изменения. Ставим галочку в чекбоксах «Линейная модель» и «Неотрицательные значения переменных». После чего нажимаем ОК (рисунок 11).
11). Нажимаем кнопку «Выполнить» в окне «Поиск решения» и в появившемся окне результаты поиска решения нажимаем ОК (рисунок 12).
Рисунок 11 – Установка параметров поиска решения
Анализ результатов расчетов
Данные по решению задачи находятся в таблице «Дуги». Так в столбце «Дуга» размещены значения искомых переменных. Если они равны 0, то соответствующая дуга в строке таблицы не принадлежит кратчайшему пути. Если это значение равно 1 то дуга, соединяющая соответствующие узлы находится на кратчайшем пути. В рассматриваемой задаче минимальное расстояние (протяженность, стоимость, время) в 13 ед. обеспечивается при движении пот маршруту 1, 2, 5, 7.
Рисунок 12 – Результаты поиска решения