Исследование операций

Федеральное агентство связи Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Поволжский государственный университет телекоммуникаций и информатики» ____________________________________________________________________________ Кафедра «Экономические и информационные системы» «УТВЕРЖДАЮ» Зав. кафедрой профессор « » августа ЭИС Маслов О.Н. 2013 г. КОНСПЕКТ ЛЕКЦИЙ ПО УЧЕБНОЙ ДИСЦИПЛИНЕ «ИССЛЕДОВАНИЕ ОПЕРАЦИЙ» для специальностей 230700 «Прикладная информатика» 230400 «Информационные системы и технологии», 080500 «Бизнес-информатика» Обсуждено на заседании кафедры « » августа протокол № 1 Самара 2013 2013 г. 2 УДК 519.7 Диязитдинова А.Р. Исследование операций. Конспект лекций. – Самара.: ФГОБУ ВПО ПГУТИ, 2013. – 73 с. Исследование операций – это наука о выборе разумных, научно основанных решений во всех областях целенаправленной человеческой деятельности. Изучение методов исследования операций является важной составляющей при подготовке студентов в области информационных технологий. Оно формирует определенную методологию совершенствования существующих и создания новых систем на основе современных компьютерных средств. Конспект лекций предназначен для студентов, обучающихся по специальностям 230700 «Прикладная информатика», 230400 «Информационные системы и технологии», 080500 «Бизнес-информатика». Также конспект лекций может быть полезен студентам смежных специальностей, изучающим методы оптимизации и исследования операций. Рецензент: Федеральное государственное образовательное бюджетное учреждение высшего профессионального образования «Поволжский государственный университет телекоммуникаций и информатики» © Диязитдинова А.Р., 2013 3 СОДЕРЖАНИЕ 1 ОБЩИЕ ПОНЯТИЯ ДИСЦИПЛИНЫ «ИССЛЕДОВАНИЕ ОПЕРАЦИЙ».............................................................................................................. 5 ИСТОРИЯ РАЗВИТИЯ ДИСЦИПЛИНЫ ................................................................. 5 НАУЧНАЯ СУЩНОСТЬ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ ......................................... 6 ОСНОВНЫЕ ПОНЯТИЯ ....................................................................................... 7 ОСНОВНЫЕ ЗАДАЧИ, РЕШАЕМЫЕ МЕТОДОМ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ. КЛАССИФИКАЦИЯ ЗАДАЧ............................................................................................... 8 1.5 МЕТОДЫ ОТЫСКАНИЯ ОПТИМАЛЬНЫХ РЕШЕНИЙ В ЗАДАЧАХ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ. КЛАССИФИКАЦИЯ МЕТОДОВ .................................................................... 12 РЕЗЮМЕ ................................................................................................................... 13 ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ............................................................................... 13 1.1 1.2 1.3 1.4 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ .................................................. 14 2 2.1 ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ .................................................. 14 2.2 ГРАФИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ .......... 16 2.3 АНАЛИЗ МОДЕЛЕЙ НА ЧУВСТВИТЕЛЬНОСТЬ .................................................. 21 РЕЗЮМЕ ................................................................................................................... 27 ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ............................................................................... 27 СИМПЛЕКСНЫЙ МЕТОД ........................................................................ 28 3 3.1 ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ СИМПЛЕКСНОГО МЕТОДА .................... 28 3.2 АЛГОРИТМ СИМПЛЕКС-МЕТОДА.................................................................... 29 РЕЗЮМЕ ................................................................................................................... 32 ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ............................................................................... 32 ДВОЙСТВЕННЫЕ ЗАДАЧИ...................................................................... 33 4 ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ, ДВОЙСТВЕННОЙ ЗАДАЧЕ ОБ ИСПОЛЬЗОВАНИИ РЕСУРСОВ ........................................................................................ 33 4.2 ВЗАИМНО-ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИХ СВОЙСТВА .................................................................................................................... 34 4.3 ТЕОРЕМЫ ДВОЙСТВЕННОСТИ ......................................................................... 36 РЕЗЮМЕ ................................................................................................................... 38 ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ............................................................................... 38 4.1 ЦЕЛОЧИСЛЕННЫЕ МОДЕЛИ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ ... 39 5 РЕЗЮМЕ ................................................................................................................... 42 ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ............................................................................... 43 6 ТРАНСПОРТНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ...................................................................................... 44 6.1 6.2 6.3 ПОСТАНОВКА ЗАДАЧИ ................................................................................... 44 МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ ................................................. 46 АЛГОРИТМ МЕТОДА ПОТЕНЦИАЛОВ .............................................................. 47 4 РЕЗЮМЕ ................................................................................................................... 52 ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ............................................................................... 52 7 ЗАДАЧИ ОПТИМИЗАЦИИ РЕШЕНИЙ С ИСПОЛЬЗОВАНИЕМ ДИНАМИЧЕСКИХ РЯДОВ .................................................................................. 53 7.1 СУЩНОСТЬ ДИНАМИЧЕСКОЙ ОПТИМИЗАЦИИ ................................................ 53 7.2 ДИНАМИЧЕСКАЯ ОПТИМИЗАЦИЯ В ПЛАНИРОВАНИИ РАБОТ .......................... 56 РЕЗЮМЕ ................................................................................................................... 58 ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ............................................................................... 59 МОДЕЛИРОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ 60 8 КОМПОНЕНТЫ И КЛАССИФИКАЦИЯ МОДЕЛЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ 60 8.2 ОДНОКАНАЛЬНАЯ МОДЕЛЬ С ПУАССОНОВСКИМ ВХОДНЫМ ПОТОКОМ С ЭКСПОНЕНЦИАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ ДЛИТЕЛЬНОСТИ ОБСЛУЖИВАНИЯ ............. 62 8.1 8.2.1 8.2.2 Одноканальная СМО с отказами ........................................................................... 62 Одноканальная СМО с ожиданием ........................................................................ 64 МНОГОКАНАЛЬНАЯ МОДЕЛЬ С ПУАССОНОВСКИМ ВХОДНЫМ ПОТОКОМ И ЭКСПОНЕНЦИАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ ДЛИТЕЛЬНОСТИ ОБСЛУЖИВАНИЯ ............. 67 8.3 8.3.1 Многоканальная СМО с отказами ......................................................................... 68 8.3.2 Многокональная СМО с ожиданием ...................................................................... 69 РЕЗЮМЕ ................................................................................................................... 71 ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ ............................................................................... 71 ГЛОССАРИЙ ........................................................................................................... 72 ПЕРЕЧЕНЬ РЕКОМЕНДУЕМОЙ К ИЗУЧЕНИЮ ЛИТЕРАТУРЫ ........... 73 5 1 ОБЩИЕ ПОНЯТИЯ ДИСЦИПЛИНЫ «ИССЛЕДОВАНИЕ ОПЕРАЦИЙ» 1.1 ИСТОРИЯ РАЗВИТИЯ ДИСЦИПЛИНЫ Зарождение исследования операций как научной дисциплины было обусловлено неотложным требованием решения важных практических проблем. Поэтому в процессе становления и развития исследования операций научные работники, которые занимались соответствующими исследованиями, не только заложили фундамент некоторого нового научного направления, но и использовали полученные знания для практического решения проблем. В течение второго и третьего десятилетий своего существования группы по исследованию операций значительно выросли и стали достаточно отличаться друг от друга по направлениям. Начало развития исследования операций как науки традиционно связывают с сороковыми годами двадцатого столетия. Среди первых исследований в данном направлении может быть названа работа Л.В. Канторовича "Математические методы организации и планирования производства", вышедшая в 1939 г. В 1975 году Л. В. Канторович стал лауреатом Нобелевской премии за свои работы по оптимальному использованию ресурсов в экономике. В зарубежной литературе отправной точкой обычно считается вышедшая в 1947 г. работа Дж. Данцига, посвященная решению линейных экстремальных задач. Имеющиеся исторические документы и архивы не позволяют точно установить количество тех ученых, которые были заняты исследованием операций во время второй мировой войны, однако даже осторожные оценки свидетельствуют о том, что общее число таких ученых в Англии, Америке и Канаде превышало 700 человек. Их деятельность, слишком разнообразная для того, чтобы можно было охарактеризовать ее полностью, не только охватывала элементы технических решений, оценки результатов тактических операций и новшеств (о чем уже говорилось), но и включала применение соответствующих знаний при планировании тактических операций и выработке стратегии. Наиболее важным для будущего было то, что многие из специалистов увидели в таких научных разработках военного времени зарождение новой науки о функциональных системах, а также возможности использования соответствующих научных знаний для многих видов деятельности в мирное время. После второй мировой войны специалисты осознали, что работам по исследованию операций в том его понимании, которое сложилось во время войны, предшествовали многие исследования аналогичной направленности, например работа Ланчестера по моделированию боевых операций, выполненная в 1916 г., работы по теории массового обслуживания Эрланга, нашедшие практическую реализацию в начале двадцатого столетия в Копенгагене, исследования Левинсона в области розничной торговли в начале 20-х годов. Однако эти исследования оставались разрозненными до тех пор, пока не были подхвачены общим потоком разработок, начало которого только что было кратко охарактеризовано. Таким образом, есть достаточные основания считать, что появление методов исследования операций связано с выделением самостоятельной области научной деятельности, имеющей продолжительную историю, начало которой положили работы, проведенные во время второй мировой войны. 6 1.2 НАУЧНАЯ СУЩНОСТЬ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ Следует отметить, что не существует жесткого, устоявшегося и общепринятого определения предмета исследования операций. Часто при ответе на данный вопрос говорится, что "исследование операций представляет собой комплекс научных методов для решения задач эффективного управления организационными системами". Второе определение: Исследование Операций – это научная подготовка принимаемого решения – это совокупность методов, предлагаемых для подготовки и нахождения самых эффективных или самых экономичных решений. Исследование операций – применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Научная дисциплина, называемая исследованием операций, наблюдает реальные явления, связанные с функциональными системами, разрабатывает теории (которые многие исследователи называют моделями), предназначенные для объяснения данных явлений, использует эти теории для описания того, что произойдет при изменении условий, и проверяет предсказания новыми наблюдениями. Исследование операций начинается тогда, когда для обоснования решения применяется тот или иной математический аппарат. Исследование операций есть своеобразное математическое «примеривание» будущих решений, позволяющее экономить время, силы и материальные средства, избегать серьезных ошибок. Несмотря на многообразие задач организационного управления, при их решении можно выделить некоторую общую последовательность этапов, через которые проходит любое операционное исследование. Как правило, это: 1) Постановка задачи. 2) Построение содержательной (вербальной) модели рассматриваемого объекта (процесса). На данном этапе происходит формализация цели управления объектом, выделение возможных управляющих воздействий, влияющих на достижение сформулированной цели, а также описание системы ограничений на управляющие воздействия. 3) Построение математической модели, т.е. перевод сконструированной вербальной модели в ту форму, в которой для ее изучения может быть использован математический аппарат. 4) Решение задач, сформулированных на базе построенной математической модели. 5) Проверка полученных результатов на их адекватность природе изучаемой системы, включая исследование влияния так называемых внемодельных факторов, и возможная корректировка первоначальной модели. 6) Реализация полученного решения на практике. Центральное место в данном курсе отведено вопросам, относящимся к четвертому пункту приведенной выше схемы. Это делается не потому, что он является самым важным, сложным или интересным, а потому, что остальные пункты существенно зависят от конкретной природы изучаемой системы, в силу чего для действий, которые должны производиться в их рамках, не могут быть сформулированы универсальные и содержательные рекомендации. 7 1.3 ОСНОВНЫЕ ПОНЯТИЯ Операция – это всякая система действий (мероприятие), объединенных единым замыслом и направленных к достижению какой-то цели. Операция есть всегда управляемое мероприятие, то есть от нас зависит, каким способом выбрать некоторые параметры, характеризующие его организацию. Каждый определенный выбор зависящих от нас параметров называется решением. Оптимальными называются решения, по тем или иным признакам предпочтительные перед другими. Целью исследования операций является предварительное количественное обоснование оптимальных решений. Само принятие решения выходит за рамки исследования операций и относится к компетенции ответственного лица, которому предоставлено право окончательного выбора и на которое возложена ответственность за этот выбор. Делая выбор, они могут учитывать наряду с рекомендациями, вытекающими из математического расчета, еще ряд соображений (количественного и качественного характера), которые этим расчетом не были учтены. Те параметры, совокупность которых образует решение, называются элементами решения. В качестве элементов решения могут быть различные числа, векторы, функции, физически признаки и т.д. Чтобы сравнить между собой различные варианты, необходимо иметь какой-то количественный критерий – показатель эффективности (W). Данный показатель называется целевой функцией. Этот показатель выбирается так, чтобы он отражал целевую направленность операции. Выбирая решение, стремимся, чтобы данный показатель стремился к максимуму или к минимуму. Если W – доход, то W → max; а если W – расход, то W → min. Если выбор зависит от случайных факторов (погода, отказ техники, колебания спроса и предложения), то в качестве показателя эффективности выбирается среднее значение – математическое ожидание – W . При решении любой конкретной задачи применение методов исследования операций заключается в следующем: − построение математических, экономических и статистических моделей для задач принятия решений и управления в сложных ситуациях в условиях неопределенности (наличие случайных факторов); − изучение взаимосвязей, определяющих возможные последствия принятых решений. Установление критериев эффективности, позволяющих оценить преимущества того или иного варианта. Методы исследования операций обладают рядом специфических черт. Чтобы подход к решению задач можно было считать операционным, он должен содержать следующие элементы: 1) ориентация на принятие решений; 8 2) оценка на основе критерия экономической эффективности; 3) доверие математической модели; 4) необходимость использования ЭВМ. Основные этапы применения метода исследования операций: 1) определение цели; 2) составление плана разработки проекта; 3) формулировка проблемы; 4) построение модели; 5) разработка вычислительного метода; 6) разработка технического задания на программирование, само программирование и отладка программы; 7) сбор данных; 8) проверка модели; 9) реализация результатов, то есть принятие решения. 1.4 ОСНОВНЫЕ ЗАДАЧИ, РЕШАЕМЫЕ МЕТОДОМ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ. КЛАССИФИКАЦИЯ ЗАДАЧ Накопленный опыт в решении задач исследования операций и его систематизация позволили выделить следующие типы задач: − задачи управления запасами, − задачи распределения ресурсов, − задачи ремонта и замены оборудования, − задачи массового обслуживания, − задачи упорядочивания, − задачи сетевого планирования и управления (СПУ), − задачи выбора маршрута, − комбинированные задачи. 1. Задачи управления запасами Этот класс задач в настоящее время наиболее распространенный, а главное, изученный. Эти задачи имеют следующую особенность: с ростом запасов, увеличиваются расходы на их хранение, но снижаются потери, связанные с возможной их нехваткой. Следовательно, одна из задач управления запасами заключается в определении такого уровня запасов, который минимизирует следующие критерии: − сумма ожидаемых затрат на хранение, − сумма потерь из-за дефицита. В зависимости от условий, задачи управления запасами делятся на 3 группы: а) моменты поставок или оформления заказов на поставки, пополнение запасов фиксированы. Определить объемы производимой или закупаемой партии запасов; 9 б) объемы производимой или закупаемой партии запасов фиксированы. Определить моменты оформления заказов на поставки; в) моменты оформления заказов и объемы закупаемых партий запасов нефиксированы. Определить эти величины, исходя из минимальных затрат и минимальных потерь из-за дефицита. 2. Задачи распределения ресурсов Эти задачи возникают тогда, когда существует определенный набор операций (работ), которые необходимо выполнить, а наличия ресурсов для выполнения операций наилучшим образом не хватает. В зависимости от условия задачи эти также делятся на 3 группы: а) заданы работы и ресурсы. Распределить ресурсы между работами таким образом, чтобы максимизировать некоторую меру эффективности (прибыль) или минимизировать ожидаемые затраты (издержки производства). Пример: известны производственное задание и производственные мощности предприятия. При существующих различных способах получения изделия, ограничения по мощности не позволяют для каждого изделия использовать наилучшую технологию. Какие способы производства надо выбрать, чтобы выполнить задание с минимальными затратами? б) заданы только наличные ресурсы. Определить, какой состав работ можно выполнить с учетом этих ресурсов, чтобы обеспечить максимум некоторой меры эффективности. Пример: задано предприятие с определенными производственными мощностями. Какую продукцию следует производить, чтобы получить максимальный доход? в) заданы только работы. Определить, какие ресурсы необходимы для того, чтобы минимизировать суммарные издержки производства. Пример: известно месячное расписание движения полетов пассажирских самолетов на авиалинии. Какое количество экипажей необходимо подобрать, чтобы выполнить план с минимальными затратами? 3. Задачи ремонта и замены оборудования Производственное оборудование с течением времени изнашивается и подлежит предупредительно-восстановительному ремонту. Оборудование также устаревает (морально и физически) и подлежит полной замене. При этом постановка задачи такова: определить такие сроки ремонта и замены оборудования, при которых минимизируется сумма затрат на ремонт и замену оборудования при его старении. Иногда в оборудовании выходят из строя отдельные элементы (например, микросхемы) – в данном случае требуется определить такие сроки профилактического ремонта по замене вышедших из строя деталей, чтобы потери на данный элемент были минимальными. Здесь также имеет место профилактический контроль по обнаружению неисправностей. Требуется определить такие сроки контроля, при которых минимизируется сумма затрат на проведение контроля, а также минимизируется сумма потерь от простоя оборудования вследствие выхода из строя отдельных элементов. 10 4. Задачи массового обслуживания Данные задачи возникают там, где образуется очередь. С образованием очереди приходится сталкиваться как в производстве, так и в быту (производство: очередность выполнения заказа; в быту: магазин, поликлиника). Подобные задачи существуют и на транспорте. Очередь возникает из-за того, что поток клиентов (заказов) поступает неравномерно и имеет случайный характер. То есть поток клиентов неуправляем. Объект, который обслуживает клиента, называется каналом обслуживания (продавец, врач, взлетно-посадочная полоса). Если каналов обслуживания много, очереди не образуется, но возможны простои каналов обслуживания. Если каналов мало – образуется очередь. А следовательно, возможны затраты, связанные с ожиданием в очереди клиента ми с отказом клиента от обслуживания. В данных задачах возможна следующая постановка: определить, какое количество каналов обслуживания необходимо, чтобы свести к минимуму суммарные затраты, связанные с несвоевременным обслуживанием и простоем каналов. Для решения задач используется теория массового обслуживания. 5. Задачи упорядочивания Эти задачи часто встречаются в производстве. Предположим, что в цехе изготавливается множество деталей по разным технологическим маршрутам. В парке оборудования имеется ограниченное число станков (токарный, фрезерный, строгальный и др.). На одном станке в данный момент времени может обрабатываться только 1 деталь. Появляется очередность выполнения работ, то есть появляются детали, ждущие обработки. Время обработки каждой детали обычно известно. Такая задача называется задачей календарного планирования или составлением расписания работ. Выбор очередности запуска деталей в обработку является задачей упорядочивания. В таких задачах в качестве критерия эффективности часто встречаются следующие: − минимизация общей продолжительности работ (то есть интервала времени между моментом началом первой операции и моментом окончания последней); − минимизация общего запаздывания. Запаздывание определяется как разность фактическим и плановым сроком обработки каждой детали. Общее запаздывание = сумме запаздываний по всем деталям. 6. Задачи сетевого планирования и управления (СПУ) Данные задачи актуальны при разработке сложных, дорогостоящих проектов. Здесь рассматривается соотношение между сроком выполнения крупного комплекса операций и моментом начала всех операций отдельно в комплексе. Для строгой постановки задачи необходимо выполнить следующие условия: − Должно существовать точно определяемое количество операций, − Множество операций по комплексу упорядочено так, что должно быть известно для каждой операции какие операции ей предшествуют, а какие следуют за ней, − В пределах заданного упорядочивания операций, операции можно начинать и заканчивать независимо друг от друга, − Известна взаимосвязь между ресурсами на выполнение операции и ее продолжительностью. 11 Если все условия выполнены, возможны следующие постановки задачи: а) задана продолжительность выполнения всего комплекса операций. Требуется определить сроки каждой операции, при которых: − минимизируются общие затраты на выполнение всего комплекса операций, − определяется вероятность невыполнения комплекса работ в установленные сроки, − определяется среднеквартальные отклонения требуемых ресурсов от наличных. б) заданы общие ресурсы. Определить сроки начала каждой операции, чтобы минимизировать время на выполнение всего комплекса операций. 7. Задачи маршрутизации Эти задачи возникают при исследовании разнообразных процессов на транспорте и в системах связи. Типичной задачей является задача выбора оптимального маршрута: имеется несколько маршрутов, из них нужно выбрать один. Стоимость прохождения и время на прохождение зависит от выбранного маршрута. При рассмотрении ряда маршрутов вводятся следующие ограничения: − запрещается возвращаться в уже пройденный пункт, − в пунктах сети возможны задержки (например, из-за ограниченной пропускной способности). Задержки носят случайный характер. Критерии оптимизации: минимизация общего времени прохождения маршрута или минимизация общих затрат. Данные задачи наиболее изучены и в литературе носят специфические названия – задача о коммивояжере или задача о максимальном потоке. 8. Комбинированные задачи Включают в себя несколько типовых задач одновременно. Пример: при планировании и управлении производством необходимо решить комплекс задач: 1) сколько изделий каждого наименования необходимо выпустить и каковы оптимальные размеры партии изделий – задача планирования производства; 2) распределить заказы или детали по видам оборудования, причем оптимальный план производства задан – задача распределения; 3) определить в какой последовательности следует выполнить производственные заказы – календарное планирование. Эти задачи нельзя решать независимо друг от друга. Критерии эффективности этих задач часто противоречат друг другу. Поэтому при решении задач часто используют: Метод последовательного приближения – с помощью этого метода можно очень близко подойти к оптимальному решению. Метод имитационного моделирования – основан на методе Монте-Карло (использование случайных чисел) и требует огромного количества вычислений, так как рассматривается очень много вариантов решений. 12 1.5 МЕТОДЫ ОТЫСКАНИЯ ОПТИМАЛЬНЫХ РЕШЕНИЙ В ЗАДАЧАХ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ. КЛАССИФИКАЦИЯ МЕТОДОВ На протяжении всей истории развития методов исследования операций научные работники следовали рекомендациям Блеккета, согласно которым исследование операций, как и любая другая наука, не базируется на использовании точных копий аналитических методов какой-либо другой науки, а требует разработки своего собственного математического аппарата - методов исследования операций - ориентированного на специфику, присущую этой области и задачам исследования. Этот аппарат не должен оставаться неизменным; наоборот, он должен меняться в соответствии с характером исследуемых задач. К основным методам отыскания оптимальных решений относятся: − математическое программирование. В свою очередь методы математического программирования делятся на следующие: o линейное программирование, o нелинейное программирование, o динамическое программирование, o целочисленное программирование, o стохастическое программирование, o эвристическое программирование − теория массового обслуживания, − сетевые модели планирования и управления, − имитационное моделирование. Рассмотренные выше классы задач можно решать указанными методами. Методами математического программирования решаются следующие классы задач: − задачи управления запасами, − задачи распределения ресурсов, − задачи замены и ремонта оборудования, − задачи выбора маршрута. С помощью теории массового обслуживания решаются задачи массового обслуживания. С использованием сетевых моделей планирования и управления можно решать: − задачи массового обслуживания, − задачи упорядочивания, − задачи сетевого планирования. 13 Методом имитационного моделирования решаются комбинированные задачи. Данным методом можно решить задачу любого класса, однако, данный метод не является универсальным. Его применение ограничено следующими факторами: 1) требуется наличие высококвалифицированных специалистов, т.к. он содержит в себе элементы всех вышеперечисленных методов; 2) решение обходится дороже, чем при использовании других методов. РЕЗЮМЕ Из материала, изложенного в данной лекции, можно сделать следующие выводы: − зарождение исследования операций как научной дисциплины было обусловлено неотложным требованием решения важных практических проблем. Поэтому в процессе становления и развития дисциплины научные работники не только заложили фундамент некоторого нового научного направления, но и использовали полученные знания для практического решения проблем. − Исследованием операций наблюдает реальные явления, связанные с функциональными системами, разрабатывает теории, предназначенные для объяснения данных явлений, использует эти теории для описания того, что произойдет при изменении условий, и проверяет предсказания новыми наблюдениями. − Несмотря на многообразие задач организационного управления, при их решении можно выделить некоторую общую последовательность этапов, через которые проходит любое операционное исследование. − Целью исследования операций является предварительное количественное обоснование оптимальных решений. − Накопленный опыт в решении задач исследования операций и его систематизация позволили выделить различные типы задач, для которых применяются соответствующие математические методы. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ Когда зародилась научная дисциплина «Исследование операций»? Дайте определение исследованию операции. Перечислите этапы операционного исследования. Дайте определение терминам «операция», «решение», «оптимальное решение», «целевая функция» 5. Перечислите основные этапы применения метода исследования операций. 6. Перечислите основные задачи, решаемые методом исследования операций. 7. Дайте характеристику задачи управления запасами. 8. Дайте характеристику задачи распределения ресурсов. 9. Дайте характеристику задачи ремонта и замены оборудования. 10. Дайте характеристику задачи массового обслуживания. 11. Дайте характеристику задачи упорядочивания. 12. Дайте характеристику задачи сетевого планирования и управления. 13. Дайте характеристику задачи выбора маршрута. 14. Перечислите и дайте краткую характеристику методов отыскания оптимальных решений в задачах исследования операций. 1. 2. 3. 4. 14 2 ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ 2.1 ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Оптимизационная задача – это экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений. В самом общем виде задача математически записывается следующим образом: U = f ( Х ) → max ; X ∈ W , где (2.1) X = ( x1 , x2 ,..., xn ) ; W – область допустимых значений переменных x1 , x2 ,..., xn ; f(Х) – целевая функция. Для того, чтобы решить задачу оптимизации, достаточно найти ее оптимальное решение, т.е. указать X 0 ∈W такое, что f ( X 0 ) ≥ f ( X ) при любом X ∈W . Оптимизационная задача является неразрешимой, если она не имеет оптимального решения. В частности, задача максимизации будет неразрешимой, если целевая функция f(Х) не ограничена сверху на допустимом множестве W. Методы решения оптимизационных задач зависят как от вида целевой функции f(Х), так и от строения допустимого множества W. Если целевая функция в задаче является функцией n переменных, то методы решения называют методами математического программирования. Задачей линейного программирования называется задача исследования операций, математическая модель которой имеет вид: n f ( Х ) = ∑ c j x j → max(min) ; (2.2) j =1 n ∑a j =1 ij x j = bi , i ∈ I , I ⊆ M = {1,2,..., m} ; (2.3) ij x j ≤ bi , I ∈ M ; (2.4) n ∑a j =1 x j ≥ 0 , j ∈ J , J ⊆ N = {1,2,..., n} . (2.5) При этом система линейных уравнений (2.3) и неравенств (2.4), (2.5), определяющая допустимое множество решений задачи W, называется системой ограничений задачи линейного программирования, а линейная функция f(Х) называется целевой функцией или критерием оптимальности. В частном случае, если I = Ø, то система (2.3) – (2.4) состоит только из линейных неравенств, а если I = M, то – из линейных уравнений. Если математическая модель задачи линейного программирования имеет вид: n f ( Х ) = ∑ c j x j → min ; j =1 (2.6) 15 n ∑a j =1 ij x j = bi , i = 1, m , (2.7) bi ≥ 0 ; x j ≥ 0 , j = 1, n , . (2.8) то говорят, что задача представлена в канонической форме. Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. Для этого в общем случае нужно уметь сводить задачу максимизации к задаче минимизации; переходить от ограничений неравенств к ограничениям равенств и заменять переменные, которые не подчиняются условию неотрицательности. Максимизация некоторой функции эквивалента минимизации той же функции, взятой с противоположным знаком, и наоборот. Правило приведения задачи линейного программирования к каноническому виду состоит в следующем: 1) если в исходной задаче требуется определить максимум линейной функции, то следует изменить знак и искать минимум этой функции; 2) если в ограничениях правая часть отрицательна, то следует умножить это ограничение на -1; 3) если среди ограничений имеются неравенства, то путем введения дополнительных неотрицательных переменных они преобразуются в равенства; 4) если некоторая переменная x k не имеет ограничений по знаку, то она заменяется (в целевой функции и во всех ограничениях) разностью между двумя новыми неотрицательными переменными: x k = x′k − xl , где l - свободный индекс, x ′k ≥ 0 ; xl ≥ 0 . Пример 2.1. Приведение к канонической форме задачи линейного программирования: min L = 2 x1 + x2 − x3 ; 2 x 2 − x3 ≤ 5 ; x1 + x2 − x3 ≥ −1 ; 2 x1 − x2 ≤ −3 ; x1 ≤ 0 , x2 ≥ 0 , x3 ≥ 0 . Введем в каждое уравнение системы ограничений выравнивающие переменные x4 , x5 , x6 . Система запишется в виде равенств, причем в первое и третье уравнения системы ограничений переменные x 4 , x6 вводятся в левую часть со знаком "+", а во второе уравнение вводится x5 со знаком "-". 2 x 2 − x3 + x 4 = 5 ; x1 + x2 − x3 − x5 = −1 ; 2 x1 − x2 + x6 = −3 ; x 4 ≥ 0 , x5 ≥ 0 , x 6 ≥ 0 . 16 Свободные члены в канонической форме должны быть положительными, для этого два последних уравнения умножим на -1: 2 x 2 − x3 + x 4 = 5 ; − x1 − x2 + x3 + x5 = 1 ; − 2 x1 + x2 − x6 = 3 . В канонической форме записи задач линейного программирования все переменные, входящие в систему ограничений, должны быть отрицательными. Допустим, что x1 = x1′ − х7 , где x1′ ≥ 0 , х7 ≥ 0 . Подставляя данное выражение в систему ограничений и целевую функцию и, записывая переменные в порядке возрастания индекса, получим задачу линейного программирования, представленную в канонической форме: 2 x 2 − x3 + x 4 = 5 ; − x1′ − x2 + x3 + x5 + х7 = 1 ; − 2 x1′ + x2 − x6 + 2 х7 = 3 ; Lmin = 2 x1′ + x2 − x3 − 2 х7 ; x1′ ≥ 0 , хi ≥ 0 ; i = 2,7 . 2.2 ГРАФИЧЕСКОЕ РЕШЕНИЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ Пример 2.2. Определение оптимального ассортимента продукции. Предприятие изготавливает два вида продукции - П1 и П 2 , которая поступает в оптовую продажу. Для производства продукции используются два вида сырья - А и В. Максимально возможные запасы сырья в сутки составляют 9 и 13 единиц соответственно. Расход сырья на единицу продукции вида П1 и вида П 2 дан в табл. 2.1. Таблица 2.1. Расход сырья продукции Расход сырья на 1 ед. продукции Сырье А В П1 П2 2 3 3 2 Запас сырья, ед. 9 13 Опыт работы показал, что суточный спрос на продукцию П1 никогда не превышает спроса на продукцию П 2 более чем на 1 ед. Кроме того, известно, что спрос на продукцию П 2 никогда не превышает 2 ед. в сутки. Оптовые цены единицы продукции равны: 3 д. е. - для П1 и 4 д.е. для П 2 . Какое количество продукции каждого вида должно производить предприятие, чтобы доход от реализация продукции был максимальным? Процесс построения математической модели для решения подавленной задачи начинается с ответов на следующие вопросы1. 1 Таха Х. Введение в исследование операции: В 2-х кн. – М.: Мир, 1985 17 1) Для определения каких величин должна быть построена модель, т.е. как идентифицировать переменные данной задачи? 2) Какие ограничения должны быть наложены на переменные, чтобы выполнялись условия, характерные для моделируемой системы? 3) В чем состоит цель задачи, для достижения которой из всех допустимых значений переменных нужно выбрать те, которые будут соответствовать оптимальному (наилучшему) решению задачи? Ответы на вышеперечисленные вопросы могут быть сформулированы для данной задачи так: фирме требуется определить объемы производства каждого вида продукции в тоннах, максимизирующие доход в д.е. от реализации продукции, с учетом ограничений на спрос и расход исходных продуктов. Для построения математической модели остается только идентифицировать переменные и представить цель и ограничения в виде математических функций этих переменных. Предположим, что предприятие изготовит x1 единиц продукции П1 и x 2 единиц продукции П 2 . Поскольку производство продукции П1 и П 2 ограничено имеющимися в распоряжении предприятия сырьем каждого вида и спросом на данную продукцию, а также учитывая, что количество изготовляемых изделий не может быть отрицательным, должны выполняться следующие неравенства: 2 x1 + 3x2 ≤ 9 ; 3x1 + 2 x2 ≤ 13 ; x1 − x2 ≤ 1 ; x2 ≤ 2 ; x1 ≥ 0 ; x2 ≥ 0 . Доход от реализации x1 единиц продукции П1 и x 2 единиц продукции П 2 составит F = 3x1 + 4 x2 . Таким образом, мы приходим к следующей математической задаче: среди всех неотрицательных решений данной системы линейных неравенств требуется найти такое, при котором функция F принимает максимальное значения Fmax . Рассмотренная задача относится к разряду типовых задач оптимизации производственной программы предприятия. В качестве критериев оптимальности в этих задачах могут быть также использованы: прибыль, себестоимость, номенклатура производимой продукции и затраты станочного времени. Графически способ решения задач линейного программирования целесообразно использовать для: − решения задач с двумя переменными, когда ограничения выражены неравенствами; − решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных. Запишем задачу линейного программирования с двумя переменными: 18 − целевая функция: Z max =c1 x1 + c 2 x 2 (2.9) − ограничения: a11 x1 + a12 x 2 ≤ b1 a x + a x ≤ b  21 1 22 2 2 ;  .......................... a m1 x1 + a m 2 x 2 ≤ bm (2.10) x1 ≥ 0 ; x 2 ≥ 0 . (2.11) Каждое из неравенств (2.10) – (2.11) системы ограничений задачи геометрически определяет полуплоскость соответственно с граничными прямыми ai1 x1 + ai 2 x 2 = bi ; ( i = 1, m ); x1 = 0 ; x 2 = 0 . В том случае, если система неравенств (2.10) – (2.11) совместна, область ее решений есть множество точек, принадлежащих всем указанным полуплоскостям. Так как множество точек пересечения данных полуплоскостей – выпуклое, то областью допустимых значений является выпуклое множество, которое называется многоугольником решений. Стороны этого многоугольника лежат на прямых, уравнения которых получаются из исходной системы ограничений заменой знаков неравенств на знаки равенств. Областью допустимых решений системы неравенств (2.10) – (2.11) может быть: − − − − − − выпуклый многоугольник; выпуклая многоугольная неограниченная область; пустая область; луч; отрезок; единственная точка. Целевая функция (2.9) определяет на плоскости семейство параллельных прямых, каждой из которых соответствует определенное значений Z. Вектор С = (с1 ; с 2 ) с координатами с1 и с 2 , перпендикулярный к этим прямым, указывает направление наискорейшего возрастания Z, а противоположный вектор – направление убывания Z. Если в одной и той же системе координат изобразить область допустимых решений системы неравенств (2.10) – (2.11) и семейство параллельных прямых (2.9), то задача определения максимума функции Z сведется к нахождению в допустимой области точки, через которую проходит прямая из семейства Z = const, и которая соответствует наибольшему значению параметра Z. Эта точка существует тогда, когда многоугольник решений не пуст и на нем целевая функция ограничена сверху. При указанных условиях в одной из вершин многоугольника решений целевая функция принимает максимальное значение. Для определения данной вершины построим линию уровня Z =c 1 x1 + c 2 x 2 = 0 , проходящую через начало координат и перпендикулярную вектору С = (с1 ; с 2 ) , и бу- 19 дем передвигать ее в направлении вектора С = (с1 ; с 2 ) до тех пор, пока она не коснется последней крайней (угловой) точки многоугольника решений. Координаты указанной точки и определяет оптимальный план данной задачи. Заканчивая рассмотрение геометрической интерпретации задачи (2.10) – (2.11), отметим, что при нахождении ее решения могут встретиться случаи, изображенные на рис. 2.1 – 2.4. Рис. 2.1 характеризует такой случай, когда целевая функция принимает максимальное значение в единственной точке А. Из рис. 2.2 видно, что максимальное значение целевая функция принимает в любой точке отрезка АВ. На рис. 2.3 изображен случай, когда максимум недостижим, а на рис. 2.4. – случай, когда система ограничений задачи несовместна. Отметим, что нахождение минимального значения Z при данной системе ограничений отличается от нахождения ее максимального значения при тех же ограничениях лишь тем, что линия уровня Z передвигается не в направлении вектора С = (с1 ; с 2 ) , а в противоположном направлении. Таким образом, отмеченные выше случаи, встречающиеся при нахождении максимального значения целевой функции, имеют место и при определении ее минимального значения. Рис. 2.1. Оптимум функции Z достижим в точке А Рис. 2.2. Оптимум функции Z достижим в точке [AB] Рис. 2.3. Оптимум функции Z недостижим Рис. 2.4. Область допустимых значений – пустая область Для практического решения задачи линейного программирования (2.9) – (2.11) на основе ее геометрической интерпретации необходимо следующее: 20 1) Построить прямые, уравнения которых получаются в результате замены в ограничениях (2.10) – (2.11) знаков неравенств на знаки равенств. 2) Найти полуплоскости, определяемые каждым из ограничений. 3) Определить многоугольник решений. 4) Построить вектор С = (с1 ; с 2 ) . 5) Построить прямую Z =c 1 x1 + c 2 x 2 = 0 , проходящую через начало координат и перпендикулярную вектору С . 6) Передвигать прямую Z =c1 x1 + c 2 x 2 в направлении вектора С , в результате чего либо находят точку (точки), в которой функция принимает максимальное значение, либо устанавливают неограниченность функции сверху на множестве планов. 7) Определить точки координаты максимума функции и вычислить значение целевой функции в этой точке. Пример 2.3. Рассмотрим решение задачи об ассортименте продукции (пример 2.2) геометрическим способом. Решение Построим многоугольник решений (рис.2.5). Для этого в системе координат Х 1 0Х 2 на плоскости изобразим граничные прямые: 2 х1 + 3х 2 = 9 3х1 + 2 х 2 = 13 х1 − х 2 = 1 х2 = 2 ( L1 ); ( L2 ); ( L3 ); ( L4 ). Областью решений является многоугольник OABCD. Для построения прямой Z = 2 х1 + 3х 2 = 0 строим вектор-градиент C = (3;4) и через точку 0 проводим прямую, перпендикулярную ему. Построенную прямую Z = 0 перемещаем параллельно самой себе в направлении вектора С . Из рис. следует, что по отношению к многоугольнику решений опорной эта прямая становится в точке C, где функция принимает максимальное значение. Точка С лежит на пересечении прямых L1 и L3 . Для определения ее координат решим систему уравнений: 2 х1 + 3х 2 = 9;   х1 − х 2 = 1. Оптимальный план задачи х1 = 2,4 ; х 2 = 1,4 . Подставляя значения х1 и х 2 в линейную функцию, получим: Z max = 3 ⋅ 2,4 + 4 ⋅ 1,4 = 12,8 . Полученное решение означает, что объем производства продукции П1 должен быть равен 2,4 ед., а продукции П2 – 1,4 ед. Доход, получаемый в этом случае, составит: Z = 12,8 д.е. 21 Рис. 2.5. Решение задачи линейного программирования геометрическим методом Рис. 2.6. Геометрическая интерпретация задачи линейного программирования 2.3 АНАЛИЗ МОДЕЛЕЙ НА ЧУВСТВИТЕЛЬНОСТЬ Анализ моделей на чувствительность – это процесс, реализуемый после получения оптимального решения. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели. В задаче об ассортименте продукции (пример 2.2) может представлять интерес вопрос о том, как повлияет на оптимальное решение увеличение и уменьшение спроса на продукцию или запасов исходного сырья. Возможно, также потребуется анализ влияния рыночных цен на оптимальное решение. При таком анализе всегда рассматривается комплекс линейных оптимизационных моделей. Это придает модели определенную динамичность, позволяющую исследователю проанализировать влияние возможных изменений исходных условий на полученное ранее оптимальное решение. Динамические характеристики моделей фактически отображают аналогичные характеристики, свойственные реальным процессам. Отсутствие методов, позволяющих выявлять влияние возможных изменений параметров модели на оптимальное решение, может привести к тому, что полученное (статическое) решение устареет еще до своей реализации. Для проведения анализа модели на чувствительность с успехом могут быть использованы графические методы. Рассмотрим основные задачи анализа на чувствительность на примере 2.3. Задача 1. Анализ изменений запасов ресурсов После нахождения оптимального решения представляется вполне логичным выяснить, как отразится на оптимальном решении изменение запасов ресурсов. Для этого необходимо ответить на два вопроса: 1) На сколько можно увеличить запас некоторого ресурса для улучшения полученного оптимального значения целевой функции Z? 2) На сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции Z? 22 Прежде чем ответить на поставленные вопросы, классифицируем ограничение линейной модели как связывающие (активные) и несвязывающие (неактивные) ограничения. Прямая, представляющая связывающее ограничение, должна проходить через оптимальную точку, в противном случае, соответствующее ограничение будет несвязываюшим. На рис. 2.5 связывающими ограничениями являются ограничения (1) и (3), представленные прямыми L1 и L3 соответственно, т.е. те, которые определяют запасы исходных ресурсов. Ограничение (1) определяет запасы сырья А. Ограничение (3) определяет соотношение спроса на выпускаемую продукцию. Если некоторое ограничение является связывающим, то соответствующий ресурс относят к разряду дефицитных ресурсов, так как он используется полностью. Ресурс, с которым ассоциировано несвязывающее ограничение, следует отнести к разряду недефицитных ресурсов (т.е. имеющихся в некотором избытке). В нашем примере несвязывающими ограничениями являются (2) и (4). Следовательно, ресурс сырье В - недефицитный, т.е. имеется в избытке, а спрос на продукцию П 2 не будет удовлетворен полностью (в таблице - ресурсы 2 и 4). При анализе модели на чувствительность к правым частям ограничений определяются: 1) предельно допустимое увеличение запаса дефицитного ресурса, позволяющее улучшить найденное оптимальное решение, и 2) предельно допустимое снижение запаса недефицитного ресурса, не изменяющее найденное ранее оптимальное значение целевой функции. В нашем примере сырье А и соотношение спроса на выпускаемую продукцию П1 и П 2 являются дефицитными ресурсами (в таблице - ресурсы 1, 3). Рассмотрим сначала ресурс - сырье А. На рис. 2.7 при увеличении запаса этого ресурса прямая L1 перемещается вверх, параллельно самой себе, до точки К, в которой пересекаются линии ограничений L2 , L3 и L4 . В точке К ограничения (2), (3) и (4) становятся связывающими; оптимальному решению при этом соответствует точка К, а пространством (допустимых) решений становится многоугольник AKD0. В точке К ограничение (1) (для ресурса А) становится избыточным, так как любой дальнейший рост запаса соответствующего ресурса не влияет ни на пространство решений, ни на оптимальное решение. 23 Рис. 2.7. Геометрическая интерпретация решения задачи линейного программирования (изменение ресурса А) Таким образом, объем ресурса А не следует увеличивать сверх того предела, когда соответствующее ему ограничение (1) становится избыточным, т.е. прямая (1) проходит через новую оптимальную точку К. Этот предельный уровень определяется следующим образом. Устанавливаются координаты точки К, в которой пересекаются прямые L2 , L3 и L4 , т.е. находится решение системы уравнений 3x1 + 2 x2 = 13  .  x1 − x2 = 1 x = 2  2 В результате получается x1 = 3 и x 2 = 1. Затем, путем подстановки координат точки К в левую часть ограничения (1), определяется максимально допустимый запас ресурса А: 2 x1 + 3x2 = 2 ⋅ 3 + 3 ⋅ 2 = 12 . Рис. 2.8 иллюстрирует ситуацию, когда рассматривается вопрос об изменении соотношения спроса на продукцию П1 и П 2 . Новой оптимальной точкой становится точка Е, где пересекаются прямые L1 и L2 . Координаты данной точки находятся путем решения системы уравнений (1) и (2) следующим образом: 2 x1 + 3x2 = 9 .  3x1 + 2 x2 = 13 В результате получается x1 = 4,2; x 2 = 0,2, причем суточный спрос на продукцию П1 не должен превышать спрос на продукцию П 2 на величину x1 − x 2 = 4,2 -0,2= = 4 ед. 24 Рис. 2.8. Геометрическая интерпретация решения задачи линейного программирования (изменение спроса на продукцию) Дальнейшее увеличение разрыва в спросе на продукцию П1 и П 2 не будет влиять на оптимальное решение. Рассмотрим вопрос об уменьшении правой части несвязывающих ограничений. Ограничение (4) x 2 ≤ 2 фиксирует предельный уровень спроса на продукцию П 2 . Из рис. 2.5 следует, что, не изменяя оптимального решения, прямую L4 (АВ) можно опускать вниз до пересечения с оптимальной точкой С. Так как точка С имеет координаты x1 = 2,4; x 2 = 1,4 уменьшение спроса на продукцию П 2 до величины x 2 = 1,4 никак не повлияет на оптимальность ранее полученного решения. Рассмотрим ограничение (2) 3x1 + 2 x2 ≤ 13 , которое представляет собой ограничение на недефицитный ресурс - сырье В. И в этом случае правую часть - запасы сырья В - можно уменьшать до тех пор, пока прямая L2 не достигнет точки С. При этом правая часть ограничения (2) станет равной 3x1 + 2 x2 = 3 ⋅ 2,4 + 2 ⋅1,4 = 10 , что позволяет записать это ограничение в виде: 3x1 + 2 x2 ≤ 10 . Этот результат показывает, что ранее полученное оптимальное решение не измените, если суточный запас ресурса В уменьшить на 3 ед. Результаты проведенного анализа можно свести в следующую таблицу: Ресурс Тип ресурса Максимальное изменение запаса ресурса, ед. 1 (А) 2 (В) 3 4 дефицитный недефицитный дефицитный недефицитный 12 – 9 = +3 10 – 13 = -3 4 – 1 = +3 1,4 – 2 = -0,6 Максимальное увеличение дохода от изменения ресурса, у.д.е. 17 – 12,8 = +4,2 12,8 – 12,8 = 0 13,4 – 12,8 = +0,6 12,8 – 12,8 = 0 Задача 2. Определение наиболее выгодного ресурса. В задаче 1 анализа на чувствительность мы исследовали влияние на оптимум увеличения объема дефицитных ресурсов. При ограничениях, связанных с дополни- 25 тельным привлечением ресурсов, естественно задать вопрос: какому из ресурсов следует отдать предпочтение при вложении дополнительных средств? Для этого вводится характеристика ценности каждой дополнительной единицы дефицитного ресурса, выражаемая через соответствующее приращение оптимального значения целевой функции. Такую характеристику для рассматриваемого примера можно получить непосредственно из таблицы, в которой приведены результаты решения задачи 1 на чувствительность. Обозначим ценность дополнительной единицы ресурса i через yi . Величина yi определяется из соотношения yi = максимальное приращение Z . максимально допустимый прирост ресурса i Результаты расчета ценности единицы каждого из ресурсов представлены в следующей таблице: Ресурс i Тип ресурса 1 (А) дефицитный 2 (В) недефицитный 3 дефицитный 4 недефицитный Значение i 1,4 = 1,4 3 =0 −3 0,6 = 0,2 3 =0 − 0,6 Полученные результаты свидетельствуют о том, что дополнительные вложения в первую очередь следует направить на увеличение ресурса А и лишь затем - на формирование соотношения спроса на продукцию П1 и продукцию П 2 . Что касается недефицитных ресурсов, то, как и следовало ожидать, их объем увеличивать не следует. Задача 3. Определение пределов изменения коэффициентов целевой функции. Изменение коэффициентов целевой функции оказывает влияние на наклон прямой, которая представляет эту функцию в принятой системе координат. Вариация коэффициентов целевой функции может привести к изменению совокупности связывающих ограничений и, следовательно, статуса того или иного ресурса (т.е. сделать недефицитный ресурс дефицитным, и наоборот). При анализе модели ни чувствительность к изменениям коэффициентов целевой функции необходимо исследовать следующие вопросы: 1) Каков диапазон изменения того или иного коэффициента целевой функции, при котором не происходят изменения оптимального решения? 2) На сколько следует изменить тот или иной коэффициент целевой функции, чтобы сделать некоторый недефицитный ресурс дефицитным, и, наоборот, дефицитный ресурс сделать недефицитным? Ответим на поставленные вопросы на нашем примере. Рассматривая первый вопрос, обозначим через с1 и с2 доходы предприятия от продажи единицы продукции П1 и П 2 соответственно. Тогда целевую функцию можно представить в следующем виде: 26 Z = c1 x1 + c2 x2 На рис. 2.5 видно, что при увеличении с1 или уменьшении с2 прямая, представляющая целевую функцию Z, вращается (вокруг точки С) по часовой стрелке. Если же с1 уменьшается или с2 увеличивается, эта прямая вращается в противоположном направлении - против часовой стрелки. Таким образом, точка С будет оставаться оптимальной точкой до тех пор, пока наклон прямой не выйдет за пределы, определяемые наклонами прямых для ограничений (1) и (3). Когда наклон прямой Z станет равным наклону прямой L1 , получим две альтернативные оптимальные угловые точки - С и В. Аналогично, если наклон прямой Z станет равным наклону прямой для ограничения (3), будем иметь альтернативные оптимальные угловые точки С и D. Наличие альтернативных оптимумов свидетельствует о том, что одно и то же оптимальное значение Z может достигаться при различных значениях переменных x1 и x 2 . Как только наклон прямой выйдет за пределы указанного выше интервала с1 , получим некоторое новое оптимальное решение. Рассмотрим на нашем примере, каким образом можно найти допустимый интервал изменения с1 , при котором точка С остается оптимальной. Исходное значение коэффициента с2 = 4 оставим неизменным. На рис. 2.3 видно, что значение с1 можно уменьшать до тех пор, пока прямая Z не совпадет с прямой L1 (отрезок ВС). Это крайнее минимальное значение коэффициента с1 можно определить из равенства углов наклонов прямой Z и прямой L1 . Так как тангенс угла наклона для пряс1 2 , а для прямой (1) равен , то минимальное значение с1 определим из 4 3 с1 2 8 равенства = , откуда min c1 = . На рис 2.5 видно, что значение с1 можно увели4 3 3 чивать беспредельно, так как прямая Z при с2 = 4 и c1 → +∞ не совпадает с прямой L3 8 (отрезок DC) и, следовательно, точка С при всех значениях коэффициента с1 ≥ бу3 мой Z равен дет единственной оптимальной. Интервал изменения с1 , в котором точка С по-прежнему остается единственной оптимальной точкой, определяется неравенством 8 8 < c1 < +∞ . При с1 = оптимальны3 3 ми угловыми точками будут как точка С, так и точка В. Как только коэффициент с1 становится меньше 8 , оптимум смещается в точку В. 3 Можно заметить, что, как только коэффициент с1 оказывается меньше 8 , ресурс 3 3 становится недефицитным, а ресурс 4 - дефицитным. Для предприятия это означает следующее; если доход от продажи единицы продукции П1 станет меньше 8 д.е., то 3 наиболее выгодная производственная программа предприятия должна предусматривать выпуск максимально допустимого количества продукции П 2 (полностью удов- 27 летворять спрос на продукцию П 2 ). При этим соотношение спроса на продукцию П1 и П 2 не будет лимитировать объемы производства, что обусловит недефицитность ресурса (3). Увеличение коэффициента с1 свыше 8 д.е. не снимает проблему дефици3 та ресурсов (1) и (3). Точка С - точка пересечения прямых L1 и L3 - остается все время оптимальной. РЕЗЮМЕ Из материала, изложенного в данной лекции, можно сделать следующие выводы. − Оптимизационная задача – это экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений. − Любую задачу линейного программирования можно свести к задаче линейного программирования в канонической форме. − Графически способ решения задач линейного программирования целесообразно использовать для: решения задач с двумя переменными, когда ограничения выражены неравенствами; решения задач со многими переменными при условии, что в их канонической записи содержится не более двух свободных переменных. − Анализ моделей на чувствительность – это процесс, реализуемый после получения оптимального решения. В рамках такого анализа выявляется чувствительность оптимального решения к определенным изменениям исходной модели. При таком анализе всегда рассматривается комплекс линейных оптимизационных моделей. Это придает модели определенную динамичность, позволяющую исследователю проанализировать влияние возможных изменений исходных условий на полученное ранее оптимальное решение. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ 1. Какая задача называется оптимизационной? 2. Приведите математическую модель задачи линейного программирования. 3. Что подразумевается под канонической формой задачи линейного программирования. 4. Поясните графический метод решения задачи линейного программирования. 5. Когда целесообразно применять графический способ решения задачи линейного программирования? 6. Что такое многоугольник решений? 7. Что может являться областью допустимых решений? 8. Перечислите основные задачи анализа на чувствительность. 9. В чем заключается анализ изменений запасов ресурсов? 10. Какие ресурсы называются дефицитными? Недефицитными? 11. Как определить наиболее выгодный ресурс? 12. Как определить пределы изменения коэффициентов целевой функции? 28 3 СИМПЛЕКСНЫЙ МЕТОД 3.1 ГЕОМЕТРИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ СИМПЛЕКСНОГО МЕТОДА Известно, что если задача линейного программирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений системы ограничений. Путь решения любой задачи линейного программирования: перебрать конечное число допустимых базисных решений системы ограничений и выбрать среди них то, на котором функция цели принимает оптимальное решение. Геометрически это соответствует перебору всех угловых точек многогранника решений. Такой перебор в конце концов приведет к оптимальному решению (если оно существует), однако его практическое осуществление связано со значительными трудностями, так как для реальных задач число допустимых базисных решений хотя и конечно, но может быть чрезвычайно велико. Число требуемых перебираемых допустимых базисных решений можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь того, чтобы каждое следующее решение было «лучше» (или, по крайней мере, «не хуже»), чем предыдущее, по значениям линейной функции (увеличение ее при отыскании максимума F → max , уменьшение – при отыскании минимума F → min . Такое перебор позволяет сократить число шагов при отыскании оптимума. Поясним это на графическом примере. Пусть область допустимых решений изображается многоугольником ABCDEGH (Рис. 3.1). Предположим, что его угловая точка А соответствует исходному допустимому базисному решению. При беспорядочном переборе пришлось бы испытать семь допустимых базисных решений, соответствующих семи угловым точкам многоугольника. Однако из чертежа видно, что после вершины А выгодно перейти к соседней вершине В, а затем Рис. 3.1 – к оптимальной точке С. Вместо семи перебрали только три вершины, последовательно улучшая линейную функцию. Идея последовательного улучшения решения легла в основу универсального метода решения задач линейного программирования – симплексного метода. Для реализации симплексного метода необходимо освоить три основных элемента: − способ определения какого-либо первоначального допустимого базисного решения задачи; − правило перехода к лучшему (точнее, не худшему значению); 29 − критерий проверки оптимальности найденного решения. Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду. 3.2 АЛГОРИТМ СИМПЛЕКС-МЕТОДА Для начала работы требуется, чтобы заданная система ограничений выражалась равенствами, причем в этой системе ограничений должны быть выделены базисные неизвестные. Решение задачи при помощи симплекс-метода распадается на ряд шагов. На каждом шаге от данного базиса Б переходят к другому, новому базису Б 1 с таким расчетом, чтобы значение функции Z уменьшалось, т. е. Z Б ≤ Z Б . Для перехо1 да к новому базису из старого базиса удаляется одна из переменных и вместо нее вводится другая из числа свободных. После конечного числа шагов находится некоторый базис Б ( k ) , для которого Z Б есть искомый минимум для линейной функции Z, а со(k ) ответствующее базисное решение является оптимальным либо выясняется, что задача не имеет решения. Рассмотрим систему ограничений и линейную форму вида: a11 x1 + a12 x2 + ... + a1n xn = b1 a x + a x + ... + a x = b  21 1 22 2 2n n 2 ;  ...  a m1 x1 + am 2 x2 + ... + amn xn = bm 3.1 Z min = c0 + c1 x1 + c2 x2 + ... + cn xn ; 3.2 xi ≥ 0 , i = 1, n . 3.3 Используя метод Жордана-Гаусса, приведем записанную систему к виду, где выделены базисные переменные. Введем условные обозначения: x1 , x 2 ,..., xr - базисные переменные; xr +1 , xr + 2 ,..., xn - свободные переменные.  x1 = β1 − (α1r +1 xr +1 + α1r + 2 xr + 2 + ... + α1n xn )  x = β − (α x + α x + ... + α x )  2 2 2 r +1 r +1 2r +2 r +2 2n n ;  ...  xr = β r − (α rr +1 xr +1 + α rr + 2 xr + 2 + ... + α rn xn ) 3.4 Z min = γ 0 − (γ r +1 xr +1 + γ r + 2 xr +1 + ... + γ n xn ) . 3.5 По последней системе ограничений и целевой функции Z построим табл. 3.1. Данная таблица называется симплекс-таблицей. Все дальнейшие преобразования связаны с изменением содержания этой таблицы. 30 Таблица 3.1. Симплекс-таблица Свободные неизвестные Свободный член xr +1 xr +2 x1 x2 β1 β2 α 1r +1 α 2 r +1 α 1r + 2 α 2 r +1 … … … … Базисные неизвестные xr Z min βr γ0 α rr +1 γ r +1 α rr + 2 γ r +2 … … … … … … xn α 1n α 2n … α rn γn Алгоритм симплекс-метода сводится к следующему. 1. В последней строке симплекс-таблицы находят наименьший положительный элемент, не считая свободного члена. Столбец, соответствующий этому элементу, считается разрешающим. 2. Вычисляют отношение свободных членов к положительным элементам разрешающего столбца (симплекс-отношение). Находят наименьшее из этих симплексотношений, оно соответствует разрешающей строке. 3. На пересечении разрешающей строки и разрешающего столбца находится разрешающий элемент. 4. Если имеется несколько одинаковых по величине симплекс-отношений, то выбирают любое из них. То же самое относится к положительным элементам последней строки симплекс-таблицы. 5. После нахождения разрешающего элемента переходят к следующей таблице. Неизвестные переменные, соответствующие разрешающей строке и столбцу, меняют местами. При этом базисная переменная становится свободной переменной и наоборот. Симплекс-таблица преобразована следующим образом (табл. 3.2). 6. Элемент табл. 3.2, соответствующий разрешающему элементу табл. 3.1, равен обратной величине разрешающего элемента. 7. Элементы строки табл. 3.2, соответствующие элементам разрешающей строки табл. 3.1, получаются путем деления соответствующих элементов табл. 3.1 на разрешающий элемент, 8. Элементы столбца табл. 3.2, соответствующие элементам разрешающего столбца табл. 3.1, получаются путем деления соответствующих элементов табл. 3.1 на разрешающий элемент и берутся с противоположным знаком. 9. Остальные элементы вычисляются по правилу прямоугольника: мысленно вычерчиваем прямоугольник в табл. 3.1, одна вершина которого совпадает с разрешающим элементом, а другая - с элементом, образ которого мы ищем; остальные две вершины определяются однозначно. Тогда искомый элемент из табл. 3.2 будет равен соответствующему элементу табл. 3.1 минус дробь, в знаменателе которой стоит разрешающий элемент, а в числителе - произведение элементов из двух неиспользованных вершин прямоугольника. 31 10. Как только получится таблица, в которой в последней строке все элементы отрицательны, считается, что минимум найден. Минимальное значение функции равно свободному члену в строке целевой функции, а оптимальное решение определяется свободными членами при базисных переменных. Все свободные переменные в этом случае равны нулю. 11. Если в разрешающем столбце все элементы отрицательны, то задача не имеет решений (минимум не достигается). Таблица 3.2. Преобразование симплекс-таблицы Свободные неизвестные Базисные неизвестные xr +2 Свободный член xr +1 x1 β1 α 1r + 2 α 1r +1 α 2 r +2 1 x2 … … … xr Z min α 1r + 2 α − 2 r +2 α 1r + 2 … α rr + 2 α 1r + 2 γ − r+2 α 1r + 2 − … xn … α 1n α 1r + 2 … … … … … Пример. Решение задачи симплекс-методом: − x1 + x2 + x3 = 1   x1 − x2 + x4 = 1 ; x + x + x = 2 5  1 2 Z max = 2 x1 − x2 + 3 x3 − 2 x4 + x5 . Приведем задачу к виду, допускающему применение симплекс-алгоритма: x3 = 1 − (− x1 + x2 ); x4 = 1 − ( x1 − x2 ); x5 = 2 − ( x1 + x2 ). Подставим в выражение Z max величины x3 , x 4 , x5 : Z max = 6 x1 − 7 x2 + 3 . По алгоритму целевая функция должна стремиться к минимуму: Z min = − Z max = −6 x1 + 7 x2 − 3 = −3 − (6 x1 − 7 x2 ) . Составим симплекс-таблицу: 32 Свободные неизвестные Базисные неизвестные Свободный член x4 x2 1 -1 1 1 -1 1 6 1 x3 x1 x5 Z min 1 2 -3 -7 Разыскиваем в последней строке наименьший положительный элемент, в нашем примере он равен +6, первый столбец коэффициентов будет разрешающим. Определим отношение свободных членов к положительным элементам разрешающего столбца. Минимальное симплекс-отношение равно 1. Разрешающий элемент находится на пересечении строки переменной x 4 и столбца - x1 . Переходим к следующей таблице, используя правило прямоугольника: Свободные неизвестные Базисные неизвестные Свободный член x1 x2 2 1 1 1 -1 1 -1 2 -9 -6 -1 x3 x4 x5 Z min В последней строке нет положительных элементов, следовательно, оптимальное решение найдено: Z min = −9 ; X = (1; 0; 2, 0, 1); Z max = − Z min = 9 . РЕЗЮМЕ Из материала, изложенного в данной лекции, можно сделать следующие выводы. − Если задача линейного программирования имеет оптимальное решение, то оно соответствует хотя бы одной угловой точке многогранника решений и совпадает, по крайней мере, с одним из допустимых базисных решений системы ограничений. − Симплекс-метод является универсальным методом решения задач линейного программирования. − В основу симплексного метода легла идея последовательного улучшения решения. − Для использования симплексного метода задача линейного программирования должна быть приведена к каноническому виду. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ 1. 2. 3. 4. Дайте определение симплекс-метода. Дайте геометрическую интерпретацию симплекс-метода. Что легло в основу симплекс-метода? Расскажите алгоритм симплекс-метода. 33 4 ДВОЙСТВЕННЫЕ ЗАДАЧИ Каждой задаче линейного программирования соответствует другая задача, называемая двойственной или сопряженной по отношению к исходной. Теория двойственности оказалась полезной для проведения качественных исследований задач линейного программирования. 4.1 ЭКОНОМИЧЕСКАЯ ИНТЕРПРЕТАЦИЯ ЗАДАЧИ, ДВОЙСТВЕННОЙ ЗАДАЧЕ ОБ ИСПОЛЬЗОВАНИИ РЕСУРСОВ Выше рассмотрена задача об использовании ресурсов. В приведенной модели bi ( i = 1,2,..., m ) обозначает запас ресурса S i ; aij - число единиц ресурса S i , потребляемого при производстве единицы продукции Pj ( j = 1,2,..., n ); c j - прибыль (выручка) от реализации единицы продукции Pj (или цена продукции Pj ). Предположим, что некоторая организация решила закупить ресурсы S1 , S 2 ,..., S m предприятия и необходимо установить оптимальные цены на эти ресурсы y1 , y 2 ,..., y m . Очевидно, что покупающая организация заинтересована в том, чтобы затраты на все ресурсы Z в количествах b1 , b2 ,..., bm по ценам соответственно y1 , y 2 ,..., y m были минимальны, т.е. Z = b1 y1 + b2 y 2 + ... + bm y m → min . С другой стороны, предприятие, продающее ресурсы, заинтересовано в том, чтобы полученная выручка была не менее той суммы, которую предприятие может получить при переработке ресурсов в готовую продукцию. На изготовление единицы продукции P1 расходуется a11 единиц ресурса S1 , a21 единиц ресурса S 2 , …, ai1 единиц ресурса S i , …, am1 единиц ресурса S m по цене соответственно y1 , y 2 ,..., yi ,..., y m . Поэтому для удовлетворения требований продавца затраты на ресурсы, потребляемые при изготовлении единицы продукции P1 , должны быть не менее ее цены c1 , т.е. a11 y1 + a21 y 2 + ... + am1 y m ≥ c1 . Аналогично можно составить ограничения в виде неравенств по каждому виду продукции P1 , P2 ,..., Pn . Экономико-математическая модель и содержательная интерпретация полученной таким образом двойственной задачи II приведена в правой части Табл. 4.1. Цены ресурсов y1 , y 2 ,..., y m в экономической литературе получили различные названия: учетные, неявные, теневые. Смысл этих названий состоит в том, что это условные, «ненастоящие» цены. В отличие от «внешних» цен c1 , c 2 ,..., cn на продукцию, известных, как правило, до начала производства, цены ресурсы y1 , y 2 ,..., y m являются внутренними, т.к. они задаются не извне, а определяются непосредственно в результате решения задачи, поэтому их часто называют оценками ресурсов. 34 Табл. 4.1 Задача I (исходная) Задача II (двойственная) F = c1 x1 + c2 x2 + ... + cn xn → max 4.1 Z = b1 y1 + b2 y 2 + ... + bm y m → min при ограничениях: при ограничениях: a11 x1 + a12 x 2 + ... + a1n x n ≤ b1 a x + a x + ... + a x ≤ b  21 1 22 2 2n n 2  ....................................... a m1 x1 + a m 2 x 2 + ... + a mn x n ≤ bm1 a11 y + a 21 y 2 + ... + a m1 y n ≥ c1 a y + a y + ... + a y ≥ c  12 1 22 2 m2 2 2  ....................................... a1n y1 + a 2 n y 2 + ... + a mn y m ≥ cn и условии неотрицательности: x1 ≥ 0 , x2 ≥ 0 ,…, x n ≥ 0 Составить 4.2 4.3 такой план выпуска продукции X = ( x1 , x2 ,..., xn ) , при котором прибыль (выручка) от реализации продукции будет максимальной при условии, что потребление ресурсов по каждому виду продукции не превзойдет имеющихся запасов. и условии неотрицательности: y1 ≥ 0 , y 2 ≥ 0 ,…, y n ≥ 0 Найти Y 4.4 4.5 4.6 такой набор цен (оценок) ресурсов = ( y1 , y 2 ,..., y m ) , при котором общие затраты на ресурсы будут минимальными при условии, что затраты на ресурсы при производстве каждого вида продукции будут не менее прибыли (выручки) от реализации этой продукции. 4.2 ВЗАИМНО-ДВОЙСТВЕННЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ И ИХ СВОЙСТВА Рассмотрим формально две задачи I и II линейного программирования, представленные в Табл. 4.1, абстрагируясь от содержательной интерпретации параметров, входящих в их экономико-математические модели. Обе задачи обладают следующими свойствами: 1. В одной задаче ищут максимум линейной функции, в другой – минимум. 2. Коэффициенты при переменных в линейной функции одной задачи являются свободными членами системы ограничений в другой. 3. Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида ≤ , а в задачи минимизации – все неравенства вида ≥ . 4. Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг к другу:  a11  a для задачи I A =  21 ...  a  m1  a11  a для задачи II AT =  12 ...  a  1n a12 a 22 ... am 2 a21 a 22 ... a2n ... a1n   ... a 2 n  , ... ...   ... a mn  ... a m1   ... a m 2  , ... ...   ... a mn  5. Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче. 6. Условия неотрицательности переменных имеются в обеих задачах. Две задачи I и II линейного программирования, обладающие указанными свойствами, называются симметричными взаимно двойственными задачами. 35 Исходя из определения, можно предложить следующий алгоритм составления двойственной задачи. 1. Привести все неравенства системы ограничений исходной задачи к одному смыслу: если в исходной задаче ищут максимум линейной функции, то все неравенства системы ограничений привести к виду ≤ , а если минимум – к виду ≥ . Для этого неравенства, в которых данное требование не выполняется, умножить на –1. 2. Составить расширенную матрицу системы A1 , в которую включить матрицу коэффициентов при переменных A , столбец свободных членов системы ограничений и строку коэффициентов при переменных в линейной функции. 3. Найти матрицу A1T , транспонированную к матрице A1 . 4. Сформулировать двойственную задачу на основании полученной матрицы A1T и условия неотрицательности переменных. Пример. Составить задачу, двойственную следующей задаче: F = − x1 + 2 x2 → max при ограничениях: 2 x1 − x2 ≥ 1 − x + 4 x ≤ 24  1 2   x1 − x2 ≤ 3  x1 + x2 ≥ 5 x1 ≥ 0 , x2 ≥ 0 . Решение. 1. Так как исходная задача на максимизацию, то приведем все неравенства системы ограничений к виду ≤ , для чего обе части первого и четвертого неравенства умножим на -1. Получим: − 2 x1 + x2 ≤ −1 − x + 4 x ≤ 24  1 2 .  x − x ≤ 3 1 2  − x1 − x2 ≤ −5 2. Составим расширенную матрицу системы  − 2 1 −1    − 1 4 24  A1 =  1 − 1 3     −1 −1 − 5  −1 2 F    3. Найдем матрицу A1T , транспонированную к матрице A1 . A1T  − 2 − 1 1 − 1 − 1   = 1 4 −1 −1 2   − 1 24 3 − 5 Z    36 4. Сформулируем двойственную задачу: Z = − y1 + 24 y 2 + 3 y3 − 5 y 4 → min при ограничениях: − 2 y1 − y 2 + y3 − y 4 ≥ −1   y1 + 4 y 2 − y3 − y 4 ≥ 2 y1 ≥ 0 , y 2 ≥ 0 , y3 ≥ 0 , y 4 ≥ 0 . 4.3 ТЕОРЕМЫ ДВОЙСТВЕННОСТИ Связь между оптимальными решениями двойственных задач устанавливается с помощью теорем двойственности. Основное неравенство теории двойственности. Пусть имеется пара двойственных задач I и Для любых решений X = (x1 , x2 ,..., xn ) и Y = ( y1 , y 2 ,..., y m ) исходной и двойственной задачи справедливо неравенство F ( X ) ≤ Z (Y ) или n m j =1 i =1 ∑ c j x j ≤ ∑ bi y i Достаточный признак оптимальности. ( ) ( 4.7 ) Если X * = x1* , x 2* ,..., x n* и Y * = y1* , y 2* ,..., y m* – допустимые решения взаимно двойственных задач, для которых выполняется равенство ( ) ( ) F X* = Z Y* 4.8 то X * – оптимальное решение исходной задачи I, а Y * – двойственной задачи II. Первая (основная) теорема двойственности. Если одна из взаимно двойственных задач имеет оптимальное решение, то его имеет и другая, причем оптимальное значение их линейных функций равны. ( ) ( ) Fmax = Z min или F X * = Z Y * 4.9 Если линейная функция одной из задач не ограничена, то условия другой противоречивы. Экономический смысл первой (основной) теоремы двойственности. План ( производства ) ( X * = x1* , x 2* ,..., x n* ) и набор цен (оценок) ресурсов * Y * = y1* , y 2* ,..., y m оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная при «внешних» (известных заранее) ценах c1 , c 2 ,..., cn равна затратам на ресурсы по «внутренним» (определяемым только из решения задачи) ценам y1 , y 2 ,..., y m . Для всех же других планов X и Y обеих задач в соответствие с основным неравенством 4.7 теории двойственности прибыль (выручка) от продукции всегда меньше (или равна) затрат на ресурсы. Экономический смысл первой теоремы двойственности можно интерпретировать и так: предприятию безразлично, производить ли продукцию по оптимальному плану X * = x1* , x 2* ,..., x n* и получить максимальную прибыль (выручку) Fmax либо ( ) 37 ( ) продавать ресурсы по оптимальным ценам Y * = y1* , y 2* ,..., y m* и возместить от продажи равные ей минимальные затраты на ресурсы Z min . Для второй теоремы двойственности Пусть даны две взаимно двойственные задачи I и II (см. Табл. 4.1). если каждую из этих задач решать симплекс-методом, то необходимо привести их к каноническому виду, для чего в систему ограничений 4.2 задачи I следует ввести m неотрицательных переменных x n +1 , x n+ 2 ,...., x n +i ,..., x n + m , а в систему ограничений 4.5 задачи II – n неотрицательных переменных y m +1 , y m + 2 ,...., y m + j ,..., y n + m , где i(j) – номер неравенства, в которое введена дополнительная переменная x n +i ≥ 0 ( y m + j ≥ 0 ). Системы ограничений каждой из взаимно двойственных задач примут вид: n ∑ a ji x j + x n+i = bi , i = 1,2,..., m 4.10 j =1 m ∑ a ji y i − y m+ j = c j , j = 1,2,..., n 4.11 i =1 Установим соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи (Табл. 4.2). Табл. 4.2 Переменные исходной задачи I Дополнительные Первоначальные x1 x2 ... xj ... xn x n +1 x n+ 2 b b ... b ... b b b ... b ... b y m+1 y m+2 y1 y2 ... yj ... ym ... y m + j Дополнительные ... y m+ n ... x n + j ... x n + m 4.12 Переменные Переменные двойственной задачи II Теорема: Положительным (ненулевым) компонентам оптимального решения одной из взаимно двойственных задач соответствуют нулевые компоненты оптимального решения другой задачи, т.е. для любых i = 1,2,..., m и j = 1,2,..., n : если x *j > 0 , то * * * * * ym + j = 0 ; если x n +i > 0 , то y i = 0 , и аналогично, если y i > 0 , то x n +i = 0 ; если * * ym + j > 0 , то x j = 0 . Из теоремы следует важный вывод о том, что введенное ранее соответствие 4.12 между переменными взаимно двойственных задач при достижении оптимума (т.е. на последнем шаге решения каждой задачи симплексным методом) представляет соответствие между основными (как правило, не равными нулю) переменными одной из двойственных задач и неосновными (равными нулю) переменными другой задачи, когда они образуют допустимые базисные решения. Вторая теорема двойственности. Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции исходной задачи, выраженной через неосновные переменные ее оптимального решения. 38 РЕЗЮМЕ Из материала, изложенного в данной лекции, можно сделать следующие выводы. − Каждой задаче линейного программирования соответствует другая задача, называемая двойственной или сопряженной по отношению к исходной. − Связь между оптимальными решениями двойственных задач устанавливается с помощью теорем двойственности − Метод, при котором вначале симплексным методом решается двойственная задача, а затем оптимум и оптимальное решение исходной задачи находятся с помощью теорем двойственности, называется двойственным симплексным методом. Этот метод бывает выгодно применять, когда первое базисное решение исходной задачи недопустимое или, например, когда число ее ограничений m больше числа переменных n. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ 1. Какая задача называется двойственной? 2. Дайте экономическую интерпретацию задачи, двойственной задаче об использовании ресурсов. 3. Приведите пример взаимно-двойственных задач линейного программирования. 4. Какие свойства присущи взаимно-двойственным задачам линейного программирования? 5. Сформулируйте основное неравенство теории двойственности. 6. Сформулируйте первую (основную) теорему двойственности. 7. В чем заключается экономический смысл первой (основной) теоремы двойственности? 8. Сформулируйте вторую теорему двойственности. 39 5 ЦЕЛОЧИСЛЕННЫЕ МОДЕЛИ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ Целочисленное программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные должны принимать только целочисленные значения. Задача называется полностью целочисленной, если условие целочисленности наложено на все ее переменные; когда это условие относится лишь к некоторым переменным, задача называется частично целочисленной. Если при этом целевая функция и функции, входящие в ограничения, линейные, то задача является линейной целочисленной. Несмотря на то, что к настоящему времени разработан ряд методов решения целочисленных задач, ни один из них не обеспечивает желаемой эффективности соответствующих вычислительных процедур, что особенно проявляется при увеличении размерности задачи. Таким образом, в отличие от задач линейного программирования, время решения которых относительно невелико, реализация целочисленных алгоритмов в ряде случаев весьма затруднительна. Одна из основных трудностей в целочисленном программировании связана с эффектом ошибки округления, возникающим при использовании цифровых ЭВМ. Даже наличие алгоритмов, применимых для решения задач с целочисленными коэффициентами и позволяющих обойтись без оперирования дробями (и, следовательно, избежать влияния ошибок округления), не упрощает ситуации, поскольку такие алгоритмы (в ряде случаев) сходятся чрезвычайно медленно. Методы решения задач целочисленного программирования можно классифицировать как (1) методы отсечений и (2) комбинаторные методы. Исходной задачей для демонстрации возможностей методов отсечений, используемых при решении линейных целочисленных задач, является задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. По мере введения специальных дополнительных ограничений, учитывающих требование целочисленности, многогранник допустимых решений ослабленной задачи постепенно деформируется/до тех пор, пока координаты оптимального решения не станут целочисленными. Название «методы отсечений» связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают (исключают) некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами. В основе комбинаторных методов лежит идея перебора всех допустимых целочисленных решений. Разумеется, на первый план здесь выдвигается проблема разработки тестовых процедур, позволяющих непосредственно рассматривать лишь (относительно небольшую) часть указанных решений, а остальные допустимые решения учитывать некоторым косвенным образом. Наиболее известным комбинаторным методом является метод ветвей и границ, который также опирается на процедуру решения задачи с ослабленными ограничениями. При таком подходе из рассматриваемой задачи получаются две подзадачи путем специального «разбиения» пространства решений и отбрасывания областей, не содержащих допустимых целочисленных решений. 40 В случае, когда целочисленные переменные являются булевыми, применяются комбинированные методы. Булевы свойства переменных существенно упрощают поиск решения. Рассматриваемый в данном разделе метод ветвей и границ решения задачи целочисленного программирования также опирается на решение задачи с ослабленными ограничениями. Метод ветвей и границ непосредственно применим как к полностью, так и к частично целочисленным задачам. Согласно общей идее метода, сначала решается задача с ослабленными ограничениями (задача линейного программирования). Пусть x r – целочисленная переменная, значение x r* которой в оптимальном решении ослабленной задачи является дробным. Интервал [x r* ] < x r < [x r* ] + 1 не содержит допустимых целочисленных компонент решения. Поэтому допустимое целое значение x r должно удовлетворять одному из неравенств x r > [x r* ] или x r ≤ [x r* ] + 1 . Введение этих условий в задачу с ослабленными ограничениями порождает две не связанные между собой задачи. В таком случае говорят, что исходная задача разветвляется (или разбивается) на две подзадачи. Осуществляемый в процессе ветвления учет необходимых условий целочисленности позволяет исключить части многогранника допустимых решений, не содержащие точек с целыми координатами. Затем каждая подзадача решается как задача линейного программирования (с целевой функцией исходной задачи). Если полученный оптимум оказывается допустимым для целочисленной задачи, такое решение следует зафиксировать как наилучшее. При этом нет необходимости продолжать «ветвление» подзадачи, поскольку улучшить полученное решение, очевидно, не удастся. В противном случае подзадача, в свою очередь, должна быть разбита на две подзадачи опять при учете условия целочисленности переменных, значения которых в оптимальном решении не являются целыми. Разумеется, как только полученное допустимое целочисленное решение одной из подзадач оказывается лучше имеющегося, оно фиксируется вместо зафиксированного ранее. Процесс ветвления продолжается, насколько это возможно, до тех пор, пока каждая подзадача не приведет к целочисленному решению или пока не будет установлена невозможность улучшения имеющегося решения. В этом случае зафиксированное допустимое решение является оптимальным. Эффективность вычислительной схемы метода можно повысить, введя в рассмотрение понятие границы, на основе которого делается вывод о необходимости дальнейшего разбиения каждой из подзадач. Если оптимальное решение подзадачи с ослабленными ограничениями обеспечивает худшее значение целевой функции, чем имеющееся решение, эту подзадачу далее рассматривать не следует. В таких случаях говорят, что подзадача прозондирована, и ее можно вычеркнуть из списка подзадач, порожденных исходной задачей. Иными словами, как только получено допустимое целочисленное решение некоторой подзадачи, целочисленное решение некоторой подзадачи, соответствующее значение целевой функции может быть использовано в качестве (верхней в случае минимизации и нижней в случае максимизации) границы, наличие которой позволяет формализовать процедуру исключения прозондированных подзадач. Рассмотрим задачу целочисленного линейного программирования (ЗЦЛП): 41 Найти вектор x ∈ E n , максимизирующий линейную форму () n f x = ∑c j x j 5.1 j =1 и удовлетворяющий условиям: n ∑a j =1 ij x j = bi , i = 1, m 5.2 x j ≥ 0 , j = 1, n 5.3 x1 , x 2 ,..., x p – целые ( p ≤ n ) 5.4 Пусть, для каждой целочисленной переменной можно указать верхнюю и нижнюю границы, в пределах которых безусловно содержатся ее оптимальные значения, то есть V j ≤ x j ≤ W j ; j = 1.. p 5.5 При этом в систему функциональных ограничений необходимо включить р неравенств (5.5). В начале любой S-й итерации метода ветвей и границ необходимо иметь: 1) Основной список задач линейного программирования, каждая из которых должна быть решена в последующих итерациях (на первой итерации список содержит одну ЗЛП - задачу 1 (5.1- 5.3) и (5.5). 2) Нижнюю границу оптимального значения линейной формы задачи (5.1) (5.3), (5.5) Z 0( S ) . На первой итерации в качестве Z 0(1) можно взять значение функции () f x в любой целочисленной точке x , лежащей внутри области (5.2) - (5.5). Если та- кую точку указать трудно, то можно положить Z 0(1) = −∞ , но это приводит к значительному увеличению числа итераций. Алгоритм S-й итерации метода ветвей и границ Пусть в результате S итераций метода получили список из Z задач: 1,2,...,Z и имеем Z 0( S ) . Шаг 1. Выбираем из списка ЗЛП одну задачу для решения, задачу R ( 1 ≤ R ≤ Z ) и решаем ее. (S ) Шаг 2. Если задача R имеет решение x R , то переходим к шагу 3. В противном случае – исключаем задачу R из списка и, полагая Z 0( S +1) = Z 0( S ) , возвращаемся к шагу 1. При S = 0, то есть на первой итерации, делаем вывод, что исходная задача (5.1)-(5.4) не имеет решения и процесс решения заканчивается. ( ) (S ) Шаг 3. Если f x R > Z 0( S ) , то переходим к шагу 4. В противном случае – задачу R исключаем из списка и, полагая Z 0( S +1) = Z 0( S ) , возвращаемся к шагу 1. (S ) Шаг 4. Если не все компоненты вектора x R удовлетворяют условиям целочисленности (3.4), то переходим к шагу 5. В противном случае – задачу R из списка ис(S ) (S ) ключаем, план x R запоминаем и, полагая Z 0( S +1) = x R , возвращаемся к шагу 1. При S = 0 вектор х является решением и исходной задачи и процесс решения заканчивается. 42 Шаг 5. Задачу R выбрасываем из списка, включая в него две новые задачи линейного программирования – задачу (Z+1) и задачу (Z+2). Далее, полагая Z 0( S +1) = Z 0( S ) , возвращаемся к шагу 1. Процесс разбиения задачи R на две новые ЗЛП осуществляет(S ) ся следующим образом: Пусть x j – дробная компонента в полученном оптимальном (S ) [ ] ее целая часть. Тогда задача Z+1 имеет вид: (S ) плане x R и x R () n f x = ∑ c j x j → max j =1 при условиях n ∑a j =1 ij x j = bi , i = 1, m V1 ≤ x1 ≤ W1 ………………………… [ ] (S ) V j ≤x j ≤ x R ………………………… Vp ≤x p ≤ Wp x1 , x 2 ,..., x n ≥ 0 Задача Z+2: () n f x = ∑ c j x j → max j =1 при условиях n ∑a j =1 ij x j = bi , i = 1, m V1 ≤ x1 ≤ W1 ………………………… [x ]+ 1 ≤ x ≤ W (S ) R j j ………………………… Vp ≤x p ≤ Wp x1 , x 2 ,..., x n ≥ 0 Процесс решения продолжаем до тех пор, пока не будут решены все задачи линейного программирования из списка. Тогда решением задачи (5.1)-(5.5) будет Z 0( S ) на последней итерации. РЕЗЮМЕ Из материала, изложенного в данной лекции, можно сделать следующие выводы. − Целочисленное программирование ориентировано на решение задач математического программирования, в которых все или некоторые переменные должны принимать только целочисленные значения. − Одна из основных трудностей в целочисленном программировании связана с эффектом ошибки округления. 43 − Методы решения задач целочисленного программирования можно классифицировать как методы отсечений и комбинаторные методы. − Название «методы отсечений» связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают (исключают) некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами. − В основе комбинаторных методов лежит идея перебора всех допустимых целочисленных решений. − Наиболее известным комбинаторным методом является метод ветвей и границ, который также опирается на процедуру решения задачи с ослабленными ограничениями. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ 1. 2. 3. 4. 5. 6. 7. Какая задача называется полностью целочисленной? Какая задача называется частично целочисленной? С чем связана основная трудность в целочисленном программировании? Дайте характеристику методов отсечения. Дайте характеристику комбинаторных методов. Что такое метод ветвей и границ? Приведите алгоритм решения задачи методом ветвей и границ.. 44 ТРАНСПОРТНЫЕ ЗАДАЧИ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ 6 Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. 6.1 ПОСТАНОВКА ЗАДАЧИ Под термином «транспортная задача» понимается широкий круг задач не только транспортного характера, которые характеризуются единой математической моделью. Общим для них является, как правило, распределение ресурсов, находящихся у m производителей (поставщиков), по n потребителям этих ресурсов. Наиболее часто встречаются следующие задачи, относящиеся к транспортным: − − − − − прикрепление потребителей ресурса к производителям; привязка пунктов отправления к пунктам назначения; взаимная привязка грузопотоков прямого и обратного направлений; отдельные задачи оптимальной загрузки промышленного оборудования; оптимальное распределение объемов выпуска промышленной продукции между заводами-изготовителями и др. Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени). Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется «перевалочный пункт», например – склад. Рассмотрим экономико-математическую модель прикрепления пунктов отправления к пунктам назначения. Имеются m пунктов отправления груза и объемы отправления по каждому пункту a1 , a 2 ,..., a m . Известна потребность в грузах b1 , b2 ,..., bn по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту сij , i = 1, m , j = 1, n . Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого i-го пункта отправления (от поставщика) в каждый j-ый пункт назначения (до потребителя) xij с минимальными транспортными издержками. В общем виде исходные данные представлены в Таблица 6.1. Строки транспортной таблицы соответствуют пунктам отправления (в последней клетке каждой строки указан объем запаса продукта ai ), а столбцы – пунктам назначения (последняя клетка каждого столбца содержит значение потребности b j ). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в правом верхнем углу находится цена перевозки еди- 45 ницы продукта, а в левом нижнем – значение объема перевозимого груза для данных пунктов. Таблица 6.1. Исходные данные Потребители B1 Поставщики B2 c11 A1 x11 x 21 … … cm 2 … … xm 2 b1 c2n x2n c m1 Потребность … x 22 x m1 c1n a1 x1n c 22 … Am … x12 c 21 A2 Bn … c12 Запасы (объемы отправления) … b2 … c mn x mn … a2 am bn Транспортная задача называется закрытой, если суммарный объем отправляе  m мых грузов  ∑ ai  равен суммарному объему потребности в этих грузах по пунктам  i =1   n  назначения  ∑ b j  :  j =1  m n i =1 j =1 ∑ ai = ∑ b j 6.1 Если такого равенства нет (потребности выше запасов или наоборот), запасу называют открытой, т.е.: m n ∑ a ≠ ∑b i =1 i j =1 j 6.2 Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза (a > b) , либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены (a < b) . Для написания модели необходимо все условия (ограничения) и целевую функцию представить в виде математических уравнений. Все грузы из i-х пунктов должны быть отправлены, т.е.: n ∑x j =1 ij = ai , i = 1, m 6.3 Все j-е пункты (потребители) должны быть обеспечены грузами в плановом объеме: 46 m ∑x i =1 ij = b j , j = 1, n 6.4 Суммарные объемы отправления должны равняться суммарным объемам назначения (6.1). Должно выполняться условие неотрицательности переменных: xij ≥ 0 , i = 1, m , j = 1, n . Перевозки необходимо осуществить с минимальными транспортными издержками (функция цели): m n Z min = ∑∑ cij xij 6.5 i =1 j =1 Будем называть любой план перевозок допустимым, если он удовлетворяет системам ограничений и требованием неотрицательности. Допустимый план, будем называть опорным, если в нем отличны от нуля не более m+n-1 базисных перевозок, а остальные перевозки равны 0. План будет называться оптимальным, если он, среди всех допустимых планов, приводит к максимальной суммарной стоимости перевозок. Вместо матрицы стоимостей перевозок ( cij ) могут задаваться матрицы расстояний. В таком случае в качестве целевой функции рассматривается минимум суммарной транспортной работы. Как видно из выражения (6.1), уравнение баланса является обязательным условием решения транспортной задачи. Поэтому, когда в исходных условиях дана открытая задача, то ее необходимо привести к закрытой форме. В случае, если − потребности по пунктам назначения превышают запасы пунктов отправления, то вводится фиктивный поставщик с недостающим объемом отправления; − запасы поставщиков превышают потребности потребителей, то вводится фиктивный потребитель с необходимым объемом потребления. Варианты, связывающие фиктивные пункты с реальными, имеют нулевые оценки. После введения фиктивных пунктов задача решается как закрытая. Транспортным задачам присущи следующие особенности: − − − − − распределению подлежат однородные ресурсы; условия задачи описываются только уравнениями; все переменные выражаются в одинаковых единицах измерения; во всех уравнениях коэффициенты при неизвестных равны единице; каждая неизвестная встречается только в двух уравнениях системы ограничений. 6.2 МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ Решение транспортной задачи включает два этапа: − Определение опорного плана; − Нахождение оптимального решения, путем последовательных операций. Для транспортной задачи существует несколько методов отыскания начального плана (опорного решения): 47 1) 2) 3) 4) метод северо-западного угла (диагональный); метод минимальной стоимости (метод наименьшего элемента); метод Фогеля; метод двойного предпочтения. Существует два метода нахождения оптимального решения транспортной задачи: 1) распределительный метод 2) метод потенциалов 6.3 АЛГОРИТМ МЕТОДА ПОТЕНЦИАЛОВ Наиболее распространенным методом решения транспортных задач является метод потенциалов. Впервые он был предложен в 1949г. Л. В. Канторовичем и М. К. Гавуриным. Позже на базе общих идей линейного программирования аналогичный метод был предложен Дж. Данцигом. Решение задачи методом потенциалов включает следующие этапы: разработку начального плана (опорного решения); расчет потенциалов; проверку плана на оптимальность; поиск максимального звена неоптимальности (если условие п не было достигнуто); 5) составление контура перераспределения ресурсов; 6) определение минимального элемента в контуре перераспределения и перераспределение ресурсов по контуру; 7) получение нового плана. 1) 2) 3) 4) Описанная процедура повторяется несколько раз (итераций), пока не будет найдено оптимальное решений. Вычислительный алгоритм для каждой итерации не меняется. рассмотрим на примере решения задачи прикрепления пунктов отправления i = 1,3 к пунктам назначения j = 1,4 . Исходные данные задачи приведены в табл. 6.2. Таблица 6.2. Исходные данные Потребители B1 Поставщики A1 1 A2 4 A3 Потребность 40 B2 B3 B4 2 3 3 2 4 2 60 2 80 1 60 Запасы (объемы отправления) 60 80 100 240 Начальный план можно составим, воспользовавшись наиболее простым способом – методом северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к 48 попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются ai(q ) , а текущих неудовлетворенных потребностей – b (jq ) . Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего угла транспортной таблицы, при этом полагаем ai(0 ) = ai , b (j0 ) = b j . Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: xi , j = min{ai(q ) , b (jq ) }. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину: ai(q +1) = ai(q ) − xi , j , b (jq +1) = b (jq ) − xi , j Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: ai(q +1) = 0 или b (jq +1) = 0 . Если справедливо первое, то это означает, что весь запас i-ro пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i + 1, т. е. переместиться к следующей клетке вниз по столбцу. Если же b (jq +1) = 0 , то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции. Основываясь на условии баланса запасов и потребностей (3.1), нетрудно доказать, что за конечное число шагов мы получим допустимый план. По указанному правилу загружаем первую клетку (i – j) = (1 – 1): x11 = min{a1 ; b1 } = min{60;40} = 40 . Таким образом, первый пункт назначения загружен, а первый пункт отправления имеет остатки груза ∆a1 = 60 − 40 = 20 , которые и распределяем на второй пункт назначения: x12 = min{∆a1 ; b2 } = min{20;60} = 20 ; ∆b2 = 40 . Продолжая преобразования аналогичным образом, получаем: x 22 = min{a 2 ; ∆b2 } = min{80;40} = 40 ; ∆a 2 = 40 и т.д. Результаты начального плана и расчета потенциалов представлены в табл. 6.3. Таблица 6.3. Начальный план перевозок Потребители B1 B2 Поставщики A1 1 A3 Потребность βj 2 4 З ⊕ 40 1 B4 3 4 2 20 З Р 40 A2 B3 3 40 Р 60 2 2 З40 Р 2 40 80 1 1 60 60 Запасы αi 60 80 1 100 1 240 49 В процессе решения после каждой итерации (в том числе и после получения допустимого решения) по загруженным клеткам проверяется выполнение следующего условия: N = m + n −1. (6.6) В рассматриваемом примере m = 3, n = 4, а число загруженных клеток равно 6, т.е. соответствует условию 6.6: N = 3 + 4 − 1 = 6 . Если условие 6.6 не выполняется, ТОО план называется вырожденным. В этом случае в свободные клетки надо поставить столько нулей, чтобы с их учетом выполнялось условие (6.6). Клетка, в которой стоит нуль, считается занятой. Значение целевой функции по результатам расчета допустимого плана m n Z = ∑∑ cij xij = 1 ⋅ 40 + 2 ⋅ 20 + 3 ⋅ 40 + 2 ⋅ 40 + 2 ⋅ 40 + 1 ⋅ 60 = 420 д.е. i =1 j =1 Расчет потенциалов выполняют по загруженным клеткам, для которых должно выполняться следующее равенство: α i + β j = cij . (6.7) где α i - потенциал i-й строки; β j - потенциал j-й строки. Вычисляя потенциалы по выражению (6.7), принимаем для первой строки α 1 =0. Используя загруженные клетки (i – j) = (1 – 1), (1 – 2), получаем: α 1 + β1 = с11 0 + β1 = 1; β1 = 1; α 1 + β 2 = с12 0 + β 2 = 2; β 2 = 2; Далее по загруженным клеткам (2 – 2), (2 – 3), (3 – 3), (3 - 4) определяем другие потенциалы: α 2 + β 2 = с 22 α 2 + 0 = 3 ; α 2 = 1; α 2 + β 3 = с 23 1 + β 3 = 2 ; β 3 = 1; α 3 + β 3 = с33 α 3 + 1 = 2 ; α 3 = 1; α 3 + β 4 = с34 1 + β 4 = 1 ; β 4 = 0; Проверяем план на оптимальность по незагруженным клеткам, используя следующее неравенство: α i + β j ≤ cij . (6.8) Если для незагруженных клеток условие (6.8) выполняется, то план - оптимальный. По табл. 6.3 осуществляем проверку начального плана на оптимальность: (i – j) = (1 – 3): 0 + 1 ≤ 3; (i – j) = (1 – 4): 0 + 0 ≤ 4; (i – j) = (2 – 1): 1 + 1 ≤ 4; (i – j) = (2 – 4): 1 + 0 > 0; ∆с 24 = 1 ; (i – j) = (3 – 1): 1 + 1 > 0; ∆с31 = 2 ; (i – j) = (3 – 2): 1 + 2 > 2; ∆с32 = 1 ; Итак, по трем клеткам условие (3.8) не выполняется, следовательно, начальный план требует улучшения. Характеристики ∆сij показывают размер экономии транспортных издержек на 1 ед. перевозимого груза. В нашем примере наибольшую экономию можно получить по клетке (i – j) = (3 – 1), где ∆с31 = 2 > {∆с 24 ; ∆с32 } . Следовательно, клетку (3 – 1) необходимо загрузить за счет перераспределения ресурсов из других загруженных клеток. В табл. 6.3 клетку (3 – 1) помечаем знаком "+", так как здесь в начальном плане находится вершина максимальной неоптимальности. 50 Контур перераспределения ресурсов составляют по следующим правилам: 1. этот контур представляет замкнутый многоугольник с вершинами в загруженных клетках, за исключением клетки с вершиной максимальной неоптимальности "+", и звеньями, лежащими вдоль строк и столбцов матрицы; 2. ломанная линия должна быть связанной в том смысле, что из любой ее вершины можно попасть в любую другую вершину по звеньям ломанной цепи (по строкам или по столбцу); 3. в каждой вершине контура встречаются только два звена, одно из них располагается из по строке, другое – по столбцу; 4. число вершин контура четное, все они в процессе перераспределения делятся на загружаемые и разгружаемые; 5. в каждой строке (столбце) имеются две вершины: одна – загружаемая, другая – разгружаемая. В этой клетке намечаем одну из вершин контура и далее по вышеизложенным правилам строим контур, вершины которого будут находиться в клетках (3–1)–(1–1) – – (1 – 2 ) – (2 – 2) – (2 – 3) – (3 – 3). Вершины контура последовательно разделяем на загружаемые (З) и разгружаемые (Р), начиная с вершин максимальной неоптимальности "+" (табл. 3.3). Перераспределение ресурсов по контуру осуществляется с целью получения оптимального плана. В процессе перераспределения ресурсов по контуру в соответствии с условием неотрицательности переменных xij ни одно из этих значений не должно превратиться в отрицательное число. Поэтому анализируют только клетки, помеченные знаком Р, из которых выбирают клетку с минимальным объемом перевозок. В нашем примере X min = min{40;40;40} = 40 . Следовательно, клетки (1 – 1), (2 – 2), (3 – 3) полностью разгружаются. В клетке (1 – 2) загрузка увеличится на 40 и достигнет 60, в клетке (2 – 3) загрузка составит 40 + 40 = 80, и клетка (3 – 1) загрузится на 40 (табл. 6.4). Таблица 6.4. Первый план перевозок Потребители B1 B2 Поставщики A1 1 A2 A3 Потребность βj 40 40 1 B3 2 B4 3 4 60 4 3 2 60 2 80 Р 2 З ⊕ 2 0 З 80 3 1 Р 60 60 2 Запасы αi 60 80 -1 100 -1 240 Проверяем условие N = m + n − 1 . В нашем примере m = 3, n = 4, а число загруженных клеток равно 4, т.е. условие не выполняется (6 ≠ 4). В процессе перераспределения ресурсов произошла полная разгрузка трех клеток, а мы должны освободить только одну клетку. В этом случае в две клетки нужно проставить нуди (нулевой ресурс) и считать условно их загруженными. Например, в клетки (1 – 1) и (3 – 3) проставим нулевой ресурс (табл. 6.4). Получение нового плана (итерации) осуществляется в том же порядке, который был рассмотрен выше, т.е. 51 − по загруженным клеткам (в соответствии с новой загрузкой) вычисляются потенциалы α i и β j ; − по незагруженным клеткам производится проверка плана на оптимальность; − находится вершина максимальной неоптимальности и строится новый контур перераспределения, и т.д., до тех пор, пока не будет найдено оптимальное решение, удовлетворяющее неравенству (6.8). По результатам первой итерации имеем: m n Z = ∑∑ cij xij = 2 ⋅ +60 + 2 ⋅ 80 + 1 ⋅ 60 + 0 ⋅ 40 = 340 д.е. i =1 j =1 Ниже приведены расчеты по второй итерации и оптимальный план. Поиск потенциалов следующий: α 1 + β1 = с11 0 + β1 = 1; β1 = 1; α 1 + β 2 = с12 0 + β 2 = 2; β 2 = 2; α 2 + β 3 = с 23 α 2 + 3 = 2 ; α 2 = -1; α 3 + β 1 = с31 α 3 + 1 = 0 ; α 3 = -1; α 3 + β 3 = с33 - 1 + β 3 = 2 ; β 3 = 3; α 3 + β 4 = с34 - 1 + β 4 = 1 ; β 4 = 2; Проведем проверку на оптимальность: (i – j) = (1 – 3): 0 + 3 ≤ 3; (i – j) = (1 – 4): 0 + 2 < 4; (i – j) = (2 – 1): 1 – 1 < 4; (i – j) = (2 – 2): 2 – 1 < 3; (i – j) = (3 – 2): 2 – 1 < 2; (i – j) = (2 – 4): 2 – 1 > 0. Клетку (2 – 4) необходимо загрузить. В соответствии с перераспределением ресурсов по контуру получаем табл. 6.5, для которой вновь рассчитываем потенциалы α i и β j , и последовательность вычислений вновь повторяется. Таблица 6.5. Оптимальный план перевозок Потребители B3 B1 B2 Поставщики A1 1 Потребность βj 3 3 2 20 40 40 1 4 60 4 A2 A3 2 B4 2 60 2 60 2 60 80 3 1 60 1 Запасы αi 60 80 -1 100 -1 240 Для распределения, полученного в табл. 6.5, условие α i + β j ≤ cij выполняется, следовательно, план – оптимальный. Транспортные издержки по оптимальному плану следующие: 52 m n Z = ∑∑ cij xij = 1 ⋅ 0 + 2 ⋅ 60 + 2 ⋅ 20 + 0 ⋅ 60 + 0 ⋅ 40 + 2 ⋅ 60 = 280 д.е. i =1 j =1 Таким образом, построение начального плана с последующим расчетом двух итераций получено оптимальное решение по прикреплению пунктов отправления грузов к пунктам назначения. РЕЗЮМЕ Из материала, изложенного в данной лекции, можно сделать следующие выводы. − Транспортная задача является представителем класса задач линейного программирования и поэтому обладает всеми качествами линейных оптимизационных задач, но одновременно она имеет и ряд дополнительных полезных свойств, которые позволили разработать специальные методы ее решения. − Различают два типа транспортных задач: но критерию стоимости и по критерию времени. − Экономико-математическая модель: имеются m пунктов отправления груза и объемы отправления по каждому пункту a1 , a 2 ,..., a m . Известна потребность в грузах b1 , b2 ,..., bn по каждому из n пунктов назначения. Задана матрица стоимостей доставки по каждому варианту сij , i = 1, m , j = 1, n . Необходимо рассчитать оптимальный план перевозок, т.е. определить, сколько груза должно быть отправлено из каждого i-го пункта отправления (от поставщика) в каждый j-ый пункт назначения (до потребителя) xij с минимальными транспортными издержками. − Решение транспортной задачи включает два этапа: определение опорного плана; нахождение оптимального решения, путем последовательных операций. − Для транспортной задачи существует несколько методов отыскания начального плана (опорного решения): метод северо-западного угла; метод минимальной стоимости; метод Фогеля; метод двойного предпочтения. − Существует два метода нахождения оптимального решения транспортной задачи: распределительный метод; метод потенциалов. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ 1. Что такое «транспортная задача»? 2. Какие задачи относятся к транспортным? 3. Приведите классификацию транспортных задач. 4. Перечислите особенности транспортной задачи. 5. Приведите математическую модель транспортной задачи. 6. Приведите пример транспортной таблицы. 7. Когда транспортная задача называется закрытой? Открытой? 8. Дайте характеристику метода северо-западного угла. 9. Дайте характеристику метода минимальной стоимости. 10. Приведите алгоритм потенциалов. 53 7 ЗАДАЧИ ОПТИМИЗАЦИИ РЕШЕНИЙ С ИСПОЛЬЗОВАНИЕМ ДИНАМИЧЕСКИХ РЯДОВ 7.1 СУЩНОСТЬ ДИНАМИЧЕСКОЙ ОПТИМИЗАЦИИ В менеджменте очень часто встречаются случаи, когда цель оптимального планирования заключается в установлении наилучшей последовательности тех или иных работ (производственных операций, этапов строительства различного рода сооружений и т.д.). Именно эта оптимальная последовательность работ или действий ведет к наилучшим результатам работы предприятия: максимальной прибыли, минимуму временных и финансовых затрат, максимальной рентабельности работы. Нахождение этой оптимальной последовательности происходит динамически с помощью полного или частичного перебора возможных вариантов на базе ЭВМ. Машина генерирует возможный вариант решения, анализирует его и делает вывод о его перспективности (запоминая его) ил неперспективности (отбрасывая его). В результате такой сортировки на каждом шаге выделяется все меньше и меньше приемлемых вариантов. В заключение такого динамического анализа выделяется одно или несколько лучших решений. Одной из первых задач такого рода, привлекших внимание специалистов, была так называемая задача о коммивояжере. Суть ее состоит в следующем: имеет (n + 1) населенных пунктов А0 , А1 ,..., Аn ( n ≥ 1 ) с заданными между ними расстояниями d ij (i, j =0, 1, 2, … , n). Требуется, отправляясь из начального пункта А 0 выбрать такой маршрут передвижения, при котором коммивояжер, побывав в каждом из населенных пунктов по одному разу, вернулся бы в исходный пункт А 0 , проделав минимально возможный суммарный путь. Эта задача может быть решена методом простого перебора всех возможный маршрутов. Общее число таких маршрутов равно: 1 × 2 × 3 × ... × (n − 1) × n При больших n полученная величина столь огромна, что практически исключает возможность прямых вычислений даже при использовании вычислительной техники. Проблема заключается в том, чтобы резко сократить перебор вариантов, отбрасывая заведомо непригодные. Сделать это можно с помощью метода динамического планирования. Допустим, что имеется всего пять пунктов А 0 , A1 , A2 , A3 , A4 . Известны расстояния между ними. Укажем это расстояние в соответствующей матрице на пересечении строк и столбцов. A0 A0 A1 A2 A3 A4 A1 A2 A3 A4 300 250 200 400 300 500 350 600 250 500 250 200 200 350 250 250 400 600 200 250 Видно, что матрица симметрична относительно главной диагонали, поэтому достаточно информации одной из ее половинок. Расстояния определяются для кон- 54 кретных путей сообщения не обязательно по прямой. Для определения кратчайшего пути коммивояжера будем рассматривать варианты его передвижения последовательно, пункт за пунктом. Начинаем с вариантов, состоящих из трех участков. Например, отправляясь из исходного пункта A0 можно добраться в третий пункт A3 шестью способами: Зная расстояния между пунктами, можно вычислить суммарный путь для каждого из шести вариантов. А0 А1 А2 А3 , А0 А2 А1 А3 , А0 А1 А4 А3 , А0 А4 А1 А3 , А0 А2 А4 А3 , А0 А4 А2 А3 . Например, сравнивая варианты А0 А1 А2 А3 и А0 А2 А1 А3 получаем, что для первого варианта суммарный путь равен: 300 + 500 + 250 = 1050 км Для второго пути: 250 + 500 + 350 = 1100 км Поскольку оба варианта относятся к одному и тому же множеству пунктов и оканчиваются в одном и том же пункте ( A3 ), то в дальнейшем оба варианта могут развиваться одинаково. Ясно, что проигрыш в 50 км, полученный для второго варианта, делает его бесперспективным в сравнении с первым при любом его дальнейшем развитии. Следовательно, второй вариант может быть отброшен, как бесперспективный. Тем самым отбрасываются и все получаемые из него варианты дальнейшего движения, число которых при больших n может быть огромным. Аналогично рассматриваем все остальные варианты движения: от исходного до первого, от исходного до второго, от исходного до четвертого. Результаты рассмотрения сводим в табл. 7.1. Таблица 7.1. Перспективы вариантов движения Вариант движения А0 А2 А3 А1 А0 А3 А2 А1 А0 А2 А4 А1 А0 А4 А2 А1 А0 А3 А4 А1 А0 А4 А3 А1 А0 А1 А3 А2 Расстояние, км 850 Перспективно или нет да 950 нет 1050 да 1100 нет 1050 нет 1000 да 900 да Вариант движения А0 А1 А2 А3 А0 А2 А1 А3 А0 А1 А4 А3 А0 А4 А1 А3 А0 А2 А4 А3 А0 А4 А2 А3 А0 А1 А2 А4 Расстояние, км 1050 Перспективно или нет да 1100 нет 1150 да 1350 нет 700 да 850 нет 1000 да 55 Вариант движения А0 А3 А1 А2 А0 А1 А4 А2 А0 А4 А1 А2 А0 А3 А4 А2 А0 А4 А3 А2 Расстояние, км 1050 Перспективно или нет нет 1100 да 1500 нет 650 да 900 нет Вариант движения А0 А2 А1 А4 А0 А1 А3 А4 А0 А3 А1 А4 А0 А2 А3 А4 А0 А3 А2 А4 Расстояние, км 1350 Перспективно или нет нет 900 да 1150 нет 750 нет 650 да После заполнения таблицы выделяем только перспективные варианты (их будет 12), дополняем их номером непосещенного населенного пункта и повторяем процедуру: определяем перспективность движения уде для четырех участков пути. Для этого к вычисленной длине пути (табл. 7.1) прибавляем расстояние до непосещенного еще населенного пункта. Результаты вычислений занесем в табл. 7.2. Таблица 7.2. Перспективы выделенных вариантов движения Вариант движения А0 А2 А3 А1 А4 А0 А2 А4 А1 А3 А0 А4 А3 А1 А2 А0 А1 А3 А2 А4 А0 А1 А4 А2 А3 А0 А3 А4 А2 А1 А0 А1 А2 А3 А4 А0 А1 А4 А3 А2 А0 А2 А4 А3 А1 А0 А1 А2 А4 А3 А0 А1 А3 А4 А2 А0 А3 А2 А4 А1 Расстояние, км 1450 Перспективно или нет нет 1400 нет 1500 нет 1100 да 1350 нет 1150 нет 1350 нет 1400 нет 1050 да 1250 да 1100 да 1250 нет Аналогично предыдущему рассмотрению из табл. 7.2. выбираем четыре перспективных варианта. Так как нам необходимо возвратиться в исходный пункт, то выделенные перспективные последовательности движения дополняем исходным пунктом A0 . Вычисляем для них суммарные расстояния и заносим результаты в табл. 7.3. Таблица 7.3. Суммарные расстояния выделенных перспективных вариантов движения Вариант движения А0 А1 А3 А2 А4 А0 А0 А2 А4 А3 А1 А0 А0 А1 А2 А4 А3 А0 А0 А1 А3 А4 А2 А0 Расстояние, км 1500 1350 1450 1350 56 Из таблицы видно, что имеется два оптимальных маршрута следования коммивояжера А0 А2 А4 А3 А1 А0 и А0 А1 А3 А4 А2 А0 , имеющие минимальную из всех возможных маршрутов длину, равную 1350 км. 7.2 ДИНАМИЧЕСКАЯ ОПТИМИЗАЦИЯ В ПЛАНИРОВАНИИ РАБОТ К задаче коммивояжера сводятся многие задачи планирования. Пусть, например, планируется строительство нескольких объектов А1 , А2 ,..., Аn . Ресурсы строительной организации ограничены. Предположим, что строительство каждого объекта состоит из m последовательных стадий (земляные работы, закладка фундамента, кладка стен и т.д.). Мощность строительных организаций не позволяет вести один и тот же вид работ одновременно на нескольких объектах. Продолжительность каждого вида работ задана, например, в месяцах (табл. 7.4). Таблица 7.4. Продолжительность работ Объекты A1 A2 A3 1 1 Виды (стадии) работ 2 3 4 3 4 2 3 2 3 1 2 2 1 4 Считая, что работа на каждом объекте должна продолжаться непрерывно с момента начала строительства до его окончания, требуется определить сроки начала строительства каждого объекта так, чтобы суммарный срок строительства всех объектов был минимальным. Последовательность строительства может быть любой: А1 А2 А3 ; А1 А3 А2 ; А2 А1 А3 ; А2 А3 А1 ; А3 А1 А2 ; А3 А2 А1 . Необходимо найти оптимальную последовательность, при которой бы суммарный срок строительства был минимальным. Покажем, как оценивается суммарное время строительства для одного их вариантов, например, А1 А2 А3 . Сроки окончания работ на первом объекте будут следующими (см. табл. 7.4): − − − − окончание первой стадии 1 месяц; окончание второй стадии 1 + 3 = 4 месяца; окончание третьей стадии 4 + 4 = 8 месяцев; окончание четвертой стадии 8 + 2 = 10 месяцев. Время t 2 начала работ на втором объекте должно удовлетворять следующим не- 57 равенствам: t 2 ≥ 1; t 2 + 3 ≥ 4; t 2 + 5 ≥ 8; t 2 + 8 ≥ 10. Эти неравенства выражают требования, чтобы каждая из стадий работ на объекте A2 начиналась лишь после окончания работ соответствующих стадий на объекте A1 . Одновременно (параллельно) вести один и тот же вид работ у организации нет возможности (по условия задачи). Первое неравенство выражает требование, чтобы первая стадия работ на втором объекте начиналась лишь после окончания первой стадии работ на первом объекте, т.е. через один месяц. Второе неравенство выражает требование, чтобы вторая стадия работ на втором объекте начиналась лишь после окончания второй стадии работ на первом объекте, т.е. через четыре месяца. При этом не надо забывать, что первая стадия работ на втором объекте уже выполнена ( t 2 + 3 ). Третье неравенство выражает требование, чтобы третья стадия работ на втором объекте начиналась лишь после окончания третьей стадии работ на первом объекте, т.е. через восемь месяцев (первая и вторая стадии работ на втором объекте уже выполнены, следовательно, t 2 + 5 ). Четвертое неравенство выражает требование, чтобы четвертая стадия работ на втором объекте начиналась лишь после окончания четвертой стадии работ на первом объекте, т.е. через десять месяцев (первая, вторая и третья стадии работ на втором объекте выполнены, следовательно, t 2 + 8 ). Наименьшее значение t 2 , удовлетворяющее этим неравенствам, равно 3. Поэтому самый ранний возможный срок начала строительства второго объекта A2 3 месяца после начала строительства первого объекта A1 . Зная это значение, несложно определить сроки окончания соответствующих стадий работ: − − − − окончание первой стадии 3 + 3 = 6 месяцев; окончание второй стадии 6 + 2 = 8 месяцев; окончание третьей стадии 8 + 3 = 11 месяцев; окончание четвертой стадии 11 + 1 = 12 месяцев. Зная сроки окончания стадии работ на втором объекте, аналогично определяем срок t 3 начала строительства третьего объекта ( A3 ). Для него неравенства будут следующие: 58 t 3 ≥ 6; t 3 + 2 ≥ 8; t 3 + 4 ≥ 11; t 3 + 5 ≥ 12. что приводит к минимальному сроку t 3 = 7 мес. Следовательно, сроки окончания отдельных стадий строительства третьего объекта соответственно: − окончание первой стадии 7 + 2 = 9 месяцев; − окончание второй стадии 9 + 2 = 11 месяцев; − окончание третьей стадии 11 + 1 = 12 месяцев; − окончание четвертой стадии 12 + 4 = 16 месяцев. Таким образом, для выбранной последовательности строительства объектов А1 А2 А3 общее время строительства (совпадающие со сроком завершения работ на объекте А3 ) равно 16 мес. Аналогично можно определить сроки и для других оставшихся последовательностей строительства: А1 А3 А2 ; А2 А1 А3 ; А2 А3 А1 ; А3 А1 А2 ; А3 А2 А1 . Поскольку в рассмотренном примере имеется всего 3! = 6 вариантов строительства, то выбор наилучшего варианта может быть осуществлен простым перебором вариантом. При большом количестве объектов (n) количество комбинаций может быть очень большим (n!). В такой ситуации выбор оптимальной последовательности может быть осуществлен точно таким же образом, как и в задаче о коммивояжере: сначала берется усеченная последовательность строительства объектов, из нее выбираются перспективные варианты (с минимумом времени), далее она постепенно дополняется с повторением процедур расчета и оценки. Показанные методы динамического программирования (или планирования) относят к классу многошаговых (или многоэтапных). Видно, что на каждом из этапов происходит анализ, оценка, выделение и запоминание наилучших (перспективны) последовательностей с последующим повторением всех отмеченных процедур расчета. На каждом из шагов варианты усекаются. Когда количество выделенных вариантов становится минимальным, происходит окончательный выбор. РЕЗЮМЕ Из материала, изложенного в данной лекции, можно сделать следующие выводы. − В основе динамического программирования лежит принцип оптимальности: «Оптимальная стратегия обладает тем свойством, что каковы бы ни были первоначальное состояние и управление, при которых система пришла в это состоя- 59 ние, последующее решение (управления) должны быть оптимальными по отношению к этому состоянию». − Сущность динамического программирования состоит в том, что задача большой размерности разбивается на ряд подзадач меньшей размерности (проводится декомпозиция). Это достигается разбивкой всего процесса на несколько стадий. Процесс решения задачи выполняется пошагово. На первом шаге вычисляют значение составляющей критерия оптимальности от одной стадии. На втором и последующих шагах оптимизируется суммарное приращение критерия оптимальности от вновь вводимой стадии процесса вместе с полученным результатом оптимизации на предыдущем шаге. − Показанные методы динамического программирования (или планирования) относят к классу многошаговых (или многоэтапных). − Общим для задач динамического программирования является то, что переменные рассматриваются не вместе, а последовательно, одна за другой. Сущность состоит в том, что строится такая вычислительная схема, когда вместо одной задачи со многими переменными строится много задач с малым числом переменных (обычно даже одной) в каждой. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ 1. 2. 3. 4. 5. 6. Дайте краткую характеристику динамической оптимизации. В чем заключается сущность динамической оптимизации? В чем заключается задача коммивояжера? Приведите алгоритм решения задачи коммивояжера. Приведите пример динамической оптимизации в планировании работ. Что является общим для задач динамического программирования? 60 8 МОДЕЛИРОВАНИЕ СИСТЕМ МАССОВОГО ОБСЛУЖИВАНИЯ 8.1 КОМПОНЕНТЫ И КЛАССИФИКАЦИЯ МОДЕЛЕЙ МАССОВОГО ОБСЛУЖИВАНИЯ Системы массового обслуживания - это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания. С позиции моделирования процесса массового обслуживания ситуации, когда образуются очереди заявок (требований) на обслуживание, возникают следующим образом. Поступив в обслуживающую систему, требование присоединяется к очереди других (ранее поступивших) требований. Канал обслуживания выбирает требование из находящихся в очереди, с тем чтобы приступить к его обслуживанию. После завершения процедуры обслуживания очередного требования канал обслуживания приступает к обслуживанию следующего требования, если таковое имеется в блоке ожидания. Цикл функционирования системы массового обслуживания подобного рода повторяется многократно в течение всего периода работы обслуживающей системы. При этом предполагается, что переход системы на обслуживание очередного требования после завершения обслуживания предыдущего требования происходит мгновенно, случайные моменты времени. Примерами систем массового обслуживания могут служить: 1. посты технического обслуживания автомобилей; 2. посты ремонта автомобилей; 3. персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач; 4. станции технического обслуживания автомобилей; 5. аудиторские фирмы; 6. отделы налоговых инспекций, занимающиеся приемкой и проверкой текущей отчетности предприятий; 7. телефонные станции и т. д. Основными компонентами системы массового обслуживания любого вида являются: − входной поток поступающих требований или заявок на обслуживание; − дисциплина очереди; − механизм обслуживания. Входной поток требований. Для описания входного потока требуется задать вероятностный закон, определяющий последовательность моментов поступления требований на обслуживание и указать количество таких требований в каждом очередном поступлении. При этом, как правило, оперируют понятием «вероятностное распределение моментов поступления требований». Здесь могут поступать как единичные, так и групповые требования (требования поступают группами в систему). В последнем случае обычно речь идет о системе обслуживания с параллельногрупповым обслуживанием. Дисциплина очереди - это важный компонент системы массового обслуживания, он определяет принцип, в соответствии с которым поступающие на вход обслу- 61 живающей системы требования подключаются из очереди к процедуре обслуживания. Чаще всего используются дисциплины очереди, определяемые следующими правилами: − первым пришел — первый обслуживаешься; − пришел последним — обслуживаешься первым; − случайный отбор заявок; − отбор заявок по критерию приоритетности; − ограничение времени ожидания момента наступления обслуживания (имеет место очередь с ограниченным временем ожидания обслуживания, что ассоциируется с понятием «допустимая длина очереди»). Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. К характеристикам процедуры обслуживания относятся: продолжительность процедуры обслуживания и количество требований, удовлетворяемых в результате выполнения каждой такой процедуры. Для аналитического описания характеристик процедуры обслуживания оперируют понятием «вероятностное распределение времени обслуживания требований». Следует отметить, что время обслуживания заявки зависит от характера самой заявки или требований клиента и от состояния и возможностей обслуживающей системы. В ряде случаев приходится также учитывать вероятность выхода обслуживающего прибора по истечении некоторого ограниченного интервала времени. Структура обслуживающей системы определяется количеством и взаимным расположением каналов обслуживания (механизмов, приборов и т. п.). Прежде всего следует подчеркнуть, что система обслуживания может иметь не один канал обслуживания, а несколько; система такого рода способна обслуживать одновременно несколько требований. В этом случае все каналы обслуживания предлагают одни и те же услуги, и, следовательно, можно утверждать, что имеет место параллельное обслуживание. Система обслуживания может состоять из нескольких разнотипных каналов обслуживания, через которые должно пройти каждое обслуживаемое требование, т. е. в обслуживающей системе процедуры обслуживания требований реализуются последовательно. Механизм обслуживания определяет характеристики выходящего (обслуженного) потока требований. Предметом теории массового обслуживания является установление зависимости между факторами, определяющими функциональные возможности системы массового обслуживания, и эффективностью ее функционирования. В большинстве случаев все параметры, описывающие системы массового обслуживания, являются случайными величинами или функциями, поэтому эти системы относятся к стохастическим системам. Случайный характер потока заявок (требований), а также, в общем случае, и длительности обслуживания приводит к тому, что в системе массового обслуживания происходит случайный процесс. По характеру случайного процесса, происходящего в системе массового обслуживания (СМО), различают системы марковские и немарковские. В марковских системах входящий поток требований и выходящий поток обслуженных требований (заявок) являются пуассоновскими. Пуассоновские потоки позволяют легко описать и построить математическую модель системы массового обслуживания. Данные модели имеют достаточно простые решения, поэтому большинство известных приложений теории массового обслуживания используют марковскую схему. В случае немарковских процессов задачи исследования систем массового об- 62 служивания значительно усложняются и требуют применения статистического моделирования, численных методов с использованием ЭВМ. Независимо от характера процесса, протекающего в системе массового обслуживания, различают два основных вида СМО: − системы с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и сразу же покидает очередь; − системы с ожиданием (очередью), в которых заявка, поступившая в момент, когда все каналы обслуживания заняты, становится в очередь и ждет, пока не освободится один из каналов. Системы массового обслуживания с ожиданием делятся на системы с ограниченным ожиданием и системы с неограниченным ожиданием. В системах с ограниченным ожиданием может ограничиваться: − длина очереди; − время пребывания в очереди. В системах с неограниченным ожиданием заявка, стоящая в очереди, ждет обслуживание неограниченно долго, т.е. пока не подойдет очередь. Все системы массового обслуживания различают по числу каналов обслуживания: − одноканальные системы; − многоканальные системы. Приведенная классификация СМО является условной. На практике чаще всего системы массового обслуживания выступают в качестве смешанных систем. Например, заявки ожидают начала обслуживания до определенного момента, после чего система начинает работать как система с отказами. 8.2 ОДНОКАНАЛЬНАЯ МОДЕЛЬ С ПУАССОНОВСКИМ ВХОДНЫМ ПОТОКОМ С ЭКСПОНЕНЦИАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ ДЛИТЕЛЬНОСТИ ОБСЛУЖИВАНИЯ Простейшей одноканальной моделью с вероятностными входным потоком и процедурой обслуживания является модель, характеризуемая показательным распределением как длительностей интервалов между поступлениями требований, так и длительностей обслуживания. При этом плотность распределения длительностей интервалов между поступлениями требований имеет вид f 1 ( x ) = λ ⋅ e − λt , (6.1) где λ - интенсивность поступления заявок в систему Плотность распределения длительностей обслуживания: f 2 ( x) = µ ⋅ e − µt , (6.2) где µ - интенсивность обслуживания Потоки заявок и обслуживания простейшие. 8.2.1 Одноканальная СМО с отказами Пусть система работает с отказами. Необходимо определить абсолютную и относительную пропускную способность системы. 63 Представим данную систему массового обслуживания в виде графа (рис. 8.1), у которого имеются два состояния: S 0 - канал свободен (ожидание); S1 - канал занят (идет обслуживание заявки). Рис. 8.1. Граф состояний одноканальной СМО с отказами Обозначим вероятности состояний: P0 (t ) - вероятность состояния «канал свободен»; P1 (t ) - вероятность состояния «канал занят». По размеченному графу состояний (рис. 8.1) составим систему дифференциальных уравнений Колмогорова для вероятностей состояний:  dP0 (t )  dt = −λ ⋅ P0 (t ) + µ ⋅ P1 (t )   dP1 (t ) = − µ ⋅ P (t ) + λ ⋅ P (t ). 1  dt (8.3) Система линейных дифференциальных уравнений (8.3) имеет решение с учетом нормировочного условия P0 (t ) + P1 (t ) = 1 . Решение данной системы называется неустановившимся, поскольку оно непосредственно зависит от t и выглядит следующим образом: P0 (t ) = λ λ+µ e −( λ + µ ) t + P1 (t ) = 1 − P0 (t ) . µ λ+µ (8.4) (8.5) Нетрудно убедиться, что для одноканальной СМО с отказами вероятность P0 (t ) есть не что иное, как относительная пропускная способность системы q. Действительно, P0 - вероятность того, что в момент t канал свободен и заявка, пришедшая к моменту t, будет обслужена, а следовательно, для данного момента времени t среднее отношение числа обслуженных заявок к числу поступивших также равно P0 (t ) , т. е. q = P0 (t ) (8.6) По истечении большого интервала времени (при t → ∞ ) достигается стационарный (установившийся) режим (q – относительная пропускная способность): q = P0 = µ µ +λ (8.7) Зная относительную пропускную способность, легко найти абсолютную. Абсолютная пропускная способность (А) - среднее число заявок, которое может обслужить система массового обслуживания в единицу времени: 64 A=λ ⋅q = λµ λ+µ (8.8) Вероятность отказа в обслуживании заявки будет равна вероятности состояния «канал занят»: Pотк = P1 = 1 − P0 = 1 − µ λ+µ = λ λ+µ (8.9) Данная величина Pотк может быть интерпретирована как средняя доля необслуженных заявок среди поданных. 8.2.2 Одноканальная СМО с ожиданием Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание - простейший поток с интенсивностью λ . Интенсивность потока обслуживания равна µ (т. е. в среднем непрерывно занятый канал будет выдавать µ обслуженных заявок). Длительность обслуживания - случайная величина, подчиненная показательному закону распределения. Поток обслуживании является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Предположим, что независимо от того, сколько требований поступает на вход обслуживающей системы, данная система (очередь + обслуживаемые клиенты) не может вместить более N-требований (заявок), т. е. клиенты, не попавшие в ожидание, вынуждены обслуживаться в другом месте. Наконец, источник, порождающий заявки на обслуживание, имеет неограниченную (бесконечно большую) емкость. Граф состояний СМО в этом случае имеет вид, показанный на рис. 8.2. Рис. 8.2. Граф состояний одноканальной СМО с ожиданием (схема гибели и размножения) Состояния СМО имеют следующую интерпретацию: S 0 - «канал свободен»; S1 - «канал занят» (очереди нет); S 2 - «канал занят» (одна заявка стоит в очереди); ……………………………………………………. S n - «канал занят» (n -1 заявок стоит в очереди); S N - «канал занят» (N - 1 заявок стоит в очереди). Стационарный процесс в данной системе будет описываться следующей системой алгебраических уравнений: 65 − ψ ⋅ P0 + P1 = 0, n = 0 ......................  − (1 − ψ ) ⋅ Pn + Pn+1 + ψ ⋅ Pn−1 = 0, ......................  − PN + ψ ⋅ PN −1 = 0, n = N где ψ = 00 (8.20) Решение данной системы уравнений имеет вид Pn = (1 −ψ )ψ n , n = 0,1,2,... где ψ = (8.21) λ <1. µ Если ψ < 1 , то очередь будет уменьшаться, если ψ > 1 , то очередь растет до бесконечности 67 Характеристики одноканальной СМО с ожиданием, без ограничения на длину очереди, следующие: − среднее число находящихся в системе клиентов (заявок) на обслуживание: ∞ ψ (8.22) LS = ∑ n ⋅ Pn = 1 −ψ n =0 − средняя продолжительность пребывания клиента в системе: WS = LS = 1 [µ ⋅ (1 −ψ )] λ − среднее число клиентов в очереди на обслуживании: λ ψ2 Lq = LS − = µ (1 −ψ ) − средняя продолжительность пребывания клиента в очереди: Lq ψ Wq = = λ [µ ⋅ (1 −ψ )] (8.23) (8.24) (8.25) 8.3 МНОГОКАНАЛЬНАЯ МОДЕЛЬ С ПУАССОНОВСКИМ ВХОДНЫМ ПОТОКОМ И ЭКСПОНЕНЦИАЛЬНЫМ РАСПРЕДЕЛЕНИЕМ ДЛИТЕЛЬНОСТИ ОБСЛУЖИВАНИЯ В подавляющем большинстве случаев на практике системы массового обслуживания являются многоканальными, и, следовательно, модели с n обслуживающими каналами (где n > 1 ) представляют несомненный интерес. Процесс массового обслуживания, описываемый данной моделью, характеризуется интенсивностью входного потока λ , при этом параллельно может обслуживаться не более n клиентов (заявок). Средняя продолжительность обслуживания одной заявки равняется 1 µ . Входной и выходной потоки являются пуассоновскими. Режим функционирования того или иного обслуживающего канала не влияет на режим функционирования других обслуживающих каналов системы, причем длительность процедуры обслуживания каждым из каналов является случайной величиной, подчиненной экспоненциальному закону распределения. Конечная цель использования n параллельно включенных обслуживающих каналов заключается в повышении (по сравнению с одноканальной системой) скорости обслуживания требований за счет обслуживания одновременно n клиентов. Граф состояний многоканальной системы массового обслуживания с отказами имеет вид, показанный на рис. 8.3. Поток заявок последовательно переводит систему из любого левого состояния в соседнее правое с одной и той же интенсивностью λ . Интенсивность же потока обслуживаний, переводящих систему из любого правого состояния в соседнее левое, постоянно меняется в зависимости от состояния. Действительно, если СМО находится в состоянии S 2 (два канала заняты), то она может перейти в состояние S1 (один канал занят), когда закончит обслуживание либо первый, либо второй канал, т.е. суммарная интенсивность их потоков обслуживаний будет 2µ . Аналогично суммарный поток обслуживаний, переводящий СМО из состояния S 3 (три канала заняты) в S 2 , 68 будет иметь интенсивность 3µ , т.е. может освободиться любой из трех каналов и т.д. Рис. 8.3. Граф состояний многоканальной СМО с отказами Состояния СМО имеют следующую интерпретацию: S 0 - все каналы свободны; S1 - занят один канал, остальные свободны; ……………………………………………………. S k - заняты ровно k каналов, остальные свободны; ……………………………………………………. S n - заняты все n каналов, остальные свободны; Уравнения Колмогорова для вероятностей состояний системы P0 ,..., Pk ,..., Pn будет иметь следующий вид:  dP0  dt = −λ ⋅ P0 + µ ⋅ P1  ..............................  dP k = λ ⋅ Pk −1 − (λ + k ⋅ µ ) ⋅ Pk + µ ⋅ (k + 1) ⋅ Pk +1 ,  dt  ...............................   dPn = λ ⋅ Pn−1 − µ ⋅ n ⋅ Pn  dt 1 ≤ k ≤ n −1 (8.26) Начальные условия решения системы таковы: P0 (0) = 1 , P1 (0) = P2 (0) = ... = Pk (0) = ... + Pn (0) = 0 . Стационарное решение системы имеет вид:  ψk  ψk k ! ⋅ P0 , k = 0,1,2,..., n  Pk = n k = k! ψ      P0 =   где ψ = ∑ 1 n ∑ k =0 (8.27) k! k =0 ψk , k = 0,1,2,..., n k! λ . Это приведенная интенсивность потока заявок или интенсивность нагрузµ ки канала. Она выражает среднее число заявок, приходящее за среднее время обслуживания одной заявки. Формулы для вычисления вероятностей Pk называются формулами Эрланга. 8.3.1 Многоканальная СМО с отказами Определим вероятностные характеристики функционирования многоканальной 69 СМО с отказами в стационарном режиме: − вероятность отказа: Pотк = Pn = ψn n! ⋅ P0 , (8.28) так как заявка получает отказ, если приходит в момент, когда все n каналов заняты. Величина Pотк характеризует полноту обслуживания входящего потока; − вероятность того, что заявка будет принята к обслуживанию (она же - относительная пропускная способность системы q) дополняет Pотк до единицы: q = 1 − Pотк = 1 − ψn n! ⋅ P0 (6.29) − абсолютная пропускная способность A = λ ⋅ q = λ ⋅ (1 − Pотк ) (4.30) − среднее число каналов, занятых обслуживанием ( k ) следующее: n k = ∑ k ⋅ Pk = ψ ⋅ (1 − Pотк ) . (4.31) k =1 Величина k характеризует степень загрузки СМО. 8.3.2 Многокональная СМО с ожиданием 8.3.2.1 Многоканальная СМО с ожиданием без ограничения на длину очереди Рассмотрим многоканальную систему массового обслуживания с ожиданием. Процесс массового обслуживания при этом характеризуется следующим: входной и выходной потоки являются пуассоновскими с интенсивностями λ и µ соответственно; параллельно обслуживаться могут не более S клиентов. Система имеет S каналов обслуживания. Средняя продолжительность обслуживания одного клиента равна - 1 . µ В установившемся режиме функционирование многоканальной СМО с ожиданием и неограниченной очередью может быть описано с помощью системы алгебраических уравнений: 0 = λ ⋅ Pn−1 − (λ + n ⋅ µ ) ⋅ Pn + (n + 1) µ ⋅ Pn+1 , при 1 ≤ n < S (8.32) 0 = λ ⋅ Pn−1 − (λ + S ⋅ µ ) ⋅ Pn + S ⋅ µ ⋅ Pn+1 . при n ≥ S Решение системы уравнений (4.32) имеет вид  ψn ⋅ P0 ,  Pn = n!  n P = ψ ⋅P ,  n S!S n−S 0 где при 1 ≤ n < S при n ≥ S (8.33) (8.34) 70   S  S −1 ψ n  ψ P0 = ∑ +   n =0 n! S!1 − ψ    S     −1 (8.35) Решение будет действительным, если выполняется следующее условие:  λ   µ ⋅ S  < 1 , где S – число каналов.   Вероятностные характеристики функционирования в стационарном режиме многоканальной СМО с ожиданием и неограниченной очередью определяются по следующим формулам: − вероятность того, что в системе находится n клиентов на обслуживании, определяется по формулам (8.33) и (8.34); − среднее число клиентов в очереди на обслуживание  S ⋅ψ  Lq =  ⋅ PS (8.36) 2  (S −ψ )  − среднее число находящихся в системе клиентов (заявок на обслуживание и в очереди) LS = Lq + ψ (8.37) − средняя продолжительность пребывания клиента (заявки на обслуживание) в очереди Wq = Lq λ − средняя продолжительность пребывания клиента в системе WS = Wq + 1 (8.38) (8.39) µ 8.3.2.2 Многоканальная СМО с ожиданием и ограничением на длину очереди Конечные формулы приведены ниже. (N -1) – ограничение очереди. − предельные вероятности −1 N −1  ψ  n +1   ψ 1 −    n  P0 = 1 +   ψ  n ⋅ n!1 −     n    ψn P = ⋅ P0 ,  n при 1 ≤ n < S n!  n+ S при n ≥ S P = ψ ⋅P ,  n n!n S 0 − вероятность отказа ψ n+ N −1 Pотк = Pn+ ( N −1) = n N −1 ⋅ n! P0 − абсолютная пропускная способность (8.40) (8.41) (8.42) (8.43) 71  ψ n+ N −1  A = λq = λ 1 − N −1 P0   n ⋅ n!  (8.44) − относительная пропускная способность ψ n+ N −1 q = 1 − Pотк = 1 − n N −1 ⋅ n! P0 (8.45) − среднее число клиентов в очереди на обслуживание N −1   ψ  ψ   ψ n=1 P0 1 −  N − ( N − 1)     Lq =  n  n   ψ n ⋅ n!1 −   n 2  − среднее число занятых каналов  ψ n+ N −1  k = ψ 1 − N −1 P0   n ⋅ n!  (8.46) (8.47) − среднее число заявок в системе LS = Lq + k (8.48) . РЕЗЮМЕ Из материала, изложенного в данной лекции, можно сделать следующие выводы. − Предметом теории массового обслуживания является установление зависимости между факторами, определяющими функциональные возможности системы массового обслуживания, и эффективностью ее функционирования. − Системы массового обслуживания - это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания. − Основными компонентами системы массового обслуживания любого вида являются: входной поток поступающих требований или заявок на обслуживание; дисциплина очереди; механизм обслуживания. − По характеру случайного процесса, происходящего в системе массового обслуживания (СМО), различают системы марковские и немарковские. ВОПРОСЫ ДЛЯ САМОКОНТРОЛЯ Какие системы относятся к системам массового обслуживания? Что относится к основным компонентам системы массового обслуживания? Что такое входной поток поступающих требований на обслуживание? Что такое дисциплина очереди? Что такое механизм обслуживания? Какие СМО относятся к марковским? Приведите классификацию систем массового обслуживания. Приведите характеристику и основные рассчитываемые показатели одноканальной модели. 9. Приведите характеристику и основные рассчитываемые показатели многоканальной модели 1. 2. 3. 4. 5. 6. 7. 8. 72 ГЛОССАРИЙ Задача о коммивояжере или о бродячем торговце [travelling salesman problem] – вид задачи математического программирования; состоит в отыскании наилучшего маршрута для коммивояжера (бродячего торговца), который должен объехать все порученные ему города и вернуться назад за кратчайший срок или с наименьшими затратами на проезд. Исследование операций – применение математических, количественных методов для обоснования решений во всех областях целенаправленной человеческой деятельности. Метод ветвей и границ - это один из методов организации полного перебора. Операция – это всякая система действий (мероприятие), объединенных единым замыслом и направленных к достижению какой-то цели. Оптимизационная задача – это экономико-математическая задача, которая состоит в нахождении оптимального (максимального или минимального) значения целевой функции, причем значения переменных должны принадлежать некоторой области допустимых значений. Симплекс - метод - это алгебраический метод решения задач линейного программирования. Системы массового обслуживания - это такие системы, в которые в случайные моменты времени поступают заявки на обслуживание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания. 73 ПЕРЕЧЕНЬ РЕКОМЕНДУЕМОЙ К ИЗУЧЕНИЮ ЛИТЕРАТУРЫ 1. Димов Э.М., Качков Д.А. Методические указания к лабораторным работам по курсу "Основы исследования операций в экономике ". - Самара ПГАТИ, 1999 2. Диязитдинова А.Р., Ран Н.А. Решение оптимизационных задач // Методические указания к лабораторно-практическим занятиям по курсу "Исследование операций в экономике". - Самара: ПГАТИ, 2008, 82 с. 3. Исследование операций в экономике учеб. пособие для вузов под ред. Н. Ш. Кремера - М. ЮНИТИ 2006 - 407 с. ил. 4. Исследование операций Е.С. Вентцель - М. Сов. радио 1972 - 552 с. ил. 5. Исследование операций учебник для вузов И. К. Волков, Е. А. Загоруйко; под ред. В.С. Зарубина, А. П. Крищенко - 2-е изд. - М. Изд-во МГТУ им. Н. Э. Баумана 2002 - 435 с. Ил 6. Исследование операций: Задачи, принципы, методология Е. С. Вентцель М. Высш. школа 2001 - 208с. ил. 7. Исследование систем управления [учеб. пособие для вузов] В. В. Мыльник, Б. П. Титаренко, В. А. Волочиенко - М. Академ. Проект; Трикста 2004 - 352 с. ил. 8. Основы исследования операций в экономике учебное пособие Э. М. Димов, Д. А. Калиновский - Самара ПИИРС 1998 - 68 с. ил.