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

Размещено на http://www.allbest.ru/

1

Министерство образования Республики Беларусь

Институт парламентаризма и предпринимательства

Кафедра экономики и управления

Курсовая работа

по учебной дисциплине «Методы и модели принятия решений»

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

Минск, 2016



Содержание

Введение

1. Теоретико-методологическое описание метода линейного программирования

1.1 Общая постановка задачи линейного программирования, ее математическая модель

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

2. Анализ использования методов линейного программирования в деятельности предприятия ЖКХ

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

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

3. Направления совершенствования линейного программирования

Заключение

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

линейный программирование управленческий решение



Введение

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

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

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

В связи с этим для достижения цели были поставлены следующие задачи:

· изучить сущность линейного программирования, общую формулировку задач ЛП;

· рассмотреть типовые задачи линейного программирования и ознакомиться с методами их решения;

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

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

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

Объектом исследования курсовой работы является УП «ЖРЭО Советского района г. Минска».

Предметом исследования в настоящей работе являются математические методы линейного программирования и возможность их применения в деятельности УП «ЖРЭО Советского района г. Минска».

Курсовая работа состоит из введения, трех глав и заключения, содержит 2 таблицы, 9 рисунков, при подготовке работы были использованы 10 источников информации, перечень которых приведен в конце.

В первой главе курсовой работы рассматриваются понятия и сущность математического программирования и, в частности, его разновидности - линейного программирования. Приведены формулы постановки задачи ЛП в общем виде, также рассматривается проблема двойственной задачи линейного программирования. Рассматриваются некоторые основные типы задач ЛП, излагаются методы или подходы, используемые для их решения. Во второй главе работы внимание уделяется рассматриваемому предприятию - УП «ЖРЭО Советского района г. Минска» а также методам и задачам линейного программирования, используемым в деятельности предприятий ЖКХ в настоящее время, а также тем, которые только планируется или рекомендуется использовать. В третьей главе приводится методика оптимизации плана вывоза твердых бытовых отходов - одной из важных задач рассматриваемого ЖРЭО. Осуществлена постановка задачи планирования вывоза ТБО в виде последовательности трех задач: задачи кластеризации множества площадок сбора ТБО, задачи построения оптимальных маршрутов объезда площадок одного кластера, задачи определения необходимого числа машин и расписания сбора ТБО. Приводится решение задачи построения оптимального маршрута (задача коммивояжера) средствами MS Excel.

Информационная база исследования основывается на использовании аналитических и статистических данных УП «ЖРЭО Советского района г. Минска», данных учета и отчетности предприятий в сфере ЖКХ согласно отчетам Национального статистического комитета РБ, материалов периодической печати, сети «Интернет» и аналитических исследований автора.

29

1. Теоретико-методическое описание метода линейного программирования

1.1 Общая постановка задачи линейного программирования, ее математическая модель

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

Особенностью задач линейного программирования является то, что экстремума целевая функция достигает на границе области допустимых решений. Классические же методы дифференциального исчисления связаны с нахождением экстремумов функции во внутренней точке области допустимых значений. Отсюда - необходимость разработки новых методов. [9, c. 7]

Линейное программирование представляет собой наиболее часто используемый метод оптимизации. К числу задач линейного программирования можно отнести задачи:

1. рационального использования сырья и материалов;

2. задачи оптимального раскроя;

3. оптимизации производственной программы предприятий;

4. оптимального размещения и концентрации производства;

5. составления оптимального плана перевозок, работы транспорта (транспортные задачи);

6. управления производственными запасами;

7. и многие другие, принадлежащие сфере оптимального планирования.

Линейное программирование является одной из основных частей того раздела современной математики, который получил название математического программирования. В общей постановке, задачи этого раздела выглядят следующим образом.

Требуется найти такие неотрицательные , которые обеспечивают максимум или минимум целевой функции (формула 1.1), которые удовлетворяют системе ограничений (формула 1.2) и не противоречат условиям неотрицательности: .

(1.1)

(1.2)

… … … … … … … … … …

В зависимости от вида функции различают разделы математического программирования: квадратичное программирование, выпуклое программирование, целочисленное программирование и т.д. Линейное программирование характеризуется тем, что функция является линейной функцией переменных . [2 c.11-12]

Формы задач линейного программирования:

1. стандартная;

1.1 первая стандартная форма (формула 1.3);

1.2 вторая стандартная форма (формула 1.4);

2. каноническая (формула 1.5).

(1.3)

… … … … … … … … ….

.

(1.4)

… … … … … … … … … …

.

(1.5)

… … … … … … … … …

.

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

(1.6)

(1.7)

Аналогично можно сменить знак неравенства меньше или равно (формула 1.8) на больше или равно (формула 1.9).

(1.8)

(1.9)

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

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

Любой набор чисел , удовлетворяющий ограничениям задачи, называют планом, а множество всех планов допустимой областью. Тот план, который доставляет экстремум (минимум или максимум) целевой функции, называют оптимальным планом или просто решением задачи линейного программирования. [9 c.7-8]

Задачи линейного программирования решаются несколькими методами:

1. графический метод;

2. симплексный метод;

3. двойственность в ЛП;

4.двойственный симплексный метод.

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

Графический метод довольно прост и нагляден. Он основан на геометрическом представлении допустимых решений задачи. Каждое из неравенств задачи ЛП определяет на координатной плоскости некоторую полуплоскость, а система неравенств в целом - пересечение соответствующих плоскостей. Множество точек пересечения данных полуплоскостей называется областью допустимых решений (ОДР). ОДР всегда представляет собой выпуклую фигуру, т.е. обладающую следующим свойством: если две точки А и В принадлежат этой фигуре, то и весь отрезок АВ принадлежит ей. ОДР графически может быть представлен выпуклым многоугольником, неограниченным выпуклой многоугольной областью, отрезком, лучом и т.д. В случае несовместности системы ограничений задачи ОДР является пустым множеством.

При поиске оптимального решения задач линейного программирования возможны следующие ситуации: существует единственное решение задачи, существует бесконечное множество решений (альтернативный оптимум); ЦФ не ограничена; область допустимых решений- единственная точка; задача не имеет решений. [9 c.55-57]

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

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

Переход от одного базиса к другому позволяет находить решения почти всех задач ЛП. Определив все крайние точки, можно вычислить значения целевой функции и найти оптимальное решение. Однако для больших значений m и n это практически невозможно. [2 c.15]

Алгоритм решения задачи ЛП табличным симплексом-методом состоит из следующих этапов:

1. рассчитывают и заполняют начальную симплекс-таблицу с допустимым единичным базисом, включая индексную строку.

2. находят разрешающий столбец;

3. находят разрешающую строку;

4. рассчитывают методом Жордано-Гаусса все параметры матрицы;

5. анализируют полученные данные в индексной строке.

Таблицы симплекс-метода необходимо строить до тех пор, пока не будет получен оптимальный план. План будет считаться оптимальным, если в последней индексной строке симплекс-таблицы будут только нули и положительные числа. [2 c.20-22]

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

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

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

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

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

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

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

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

1. если прямая задача является задачей максимизации, то двойственная будет задачей минимизации, и наоборот;

2. коэффициенты целевой функции прямой задачи становятся свободными членами ограничений двойственной задачи;

3. свободные члены ограничений прямой задачи становятся коэффициентами целевой функции двойственной задачи;

4. матрица ограничений двойственной задачи получается путем транспортирования матрицы ограничений прямой задачи;

5. знаки неравенств в ограничениях изменяются на противоположные;

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

Виды математических моделей двойственных задач могут быть представлены в таблице (табл. 1.1).

Таблица 1.1

Виды математических моделей двойственных задач

Исходная задача	Двойственная задача
Несимметричные задачи
Симметричные задачи

Примечание: Источник: [9, с.114-115]

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

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

(1.10)

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

Двойственную задачу выгоднее решать, чем прямую, если в прямой задаче при малом количестве переменных имеется большое количество ограничений. [8, c 70-71]

Симплексный метод позволяет наряду с получением решения прямой задачи получать и решение двойственной задачи. Этот результат и лежит в основе двойственного симплексного метода решения задачи. Суть метода состоит в таком последовательном переборе угловых точек допустимого множества Q₀ двойственной задачи, при котором значение целевой функции возрастает, т. е. в применении симплексного метода к решению двойственной задачи. Будем предполагать, что задача невырождена, т. е. каждой угловой точке множества Q₀ соответствует квадратная невырожденная система уравнений размерности m, матрицу которую и называют двойственным базисом прямой задачи. Вместе с тем двойственный симплекс-метод можно применять при решении задачи линейного программирования, свободные члены системы уравнений которой могут быть любыми числами (при решении задачи симплексным методом эти числа предполагались неотрицательными).

Отыскание решения задачи двойственным симплекс-методом включает в себя следующие этапы:

1. Находят псевдоплан задачи.

2. Проверяют этот псевдоплан на оптимальность. Если псевдоплан оптимален, то найдено решение задачи. В противном случае либо устанавливают неразрешимость задачи, либо переходят к новому псевдоплану.

3. Выбирают разрешающую строку с помощью определения наибольшего по абсолютной величине отрицательного числа столбца вектора Р₀ и разрешающий столбец с помощью нахождения наименьшего по абсолютной величине отношения элементов (m+1)-и строки к соответствующим отрицательным элементам разрешающей строки.

4. Находят новый псевдоплан и повторяют все действия начиная со второго этапа.

Двойственный симплексный метод называют также методом последовательного уточнения оценок, поскольку угловые точки задачи, возникающие при итерациях, можно рассматривать как приближенные значения точной оценки у*, т. е. как приближенные оценки влияния условий задачи на величину минимума целевой функции. [8, c.87-92]

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

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

Метод решения таких задач, предложенный Гомори, основан на симплексном методе и состоит в следующем. Симплексным методом находится оптимальный план задачи без учета условия целочисленности. Если оптимальный план целочисленный, то вычисления заканчивают; если же оптимальный план содержит хотя бы одну дробную компоненту X_i, то накладывают дополнительное ограничение, учитывающее целочисленность компонент плана, и вычисления симплексным методом продолжают до тех пор, пока либо будет найден целочисленный оптимальный план, либо доказано, что задача не имеет целочисленных оптимальных планов. [9 c.122-123]

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

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

Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов, производственно-транспортных и других задач). [8, c.92]

Рассмотрим постановку задачи о наилучшем использовании ресурсов. Пусть некоторая производственная единица (цех, завод, объединение и т. д.), исходя из конъюнктуры рынка, технических или технологических возможностей и имеющихся ресурсов, может выпускать n различных видов продукции (товаров), известных под номерами, обозначаемыми индексом j . Товары будем обозначать . Предприятие при производстве этих видов продукции должно ограничиваться имеющимися видами ресурсов, технологий, других производственных факторов (сырья, полуфабрикатов, рабочей силы, оборудования, электроэнергии и т. д.). Все эти виды ограничивающих факторов называют ингредиентами . Пусть их число равно m; припишем им индекс i . Они ограничены, и их количества равны соответственно условных единиц. Таким образом, - вектор ресурсов. Известна экономическая выгода (мера полезности) производства продукции каждого вида, исчисляемая, скажем, по отпускной цене товара, его прибыльности, издержкам производства, степени удовлетворения потребностей и т. д. Примем в качестве такой меры, например, цену реализации , т. е. -- вектор цен. Известны также технологические коэффициенты , которые указывают, сколько единиц i-го ресурса требуется для производства единицы продукции j-го вида. Матрицу коэффициентов называют технологической и обозначают буквой А. Имеем . Обозначим через план производства, показывающий, какие виды товаров нужно производить и в каких количествах, чтобы обеспечить предприятию максимум объема реализации при имеющихся ресурсах. Так как - цена реализации единицы j-й продукции, цена реализованных единиц будет равна , а общий объем реализации примет вид (формула 2.1). Это -- целевая функция, которую нужно максимизировать.

(1.11)

Так как - расход i-го ресурса на производство единиц j-й продукции, то, просуммировав расход i-го ресурса на выпуск всех n видов продукции, получим общий расход этого ресурса, который не должен превосходить единиц (формула 1.12).

(1.12)

Чтобы искомый план был реализован, наряду с ограничениями на ресурсы нужно наложить условие неотрицательности на объёмы выпуска продукции .

В модель задачи о наилучшем использовании ресурсов входят: целевая функция (формула 1.13), система ограничений (формула 1.14) и условия неотрицательности (формула 1.15)

(1.13)

(1.14)

(1.15)

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

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

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

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления в n пунктов назначения . При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через - запасы груза в i-м пункте отправления, через - потребности в грузе в j-м пункте назначения, а через - количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции (формула 1.16) при определенных ограничениях (формула 1.17) и условиях неотрицательности (формула 1.18).

(1.16)

(1.17)

(1.18)

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

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

В случае превышения запаса над потребностью, вводится фиктивный (n+1)-й пункт назначения с потребностью (формула 1.19) и соответствующие тарифы считаются равными нулю. Аналогично, в случае, если потребности превышают количество запасов, также вводится фиктивный (m+1)-й пункт отправления с запасом груза и тарифы полагаются равными нулю (формула 1.20). Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи.

(1.19)

(1.20)

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

1. метод северо-западного угла;

2. метод минимального элемента;

3. метод двойного предпочтения;

4. метод штрафов (Фогеля).

"Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла- наихудшее.

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

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

Для того чтобы заполнить клетку (i,j), необходимо сравнить текущий запас товара в рассматриваемой i-й строке с текущей потребностью в рассматриваемом j-м столбце. Нахождение опорного плана продолжается до тех пор, пока не будут вычеркнуты все строки и столбцы. [9 c.137]

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

Если таблица стоимостей велика, то перебор всех элементов затруднителен. В этом случае используют метод двойного предпочтения, суть которого заключается в следующем: в каждой строке и каждом столбце отмечают «V» наименьшую стоимость, а затем клетки с двойным символом «VV» заполняют с учетом наименьшей стоимости. Затем распределяют перевозки по клеткам, отмеченным знаком «V». В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

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

Если клеток с минимальным тарифом также несколько, то из них выбирается клетка (i,j) с максимальным суммарным штрафом, т.е. суммой штрафов по i-й строке и j-му столбцу.

Если план транспортной задачи является оптимальным, то ему соответствует система из m+n чисел Ui и Vj, удовлетворяющих условиям: Ui+Vj=Cij для занятых клеток и Ui+Vj?Сij в свободных клетках. Числа Ui и Vj называются потенциалами соответственно поставщиков и потребителей. При решении одному неизвестному потенциалу придается произвольное значение. [9 c.141]

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

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

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

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

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

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

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

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

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

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

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

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



2. Анализ использования методов линейного программирования в деятельности предприятий ЖКХ

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

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

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

На балансе ЖРЭО находится 600 жилых домов, из них 535 домов местных Советов и 60 домов ЖСК, 5 ведомственных зданий. На техническом обслуживании объединения находится также 17 отдельно стоящих нежилых строений.

Основными задачами деятельности предприятия являются:

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

· защита социально-экономических интересов собственника имущества и членов трудового коллектива предприятия.

Основными функциями предприятия являются:

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

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

· организация эксплуатации, технического обслуживания и санитарного содержания жилищного фонда;

· планирование и организация всех видов ремонта, включая реконструкцию жилых домов;

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

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

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

· - установка групповых приборов учета на отопление и горячее водоснабжение,

· - установка индивидуальных приборов учета в квартирах и переход на расчеты с населением по показаниям приборного учета,

· - наличие просроченной задолженности по оплате населением за жилищно-коммунальные услуги.

Проведем анализ основных показателей деятельности УП «ЖРЭО Советского района г. Минска» за 2013-2015 гг. (Таблица 2.1).

Таблица 2.1

Структура жилищно - коммунальных услуг, оказываемых УП «ЖРЭО Советского района г. Минска» (в %)

№ п/п	Виды жилищно - коммунальных услуг	2013	2014	2015	Изменение
1	2	3	4	5	6
1	Техническое обслуживание жилого помещения	9,2	9,5	10,4	1,0
2	Отчисления на капитальный ремонт жилого фонда	9,2	9,5	10,4	1,0
3	Отопление	38,5	41,5	40,2	-1,3
4	Подогрев воды	17,3	19,3	15,1	-4,2
5	Водопровод и канализация	9,2	9,6	9,9	0,3
6	Газоснабжение	5,0	5,9	9,0	3,1
7	Пользование лифтом	2,6	2,9	2,9	-
8	Вывоз мусора и обезвреживание ТБО	1,2	1,4	1,4	-
9	Пользование коллективной антенной и радиоточкой	0,4	0,6	0,7	0,1

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

В соответствии с Жилищным кодексом Республики Беларусь, от 28.08.2012 N 428-З (ред. 10.01.2015 г.) и типовым договором на участие собственника (нанимателя) жилого помещения и жилищно-эксплуатационной организации по содержанию многоквартирного жилого дома и предоставлению коммунальных услуг понятие «техническое обслуживание» включает в себя:

1. Ремонт элементов отделки ограждающих конструктивных элементов, санитарно-технического и иного оборудования.

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

3. Техническое обслуживание инженерных систем:

- по электроснабжению;

- по холодной и горячей воде;

- по канализации;

- по центральному отоплению.

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

5. Вывоз твердых бытовых отходов, содержание контейнеров и контейнерных площадок в соответствии с требованиями, отвечающими техническим и санитарным нормам.

6. Устранение повреждений в жилом помещении собственника (нанимателя), вызванных неисправностями инженерных систем или конструктивных элементов жилого дома, кроме неисправностей, возникших по вине собственника (нанимателя), а также граждан, вина которых установлена.

7. Обеспечение коммунальными услугами по договорам с другими организациями, оказывающими эти услуги.

8. Освещение входа в подъезд, посадочные площадки лифтов и придомовую территорию, а также содержание в исправном состоянии осветительной арматуры на лестничных площадках и других вспомогательных помещениях.

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

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

11. Обслуживание диспетчерскими и аварийными службами.

12. Выдача справок (копий лицевого счета), прописка, выписка.

Двумя основными направлениями текущего содержания жилфонда являются содержание домового хозяйства и текущий ремонт.

Таблица 2.2

Доходы УП «ЖРЭО Советского района г. Минска»

№№ п/п	Наименование статей	2013 год (тыс.руб.)	2014 год (тыс.руб.)	2015 год (тыс.руб.)	Изменение (+/-)
1	2	3	3	4	5
1	Плата за техническое обслуживание жилых помещений	99900,8	104895,8	114829,3	15 %
1.1	в государственном жилищном фонде	16452,4	16946,3	18771,7	14%
1.2	в приватизированном жилищном фонде	65387,6	65387,6	70377,7	8%
1.3	в ЖСК	18060,8	22561,9	25679,9	42%
2	Арендная плата	90336,2	91836,5	92705,9	0,8%
3	Комиссионные за сбор жилищно-коммунальных платежей	10033,7	10334,7	10501,0	5%
4	Возмещение эксплуатационных расходов арендаторами	11931,8	12057,5	12253,8	3%
5	Прочие доходы	1538,8	1264,7	1367,1	-12%
6	Доходы от основной деятельности	213741,3	220389,2	231657,1	8%
7	Внереализационные прибыль+, убытки-	2892,4	292,4	224,7
8	Ассигнования на покрытие разницы в цене в части покрытия убытков	103785,0	108975,3	125230,9	21%
9	Доходы от оказания бытовых и прочих платных услуг	14601,7	14354,7	14067,2	-4%
10	Плата за сбор и вывоз ТБО	10714,4	11214,4	12132,4	13%
11	Плата за пользование лифтами	11638,7	12564,5	13387,0	15%
12	Всего доходов	357373,5	367790,5	396699,3	11%
13	Налоги из выручки	21500,7	22127,4	21525,1	0,1%
13.1	НДС	17558,4	18070,2	18650,7	6%
13.2	единый платеж	3942,3	4057,2	2874,4	-37%
	Финансовый результат	0,0	0,0	0,0	0,0
14	Ассигнования на платежи в бюджет	3713,1	3713,1	3589,0	-3%

Данные таблицы 2.2 и рисунка 2.3 показывают, что доходы УП «ЖРЭО Советского района г. Минска» от основной деятельности с учетом внереализационного результата на 2015 год сформированы в сумме 231,6 млн. руб., что выше уровня 2012 года на 8,0%

Комиссионные за сбор жилищно-коммунальных платежей составит 10,5 млн. рублей и прочие доходы 1,4 млн. руб.

Доходы от населения за пользование лифтами, сбор и вывоз ТБО составят 25,5 млн. руб. Общая сумма доходов составит 271,5 млн. руб.

Стоимость основных фондов, находящихся на балансе подведомственных организаций УП «ЖРЭО Советского района г. Минска, на 01.01.2015 г. составила 1862,3млрд. руб. Уставной капитал на 1.01.2015 г. составил 0,4млрд. руб.

За 2015 год получена от населения сумма доходов 136,9 млн. рублей или 42,4% от общих затрат жилищно-эксплуатационных организаций по обслуживанию жилого фонда (323,1 млн. руб.). Доходы от арендной платы составили 90,3 млн. рублей или 27,9% от фактических расходов по обслуживанию жилищного фонда. Расходы на содержание аппарата управления за 2015 год составили 50,9 млн. руб. или 15,7% от общих расходов предприятия. Содержание домового хозяйства составило 93,9 млн. руб. или 29,0% от всех расходов. Расходы на содержание домового хозяйства за 2015 год составили 82,1 млн. руб. или 25,4% всех затрат, в связи с этим на налоги было затрачено 6,9 млн. руб., что составило 2,1% от общих расходов.

Среднемесячная себестоимость обслуживания 1 кв. метра эксплуатируемой площади в 2015 году составила 758,4 руб.

В 2015 году жилищными организациями получено из бюджета ассигнований на текущее содержание 119,2 млн. руб.

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

Просроченная задолженность населения по оплате ЖКУ на 01.01.2015 составляла 6,08 млн. руб. или 6% от общего количества лицевых счетов, на 01.01.2016 задолженность снижена на 0,59 млн. рублей и составила 5,49 млн. руб. или 5% от лицевых счетов.

Просроченная задолженность арендаторов на 01.01.2016 год составила 744,6 млн. руб. или 7% от ожидаемой суммы доходов.

По подведомственным коммунальным предприятиям получена прибыль от реализации в сумме 6,9 млн. руб. В течение отчетного года из полученной предприятиями прибыли от реализации после уплаты налогов и других обязательных платежей, выплат из прибыли нераспределенная прибыль составила 4,3 млн. руб.

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

Модель линейного программирования, в УП «ЖРЭО Советского района г. Минска» применяют для определения оптимального способа распределения дефицитных ресурсов при наличии конкурирующих потребителей.

Некоторые типичные способы применения этого метода в управлении УП «ЖРЭО Советского района г. Минска» перечислены ниже:

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

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

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

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

Регулирование запасов. Определение оптимального сочетания продуктов на складе или хранилище.

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

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

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

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

По разработанным социально-экономическим показателям должен проводиться расчет интегрального индикатора качества жизни населения. Так, например, для расчета интегрального индикатора качества жизни может быть применена экономическая методика Айвазяна, согласно которой социально-экономическая эффективность безопасных и комфортных условий проживания сопоставима с интегральным индикатором качества жизни, который определяется по формуле [1]:

^(2.1)

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

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

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

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

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

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

3. Направления совершенствования линейного программирования

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

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

Решение рассматриваемой задачи предлагается разбить на последовательное решение трех подзадач: 1) задачи кластеризации множества площадок сбора твердых бытовых отходов; 2) задачи построения оптимальных маршрутов объезда площадок одного кластера; 3) задачи определения необходимого числа машин и расписания сбора ТБО.

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

Требуется разбить множество площадок на кластеры , определив при этом их число k, таким образом, чтобы выполнялись следующие условия:

(3.1)

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

Математическая модель задачи построения оптимального маршрута объезда площадок одного кластера.

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

1) Маршрут «предприятие - кластер - завод».

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

(3.2)

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

...