Составим опорный план, применив метод «Минимального элемента».
Минимальная цена поставки находится в ячейке 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 | |
| A 2 | - 25 | - 30 | - 20 | 20 12 | 40 16 | 20 22 | |
| A 3 | - 20 | - 25 | - 18 | - 20 | - 18 | 50 25 | |
| A 4 | - 18 | - 20 | 50 15 | - 16 | 10 15 | - | |
| Заявки |
Проверим, является ли этот план допустимым: да, потому что в нем сумма перевозок по строке равна запасу соответствующего пункта отправления, а сумма перевозок по столбцу - заявке соответствующего пункта назначения. Значит, все заявки удовлетворены, все запасы израсходованы (сумма запасов равна сумме заявок и выражается числом 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 у.е.
Оптимизация задачи методом отрицательных циклов
Этот план можно улучшить, если произвести в нем «циклическую перестановку» перевозок между клетками таблицы, уменьшив перевозки в «дорогой клетке» (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 | |
| A 2 | - 25 | - 30 | - 20 | 20 12 | 40 16 | 20 22 | |
| A 3 | - 20 | - 25 | - 18 | - 20 | - 18 | 50 25 | |
| A 4 | - 18 | - 20 | 50 15 | - 16 | 10 15 | - | |
| Заявки |
Чтобы план оставался опорным, необходимо сделать одну из свободных клеток базисной, а одну из базисных - свободной. По циклу (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 | |
| A 2 | - 25 | - 30 | - 20 | 20 12 | 60 22 | ||
| A 3 | - 20 | - 25 | - 18 | - 20 | 40 18 | 10 25 | |
| A 4 | - 18 | - 20 | 50 15 | - 16 | 10 15 | - | |
| Заявки |
Таким образом, переносим 10 единиц груза из более «дорогой» клетки, в более «дешевую», при этом цена цикла уменьшится и будет равна:
-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 | - | - 20 | 10 18 | ||
| A 2 | - 25 | - 30 | - 20 | 20 12 | - 16 | 60 22 | |
| A 3 | 10 20 | - 25 | - 18 | - 20 | 40 18 | - 25 | |
| A 4 | - 18 | - 20 | 50 15 | - 16 | 10 15 | - | |
| Заявки |
В результате этого циклического переноса мы переносим из более «дорогих» клеток 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 | - | - 20 | 40 18 | ||
| A 2 | - 25 | - 30 | - 20 | 20 12 | 30 16 | 30 22 | |
| A 3 | 40 20 | - 25 | - 18 | - 20 | 10 18 | - 25 | |
| A 4 | - 18 | - 20 | 50 15 | - 16 | 10 15 | - | |
| Заявки |
Улучшим план поставок.
Таблица 7
| Заводы | Бензохранилища | Запасы | |||||
| B 1 | B 2 | B 3 | B 4 | B 5 | B 6 | ||
| A 1 | - 15 | 20 18 | - | - 20 | 50 18 | ||
| A 2 | - 25 | - 30 | - 20 | 20 12 | 40 16 | 20 22 | |
| A 3 | 40 20 | - 25 | - 18 | - 20 | 10 18 | - 25 | |
| A 4 | - 18 | 10 20 | 50 15 | - 16 | - 15 | - | |
| Заявки |
Цена цикла будет равна:
-15+16-22+18-18=-1*10=-10=4520+ (-10) =4510 у.е.
Таблица 8
| Заводы | Бензохранилища | Запасы | |||||
| B 1 | B 2 | B 3 | B 4 | B 5 | B 6 | ||
| A 1 | - 15 | 10 18 | - | - 20 | 60 18 | ||
| A 2 | - 25 | - 30 | - 20 | 20 12 | 50 16 | 10 22 | |
| A 3 | 40 20 | - 25 | 10 18 | - 20 | - 18 | - 25 | |
| A 4 | - 18 | 20 20 | 40 15 | - 16 | - 15 | - | |
| Заявки |
Цена цикла будет равна:
-18+16-22+18-18+20-15=-1*10=-10=4510+ (-10) =4500 у.е.
В данной таблице отрицательные циклы отсутствуют, следовательно, данное решение будет являться оптимальным.
Оптимальная стоимость плана составит 4500 у.е.
Проверка решения задачи с использованием системы 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,2,4,5,6,1,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,6,1,2,3,4,5,6,1,2,3,4,5
X1,1 0,2 10,4 0,5 0
X1,6 60,1 0,2 0
X2,3 0
X2,4 20,5 50
X2,6 = 10
X3,1 40
X3,2 0
X3,3 10,4 0,5 0,6 04,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.
) Лаврусь, О.Е. Теория массового обслуживания. Методические указания/ О.Е. Лаврусь, Ф.С. Миронов. Самара: СамГАПС, 2005.
) Авсиевич, А.В. Теория массового обслуживания. Потоки требований, системы массового обслуживания / А.В. Авсиевич, Е.Н. Авсиевич. Самара: СамГАПС. 2007 г.
) Черненко, В.Д. Высшая математика в примерах и задачах. В 3. т. Т. 3/ В.Д. Черненко. Санкт - Петербург: Политехника, 2006.
) Олзоева, С.И. Моделирование и расчет распределенных информационных систем. Учебное пособие / С.И. Олзоева. Улан-Удэ: ВСГТУ, 2009.
6) Системы массового обслуживания и их применение в логистике https://www.kt-lospo.com/study/l_3_5.htm
) Моделирование систем массового обслуживания https://stratum.ac.ru/textbooks/modelir/lection30.html
) Теория массового обслуживания https://ru.wikipedia.org/
) Построение математических моделей при решении задач оптимизации https://studyport.ru/tochnyie-nauki/postroenie-matematicheskih-modeley-pri-reshenii-zadach-optimizatsii.