Модели линейного программирования и их применение в науке управления УП "ЖРЭО Советского района г. Минска"

Целевая функция, определяющая длину маршрута, и ограничения имеют вид:

(3.3)

(3.4)

2) Маршрут «завод - кластер - завод».

Введем переменные

(3.5)

где - число площадок по сбору ТБО в кластере . Заводу присваивается номер 0.

Тогда целевая функция, определяющая длину маршрута, и ограничения имеют вид:

(3.6)

(3.7)

Рассматриваемые математические модели (3.2) - (3.7) являются моделями задачи коммивояжера. Для решения задачи коммивояжера используется одна из реализаций метода ветвей и границ - алгоритм Литтла, Мурти, Суини и Кэрел.

Математическая модель задачи определения необходимого числа машин и расписания сбора ТБО заключается в следующем. Пусть длительность рабочего дня водителя и для каждого кластера определены маршруты и . Тогда вывоз бытовых отходов по маршрутам занимаем время и : где средняя скорость машины, суммарное время остановок для сбора отходов с площадок кластера и , где - число контейнеров на i-ой площадке кластера , - среднее время забора отходов из контейнера. Стоимости вывоза отходов с площадок кластера по маршрутам , равны: , , где - средняя стоимость эксплуатации машины в час.

Допустим, что известно число машин N, необходимое для вывоза всех бытовых отходов, и первый кластер, который каждая машина обслуживает, выезжая с предприятия. Тогда для того, чтобы распределить между машинами оставшиеся кластеры сформулируем следующую задачу целочисленного линейного программирования (ЗЦЛП).

Обозначим через номера всех кластеров,

номера первых кластеров,

распределение кластеров по обслуживающим машинам, где:

.

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

(3.8)

(3.9)

(3.10)

(3.11)

Ограничение (3.9) означает, что каждая машина работает в пределах времени . Ограничение (3.10) означает, что отходы из одного кластера может забрать только одна машина.

Задача (3.8) - (3.11) может быть решена классическим методом - методом Ленда и Дойга, если переменные и известны.

Не вдаваясь во все сложности данной методики рассмотрим более подробно один из ее этапов - решение задачи коммивояжера средствами табличного процессора MS Excel.

Задача коммивояжера - задача математического программирования по определению оптимального маршрута движения коммивояжера, цель которого состоит в том, чтобы посетить все объекты, записанные в задании, за кратчайший срок и с наименьшими затратами. В теории графов - это поиск пути, связывающего два или более узла, с использованием критерия оптимальности. Задача коммивояжера формулируется очень просто: на плоскости (в пространстве) расположены N городов, заданы расстояния между каждой парой городов. Требуется найти маршрут минимальной длины с посещением каждого города ровно один раз и с возвращением в исходную точку. В задаче коммивояжера целевой функцией, которую надо минимизировать, является стоимость обхода. На графах задача формулируется следующим образом: требуется найти гамильтонов цикл наименьшей стоимости во взвешенном полном графе. Т.е. выйдя из стартовой вершины, посетить каждую вершину графа ровно один раз и вернуться в начальную по кратчайшему пути.

Мощным средством анализа данных MS Excel является надстройка «Поиск решения». С ее помощью можно определить, при каких значениях указанных влияющих ячеек формула в целевой ячейке принимает нужное значение (минимальное, максимальное или равное какой-либо величине). Для процедуры поиска решения можно задать ограничения, причем не обязательно, чтобы при этом использовались те же влияющие ячейки, данные которых определяют значение целевой ячейки. Для расчета заданного значения применяются различные математические методы поиска. Вы можете установить режим, в котором полученные значения переменных автоматически заносятся в таблицу. Кроме того, результаты работы программы могут быть оформлены в виде отчета.

Постановка задачи коммивояжера, которую необходимо решить посредством надстройки «Поиск решения» методом полного перебора следующая:

Мусоровоз выезжает для сбора ТБО из пункта 1 (место расположения автопарка ЖЭУ), должен объехать необходимые пункты сбора ТБО, расстояния между каждым из которых известны, затем отвезти мусор на выгрузку (на свалку) и вернуться в пункт 1.

Заполним лист Excel следующим образом.

Зададим ограничения на решение задачи.

Рисунок 3.1

Также необходимо определить матрицу расстояний между пунктами назначения.

Рисунок 3.2

Целевая функция - суммарное пройденное расстояние.

Рисунок 3.3

Задание ячеек для дополнительных переменных u_i:

Рисунок 3.4

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

Рисунок 3.5

В окне Поиск решения установим следующие параметры решения задачи:

Установить целевую ячейку - $С$8 - равной минимальному значению.

Изменяя ячейки: $B$2:$E$5, $C$8:$E$8 - сюда заносятся не только ячейки, которые будут изменяться и в которых будут занесены решения задачи (ячейки с адресами $B$2:$E$5), но и ячейки $C$8:$E$8, содержащие переменные u_i, которые также являются изменяемыми. Ограничения задачи заносятся так же, как указано в лабораторных работах №1-№3, с обязательным указанием того, что переменные в ячейках $B$2:$E$5 - двоичные. В окне Параметры отметить: линейная модель, неотрицательные значения, автоматическое масштабирование.

Рисунок 3.6

Результаты оптимального решения задачи коммивояжера приведены на рисунке 3.7:

Рисунок 3.7

Таким образом, оптимальный маршрут объезда 1-3-2-4, минимальная длина маршрута равна 170.

Задача планирования вывоза твердых бытовых отходов может быть представлена в виде последовательности трех задач: задачи кластеризации множества площадок сбора ТБО, задачи построения оптимальных маршрутов объезда площадок одного кластера, задачи определения необходимого числа машин и расписания сбора ТБО. Указаны математические модели и алгоритмы решения вышеперечисленных задач.

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

Заключение

Результаты проведенного исследования позволяют сделать следующие выводы:

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

· Повышение качества жилищно-коммунальных услуг (ЖКУ) сегодня, безусловно, актуально, поскольку вектор развития национальной экономики Беларуси становится все более ориентированным на повышение качества жизни населения в условиях энерго-ресурсосбережения. Успешное решение указанной проблемы определяется государственной политикой в области качества жизни и выработкой концептуальных и методических подходов, адекватных требованиям современных рыночных отношений.

Для достижения данных целей необходимо максимально оптимизировать использование имеющихся ресурсов, в первую очередь средствами математического программирования применительно к основным функциям ЖРЭО.

Для повышения эффективности работы ЖКХ служит трехуровневая модель согласования интересов, основанная на методе последовательных уступок.

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

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

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

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

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

· организация работы с задолженностью по оплате ЖКУ.

В ходе работы были решены следующие задачи:

1. Изучена сущность линейного программирования а также общая формулировка задач ЛП.

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

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

2. Рассмотрены типовые задачи линейного программирования и методы их решения.

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

- задача о максимальном потоке

- задача о потоке минимальной стоимости

- задача коммивояжера

- задача о покрытии/раскрое

- задача о выборе диеты (о составлении сплава/раствора/смеси)

- транспортная задача

- задача о назначениях

- задача о выборе проектов

- другие типы задач

3. Дана общая характеристика УП «ЖРЭО Советского района г. Минска», рассмотрена его организационная структура и функции.

В состав УП «ЖРЭО Советского района г. Минска» входит 11 юридических самостоятельных жилищно-эксплуатационных участков и структурные подразделения объединения: участок механизации, ремонтно-строительный участок, участок ремонтных работ, лаборатория электрофизических измерений. На базе всех жилищно-эксплуатационных участков создано 4 расчетно-справочных центра.

Функции и организационная структура рассматриваемого ЖРЭО изложены в разделе 2.1 данной работы.

4. Рассмотрены методы ЭММ и, в частности, линейного программирования, в деятельности ЖКХ.

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

Также распространенными задачами ЛП в сфере ЖКХ являются транспортная задача, задача коммивояжера, задача о выборе проектов.

5. Рассмотрена методика определения оптимального плана вывоза ТБО для ЖРЭО, продемонстрировано решение задачи коммивояжера средствами табличного процессора MS Excel.

Важной задачей в работе ЖРЭО является построение плана утилизации твердых бытовых отходов. Задача планирования вывоза ТБО может быть представлена в виде последовательности трех задач: задачи кластеризации множества площадок сбора ТБО, задачи построения оптимальных маршрутов объезда площадок одного кластера, задачи определения необходимого числа машин и расписания сбора ТБО. Указаны математические модели и алгоритмы решения вышеперечисленных задач.

Надстройка «Поиск решения» для MS Excel представляет собой мощный инструментарий для решения задач линейного программирования, что очень полезно для практического использования в работе УП «ЖРЭО Советского района г. Минска».

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

Список использованных источников

1. Айвазян С.А. Измерение синтетических категорий качества жизни населения региона и выявление ключевых направлений совершенствования социально-экономической политики (на примере Самарской области и ее муниципальных образований) / С.А. Айвазян, В.С. Степанов, Н.И. Козлов // Прикладная эконометрика. 2006. № 2. С. 52-54.

2. Берюхова Т.Н. Банк производственных задач в расчетах на ЭВМ: учебное пособие. / Т.Н. Берюхова. Тюмень.: ТюмИИ, 1992. 124 с.

3. Вариант оценки эффективности технологий энергосбережения на основе методологии Киотского протокола / В.Г. Лугин [и др.] // Наука в нефтяной и газовой промышленности. 2009. № 2. С. 12-14.

4. Главная // Официальный сайт УП «ЖРЭО Советского района г. Минска» [Электронный ресурс]. 2015. Режим доступа: http://www.jreosovet.by/. Дата доступа: 02.11.2015.

5. Егорова Н.Е. Имитационное моделирование в задачах планирования и управления экономикой: сб. / Н.Е. Егорова. М.: ЦЭМИ АН, 1990.

6. ЖИЛИЩНЫЙ КОДЕКС РЕСПУБЛИКИ БЕЛАРУСЬ 28 августа 2012 г. № 428-З. Изменения и дополнения: Закон Республики Беларусь от 10 января 2015 г. № 244-З - Национальный правовой интернет-портал Республики Беларусь. Режим доступа: http://www.pravo.by/world_of_law/text.asp?RN=HK1200428. Дата доступа: 06.11.2015 г.

7. Задачи и функции // Официальный сайт УП «ЖРЭО Советского района г. Минска» [Электронный ресурс]. 2015. Режим доступа: http://www.jreosovet.by/zadachi-i-funktsii.html. Дата доступа: 02.11.2015.

8. Карманов В.Г. Математическое программирование: учебное пособие для студентов вузов. / В.Г. Карманов. М.: Физматлит, 2001. 264 с.

9. Кузнецов А.В. Математическое программирование: учебное пособие для вузов. / А.В. Кузнецов. М.: Высшая школа, 1976. 352 с.

10. Метод последовательных уступок // Wiki-справочник по математическому моделированию [Электронный ресурс] - Режим доступа: wafido.org/metod-posledovatelnyx-ust.html - Дата доступа: 08.11.2015 г.

11. Красов, А.В. Моделирование систем управления: Учебное пособие для вузов / С.Е. Душин, А.В. Красов, Н.Н. Кузьмин; Под ред. С.Е. Душин. М.: Студент, 2012. 348 c.

12. Лабскер, Л.Г. Вероятностное моделирование в финансово-экономической области: Учебное пособие / Л.Г. Лабскер. М.: ИНФРА-М, 2012. 172 c.

13. Лычкина, Н.Н. Имитационное моделирование экономических процессов: Учебное пособие / Н.Н. Лычкина. М.: НИЦ ИНФРА-М, 2012. 254 c.

14. Орлов, А.И. Организационно-экономическое моделирование. В 3-х т. Т. 2. Экспертные оценки: Учебник / А.И. Орлов. М.: МГТУ им. Баумана, 2011. 486 c.

15. Орлов, А.И. Организационно-экономическое моделирование. В 3-х т. Т. 3. Статистические методы анализа данных: Учебник / А.И. Орлов. М.: МГТУ им. Баумана, 2012. 623 c.

Размещено на Allbest.ru

11.