Разработка оптимального плана поставок - Курсовая работа

Теория массового обслуживания - область прикладной математики, занимающаяся анализом процессов в системах производства, обслуживания, управления, в которых однородные события повторяются многократно, например, на предприятиях бытового обслуживания; в системах приема, переработки и передачи информации; автоматических линиях производства и др. Задача теории массового обслуживания - установить зависимость результирующих показателей работы системы массового обслуживания (вероятности того, что заявка будет обслужена; математического ожидания числа обслуженных заявок и т.д.) от входных показателей (количества каналов в системе, параметров входящего потока заявок и т.д.). Характерным примером систем массового обслуживания могут служить заправочные станции, и задачи теории массового обслуживания в данном случае сводятся к тому, чтобы установить оптимальное соотношение между числом поступающих на заправочную станцию требований на обслуживание и числом обслуживающих устройств, при котором суммарные расходы на обслуживания и убытки от простоя были бы минимальными. Случайный характер потока заявок и времени их обслуживания приводит к неравномерности загрузки СМО - перегрузке с образованием очередей заявок или недогрузке - с простаиванием ее каналов. В СМО с неограниченным временем ожидания очередное требование, застав все устройства занятыми, становится в очередь и ожидает обслуживания до тех пор, пока одно из устройств не освободится.Оптимальное распределение груза между пунктами отправления и пунктами назначения, т.е. план перевозок, следующее: из A1 в B2 перевезут 10 единиц груза, в B6 - 60 единиц груза.

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

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

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

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

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

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

1. Теоретическая часть

1.1 Системы массового обслуживания и их параметры

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

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

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

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

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

После обслуживания заявки канал освобождается и готов к приему следующей заявки. Случайный характер потока заявок и времени их обслуживания приводит к неравномерности загрузки СМО - перегрузке с образованием очередей заявок или недогрузке - с простаиванием ее каналов.

Эффективность функционирования СМО характеризуют три основные группы параметров: 1.1.2) Эффективность использования СМО - абсолютная или относительная пропускные способности, средняя продолжительность периода занятости СМО, коэффициент использования СМО, коэффициент не использования СМО;

1.1.3) Качество обслуживания заявок- среднее время (среднее число заявок, закон распределения) ожидания заявки в очереди или пребывания заявки в СМО; вероятность того, что поступившая заявка немедленно примется к исполнению;

1.1.4) Эффективность функционирования пары СМО потребитель, причем под потребителем понимается как совокупность заявок или их некоторый источник (например, средний доход, приносимый СМО за единицу времени эксплуатации, и др.).

1.2 Классификация СМО и их основные элементы

СМО классифицируются на разные группы в зависимости от состава и от времени пребывания в очереди до начала обслуживания, и от дисциплины обслуживания требований.

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

1.2.2) По времени пребывания требований в очереди до начала обслуживания системы делятся на три группы: 1.2.3) с неограниченным временем ожидания (с ожиданием), 1.2.4) с отказами;

1.2.5) смешанного типа.

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

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

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

1.2.6) Так же системы СМО делятся по количеству поступающих требований в один момент времени - на системы с одинарным и неординарным потоками требований.

1.2.7) По связи между требованиями.

Такие системы делятся на системы: С последействием, и без последействия.

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

1.2.8) По характеру обслуживания требования в системе делятся на с детерминированным выбором обслуживания и случайным.

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

2. Практическая часть

2.1 Разработать оптимальный план поставок

Постановка задачи.

Имеется четыре пункта отправления (Завода) A1, A2, A3, A4 в которых сосредоточены запасы бензина в количестве 70, 80, 50, 60 единиц. Имеется шесть пунктов назначения (Бензохранилища) B1, B2, B3, B4, B5, B6 подавших заявки на 40, 30, 50, 20, 50, 70 единиц груза. Сумма всех заявок равна сумме всех запасов.

Известны стоимости перевозки единицы груза от каждого пункта отправления Ai, до каждого пункта назначения Bj; ( i=1, 2, 3, 4; j=1, 2, 3, 4, 5, 6);

Считается, что стоимость перевозки нескольких единиц груза пропорциональна их числу.

Таблица 1

Заводы Бензохранилища Запасы

B 1 B 2 B 3 B 4 B 5 B 6

A 1 15 18 - 15 - 20 - 18 70

A 2 - 25 - 30 - 20 12 16 22 80

A 3 - 20 - 25 - 18 - 20 - 18 25 50

A 4 - 18 - 20 15 - 16 15 - 60

Заявки 40 30 50 20 50 70 260

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

2.2 Построение математической модели

Обозначим через Xij, - количество единиц груза, отправляемого из i - ого завода Ai, в j - ое бензохранилище Bj. Эти неотрицательные переменные должны удовлетворять следующим условиям.

Суммарное количество груза, направляемого из каждого завода во все бензохранилища, должно быть равно запасу груза в данном пункте: X1,1 X1,2 X1,4 X1,5 X1,6=70, X2,1 X2,2 X2,3 X2,4 X2,5 X2,6=80, (2.2.1)

X3,1 X3,2 X3,3 X3,4 X3,5 X3,6=50, X4,1 X4,2 X4,3 X4,4 X4,5=60;

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

X1,1 X2,1 X3,1 X4,1=40, X1,2 X2,2 X3,2 X4,2=30, X2,3 X3,3 X4,3=50, (2.2.2)

X1,4 X2,4 X3,4 X4,4=20, X1,5 X2,5 X3,5 X4,5=50, X1,6 X2,6 X3,6=70;

Суммарная стоимость всех перевозок, то есть сумма величин Xij, умноженных на соответствующие стоимости, должна быть минимальной: Y=15X1,1 18X1,2 15X1,4 20X1,5 18X1,6 25X2,1 30X2,2 20X2,3 12X2,4 16X2,5 22X2,6 20X3,1 25X3,2 18X3,3 20X3,4 18X3,5 25X3,6 18X4,1 20X4,2 15X4,3 16X4,4 15X4,5 (2.2.3)

2.3 Нахождение опорного решения

Составим опорный план, применив метод «Минимального элемента».

Минимальная цена поставки находится в ячейке A2B4 и равна 12, то есть из незадействованных маршрутов, этот маршрут доставки является наиболее рентабельным. Запасы завода A2 составляют 80 единиц продукции. Потребность потребителя B4 составляет 20 единиц продукции. От поставщика A2 к потребителю B4 будем доставлять min = {80 , 20} = 20 единиц продукции. Разместим в ячейку A2B4 значение равное 20. Мы полностью удовлетворили потребность потребителя B4. Вычеркиваем столбец 4 таблицы, т. е. исключаем его из дальнейшего рассмотрения.

Минимальная цена поставки находится в ячейке A1B1 и равен 15. Запасы поставщика A1 составляют 70 единиц продукции. Потребность потребителя B1 составляет 40 единиц продукции. Min = {70 , 40} = 40 единиц продукции. Разместим в ячейку A1B1 значение равное 40 и исключим столбец 1 из дальнейшего рассмотрения.

Минимальная цена поставки находится в ячейке A4B3 и равен 15. Min = {60, 50} = 50 единиц продукции. Разместим в ячейку A4B3 значение равное 50, и исключаем столбец 3 из дальнейшего рассмотрения.

Минимальная цена поставки находится в ячейке A4B5 и равен 15, min = {10 , 50} = 10 единиц продукции. Разместим в ячейку A4B5 значение равное 10, и исключаем строку 4 из дальнейшего рассмотрения, так как план полностью выполнен.

Минимальная цена поставки находится в ячейке A2B5 и равен 16, Min = {60 , 40} = 40 единиц продукции. Разместим в ячейку A2B5 значение равное 40, и исключаем столбец 5 из дальнейшего рассмотрения.

Рассуждая, таким образом, заполним транспортную таблицу перевозками Xi,j до конца.

Таблица 2

Заводы Бензохранилища Запасы

B 1 B 2 B 3 B 4 B 5 B 6

A 1 40 15 30 18 - 0 15 - 20 - 18 70

A 2 - 25 - 30 - 20 20 12 40 16 20 22 80

A 3 - 20 - 25 - 18 - 20 - 18 50 25 50

A 4 - 18 - 20 50 15 - 16 10 15 - 60

Заявки 40 30 50 20 50 70 260

Проверим, является ли этот план допустимым: да, потому что в нем сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу - заявке соответствующего пункта назначения. Значит, все заявки удовлетворены, все запасы израсходованы (сумма запасов равна сумме заявок и выражается числом 260, стоящим в правом нижнем углу таблицы).

В таблицах будем проставлять отличные от нуля перевозки, а клетки, соответствующие нулевым перевозкам, оставляем «свободными». Проверим, является ли план перевозок, данный в таблице -----, опорным. Число свободных клеток с нулевыми перевозками равно (4-1)(6-1)=3*5=15, так что план опорный.

Общие затраты для этого плана составят: L1= 15 * 40 18 * 30 12 * 20 16 * 40 22 * 20 25 * 50 15 * 50 15 * 10 = 4610 у.е.

2.4 Оптимизация задачи методом отрицательных циклов

Этот план можно улучшить, если произвести в нем «циклическую перестановку» перевозок между клетками таблицы, уменьшив перевозки в «дорогой клетке» (3.6) со стоимостью 25, но зато увеличив перевозки в «дешевой» (3.5) со стоимостью 18.

Таблица 3

Заводы Бензохранилища Запасы

B 1 B 2 B 3 B 4 B 5 B 6

A 1 40 15 30 18 - 0 15 - 20 - 18 70

A 2 - 25 - 30 - 20 20 12 40 16 20 22 80

A 3 - 20 - 25 - 18 - 20 - 18 50 25 50

A 4 - 18 - 20 50 15 - 16 10 15 - 60

Заявки 40 30 50 20 50 70 260

Чтобы план оставался опорным, необходимо сделать одну из свободных клеток базисной, а одну из базисных - свободной. По циклу (3.5) -> (2.5) -> (2.6) -> (3.6) можно перенести не более 40 единиц груза.

Таким образом, стоимость перевозок уменьшилась на 18-25 22-16=-1*40=-40

L2=4610 (-40) =4570у.е.

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

Таблица 4

Заводы Бензохранилища Запасы

B 1 B 2 B 3 B 4 B 5 B 6

A 1 40 15 30 18 - - 15 - 20 - 18 70

A 2 - 25 - 30 - 20 20 12 16 60 22 80

A 3 - 20 - 25 - 18 - 20 40 18 10 25 50

A 4 - 18 - 20 50 15 - 16 10 15 - 60

Заявки 40 30 50 20 50 70 260

Таким образом, переносим 10 единиц груза из более «дорогой» клетки, в более «дешевую», при этом цена цикла уменьшится и будет равна: 20-25 18-15=-2*10=-20 L3=4570 (-20) =4550у.е;

Еще раз улучшим план стоимости перевозок.

Таблица 5

Заводы Бензохранилища Запасы

B 1 B 2 B 3 B 4 B 5 B 6

A 1 30 15 30 18 - 15 - 20 10 18 70

A 2 - 25 - 30 - 20 20 12 - 16 60 22 80

A 3 10 20 - 25 - 18 - 20 40 18 - 25 50

A 4 - 18 - 20 50 15 - 16 10 15 - 60

Заявки 40 30 50 20 50 70 260

В результате этого циклического переноса мы переносим из более «дорогих» клеток 30 единиц груза в более «дешевые».

Таким образом, цена цикла становится равна: 16-22 18-15 20-18=-1*30=-30 L4=4550 (-30) =4520 у.е.

Таблица 6

Заводы Бензохранилища Запасы

B 1 B 2 B 3 B 4 B 5 B 6

A 1 - 15 30 18 - 15 - 20 40 18 70

A 2 - 25 - 30 - 20 20 12 30 16 30 22 80

A 3 40 20 - 25 - 18 - 20 10 18 - 25 50

A 4 - 18 - 20 50 15 - 16 10 15 - 60

Заявки 40 30 50 20 50 70 260

Улучшим план поставок.

Таблица 7

Заводы Бензохранилища Запасы

B 1 B 2 B 3 B 4 B 5 B 6

A 1 - 15 20 18 - 15 - 20 50 18 70

A 2 - 25 - 30 - 20 20 12 40 16 20 22 80

A 3 40 20 - 25 - 18 - 20 10 18 - 25 50

A 4 - 18 10 20 50 15 - 16 - 15 - 60

Заявки 40 30 50 20 50 70 260

Цена цикла будет равна: 20-15 16-22 18-18=-1*10=-10

L5=4520 (-10) =4510 у.е.

Таблица 8

Заводы Бензохранилища Запасы

B 1 B 2 B 3 B 4 B 5 B 6

A 1 - 15 10 18 - 15 - 20 60 18 70

A 2 - 25 - 30 - 20 20 12 50 16 10 22 80

A 3 40 20 - 25 10 18 - 20 - 18 - 25 50

A 4 - 18 20 20 40 15 - 16 - 15 - 60

Заявки 40 30 50 20 50 70 260

Цена цикла будет равна: 18-18 16-22 18-18 20-15=-1*10=-10

L6=4510 (-10) =4500 у.е.

В данной таблице отрицательные циклы отсутствуют, следовательно, данное решение будет являться оптимальным.

Оптимальная стоимость плана составит 4500 у.е.

2.5 Проверка решения задачи с использованием системы Mathcad

Критерий оптимизации - целевая функция

Y(X1,1,X1,2,X1,4,X1,5,X1,6,X2,1,X2,2,X2,3,X2,4,X2,5,X2,6,X3,1,X3,2,X3,3,X3,4,X3,5,X3,6,X4,1,X4,2,X4,3,X4,4,X4,5):=15X1,1 18X1,2 15X1,4 20X1,5 18X1,6 25X2,1 30X2,2 20X2,3 12X2,4 16X2,5 22X2,6 20X3,1 25X3,2 18X3,3 20X3,4 18X3,5 25X3,6 18X4,1 20X4,2 15X4,3 16X4,4 15X4,5;

Начальные приближения

X1,1:=0 X1,2:=0 X1,4:=0 X1,5:=0 X1,6:=0

X2,1:=0 X2,2:=0 X2,3:=0 X2,4:=0 X2,5:=0 X2,6:=0

X3,1:=0 X3,2:=0 X3,3:=0 X3,4:=0 X3,5:=0 X3,6:=0

X4,1:=0 X4,2:=0 X4,3:=0 X4,4:=0 X4,5:=0

Given

Система ограничений

X1,1 X1,2 X1,4 X1,5 X1,6=70, X2,1 X2,2 X2,3 X2,4 X2,5 X2,6=80, X3,1 X3,2 X3,3 X3,4 X3,5 X3,6=50, X4,1 X4,2 X4,3 X4,4 X4,5=60;

X1,1 X2,1 X3,1 X4,1=40, X1,2 X2,2 X3,2 X4,2=30, X2,3 X3,3 X4,3=50, X1,4 X2,4 X3,4 X4,4=20, X1,5 X2,5 X3,5 X4,5=50, X1,6 X2,6 X3,6=70;

Граничные условия

X1,1?0 X1,2?0 X1,4?0 X1,5?0 X1,6?0

X2,1?0 X2,2?0 X2,3?0 X2,4?0 X2,5?0 X2,6?0

X3,1?0 X3,2?0 X3,3?0 X3,4?0 X3,5?0 X3,6?0

X4,1?0 X4,2?0 X4,3?0 X4,4?0 X4,5?0

Найти оптимальное решение

X1,1

X1,2

X1,4

X1,5

X1,6

X2,1

X2,2

X2,3 := Minimize(Y, X1,1,X1,2,X1,4,X1,5,X1,6,X2,1,X2,2,X2,3,X2,4,X2,5,X2,6,X3,1,X3,2, X2,4 X3,3,X3,4,X3,5,X3,6,X4,1,X4,2,X4,3,X4,4,X4,5);

X2,5

X2,6

X3,1

X3,2

X3,3

X3,4

X3,5

X3,6

X4,1

X4,2

X4,3

X4,4

X4,5

X1,1 0

X1,2 10

X1,4 0

X1,5 0

X1,6 60

X2,1 0

X2,2 0

X2,3 0

X2,4 20

X2,5 50

X2,6 = 10

X3,1 40

X3,2 0

X3,3 10

X3,4 0

X3,5 0

X3,6 0

X4,1 0

X4,2 20

X4,3 40

X4,4 0

X4,5 0

Определить величину целевой функции для оптимального решения план поставка оптимизация задача

Y(X1,1,X1,2,X1,4,X1,5,X1,6,X2,1,X2,2,X2,3,X2,4,X2,5,X2,6,X3,1,X3,2,X3,3,X3,4,X3,5,X3,6,X4,1,X4,2,X4,3,X4,4,X4,5) = 4500 у.е;

Оптимальное распределение груза между пунктами отправления и пунктами назначения, т.е. план перевозок, следующее: из A1 в B2 перевезут 10 единиц груза, в B6 - 60 единиц груза. Из A2 в B4 перевезут 20 единиц груза, в B5 - 50 единиц, в B6 - 10 единиц. Из A3 в B1 перевезут 40 единиц груза, в B3 - 10 единиц. Из A4 в B2 перевезут 20 единиц, в B3 - 40 единиц. Общая стоимость всех перевозок будет минимальна и составит 4500 у.е.

1) Гмурман, В.Е. Теория вероятностей и математическая статистика / В.Е. Гмурман. М.: «Высшая школа», 2003.

2) Лаврусь, О.Е. Теория массового обслуживания. Методические указания/ О.Е. Лаврусь, Ф.С. Миронов. Самара: САМГАПС, 2005.

3) Авсиевич, А.В. Теория массового обслуживания. Потоки требований, системы массового обслуживания / А.В. Авсиевич, Е.Н. Авсиевич. Самара: САМГАПС. 2007 г.

4) Черненко, В.Д. Высшая математика в примерах и задачах. В 3. т. Т. 3/ В.Д. Черненко. Санкт - Петербург: Политехника, 2006.

5) Олзоева, С.И. Моделирование и расчет распределенных информационных систем. Учебное пособие / С.И. Олзоева. Улан-Удэ: ВСГТУ, 2009.

6) Системы массового обслуживания и их применение в логистике http://www.kt-lospo.com/study/l_3_5.htm

7) Моделирование систем массового обслуживания http://stratum.ac.ru/textbooks/modelir/lection30.html

8) Теория массового обслуживания http://ru.wikipedia.org/

9) Построение математических моделей при решении задач оптимизации http://studyport.ru/tochnyie-nauki/postroenie-matematicheskih-modeley-pri-reshenii-zadach-optimizatsii.

Размещено на