Исследование математических операций 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)