Определение оптимального плана работы почтовых отделений
Введение
математический оптимизационный прикладной программа
Математика необходима в повседневной жизни, следовательно, определенные математические навыки нужны каждому человеку. Нам приходится в жизни считать (например, деньги), мы постоянно используем (часто не замечая этого) знания о величинах, характеризующих протяженности, площади, объемы, промежутки времени, скорости и многое другое. Математические знания и навыки нужны практически во всех профессиях, прежде всего, конечно, в тех, что связаны с естественными науками, техникой и экономикой. В экономике постоянно приходится решать задачи поиска наилучшего решения из некоторого множества допустимых решений. Такое решение называют оптимальным, процесс поиска такого решения - оптимизацией, а задачи в которых ищется такое решение - оптимизационными задачами [1].
Целью курсовой работы является развитие навыков работы при решении оптимизационной задачи, освоение и практическое применение оптимизационного пакета прикладных программ.
Для достижения поставленной цели необходимо решить следующие задачи:
.Провести анализ полученного задания.
.Осуществить подбор необходимой литературы.
.Построить математическую модель.
.Выбрать метод оптимизации.
.Реализовать выбранный метод.
.Решить задачу с помощью ППП «LINDO».
.Проанализировать полученные результаты.
Задание на курсовую работу
Планируется доставка газет в новые микрорайоны города. Схема доставки следующая. Каждый день в 5.30 утра издательство отправляет газеты в почтовые отделения (п/о), откуда они после сортировки доставляются в микрорайоны. Общее количество газет, поступающих в почтовые отделения, может превышать потребности подписчиков. Остающаяся часть газет реализуется через п/о или в расположенных рядом киосках «Союзпечати». Каждое п/о может обслуживать один или несколько микрорайонов и один микрорайон может обслуживаться несколькими п/о, причем газеты подписчикам должны быть доставлены не позднее 7.30 утра. Известны стоимость и время доставки газет от издательства до п/о и от п/о до каждого микрорайона, а также время, затрачиваемое на сортировку.
Каждый год после завершения подписки устанавливается объем выпуска газет издательству и поставки каждому п/о. Эти данные являются исходными для планирования доставки газет подписчикам.
Требуется найти оптимальный план доставки газет от п/о к микрорайонам и количество газет, реализуемых п/о на месте.
Показать, как изменится решение в следующих ситуациях:
п/о №1 доступны только районы А и Г, п/о №3 - Б и З.
время сортировки газет увеличится на 20%.
ПоказателиНомер почтового отделения12345Стоимость доставки 1 тыс.экз. от издательства до п/о, руб.1,00,90,80,60,5Время доставки газет от издательства до п/о, мин.2018221512Время сортировки газет в п/о, мин.4535405048Количество газет, поступающих в п/о, тыс.экз.152382724
Номер п/оМикрорайоныАБВГДЖЗ11,5 382,1 471,7 301,4 411,2 282,0 601,0 3520,9 301,3 451,1 401,8 651,5 681,4 501,1 3531,6 660,8 321,2 441,9 701,0 391,7 492,0 6040,9 351,5 541,5 521,4 432,0 581,3 322,5 5551,0 500,7 301,0 601,8 522,2 552,5 643,0 55Потребности микрорайона, тыс.экз.913112071314
В числителе показана стоимость доставки 1 тыс.экз. в руб., а в знаменателе - время доставки от п/о к микрорайону в мин.
1. Преобразование исходных данных
Для того чтобы прояснить структуру математической модели и определить численные значения всех параметров, входящих в модель, необходимо преобразовать исходные данные.
Для этого посчитаем время доставки газет от издательства до п/о и от п/о до каждого микрорайона, а также время, затрачиваемое на сортировку. Результаты занесем в таблицу 1.
Таблица 1
Номер п/оМикрорайоныАБВГДЖЗ11031129510693125100283989311812110388312894106132101111122410011911710812397120511090120112115124115Потребности микрорайона, тыс.экз.913112071314
Исходя из условий задачи (время доставки газет от издательства до микрорайона составляет не более 120 мин.) составим новую таблицу, отметив в ней элементы которые не удовлетворяют нашим условиям буквой М.
Таблица 2
Номер п/оМикрорайоныАБВГДЖЗ11031129510693М1002839893118М103883М94106М101111М4100119117108М97M511090M112115М115Потребности микрорайона, тыс.экз.913112071314
Посчитаем стоимость доставки 1 тыс. экз. газет от издательства до п/о и от п/о до микрорайона. Результаты занесем в новую таблицу, исключая элементы отмеченные буквой М из таблицы 2.
Таблица 3
Номер п/оМикрорайоныАБВГДЖЗ12,53,12,72,42,2М2,021,82,22,02,7М2,32,03М1,62,0М1,82,5М41,52,12,12,0М1,9M51,51,2M2,32,7М3,5Потребности микрорайона, тыс.экз.913112071314
Добавим в таблицу 3 данные о количестве газет поступающих в п/о. Результаты занесем в таблицу 4.
Таблица 4
Номер п/оМикрорайоныАБВГДЖЗ 9131120713141152,53,12,72,42,2М2,02231,82,22,02,7М2,32,038М1,62,0М1,82,5М4271,52,12,12,0М1,9M5241,51,2M2,32,7М3,5
Для удобства решения задачи преобразуем таблицу 4, удалив из нее ненужные строки и столбцы. Результаты занесем в таблицу 5.
Таблица 5
913112071314152,53,12,72,42,2М2,0231,82,22,02,7М2,32,08М1,62,0М1,82,5М271,52,12,12,0М1,9M241,51,2M2,32,7М3,5
2. Построение математической модели
Для построения модели необходимо определить критерий, переменные, блок условий и ограничений.
- количество газет доставляемых из - го п/о к - му микрорайону.
Критерий - затраты на доставку газет.
.
Условия:
,
,
,
,
.
,
,
,
,
,
,
.
Ограничения:
.
. Выбор метода решения
Многие прикладные модели в экономике сводятся к задачам линейного программирования. Одна из самых распространенных и востребованных задач - транспортная задача. В классическом виде она предполагает нахождение оптимального (т.е. сопряженного с минимальными затратами) плана грузоперевозок [3].
Исходя из условий задачи, а именно нахождение оптимального плана доставки газет, можно предположить, что перед нами классический пример транспортной задачи. Анализируя математическую модель задачи, можно выделить ее следующие особенности, присущие, в том числе и транспортным задачам:)Все переменные в условия входят с коэффициентом плюс единица.)Модель содержит два блока условий: по пунктам отправления (п/о) и по пунктам назначения (микрорайоны). При этом каждая переменная входит в условия два раза - по одному разу в каждый блок.)Задача имеет простые условия разрешимости: необходимо и достаточно, чтобы задача была сбалансирована .
Решить транспортную задачу можно различными методами, начиная от симплекс-метода и простого перебора, и заканчивая методом графов.
Один из наиболее применяемых и подходящих для большинства случаев методов - итерационное улучшение плана перевозок. Суть его в следующем: находим некий опорный план и проверяем его на оптимальность. Если план оптимален - решение найдено. Если нет - улучшаем план столько раз, сколько потребуется, пока не будет найден оптимальный план.
Для анализа полученных планов и их последующего улучшения удобно ввести дополнительные характеристики пунктов отправления и назначения, называемые потенциалами. Этот метод улучшения плана перевозок называется методом потенциалов [4]. Остановимся подробно на этом методе решения.
Порядок решения транспортной задачи методом потенциалов следующий:
.Проверяем задачу на сбалансированность . Если задача не сбалансирована, то вводим фиктивного поставщика или потребителя с недостающими запасами или запросами и нулевыми стоимостями перевозок.
.Строим начальный план перевозок (используя метод минимальной стоимости). Вычисляем значение критерия при данном плане.
.Проверяем план на оптимальность. Для этого подсчитываем количество занятых клеток (их должно быть ) и строим систему потенциалов для них: одному из потенциалов (обычно тому, которому соответствует большее число занятых клеток) задаем произвольное значение, а остальные потенциалы вычисляем, используя уравнения . Для свободных клеток вычисляем оценки по формуле: . Если все оценки свободных клеток - не отрицательны, то полученное решение является оптимальным. Если же имеется хотя бы одна клетка с отрицательной оценкой, то опорное решение не является оптимальным и переходим к следующему этапу.
.Переходим к новому опорному решению, на котором значение целевой функции будет меньше. Для этого находим клетку, которой соответствует наименьшая оценка . Строим цикл пересчета, расставляя в клетках цикла поочередно знаки «+» и «-», начиная с «+» в свободной клетке. Осуществляем сдвиг по циклу на величину , при этом из клеток со знаком «-» вычитаем , а к клеткам со знаком «+» прибавляем . Если минимум достигается в нескольких клетках, то одна из них остается пустой, а в остальных проставляют базисные нули, чтобы число занятых клеток оставалось равным . Вычисляем значение критерия для данного опорного решения. Далее возвращаемся к пункту 3 [5].
1)Проверим задачу на сбалансированность:
, , → задача не сбалансирована.
)Приведем открытую транспортную задачу к закрытой.
Так как , то введем фиктивного потребителя (киоски «Союзпечати»), потребности которого равны:
.
Результаты занесем в таблицу 6.
Таблица 6
913112071314152,53,12,72,42,2М2,0231,82,22,02,7М2,32,08М1,62,0М1,82,5М271,52,12,12,0М1,9M241,51,2M2,32,7М3,5
)Построим начальный план доставки газет по методу минимальной стоимости.
Минимальная стоимость доставки: . Заполнение таблицы начинаем с клетки . Результаты занесем в таблицу 7.
Таблица 7
91311207131410152,53,12,72,42,2 5М2,00 10231,82,22,0 52,7М2,3 42,0 14 08М1,62,0 6 М1.8 22,5М0271,52,12,12,0 18 М1,9 9M0241,5 9 1,2 13 M2,3 2 2,7М3,50
.
)Определим, будет ли данный план доставки газет оптимальным.
Находим значения потенциалов для занятых клеток, используя уравнения вида :
, , , , , ,,, , , , .
Результаты занесем в таблицу 8.
Таблица 8
91311207131410152,53,12,72,42,2 5М2,00 10231,82,22,0 52,7М2,3 42,0 14 08М1,62,0 6 М1.8 22,5М0271,52,12,12,0 18 М1,9 9M0241,5 9 1,2 13 M2,3 2 2,7М3,50
Для свободных клеток вычислим оценки по формуле:
.
, , , , ,
, ,
,, , , , , , ,
, , , , .
5)Т.к. план доставки газет не оптимальный (среди оценок свободных клеток есть отрицательные), построим новый план доставки.
Выбираем наименьшую . Этому условию соответствуют 2 клетки: и .
Выберем среди них клетку с минимальной стоимостью: (. На соответствующей клетке построим цикл пересчета. Результаты занесем в таблицу 9.
Таблица 9
91311207131410152,53,12,72,42,2 - 5М+ 2,00 10231,82,22,0 + 52,7М2,3 42,0 - 14 08М1,62,0 - 6 М1.8 + 22,5М0271,52,12,12,0 18 М1,9 9M0241,5 9 1,2 13 M2,3 2 2,7М3,50
Определяем количество газет, которое будем сдвигать по циклу пересчета: .
Строим новый план доставки газет. Результаты заносим в таблицу 10.
Таблица 10
91311207131410152,53,12,72,42,2М2,0 5 0 10231,82,22,0 102,7М2,3 42,0 9 08М1,62,0 1 М1.8 72,5М0271,52,12,12,0 18 М1,9 9M0241,5 9 1,2 13 M2,3 2 2,7М3,50
.
Проверяем новый план на оптимальность. Находим значения потенциалов и оценки свободных клеток. Результаты заносим в таблицу 11.
Таблица 11
91311207131410152,53,12,72,42,2М2,0 5 0 10231,82,22,0 102,7М2,3 42,0 9 08М1,62,0 1 М1.8 72,5М0271,52,12,12,0 18 М1,9 9M0241,5 9 1,2 13 M2,3 2 2,7М3,50
, , ,
, , ,
,,
, , ,
, ,
, , ,
, .
План доставки газет оптимальный, т.к. все оценки свободных клеток - не отрицательны. Однако оценки и равны нулю, следовательно, оптимальное решение не единственно.
)Решение задачи с помощью ППП «LINDO».
Для решения задачи математическая модель была введена в программу «LINDO». Существует несколько вариантов оптимального решения задачи, однако значение целевой функции во всех случаях равно . Два различных оптимальных плана и результаты работы программы представлены в Приложении 1 и в Приложении 2.
)Показать как измениться решение при следующих ситуациях:)п/о №1 доступны только районы А и Г, п/о №3 - Б и З.
Преобразуем таблицу 6, учитывая новые условия (недоступные районы отметим буквой М). Результаты занесем в таблицу 12.
Таблица 12
913112071314152,5ММ2,4МММ231,82,22,02,7М2,32,08М1,6МММММ271,52,12,12,0М1,9M241,51,2M2,32,7М3,5
Построим математическую модель:
.
Условия:
,
,
,
,
.
,
,
,
,
,
,
.
Ограничения:
.
Введем математическая модель в программу «LINDO». Результаты работы программы представлены в Приложении 3. Значение целевой функции равно .)Время сортировки газет увеличиться на 20%.
Таблица 13
Номер п/оМикрорайоныАБВГДЖЗ111212110411510213410929010510012512811095313610211414010911913041101291271181331071305119,699,6129,6121,6124,6133,6124,6Потребности микрорайона, тыс.экз.913112071314
Исходя из условий задачи (время доставки газет от издательства до микрорайона составляет не более 120 мин.) составим новую таблицу, отметив в ней элементы которые не удовлетворяют нашим условиям буквой М.
Таблица 14
Номер п/оМикрорайоныАБВГДЖЗ1112М104115102М109290105100ММ110953М102114М109119М4110ММ118М107М5119,699,6МММММПотребности микрорайона, тыс. экз.913112071314
Преобразуем таблицу 7, учитывая новые условия. Результаты занесем в таблицу 15.
Таблица 15
913112071314152,5М2,72,42,2М2,0231,82,22,0ММ2,32,08М1,62,0М1.82,5М271,5ММ2,0М1,9M241,51,2MМ МММ
Построим математическую модель:
.
Условия:
,
,
,
,
.
,
,
,
,
,
,
.
Ограничения:
.
Введем математическая модель в программу «LINDO». Результаты работы программы представлены в Приложении 4. Значение целевой функции равно .
5. Анализ полученных результатов
Оптимальный план доставки газет от п/о к микрорайонам представлен в таблице 18.
Таблица 18
913112071314152,53,12,72,42,2М2,0 5 0 10231,82,22,0 102,7М2,3 42,0 9 8М1,62,0 1 М1.8 72,5М271,52,12,12,0 18 М1,9 9M241,5 9 1,2 13 M2,3 2 2,7М3,5
Из таблицы видно, что:
из п/о №1 5 тыс. экз. газет доставляется в микрорайон «З», а 10 тыс. экз. газет реализуется через киоски «Союзпечати»;
из п/о №2 10 тыс. экз. газет доставляется в микрорайон «В», 4 тыс. экз. газет доставляется в микрорайон «Ж», 9 тыс. экз. газет доставляется в микрорайон «З»;
из п/о №3 1 тыс. экз. газет доставляется в микрорайон «В», 7 тыс. экз. газет доставляется в микрорайон «Д»;
из п/о №4 18 тыс. экз. газет доставляется в микрорайон «Г», 9 тыс. экз. газет доставляется в микрорайон «Ж»;
из п/о №5 9 тыс. экз. газет доставляется в микрорайон «А», 13 тыс. экз. газет доставляется в микрорайон «Б», 2 тыс. экз. газет доставляется в микрорайон «Г».
Суммарные затраты на доставку газет от п/о к микрорайонам равны 158,6 руб.
Результаты работы программы «LINDO», совпадают с результатами, полученными при решении задачи вручную. Следовательно, задача решена правильно.
Изменение условий задачи, а именно изменение доступности микрорайонов и увеличение времени сортировки газет, приводит к тому, что суммарные затраты на доставку газет от п/о к микрорайнонам увеличиваются: (доступность микрорайонов) и (время сортировки).
Заключение
В данной курсовой работе были получены навыки работы при решении задачи по определению оптимального плана работы почтовых отделений, был освоен и практически применен оптимизационный пакет прикладных программ (ППП «LINDO»).
Для решения задачи была составлена математическая модель. Задача была решена ручным и машинным методом (используя ППП «LINDO»). Сравнение полученных результатов подтвердило правильность выбора метода решения и его реализацию.
Список использованных источников
1В.Н. Костин. Оптимизационные задачи электроэнергетики: Учебное пособие. - СПб.: СЗТУ, 2003 - 120 с.
Методические указания к выполнению курсовой работы по дисциплине «Исследование операций и методы оптимизации систем». Составил ст. преподаватель кафедры АИИТ ЧФ ПНИПУ Лабутина Т.В. - Чайковский: ЧФ ПНИПУ, 2014. - 12с.
Экономико-математические методы и прикладные модели [Электронный ресурс]. - Режим доступа: #"justify">Приложение 1
LP OPTIMUM FOUND AT STEP 12
FUNCTION VALUE
) 158.6000
VALUE REDUCED COST0.000000 0.9000000.000000 1.8000000.000000 0.7000000.000000 0.0000000.000000 0.4000005.000000 0.0000000.000000 0.2000000.000000 0.90000010.000000 0.0000000.000000 0.3000004.000000 0.0000009.000000 0.0000000.000000 0.3000001.000000 0.0000007.000000 0.0000000.000000 0.2000000.000000 0.3000000.000000 1.2000000.000000 0.50000018.000000 0.0000009.000000 0.0000009.000000 0.00000013.000000 0.0000002.000000 0.0000000.000000 1.0000000.000000 1.600000
SLACK OR SURPLUS DUAL PRICES
) 10.000000 0.000000
) 0.000000 0.000000
) 0.000000 0.000000
) 0.000000 0.400000
) 0.000000 0.100000
) 0.000000 -1.600000
) 0.000000 -1.300000
) 0.000000 -2.000000
) 0.000000 -2.400000
) 0.000000 -1.800000
) 0.000000 -2.300000
) 0.000000 -2.000000
. ITERATIONS= 12
Приложение 2
LP OPTIMUM FOUND AT STEP 13
FUNCTION VALUE
) 158.6000
VALUE REDUCED COST0.000000 0.9000000.000000 1.8000000.000000 0.7000000.000000 0.0000000.000000 0.40000014.000000 0.0000000.000000 0.2000000.000000 0.90000011.000000 0.0000000.000000 0.3000004.000000 0.0000000.000000 0.0000000.000000 0.3000000.000000 0.0000007.000000 0.0000000.000000 0.2000000.000000 0.3000000.000000 1.2000000.000000 0.50000018.000000 0.0000009.000000 0.0000009.000000 0.00000013.000000 0.0000002.000000 0.0000000.000000 1.0000000.000000 1.600000
SLACK OR SURPLUS DUAL PRICES
) 8.000000 0.000000
) 1.000000 0.000000
) 0.000000 0.400000
) 0.000000 0.100000
) 0.000000 -1.600000
) 0.000000 -1.300000
) 0.000000 -2.000000
) 0.000000 -2.400000
) 0.000000 -1.800000
) 0.000000 -2.300000
) 0.000000 -2.000000
. ITERATIONS= 13
Приложение 3
LP OPTIMUM FOUND AT STEP 12
FUNCTION VALUE
) 168.1000
VALUE REDUCED COST0.000000 0.60000013.000000 0.0000000.000000 0.4000000.000000 1.1000009.000000 0.0000000.000000 0.8000000.000000 0.50000014.000000 0.0000000.000000 0.0000005.000000 0.0000000.000000 0.9000002.000000 0.0000007.000000 0.00000013.000000 0.0000004.000000 0.00000013.000000 0.0000000.000000 0.3000007.000000 0.0000000.000000 1.400000
ROW SLACK OR SURPLUS DUAL PRICES
) 2.000000 0.000000
) 0.000000 0.500000
) 8.000000 0.000000
) 0.000000 0.400000
) 0.000000 0.400000
) 0.000000 -1.900000
) 0.000000 -1.600000
) 0.000000 -2.500000
) 0.000000 -2.400000
) 0.000000 -3.100000
) 0.000000 -2.300000
) 0.000000 -2.500000
. ITERATIONS= 12
Приложение 4
LP OPTIMUM FOUND AT STEP 17
FUNCTION VALUE
) 158.8000
VALUE REDUCED COST0.000000 1.0000000.000000 0.7000006.000000 0.0000000.000000 0.4000001.000000 0.0000000.000000 0.3000000.000000 1.00000010.000000 0.0000000.000000 0.00000013.000000 0.0000000.000000 0.4000001.000000 0.0000007.000000 0.0000000.000000 0.2000000.000000 0.40000014.000000 0.00000013.000000 0.0000009.000000 0.00000013.000000 0.000000
ROW SLACK OR SURPLUS DUAL PRICES
) 8.000000 0.000000
) 0.000000 0.000000
) 0.000000 0.000000
) 0.000000 0.400000
) 2.000000 0.000000
) 0.000000 -1.500000
) 0.000000 -1.200000
) 0.000000 -2.000000
) 0.000000 -2.400000
) 0.000000 -1.800000
) 0.000000 -2.300000
) 0.000000 -2.000000
. ITERATIONS= 17