Исследование математических операций 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 max; а если W – расход, то W min.

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

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

Для иллюстрации принципов выбора показателя эффективности вернемся к рассмотренным ранее примерам:

1) План снабжения предприятия.

Показатель эффективности виден в цели. R
– число – стоимость перевозок, . При этом все ограничения должны быть выполнены.

2) Постройка участка магистрали.

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

3) Выборочный контроль продукции.

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

4) Военные действия.

Операция должна быть спланирована так, чтобы уничтожить вражеский объект. В качестве целевой функции – вероятность того, что произойдет событие А (уничтожение). Р(А)1.

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 году академик Л.В.Канторович и американец профессор Т.Купманс получили Нобелевскую премию по экономическим наукам за "вклад в разработку теории и оптимального использования ресурсов в экономике".

Оптимизационная задача

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

В самом общем виде задача математически записывается следующим образом:

;
, (2.1)

где 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.2)

(2.3)

(2.4)

. (2.5)

При этом система линейных уравнений (2.3) и неравенств (2.4), (2.5), определяющая допустимое множество решений задачи W
, называется системой ограничений задачи линейного программирования

, а линейная функция f
(Х
) называется целевой

функцией

или критерием оптимальности

.

В частном случае, если I
= Ø, то система (2.3) – (2.4) состоит только из линейных неравенств, а если I
= M
, то – из линейных уравнений.

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

величине этой переменной. Например, если, продавая j
-й товар в общем случае по цене 100 рублей, фирма будет делать скидку при определенном уровне закупки до уровня цены 95 рублей, то будет отсутствовать прямая пропорциональность между доходом фирмы и величиной переменной xj
. Т.е. в разных ситуациях одна
единица j
-го товара будет приносить разный
доход. Аддитивность
означает, что целевая функция и ограничения должны представлять собой сумму вкладов от различных переменных.

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

Допустимое решение
– это совокупность чисел (план) X = (x1
, x2
, ... , xn
), удовлетворяющих ограничениям задачи.

Оптимальное решение –
это план, при котором целевая функция принимает свое максимальное (минимальное) значение.

Если математическая модель задачи линейного программирования имеет вид:

; (2.6)

, , (2.7)

, , (2.8)

то говорят, что задача представлена в канонической форме

.

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

Правило приведения задачи линейного программирования к каноническому виду состоит в следующем
:

1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции;

2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1;

3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства;

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

Пример 2.1

. Приведение к канонической форме задачи линейного программирования:

Введем в каждое уравнение системы ограничений выравнивающие переменные x
4
, x
5
, x
6
. Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x
4
, x
6
вводятся в левую часть со знаком "+", а во второе уравнение вводится x
5
со знаком "-".

.

Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -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
.

По условию задачи машины работают заданное время Т
, поэто­му данное ограничение можно представить в следующем виде:

,
. (2.9)

Ограничение по заданному количеству продукции выглядит следующим образом:

, . (2.10)

Задача решается на минимум затрат на производство:

. (2.11)

Необходимо также учесть неотрицательность переменных
.

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

,
(2.12)

, (2.10)

(2.11)

, (2.12)

Пример 2.4.

Минимизация дисбаланса на линии сборки.

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

Из-за различий в составе технологического оборудования про­изводительность заводов по выпуску j
-го узла неодинакова и равна bij
. Каждый i
-й завод располагает максимальным суммарным ресурсом времени в течение недели для производства m
узлов, равного величине Ti
.

Задача состоит в максимизации выпуска изделий, что по существу эквивалентно минимизации дисбаланса, возникающего вследствие некомплектности поставки по одному или по нескольким видам узлов.

В данной задаче требуется определить еженедельные затраты времени (в часах) на производство j
-го узла на i
-м заводе, не превышающие в сумме временные ресурсы 1-го завода и обеспечивающие максимальный выпуск изделий.

Пусть xij
- недельный фонд времени (в часах), выделяемый на заводе для производства узла j
. Тогда объемы производства узла j
будут следующими:

,
. (2.15)

Так как в конечной сборке каждый из комплектующих узлов представлен в одном экземпляре, количество конечных изделии должно быть равно количеству комплектующих узлов, объем про­изводства которых минимален:

(2.16)

Условие рассматриваемой задачи устанавливает ограничение на фонд времени, которым располагает завод i
.

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

Максимизируем

(2.17)

,
(2.18)

для всех i
и j
.

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

(2.19)

Этому выражению с математической точки зрения эквивалентна следующая формулировка: максимизировать Z
= Y
при ограничениях

,
(2.20)

,
(2.21)

для всех i
и j
;
.

Пример 2.5.

Задача составления кормовой смеси, или задача диете.
.

Пусть крупная фирма (условно назовем ее «Суперрацион») име­ет возможность покупать m
различных видов сырья и приготавливать различные виды смесей (продуктов). Каждый вид сырья содер­жит разное количество питательных компонентов (ингредиентов). Лабораторией фирмы установлено, что продукция должна удов­летворять по крайней мере некоторым минимальным требованиям с точки зрения питательности (полезности). Перед руководством ширмы стоит задана определить количество каждого i
-го сырья, об­разующего смесь минимальной стоимости при соблюдении требо­ваний к общему расходу смеси и ее питательности.

Решение

Введем условные обозначения:

xi
- количество i
-го сырья в смеси;

m
- количество видов сырья;

n
- количество ингредиентов в сырье;

aij
- количество ингредиента j
, содержащегося в единице i
-го вида сырья;

bj
- минимальное количество ингредиента j
, содержащегося в единице смеси;

ci
- стоимость единицы сырья i
;

q
- минимальный общий вес смеси, используемый фирмой,

Задача может быть представлена в виде

(2.22)

при следующих ограничениях:

на общий расход смеси:

; (2.23)

на питательность смеси:

,
(2.24)

на неотрицательность переменных:

,
(2.25)

Пример 2.6.

Задача составления жидких смесей.

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

Представим себе фирму, торгующую различного рода химическими продуктами, каждый из которых является смесью нескольких компонентов. Предположим, что эта фирма планирует изготовление смесей m
-видов. Обозначим подлежащее определению количе­ство литров i
-
го химического компонента, используемого для получения j
-го продукта через xij
. Будем предполагать, что

, , .

Первая группа ограничений относится к объемам потребляе­мых химических компонентов:

,
(2.26)

где Si
- объем i
-го химического компонента, которым располагает фирма в начале планируемого периода.

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

,
(2.27)

где Di
- минимальный спрос на продукцию у в течение планируемого периода.

Третья группа ограничений связана с технологическими особенностями, которые необходимо принимать во внимание при приготовлении смеси например, простое ограничение, определяемое некоторыми минимально допустимыми значениями, отношения между объемами двух химических компонентов в процессе получе­ния продукта j
:

или
,

где r
- некоторая заданная константа.

Обозначив через Рij
доход с единицы продукции хij
запишем целевую функцию:

. (2.28)

Пример 2.7.

Задача о раскрое или о минимизации обрезков.

Данная задача состоит В разработке таких технологических планов раскроя, при которых получается необходимый комплекс заготовок, а отходы (по длине, площади, объему, массе или стоимости) сводятся к минимуму.

Например, продукция бумажной фирмы выпускается в виде бумажных рулонов стандартной ширины L
. По специальным заказам потребителей фирма поставляет рулоны других размеров, для этого производится разрезание стандартных рулонов. Типичные заказы на рулоны нестандартных размеров могут включать т
видов шириной Hi
(). Известна потребность в нестандартных рулонах каждого вида, она равна bi
. Возможны n
различных вариантов построения технологической карты раскроя рулонов стандартной ширины L
на рулоны длиной Hi
.

Обозначим через aij
количество рулонов i
-го вида, получаемых при раскрое единицы стандартного рулона по j
-му варианту. При каждом варианте раскроя на каждый стандартный рулон возможны потери, равные Pi
. К потерям следует относить также избыточные рулоны нестандартной длины li
, получаемые при различных вариантах раскроя yij
,
.

В качестве переменных следует идентифицировать количество стандартных рулонов, которые должны быть разрезаны при j
-м варианте раскроя. Определим переменную следующим образом: xj
- количество стандартных рулонов, разрезаемых по варианту j
, .

Целевая функция - минимум отходов при раскрое

. (2.29)

Ограничение на удовлетворение спроса потребителя

, , . (2.30)

Пример 2.8.

Транспортная задача.

Имеется три поставщика и четыре потребителя однородной продукции. Известны затраты на перевозку груза от каждого поставщика каждому потребителю. Обозначим их cij
,
,
. Запасы грузов у поставщиков равны ai
,
. Известны потребности каждого потребителя bi
,
. Будем считать, что суммарные потребности равны суммарным запасам:

.

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

Введем переменные хij
- количество груза, перевозимого от i
-го поставщика j
-му потребителю. Ограничения задачи выглядят следующим образом:

 потребности всех потребителей должны быть удовлетворены пол­ностью:

(2.31)

или в общем виде:

,

 груз от поставщика должен быть вывезен полностью:

(2.32)

или в общем виде:

,

 условие неотрицательности переменных:

, ,

Целевая функция - минимизировать суммарные затраты на пе­ревозку:

(2.33)

Количество поставщиков и потребителей в общем случае может быть произвольным.

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

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

2. Линейная функция может стремиться как к максимуму, так и к минимуму.

3. Переменные в задачах всегда неотрицательны.

Напомним, что от любой из вышеперечисленных задач можно перейти к канонической (основной) задаче линейного программи­рования.

Назад | Содержание | Далее

2.3. Графическое решение задачи линейного программирования

Графически способ решения задач линейного программирования целесообразно использовать для:

 решения задач с двумя переменными, когда ограничения выражены неравенствами;

 решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных.

Запишем задачу линейного программирования с двумя переменными:

 целевая функция:

; (2.34)

 ограничения:

; (2.35)

. (2.36)

Каждое из неравенств (2.35) – (2.36) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми ; (
; х1
= 0; х2
= 0. В том случае, если система неравенств (2.35) – (2.36) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых значений является выпуклое множество, которое называется многоугольником

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

Областью допустимых решений

системы неравенств (2.35) – (2.36) может быть:

 выпуклый многоугольник;

 выпуклая многоугольная неограниченная область;

 пустая область;

 луч;

 отрезок;

 единственная точка.

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

Вектор
с координатами с2
и с1
, перпендикулярный к этим прямым, указывает направление наискорейшего возрастания Z
, а противоположный вектор – направление убывания 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). Для этого в системе координат X1
0X2
на плоскости изобразим граничные прямые:

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 проводим прямую, перпендикулярную ему. Построенную прямую Z
= 0 перемещаем параллельно самой себе в направлении вектора
. Из рис. следует, что по отношению к многоугольнику решений опорной эта прямая становится в точке C
, где функция принимает максимальное значение. Точка С
лежит на пересечении прямых L1
и L3
. Для определения ее координат решим систему уравнений:

Оптимальный план задачи х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)
, которое представля­ет собой ограничение на недефицитный ресурс - сырье В
. И в этом случае правую часть - запасы сырья В
- можно уменьшать до тех пор, пока прямая L2
не достигнет точки С
. При этом правая часть ограничения (2) станет равной , что позволяет записать это ограничение в виде:
. Этот результат показывает, что ранее полученное оптимальное решение не измените, если суточный запас ресурса В
уменьшить на 3 ед.

Результаты проведенного анализа можно свести в следующую таблицу:

Ресурс	Тип ресурса	Максимальное изменение запаса ресурса, ед.	Максимальное увеличение дохода от изменения ресурса, у.д.е.
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, откуда
. На рис 2.5 видно, что значение c1
можно увеличивать беспредельно, так как прямая Z
при c2
= 4 и не совпадает с прямой L3
(отрезок DC
) и, следовательно, точка С
при всех значениях коэффициента будет единствен­ной оптимальной.

Интервал изменения c1
, в котором точка С
по-прежнему оста­ется единственной оптимальной точкой, определяется неравенством . При c1
= 8/3 оптимальными угловыми точками будут как точка С
, так и точка В
. Как только коэффициент c1
становится меньше 8/3 , оптимум смещается в точку В
.

Можно заметить, что, как только коэффициент 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
уменьшалось, т. е.
. Для перехода к новому базису из старого базиса уда­ляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый ба­зис Б
(
k
)
, для которого есть искомый минимум для линейной функции Z
, а соответствующее базисное решение является опти­мальным либо выясняется, что задача не имеет решения.

Назад | Содержание | Далее

2.5.2. Алгоритм симплекс-метода

Рассмотрим систему ограничений и линейную форму вида:

; (2.37)

; (2.38)

, . (2.39)

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

x1
, x2
, ... , xr
- базисные переменные;

xr
+1
, xr
+2
, ... , xn
- свободные переменные.

; (2.40)

. (2.41)

По последней системе ограничений и целевой функции 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
, . Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого i
-го пункта отправления (от поставщика) в каждый j
-ый пункт назначения (до потребителя) xij
с минимальными транспортными издержками.

В общем виде исходные данные представлены в табл. 3.1. Строки транспортной таблицы соответствуют пунктам отправления (в последней клетке каждой строки указан объем запаса продукта ai
), а столбцы — пунктам назначения (послед­няя клетка каждого столбца содержит значение потребности bj
). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о пе­ревозке из i
-го пункта в j
-й: в правом верхнем углу находится цена перевозки единицы продукта, а в левом нижнем — значе­ние объема перевозимого груза для данных пунктов.

Таблица 3.1

Исходные данные

Транспортная задача называется закрытой, если суммарный объем отправляемых грузов .
равен суммарному объему потребности в этих грузах по пунктам назначения
:

(3.1)

Если такого равенства нет (потребности выше запасов или наоборот), запасу называют открытой, т.е.:

(3.2)

Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнении.

Все грузы из i
-х пунктов должны быть отправлены, т.е.:

, (3.3)

Все j
-е пункты (потребители) должны быть обеспечены грузами в плановом объеме:

,
(3.4)

Суммарные объемы отправления должны равняться суммарным объемам назначения (3.1). Должно выполняться условие неотрицательности переменных:
,
, . Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели):

(3.5)

Вместо матрицы стоимостей перевозок (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
остается измененный запас . В оставшейся новой таблице с тремя строками A1
,A
2
,A
3
и четырьмя столбцами B1
,B
2
,B
3
,B
4
; северо-западным углом будет клетка для неизвестного x12
. Первая база с запасом
может полностью удовлетворить потребность второго заказчика B2

. Полагаем x12
= 110, вписываем это значе­ние в клетку x12
и исключаем из рассмотрения второй столбец. На базе A1
остается новый остаток (запас) . В оставшейся новой таблице с тремя строками A1
,A
2
,A
3
и тремя столбцами B3
,B
4
,B
5
северо-западным углом будет клетка для неизвестного x13
. Теперь третий заказчик B3
может принять весь запас с базы A1

. Полагаем x13
= 20, вписываем это значение в клетку x13
и исключаем из рассмотрения первую строку. У заказ­чика из B3
осталась еще не удовлетворенной потребность .

Теперь переходим к заполнению клетки для неизвестного x23
и т.д.

Через шесть шагов у нас останется одна база A3
с запасом груза (остатком от предыдущего шага) и один пункт B5
с потреб­ностью b5
=200 . Соответственно этому имеется одна свободная клетка, которую и заполняем, положив x35
=200. План составлен. Базис образован неизвестными x11
,x
12
,x
13
,x
23
,x
24
,x
34
,x
35
. Правиль­ность составленного плана легко проверить, подсчитав суммы чисел, стоящих в заполненных клетках по строкам и столбцам.

Общий объем перевозок в тонно-километрах для этого плана составит

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

Пример

В данном случае заполнение таблицы начинается с клетки для неизвест­ного x32
, для которого мы имеем значение c32
= 10, наименьше из всех значений cij
. Эта клетка находится на пересечении третьей строки и второго столбца, соответствующим третьей базе A3
и вто­рому заказчику B2
. Третья база A3
может полностью удовлетворить потребность второго заказчика B2
(a3
=250, b2
=110, a3
> b2
) . Пола­гая x32
= 110, вписываем это значение в клетку x32
и исключаем из рассмотрения второй столбец. На базе A3
остается изменённый запас . В оставшейся новой таблице с тремя строками A1
,A
2
,A
3
и четырьмя столбцами B1
,B
3
,B
4
,B
5
клеткой с наименьшим значе­нием cij
клетка, где c34
=11. Заполняем описанным выше способом эту клетку и аналогично заполняем следующие клетки. В резуль­тате оказываются заполненными (в приведенной последовательности) следующие клетки:

На пятом шаге клеток с наименьшими значениями cij
оказалось две (c11
=c15
=70) . Мы заполнили клетку для x15
, положив x15
= 180. Можно было выбрать для заполнения другую клетку, положив x11
= 170, что приведет в результате к другому опорному плану. Общий объем перевозок в тонно-километрах для этого плана составит

Замечание

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

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

Назад | Содержание | Далее

3.3. Понятие потенциала и цикла

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

Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям:

1. Одно из неизвестных последовательности свободное, а все остальные – базисные.

2. Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.

3. Три последовательных неизвестных не могут находиться в одном столбце или в одной строке.

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

Второе условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.

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

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

Так, например, в таблице перевозок, составленной по диагональному методу при решения задачи из предыдущего пункта, неизвестному x21
соответствует цикл x21
,x
23
,x
13
,x
11
,x
21
и т.д.

Пусть теперь мы имеем некоторую свободную клетку с соответствующим ей циклом. Если мы изменим значение свободного неизвестного, увеличив его на некоторое число x
, то, переходя последовательно от одной вершины цикла к другой, мы должны будем в силу неизменности сумм по строкам и по столбцам поочередно уменьшать и увеличивать значения неизвестных в цикле на то же число x
. Например, в указанном выше цикле для свободного неизвестного x21
получим:

старые значения: x21
= 0, x
23
= 80, x13
= 20,x
11
= 170, x
21
= 0;

новые значения:

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

Замечание.
Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак "+", т. е. тот знак, который ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, в каком направлении обходится цикл при “означивании” вершин.

Если в качестве x
выбрать наименьшее из чисел, стоящих в вершинах, снабженных знаком "–", то, по крайней мере, одно из прежних базисных неизвестных примет значение нуль, и мы можем перевести его в число свободных неизвестных, сделав вместо него базисным то неизвестное, которое было свободным.

Так, например, в рассмотренном выше цикле имеем отрицательные вершины x21
и x11
; следовательно, выбрав х = min {80; 170} = 80 , мы получаем:

старые значения: x21
= 0, x
23
= 80, x13
= 20,x
11
= 170, x
21
= 0;

новые значения:

т. е. вместо прежнего базисного решения получаем новое базисное решение:

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

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

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

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

Заметим, что неизвестные, не входящие в цикл, этим преобразованием не затрагиваются, их значения остаются неизменными и каж­дое из них остается либо в группе базисных, либо в группе свобод­ных неизвестных, как и до пересчета.

Выясним теперь, как пересчет по циклу влияет на общий объем затрат на перевозки и при каком условии эти затраты становятся меньше.

Пусть xpq
– некоторое свободное неизвестное, для которого мы построили цикл и осуществили пересчет по циклу с некоторым числом x
.
Если вершине цикла, находящейся в i-й строке и j-м столбце таблицы перевозок, приписан знак "+", то значение неизвестного xij
,
находящегося в этой вершине, увеличивается на x
,
что в свою очередь вызывает увеличение затрат на cij
x, где cij
– тариф, соответствующий этой клетке; если же указанной вершине приписан знак “–”, то значение неизвестного xij
уменьшается на x
, что вызывает уменьшение затрат на cij
x.

Сложим тарифы, соответствующие положительным вершинам цикла, и вычтем из этой суммы сумму тарифов, соответствующих отрицательным вершинам цикла; полученную разность Spq
назовем алгебраической суммой тарифов
для данного свободного неизвестного xpq
. Подсчет алгебраической суммы тарифов можно истолковать и так: припишем тарифам те же знаки, которые приписаны соответствующим вершинам цикла, тогда алгебраическая сумма тарифов равна сумме таких тарифов со знаком (“относительных тарифов”).

Теперь, очевидно, мы можем, заключить, что в целом при пере­счете но циклу, соответствующему свободному неизвестному xpq
общий объем затрат на перевозки изменится на произведение алгеб­раической суммы тарифов на x
, т. е. на величину Spq
x . Следовательно, если алгебраическая сумма тарифов для некоторого свобод­ного неизвестного xpq
отрицательна (Spq
< 0), то пересчет по циклу, соответствующему этому неизвестному, приводит к уменьшению общей суммы затрат на реализацию плана перевозок. Если же алгебраическая сумма тарифов положительна (Spq
> 0), то пересчет по соответствующему циклу приведет к увеличению общей суммы затрат. И, наконец, если алгебраическая сумма тарифов равна нулю (Spq
= 0), то пересчет по соответствующему циклу не изменит общую сумму затрат (два различных базисных плана требуют одинаковых затрат на их реализацию).

Так, например, для цикла x21
,x
23
,x
13
,x
11
,x
21
в рассмотренной задаче алгебраическая сумма тарифов

.

Значит, пересчет по этому циклу снижает расходы. И действитель­но, осуществив такой пересчет, мы получаем план, по которому объем перевозок в тонно-километрах составляет

тогда как по исходному плану он составил 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
,x
23
,x
13
,x
11
,x
21
в рассмотренной выше задаче имеем

.

Для базисных клеток сумма потенциалов строки и столбца, в которых находится эта клетка, равна тарифу, соответствующему этой клетке; если же клетка для неизвестного xpq
свободная, то сумму потенциалов

(3.7)

называют косвенным тарифом
этой клетки. Следовательно, алгеб­раическая сумма тарифов для свободной клетки xpq
равна разности ее настоящего (“истинного”) и косвенного тарифов:

(3.8)

Из (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. Ряд транспортных маршрутов, по которым необходимо доставить грузы, имеют ограничения по пропускной способности. Если, например, по маршруту Ai
Bj
можно провести не более q
единиц груза, то Bj
-й столбец матрицы разбивается на два столбца -
и
. В первом столбце спрос принимается равным разности между действительным спросом
и ограничением q
:
, во втором – равным ограничению q
, т.е. . Затраты cij
в обоих столбцах одинаковы и равны данным, но в первом столбце
, в клетке, соответствующей ограничению i
, вместо истинного тарифа cij
ставится искусственно завышенный тариф M
(клетка блокируется). Затем задача решается обычным способом.

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

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

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

7. необходимо в одно время распределить груз различного рода по потребителям. Задачи данного типа называются многопродуктовыми транспортными задачами. В этих задачах поставщики m
родов грузов разбиваются на m
условных поставщиков, а потребители n
родов грузов разбиваются на n
условных потребителей. С учетом этой разбивки составляют полную транспортную таблицу. При этом заметим, что некоторые маршруты Ai
Bj
должны быть блокированы (закрыты), поскольку в данной постановке задачи грузы разного рода не могут заменять друг друга. Этим маршрутам Ai
Bj
должна соответствовать очень высокая стоимость перевозки. Многопродуктовую задачу не всегда обязательно описывать одной моделью. Например, если поставки грузов различного рода независимы, тот задачу можно представить в виде комплекса транспортных задач по каждому роду груза. Однако, если между грузами Различного рода существует связь (например, одни из грузов можно заменить другими), то в общем случае исходную модель (задачу) не удается разбить на комплекс простых транспортных задач.

Рассмотрим примеры задач транспортного типа.

Пример 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 д.е. соответственно.

Составить оптимальный план перевозок.

Решение

Каждого поставщика условно разбиваем на две части согласно двум видам зерна (
и
; и ), аналогично потребителей разбиваем на три части (пшеница III класса, IV класса и любой класс): , и
, а также
, и . Потребности превышают запасы, поэтому вводим фиктивного поставщика A3
. Часть клеток в таблице запираем большими числами М
; например, в клетке (1; 2) стоит большое число. Это значит, что поставщик не может удовлетворить потребителя
пшеницей IV класса за счет имеющейся пшеницы III класса.

С учетом сделанных замечаний составим первую таблицу (табл. 3.6).

Таблица 3.6

Исходные данные

Перевозки от фиктивного поставщика не производятся, поэтому . Величина М
намного больше cij
. Применяя метод потенциалов, в итоге получим таблицу с оптимальным решением (табл. 3.7).

Таблица 3.7

Оптимальное решение

Анализ решения

. Первый поставщик поставит на первый элеватор (B1
) пшеницу III класса ( x
12
= 2); пшеницу IV класса (x
22
= 3), а также пшеницу любого класса (III или IV) (x
13
= 1 ; x
23
= 1).

Второй поставщик (A2
) поставит на второй элеватор (B2
) пшеницу III класса (x
31
= 1), пшеницу IV класса (x
45
= 1,5) и частично любую пшеницу (x
36
= 4; x
46
= 0,5). Потребность элеватора в любой пшенице не удовлетворена на 1,25 тыс. тонн (x
56
= 1,25). Минимальные затраты на перевозку составили: Z
min
= 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
) влечет за собой дополнительные расходы в виде штрафа. Например,

c
11
= 4 д.е.

c
24
= 4 + (0,5 + 0,5) = 5 д.е.

c
41
= 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 т, поэтому необходимо в таблицу ввести фиктивный тираж B
5
с нулевыми затратами. В связи с тем, что мы составляем модель относительно бумаги, а матрица 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
A 1	3	2	4	50
A 2	5	4	5	75
A 3	1	6	7	30
Потребность, шт.	60	40	70

Найдите оптимальное решение.

Для задач 3.14 – 3.25 дано следующее условие.

Имеются три пункта поставки однородного груза - A
1
; A
2
; A
3
и пять пунктов потребления этого груза B
1
; B
2
; B
3
; B
4
; B
5
. В пунктах A
1
; A
2
; A
3
находится груз a
1
; a
2
; a
3
соответственно. Груз необходимо доставить в пункты B
1
; B
2
; B
3
; B
4
; B
5
в количестве b
1
; b
2
; b
3
; b
4
; b
5
соответственно. Расстояния между пунктами в км заданы следующей матрицей:

.

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

Задача 3.14

= (200; 450; 250);

= (100; 125; 325; 250; 100);

.

Задача 3.15

= (250; 200; 200);

= (120; 130; 100; 160; 110);

.

Задача 3.16

= (300; 250; 200);

= (210; 170; 220; 150; 200);

.

Задача 3.17

= (350; 200; 300);

= (170; 140; 200; 195; 145);

.

Задача 3.18

= (230; 250; 170);

= (140; 90; 160; 110; 150);

.

Задача 3.19

= (200; 350; 300);

= (270; 130; 190; 150; 110);

.

Задача 3.20

= (150; 150; 200);

= (110; 70; 130; 110; 90);

.

Задача 3.21

= (330; 270; 350);

= (220; 170; 220; 150; 200);

.

Задача 3.22

= (150; 200; 100);

= (90; 150; 75; 60; 75);

.

Задача 3.23

= (300; 300; 250);

= (150; 140; 115; 225; 220);

.

Задача 3.24

= (300; 230; 320);

= (190; 150; 130; 180; 200);

Задача 3.25

= (200; 300; 250);

= (120; 140; 160; 180; 150);

.

Назад | Содержание | Далее

4. МОДЕЛИРОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ

4.1. Компоненты и классификация моделей массового обслуживания

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

С позиции моделирования процесса массового обслуживания ситуации, когда образуются очереди заявок (требований) на обслу­живание, возникают следующим образом. Поступив в обслуживаю­щую систему, требование присоединяется к очереди других (ранее поступивших) требований. Канал обслуживания выбирает требова­ние из находящихся в очереди, с тем чтобы приступить к его об­служиванию. После завершения процедуры обслуживания очеред­ного требования канал обслуживания приступает к обслуживанию следующего требования, если таковое имеется в блоке ожидания.

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

Примерами систем массового обслуживания могут служить:

1. посты технического обслуживания автомобилей;

2. посты ремонта автомобилей;

3. персональные компьютеры, обслуживающие поступающие заяв­ки или требования на решение тех или иных задач;

4. станции технического обслуживания автомобилей;

5. аудиторские фирмы;

6. отделы налоговых инспекций, занимающиеся приемкой и про­веркой текущей отчетности предприятий;

7. телефонные станции и т. д.

Основными компонентами системы массового обслуживания лю­бого вида являются:

 входной поток поступающих требований или заявок на обслужи­вание;

 дисциплина очереди;

 механизм обслуживания.

Входной поток требований

. Для описания входного потока тре­буется задать вероятностный закон, определяющий последователь­ность моментов поступления требований на обслуживание и ука­зать количество таких требований в каждом очередном поступле­нии. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (требования поступают группами в систему). В последнем случае обычно речь идет о системе обслуживания с параллельно-групповым обслужи­ванием.

Дисциплина очереди

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

 первым пришел — первый обслуживаешься;

 пришел последним — обслуживаешься первым;

 случайный отбор заявок;

 отбор заявок по критерию приоритетности;

 ограничение времени ожидания момента наступления обслужи­вания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая дли­на очереди»).

Механизм обслуживания

определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся: продол­жительность процедуры обслуживания и количество требований, удовлетворяемых в результате выполнения каждой такой процеду­ры. Для аналитического описания характеристик процедуры обслу­живания оперируют понятием «вероятностное распределение вре­мени обслуживания требований».

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

Структура обслуживающей системы определяется количеством и взаимным расположением каналов обслуживания (механизмов, приборов и т. п.). Прежде всего следует подчеркнуть, что система обслуживания может иметь не один канал обслуживания, а не­сколько; система такого рода способна обслуживать одновременно несколько требований. В этом случае все каналы обслуживания предлагают одни и те же услуги, и, следовательно, можно утверж­дать, что имеет место параллельное обслуживание.

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

Предметом теории массового обслуживания

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

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

Независимо от характера процесса, протекающего в системе мас­сового обслуживания, различают два основных вида СМО:

 системы с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и сразу же по­кидает очередь;

 системы с ожиданием (очередью), в которых заявка, поступив­шая в момент, когда все каналы обслуживания заняты, стано­вится в очередь и ждет, пока не освободится один из каналов. Системы массового обслуживания с ожиданием делятся на си­стемы с ограниченным ожиданием и системы с неограниченным ожиданием.

В системах с ограниченным ожиданием может ограничиваться:

 длина очереди;

 время пребывания в очереди.

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

Все системы массового обслуживания различают по числу каналов обслуживания:

 одноканальные системы;

 многоканальные системы.

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

4.2. Определение характеристик систем массового обслуживания

4.2.1. Одноканальная модель с пуассоновским входным потоком с экспоненциальным распределением длительности обслуживания

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

, (4.1)

где - интенсивность поступления заявок в систему

Плотность распределения длительностей обслуживания:

, (4.2)

где - интенсивность обслуживания

Потоки заявок и обслуживании простейшие.

Пусть система работает с отказами

. Необходимо определить абсолютную и относительную пропускную способность системы.

Представим данную систему массового обслуживания в виде графа (рис. 4.1), у которого имеются два состояния:

S0
- канал свободен (ожидание);

S1
- канал занят (идет обслуживание заявки).

Рис. 4.1. Граф состояний одноканальной СМО с отказами

Обозначим вероятности состояний: P0
(t) - вероятность состояния «канал свободен»; P1
(t) - вероятность состояния «канал занят». По размеченному графу состояний (рис. 4.1) составим систему дифференциальных уравнений Колмогорова для вероятностей состояний:

(4.3)

Система линейных дифференциальных уравнений (4.3) имеет решение с учетом нормировочного условия P0
(t) + P1
(t) = 1 . Реше­ние данной системы называется неустановившимся, поскольку оно непосредственно зависит от t
и выглядит следующим образом:

, (4.4)

P1
(t) = 1 - P0
(t) = 1 . (4.5)

Нетрудно убедиться, что для одноканальной СМО с отказами вероятность P0
(t) есть не что иное, как относительная пропускная способность системы q
.

Действительно, P0
- вероятность того, что в момент t
канал сво­боден и заявка, пришедшая к моменту t
, будет обслужена, а следо­вательно, для данного момента времени t
среднее отношение числа обслуженных заявок к числу поступивших также равно P0
(t), т. е.

q = P0
(t), (4.6)

По истечении большого интервала времени (при ) дости­гается стационарный (установившийся) режим:

, (4.7)

Зная относительную пропускную способность, легко найти аб­солютную. Абсолютная пропускная способность (А) - среднее чис­ло заявок, которое может обслужить система массового обслужива­ния в единицу времени:

. (4.8)

Вероятность отказа в обслуживании заявки будет равна вероят­ности состояния «канал занят»:

. (4.9)

Данная величина Pотк
может быть интерпретирована как сред­няя доля необслуженных заявок среди поданных.

Пример 4.1.

Пусть одноканальная СМО с отказами представля­ет собой один пост ежедневного обслуживания (ЕО) для мойки ав­томобилей. Заявка - автомобиль, прибывший в момент, когда пост занят, - получает отказ в обслуживании. Интенсивность потока ав­томобилей
= 1,0 (автомобиль в час). Средняя продолжительность обслуживания - 1,8 часа. Поток автомобилей и поток обслужива­нии являются простейшими.

Требуется определить в установившемся режиме предельные значения:

 относительной пропускной способности 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)

где
; n – номер состояния.

Решение приведенной выше системы уравнений (4.10) для на­шей модели СМО имеет вид

(4.11)

(4.12)

Тогда

Следует отметить, что выполнение условия стационарности
для данной СМО не обязательно, поскольку число допускаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди (которая не может превы­шать N
- 1), а не соотношением между интенсивностями входного потока, т. е. не отношением
.

Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N
- 1):

 вероятность отказа в обслуживании заявки:

(4.13)

 относительная пропускная способность системы:

(4.14)

 абсолютная пропускная способность:

(4.15)

 среднее число находящихся в системе заявок:

(4.16)

 среднее время пребывания заявки в системе:

(4.17)

 средняя продолжительность пребывания клиента (заявки) в очереди:

(4.18)

 среднее число заявок (клиентов) в очереди (длина очереди):

(4.19)

Рассмотрим пример одноканальной СМО с ожиданием

.

Пример 4.2.

Специализированный пост диагностики представ­ляет собой одноканальную СМО. Число стоянок для автомоби­лей, ожидающих проведения диагностики, ограниченно и равно 3 [(N
- 1) = 3]. Если все стоянки заняты, т. е. в очереди уже нахо­дится три автомобиля, то очередной автомобиль, прибывший на диагностику, в очередь на обслуживание не становится. Поток ав­томобилей, прибывающих на диагностику, распределен по закону Пуассона и имеет интенсивность
= 0,85 (автомобиля в час). Вре­мя диагностики автомобиля распределено по показательному зако­ну и в среднем равно 1,05 час.

Требуется определить вероятностные характеристики поста ди­агностики, работающего в стационарном режиме.

Решение

1. Параметр потока обслуживании автомобилей:

2. Приведенная интенсивность потока автомобилей определя­ется как отношение интенсивностей и
, т. е.

.

3. Вычислим финальные вероятности системы:

4. Вероятность отказа в обслуживании автомобиля:

.

5. Относительная пропускная способность поста диагностики:

.

6. Абсолютная пропускная способность поста диагностики

(автомобиля в час)

7. Среднее число автомобилей, находящихся на обслуживании и в очереди (т.е. в системе массового обслуживания):

8. Среднее время пребывания автомобиля в системе:

часа

9. Средняя продолжительность пребывания заявки в очереди на обслуживание:

часа.

10. Среднее число заявок в очереди (длина очереди):

.

Работу рассмотренного поста диагностики можно считать удов­летворительной, так как пост диагностики не обслуживает автомо­били в среднем в 15,8% случаев ( Pотк
= 0,158).

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

Стационарный режим функционирования данной СМО существует при для любого n = 0, 1, 2, ... и когда
< . Система алгебраических уравнений, описывающих работу СМО при
для любого n = 0, 1, 2, ... .
имеет вид

. (4.20)

Решение данной системы уравнений имеет вид

, n = 0, 1, 2, ... (4.21)

где
.

Характеристики одноканальной СМО с ожиданием, без ограничения на длину очереди, следующие:

 среднее число находящихся в системе клиентов (заявок) на обслуживание:

(4.22)

 средняя продолжительность пребывания клиента в системе:

(4.23)

 среднее число клиентов в очереди на обслуживании:

(4.24)

 средняя продолжительность пребывания клиента в очереди:

(4.25)

Пример 4.3.

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

Требуется определить финальные значения следующих вероят­ностных характеристик:

 вероятности состояний системы (поста диагностики);

 среднее число автомобилей, находящихся в системе (на обслу­живании и в очереди);

 среднюю продолжительность пребывания автомобиля в системе (на обслуживании и в очереди);

 среднее число автомобилей в очереди на обслуживании;

 среднюю продолжительность пребывания автомобиля в очереди.

Решение

1. Параметр потока обслуживания и приведенная интенсив­ность потока автомобилей
определены в примере 4.2:

=0,952; =0,893.

2. Вычислим предельные вероятности системы по формулам

и т.д.

Следует отметить, что P0
(t) определяет долю времени, в течение которого пост диагностики вынужденно бездействует (простаива­ет). В нашем примере она составляет 10,7%, так как P0
(t) = 0,107.

3. Среднее число автомобилей, находящихся в системе (на об­служивании и в очереди):

ед.

4. Средняя продолжительность пребывания клиента в системе:

час.

5. Среднее число автомобилей в очереди на обслуживание:

.

6. Средняя продолжительность пребывания автомобиля в очереди:

час.

7. Относительная пропускная способность системы:

q
= 1

т. е. каждая заявка, пришедшая в систему, будет обслужена. 8. Абсолютная пропускная способность:

.

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

Допустим, в первоначальном варианте количество мест для сто­янки прибывающих автомобилей было равно трем (см. пример 4.2). Частота т возникновения ситуаций, когда прибывающий на пост диагностики автомобиль не имеет возможности присоединиться к очереди:

.

В нашем примере при N
= 3 + 1 = 4 и = 0,893

автомобиля в час

При 12-часовом режиме работы поста диагностики это эквива­лентно тому, что пост диагностики в среднем за смену (день) будет терять 12 • 0,134 = 1,6 автомобиля.

Снятие ограничения на длину очереди позволяет увеличить ко­личество обслуженных клиентов в нашем примере в среднем на 1,6 автомобиля за смену (12ч. работы) поста диагностики. Ясно, что ре­шение относительно расширения площади для стоянки автомоби­лей, прибывающих на пост диагностики, должно основываться на оценке экономического ущерба, который обусловлен потерей кли­ентов при наличии всего трех мест для стоянки этих автомобилей.

Назад | Содержание | Далее

4.2.2. Многоканальная модель с пуассоновским входным потоком и экспоненциальным распределением длительности обслуживания

В подавляющем большинстве случаев на практике системы мас­сового обслуживания являются многоканальными, и, следователь­но, модели с

n

обслуживающими каналами

(где n > 1) представляют несомненный интерес.

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

Граф состояний многоканальной системы массового обслужи­вания с отказами имеет вид, показанный на рис. 4.3.

Рис. 4.3. Граф состояний многоканальной СМО с отказами

Состояния СМО имеют следующую интерпретацию:

S0
- все каналы свободны;

S1
- занят один канал, остальные свободны;

…………………………………………………….

Sk
- заняты ровно k
каналов, остальные свободны;

…………………………………………………….

Sn
- заняты все n
каналов, остальные свободны;

Уравнения Колмогорова для вероятностей состояний системы P0
, ... ,Pk
, ... Pn
будет иметь следующий вид:

(4.26)

Начальные условия решения системы таковы:

P0
(0) = 1, P1
(0) = P2
(0) = ... = Pk
(0) = ... = P1
(0) = 0 .

Стационарное решение системы имеет вид:

(4.27)

где .

Формулы для вычисления вероятностей Pk
называются формулами Эрланга.

Определим вероятностные характеристики функционирования многоканальной СМО с отказами в стационарном режиме:

 вероятность отказа:

,
(4.28)

так как заявка получает отказ, если приходит в момент, когда все n
каналов заняты. Величина Pотк
характеризует полноту обслуживания входящего потока;

 вероятность того, что заявка будет принята к обслуживанию (она же - относительная пропускная способность системы q
) дополняет Pотк
до единицы:

(4.29)

 абсолютная пропускная способность

(4.30)

 среднее число каналов, занятых обслуживанием () следующее:

(4.31)

Величина
характеризует степень загрузки СМО.

Пример 4.4.

Пусть n
-канальная СМО представляет собой вы­числительный центр (ВЦ) с тремя (n
= 3) взаимозаменяемыми ПЭВМ для решения поступающих задач. Поток задач, поступаю­щих на ВЦ, имеет интенсивность
= 1 задаче в час. Средняя про­должительность обслуживания
= 1,8 час. Поток заявок на ре­шение задач и поток обслуживания этих заявок являются простей­шими.

Требуется вычислить финальные значения:

 вероятности состояний ВЦ;

 вероятности отказа в обслуживании заявки;

 относительной пропускной способности ВЦ;

 абсолютной пропускной способности ВЦ;

 среднего числа занятых ПЭВМ на ВЦ.

Определите, сколько дополнительно надо приобрести ПЭВМ, чтобы увеличить пропускную способность ВЦ в 2 раза.

Решение

1. Определим параметр потока обслуживании:

2. Приведенная интенсивность потока заявок

.

3. Предельные вероятности состояний найдем по формулам Эр­ланга (4.27):

.

4. Вероятность отказа в обслуживании заявки

.

5. Относительная пропускная способность ВЦ

.

6. Абсолютная пропускная способность ВЦ

.

7. Среднее число занятых каналов – ПЭВМ

.

Таким образом, при установившемся режиме работы СМО в среднем будет занято 1,5 компьютера из трех - остальные полтора будут простаивать. Работу рассмотренного ВЦ вряд ли можно считать удовлетворительной, так как центр не обслуживает заявки в среднем в 18% случаев. Очевидно, что пропускную способность ВЦ при данных и можно увеличить только за счет увеличения числа ПЭВМ.

Определим, сколько нужно использовать ПЭВМ, чтобы сократить число необслуженных заявок, поступающих на ВЦ, в 10 раз, т.е. чтобы вероятность отказа в решении задач не превосходили 0,0180. Для этого используем формулу (4.28):

Составим следующую таблицу:

Рассмотрим многоканальную систему массового обслуживания с ожиданием

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

В установившемся режиме функционирование многоканальной СМО с ожиданием и неограниченной очередью может быть описа­но с помощью системы алгебраических уравнений:

(4.32)

Решение системы уравнений (4.32) имеет вид

(4.33) (4.34)

где

(4.35)

Решение будет действительным, если выполняется следующее условие: .

Вероятностные характеристики функционирования в стационар­ном режиме многоканальной СМО с ожиданием и неограниченной оче­редью определяются по следующим формулам:

 вероятность того, что в системе находится n
клиентов на обслу­живании, определяется по формулам (4.33) и (4.34);

 среднее число клиентов в очереди на обслуживание

; (4.36)

 среднее число находящихся в системе клиентов (заявок на Об­служивание и в очереди)

; (4.37)

 средняя продолжительность пребывания клиента (заявки на обслуживание) в очереди

; (4.38)

 средняя продолжительность пребывания клиента в системе

; (4.39)

Рассмотрим примеры многоканальной системы массового обслуживания с ожиданием.

Пример 4.5.

Механическая мастерская завода с тремя постами (каналами) выполняет ремонт малой механизации. Поток неисправных механизмов, прибывающих в мастерскую, - пуассоновский и имеет интенсивность = 2,5 механизма в сутки, среднее время ремонта одного механизма распределено по показательном у закону и равно
= 0,5 сут. Предположим, что другой мастерской на заводе нет, и, значит, очередь механизмов перед мастерской может расти практически неограниченно.

Требуется вычислить следующие предельные значения вероятностных характеристик системы:

 вероятности состояний системы;

 среднее число заявок в очереди на обслуживание;

 среднее число находящихся в системе заявок;

 среднюю продолжительность пребывания заявки в очереди;

 среднюю продолжительность пребывания заявки в системе.

Решение

1. Определим параметр потока обслуживаний

2. Приведенная интенсивность потока заявок

,

при этом
.

Поскольку
<1, то очередь не растет безгранично и в сис­теме наступает предельный стационарный режим работы.

3. Вычислим вероятности состояний системы:

.

4. Вероятность отсутствия очереди у мастерской

.

5. Среднее число заявок в очереди на обслуживание

.

6. Среднее число находящихся в системе заявок

.

7. Средняя продолжительность пребывания механизма в очереди на обслуживание

суток.

8. Средняя продолжительность пребывания механизма в мастерской (в системе)

суток.

Назад | Содержание | Далее

4.2.3. Модель обслуживания машинного парка

Модель обслуживания машинного парка представляет собой модель замкнутой системы массового обслуживания.

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

Например, обслуживается машинный парк, состоящий из N
машин, бригадой R
механиков (N
> R
), причем каждая машина мо­жет обслуживаться только одним механиком. Здесь машины являются источниками требований (заявок на обслуживание), а механики - обслуживающими каналами. Неисправная машина после обслуживания используется по своему прямому назначению и становится потенциальным источником возникновения требований на обслуживание. Очевидно, что интенсивность
зависит от того, сколько машин в данный момент находится в эксплуатации (N
- k
) и сколько машин обслуживается или стоит в очереди, ожидая обслуживания (k
).

В рассматриваемой модели емкость источника требований следует считать ограниченной. Входящий поток требований исходит из ограниченного числа эксплуатируемых машин (N
- k
), которые в случайные моменты времени выходят из строя и требуют обслуживания. При этом каждая машина из (N
- k
) находится в эксплуатации. Генерирует пуассоновский поток требований с интенсивностью X независимо от других объектов, общий (суммарный) входящий поток имеет интенсивность
. Требование, поступившее в систему в момент, когда свободен хотя бы один канал, немедленно идет на обслуживание. Если требование застает все каналы занятыми обслуживанием других требований, то оно не покидает систему, а становится в очередь и ждет, пока один из каналов не станет свободным.

Таким образом, в замкнутой системе массового обслуживания входящий поток требований формируется из выходящего.

Состояние Sk
системы характеризуется общим числом требований, находящихся на обслуживании и в очереди, равным k
. Для рассматриваемой замкнутой системы, очевидно, k = 0, 1, 2, ... , N. При этом если система находится в состоянии Sk
, то число объектов, находящихся в эксплуатации, равно (N
- k
).

Если
- интенсивность потока требований в расчете на одну машину, то:

;

Система алгебраических уравнений, описывающих работу за­мкнутой СМО в стационарном режиме, выглядит следующим об­разом:

(4.40)

Решая данную систему, находим вероятность k
-гo состояния:

(4.41)

Величина P0
определяется из условия нормирования
полученных результатов по формулам (4.41) для Pk
, k = 0, 1, 2, ... , N. Определим следующие вероятностные характеристики системы:

 среднее число требований в очереди на обслуживание:

; (4.42)

 среднее число требований, находящихся в системе (на обслуживании и в очереди)

; (4.43)

 среднее число механиков (каналов), «простаивающих» из-за отсутствия работы

; (4.44)

 коэффициент простоя обслуживаемого объекта (машины) в очереди

; (4.45)

 коэффициент использования объектов (машин)

; (4.46)

 коэффициент простоя обслуживающих каналов (механиков)

; (4.47)

 среднее время ожидания обслуживания (время ожидания обслуживания в очереди)

. (4.48)

Пример 4.6

. Пусть для обслуживания десяти персональных компьютеров (ПК) выделено два инженера одинаковой производительности. Поток отказов (неисправностей) одного компьютера - пуассоновский с интенсивностью = 0,2. Время обслуживания ПК подчиняется показательному закону. Среднее время обслуживания одного ПК одним инженером составляет: =1,25 час.

Возможны следующие варианты организации обслуживания:

 оба инженера обслуживают все десять компьютеров, так что при отказе ПК его обслуживает один из свободных инженеров, в этом случае R
= 2, N
= 10;

 каждый из двух инженеров обслуживает по пять закреплен­ных за ним ПК. В этом случае R
= 1, N
= 5.

Необходимо выбрать наилучший вариант организации обслуживания ПК.

Решение

1. Вычислим параметр обслуживания

.

2. Приведенная интенсивность

.

3. Вычислим вероятностные характеристики СМО для двух вариантов организации обслуживания ПК.

Вариант 1

1. Определим вероятности состояний системы:

Учитывая, что
=1 и используя результаты расчета Pk
, вычислим P0
:

.

Откуда P0
= 0,065.

Тогда

 Определим среднее число компьютеров в очереди на обслуживание:

 Определим среднее число ПК, находящихся в системе (на обслу­живании и в очереди):

 Определим среднее число инженеров, простаивающих из-за от­сутствия работы:

.

 Коэффициент простоя персонального компьютера в очереди сле­дующий:

.

 Коэффициент использования компьютеров определяется по фор­муле:

.

 Коэффициент простоя обслуживающих инженеров рассчитыва­ется так:

.

 Среднее время ожидания ПК обслуживания

час.

Вариант 2

Определим вероятности состояний системы:

Откуда P0
= 0,199.

Тогда

 Среднее число компьютеров в очереди на обслуживание таково:

 Среднее число компьютеров, находящихся на обслуживании и в очереди рассчитывается так:

 Среднее число инженеров, простаивающих из-за отсутствия ра­боты:

.

 Коэффициент простоя персонального компьютера в очереди:

.

 Коэффициент использования компьютеров:

.

 Коэффициент простоя обслуживающих инженеров:

.

 Среднее время ожидания ПК обслуживания:

час.

Сведем полученные результаты по двум вариантам в следую­щую таблицу:

Таким образом, в варианте 1 каждый компьютер стоит в очереди в ожидании начала его обслуживания приблизительно 0,142 ча­сти рабочего времени, что меньше этого показателя при варианте 2 организации работ. Далее в варианте 1 вероятность того, что ПК и любой момент времени будет работать выше, чем в варианте 2, и равна . Очевидно, вариант 1 организации работ по обслуживанию ПК эффективнее, чем вариант 2.

Назад | Содержание | Далее

5. СТАТИСТИЧЕСКОЕ МОДЕЛИРОВАНИЕ ЭКОНОМИЧЕСКИХ СИСТЕМ

5.1. Теоретические основы метода

Метод статистического моделирования (или метод Монте-Кар­ло) - это способ исследования поведения вероятностных систем (экономических, технических и т. д.) в условиях, когда не извест­ны в полной мере внутренние взаимодействия в этих системах.

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

Первые сведения о методе Монте-Карло были опубликованы в конце 40-х гг. Авторами метода являются американские математи­ки Дж. Нейман и С. Улам. В нашей стране первые работы были опубликованы в 1955-1956 гг. В.В. Чавчанидзе, Ю.А. Шрейдером и B.C. Владимировым.

Основой метода
статистического моделирования является за­кон больших чисел. Закон больших чисел в теории вероятностей доказывает для различных условий сходимость по вероятности средних значений результатов большого числа наблюдений к неко­торым постоянным величинам.

Под законом больших чисел понимают ряд теорем. Например, одна из теорем

Л.Л. Чебышева

формулируется так: "При неограни­ченном увеличении числа независимых испытаний n
среднее ариф­метическое свободных от систематических ошибок и равноточных результатов наблюдений
случайной величины
, имеющей ко­нечную дисперсию D(), сходится по вероятности к математичес­кому ожиданию М
() этой случайной величины». Это можно запи­сать в следующем виде:

, (5.1)

где
- сколь угодно малая положительная величина

Теорема Бернулли

формулируется так: "При неограниченном увеличений числа независимых испытаний в одних и тех же усло­виях частота
наступления случайного события А
сходится по вероятности к его вероятности Р
, т. е.

, (5.2)

Согласно данной теореме, для получения вероятности какого-либо события, например вероятности состояний некоторой системы
,
, вычисляют частоты
для одной реализации (испытания), далее проводят подобные вычисления для числа реализаций, равного n
. Результаты усредняют и этим самым с не­которым приближением, получают искомые вероятности состоя­ний системы. На основании вычисленных вероятностей определя­ют другие характеристики системы. Следует отметить, что, чем больше число реализаций 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
точками с координатами на n
частичных интервалов
.

Тогда получим:

Длина

Длина

.......................................................

Длина

Видно, что длина частичного интервала с индексом i
равна вероятности Р
с тем же индексом. Длина

Таким образом, при попадании случайного числа ri
в интервал
случайная величина Х принимает значение xi
с вероятностью Pi
.

Существует следующая теорема:

Если каждому случайному числу
, которое попало в интервал
, поставить в соответствие возможное значение xi
, то разыгрываемая величина будет иметь заданный закон распределения

Алгоритм разыгрывания дискретной случайной величины заданной законом распределения

1. Нужно разбить интервал (0,1) оси 0r
на n
частичных интервалов:

2. Выбрать (например, из таблицы случайных чисел, или в компьютере) случайное число rj
.

Если rj
попало в интервал
, то разыгрываемая дискретная случайная величина приняла возможное значение xi
.

Пример 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
.. Получим отсюда:

(5.3)

Далее в соответствии с алгоритмом выберем три случайных числа, распределенных равномерно в интервале (0; 1). Например r1
= 0,11; r2
= 0,17; r3
= 0,66.

Подставим эти числа в уравнение (5.3).Получим соответствующие возможные значения х
:

Пример 5.3

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

( x>0, параметр > 0 известен)

Требуется найти формулу для разыгрывания возможных значений Х
.

Решение

В соответствии с алгоритмом разыгрывания непрерывной случайной величины получим уравнение

Решим это уравнение относительно 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
. Получим

(то есть
)

На основании центральной предельной теоремы
теории вероятностей при распределение этой нормированной случайной величины стремится к нормальному закону с параметрами a
= 0 и
= 1.

При конечном n
распределение можно рассматривать как приближенно нормальное. Например, при n
= 12 получим достаточно точное для практики приближение

Таким образом, получаем, что для того чтобы разыграть возможное значение xi
нормальной случайной величины Х
с параметрами a
= 0 и
= 1, нужно сложить 12 независимых случайных чисел и из полученной суммы вычесть 6.

Пример 5.4.

1. Разыграть 100 возможных значений случайной величины Х
распределенной нормально с параметрами a
= 0 и
= 1.

2. Оценить параметры разыгранной случайной величины Х
.

Решение

1. Выберем 12 случайных чисел распределенных равномерно в интервале (0, 1) из таблицы случайных чисел, либо из компьютера. Сложим эти числа и из суммы вычтем 6, в итоге получим:

Поступая аналогичным образом найдем остальные возможные значения .

2. Выполнив необходимые расчеты найдем выборочную среднюю, которая является оценкой и выборочное среднее квадратическое отклонение, которое является оценкой . Получим:

Как видим, оценки удовлетворительны, т.е.
близко к нулю, а
близко к единице.

Если требуется разыграть значения нормальной ненормированной случайной величины с математическим ожиданием
отличным от нуля и
отличным от единицы, то сначала разыгрывают возможные значения xi

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

которая получена из соотношения:

Таблица 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)
):

 если [] < 0, то заявка получает отказ и вырабатыва­ют новый момент поступления заявки описанным способом;

 если , то происходит обслуживание.

6. При выполнении условия 5 б) определяют время обслужива­ния i
-й заявки на первом канале
путем преобразования случай­ной величины
в величину (время обслуживания /-и заявки) с за­данным законом распределения.

7. Вычисляют момент окончания обслуживания i
-й заявки на первом канале
.

8. Устанавливают новый момент поступления заявки, и вычислительная процедура повторяется в соответствии с изложенным.

9. В ходе моделирования СМО накапливаются статистические данные о процессе обслуживания.

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

Назад | Содержание | Далее

5.4. Моделирование потоков отказов элементов сложных технических систем

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

Рассмотрим последовательность замен некоторого определенного элемента Z
данного наименования. Эксплуатация каждого нового элемента начинается с момента окончания срока службы предыдущего. Первый элемент отрабатывает время
t1
, второй -
t2
, третий -
t3
и т. д.

Случайная ситуация, сложившаяся в k
-м опыте (ситуации) для элемента Z
, показана на рис. 5.1.

Рис. 5.1. Временная эпюра случайной ситуации при k
-м опыте в случае мгновенного восстановления отказавшей системы путем замены элемента

На рис. 5.1 видно, что система начинает свою работу в момент времени t
= 0 и, отработав случайное время
t1k
, выходит из строя в момент t1k
=
t1k
. В этот момент система мгновенно восстанавливается (элемент заменяется) и снова работает случайное время
t2k
. По истечении некоторого времени система (элемент) вновь выходит из строя в момент
и вновь мгновенно восстанавливается.

Считают, что интервалы времени между отказами
t1k
,
t2k
, ....
tpk
представляют собой систему взаимно независимых случайных величин с плотностями распределения наработок между отказами f(
t1
), f(
t2
) , … , f(
tp
) .

Моменты отказов или восстановлений образуют в каждом k
-м опыте (испытании) ряд чисел по следующему правилу:

(5.4)

или

.

где tik
- время работы (наработка) элемента до i
-го отказа в k
–м опыте, час,

, .

tik
- время работы (наработка) элемента между (i
-1)-м и i
-м отказами в k
–й реализации, час,
, .

Числа t1k
, t2k
, ... ,tpk
образуют случайный поток, который назы­вается процессом восстановления. Этот процесс является различным для различных элементов и продолжается до окончания срока служ­бы системы. Изучением таких процессов занимается теория восста­новления.

Из большого количества различных процессов восстановления для исследования надежности элементов технической системы (как неремонтируемых, так и ремонтируемых) используют три типа про­цессов:

 простой, при котором все функции распределения наработок до первого и между последующими отказами Fi
(t) равны;

 общий, при котором вид функции распределения наработки до первого отказа элемента, установленного в системе заводом-изготовителем, отличается от вида функций распределения нара­боток элементов при последующих заменах, т. е. , i
= 2, 3, 4,…

 сложный, при котором все функции распределения Fi
(t) раз­личны.

Основной характеристикой процесса восстановления является функция восстановления
и ее дифференциальная характерис­тика - плотность восстановления
, определяемые по следую­щим формулам:

; (5.5)

; (5.6)

где Fn
(t) и fn
(t) - соответственно плотность и функция распределения на­работки до n
-го отказа.

В случае независимости наработок между отказами функции распределения Fn
(t) наработок до n
-го отказа находятся путем по­следовательного применения правила свертки для суммы двух слу­чайных величин:

; (5.7)

F1
(t) = F(t) .

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

Расчет ведущей функции и параметра потока отказов этим методом в случае простого, общего или сложного процессов производится в следующем порядке.

По известным законам распределения наработок элементов с использованием формул преобразования (табл. 5.1) моделируются массивы случайных величин
tik
между (i-1)-м и i
-м отказами Размерность каждого массива равна N
.

Далее вычисляются значения наработок до i
-го отказа tik
по следующим формулам:

; (5.8)

, (5.9)

где i
– номер отказа,

k
– номер реализации при моделировании,

p
– максимальное число отказов элемента, получаемое в k-й реализации случайного процесса

Затем полученные случайные величины наработок tik
группиру­ются по интервалам времени.

Номера интервалов, в которые попадают моменты возникнове­ния отказов t1k
, t2k
, ... ,tik
, ... , tpk
определяются по формуле:

, (5.10)

где
- наименьшее целое число, не меньшее
;

ti
- величина интервала времени

Параметр и ведущая функция потока отказов в j
-м интервале времени определяется по следующим формулам:

; (5.11)

; (5.12)

где nij
- число попаданий случайной наработки до i
-го отказа tik
в j
-й ин­тервал времени () за N
реализаций.

; (5.13)

. (5.22)

где h
- максимальное число интервалов времени.

Пример 5.5.

Законы распределения наработок элемента системы до первого и второго отказов и соответствующие параметры этих законов приведены в следующей таблице:

№ отказа	Закон распределения	Параметры закона
		a()	b
1	Вейбула	1,4	45,8
2	Экспоненциальный	0,3	-

Определите номера временных интервалов, на которых про изойдут первый и второй отказы в ходе первого опыта (испытания) (
ti
= 1 час).

Решение

1. Выберем равномерно распределенное случайное число. До пустим i
= 0,725.

2. Вычислим случайные значения наработок на отказ элемента используя формулы табл. 5.1.

час.;

;

час.;

час.

3. Определим номер временного интервала, на котором произойдут отказы

первый отказ

;

второй отказ

.

В ходе первой реализации элемент системы первый раз откажет на 21-м временном интервале, а второй отказ произойдет на 22-м временном интервале.

В ходе первой реализации элемент системы первый раз откажет на 21-м временном интервале, а второй отказ произойдет на 22-м временном интервале.

Назад | Содержание | Далее

ЗАДАЧИ ДЛЯ САМОСТОЯТЕЛЬНОГО РЕШЕНИЯ

Задача 5.1

Периодичность поступления заявок на обслуживание под­чинена показательному закону распределения Средний интервал между поступлениями заявок в систему равен = 2 час. Определи­те последовательность значений продолжительности интервалов между поступлениями заявок. Число реализаций равно 10.

Задача 5.2

Время обслуживания работника предприятия кассой бух­галтерии является случайной величиной, распределенной в соответствии с законом Вейбула. Среднее время обслуживания
= 3 мин., среднее квадратическое отклонение равно
= 2 мин. Требуется смоделировать случайную величину, отвечающую этим условиям. Число реализаций принять равным 10.

Задача 5.3

При обработке экспериментальных данных было установлено, что время, расходуемое на станции технического обслужива­ния автомобилей для замены двигателя, распределено по нормаль­ному закону, параметры которого
= 2,8 час. на один двигатель и
= 0,6 час. Требуется смоделировать для отмеченных условий случайную величину - время X
, расходуемое для замены двигателя. Число реализаций принять равным 5.

Задача 5.4

Время проверки приемки квартального отчета инспектором Налоговой службы (t
) величина случайная, распределенная в соответствии с законом Вейбула. Среднее время проверки и приемки равно
= 20 мин. Коэффициент вариации величины t
равен
= 0,52. Требуется смоделировать для заданных условий случай­ные числа t
(число реализаций принять равным 10).

Задача 5.5

Среднее число исправных станков в токарном цехе на за­воде равно
= 6. Среднее квадратическое отклонение
= 2,2. Требуется смоделировать число исправных станков в цехе (число реализаций равно 5) при условии, что случайная величина X
имеет гамма-распределение.

Задача 5.6

Система имеет два элемента. Средняя периодичность первого элемента 1
= 60 час., второго элемента - 2
= 85 час. Периодичности отказа первого и второго элементов — случайные вели чины, подчиненные экспоненциальному закону распределения. Определите параметр и функцию распределения потока отказов систе­мы по интервалам времени
t = 8 час. Число реализаций N
= 10.

Задача 5.7

Периодичность проверки предприятий налоговой инспек­ции - величина случайная (
t), подчиняющаяся закону гамма-рас­пределения. Средний интервал проверки
= 2,5 мес. Коэффици­ент вариации величины
t равен V
=0,38. Требуется смоделировать для заданных условий возможные моменты проверок предприятия налоговой инспекцией (число реализаций принять равным 10).

Задача 5.8

Среднее число работающих машин на заводе
= 25. Ко­эффициент вариации числа работающих V
= 0,6. Требуется смоде­лировать число работающих машин на заводе (число реализаций равно 10). Случайная величина X
имеет распределение Вейбула.

Задача 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
= величина спроса в единицу времени, умноженная на время выполнения заказа =
. Другие характеристики системы определяются также, как и в модели1.1. Модель иллюстрируется рис. 6.3.

рис. 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. Необходимо найти размер заказа, минимизирующий общие издержки.

Решение
.

Рассчитаем оптимальный размер заказа для каждого вида скидок, т.е. Q
1*, Q
2* и Q
3*, и получим Q
1* = 700; Q
2* = 714; Q
3*=718.

Так как Q
1* - величина между 0 и 999, то ее можно оставить прежней. Q
2* меньше количества, необходимого для получения скидки, следовательно, его значение необходимо принять равным 1000 единиц. Аналогично Q
3* берем равным 2000 единиц. Получим Q
1* = 700; Q
2* = 1000; Q
3* = 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 игрушечных гоночных машинок будет минимизировать совокупные издержки.

Назад | Содержание | Далее