МЕТОД
“НАДУВНОГО ШАРИКА” ДЛЯ РЕШЕНИЯ ЗАДАЧ
ПЛАНИРОВАНИЯ
ПРОИЗВОДСТВА
Г.Б.
Бронфельд ( Н.Новгород )
В современных условиях значительное
количество отечественных предприятий имеет свой самостоятельный опыт
эксплуатации и развития информационных систем на базе средств вычислительной
техники, в том числе сетей ПЭВМ, для планирования и управления производством.
Однако сам процесс планирования
производства или выполняется управленческим персоналом с помощью калькуляторов
или с помощью простейших методов, реализуемых на ЭВМ.
Современные
условия рыночной экономики характеризуются недостатком денежных и материальных
ресурсов, носящим, к сожалению, длительный характер, и усилением конкурентной
ценовой борьбы на продукцию.
И то и
другое приводит к тому, что каждый процент сэкономленных денежных, материальных
ресурсов или ускорение их оборачиваемости приносит значительные доходы. А
несколько процентов вообще могут разделять предприятия на процветающие и
разоряющиеся.
При этом
управленец самостоятельно, как правило, не в состоянии принять оптимальное
решение (принимает практически всегда лишь рациональное решение, значительно
отличающееся от оптимального подчас на десятки и сотни процентов) по следующим
причинам:
задачи планирования сложны, а человек не в состоянии одновременно
учесть все взаимосвязи;
задачи носят нелинейный характер, а человек часто плохо
решает даже простейшие нелинейные задачи;
задачи
планирования часто имеют большую размерность, для некоторых из которых даже
применение ЭВМ и современных методов не позволяет найти оптимальное решение
[1,2];
при
быстром изменении ситуации, например, с случае аварии, человек, как правило, не
в состоянии принять наилучшее решение;
человек,
который временно замещает опытного управленца, например, во время его отпуска,
болезни и т.п., как правило, даже близко не способен его заменить по точности
принимаемых решений (пока сам не научится и не вникнет в текущую ситуацию).
ЭВМ
широко применяется для оптимального планирования производства, начиная с 60-х
годов.
В
развитых странах на многих производственных предприятиях системы оперативного
и долгосрочного планирования на базе ПЭВМ
достигли очень высокого уровня. При этом продаются многочисленные пакеты
программного обеспечения для этих целей, часто весьма дорогие с точки зрения
российских условий.
В СССР
это шло своим путем, как процесс создания АСУ разного уровня, хотя конечная
точка развития оказалась совершенно одинаковая. Однако в перестроечные годы
этот процесс оказался разорванным из-за реформы системы собственности, резкого
спада объемов производства, резкого изменения экономических условий
хозяйствования, резкого изменения системы налогового законодательства,
свертывания отечественного производства вычислительной техники, совпавшего с
этим временем изменением базы используемых ЭВМ с больших и средних ЭВМ на сети
ПЭВМ определенных типов. Информационные подсистемы низового уровня на многих
предприятиях удалось сохранить, но системы верхнего уровня повсеместно
оказались разрушенными или резко устарели. Отечественные многочисленные
организации-разработчики систем АСУ оказались почти полностью или ликвидированы
или поменяли сферы деятельности.
Возникли
относительно немногочисленные малые предприятия, в большинстве случаев с
молодым, но недостаточно опытным составом, ориентированных почти повсеместно
на разработку, внедрение и продажу простых информационных систем с относительно
простыми процедурами обработки информации.
Сейчас
для многих предприятий машиностроительного профиля при наличии заказов стоит
задача скорейшего их выполнения в условиях недостатка кадров, недостатка требуемого
оборудования и материальных ресурсов. Задачи эти, как правило, имеют большую размерность и многочисленные
нелинейности. Считается, что общего метода решения такой задачи, кроме полного
перебора вариантов не существует. А это часто не под силу и современным ЭВМ
[1]. Тем не менее такой метод для
реальных задач существует уже более 25 лет. Это метод “надувного шарика” (метод
Бронфельда) [3], разработанный в 1975 г..
Рассмотрим
одну из задач, поставленных Л.В.Канторовичем [4,5], с которой началось
рассмотрение задач нелинейного программирования.
Имеется
множество предприятий (участков, станков) I = { i : i =1,
2,…, m} на которых необходимо выпускать множество видов
изделий J = { j : j =1,
2,…, n} в заданном ассортименте. Ассортиментный набор
изделий задан вектор - столбцом [b j o]. Известна матрица производительности i-го предприятия по выпуску j-го изделия [а
i j] . Пусть x i j –
время работы i – го предприятия по выпуску j – го изделия.
Примем
за единицу время, на которое рассчитана вся программа работы. Требуется так
распределить производство изделий между предприятиями, т.е. найти матрицу [x i j о],
чтобы в единицу времени выпускалось максимальное количество полных
ассортиментных наборов изделий m .
Для
судостроения эта задача может быть интерпретирована как задача распределения заданий
по выпуску комплектующих изделий по заводам (цехам, участкам) с целью максимизации
количества выпускаемых судов на судостроительном заводе, для автомобилестроения
– с целью максимизации выпуска автомобилей, для станкостроения – станков и т.п.
Возможна
также постановка задачи, когда требуется найти минимальное время, за которое
будет выполнен заданный ассортиментный набор изделий.
Итак,
требуется найти матрицу оптимального решения [x i j о], максимизирующую линейную форму
L при
условиях
m
S a i j х i j ³ b j
o m , (2)
i =1
n
S x i j = 1,
(3)
j = 1
х i j ³ 0, (4)
a i
j ³ 0
, b
j o > 0. (5)
Задача
сформулирована в линейном виде и относится к задачам, решаемым методами линейного
программирования. Например, для решения данной задачи малой и средней размерности
известны эффективные методы [1], [5 - 7].
Однако возникают трудности при решении задач большой размерности [1].
Кроме того, существует проблема вырожденности матриц условий, а также
нечувствительности известных известных методов к особенностям условий задачи,
например, к слабозаполненности матриц. Этой задаче присуща выпуклая область
изменения переменных.
Ранее считалось,
что задача (1) – (5) при максимизируемой форме (1) является частным случаем
стандартной задачи линейного программирования
с суммарной линейной формулой.
Однако
оказалось, что именно для задачи (1) – (5) существует принципиально иной метод
решения задач, уже не только линейного программирования, но и нелинейного
программирования.
Реальные
практические задачи осложнены различными нелинейными эффектами. Например,
обычная потребность в переналадках оборудования при переходе на новый вид
изделий, приводит к разрывам, а область изменения переменных становится
невыпуклой и представляет собой форму "ежа ".
Предлагаемый
метод "надувного шарика" ориентирован на решение реальных практических
задач вида (1) – (5), имеющих линейный
или нелинейный характер, в том числе большой размерности, с невыпуклой, но
ограниченной областью изменения переменных.
Рассматриваемый
метод основан на итеративном подходе [8], использует идеи метода максимального
элемента [6] и метода ветвей и границ
[9], а также использовании специального приема, направленного на понижение
размерности в процессе решения задачи. Эффективность метода повышается при
решении задач со слабозаполненной матрицей [a i j] , большой
разницей в величинах a i j , использовании условия целочисленности решения
[х i j]. А
это как раз характерно для практических задач.
Первоначально
находится нулевое решение. Им может быть ранее используемое решение (на
практике), но при заведомо меньшей загрузке. Или же решается быстро задач при
значительно меньшем векторе.
Само название
метод "надувного шарика" трактуется следующим образом. Если
внутрь замкнутой, но условно невыпуклой
области изменения переменных поместить спущенный детский шарик и начинать его
надувать, то момент , когда он изнутри начнет облегать эту невыпуклую область,
является моментом нахождения оптимального решения. Предлагаемый метод решения
задач (1) – (5) с нелинейными эффектами.
Весьма ценной
особенностью метода "надувного шарика" является то, что автоматически
решается задача целочисленного программирования, поскольку решение всегда
ищется изнутри области изменения переменных, а решения рассчитываются с той
точностью, которая требуется.
В 60-е, 70-е
годы периодически в печати дебатировалось [9], что лучше - суммарный критерий
линейного программирования, который обеспечивает оценку в денежной форме и максимизирует
прибыль, или же критерий (1), максимизирующий выпуск продукции в физических
единицах.
Современная
практика развития производств в рыночной экономики четко показала – предмета
спора по существу нет. Максимизация выпуска изделий или же выпуск заданного
количества изделий за минимальное время настолько мощно положительно влияет на
снижение удельных затрат и себестоимости (а соответственно на максимизацию
прибыли), на демонстрацию способности предприятия выпустить продукцию в
заданные сроки, на управляемость предприятия, что с этим сложно спорить.
А сам процесс
увеличения прибыли отдельно происходит при выборе рыночной линии для
предприятия, выборе цены на изделия, анализе отдельных статей себестоимости,
использования финансовых методов для ускорения оборачиваемости денежных средств
и правильном налоговом регулировании. А это иные задачи с другими
математическими постановками и другими критериями, но часто это снова не суммарный критерий.
Суммарный
критерий тоже необходим для многих задач, но, как правило, не для задач
планирования производства.
В настоящее
время стали модными несколько иные подходы и математические методы решения
задач [10,11] , но это нисколько не снижает актуальности рассматриваемой постановки
задачи и предлагаемого метода ее решения.
К задаче (1) –
(5) сводятся не только задачи планирования машиностроительного дискретного
производства (кстати не только машиностроительного, но, например, это подойдет
для производств переработки пластмасс).
Этот же метод
применим, например, для решения задач операционно-сетевого планирования [12].
Метод позволяет:
повысить объем
производства или снизить удельные затраты от нескольких процентов до нескольких
десятков процентов (в зависимости от отработанности производства);
обеспечить
прибыльность вложений в применение метода (иногда) до нескольких тысяч
процентов при окупаемости в несколько недель.
ЛИТЕРАТУРА
1.
Гилл Ф., Моррей У.,
Райт М. Практическая оптимизация. - М.:
Мир, 1985.- 509 с.
2.
РД5.160.039-87.
Внутризаводское планирование инструментального производства в условиях
функционирования автоматизированной системы управления. Методические указания.-
Горький: ВНИИТСМ "СИРИУС". 1988.-137 с.
3.
Бронфельд Г.Б.
Алгоритм решения задачи оптимального распределения плана производства. // Труды
института. Автоматизация и механизация управления производством. Горький.
НИИУавтопром. 1977, вып. 2, с.75-83.
4.
Канторович Л.В.
Математические методы организации и планирования производства.- Л.: ЛГУ, 1939.-
89 с.
5.
Канторович Л.В.
Экономический расчет наилучшего использования ресурсов.- М.: АН СССР, 1960.-
323 с.
6.
Берзин Е.А.
Оптимальное распределение ресурсов и элементы синтеза систем.- М.: Советское
радио, 1974.- 324 с.
7.
Шор Н.З., Гершкович
В.И. Об одном свойстве алгоритмов для решения задач выпуклого программирования.
// Кибернетика, 1979, №4, с. 62-67.
8.
Беленький В.В.,
Волконский В.А. и др., Итеративные методы теории игр и программирования. - М.: Наука, 1974.- 239 с.
9.
Корбут А.А.,
Финкельштейн Ю.Ю. Дискретное программирование. - М.: Наука, 1969.- 368 с.
10.
Андрейчиков А.В.,
Андрейчикова О.Н. Анализ, синтез, планирование решений в экономике..- М.:
Финансы и статистика, 2000.-368 с.
11.
Сергеев В.И.
Логистика в бизнесе. – М.: ИНФРА –М, 2001.- 608 с.
12.
Первозванский А.А.
Математические модели в управлении производством.- М.: Наука, 1975.- 616 с.