Исследование и разработка методов решения задач производственного планирования

УДК 519.7

О.Н. БЕЗГИНОВА, А.Н. ГВОЗДИНСКИЙ, М.Д. ПОВАЖНАЯ

ИССЛЕДОВАНИЕ И РАЗРАБОТКА МЕТОДОВ РЕШЕНИЯ ЗАДАЧ ПРОИЗВОДСТВЕННОГО ПЛАНИРОВАНИЯ

Исследуются методы решения задач в производственном планировании современного промышленного предприятия. Предлагается оптимизационный метод решения задач производственного планирования, позволяющий оптимально распределять ресурсы и выявлять «узкие места» предприятия.

1. Введение

Актуальность исследования. В современном мире человек, стараясь сделать все наилучшим образом, в основу любой целенаправленной деятельности закладывает процессы принятия решений. Теория принятия решений - быстро развивающаяся наука. Задачи,

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

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

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

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

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

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

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

- анализ полученного решения, выявление «узких мест» на производстве; дать рекомендации по их разрешению;

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

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

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

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

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

Рассмотрим на конкретном практическом примере построение математической модели некоторого предприятия.

Значения ограничений ресурсов рассматриваемого предприятия приведены в табл.1,2.

Таблица 1. Плановые задания

Лимитированные ресурсы и показатели Номенклатура изделий

В1 В2 В3 В4 В5

Ограничения по ассортименту > 10000 < 30000 > 15000 > 20000 > 30000

Таблица 2. Нормы затрат ресурсов

Лимитированные ресурсы и показатели Номенклатура изделий Я], х 105

В, В 2 В 3 В 4 В 5

Фонд производственного времени,станко-часов 2 3 1 1 3 9

М атериалы, кг 1 2 3 4 2 8

Комплектующие изделия, шт. 3 1 3 2 4 6

Трудозатраты,часов 3 4 1 2 3 5

Фонд заработной платы 3 2 3 4 1 9,5

Выпуск продукции в стоимостном выражении, грн 10 12 8 16 11 25

Себестоимость, грн 3 4 4 2 1

Обозначим количество каждой 1-й продукции, которую выпускает данное предприятие, как XI, фонд производственного времени - Т1, материалы - М1, комплектующие изделия -Ы, трудозатраты - Ы, фонд заработной платы - 81, выпуск продукции в стоимостном выражении - Р1, себестоимость - С1, ограничение по ассортименту - А1, объем ресурсов - Я]. Количество каждой 1-й продукции, которую выпускает данное предприятие - XI. Ограничение по фонду производственного времени в общем виде представлено форму-5

лой 2 Т1 * XI < Ю. 1=1

Подставив значения из табл. 1, мы получим первое уравнение системы ограничений: 2х1 + 2х2 + х3 + х4 + 3х5 < 9*105.

Ограничение по объему используемых материалов в общем виде представлено форму-

5

лой 2 М1 * XI < Я2. 1=1

Запишем второе уравнение системы ограничений: х1 + 2х2 + 3х3 + 4х4 + 2х5 < 8*105. Ограничение по количеству комплектующих изделий в общем виде представлено фор-

5

мулой 2 к1 * XI < Я3.

Таким образом, третье уравнение системы ограничений будет иметь вид:

3х1 + х2 + 3х3 + 2х4 + 4х5 < 6*105.

5

Ограничение по затратам труда в общем виде представлено формулой 2 Ь1*Ж <

1=1

Четвертое уравнение системы ограничений будет иметь вид:

3х1 + 4х2 + х3 + 2х4 + 2х5 < 5* 105. Ограничение по фонду заработной платы труда в общем виде представлено формулой

5

2 Б1*» < Я5. 1 =1

Следующее уравнение системы ограничений будет иметь вид:

3x1 + 2x2 + 3x3 + 4x4 +...+1x5 < 9,5*105. Ограничение по выпуску продукции в стоимостном выражении в общем виде представ-5

лено формулой 2 Pi * XI < R6 i=1

И, наконец, шестое уравнение системы ограничений будет иметь вид:

10х1 + 12х2 +...+ 8x3 16x4 + 11х5 < 25*105. Данные об ассортименте дают нам следующие ограничения:

x1 > 10000, x2 < 30000, x3 > 15000, x4 > 20000, x5 > 30000. Таким образом, система ограничений для данной задачи имеет вид:

2x1 + 2x2 + x3 + x4 + 3x5 < 9*105, x1 + 2x2 + 3x3 + 4x4 + 2x5 < 8*105, 3x1 + x2 + 3x3, + 2x4 + 4x5 < 6*105, 3x1 + 4х2 + х3 + 2х4 + 2х5 < 5* 105, 3х1 + 2х2 + 3х3 + 4х4 + х5 < 9,5*105, 10х1 + 12х2 + 8х3 + 16х4 + 11х5 < 25*105, х1 > 10000, х2 < 30000, х3 > 15000, х4> 20000, х5> 30000.

При этом необходимо учитывать условие X; > 0, 1 = 1,5 .

Теперь составим функции цели, которые позволят нам определить наиболее оптимальное использование ресурсов и оптимизировать работу предприятия.

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

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

5

Запишем ее в общем виде: 2 (Р; - С;)*Х; ^ МАХ.

;=1

Для конкретных значений функция цели будет иметь вид:

Б1(Х) = 7х1 + 8х2 + 4х3 +...+ 14х4+ 10х5 ^ МАХ . Вторая функция цели будет выражать максимизацию валового объема выпуска продук-

5

ции в денежном выражении. Запишем ее в общем виде 2 Р;*Х; ^ МАХ.

Для конкретных значений функция цели примет вид:

Б2(Х) = 10х1 + 12х2 + 8х3 + 16х4 +...+ 11х5 ^ МАХ . Третьей функцией цели представим минимизацию себестоимости, которая имеет общий

5

вид: 2 С1*Х1 ^ М1К ;=1

Запишем эту функцию с конкретными значениями: Р3(Х) = 3х1 + 4х2 + 4х3 + 2х4 +...+ х5 ^ МЖ

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

5

ственного времени: 2 Т; * Х1 ^ МАХ и Б4(Х) = 2х1 + 2х2 + х3 + х4 + 3х5 ^ МАХ. ;=1

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

3. Методы исследования

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

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

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

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

Существуют следующие виды математического программирования: линейное, нелинейное, дискретное, динамическое, выпуклое программирование и др.

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

Нелинейное программирование - это раздел математического программирования, изучающий методы решения таких экстремальных задач, в которых результаты возрастают или убывают непропорционально изменению масштабов использования ресурсов. В краткой форме задачу нелинейного программирования можно записать так: тах О(х) при условиях g(x) < Ь, х > 0, где х - вектор искомых переменных, О(х) - целевая функция, g(x) -функции ограничений, Ь - вектор констант ограничений.

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

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

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

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

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

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

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

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

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

В результате применения указанного метода получим следующий оптимальный план (рисунок).

2) ' 2500000 10+0М 12+ОМ 8+ОМ 16+ОМ 11+0М о+ом о+ом о+ом 0+0М 0+0М 1+0М о^ом о+ом о+ом о+ом о+ом о+ом о+ом о+ом о+ом

Оптимальный план решения задачи, полученный путем применения симплекс-метода

В результате вычислений мы получили следующее решение: Х* = || 10000, 30000, 15000, 99375, 30000 ||; Б(Х*) = 2500000.

Запишем математическую модель двойственной задачи максимизации валового объема выпуска продукции:

р(У) = 9*105у1 + 8*105у2 + 6*105у3 + 5*105у4 + 9,5*105у5 + 25*105у6 -- 10000у7 + 30000у8 - 15000у9 - 20000у10 - 30000у11 ^ МШ ,

2у1 + У2 + 3у3 + 3у4 + 3у5 + 10уб - У7 > 10,

2у1 + 2у2 + у3 + 4у4 + 2у5 + 12уб + у8 > 12,

у1 + 3у2 + 3у3 + у4 + 3у5 + 8уб - у9 > 8, у1 + 4у2 + 2у3 + 2у4 + 4у5 + 16уб - ую > 16, 3у1 + 2у2 + 4у3 + 2у4 + у5 + 11у6 - уи > 11, У > 0.

Решение двойственной задачи получается из т+1 строки оптимального плана и имеет вид: У* =|| 0, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0 ||.

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

4. Выводы

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

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

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

Список литературы: 1. Угланов Г.М и др. Методы разработки интегрированных АСУ промышленными предприятиями. М.: Энергоатомиздат, 1983. 380с. 2. Таха, Хэмди А. Введение в исследование операций. М.: Мир, 2001. 400с. 3. Карманов В.Г. Математическое программирование. М.: Наука, 1980. 256с. 4.Химмельблау Д. Прикладное нелинейсное программирование: Пер. с англ. М.: Мир, 1975. 534с.

Поступила в редколлегию 05.03.2010

Безгинова Ольга Николаевна, студентка факультета КН ХНУРЭ. Адрес: Украина, 61085, Харьков, ул. Астрономическая, 44а, кв. 15, тел. 720-56-19.

Гвоздинский Анатолий Николаевич, канд. техн. наук, профессор кафедры искусственного интеллекта ХНУРЭ. Научные интересы: оптимизация процедур принятия решений в сложных системах управления. Адрес: Украина, 61166, Харьков, ул. Ак. Ляпунова, 7, кв. 9, тел. 702-38-23.

Поважная Марина Дмитриевна, студентка факультета КН ХНУРЭ. Адрес: Украина, 61033, Харьков, ул. Саперная, 20, кв. 121, тел. 717-26-45.