Задача. На данной сети дорог (рис. 3) указаны стоимости перевозки единицы груза из пункта в пункт. Найти наиболее экономный маршрут перевозки груза из пункта 1 в пункт 10.

Граф сети дорог

Решение. (Если затраты минимальны при перевозке единицы груза, то они будут минимальны и при перевозке любого количества груза).

Разобьём все пункты сети на группы (таблица 3):

Таблица 3 - Группировка пунктов сети

(К i-ой группе отнесём пункты, в которые можно попасть из любого пункта (i-1)-ой группы).

Формирование наиболее экономного маршрута может быть реализовано за четыре шага.

Физическая система - транспорт с грузом, перемещающийся из начального состояния C₁ (из пункта 1) в конечное состояние C₁₀ (пункт 10) и сеть дорог, где C_i - состояние системы перед i-ым шагом. Естественно принять местонахождение транспорта с грузом в пункте, в котором он пребывает перед этим шагом. Управление u_i на i-ом шаге состоит в выборе маршрута (i, j), по которому следует направлять груз из данного в общем направлении на пункт 10. Состояние в конце шага определяется номером пункта, в который будет доставлен груз в результате сделанного выбора (принятого управления). Z_i (значение целевой функции на i-ом шаге) - это затраты на перевозку единицы груза из данного пункта в выбранный соседний пункт. F_i определяется из рекуррентных формул [5].

Первый этап: i=N=4 (xi, xi-1 - состояния, u_i - управления).

Таблица 4 - Результаты вычислений для четвертого шага

Второй этап: i=3.

Таблица 5 - Результаты вычислений для третьего шага

Третий этап: i=2.

Таблица 6 - Результаты вычислений для второго шага

Четвёртый этап: i=1.

Таблица 7 - Результаты вычислений для первого шага

Из последней таблицы видно, что условно-оптимальным управлением для этого шага является выбор маршрута (1,3), обеспечивающий минимальные суммарные затраты F₁(x₀, u₁)=F₁(1, (1, 3))=11 на всём пути от пункта 1 до пункта 10. Структура этого пути (наиболее экономный маршрут) выяснится в процессе безусловной оптимизации.

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

Таблица 7. Из пункта 1 (состояние C₁) груз следует направить по дороге (1, 3) (т.к. этому шаговому управлению соответствуют минимальные затраты F₁) в пункт 3 (состояние C₃).

Таблица 6. Из пункта 3 (состояние C₃) груз следует направить по дороге (3, 5) в пункт 5.

Таблица 5. Из пункта 5 (состояние C₅) груз следует направить по дороге (5, 7) в пункт 7.

Таблица 4. Из пункта 7 (состояние C₇)груз следует направить по дороге (7, 10) в пункт 10.

Вывод: наиболее экономный маршрут пролегает через пункты 1, 3, 5, 7, 10, при этом транспортные расходы минимизируются и составляют 11 денежных единиц на единицу груза.

2.3 Применение теории линейного программирования для КУП «СПЕЦКОММУНТРАНС»

2.3.1 Модели линейного программирования. Основные определения

Еще одним классом задач экономико-математического моделирования являются задачи линейного программирования. [1]

Математические модели (ММ) линейного программирования отличаются следующими особенностями. Показатель эффективности W представляет собой линейную функцию от элементов решения (x₁, x₂, ..., x_n). Элементы решения представляют собой ряд неотрицательных переменных x_i0, . Ограничительные условия имеют вид линейных уравнений и неравенств. Ищутся такие решения, которые минимизируют или максимизируют W. Такие системы нельзя решать путём дифференцирования по аргументам x_i, так как экстремум достигается на границах области допустимых значений x_i, то есть там, где действуют ограничения. Чтобы обеспечить линейность ММ, необходимо выполнение допущения делимости и аддитивности. Первое допущение означает, что для каждого технологического процесса (ТПР) суммарное количество ресурсов и прибыль строго пропорциональны объёму выпускаемой продукции. Все показатели ТПР могут быть одновременно увеличены или уменьшены при сохранении их взаимной пропорциональности. Второе допущение показывает, что полное количество потребляемых ресурсов, затраченных при реализации ТПР, суммируется, а полная прибыль равна сумме прибылей в реализации этих ТПР.

Общая формулировка линейных моделей ИСО имеет вид:

найти max W=f(x₁, x₂, ..., x_n)

при ограничениях:

G_j(x₁, x₂, ..., x_n)b_j, (16)

x_i0, .

Существует несколько канонических форм ММ ЛП. Наиболее распространена запись ММ ЛП вида :

. (17)

Любую задачу линейного программирования можно рассматривать как задачу о распределении ограниченных ресурсов b₁, b₂, ..., b_m между n потребителями, представляемые столбцами матрицы ограничений (a_ij) задачи. Любое допустимое решение задачи () даёт конкретное распределение, указывая ту долю каждого из ресурсов, которая должна использоваться при осуществлении соответствующего ТПР.

Если в задаче при малом количестве переменных имеется большое число ограничений (m>n), то переходят к формулировке двойственной задачи:

(18)

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

:

(19)

(20)

Сопоставляя формы записи прямой и двойственной задач ЛП можно установить следующие взаимосвязи.

- Если прямая задача ЛП является задачей максимизации, то двойственная будет задачей минимизации, и наоборот.

- Коэффициенты целевой функции прямой задачи c₁, c₂, ..., c_n становятся свободными членами ограничений двойственной задачи.

- Свободные члены ограничений прямой задачи b₁, b₂, ..., b_m становятся коэффициентами целевой функции двойственной задачи.

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

- Знаки неравенств в ограничениях изменяются на обратные.

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

Переменные y₁, y₂, ..., y_m двойственной задачи иногда называют "теневыми" ценами. Для случая смешанных ограничений соотношения между прямой и двойственной задачами имеет вид

(21)

(22)

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

- Если переменная x_j прямой задачи больше 0, то j-ое условие системы ограничений двойственной задачи является неравенством.

- Если на x_j не накладывается такое ограничение, то j-ое ограничение двойственной задачи будет равенством.

В частности, одним из способов решения такого рода задач является графический метод.

Графическим методом можно решать задачи линейного программирования (ЗЛП) с n=2 переменными, если в её канонической записи число неизвестных n и число линейно независимых уравнений m связаны соотношением n_m 2. В этом случае каноническую форму задачи преобразовывают в симметричную, которая будет содержать не более двух переменных. Решая эту задачу графически, находят два компонента оптимального плана, Подставляя их в ограничения задач, определяют и остальные компоненты.

2.3.2 Составление плана работы погрузочной техники разной мощности

Постановка задачи применительно для КУП «СПЕЦКОММУНТРАНС»: двум погрузчикам разной мощности, это автомобили ТО 28 и ТО 49, за 23 часа нужно погрузить на первой площадке 230 т, на второй - 168 т. Первый погрузчик на первой площадке может погрузить 10 т в час, на второй - 12 т. Второй - на каждой площадке может погрузить по 13 т в час, Стоимость работ, связанных с погрузкой 1 т, первым погрузчиком на первой площадке - 8 ден. ед., на второй - 7 ден. ед., вторым погрузчиком на первой площадке 12 ден. ед., на второй - 13 ден. ед. Нужно составить план работы, т.е. найти, какой объём работ должен выполнить каждый погрузчик на каждой площадке, чтобы стоимость всех работ по погрузке была минимальной. Причём по техническим причинам первый погрузчик на второй площадке должен работать не более 16 часов.

Решение:

Обозначим через x_ij объём работ (в тоннах) i-го погрузчика (i=1, 2) на j-й площадке (j=1, 2). Условия задачи занесём в таблицу 8.

Таблица 8 - Исходные данные для задачи

Построим математическую модель задачи. Целевая функция описывает затраты, связанные с выполнением всех работ:

8 x₁₁+7 x₁₂+12 x₂₁+13 x₂₂.

Ограничения на лимиты рабочего времени:

на необходимость выполнить задание:

условие неотрицательности:

x_ij0 (i, j=1, 2).

Исключаем из модели переменные x₂₁ и x₂₂. Из ограничений-равенств имеем:

x₂₁=230_ x₁₁, x₂₂=168_ x₁₂.

Подставив выражения для x₂₁ и x₂₂ в ограничения-неравенства и целевую функцию, получим ЗЛП с двумя переменными x₁₁ и x₁₂:

Очевидно, что целевая функция Z=4944_4x₁₁_6x₁₂ достигает минимального значения при условии, что Z'=4x₁₁+6x₁₂ принимает максимальное значение. Имеем задачу:

Её графическое решение представлено на рисунке 4.

Функция Z' достигает наибольшего значения при x^*₁₁=100, x^*₁₂=168.

Из выражений для x₂₁ и x₂₂ получим: x^*₂₁=130, x^*₂₂=0.

Итак, по оптимальному плану первый погрузчик (ТО28) должен погрузить 100 т на первой площадке и 168 т - на второй, второму погрузчику (ТО49) надлежит погрузить 130 т на первой площадке. Стоимость всех работ составит 3536 ден. ед. (Z*=4944_4100_6168=3536).

Графическое решение задачи

3 Влияние экономико-математических методов и моделей на повышение эффективности производства КУП «СПЕЦКОММУНТРАНС»

Для ее осуществления на всех уровнях управления необходимо соответствующее количество материальных и трудовых ресурсов, которые должны быть так задействованы, чтобы обеспечивались техническая, организационная, социальная и экономическая целесообразности. Условие целесообразности заключается в том, что при определенных исходных данных получается результат, который по принципу обратной связи оказывает влияние на исходные составляющие. Так, выпуск продукции с точки зрения технической целесообразности -- это точное соответствие техническим показателям. Организационная целесообразность изготовления продукции -- это ее выпуск в нужном объеме и в определенные сроки при соответствующей организации производства [15]. Социальная -- выражается в достижении социальных показателей в области улучшения условий труда, здоровья людей, охраны окружающей среды. Экономическая целесообразность выпуска продукции отражает уровень конечных стоимостных показателей: издержки производства, цена, степень использования ресурсов, прибыль, рентабельность.

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

Следует отличать понятие эффекта и эффективности.

Эффект -- результат каких-либо действий или следствие какой-либо причины. Например, экономия затрат, высвобождение численности рабочих. По народному хозяйству экономический эффект проявляется в росте валового внутреннего продукта; на предприятии -- в увеличении прибыли, росте объемов производства, снижении себестоимости, улучшении качества продукции, расширении ассортимента. В целом можно выделить 3 группы показателей экономического эффекта:

а) объемные (валовая, товарная, нормативно-чистая продукция, объем строительно-монтажных работ, прибыль и др.);

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

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

Экономическая эффективность -- это результативность использования затрат (или ресурсов). Определяется эффективность соизмерением эффекта и затрат. Можно соизмерить затраты к эффекту или эффект к затратам.

эффект затраты, ресурсы

Эффективность = ------------------------ (23)

затраты, ресурсы, эффект

В этом случае прослеживаются два аспекта:

а) необходимость измерения эффективности различных видов затрат и ресурсов и определения путей их повышения;

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

3.2 Влияние сетевых и графовых моделей на повышение эффективности производства КУП «СПЕЦКОММУНТРАНС»

3.2.1 Основные понятия сетевых и графовых моделей

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

Технология решения этих задач основывается на следующих понятиях и обозначениях. Каждая дуга графа, соединяющая два узла x_i и x_j, характеризуется длиной l(x_i, x_j). Каждый из узлов сети (x_i) называют вершиной графа G, представляющего собой всю сеть. Дуги могут быть как ориентированными, обозначаемыми на графе G в виде стрелок, так и неориентированными. Общее число вершин графа G равно n и индексы вершин х_i меняются от i=1 до i=n.

Введём понятие транспортная сеть - связный ориентированный мультиграф без петель в котором:

- существует одна и только одна вершина х₀, называемая входом сети (истоком);

- существует одна и только одна вершина x_n, называемая выходом сети (стоком);

- каждой дуге g_ij(х_i, х_j) отнесено целое число С(х_i, х_j)0, называемое пропускной способностью.

Для произвольной вершины х_i множество дуг, входящих в неё, обозначим через , а множество дуг, выходящих из х_i, обозначим через . Тогда потоком (g_ij) транспортной сети назовём целочисленную функцию, определённую на множестве дуг графа G(х), которая удовлетворяет следующим свойствам:

а) : (24)

б) : (25)

в) . (26)

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

Приток вещества в вершине x_n представляет собой величину транспортного потока в сети и определяется по формуле

. (27)

Если сделать разрез графа G через множество вершин {x_i}=A, то множество дуг, заходящих в множество вершин A, назовём разрезом сети. Пропускная способность разреза равна сумме пропускных способностей дуг, входящих в множество A:

. (28)

Любой элемент вещества (груз), движущийся от x₀ к x_n, пройдёт хотя бы один раз по некоторой дуге разреза . Тогда, каковы бы ни были поток (g_ij) и разрез сети , всегда имеет место неравенство

. (29)

Существует следующая лемма.

Если для какого-либо разреза . имеет место равенство , то

а) поток имеет наибольшую величину;

б) разрез обладает наименьшей пропускной способностью, равной сумме пропускных способностей дуг.

3.2.2 Нахождение кратчайшего пути в транспортной сети

В зависимости от содержания задачи может быть два случая: когда рёбра графа G единичной длины; когда рёбра графа произвольной длины. Для каждого из этих случаев разработаны две разновидности алгоритма решения задачи. Рассмотрим первый из случаев. Транспортная сеть представлена графом G₁, в котором длины рёбер одинаковы и равны некоторой постоянной величине (l₁=const). Для простоты изложения будем считать, что l₁=1. Каждому узлу x_i графа G₁ приписываем индекс _i, равный длине кратчайшего пути из x_i в конечный узел x_n.

Алгоритм основан на последовательном приписывании индексов, последовательно проходя в обратном направлении (от x_n до x₀) следующим образом.

- Узлу x_n приписывается индекс _n=0.

- Всем узлам (ещё не имеющим индексов), от которых идёт ребро в конечный узел, приписываем индекс _i=1.

- Всем следующим узлам, от которых идут рёбра в только что помеченные узлы приписываем индекс (_i+1).

Этот процесс продолжается, концентрическими кругами расширяясь от x_n, до тех пор, пока не будет помечен начальный узел x₀ графа G₁. Значение индекса ₀ у начального узла x₀ и будет равно длине кратчайшего пути.

Пример. Относительно КУП «СПЕЦКОММУНТРАНС» задача формулируется, как нахождение кратчайшего пути следования автомобиля, производящего работу по вывозу мусора на свалку. В общем виде задача звучит так. Пусть дан граф G₁, представленный на рисунке 5. Сеть состоит из десяти узлов. Необходимо найти кратчайший путь от x₀ до x_n. На рисунке 5 показаны значения индексов _i для каждого i-го узла. Начинается расчёт узла x_n (для которого _n=0) и завершается установкой индексов у всех остальных узлов. Индекс при x₀ равен ₀=3. Поэтому длина кратчайшего пути равна L_кр=3. Само направление кратчайшего пути находим путём составления последовательности узлов по направлению убывания у них индексов от ₀=3 до _n=0. Для графа G₁ кратчайший путь составляют узлы: x₀, x₁, x₇, x_n. На рисунке 5 кратчайший путь выделен жирными стрелками.