Содержание к диссертации
Введение
1. Анализ существующих моделей и механизмов материально - технического обеспечения проектов 13
1.1. Задачи системы материально - технического обеспечения 13
1.2. Организационные формы материально - технического обеспечения . 17
1.3. Модели прогнозирования, используемые в сфере материально - технического обеспечения 24
1.4. Модели распределения ресурсов в рамках управления материально -техническим обеспечением 31
1.5. Задача управления запасами и выпуском продукции 37
1.6. Выводы и постановка задач исследования 49
2. Модели определения согласованных цен 53
2.1. Особенности функционирования централизованной схемы снабжения 53
2.2. Метод решения задачи 54
2.3. Метод дихотомического программирования 69
2.4. Описание алгоритма дихотомического программирования в задачах выбора вариантов оптовых закупок 85
3. Модели выбора стратегии оптовых закупок 98
3.1 Определение сроков и объемов оптовых закупок 98
3.2. Формирование оптимального плана закупок при стохастическом спросе 110
3.3. Учет риска изменения цен 117
Заключение 123
Литература
- Модели прогнозирования, используемые в сфере материально - технического обеспечения
- Модели распределения ресурсов в рамках управления материально -техническим обеспечением
- Метод дихотомического программирования
- Формирование оптимального плана закупок при стохастическом спросе
Введение к работе
Актуальность темы. Совершенствование экономического механизма управления на предприятиях, в организациях строительного комплекса является одним из важнейших путей повышения эффективности функционирования в рыночных условиях. Особую роль в данном рассмотрении играют системы типа «Поставщик-Потребитель», описывающие взаимодействие между потребляющими и поставляющими продукцию организационными единицами, будь то производственные предприятия, снабженческие базы, организации торговли, структурные подразделения.
Система «Поставщик-Потребитель» строительного комплекса в настоящее время охватывает широкий спектр строительных организаций, реализующих и потребляющих огромный ассортимент строительных материалов и изделий. «Поставщиком» в данной системе могут выступать производители или оптовые предприятия, занимающиеся реализацией комплектующих, строительных материалов, а в качестве «Потребителя» - строительные организации, выпускающие и реализующие сложное изделие (строительные объекты, сооружения, монтажные, общестроительные, пусконаладочные работы и т.д.).
В условиях полной хозяйственной самостоятельности субъектов строительной деятельности, каждое предприятие выбирает себе партнеров руководствуясь только своей выгодой.
Основной организационной структурой реализующей связи в системе «Поставщик-Потребитель» являются органы материально-технического обеспечения строительства (МТО). Учитывая, что именно через органы МТО проходит основной финансовый поток, обеспечивающий реализацию строительного проекта (в себестоимости строительной продукции 55 - 60 % приходится на материальные ресурсы), особую значимость приобретают вопросы оптимизации функционирования системы материально-технического обеспечения строительства. Служба материально-технического обеспечения предприятия должна обеспечить производство сырьем, материалами и комплектующими изделиями тысяч различных наименований, поступающих от сотен различных поставщиков либо непосредственно, либо через базы снабжения с учетом различный условий поставки и оплаты. Спрос предопределен планом производства лишь приблизительно, обычно без учета развертывания потребляющего производства во времени. Более того, на него влияют такие случайные обстоятельства, как брак в поставляемых изделиях, брак в процессе производства и так далее.
Снабженческая деятельность призвана обеспечить производство или сбыт необходимыми материальными ресурсами (готовой продукцией) с тем, чтобы обеспечить должные объемы выпуска продукции либо объемы продаж. При этом следует обеспечить закупку необходимых ресурсов на наиболее выгодных для потребителя условиях, что в случае разнообразных предложений по цене, качеству, срокам оплаты и поставки со стороны производителя, представляет собой довольно - таки сложную оптимизационную комбинаторного типа.
Таким образом, актуальность темы диссертационной работы определяется необходимостью разработки новых подходов к управлению процессом оптовых закупок в систем материально-технического обеспечения.
Основные исследования, получившие отражение в диссертации, выполнялись по планам научно-исследовательских работ:
- федеральная комплексная программа «Исследование и разработки по приоритетным направлениям науки и техники гражданского назначения»;
- грант РФФИ «Гуманитарные науки» «Разработка оптимизационных моделей управления распределением инвестиций на предприятии по видам деятельности» № Г00-3.3-306;
- госбюджетная научно - исследовательская работа «Разработка и совершенствование моделей и механизмов внутрифирменного управления». Цель и постановка задач исследования. Целью диссертации является разработка методов и моделей оптимального выбора вариантов оптовых закупок в системе материально - технического обеспечения.
Достижение цели работы потребовало решения следующих основных задач:
1. Проанализировать существующие модели материально - технического обеспечения проектов.
2. Применить модификацию метода ветвей и границ для решения задач размещения заказов для двух схем представления скидок по цене продукции.
3. Доказать теорему о приоритетности поставщиков в задаче размещения заказов.
4. Применить метод дихотомического программирования для решения задачи размещения заказов для двух схем представления скидок по цене продукции.
5. Построить графовую модель описания рациональных вариантов оптовых закупок с учетом прогноза изменения цен на продукцию.
6. Разработать модель определения оптимальных объемов и сроков оптовых закупок с учетом прогноза изменения цен.
Методы исследования. В работы использованы методы моделирования организационных систем управления, теории активных систем, системного анализа, математического программирования, теории графов, теория игр.
Научная новизна. В диссертации получены следующие результаты, характеризующиеся научной новизной:
1. Предложена модификация метода ветвей и границ для решения задач размещения заказов для двух схем представления скидок по цене продукции, отличающаяся разбиением решения на подмножества по величинам заказа, при которых происходит изменение цены продукции и позволяющая получить решения оценочных задач, в которых только не более чем для одного поставщика оценочная стоимость заказа меньше фактической стоимости. 2. Доказана теорема, позволяющая определить приоритетность поставщиков в задаче размещения заказов.
3. Разработана модификация метода дихотомического программирования для решения задачи размещения заказов для двух схем представления скидок по цене продукции, отличающаяся тем, что на первом этапе для каждого поставщика определяется рациональные величины заказов.
4. Построена графовая модель на основе учета возможных моментов заказа продукции определяемых моментами изменения спроса, а также моментами, предшествующими моментам изменения цен в сторону повышения и позволяющая описывать рациональные варианты оптовых закупок с учетом прогноза изменения цен на продукцию.
5. Разработана модель определения оптимальных объемов и сроков оптовых закупок с учетом прогноза изменения цен, позволяющая воспользоваться алгоритмом определения кратчайшего пути в графе рациональных закупок.
Достоверность научных результатов. Научные положения, теоретические выводы и практические рекомендации, включенные в диссертацию, обоснованы математическими доказательствами. Они подтверждены расчетами на примерах, производственными экспериментами и многократной проверкой при внедрении в практику управления.
Практическая значимость и результаты внедрения. На основании выполненных автором исследований созданы методы и модели определения рациональных вариантов оптовых закупок и размещения заказов при различных условиях представления скидок по цене продукции.
Использование разработанных в диссертации моделей и механизмов позволяет многократно применять разработки, тиражировать их и осуществлять их массовое внедрение с существенным сокращением продолжительности трудозатрат и средств.
Разработанные модели используются в практике разработки планов закупки материалов и комплектующих изделий в ООО «Главмонолит», ЗАО «Новые строительные технологии» и 000 «УС - 2 Интердорстрой». Модели, алгоритмы и механизмы включены в состав учебного курса «Исследование операций при моделировании социально - экономических систем», читаемого в Воронежском государственном архитектурно - строительном университете.
На защиту выносятся;
1. Модификация метода ветвей и границ для решения задач размещения заказов для двух схем представления скидок по цене продукции.
2. Теорема о приоритетность поставщиков в задаче размещения заказов.
3. Модификация метода дихотомического программирования для решения задачи размещения заказов при различных условиях скидки по цене продукции.
4. Графовая модель рациональных вариантов оптовых закупок с учетом прогноза изменения цен на продукцию.
5. Модель определения оптимальных объемов и сроков оптовых закупок с учетом прогноза изменения цен на основе алгоритма определения кратчайшего пути в графе рациональных закупок.
Апробация работы.
Основные результаты исследований и научных разработок докладывались и обсуждались на следующих конференциях: международная конференция «Современные сложные системы управления» (Воронеж, 2005 г.); международная научно-практическая конференция «Теория активных систем» (Москва, 2005 г.); 2-ая Всероссийская научно-практическая конференция «Актуальные проблемы и перспективы менеджмента организаций в России» (Самара, 2006 г.); научно-практическая конференция «Образование, наука, производство и управление» (Старый Оскол, 2006 г.); международная научно-практическая конференция «Управление инновациями» (Москва, 2006 г.); 60 - 62 научно-технические конференции по проблемам архитектуры и строительных наук (Воронеж, ВГАСУ, 2004-2006 гг.).
Публикации. По теме диссертации опубликовано 11 печатных работ. Личный вклад автора в работах, опубликованных в соавторстве, состоит в следующем: в работах [3], [8], [10] автору принадлежит модификация метода ветвей и границ для решения задач размещения заказов; в работах [2], [7] автору принадлежит теорема о приоритетность поставщиков в задаче размещения заказов; в работах [4], [11] автору принадлежит модификация метода дихотомического программирования для решения задачи размещения заказов; в работах [6], [9] автору принадлежит графовая модель рациональных вариантов оптовых закупок с учетом прогноза изменения цен на продукцию; в работах [1], [5] автору принадлежит модель определения оптимальных объемов и сроков оптовых закупок с учетом прогноза изменения цен на основе алгоритма определения кратчайшего пути в графе рациональных закупок
Объем и структура работы. Диссертация состоит из введения, трех
//3 глав, заключения, списка литературы и приложений. Она содержит 137 страві, .с л- спин псі/ !«итгґ 1У ниц основішпишкста; 45 рисунков, 20 таблиц и приложения. Библиография
включает 137 наименования.
Во введении обосновывается актуальность, описывается цели и задачи исследования, научная новизна и практическая значимость.
В первой главе отмечается, что для производственных предприятий неотъемлемым элементом системы рационального распределения ресурсов является план выпуска продукции. В условиях ограниченности ресурсов (финансовых, кадровых, транспортных, материальных, производственных мощностей и т. д.) необходимо так планировать выпуск продукции, чтобы получить максимальную отдачу. В этом процессе обычно участвуют несколько структурных подразделений предприятия, помимо планового отдела. Здесь задействованы многие звенья: от специалистов по маркетингу и финансам, прогнозирующих потребительский спрос, формирующих портфель договоров, вплоть до специалистов отдела информационного обеспечения, сопровождающих соответствующие управленческие решения.
Анализируя модели, используемые для описания сферы материально -технического обеспечения можно придти к заключению, что при исследова 9
нии этой области строительного производства не соблюдается принцип комплексного подхода к изучаемой проблеме или же пока не создана комплексная модель материально - технического обеспечения производства. Все известные подходы к изучению данной проблемы пока носят только функциональный характер, так как описывают одну или несколько функций материально - технического обеспечения (хранение запасов, транспортировка, прогнозирование спроса, оценка надежности контрагентов и т.п.).
Более общий характер носит сетевая модель межхозяйственных связей, но такая постановка не учитывает интересы отдельного субъекта хозяйственных связей, которые могут быть антагонистичны ко всем остальным участникам или всей системе в целом.
Если же учесть, что сфера материально-технического обеспечения является сферой деятельности различных субъектов, интересы которых часто не совпадают, а иногда и вообще антагонистичны, то следует признать, что достаточно перспективной моделью может быть модель построенная на основе теории игр.
При этом следует отметить, что в настоящее время наблюдается резкое снижение интереса строительных фирм к централизованным схемам снабжения. Следовательно необходимо создание модели, позволяющей изучить условия применения централизованных схем снабжения, определить выигрыш каждого из участников такой схемы и выигрыш снабженческой фирмы, осуществляющей централизованное комплектование строительными материалами строящихся объектов. Такая модель должна определять условия включения строительной фирмы в централизованную схему снабжения.
С другой стороны, основой для получения прибыли специализированной снабженческой фирмы, играющей роль центра, являются крупнооптовые скидки представляемые изготовителями продукции. Следовательно, возникает задача построения модели распределения заказа между несколькими изготовителями с целью максимизации прибыли. Основной трудностью построе 10
ния алгоритмов решения такой задачи являются разрывный характер целевой функции, как правило, задаваемой таблично.
При этом следует иметь ввиду, что объемы, поставляемых ресурсов распределены на достаточно большой промежуток времени, следовательно, необходимо создание комплекса моделей, позволяющих учесть оптимальные сроки закупки материальных ресурсов и осуществить выбора оптимальных вариантов оптовых закупок в системе материально - технического обеспечения.
Во второй главе рассматривается централизованная схема снабжения, в которой вопросы материально-технического обеспечения берет на себя специализированная организация (центр), заключающая договор с организациями-потребителями. Центр проводит оптовые закупки продукции у производителей, что позволяет ему покупать по более низким ценам и, за счет этого, обеспечивать привлекательность централизованной схемы для потребителей.
Рассмотрим сначала задачу снабжения одним видом продукции. Пусть в регионе имеется п организаций - потенциальных потребителей продукции данного вида. Обозначим через Cj цену, по которой i-ый потребитель согласен приобретать продукцию у центра, а через Vj - количество продукции, требуемое і-му потребителю в рассматриваемый период времени. Очевидно, что потребитель і будет выбирать централизованную схему снабжения если цена продукции у центра, которую мы будем обозначать через q, будет меньше или равна Cj, то есть q Cj. Таким образом, количество продукции, которое будет заказано центру равно сумме потребностей тех потребителей, для которых централизованная схема является выгодной.
Задачи такого вида называются многоэкстремальными задачами математического программирования. Для решения таких задач, как правило, применяются специальные методы (динамического программирования, локальной оптимизации, ветвей и границ и другие).
Рассмотрим модификацию метода ветвей границ, которая отличается от описанной в работе В.Н. Буркова и Н.Н. Образцова способом разбиения на подмножества. А именно, разбиения на подмножества будем производить по величинам заказа, при которых происходит изменение цены продукции.
Такая модификация упрощает построение оценочных функций, каждая из которых будет линейной функцией величины заказа. Более того, в этом случае имеет место следующий результат.
Теорема 1. Существует решения оценочных задач, в которых только не более чем для одного поставщика оценочная стоимость заказа меньше фактической стоимости.
Доказанная теорема приводит к естественному выбору поставщика для разбиения рассматриваемого множества решений на подмножества. А именно, для разбиения на подмножества выбирается поставщик, для которого оценочная стоимость меньше фактической. Если такого поставщика нет, то полученное решение оценочной задачи является оптимальным в рассматриваемом множестве решений.
Рассмотрим другой способ предоставления скидок к цене продукции. В ряде случаев меньшая цена устанавливается только на часть заказа, сверх установленной величины. Это кусочнолинейные вогнутые функции величины заказа.
Заметим, что теорема 1 имеет место и для рассматриваемого случая.
В третьей главе отмечается, что планирование закупок на поздние сроки связано с риском изменения цен. Поэтому целесообразно рассмотреть рациональные варианты закупок, уменьшающие риск, связанный с возможным будущим изменением цен.
В работе В.Н. Буркова и Н.Н Образцова рассмотрен простой пример, когда все закупки следует выполнять не позднее определенного срока, после которого возможно повышение цен.
Рассмотрим модификацию модели, позволяющую учесть прогнозируемое изменение цен как в сторону увеличения, так и в сторону уменьшения. Как и ранее будем считать заданным интегральный график закупок продукции у поставщиков (производителей). Кроме того, известны моменты изме 12
нения цен и величины этих изменений. Очевидно, что покупка продуктов, если она целесообразна, должна проводиться в момент, предшествующий моменту изменения цены, если цена повышается. Если цена понижается в некоторый момент г, то данный момент можно исключить из рассмотрения. Действительно, поскольку цена уменьшилась, то момент заказа будет ближайшим моментом, когда требуется поставка продукта потребителям, а имеющегося количества не хватает.
Примем, что и величины заказа продукции у поставщиков, и величин поставок продукции потребителям являются дискретными, что связано, в первую очередь с возможностями транспортировки (вагон, контейнер, грузовик и т. д.). Будем считать, что объемы закупаемых и поставляемых партий кратны некоторой величине (минимальный объем продукции) и количество закупаемых и поставляемых будет определять в числе минимальных объемов. Так, например, если минимальный объем равен 15 единицам, то заказ х=4 соответствует заказу 60 единиц продукции.
Рассмотрим общий шаг алгоритма построения семи рациональных вариантов закупок. Заметим, что возможные моменты заказа продукции определяется, во-первых, моментами изменения спроса, а во-вторых моментами, предшествующими моментам изменения цен в сторону повышения. Показано, задача определения оптимальных объемов и сроков оптовых закупок с учетом прогноза изменения цен, сводится к задаче определения кратчайшего пути в графе рациональных закупок.
Модели прогнозирования, используемые в сфере материально - технического обеспечения
Принципиально новые задачи, стоящие перед органами материально -технического обеспечения предполагают использование современных мето-дов изучения и прогнозирования потребности в материальных ресурсах, их цены, рынка спроса и предложения на конкретную продукцию
Требуется предвидеть и прогнозировать основные направления развития рынка товаров и услуг.
В настоящее время насчитывается более 160 различных по сложности и научной обоснованности методов и приемов прогнозирования. Все их можно разделить на три большие группы: методы моделирования; методы экстраполяции; методы экспертных оценок. Использование методов моделирования предполагает построение корреляционно-регрессионной модели. Предположим известен из статистических данных уровень потребления какого - то ресурса Yf при определенных факторах X ={х,,х2,...,хп},требуется определить аналитическую зависимость уровня потребления ресурса Y от спектра значений факторных признаков X. Задача моделирования состоит в выявлении количественной связи между факторами X и результирующим показателем Y - уровнем потребления материального ресурса. Простейшей моделью предсказания является среднее значение изучаемой величины, но предсказательная сила такой модели в большинстве случаев очень и очень невелика. Существуют методы, позволяющие существенно улучшить эту модель. Первым этапом в построении таких моделей является отбор факторных признаков, оказывающих наибольшее влияние на изучаемый результативный признак. При этом фактор, включаемый в модель, должен соответствовать следующим требованиям [77]: иметь количественное выражение; между фактором и результирующим показателем должна быть логическая, причинная связь; между фактором и результирующим показателем должна быть статистическая связь; факторы не должны быть тесно связаны между собой, т.е. между факторами не должно быть мультиколлинеарности.
Последнее обстоятельство означает, что парный коэффициент корреляции между двумя факторами не должен быть больше 0,85. Имеются и другие подходы к преодолению явления мультиколлинеарности: можно рекомендовать включать в многофакторные модели те факторы, коэффициент корреляции между которыми не оказался значимым при вероятности 0,9, т.е. для них подтвердилась нулевая гипотеза [11].
Основной сложностью моделирования является выбор вида теоретической линии регрессии, то есть какого вида функциональную зависимость можно использовать для моделирования изучаемого явления. При этом, как правило, используемый класс функций ограничивается только гладкими, непрерывными функциями типа линейной, экспоненциальной, логарифмической, полиномиальной и т.п. В большинстве исследований, носящих прикладной характер вообще принято ограничиваться рассмотрением только линейных функциональных зависимостей. Связанно это обстоятельство с исключительно большой трудоемкостью расчетов при использовании нелинейных представления. Следует отметить, что построение многофакторных корреляционных моделей при достаточно большом числе факторных признаков возможно только при использовании средств вычислительной техники, оснащенных современными типовыми программами обработки статистических данных.
После отбора факторных признаков и выбора теоретической линии регрессии, используя метод наименьших квадратов, находят неизвестные параметры линии регрессии и производят оценку полученной модели с использованием критерия Фишера, проверяют значимость коэффициентов уравнения регрессии и коэффициентов корреляции или корреляционного соотношения. В случае удовлетворительного выполнения всех этих требований, полученная модель позволяет осуществлять прогнозирование поведения изучаемой величины при изменении факторных признаков, включенных в модель. Для оценки влияния отдельных факторов на результативный признак используются коэффициенты эластичности, показывающие уровень изменения результативного показателя в случае изменения факторного признака на 1 % при неизменных значениях других факторов.
Модели распределения ресурсов в рамках управления материально -техническим обеспечением
Основной функцией материально-технического обеспечения строительного производства является своевременное обеспечение строящихся объектов необходимыми ресурсами. Как уже указывалось выше, через органы МТО проходят значительные суммы средств в виде материалов, полуфабрикатов, комплектующих и т.п., это обстоятельство делает весьма актуальной задачу эффективного распределения ресурсов, с целью удовлетворения некоторому критерию оптимальности.
Рассмотрим существующие модели распределения ресурсов в рамках управления материально - техническим обеспечением строительства. При этом можно использовать методики управления мультипроектами, так как под термином ресурсы можно понимать не только финансовые, но и конкретные материальные потоки, подлежащие распределению. В этом случае необходимо перейти от скалярной величины, описывающей финансовые ресурсы, к векторной величине, характеризующей материальные ресурсы. Размерность вектора, описывающего набор распределяемых материальных ресурсов, определяется из условий конкретной задачи. В целом, функцию материально - технического обеспечения, связанную с распределением ограниченного ресурса, можно рассматривать как задачу управления несколькими проектами, связанными друг с другом только общими ресурсами, то есть как управление мультипроектом.
Рассмотрим типичную модель распределения ограниченных ресурсов при реализации произвольного числа независимых проектов (сущность каждого проекта, его взаимосвязь с остальными учитывается только на уровне потребляемых общих ресурсов). Такая задача, при распределении финансовых ресурсов, рассмотрена в работах В.Н. Буркова [24-25]. Основные соотношения в этих работах выполнены в общем виде, что позволяет легко перейти от финансовых потоков к материальным.
Перейдем к формулировке задачи распределения ограниченных ресурсов в наиболее общей постановке, данной в работах [24-25].
Рассмотрим m проектов, удовлетворяющих необходимым условиям эффективности (коммерческой, бюджетной и экономической), каждый из которых характеризуется набором параметров: St -требуемым объемом финансирования і -го проекта; Tt - продолжительность реализации і -го проекта; F, - ожидаемая доходность і - го проекта.
Ценным в рассматриваемых алгоритмах является то, что исследуются источники финансирования проектов, при этом выделяются собственные и заемные средства. Это приводит к необходимости решения двух задач в зависимости от источников средств финансирования.
Вводя обозначения по [24]: Q - множество финансируемых проектов (портфель проектов), А - объем финансирования из собственных средств; S - общий объем финансирования. Если S А, то разность S-A финансируется за счет кредитов, что естественно увеличивает стоимость проекта; F(Q) = YJF доходность портфеля проектов и каждого проекта; ieQ Э; = Fi - Si коммерческая эффективность і-го проекта (приведенная к рассматриваемому периоду).
Сложность решения задачи во многом зависит от характера функций доходности исследуемого набора проектов: чем больше ограничений накла 34 дывается на характер функции, тем, как правило, сложнее процедура решения. В [24-25] введено минимальное требование, которое логично вытекает из природы рассматриваемой задачи, считается, что функция должна обладать свойством аддитивности.
В этом случае, стоимость финансовых ресурсов требуемых для реализации набора проектов с учетом процентной ставки за кредит (а- процентная ставка), будет определяться в следующем виде: { S, если S А, S + a(S - А), если S А тогда эффективность набора проектов Q будет характеризоваться 3(Q)=F(Q)-L(Q) (1.4.1)
Следовательно, выражение (1.4.1) представляет собой целевую функцию задачи нахождения оптимального распределения имеющихся ограниченных ресурсов, которая может быть записана в классической форме задачи нелинейного программирования, в частности известную ее разновидность -это задачу о ранце Х(Э,)-ипах (1.4.2) ZS: A, (1.4.3) ieO
Решение сформулированной задачи зависит от вида целевой функции. Если ограничиться только ранее введенным требованием аддитивности целевой функции, то в этом случае наиболее эффективным будет применение метода динамического программирования.
В [24] сформулированы условия применимости рассмотренной модели и проанализированы различные ситуации, позволяющие воспользоваться полученной моделью. Исследован класс задач, которые могут быть сведены к задаче распределения ограниченного ресурса. Отмечено, что такие задачи объединяет проблема организации совместной деятельности. При этом субъектами этой деятельности могут выступать предприятия любой органи 35 зационно-правовой формы. Особый интерес вызывает случай, когда одним из субъектов совместной деятельности являются бюджетные органы, то есть в данном случае речь идет о реализации проектов, пользующихся поддержкой на федеральном или региональном уровне.
Отдельно исследован вопрос двойственности задач распределения, которая выражается в том, что распределению не только инвестиционные ресурсы, но так же и затраты, понесенные на реализацию совместного проекта.
Подробно исследованы, которым должно удовлетворять справедливое распределение ресурсов. Традиционно к ним отнесены аксиомы анонимности и монотонности.
Аксиома анонимности требует чтобы результат распределения зависел только от оценок ожидаемого дохода и ни один участник не пользовался преимуществами перед другими. Это требование означает, что результат решения задачи не должен зависеть от перенумерации участников реализации совместного проекта.
Аксиома монотонности реализует идею справедливого распределения: с ростом дохода, должны возрастать (или по крайней мере не уменьшаться) и расходы участника реализации совместного проекта требует
Введенные аксиомы реализуют обещепризнанные идеи справедливого распределения: равенство партнеров (условие анонимности) и большим доходам должны соответствовать и большие затраты (аксиома монотонности).
Метод дихотомического программирования
Многие задачи дискретной оптимизации сводятся к следующей постановке: определить вектор х = {XJ} с дискретными компонентами, минимизирующий аддитивную функцию п ФМ=2 І(ХІ) І=І (2.3.1) при ограничении f(x) b. (2.3.2) Широкий класс функций f(x) допускает дихотомическое представление, такое что вычисление значений функции сводится к последовательному вычислению значений функций двух переменных. Так функция f(x) = f0[f](X],X2), Ґ2(Х2,Х3)] допускает дихотомическое представление (рис. 2.3.1). При этом соответствующие функции f0, fj, f2 удобно представлять в матричном виде (рис. 2.3.2). Рис. 2.3.2. f.3 И f(x) ХіЗ Xl — і і 2 3 3 1 2 3 1 2 2 2 3 2 2 3 — 1 1 2 Ґ21 f22 f 23 ХЗЗ X32 Х31 t 3 3 2 2 3 1 1 X21 X22 X23 t X21 X22 X23 X3 і Рис. 2.3.2. Такое представление широко используется в методах комплексного оценивания программ развития предприятий, регионов, результатов деятельности подразделений, уровня безопасности объектов и др. [2, 3,16]. Колмогоровым А.Н.[4] и Арнольдом В.И. [1, 21] доказаны теоремы о представлении непрерывных функций нескольких переменных суперпозициями непрерывных функций меньшего числа переменных (в частности, двух переменных). Так, например, любая непрерывная функция трех переменных представима в виде [1] f(x,,x2,x3)=h1 (хі,фі(х2,х3))+Ь2(х1,ф2(х2,х3))+ Ь3(х,,фз(х2,Хз)) Ее дихотомическое представление (в агрегированном виде) - на рис. 2.3.3. Поскольку функция дискретных переменных может быть продолжена до непрерывной функции, то, тем более, любая функция дискретных переменных представима в дихотомическом виде. В дихотомическом виде можно представить и систему неравенств. Рассмотрим, например, систему неравенств гДх) Ь;, j=ui (2.3.3) Рис.2.3.3 Без ограничения общности можно принять, что bj - положительные и одинаковые числа, bj = b 0. В этом случае систему неравенств (2.3.3) можно заменить одним неравенством f(x) b где f (x) = maxfj(x)
Очевидно, что функция f(x) допускает дихотомическое представление, если все функции fj допускают такое представление [14, 15].
В задачах комплексного оценивания [2, 3, 16 и др.] функция f(x), дающая интегральную оценку объекта, как правило, допускает дихотомическое представление в виде дерева. В этом случае можно предложить эффективный метод решения задачи (2.3.1), (2.3.2). На рис. 2.3.4 приведен пример построения интегральной оценки трех показателей, имеющей вид f(x,,x2,x3) = (p0[fi(xbx2), х3] = фо(у,х3) Значения функций ф,(х;) даны в нижних половинах квадратов, соответствующих переменным хь х2 и хз. Дадим описание алгоритма на примере рис. 2.3.4.
1 шаг. Рассматриваем нижнюю матрицу и для каждого элемента этой матрицы записываем в нижней половине соответствующей клетки сумму
Далее будем называть эту сумму затратами на достижение соответствующего состояния. шаг. Из всех элементов матрицы имеющих одно и то же значение у = fi(xbX2) выбираем элемент с минимальной суммой фі(хі)+ф2(х2). Минимальную сумму записываем в нижнюю половину клетки, соответствующей этому значению у в верхней матрице. Так, например, значению у = 3 соответствуют 5 элементов нижней матрицы: (3;2), (4;2), (3;3), (4;3) и (2;4). Из них элемент (3;2) имеет минимальную сумму 30 (это число записано в нижней половине соответствующей клетки). Поэтому в верхней матрице значению у = 3 соответствует число 30, записанное в нижней половине соответствующей клетки. Далее шаги 1 и 2 повторяются для верхней матрицы. В результате для каждого значения f(x) мы получаем минимальную величину ф(х).
Несложно обобщить описанный алгоритм на случай производльного дихотомического представления функции f(x) в виде дерева. Шаги 1 и 2 алгоритма повторяются, начиная с висячих вершин дерева дихотомического представления.
Заметим, что дихотомическое представление рис. 2.3.4 имеет тип ветви дерева. В этом случае метод дихотомического программирования переходит в метод динамического программирования. Таким образом, метод дихотомического программирования в случае, когда дихотомическое представление имеет вид дерева, является обобщением метода динамического программирования, расширяя круг задач, решаемых на основе данного подхода (рис. 2.3.5). Метод динамического программирования (ветвь дерева)
Метод дихотомического программирования (произвольное дерево) Если в методе динамического программирования решением задачи является путь в некоторой специальным образом построенной сети, то в методе дихотомического программирования решением задачи является частичное дерево в некотором специально построенном дереве. Соответственно, принцип оптимальности в методе дихотомического программирования можно сформулировать следующим образом: любое поддерево оптимального дерева должно быть оптимальным. Формально этот принцип оптимальности можно записать следующим образом: Фк(у)= min h (yi)+9j(yj)JJ где P(y) - множество пар (i,j), такие что fk(yi,yj) = y. Рассмотрим произвольное дихотомическое представление функции f(x), задаваемое сетью, входом которой является вершина, соответствующая функции f(x), а выходами - вершины, соответствующие переменным х,-, i = l,n. Рассмотрим множество конечных вершин, которые не являются висячими, то есть их степень захода больше 1. Разделим произвольным образом затраты ФІ(ХІ) на kj частей, где к; - число заходящих дуг. Фактически мы как бы разделили вершину і на kj висячих вершин с соответствующей частью затрат. Далее применяем описанный выше алгоритм. При этом каждый раз, когда встречается вершина, имеющая степень захода больше 1, мы делим затраты на соответствующее число частей. В результате применения алгоритма мы получим оптимальное решение для модифицированной сети. Однако, это решение может не быть решением исходной задачи. Тем не менее, имеет место следующая теорема.
Формирование оптимального плана закупок при стохастическом спросе
Выше была рассмотрена задача определения согласованных цен, а значит - множества потребителей, включенных в централизованную схему снабжения. На основе этой информации можно построить график поставок продукции от центра к потребителям. Для обеспечения этого графика соответствуют объемы продукции должны быть своевременно заказаны у производителей и находиться на складе у центра.
С точки зрения оптовых цен, очевидно, самое выгодное закупить сразу весь объем продукции, заказанный потребителями в рассматриваемом периоде времени и держать его на складе. Именно такой вариант закупок был рассмотрен в предыдущей главе. Однако, при этом возрастают затраты на хранение продукции на складе, а также возможные потери в качестве и количестве продукции. Кроме того, большие закупки требуют соответствующего количества оборотных средств, что приведет к необходимости взятия кредита и выплаты процентов. Требуется найти оптимальный вариант закупок, обеспечивающий минимум суммарных потерь.
В качестве основного требования примем безусловное выполнение центром графика поставок потребителям (считаем, что санкции за срыв поставок превышают возможную экономию от уменьшения издержек на хранение и процентов за кредит). Рассмотрим интегральный график поставок продукции потребителям (рис. 3.1.1).
Смысл этого графика в том, что к моменту tj центр должен поставить потребителям продукцию в объеме Wj. На основе графика поставок можно построить интегральный график закупок продукции у производителей (рис. 3.1.2), учитывая сроки поставок продукции от производителя центру.
Рис. 3.1.2. Можно закупать и раньше, но позже нельзя, поскольку это приведет к срыву графика поставок потребителям. В дальнейшем будем считать, что рост цен на продукцию незначителен, так что закупка продукции раньше, чем требуется, нецелесообразна. По этой причине возможные закупки продукции будут производиться центром в моменты Т;, определяемый сроками tj изменения объема поставок. Очевидно, что в момент Т\ центр должен закупить продукции в объеме не менее W]. При этом, если следующая закупка продукции будет производиться в момент ТІ, то в момент Ті центр должен закупить продукции в объеме щ.[. Действительно, объем продукции, закупленной в момент Ті должен быть достаточен для того, чтобы обеспечить всех потребителей, поставки которым должны быть раньше, чем tj.
Предположим сначала, что оптовая цена продукции не зависит от объема закупок (это вполне возможная ситуация, когда объемы закупок попадают в интервал постоянства оптовой цены). Покажем, что в этом случае оптимальная стратегия закупок состоит в том, чтобы производить закупки продукции в моменты ТІ в объеме A; = Wj - Wj.i, то есть в объеме, который требуется для выполнения заказов потребителей в момент tj. Действительно, закупки ранее требуемого срока приведут только к росту затрат на хранение и процентов за кредит. Таким образом, закупка в момент Tj продукции в объеме более чем ДІ целесообразна только, если объем закупочной партии будет обеспечивать скидку в оптовой цене. Примем, что скидка к оптовой цене дается производителем в случае, если объем закупок не менее определенной величины Q. Рассмотрим метод построения всех рациональных стратегий закупок. Начнем с момента времени Ті первой закупки. Очевидно, что в этот момент центр должен произвести закупку продукции либо в объеме Ді = Wi, либо не менее Q. Действительно, как было показано выше, закупать больше чем Д имеет смысл только в том случае, если объем закупки не менее Q. Пусть W; Q Wj+i. Это означает, что объема Q достаточно, чтобы обеспечить потребителей до момента Tj включительно. Нетрудно показать, что если объем закупленной продукции равен Q, то следующую закупку рационально сделать в момент vl+\ (не ранее), поскольку в противном случае возникают дополнительные расходы на хранение и, возможно, проценты за кредит. По той же причине в случае, если объем закупленной продукции превышает Q, то рациональные варианты закупок составят wi+i, Wj+2, ... , wm. Аналогичные рассуждения можно провести для момента Т2 и т.д.
