В зависимости от вида целевой функции и функций ограничений (линейные, нелинейные, динамические, стохастические, дискретные) методы нахождения решений таких задач носят названия методов линейного, нелинейного, динамического, стохастического, дискретного программирования.
Задачи сетевого планирования и управления рассматривают соотношения между сроками окончания крупного комплекса операций (работ) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальных продолжительностей комплекса операций, оптимального соотношения величин стоимости и сроков их выполнения.
Задачи массового обслуживания посвящены изучению и анализу систем обслуживания с очередями заявок или требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик, например в определении числа каналов обслуживания, времени обслуживания и т. п.
Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов (точки заказа) и размера заказа. Особенность таких задач заключается в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но, с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта.
Задачи распределения ресурсов возникают при определенном наборе операций (работ), которые необходимо выполнять при ограниченных наличных ресурсах, и требуется найти оптимальные распределения ресурсов между операциями или состав операций.
Задачи ремонта и замены оборудования актуальны в связи с износом и старением оборудования и необходимостью его замены с течением времени. Задачи сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а также моментов замены оборудования модернизированным.
Задачи составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, обработки деталей) на различных видах оборудования.
Задачи планировки и размещения состоят в определении оптимального числа и места размещения новых объектов с учетом их взаимодействия с существующими объектами и между собой.
Задачи выбора маршрута, или сетевые задачи, чаще всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов.
Среди моделей исследования операций особо выделяются модели принятия оптимальных решений в конфликтных ситуациях, изучаемые теорией игр.
К конфликтным ситуациям, в которых сталкиваются интересы двух (или более) сторон, преследующих разные цели, можно отнести ряд ситуаций в области экономики, права, отношений регионального уровня управления и местного самоуправления и др. В задачах теории игр необходимо выработать рекомендации по разумному поведению участников конфликта, определить их оптимальные стратегии.
На практике в большинстве случаев успех операции оценивается не по одному, а по нескольким критериям одной либо разных направленностей (на max и min). Такие задачи получили название многокритериальных задач исследования операций.
Для того чтобы из множества критериев, в том числе и противоречащих друг другу (например, прибыль и расход), выбрать целевую функцию, необходимо установить приоритет критериев. Обозначим критерии f1(x), f2(x), …, fn(x) (здесь x – условный аргумент). Пусть они расположены в порядке убывания приоритетов. В зависимости от определенных условий возможны в основном два варианта:
– в качестве целевой функции выбирается критерий f1(x), имеющий наивысший приоритет;
– рассматривается комбинация
,
где 
– некоторые коэффициенты (веса).
Величина f(x), учитывающая в определенной степени все критерии, выбирается в качестве целевой функции.
В условиях определенности 
– числа, fi(x) – функции. В условиях неопределенности fi(x) могут оказаться случайными и вместо f(x) в качестве целевой функции следует рассматривать математическое ожидание суммы частных критериев.
Попытка сведения многокритериальной задачи к задаче с одним критерием эффективности (целевой функцией) в большинстве случаев не дает удовлетворительных результатов. Другой подход состоит в отбрасывании («выбраковке») из множества допустимых решений заведомо неудачных решений, уступающих другим по всем критериям. В результате такой процедуры остаются так называемые эффективные (или «паретовские») решения, множество которых обычно существенно меньше исходного.
А окончательный выбор «компромиссного» решения (не оптимального по всем критериям, которого, как правило, не существует, а приемлемого по этим критериям) остается за человеком – лицом, принимающим решение.
Математическое моделирование в исследовании операций является практически не поддающимся научной формализации процессом. Поэтому полезно знакомство с техникой математического моделирования на конкретных примерах.
Пример 1. Управление портфелем активов. Рассмотрим проблему принятия инвестором решения о вложении имеющегося у него капитала. Набор характеристик потенциальных объектов инвестирования, имеющих условные имена от А до F, приведен в табл. 6.
Таблица 6
Характеристики потенциальных объектов инвестирования
Название | Доходность, % | Срок выкупа, год | Надежность, |
А | 5,5 | 2003 | 5 |
В | 6,0 | 2005 | 4 |
C | 8,0 | 2010 | 2 |
D | 7,5 | 2004 | 3 |
E | 5,5 | 2003 | 5 |
F | 7,0 | 2003 | 4 |
Предположим, что при принятии решения о приобретении активов должны быть соблюдены условия:
а) суммарный объем капитала, который должен быть вложен, составляет 100 000$;
б) доля средств, вложенная в один объект, не может превышать четверти от всего объема;
в) более половины всех средств должны быть вложены в долгосрочные активы (допустим, на рассматриваемый момент к таковым относятся активы со сроком погашения после 2004 г.);
г) доля активов, имеющих надежность менее 4 баллов, не может превышать трети от суммарного объема.
Приступим к составлению экономико-математической модели для данной ситуации. Целесообразно начать процесс с определения структуры управляемых переменных. В рассматриваемом примере в качестве таких переменных выступают объемы средств, вложенные в активы той или иной фирмы. Обозначим их как xA, xB, xC, xD, xE, xF. Тогда годовая прибыль от размещенных активов, которую получит инвестор, может быть представлена в виде
P = 0,055xA + 0,06xB + 0,08xC + 0,075xD + 0,055xE + 0,07xF.
На следующем этапе моделирования мы должны формально описать перечисленные выше ограничения a-r на структуру портфеля:
а) ограничение на суммарный объем активов:
xA + xB + xC + xD + xE + xF
100 000;
б) ограничение на размер доли каждого актива:
xA 25 000, xB 25 000; xC 25 000;
xD 25 000, xE 25 000; xF 25 000;
в) ограничение, связанное с необходимостью вкладывать половину средств в долгосрочные активы:
xB + xC 
50 000;
г) ограничение на долю ненадежных активов:
xC + xD 30 000.
Система ограничений в соответствии с экономическим смыслом задачи должна быть дополнена условиями неотрицательности для искомых переменных:
xA 0; xB 0; xC0; xD 0; xE 0; xF 0.
Таким образом, сформулирована математическая модель выбора решения инвестором. В рамках этой модели может быть поставлена задача поиска таких значений переменных xA, xB, xC, xD, xE, xF, при которых достигается наибольшее значение прибыли и одновременно выполняются ограничения на структуру портфеля активов.
Пример 2. Определить оптимальный план выпуска изделий, при котором предприятие будет иметь наибольшую прибыль. Исходные данные приведены в табл. 7. Формулируем экономико-математическую модель задачи. Она будет иметь следующий вид:
обеспечить 
при условиях 
Модель по своему виду относится к стандартной задаче линейного программирования. Такие задачи решаются симплекс-методом. Преобразуем ее с заменой неравенств в условиях на уравнения:
Переменные Х4…Х7 – дополнительные. Экономический смысл дополнительных переменных состоит в том, что они обозначают количество неиспользуемого ресурса, когда объем ресурсов ограничен сверху, или количество недостающего ресурса, когда объем задан по нижнему пределу.
После введения дополнительных переменных модель подготовлена к решению симплекс-методом. На первом шаге в симплексной таблице все основные переменные приравниваются к нулю. Это означает, что производство не начато, ресурсы пока не используются, а дополнительные переменные равны своему предельному значению.
На следующем шаге вводим производство изделия, соответствующего одной из основных переменных. В принципе можно вводить в базис любую переменную, но целесообразнее начать с той, которая входит в целевую функцию с наибольшим показателем эффективности. То же повторяется в следующих итерациях, пока не будет получено оптимальное решение.
Таблица 7
Исходные данные для оптимального планирования производства
Виды ресурсов | Нормы затрат на единицу изделия | Объем | Дополнительный выпуск 4-го изд. | ||
1-е изд. | 2-е изд. | 3-е изд. | |||
Сталь, кг | 5 | 7 | 4 | 4 | 6 |
Пластмасса, кг | 10 | 5 | 20 | 80 | 4 |
Оборудование механического цеха (станко-ч.) | 5 | 2 | 1 | 10 | 3 |
Оборудование гальванического цеха (станко-ч.) | 2 | 1 | 1 | 6 | 2 |
Прибыльна единицу изделий, руб. | 18 | 12 | 8 | 14 | |
Объем выпуска | Х1 | Х2 | Х3 | Х4 |
В предельной интерпретации в столбцах дополнительных переменных в (m + 1)-й строке получаем экономико-математические оценки соответствующих ограничивающих факторов, то есть решение двойственной задачи.
Запишем двойственную задачу:
обеспечить 
при условиях 
Формулировка прямой задачи: определить объем выпуска изделий j-го вида, чтобы получить максимальную прибыль.
Формулировка двойственной задачи: определить, какую надбавку yi к стоимости единицы каждого из ресурсов можно назначить, чтобы при заданных объемах ресурсов Ai величинах Pj прибыли за единицу изделий и нормативах aij расходов ресурсов на изготовление продукции получить минимум общей суммы надбавки к стоимости ресурсов.
В (m + 1)-й строке последней итерации решения прямой задачи по симплекс-методу получаем следующие значения оценок ресурсов:
y1 = 0,842 р/кг;
y2 = 0;
y3 = 1,5 р/станко/ч;
y4 = 3,166 р/ станко/ч.
Решение двойственной задачи yi – вектор разрешающих множителей – дает оценки ограничивающих производственных факторов.
Оценки ограниченных ресурсов характеризуют возможные улучшения целевой функции при увеличении ресурсов на единицу. Чем больше по абсолютной величине значение оценки ресурса, тем более эффективно его использование, тем больший эффект даст его экономия. В данном примере оценка y4 = 3,166 р/ станко/ч максимальна, что означает наибольшую дефицитность четвертого вида ресурса оборудования гальванического цеха. При увеличении мощности на 1 станко/ч получим дополнительную прибыль в 3,166 р. По величине оценки можно сделать вывод о том, что гальванический цех – узкое место производства. При уменьшении ограниченного ресурса на единицу значение целевой функции ухудшается на величину оценки данного ресурса. В этом примере уменьшение объема стали (первого ресурса) на 1 кг даст снижение прибыли на 0,842 р.
Ресурс, имеющий нулевую оценку, находится в избытке (y2 = 0, следовательно, второй вид ресурса, т. е. пластмасса, находится в избытке). Изменение этого ресурса не окажет влияния на целевую функцию.
По уравнению оценок двойственной задачи делается вывод о целесообразности включения переменных в оптимальный план. Для переменных, входящих в оптимальный план, справедливо равенство
.
Для переменных, которые целесообразно включать в оптимальный план, 
.
Обратимся к примеру, рассмотренному выше. Допустим, что министерство намечает включить в программу завода выпуск изделий четвертого вида. Указываем нормативы ai4 и прибыль Р4 в дополнительной графе таблицы исходных данных. Требуется определить, целесообразно ли изменение программы при тех же объемах лимитов на ресурсы. Это можно сделать без повторного решения задачи путем составления и анализа уравнения оценок для четвертого изделия:
.
Следовательно, затраты в оценках больше, чем получаемая прибыль, и включать четвертое изделие в план невыгодно.
Разработанные пакеты прикладных программ по оптимизационным методам, в том числе для ПЭВМ, позволяют не только отыскивать оптимальное решение задачи, но и проводить анализ условий производств.
Методы математического программирования в совокупности с программными модулями могут найти (и находят на передовых предприятиях) обширную сферу применения в составе внедряемых автоматизированных систем управления. О возможных областях их применения свидетельствует табл. 8.
Более подробный анализ полезности применения методов исследования операций приводит Р. Шеннон (табл. 9, 10).
Таким образом, представленные примеры возможностей методов ИСО с имеющимся математическим и программным аппаратом реализации подтверждают целесообразность их более широкого применения на практике. Причины неприятия методов ИСО практиками, на наш взгляд, можно разделить на два вида: объективного характера, обусловленные дефицитом времени на разработку решения, большой трудоемкостью построения моделей, адекватно отражающих специфику функционирования социально-экономической системы (по оценкам Д. Форрестера, на разработку математической модели предприятия требуется 5 – 6 человеко-лет трудозатрат), и соответственно большой стоимостью таких разработок; субъективного характера, обусловленные недостаточной компетентностью специалистов в области построения моделей – инженеров-системотехников в знании предметной области, а также наличием факторов неопределенности и непредсказуемости воздействий внешней среды и человеческого фактора.
Интенсивно ведутся разработки математических моделей и прикладного программного обеспечения в сфере разработки решений по логистическому менеджменту. Разработаны типовые программные комплексы, в том числе на базе геоинформационных систем, позволяющие находить оптимальные и рациональные решения по товародвижению, загрузке транспортных средств и складских помещений.
Таблица 8\
Область применения методов математического
программирования в АСУ
Методы МП | Задачи АСУ, в которых используются МП |
1. Линейное | 1. Формирование производственной программы предприятия. Расчет производственной мощности. |
2. Нелинейное | 1. Оптимальное распределение выпуска продукции между предприятиями объединения либо цехами предприятия. |
3. Дискретное | 1. Оптимальное распределение производственной программы по периодам года (квартала). |
4. Динамическое | 1. Оптимальное распределение капитальных вложений. |
5. Стохастическое | 1. Составление календарного плана выпуска продукции при отсутствии данных о спросе. |
6. Оптимизация | 1. Календарное планирование ТПП изделий. |
ТПП – техническая подготовка производства
При решении названных задач могут быть применены различные модели исследования операций, в качестве наиболее применяемых можно назвать следующие:
1. «Задача о кратчайшем пути», используемая при решении транспортных задач линейного программирования с минимизацией стоимости транспортировки груза.
2. «Задача о распределении поставок», применяемая в логистических системах, функционирующих по принципу «управления запасами», в которой в качестве оптимизируемого критерия используется уровень запасов на складах и их расходование.
3. «Задача о рюкзаке», или «задача о ранце», на размещение максимальной стоимости количества различных предметов при ограничениях на объем «ранца», используется для достижения максимальной загрузки подвижного состава, грузовместимости судна и т. п.
4. «Задача о коммивояжере», формирующая наилучший маршрут для коммивояжера, который должен объехать с грузами несколько населенных пунктов и вернуться назад за кратчайший срок с наименьшими затратами на проезд.
5. «Задача сделать или купить» применяется для обоснованного решения целесообразности собственного производства нужных деталей, комплектующих изделий и т. п. или закупки их у известного производителя этих товаров. Эта же модель используется при решении дилемм: приобретения собственных транспортных средств или заключения договора с перевозчиком; постройки собственных складов или аренды складских помещений.
Приведем пример возможного использования оптимизационных моделей при решении логистических задач.
Пример. Четыре автохозяйства Аi ежедневно выпускают на линию 1 600 автомобилей марки ЗИЛ-150. Эти хозяйства должны ежедневно подавать подвижный состав пяти крупным грузоотправителям Вj и разовым клиентам P1. Расстояние между автохозяйствами и основными клиентами, а также потребность грузовладельцев в автомобилях и наличие их в автохозяйствах приводятся в табл. 11.
Найти оптимальный вариант закрепления автохозяйств за грузоотправителями, обеспечивающий минимальный порожний пробег автомобилей.
Таблица 11
Исходные данные для решения транспортной задачи
Автохозяйство | Расстояние между автохозяйствами | Наличие | |||||
В1 | В2 | В3 | В4 | В5 | Р1 | ||
А1 | 2 | 4 | 1 | 3 | 5 |
| 200 |
А2 | 7 | 3 | 9 | 4 | 1 |
| 600 |
А3 | 10 | 15 | 14 | 8 | 4 |
| 500 |
А4 | 9 | 13 | 12 | 11 | 7 |
| 300 |
Потребность в автомобилях | 300 | 500 | 400 | 200 | 180 | 20 | 1 600 |
Р1 – разовые мелкие отправители (расстояние между ними и автохозяйствами неизвестно).
|
Из за большого объема этот материал размещен на нескольких страницах:
1 2 3 4 5 |
