Б. М. Шлаин Россия, Москва, Московский инженерно-физический институт использование интернет-сервисов для автоматизации бизнес-процессов на примере задачи выбора поставщиков доклад

Вид материала

Содержание

Условия, при котором производится пересчет оценок поставщиков в связи с изменением решения.
Необходимость упорядочения поставщиков, подлежащих рассмотрению.
Условия добавления поставщика для данного товара при отсутствии товара в решении.
Условия замены поставщика для данного товара при наличии товара в решении.
Вид характеристической функции и ее изменение в ходе решения.
Таблица 1. Состав заказа
Epson lq 100
Таблица 2. Решения задачи.

Подобный материал:

Г.Л. Вайсман, А.В. Меньков, Б.М. Шлаин

Россия, Москва, Московский инженерно-физический институт

ИСПОЛЬЗОВАНИЕ ИНТЕРНЕТ-СЕРВИСОВ
ДЛЯ АВТОМАТИЗАЦИИ БИЗНЕС-ПРОЦЕССОВ
НА ПРИМЕРЕ ЗАДАЧИ ВЫБОРА ПОСТАВЩИКОВ

(Доклад)

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

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

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

Такая реализация оправдана в следующих случаях:

Для решения задач используется нуждающаяся в частом обновлении общая для всех клиентов база данных;
Соответствующие задачи решаются предприятием достаточно редко;
Необходимая информация может быть передана через Интернет.

С другой стороны, программное обеспечение при реализации сервиса в Интернете должно удовлетворять специфическим требованиям:

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

Задача выбора поставщиков.

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

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

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

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

Имеется множество из N фирм-поставщиков. Необходимо разместить среди них заказ, который задается множеством пар (наименование товара; количество товара). Для каждого поставщика определена цена на каждый товар, который есть в ассортименте данного поставщика. На практике практически всегда выдвигают дополнительное условие: покупать товар одного типа только у одного поставщика. Под решением в этом случае понимается набор пар (фирма; наименование товара). Пусть S – суммарная стоимость заказа при приобретении товаров в фирмах, входящих в решение, по минимально возможным ценам, а Q – общее количество фирм, включенных в решение.

Практическая задача подбора поставщиков может быть сведена к одной из трех строгих постановок:

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

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

Эвристические методы решения задачи выбора поставщиков.

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

Общая последовательность действий выглядит следующим образом:

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

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

Условия, при котором производится пересчет оценок поставщиков в связи с изменением решения. При добавлении в решение нового поставщика изменяется состав заказа. Следовательно, может измениться полезность каждого из еще нерассмотренных поставщиков. При этом значения характеристической функции можно не пересчитывать, пересчитывать всегда после изменения решения и пересчитывать только в тех случаях, когда заказ сокращается «существенно». В этой связи возникает необходимость оценить понятие «существенного изменения».
Необходимость упорядочения поставщиков, подлежащих рассмотрению. Если пересчет оценок поставщиков производится редко, следует упорядочивать их или, по меньшей мере, находить несколько лучших. Если пересчет оценок поставщиков происходит каждый раз при изменении решения, можно находить только лучшую фирму из оставшихся.
Условия добавления поставщика для данного товара при отсутствии товара в решении. Важно определить, готовы ли мы покупать товар по любой цене, или существует верхний предел. В последнем случае наличие товара у поставщика с наилучшей оценкой не означает автоматически, что он будет в ней приобретен, – это произойдет только тогда, когда он «не слишком дорог».
Условия замены поставщика для данного товара при наличии товара в решении. В ходе решения задачи возможен случай, когда добавление нового поставщика в решение позволит купить товар, который уже присутствует в решении, по лучшей цене. Это означает, что мы можем улучшить решение за счет тех товаров, которые уже считались рассмотренными. Однако оборотной стороной такого подхода является анализ всех позиций заказа при добавлении фирмы (а не только тех, для которых еще не подобран поставщик). Это увеличит время, необходимое для получения решения; особенно существенной разница во времени будет в случае, когда уже у нескольких первых найденных поставщиков может быть куплена значительная часть заказа.
Вид характеристической функции и ее изменение в ходе решения. В общем случае характеристическая функция зависит от параметров поставщика и текущего заказа. Можно построить алгоритм таким образом, чтобы в процессе поиска решения изменялся сам вид функции или значения параметров. Например, если функция представляет собой свертку различных критериев, по мере поиска решения в зависимости от текущего заказа, решения и общих характеристик еще не рассмотренных поставщиков можно изменить приоритет критериев.

При решении задачи поиска поставщиков была выбрана следующая характеристическая функция: для j-го поставщика

_.

В этой формуле: M_j – множество (номеров) товаров, которые есть в наличии у j-го поставщика; q_i – количество i-го товара в заказе.

p¹_ij - функция, зависящая от жесткости, цены на товар у данного поставщика, минимальной и максимальной цены на данный товар среди всех поставщиков. Функция была подобрана таким образом, что при мягком решении (т.е. когда необходимо приобрести товар по минимальной цене), при отклонении цены от минимальной p¹ отклоняется от минимальной больше, чем сама цена - таким образом поставщик "штрафуется" за "неминимальность" цены. При жестком решении, наоборот, фирма «поощряется» за наличие в ней данного товара, и оценка цены меньше самой цены (штраф в данном случае отрицательный).

p²_ij - это функция, зависящая от жесткости, минимальной и максимальной цены на данный товар среди всех поставщиков. Её можно охарактеризовать как штраф за отсутствие товара у данного поставщика; она оценивает издержки при покупке данного товара в какой-либо другой фирме. Функция была подобрана так, что при мягком решении штраф равен минимальной цене на товар, а при жестком - максимальной цене.

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

В Таблице 1 приведен пример заказа, а в Таблице 2 – стоимость решений, найденных для разных значений жесткости. В качестве источника информации использовалась база данных по предложениям на московском рынке компьютерной техники (по состоянию на весну 1999г.).

Таблица 1. Состав заказа

Наименование товара	Количество в заказе	Минимальная цена	Максимальная цена
Принтер EPSON LQ 100	2	39	158
Принтер HP LASERJET 1100	1	355	429
Тонер для принтера HP LASERJET II/III	6	5	8
Всего по заказу		463	793

Таблица 2. Решения задачи.

Жесткость	Количество фирм в решении	Стоимость решения
Высокая	2	613
Низкая	3	463

Комбинированное применение эвристических алгоритмов и метода ветвей и границ.

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

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

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

для всех i=1,..,N (Частичное решение a доминирует над b, если в нем не больше фирм чем в b, и цена на каждый товар в a не выше чем в b).

При использовании алгоритма ветвей и границ пары вида (a, b) проверяются на предмет принадлежности к D. Повысить эффективность применения правила доминирования можно за счет использование полиномиального эвристического алгоритма. Он позволяет получить множество частичных «хороших решений», которые впоследствии будут использованы в МВГ. «Хорошие вершины» должны быть найдены для частичных решений с различным количеством фирм, чтобы на всех этапах применения МВГ мы располагали такой вершиной. При проверке правила доминирования будем в первую очередь проверять доминирование с соответствующей «хорошей вершиной», что позволит сразу исключить из рассмотрения достаточно большое количество ветвей.

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

Blog

Содержание

Г.Л. Вайсман, А.В. Меньков, Б.М. Шлаин