Математические методы в экономике

Курс лекций по дисциплине «Математические методы в экономике» Оглавление Введение ..................................................................................................................... 3 Классификация задач ИО ...................................................................................... 4 Этапы исследования операций ............................................................................. 7 Общая постановка задачи исследования операций ............................................ 9 Линейное программирование................................................................................. 12 Понятие экономико-математической модели ................................................... 12 Примеры построения ЭММ экономических задач линейного программирования ............................................................................................... 12 Общая задача линейного программирования ................................................... 17 Система m линейных уравнений с n переменными ......................................... 18 Геометрический смысл решений неравенств, уравнений и их систем .......... 20 Свойства задач ЛП ............................................................................................... 23 Геометрический метод решения задач ЛП........................................................ 23 Симплексный метод ............................................................................................ 27 Нахождение оптимума линейной функции ................................................... 28 Особые случаи симплексного метода ............................................................ 32 Симплексные таблицы ..................................................................................... 34 Метод искусственного базиса (М-метод) .......................................................... 37 Теория двойственности в линейном программировании .................................... 39 Экономическая интерпретация двойственной задачи ..................................... 39 Прямая и двойственная задачи ........................................................................... 40 Общие правила составления двойственных задач: .......................................... 40 Первая (основная) теорема двойственности ..................................................... 41 Пример применения 1-ой (основной) теоремы двойственности ................. 41 Экономический смысл 1-ой (основной) теоремы двойственности. ............ 41 Вторая теорема двойственности ........................................................................ 42 Пример двойственной задачи ............................................................................. 43 Анализ чувствительности в линейном программировании ............................ 47 Критические границы и допустимые изменения ресурса ............................ 48 Ценовой анализ ................................................................................................. 53 Решение задачи ЛП средствами EXCEL............................................................... 56 Описание ситуации .............................................................................................. 56 Создание в Excel модели для решения задачи .................................................. 57 1 Решение задачи в Excel ....................................................................................... 58 Анализ оптимального решения на чувствительность в Excel ......................... 62 Параметрическое линейное программирование .................................................. 67 Целочисленное программирование ....................................................................... 70 Методы отсечения ............................................................................................... 70 Метод ветвей и границ ........................................................................................ 73 Многокритериальная оптимизация ....................................................................... 74 Метод «свертки» критериев................................................................................ 74 Метод выделения главного критерия ................................................................ 75 Методы упорядочения критериев ...................................................................... 75 Задача с независимыми критериями .................................................................. 76 Транспортная задача ............................................................................................... 78 Постановка транспортной задачи ...................................................................... 78 Выбор критерия оптимальности ..................................................................... 78 Решение транспортной задачи ........................................................................... 82 Построение допустимого (опорного) плана в транспортной задаче........... 83 Нахождение оптимального решения .............................................................. 85 Решение транспортной задачи средствами EXCEL ......................................... 88 Создание в Excel модели для решения задачи .............................................. 88 Решение задачи в Excel .................................................................................... 89 Анализ оптимального решения на чувствительность в Excel ..................... 92 Задача о назначениях .............................................................................................. 94 Модель задачи о назначениях............................................................................. 94 Общий вид матрицы задачи о назначениях ...................................................... 96 Пример постановки задачи о назначениях ........................................................ 96 Модели нелинейного программирования ............................................................. 98 Примеры задач нелинейного программирования............................................. 99 Метод множителей Лагранжа ........................................................................... 101 Методы решения для моделей выпуклого программирования..................... 102 Квадратичное программирование .................................................................... 104 Модели сетевого планирования и управления ................................................... 106 Основные понятия СПУ .................................................................................... 106 Правила построения сетевой модели проекта ................................................ 108 Расчет параметров сетевого графика ............................................................... 110 2 Введение Математические методы в экономике — это научное направление в экономике, которое занимается исследованием экономических систем и процессов с помощью математических моделей. Одной из основных составляющих этого направления является исследование операций. Исследование операций – научная дисциплина, занимающаяся разработкой и практическим применением математических методов для наиболее эффективного управления различными организационными системами. Исследование операций — дисциплина, занимающаяся разработкой и применением методов нахождения оптимальных решений на основе математического моделирования, статистического моделирования и различных эвристических подходов в различных областях человеческой деятельности. В создание современного математического аппарата и развитие многих направлений исследования операций большой вклад внесли российские ученые Л. В. Канторович, Н. П. Бусленко, Е. С. Вентцель и многие другие. Значительный вклад в формирование и развитие ИО внесли зарубежные ученые Р. Беллман, Г. Данциг, Дж. Нейман, Т. Саати и многие другие. Цель, которую преследуют в процессе ИО, заключается в том, чтобы выявить наилучший (оптимальный) способ действия при решении той или иной задачи организационного управления в условиях, когда имеют место ограничения технико-экономического или какого-либо другого характера. Управление любой системой реализуется как процесс, подчиняющийся определенным закономерностям. Знание этих закономерностей позволяет определить условия, необходимые и достаточные для осуществления данного процесса. Для этого все параметры, характеризующие процесс и внешние условия, должны быть количественно определены, измерены. Поэтому, другими словами, цель ИО – количественное обоснование принимаемых решений по организации управления. Различают два вида целей: 1) качественная цель (социальные достижения- повысить ответственность за порученное дело, улучшить моральное состояние в коллективе), для нее все способы достижения цели одинаково удовлетворительны 2) количественная цель (имеющая показатель эффективности в числовой мере). Часто цель- это увеличение или уменьшение одного критерия эффективности. При исследовании операций важен вопрос формализованного представления цели операции. Эквивалентом цели, таким образом, выступает критерий эффективности, увеличение или уменьшение которого является математическим описанием цели операции. При использовании термина ИО почти всегда имеют в виду применение математических методов для моделирования систем и анализа их характеристик. Действительно, мат. модели и методы занимают центральное 3 место в ИО. Но, следует иметь в виду, что решение задач организационного управления не всегда сводится к построению моделей и выполнению соответствующих вычислений. Это связано с тем, что в ходе формирования управляющих решений нередко сталкиваются с факторами, которые являются существенными для правильного решения поставленной задачи, но не поддаются строгой формализации, и, следовательно, не могут непосредственно вводиться в математическую модель. Одним из труднореализуемых факторов такого рода является фактор человеческой деятельности. Пример – «проблема лифта», которая используется в качестве иллюстрации во многих публикациях по ИО. При решении конкретной задачи управления прежде всего важно определить цель, которая преследуется в ходе решения задачи и установить, значениями каких характеристик (переменных) исследуемой системы или процесса можно варьировать. Цель – конечный результат, который необходимо получить путем выбора и реализации тех или иных управляющих воздействий на исследуемую систему. В производственно-коммерческой сфере цель, как правило, заключается в получении максимально возможной прибыли или в минимизации расходов. Классификация задач ИО Задачи ИО можно классифицировать по своей содержательной постановке: Задачи сетевого планирования и управления рассматривают соотношения между сроками окончания комплексов операций (работ) и моментами начала всех операций комплекса. Эти задачи состоят в нахождении минимальных продолжительностей комплекса операций, оптимального соотношения величин стоимостей и сроков их выполнения. Задачи массового обслуживания посвящены изучению и анализу систем обслуживания с очередями заявок или требований и состоят в определении показателей эффективности работы систем, их оптимальных характеристик, например, в определении числа каналов обслуживания, времени обслуживания и т.д. Задачи управления запасами состоят в отыскании оптимальных значений уровня запасов (точки заказа) и размера заказа. Особенность таких задач состоит в том, что с увеличением уровня запасов, с одной стороны, увеличиваются затраты на их хранение, но с другой стороны, уменьшаются потери вследствие возможного дефицита запасаемого продукта. Задачи распределения ресурсов возникают при определенном наборе операций (работ), которые необходимо выполнять при ограниченных наличных ресурсах, и требуется найти оптимальные распределения ресурсов между операциями или состав операций. Задачи ремонта и замены оборудования актуальны в связи с износом и старением оборудования и необходимостью его замены с течением времени. 4 Задачи сводятся к определению оптимальных сроков, числа профилактических ремонтов и проверок, а также моментов замены оборудования модернизированным. Задача составления расписания (календарного планирования) состоят в определении оптимальной очередности выполнения операций (например, обработки деталей) на различных видах оборудования. Задачи выбора маршрута, или сетевые задачи, чаще всего встречаются при исследовании разнообразных задач на транспорте и в системе связи и состоят в определении наиболее экономичных маршрутов. Среди моделей ИО особо выделяются модели принятия оптимальных решений в конфликтных ситуациях, изучаемые теорией игр. К конфликтным ситуациям, в которых сталкиваются интересы двух (или более) стон, преследующих разные цели, можно отнести ряд ситуаций в экономике, военного дела и т.п. в задачах теории игр необходимо выработать рекомендации по разумному поведению участников конфликта, определить их оптимальные стратегии. Задачи ИО можно классифицировать по учету динамики изучаемой системы на динамические и статические Задачи ИО можно классифицировать по числу критериев на одно и многокритериальные С точки зрения информированности исследователя об обстановке операции на x задачи в условиях определенности x задачи в условиях риска x задачи в условиях неопределенности. Неконтролируемые факторы, определяющие тип задачи, делятся на три группы: 1) фиксированные (значение которых известно), 2) случайные (с заданным законом распределения), 3) неопределенные, для которых известен лишь диапазон (область) изменения. Неопределенные факторы в свою очередь делятся на: 1) факторы, связанные с действием людей, противостоящих оперирующей стороне - стратегия противника, обладающего своими активными действиями. 2) факторы, связанные с недостаточной изученностью процесса, 3) факторы, отражающие нечеткость знания цели операции или критерия эффективности. Примеры задач: Задача 1. К заданному сроку необходимо провести массовое медицинское обследование населения с целью выявления определенных заболеваний. На обследование выделены материальные средства, оборудование персонал. Надо разработать такой план обследования – установить число медпунктов, их 5 размещение, вид и количество анализов, чтобы выявить как можно больший процент из числа заболевших. Задача 2. Для реализации определенной партии сезонных товаров надо создать сеть временных торговых точек. Требуется выбрать параметры этой сети – число точек, их размещение, количество персонала – так, чтобы обеспечить максимальную экономическую эффективность распродажи. Также необходимо отметить задачи об использовании ресурсов (планирования производства), об использовании мощностей (загрузке оборудования), о раскрое материалов, транспортную задачу и др, в которых требуется найти решение, когда некоторый критерий эффективности (прибыль, выручка, затраты и т.д.) принимает макс или мин значение. Приведенные задачи относятся к разным областям практики, но в них есть общие черты: в каждом случае речь идет о каком-либо управляемом мероприятии (операции), которое преследует определенную цель. В задаче 1 – массовое обследование с целью определения процента заболевших. В задаче 2 – организация временных торговых точек с целью проведения распродажи. В каждой задаче заданы некоторые условия проведения этого мероприятия, в рамках которого следует принять решение. Условия – средства, время, оборудование и т.д. Решения: в задаче1 – в выборе числа медпунктов, вида и количества анализов; в задаче 2 – в выборе числа точек размещения, количества персонала. Некоторые понятия и определения ИО: Операция - совокупность взаимосогласованных действий, направленных на достижение вполне определенной цели. До тех пор, пока цель не определена, нет смысла говорить об операции. Если же цель определена и существуют разные пути ее достижения, то желательно найти лучший из них, добиваясь надлежащей согласованности предпринимаемых действий. Понятие ”лучший” относительно и требует уточнения во всех случаях. Оно означает что либо тогда, когда назван показатель качества выбираемых решений ( например, ”план А лучше плана В с точки зрения более полной загрузки оборудования” или ”вычислительная машина одного типа лучше вычислительной машины другого типа в смысле быстродействия ”). Из этих замечаний следует утверждение об единственности цели в каждой конкретной операции. Всякий определенный выбор параметров называется решением. Оптимальными считаются те решения, которые по тем или иным соображениям предпочтительнее других. Поэтому основной задачей ИО является предварительное количественное обоснование оптимальных решений. При этом само принятие решений выходит за рамки ИО и относится к компетенции ответственного лица или группы лиц, которые могут учитывать и другие соображения, отличные от математически обоснованных. В разных задачах ИО оптимальными могут быть решения, удовлетворяющие разным критериям. Например, в задаче 2 (сезонная реализация товаров) оптимальным можно считать такое количество торговых точек и персонала в 6 них, при котором среднее время обслуживания не превышает, например, 5 мин, а длина очереди, в среднем в любой момент – не более 3 человек. Во многих задачах ИО оптимальным является решение, при котором критерий эффективности принимает макс или мин. Этапы исследования операций Можно выделить следующие основные этапы ИО: x идентификация проблемы; x построение модели; x решение поставленной задачи с помощью модели; x проверка адекватности модели; x реализация результатов исследования. Идентификация проблемы. Можно выделить основные стадии: формулировка задачи или цели исследования, выявление возможных альтернатив решения применительно к исследуемой проблемной ситуации, определение требований, условий и ограничений к исследуемой системе. Построение модели. Выбирается модель, наиболее подходящая для адекватного описания исследуемой системы. Наиболее важным типом моделей ИО являются математические модели. Математическая модель - представление какого-либо объекта, выраженное с помощью математической символики. В основе их построения лежит допущение о том, что все переменные, параметры и ограничения, а также целевая функция количественно измеримы. Чтобы построить математическую модель, необходимо оценить количественно проявления рассматриваемых факторов и указать группы рассматриваемых параметров, формально представляющие эти факторы. Однако следует иметь в виду, что никаких правил построения математических моделей не существует. Каждая модель есть проявление знаний, опыта, искусства оперирующей стороны. Процесс создания модели требует четкого осознания цели операции, проникновение в существо моделируемых явлений, умения отделить главное от второстепенного. Математические модели могут иметь вид формул, систем уравнений или неравенств, а также таблиц, числовых последовательностей, геометрических образов, отражающих зависимость между критерием эффективности операции и теми параметрами, которые представляют учтенные действующие факторы. Кроме математических моделей в ИО используются также имитационные и эвристичекие модели. Имитационная модель - модель, используемая в процессе имитационного моделирования. 7 Имитационное моделирование — это метод исследования, при котором изучаемая система заменяется моделью, с достаточной точностью описывающей реальную систему, с которой проводятся эксперименты с целью получения информации об этой системе. Имитационные модели «воспроизводят» поведение системы на протяжении некоторого промежутка времени. Это достигается путем идентификации ряда событий, распределение которых во времени дает важную информацию о поведении системы. После того, как такие события определены, требуемые характеристики системы необходимо регистрировать только в моменты реализации этих событий. Информация накапливается в виде статистических данных таких наблюдений. Для построения имитационных моделей не требуется использования математических функций, явным образом связывающих те или иные переменные, поэтому они, как правило, позволяют имитировать поведение очень сложных систем, для которых построение математических моделей невозможно. Основной недостаток имитационного моделирования заключается в том, что его реализация эквивалентна проведению множества экспериментов, а это неизбежно обуславливает наличие экспериментальных ошибок. Эвристические модели применяются при решении задач, имеющих нечисловую природу или отличающихся сложностью и неопределенностью каких-то параметров. Эвристика - это совокупность знаний, опыта, интуиции, интеллекта, используемых для получения решений с помощью неформальных правил. Обычно эти правила обосновываются с позиции ”здравого смысла” и отражают внутренние мотивы предпринимаемых действий, не поддающиеся подробному описанию. При построении модели д.б. установлены количественные соотношения для выражения целевой функции и ограничений в виде функций от переменных, которыми можно варьировать. Если разработанная модель соответствует некоторому общему классу математических моделей (например, моделям линейного программирования), то для получения решения удобно воспользоваться известными мат методами. Если математические соотношения, используемые в модели, слишком сложны и не позволяют получить аналитического решения задачи, то более подходящей м.б. имитационная модель. В некоторых случаях возникает необходимость совместного использования мат, имит и эврис моделей. Решение поставленной задачи с помощью модели. В случае использования мат модели решение получают с помощью апробированных оптимизационных методов. В случае применение имит или эврист моделей понятие оптимальности становится менее определенным и получаемое решение соответствуют лишь приближенным оценкам оптимальности функционирования системы. На этом же этапе, когда это возможно, должно быть обеспечено получение дополнительной информации о возможных 8 изменениях решения при изменениях параметров системы. Эту часть исследования обычно называют анализом системы на чувствительность. Проверка адекватности модели. Модель можно считать адекватной, если, несмотря на некоторые неточности отображения системы-оригинала, она способна обеспечить достаточно надежное предсказание поведения системы. Общий метод проверки состоит в сопоставлении получаемых результатов с характеристиками системы, которые при тех же исходных условиях имели место в прошлом. Негодится при разработке новых систем, так как нет необходимых для проверки данных. Иногда, например, при использовании мат модели, параллельно строится для проверки имит модель. Реализация результатов исследования. Написание инструкций по работе с системой. Общая постановка задачи исследования операций Все факторы, которые входят в описание операции, можно разделить на две группы: x постоянные факторы (условия проведения операции), на которые мы влиять не можем; x зависимые факторы (элементы решения), которые можно в известных пределах выбирать по своему усмотрению. Например, в задаче об использовании ресурсов к постоянным факторам можно отнести запасы ресурсов каждого вида, производственную матрицу, элементы которой определяют расход сырья каждого вида на единицу выпускаемой продукции каждого вида. Элементы решения – план выпуска продукции каждого вида. Критерий эффективности, выражаемый некоторой функцией, называется целевой, зависит от факторов обеих групп. Все модели ИО м.б. классифицированы в зависимости от природы и свойств операции, характера решаемых задач, особенностей применяемых мат методов. Класс оптимизационных моделей. Такие задачи возникают при попытке оптимизировать планирование и управление сложными системами, в первую очередь экономическими системами. Оптимизационную задачу можно сформулировать в общем виде: найти переменные х 1, х2, …, хп, удовлетворяющие системе неравенств (уравнений) φi (х1, х2, …, хп) <= bi, i=1,2,…,m (1) и обращающие в максимум (минимум) целевую функцию Z = f ((х1, х2, …, хп) Æ max (2) (Условия неотрицательности переменных, если они есть, входят ограничения (1)). в Частным случаем общей задачи является, например, классическая задача потребления, имеющая важное значение в экономическом анализе. 9 Имеется n видов товаров и услуг, количества которых (в натуральных единицах) х1, х2, …, хп по ценам p1, p2, …, pn за единицу. Суммарная стоимость этих товаров и услуг n ¦ Pi Xi . i 1 Уровень потребления Z может быть выражен некоторой функцией Z = f ((х1, х2, …, хп), называемой функцией полезности. Необходимо найти такой набор товаров и услуг х1, х2, …, хп при данной величине доходов I, чтобы обеспечить макс уровень потребления, т.е. Z = f ((х1, х2, …, хп) Æ max При условии (3) n ¦ Pi Xi <= I, (4) i 1 Хi >= 0 (i=1,2,…,n) (5) Решение этой задачи, зависящее от цен p1, p2, …, pn и величины дохода I, называют функцией спроса. В некоторых случаях для решения задачи (1) – (2) можно применять классические методы оптимизации. Если эти методы не работают, то для решения задачи (1) – (2) применяют методы математического программирования. Метод математического программирования – это метод, который состоит в отыскании экстремума функции многих переменных при ограничениях в виде системы неравенств и равенств. Если критерий эффективности (2) представляет линейную функцию и функции φi в системе ограничений (1) также линейны, то такая задача называется задачей линейного программирования. Если, исходя из содержательного смысла, ее решения должны быть целыми числами, то это задача целочисленого линейного программирования. Если критерий эффективности и (или) система ограничений задаются нелинейными функциями, то имеем задачу нелинейного программирования. В частности, если указанные функции обладают свойствами выпуклости, то полученная задача является задачей выпуклого программирования. Если в задаче математического программирования имеется переменная времени и критерий эффективности (2) выражается не в явном виде как функция переменных, а косвенно – через уравнения, описывающие протекание операций во времени, то задача является задачей динамического программирования. Если критерий эффективности (2) и (или) система ограничений (1) задаются функциями вида c*x1a1 xa2 2...xan , то такая задача называется задачей n геометрического программирования. Если функции в выражениях (1) и (или) (2) зависят от параметров, то получаем задачу параметрического программирования. 10 Если функции в выражениях (1) и (или) (2) носят случайный характер, то получаем задачу стохастического программирования. Если точный оптимум найти алгоритмическим путем невозможно из-за большого числа вариантов решения, то прибегают к методам эвристического программирования, позволяющим существенно сократить просматриваемое число вариантов и найти, если не оптимальное, то достаточно хорошее, удовлетворяющее с точки зрения практики, решение. Из перечисленных методов мат программирования наиболее распространенным и разработанным является линейное программирование. В его рамки укладывается широкий круг задач ИО. На практике в большинстве случаев успех операции оценивается не по одному, а сразу по нескольким критериям, одни из которых следует макс, а другие мин. Для того чтобы из множества критериев, в том числе и противоречащих друг другу (например, прибыль и расход), выбрать целевую функцию, необходимо установить приоритет критериев. Обозначим f1(x), f21(x), …, fn(x) (здесь x – условный аргумент). Пусть они расположены в порядке убывания приоритетов. В зависимости от определенных условий возможны в основном два варианта: x в качестве целевой функции выбирается критерий f1(x), обладающий наиболее высоким приоритетом; x рассматривается комбинация f(x) = ω1 f1(x) + ω2 f2(x) + … + ωn fn(x), где ω1, ω2, …, ωn – некоторые коэффициенты (веса). 11 Линейное программирование Оптимизационная задача была сформулирована в общем виде: найти переменные х1, х2, …, хп, обращающие в максимум (минимум) целевую функцию Z = f ((х1, х2, …, хп) Æ max (1) и удовлетворяющие системе неравенств (уравнений) φi (х1, х2, …, хп) <= bi, (2) i=1,2,…,m (Условия неотрицательности переменных, если они есть, входят ограничения (2)). в Если критерий эффективности (1) представляет линейную функцию и функции φi в системе ограничений (2) также линейны, то такая задача называется задачей линейного программирования. Понятие экономико-математической модели Существует много различных определений понятия «модель», отличающихся друг от друга. Но это понятие знакомо каждому: игрушечный корабль – модель корабля, фотоснимок пейзажа, географическая карта – модель местности, формула – математическая модель. Под моделью будем понимать условный образ какого-либо объекта, приближенно воссоздающий этот объект с помощью некоторого языка. В экономикоматематических моделях объектом является экономический процесс (например, использование ресурсов, распределение изделий между различными типами оборудования и т.п.), а языком – классические и специально разработанные математические методы. Экономико-математическая модель – математическое описание исследуемого экономического процесса или объекта. Эта модель выражает закономерности экономического процесса с помощью математических соотношений. Процедура экономико-математического моделирования заменяет дорогостоящие и трудоемкие натуральные эксперименты расчетами. При помощи ЭВМ можно достаточно быстро и дешево произвести сравнение многочисленных вариантов планов и управленческих решений. В результате отбираются наиболее оптимальные варианты. Примеры построения ЭММ экономических задач линейного программирования 1. Задача об использовании ресурсов (задача планирования производства). Для изготовления двух видов продукции П1 и П2 используют три вида ресурсов Р1, Р2 и Р3. Известны запасы этих ресурсов В1, В2 и В3 и число единиц ресурсов, затрачиваемых на изготовление единицы каждого вида 12 продукции а11, а12, а21, а22, а31, а32. Известна также прибыль, получаемая от единицы продукции П1 и П2 – соответственно С1 и С2. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет макс. ЭММ задачи: Х1 и Х2 – число единиц продукции П1 и П2 соответственно. F = С1*Х1 + С2*Х2 (1.1) При ограничениях: а11*Х1 + а12*Х2 <= В1 а21*Х1 + а22*Х2 <= В2 (1.2) а31*Х1 + а32*Х2 <= В3 По смыслу задачи Х1>=0, X2>=0. (1.3) Итак ЭММ задачи: найти такой план выпуска продукции Х = (Х1, Х2), удовлетворяющий системе (1.2) и условию (1.3), при котором функция (1.1) принимает макс значение. В общей постановке ЭММ задачи об использовании ресурсов примет вид: Найти такой план Х = (Х1, Х2, …, Хn) выпуска продукции, при котором функция F = С1*Х1 + С2*Х2 + … + Сn*Xn (1.4) принимает оптимальное значение, и справедлива система а11*Х1 + а12*Х2 + … + а1n*Xn <= В1 а21*Х1 + а22*Х2 + … + а2n*Xn <= В2 …………………………. аm1*Х1 + аm2*Х2 + … + аmn*Xn <= Вm и условие Х1>=0, X2>=0, …, Xn>=0 (1.5) (1.6) 2. Задача о раскрое материалов. На раскрой (распил, обработку) поступает материал одного образца в количестве А единиц. Требуется изготовить из него L разных комплектующих изделий в количествах, пропорциональных числам b1, b2, … bl (условие комплектности). Каждая единица материала м.б. раскроена N различными способами, причем использование i-го способа (i=1,2,…,n) дает аik единиц k-го изделия (к=1,2, …,l). Необходимо найти план раскроя, обеспечивающий макс число комплектов. Составим ЭММ задачи: Обозначим Хi – число единиц материала раскраиваемых i-ым способом, и Х – число изготавливаемых комплектов изделий. Т.к. общее количество материала равно сумме его единиц, раскраиваемых различными способами, то n ¦ Xi (2.1) a i 1 13 Требование комплектности выразится уравнениями n ¦ XiAik Bk * X (k=1,2,…, l) (2.2) i 1 Очевидно, что Хi >= ) (i=1,2,…,n) (2.3) ЭММ задачи: найти такое решение Х=(х1, х2, …, хn), удовлетворяющее системе уравнений (2.1) – (2.2) и условию (2.3), при котором функция F = х принимает макс значение. Эту задачу можно обобщить на случай m раскраиваемых материалов. Пусть каждая единица j-го материала (j = 1, 2,…, m) может быть раскроена N различными способами, причем использование i-го способа (i =1,2,…,n) дает аijk единиц k-го изделия (к=1,2, …,l), а запас j-го материала равен Aj единиц. Обозначим Хij – число единиц j-го материала раскраиваемого i-ым способом. ЭММ задачи о раскрое материалов в общей постановке примет вид: найти такое решение Х=(х11, х12, …, хnm), удовлетворяющее системе n ¦ Xij i 1 n m i 1 j 1 (j = 1, 2,…, m), Aj ¦ ¦ XijAijk Bk * X (k=1,2,…, l) (2.4) и условию Xij >= 0, при котором функция F = х принимает макс значение. 3. Задача распределения плановой величины заказа между бригадами На примере 2-х бригад и 2-х изделий. Выполнить заказ по производству Кj изделий j-ого вида взялись 2 бригады. Производительности бригад по производству изделий равны aij изделий в час (i – номер бригады, j – номер изделия), фонд рабочего времени бригад – Вi часов. Затраты каждой бригады, связанные с производством единицы каждого вида изделия, равны cij. Составить математическую модель задачи, позволяющую найти оптимальный объем выпуска изделий, обеспечивающий минимальные затраты на выполнение заказа. ЭММ задачи: Переменные задачи Искомыми величинами в задаче являются объемы выпуска двух видов изделий. Изделия будут выпускаться двумя бригадами. Поэтому необходимо различать количество разного вида изделий, произведенных первой и второй бригадами. Вследствие этого в данной задаче 4 переменные. Для удобства восприятия можно использовать двухиндексную форму записи – количество изделий (j=1,2), изготавливаемых бригадой (i=1,2), а именно: 14 х11 – количество изделий первого вида, изготавливаемых первой бригадой; х12 – количество изделий второго вида, изготавливаемых первой бригадой; х21 – количество изделий первого вида, изготавливаемых второй бригадой; х22 – количество изделий второго вида, изготавливаемых второй бригадой. Целевая функция Целью решения задачи является выполнение плана с минимальными затратами, т.е. критерием эффективности решения служит показатель затрат на выполнение всего заказа. Поэтому ЦФ должна быть представлена формулой расчета этих затрат. Затраты каждой бригады на производство одного изделия каждого вида известны из условия. Таким образом, ЦФ имеет вид: F=C11*X11 + C12*X12 + C21*X21 + C22*X22 → min Ограничения Возможные объемы производства изделий бригадами ограничиваются следующими условиями: x общее количество изделий первого вида, выпущенное обеими бригадами, должно равняться К1 шт., а общее количество изделий второго вида – К2 шт.; x время, отпущенное на работу над данным заказом, составляет для первой бригады – B1 час., а для бригады – B2 час.; x объемы производства изделий не могут быть отрицательными величинами. Таким образом, все ограничения данной задачи делятся на 3 группы, обусловленные: 1) величиной заказа на производство изделий; 2) фондами времени, выделенными бригадам; 3) неотрицательностью объемов производства. 1) Ограничения по заказу изделий будут иметь следующий вид: X11 + X21 = К1 X12 + X22 = К2 2) Ограничение по фондам времени будут иметь содержательную форму: Общее время, затраченное первой бригадой на выпуск всех изделий Общее время, затраченное второй бригадой на выпуск всех изделий <= B1 <= B2 Проблема заключается в том, что в условии задачи прямо не задано время, которое тратят бригады на выпуск одного изделия каждого вида, т.е. не задана трудоемкость производства. Но имеется информация о производительности каждой бригады, т.е. о количестве производимых изделий 15 в 1 ч. Трудоемкость и производительность являются обратными величинами, т.е.: Трудоемкость = 1 / aij В математическом виде ограничения по фондам времени будут иметь следующий вид: X 11  A11 X 21  A21 X 12  B1 A12 X 22  B2 A22 3) Неотрицательность объемов производства задается как: Xij >= 0 (i=1,2; j=1,2) Таким образом, полная математическая модель этой задачи имеет вид: F=C11*X11 + C12*X12 + C21*X21 + C22*X22 → min при ограничениях: X11 + X21 = К1 X12 + X22 = К2 X 11  A11 X 21  A21 (3.1) X 12  B1 A12 X 22  B2 A22 (3.2) Xij >= 0 (i=1,2; j=1,2) (3.3) Эту задачу можно обобщить на случай n разных видов изделий и m бригад. Выполнить заказ по производству n разного вида изделий взялись m бригад. Необходимо выпустить Кl штук изделий каждого вида (l=1,n). Производительности бригад по производству изделий равны aij изделий в час (i – номер бригады, j – номер изделия), фонд рабочего времени бригад – Вi часов. Затраты каждой бригады, связанные с производством единицы каждого вида изделия, равны cij. Полная математическая модель задачи в общем виде: m n i 1 j 1 ¦ ¦ CijXij o max m ¦ Xij i 1 n Xij ¦ Aij  Kj (3.4) (j=1,n) Bi (i=1,m) (3.5) j 1 Xij >= 0 (i=1,m; j=1,n) (3.6) 16 Общая задача линейного программирования Рассмотренные примеры задач линейного программирования позволяют сформулировать общую задачу линейного программирования. Дана линейная функция F = С1*Х1 + С2*Х2 + … + Сn*Xn (1) и система m линейных уравнений и неравенств с n переменными а11*Х1 + а12*Х2 + … + а1n*Xn <= В1 а21*Х1 + а22*Х2 + … + а2n*Xn <= В2 …………………………. ак1*Х1 + ак2*Х2 + … + акn*Xn <= Вк ак+1,1*Х1 + ак+1,2*Х2 + … + а к+1,n*Xn = В к+1 (2) а к+2,1*Х1 + а к+2,2*Х2 + … + а к+2,n*Xn = В к+2 …………………………. аm1*Х1 + аm2*Х2 + … + аmn*Xn = Вm Найти такое решение системы Х = (Х1, Х2, …,Xj,…, Хn), где Хj>=0 (j = 1, 2,…, n) (3) при котором линейная функция (1) принимает оптимальное (макс или мин) значение. Система (2) называется системой ограничений, а функция F – линейной функцией, линейной формой, целевой функцией или функцией цели. Более кратко общую задачу линейного программирования можно представить в виде: F= n ¦ CjX j Æ max (min) j 1 При ограничениях: n ¦ АijXj  Bi (I = 1, 2, …, k) j 1 n ¦ АijXj Bi (I = k+1, k+2, …, m) j 1 Хj>=0 (j = 1, 2,…, l; l<=n) Оптимальным решением (или оптимальным планом) задачи ЛП называется решение Х = (Х1, Х2, …,Xj,…, Хn) системы ограничений (2), при котором линейная функция (1) принимает оптимальное (макс или мин) значение. Термины «решение» и «план» - синонимы, однако первый используется чаще, когда речь идет о формальной стороне задачи (ее математическом решении), а второй – о содержательной стороне (экономической интерпретации). При условии, что все переменные неотрицательны (Хj>=0, j = 1, 2,…, n), система ограничений (2) состоит лишь из одних неравенств, - такая задача ЛП 17 называется стандартной; если система ограничений (2) состоит из одних уравнений, то задача называется канонической. В приведенных выше примерах задача 1 – стандартная, 2 – каноническая, 3 – общая. Любая задача ЛП м.б. сведена к канонической, стандартной или общей. Вспомогательная теорема (без доказательства): Всякому решению неравенства аi1*Х1 + аi2*Х2 + … + аin*Xn <= Вi (4) соответствует определенное решение уравнения аi1*Х1 + аi2*Х2 + … + аin*Xn + Хn+i= Вi в котором Хn+i>=0 I = 1,m (5) (6) и, наоборот, каждому решению уравнения (5) и неравенства (6) соответствует определенное решение неравенства (4). Используя эту теорему, можно представить любую стандартную задачу в каноническом виде. С этой целью в каждое из m неравенств в системе ограничений вводятся дополнительные неотрицательные переменные Xn+1, Xn+2, Хn+m и система ограничений примет вид: а11*Х1 + а12*Х2 + … + а1n*Xn + Xn+1 = В1 а21*Х1 + а22*Х2 + … + а2n*Xn + Xn +2 = В2 ……………………………………………………………. аm1*Х1 + аm2*Х2 + … + аmn*Xn + Xn +m = Вm Замечание. В рассматриваемой задаче все неравенства вида <=, поэтому дополнительные неотрицательные переменные вводились со знаком «+». В случае неравенства вида >= соответствующие дополнительные неотрицательные переменные вводились бы со знаком «-». Система m линейных уравнений с n переменными Система m линейных уравнений с n переменными имеет вид: а11*Х1 + а12*Х2 + …+ а1j*Xj + …+ а1n*Xn = В1 а21*Х1 + а22*Х2 + …+ а2j*Xj + … + а2n*Xn = В2 …………………………. аi1*Х1 + аi2*Х2 +…+ аij*Xj + … + а in*Xn = В i …………………………. аm1*Х1 + аm2*Х2 + … + аmn*Xn = Вm или в краткой записи n ¦ АijXj Bi (I = 1, 2, …, m) j 1 18 (6) в задачах ЛП представляют интерес системы, в которых максимальное число независимых уравнений системы меньше числа переменных. Будем полагать, что в системе (6) все m уравнений системы независимы, т.е. m < n. Любые m переменных системы m линейных уравнений с n переменными (m < n) называются основными (базисными), если определитель матрицы коэффициентов при них отличен от нуля. Тогда остальные n - m переменных называются неосновными (или свободными). Основными могут быть разные группы из n переменных, но общее число групп не превосходит число сочетаний C nm . C nm = n! / ((n-m)! m!) Пример: Найти все возможные группы основных переменных в системе х1 – х2 – 2х3 + х4 = 0 (7) 2х1 + х2 + 2х3 – х4 = 2 Решение. Общее число групп основных переменных не более чем C 42 = 4*3/2 = 6, т.е. возможны группы основных переменных: х1, х2; х1, х3; х1, х4; х2, х3; х2, х4; х3, х4. Переменные х1, х2 могут быть основными, т.к. определитель матрицы из коэффициентов при этих переменных 1 1 2 1 = 1 * 1 – 2 * (-1) = 3 z 0. рассуждая аналогично, можно найти, что могут быть основными переменные х1, х3; х1, х4, но не могут быть основными х2, х3; х2, х4; х3, х4, т.к. соответствующие определители равны 0. х3, х4 2 1 = (-2) * (-1) – 2 * 1 = 0. 2 1 Существует теорема. Если для системы из m линейных уравнений с n переменными ((m < n) существует хотя бы одна группа основных переменных, то эта система является неопределенной, причем каждому произвольному набору значений неосновных переменных соответствует одно решение системы. Пусть, например, х1, х2, …, хm – основные переменные (если это не так, то нумерацию можно изменить), то определитель матрицы a11 a12 a 21 a 22 ... ... am1 am2 ... a1m ... a 2m ... ... ... amm z 0. Оставим в левых частях уравнений системы (6) члены с переменными х1, х2, …, хm, а члены с переменными xm+1, xm+2, …, xn перенесем в правые части. Получим: а11*Х1 + а12*Х2 + …+ а1m*Xm = В1 - а1m+1*Xm+1 - … - а1n*Xn а21*Х1 + а22*Х2 + …+ а2m*Xm = В2 – а2m+1*Xm+1 - … - а2n*Xn 19 ……………………………………………………………………. аm1*Х1 + аm2*Х2 + …+ аmm*Xm = Вm - аmm+1*Xm+1 - … - аmn*Xn Задавая неосновным переменным xm+1, xm+2, …, xn произвольные значения, каждый раз будем получать новую систему с новыми свободными членами. Каждая из полученных систем будет иметь один и тот же определитель, т.е. каждая из систем будет иметь единственное решение. Так как получаемых таким образом систем бесконечное множество, то и система (6) будет иметь бесконечное множество решений. Решение Х = (х1, х2, …, хn) системы (6) называется допустимым, если оно содержит лишь неотрицательные компоненты, т.е. Хj >=0 для любых j = 1, 2, …, n. В противном случае решение называется недопустимым. Среди бесконечного множества решений системы выделяют базисные решения. Базисным решением системы m линейных уравнений с n переменными называют решение, в котором все n – m неосновных переменных равны нулю. В задачах ЛП особый интерес представляют допустимые базисные решении, или, как их еще называют, опорные планы. Число базисных решений является конечным, т.к. оно равно числу групп основных переменных, не превосходящему C nm . Базисное решение, в котором хотя бы одна из основных переменных равна нулю, называется вырожденным. Пример: В примере (7) существует три группы основных переменных, т.е. число базисных решений = 3. Первое х1 и х2 – основные, х3 и х4 – неосновные (= 0), тогда х1 – х2 = 0 2х1 + х2 = 2 откуда х1 =2/3; х2 = 2/3. следовательно первое баз решение системы Х1 = (2/3; 2/3; 0; 0) –допустимое. Если взять за основные переменные Х1 и Х3, то получим второе баз решение системы Х2 = (2/3; 0; 2/3; 0) – также допустимое. Аналогично можно найти третье баз решение при основных переменных х1, х4 Х3 = (2/3; 0; 0; 2/3) – недопустимое. Вывод: Совместная система (6) имеет бесконечно много решений, из них базисных решений – конечное число, не превосходящее C nm . Геометрический смысл решений неравенств, уравнений и их систем Теорема 1. Множество решений неравенства с двумя переменными а11х1 + а12х2 <= b1 является одной из двух полуплоскостей, на которые вся плоскость делится прямой а11х1 + а12х2 = b1, включая и эту прямую, а другая полуплоскость с той же прямой есть множество решений неравенства а11х1 + а12х2 >= b1. Пример: 3х1 – 4х2 + 12 <= 0 20 5 4,5 4 3,5 3 Х2 2,5 2 1,5 1 0,5 -5 -4 -3 -2 -1 1 2 3 Х1 Для определения искомой полуплоскости (верхней или нижней) рекомендуется задать произвольную контрольную точку, не лежащую на ее границе – построенной прямой. Если неравенство выполняется в контрольной точке, то оно выполняется и во всех точках полуплоскости, содержащей контрольную точку, и не выполняется во всех точках другой полуплоскости. Учитывая, что множество точек, удовлетворяющих уравнению а11х1 + а12х2 +… + a1nxn = b1 при n=3 является плоскостью, а при n>3 – ее обобщением в n – мерном пространстве – гиперплоскостью, можно обобщить вышесформулированную теорему на случай трех и более переменных. Теорема 2. Множество решений линейного неравенства с n переменными а11х1 + а12х2+… + a1nxn <= b1 является одним из двух полупространств, на которые все пространство делится плоскостью или гиперплоскостью а11х1 + а12х2 +… + a1nxn = b1, включая и эту плоскость (гиперплоскость). Теорема 3. Множество решений совместной системы m линейных неравенств с двумя переменными а11*Х1 + а12*Х2 <= В1 а21*Х1 + а22*Х2 <= В2 …………………………. аm1*Х1 + аm2*Х2 <= Вm является выпуклым многоугольником (или выпуклой многоугольной областью). Каждое из неравенств в соответствии с теоремой 1 определяет одну из полуплоскостей, являющуюся выпуклым множеством точек (из математики: выпуклое множество точек – если оно вместе с любыми двумя своими точками содержит весь отрезок, соединяющий эти точки). Множество решений совместной системы линейных неравенств служат точки, которые принадлежат полуплоскостям решений всех неравенств, т.е. их пересечению. Согласно существующей теореме о том, что пересечение (общая часть) любого числа выпуклых множеств есть выпуклое множество – множество решений совместной системы линейных неравенств является выпуклым и содержит конечное число угловых точек, т.е. является выпуклым многоугольником (выпуклой многоугольной областью). Пример: Построить множество решений системы неравенств: -5х1 + 4х2 <= 20 (I) 2х1 + 3х2 <= 24 (II) х1 - 3х2 <= 3 (III) x2 <= 6 (IV) 21 х1,х2 >=0 (V, VI) 10 I 8 С(3;6) 6 IV В(4/5;6) А(0;5) II 4 D(9;2) 2 V -8 -6 -4 -2 III Е(3;0) 2 4 6 8 10 -2 -4 -6 Координаты угловых точек – вершин многоугольника находятся как координаты точек пересечения соответствующих прямых. Например, точка D – пересечение прямых II и III, т.е. ее координаты являются решением системы 2х1 +3х2 <= 24 (II) х1 - 3х2 <= 3 (III) откуда Х1 = 9, Х2 = 2, т.е. D(9;2). Аналогично находятся координаты других угловых точек: О(0;0), А(0;5), В(4/5;6), С(3;6), Е(3;0). При построении областей решений систем неравенств (ОДЗ) могут встретиться следующие случаи: ƒ множество решений – выпуклый многоугольник; ƒ множество решений – выпуклая многоугольная область; ƒ одна точка; ƒ пустое множество, когда систем неравенств несовместима. Утверждение: 22 Между допустимыми базисными решениями и угловыми точками множества допустимых решений системы линейных уравнений существует взаимооднозначное соответствие. Рассмотрими последнее утверждение на примере: Для системы, приведенной выше можно получить четыре допустимых базисных решения. Группы основных переменных могут быть любые, т.к. все определители не равны 0: х1 и х2 (х3, х4 = 0) – недопустимое (т.к. х1 = -9, х2 = 10), х1 и х3 (х2, х4 = 0) – допустимое Х1 = (1;0;10;0), х1 и х4 (х2, х3 = 0) – допустимое Х2 = (6;0;0;5), х2 и х3 (х1, х4 = 0) – допустимое Х3 = (0;1;9;0), х2 и х4 (х1, х3 = 0) – допустимое Х4 = (0;4;0;3), х3 и х4 (х1, х2 = 0) – недопустимое (т.к. х3 = 12, х4 = -1). Из рисунка, иллюстрирующего решение, видно, что этим допустимым базисным решениям соответствуют угловые точки D(1;0), С(6;0), А(0;1) и В(0;4) четырехугольника ABCD. Свойства задач ЛП Выше было показано, что любая задача ЛП м.б. представлена в виде общей, канонической или стандартной задачи. Причем, от одной задачи можно перейти к другой. Будем рассматривать каноническую задачу, в которой система ограничений – система уравнений. Теорема. Если задача ЛП имеет оптимальное решение, то линейная функция принимает макс (мин) значение в одной из угловых точек многогранника решений (ОДЗ). Эта теорема является фундаментальной, т.к. она указывает принципиальный путь решения ЗЛП. Действительно, согласно этой теореме вместо исследования бесконечного множества допустимых решений для нахождения среди них искомого оптимального решения необходимо исследовать лишь конечное число угловых точек многогранника решений. Теорема. Каждому допустимому базисному решению ЗЛП соответствует угловая точка многогранника решений, и наоборот, каждой угловой точке многогранника решений соответствует допустимое базисное решение. Из двух последних теорем вытекает следствие: если ЗЛП имеет оптимальное решение, то оно совпадает, по крайней мере, с одним из ее допустимых базисных решений. Итак, оптимум линейной функции ЗЛП следует искать среди конечного числа ее допустимых базисных решений. Геометрический метод решения задач ЛП Итак, выше было доказано, что множество допустимых решений (многогранник решений) ЗЛП представляет собой выпуклый многогранник 23 (или выпуклую многогранную область), а оптим решение задачи находится, по крайней мере, в одной из угловых точек многогранника решений. Рассмотрим задачу в стандартной форме Найти такой план Х = (Х1, Х2, …, Хn) выпуска продукции, удовлетворяющий системе 24 а11*Х1 + а12*Х2 + … + а1n*Xn <= В1 а21*Х1 + а22*Х2 + … + а2n*Xn <= В2 …………………………. аm1*Х1 + аm2*Х2 + … + аmn*Xn <= Вm и условию Х1>=0, X2>=0, …, Xn>=0, при котором функция F = С1*Х1 + С2*Х2 + … + Сn*Xn принимает макс значение. с двумя переменными (n=2). К такой форме может быть сведена и каноническая задача (с ограничениями в виде уравнений), когда число переменных n больше числа уравнений m на 2, т.е. n – m = 2. Этапы решения задач геометрическим способом: I. Построение ограничений и определения полуплоскости действия каждого ограничения. II. Определение общей области допустимых значений. III. Построение линий ЦФ при двух любых произвольных значениях для определения наклона этой линии и направления роста (уменьшения). IV. Определение точки ОДЗ, в которой ЦФ последний раз пересечет эту область в сторону увеличения (уменьшения), т.е. точки оптимального решения. V. Определение координат точки оптимального решения. F=a F = Fmax C B F = Fmin F=0 A E D O ABCDE – геометрическое изображение системы ограничений. Необходимо среди точек этого многоугольника найти такую точку, в которой линейная функция F = С1*Х1 + С2*Х2 принимает макс или мин значение. Рассмотрим линию, вдоль которой функция принимает одно и тоже фиксированное значение а, т.е. F = а, или с1*х1 + с2*х2 = а. На многоугольнике решений следует найти точку, через которую проходит такая линия функции с наибольшим (при макс функции) или наим (при мин функции) значением. Уравнение линии с1*х1 + с2*х2 = а – это уравнение прямой линии. При различных значениях а линии будут параллельны, т.к. их угловые 25 коэффициенты определяются соотношением между коэффициентами с1 и с2 и, следовательно равны. Важное свойство линии уровня состоит в том, что при параллельном смещении линии в одну сторону уровень только возрастает, а при смещении в другую – только убывает. Может быть неограниченная прямоугольная область: В данном примере есть мин, но нет макс. А В С В вышеприведенных примерах макс и мин достигались в одной точке, т.е. задача имела единственное решение. Могут быть другие варианты: А В D С с1 с2 На левом рисунке видно, что линия уровня с макс уровнем совпадает с граничной линией АВ многоугольника решений АВСD. Следовательно на отрезке АВ линейная функция принимает одно и то же макс значение. Это значит, что задача имеет бесконечно много оптимальных решений (их задают координаты точек отрезка АВ), среди которых базисных оптим решений два – соответственно в угловых точках А и В. Точки отрезка АВ задаются уравнением соответствующей прямой, где с1 <= Х1<= c2. При геометрическом решении подобных задач может быть неточность построения. Надо убедиться, что линия уровня совпадает с границей многоугольника решений. Это может быть, если они параллельны, т.е. их коэффициенты при переменных пропорциональны. На правом рисунке показано, что если перемещать линию уровня в направлении убывания линейной функции, то она всегда будет пересекать многоугольник решений, т.е. лин функция неограниченно убывает (нет конечного оптимума). Если при геометрическом решении ЗЛП получен вариант, когда условия задачи противоречивы, т.е. область допустимых решений системы ограничений – пустое множество, то ясно, что оптим решения нет и нет смысла строить линию уровня. 26 Плюсы геом метода: ▪ ƒ Минусы геом метода: ▪ ƒ нагляден, быстро получить ответ. возможны техн погрешности, можно применять когда только 2 переменных. Симплексный метод Выше были рассмотрены основные теоремы ЛП. Из них следует, что если ЗЛП имеет оптимальное решение, то оно соответствует хотя бы одной точке многогранника решений и совпадает хотя бы с одним из допустимых базисных решений системы ограничений. Там же мы рассмотрели, что путем решения любой ЗЛП является перебор конечного числа допустимых базисных решений системы ограничений и выбор среди них того, на котором функция цели принимает оптимальное значение. Геометрически надо перебрать все угловые точки многогранника решений. Трудно осуществить, т.к. для реальных задач число ДБР хоть и конечно, но м.б. велико. Число перебираемых ДБР можно сократить, если производить перебор не беспорядочно, а с учетом изменений линейной функции, т.е. добиваясь, чтобы каждое следующее решение было «лучше» (или, по крайней мере, «не хуже») предыдущего по значению целевой функции. Предположим, точка А – исходное ДБР. Из чертежа видно, что от А выгодно перейти к В, а потом к С. Идея последовательного улучшения решения легла в основу универсального метода решения ЗЛП – симплексного метода. Впервые был предложен амер. ученым Дж. Данцигом в 1949 г., хотя идеи метода были разработаны Л. В. Канторовичем в 1939 году. Метод используется для компьютерных расчетов. Для реализации метода необходимо освоить три основных элемента: ƒ способ определения первоначального ДБР задачи; ƒ правило перехода к лучшему (не худшему) решению; ƒ критерий проверки оптимальности найденного решения. Для использования симплексного метода ЗЛП д.б. приведена к каноническому виду, т.е. система ограничений – в виде уравнений. 27 Нахождение оптимума линейной функции Пример: Решим симплексным методом задачу: F=2x1 + 3х2 Æ max при ограничениях: х1 + 3х2 <= 18 2х1 + х2 <= 16 х2 <= 5 3x1 <= 21 х1, х2 >= 0 х5=0 А5 х1=0 F=Fmax=24 В С х3=0 х4=0 D х2=0 х6=0 Е Перейдем к канонической форме с помощью дополнительных неотрицательных переменных: х1 + 3х2 + х3 = 18 2х1 + х2 + х4 = 16 х2 + х5 = 5 3x1 + х6 = 21 Для нахождения первоначального БР разобъем на основные (базисные) и неосновные (свободные). Т.к. определитель при переменных х3 – х6 не равен 0, то на первом шаге – основные. Не обязательно составлять определитель на первом шаге. Следующее правило: В качестве основных переменных на первом шаге следует выбрать (если возможно) такие m переменных, каждая из которых входит только в одно из m уравнений системы ограничений, при этом нет таких уравнений системы, в которые не входит ни одна из этих переменных. Если выбранные переменные имеют те же знаки, что и соответствующие им свободные члены, то полученное БР будет ДБР. Если получено не ДБР, то М-метод. Будет рассмотрен дальше. 1 шаг. Осн – х3, х4, х5, х6. Неосн – х1, х2. Х3 = 18 – х1 – 3х2 Х4 = 16 – 2х1 – х2 (1) Х5 = 5 – х2 Х6 = 21– 3х1 Неосновные = 0ÆХ1 =(0; 0; 18; 16; 5; 21) соответствует вершине О(0; 0). 28 Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2. При решении Х1 значение функции F(X1) = 0. Функцию можно увеличить за счет увеличения любой из неосновных переменных, входящих в уравнение для функции с положительным коэффициентом. Это можно осуществить перейдя к такому новому ДБР, в котором эта переменная будет основной, т.е. принимать не нулевое, а положительное значение (если новое решение будет вырождено, то функция цели сохранит свое значение). Одна из переменных, при этом из основных – в неосновные. Геометрически – к соседней вершине. В данном примере и х1 и х2 можно. Выберем х2 – больший коэффициент. Система (1) накладывает ограничения на рост переменной х2. Т.к. необходимо сохранять допустимость решений, т.е. все переменные неотрицательны, то должны выполняться неравенства (х1 при этом = 0 как неосновная): Х3 = 18 – 3х2 >= 0 Х4 = 16 – х2 >= 0 Х5 = 5 – х2 >= 0 Х6 = 21 >= 0 откуда Х2 <= 18/3 Х2 <= 18/1 Х2 <= 5/1 Каждое уравнение системы (1), кроме последнего, определяет оценочное отношение – границу роста переменной х2, сохраняющую неотрицательность соответствующей переменной. Эта граница определяется абсолютной величиной отношения свободного члена к коэффициенту при х2 при условии, что эти числа имеют разные знаки. Граница - f: ƒ Последнее уравнение системы не ограничивает рост переменной х2, т.к. эта переменная не входит в него (входит с 0 коэффициентом). ƒ Когда свободный член и коэффициент при переменной имеют одинаковые знаки, так как и в этом случае нет ограничения на рост переменной. ƒ Не накладывает ограничений на рост переменной, переводимой в основные, и такое уравнение, где свободный член = 0, а переводимая переменная имеет знак +. При свободном члене = 0, а переводимая переменная имеет знак – уравнение ограничивает рост переменной 0. В данном примере наибольшее возможное значение для х2 = min{18/3; 16/1; 5/1; f} = 5. При х2 = 5 переменная х5 обращается в 0 и переходит в неосновные. Уравнение, где достигается наибольшее возможное значение переменной, переводимой в основные (т.е. где оценка минимальна) называется разрешающим. В данном случае – 3. выделяется рамкой в системе ограничений. 29 2 шаг. Осн – х2, х3, х4, х6. Неосн – х1, х5. Х2 = 5 – х5 Х3 = 18 – х1 – 3(5 – х5) Х4 = 16 – 2х1 – (5 – х5) Х6 = 21– 3х1 или Х2 = 5 – х5 Х3 = 3 – х1 + 3 х5 Х4 = 11 – 2х1 + х5 Х6 = 21– 3х1 (2) Неосновные = 0ÆХ2 =(0; 5; 3; 11; 0; 21) соответствует вершине А(0; 5). Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2 = 2х1+ 3(5 – х5) = 15+ 2х1 – 3х5. При решении Х2 значение функции F(X2) = 15. Изменение значения линейной функции можно определить заранее как произведение наибольшего возможного значения переменной, переводимой в основные, на ее коэффициент в целевой функции (изменение F = 5 * 3 =15. Значение F2 не является макс, т.к., повторяя рассуждения шага 1, можно обнаружить возможность дальнейшего увеличения лин функции за счет переменной х1, входящий в выражение для F с положительным коэффициентом. Система (2) определяет наибольшее возможное значение для х1 = min{f; 3/1; 11/2; 21/3} = 3. второе уравнение – разрешающее, переменная х3 обращается в 0 и переходит в неосновные, при этом приращение целевой функции = 3*2 = 6. 3 шаг. Осн – х1, х2, х4, х6. Неосн – х3, х5. Выражаем новые основные переменные через новые неосновные, начиная с разрешающего уравнения. После преобразования получаем: Х1 = 3 – х3 + 3 х5 Х2 = 5 – х5 Х4 = 5 + 2х3 - 5х5 (3) Х6 = 12 + 3х3 – 9х5 Неосновные = 0ÆХ3 =(3; 5; 0; 5; 0; 12) соответствует вершине В(3; 5). Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2 = 2(3 – х3 +3х5) + 3(5 – х5) = 21- 2х3 + 3х5. При решении Х3 значение функции F(X3) = 21. 30 Значение F3 не является оптим, т.к. можно обнаружить возможность дальнейшего увеличения лин функции за счет переменной х5, входящий в выражение для F с положительным коэффициентом. При определении наибольшего возможного значения для х5, которую переводим в основные, обратить внимание, что первое уравнение системы (3) не дает ограничения на рост х5, т.к. свободный член и коэффициент при х5 имеют одинаковые знаки. Система (3) определяет наибольшее возможное значение для х5 = min{f; 5; 1; 12/9} = 1. Третье уравнение – разрешающее, переменная х4 обращается в 0 и переходит в неосновные, при этом приращение целевой функции = 1*3 = 3. 4 шаг. Осн – х1, х2, х5, х6. Неосн – х3, х4. Выражаем новые основные переменные через новые неосновные, начиная с разрешающего уравнения. После преобразования получаем: Х1 = 6 + 1/5х3 – 3/5х4 Х2 = 4 – 2/5х3 + 1/5х4 Х5 = 1 + 2/5х3 – 1/5х4 (3) Х6 = 3 – 3/5х3 + 9/5х4 Неосновные = 0ÆХ4 =(6; 4; 0; 0; 1; 3) соответствует вершине С(6; 4). Решение – допустимое, м.б. оптимальным. Проверим. Выразим целевую функцию через неосновные переменные F=2x1 + 3х2 = 24 – 4/5х3 – 3/5х4. При решении Х4 значение функции F(X4) = 24. Значение F4 является оптим, т.к. нет положительных коэффициентов при неосновных переменных. Вспоминая экономический смысл всех переменных, можно сделать следующие выводы: ƒ Прибыль предприятия примет макс значение 24 руб. при реализации 6 ед. продукции первого вида (х1 = 6) и 4 ед. продукции второго вида (х2 = 4). ƒ Дополнительные переменные х3, х4, х5 и х6 показывают разницу между запасами ресурсов каждого вида и их потреблением, т.е. остатки ресурсов. При оптим плане производства х3 = х4 = 0, т.е. остатки первого и второго ресурсов равны 0, а остатки третьего и четвертого ресурсов равны соответственно 1 и 3 единицам. В общем виде можно сформулировать критерий оптимальности при отыскании макс лин функции: если в выражении линейной функции через неосновные переменные отсутствуют положительные коэффициенты при неосновных переменных, то решение оптимально. При отыскании мин лин функции Z возможны два пути: 1) отыскать макс лин функции F, полагая, что F = - Z и учитывая, что Zmin = - Fmax; 31 2) модифицировать симплексный метод: на каждом шаге уменьшать лин функцию за счет той неосновной переменной, которая входит в выражение лин функ с отрицательным коэффициентом. В общем виде можно сформулировать критерий оптимальности при отыскании мин лин функции: если в выражении линейной функции через неосновные переменные отсутствуют отрицательные коэффициенты при неосновных переменных, то решение оптимально. Замечание. На каждом шаге симплексного метода какая-либо неосновная переменная переводится в основные, при этом каждое уравнение системы ограничении определяет конечное или бесконечное наибольшее возможное значение этой переменной – оценочное отношение. Могут встречаться различные случаи оценки роста неосновной переменной, которые зависят от знаков и значений свободного члена и коэффициентов при переводимой переменной. Введем обозначения: Xi – переводимая неосновная переменная; Bj– свободный член; Aij – коэффициент при Xi; Сформулируем все возможные случаи оценки роста Xi в уравнении Xj = Bj + … + AijXi + … : 1) Хi = ~Bj/Aij~, если Bj и Aij разного знака и Aij не = 0, Bj не = 0. 2) Хi = f, если Bj и Aij одного знака и Aij не = 0, Bj не = 0. 3) Хi = 0, если Bj = 0 и Aij > 0. 4) Хi = f, если Bj = 0 и Aij < 0. 5) Хi = f, если Aij = 0. Особые случаи симплексного метода Неединственность оптимального решения (альтернативный оптимум): Решим симплексным методом задачу: F=3x1 + 3х2 Æ max при ограничениях: х1 + х2 <= 8 2х1 - х2 >= 1 A х1 - 2х2 <= 2 B х1, х2 >= 0 F=24 Геометрическое решение: Оптимум в любой точке отрезка АВ. Т.к. линия уровня параллельна этому отрезку. При решении задачи симплекс-методом наличие альтернативного оптимума проявляется следующим образом: На очередном шаге получим: осн пер – х1, х2, х5; неос п - х3, х4. Выражение основных через неосн: Х1 = 5 – (2/3)Х3 – (1/3)Х4 32 Х2 = 3 – (1/3)Х3 + (1/3)Х4 Х5 = 9 – Х3 – Х4 Х1 = (3; 5; 0; 0; 9) – ДБР, соответствует угловой точке А (3; 5). Линейная функция F = 24 – Х3. В выражении отсутствуют положительные коэффициенты при неосновных переменных, значит критерий оптимальности выполнен, т.е. Х1 – оптим БР, Fмакс = 24. Однако в последнем выражении для F = 24 – Х3 отсутствует неосновная переменная Х4 (входит с нулевым к-ом), поэтому изменение этой переменной не приведет к изменению цел функции. Вырожденность базисного решения: Решим симплексным методом задачу: F=2x1 - х2 Æ max при ограничениях: х1 - х2 <= 2 3х1 - 2х2 <= 6 6х1 - 4х2 <= 14 х1, х2 >= 0 На первом шаге получим: осн пер – х3, х4, х5; неос п - х1, х2. Выражение основных через неосн: Х3 = 2 - Х1 + Х2 Х4 = 6 – 3Х1 + 2Х2 Х5 = 14 – 6Х1 + 4Х2 Х1 = (0; 0; 2; 6; 14) – допустимое БР. Линейная функция F = 2x1 - х2. Переводя Х1 в основные, получаем Х1 = min{2; 6/3; 14/6} = 2. Оценочные отношения в первых двух совпадают. Любое выбираем. На втором шаге получим: осн пер – х1, х4, х5; неос п - х2, х3. Выражение основных через неосн: Х1 = 5 + Х2 – Х3 Х4 = 0 – Х2 + 3Х3 Х5 = 2 – 2Х2 + 6Х3 Х2 = (2; 0; 0; 0; 2) – вырожденное БР, т.к. осн переменная Х4 = 0. Линейная функция F = 4 + Х2 – 2Х3. Переводя Х2 в основные, получаем Х2 = min{f; 0; 1} = 0, поэтому на следующем шаге изменения целевой функции не произойдет (0 * 1). Это нарушение принципа улучшения решения. Поэтому принцип – не ухудшить. Следующий шаг данного примера тоже приведет к вырожденному БР. Этот шаг, хоть и не вызвал увеличения значения цел функции, привел к новому БР. Наличие «пустых» шагов может привести к «зацикливанию» - не рассматриваем. Вывод: 33 Если на каком-либо шаге наибольшее возможное значение переменной достигается в нескольких уравнениях одновременно (совпадают их оценочные отношения), то разрешающее – любое из них. На очередном шаге получим вырожденное БР. Отсутствие конечного оптимума: Решим симплексным методом задачу: F=2x1 - 3х2 + 1Æ min при ограничениях: х1 + х2 >= 4 2х1 - х2 >= 1 х1 - 2х2 <= 1 F=0 х1, х2 >= 0 На очередном шаге получим: осн пер – х1, х2, х5; A неос п - х3, х4. B Выражение основных через неосн: Х1 = 5/3 + 1/3 Х3 + 1/3 Х4 Х2 = 7/3 + 2/3 Х3 – 1/3 Х4 Х5 = 4 + Х3 – Х4 Х1 = (5/3; 7/3; 0; 0; 4) – допустимое БР. Линейная функция F = -8/3 4/3x3 + 4/3х4. Переводя Х3 в основные (т.к. имеет отрицательный коэффициент, а ищем мин), получаем Х3 = min{f; f; f} = f, т.к. во все уравнения эта переменная входит со знаком свободного члена. Уравнения не ограничивают рост Х3, поэтому и целевая функция неограниченно убывает. Вывод: Если на каком-либо шаге получаем, что во всех уравнениях системы бесконечны оценочные отношения той переменной, которую переводим в основные, то задача не имеет конечного оптимума. Симплексные таблицы Практические расчеты с использованием симплекс метода – на компьютере. Если вручную, то используются симплекс-таблицы. Будем решать задачу на максимум. I. После введения добавочных переменных систему уравнений и лин функцию записывают в виде, который называется расширенной системой: (Слайд 2) а11*Х1 + а12*Х2 + … + а1n*Xn + Xn+1 = В1 а21*Х1 + а22*Х2 + … + а2n*Xn + Xn +2 = В2 ……………………………………………………………. аm1*Х1 + аm2*Х2 + … + аmn*Xn + Xn +m = Вm F – c1X1 – c2X2 - … - cnXn =0 Предполагаем, что все добавочные переменные имеют тот же знак, что и свободные члены, в противном случае используется М-метод (рассмотрим дальше). II. Исходную расширенную систему заносим в первую симплексную таблицу. Последняя строка таблицы, в которой уравнение целевой функции – оценочная. В левом столбце таблицы – основные переменные 34 (базис), в первой строке – все переменные (отмечая при этом основные), во втором столбце – свободные члены. Последний столбец – для оценочных отношений. В рабочую часть таблицы (начиная с третьего столбца и второй строки) занесены коэффициенты Aij. III. Проверим выполнения критерия оптимальности (при макс – наличие отриц коэффициентов в последней строке, т.к. они с «-»). Если их нет, то достигнут максимум (его значение – в левом нижнем углу таблицы), основные переменные – значение второго столбца, неосновные = 0, т.е. оптимальное БР. IV. Если критерий оптим не выполнен. То наибольший по модулю отрицательный коэффициент в последней строке определяет разрешающий столбец. Составляем оценочные отношения каждой строки по правилам: 1) ~Bi/Aij~, если Bi и Aij одного знака и Aij не = 0, Bi не = 0. 2) f, если Bi и Aij разного знака и Aij не = 0, Bi не = 0. 3) 0, если Bi = 0 и Aij > 0. 4) f, если Bi = 0 и Aij < 0. 5) f, если Aij = 0. Определяем min по I для {~Bi/Aij~}. Если конечного минимума нет, то нет конечного оптимума. Если минимум конечен, то выбирается строка q, на которой он достигается (любая, если их несколько), называется разрешающей строкой. На пересечении разрешающий элемент Aqs. V. Переходим к следующей таблице по правилам: 1) в левом столбце записываем новый базис: вместо основной переменной Xq – переменную Xs; 2) в столбцах, соответствующих основным переменным, проставляем: 1 – против «своей основной переменной, 0 – против «чужой основной переменной, 0 – в последней строке для всех основных переменных; 3) новую строку с номером q получаем из старой делением на разрешающий элемент Aqs; 4) все остальные новые элементы Aij вычисляем по правилу прямоугольника: (Слайд 3) Aij' Aij  Bi' Bi  AisAqj Aqs AisBq Aqs Далее перейти к п. III алгоритма. Пример (решали как пример симплекс-метода): 35 F=2x1 + 3х2 Æ max при ограничениях: Расширенная система имеет вид: х1 + 3х2 + х3 = 18 2х1 + х2 + х4 = 16 х2 + х5 = 5 3x1 + х6 = 21 х1, х2, х3, х4, х5, х6 >= 0 х1 + 3х2 <= 18 2х1 + х2 <= 16 х2 <= 5 3x1 <= 21 х1, х2 >= 0 Базис Х3 Х4 Х5 Х6 F Базис Х3 Х4 Х2 Х6 F Базис Х1 Х4 Х2 Х6 F Базис Х1 Х5 Х2 Х6 F Свободный член Х1 18 1 16 2 5 21 3 -2 F - 2x1 - 3х2 = 0 Переменные Х2 Х3 Х4 Х5 Х6 3 1 1 1 1 1 1 -3 Свободный член Х1 3 1 11 2 5 21 3 15 -2 Переменные Х2 Х3 Х4 Х5 1 -3 1 -1 1 1 3 Свободный член Х1 3 1 5 5 12 21 Переменные Х2 Х3 Х4 1 -2 1 1 -3 2 Свободный член Х1 6 1 1 4 3 24 Х2 1 Х5 -3 5 1 9 -3 Переменные Х3 Х4 Х5 -1/5 3/5 -2/5 1/5 1 2/5 -1/5 3/5 -9/5 4/5 3/5 36 Х6 1 Х6 1 Х6 1 Оценочное отношение 18/3 16 5 f Оценочное отношение 3 11/2 f 7 Оценочное отношение f 5/5 5/1 12/9 Оценочное отношение Метод искусственного базиса (М-метод) Используется, когда первое БР – недопустимое. В каждое уравнение, дающее отрицательную компоненту в БР, вводится своя новая неотрицательная искусственная переменная У1, У2, …, Ук, которая имеет тот же знак, что и свободный член в правой части уравнения. В первой таблице включаются в число основных (базисных) все искусственные переменные и те обычные добавочные переменные, которые определяют неотрицательные компоненты БР. Составляется новая линейная функция Т = F – М(У1 + У2 + … + Ук), где М – произвольно большое число, и ищется ее максимум. (Слайд 6) Справедлива теорема (без доказательства): 1. Если в оптимальном решении новой функции все искусственные переменные = 0, то соответствующие значения остальных переменных дают оптимальное решение исходной задачи (т.е. Тмах = Fмах, если У1=У2=…=Ук=0, т.е. минимум М-функции = 0) . 2. Если имеется оптимальное решение новой функции, в котором хотя бы одна из искусственных переменных отлична от 0, то система ограничений исходной задачи несовместна. 3. Если Тмах = f, то исходная задача также неразрешима, причем либо Fмах = f, либо условия задачи противоречивы. Из теоремы следует, что сначала надо найти минимум М-функции. Если он = 0, то далее можно отбросить эти переменные и решать исходную задачу, исходя из полученного БР. На практике находят не минимум М-функции, а максимум (-М)-функции. Пример: F=x1 + 2х2 Æ max Расширенная система имеет вид: х1 - х2 <= -1 х1 – х2 + х3 = -1 х1 - х2 >= -3 х1 - х2 - х4 = -3 х1 <= 3 х1 + х5 = 3 х1, х2 >= 0 х1, х2, х3, х4, х5, х6 >= 0 Х1= (0; 0; -1; 3; 3) – недопустимое БР, поэтому в первое уравнение введем искусственную переменную У1 с тем же знаком, что и свободный член. х1 – х2 + х3 – у1= -1 - х1 + х2 - х3 + у1= 1 х1 - х2 - х4 = -3 - х1 + х2 + х4 = 3 х1 + х5 = 3 х1 + х5 = 3 В первой симплексной таблице последняя строка – это (-М)-функция, т.е. (-М)У1. Заполняется умножением строки У1 на коэффициент (-М). 37 Свободный Базис член У1 1 Х4 3 Х5 3 F -Мф -М Х1 -1 -1 1 -1 М Заменяем У1 на Х2. Свободный Базис член Х1 Х2 1 -1 Х4 2 Х5 3 1 F 2 -3 -Мф Х2 1 1 -2 -М Переменные Х3 Х4 -1 1 М Переменные Х2 Х3 Х4 1 -1 1 1 -2 Х5 1 Х5 1 У1 1 -М Оценочное отношение 1 3 f Оценочное отношение Последняя строка показывает, что критерий оптимальности выполнен: мах (М) = 0, значит мин М = 0. далее эту строку можно не рассматривать. Получено ДБР (0; 1; 0; 2; 3). Начиная с которого решаем исходную задачу в соответствии с обычным алгоритмом. 38 Теория двойственности в линейном программировании Каждой задаче ЛП соответствует другая задача, называемая двойственной или сопряженной по отношению к исходной. Теория двойственности оказалась полезной для проведения исследования ЗЛП. Экономическая интерпретация двойственной задачи Определить, сколько надо выпускать продукции первого и второго вида, чтобы общая прибыль была максимальна. Прибыль от выпуска единицы П1 – 7 рублей, П2 – 5 рублей. Имеется 4 вида ресурсов, которые идут на изготовление этой продукции (запасы ресурсов – 19, 13, 15 и 18 единиц соответственно). Математическая формулировка задачи об использовании ресурсов: F x 7 x1  5x2 o max (1) при ограничениях ­2 x1  3 x 2 d 19, °2 x  x d 13, ° 1 2 ® x  3 x 2 d 15, ° 1 °¯3 x1  0 x 2 d 18. (2), x1 t 0, x2 t 0 (3). Предположим, что некоторая организация желает приобрести сырье, которым располагает предприятие. По какой цене эта организация стала бы покупать указанное сырье, обозначим, соответственно, через y1 , y 2 , y3 , y 4 , цену единицы сырья вида S1 , S 2 , S 3 , S 4 . Выручка от продажи всего сырья, расходуемого на единицу продукции вида П1 по ценам y i , составит 2 y1  2 y2  0 y3  3 y4 . Предприятию выгодно продавать сырье, если ­2 y1  2 y 2  0 y3  3 y 4 t 7, ® ¯3 y1  1y 2  3 y3  0 y 4 t 5. С другой стороны общая стоимость всех запасов сырья, приобретаемого составит T y 19 y1  13 y2  15 y3  18 y 4 (4). Ясно, что покупающая организация стремится приобрести сырье по возможности дешевле, то есть минимизирует форму (4). Таким образом T y 19 y1  13 y 2  15 y3  18 y 4 o min (4) при ограничениях ­2 y1  2 y 2  0 y3  3 y 4 t 7, ® ¯3 y1  1y 2  3 y3  0 y 4 t 5. (5), y1 , y 2 , y3 , y 4 t 0 (6). 39 Цены Y1, Y2, …, Ym в экономической литературе получили названия: учетные, неявные, теневые. Смысл в том, что это условные, «ненастоящие» цены. Их часто называют оценками ресурсов. Две задачи линейного программирования (1) - (3), (4) - (6), связанные подобного рода особенностями называются взаимно двойственными или сопряженными. Прямая и двойственная задачи Исходная задача Двойственная задача при ограничениях при ограничениях Составить такой план выпуска Найти такой набор цен (оценок) продукции ресурсов У = (У1, У2, …, Уm), при котором Х = (Х1, Х2, …, Хn), при котором общие затраты на ресурсы будут прибыль от реализации продукции минимальные при условии, что будет максимальной при условии, затраты на ресурсы при что потребление ресурсов по производстве каждого вида каждому виду продукции не продукции будут не менее прибыли превзойдет имеющиеся запасы от реализации этой продукции Общие правила составления двойственных задач: 1) В одной задаче ищут максимум ЛФ, в другой – минимум. 2) Свободные члены ограничений одной из задач являются коэффициентами при соответствующих переменных в целевой функции другой задачи. При этом максимум меняется на минимум и наоборот. 3) Каждая из задач задана в стандартной форме, причем в задаче максимизации все неравенства вида «<=», а в задаче минимизации все неравенства вида «>=». 4) Матрицы коэффициентов при переменных в системах ограничений обеих задач являются транспонированными друг другу. 5) Число неравенств в системе ограничений одной задачи совпадает с числом переменных в другой задаче. 6) Условия неотрицательности переменных имеются в обеих задачах 40 Первая (основная) теорема двойственности Теорема: Если одна из сопряженных задач имеет оптимальное решение X * , то и вторая имеет оптимальное решение Y * , при этом Fmax = Zmin или F(X*) = Z(Y*). Если линейная функция одной из задач не ограничена, то условия другой задачи противоречивы. Пример применения 1-ой (основной) теоремы двойственности Задача. Дана задача (рассматривали в лекции по симплекс-методу): F = 2x1 + 3х2 Æ max при ограничениях: х1 + 3х2 <= 18 2х1 + х2 <= 16 х2 <= 5 3x1 <= 21 х1, х2 >= 0 и двойственная к ней: Z =18y1 + 16y2 +5y3 + 21y4 Æ min при ограничениях: y1 + 2y2 + 3y4 >= 2 3y1 + y2 + y3 >= 3 y1, y2, y3, y4 >= 0 Прямая задача была решена в лекции о симплекс-методе и был получен ответ F max = 24. если решить симплекс-методом двойственную задачу, то будет получен ответ, что Z min = 24. Т.е. заключение первой части теоремы двойственности верно. Экономический смысл 1-ой (основной) теоремы двойственности. План производства Х* = (х1*, х2*, …,хn*) и набор цен (оценок) ресурсов Y* = (y1*, y2*, …, ym*) оказываются оптимальными тогда и только тогда, когда прибыль (выручка) от продукции, найденная по известным заранее «ценам» с1, с2, .., сn, равна затратам на ресурсы по «внутренним» (определенным только из решения задачи) ценам y1, y2, …, ym. Так в рассмотренной выше задаче оптимумы F max и Z min = 24, для всех остальных планов F(X) <= 24, а Z(Y) >= 24. Можно интерпретировать экономический смысл 1-ой (основной) теоремы двойственности и так: предприятию безразлично, производить ли продукцию на основе оптимального плана Х* = (х1*, х2*, …, хn*) и получить максимальную прибыль (выручку) F max либо продавать ресурсы по оптимальным «внутренним» ценам Y* = (y1*, y2*, …, ym*) и возместить от продажи равные ей минимальные затраты на ресурсы Z min. 41 Вторая теорема двойственности Теорема: Для того чтобы два допустимых решения X * x1* , x2* ,, xn* и Y* y1* , y 2* ,, y m* пары двойственных задач были их оптимальными решениями необходимо и достаточно, чтобы они удовлетворяли системе уравнений (1) Замечание: Теорема верна для симметричной двойственной пары, для задач в канонической и общей форме соотношения (1) верны только для ограничений в виде неравенств и для неотрицательных переменных. В некоторой литературе под второй теоремой двойственности понимается другая теорема, следствием которой является предыдущая. Теорема: Компоненты оптимального решения двойственной задачи равны абсолютным значениям коэффициентов при соответствующих переменных линейной функции исходной задачи, выраженной через неосновные переменные ее оптимального решения. Соответствие между первоначальными переменными одной из двойственных задач и дополнительными переменными другой задачи: Переменные исходной задачи Первоначальные Х1 Х2 Ym+1 Ym+2 … … Дополнительные Хj … Xn Ym+j … Ym+n Xn+1 Xn+2 … Xn+I … Xn+m Y1 Дополнительные Y2 … Yi … Первоначальные Переменные двойственной задачи Пример. При решении прямой задачи F = 2x1 + 3х2 Æ max при ограничениях: х1 + 3х2 <= 18 2х1 + х2 <= 16 х2 <= 5 3x1 <= 21 х1, х2 >= 0 (Слайд 6) 42 Ym симплекс-методом получили на последнем шаге: F= 24 – 4/5х3 – 3/5х4 при оптимальном БР Х* =(6; 4; 0; 0; 1; 3). Базис Х1 Х5 Х2 Х6 F Свободный член Х1 6 1 1 4 3 24 Х2 1 Переменные Х3 Х4 Х5 -1/5 3/5 -2/5 1/5 1 2/5 -1/5 3/5 -9/5 4/5 3/5 Х6 1 Оценочное отношение Если решить симплекс-методом двойственную задачу: Z =18y1 + 16y2 +5y3 + 21y4 Æ min при ограничениях: y1 + 2y2 + 3y4 >= 2 3y1 + y2 + y3 >= 3 y1, y2, y3, y4 >= 0 то получим на последнем шаге: Z = 24 + y3 + 3y4 + 6y5 + 4y6 при оптимальном БР Y* =(4/5; 3/5; 0; 0; 0; 0). Базис Y1 Y2 Z Свободный член Y1 4/5 1 3/5 24 Y2 1 Переменные Y3 Y4 Y5 2/5 -3/5 1/5 -1/5 9/5 -3/5 1 3 6 Y6 -2/5 1/5 4 Оценочное отношение Замечание. Если в одной из взаимно двойственных задач нарушается единственность оптимального решения, то оптимальное решение другой двойственной задачи вырожденное. С помощью теорем двойственности можно, решив симплекс-методом исходную задачу, найти оптимум и оптимальное решение ДЗ. Метод, при котором сначала решают симплекс-методом ДЗ, а потом оптимум и оптимальное решение исходной задачи находятся с помощью теорем двойственности, называется двойственным симплекс-методом. Этот метод применяется, когда первое БР исходной задачи недопустимое или, например, число ее ограничений m больше числа переменных n. Пример двойственной задачи Экономическую интерпретацию двойственных задач и двойственных оценок рассмотрим на примере. 43 Пример. Для производства трех видов изделий А, В и С используется три различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 180, 210 и 244 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице. Нормы затрат сырья (кг) на Вид сырья единицу продукции А В С I 4 2 1 II 3 1 3 III 1 2 5 Цена единицы продукции (руб.) 10 14 12 Определить план выпуска продукции, при котором обеспечивается ее максимальная стоимость, и оценить каждый из видов сырья, используемых для производства продукции. Оценки, приписываемые каждому из видов сырья, должны быть такими, чтобы оценка всего используемого сырья была минимальной, а суммарная оценка сырья, используемого на производство единицы продукции каждого вида,– не меньше цены единицы продукции данного вида. Решение. Предположим, что производится x1 изделий А, х2 изделий В и х3 изделий С. Для определения оптимального плана производства нужно решить задачу, состоящую в максимизации целевой функции (1) при следующих условиях (2) (3) 44 Припишем каждому из видов сырья, используемых для производства продукции, двойственную оценку, соответственно равную у1, у2 и у3. Тогда общая оценка сырья, используемого на производство продукции, составит (4) Согласно условию, двойственные оценки должны быть такими, чтобы общая оценка сырья, используемого на производство единицы продукции каждого вида, была не меньше цены единицы продукции данного вида, т. е. у1, у2 и у3 должны удовлетворять следующей системе неравенств: (5) (6) Задачи (1) – (3) и (4) – (6) образуют симметричную пару двойственных задач. Решение прямой задачи дает оптимальный план производства изделий A, В и С, а решение двойственной – оптимальную систему оценок сырья, используемого для производства этих изделий. Чтобы найти решение этих задач, следует сначала отыскать решение какой–либо одной из них. Так как система ограничений задачи (1) – (3) содержит лишь неравенства вида “ ”, то лучше сначала найти решение этой задачи. Ее решение приведено в таблице: Базис Св.член Х1 Х2 Х3 Х4 Х5 Х6 Х2 82 19/8 1 5/8 –1/8 Х5 80 23/8 1/8 1 –5/8 Х3 16 –3/4 1 –1/4 1/4 1340 57/4 23/4 5/4 Из этой таблицы видно, что оптимальным планом производства изделий является такой, при котором изготовляется 82 изделия В и 16 изделий С. При данном плане производства остается неиспользованным 80 кг сырья II вида, а общая стоимость изделий равна 1340 руб. Из таблицы также видно, что оптимальным решением двойственной задачи является Переменные у1* и у3* обозначают условные двойственные оценки единицы сырья, соответственно I и III видов. Эти оценки отличны от нуля, а 45 сырье 1 и III видов полностью используется при оптимальном плане производства продукции. Двойственная оценка единицы сырья II вида равна нулю. Этот вид сырья не полностью используется при оптимальном плане производства продукции. Таким образом, положительную двойственную оценку имеют лишь те виды сырья, которые полностью используются при оптимальном плане производства изделий. Поэтому двойственные оценки определяют дефицитность используемого предприятием сырья. Более того, величина данной двойственной оценки показывает, на сколько возрастает максимальное значение целевой функции прямой задачи при увеличении количества сырья соответствующего вида на 1 кг. Так, увеличение количества сырья I вида на 1 кг приведет к тому, что появится возможность найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 5,75 руб. и станет равной 1340+5,75=1345,75 руб. При этом числа, стоящие в столбце вектора Х4 таблицы, показывают, что указанное увеличение общей стоимости изготовляемой продукции может быть достигнуто за счет увеличения выпуска изделий В на 5/8 ед. и сокращения выпуска изделий С на 1/4 ед. Вследствие этого использование сырья II вида уменьшится на 1/8 кг. Точно так же увеличение на 1 кг сырья III вида позволит найти новый оптимальный план производства изделий, при котором общая стоимость изготовляемой продукции возрастет на 1,25 руб. и составит 1340+1,25=1341,25 руб. Это будет достигнуто в результате увеличения выпуска изделий С на 1/4 ед. и уменьшения изготовления изделий В на 1/8 ед., причем объем используемого сырья II вида возрастет на 5/8 кг. Продолжим рассмотрение оптимальных двойственных оценок. Вычисляя минимальное значение целевой функции двойственной задачи видим, что оно совпадает с максимальным значением целевой функции исходной задачи. При подстановке оптимальных двойственных оценок в систему ограничений двойственной задачи получаем Первое ограничение двойственной задачи выполняется как строгое неравенство. Это означает, что двойственная оценка сырья, используемого на производство одного изделия вида А, выше цены этого изделия и, следовательно, выпускать изделия вида А невыгодно. Его производство и не предусмотрено оптимальным планом прямой задачи. Второе и третье ограничения двойственной задачи выполняются как строгие равенства. Это означает, что двойственные оценки сырья, используемого для производства единицы соответственно изделий В и С, равны в точности их ценам. Поэтому 46 выпускать эти два вида продукции по двойственным оценкам экономически целесообразно. Их производство и предусмотрено оптимальным планом прямой задачи. Таким образом, двойственные оценки тесным образом связаны с оптимальным планом прямой задачи. Всякое изменение исходных данных прямой задачи может оказать влияние как на ее оптимальный план, так и на систему оптимальных двойственных оценок. Поэтому, чтобы проводить экономический анализ с использованием двойственных оценок, нужно знать их интервал устойчивости. К рассмотрению этого мы сейчас и перейдем. Анализ чувствительности в линейном программировании Решение практической задачи нельзя считать законченным, если найдено оптимальное решение. Дело в том, что некоторые параметры задачи ЛП (финансы, запасы сырья, производственные мощности) можно регулировать, что, в свою очередь, может изменить найденное оптимальное решение. Эта информация получается в результате выполнения анализа чувствительности. Анализ чувствительности позволяет оценить влияние этих параметров на оптимальное решение. Если обнаруживается, что оптимальное решение можно значительно улучшить за счет небольших изменений заданных параметров, то целесообразно реализовать эти изменения. Кроме того, во многих случаях оценки параметров получаются путем статистической обработки ретроспективных данных (например, ожидаемый сбыт, прогнозы цен и затрат). Оценки, как правило, не могут быть точными. Если удается определить, какие параметры в наибольшей степени влияют на значение целевой функции, то целесообразно увеличить точность оценок именно этих параметров, что позволяет повысить надежность рассматриваемой модели и получаемого решения. Таким образом, после математического решения задачи линейного программирования, расчета ее оптимального плана и оптимума, необходимо проанализировать полученные результаты. Общая задача такого анализа - определить устойчивость полученного решения к тому или иному изменению ситуации, к изменению условий задачи, а также оценить чувствительность решения к изменению конкретных численных значений тех или иных параметров ситуации. Обычно результаты анализа охватывают несколько разделов. Важность тех или иных разделов зависит от конкретной экономической ситуации, описываемой в задаче. Во-первых, необходимо выявить, какие ограничения выполняются как равенства (связанные, или активные ограничения), какие - как строгие неравенства (несвязанные, неактивные ограничения). Это важная информация. Для задачи производственного планирования ограничения соответствуют ресурсам. Равенство левой и правой частей ограничения, его активность 47 означает полное использование данного ресурса. Строгое неравенство неполное использование ресурса. Говорили об этом выше. В нашем примере связанными являются ограничения по I и III видам ресурсов. Эти два ресурса используются полностью. Остальные избыточны. Знание того, какие ресурсы как используются, определяет узкие места в обеспечении производственного процесса и возможность маневра. Можно, например, продать излишки ресурсов для получения дополнительного дохода. Можно, наоборот, докупить дополнительные объемы тех ресурсов, которые используются полностью. Эти новые объемы вместе с оставшимися излишками других ресурсов позволят выпустить дополнительную продукцию и получить дополнительный доход. Для того, чтобы оценить выгодность такого решения, следует оценить величину такого дополнительного дохода, то есть величину предельной эффективности ресурсов. Величина предельной эффективности называется также теневой ценой (или двойственной оценкой) ресурса. Отметим, что теневая цена является внутренней характеристикой ресурса в сложившейся производственной ситуации и не отражает ценность данного ресурса во внешней среде, его рыночную цену. Теневая цена определяет оценку чувствительности оптимума к изменению правых частей ограничений. Сопоставление теневой и рыночной цены может служить основанием для принятия решения о закупке дополнительных объемов данного ресурса (если теневая цена больше рыночной) или о продаже части ресурса (если теневая цена меньше рыночной). В нашем примере есть смысл докупать сырье I вида, если рыночная цена на него ниже 5,25 руб. за единицу, а сырье III вида, если рыночная цена на него ниже 1, 25 руб. за единицу. Сырье II вида докупать не имеет смысл, т.к. по нему и так остается запас 80 единиц. В решениях такого рода важным является вопрос о границах действия теневой цены, а тем самым и о разумных объемах купли-продажи ресурса. Критические границы и допустимые изменения ресурса Рассмотрим пример: Для производства двух видов изделий А и В используется четыре различных вида сырья. Каждый из видов сырья может быть использован в количестве, соответственно не большем 18, 16, 5 и 21 кг. Нормы затрат каждого из видов сырья на единицу продукции данного вида и цена единицы продукции каждого вида приведены в таблице. Нормы затрат сырья (кг) на единицу продукции Вид сырья А В I II III 1 2 48 3 1 1 IV 3 Цена единицы 2 3 продукции (руб.) Определить план выпуска продукции, при котором обеспечивается ее максимальная стоимость, и провести анализ чувствительности. ЭММ (решали задачу симплекс-методом): F = 2x1 + 3х2 Æ max при ограничениях: х1 + 3х2 <= 18 2х1 + х2 <= 16 х2 <= 5 3x1 <= 21 х1, х2 >= 0 симплекс-методом получили на последнем шаге: F= 24 – 4/5х3 – 3/5х4 при оптимальном БР Х* =(6; 4; 0; 0; 1; 3). Базис Х1 Х5 Х2 Х6 F Свободный член Х1 6 1 1 4 3 24 Х2 1 Переменные Х3 Х4 Х5 -1/5 3/5 -2/5 1/5 1 2/5 -1/5 3/5 -9/5 4/5 3/5 Х6 1 Оценочное отношение В этом примере связанными являются ограничения по I и II видам сырья. Эти два вида сырья используются полностью. Остальные - избыточны (остаток по III виду сырья – 1 кг, по IV – 3 кг. Есть смысл докупать только сырье I вида, если рыночная цена на него ниже 0,8 руб. за единицу (т.к. прирост целевой функции будет равен 0,8 руб.), и сырье II вида, если рыночная цена на него ниже 0,6 руб. за единицу (т.к. прирост целевой функции будет равен 0,6 руб.). Важно определить до скольких единиц имеет смысл закупать первые два вида сырья. Предположим, что запасы I вида сырья изменились на Δb1. Тогда затраты на ресурсы в соответствии с целевой функцией ДЗ будут равны: Z =(18+ Δb1) y1 + 16y2 +5y3 + 21y4. Базис Y1 Y2 Z Свободный член Y1 4/5 1 3/5 24 Y2 1 Переменные Y3 Y4 Y5 2/5 -3/5 1/5 -1/5 9/5 -3/5 1 3 6 49 Y6 -2/5 1/5 4 Оценочное отношение Заменяем переменные у1 и у2 их выражениями через неосновные переменные оптимального БР: у1= 4/5 – 2/5 у3 + 3/5 у4 – 1/5 у5 + 2/5 у6 у2= 3/5 + 1/5 у3 – 9/5 у4 + 3/5 у5 – 1/5 у6, подставляем в целевую функцию: Z =(18+ Δb1) (4/5 – 2/5 у3 + 3/5 у4 – 1/5 у5 + 2/5 у6) + 16 (3/5 + 1/5 у3 – 9/5 у4 + 3/5 у5 – 1/5 у6) +5y3 + 21y4 = = (24 + 4/5 Δb1) + (1 – 2/5 Δb1 ) у3 + (3 + 3/5 Δb1) у4 + (6 – 1/5 Δb1) у5 + (4 + 2/5 Δb1) у6. Для того, чтобы оценки ресурсов оставались неизменными и при изменении запасов сырья, т.е. сохранилось оптимальное решение ДЗ Y* = (4/5; 3/5; 0; 0; 0; 0), достаточно, чтобы коэффициенты при неосновных переменных в последнем выражении оставались неотрицательными, т.е. 1 – 2/5 Δb1 >= 0 Δb1 <= 2,5 3 + 3/5 Δb1 >= 0 Δb1 >= -5 и 6 – 1/5 Δb1 >= 0 Δb1 <= 30 4 + 2/5 Δb1 >= 0 Δb1 >= -10 Откуда: –5 <= Δb1 <= 2,5 18 -5 <= b1 + Δb1 <= 18 + 2,5 или 13 <= b1 + Δb1 <= 20,5 , т.е . при неизменности теневых цен (или оценок ресурсов) запас I вида сырья может изменяться в пределах от 13 до 20,5 единиц. Аналогично можно высчитать пределы изменения по запасам II вида сырья, который может меняться от 11 до 17, 67 единиц. Можно определить графическим способом. Посмотрим на график, который строили при решении задачи графическим способом. С 50 F=24 F=26 I Е F=20 F Если в нашем примере постепенно увеличивать запас I вида сырья, то оптимальный план будет смещаться, оставаясь на пересечении границ по I и II видам сырья. Так будет продолжаться до тех пор, пока он не дойдет до точки Е – точки пересечения границ по II и III видам сырья. В точке Е пересекутся три границы: по I, II и III видам сырья. Этот момент является критическим. Дальнейшее увеличение запаса I вида сырья приведет к избыточности данного ресурса. Он станет несвязанным, его теневая цена будет равна 0. Связанным станет III вид сырья. Таким образом, в наборе связанных ресурсов, после прохождения критического положения границы, один ресурс будет заменен другим, два этих ресурса изменят свой статус. Расчет критической границы по I виду сырья можно провести следующим образом. Сначала определим координаты точки пересечения границ по II и III видам сырья. Для этого следует решить соответствующую систему уравнений 2х1 + х2 = 16 х2 = 5 В результате получим: x1 = 5,5 x2 = 5. Подставим эти значения в левую часть неравенства, определяющего ограничение по I виду сырья: х1 + 3х2 = 5,5 + 3u5 = 20,5. Полученная величина 20,5 и является верхней критической границей по I ресурсу. Таким образом, исходный объем I вида сырья, равный 18 кг, можно 51 увеличить на 2,5 кг без изменения статуса ограничений и без изменения теневой цены ресурса. Величина 2,5 кг в этом примере является допустимым увеличением этого вида сырья. Нижняя критическая граница и, соответственно, допустимое уменьшение вычисляются аналогично. В нашем примере при уменьшении объема I вида сырья оптимальный план будет смещаться налево-вниз. Критическим будет такая величина объема ресурса, при которой линия I вида сырья пройдет через точку пересечения F границ по II и IV видам сырья. При дальнейшем уменьшении доступного объема I вида сырья произойдет изменение статуса некоторых ограничений. Именно, связанными ресурсами станут I и IV виды сырья, а II вид сырья станет несвязанным, и его теневая цена будет равна 0. Для вычисления координат точки F решим соответствующую систему уравнений: 2х1 + х2 = 16 3x1 = 21 В результате получим x1 = 7 x2 = 2. Подставим эти значения в левую часть неравенства, определяющего ограничение по I виду сырья: х1 + 3х2 = 7 + 3u2 = 13. Величина 13 есть нижняя критическая граница ресурса. Допустимое уменьшение данного ресурса определяется разностью 18 – 13 = 5. Таким образом, при изменении доступного объема I вида сырья теневые цены и статус ресурсов сохраняются, если его объем остается между вычисленными критическими границами. При переходе через одну из границ, происходит изменение статуса и теневых цен ресурсов. Аналогично могут быть определены критические границы по остальным ограничениям. Для избыточных ресурсов (их теневая цена равна 0) верхней границы не существует, такой ресурс при любом увеличении объема остается избыточным. Напомним, что координатные оси являются граничными прямыми ограничений x1 t 0, x2 t 0. Таким образом, в некоторых ситуациях прохождение через критическую границу может привести к тому, что производство одного из продуктов прекратится (оптимальное значение одной из переменных x1, x2 станет равным 0), или возобновится (оптимальное значение одной из переменных x1, x2 станет больше 0). Критические границы ресурсов соответствуют границам устойчивости статуса ограничений при изменении их правых частей. Если запасы первых двух видов сырья будут меняться одновременно, то исследование теневых цен (оценок) усложняется. 52 Ценовой анализ Изменение оптимального плана может быть связано с изменением цен на продукцию (коэффициентов при переменных в целевой функции). В рассматриваемой модели цены считаются неизменными. При небольших изменениях цен оптимальный план обычно сохраняет свою оптимальность. При существенных изменениях цен оптимальным становится другой план. Важно разобраться в этом, рассчитать критические ценовые границы. Такое изучение воздействия ценовых изменений на оптимальный план и оптимум относят к ценовому постоптимизационному анализу. Обратимся к нашему примеру. Цена изделия А составляет 3 руб. за ед. Предположим, что отпускная цена изменилась, и теперь изделие А продается по другой цене. Следует ожидать, что при этом изменится выручка от продаж. Однако изменится ли оптимальный план? Предположим, что цена Изделия А изменились на Δс1. Тогда прибыль в соответствии с целевой функцией будет равна: Переменные Свободный Оценочное Базис член отношение Х1 Х2 Х3 Х4 Х5 Х6 Х1 6 1 -1/5 3/5 Х5 1 -2/5 1/5 1 Х2 4 1 2/5 -1/5 Х6 3 3/5 -9/5 1 F 24 4/5 3/5 F =(2+ Δc1) х1 + 3х2. Заменяем переменные х1 и х2 их выражениями через неосновные переменные оптимального БР: х1= 6 + 1/5 х3 - 3/5 х4 х2= 4 2/5 х3 + 1/5 х4, подставляем в целевую функцию F и после преобразования получаем: F =(24 + 6 Δc1) – (4/5 – 1/5 Δc1) х3 – (3/5 + 3/5 Δc1) х4. Для того, чтобы сохранилось оптимальное решение Х* =(6; 4; 0; 0; 1; 3), достаточно, чтобы коэффициенты при неосновных переменных в последнем выражении оставались неотрицательными, т.е. 4/5 – 1/5 Δc1>= 0 Δс1 <= 4 и 3/5 + 3/5 Δc1>= 0 Δс1 >= -1 Откуда: –1 <= Δс1 <= 4 2 - 1 <= с1 + Δс1 <= 2 + 4 или 1 <= с1 + Δс1 <= 6 , т.е. оптимальное решение будет неизменно при изменении цен на Изделие А в пределах от 1 до 6 рублей. Можно определить графическим способом. 53 С D Небольшое изменение цены приведет к незначительному повороту градиента (вместе со всей системой перпендикулярных ему линий уровня целевой функции). В результате оптимальный план останется в прежней точке. При более значительном изменении цены он перейдет в другую вершину области допустимых планов. Рассмотрим этот вопрос подробнее. Предположим, что цена Изделия А увеличивается. Это соответствует повороту наклона прямой целевой функции по часовой стрелке. При небольшом повороте оптимальный план остается в первоначальной точке C. При достаточно большом повороте оптимальный план перейдет в точку D, находящуюся на пересечении границ по II и IV видам сырья. Критическая величина цены, при которой происходит переход оптимального плана из одной точки в другую, соответствует положению, когда линия уровня целевой функции параллельна прямой, которой принадлежит отрезок СD. Условием параллельности прямых является пропорциональность коэффициентов при переменных в двух уравнениях: линии уровня целевой функции и границы по II виду сырья. Составим пропорцию с неизвестной ценой c1 изделия А: F = 2x1 + 3х2 2х1 + х2 <= 16 C1 2 3 1 Отсюда получаем c1= 6. Таким образом, при увеличении цены Изделия А с первоначальных 2 до 6 руб. за ед. (и при сохранении цены Изделия В) оптимальный план остается неизменным, по-прежнему следует производить 6 ед. Изделия А и 4 ед. Изделия В. Если же цена поднимется выше 6 руб., то оптимальным планом станет точка D, находящаяся на пересечении границ по II и IV видам сырья. Ее координаты можно определить решением системы соответствующих уравнений. При цене Изделия А, в точности равной 6 руб., оптимальным является как первоначальный план С, так и новый план D, а также и все точки, лежащие 54 на отрезке СD. В этом случае задача имеет бесконечно много оптимальных планов. Разумеется, все эти разные планы производства обеспечивают в точности одну и ту же величину выручки от продаж. Верхняя критическая граница цены Изделия А равна 6. Отсюда следует, что допустимое увеличение первоначальной цены равно 4. Аналогичным образом рассчитывается нижняя граница цены Изделия А, и верхняя и нижняя критические границы цен Изделия В. Критические границы цен соответствуют границам устойчивости оптимального плана при изменении коэффициентов целевой функции. 55 Решение задачи ЛП средствами EXCEL Описание ситуации Требуется определить план выпуска 4 видов продукции. На изготовление расходуются трудовые ресурсы, сырье и финансы. Границы выпуска каждого вида продукции, а так же наличие и нормы расхода ресурсов, прибыль на единицу продукции приведены в таблице: Ресурсы Труд Сырье Финансы нижн. гр. верхн. гр. Продукт 1 2 8 10р. 1 6 Продукт 2 1 5 8р. 1 - Продукт 3 2 6 10р. 2 4 Продукт 4 2 5 15р. 3 5 Прибыль 800р. 700р. 1 200р. 1 500р. Наличие 36 85 180р. Необходимо создать производственный план, обеспечивающий наибольшую прибыль. Выполнить анализ полученных результатов и ответить на следующие вопросы: 1. Выгодно ли включать в производственный план новые продукты со следующими характеристиками: Ресурсы Труд Сырье Финансы Продукт 1 2 4 8р. Продукт 2 1 12 5р. Прибыль 1000р. 1200р. 2. Вырастет ли прибыль, если привлечь: x дополнительные финансовые средства в размере 20 рублей? x дополнительное сырье по цене 100 рублей? 3. На сколько увеличится прибыль, если привлечь дополнительно сырья: x 5 единиц? x 10 единиц? 4. Изменится ли выпуск: x Продукта 1, если прибыль на него вырастет до 1100 рублей? x Продукта 4, если прибыль на него снизится до 600 рублей? Обозначив количество выпускаемой продукции через x1, x2, x3, x4, а целевую функцию (валовую прибыль) – через F, построим математическую модель задачи: F = 800x1 + 700x2 + 1200x3 + 1500x4 max, Три неравенства – ограничения на ресурсы: 56 2 x1 + 1 x2 + 2 x3 + 2 x4 ≤ 36, 8 x1 + 5 x2 + 6 x3 + 5 x4 ≤ 85, 10 x1 + 8 x2 + 10 x3 + 15 x4 ≤ 180; четыре неравенства – ограничения на выпуск: 1 ≤ x1 ≤ 6, 1 ≤ x2, 2 ≤ x3 ≤ 4, 2 ≤ x4 ≤ 5. Создание в Excel модели для решения задачи Для решения задачи средствами Excel удобно подготовить на листе Excel модель следующего вида: Для создания модели используются формулы расчета общей прибыли и определения количества ресурсов, необходимых на выпуск продукции. Эти формулы удобно задавать при помощи функции СУММПРОИЗВ. 57 Для задания ограничений на выпуск удобно сделать ссылки на ячейки, в которых будет выводиться количество выпускаемой продукции. Решение задачи в Excel Для решения задачи используется команда Поиск решения группы Анализ вкладки Данные. Если такой команды в меню нет, то необходимо выполнить нажать Кнопку «Office» , в нижней части появившегося меню нажать кнопку Параметры Excel, в появившемся окне перейти в Надстройки, нажать кнопку Перейти к Настройкам Excel и установить Поиск решения. После выполнения команды появится окно: Задать ячейку с целевой функцией, изменяемые ячейки, ограничения. 58 Добавление ограничений: Задать параметры поиска решения: Параметр "Максимальное время" служит для назначения времени (в секундах), выделяемого на решение задачи. В поле можно ввести время, не превышающее 32 767 секунд (более 9 часов). Параметр "Предельное число итераций" служит для управления временем решения задачи путем ограничения числа промежуточных вычислений. В поле можно ввести количество итераций, не превышающее 32 767. Параметр "Относительная погрешность" служит для задания точности, с которой определяется соответствие ячейки целевому значению или приближение к указанным границам. Поле должно содержать число из интервала от 0 до 1. Чем меньше количество десятичных знаков во введенном числе, тем ниже точность. Высокая точность увеличит время, которое требуется для того, чтобы сошелся процесс оптимизации. 59 Параметр "Допустимое отклонение" служит для задания допуска на отклонение от оптимального решения в целочисленных задачах. При указании большего допуска поиск решения заканчивается быстрее. Параметр "Сходимость" применяется только при решении нелинейных задач. Установка флажка "Линейная модель" обеспечивает ускорение поиска решения линейной задачи за счет применение симплекс-метода. При этом в отчете по устойчивости, который можно получить после решения задачи, будет выводиться более полная информация. Параметр "Неотрицательные значения" позволяет установить нулевую нижнюю границу для тех изменяемых ячеек, для которых она не была указана в ограничениях. Параметр "Автоматическое масштабирование" служит для включения автоматической нормализации входных и выходных значений, качественно различающихся по величине — например, максимизация прибыли в процентах по отношению к вложениям, исчисляемым в миллионах рублей. Параметр "Показывать результаты итераций" служит для приостановки поиска решения для просмотра результатов отдельных итераций. Параметр "Оценка" служит для указания метода экстраполяции — линейная или квадратичная — используемого для получения исходных оценок значений переменных в каждом одномерном поиске. Параметр "Производные" служит для указания метода численного дифференцирования — прямые или центральные производные — который используется для вычисления частных производных целевых и ограничивающих функций. Параметр "Метод" служит для выбора алгоритма оптимизации — метод Ньютона или сопряженных градиентов — для указания направление поиска. Для нахождения решения нажать кнопку «Выполнить» в окне Поиска решения. 60 В появившемся окне «Результаты поиска решения» отображается информация о том, найдено или нет решение, в этом окне можно выбрать тип отчета. Иногда сообщения о том, найдено или нет оптимальное решение свидетельствуют не о характере оптимального решения задачи, а о том, что при вводе условий задачи в Excel были допущены ошибки, не позволяющие Excel найти оптимальное решение, которое в действительности существует . В окне "Результаты поиска решения" представлены названия трех типов отчетов: "Результаты", "Устойчивость", "Пределы". Для выбора нужных отчетов необходимо выделить их названия. Отчет будет представлен на отдельном листе рабочей книги Excel. Описание отчетов: Результаты. Используется для создания отчета, состоящего из целевой ячейки и списка влияющих ячеек модели (ячеек с исходными данными), их исходных и конечных значений, а также формул ограничений и дополнительных сведений о наложенных ограничениях. Устойчивость. Используется для создания отчета, содержащего сведения о чувствительности решения к малым изменениям в формуле (поле Установить целевую ячейку, диалоговое окно Поиск решения) или в формулах ограничений. В случае нелинейных моделей отчет содержит данные для градиентов и множителей Лагранжа. В отчет по нелинейным моделям включаются ограниченные затраты, фиктивные цены, объективный коэффициент (с некоторым допуском), а также диапазоны ограничений справа. Пределы. Используется для создания отчета, состоящего из целевой ячейки и списка влияющих ячеек модели, их значений, а также нижних и верхних границ. Нижним пределом является наименьшее значение, которое может содержать влияющая ячейка, в то время как значения остальных влияющих ячеек фиксированы и удовлетворяют наложенным ограничениям. Соответственно, верхним пределом называется наибольшее значение (используется реже). Отчеты по устойчивости и по пределам нельзя получить, если на изменяемые переменные наложены ограничения целочисленности. Для 61 получения более полной информации в отчете по устойчивости нужно в окне задания параметров установить флажок "Линейная модель". Для получения же ответа (значений переменных, ЦФ и левых частей ограничений) прямо в экранной форме можно сразу нажать кнопку "OK". После этого в экранной форме появляется оптимальное решение задачи. Анализ оптимального решения на чувствительность в Excel Для проведения анализа на полученного решения чувствительность (т.е. для ответа на поставленные вопросы) необходимо после запуска в Excel задачи на решение в окне "Результаты поиска решения" выделить с помощью мыши два типа отчетов: "Результаты" и "Устойчивость". Отчет по результатам Отчет по результатам состоит из трех таблиц: x таблица 1 содержит информацию о ЦФ; x таблица 2 содержит информацию о значениях переменных, полученных в результате решения задачи; x таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий. 62 Если ресурс используется полностью (то есть ресурс дефицитный), то в графе "Статус" соответствующее ограничение указывается как "связанное"; при неполном использовании ресурса (то есть ресурс недефицитный) в этой графе указывается "не связан". В графе "Значение" приведены величины использованного ресурса. Для граничных условий (ограничения на выпуск) в графе "Разница" показана разность между значением переменной в найденном оптимальном решении и заданным для нее граничным условием. Таблица 3 отчета по результатам дает информацию для анализа возможного изменения запасов недефицитных ресурсов при сохранении полученного оптимального значения ЦФ. Если на ресурс наложено ограничение типа , то в графе "Разница" дается количество ресурса, которое не используется при реализации оптимального решения. Так, анализ первой строки показывает, что трудового ресурса используется 25,6 ч/час. Неизрасходованным остается 10,4 ч/час из общего фонда времени, отведенного на выпуск продукции. Из этого следует, что запас недефицитного ресурса Труд можно уменьшить на 10,4 ч/час и это никак не повлияет на оптимальное решение. 63 Анализ строки 8 показывает, что общее количество выпускаемой Продукта 1 составляет 1 т, что меньше предполагаемой емкости рынка на 5 т. То есть уменьшение спроса до 1 т никак не скажется на оптимальных объемах выпуска этой продукции. Отчет по устойчивости Отчет по устойчивости состоит из двух таблиц. Таблица 1 содержит информацию, относящуюся к переменным: x Результ. значение показывает результат решения задачи. x Нормированная стоимость показывает, на сколько изменится значение ЦФ в случае принудительного включения единицы этой продукции в оптимальное решение. Если нормированная стоимость какого-либо процесса положительна, то это значит, что стоимость потребленных ресурсов (в теневых ценах) больше возможной прибыли и значение соответствующей переменной в оптимальном решении равно 0. Если значения переменных > 0 в оптимальном решении (т.е. выпуск соответствующей продукции включен в оптимальный план), то нормированные стоимости у них равны 0. У нас в примере все 0, т.е. вся продукция включена в план выпуска. x Коэффициенты ЦФ отображают исходные данные. x Допустимое увеличение и уменьшение показывают предельные значения приращения целевых коэффициентов ∆Сj, при которых сохраняется первоначальное оптимальное решение. Например, допустимое увеличение цены на Продукт 1 равно 320 руб., а 64 допустимое уменьшение – практически не ограничено. Это означает, что если цена на Продукт 1 возрастет более чем на 320 руб., например станет равной 1130 руб., то оптимальное решение изменится. А если их цена будет снижаться вплоть до нуля, то оптимальное решение останется прежним. Примечание. При выходе за указанные в отчете по устойчивости пределы изменения цен оптимальное решение может меняться как по номенклатуре выпускаемой продукции, так и по объемам выпуска (без изменения номенклатуры). Таблица 2 содержит информацию, относящуюся к ограничениям. x Результ. значение показывает величина использованных ресурсов. x Теневая цена показывает ценность дополнительной единицы соответствующего ресурса. Теневая цена рассчитывается только для дефицитных ресурсов, для недефицитных равна 0. Она показывает, на сколько возрастет значение целевой функции при увеличении запаса соответствующего ресурса на 1. x Ограничение правая часть показывает исходные данные из правых частей ограничений. x Допустимое увеличение и уменьшение показывают предельные значения приращения ресурсов ∆Bi. В графе "Допустимое Уменьшение" показывается, на сколько можно уменьшить (устранить излишек) или увеличить (повысить минимально необходимое требование) ресурс, сохранив при этом оптимальное решение. Рассмотрим анализ дефицитных ресурсов, так как анализ недефицитных ресурсов был дан выше. Анализируя отчет по результатам, мы установили, что существуют причины (ограничения), не позволяющие выпускать большее, чем в оптимальном решении, количество продукции и получать более высокую прибыль. В рассматриваемой задаче таким ограничением является дефицитный ресурс “Сырье”. Поскольку знак ограничений этих запасов имеет вид <=, то возникает вопрос, на сколько максимально можно увеличить запас ресурса, чтобы обеспечить увеличение выпуска продукции. Ответ на этот вопрос показан в графе "Допустимое Увеличение". Емкость сушилки имеет смысл увеличить самое большее на 6,375 единиц. Это приведет к увеличению прибыли по сравнению с текущим оптимальным решением. Дальнейшее увеличение запасов сырья сверх указанных пределов не будет больше улучшать решение, т.к. уже другие ресурсы станут связывающими. Теперь ответим на поставленные вопросы: 1) Выгодно ли включать в производственный план новые продукты со следующими характеристиками: 65 Ресурсы Труд Сырье Финансы Продукт 1 2 4 8р. Продукт 2 1 12 5р. Прибыль 1000р. 1200р. 2 * 0 + 4 * 140 + 8 * 0 = 560 < 1000 выгодно 1 * 0 + 12 * 140 + 5 * 0 = 1680 > 1200 не выгодно 2) Вырастет ли прибыль, если привлечь: x дополнительные финансовые средства в размере 20 рублей? Нет, т.к. финансовые средства и так не полностью используются. x дополнительное сырье по цене 100 рублей? Да, т.к. дополнительно привлечь единицу сырья. То прибыль увеличится на 140 руб. 3) На сколько увеличится прибыль, если привлечь дополнительно сырья: x 5 единиц? (5 * 140 – 5 * 100) x 10 единиц? (6,375 * 140 – 10 * 100 = 892,5 - 1000) 4) Изменится ли выпуск: x Продукта 1, если прибыль на него вырастет до 1100 рублей? (нет, не изменится, т.к. предельное увеличение 800 + 320) x Продукта 4, если прибыль на него снизится до 600 рублей? (да, изменится, т.к. допустимое уменьшение 1500 – 800 = 700) 66 Параметрическое линейное программирование Параметрическое программирование представляет собой один из разделов математического программирования, изучающий задачи, в которых целевая функция или ограничения зависят от одного или нескольких параметров. Необходимость рассмотрения подобных задач обусловлена различными причинами. Одной из основных является та, что исходные данные для численного решения любой реальной задачи оптимизации в большинстве случаев определяются приближенно или могут изменяться под влиянием каких-то факторов, что может существенно сказаться на оптимальности выбираемой программы (плана) действий. Соответственно, разумно указывать не конкретные данные, а диапазон возможного изменения данных, чтобы в результате решения иметь наилучшие планы для любого варианта исходных данных. С математической точки зрения параметрическое программирование выступает как одно из средств анализа чувствительности решения к вариации исходных данных, оценки устойчивости решения. Заметим, что существуют различные подходы к подобному анализу (например, на основе постановки двойственной задачи). Здесь мы, не ссылаясь на двойственные оценки, рассмотрим самые простейшие варианты решения для самых простейших параметрических программ. Рассмотрим задачу параметрического линейного программирования, в которой только коэффициенты целевой функции линейно зависят от некоторого единственного параметра t (времени, температуры и т. п.): Отыскать максимум (или минимум) функции: Алгоритм для решения задач параметрического линейного программирования в случае зависимости от параметра коэффициентов целевой функции незначительно отличается от обычного симплексного метода (пример решения подобных задач рассмотрим ниже). В случае зависимости от параметра компонент вектора правых частей ограничений, т. е. решения задачи поиска экстремума функции 67 Пример. Рассмотрим задачу минимизации F = (2 - t) X1 – 3 t X2 + (t - 3) X3 при условиях X1 + X2 + X3≤ 5; 3 X1 - X2 - 2 X3 ≤ 6; X1 + 2 X2 + 2 X3 ≤ 8; Xj ≥ 0, j = 1 ... 3; 0 < t < 4. Решение. Базис X4 X5 X6 F Своб. чл 5 6 8 X1 1 3 1 2-t X2 1 -1 2 - 3t X3 1 -2 2 t -3 68 X4 1 X5 1 X6 1 Находим начальный базисный план задачи X0 = (0, 0, 0, 5, 6, 8), который был бы оптимален при выполнении условий: 2 - t >= 0, - 3 t >= 0, t – 3 >= 0. Однако попытка решения этой системы трех линейных неравенств обнаруживает её противоречивость (t ≤ 2, t ≤ 0, t ≥ 3). У нас еще ограничение t > 0. Пусть t < 3. Тогда t - 3 < 0 и вводим в базис X3, выводим X6: Базис X4 X5 X3 F Своб. чл 1 14 4 4 (3 - t) X1 1/2 3 1/2 (7 – 3t)/2 X2 -1 1 3 - 4t X3 1 1 X4 1 X5 1 X6 -1/2 1 1/2 (3 – t)/2 Полученный базисный план оптимален, если (7 – 3t)/2 >= 0, 3 - 4t >= 0, (3 – t)/2 >= 0. Решение этой системы обнаруживает, что план X=(0, 0, 4, 1, 14, 0) оптимален при t ≤ 3/4. Пусть t > 3/4. Тогда 3 - 4t < 0 и вводим в базис X2, выводим X3: Базис X4 X5 X2 F Своб. чл 1 10 4 12 t X1 1/2 7/2 1/2 (t + 4)/2 X2 1 X3 -1 1 4t-3 X4 1 X5 1 X6 -1/2 1/2 1/2 3t/2 Полученный план оптимален, если: (t + 4)/2 >= 0, 4 t – 3 >= 0, 3 t / 2 >= 0. Решение системы неравенств обнаруживает, что X = (0, 4, 0, 1, 10, 0) оптимален при всех t ≥ 3/4. Таким образом, рассмотрен весь диапазон значений t. Задача решена: В случае зависимости от параметра компонент матрицы ограничений простого универсального подхода к решению не существует. Нет простых решений и в случае зависимости характеристик задачи от нескольких параметров. 69 Целочисленное программирование Под задачей целочисленного программирования (ЦП) понимается задача, в которой все или некоторые переменные должны принимать целые значения. В том случае, когда ограничения и целевая функция задачи представляют собой линейные зависимости, задачу называют целочисленной задачей линейного программирования. В противном случае, когда хотя бы одна зависимость будет нелинейной, это будет целочисленной задачей нелинейного программирования. К задачам целочисленного программирования относятся многие задачи, т.к. они основаны на требовании целочисленности переменных, вытекающем из физических условий практических задач. К таким задачам относится, в частности, задача об определении оптимальной структуры производственной программы, где Х1, Х2, …, Хn - объемы выпуска соответствующей продукции. Математическая модель этой задачи имеет следующий вид: Оптимизировать F= n ¦ CjX j Æ max (min) j 1 при условиях: n ¦ АijXj  Bi (I = 1, 2, …, k) j 1 Хj>=0 (j = 1, 2,…, n) Х1, Х2, …, Хn – целые При решении некоторых задач «автоматически» обеспечивается решение в целых числах ( если заданы целочисленные параметры в условиях задачи). Однако в общем случае условие целочисленности, добавленное к обычным условиям ЗЛП, существенно усложняет решение задачи. Для решения ЗЛЦП используют разные методы. Самый простой из них – обычный метод ЛП. В том случае, когда компоненты оптимального решения оказались нецелочисленными, их округляют до ближайшего целого числа. Но такой метод можно применять тогда, когда отдельная компонента составляет малую часть всей совокупности. В противном случае округление может привести к далекому от оптимального целочисленному решению. Так что, в этом случае используют специальные методы. Методы целочисленной оптимизации можно разделить на три основные группы: x методы отсечения; x комбинаторные методы; x приближенные методы. Методы отсечения Суть методов в том, что сначала задача решается без условия целочисленности. Если полученное решение – целочисленное, то задача 70 решена. Иначе к ограничениям задачи добавляется новое ограничение, обладающее следующими свойствами: ƒ оно д.б. линейно; ƒ должно отсекать найденный оптимальный нецелочисленный план; ƒ не должно отсекать ни одного целочисленного плана. Далее задача решается с новым ограничением. После получения нового решения в случае необходимости добавляется новое ограничение и т.д. Метод отсекающих плоскостей впервые разработан Р. Гомори в 19571958 гг. для задач линейного целочисленного программирование (ЛЦП). Допустим необходимо решить задачу ЛЦП: Максимизировать F= n ¦ CjX j (1) j 1 при условиях n ¦ АijXj  Bi (I = 1, 2, …, m), (2) j 1 Хj>=0 (j = 1, 2,…, n) Х1, Х2, …, Хn – целые (3) (4) Алгоритм решения по методу Гомори: 1. Отбросив на определенное время условие целочисленности (4), найдем оптимальное решение симплекс-методом. Если окажется, что он удовлетворяет также и условию целочисленности, то это решение является искомым. 2. В противном случае нужно выбрать компоненту оптимального решения с наибольшей целой частью (иногда наибольшей дробной частью, иногда другой критерий эффективности отсечения) и по соответствующему уравнению на основе последней симплекс- таблицы сформировать 'правильное отсечение' на основе неравенства {Вi опт.} – {Ai m+1} X m+1 - … - {Ain} Xn <= o, (5) (5) можно доказать, но не будем где Х m+1, …, Xn - неосновные переменные, {} означают дробную часть числа, например: {4/3}=1/3, {-4/3}=2/3 3. В неравенство (5) вводим дополнительную неотрицательную целочисленную переменную Хn+1; преобразовываем (5) в уравнение и включаем в систему ограничений (2). 4. Полученную новую задачу решают симплекс-методом. Если найденный новый опт план – целочисленный, то ЗЦП решена. Иначе переходят к п.2 алгоритма. Если задача имеет решение в целых числах, то после конечного числа итераций оптим целочисл план будет найден. Если в процессе решения появится уравнение (выражающее основную переменную через неосновные) с нецелым свободным членом и целыми остальными коэффициентами, то соответствующее уравнение не имеет решения в целых числах. В этом случае и задача не имеет оптим целочисл решения. 71 Пример: Методом Гомори найти максимальное значение функции (1) при условии (2) (3) – целые (4) Решение. Для определения оптимального плана задачи (1) – (4) сначала находим оптимальный план задачи (1) – (3). Базис СЧ Х1 Х2 Х3 Х4 Х5 Х3 Х4 Х5 Х3 Х1 Х5 Х2 Х1 Х5 13 1 6 1 9 –3 1 –1 1 1 1 1 –3 –2 7 6 27 1 2 –1 –2 1 –1 1 3 1 18 –5 3 7/2 0 19/2 1 34 0 1 1/2 1/2 1 –1/2 0 1/2 0 2 1 71/2 0 5/2 1/2 Как видно из таблицы, найденный оптимальный план задачи (1) – (1) не является оптимальным планом задачи (1) – (4), поскольку две компоненты и имеют нецелочисленные значения. При этом целая часть больше для компоненты . Поэтому составим ограничение для переменной . Из последней симплекс–таблицы составляем неравенство или и добавляем к системе ограничений задачи (1) – (4). Вводим новую дополнительную переменную и решаем симплекс-методом (модифицированным симплекс-методом, т.к. первое БР – будет недопустимое). Чаще добавляют еще одно ограничение к системе ограничений из последней итерации и вводят в базис переменную из последнего (нового) ограничения, которая имеет меньший положительный коэффициент в строке ЦФ. После решения получаем Целевая функция = 35. 72 Метод ветвей и границ Метод ветвей (веток) и границ относится к группе комбинаторных методов и является одним из наиболее распространенных методов этой группы. Впервые метод ветвей и границ был предложен в работе Лэнд и Дойг в 1960 г. применительно к задаче линейного целочисленного программирования. Второе рождение метода связано с работой Литтла, Мурти, Суини и Кэрел, 1963 г., посвященной задаче о коммивояжере. Суть метода ветвей и границ заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые по определенным признакам оказались перспективными. Это достигается путем разбиения множества ДР на подмножества некоторым способом, каждое из подмножеств этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор, пока не получено оптим решение исх задачи. Алгоритм решения методом ветвей и границ: 1. Отбросив на определенное время условие целочисленности (4), найдем оптимальное решение симплекс-методом. Если окажется, что он удовлетворяет также и условию целочисленности, то это решение является искомым. 2. В противном случае производим ветвление задачи на две, для каждой из задач вводим дополнительные ограничения по одной из нецелочисленных переменных xi<=ai, xi>=bi, где ai – наибольшее целое, не превосходящее xi, а bi – наименьшее целое, большее xi, например, при нецелочисленной компоненте исходной задачи x2=2.3 доп. ограничение в одной ветви будет x2>=3, а по другой – x2<=2. 3. Снова решаются задачи в обеих ветвях с накладыванием последующих ограничений по другим переменным. На каждом шаге проверяется выполнения условия целочисленности. Ветку считают тупиковой, если: а) допустимое решение очередной задачи ЛП отсутствует; б) текущее решение (значение целевой функции) хуже уже найденного целочисленного решения; в) текущая задача ЛП является подзадачей ранее рассчитанной задачи. Процесс продолжается до тех пор, пока список задач не будет исчерпан, т.е. все задачи не будут решены. 73 Многокритериальная оптимизация На практике в большинстве случаев успех операции оценивается не по одному, а сразу по нескольким критериям. Такие задачи называются многокритериальными. Задача многокритериальной оптимизации может быть поставлена следующим образом: Fk = fk (x1, x2, ..., xn) Æ max (min) (k = 1, 2, …, K) при ограничениях: g i (x1, x2, ..., xn) ≤ b i (i = 1, 2, …, m), где К – количество различных критериев. При этом может оказаться, что достижение оптимальности по всем критериям невозможно, так как оптимизация по одному критерию приведет к худшему решению с точки зрения другого критерия. Например, всегда будут противоречить друг другу критерии при решении таких задач, как: максимизация доходов при одновременном снижении затрат или минимизация себестоимости с одновременным повышением качества продукции. Поставленная в таком виде задача никогда не даст результата, который будет лучше по всем признакам. В том случае, когда критерии противоречивы, используют несколько разных подходов к поиску оптимального решения. Ниже приведены основные методы: 1) многокритериальную задачу сводят к задаче с одним критерием путем «свёртки» критериев в один комплексный, при этом создается целевая функция, которая является функцией от исходных функций; 2) вместо некоторых критериев вводят дополнительные ограничения, которые устанавливают нижнюю или верхнюю границу для этого критерия; 3) критерии ранжируются по степени важности и после этого последовательно применяются при поиске решения; 4) находят решения, которые являются лучшими хотя бы одному критерию. Первые два подхода позволяют представить задачу в виде задачи с одним критерием и применять для ее решения те же методы, которые применяются для решения однокритериальных задач. Метод «свертки» критериев Для того чтобы из множества критериев, в том числе и противоречащих друг другу (например, доход и затраты), записать общую целевую функцию, необходимо установить значение весовых (экспертных) коэффициентов для каждого из критериев (при этом, более важный критерий получает более высокий вес). 74 Если целевые функции критериев обозначить через F1(Х), F2(Х), …, FК(Х), (Х=(x1, x2, ..., xn)), тогда целевая задачи будет записана в виде: F(X) = ω1 F1(X) + ω2 F2(X) + … + ωn FK(X), где ω1, ω2, …, ωn – некоторые коэффициенты (веса). Метод выделения главного критерия Применения этого метода возможно, когда частные критерии неравнозначны между собой (одни из них являются более важными, чем другие), что позволяет выделить главный критерий, а остальные критерии рассматривать как дополнительные и наложить на них только некоторые ограничения, чтобы они были не меньше (или не больше) каких-то заданных величин. Например, критерий минимизации себестоимости: F = f (x1, x2, ..., xn) Æ min заменить на ограничение: F = f (x1, x2, ..., xn) ≤ А, где А – некоторое максимально допустимая себестоимость продукции. При таком подходе все критерии, кроме главного, записываются как дополнительные ограничения задачи. Это позволяет свести задачу многокритериальной оптимизации к задаче нахождения оптимального решения по главному критерию. Например, при нахождении оптимального плана предприятия можно задать в качестве главного критерия, чтобы прибыль была максимальна, а себестоимость продукции – не выше заданной. Методы упорядочения критериев Суть методов упорядочивания критериев состоит в том, что все критерии упорядочиваются по их важности и оптимальное решение задачи находится по наиболее важному критерию. Далее поиск общего оптимального решения может продолжаться на основе использования следующих алгоритмов: 1. Метод последовательных уступок Если при решении задачи можно пойти на некоторое снижение значений более важных критериев, чтобы повысить величину менее важных, то для решения задачи может применяться метод последовательных уступок. В этом случае, после нахождения оптимального решения на основе самого важного критерия, на следующем шаге ищется решение наилучшее по следующему по важности критерию, при этом допускается потеря в значении первого критерия, но не более, чем на некоторую заданную величину, т.е. делается уступка по первому критерию. На третьем шаге оптимизируется 75 решение по третьему критерию, при заданных уступках по первому и второму критериям и т.д., пока не будет рассмотрен последний по важности критерий. Получаемое в итоге решение и будет считаться оптимальным. 2. Лексикографическое упорядочение Если разница между важностью упорядоченных критериев очень велика, и следующий критерий будет рассматривается только в том случае, когда сравниваемые альтернативы неразличимы по старшим критериям и об уступках не может быть и речи, то можно использовать лексикографическое упорядочение. При использовании этого метода, после нахождения оптимального решения на основе самого важного критерия, выбирается это решение в качестве оптимального решения задачи, если это решение единственное, несмотря на то, насколько оно является хорошим или плохим по другим, менее важным, критериям. Но если полученных оптимальных решений несколько, то, в области этих решений, ищется оптимальное решение на основе следующего по важности критерия. Процедура продолжается до тех пор, пока не будет найдено единственное оптимальное решение. Другими словами можно сказать, что ищется оптимальное решение для наименее важного критерия на множестве решений, оптимальных для более важного критерия. В этом случае решение часто заканчивается на первом шаге, а до последнего критерия вообще не доходят, так как не так часто существует несколько альтернативных оптимальных решений на каждом шаге. Задача с независимыми критериями При нахождении решения, которые являются лучшими хотя бы одному критерию, задача сводится к задаче с независимыми критериями. В таких задачах нужно найти множество решений, которые лучше любого другого допустимого решения хотя бы по одному критерию или не хуже по всем критериям. Такое множество называется множеством Парето. Множество Парето – это множество состояний системы, оптимальных по Парето. Оптимальность по Парето - такое состояние системы, при котором значение каждого частного показателя, характеризующего систему, не может быть улучшено без ухудшения других. Другими словами множество Парето можно определить как множество, в котором значение любого из частных критериев оптимальности можно улучшить только за счет ухудшения других частных критериев – любое из решений, принадлежащее множеству Парето, не может быть улучшено одновременно по всем частным критериям. В постановке задачи многокритериальной оптимизации фиксируется лишь множество допустимых значений и частные критерии. Этой информации недостаточно для однозначного решения задачи 76 многокритериальной оптимизации, она позволяет лишь выделить соответствующее множество Парето. Для однозначного решения задачи нужна дополнительная информация. 77 Транспортная задача Постановка транспортной задачи Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Первая строгая постановка Тзадачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее часто называют проблемой Хичкока. Первый точный метод решения Т-задачи разработан Л. В. Канторовичем и М. К. Гавуриным. Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (заводы, склады, базы и т.д.) в n пунктов назначения (магазины). При этом, из каждого пункта отправления (производства) возможно транспортировка продукта в любой пункт назначения (потребления). В качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Выбор критерия оптимальности При решении транспортной задачи выбор критерия оптимальности имеет важное значение. Как известно, оценка экономической эффективности примерного плана может определятся по тому или иному критерию, положенного в основу расчета плана. Этот критерий является экономическим показателем, характеризующим качество плана. До настоящего времени нет общепринятого единого критерия всесторонне учитывающего экономические факторы. При решении транспортной задачи, в качестве критерия оптимальности в различных случаях используют следующие показатели: 1) Объем работы транспорта (критерий - расстояние в т/км). Минимум пробега удобен для оценки планов перевозок, поскольку расстояние перевозки определяется легко и точно для любого направления. Поэтому критерию нельзя решать транспортные задачи с участием многих видов транспорта. С успехом применяется при решении транспортных задач для автомобильного транспорта. При разработке оптимальных схем перевозки однородных грузов автомобилями. 2) Тарифная плата за перевозку груза (критерий - тарифы провозных плат). Позволяет получить схему перевозок, наилучшую с точки зрения хозрасчетных показателей предприятия. Все надбавки, а также существующие льготные тарифы затрудняют его использование. 3) Эксплутационные расходы на транспортировку грузов (критерий себестоимость эксплутационных расходов). Более верно отражает экономичность перевозок различными видами транспорта. Позволяет делать обоснованные выводы о целесообразности переключения с одного вида транспорта на другой. 4) Сроки доставки грузов (критерий - затраты времени). 78 T l уч ¦v уч  ¦ Tтехн 5) Приведенные затраты (с учетом эксплуатационных расходов, зависящих от размеров движения и капиталовложения в подвижной состав). 6) Приведенные затраты (с учетом полных эксплуатационных расходов капиталовложений на строительство объектов в подвижной состав). С прив T Ц · § С зав  K эф ¨ K п  ¸ руб т 24 365 ¹ © , где С зав - эксплутационные издержки, К эф -расчетный коэффициент эффективности капиталовложения, Кп - капитальные вложения, приходящие на 1 т груза на протяжении участка, Т - время следования, Ц - цена одной тоны груза. Позволяет более полно производить оценку рационализации разных вариантов планов перевозок, с достаточно полной выраженностью количественно-одновременное влияние нескольких экономических факторов. Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе в j–м пункте назначения, а через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции (1) при условиях (2) (3) (4) 79 Поскольку переменные удовлетворяют системам линейных уравнений (2) и (3) и условию неотрицательности (4), то обеспечиваются вывоз имеющегося груза из всех пунктов отправления, доставка необходимого количества груза в каждый из пунктов назначения, а также исключаются обратные перевозки. Таким образом, Т-задача представляет собой задачу ЛП с m*n числом переменных, и m + n числом ограничений - равенств. Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единиц. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т. е. , (5) то модель такой транспортной задачи называется закрытой или сбалансированной. Существует ряд практических задач, в которых условие баланса не выполняется. Возможные два случая: Такие модели называются открытыми. 1) 2) В первом случае полное удовлетворение спроса невозможно. Такую задачу можно привести к обычной транспортной задаче следующим образом. В случае превышения потребности над запасом, т. е. вводится фиктивный (m+1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю: Тогда требуется минимизировать при условиях 80 Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. Рассмотрим теперь второй случай. Аналогично, при вводится фиктивный (n+1)–й назначения с потребностью и соответствующие считаются равными нулю: Тогда соответствующая Т-задача запишется так: пункт тарифы Минимизировать при условиях: Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (5). В некоторых случаях нужно задать, что по каким-либо маршрутам нельзя перевозить продукцию. Тогда стоимости перевозок по этим маршрутам задаются так, чтобы они превышали самые высокие стоимости возможных перевозок (для того, чтобы было невыгодно везти по недоступным маршрутам) – при решении задачи на минимум. На максимум – наоборот. Иногда нужно учесть, что между какими-то пунктами отправки и какими-то пунктами потребления заключены договора на фиксированные объемы поставки, то надо исключить объем гарантированной поставки из дальнейшего рассмотрения. Для этого объем гарантированной поставки вычитается из следующих величин: x из запаса соответствующего пункта отправки; x из потребности соответствующего пункта назначения. Пример. Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого 81 пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей Составить такой план перевозок, при котором общая стоимость перевозок является минимальной. Решение. Обозначим через количество единиц сырья, перевозимого из i–го пункта его получения на j–е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств: (6) При данном перевозок составит плане перевозок общая стоимость (7) Таким образом, математическая постановка данной транспортной задачи состоит в нахождении такого неотрицательного решения системы линейных уравнений (6), при котором целевая функция (7) принимает минимальное значение. Решение транспортной задачи Основные шаги при решении транспортной задачи: 1. Найти начальный допустимый план. 2. Выбрать из небазисных переменных ту, которая будет вводиться в базис. Если все небазисные переменные удовлетворяют условиям оптимальности, то закончить решение, иначе к след. шагу. 3. Выбрать выводимую из базиса переменную, найти новое базисное решение. Вернуться к шагу 2. Всякое неотрицательное решение систем линейных уравнений (2) и (3), определяемое матрицей , называется планом транспортной задачи. Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Обычно исходные данные транспортной задачи записывают в виде таблицы. 82 Матрицу С называют матрицей транспортных затрат, матрицу X, удовлетворяющую условиям Т-задачи (2) и (3) называют планом перевозок, а переменные - перевозками. План , при котором целевая функция минимальна, называется оптимальным. Число переменных в транспортной задаче с m пунктами отправления и n пунктами назначения равно m*n, а число уравнений в системах (2) и (3) равно m+n. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно m+n–1. Следовательно, опорный план транспортной задачи может иметь не более m+n–1 отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонент равно в точности m+n–1, то план является невырожденным, а если меньше – то вырожденным. Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом. Построение допустимого (опорного) плана в транспортной задаче По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Существует несколько методов построения начальных опорных планов Тзадачи. Из них самый распространенный метод северо-западного угла и метод минимального элемента. Наиболее простой способ его нахождения основывается на так называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины текущих нераспределенных запасов обозначаются аi(q), а текущих неудовлетворенных потребностей — bj(q). Построение допустимого начального плана, согласно методу северо-западного угла, начинается с левого верхнего 83 угла транспортной таблицы, при этом полагаем аi(0)= аi, bj(0)= bj. Для очередной клетки, расположенной в строке i и столбце j, рассматриваются значения нераспределенного запаса в i-ом пункте производства и неудовлетворенной потребности j-ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: хi,j=min{аi(q), bj(q)}. После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на данную величину: аi(q+1)= аi(q) - xi,j, bj(q+1)= bj(q) - xi,j Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: (q+1) аi = 0 или bj(q+1)= 0. Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте производства i+1, т. е. переместиться к следующей клетке вниз по столбцу. Если же bj(q+1) = 0, то значит, полностью удовлетворена потребность для j-го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все перечисленные операции. Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы получим допустимый план. В силу того же условия число шагов алгоритма не может быть больше, чем m+n-1, поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не исключено, что на некотором промежуточном шаге текущий нераспределенный запас оказывается равным текущей неудовлетворенной потребности (аi(q)=bj(q)). В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и потребления), а это означает «потерю» одной ненулевой компоненты в плане или, другими словами, вырожденность построенного плана. Особенностью допустимого плана, построенного методом северозападного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимального. Это происходит потому, что при его построении никак не учитываются значения ci,j. В связи с этим на практике для получения исходного плана используется другой способ — метод минимального элемента, в котором при распределении объемов перевозок в первую очередь занимаются клетки с наименьшими ценами. Пример нахождения опорного плана Поставщики 1 2 3 Потребители и их спрос 1 2 3 4 33 13 27 17 14 28 21 28 10 17 15 24 14 30 25 21 84 Мощность поставщиков 27 20 43 F=14 x11 + 28 x12 + 21 x13 + 28 x14 + 10 x21 + 17 x 22 + 15 x23 + 24 x24 + 14 x31 + 30 x32 +25 x33 + 21 x34 Первоначальный план получен по методу северо-западного угла. Задача сбалансированная (закрытая). Таблица 1 Стоимость перевозок по данному плану составляет: 1681: F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 =1681 Нахождение оптимального решения С помощью методов построения первоначального опорного плана можно получить вырожденный или невырожденный опорный план. Построенный план транспортной задачи как задачи линейного программирования можно было бы довести до оптимального с помощью симплексного метода. Однако из-за громоздкости симплексных таблиц, содержащих тп неизвестных, и большого объема вычислительных работ для получения оптимального плана используют более простые методы. Наиболее часто применяются метод потенциалов (модифицированный распределительный метод) и метод дифференциальных рент. Метод потенциалов. Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А. В. И Гавуриным М. К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций). 85 Алгоритм нахождения решения транспортной задачи этим методом основан на соотношении между прямой и двойственной задачами. Выбор небазисной переменной, которая будет вводиться в базис. Пусть одним из методов найден опорный план. Для опорного плана, в котором m  n  1 базисных клеток, для каждой строки и каждого столбца определяются потенциалы u i и v j так, чтобы выполнялось условие: u i  v j cij , если xij ! 0 (где cij - стоимость перевозки из пункта i в пункт j) (8) Поскольку система (8) содержит m  n  1 уравнений и m+n неизвестных, то одну из них можно задать произвольно (например, приравнять к нулю). После этого из m  n  1 уравнений (8) определяются остальные потенциалы и для каждой из свободных клеток вычисляются величины ci,j’ = ui + vj - ci,j. Если оказалось, что все ci,j’ отрицательны, то план оптимален. Если же хотя бы в одной свободной клетке ci,j’ > 0, то план не является оптимальным и для включения в базис выбирается небазисная переменная, имеющая самую большую положительную оценку ci,j’ (опорная клетка). Выбор переменной, которая будет выводиться из базиса. Для того, чтобы найти новый план перевозок необходимо составить цикл пересчета. Цикл пересчета представляет собой замкнутую ломаную линию состоящую из горизонтальных и вертикальных линий, концы которых лежат в заполненных клетках. Ломаная линия начинается и заканчивается в опорной клетке. Узел в опорной клетке считается положительным, следующий отрицательный, и так далее чередуясь. Берется минимальное по абсолютной величине значение в отрицательных клетках. Эта клетка и будет соответствовать базисной переменной, выводимой из базиса. Во всех отрицательных клетках это значение отнимается, в положительных прибавляется. Получили новый план перевозок. Если ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами. Процесс улучшения плана продолжается до тех пор, пока не будет получен план, в котором все ci,j’ отрицательны. Пример нахождения оптимального плана (См. Пример нахождения опорного плана.) Рассчитаем потенциалы пунктов отправки и пунктов доставки u i и v j . Для этого составьте систему для заполненных клеток плана перевозок: u i  v j cij , Решим данную систему, полагая u i =0. . 2. Вычислим коэффициенты изменения стоимости для незаполненных клеток плана: ci,j’ = ui + vj - ci,j. 86 Таблица 2 Поставщики Потребители и их спрос B1 B2 B3 и их ресурсы 33 13 27 A1 27 14 27 28 -7 20 10 [-6] 0 6 17 43 14 [+6] 6 0 30 -3 A2 A3 14 17 28 -13 13 15 [+6] 0 1 24 -13 25 [-6] 0 26 21 21 -2 B4 21 19 17 -4 6 15 Стоимость перевозок по данному плану составляет: 1681. F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 =1681 Получим потенциалы u i и v j .. Рассчитаем коэффициенты изменения стоимости перевозок. Составим цикл пересчета: Опорная клетка: (3:1) , далее (3:3) [-6], (2:3) [+6], (2:1) [-6]. Количество единиц изменения плана: 6. Потенциалы, коэффициенты и цикл пересчета указаны в таблице 2. Получим следующий план перевозок (Табл.3). Таблица 3. Поставщики Потребители и их спрос B1 B2 B3 и их ресурсы 33 13 27 A1 27 14 [-20] 28 0 27 -1 20 10 -6 43 14 [+20] 30 0 6 -3 A2 A3 14 17 13 27 B4 17 21 [+20] 28 4 0 -7 15 7 24 -13 25 [-20] 21 0 20 25 17 -10 21 Стоимость перевозок по данному плану составляет: 1645. F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *0 + 17 *13 + 15*7 + 24 *0 + 14 *6 + 30 *0 +25*20 + 21 *17 =1645 Получим потенциалы u i и v j . Рассчитаем коэффициенты изменения стоимости перевозок. Составим цикл пересчета: Опорная клетка: (1:3) , далее (1:1) [-20], (3:1) [+20], (3:3) [-20]. Количество единиц изменения плана: 20 Потенциалы, коэффициенты и цикл пересчета указаны в таблице 3. Получим следующий план перевозок (Табл.4). 87 Таблица 4. Потребители и их спрос B1 B2 B3 33 13 27 B4 27 14 20 28 -7 20 10 -2 7 24 -9 43 14 21 17 Поставщики и их ресурсы A1 A2 A3 14 7 28 -5 17 26 30 -7 23 21 13 15 25 -4 17 21 -6 21 Стоимость перевозок по данному плану составляет: 1565. F=14 *7 + 28* 0 + 21*20 + 28*0 + 10 *0 + 17 *13 + 15*7 + 24 *0 + 14 *26 + 30 *0 +25*0 + 21 *17 =1565 Получим потенциалы u i и v j . Рассчитаем коэффициенты изменения стоимости перевозок. Потенциалы и коэффициенты указаны в таблице 4. Полученный план оптимальный, т.к. все коэффициенты изменения стоимости отрицательны или равны нулю. Решение транспортной задачи средствами EXCEL Создание в Excel модели для решения задачи Для решения задачи средствами Excel удобно подготовить на листе Excel модель следующего вида: 88 Для создания модели используются формулы расчета общей стоимости перевозок и определения суммарного количества перевозок от каждого производителя и к каждому потребителю. Эти формулы удобно задавать при помощи функции СУММПРОИЗВ. Решение задачи в Excel Для решения задачи используется команда Сервис/Поиск решения. Если такой команды в меню нет, то необходимо выполнить нажать Кнопку «Office» , в нижней части появившегося меню нажать кнопку Параметры Excel, в появившемся окне перейти в Надстройки, нажать кнопку Перейти к Настройкам Excel и установить Поиск решения. После выполнения команды появится окно: Задать ячейку с целевой функцией, изменяемые ячейки, ограничения. Задать параметры «Линейная модель» и «Неотрицательные значения» (См. лекцию по ЛП). 89 Для нахождения решения нажать кнопку «Выполнить» в окне Поиска решения. В появившемся окне «Результаты поиска решения» отображается информация о том, найдено или нет решение, в этом окне можно выбрать тип отчета. Иногда сообщения о том, найдено или нет оптимальное решение свидетельствуют не о характере оптимального решения задачи, а о том, что при вводе условий задачи в Excel были допущены ошибки, не позволяющие Excel найти оптимальное решение, которое в действительности существует. В окне "Результаты поиска решения" представлены названия трех типов отчетов: "Результаты", "Устойчивость", "Пределы". Для выбора нужных отчетов необходимо выделить их названия. Отчет будет представлен на отдельном листе рабочей книги Excel. Для получения более полной информации в отчете по устойчивости нужно в окне задания параметров установить флажок "Линейная модель". Для получения же ответа (значений переменных и ЦФ) прямо в экранной форме можно сразу нажать кнопку "OK". После этого в экранной форме появляется оптимальное решение задачи. 90 x x x x x Замечания по решению ТЗ: Если запасы груза в пунктах отправления и потребности в пунктах назначения выражены целыми числами, то, исходя из алгоритма решения ТЗ будут получены целочисленные решения. Если задача не сбалансированная и при этом объемы предложения больше спроса, то ограничения не меняются. Если задача не сбалансированная и при этом объемы предложения меньше спроса, то в ограничениях на количество отправляемых грузов надо знак « <= » поменять на знак « = », а в ограничениях на количество доставляемых грузов поменять знак « >= » на знак « <= » (т.е. не все потребности будут удовлетворены). Если по каким-либо маршрутам нельзя перевозить продукцию, то стоимости перевозок по этим маршрутам задаются так, чтобы они превышали самые высокие стоимости возможных перевозок (для того, чтобы было невыгодно везти по недоступным маршрутам) – при решении задачи на минимум. На максимум – наоборот. Если нужно учесть, что между какими-то пунктами отправки и какими-то пунктами потребления заключены договора на фиксированные объемы поставки, то надо исключить объем гарантированной поставки из дальнейшего рассмотрения. Для этого объем гарантированной поставки вычитается из следующих величин: ƒ из запаса соответствующего пункта отправки; ƒ из потребности соответствующего пункта назначения. 91 Анализ оптимального решения на чувствительность в Excel Для проведения анализа полученного решения на чувствительность необходимо после запуска в Excel задачи на решение в окне "Результаты поиска решения" выделить с помощью мыши два типа отчетов: "Результаты" и "Устойчивость". Отчет по результатам Отчет по результатам состоит из трех таблиц: x таблица 1 содержит информацию о ЦФ; x таблица 2 содержит информацию о значениях переменных, полученных в результате решения задачи; x таблица 3 показывает результаты оптимального решения для ограничений и для граничных условий. Отчет по устойчивости Отчет по устойчивости состоит из двух таблиц. Таблица 1 содержит информацию, относящуюся к переменным: x Результ. значение показывает результат решения задачи. x Нормированная стоимость показывает, на сколько изменится значение ЦФ в случае принудительного включения единицы соответствующей перевозки в оптимальное решение. x Коэффициенты ЦФ отображают исходные данные. x Допустимое увеличение и уменьшение показывают предельные значения приращения целевых коэффициентов, при которых сохраняется первоначальное оптимальное решение. Другими словами: на сколько нужно снизить затраты на перевозку по неиспользуемым направлениям, чтобы по ним было выгодно везти 92 продукцию. Например, если затраты на перевозку из А1 в В2 снизить более, чем на 5 единиц, т.е. они станут < 28-5, то везти груз по этому маршруту станет выгодно. Таблица 2 содержит информацию, относящуюся к ограничениям. x Результ. значение показывает сколько всего груза заберут у производителей и привезут потребителям. x Теневая цена показывает, на сколько будет изменяться значение ЦФ (т.е. общие затраты на перевозки), если будут уменьшаться потребности в пунктах назначения или увеличиваться запасы в пунктах отправления (в другую сторону невозможно, т.к. данная задача будет неразрешима из-за превышения спроса над предложением). x Ограничение правая часть показывает исходные данные из правых частей ограничений. Допустимое увеличение и уменьшение показывают предельные значения уменьшения потребностей или увеличения запасов. 93 Задача о назначениях Задача о назначениях – это задача, в которой для выполнения каждой работы требуется один и только один ресурс (один человек, одна автомашина и т.д.), а каждый ресурс может быть использован на одной и только одной работе. То есть ресурсы не делимы между работами, а работы не делимы между ресурсами. Таким образом, задача о назначениях является частным случаем ТЗ. Задача о назначениях имеет место при назначении людей на должности или работы, автомашин на маршруты, водителей на машины, при распределении групп по аудиториям, научных тем по научноисследовательским лабораториям и т.п. Метод назначений - это один из методов линейного программирования, который предназначен для оптимального подбора m "предложений" к n "потребностям". Т.о. метод назначений применяется при решении задач, имеющих следующие характеристики: 1. Имеется m "предметов", которые должны быть распределены по n "пунктам назначения". 2. Каждый "предмет" должен быть назначен единственному "пункту назначения". В понятие "предмет" и "пункт назначения" может вкладываться различное смысловое значение, определяемое конкретной задачей менеджмента. Так в качестве предмета может выступать определенный человек, автомашина и т.д. 3. Оптимальный подбор назначений должен быть достигнут за счет максимизации или минимизации определенной меры эффективности назначения: прибыли или стоимости. Для каждого потенциального назначения оценивается мера эффективности. Если мерой эффективности является прибыль, то в процессе решения задачи о назначениях она максимизируется, если мерой эффективности является стоимость, она минимизируется. Модель задачи о назначениях (1) ; 94 Где: x исходные параметры: m – количество ресурсов (предложений), n – количество работ (потребностей); ai = 1 – единичное количество ресурса (предложения) Ai (i = 1,m), например: один работник; одно транспортное средство; одна научная тема и т.д.; b j 1 – единичное количество работы (потребности) B j (j = 1,n), например: одна должность; один маршрут; одна лаборатория; cij – характеристика качества выполнения работы B j с помощью ресурса Ai . Например, компетентность i -го работника при работе на j -й должности; время, за которое i -е транспортное средство перевезет груз по j му маршруту и т.д.. x искомые параметры x ij B – факт назначения или неназначения ресурса Ai на работу j : F – общая (суммарная) характеристика качества распределения ресурсов по работам. В зависимости от экономического смысла cij может либо максимизироваться, либо минимизироваться. Некоторые замечания по постановке и решению задачи о назначениях: 1. Для того, чтобы показать невозможность назначения i –го ресурса на c j–ую работу тариф ij для этого назначения задается, руководствуясь принципом "невыгодности" запрещенных назначений. Так, если F – это общая компетентность работников, то в качестве запрещающих надо выбирать cijз нулевые компетентности . А если F – это общее время прохождения машинами транспортных маршрутов, то в качестве запрещающих надо cз выбирать значения ij , превосходящие по величине максимальные реальные c значения ij . 95 2. В случае несбалансированности (не выполняется условие ) задачи из-за нехватки ресурсов или работ в количестве k ab для создания баланса надо ввести такое же количество k ab фиктивных строк или столбцов. c Все значения ij для фиктивных строк или столбцов должны полагаться равными нулю. Общий вид матрицы задачи о назначениях Ресурсы, Ai А1 А2 … Am В1 Количество работ 1 c11 c21 … cm1 Работы, B j … В2 c12 … c22 … … … cm2 … 1 … Количество ресурсов Вn c1n c2n … cmn 1 1 … 1 1 Для решения задачи о назначениях существует несколько различных методов. Наиболее часто используется так называемый "Венгерский метод" ее решения. Пример постановки задачи о назначениях Например, пусть имеются четыре должности, на которые необходимо назначить четырех кандидатов, которые в этом случае становятся работниками. Каждому работнику может быть назначена единственная должность. Заметим, что количество должностей равно количеству работников. Необходимо составить матрицу, чтобы показать все возможные взаимосвязи между четырьмя должностями и четырьмя работниками. Работников можно представить строками матрицы, а должности - столбцами, как показано в таблице 1. 16 ячеек матрицы содержат стоимости каждой возможной комбинации работник-должность. Например, стоимость назначения должности 2 работнику 2 составляет $19. Содержимое ячеек матрицы определяет интегральную меру эффективности, которая должна минимизироваться, поскольку является стоимостью. Если содержимое ячеек матрицы представляет собой прибыль, мера эффективности должна максимизироваться. 96 Таблица 1. Матрица назначений работников на должности Кандидаты Должности 1 2 3 4 1 16 9 14 17 2 7 19 8 14 3 15 6 9 10 4 19 17 11 4 Замечание: Содержимое ячеек - стоимости соответствующих комбинаций должность-работник. Cтоимость в этом примере может зависеть от квалификации потенциального работника, его опыта и т.п. Ответ: Должности Кандидаты 1 2 3 4 1 1 1 2 1 3 1 4 При этом минимальная стоимость = 29. В Excel задачи решаются обычным симплекс-методом. Модель для решения задачи аналогична той, которая была описана для решения транспортной задачи. Только, при решении задач о назначении в Excel, необходимо x учитывать, что переменные ij являются булевыми (двоичными). 97 Модели нелинейного программирования В предыдущих лекциях были рассмотрены постановки задач линейного программирования, в которых целевая функция и ограничения содержали только линейные функции. На практике, очень часто при построении экономических моделей оказывается, что зависимости между постоянными и переменными факторами имеют нелинейный характер. Обычно, такие показатели, как прибыль, себестоимость, совокупные транспортные затраты и многие другие, зависят от объема производства (расходы ресурсов, объема перевозок и др.) нелинейно. В этом случае задача будет относиться к задачам нелинейного программирования. Задачи нелинейного программирования – это задачи, в которых (как и в задачах линейного программирования) требуется найти такие значения переменных X1, X2, ..., Xn, которые обеспечивают максимальное или минимальное значение целевой функции при соблюдении системы ограничений. Но целевая функция и/или некоторые из ограничений, в этом случае, являются нелинейными, т.е. содержат нелинейные составляющие (например, Х12, 1/X1, X1X2 и т.д.). Общую задачу нелинейного программирования можно представить в виде: F = f (x1, x2, ..., xn) Æ max (min) При ограничениях: g i (x1, x2, ..., xn) ≤ b i (i = 1, 2, …, k) g i (x1, x2, ..., xn) = b i (i = k+1, k+2, …, m), где f и g i – известные функции n переменных (одна или несколько из них являются нелинейными), а bi – заданные значения. Как и в задачах линейного программирования, любые значения переменных X1, X2, ..., Xn, удовлетворяющие ограничениям задачи, называются допустимыми решениями, а все множество допустимых решений – областью допустимых значений (ОДЗ). Допустимые значения переменных X1, X2, ..., Xn, при которых целевая функция принимает минимальное или максимальное значение, являются оптимальным решением. В задачах нелинейного программирования оптимальное решение может находиться как на границе, так и внутри ОДЗ. Математические модели задач нелинейного программирования очень разнообразны, поэтому универсальных методов, позволяющих решать любую задачу нелинейного программирования, не существует. Разработано большое количество методов, каждый из которых предназначен для решения определенного класса задач. 98 Если проводить классификацию методов с точки зрения характера решаемых задач, то можно выделить следующие группы методов: x методы решения задач без ограничений, которые предназначены для решения задач, в которых требуется найти экстремум нелинейной функции без ограничений на значения переменных; x методы квадратичного программирования, которые предназначены для решения задач с линейными ограничениями и квадратичной целевой функцией, т.е. целевой функцией, содержащей квадраты переменных (например, x12 или x22) и/или их попарные произведения (например, x1x2); x методы сепарабельного программирования, которые предназначены для решения задач, в которых ограничения и целевая функция являются сепарабельными, т.е. могут быть представлены в виде сумм функций одной переменной. При классификации методов на основе используемого математического аппарата обычно выделяют следующие группы методов: x аналитические (классические) - поиск решения осуществляется на основе использования необходимых и достаточных условий экстремумов функций (например, равенства нулю производных); x численные - поиск решения производится на основе постепенного сужения диапазона, в котором ищется решение; x покоординатные - поиск решения производится на основе поочередного поиска экстремума целевой функции по каждой из переменных; x градиентные - поиск решения производится на основе использования градиента целевой функции; x случайного поиска - поиск решения осуществляется на основе многократного случайного выбора возможных решений. Примеры задач нелинейного программирования Пример 1. Предприятие производит и продает только один вид продукции. Предприятие может устанавливать свои отпускные цены на продукцию. Известно, что спрос на данную продукцию зависит только от цены на эту продукцию, и для данного предприятия функция спроса на продукцию является линейной и может быть описана следующим образом: Q = - Р + 8. где Q – объем спроса на продукцию, P – цена продукции. Себестоимость выпуска единицы продукции на предприятии не зависит от объема выпуска и составляет 2 рубля. Задача состоит в том, чтобы определить такую цену и объем выпуска, при которых прибыль предприятия была бы максимальной. Выручка от продаж R определяется формулой 99 R(P) = Q * P Прибыль π можно вычислить как разность между выручкой и общими затратами: π(P) = R(P) – C * Q, где С – себестоимость выпуска единицы продукции. Если цену за единицу продукции обозначить Х1, то можно построить следующую математическую модель: F = (-Х1 + 8) * Х1 – 2 * (-Х1 + 8) = 10 Х1 – Х12 -16 → max - Х1 + 8 t 0 Х1 t 0. Модель предполагает максимизацию прибыли при условии, что объемы продукции и цены неотрицательны. Даже для линейной функции спроса функция выручки является квадратичной, так что и в этом случае задача будет являться задачей квадратичного программирования. Пример 2. Предприятие выпускает продукцию двух типов (А и В) и запасные части к этой продукции. В комплект запасных частей, выпускаемых вместе с каждым видом продукции, может входить от одной до трех запасных частей, причем количество запасных частей для всей продукции одного типа должно быть одинаковым. Данные о расходе ресурсов на выпуск продукции и запасных частей и запасы ресурсов приведены в таблице: Вид ресурса Продукция А Ресурс 1 (кг) Ресурс 2 (м) 5 2 Прибыль от одной штуки (руб.) 8 Запасная Продукция часть к В продукции А 0,4 4 0,2 6 0,4 10 Запасная часть к продукции В Запас ресурсов 0,2 0,2 600 500 0,8 Требуется определить, сколько продукции каждого типа и запасных частей к ней должно выпустить предприятие, чтобы получить максимальную прибыль. Для решения задачи необходимо использовать следующие переменные: X1 – количество выпуска продукции А; X2 – количество запасных частей в комплекте к одной штуке продукции А; X3 – количество выпуска продукции В; X4 – количество запасных частей в комплекте к одной штуке продукции В. 100 При этом количество запасных частей к продукции можно рассчитать по формулам: количество запасных частей к продукции А = X1 * X2; количество запасных частей к продукции В = X3 * X4; Математическая модель задачи: F = 8 X1 + 0,4 X1 * X2+ 10 X3+ 0,8 X3 * X4 → max при ограничениях: X2 ≤ 3 X2 ≥ 1 X4 ≤ 3 X4 ≥ 1 5 X1 + 0,4 X1 * X2 + 4 X3 + 0,2 X3 * X4 ≤ 600 2 X1 + 0,2 X1 * X2 + 6 X3 + 0,2 X3 * X4 ≤ 500 Xi – целые, i = 1, ..., 4 Xi ≥ 0, i = 1, ..., 4 Целевая функция выражает общую прибыль от выпуска приборов и запасных частей. Первые четыре ограничения показывают, что количество запасных частей к одной единице продукции A и В должно составлять не менее одной и не более трех штук. Пятое и шестое ограничения устанавливают предельный расход ресурсов. В этой задаче нелинейными являются целевая функция, четвертое и пятое ограничения. Метод множителей Лагранжа Далее будет рассмотрен частный случай общей задачи нелинейного программирования, который предполагает, что система ограничений содержит только уравнения, отсутствуют условия неотрицательности переменных и функции f и gi являются непрерывными вместе со своими частными производными: F = f (x1, x2, ..., xn) Æ max (min) g i (x1, x2, ..., xn) = b i (i = 1, …, m). В курсе математического анализа такую задачу называют задачей на условный экстремум или классической задачей оптимизации. Чтобы найти решение этой задачи, вводят набор переменных λ1, λ2 , ..., λm, называемых множителями Лагранжа, и составляют функцию Лагранжа: F = F (x1, x2, ..., xn, λ1, λ2 , ..., λm) = f (x1, x2, ..., xn) + Далее находят частные производные 101 λi [bi - g i (x1, x2, ..., xn)] и рассматривают систему n+m уравнений: с n+m неизвестными x1, x2 ,..., xn, λ1, λ2 ,..., λm . Всякое решение системы уравнений определяет точку Х*=( x1, x2, ..., xn), в которой может иметь место экстремум функции f (x1, x2 ,..., xn ). Следовательно, решив данную систему уравнений, получают все точки, в которых указанная функция может иметь экстремальные значения. Дальнейшее исследование найденных точек проводят так же, как и в случае безусловного экстремума. Таким образом, определение экстремальных точек задачи методом множителей Лагранжа включает следующие этапы: x составляют функцию Лагранжа; x находят частные производные от функции Лагранжа по переменным xj и λi, приравнивают их к нулю; x решая данную систему уравнений, находят точки, в которых целевая функция задачи может иметь экстремум; x среди точек, подозрительных на экстремум, находят такие, в которых достигается экстремум, и вычисляют значение функции в этих точках. Методы решения для моделей выпуклого программирования Если рассматривать задачу нелинейного программирования с условиями неотрицательности переменных: f (x1, x2, ..., xn) → max (1) gi (x1, x2, ..., xn ) − bi ≤ 0 (i = 1,...,m) (2) x j ≥ 0 ( j =1,..., n), (3) где f и gi — некоторые нелинейные функции n переменных x1, x2, ..., xn, то для решения задачи в такой общей постановке не существует универсальных методов. Однако для отдельных классов задач, в которых сделаны дополнительные ограничения относительно свойств функций f и gi, есть методы решения. В частности, ряд методов существует для решения задач нелинейного программирования при условии, что f — вогнутая (выпуклая) функция и область допустимых значений (решений), определяемая ограничениями, является выпуклой. 102 Множество называется выпуклым, если вместе с любыми двумя точками из этого множества, ему принадлежит и отрезок, их соединяющий. Функция f (x) является выпуклой на выпуклом множестве, если для любых двух точек х1 и х2 и для любого числа выполняется неравенство Йенсена: f ( tx1 + (1 - t) x2) ≤ t f(x1) + (1 – t) f (x2) Если это неравенство является строгим для всех и x1 ≠ x2, то функция называется строго выпуклой; если выполняется обратное неравенство, функция называется вогнутой, или выпуклой вверх. Для функции одной переменной это означает, что функция f (x) лежит ниже хорды, соединяющей любые две точки ее графика. Функцией Лагранжа задачи выпуклого программирования называется функция L(x1, x2, ..., xn, λ1, λ2 , ..., λm) = f (x1, x2, ..., xn) + yi [bi - g i (x1, x2, ..., xn)], где y1, yλ2 , ..., ym – множители Лагранжа. Точка (Х0;Y0) = функции Лагранжа, если называется седловой точкой для всех x j ≥ 0 ( j =1,..., n) и y i ≥ 0 ( i =1,..., m). Говорят, что множество допустимых решений задачи (1) - (3) удовлетворяет условию регулярности, если существует, по крайней мере, одна точка X0, принадлежащая области допустимых решений такая, что gi (x1, x2, ..., xn ) < bi (i = 1,...,m) . Теорема (Куна - Таккера). Для задачи выпуклого программирования, множество допустимых решений которой обладает свойством регулярности, является оптимальным решением тогда и только тогда, когда существует такой вектор , что (X0;Y0) седловая точка функции Лагранжа. Если предположить, что функции f и gi непрерывно дифференцируемы, то теорема Куна - Таккера может быть дополнена аналитическими выражениями, определяющими необходимые и достаточные условия того, чтобы точка (X0;Y0) была седловой точкой функции Лагранжа, т. е. являлась решением задачи выпуклого программирования: 103 где - значения соответствующих частных производных функции Лагранжа, вычисленных в седловой точке. Таким образом, процесс нахождения решения задачи выпуклого программирования включает следующие этапы: x проверка задачи на принадлежность выпуклому программированию; x составление функции Лагранжа; x формулировка необходимых и достаточных условий существования седловой точки для функции Лагранжа; x нахождение координаты седловой точки функции Лагранжа (проверяя, будет ли найденная точка являться точкой максимума), или определение ее отсутствия; x определение значения целевой функции. Квадратичное программирование Задача квадратичного программирования является частным случаем задачи нелинейного программирования. Ограничения в задаче квадратичного программирования представлены в виде линейных функций, а функция f (x1, x2, ..., xn) представляет собой сумму линейной и квадратичной функций. Модель такой задачи может быть представлена в следующем виде: (4) gi (x1, x2, ..., xn ) = ≤ 0 (i = 1,...,m) (5) 104 Как и в общем случае решения задач нелинейного программирования, для определения глобального экстремума задачи квадратичного программирования не существует эффективного вычислительного метода, если не известно, что любой локальный экстремум является одновременно и глобальным. Так как в задаче квадратичного программирования множество допустимых решений выпукло, то, если целевая функция вогнута, любой локальный максимум является глобальным; если целевая функция - выпуклая, то любой локальный минимум является глобальным. Функция представляет собой сумму линейной функции и квадратичной формы. Если последняя является вогнутой (выпуклой), то задачи отыскания максимума (минимума) целевой функции могут решены. Функция в задаче квадратичного программирования будет вогнутой (выпуклой), если матрица коэффициентов D (в целевой функции) положительно определена, то есть, если XTDX > 0 при любом Х и XTDX=0 лишь при Х=0 (где: Х – n–мерный вектор, ХТ – транспонированный n–мерный вектор). Так как ограничения в задаче квадратичного программирования линейны ограничений (то есть множество планов выпукло), то для решения задач с вогнутой (выпуклой) можно использовать теорему Куна-Таккера. 105 Модели сетевого планирования и управления Основной подход всех сетевых методов состоит в построении фактической или предполагаемой сети работ и событий, которая графически представляет последующие отношения между работами в проекте. Работы, которые должны предшествовать или следовать за другими работами, четко определяются по времени, а также по назначению. Сетевое планирование (СПУ) является одним из методов планирования и управления производством календарного проекта, базирующимся на решении задач класса упорядочения с использованием теории графов. При использовании данного метода строят пространственную модель выполнения работ какого-либо разового процесса (явления), проекта. Сетевые графики являются воплощением плана действий проекта в рабочее расписание. Они служат фундаментальной основой мониторинга и контроля работ проекта. Вместе с планом и бюджетом они являются главнейшим инструментом управления проектами. В отличие от линейных графиков сетевое планирование служит основой для экономических и математических расчетов, графических и аналитических вычислений, организационных и управленческих решений, оперативных и стратегических планов. Сетевое планирование обеспечивает не только изображение, но и моделирование, анализ и оптимизацию проектов выполнения сложных технических заданий, конструкторских разработок и т.д. Применение сетевого планирования в современном производственном процессе способствует решению стратегических и оперативных задач. Под сетевым планированием принято понимать воображение определенного комплекса выполняемых работ, которое отражает их логическую последовательность, существующую взаимосвязь и планируемую продолжительность, но обеспечивает также последующую оптимизацию разработанного графика с тем, чтобы использовать его для текущего управления ходом работ. Основные понятия СПУ Сетевая модель проекта строится на основе четырех основных понятий: работа, событие, путь, резервы. Работа – это процесс требующий затрат времени и ресурсов и приводящий к определенному результату. На сетевом графике работа обозначается стрелкой слева направо. На самом деле, термин работа в СПУ имеет несколько значений: x действительная работа – процесс выполнения каких-либо действий, приводящий к достижению определенного результата, протяжённый во времени и требующий затрат трудовых, материальных и финансовых ресурсов; 106 x ожидание – процесс, не требующий затрат труда, но обладающий определенной протяжённостью во времени (например, процесс сушки после покраски, твердения бетона и т.п.); x зависимость или фиктивная работа – логическая связь между двумя или несколькими работами, не требующая затрат труда, материальных ресурсов или времени; она указывает, что начало одной работы требует результатов другой; продолжительность фиктивной работы принимается равной нулю. На сетевом графике действительные работы и работы ожидания обозначаются сплошными стрелками, фиктивные работы обозначаются пунктирными стрелками. Событие – это факт начала или окончания работы. Событие не требует затрат ресурсов. Продолжительность событий во времени равна нулю. На графиках события обозначают кружками. На сетевом графике можно выделить три вида событий: x исходное событие – это событие означающее начало выполнения комплекса и не имеющее предшествующих работ; x завершающее событие – событие, означающее завершение комплекса работ и достижение его конечной цели. Такое событие не имеет следующих за ним работ; x промежуточное событие, или просто событие – результат одной или нескольких работ, предоставляющий возможность начать работы, которые для своего начала требуют этого результата. Любое промежуточное событие имеет двойственный характер: для всех непосредственно предшествующих ему работ оно является конечным, а для всех непосредственно следующих за ним – начальным. Каждая работа сетевого графика соединяет между собой два события: непосредственно предшествующее данной работе (являющееся для нее начальным событием) и непосредственно следующее за ней (являющееся для нее конечным событием). Событие считается свершившимся, если заканчивается самая продолжительная из предшествующих ему работ. Путь – это непрерывная последовательность работ и событий на сетевом графике. Длина пути определяется суммой продолжительности составляющих его работ. Можно выделить несколько видов путей: x полные пути – это пути, ведущие от исходного события к завершающему, таких путей может быть несколько; x предшествующие пути – ведут от исходного события к рассматриваемому событию; x последующие пути – ведут от конечного события данной работы к завершающему событию; 107 x критический путь – это полный путь, имеющий наибольшую продолжительность из всех полных путей; продолжительность такого пути определяет продолжительность всего комплекса работ. На сетевом графике может быть несколько критических путей. Работы, составляющие критический путь, называются критическими. Длиной критического пути является общая наибольшая продолжительность выполнения всего комплекса намеченных работ, поэтому критический путь служит основой оптимизации сетевого графика. Резервы - промежуток времени, на который можно задержать начало работы или увеличить ее длительность без изменения срока завершения проекта (общий или полный резерв) или без изменения раннего начала последующих работ (частный или свободный резерв). Каждый полный путь, кроме критического и каждая работа, лежащая на полном пути кроме критического, имеют резерв ресурса. За счет резервов времени производится оптимизация сетевого графика, заключающаяся в сокращении продолжительности работ, лежащих на критическом пути, в совершенствовании методов их выполнения; в перераспределении ресурсов работ лежащих на некритическом и критическом путях; в привлечении дополнительных ресурсов для ускорения работ на критическом пути. Правила построения сетевой модели проекта Построение сетевого графика заключается в правильном соединении между собой работ-стрелок с помощью событий-кружков. Пример сетевого графика приведен на рис. 3. 2 d 4 2 а 2 1 c 1 5 f b 3 e g 4 6 5 3 Рис. 1. Пример сетевого графика. При этом правильность соединения стрелок заключается в следующем: x график должен иметь только одно начальное событие (событие 1) и только одно конечное событие (событие 6); 108 x каждая работа в сетевом графике должна выходить из события, которое означает окончание всех работ, результат которых необходим для ее начала (работа g может начаться только после окончания работ e и f); x событие, означающее начало определенной работы не должно включать в себя результаты работ, завершение которых не требуется для начала этой работы; x график строится слева направо, и каждое событие с большим порядковым номером должно быть расположено правее предыдущего; x стрелки, изображающие работы, должны располагаться слева направо; x для изображения параллельных работ вводятся фиктивные работы (работа с); x в сети не должно быть «тупиков»: b 2 4 c а 1 e 5 6 d 3 Рис. 2. Пример сетевого графика с "тупиками".  событий, из которых не выходит ни одна работа, если это событие не является завершающим (событие 4 на рис. 4);  событий, в которые не входит ни одна работа, если это событие не начальное (событие 3 на рис. 4); x в сети не должно быть замкнутых контуров, состоящих из взаимосвязанных работ, создающих замкнутую цепь (работы d, e, c на рис. 5). 2 d а 1 c e b 5 f 3 Рис. 3. Пример сетевого графика с замкнутым контуром. 109 6 Расчет параметров сетевого графика Основными параметрами сетевого планирования и управления являются: x календарное планирование работ проекта (ранние и поздние даты начала и окончания работ проекта); x расчет критического пути; x вычисление резервов времени работ. Такие же параметры могут рассчитываться для событий: ранний и поздний срок свершения события, резерв времени события. Располагая данными о продолжительности работ, включенных в график можно определить остальные параметры. Расчеты ведут в следующем порядке: 1. Определяют ранние сроки начала t р .н и окончания t р .к работ. Ранние сроки соответствуют наиболее ранним из возможных сроков начала и окончания работ; Ранние сроки начала и окончания работ определяют для каждой работы в отдельности последовательным переходом от более ранних событий к более поздним, т.е. слева направо. Сроки начала и окончания работ следует определять совместно. Раннее окончание работы равно раннему ее началу плюс продолжительность самой работы t : t р .о . t р .н.  t . Ранние сроки начала работ, выходящих из события 1, равны нулю. Следовательно, ранние сроки окончания этих работ будут равны продолжительности: t р .о . 0t . Раннее начало последующей работы равно раннему окончанию данной работы. Если данной работе предшествует несколько работ, то раннее начало равно максимальному значению из всех ранних окончаний предшествующих работ: t р . н. t max р.о. 2. Рассчитывают продолжительность критического пути на основе ранних сроков начала и окончания работ. t t 3. Устанавливают поздние сроки начала п.н. и окончания п.к работ, входящих в график. Поздними считаются также допустимые сроки, позднее которых работа не может начаться или окончиться (в противном случае появляется угроза срыва графика выполнения намеченных работ). 4. Вычисляют резервы времени для всех некритических путей и работ. 110 Параметры сетевого графика рассчитываются разными методами. Наиболее простым и наглядным методом расчета параметров является графический метод. Рассмотрим этот метод на примере проекта, исходные данные для которого описаны в таблице 1, а модель приведена на рис. 6. Таблица 1 Характеристика работ сетевого графика Рассматриваемая работа A B C D E F G Предшествующая работа A B,C C E E Длительность работы 3 2 6 4 2 1 3 Рис. 4. Модель сетевого графике проекта. В случае расчета графика на модели кружок, обозначаемый событие сетевого графика, разбивается на четыре сектора и в них показывается следующая информация: Окончательные результаты расчета сетевого графика методом критического пути приведены на рис. 7. Критический путь проходит по работам С, Е и G и составляет 11 дней. При этом работа А не имеет частного (свободного) резерва времени, ее задержка приведет к срыву сроков начала последующей работы В. 111 Рис. 5. Сетевой график с результатами расчета. Аналитический способ проведения расчетов: t ip – ранний срок свершения событий равен сумме продолжительности всех работ, лежащих на наиболее длинном пути, который ведет к этому событию от исходного события; t iп – поздний срок свершения события, самый поздний срок наступления данного события, при котором не происходит задержки раннего срока свершения событие, завершающего сетевой график; Ri – резерв времени события, т.е. интервал времени между поздним и ранним сроками свершения события. Чем больше напряженность выполнения данной работы. Ri Ri тем меньше tiп  tiр . t ijp.н – ранний срок начала работы; t ijp.о – ранний срок окончания работы; t ijп.н. – поздний срок начала работы, не приводящий к задержке раннего срока свершения завершающего события; Rijп – полный резерв времени работы, на которое можно увеличить продолжительность критического пути: Rijп данной работы, tijп.н  tijр.н или Rijп tijп.о  tijр.о ; 112 не изменив продолжительности Rijс – свободный резерв времени работы, т.е. максимальное время, на которое можно увеличить продолжительность данной работы или перенести срок ее начала, не изменив при этом раннего срока начала периода следующих работ. Ранний срок свершения события. tip max( tip  tij ) t1p t 0p  t 01 . Ранний срок свершения начального события принимаем равным нулю. 0  1 1. 113