X Международная студенческая научная конференция Студенческий научный форум - 2018
УЧИМСЯ МИНИМИЗИРОВАТЬ РАСХОДЫ НА ПЕРЕВОЗКУ
Полная версия работы доступна во вкладке "Файлы работы" в формате PDF
Требуется определить структуру перевозок между элеваторами и мельницами с минимальной стоимостью. Для этого необходимо найти матрицу перевозок, при которой стоимость всех расходов на доставку груза окажется минимальной. Заполним транспортную таблицу (табл. 1).
Таблица 1
Начальное решение получим, например, методом северо-западного угла (табл. 2) [3].
Таблица 2
Суммарная стоимость перевозок равна
(ден. ед.).
Для нахождения оптимального решения используем метод потенциалов [1, 2]. Вычисления обычно выполняются непосредственно в транспортной таблице (табл. 3). Положим . Поскольку все потенциалы определены, далее вычислим косвенные стоимости для всех свободных клеток и запишем найденные значения в левом верхнем углу каждой незанятой клетки. В левом нижнем углу записываем разности для каждой небазисной переменной .
Таблица 3
Определив вводимую в базис переменную , найдём исключаемую из базиса переменную. Необходимо, чтобы перевозки по маршруту, соответствующему переменной , уменьшили общую стоимость перевозок. Какой объём груза можно перевезти по этому маршруту? Обозначим через количество груза, перевозимого по маршруту (т. е. ). Сначала построим замкнутый цикл, который начинается и заканчивается в ячейке, соответствующей вводимой переменной . Для ячейки определим цикл, включающий клетки с базисными поставками: , , , , и (табл. 4).
Таблица 4
Для перераспределения поставок по найденному циклу необходимо определить минимальный перевозимый груз [1]. Чтобы выполнились ограничения по спросу и предложению, надо поочерёдно отнимать и прибавлять величину к значениям базисных переменных, расположенных в угловых ячейках найденного цикла (табл. 5).
Таблица 5
Искомую величину следует выбирать среди клеток, содержащих знак «минус», т.е. . Переменные и обращаются в нуль. Поскольку только одна переменная исключается из базиса, то в качестве исключаемой можно выбрать как , так и . Остановим свой выбор на . Тогда . Определив значение для вводимой переменной , и выбрав исключаемую переменную, откорректируем значения базисных переменных, соответствующих угловым ячейкам замкнутого цикла (табл. 6).
Таблица 6
Перевозка единицы груза по маршруту уменьшает общую стоимость перевозки на ден. ед. Суммарная стоимость перевозок будет на ден. ед. меньше, чем в предыдущем решении.
Так как , то получим
ден. ед.
Продолжим анализ оптимальности. Вычислим потенциалы нового базисного решения (табл. 7). Новой вводимой в базис переменной будет . Замкнутый цикл позволяет найти её значение и исключаемую переменную .
Таблица 7
Новое решение, представленное в табл. 8, уменьшает значение целевой функции на 40 (ден. ед.). Тогда ден. ед.
Таблица 8
Теперь для всех небазисных переменных оценки . Т.е. выполнился критерий оптимальности на минимум [2]. Таким образом, найденное решение является оптимальным.
, .
Полученное решение, изложенное в терминах исходной задачи перевозки зерна от элеваторов до мельниц, имеет следующий смысл:
|
От элеватора |
До мельницы |
Количество зерновозов |
|
1 |
2 |
5 |
|
1 |
4 |
10 |
|
2 |
2 |
10 |
|
2 |
3 |
15 |
|
3 |
1 |
5 |
|
3 |
4 |
5 |
Суммарная стоимость перевозок ден. ед.
Литература:
1. Агишева Д. К., Зотова С. А., Светличная В. Б., Матвеева Т. А. Транспортные и сетевые модели управления. Часть 2: учебное пособие/ С. А. Зотова, Д. К. Агишева, В. Б. Светличная, Т. А. Матвеева / ВПИ (филиал) ВолгГТУ. – Волгоград: ИУНЛ ВолгГТУ, 2012. – 160 с.
2. Агишева Д.К., Зотова С.А., Матвеева Т.А., Светличная В.Б. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ (учебное пособие) // Успехи современного естествознания. – 2010. – № 9 – С. 61-62 URL: www.rae.ru/use/?section=content&op=show_article&article_id=7785125
3. Казачков А.Д., Агишева Д.К., Светличная В.Б., Зотова С.А. РЕАЛИЗАЦИЯ МЕТОДА СЕВЕРО-ЗАПАДНОГО УГЛА НА MATHCAD 15 // Материалы VIII Международной студенческой электронной научной конференции «Студенческий научный форум» www.scienceforum.ru/2016/1762/23702