Реферат Исследование математических операций 2
Работа добавлена на сайт bukvasha.net: 2015-10-28Поможем написать учебную работу
Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
от 25%
Подписываем
договор
Гипероглавление:
ВВЕДЕНИЕ. ДИСЦИПЛИНА ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И ЧЕМ ОНА ЗАНИМАЕТСЯ
1. ОБЩИЕ ПОНЯТИЯ
1.1. Цель и основные понятия в исследованиях операций
1.2. Основные элементы метода исследования операций
1.3. Основные задачи, решаемые методом исследования операций. Классификация задач
1.4. Методы отыскания оптимальных решений в задачах Исследования Операций. Классификация методов
2.1. Задачи линейного программирования
2.2. Построение экономико-математических моделей задач линейного программирования
2.3. Графическое решение задачи линейного программирования
2.4. Анализ моделей на чувствительность
2.5. Симплекс-метод
2.5.1. Общая идея симплекс-метода
2.5.2. Алгоритм симплекс-метода
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
3. ТРАНСПОРТНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
3.1. Постановка задачи
3.2. Методы составления начального опорного плана
3.3. Понятие потенциала и цикла
3.4. Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения
3.5. Усложненные задачи транспортного типа
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
4. МОДЕЛИРОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
4.1. Компоненты и классификация моделей массового обслуживания
4.2. Определение характеристик систем массового обслуживания
4.2.1. Одноканальная модель с пуассоновским входным потоком с экспоненциальным распределением длительности обслуживания
4.2.2. Многоканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительности обслуживания
4.2.3. Модель обслуживания машинного парка
5. СТАТИСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ СИСТЕМ
5.1. Теоретические основы метода
5.2. Моделирование случайных событий с заданным законом распределения
5.2.1. Разыгрывание дискретной случайной величины
5.2.2. Разыгрывание непрерывной случайной величины
5.2.3. Разыгрывание случайной величины X, распределенной нормально
5.3. Моделирование систем массового обслуживания с использованием метода Монте-Карло
5.4. Моделирование потоков отказов элементов сложных технических систем
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
6. СИСТЕМЫ УПРАВЛЕНИЯ ЗАПАСАМИ
6.1. Модели управления запасами
6.2. Краткая характеристика моделей управления запасами
Формирование исследования операций как самостоятельной ветви прикладной математики относится к периоду 40-х и 50-х годов. Последующие полтора десятилетия были отмечены широким применением полученных фундаментальных теоретических результатов к разнообразным практическим задачам и связанным с этим переосмыслением потенциальных возможностей теории. В результате исследование операций приобрело черты классической научной дисциплины, без которой немыслимо базовое экономическое образование.
Обращаясь к задачам и проблемам, составляющим предмет исследования операций, нельзя не вспомнить о вкладе, внесенном в их решение представителями отечественной научной школы, среди которых в первую очередь должен быть назван Л. В. Канторович, ставший в 1975 г. лауреатом Нобелевской премии за свои работы по оптимальному использованию ресурсов в экономике.
Начало развития исследования операций как науки традиционно связывают с сороковыми годами двадцатого столетия. Среди первых исследований в данном направлении может быть названа работа Л. В. Канторовича "Математические методы организации и планирования производства", вышедшая в 1939 г. В зарубежной литературе отправной точкой обычно считается вышедшая в 1947 г. работа Дж. Данцига, посвященная решению линейных экстремальных задач.
Следует отметить, что не существует жесткого, устоявшегося и общепринятого определения предмета исследования операций. Часто при ответе на данный вопрос говорится, что "исследование операций представляет собой комплекс научных методов для решения задач эффективного управления организационными системами".
Второе определение: Исследование операций – это научная подготовка принимаемого решения – это совокупность методов, предлагаемых для подготовки и нахождения самых эффективных или самых экономичных решений.
Природа систем, фигурирующих в приведенном определении под именем "организационных", может быть самой различной, а их общие математические модели находят применение не только при решении производственных и экономических задач, но и в биологии, социологических исследованиях и других практических сферах. Кстати, само название дисциплины связано с применением математических методов для управления военными операциями.
Несмотря на многообразие задач организационного управления, при их решении можно выделить некоторую общую последовательность этапов, через которые проходит любое операционное исследование. Как правило, это:
1. Постановка задачи.
2. Построение содержательной (вербальной) модели рассматриваемого объекта (процесса). На данном этапе происходит формализация цели управления объектом, выделение возможных управляющих воздействий, влияющих на достижение сформулированной цели, а также описание системы ограничений на управляющие воздействия.
3. Построение математической модели, т. е. перевод сконструированной вербальной модели в ту форму, в которой для ее изучения может быть использован математический аппарат.
4. Решение задач, сформулированных на базе построенной математической модели.
5. Проверка полученных результатов на их адекватность природе изучаемой системы, включая исследование влияния так называемых внемодельных факторов, и возможная корректировка первоначальной модели.
6. Реализация полученного решения на практике.
Центральное место в данном курсе отведено вопросам, относящимся к четвертому пункту приведенной выше схемы. Это делается не потому, что он является самым важным, сложным или интересным, а потому, что остальные пункты существенно зависят от конкретной природы изучаемой системы, в силу чего для действий, которые должны производиться в их рамках, не могут быть сформулированы универсальные и содержательные рекомендации.
В самых разнообразных областях человеческой деятельности встречаются сходные между собой задачи: организация производства, эксплуатация транспорта, боевые действия, расстановка кадров, телефонная связь и т.д. Возникающие в этих областях задачи сходны между собой по постановке, обладают рядом общих признаков и решаются сходными методами.
Пример:
Организуется какое-то целенаправленное мероприятие (система действий), которое можно организовать тем или иным способом. Необходимо выбрать определенное решение из ряда возможных вариантов. Каждый вариант имеет преимущества и недостатки – сразу не ясно, какой из них предпочтительнее. С целью прояснить обстановку и сравнить между собой по ряду признаков различные варианты, организуется серия математических расчетов. Результаты расчетов показывают, на каком варианте остановится.
Математическое моделирование в исследовании операций является, с одной стороны, очень важным и сложным, а с другой - практически не поддающимся научной формализации процессом. Заметим, что неоднократно предпринимавшиеся попытки выделить общие принципы создания математических моделей приводили либо к декларированию рекомендаций самого общего характера, трудноприложимых для решения конкретных проблем, либо, наоборот, к появлению рецептов, применимых в действительности только к узкому кругу задач. Поэтому более полезным представляется знакомство с техникой математического моделирования на конкретных примерах.
1) План снабжения предприятия.
Имеется ряд предприятий, использующих различные виды сырья; имеется ряд сырьевых баз. Базы связаны с предприятиями различными путями сообщения (железные дороги, автотранспорт, водный, воздушный транспорт). Каждый транспорт имеет свои тарифы. Требуется разработать такой план снабжения предприятий сырьем, чтобы потребности в сырье были удовлетворены при минимальных расходах на перевозки.
2) Постройка участка магистрали.
Сооружается участок железнодорожной магистрали. В нашем распоряжении определенное количество средств: людей, техники и т.п. Требуется назначить очередность работ, распределить людей и технику по участкам пути таким образом, чтобы завершить строительство в минимальные сроки.
3) Выборочный контроль продукции.
Выпускается определенный вид изделий. Для обеспечения высокого качества продукции требуется организовать систему выборочного контроля: определить размер контрольной партии, набор тестов, правила отбраковки и т.д. Требуется обеспечить заданный уровень качества продукции при минимальных расходах на контроль.
4) Военные действия.
Целью в данном случае является уничтожение вражеского объекта.
Подобные задачи встречаются в практике часто. Они имеют общие черты. В каждой задаче определена цель – цели эти похожи; заданы некоторые условия – в рамках этих условий и нужно принять решение, чтобы данное мероприятие было наиболее выгодным. В соответствии с этими общими чертами применяются и общие методы.
ВВЕДЕНИЕ. ДИСЦИПЛИНА ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И ЧЕМ ОНА ЗАНИМАЕТСЯ
1. ОБЩИЕ ПОНЯТИЯ
1.1. Цель и основные понятия в исследованиях операций
1.2. Основные элементы метода исследования операций
1.3. Основные задачи, решаемые методом исследования операций. Классификация задач
1.4. Методы отыскания оптимальных решений в задачах Исследования Операций. Классификация методов
2.1. Задачи линейного программирования
2.2. Построение экономико-математических моделей задач линейного программирования
2.3. Графическое решение задачи линейного программирования
2.4. Анализ моделей на чувствительность
2.5. Симплекс-метод
2.5.1. Общая идея симплекс-метода
2.5.2. Алгоритм симплекс-метода
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
3. ТРАНСПОРТНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
3.1. Постановка задачи
3.2. Методы составления начального опорного плана
3.3. Понятие потенциала и цикла
3.4. Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения
3.5. Усложненные задачи транспортного типа
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
4. МОДЕЛИРОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
4.1. Компоненты и классификация моделей массового обслуживания
4.2. Определение характеристик систем массового обслуживания
4.2.1. Одноканальная модель с пуассоновским входным потоком с экспоненциальным распределением длительности обслуживания
4.2.2. Многоканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительности обслуживания
4.2.3. Модель обслуживания машинного парка
5. СТАТИСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ СИСТЕМ
5.1. Теоретические основы метода
5.2. Моделирование случайных событий с заданным законом распределения
5.2.1. Разыгрывание дискретной случайной величины
5.2.2. Разыгрывание непрерывной случайной величины
5.2.3. Разыгрывание случайной величины X, распределенной нормально
5.3. Моделирование систем массового обслуживания с использованием метода Монте-Карло
5.4. Моделирование потоков отказов элементов сложных технических систем
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
6. СИСТЕМЫ УПРАВЛЕНИЯ ЗАПАСАМИ
6.1. Модели управления запасами
6.2. Краткая характеристика моделей управления запасами
ВВЕДЕНИЕ. ДИСЦИПЛИНА ИССЛЕДОВАНИЕ ОПЕРАЦИЙ И ЧЕМ ОНА ЗАНИМАЕТСЯ
Формирование исследования операций как самостоятельной ветви прикладной математики относится к периоду 40-х и 50-х годов. Последующие полтора десятилетия были отмечены широким применением полученных фундаментальных теоретических результатов к разнообразным практическим задачам и связанным с этим переосмыслением потенциальных возможностей теории. В результате исследование операций приобрело черты классической научной дисциплины, без которой немыслимо базовое экономическое образование.
Обращаясь к задачам и проблемам, составляющим предмет исследования операций, нельзя не вспомнить о вкладе, внесенном в их решение представителями отечественной научной школы, среди которых в первую очередь должен быть назван Л. В. Канторович, ставший в 1975 г. лауреатом Нобелевской премии за свои работы по оптимальному использованию ресурсов в экономике.
Начало развития исследования операций как науки традиционно связывают с сороковыми годами двадцатого столетия. Среди первых исследований в данном направлении может быть названа работа Л. В. Канторовича "Математические методы организации и планирования производства", вышедшая в 1939 г. В зарубежной литературе отправной точкой обычно считается вышедшая в 1947 г. работа Дж. Данцига, посвященная решению линейных экстремальных задач.
Следует отметить, что не существует жесткого, устоявшегося и общепринятого определения предмета исследования операций. Часто при ответе на данный вопрос говорится, что "исследование операций представляет собой комплекс научных методов для решения задач эффективного управления организационными системами".
Второе определение: Исследование операций – это научная подготовка принимаемого решения – это совокупность методов, предлагаемых для подготовки и нахождения самых эффективных или самых экономичных решений.
Природа систем, фигурирующих в приведенном определении под именем "организационных", может быть самой различной, а их общие математические модели находят применение не только при решении производственных и экономических задач, но и в биологии, социологических исследованиях и других практических сферах. Кстати, само название дисциплины связано с применением математических методов для управления военными операциями.
Несмотря на многообразие задач организационного управления, при их решении можно выделить некоторую общую последовательность этапов, через которые проходит любое операционное исследование. Как правило, это:
1. Постановка задачи.
2. Построение содержательной (вербальной) модели рассматриваемого объекта (процесса). На данном этапе происходит формализация цели управления объектом, выделение возможных управляющих воздействий, влияющих на достижение сформулированной цели, а также описание системы ограничений на управляющие воздействия.
3. Построение математической модели, т. е. перевод сконструированной вербальной модели в ту форму, в которой для ее изучения может быть использован математический аппарат.
4. Решение задач, сформулированных на базе построенной математической модели.
5. Проверка полученных результатов на их адекватность природе изучаемой системы, включая исследование влияния так называемых внемодельных факторов, и возможная корректировка первоначальной модели.
6. Реализация полученного решения на практике.
Центральное место в данном курсе отведено вопросам, относящимся к четвертому пункту приведенной выше схемы. Это делается не потому, что он является самым важным, сложным или интересным, а потому, что остальные пункты существенно зависят от конкретной природы изучаемой системы, в силу чего для действий, которые должны производиться в их рамках, не могут быть сформулированы универсальные и содержательные рекомендации.
В самых разнообразных областях человеческой деятельности встречаются сходные между собой задачи: организация производства, эксплуатация транспорта, боевые действия, расстановка кадров, телефонная связь и т.д. Возникающие в этих областях задачи сходны между собой по постановке, обладают рядом общих признаков и решаются сходными методами.
Пример:
Организуется какое-то целенаправленное мероприятие (система действий), которое можно организовать тем или иным способом. Необходимо выбрать определенное решение из ряда возможных вариантов. Каждый вариант имеет преимущества и недостатки – сразу не ясно, какой из них предпочтительнее. С целью прояснить обстановку и сравнить между собой по ряду признаков различные варианты, организуется серия математических расчетов. Результаты расчетов показывают, на каком варианте остановится.
Математическое моделирование в исследовании операций является, с одной стороны, очень важным и сложным, а с другой - практически не поддающимся научной формализации процессом. Заметим, что неоднократно предпринимавшиеся попытки выделить общие принципы создания математических моделей приводили либо к декларированию рекомендаций самого общего характера, трудноприложимых для решения конкретных проблем, либо, наоборот, к появлению рецептов, применимых в действительности только к узкому кругу задач. Поэтому более полезным представляется знакомство с техникой математического моделирования на конкретных примерах.
1) План снабжения предприятия.
Имеется ряд предприятий, использующих различные виды сырья; имеется ряд сырьевых баз. Базы связаны с предприятиями различными путями сообщения (железные дороги, автотранспорт, водный, воздушный транспорт). Каждый транспорт имеет свои тарифы. Требуется разработать такой план снабжения предприятий сырьем, чтобы потребности в сырье были удовлетворены при минимальных расходах на перевозки.
2) Постройка участка магистрали.
Сооружается участок железнодорожной магистрали. В нашем распоряжении определенное количество средств: людей, техники и т.п. Требуется назначить очередность работ, распределить людей и технику по участкам пути таким образом, чтобы завершить строительство в минимальные сроки.
3) Выборочный контроль продукции.
Выпускается определенный вид изделий. Для обеспечения высокого качества продукции требуется организовать систему выборочного контроля: определить размер контрольной партии, набор тестов, правила отбраковки и т.д. Требуется обеспечить заданный уровень качества продукции при минимальных расходах на контроль.
4) Военные действия.
Целью в данном случае является уничтожение вражеского объекта.
Подобные задачи встречаются в практике часто. Они имеют общие черты. В каждой задаче определена цель – цели эти похожи; заданы некоторые условия – в рамках этих условий и нужно принять решение, чтобы данное мероприятие было наиболее выгодным. В соответствии с этими общими чертами применяются и общие методы.
1. ОБЩИЕ ПОНЯТИЯ
1.1. Цель и основные понятия в исследованиях операций
Операция – это всякая система действий (мероприятие), объединенных единым замыслом и направленных к достижению какой-то цели. Это управляемое мероприятие, то есть от нас зависит, каким способом выбрать некоторые параметры, характеризующие его организацию.
Каждый определенный выбор зависящих от нас параметров называется решением.
Целью исследования операций является предварительное количественное обоснование оптимальных решений.
Те параметры, совокупность которых образует решение, называются элементами решения. В качестве элементов решения могут быть различные числа, векторы, функции, физически признаки и т.д.
Пример: перевозка однородного груза.
Существуют пункты отправления: А1, А2, А3,…, Аm.
Имеются пункты назначения: В1, В2, В3,…, Вn.
Элементами решения здесь будут числа xij
, показывающие, какое количество грузов будет отправлено из i-того пункта отправления в j-ый пункт назначения.
Совокупность этих чисел: x
11
,
x
12
,
x
13
,…,
x
1
m
,…,
xn
1
,
xn
2
,…,
xnm
образует решение.
Чтобы сравнить между собой различные варианты, необходимо иметь какой-то количественный критерий – показатель эффективности (W). Данный показатель называется целевой функцией.
Этот показатель выбирается так, чтобы он отражал целевую направленность операции. Выбирая решение, стремимся, чтобы данный показатель стремился к максимуму или к минимуму. Если W – доход, то W
Если выбор зависит от случайных факторов (погода, отказ техники, колебания спроса и предложения), то в качестве показателя эффективности выбирается среднее значение – математическое ожидание –
В качестве показателя эффективности иногда выбирают вероятность достижения цели. Здесь цель операции сопровождается случайными факторами и работает по схеме ДА-НЕТ.
Для иллюстрации принципов выбора показателя эффективности вернемся к рассмотренным ранее примерам:
1) План снабжения предприятия.
Показатель эффективности виден в цели. R – число – стоимость перевозок,
2) Постройка участка магистрали.
В задаче большую роль играют случайные факторы. В качестве показателя эффективности выбирают среднее ожидаемое время окончания стройки
3) Выборочный контроль продукции.
Естественный показатель эффективности, подсказанный формулировкой задачи – это средние ожидаемые расходы на контроль за единицу времени, при условии, что система контролирует обеспечение заданного уровня качества.
4) Военные действия.
Операция должна быть спланирована так, чтобы уничтожить вражеский объект. В качестве целевой функции – вероятность того, что произойдет событие А (уничтожение). Р(А)
1.2. Основные элементы метода исследования операций
При решении любой конкретной задачи применение методов исследования операций заключается в следующем:
построение математических, экономических и статистических моделей для задач принятия решений и управления в сложных ситуациях в условиях неопределенности (наличие случайных факторов);
изучение взаимосвязей, определяющих возможные последствия принятых решений. Установление критериев эффективности, позволяющих оценить преимущества того или иного варианта.
Методы исследования операций обладают рядом специфических черт. Чтобы подход к решению задач можно было считать операционным, он должен содержать следующие элементы:
1. Ориентация на принятие решений. Основные результаты анализа должны иметь непосредственное и полностью определенное отношение к выбору способа действий (стратегии или тактики);
2. Оценка на основе критерия экономической эффективности. Сравнение различных возможных вариантов действий должно основываться на количественных оценках, позволяющих однозначно определить полезность ожидаемого исхода. Количественные оценки для коммерческих фирм обычно предполагают использование таких измеримых величин, как расходы, доходы, наличие денежных средств, норма прибыли от дополнительных капиталовложений и т.д. В рекомендуемом решении должен быть достигнут оптимальный баланс с учетом всех, нередко противоречивых факторов;
3. Доверие математической модели. Процедуры обращения с упомянутыми выше параметрами должны быть определены настолько точно, чтобы любой специалист в области системного анализа смог их трактовать совершенно однозначно. Другими словами: опираясь на одни и те же данные, различные специалисты должны получить одинаковые результаты.
4. Необходимость использования ЭВМ. Это условие отнюдь не является лишь желательным, оно скорее необходимо. Это обуславливается сложностью используемых математических моделей и большим объемом исходных данных. Вычисления могут быть громоздкими – необходимо использовать ЭВМ; а могут быть несложными, но в больших объемах (статистические модели).
Основные этапы применения метода ИО:
1. определение цели;
2. составление плана разработки проекта;
3. формулировка проблемы;
4. построение модели;
5. разработка вычислительного метода;
6. разработка технического задания на программирование, само программирование и отладка программы;
7. сбор данных;
8. проверка модели;
9. реализация результатов, то есть принятие решения.
1.3. Основные задачи, решаемые методом исследования операций. Классификация задач
Накопленный опыт в решении задач исследования операций и его систематизация позволили выделить следующие типы задач:
задачи управления запасами,
задачи распределения ресурсов,
задачи ремонта и замены оборудования,
задачи массового обслуживания,
задачи упорядочивания,
задачи сетевого планирования и управления (СПУ),
задачи выбора маршрута,
комбинированные задачи.
1. Задачи управления запасами.
Этот класс задач в настоящее время наиболее распространенный, а главное, изученный. Эти задачи имеют следующую особенность: с ростом запасов, увеличиваются расходы на их хранение, но снижаются потери, связанные с возможной их нехваткой. Следовательно, одна из задач управления запасами заключается в определении такого уровня запасов, который минимизирует следующие критерии:
сумма ожидаемых затрат на хранение,
сумма потерь из-за дефицита.
В зависимости от условий, задачи управления запасами делятся на 3 группы:
а) моменты поставок или оформления заказов на поставки, пополнение запасов фиксированы. Определить объемы производимой или закупаемой партии запасов;
б) объемы производимой или закупаемой партии запасов фиксированы. Определить моменты оформления заказов на поставки;
в) моменты оформления заказов и объемы закупаемых партий запасов нефиксированы. Определить эти величины, исходя из минимальных затрат и минимальных потерь из-за дефицита.
2. Задачи распределения ресурсов.
Эти задачи возникают тогда, когда существует определенный набор операций (работ), которые необходимо выполнить, а наличия ресурсов для выполнения операций наилучшим образом не хватает. В зависимости от условия задачи эти также делятся на 3 группы:
а) заданы работы и ресурсы. Распределить ресурсы между работами таким образом, чтобы максимизировать некоторую меру эффективности (прибыль) или минимизировать ожидаемые затраты (издержки производства).
Пример: известны производственное задание и производственные мощности предприятия. При существующих различных способах получения изделия, ограничения по мощности не позволяют для каждого изделия использовать наилучшую технологию. Какие способы производства надо выбрать, чтобы выполнить задание с минимальными затратами?
б) заданы только наличные ресурсы. Определить, какой состав работ можно выполнить с учетом этих ресурсов, чтобы обеспечить максимум некоторой меры эффективности.
Пример: задано предприятие с определенными производственными мощностями. Какую продукцию следует производить, чтобы получить максимальный доход?
в) заданы только работы. Определить, какие ресурсы необходимы для того, чтобы минимизировать суммарные издержки производства.
Пример: известно месячное расписание движения полетов пассажирских самолетов на авиалинии. Какое количество экипажей необходимо подобрать, чтобы выполнить план с минимальными затратами?
3. Задачи ремонта и замены оборудования.
Производственное оборудование с течением времени изнашивается и подлежит предупредительно-восстановительному ремонту. Оборудование также устаревает (морально и физически) и подлежит полной замене. При этом постановка задачи такова: определить такие сроки ремонта и замены оборудования, при которых минимизируется сумма затрат на ремонт и замену оборудования при его старении. Иногда в оборудовании выходят из строя отдельные элементы (например, микросхемы) – в данном случае требуется определить такие сроки профилактического ремонта по замене вышедших из строя деталей, чтобы потери на данный элемент были минимальными.
Здесь также имеет место профилактический контроль по обнаружению неисправностей. Требуется определить такие сроки контроля, при которых минимизируется сумма затрат на проведение контроля, а также минимизируется сумма потерь от простоя оборудования вследствие выхода из строя отдельных элементов.
4. Задачи массового обслуживания.
Данные задачи возникают там, где образуется очередь. С образованием очереди приходится сталкиваться как в производстве, так и в быту (производство: очередность выполнения заказа; в быту: магазин, поликлиника). Подобные задачи существуют и на транспорте.
Очередь возникает из-за того, что поток клиентов (заказов) поступает неравномерно и имеет случайный характер. То есть поток клиентов неуправляем. Объект, который обслуживает клиента, называется каналом обслуживания (продавец, врач, взлетно-посадочная полоса). Если каналов обслуживания много, очереди не образуется, НО возможны простои каналов обслуживания. Если каналов мало – образуется очередь. А следовательно, возможны затраты, связанные с ожиданием в очереди клиента ми с отказом клиента от обслуживания.
В данных задачах возможна следующая постановка: определить, какое количество каналов обслуживания необходимо, чтобы свести к минимуму суммарные затраты, связанные с несвоевременным обслуживанием и простоем каналов. Для решения задач используется теория массового обслуживания.
5. Задачи упорядочивания.
Эти задачи часто встречаются в производстве. Предположим, что в цехе изготавливается множество деталей по разным технологическим маршрутам. В парке оборудования имеется ограниченное число станков (токарный, фрезерный, строгальный и др.). На одном станке в данный момент времени может обрабатываться только 1 деталь. Появляется очередность выполнения работ, то есть появляются детали, ждущие обработки. Время обработки каждой детали обычно известно. Такая задача называется задачей календарного планирования или составлением расписания работ. Выбор очередности запуска деталей в обработку является задачей упорядочивания. В таких задачах в качестве критерия эффективности часто встречаются следующие:
минимизация общей продолжительности работ (то есть интервала времени между моментом началом первой операции и моментом окончания последней);
минимизация общего запаздывания. Запаздывание определяется как разность фактическим и плановым сроком обработки каждой детали. Общее запаздывание = сумме запаздываний по всем деталям.
6. Задачи сетевого планирования и управления (СПУ).
Данные задачи актуальны при разработке сложных, дорогостоящих проектов. Здесь рассматривается соотношение между сроком выполнения крупного комплекса операций и моментом начала всех операций отдельно в комплексе. Для строгой постановки задачи необходимо выполнить следующие условия:
Должно существовать точно определяемое количество операций,
Множество операций по комплексу упорядочено так, что должно быть известно для каждой операции какие операции ей предшествуют, а какие следуют за ней,
В пределах заданного упорядочивания операций, операции можно начинать и заканчивать независимо друг от друга,
Известна взаимосвязь между ресурсами на выполнение операции и ее продолжительностью.
Если все условия выполнены, возможны следующие постановки задачи:
а) задана продолжительность выполнения всего комплекса операций. Требуется определить сроки каждой операции, при которых:
минимизируются общие затраты на выполнение всего комплекса операций,
определяется вероятность невыполнения комплекса работ в установленные сроки,
определяется среднеквартальные отклонения требуемых ресурсов от наличных.
б) заданы общие ресурсы. Определить сроки начала каждой операции, чтобы минимизировать время на выполнение всего комплекса операций.
7. Задачи маршрутизации.
Эти задачи возникают при исследовании разнообразных процессов на транспорте и в системах связи. Типичной задачей является задача выбора оптимального маршрута: имеется несколько маршрутов, из них нужно выбрать один. Стоимость прохождения и время на прохождение зависит от выбранного маршрута. При рассмотрении ряда маршрутов вводятся следующие ограничения:
- запрещается возвращаться в уже пройденный пункт,
- в пунктах сети возможны задержки (например, из-за ограниченной пропускной способности). Задержки носят случайный характер.
Критерии оптимизации: минимизация общего времени прохождения маршрута или минимизация общих затрат.
Данные задачи наиболее изучены и в литературе носят специфические названия – задача о коммивояжере или задача о максимальном потоке.
8. Комбинированные задачи.
Включают в себя несколько типовых задач одновременно.
Пример: при планировании и управлении производством необходимо решить комплекс задач:
1) сколько изделий каждого наименования необходимо выпустить и каковы оптимальные размеры партии изделий – задача планирования производства;
2) распределить заказы или детали по видам оборудования, причем оптимальный план производства задан – задача распределения;
3) определить в какой последовательности следует выполнить производственные заказы – календарное планирование.
Эти задачи нельзя решать независимо друг от друга. Критерии эффективности этих задач часто противоречат друг другу. Поэтому при решении задач часто используют:
Метод последовательного приближения – с помощью этого метода можно очень близко подойти к оптимальному решению.
Метод имитационного моделирования – основан на методе Монте-Карло (использование случайных чисел) и требует огромного количества вычислений, так как рассматривается очень много вариантов решений.
1.4. Методы отыскания оптимальных решений в задачах Исследования Операций. Классификация методов
К основным методам отыскания оптимальных решений относятся:
математическое программирование. В свою очередь методы математического программирования делятся на следующие:
линейное программирование,
нелинейное программирование,
динамическое программирование,
целочисленное программирование,
стохастическое программирование,
эвристическое программирование
теория массового обслуживания,
сетевые модели планирования и управления,
имитационное моделирование.
Рассмотренные выше классы задач можно решать указанными методами. Методами математического программирования решаются следующие классы задач:
задачи управления запасами,
задачи распределения ресурсов,
задачи замены и ремонта оборудования,
задачи выбора маршрута.
С помощью теории массового обслуживания решаются задачи массового обслуживания.
С использованием сетевых моделей планирования и управления можно решать:
задачи массового обслуживания,
задачи упорядочивания,
задачи сетевого планирования.
Методом имитационного моделирования решаются комбинированные задачи. Данным методом можно решить задачу любого класса, однако, данный метод не является универсальным. Его применение ограничено следующими факторами:
1) требуется наличие высококвалифицированных специалистов, т.к. он содержит в себе элементы всех вышеперечисленных методов;
2) решение обходится дороже, чем при использовании других методов.
2. ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ
Временем рождения линейного программирования принято считать 1939г., когда была напечатана брошюра Леонида Витальевича Канторовича "Математические методы организации и планирования производства". Поскольку методы, изложенные Л.В.Канторовичем, были мало пригодны для ручного счета, а быстродействующих вычислительных машин в то время не существовало, работа Л.В.Канторовича осталась почти не замеченной.
Однако идеи Л.В.Канторовича не встретили понимания в момент их зарождения, были объявлены ересью, и его работа была прервана. Концепции Леонида Витальевича вскоре после войны были переоткрыты на западе. Американский экономист Т.Купманс в течение многих лет привлекал внимание математиков к ряду задач, связанных с военной тематикой. Он активно способствовал тому, чтобы был организован математический коллектив для разработки этих проблем. В итоге было осознано, что надо научиться решать задачи о нахождении экстремумов линейных функций на многогранниках, задаваемых линейными неравенствами. По предложению Купманса этот раздел математики получил название линейного программирования.
Американский математик А.Данциг в 1947 году разработал весьма эффективный конкретный метод численного решения задач линейного программирования (он получил название симплекс метода). Идеи линейного программирования в течение пяти шести лет получили грандиозное распространение в мире, и имена Купманса и Данцига стали повсюду широко известны.
Свое второе рождение линейное программирование получило в начале пятидесятых годов с появлением ЭВМ. Тогда началось всеобщее увлечение линейным программированием, вызвавшее в свою очередь развитие других разделов математического программирования. В 1975 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".
Оптимизационная задача – это экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений.
В самом общем виде задача математически записывается следующим образом:
где X = (x1, x2 , ... , xn);
W – область допустимых значений переменных x1, x2 , ... , xn ;
f(Х) – целевая функция.
Для того, чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т.е. указать
Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешимой, если целевая функция f(Х) не ограничена сверху на допустимом множестве W.
Методы решения оптимизационных задач зависят как от вида целевой функции f(Х), так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования.
2.1. Задачи линейного программирования
Линейное программирование является наиболее простым и лучше всего изученным разделом математического программирования. Характерные черты задач линейного программирования следующие:
1) показатель оптимальности f(X) представляет собой линейную функцию от элементов решения X = (x1, x2 , ... , xn);
2) ограничительные условия, налагаемые на возможные решения, имеют вид линейных равенств или неравенств.
Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид:
При этом система линейных уравнений (2.3) и неравенств (2.4), (2.5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(Х) называется целевой функцией или критерием оптимальности.
В частном случае, если I = Ø, то система (2.3) – (2.4) состоит только из линейных неравенств, а если I = M, то – из линейных уравнений.
При описании реальной ситуации с помощью линейной модели следует проверять наличие у модели таких свойств, как пропорциональность и аддитивность. Пропорциональность означает, что вклад каждой переменной в целевой функции и общий объем потребления соответствующих ресурсов должен быть прямо пропорционален величине этой переменной. Например, если, продавая j-й товар в общем случае по цене 100 рублей, фирма будет делать скидку при определенном уровне закупки до уровня цены 95 рублей, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной xj . Т.е. в разных ситуациях одна единица j-го товара будет приносить разный доход. Аддитивность означает, что целевая функция и ограничения должны представлять собой сумму вкладов от различных переменных.
Примером нарушения аддитивности служит ситуация, когда увеличение сбыта одного из конкурирующих видов продукции, производимых одной фирмой, влияет на объем реализации другого.
Допустимое решение – это совокупность чисел (план) X = (x1, x2 , ... , xn), удовлетворяющих ограничениям задачи.
Оптимальное решение – это план, при котором целевая функция принимает свое максимальное (минимальное) значение.
Если математическая модель задачи линейного программирования имеет вид:
то говорят, что задача представлена в канонической форме.
Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком, и наоборот.
Правило приведения задачи линейного программирования к каноническому виду состоит в следующем:
1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;
2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;
3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;
4) если некоторая переменная xk не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными:
Пример 2.1. Приведение к канонической форме задачи линейного программирования:
Введем в каждое уравнение системы ограничений выравнивающие переменные x4, x5, x6. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x4, x6 вводятся в левую часть со знаком "+", а во второе уравнение вводится x5 со знаком "-".
Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1:
В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Допустим, что
Подставляя данное выражение в систему ограничений и целевую функцию и записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме:
Назад | Содержание | Далее
2.2. Построение экономико-математических моделей задач линейного программирования
Рассмотрим процесс построения математических моделей задач линейного программирования на примерах.
Пример 2.2. Определение оптимального ассортимента продукции.
Предприятие изготавливает два вида продукции - П1 и П2, которая поступает в оптовую продажу. Для производства продукции используются два вида сырья - А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П1 и вида П2 дан в табл. 2.1.
Таблица 2.1.
Расход сырья продукции
| Сырье | Расход сырья на 1 ед. продукции | Запас сырья, ед. | |
| П1 | П2 | ||
| А | 2 | 3 | 9 |
| В | 3 | 2 | 13 |
Опыт работы показал, что суточный спрос на продукцию П1 никогда не превышает спроса на продукцию П2 более чем на 1 ед. Кроме того, известно, что спрос на продукцию П2 никогда не превышает 2 ед. в сутки.
Оптовые цены единицы продукции равны: 3 д. е. - для П1 и 4 д.е. для П2.
Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализация продукции был максимальным?
Процесс построения математической модели для решения подавленной задачи начинается с ответов на следующие вопросы:
1. Для определения каких величин должна быть построена модель, т.е. как идентифицировать переменные данной задачи?
2. Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы?
3. В чем состоит цель задачи, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи?
Ответы на вышеперечисленные вопросы могут быть сформулированы для данной задачи так: фирме требуется определить объемы производства каждого вида продукции в тоннах, максимизирующие доход в д.е. от реализации продукции, с учетом ограничений на спрос и расход исходных продуктов.
Для построения математической модели остается только идентифицировать переменные и представить цель и ограничения в виде математических функций этих переменных.
Предположим, что предприятие изготовит х1 единиц продукции П1 и х2 единиц продукции П2. Поскольку производство продукции П1 и П2 ограничено имеющимися в распоряжении предприятия сырьем каждого вида и спросом на данную продукцию, а также учитывая, что количество изготовляемых изделий не может быть отрицательным, должны выполняться следующие неравенства:
Доход от реализациих1 единиц продукции П1 и х2 единиц продукции П2 составит F = 3 х1 + 4х2 .
Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значения Fmax .
Рассмотренная задача относится к разряду типовых задач оптимизации производственной программы предприятия. В качестве критериев оптимальности в этих задачах могут быть также использованы: прибыль, себестоимость, номенклатура производимой продукции и затраты станочного времени.
Пример 2.3. Использование мощностей оборудования.
Предприятие имеет m моделей машин различных мощностей. Задан план по времени и номенклатуре: Т - время работы каждой машины; продукции j-го вида должно быть выпущено не менее Nj единиц.
Необходимо составить такой план работы оборудования, чтобы обеспечить минимальные затраты на производство, если известны производительность каждой i-й машины по выпуску j-го вида продукции bij и стоимость единицы времени, затрачиваемого i-й машиной на выпуска j-го вида продукции cij .
Другими словами, задача для предприятия состоит в следующем: требуется определить время работы i-й машины по выпуску j-го вида продукции xij , обеспечивающее минимальные затраты на производство при соблюдении ограничений по общему времени работы машин Т и заданному количеству продукции Nj .
По условию задачи машины работают заданное время Т, поэтому данное ограничение можно представить в следующем виде:
Ограничение по заданному количеству продукции выглядит следующим образом:
Задача решается на минимум затрат на производство:
Необходимо также учесть неотрицательность переменных
Задача поставлена так, чтобы израсходовать все отведенное время работы машины, т.е. обеспечить полную загрузку машины. При этом количество выпускаемой продукции каждого вида должно быть по крайней мере не менее Nj . Однако в некоторых случаях не допускается превышение плана по номенклатуре, тогда ограничения математической модели изменяются следующим образом:
Пример 2.4. Минимизация дисбаланса на линии сборки.
Промышленная фирма производит изделие, представляющее собой сборку из m различных узлов. Эти узлы изготавливаются на n заводах.
Из-за различий в составе технологического оборудования производительность заводов по выпуску j-го узла неодинакова и равна bij . Каждый i-й завод располагает максимальным суммарным ресурсом времени в течение недели для производства m узлов, равного величине Ti .
Задача состоит в максимизации выпуска изделий, что по существу эквивалентно минимизации дисбаланса, возникающего вследствие некомплектности поставки по одному или по нескольким видам узлов.
В данной задаче требуется определить еженедельные затраты времени (в часах) на производство j-го узла на i-м заводе, не превышающие в сумме временные ресурсы 1-го завода и обеспечивающие максимальный выпуск изделий.
Пусть xij - недельный фонд времени (в часах), выделяемый на заводе для производства узла j. Тогда объемы производства узла j будут следующими:
Так как в конечной сборке каждый из комплектующих узлов представлен в одном экземпляре, количество конечных изделии должно быть равно количеству комплектующих узлов, объем производства которых минимален:
Условие рассматриваемой задачи устанавливает ограничение на фонд времени, которым располагает завод i .
Таким образом, математическая модель может быть представлена в следующем виде.
Максимизируем
Эта модель не является линейной, но ее можно привести к линейной форме с помощью простого преобразования. Пусть Y
- количество изделий:
Этому выражению с математической точки зрения эквивалентна следующая формулировка: максимизировать Z
= Y при ограничениях
Пример 2.5. Задача составления кормовой смеси, или задача диете..
Пусть крупная фирма (условно назовем ее «Суперрацион») имеет возможность покупать m различных видов сырья и приготавливать различные виды смесей (продуктов). Каждый вид сырья содержит разное количество питательных компонентов (ингредиентов). Лабораторией фирмы установлено, что продукция должна удовлетворять по крайней мере некоторым минимальным требованиям с точки зрения питательности (полезности). Перед руководством ширмы стоит задана определить количество каждого i-го сырья, образующего смесь минимальной стоимости при соблюдении требований к общему расходу смеси и ее питательности.
Решение
Введем условные обозначения:
xi - количество i-го сырья в смеси;
m
- количество видов сырья;
n
- количество ингредиентов в сырье;
aij - количество ингредиента j, содержащегося в единице i-го вида сырья;
bj - минимальное количество ингредиента j, содержащегося в единице смеси;
ci - стоимость единицы сырья i;
q - минимальный общий вес смеси, используемый фирмой,
Задача может быть представлена в виде
при следующих ограничениях:
на общий расход смеси:
на питательность смеси:
на неотрицательность переменных:
Пример 2.6. Задача составления жидких смесей.
Еще один класс моделей, аналогичных рассмотренным выше, возникает при решении экономической проблемы, связанной с изготовлением смесей различных жидкостей с целью получения пользующихся спросом готовых продуктов.
Представим себе фирму, торгующую различного рода химическими продуктами, каждый из которых является смесью нескольких компонентов. Предположим, что эта фирма планирует изготовление смесей m-видов. Обозначим подлежащее определению количество литров i
-го химического компонента, используемого для получения j-го продукта через xij . Будем предполагать, что
Первая группа ограничений относится к объемам потребляемых химических компонентов:
где Si - объем i-го химического компонента, которым располагает фирма в начале планируемого периода.
Вторая группа ограничений отражает требование, заключающееся в том, чтобы запланированный выпуск продукции хотя бы в минимальной степени удовлетворял имеющийся спрос на каждый из химических продуктов, т.е.
где Di - минимальный спрос на продукцию у в течение планируемого периода.
Третья группа ограничений связана с технологическими особенностями, которые необходимо принимать во внимание при приготовлении смеси например, простое ограничение, определяемое некоторыми минимально допустимыми значениями, отношения между объемами двух химических компонентов в процессе получения продукта j:
где r - некоторая заданная константа.
Обозначив через Рij доход с единицы продукции хij запишем целевую функцию:
Пример 2.7. Задача о раскрое или о минимизации обрезков.
Данная задача состоит В разработке таких технологических планов раскроя, при которых получается необходимый комплекс заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму.
Например, продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины L. По специальным заказам потребителей фирма поставляет рулоны других размеров, для этого производится разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров могут включать т видов шириной Hi (
Обозначим через aij количество рулонов i-го вида, получаемых при раскрое единицы стандартного рулона по j-му варианту. При каждом варианте раскроя на каждый стандартный рулон возможны потери, равные Pi . К потерям следует относить также избыточные рулоны нестандартной длины li, получаемые при различных вариантах раскроя yij ,
В качестве переменных следует идентифицировать количество стандартных рулонов, которые должны быть разрезаны при j-м варианте раскроя. Определим переменную следующим образом: xj - количество стандартных рулонов, разрезаемых по варианту j,
Целевая функция - минимум отходов при раскрое
Ограничение на удовлетворение спроса потребителя
Пример 2.8. Транспортная задача.
Имеется три поставщика и четыре потребителя однородной продукции. Известны затраты на перевозку груза от каждого поставщика каждому потребителю. Обозначим их cij ,
Требуется составить такой план перевозок, чтобы обеспечить минимальные суммарные затраты при полном удовлетворении потребностей.
Введем переменные хij - количество груза, перевозимого от i-го поставщика j-му потребителю. Ограничения задачи выглядят следующим образом:
потребности всех потребителей должны быть удовлетворены полностью:
или в общем виде:
груз от поставщика должен быть вывезен полностью:
или в общем виде:
условие неотрицательности переменных:
Целевая функция - минимизировать суммарные затраты на перевозку:
Количество поставщиков и потребителей в общем случае может быть произвольным.
Мы рассмотрели девять примеров типовых задач линейного программирования. Обобщая их, можно сделать следующие выводы.
1. Ограничения в задачах линейного программирования могут быть выражены как равенствами, так и неравенствами.
2. Линейная функция может стремиться как к максимуму, так и к минимуму.
3. Переменные в задачах всегда неотрицательны.
Напомним, что от любой из вышеперечисленных задач можно перейти к канонической (основной) задаче линейного программирования.
Назад | Содержание | Далее
2.3. Графическое решение задачи линейного программирования
Графически способ решения задач линейного программирования целесообразно использовать для:
решения задач с двумя переменными, когда ограничения выражены неравенствами;
решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных.
Запишем задачу линейного программирования с двумя переменными:
целевая функция:
ограничения:
Каждое из неравенств (2.35) – (2.36) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми
Областью допустимых решений системы неравенств (2.35) – (2.36) может быть:
выпуклый многоугольник;
выпуклая многоугольная неограниченная область;
пустая область;
луч;
отрезок;
единственная точка.
Целевая функция (2.34) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значений Z.
Вектор
Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (2.35) – (2.36) и семейство параллельных прямых (2.34), то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z.
Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение.
Для определения данной вершины построим линию уровня
Заканчивая рассмотрение геометрической интерпретации задачи (2.35) – (2.36), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 2.1 – 2.4. Рис. 2.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 2.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 2.3 изображен случай, когда максимум недостижим, а на рис. 2.4. – случай, когда система ограничений задачи несовместна. Отметим, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора
Рис. 2.1. Оптимум функции Z достижим в точке А
Рис. 2.2. Оптимум функции Z достигается в любой точке |АB|
Рис. 2.3. Оптимум функции Z недостижим
Рис. 2.4. Область допустимых решений – пустая область
Для практического решения задачи линейного программирования (2.34) – (2.36) на основе ее геометрической интерпретации необходимо следующее:
1. Построить прямые, уравнения которых получаются в результате замены в ограничениях (2.35) – (2.36) знаков неравенств на знаки равенств.
2. Найти полуплоскости, определяемые каждым из ограничений.
3. Определить многоугольник решений.
4. Построить вектор
5. Построить прямую
6. Передвигать прямую Z в направлении вектора
7. Определить точки координаты максимума функции и вычислить значение целевой функции в этой точке.
Пример 2.9. Рассмотрим решение задачи об ассортименте продукции (пример 2.2) геометрическим способом.
Решение
Построим многоугольник решений (рис.2.5). Для этого в системе координат X10X2 на плоскости изобразим граничные прямые:
2х1 + 3х2 = 9 (L1);
3х1 + 2х2 = 13 (L2);
х1 - х2 = 1 (L3);
х2 = 2 (L4).
Взяв какую-либо точку, например, начало координат, установим, какую полуплоскость определяет соответствующее неравенство. Полуплоскости, определяемые неравенствами, на рис. Показаны стрелками. Областью решений является многоугольник OABCD.
Для построения прямой Z = 3х1 + 4х2 = 0 строим вектор-градиент
= 0 перемещаем параллельно самой себе в направлении вектора
Оптимальный план задачи х1=2,4; х2=1,4. Подставляя значения х1 и х2 в линейную функцию, получим:
Полученное решение означает, что объем производства продукции П1 должен быть равен 2,4 ед., а продукции П2 – 1,4 ед. Доход, получаемый в этом случае, составит: Z = 12,8 д.е.
Рис. 2.5. Решение задачи линейного программирования геометрическим способом
Назад | Содержание | Далее
2.4. Анализ моделей на чувствительность
Анализ моделей на чувствительность — это процесс, реализуемый после получения оптимального решения. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели. В задаче об ассортименте продукции (пример 2.2) может представлять интерес вопрос о том, как повлияет на оптимальное решение увеличение и уменьшение спроса на продукцию или запасов исходного сырья. Возможно, также потребуется анализ влияния рыночных цен на оптимальное решение.
При таком анализе всегда рассматривается комплекс линейных оптимизационных моделей. Это придает модели определенную динамичность, позволяющую исследователю проанализировать влияние возможных изменений исходных условий на полученное ранее оптимальное решение. Динамические характеристики моделей фактически отображают аналогичные характеристики, свойственные реальным процессам. Отсутствие методов, позволяющих выявлять влияние возможных изменений параметров модели на оптимальное решение, может привести к тому, что полученное (статическое) решение устареет еще до своей реализации. Для проведения анализа модели на чувствительность с успехом могут быть использованы графические методы.
Рассмотрим основные задачи анализа на чувствительность на примере 2.9.
Задача 1. Анализ изменений запасов ресурсов.
После нахождения оптимального решения представляется вполне логичным выяснить, как отразится на оптимальном решении изменение запасов ресурсов. Для этого необходимо ответить на два вопроса:
1. На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции Z?
2. На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции Z?
Прежде чем ответить на поставленные вопросы, классифицируем ограничение линейной модели как связывающие (активные) и несвязывающие (неактивные) ограничения. Прямая, представляющая связывающее ограничение, должна проходить через оптимальную точку, в противном случае, соответствующее ограничение будет несвязываюшим. На рис. 2.5 связывающими ограничениями являются ограничения (1) и (3), представленные прямыми L1 и L3 соответственно, т.е. те, которые определяют запасы исходных ресурсов. Ограничение (1) определяет запасы сырья А. Ограничение (3) определяет соотношение спроса на выпускаемую продукцию.
Если некоторое ограничение является связывающим, то соответствующий ресурс относят к разряду дефицитных ресурсов, так как он используется полностью. Ресурс, с которым ассоциировано несвязывающее ограничение, следует отнести к разряду недефицитных ресурсов (т.е. имеющихся в некотором избытке). В нашем примере несвязывающими ограничениями являются (2) и (4). Следовательно, ресурс - сырье В - недефицитный, т.е. имеется в избытке, а спрос на продукцию П2 не будет удовлетворен полностью (в таблице - ресурсы 2 и 4).
При анализе модели на чувствительность к правым частям ограничений определяются: 1) предельна допустимое увеличение запаса дефицитного ресурса, позволяющее улучшить найденное оптимальное решение, и 2) предельно допустимое снижение запаса недефицитного ресурса, не изменяющее найденное ранее оптимальное значение целевой функции.
В нашем примере сырье А и соотношение спроса на выпускаемую продукцию П1 и П2 являются дефицитными ресурсами (в таблице - ресурсы 1, 3).
Рассмотрим сначала ресурс - сырье А. На рис. 2.6 при увеличении запаса этого ресурса прямая L1 перемещается вверх, параллельно самой себе, до точки К, в которой пересекаются линии ограничений L2, L3 и L4. В точке К ограничения (2), (3) и (4) становятся связывающими; оптимальному решению при этом соответствует точка К, а пространством (допустимых) решений становится многоугольник AKD
0. В точке К ограничение (1) (для ресурса А) становится избыточным, так как любой дальнейший рост запаса соответствующего ресурса не влияет ни на пространство решений, ни на оптимальное решение.
Рис. 2.6. Геометрическая интерпретация решения задачи линейного программирования (изменение ресурса А)
Таким образом, объем ресурса А не следует увеличивать сверх того предела, когда соответствующее ему ограничение (1) становится избыточным, т.е. прямая (1) проходит через новую оптимальную точку К. Этот предельный уровень определяется следующим образом. Устанавливаются координаты точки К, в которой пересекаются прямые L2, L3 и L4, т.е. находится решение системы уравнений
В результате получается х1 = 3 и х2 = 1. Затем, путем подстановки координат точки К в левую часть ограничения (1), определяется максимально допустимый запас ресурса А:
Рис. 2.7иллюстрирует ситуацию, когда рассматривается вопрос об изменении соотношения спроса на продукцию П1 и П2.
Рис. 2.7. Геометрическая интерпретация решения задачи линейного программирования (изменение спроса на продукцию)
Новой оптимальной точкой становится точка Е, где пересекаются прямые L1 и L2. Координаты данной точки находятся путем решения системы уравнений (1) и (2) следующим образом:
В результате получается х1 = 4,2; х2 = 0,2, причем суточный спрос на продукцию П1 не должен превышать спрос на продукцию П2 на величину х1 - х2 = 4,2 -0,2= 4 ед.
Дальнейшее увеличение разрыва в спросе на продукцию П1 и П2 не будет влиять на оптимальное решение.
Рассмотрим вопрос об уменьшении правой части несвязывающих ограничений. Ограничение (4) фиксирует предельный уровень спроса на продукцию П2 . Из рис. 2.5 следует, что, не изменяя оптимального решения, прямую L4 (АВ) можно опускать вниз до пересечения с оптимальной точкой С. Так как точка С имеет координаты х1 = 4,2; х2 =1,4 уменьшение спроса на продукцию П2 до величины х2 =1,4 никак не повлияет на оптимальность ранее полученного решения.
Рассмотрим ограничение (2)
Результаты проведенного анализа можно свести в следующую таблицу:
| Ресурс | Тип ресурса | Максимальное изменение запаса ресурса, ед. | Максимальное увеличение дохода от изменения ресурса, у.д.е. |
| 1 (А) | дефицитный | 12 – 9 = +3 | 17 – 12,8 = +4,2 |
| 2 (В) | недефицитный | 10 – 13 = -3 | 12,8 – 12,8 = 0 |
| 3 | дефицитный | 4 – 1 = +3 | 13,4 – 12,8 = +0,6 |
| 4 | недефицитный | 1,4 – 2 = -0,6 | 12,8 – 12,8 = 0 |
Задача 2. Определение наиболее выгодного ресурса.
В задаче 1 анализа на чувствительность мы исследовали влияние на оптимум увеличения объема дефицитных ресурсов. При ограничениях, связанных с дополнительным привлечением ресурсов, естественно задать вопрос: какому из ресурсов следует отдать предпочтение при вложении дополнительных средств? Для этого вводится характеристика ценности каждой дополнительной единицы дефицитного ресурса, выражаемая через соответствующее приращение оптимального значения целевой функции. Такую характеристику для рассматриваемого примера можно получить непосредственно из таблицы, в которой приведены результаты решения задачи 1 на чувствительность. Обозначим ценность дополнительной единицы ресурса i через yi. Величина yi определяется из соотношения
Результаты расчета ценности единицы каждого из ресурсов представлены в следующей таблице:
Полученные результаты свидетельствуют о том, что дополнительные вложения в первую очередь следует направить на увеличение ресурса А и лишь затем - на формирование соотношения спроса на продукцию П1 и продукцию П2 . Что касается недефицитных ресурсов, то, как и следовало ожидать, их объем увеличивать не следует.
Задача 3. Определение пределов изменения коэффициентов целевой функции.
Изменение коэффициентов целевой функции оказывает влияние на наклон прямой, которая представляет эту функцию в принятой системе координат. Вариация коэффициентов целевой функции может привести к изменению совокупности связывающих ограничений и, следовательно, статуса того или иного ресурса (т.е. сделать недефицитный ресурс дефицитным, и наоборот).
При анализе модели ни чувствительность к изменениям коэффициентов целевой функции необходимо исследовать следующие вопросы:
1. Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходят изменения оптимального решения?
2. На сколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным, и, наоборот, дефицитный ресурс сделать недефицитным?
Ответим на поставленные вопросы на нашем примере.
Рассматривая первый вопрос, обозначим через c1 и c2 доходы предприятия от продажи единицы продукции П1 и П2 соответственно. Тогда целевую функцию можно представить в следующем виде:
Z = с1х1 + с2х2
На рис. 2.5 видно, что при увеличении c1 или уменьшении c2 прямая, представляющая целевую функцию Z, вращается (вокруг точки С) по часовой стрелке. Если же c1 уменьшается или c2 увеличивается, эта прямая вращается в противоположном направлении - против часовой стрелки. Таким образом, точка С будет оставаться оптимальной точкой до тех пор, пока наклон прямой не выйдет за пределы, определяемые наклонами прямых для ограничений (1) и (3).
Когда наклон прямой Z станет равным наклону прямой L1, получим две альтернативные оптимальные угловые точки - С и В. Аналогично, если наклон прямой Z станет равным наклону прямой для ограничения (3), будем иметь альтернативные оптимальные угловые точки С и D. Наличие альтернативных оптимумов свидетельствует о том, что одно и то же оптимальное значение Z может достигаться при различных значениях переменных х1 и х2 . Как только наклон прямой выйдет за пределы указанного выше интервала c1, получим некоторое новое оптимальное решение.
Рассмотрим на нашем примере, каким образом можно найти допустимый интервал изменения c1, при котором точка С остается оптимальной. Исходное значение коэффициента c2 = 4 оставим неизменным. На рис. 2.5 видно, что значение c1 можно уменьшать до тех пор, пока прямая Z не совпадет с прямой L1 (отрезок ВС).
Это крайнее минимальное значение коэффициента c1 можно определить из равенства углов наклонов прямой Z и прямой L1 . Так как тангенс угла наклона для прямой Z равен (c1/4) , а для прямой (1) равен 2/3, то минимальное значение c1 определим из равенства c1/4=2/3, откуда
Интервал изменения c1, в котором точка С по-прежнему остается единственной оптимальной точкой, определяется неравенством
Можно заметить, что, как только коэффициент c1 оказывается меньше 8/3, ресурс 3 становится недефицитным, а ресурс 4 - дефицитным. Для предприятия это означает следующее; если доход от продажи единицы продукции П1 станет меньше 8/3 д.е., то наиболее выгодная производственная программа предприятия должна предусматривать выпуск максимально допустимого количества продукции П2 (полностью удовлетворять спрос на продукцию П2). При этим соотношение спроса на продукцию П1 и П2 не будет лимитировать объемы производства, что обусловит недефицитность ресурса (3). Увеличение коэффициента c1 свыше 8/3 д.е. не снимает проблему дефицита ресурсов (1) и (3). Точка С - точка пересечения прямых L1 и L3 - остается все время оптимальной.
Назад | Содержание | Далее
2.5. Симплекс-метод
2.5.1. Общая идея симплекс-метода
Для начала работы требуется, чтобы заданная система ограничений выражалась равенствами, причем в этой системе ограничений должны быть выделены базисные неизвестные. Решение задачи при помощи симплекс-метода распадается на ряд шагов. На каждом шаге от данного базиса Б переходят к другому, новому базису Б1 с таким расчетом, чтобы значение функции Z уменьшалось, т. е.
Назад | Содержание | Далее
2.5.2. Алгоритм симплекс-метода
Рассмотрим систему ограничений и линейную форму вида:
Используя метод Жордана-Гаусса, приведем записанную систему к виду, где выделены базисные переменные. Введем условные обозначения:
x1, x2 , ... , xr - базисные переменные;
xr+1, xr+2 , ... , xn - свободные переменные.
По последней системе ограничений и целевой функции Z построим табл. 2.3.
Таблица 2.3
Симплекс-таблица
Данная таблица называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы.
Алгоритм симплекс-метода сводится к следующему.
1. В последней строке симплекс-таблицы находят наименьший положительный элемент, не считая свободного члена. Столбец, соответствующий этому элементу, считается разрешающим.
2. Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение). Находят наименьшее из этих симплекс-отношений, оно соответствует разрешающей строке.
3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент.
4. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симплекс-таблицы.
5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс-таблица преобразована следующим образом (табл. 2.4):
6. Элемент табл. 2.4, соответствующий разрешающему элементу табл. 2.3, равен обратной величине разрешающего элемента.
7. Элементы строки табл. 2.4, соответствующие элементам разрешающей строки табл. 2.3, получаются путем деления соответствующих элементов табл. 2.3 на разрешающий элемент,
8. Элементы столбца табл. 2.4, соответствующие элементам разрешающего столбца табл. 2.3, получаются путем деления соответствующих элементов табл. 2.3 на разрешающий элемент и берутся с противоположным знаком.
9. Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл. 2.3, одна вершина которого совпадает с разрешающим элементом, а другая - с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент из табл. 2.4 будет равен соответствующему элементу табл. 2.3 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе - произведение элементов из двух неиспользованных вершин прямоугольника.
10. Как только получится таблица, в которой в последней строке все элементы отрицательны, считается, что минимум найден. Минимальное значение функции равно свободному члену в строке целевой функции, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные в этом случае равны нулю.
11. Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается).
Таблица 2.4
Преобразование симплекс-таблицы
Пример 2.10
. Решение задачи симплекс-методом:
Приведем задачу к виду, допускающему применение симплекс-алгоритма:
Подставим в выражение Zmax величины x3, x4, x5:
По алгоритму целевая функция должна стремиться к минимуму:
Составим симплекс-таблицу:
Разыскиваем в последней строке наименьший положительный элемент, в нашем примере он равен +6, первый столбец коэффициентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Минимальное симплекс-отношение равно 1. Разрешающий элемент находится на пересечении строки переменной x4 и столбца - x1.
Переходим к следующей таблице, используя правило прямоугольника:
В последней строке нет положительных элементов, следовательно, оптимальное решение найдено: Zmin = -9; X = (1; 0; 2, 0, 1); Zmin = - Zmax = 9
Назад | Содержание | Далее
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Построить математическую модель задачи линейного программирования (2.1 – 2.20).
Задача 2.1
Для сохранения нормальной жизнедеятельности человек должен в сутки потреблять белков не менее 120 условных единиц (усл. ед.), жиров – не менее 70 и витаминов – не менее 10 усл. ед. Содержание их в каждой единице продуктов П1 и П2 равно соответственно (0,2; 0,075; 0) и (0,1; 0,1; 0,1) усл. ед.
Стоимость 1 ед. продукта П1 – 2 руб., П2 –3 руб.
Постройте математическую модель задачи, позволяющую так организовать питание, чтобы его стоимость была минимальной, а организм получил необходимое количество питательных веществ.
Задача 2.2
Из пункта А в пункт В ежедневно отправляются пассажирские и скорые поезда. Данные об организации перевозок следующие:
| Поезда | Количество вагонов в поезде | ||||
| багажный | почтовый | плацкарт | купе | СВ | |
| скорый | 1 | 1 | 5 | 6 | 3 |
| пассажирский | 1 | - | 8 | 4 | 1 |
| число пассажиров | - | - | 58 | 40 | 32 |
| парк вагонов | 12 | 8 | 81 | 70 | 26 |
Сколько должно быть сформировано скорых и пассажирских поездов, чтобы перевезти наибольшее количество пассажиров?
Задача 2.3
Четыре овощехранилища каждый день обеспечивают картофелем три магазина. Магазины подали заявки соответственно на 17, 12 и 32 тонны. Овощехранилища имеют соответственно 20, 20 ,15 и 25 тонн. Тарифы (в д.е. за 1 тонну) указаны в следующей таблице:
| Овощехранилища | Магазины | ||
| 1 | 2 | 3 | |
| 1 | 2 | 7 | 4 |
| 2 | 3 | 2 | 1 |
| 3 | 5 | 6 | 2 |
| 4 | 3 | 4 | 7 |
Составьте план перевозок, минимизирующий суммарные транспортные расходы.
Задача 2.4
Имеются два склада готовой продукции: А1 и А2 с запасами однородного груза 200 и 300 тонн. Этот груз необходимо доставить трем потребителям В1, В2 и В3 в количестве 100, 150 и 250 тонн соответственно. Стоимость перевозки 1 тонны груза из склада А1 потребителям В1, В2 и В3 равна 5, 3 ,6 д.е., а из склада А2 тем же потребителям – 3, 4, 2 д.е. соответственно.
Составьте план перевозок, минимизирующий суммарные транспортные расход.
Задача 2.5
При откорме каждое животное должно получить не менее 9 ед. белков, 8 ед. углеводов и 11 ед. протеина. Для составления рациона используют два вида корма, представленных в следующей таблице.
| Питательные вещества | Количество единиц питательных веществ на 1 кг. | |
| корма 1 | корма 2 | |
| белки | 3 | 1 |
| углеводы | 1 | 2 |
| протеин | 1 | 6 |
Стоимость 1 кг корма первого вида – 4 д.е., второго – 6 д.е.
Составьте дневной рацион питательности, имеющий минимальную стоимость.
Задача 2.6
Хозяйство располагает следующими ресурсами: площадь – 100 ед., труд – 120 ед., тяга – 80 ед. Хозяйство производит четыре вида продукции: П1 , П2, П3 и П4. Организация производства характеризуется следующей таблицей:
| продукция | Затраты на 1 ед. продукции | Доход от единицы продукции | ||
| площадь | труд | тяга | ||
| П1 | 2 | 2 | 2 | 1 |
| П2 | 3 | 1 | 3 | 4 |
| П3 | 4 | 2 | 1 | 3 |
| П4 | 5 | 4 | 1 | 5 |
Составьте план выпуска продукции, обеспечивающий хозяйству максимальную прибыль.
Задача 2.7
Цех выпускает трансформаторы двух видов. Для изготовления трансформаторов обоих видов используются железо и проволока. Общий запас железа – 3 тонны, проволоки – 18 тонн. На один трансформатор первого вида расходуются 5 кг железа и 3 кг проволоки, а на один трансформатор второго вида расходуются 3 кг железа и 2 кг проволоки. За каждый реализованный трансформатор первого вида завод получает прибыль 3 д.е., второго – 4 д.е.
Составьте план выпуска трансформаторов, обеспечивающий заводу максимальную прибыль.
Задача 2.8
Совхоз отвел три земельный массива размером 5000, 8000 и 9000 га на посевы ржи, пшеницы, кукурузы. Средняя урожайность в центнерах на 1 га по массивам указана в следующей таблице:
| Посевы | Массивы | ||
| I | II | III | |
| рожь | 12 | 14 | 15 |
| пшеница | 14 | 14 | 22 |
| кукуруза | 30 | 35 | 25 |
За 1 центнер ржи совхоз получает 2 д.е., за 1 центнер пшеницы – 2,8 д.е., за 1 центнер кукурузы – 1,4 д.е. Сколько гектаров и на каких массивах совхоз должен отвести на каждую культуру, чтобы получить максимальную выручку, если по плану он обязан сдать не менее 1900 тонны ржи, 158 000 тонны пшеницы и 30 000 тонн кукурузы?
Задача 2.9
Из трех продуктов – I, II, III составляется смесь. В состав смеси должно входить не менее 6 ед. химического вещества А, 8 ед. – вещества В и не менее 12 ед. вещества С. Структура химических веществ приведена в следующей таблице:
| Продукт | Содержание химического вещества в 1 ед. продукции | Стоимость 1 ед. продукции | ||
| А | В | С | ||
| I | 2 | 1 | 3 | 2 |
| II | 1 | 2 | 4 | 3 |
| III | 3 | 1,5 | 2 | 2,5 |
Составьте наиболее дешевую смесь.
Задача 2.10
В школе проводится конкурс на лучшую стенгазету. Одному школьнику дано следующее поручение:
купить акварельной краски по цене 30 д.е. за коробку, цветные карандаши по цене 20 д.е. за коробку, линейки по цене 12 д.е., блокноты по цене 10 д.е.;
красок нужно купить не менее трех коробок, блокнотов – столько, сколько коробок карандашей и красок вместе, линеек не более пяти. На покупки выделяется не менее 300 д.е.
В каком количестве школьник должен купить указанные предметы, чтобы общее число предметов было наименьшим?
Задача 2.11
Имеются три специализированные мастерские по ремонту двигателей. Их производственные мощности равны соответственно 100, 700, 980 ремонтов в год. В пяти районах, обслуживаемых этими мастерскими, потребность в ремонте равна соответственно 90, 180, 150, 120, 80 двигателей в год. Затраты на перевозу одного двигателя из районов к мастерским следующие:
| Районы | Мастерские | ||
| 1 | 2 | 3 | |
| 1 | 4,5 | 3,7 | 8,3 |
| 2 | 2,1 | 4,3 | 2,4 |
| 3 | 7,5 | 7,1 | 4,2 |
| 4 | 5,3 | 1,2 | 6,2 |
| 5 | 4,1 | 6,7 | 3,1 |
Спланируйте количество ремонтов каждой мастерской для каждого из районов, минимизирующее суммарные транспортные расходы.
Задача 2.12
Нефтеперерабатывающий завод получает четыре полуфабриката: 400 тыс. л алкилата, 250 тыс. л крекинг-бензина, 350 тыс. л бензина прямой перегонки и 100 тыс. л изопентона. В результате смешивания этих четырех компонентов в разных пропорциях образуются три сорта авиационного бензина: бензин А-2:3:5:2, бензин В-3:1:2:1, бензин С-2:2:1:3. Стоимость 1 тыс. л указанных сортов бензина характеризуется числами 120 д.е., 100 д.е., 150 д.е.
Составьте план выпуска разных сортов авиационного бензина из условия получения максимальной стоимости всей продукции.
Задача 2.13
Для участия в соревнованиях спортклуб должен выставить команду, состоящую из спортсменов I и II разрядов. Соревнования проводятся по Буге, пряжкам в высоту, прыжкам в длину. В беге должны участвовать 5 спортсменов, в прыжках в длину – 8 спортсменов, а в прыжках в высоту – не более 10. количество очков, гарантируемых спортсмену каждого разряда по каждому виду, указано в таблице:
| Разряд | Бег | Прыжки в высоту | Прыжки в длину |
| I | 4 | 5 | 5 |
| II | 2 | 3 | 3 |
Распределите спортсменов в команды так, чтобы сумма очков команды была наибольшей, если известно, что в команде I разряд имеют только 10 спортсменов.
Задача 2.13
Звероферма выращивает черно-бурых лисиц и песцов. На звероферме имеется 10 000 клеток. В одной клетке могут быть либо 2 лисицы, либо 1 песец. По плану на ферме должно быть не менее 3000 лис и 6000 песцов. В одни сутки необходимо выдавать каждой лисе корма – 4 ед., а каждому песцу – 5 ед. Ферма ежедневно может иметь не более 200 000 единиц корма. От реализации одной шкурки лисы ферма получает прибыль 10 д.е., а от реализации одной шкурки песца – 5 д.е.
Какое количество лисиц и песцов нужно держать не ферме, чтобы получить наибольшую прибыль?
Задача 2.14
Имеются два элеватора, в которых сосредоточено соответственно 4200 и 1200 тонн зерна. Зерна необходимо перевезти трем хлебозаводам в количестве 1000, 2000 и 1600 тонн каждому. Расстояние от элеватора до хлебозавода указано в следующей таблице:
| Элеваторы | Хлебозаводы | ||
| 1 | 2 | 3 | |
| 1 | 20 | 30 | 50 |
| 2 | 60 | 20 | 40 |
Затраты на перевозку 1 тонны продукта на 1 км составляют 25 д.е.
Спланируйте перевозки зерна из условия минимизации транспортных расходов.
Задача 2.15
Из двух сортов бензина образуются две смеси – А и В. Смесь А содержит Бензина 60% 1-го сорта и 40% 2-го сорта; смесь В – 80% 1-го сорта и 20% 2-го сорта. Цена 1 кг смеси А – 10 д.е., а смеси В – 12 д.е.
Составьте план образования смесей, при котором будет получен максимальный доход, если в наличии имеется бензин 50 т 1-госорта и 30 т второго сорта.
Задача 2.16
Имеются две почвенно-климатические зоны, площади которых соответственно равны 0,8 и 0,6 млн. га. Данные об урожайности зерновых культур приведены в таблице:
| Зерновые культуры | Урожайность (ц/га) | Стоимость 1 ц, д.е. | |
| 1-я зона | 2-я зона | ||
| Озимые | 20 | 25 | 8 |
| Яровые | 25 | 20 | 7 |
Определите размеры посевных площадей озимых и яровых культур, необходимые для достижения максимального выхода продукции в стоимостном выражении.
Задача 2.17
Для полива различных участков сада, на которых растут сливы, яблони, груши, служат три колодца. Колодцы могут дать соответственно 180, 90 и 40 ведер воды. Участки сада требуют для полива соответственно 100 120 и 90 ведер воды. Расстояния (в метрах) от колодцев до участков чада указаны в следующей таблице:
| Колодцы | Участки | ||
| сливы | яблони | груши | |
| 1 | 10 | 5 | 12 |
| 2 | 23 | 28 | 33 |
| 3 | 43 | 4 | 39 |
Как лучше организовать полив?
Задача 2.18
На заводе выпускают изделия четырех типов. От реализации 1 ед. каждого изделия завод получает прибыль соответственно 2, 1, 3, 5 д.е. На изготовление изделий расходуются ресурсы трех видов: энергия, материалы, труд. Данные о технологическом процессе приведены в следующей таблице:
| Ресурсы | Затраты ресурсов на единицу изделия | Запасы ресурсов, ед. | |||
| I | II | III | IV | ||
| энергия | 2 | 3 | 1 | 2 | 30 |
| материалы | 4 | 2 | 1 | 2 | 40 |
| труд | 1 | 2 | 3 | 1 | 25 |
Спланируйте производство так, чтобы прибыль от их реализации была наибольшей.
Задача 2.19
При изготовлении изделий П1 и П2 используются сталь и цветные металлы, а также токарные и фрезерные станки. По технологическим нормам на производство единицы изделия П1 требуется 300 и 200 станко-часов соответственно токарного и фрезерного оборудования, а также 10 и 20 кг соответственно стали и цветных металлов. Для производства единицы изделия П2 требуется 400, 100, 70 и 50 соответствующих единиц тех же ресурсов.
Цех располагает 12400 и 6800 станко-часами соответственно токарного и фрезерного оборудования и 640 и 840 кг соответственно стали и цветных металлов. Прибыль от реализации единицы изделия П1 составляет 6 руб. и от единицы изделия П2 – 16 руб.
Постройте математическую модель задачи, используя в качестве показателя эффективности прибыль и учитывая, что время работы фрезерных станков должно быть использовано полностью.
Задача 2.20
Ежедневно в ресторане фирменный коктейль (порция составляет 0,33 л) заказывают в среднем 600 человек. Предполагается, что в ближайшее время их количество увеличится в среднем на 50 человек. Согласно рецепту в составе коктейля должно быть:
не менее 20%, но и не более 35% спирта;
не менее 2% сахара;
не более 5% примесей;
не более 76% воды;
не менее 7% и не более 12% сока.
В таблице приведены процентный состав напитков, из которых смешивается коктейль, и их количество, которое ресторан может ежедневно выделять на приготовление коктейля.
Процентный состав и запасы напитков
| Напиток | Спирт | Вода | Сахар | Примеси | Количество, л/сут. |
| Водка | 40% | 57% | 1% | 2% | 50 |
| Вино | 18% | 67% | 9% | 6% | 184 |
| Сок | 0% | 88% | 8% | 4% | 46 |
Постройте модель, на основании которой можно будет определить, хватит ли ресторану имеющихся ежедневных запасов напитков для удовлетворения возросшего спроса на коктейль.
Решите задачи линейного программирования (2.21 – 2.36) графическим методом, проведите анализ на чувствительность.
Во всех задачах
Задачи линейного программирования (2.37 – 90) решите симплекс-методом и проведите анализ моделей на чувствительность.
Назад | Содержание | Далее
3. ТРАНСПОРТНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ
Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения.
Транспортная задача является одной из наиболее распространенных специальных задач линейного программирования. Частные постановки задачи рассмотрены рядом специалистов по транспорту, например О. Н. Толстым.
Первая строгая постановка транспортной задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее называют проблемой Хичкока.
Первый точный метод решения Т-задачи разработан Л. В. Канторовичем и М. К. Гавуриным. Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Назад | Содержание | Далее
3.1. Постановка задачи
Под термином "транспортные задачи" понимается широкий круг задач не только транспортного характера. Общим для них является, как правило, распределение ресурсов, находящихся у m
производителей (поставщиков), по n потребителям этих ресурсов. Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
Наиболее часто встречаются следующие задачи, относящиеся к транспортным:
прикрепление потребителей ресурса к производителям;
привязка пунктов отправления к пунктам назначения;
взаимная привязка грузопотоков прямого и обратного направлений;
отдельные задачи оптимальной загрузки промышленного оборудования;
оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др.
Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза и объемы отправления по каждому пункту a1, a2 ,...,am . Известна потребность в грузах b1, b2 ,...,bn по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту cij ,
В общем виде исходные данные представлены в табл. 3.1. Строки транспортной таблицы соответствуют пунктам отправления (в последней клетке каждой строки указан объем запаса продукта ai ), а столбцы — пунктам назначения (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в правом верхнем углу находится цена перевозки единицы продукта, а в левом нижнем — значение объема перевозимого груза для данных пунктов.
Таблица 3.1
Исходные данные
Транспортная задача называется закрытой, если суммарный объем отправляемых грузов .
Если такого равенства нет (потребности выше запасов или наоборот), запасу называют открытой, т.е.:
Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнении.
Все грузы из i-х пунктов должны быть отправлены, т.е.:
Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:
Суммарные объемы отправления должны равняться суммарным объемам назначения (3.1). Должно выполняться условие неотрицательности переменных:
Вместо матрицы стоимостей перевозок (cij ) могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы. Как видно из выражения (3.1), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае, если
потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления;
запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления.
Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая.
Транспортным задачам присущи следующие особенности:
распределению подлежат однородные ресурсы;
условия задачи описываются только уравнениями;
все переменные выражаются в одинаковых единицах измерения;
во всех уравнениях коэффициенты при неизвестных равны единице;
каждая неизвестная встречается только в двух уравнениях системы ограничений.
Транспортные задачи могут решаться симплекс-методом. Однако перечисленные особенности позволяют для транспортных задач применять более простые методы решения.
Опорный план является допустимым решением транспортной задачи и используется в качестве начального базисного решения при нахождении оптимального решения методом потенциалов. Существует три метода нахождения опорных планов: метод северо-западного угла, метод минимального элемента и метод Фогеля. "Качество" опорных планов, полученных этими методами, различается: в общем случае метод Фогеля дает наилучшее решение (зачастую оптимальное), а метод северо-западного угла – наихудшее.
Все существующие методы нахождения опорных планов отличаются только способом выбора клетки для заполнения. Само заполнение происходит одинаково независимо от используемого метода.
Назад | Содержание | Далее
3.2. Методы составления начального опорного плана
Базисный план составляется последовательно, в несколько шагов (точнее, m + n - 1 шагов). На каждом из этих шагов заполняется одна клетка, притом так, что, либо полностью удовлетворяется один из заказчиков (тот, в столбце которого находится заполняемая клетка), либо полностью вывозится весь запас груза с одной из баз (с той, в строке которой находится заполняемая клетка).
В первом случае мы можем исключить столбец, содержащий заполненную на этом шаге клетку, и считать, что задача свелась к заполнению таблицы с числом столбцов, на единицу меньшим, чем было перед этим шагом, но с тем же количеством строк и с соответственно измененным запасом груза на одной из баз (на той базе, которой был удовлетворен заказчик на данном шаге).
Во втором случае исключается строка, содержащая заполняемую клетку, и считается, что таблица сузилась на одну строку при неизменном количестве столбцов и при соответствующем изменении потребности заказчика, в столбце которого находится заполняемая клетка.
Начиная с первоначально данной таблицы и повторив (m + n - 2) раз описанный шаг, мы придем к “таблице”, состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причем потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потребность последнего заказчика. В результате, совершив (m + n - 1) шагов, мы и получим искомый опорный план.
Замечание. Может случиться, что уже на некотором (но не на последнем!) шаге потребность очередного заказчика окажется равной запасу груза на очередной базе. Тогда после заполнения очередной клетки объем таблицы как бы одновременно уменьшается на одни столбец и на одну строку. Но и при этом мы должны считать, что уменьшение объема таблицы происходит либо на один столбец, а на базе сохраняется "остаток" равный нулю, либо на одну строку, а у заказчика еще осталась неудовлетворенная "потребность" в количестве нуля единиц груза, которая и удовлетворяется на одном из следующих шагов. Этот нуль ("запас" или "потребностью" – безразлично) надо записать в очередную заполняемую клетку на одном из последующих шагов. Так как при этом оказывается равной нулю одна из базисных неизвестных, то мы имеем дело с вырожденным случаем.
1. Диагональный метод, или метод северо-западного угла. При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного x11 и заканчивается в клетке неизвестного xmn , т. е. идет как бы по диагонали таблицы перевозок.
Пример
Заполнение таблицы начинается с ее северо-западного угла, т.е. клетки с неизвестным x11. Первая база A1 может полностью удовлетворить потребность первого заказчика B1 (a1=300, b1=170, a1 > b1). Полагая x11= 170, вписываем это значение в клетку x11 и исключаем из рассмотрения первый столбец. На базе A1 остается измененный запас
Теперь переходим к заполнению клетки для неизвестного x23 и т.д.
Через шесть шагов у нас останется одна база A3 с запасом груза (остатком от предыдущего шага)
Общий объем перевозок в тонно-километрах для этого плана составит
2. Метод наименьшей стоимости. При этом методе на каждом шаге построения опорного плана первою заполняется та клетка оставшейся части таблицы, которая имеет наименьший тариф. Если такая клетка не единственная, то заполняется любая из них.
Пример
В данном случае заполнение таблицы начинается с клетки для неизвестного x32, для которого мы имеем значение c32 = 10, наименьше из всех значений cij . Эта клетка находится на пересечении третьей строки и второго столбца, соответствующим третьей базе A3 и второму заказчику B2. Третья база A3 может полностью удовлетворить потребность второго заказчика B2 (a3=250, b2=110, a3 > b2) . Полагая x32 = 110, вписываем это значение в клетку x32 и исключаем из рассмотрения второй столбец. На базе A3 остается изменённый запас
На пятом шаге клеток с наименьшими значениями cij оказалось две (c11=c15=70) . Мы заполнили клетку для x15 , положив x15 = 180. Можно было выбрать для заполнения другую клетку, положив x11 = 170, что приведет в результате к другому опорному плану. Общий объем перевозок в тонно-километрах для этого плана составит
Замечание. В диагональном методе не учитываются величины тарифов, в методе же наименьшей стоимости эти величины учитываются, и часто последний метод приводит к плану с меньшими общими затратами (что и имеет место в нашем примере), хотя это и не обязательно.
Кроме рассмотренных выше способов иногда используется, так называемый, метод Фогеля. Суть его состоит в следующем: В распределительной таблице по строкам и столбцам определяется разность между двумя наименьшими тарифами. Отмечается наибольшая разность. Далее в строке (столбце) с наибольшей разностью заполняется клетка с наименьшим тарифом. Строки (столбцы) с нулевым остатком груза в дальнейшем в расчет не принимаются. На каждом этапе загружается только одна клетка. Распределение груза производится, как и ранее.
Назад | Содержание | Далее
3.3. Понятие потенциала и цикла
Для перехода от одного базиса к другому при решении транспортной задачи используются так называемые циклы.
Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям:
1. Одно из неизвестных последовательности свободное, а все остальные – базисные.
2. Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.
3. Три последовательных неизвестных не могут находиться в одном столбце или в одной строке.
4. Если, начиная с какого-либо неизвестного, мы будем последовательно переходить от одного к следующему за ним неизвестному то, через несколько шагов мы вернемся к исходному неизвестному.
Второе условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.
Если каждые два соседних неизвестных цикла соединить отрезком прямой, то будет получено геометрическое изображение цикла – замкнутая ломаная из чередующихся горизонтальных и вертикальных звеньев, одна из вершин которой находится в свободной клетке, а остальные - в базисных клетках.
Можно доказать, что для любой свободной клетки таблицы перевозок существует один и только один цикл, содержащий свободное неизвестное из этой клетки, и что число вершин в цикле всегда четно.
Так, например, в таблице перевозок, составленной по диагональному методу при решения задачи из предыдущего пункта, неизвестному x21 соответствует цикл x21,x23,x13,x11,x21 и т.д.
Пусть теперь мы имеем некоторую свободную клетку с соответствующим ей циклом. Если мы изменим значение свободного неизвестного, увеличив его на некоторое число x, то, переходя последовательно от одной вершины цикла к другой, мы должны будем в силу неизменности сумм по строкам и по столбцам поочередно уменьшать и увеличивать значения неизвестных в цикле на то же число x. Например, в указанном выше цикле для свободного неизвестного x21 получим:
старые значения: x21= 0, x23= 80, x13= 20,x11= 170, x21= 0;
новые значения:
Очевидно, если снабдить вершины цикла поочередно знаками "+" и "–", приписав вершине в свободной клетке знак "+", то можно сказать, что в вершинах со знаком "+" число x прибавляется к прежнему значению неизвестного, находящегося в этой вершине, а в вершинах со знаком "–" это число x вычитается из прежнего значения неизвестного, находящегося в этой вершине.
Замечание. Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак "+", т. е. тот знак, который ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, в каком направлении обходится цикл при “означивании” вершин.
Если в качестве x выбрать наименьшее из чисел, стоящих в вершинах, снабженных знаком "–", то, по крайней мере, одно из прежних базисных неизвестных примет значение нуль, и мы можем перевести его в число свободных неизвестных, сделав вместо него базисным то неизвестное, которое было свободным.
Так, например, в рассмотренном выше цикле имеем отрицательные вершины x21 и x11 ; следовательно, выбрав х = min {80; 170} = 80 , мы получаем:
старые значения: x21= 0, x23= 80, x13= 20,x11= 170, x21= 0;
новые значения:
т. е. вместо прежнего базисного решения получаем новое базисное решение:
Выбор в качестве x минимального среди чисел, стоящих в отрицательных вершинах цикла, обеспечивает допустимость нового базиса.
Если минимальное значение среди базисных неизвестных, стоящих в отрицательных вершинах цикла, принимается не в одной отрицательной вершине, то свободной оставляют только одну из них, а в других клетках с тем же минимальным значением пишут нули. В этом случае новое базисное решение будет вырожденным.
Может случиться, что и само минимальное значение среди чисел в отрицательных клетках равно нулю. Тогда преобразование таблицы перевозок сведется к перестановке этого нуля в свободную клетку. Значения всех неизвестных при этом остаются неизменными, но решения считаются различными, так как различны базисы. Оба решения вырождены.
Описанное выше преобразование таблицы перевозок, в результате которого преобразуется базис, называется пересчетом по циклу.
Заметим, что неизвестные, не входящие в цикл, этим преобразованием не затрагиваются, их значения остаются неизменными и каждое из них остается либо в группе базисных, либо в группе свободных неизвестных, как и до пересчета.
Выясним теперь, как пересчет по циклу влияет на общий объем затрат на перевозки и при каком условии эти затраты становятся меньше.
Пусть xpq – некоторое свободное неизвестное, для которого мы построили цикл и осуществили пересчет по циклу с некоторым числом x
. Если вершине цикла, находящейся в i-й строке и j-м столбце таблицы перевозок, приписан знак "+", то значение неизвестного xij , находящегося в этой вершине, увеличивается на x
, что в свою очередь вызывает увеличение затрат на cij x, где cij – тариф, соответствующий этой клетке; если же указанной вершине приписан знак “–”, то значение неизвестного xij уменьшается на x, что вызывает уменьшение затрат на cij x.
Сложим тарифы, соответствующие положительным вершинам цикла, и вычтем из этой суммы сумму тарифов, соответствующих отрицательным вершинам цикла; полученную разность Spq назовем алгебраической суммой тарифов для данного свободного неизвестного xpq . Подсчет алгебраической суммы тарифов можно истолковать и так: припишем тарифам те же знаки, которые приписаны соответствующим вершинам цикла, тогда алгебраическая сумма тарифов равна сумме таких тарифов со знаком (“относительных тарифов”).
Теперь, очевидно, мы можем, заключить, что в целом при пересчете но циклу, соответствующему свободному неизвестному xpq общий объем затрат на перевозки изменится на произведение алгебраической суммы тарифов на x, т. е. на величину Spqx . Следовательно, если алгебраическая сумма тарифов для некоторого свободного неизвестного xpq отрицательна (Spq < 0), то пересчет по циклу, соответствующему этому неизвестному, приводит к уменьшению общей суммы затрат на реализацию плана перевозок. Если же алгебраическая сумма тарифов положительна (Spq > 0), то пересчет по соответствующему циклу приведет к увеличению общей суммы затрат. И, наконец, если алгебраическая сумма тарифов равна нулю (Spq = 0), то пересчет по соответствующему циклу не изменит общую сумму затрат (два различных базисных плана требуют одинаковых затрат на их реализацию).
Так, например, для цикла x21,x23,x13,x11,x21 в рассмотренной задаче алгебраическая сумма тарифов
Значит, пересчет по этому циклу снижает расходы. И действительно, осуществив такой пересчет, мы получаем план, по которому объем перевозок в тонно-километрах составляет
тогда как по исходному плану он составил S1= 30650. Имеем снижение объема перевозок на 1200 тонно-километров, что и следовало ожидать, так как алгебраическая сумма тарифов в данном случае равна –15, а пересчет по циклу осуществляется с помощью числа х = 80 (изменение затрат равно -15*80 = - 1200).
Вычисление алгебраической суммы тарифов для каждого из свободных неизвестных можно производить без построения соответствующего цикла, пользуясь, так называемыми, потенциалами. Припишем каждой базе Ai, , некоторое число ui, и каждому потребителю Bj некоторое число vj :
так что
ui, + vj = cij , (3.6)
где cij – тарифы, соответствующие клеткам, заполненным базисными неизвестными. Эти числа ui, и vj называются потенциалами соответствующих баз и потребителей.
Зная потенциалы, легко вычислить алгебраическую сумму тарифов. Действительно, если в алгебраической сумме тарифов по циклу, соответствующему свободному неизвестному xpq , заменить тарифы базисных клеток их выражениями через потенциалы по формулам (3.6), то, в силу чередования знаков при вершинах цикла, все потенциалы, кроме up и vq сократятся, и мы получим:
Spq = cpq - ( up + vq ).
Так, например, для цикла x21,x23,x13,x11,x21 в рассмотренной выше задаче имеем
Для базисных клеток сумма потенциалов строки и столбца, в которых находится эта клетка, равна тарифу, соответствующему этой клетке; если же клетка для неизвестного xpq свободная, то сумму потенциалов
называют косвенным тарифом этой клетки. Следовательно, алгебраическая сумма тарифов для свободной клетки xpq равна разности ее настоящего (“истинного”) и косвенного тарифов:
Из (3.8) следует, что если косвенный тариф для данной свободной клетки больше её истинного тарифа, то алгебраическая сумма тарифов по циклу, соответствующему этой клетке, будет отрицательна; если же косвенный тариф меньше истинного, то алгебраическая сумма тарифов положительна, и, наконец, если косвенный тариф равен истинному, то алгебраическая сумма тарифов равна нулю.
Потенциалы можно найти из системы равенств (3.6), рассматривая их как систему (m + n - 1) уравнений с m+n неизвестными. Так как неизвестных здесь на единицу больше, чем уравнений, то, по крайней мере, один из потенциалов мы можем выбрать произвольно, положив, например, u1 = 0; тогда остальные потенциалы легко определяются из уравнений(3.6).
Например, для плана, полученного по диагональному методу в рассмотренной выше задаче, имеем
Система содержит семь уравнений с восемью неизвестными. Выбирая произвольно значение
Положив, например, u1 = 0 , получаем значения потенциалов:
Найдем теперь косвенные тарифы для свободных клеток и сравним их с истинными тарифами:
Для клеток с неизвестными x21 и x32 косвенные тарифы больше истинных. Следовательно, для них мы будемиметь отрицательные алгебраические суммы тарифов:
Значение S21 = -15 мы уже имели раньше, вычисляя алгебраическую сумму тарифов для этой клетки непосредственно по циклу.
Замечание 1. Подсчитывая косвенные тарифы как суммы соответствующих потенциалов, полезно не пропускать и клетки с базисными неизвестными (заполненные клетки). Для этих клеток сумма потенциалов равна истинному тарифу; последнее может служить проверкой правильности найденных значении потенциалов.
Замечание 2. Можно показать, что если сумму всех затрат по данному плану перевозок выразить черех свободные неизвестные, то коэффициент при каждом из таких неизвестных будет равен алгебраической сумме тарифов по циклу, соответствующему ей в таблице перевозок. Это еще раз подтверждает, что пересчет по циклам является специфической формой применения симплекс-метода к решению транспортной задачи.
Назад | Содержание | Далее
3.4. Критерий оптимальности базисного решения транспортной задачи. Методы отыскания оптимального решения
Из сказанного в предыдущем пункте вытекает следующий критерий оптимальности базисного решения транспортной задачи: если для некоторого базисного плана перевозок алгебраические суммы тарифов по циклам для всех свободных клеток неотрицательны, то этот план оптимальный.
Отсюда вытекает способ отыскания оптимального решения транспортной задачи, состоящий в том, что, имея некоторое базисное решение, вычисляют алгебраические суммы тарифов для всех свободных клеток. Если критерий оптимальности выполнен, то данное решение является оптимальным; если же имеются клетки с отрицательными алгебраическими суммами тарифов, то переходят к новому базису, производя пересчет по циклу, соответствующему одной из таких клеток. Полученное таким образом новое базисное решение будет лучше исходного – затраты на его реализацию будут меньшими. Для нового решения также проверяют выполнимость критерия оптимальности и в случае необходимости снова совершают пересчет по циклу для одной из клеток с отрицательной алгебраической суммой тарифов и т. д.
Через конечное число шагов приходят к искомому оптимальному базисному решению.
В случае если алгебраические суммы тарифов для всех свободных клеток положительны, мы имеем единственное оптимальное решение; если же алгебраические суммы тарифов для всех свободных клеток неотрицательны, но среди них имеются алгебраические суммы тарифов, равные нулю, то оптимальное решение не единственное: при пересчете по циклу для клетки с нулевой алгебраической суммой тарифов мы получим оптимальное же решение, но отличное от исходного (затраты по обоим планам будут одинаковыми).
В зависимости от методов подсчета алгебраических сумм тарифов для свободных клеток различают два метода отыскания оптимальногорешения транспортной задачи:
1. Распределительный метод. При этомметоде для каждой пустой клетки строят цикл и для каждого цикла непосредственно вычисляют алгебраическую сумму тарифов.
2. Метод потенциалов. При этом методе предварительно находят потенциалы баз и потребителей, а затем вычисляют для каждой пустой клетки алгебраическую сумму тарифов с помощью потенциалов.
Преимущества метода потенциалов по сравнению с распределительным методом состоят в том, что отпадает необходимость построения циклов для каждой из пустых клеток и упрощается вычисление алгебраических сумм тарифов. Цикл строится только один – тот, по которому производится пересчет.
Применяя метод потенциалов, можно говорить не о знаке алгебраических сумм тарифов, а о сравнении косвенных тарифов с истинными. Требование неотрицательности алгебраических сумм тарифов заменяется условием, что косвенные тарифы не превосходят истинных.
Следует иметь в виду, что потенциалы (так же как и циклы) для каждого нового базисного плана определяются заново.
Назад | Содержание | Далее
3.5. Усложненные задачи транспортного типа
Выше рассмотрена классическая транспортная задача, на которой показано, как используется метод потенциалов для нахождения оптимального плана. В экономике предприятия такие задачи встречаются крайне редко. Обычно при составлении экономико-математической модели задачи транспортного типа приходится вводить целый ряд дополнительных ограничений, а затем пользоваться методом потенциалов.
Ряд экономических задач легко сводимы к транспортной задаче. Рассмотрим наиболее часто встречающиеся ситуации в экономике предприятия.
1. Отдельные поставки от определенных поставщиков некоторым потребителям должны быть исключены (из-за отсутствия необходимых условий хранения, чрезмерной перегрузки коммуникаций и т.д.). Это ограничение требует, чтобы в матрице перевозок, содержащей оптимальный план, определенные клетки оставались свободными. Последнее достигается искусственным завышением затрат на перевозки cij в клетках, перевозки через которые следует запретить. При этом производят завышение величины cij до таких значений, которые заведомо больше всех и с которыми их придется сравнивать в процессе решения задачи.
2. На предприятии необходимо определить минимальные суммарные затраты на производство и транспортировку продукции. С подобной задачей сталкиваются при решении вопросов, связанных с оптимальным размещением производственных объектов. Здесь может оказаться экономически более выгодным доставлять сырье из более отдаленных пунктов, но зато при меньшей его себестоимости. В таких задачах за критерий оптимальности принимают сумму затрат на производство и транспортировку продукции.
3. Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеют ограничения по пропускной способности. Если, например, по маршруту AiBj можно провести не более q единиц груза, то Bj -й столбец матрицы разбивается на два столбца -
4. Поставки по определенным маршрутам обязательны и должны войти в оптимальный план независимо от того, выгодно это или нет. В этом случае уменьшают запас груза у поставщиков и спрос потребителей и решают задачу относительно тех поставок, которые необязательны. Полученное решение корректируют с учетом обязательных поставок.
5. Экономическая задача не является транспортной, но в математическом отношении подобна транспортной, т.к. описывается аналогичной моделью, например, распределение производства изделий между предприятиями, оптимальное закрепление механизмов по определенным видам работы.
6. Необходимо максимизировать целевую функцию задачи транспортного типа. В этой ситуации при составлении опорного плана в первую очередь стараются заполнить клетки с наиболее высокими значениями показателя cij . Выбор клетки, подлежащей заполнению при переходе от одного допустимого плана к другому, должен производиться не по минимальной отрицательной разнице
7. необходимо в одно время распределить груз различного рода по потребителям. Задачи данного типа называются многопродуктовыми транспортными задачами. В этих задачах поставщики m родов грузов разбиваются на m условных поставщиков, а потребители n родов грузов разбиваются на n условных потребителей. С учетом этой разбивки составляют полную транспортную таблицу. При этом заметим, что некоторые маршруты AiBj должны быть блокированы (закрыты), поскольку в данной постановке задачи грузы разного рода не могут заменять друг друга. Этим маршрутам AiBj должна соответствовать очень высокая стоимость перевозки. Многопродуктовую задачу не всегда обязательно описывать одной моделью. Например, если поставки грузов различного рода независимы, тот задачу можно представить в виде комплекса транспортных задач по каждому роду груза. Однако, если между грузами Различного рода существует связь (например, одни из грузов можно заменить другими), то в общем случае исходную модель (задачу) не удается разбить на комплекс простых транспортных задач.
Рассмотрим примеры задач транспортного типа.
Пример 1. Одно фермерское хозяйство (A1) имеет продовольственное зерно двух видов: 3 тыс. тонн – III класса и 4 тыс. тонн - IV класса. Второе фермерское хозяйство (A2) также имеет зерно двух видов: 5 тыс. тонн – III класса и 2 тыс. тонн - IV класса. Зерно должно быть вывезено на два элеватора: на первый элеватор (B1) необходимо поставить 2 тыс. тонн пшеницы III класса, 3 тыс. тонн пшеницы IV класса и остальные 2 тыс. тонн пшеницы любого класса.
Аналогично второй элеватор (B2) должен получить 8,25 тыс. тонн, из них пшеницы - 1 тыс. тонн III класса и 1,5 тыс. тонн IV класса.
Стоимость перевозки в д.е. 1 тонны зерна составляет: из пункта A1 в пункты B1 и B2 - 1 и 1,5 соответственно; из пункта A2 в пункты B1 и B2 - 2 и 1 д.е. соответственно.
Составить оптимальный план перевозок.
Решение
Каждого поставщика условно разбиваем на две части согласно двум видам зерна (
С учетом сделанных замечаний составим первую таблицу (табл. 3.6).
Таблица 3.6
Исходные данные
Перевозки от фиктивного поставщика не производятся, поэтому
Таблица 3.7
Оптимальное решение
Анализ решения. Первый поставщик поставит на первый элеватор (B1) пшеницу III класса ( x12 = 2); пшеницу IV класса (x22 = 3), а также пшеницу любого класса (III или IV) (x13 = 1 ; x23 = 1).
Второй поставщик (A2) поставит на второй элеватор (B2) пшеницу III класса (x31 = 1), пшеницу IV класса (x45 = 1,5) и частично любую пшеницу (x36 = 4; x46 = 0,5). Потребность элеватора в любой пшенице не удовлетворена на 1,25 тыс. тонн (x56 = 1,25). Минимальные затраты на перевозку составили: Zmin = 14 д.е.
Пример 2. Модель производства с запасами.
Фирма переводит свой головной завод на производство определенного вида изделий, которые будут выпускаться в течение четыре месяцев. Величины спроса в течение этих четырех месяцев составляют 100, 200, 180 и 300 изделий соответственно. В каждый месяц спрос можно удовлетворить за счет:
запасов изделий, произведенных в прошлом месяце, сохраняющихся для реализации в будущем;
производства изделий в течение текущего месяца;
избытка производства изделий в более поздние месяцы в счет невыполненных заказов.
Затраты на одно изделие в каждом месяце составляют 4 д.е. Изделие, произведенное для более поздней реализации, влечет за собой дополнительные издержки на хранение в 0,5 д.е. в месяц. С другой стороны, каждое изделие, выпускаемое в счет невыполненных заказов, облагается штрафом в размере 2 д.е. в месяц.
Объем производства изделий меняется от месяца к месяцу в зависимости от выпуска других изделий. В рассматриваемые четыре месяца предполагается выпуск 50, 180, 280 и 270 изделий соответственно.
Требуется составить план, имеющий минимальную стоимость производства и хранения изделий.
Решение
Задачу можно сформулировать как транспортную. Эквивалентность между элементами производственной и транспортной систем устанавливается следующим образом:
| Транспортная система | Производственная система |
| 1. Исходный пункт i | 1. Период производства i |
| 2. Пункт назначения j | 2. Период потребления j |
| 3. Предложение в пункте i | 3. Объем производства за период i |
| 4. Спрос в пункте j | 4. Реализация за период j |
| 5. Стоимость перевозки из i в j | 5. Стоимость производства и хранения за период i и j |
Перед нами структура транспортной модели. Для рассматриваемой задачи стоимость "перевозки" изделий из периода i в период j выражается как:
Из определения cij следует, что затраты в период i при реализации продукции в тот же период i (i = j) оцениваются только стоимостью производства. Если в период i производится продукция, которая будет потребляться позже (i < j), то имеют место дополнительные издержки, связанные с хранением. Аналогично производство в i –й период в счет невыполненных заказов (i > j) влечет за собой дополнительные расходы в виде штрафа. Например,
c11 = 4 д.е.
c24 = 4 + (0,5 + 0,5) = 5 д.е.
c41 = 4 + (2 + 2 + 2) = 10 д.е.
Исходная транспортная таблица выглядит следующим образом (табл. 3.8).
Таблица 3.8
Оптимальное решение
Пример 3. Имеются три сорта бумаги в количестве 10, 8 и 5 т, которую можно использовать на издание четырех книг тиражом 8000, 6000, 15000 и 10000 экземпляров. Расход бумаги на одну книгу составляет: 0,6; 0,8; 0,4; 0,5 кг, а себестоимость тиража книги при использовании i-го сорта бумаги задается следующей матрицей (д.е.):
Определить оптимальное распределение бумажных резервов.
Решение
Задача по своему экономическому смыслу не является транспортной, в то же время можно построить математическую модель, аналогичную транспортной задаче.
Потребности в бумаге легко определить, зная тираж и расход на одну книгу:
8000 * 0,6 = 4,8 т
15000 * 0,4 = 6 т
8000 * 0,6 = 4,8 т
10000 * 0,5 = 5 т
Общие запасы бумаги составляют 23т, а общие потребности – 20,5 т, поэтому необходимо в таблицу ввести фиктивный тираж B5 с нулевыми затратами. В связи с тем, что мы составляем модель относительно бумаги, а матрица cij характеризует себестоимость печатания книги, необходимо исходную матрицу преобразовать относительно единицы бумаги (каждый столбец матрицы cij разделим на количество бумаги, приходящейся на одну книгу).
Согласно изложенному составим первую таблицу (табл. 3.9).
Таблица 3.9
Исходные данные
Используя метод потенциалов, получим оптимальное решение (табл. 3.10).
Таблица 3.10
Оптимальное решение
Анализ решения. Бумаги 1-го сорта в количестве 4,8 т затрачено на издание второй книги; 2,8 т – на издание четвертой книги; 2,4 т – не использовано. Бумаги 2-го сорта затрачено: на первую книгу – 4,8 т; на издание третьей книги 1 т; на издание четвертой книги – 2,2 т; бумага 3-го сорта использована на издание третьей книги в количестве 5 т.
Назад | Содержание | Далее
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Задача 3.1
В пунктах A и B находятся соответственно 150 и 90 т горючего. Пунктам 1, 2, 3 требуются соответственно 60, 70, 110 т горючего. Стоимость перевозки 1 т горючего из пункта A
в пункты 1, 2, 3 равна соответственно 60, 10, 40 тыс. руб. за 1 т соответственно, а из пункта B
в пункты 1, 2, 3 - 120, 20, 80 тыс. руб. за 1 т соответственно.
Составьте план перевозок горючего, минимизирующий общую сумму транспортных расходов.
Задача 3.2
Три завода выпускают грузовые автомобили, которые отправляются четырем потребителям. Первый завод поставляет 90 платформ грузовиков, второй – 30 платформ, третий – 40 платформ. Требуется поставить платформы следующим потребителям: первому – 70 штук, втором – 30, третьем – 20, четвертому – 40 штук. Стоимость перевозки одной платформы от поставщика до потребителя указана в следующей таблице (д.е.):
| Поставщики | Потребители | |||
| 1 | 2 | 3 | 4 | |
| I | 18 | 20 | 14 | 10 |
| II | 10 | 20 | 40 | 30 |
| III | 16 | 22 | 10 | 20 |
Составьте оптимальный план доставки грузовых автомобилей
Задача 3.3
Строительство магистральной дороги включает задачу заполнения имеющихся на трассе выбоин до уровня основной дороги и срезания в некоторых местах дороги выступов. Срезанным грунтом заполняются выбоины. Перевозка грунта осуществляется грузовиками одинаковой грузоподъемности. Расстояние в километрах от срезов до выбоин и объем работ указаны в следующей таблице:
| Поставщики | Потребители | Наличие грунта, т | ||
| I | II | III | ||
| А | 1 | 2 | 3 | 10 |
| В | 2 | 1 | 3 | 30 |
| С | 1 | 2 | 4 | 20 |
| Требуемое количество грунта, т | 100 | 140 | 60 | |
Составьте план перевозок, минимизирующий общий пробег грузовиков.
Задача 3.4
Груз, хранящийся на трех складах и требующий для перевозки 60, 80, 106 автомашин соответственно, необходимо перевезти в четыре магазина. Первому магазину требуется 44 машины груза, второму – 70, третьему – 50 и четвертому – 82 машины. Стоимость пробега одной автомашины за 1 км составляет 10 д.е. Расстояния от складов до магазинов указаны в следующей таблице:
| Склады | Магазины | |||
| 1 | 2 | 3 | 4 | |
| 1 | 13 | 17 | 6 | 8 |
| 2 | 2 | 7 | 10 | 41 |
| 3 | 12 | 18 | 2 | 22 |
Составьте оптимальный по стоимости план перевозки груза от складов до магазинов.
Задача 3.5
На складах А, В, С находится сортовое зерно 100, 150, 250 т, которое нужно доставить в четыре пункта. Пункту 1 необходимо поставить 50 т, пункту 2 – 100, пункту 3 – 200, пункту 4 – 150 т сортового зерна. Стоимость доставки 1 т зерна со склада А в указанные пункты соответственно равна (д.е.) 80, 30, 50, 20; со склада В – 40, 10, 60, 70; со склада С -10, 90, 40, 30.
Составьте оптимальный план перевозки зерна из условия минимума стоимости перевозки.
Задача 3.6
Завод имеет три цеха – А, В, С и четыре склада – 1; 2; 3; 4. Цех А производит 30 тыс. шт. изделий, цех В – 40; цех С – 20 тыс. шт. изделий. Пропускная способность складов за то же время характеризуется следующими показателями: склад 1 – 20 тыс. шт. изделий; склад 2 – 30; склад 3 – 30 и склад 4 – 10 тыс. шт. изделий. Стоимость перевозки 1 тыс. шт. изделий из цеха А на склады 1, 2, 3, 4 – соответственно (д.е.): 20, 30, 40, 40; из цеха В – соответственно 30, 20, 50, 10; а из цеха С – соответственно 40, 30, 20, 60.
Составьте такой план перевозки изделий, при котором расходы на перевозку 90 тыс. шт. изделий были бы наименьшими.
Задача 3.7
Имеются две станции технического обслуживания (СТО), выполняющие ремонтные работы для трех автопредприятий. Производственные мощности СТО, стоимость ремонта в различных СТО, затраты на транспортировку от автопредприятий на СТО и обратно и прогнозируемое количество ремонтов в планируемом периоде на каждом автопредприятии приведены в следующей таблице:
| СТО | Стоимость ремонта ед., д.е. | Затраты на транспортировку, тыс. руб. | Производственная мощность, шт. | ||
| АТП-1 | АТП-2 | АТП-3 | |||
| 1 | 520 | 60 | 70 | 20 | 10 |
| 2 | 710 | 40 | 50 | 30 | 8 |
| Потребное количество, д.е. | | 6 | 7 | 5 | 18 |
Требуется определить, какое количество автомашин из каждого автопредприятия необходимо отремонтировать на каждый СТО, чтобы суммарные расходы на ремонт и транспортировку были минимальными.
Задача 3.8
Имеются два хранилища с однородным продуктом, в которых сосредоточено 200 и 120 т продукта соответственно. Продукты необходимо перевезти трем потребителям соответственно в количестве 80, 100 и 120 т. Расстояния от хранилищ до потребителей (8 км) следующие:
| Хранилище | Потребители | ||
| 1 | 2 | 3 | |
| 1 | 20 | 30 | 50 |
| 2 | 60 | 20 | 40 |
Затраты на перевозку 1 т продукта на 1 км постоянны и равны 5 д.е.
Определите план перевозок продукта от хранилищ до потребителей из условия минимизации транспортных расходов.
Задача 3.9
Промышленный концерн имеет два заводы и пять складов в различных регионах страны. Каждый месяц первый завод производит 40,а второй 70 ед. продукции. Вся продукция, производимая заводами, должна быть направлена на склады. Вместимость первого склада равна 20 ед. продукции; второго – 30; третьего – 15; четвертого – 27; пятого – 28 ед. Издержки транспортировки продукции от завода до склада следующие (ед.):
| Заводы | Склады | ||||
| 1 | 2 | 3 | 4 | 5 | |
| 1 | 520 | 480 | 650 | 500 | 720 |
| 2 | 450 | 525 | 630 | 560 | 750 |
Распределите план перевозок из условия минимизации ежемесячных расходов на транспортировку.
Задача 3.10
Три нефтеперерабатывающих завода с суточной производительностью 10, 8 и 6 млн. галлонов бензина снабжают три бензохранилища, спрос которых составляет 6, 11 и 7 млн. галлонов. Бензин транспортируется в бензохранилища по трубопроводу. Стоимость перекачки бензина на 2 км составляет 5 д.е. на 100 галлонов. Завод 1 не связан с хранилищем 3. Расстояние от заводов до бензохранилищ следующее:
| № завода | Бензохранилища | ||
| 1 | 2 | 3 | |
| 1 | 100 | 150 | - |
| 2 | 420 | 180 | 60 |
| 3 | 200 | 280 | 120 |
Сформулируйте соответствующую транспортную задачу и решите на минимум транспортных затрат.
Задача 3.11
Автомобили перевозятся на трайлерах из трех центров распределения пяти продавцам. Стоимость перевозки в расчете на 1 км пути, пройденного трайлером, равна 60 д.е. Один трайлер может перевозить 15 автомобилей. Стоимость перевозок не зависит от того, насколько полно загружается трайлер. В приведенной ниже таблице указаны расстояния между центрами распределения и продавцами, а также величины, характеризующие ежемесячный спрос и объемы поставок, исчисляемые количеством автомобилей:
| Центр распределения | Продавцы | Объем поставок, шт. | ||||
| 1 | 2 | 3 | 4 | 5 | ||
| 1 | 80 | 120 | 180 | 150 | 50 | 300 |
| 2 | 60 | 70 | 50 | 65 | 90 | 350 |
| 3 | 30 | 80 | 120 | 140 | 90 | 120 |
| Спрос на автомобили, шт. | 110 | 250 | 140 | 150 | 120 | 770 |
Определите минимальные затраты на доставку автомобилей.
Задача 3.12
Решите задачу распределения станков четырех различных типов по шести типам работ. Пусть имеются 30, 45, 25 и 20 станков соответствующих типов. Шесть типов работ характеризуются 30, 20, 10, 40, 10 и 10 операциями соответственно. На станке 3 не может выполняться операция 6. Исходя из коэффициентов стоимости операции, представленных в следующей таблице, постройте модель и выполните оптимальное распределение станков по работам:
| Тип станков | Тип работы | |||||
| 1 | 2 | 3 | 4 | 5 | 6 | |
| 1 | 10 | 1 | 3 | 7 | 14 | 8 |
| 2 | 4 | 8 | 12 | 2 | 10 | 7 |
| 3 | 12 | 3 | 14 | 6 | 2 | - |
| 4 | 11 | 12 | 9 | 3 | 1 | 3 |
Задача 3.13
В данной транспортной задаче суммарный спрос превосходит суммарный объем производства. Пусть штрафы за недопоставку единицы продукции в пункты назначения 1, 2 и 3 равны соответственно 5, 3 и 2.
Исходные данные следующие:
| Заводы | Потребители | Объем производства, шт. | ||
| 1 | 2 | 3 | ||
| A1 | 3 | 2 | 4 | 50 |
| A2 | 5 | 4 | 5 | 75 |
| A3 | 1 | 6 | 7 | 30 |
| Потребность, шт. | 60 | 40 | 70 | |
Найдите оптимальное решение.
Для задач 3.14 – 3.25 дано следующее условие.
Имеются три пункта поставки однородного груза - A1; A2; A3 и пять пунктов потребления этого груза B1; B2; B3; B4; B5. В пунктах A1; A2; A3 находится груз a1; a2; a3 соответственно. Груз необходимо доставить в пункты B1; B2; B3; B4; B5 в количестве b1; b2; b3; b4; b5 соответственно. Расстояния между пунктами в км заданы следующей матрицей:
Требуется найти оптимальный план закрепления потребителей за поставщиками однородного груза при условии минимизации общего пробега автомобилей, используя параметры, представленные ниже.
Задача 3.14
Задача 3.15
Задача 3.16
Задача 3.17
Задача 3.18
Задача 3.19
Задача 3.20
Задача 3.21
Задача 3.22
Задача 3.23
Задача 3.24
Задача 3.25
Назад | Содержание | Далее
4. МОДЕЛИРОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ
4.1. Компоненты и классификация моделей массового обслуживания
Системы массового обслуживания - это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания.
С позиции моделирования процесса массового обслуживания ситуации, когда образуются очереди заявок (требований) на обслуживание, возникают следующим образом. Поступив в обслуживающую систему, требование присоединяется к очереди других (ранее поступивших) требований. Канал обслуживания выбирает требование из находящихся в очереди, с тем чтобы приступить к его обслуживанию. После завершения процедуры обслуживания очередного требования канал обслуживания приступает к обслуживанию следующего требования, если таковое имеется в блоке ожидания.
Цикл функционирования системы массового обслуживания подобного рода повторяется многократно в течение всего периода работы обслуживающей системы. При этом предполагается, что переход системы на обслуживание очередного требования после завершения обслуживания предыдущего требования происходит мгновенно, случайные моменты времени.
Примерами систем массового обслуживания могут служить:
1. посты технического обслуживания автомобилей;
2. посты ремонта автомобилей;
3. персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач;
4. станции технического обслуживания автомобилей;
5. аудиторские фирмы;
6. отделы налоговых инспекций, занимающиеся приемкой и проверкой текущей отчетности предприятий;
7. телефонные станции и т. д.
Основными компонентами системы массового обслуживания любого вида являются:
входной поток поступающих требований или заявок на обслуживание;
дисциплина очереди;
механизм обслуживания.
Входной поток требований. Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (требования поступают группами в систему). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслуживанием.
Дисциплина очереди - это важный компонент системы массового обслуживания, он определяет принцип, в соответствии с которым поступающие на вход обслуживающей системы требования подключаются из очереди к процедуре обслуживания. Чаще всего используются дисциплины очереди, определяемые следующими правилами:
первым пришел — первый обслуживаешься;
пришел последним — обслуживаешься первым;
случайный отбор заявок;
отбор заявок по критерию приоритетности;
ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»).
Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся: продолжительность процедуры обслуживания и количество требований, удовлетворяемых в результате выполнения каждой такой процедуры. Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований».
Следует отметить, что время обслуживания заявки зависит от характера самой заявки или требований клиента и от состояния и возможностей обслуживающей системы. В ряде случаев приходится также учитывать вероятность выхода обслуживающего прибора по истечений некоторого ограниченного интервала времени.
Структура обслуживающей системы определяется количеством и взаимным расположением каналов обслуживания (механизмов, приборов и т. п.). Прежде всего следует подчеркнуть, что система обслуживания может иметь не один канал обслуживания, а несколько; система такого рода способна обслуживать одновременно несколько требований. В этом случае все каналы обслуживания предлагают одни и те же услуги, и, следовательно, можно утверждать, что имеет место параллельное обслуживание.
Система обслуживания может состоять из нескольких разнотипных каналов обслуживания, через которые должно пройти каждое обслуживаемое требование, т. е. в обслуживающей системе процедуры обслуживания требований реализуются последовательно. Механизм обслуживания определяет характеристики выходящего (обслуженного) потока требований.
Предметом теории массового обслуживания является установление зависимости между факторами, определяющими функциональные возможности системы массового обслуживания, и эффективностью ее функционирования. В большинстве случаев все параметры, описывающие системы массового обслуживания, являются случайными величинами или функциями, поэтому эти системы относятся к стохастическим системам.
Случайный характер потока заявок (требований), а также, в общем случае, и длительности обслуживания приводит к тому, что в системе массового обслуживания происходит случайный процесс. По характеру случайного процесса, происходящего в системе массового обслуживания (СМО), различают системы марковские и немарковские. В марковских системах входящий поток требований и выходящий поток обслуженных требований (заявок) являются пуассоновскими. Пуассоновские потоки позволяют легко описать и построить математическую модель системы массового обслуживания. Данные модели имеют достаточно простые решения, поэтому большинство известных приложений теории массового обслуживания используют марковскую схему. В случае немарковских процессов задачи исследования систем массового обслуживания значительно усложняются и требуют применения статистического моделирования, численных методов с использованием ЭВМ.
Независимо от характера процесса, протекающего в системе массового обслуживания, различают два основных вида СМО:
системы с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и сразу же покидает очередь;
системы с ожиданием (очередью), в которых заявка, поступившая в момент, когда все каналы обслуживания заняты, становится в очередь и ждет, пока не освободится один из каналов. Системы массового обслуживания с ожиданием делятся на системы с ограниченным ожиданием и системы с неограниченным ожиданием.
В системах с ограниченным ожиданием может ограничиваться:
длина очереди;
время пребывания в очереди.
В системах с неограниченным ожиданием заявка, стоящая в очереди, ждет обслуживание неограниченно долго, т.е. пока не подойдет очередь.
Все системы массового обслуживания различают по числу каналов обслуживания:
одноканальные системы;
многоканальные системы.
Приведенная классификация СМО является условной. На практике чаще всего системы массового обслуживания выступают в качестве смешанных систем. Например, заявки ожидают начала обслуживания до определенного момента, после чего система начинает работать как система с отказами.
4.2. Определение характеристик систем массового обслуживания
4.2.1. Одноканальная модель с пуассоновским входным потоком с экспоненциальным распределением длительности обслуживания
Простейшей одноканальной моделью с вероятностными входным потоком и процедурой обслуживания является модель, характеризуемая показательным распределением как длительностей интервалов между поступлениями требований, так и длительностей обслуживания. При этом плотность распределения длительностей интервалов между поступлениями требований имеет вид
где
Плотность распределения длительностей обслуживания:
где
Потоки заявок и обслуживании простейшие.
Пусть система работает с отказами. Необходимо определить абсолютную и относительную пропускную способность системы.
Представим данную систему массового обслуживания в виде графа (рис. 4.1), у которого имеются два состояния:
S0 - канал свободен (ожидание);
S1 - канал занят (идет обслуживание заявки).
Рис. 4.1. Граф состояний одноканальной СМО с отказами
Обозначим вероятности состояний: P0(t) - вероятность состояния «канал свободен»; P1(t) - вероятность состояния «канал занят». По размеченному графу состояний (рис. 4.1) составим систему дифференциальных уравнений Колмогорова для вероятностей состояний:
Система линейных дифференциальных уравнений (4.3) имеет решение с учетом нормировочного условия P0(t) + P1(t) = 1 . Решение данной системы называется неустановившимся, поскольку оно непосредственно зависит от t
и выглядит следующим образом:
P1(t) = 1 - P0(t) = 1 . (4.5)
Нетрудно убедиться, что для одноканальной СМО с отказами вероятность P0(t) есть не что иное, как относительная пропускная способность системы q.
Действительно, P0 - вероятность того, что в момент t канал свободен и заявка, пришедшая к моменту t, будет обслужена, а следовательно, для данного момента времени t
среднее отношение числа обслуженных заявок к числу поступивших также равно P0(t), т. е.
q = P0(t), (4.6)
По истечении большого интервала времени (при
Зная относительную пропускную способность, легко найти абсолютную. Абсолютная пропускная способность (А) - среднее число заявок, которое может обслужить система массового обслуживания в единицу времени:
Вероятность отказа в обслуживании заявки будет равна вероятности состояния «канал занят»:
Данная величина Pотк может быть интерпретирована как средняя доля необслуженных заявок среди поданных.
Пример 4.1. Пусть одноканальная СМО с отказами представляет собой один пост ежедневного обслуживания (ЕО) для мойки автомобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока автомобилей
Требуется определить в установившемся режиме предельные значения:
относительной пропускной способности q;
абсолютной пропускной способности А;
вероятности отказа Pотк ;
Сравните фактическую пропускную способность СМО с номинальной, которая была бы, если бы каждый автомобиль обслуживался точно 1,8 часа и автомобили следовали один за другим без перерыва.
Решение
1. Определим интенсивность потока обслуживания:
2. Вычислим относительную пропускную способность:
Величина q означает, что в установившемся режиме система будет обслуживать примерно 35% прибывающих на пост ЕО автомобилей.
3. Абсолютную пропускную способность определим по формуле:
Это означает, что система (пост ЕО) способна осуществить в среднем 0,356 обслуживания автомобилей в час.
4. Вероятность отказа:
Это означает, что около 65% прибывших автомобилей на пост ЕО получат отказ в обслуживании.
5. Определим номинальную пропускную способность системы:
Оказывается, что Аном в 1,5 раза
Рассмотрим теперь одноканальную СМО с ожиданием.
Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание - простейший поток с интенсивностью
Предположим, что независимо от того, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), т. е. клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость.
Граф состояний СМО в этом случае имеет вид, показанный на рис. 4.2.
Рис. 4.2. Граф состояний одноканальной СМО с ожиданием (схема гибели и размножения)
Состояния СМО имеют следующую интерпретацию:
S0 - «канал свободен»;
S1 - «канал занят» (очереди нет);
S2 - «канал занят» (одна заявка стоит в очереди);
…………………………………………………….
Sn - «канал занят» (n -1 заявок стоит в очереди);
SN - «канал занят» (N - 1 заявок стоит в очереди). Стационарный процесс в данной системе будет описываться следующей системой алгебраических уравнений:
где
Решение приведенной выше системы уравнений (4.10) для нашей модели СМО имеет вид
Тогда
Следует отметить, что выполнение условия стационарности
- 1), а не соотношением между интенсивностями входного потока, т. е. не отношением
Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N - 1):
вероятность отказа в обслуживании заявки:
относительная пропускная способность системы:
абсолютная пропускная способность:
среднее число находящихся в системе заявок:
среднее время пребывания заявки в системе:
средняя продолжительность пребывания клиента (заявки) в очереди:
среднее число заявок (клиентов) в очереди (длина очереди):
Рассмотрим пример одноканальной СМО с ожиданием.
Пример 4.2. Специализированный пост диагностики представляет собой одноканальную СМО. Число стоянок для автомобилей, ожидающих проведения диагностики, ограниченно и равно 3 [(N - 1) = 3]. Если все стоянки заняты, т. е. в очереди уже находится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток автомобилей, прибывающих на диагностику, распределен по закону Пуассона и имеет интенсивность
Требуется определить вероятностные характеристики поста диагностики, работающего в стационарном режиме.
Решение
1. Параметр потока обслуживании автомобилей:
2. Приведенная интенсивность потока автомобилей определяется как отношение интенсивностей
3. Вычислим финальные вероятности системы:
4. Вероятность отказа в обслуживании автомобиля:
5. Относительная пропускная способность поста диагностики:
6. Абсолютная пропускная способность поста диагностики
7. Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):
8. Среднее время пребывания автомобиля в системе:
9. Средняя продолжительность пребывания заявки в очереди на обслуживание:
10. Среднее число заявок в очереди (длина очереди):
Работу рассмотренного поста диагностики можно считать удовлетворительной, так как пост диагностики не обслуживает автомобили в среднем в 15,8% случаев ( Pотк = 0,158).
Перейдем теперь к рассмотрению одноканальной СМО с ожиданием без ограничения на вместимость блока ожидания (т. е.
Стационарный режим функционирования данной СМО существует при
Решение данной системы уравнений имеет вид
где
Характеристики одноканальной СМО с ожиданием, без ограничения на длину очереди, следующие:
среднее число находящихся в системе клиентов (заявок) на обслуживание:
средняя продолжительность пребывания клиента в системе:
среднее число клиентов в очереди на обслуживании:
средняя продолжительность пребывания клиента в очереди:
Пример 4.3. Вспомним о ситуации, рассмотренной в примере 4.2, где речь идет о функционировании поста диагностики. Пусть рассматриваемый пост диагностики располагает неограниченным количеством площадок для стоянки прибывающих на обслуживание автомобилей, т. е. длина очереди не ограничена.
Требуется определить финальные значения следующих вероятностных характеристик:
вероятности состояний системы (поста диагностики);
среднее число автомобилей, находящихся в системе (на обслуживании и в очереди);
среднюю продолжительность пребывания автомобиля в системе (на обслуживании и в очереди);
среднее число автомобилей в очереди на обслуживании;
среднюю продолжительность пребывания автомобиля в очереди.
Решение
1. Параметр потока обслуживания
2. Вычислим предельные вероятности системы по формулам
и т.д.
Следует отметить, что P0(t) определяет долю времени, в течение которого пост диагностики вынужденно бездействует (простаивает). В нашем примере она составляет 10,7%, так как P0(t) = 0,107.
3. Среднее число автомобилей, находящихся в системе (на обслуживании и в очереди):
4. Средняя продолжительность пребывания клиента в системе:
5. Среднее число автомобилей в очереди на обслуживание:
6. Средняя продолжительность пребывания автомобиля в очереди:
7. Относительная пропускная способность системы:
q = 1
т. е. каждая заявка, пришедшая в систему, будет обслужена. 8. Абсолютная пропускная способность:
Следует отметить, что предприятие, осуществляющее диагностику автомобилей, прежде всего интересует количество клиентов, которое посетит пост диагностики при снятии ограничения на длину очереди.
Допустим, в первоначальном варианте количество мест для стоянки прибывающих автомобилей было равно трем (см. пример 4.2). Частота т возникновения ситуаций, когда прибывающий на пост диагностики автомобиль не имеет возможности присоединиться к очереди:
В нашем примере при N = 3 + 1 = 4 и
При 12-часовом режиме работы поста диагностики это эквивалентно тому, что пост диагностики в среднем за смену (день) будет терять 12 • 0,134 = 1,6 автомобиля.
Снятие ограничения на длину очереди позволяет увеличить количество обслуженных клиентов в нашем примере в среднем на 1,6 автомобиля за смену (12ч. работы) поста диагностики. Ясно, что решение относительно расширения площади для стоянки автомобилей, прибывающих на пост диагностики, должно основываться на оценке экономического ущерба, который обусловлен потерей клиентов при наличии всего трех мест для стоянки этих автомобилей.
Назад | Содержание | Далее
4.2.2. Многоканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительности обслуживания
В подавляющем большинстве случаев на практике системы массового обслуживания являются многоканальными, и, следовательно, модели с n
обслуживающими каналами (где n > 1) представляют несомненный интерес.
Процесс массового обслуживания, описываемый данной моделью, характеризуется интенсивностью входного потока
клиентов.
Граф состояний многоканальной системы массового обслуживания с отказами имеет вид, показанный на рис. 4.3.
Рис. 4.3. Граф состояний многоканальной СМО с отказами
Состояния СМО имеют следующую интерпретацию:
S0 - все каналы свободны;
S1 - занят один канал, остальные свободны;
…………………………………………………….
Sk - заняты ровно k каналов, остальные свободны;
…………………………………………………….
Sn - заняты все n каналов, остальные свободны;
Уравнения Колмогорова для вероятностей состояний системы P0 , ... ,Pk, ... Pn будет иметь следующий вид:
Начальные условия решения системы таковы:
P0(0) = 1, P1(0) = P2(0) = ... = Pk(0) = ... = P1(0) = 0 .
Стационарное решение системы имеет вид:
где
Формулы для вычисления вероятностей Pk называются формулами Эрланга.
Определим вероятностные характеристики функционирования многоканальной СМО с отказами в стационарном режиме:
вероятность отказа:
так как заявка получает отказ, если приходит в момент, когда все n каналов заняты. Величина Pотк характеризует полноту обслуживания входящего потока;
вероятность того, что заявка будет принята к обслуживанию (она же - относительная пропускная способность системы q) дополняет Pотк до единицы:
абсолютная пропускная способность
среднее число каналов, занятых обслуживанием (
Величина
Пример 4.4. Пусть n-канальная СМО представляет собой вычислительный центр (ВЦ) с тремя (n = 3) взаимозаменяемыми ПЭВМ для решения поступающих задач. Поток задач, поступающих на ВЦ, имеет интенсивность
Требуется вычислить финальные значения:
вероятности состояний ВЦ;
вероятности отказа в обслуживании заявки;
относительной пропускной способности ВЦ;
абсолютной пропускной способности ВЦ;
среднего числа занятых ПЭВМ на ВЦ.
Определите, сколько дополнительно надо приобрести ПЭВМ, чтобы увеличить пропускную способность ВЦ в 2 раза.
Решение
1. Определим параметр
2. Приведенная интенсивность потока заявок
3. Предельные вероятности состояний найдем по формулам Эрланга (4.27):
4. Вероятность отказа в обслуживании заявки
5. Относительная пропускная способность ВЦ
6. Абсолютная пропускная способность ВЦ
7. Среднее число занятых каналов – ПЭВМ
Таким образом, при установившемся режиме работы СМО в среднем будет занято 1,5 компьютера из трех - остальные полтора будут простаивать. Работу рассмотренного ВЦ вряд ли можно считать удовлетворительной, так как центр не обслуживает заявки в среднем в 18% случаев. Очевидно, что пропускную способность ВЦ при данных
Определим, сколько нужно использовать ПЭВМ, чтобы сократить число необслуженных заявок, поступающих на ВЦ, в 10 раз, т.е. чтобы вероятность отказа в решении задач не превосходили 0,0180. Для этого используем формулу (4.28):
Составим следующую таблицу:
Рассмотрим многоканальную систему массового обслуживания с ожиданием. Процесс массового обслуживания при этом характеризуется следующим: входной и выходной потоки являются пуассоновскими с интенсивностями
В установившемся режиме функционирование многоканальной СМО с ожиданием и неограниченной очередью может быть описано с помощью системы алгебраических уравнений:
Решение системы уравнений (4.32) имеет вид
где
Решение будет действительным, если выполняется следующее условие:
Вероятностные характеристики функционирования в стационарном режиме многоканальной СМО с ожиданием и неограниченной очередью определяются по следующим формулам:
вероятность того, что в системе находится n клиентов на обслуживании, определяется по формулам (4.33) и (4.34);
среднее число клиентов в очереди на обслуживание
среднее число находящихся в системе клиентов (заявок на Обслуживание и в очереди)
средняя продолжительность пребывания клиента (заявки на обслуживание) в очереди
средняя продолжительность пребывания клиента в системе
Рассмотрим примеры многоканальной системы массового обслуживания с ожиданием.
Пример 4.5. Механическая мастерская завода с тремя постами (каналами) выполняет ремонт малой механизации. Поток неисправных механизмов, прибывающих в мастерскую, - пуассоновский и имеет интенсивность
Требуется вычислить следующие предельные значения вероятностных характеристик системы:
вероятности состояний системы;
среднее число заявок в очереди на обслуживание;
среднее число находящихся в системе заявок;
среднюю продолжительность пребывания заявки в очереди;
среднюю продолжительность пребывания заявки в системе.
Решение
1. Определим параметр потока обслуживаний
2. Приведенная интенсивность потока заявок
при этом
Поскольку
3. Вычислим вероятности состояний системы:
4. Вероятность отсутствия очереди у мастерской
5. Среднее число заявок в очереди на обслуживание
6. Среднее число находящихся в системе заявок
7. Средняя продолжительность пребывания механизма в очереди на обслуживание
8. Средняя продолжительность пребывания механизма в мастерской (в системе)
Назад | Содержание | Далее
4.2.3. Модель обслуживания машинного парка
Модель обслуживания машинного парка представляет собой модель замкнутой системы массового обслуживания.
До сих пор мы рассматривали только такие системы массового обслуживания, для которых интенсивность
Например, обслуживается машинный парк, состоящий из N машин, бригадой R механиков (N > R), причем каждая машина может обслуживаться только одним механиком. Здесь машины являются источниками требований (заявок на обслуживание), а механики - обслуживающими каналами. Неисправная машина после обслуживания используется по своему прямому назначению и становится потенциальным источником возникновения требований на обслуживание. Очевидно, что интенсивность
В рассматриваемой модели емкость источника требований следует считать ограниченной. Входящий поток требований исходит из ограниченного числа эксплуатируемых машин (N - k), которые в случайные моменты времени выходят из строя и требуют обслуживания. При этом каждая машина из (N - k) находится в эксплуатации. Генерирует пуассоновский поток требований с интенсивностью X независимо от других объектов, общий (суммарный) входящий поток имеет интенсивность
Таким образом, в замкнутой системе массового обслуживания входящий поток требований формируется из выходящего.
Состояние Sk системы характеризуется общим числом требований, находящихся на обслуживании и в очереди, равным k. Для рассматриваемой замкнутой системы, очевидно, k = 0, 1, 2, ... , N. При этом если система находится в состоянии Sk , то число объектов, находящихся в эксплуатации, равно (N - k).
Если
Система алгебраических уравнений, описывающих работу замкнутой СМО в стационарном режиме, выглядит следующим образом:
Решая данную систему, находим вероятность k-гo состояния:
Величина P0 определяется из условия нормирования
среднее число требований в очереди на обслуживание:
среднее число требований, находящихся в системе (на обслуживании и в очереди)
среднее число механиков (каналов), «простаивающих» из-за отсутствия работы
коэффициент простоя обслуживаемого объекта (машины) в очереди
коэффициент использования объектов (машин)
коэффициент простоя обслуживающих каналов (механиков)
среднее время ожидания обслуживания (время ожидания обслуживания в очереди)
Пример 4.6. Пусть для обслуживания десяти персональных компьютеров (ПК) выделено два инженера одинаковой производительности. Поток отказов (неисправностей) одного компьютера - пуассоновский с интенсивностью
Возможны следующие варианты организации обслуживания:
оба инженера обслуживают все десять компьютеров, так что при отказе ПК его обслуживает один из свободных инженеров, в этом случае R = 2, N = 10;
каждый из двух инженеров обслуживает по пять закрепленных за ним ПК. В этом случае R = 1, N = 5.
Необходимо выбрать наилучший вариант организации обслуживания ПК.
Решение
1. Вычислим параметр обслуживания
2. Приведенная интенсивность
3. Вычислим вероятностные характеристики СМО для двух вариантов организации обслуживания ПК.
Вариант 1
1. Определим вероятности состояний системы:
Учитывая, что
Откуда P0 = 0,065.
Тогда
Определим среднее число компьютеров в очереди на обслуживание:
Определим среднее число ПК, находящихся в системе (на обслуживании и в очереди):
Определим среднее число инженеров, простаивающих из-за отсутствия работы:
Коэффициент простоя персонального компьютера в очереди следующий:
Коэффициент использования компьютеров определяется по формуле:
Коэффициент простоя обслуживающих инженеров рассчитывается так:
Среднее время ожидания ПК обслуживания
Вариант 2
Определим вероятности состояний системы:
Откуда P0 = 0,199.
Тогда
Среднее число компьютеров в очереди на обслуживание таково:
Среднее число компьютеров, находящихся на обслуживании и в очереди рассчитывается так:
Среднее число инженеров, простаивающих из-за отсутствия работы:
Коэффициент простоя персонального компьютера в очереди:
Коэффициент использования компьютеров:
Коэффициент простоя обслуживающих инженеров:
Среднее время ожидания ПК обслуживания:
Сведем полученные результаты по двум вариантам в следующую таблицу:
Таким образом, в варианте 1 каждый компьютер стоит в очереди в ожидании начала его обслуживания приблизительно 0,142 части рабочего времени, что меньше этого показателя при варианте 2 организации работ. Далее в варианте 1 вероятность того, что ПК и любой момент времени будет работать выше, чем в варианте 2, и равна
Назад | Содержание | Далее
5. СТАТИСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ СИСТЕМ
5.1. Теоретические основы метода
Метод статистического моделирования (или метод Монте-Карло) - это способ исследования поведения вероятностных систем (экономических, технических и т. д.) в условиях, когда не известны в полной мере внутренние взаимодействия в этих системах.
Этот метод заключается в воспроизведении исследуемого физического процесса при помощи вероятностной математической модели и вычислении характеристик этого процесса. Одно такое воспроизведение функционирования системы называют реализацией или испытанием. После каждого испытания регистрируют совокупность параметров, характеризующих случайный исход реализации. Метод основан на многократных испытаниях построенной модели с последующей статистической обработкой полученных данных с целью определения числовых характеристик рассматриваемого процесса в виде статистических оценок его параметров. Процесс моделирования функционирования экономической системы сводится к машинной имитации изучаемого процесса, который как бы копируется на ЭВМ со всеми сопровождающими его случайностями.
Первые сведения о методе Монте-Карло были опубликованы в конце 40-х гг. Авторами метода являются американские математики Дж. Нейман и С. Улам. В нашей стране первые работы были опубликованы в 1955-1956 гг. В.В. Чавчанидзе, Ю.А. Шрейдером и B.C. Владимировым.
Основой метода статистического моделирования является закон больших чисел. Закон больших чисел в теории вероятностей доказывает для различных условий сходимость по вероятности средних значений результатов большого числа наблюдений к некоторым постоянным величинам.
Под законом больших чисел понимают ряд теорем. Например, одна из теорем Л.Л. Чебышева формулируется так: "При неограниченном увеличении числа независимых испытаний n среднее арифметическое свободных от систематических ошибок и равноточных результатов наблюдений
где
Теорема Бернулли формулируется так: "При неограниченном увеличений числа независимых испытаний в одних и тех же условиях частота
Согласно данной теореме, для получения вероятности какого-либо события, например вероятности состояний некоторой системы
Решение любой задачи методом статистического моделирования состоит в:
разработке и построении структурной схемы процесса, выявлении основных взаимосвязей;
формальном описании процесса;
моделировании случайных явлений (случайных событий, случайных величин, случайных функций), сопровождающих функционирование исследуемой системы;
моделировании (с использованием данных, полученных на предыдущем этапе) функционирования системы - воспроизведении процесса в соответствии с разработанной структурной схемой и формальным описанием;.
накоплении результатов моделирования, их статистической обработке, анализе и обобщении.
В отличие от описанных ранее математических моделей, результаты которых отражали устойчивое во времени поведение системы, результаты, получаемые при статистическом моделировании, подвержены экспериментальным ошибкам. Это означает, что любое утверждение, касающееся характеристик моделируемой системы, должно основываться на результатах соответствующих статистических проверок.
Экспериментальные ошибки при статистическом моделировании в значительной степени зависят от точности моделирования случайных явлений, сопровождающих функционирование исследуемой системы.
Известно, что при изучении вероятностных систем случайные явления могут интерпретироваться в виде случайных событий, случайных величин и случайных функций. Следовательно, моделирование случайных явлений сводится к моделированию случайных событий, случайных величин и случайных функций. Так как случайные события и случайные функции могут быть представлены через случайные величины, то и моделирование случайных событий и случайных функций производится с помощью случайных величин. В связи с этим рассмотрим сначала способы моделирования случайных величин.
Моделирование случайных величин
Для моделирования случайной величины необходимо знать ее закон распределения. Наиболее общим способом получения последовательности случайных чисел, распределенных по произвольному закону, является способ, в основе которого лежит их формирование из исходной последовательности случайных чисел, распределенных в интервале [0,1] по равномерному закону.
Равномерно распределенные в интервале [0,1] последовательности случайных чисел можно получить тремя способами:
использование таблиц случайных чисел;
применение генераторов случайных чисел;
метод псевдослучайных чисел.
При решении задачи без применения ЭВМ чаще всего используют таблицы случайных чисел. В таблицах случайных чисел случайные цифры имитируют значения дискретной случайной величины с равномерным распределением:
При составлении таких таблиц выполняется требование, чтобы каждая из этих цифр от 0; 1;...; 9 встречалась примерно одинаково часто и независимо от других с вероятностью pi = 0,1.
Самая большая из опубликованных таблиц случайных чисел содержит 1000 000 цифр. Таблицы случайных чисел составить не так просто. Они требуют тщательной проверки с помощью специальных статистических тестов.
При решении задач на ЭВМ для выработки случайных чисел, равномерно распределенных в интервале [0,1], могут применяться генераторы случайных чисел. Данные генераторы преобразуют результаты случайного физического процесса в двоичные числа. В качестве случайного физического процесса обычно используют собственные шумы (случайным образом меняющееся напряжение).
Недостатки данного способа получения случайных чисел следующие:
1. Трудно проверить качество вырабатываемых чисел.
2. Случайные числа не воспроизводимы (если их не запоминать), и, как следствие, нельзя повторить расчет на ЭВМ для исключения случайного сбоя.
Получение псевдослучайных чисел с равномерным законом распределения заключается в выработке псевдослучайных чисел. Псевдослучайные числа - это числа, полученные по какой-либо формуле и имитирующие значения случайной величины. Под словом "имитирующие" подразумевается, что эти числа удовлетворяют ряду тестов так, как если бы они были значениями этой случайной величины.
Первый алгоритм для получения псевдослучайных чисел предложил Дж. Нейман. Это так называемый метод середины квадратов, который заключается в следующем:
Алгоритм себя не оправдал: получилось больше, чем нужно, малых значений
Назовем достоинства метода псевдослучайных чисел.
1. На получение каждого случайного числа затрачивается несколько простых операций, так что скорость генерирования случайных чисел имеет тот же порядок, что и скорость работы ЭВМ.
2. Малый объем памяти ЭВМ для программирования.
3. Любое из чисел легко воспроизвести.
4. Качество генерируемых случайных чисел достаточно проверить один раз.
Подавляющее число расчетов по методу Монте-Карло осуществляется с использованием псевдослучайных чисел. От последовательности случайных чисел, равномерно распределенных в интервале [0,1], нетрудно перейти к последовательности случайных чисел с произвольным заданным законом распределения.
Назад | Содержание | Далее
5.2. Моделирование случайных событий с заданным законом распределения
5.2.1. Разыгрывание дискретной случайной величины
Пусть требуется разыграть дискретную случайную величину, т.е. получить последовательность ее возможных значений xi (i = 1,2,3,...n), зная закон распределения X:
Обозначим через R непрерывную случайную величину. Величина R распределена равномерно в интервале (0,1). Через rj (j = 1,2,...) обозначим возможные значения случайной величины R. Разобьем интервал 0 < R < 1 на оси 0r точками с координатами
Тогда получим:
Длина
Длина
.......................................................
Длина
Видно, что длина частичного интервала с индексом i равна вероятности Р с тем же индексом. Длина
Таким образом, при попадании случайного числа ri в интервал
Существует следующая теорема:
Если каждому случайному числу
Алгоритм разыгрывания дискретной случайной величины заданной законом распределения
1. Нужно разбить интервал (0,1) оси 0r на n частичных интервалов:
2. Выбрать (например, из таблицы случайных чисел, или в компьютере) случайное число rj.
Если rj попало в интервал
Пример 5.1.
Разыграть 8 значений дискретной случайной величины Х, закон распределения которой задан в виде таблицы:
Решение
1. Разобьем интервал (0,1) оси Оr точками с координатами 0,25; 0,25+0,16=0,41 на три частичных интервала;
2. Выпишем из таблицы случайных чисел 9 чисел, например 0,10; 0,37; 0,08; 0,99; 0,12; 0,66; 0,31; 0,85.
3. Случайное число r1 = 0,10 принадлежит первому частичному интервалу, поэтому разыгрываемая случайная величина приняла возможное значение x1 = 3. Случайное число r2= 0,37 принадлежит второму частичному интервалу, поэтому разыгрываемая величина приняла возможное значение x2 = 11. Аналогично получим остальные возможные значения дискретной случайной величины Х.
Итак: разыгранные возможные значения Х таковы: 3; 11; 3; 24; 3; 24; 11; 24.
Как видим, можно получить множество значений случайной величины Х с заданным законом распределения.
Назад | Содержание | Далее
5.2.2. Разыгрывание непрерывной случайной величины
Пусть требуется разыграть непрерывную случайную величину Х, т.е. получить последовательность ее возможных значений xi (i = 1,2,...). При этом функция распределения F(X) известна.
Существует следующая теорема.
Если ri - случайное число, то возможное значение xi разыгрываемой непрерывной случайной величины Х с известной функцией распределения F(X) соответствующее ri , является корнем уравнения
Алгоритм разыгрывания непрерывной случайной величины:
1. Необходимо выбрать случайное число ri.
2. Приравнять выбранное случайное число известной функции распределения F(X) и получить уравнение
3. Решить данное уравнение относительно xi. Полученное значение xi будет соответствовать одновременно и случайному числу ri. и заданному закону распределения F(X).
Пример5.2.
Разыграть 3 возможных значения непрерывной случайной величины Х, распределенной равномерно в интервале (2; 10).
Решение
Функция распределения величины Х имеет следующий вид:
По условию, a = 2, b = 10, следовательно,
В соответствии с алгоритмом разыгрывания непрерывной случайной величины приравняем F(X) выбранному случайному числу ri.. Получим отсюда:
Далее в соответствии с алгоритмом выберем три случайных числа, распределенных равномерно в интервале (0; 1). Например r1 = 0,11; r2 = 0,17; r3 = 0,66.
Подставим эти числа в уравнение (5.3).Получим соответствующие возможные значения х :
Пример 5.3
Непрерывная случайная величина Х распределена по показательному закону с известной функцией
Требуется найти формулу для разыгрывания возможных значений Х.
Решение
В соответствии с алгоритмом разыгрывания непрерывной случайной величины получим уравнение
Решим это уравнение относительно xi. Получим:
Случайное число ri находится в интервале (0, 1). Следовательно число (1- ri) также случайное и принадлежит интервалу (0, 1). То есть случайные величины R и 1 - R распределены одинаково, т.е. равномерно в одном и том же интервале (0, 1). Поэтому для отыскания значения xi можно воспользоваться более простой формулой:
Назад | Содержание | Далее
5.2.3. Разыгрывание случайной величины X, распределенной нормально
Известно, что если случайная величина R распределена равномерно в интервале (0, 1), то ее математическое ожидание М(R) = 1/2, а дисперсия D(R) = 1/12.
Составим сумму n независимых случайных величин Rj (j = 1,2,...n), которые распределены равномерно в интервале (0, 1). Получим
Пронормируем эту сумму. Для этого найдем сначала ее математическое ожидание и дисперсию. Известно, что математическое ожидание суммы случайных величин равно сумме математических ожиданий слагаемых. Сумма Ri содержит n слагаемых. Математическое ожидание каждого слагаемого равна 1/2. Следовательно математическое ожидание суммы равно:
Аналогично для дисперсии суммы Rj получим:
Отсюда среднее квадратическое отклонение суммы Rj:
Теперь пронормируем сумму Rj.
Для этого вычтем из суммы Rj математическое ожидание этой суммы и разделим на среднее квадратическое отклонение суммы Rj. Получим
На основании центральной предельной теоремы теории вероятностей при
При конечном n распределение можно рассматривать как приближенно нормальное. Например, при n = 12 получим достаточно точное для практики приближение
Таким образом, получаем, что для того чтобы разыграть возможное значение xi нормальной случайной величины Х с параметрами a = 0 и
Пример 5.4.
1. Разыграть 100 возможных значений случайной величины Х распределенной нормально с параметрами a = 0 и
2. Оценить параметры разыгранной случайной величины Х.
Решение
1. Выберем 12 случайных чисел распределенных равномерно в интервале (0, 1) из таблицы случайных чисел, либо из компьютера. Сложим эти числа и из суммы вычтем 6, в итоге получим:
Поступая аналогичным образом найдем остальные возможные значения
2. Выполнив необходимые расчеты найдем выборочную среднюю, которая является оценкой
Как видим, оценки удовлетворительны, т.е.
Если требуется разыграть значения нормальной ненормированной случайной величины с математическим ожиданием
которая получена из соотношения:
Таблица 5.1
Формулы для моделирования случайных величин
Назад | Содержание | Далее
5.3. Моделирование систем массового обслуживания с использованием метода Монте-Карло
В реальных условиях функционирования СМО имеются переходные режимы, а входящие и исходящие потоки требований являются далеко не простейшими. В этих условиях для оценки качества функционирования систем обслуживания широко используют метод статистических испытаний (метод Монте-Карло). Основой решения задачи исследования функционирования СМО в реальных условиях является статистическое моделирование входящего потока требований и процесса их обслуживания (исходящего потока требований).
Для решения задачи статистического моделирования функционирования СМО должны быть заданы следующие исходные данные:
описание СМО (тип, параметры, критерии эффективности работы системы);
параметры закона распределения периодичности поступлений требований в систему;
параметры закона распределения времени пребывания требования в очереди (для СМО с ожиданием);
параметры закона распределения времени обслуживания требований в системе.
Решение задачи статистического моделирования функционирования СМО складывается из следующих этапов.
1. Вырабатывают равномерно распределенное случайное число
2. Равномерно распределенные случайные числа преобразуют в величины с заданным законом распределения:
интервал времени между поступлениями требований в систему (
время ухода заявки из очереди (для СМО с ограниченной длиной очереди);
длительность времени обслуживания требования каналами (
3. Определяют моменты наступления событий:
поступление требования на обслуживание;
уход требования из очереди;
окончание обслуживания требования в каналах системы.
4. Моделируют функционирование СМО в целом и накапливают статистические данные о процессе обслуживания.
5. Устанавливают новый момент поступления требования в систему, и вычислительная процедура повторяется в соответствии с изложенным.
6. Определяют показатели качества функционирования СМО путем обработки результатов моделирования методами математической статистики.
Методику решения задачи рассмотрим на примере моделирования СМО с отказами.
Пусть система имеет два однотипных канала, работающих с отказами, причем моменты времени окончания обслуживания на первом канале обозначим через t1i , на втором канале - через t2i . Закон распределения интервала времени между смежными поступающими требованиями задан плотностью распределения f1(tT). Продолжительность обслуживания также является случайной величиной с плотностью распределения f1(to).
Процедура решения задачи будет выглядеть следующим образом:
1. Вырабатывают равномерно распределенное случайное число
2. Равномерно распределенное случайное число преобразуют в величины с заданным законом распределения, используя формулы табл. 5.1. Определяют реализацию случайного интервала времени (
3. Вычисляют момент поступления заявки на обслуживание:
4. Сравнивают моменты окончания обслуживания предшествующих заявок на первом t1(i-1) и втором t2(i-1) каналах.
5. Сравнивают момент поступления заявки ti c минимальным моментом окончания обслуживания (допустим, что t1(i-1) < 2(i-1)):
если [
если
6. При выполнении условия 5 б) определяют время обслуживания i-й заявки на первом канале
7. Вычисляют момент окончания обслуживания i-й заявки на первом канале
8. Устанавливают новый момент поступления заявки, и вычислительная процедура повторяется в соответствии с изложенным.
9. В ходе моделирования СМО накапливаются статистические данные о процессе обслуживания.
10. Определяют показатели качества функционирования системы путем обработки накопленных результатов моделирования методами математической статистики.
Назад | Содержание | Далее
5.4. Моделирование потоков отказов элементов сложных технических систем
Под сложной технической системой будем понимать систему, состоящую из элементов (два и более). Отказ одного из элементов системы приводит к отказу системы в целом.
Рассмотрим последовательность замен некоторого определенного элемента Z данного наименования. Эксплуатация каждого нового элемента начинается с момента окончания срока службы предыдущего. Первый элемент отрабатывает время
Случайная ситуация, сложившаяся в k-м опыте (ситуации) для элемента Z, показана на рис. 5.1.
Рис. 5.1. Временная эпюра случайной ситуации при k-м опыте в случае мгновенного восстановления отказавшей системы путем замены элемента
На рис. 5.1 видно, что система начинает свою работу в момент времени t = 0 и, отработав случайное время
Считают, что интервалы времени между отказами
Моменты отказов или восстановлений образуют в каждом k-м опыте (испытании) ряд чисел по следующему правилу:
или
где tik - время работы (наработка) элемента до i-го отказа в k–м опыте, час,
Числа t1k, t2k, ... ,tpk образуют случайный поток, который называется процессом восстановления. Этот процесс является различным для различных элементов и продолжается до окончания срока службы системы. Изучением таких процессов занимается теория восстановления.
Из большого количества различных процессов восстановления для исследования надежности элементов технической системы (как неремонтируемых, так и ремонтируемых) используют три типа процессов:
простой, при котором все функции распределения наработок до первого и между последующими отказами Fi (t) равны;
общий, при котором вид функции распределения наработки до первого отказа элемента, установленного в системе заводом-изготовителем, отличается от вида функций распределения наработок элементов при последующих заменах, т. е.
сложный, при котором все функции распределения Fi (t) различны.
Основной характеристикой процесса восстановления является функция восстановления
где Fn(t) и fn(t) - соответственно плотность и функция распределения наработки до n-го отказа.
В случае независимости наработок между отказами функции распределения Fn(t) наработок до n-го отказа находятся путем последовательного применения правила свертки для суммы двух случайных величин:
F1(t) = F(t) .
Следует отметить, что сложность получения аналитических выражений для
Расчет ведущей функции и параметра потока отказов этим методом в случае простого, общего или сложного процессов производится в следующем порядке.
По известным законам распределения наработок элементов с использованием формул преобразования (табл. 5.1) моделируются массивы случайных величин
Далее вычисляются значения наработок до i-го отказа tik по следующим формулам:
где i – номер отказа,
k – номер реализации при моделировании,
p – максимальное число отказов элемента, получаемое в k-й реализации случайного процесса
Затем полученные случайные величины наработок tik группируются по интервалам времени.
Номера интервалов, в которые попадают моменты возникновения отказов t1k, t2k, ... ,tik, ... , tpk определяются по формуле:
где
Параметр и ведущая функция потока отказов в j-м интервале времени определяется по следующим формулам:
где nij - число попаданий случайной наработки до i-го отказа tik в j-й интервал времени (
где h - максимальное число интервалов времени.
Пример 5.5. Законы распределения наработок элемента системы до первого и второго отказов и соответствующие параметры этих законов приведены в следующей таблице:
| № отказа | Закон распределения | Параметры закона | |
| a( | b | ||
| 1 | Вейбула | 1,4 | 45,8 |
| 2 | Экспоненциальный | 0,3 | - |
Определите номера временных интервалов, на которых про изойдут первый и второй отказы в ходе первого опыта (испытания) (
Решение
1. Выберем равномерно распределенное случайное число. До пустим
2. Вычислим случайные значения наработок на отказ элемента используя формулы табл. 5.1.
3. Определим номер временного интервала, на котором произойдут отказы
первый отказ
второй отказ
В ходе первой реализации элемент системы первый раз откажет на 21-м временном интервале, а второй отказ произойдет на 22-м временном интервале.
В ходе первой реализации элемент системы первый раз откажет на 21-м временном интервале, а второй отказ произойдет на 22-м временном интервале.
Назад | Содержание | Далее
ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ
Задача 5.1
Периодичность поступления заявок на обслуживание подчинена показательному закону распределения Средний интервал между поступлениями заявок в систему равен
Задача 5.2
Время обслуживания работника предприятия кассой бухгалтерии является случайной величиной, распределенной в соответствии с законом Вейбула. Среднее время обслуживания
Задача 5.3
При обработке экспериментальных данных было установлено, что время, расходуемое на станции технического обслуживания автомобилей для замены двигателя, распределено по нормальному закону, параметры которого
Задача 5.4
Время проверки приемки квартального отчета инспектором Налоговой службы (t) величина случайная, распределенная в соответствии с законом Вейбула. Среднее время проверки и приемки равно
Задача 5.5
Среднее число исправных станков в токарном цехе на заводе равно
Задача 5.6
Система имеет два элемента. Средняя периодичность первого элемента
Задача 5.7
Периодичность проверки предприятий налоговой инспекции - величина случайная (
Задача 5.8
Среднее число работающих машин на заводе
имеет распределение Вейбула.
Задача 5.9
После каждой проверки предприятия налоговой инспекцией вероятность появления необходимости аудиторской проверки Данного предприятия Р = 0,72. Смоделируйте шесть испытаний. Определите последовательность проведения различных проверок предприятия.
Назад | Содержание | Далее
6. СИСТЕМЫ УПРАВЛЕНИЯ ЗАПАСАМИ
6.1. Модели управления запасами
Возникновение теории управления запасами можно связать с работами Ф.Эджуорта и Ф. Харриса, появившимися в конце XIX – начале XX вв., в которых исследовалась простая оптимизационная модель определении экономичного размера партии поставки для складской системы с постоянным равномерным расходом и периодическим поступлением хранимого продукта.
Запасами называется любой ресурс на складе, который используется для удовлетворения будущих нужд. Примерами запасов могут служить полуфабрикаты, готовые изделия, материалы, различные товары, а также такие специфические товары, как денежная наличность, находящаяся в хранилище. Большинство организаций имеют примерно один тип системы планирования и контроля запасов. В банке используются методы контроля за количеством наличности, в больнице применяются методы контроля поставки различных медицинских препаратов.
Простейшая схема системы управления запасами выглядит следующим образом (рис.6.1.):
Рис. 6.1. Система управления запасами
Существуют причины, побуждающие организации создавать запасы:
1) дискретность поставок при непрерывном потреблении;
2) упущенная прибыль;
3) случайные колебания:
в спросе за период между поставками;
в объеме поставок;
в длительности интервала между поставками;
4) предполагаемые изменения конъюнктуры:
сезонность спроса;
сезонность производства;
ожидаемое повышение цен.
Имеются также причины, побуждающие предприятия стремиться к минимизации запасов на складе:
1) плата за физическое хранение запаса;
2) потери в количестве запаса;
3) моральный износ продукта.
Рассмотрим определяющие понятия теории управления запасами.
Издержки выполнения заказа (издержки заказа) - накладные расходы, связанные с реализацией заказа. В промышленности такими издержками являются затраты на подготовительно-заготовочные операции.
Издержки хранения – расходы, связанные с физическим содержанием товаров на складе, плюс возможные проценты на капитал, вложенный в запасы. Обычно они выражаются или в абсолютных единицах, или в процентах от закупочной цены и связываются с определенным промежутком времени.
Упущенная прибыль – издержки, связанные с неудовлетворительным спросом, возникающим в результате отсутствия продукта на складе.
Совокупные издержки за период представляют собой сумму издержек заказа, издержек хранения и упущенного дохода. Иногда к ним прибавляются издержки на покупку товаров.
Срок выполнения заказов – срок между заказом и его выполнением.
Точка восстановления – уровень запаса, при котором делается новый заказ.
Назад | Содержание | Далее
6.2. Краткая характеристика моделей управления запасами
1.1. Модель оптимального размера заказа.
Предпосылки:
1) темп спроса на товар известен и постоянен;
2) получение заказа мгновенно;
3) отсутствуют количественные скидки при закупке больших партий товара;
4) единственные меняющиеся параметры – издержки заказа и хранения;
5) исключается дефицит в случае своевременного заказа.
Исходные данные: темп спроса; издержки заказа и хранения.
Результат: оптимальный размер заказа; время между заказами и их количество за период.
1.2. Модель оптимального размера заказа в предположении, что получение заказа не мгновенно. Следовательно, нужно найти объем запасов, при котором необходимо делать новый заказ.
Исходные данные: темп спроса; издержки заказа и хранения; время выполнения заказа.
Результат: оптимальный размер заказа; время между заказами; точка восстановления запаса.
1.3. Модель оптимального размера заказа в предположении, что допускается дефицит продукта и связанная с ним упущенная прибыль. Необходимо найти точку восстановления.
Исходные данные: темп спроса; издержки заказа и хранения; упущенная прибыль.
Результат: оптимальный размер заказа; время между заказами; точка восстановления запаса.
1.4. Модель с учетом производства (в сочетании с условиями 1.1 – 1.3). Необходимо рассматривать уровень ежедневного производства и уровень ежедневного спроса.
Исходные данные: темп спроса; издержки заказа и хранения; упущенная прибыль; темп производства.
Результат: оптимальный уровень запасов (точка восстановления)
1.5. Модель с количественными скидками. Появляется возможность количественных скидок в зависимости от размера заказа. Рассматривается зависимость издержек хранения от цены товара. Оптимальный уровень заказа определяется исходя из условия минимизации общих издержек дл каждого вида скидок.
Модель 1.1 наиболее экономичного размера заказа. Заказ, пополняющий запасы, поступает как одна партия. Уровень запасов убывает с постоянной интенсивностью пока не достигнет нуля. В этой точке поступает заказ, размер которого равен Q, и уровень запасов восстанавливается до максимального значения. При этом оптимальным решением задачи будет тот размер заказа, при котором минимизируются общие издержки за период (рис. 6.2).
рис. 6.2
Пусть Q – размер заказа;
Т – протяженность периода планирования;
D – величина спроса за период планирования;
d – величина спроса в единицу времени;
K – издержки заказа;
H – удельные издержки за период;
h – удельные издержки хранения в единицу времени.
Тогда:
совокупные издержки заказа =
совокупные издержки хранения =
оптимальный размер заказа
оптимальное число заказов за период
время цикла (оптимальное время между заказам)
Модель 1.2. Введем предположение о том, что заказ может быть получен не мгновенно, а с течением времени. Тогда нам необходимо заранее делать заказ, чтобы в нужное время иметь достаточное количество товара на складе. Следовательно, нам необходимо найти тот уровень запасов, при котором делается новый заказ. Этот уровень называется точкой восстановления R. Пусть L – время выполнения заказа. Тогда R = величина спроса в единицу времени, умноженная на время выполнения заказа =
рис. 6.3
Пример 1. Андрей Удачливый является торговым агентом компании TOYOTA и занимается продажей последней модели этой марки автомобиля. Годовой спрос оценивается в 4000 ед. Цена каждого автомобиля равна 90 тыс. руб., а годовые издержки хранения составляют 10% от цены самого автомобиля. Андрей произвел анализ издержек заказа и понял, что средние издержки заказа составляют 25 тыс. руб. на заказ. Время выполнения заказа равно восьми дням. В течение этого времени ежедневный спрос на автомобили равен 20.
Чему равен оптимальный размер заказа?
Чему равна точка восстановления?
Каковы совокупные издержки?
Каково оптимальное количество заказов в год?
Каково оптимальное время между двумя заказами, ели предположить, что количество рабочих дней в году равно 200?
Исходные данные
величина спроса за год D = 4000;
издержки заказа K = 25;
издержки хранения h =
цена за единицу с = 90;
время выполнения заказа L
= 8;
ежедневный спрос d = 20;
число рабочих дней T = 200.
Решение
оптимальный размер заказа
точка восстановления R = 160 – 149 = 11;
число заказов за год
совокупные издержки = совокупные издержки заказа + совокупные издержки хранения С =
стоимость продаж = 360000;
число дней между заказами t = 7,45.
Модель 1.3. оптимального размера заказа в предположении, что допускается дефицит продукта и связанная с ним упущенная прибыль (рис. 6.4).
рис. 6.4
Пусть p – упущенная прибыль в единицу времени, возникающая в результате дефицита одной единицы продукта;
P – упущенная прибыль за период, возникающая в результате дефицита одной единицы продукта.
Тогда:
оптимальный размер заказа
максимальный размер запаса
максимальный дефицит
Модель 1.4 производства и распределения. В предыдущей модели мы допускали, что пополнение запаса происходит единовременно. Но в некоторых случаях, особенно в промышленном производстве, для комплектования партии товаров требуется значительное время и производство товаров для пополнения запасов происходит одновременно с удовлетворением спроса. Такой случай показан на рис. 6.5.
рис. 6.5
Спрос и производство являются частью цикла восстановления запасов.
Пусть u - уровень производства в единицу времени;
K – фиксированные издержки хранения.
Тогда:
совокупные издержки хранения =
средний уровень запасов = (максимальный уровень запасов)/2;
максимальный уровень запасов =
время выполнения заказа
издержки заказа =
оптимальный размер заказа
максимальный уровень запасов
Модель 1.5 с количественными скидками. Для увеличения объема продаж компании часто предлагают количественные скидки своим покупателям. Количественная скидка – сокращенная цена на товар в случае покупки большого количества этого товара. Типичные примеры количественных скидок приведена в табл. 6.1.
Таблица 6.1
| Варианты скидок | 1 | 2 | 3 |
| Количество, при котором делается скидка | от 0 до 999 | от 1000 до 1999 | от 2000 и выше |
| Размер скидки, % | 0 | 3 | 5 |
| Цена со скидкой | 5 | 4,8 | 4,75 |
Пусть I – доля издержек хранения в цене продукта с.
Тогда:
оптимальный размер заказа
Пример 2. Рассмотрим пример, объясняющий принцип принятия решения в условиях скидки. Магазин "Медвежонок" продает игрушечные гоночные машинки. Эта фирма имеет таблицу скидок на машинки в случае покупок их в определенном количестве (табл. 6.1). Издержки заказа составляют 49 тыс. руб. Годовой спрос на машинки равен 5000. годовые издержки хранения в отношении к цене составляют 20%, или 0,2. Необходимо найти размер заказа, минимизирующий общие издержки.
Решение.
Рассчитаем оптимальный размер заказа для каждого вида скидок, т.е. Q1*, Q2* и Q3*, и получим Q1* = 700; Q2* = 714; Q3*=718.
Так как Q1* - величина между 0 и 999, то ее можно оставить прежней. Q2* меньше количества, необходимого для получения скидки, следовательно, его значение необходимо принять равным 1000 единиц. Аналогично Q3* берем равным 2000 единиц. Получим Q1* = 700; Q2* = 1000; Q3* = 2000.
Далее необходимо рассчитать общие издержки для каждого размера заказа и вида скидок, а затем выбрать наименьшее значение.
Рассмотрим следующую таблицу.
| Варианты скидок | 1 | 2 | 3 |
| Цена | 5 | 4,8 | 4,75 |
| Размер заказа | 700 | 1000 | 2000 |
| Цена на товар за год | 25000 | 24000 | 23750 |
| Годовые издержки заказа | 350 | 245 | 122,5 |
| Годовые издержки хранения | 350 | 480 | 950 |
| Общие годовые издержки | 25700 | 24725 | 24822,5 |
Выберем тот размер заказа, который минимизирует общие годовые издержки. Из таблицы видно, что заказ в размере 1000 игрушечных гоночных машинок будет минимизировать совокупные издержки.
Назад | Содержание | Далее
