Меню
Главная
Авторизация/Регистрация
 
Главная arrow Математика, химия, физика arrow Дискретная оптимизация. Модели, методы, алгоритмы решения прикладных задач

Оптимальный выбор поставщиков

Пусть требуется заключить контракты на поставку некоторого товара. Необходимое количество товара обозначим Ь. Товар можно получить от нескольких поставщиков (i=l,2,...,n), причём от каждого из них можно получить несколько партий товара (xi=0, 1,2,...,л). В каждой партии содержится определённое количество товара ai >0, причём объём партии ai у различных поставщиков различный, также как и зависимость стоимости поставки от количества поставляемых партий Ci(xi)>0. Требуется выбрать одного или нескольких поставщиков, так чтобы обеспечить суммарный объём поставок за минимальную стоимость.

Это означает, что нужно найти такие целые числа Xi, которые дают

Может быть предложено простое решение данной задачи: заключить контракт с тем поставщиком, который обеспечит поставку всего товара за минимальную стоимость, а всех остальных поставщиков игнорировать. Однако при нелинейных зависимостях Ci(xi) это решение может оказаться не оптимальным. Следующий простой пример доказывает это. Нужно 100 единиц товара. Каждый из двух поставщиков продаёт товар партиями по 50 единиц, причём у первого из них одна партия стоит 1000 у.е., а две партии 1975 у.е., а у другого соответственно 960 и 1970. Оказывается выгоднее у каждого из них заказать по одной партии товара при суммарной стоимости 1960 у.е.

При большом числе поставщиков и различных объёмах партий оптимальный выбор далеко не очевиден.

Данная задача также может быть решена по методу динамического программирования.

Решение разбивается на п этапов по числу возможных поставщиков. На каждом j-ом этапе состояние системы - это суммарное количество уже заказанного товара а оценка этого состояния Sj- суммарные затраты на переход из начального состояния (0,0) в данное (bj,Sj). Переход на следующий этап (управление в терминологии [6]) - это приобретение соответствующего количества партий товара у очередного поставщика. Последовательность рассмотрения поставщиков существенного значения не имеет.

Если Xi =0 или 1, то математическая модель данной задачи (4.2) в точности такая же, что и в задаче оптимального использования транспортных средств (см. раздел 4.1). Наличие другого знака неравенства в 4.2 принципиального значения не имеет. На каждом шаге рассматриваются все те же состояния, что и при знаке <, плюс одно состояние с равенством или превышением Ь. На последнем шаге рассматривается переход только в такое состояние.

Эта задача в многочисленных источниках решалась по методу динамического программирования при рассмотрении регулярной сетки состояний. Однако, как мы установили в разд. 4.1, она может существенно более эффективно решаться по методу динамического программирования с использованием множеств Парето (минимум стоимости при максимуме товара). Возможность отбраковки не только путей, приводящих в данное состояние, но и неэффективных состояний была установлена нами даже в более простой задаче об оптимальной загрузке машины [6].

 
Посмотреть оригинал
Если Вы заметили ошибку в тексте выделите слово и нажмите Shift + Enter
< Пред   СОДЕРЖАНИЕ ОРИГИНАЛ   След >
 

Популярные страницы