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

Новикова Наталья Владимировна Исследование операций Конспект лекций Минск, 2010 1 1 2 Литература ............................................................................................................................3 Основные понятия исследования операций (ИСО). Классификация задач ...................4 2.1 Классификация задач ИСО.............................................................................................5 2.2 Многокритериальные задачи .........................................................................................6 3 Основы линейного программирования..............................................................................8 3.1 Примеры задач ЛП. .........................................................................................................8 3.2 Графический метод решения задач ЛП.......................................................................10 3.3 Возможные варианты решения задач ЛП ...................................................................12 3.4 Эквивалентные постановки задач ЛП .........................................................................12 3.5 Симплекс-метод.............................................................................................................13 3.6 Элементы теории двойственности...............................................................................20 3.7 Транспортная задача (ТЗ) ЛП.......................................................................................24 3.8 Задача о назначениях ....................................................................................................30 4 Основы теории графов.......................................................................................................34 4.1 Основные понятия.........................................................................................................34 4.2 Построение эйлерова цикла .........................................................................................34 4.3 Остовное дерево (остов) минимального веса .............................................................35 4.4 Кратчайшие пути...........................................................................................................37 5 Сетевое планирование и управление проектами ............................................................41 2 1 Литература Основная: 1. Исследование операций. Теория игр: Учеб.пособие/ Л.С. Костевич, А.А. Лапко. — Мн.: Выш. шк., 2008. 2. Волков И.K., Загоруйко Е.А. Исследование операций: учебное пособие для вузов. 2-е изд. / Под ред. B.C. Зарубина, A.П. Крищенко. – М. Изд-во MГТУ им. Н.Э. Баумана. 2002. – 436 с. 3. M.M. Ковалев, M.M. Писарук. Современное линейное программирование. - Минск, Издательский центр Белгосуниверситета, 1998. - 260 с. 4. Высшая математика: Математическое программирование.: Учеб.пособие/ А.В. Кузнецов, В.А. Сакович, Н.И. Холод; Под общ. ред. А.В. Кузнецова. — Мн.: Выш. шк., 2001. Дополнительная: 5. Вентцель Е.С. Исследование операций. – М.. Советское радио, 1972. - 552 с. 6. Вентцель Е.С. Исследование операций. – М., Знание. 1976. 7. Вентцель Е.С. Исследование операций. Задачи, принципы, методология. – М., Наука, 1988. 8. Математическое программирование:Информационные технологии оптимальных решений: Учеб.пособие/ Л.С. Костевич. — Мн.: Новое знание., 2003. 3 2 Основные понятия исследования операций (ИСО). Классификация задач Исследование операций – это комплексная математическая дисциплина, занимающаяся построением, анализом и применением математических моделей принятия оптимальных решений при проведении операций. Операция – система управляемых действий, объединенная единым замыслом и направленная на достижение определенной цели. Примеры операций. Пример 1. Предприятие выпускает несколько видов изделий, при изготовлении которых используются ограниченные ресурсы различного типа. Требуется составить план выпуска изделий на месяц, т.е. указать количество выпускаемых изделий каждою вида, так, чтобы максимизировать прибыль при выполнении ограничений на потребляемые ресурсы. Пример 2. Требуется создать сеть временных торговых точек так, чтобы обеспечивать максимальную эффективность продаж. Для этого требуется определить - число точек, - их размещение, - количество персонала и их зарплату, - цены на товары. Пример 3. Требуется организовать строительство магазина. При этом необходимо указать порядок выполнения работ во времени и распределить требуемые ресурсы между работами так, чтобы завершить строительство вовремя и минимизировать его стоимость. Набор управляющих параметров (переменных) при проведении операции называется решением. Решение называется допустимым, если оно удовлетворяет набору определенных условий. Решение называется оптимальным, если оно допустимо и, по определенным признакам, предпочтительнее других, или, по крайней мере, не хуже. Признак предпочтения называется критерием оптимальности. Критерий оптимальности включает в себя целевую функцию и направление оптимизации или набор целевых функций и соответствующих направлений оптимизации. Целевая функция – это количественный показатель предпочтительности или эффективности решений. Направление оптимизации – это максимум (минимум), если наиболее предпочтительным является наибольшее (наименьшее) значение целевой функции. Например, критерием может быть максимизация прибыли либо минимизация расходов. Математическая модель задачи ИСО включает в себя: 1) описание переменных, которые необходимо найти, 2) описание критериев оптимальности, 3) описание множества допустимых решений (ограничений, накладываемых на переменные). Цель ИСО количественно и качественно обосновать принимаемое решение. Окончательное решение принимает ответственное лицо (либо группа лиц), называемое лицо, принимающее решение (ЛПР). Математическая модель задачи ИСО составляется в соответствии с представлениями ЛПР об этой задаче, т.e. в соответствии с его информационным состоянием. При этом важно, чтобы математическая модель задачи была наиболее адекватной, т.e. наиболее правильно отражала информационное состояние ЛПР. Для этого разработчик математической модели должен работать в тесном контакте с ЛПР. Основной принцип разработчика: "Разрабатывай не то, что заказчик просит, а то, что ему нужно." (М. Гэри и Д. Джонсон "Вычислительные машины и труднорешаемые задачи") 4 Проверка адекватности представлений ЛРП о задаче не является предметом ИСО. Изменение информационного состояния ЛРП может привести к изменению математической модели задачи. 2.1 Классификация задач ИСО Классификация по зависимости параметров задачи от времени. 1. Статическая задача. Принятие решения происходит при условии, что все параметры задачи заранее известны и не изменяются но времени. Процедура принятия решения осуществляется один раз. 2. Динамическая задача. В процессе принятия решения параметры задачи изменяются по времени. Процедура принятия решения осуществляется поэтапно и может быть представлена и виде процесса, зависящего от времени, в том числе непрерывно. Пример – навигационная задача. Классификация в зависимости от достоверности информации о задаче. 1. Детерминированная задача. Все параметры задачи заранее известны. Для решения детерминированных задач в основном применяются методы математического программирования. 2. Недетерминированная задача. Не все параметры задачи заранее известны. Например, необходимо принять решение об управлении устройством, некоторые узлы которого могут непредсказуемо выходить из строя. Оптимальное решение недетерминированной задачи ИСО отыскать практически невозможно. Однако некоторое "разумное" решение отыскать можно. «Исследование операций представляет собой искусство давать плохие ответы па те практические вопросы, на которые даются еще худшие ответы, другими методами». (Т.Л. Саати) 2,а). Стохастическая задача. Не все параметры задачи заранее известны, но имеются статистические данные о неизвестных параметрах (вероятности, функции распределения, математические ожидания и т.д.). Для отыскания оптимального решения стохастической задачи применяется один и из следующих приемов:  искусственное сведение к детерминированной задаче (неизвестные параметры заменяются их средними значениями).  "оптимизация в среднем" (вводится и оптимизируется некоторый статистический критерий). 2,б). Задача в условиях (полной) неопределенности. Статистические данные о неизвестных параметрах отсутствуют. Задачи ИСО в условиях неопределенности в основном изучаются в рамках теории игр. Классификация по виду критерия оптимальности. Критерий оптимальности может иметь любой вид, в том числе неформализуемый. Наиболее распространенные формализуемые критерии оптимальности заключаются в оптимизации (минимизации либо максимизации) одной либо нескольких скалярных целевых функций. Функция называется скалярной, если ее значением является некоторое число. Задача оптимизации скалярной функции на заданном множестве допустимых числовых решений называется задачей математического программирования. Наиболее изученными представителями однокритериальных задач математического программирования, т.е. задач с одной целевой функцией, являются следующие задачи. Задачи линейного программирования. Целевая функция линейная, множество допустимых решений – выпуклый многогранник. 5 Задачи квадратичного программирования. Целевая – функция квадратичная n n  c x x i 1 j 1 ij i j , а множество допустимых решений – выпуклый многогранник. Задачи стохастического программирования. Это задачи линейного программирования с неизвестными числовыми параметрами, о которых имеются статистические данные. Задачи дискретного программирования. Множество допустимых решений – дискретное множество. Задачи целочисленного программирования. Множество допустимых решений – точки целочисленной решетки. Задачи булева программирования. Множество допустимых решений – 0-1 матрицы. 2.2 Многокритериальные задачи И задачах ИСО, как правило, присутствует не один, а несколько признаков предпочтения (критериев). Такие задачи называются многокритериальными. Критерии могут оказаться противоречивыми, т.e. решение, лучшее по определенному признаку, может оказаться худшим по другому признаку. Например, минимизация стоимости и максимизации качества товара почти всегда противоречивы. В этом случае задача отыскания решения, предпочтительного по всем признакам, будет некорректной, т.e. не будет иметь ни одного решении. В случае противоречивых критериев ИСО предлагает следующие подходы к отысканию подходящего решения. 1) Замена некоторых критериев ограничениями вида  или  . Например, минимизация стоимости f  x   min может быть заменена ограничением вида f x   A , где А – некоторая верхняя оценка стоимости, т.е. максимально допустимая стоимость. 2) Свертка критериев. Создается один глобальный скалярный критерий, целевая функция которого является некоторой функцией от исходных целевых функций. Наиболее употребимыми являются линейные свертки вида  f x    g x  (в случае двух критериев). Нетривиальной является задача отыскания адекватных значений коэффициентов  и  , отражающих относительную важность целевых функций f  x  и g x  . 3) Ранжирование критериев. Критерии ранжируются по степени важности. 4) Отыскание решений, лучших хотя бы по одному критерию. Подходы 1) и 2) приводят к однокритериальной задаче. Подход 3) приводит к задаче с упорядоченными критериями. Подход 4) приводит к задаче с независимыми критериями. В задаче с упорядоченными критериями критерии упорядочиваются по важности и требуется найти оптимальное решение для наименее важного критерия на множестве решений, оптимальных для более важного критерия (см. рисунок). 6 Самое большое – множество всех допустимых решений, в него вложено множество решений, оптимальных по самому важному критерию, далее вложено множество оптимальных решений по второму по важности критерию, и т.д. В задаче с независимыми критериями требуется найти множество недоминируемых (эффективных) решений. Недоминируемое решение лучше любого другого допустимого решения хотя бы по одному критерию либо не хуже по веем критериям. Множество недоминируемых решений также называется множеством Парето. Пример многокритериальной задачи с независимыми критериями. Фирма по разработке программного обеспечения должна выполнить проекты 1 и 2 в последовательности 1, 2. Для выполнения каждого проекта можно привлечь одного, двух или трех исполнителей. Пусть x1 и x2 – число исполнителей для выполнения проектов 1 и 2 соответственно. Время выполнения проекта i равно ti  xi  месяцев, а соответствующая стоимость – ci  xi  млн. рублей. Требуется минимизировать общее время выполнения проектов при минимальной стоимости. Значения функций заданы следующим образом: X 1 2 3 2 1 1 t1 x  3 1 1 t2  x  1 2 3 c1  x  4 4 5 c2  x  Общее время выполнения проектов равно F1 x1 , x2   T x1 , x2   t1 x1   t2 x2  , а стоимость F2 x1 , x2   C x1 , x2   c1 x1   c2 x2  . Определим все возможные значения пар F1 , F2   F1 x1 , x2 , F2 x1 , x2  , см. таблицу и рис. (1,2) (1,3) (2,1) (2,2) (2,3) (3,1) (3,2) (3,3) x1 , x2  (1,1) 5 3 3 4 2 2 4 2 2 F1 5 5 6 6 6 7 7 7 8 F2 Задача отыскания множества Парето в случае двух критериев вида F1 x   min и F2  x   min может быть решена графически следующим образом. Находим все точки с наименьшим значением F1 x  . Если их несколько, выбираем из них точку с наименьшим значением F2  x  . Включаем ее в множество Парето. Отсекаем точки с большими либо равными значениями F1 x  и F2  x  (северо-восточный угол с вершиной в выбранной точке). Повторяем процедуру для оставшейся части допустимой области. Из рисунка видно, что для нас представляют интерес пары F1 , F2   {(2,6), (3,5)} и соответствующие решения x1 , x2   {(2,2), (1,2)}, которые являются недоминируемыми и образуют множество Парето для рассматриваемой задачи. 7 3 Основы линейного программирования Задачи линейного программирования (ЛП) и методы их решения широко используются в промышленном производстве, экономике, логистике, военном деле и других областях целенаправленной деятельности человека. 3.1 Примеры задач ЛП. Макроэкономические линейные модели Основой большинства макроэкономических моделей является модель межотраслевого баланса, разработанная и изученная американским ученым Василием Леонтьевым в 1920-х годах. Модель получила название автора, а сам автор получил за ее разработку Нобелевскую премию в области экономики. Модель Леонтьева. Предположим, что весь производственный сектор страны (или любой другой крупной экономической системы) разделен на n отраслей. Предполагается, что каждая отрасль выпускает однородную продукцию (продукцию одного типа), но разные отрасли выпускают разную продукцию. Таким образом, в целом выпускается n типов продукции. В процессе производства каждая отрасль использует продукцию других отраслей и, в свою очередь, снабжает другие отрасли своей продукцией. Кроме того, каждая отрасль выпускает продукцию, которая потребляется в непроизводственной сфере. Допустим, что для отрасли i известно, что aij единиц продукции этой отрасли используется для производства единицы (!) продукции отрасли j и ci единиц продукции этой отрасли используется в непроизводственной сфере (накопление, потребление). Величина ci также называется внешним спросом. Требуется определить x j – валовый объем (количество единиц) продукции отрасли i , i  1,..., n , так, чтобы выполнялось условие межотраслевого баланса: n a x j 1 ij j  ci  xi , xi  0, i  1,..., n или в матричной форме x  Ax  c, x  0 . Приведенные соотношения называются моделью Леонтьева. Соотношение x  Ax  c можно ослабить: x  Ax  c (в этом случае c определяет нижнюю границу внешнего спроса). С моделью Леонтьева связаны некоторые задачи оптимизации. 1) Задача максимизации суммарного валового выпуска при ограниченных трудовых ресурсах. Пусть для выпуска единицы продукции отрасли j требуется t j единиц трудовых ресурсов. Пусть Т – общее количество трудовых ресурсов, имеющееся в наличии. Тогда модель задачи максимизации суммарного валового выпуска при ограниченных трудовых ресурсах состоит в следующем: n x j 1 j  max  x  Ax  c n   t j x j  T  j 1  x  0 2) Задача минимизации требуемых трудовых ресурсов при заданном уровне суммарного валового выпуска: 8 n t x j 1 j  max j  x  Ax  c , n   x j  V  j 1  x  0 где V – заданный уровень суммарного валового выпуска. Микроэкономические линейные модели Модель оптимальной производственной программы предприятия. Предприятие выпускает n видов продукции. Для выпуска единицы продукции вида j требуется единиц ресурса i , который имеется в объеме bi , i  1,..., m (всего имеется m видов ресурсов). Выпуск единицы продукции вида j приносит прибыль в объеме p j . Требуется определить программу выпуска продукции x   x1 ,..., xn  , где x j – количество выпускаемой продукции вида j , такую, что выполнены ограничения на ресурсы и суммарная прибыль максимальна. Соответствующая задача ЛП имеет вид: n p x j j 1 j  max n  aij x j  bi i  1,..., m  j 1  x  0 j  1,..., n  j Модель распределения ресурсов. Имеется n видов деятельности и m видов ресурсов. Ресурс i имеется в объеме bi , i  1,..., m . С помощью единицы i -го ресурса можно выполнить d ij -ю часть j -ro вида деятельности и при этом затраты будут составлять cij . Введем переменные xij , показывающие какое количество ресурса i направлено для вида деятельности j . Задача состоит в следующем. m n  d c i 1 j 1 ij ij  min m  d ij xij  1 j  1,..., n  i 1 n  xij  bi i  1,..., m  j 1  x  0 i  1,..., m, j  1,..., n  ij  Модель оптимальной купли-продажи валюты. Рассмотрим ситуацию, когда брокер осуществляет куплю-продажу валюты с целью получения прибыли за счет разницы в курсах валют. Пусть n – количество доступных валютных рынков, m – количество операции купли-продажи. Обозначим через rij количество денежных единиц i -го валютного рынка, которые можно купить ( rij  0 ) либо продать ( rij  0 ) в результате операции j стандартного объема. Например, при проведении операции 2 стандартного объема, продавая 2 евро, можно купить 1 доллар и 5000 бел.рублей. Пусть x j – объем 9 операции j . В этом случае соответствующие величины rij умножаются на x j Например, для операции 2, продавая 2x2 евро, можно купить x2 долларов и 5000x2 бел.рублей. Рассмотрим идеальную ситуацию, когда все операции выполняются одновременно. Ограничение состоит в том, что количество проданных денежных единиц не должно превосходить количества купленных для каждого вида валюты. Задача состоит в отыскании таких объемов операций, что количество денежных единиц по одному из типов валют, например, первом, максимально. Соответствующая математическая модель выглядит следующим образом. n r j 1 1j x j  max n  rij x j  0 i  1,..., m  j 1  x  0 j  1,..., n  j 3.2 Графический метод решения задач ЛП Применяется, когда число переменных равно 2. Пусть дана задача z  c1 x1  c2 x2  max a11 x1  a12 x2  b1 a x  a x  b 22 2 2  21 1 (1) ....................... a x  a x  b m2 2 m  m1 1  x1  0 x2  0 Дадим геометрическую интерпретацию элементов этой задачи. Каждое из ограничений задачи задает на плоскости x1 0x2 некоторую полуплоскость. Пересечение всех этих полуплоскостей образует область допустимых решений задачи (1). Перейдем к геометрической интерпретации целевой функции. Для любого произвольного значения z  z0 целевая функция принимает вид c1 x1  c2 x2  z0 . Это уравнение прямой линии. Изменяя z0 получим целое семейство параллельных прямых, называемых линиями уровня целевой функции. Вектор c  c1 ,c2  называется градиентом функции. Он показывает направление наискорейшего возрастания целевой функции. Вектор  c указывает направление наискорейшего убывания целевой функции. Его называют антиградиентом. Из геометрической интерпретации элементов ЗЛП следует порядок ее графического решения. 1. С учетом системы ограничений строим область допустимых решений  . 2. Строим вектор c  c1 ,c2  наискорейшего возрастания целевой функции – вектор градиентного направления. 3. Проводим произвольную линию уровня z  z0 (проще всего провести линию z  0 , перпендикулярную к вектору c ). 4. При решении задачи на максимум перемещаем линию уровня z  z0 в направлении вектора c так, чтобы она касалась области допустимых решений в ее 10 крайнем положении (крайней точке). В случае решения задачи на минимум линию уровня z  z0 перемещаем в антиградиентном направлении.   5. Определяем оптимальный план x*  x1* , x2* и экстремальное значение целевой функции z *  z x* . Пример. Компания производит погрузчики и тележки. От одного погрузчика компания получает доход в размере $80 и от одной тележки в размере $40. Имеется три обрабатывающих центра, на которых выполняются операции металлообработки, сварки и сборки, необходимые для производства любого из продуктов. Для интервала планирования, равного месяцу, задана предельная производственная мощность каждого обрабатывающего центра в часах, а также количество часов, необходимое на этом центре для производства одного погрузчика и одной тележки. Эта информация задана в таблице.   Изделие Погрузчик Тележка Общая мощность Центр (часы на ед.) (часы на ед.) (часы) Мет.обработка 6 4 2400 Сварка 2 3 1500 Сборка 9 3 2700 Требуется составить допустимый план работ на месяц с максимальным доходом. Математическая модель задачи может быть записана следующим образом. z  80 x1  40 x2  max 6 x1  4 x2  2400 2 x  3 x  1500  1 2  9 x  3 x 2  2700  1  x1  0 x2  0 где x1 и x2 - количества производимых погрузчиков и тележек соответственно. Представим ограничения в виде следующего графика, где по осям ( 0x1 ) и ( 0x2 ) откладывается количество произведенных погрузчиков и тележек соответственно, а линии представляют ограничения па производственные мощности. Допустимая область задачи представлена в виде многоугольника. Представим целевую функцию 80 x1  40 x2  z с переменным значением z прерывистой линией. Любая точка x  x1 , x2 на линии 80 x1  40 x2  z соответствует доходу в размере z . Перемещая ее параллельно себе самой, получаем разные значения дохода.   11 При x1  0 значение 40 x2  z . Следовательно, значение z увеличивается при увеличении x2 , т.е. при перемещении целевой функции вверх. При этом линия 80 x1  40 x2  z не должна покинуть допустимую область. Нетрудно заметить, что максимальный доход среди допустимых точек достигается в одной из вершин многоугольника ограничений. В данном случае в точке пересечения линий, соответствующих ограничениям на металлообработку и сборку, x1*  200 , x2*  300 . Для определения точки, соответствующей оптимальному решению, нужно сравнить углы наклона прямых, соответствующих целевой функции и ограничению. 3.3 Возможные варианты решения задач ЛП 1. ЗЛП имеет единственное решение 2. Не существует допустимого решения ЗЛП 3. ЗЛП имеет бесконечно много оптимальных решений, которые называются альтернативными 4. Целевая функция ЗЛП неограничена (в допустимой области). 3.4 Эквивалентные постановки задач ЛП Общая постановка: n z   c j x j  maxmin  j 1 n  aij x j  bi , i  I1  j 1 n  aij x j  bi , i  I 2  j 1 n  a x  b ,i  I ij j i 3  j 1   x j  0, j  N1  x j  R , j  N2  x j  0, j  N 3  где c j , aij , bi – заданные числовые параметры, множества I1 , I 2 и I 3 попарно не пересекаются, I1  I 2  I 3  1,..., m, R – множество действительных чисел, множества N1 , N 2 и N 3 попарно не пересекаются, и N1  N 2  N 3  1,..., n . Канонической формой записи ЗЛП называют задачу n z   c j x j  max j 1   aij x j  bi , i  1,..., m  j 1  x  0, j  1,..., n  j n Существует несколько эквивалентных постановок задач ЛП:  Задачи максимизации и минимизации. Для перехода от одной задачи к другой коэффициенты целевой функции можно умножить на -1. 12  Задачи с ограничениями типа "=", "  " и "  ". Для перехода от ограничения "  " к ограничению "=" можно ввести в левую часть ограничения дополнительную неотрицательную переменную с коэффициентом +1. В целевую функцию эта переменная войдет с коэффициентом 0. Для перехода от ограничения "  " к ограничению "  " и наоборот достаточно домножить соответствующее ограничение на -1. Ограничение типа "=" может быть представлено в виде двух ограничений "  " и "  " с той же левой и правой частью. Для перехода от ограничений типа "=" к ограничениям типа "  " можно применить метод Гаусса. Например, рассмотрим задачу  x1  x2  x5  min  x1  x2  1  x  2 x  3  2 3   x3  x4  x5  1 x j  0  При помощи ограничений. 1 1 0 0 1 2 0 0 0 1 1 метода Гаусса выделяем единичную подматрицу в матрице 0 1 1 0 2 0 0 4 1 0 0 2 2 2 0  3  0 1  2 0 0  3  0 1 0  2 2 1 1 1 0 0 1 1 1 1 0 0 1 1 1 1  x1  2 x4  2 x5  2  x1  2  2 x4  2 x5   0    x2  2 x4  2 x5  1   x2  1   2 x4  2 x5   0 x  x  x  1  x  1   x  x   0 4 5 4 5  3  3 Эквивалентная задача  2  2 x4  2 x5    1  2 x4  2 x5   x5  2  2 x4  2 x5  1  2 x4  2 x5  x5   3  4 x4  3 x5  min 2  2 x4  2 x5   0  2 x4  2 x5   2 2 x4  2 x5  2  1   2 x  2 x   0   2 x  2 x   1  2 x  2 x  1    4 5 4 5 4 5    1   x4  x5   0   x4  x5   1  x4  x5  1  x4 , x5  0  x4 , x5  0  x4 , x5  0 Переменная x j  R может быть представлена в виде двух новых неотрицательных переменных: x j  x j  x j , x j  0 , x j  0 . 3.5 Симплекс-метод Симплекс-метод является методом решения задач ЛП. Он впервые использовался лауреатом Нобелевской премии в области экономики советским ученым Леонидом Канторовичем в 1939 г. и описан в том виде, в котором существует сейчас, Данцигом в 1947 г. Описание метода проведем для задачи ЛП в канонической форме: 13 n z   c j x j  max j 1   aij x j  xn  i  bi , bi  0  j 1  x  0, j  1,..., n  j n i  1,..., m Симплекс-метод осуществляет направленный перебор допустимых базисных решений, в которых базисные переменные неотрицательны, а небазисные равны нулю. Этот процесс соответствует переходу от одной угловой точки многогранника ограничений к другой в направлении неуменьшения значения целевой функции. Рассмотрим следующий пример. Пример 1. Для изготовления двух видов продукции П1 и П2 используются четыре вида ресурсов Р1, Р2, Р3, Р4. Запасы ресурсов, число единиц ресурсов, затрачиваемых на изготовление единицы продукции, приведены в таблице 1. Таблица 1. Числовые данные для задания 1 Число единиц ресурсов, затрачиваемых на Вид ресурса Запас ресурса изготовление единицы продукции П1 П2 Р1 90 5 15 Р2 80 10 5 Р3 25 – 5 Р4 21 3 – Прибыль, получаемая от единицы продукции Р1, Р2 соответственно равна 2 и 3 ден. ед. Необходимо составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной. Составим экономико-математическую модель задачи. Обозначим x1 , x 2 — число единиц продукции П1 и П2, запланированных к производству. Для их изготовления потребуется 5 x1  15 x2 единиц ресурса Р1, 10 x1  5 x2 единиц ресурса Р2, 5x2 единиц ресурса Р3 и 3x1 единиц ресурса Р4. Так как потребление ресурсов Р1, Р2, Р3, Р4 не должно превышать их запасов, равных соответственно 90, 80, 25 и 21 единицам, то связь между потреблением ресурсов и их запасами выразится системой неравенств: 5 x1  15 x2  90 10 x  5 x  80  1 2  5 x2  25  3 x1  21 По смыслу задачи переменные x1  0, x 2  0. Суммарная прибыль F составит 2  x1 ден.ед. от реализации продукции П1 и 3  x 2 ден.ед. от реализации продукции П2, то есть z  2 x1  3x2 Итак, экономико-математическая модель задачи: 14 z  2 x1  3 x2  max 5 x1  15 x2  90 10 x  5 x  80 2  1 . 5 x  2  25 3 x  21  1  x1  0, x2  0 Приведем задачу к канонической форме записи, для этого введем дополнительные переменные x 3 , x 4 , x 5 , x 6 . Расширенная система задачи имеет вид:  90 5 x1  15 x2  x3 10 x  5 x  x  80  1 2 4  5 x2  x5  25  3 x1  x6  21 Условия неотрицательности примут вид: x1  0, x 2  0 x 3  0, x 4  0, x 5  0, x 6  0 . Целевую функцию прибыли представим в виде: z  2 x1  3 x2  0 x3  0 x4  0 x5  0 x6 . Экономический смысл дополнительных переменных состоит в том, что они выражают возможные остатки ресурсов, x 3 — остаток ресурса Р1, x 4 — остаток ресурса Р2 и т.д. Говорят, что ограничение ЗЛП имеет предпочтительный вид, если при неотрицательности правой части ( bi  0 ) левая часть ограничения содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограничения-равенства – с коэффициентом равным нулю. Если каждое ограничение-равенство ЗЛП в каноническом виде содержит переменную, входящую с коэффициентом, равным единице, а в остальные ограниченияравенства с коэффициентом равным нулю, то говорят, что система ограничений представлена в предпочтительном виде. В этом случае легко найти ее опорное (базисное) решение. Симплекс-метод. Шаг 0. Находим начальное допустимое базисное решение. Пусть задача линейного программирования представлена системой ограничений в каноническом виде: n z   c j x j  max j 1   aij x j  xn  i  bi , bi  0  j 1  x  0, j  1,..., n  j n i  1,..., m Приравнивая свободные переменные к нулю, получим начальный опорный план задачи. Т.е. x0  (0; 0; ...; 0; b1; b2 ; ...; bm )     n m Для примера: x0  (0; 0; 80; 90; 25; 21) 15 Любую задачу линейного программирования можно представить в эквивалентном предпочтительном виде: n z   c j x j  max(min) j 1 n  x   i   ij x j   i ,  i  0 j  m 1   x  0, j  1,..., n  j (1) i  1,..., m Выразим базисные переменные x1; x2 ; ...; xm из равенств (1) через свободные xm 1; xm  2 ; ...; xn и подставим их в целевую функцию. После группировки подобных членов получим z  c11  c2  2  ...  cm  m   c11, m 1  c2 2, m 1  ...  cm m , m 1   cm 1 xm 1   c11, m  2  c2 2, m  2  ...  cm m , m  2   cm  2 xm  2  ...  c11n  c2 2 n  ...  cm mn   cn xn Введем обозначения  0  c11  c2  2  ...  cm  m  cB A0  j  c11 j  c2 2 j  ...  cm mj   c j  cB A j  c j j  1,..., n , где cB  c1; c2 ;...; cm  – вектор коэффициентов целевой функции при базисных переменных; A0  1;  2 ;...;  m  – вектор-столбец свободных членов; A j  1 j ; 2 j ;...; mj  T T – вектор-столбец коэффициентов при переменных x j . Тогда задачу (1) можно переписать в следующем виде: z  0  n  x j  m 1 j j  max(min) n  x   i   ij x j   i ,  i  0 j  m 1   x  0, j  1,..., n  j (2) i  1,..., m где  0  cB A0 ;  j  cB A j  c j j  1,..., n . Задачу (2) записывают в таблицу, которая называется симплексной. Последнюю (m+1)-ю строку называют индексной строкой (строкой целевой функции), число  0  cB A0 – значение целевой функции для начального опорного плана x0 , т.е.  0  z  x0   cB A0 . Числа  j  cB A j  c j j  1,..., n называют оценками свободных переменных. Таблица 2. Симплексная таблица. БП … … … … xj A0 xi xm xm 1 xn x1 x2 x1 1 1 … … 1, m 1 … 1 j … 1n x2 2 1 … …  2 , m 1 … 2 j …  2n … xi … … … … … … 1 … … … … … … … … … … … xm … m … … … … … … … … 1 z 0 … … i  i , m 1 …  m , m 1 … …  m 1 …  ij …  in  mj … … …  mn j … n Теорема 1. Пусть исходная задача решается на максимум. Если для некоторого опорного плана все оценки  j  j  1,..., n  неотрицательны, то такой план оптимален. 16 Переход к нехудшему опорному плану. Шаг 1. Определяем вводимую переменную x j 0 – это небазисная переменная с наименьшим отрицательным коэффициентом в строке z . Столбец j0 называется разрешающим столбцом (ведущим). Если все коэффициенты в строке z неотрицательны, то построенное базисное решение оптимально. Если существует небазисная переменная с отрицательным коэффициентом в строке z , все коэффициенты которой в матрице ограничений неположительны (столбец в симплекс-таблице), то значение целевой функции неограничено (может быть бесконечно большим). Шаг 2. Определяем выводимую переменную xi 0 : это базисная переменная с наименьшим неотрицательным значением симплексного отношения     min  i   i 0    ij 0   i 0 j 0 Строка i0 называется ведущей или разрешающей строкой. Элемент  i 0 j 0 на пересечении ведущей строки и ведущего столбца называется ведущим. Шаг 3. Пересчитываем симплекс-таблицу, применяя метод Гаусса (получаем ведущий элемент равным 1 и остальные элементы в ведущем столбце равными 0): модифицированная разрешающая строка = разрешающая строка, деленная на ведущий элемент, (любая другая строка, включая строку z): модифицированная строка = (строка) - (ее коэффициент в разрешающем столбце) *(модифицированная разрешающая строка). Повторяем Шаг 1. Отметим, что выбор разрешающего столбца и разрешающей строки может быть неоднозначным. Пока будем считать, что в таком случае выбор произволен. Пример 2.(решение примера 1) Представим задачу в виде симплексной таблицы: Заполним первую симплексную таблицу (Табл. 2), в которой переменные x 3 , x 4 , x 5 , x 6 являются базисными, переменные x1 , x 2 свободными. Последняя строка заполняется коэффициентами целевой функции с противоположным знаком. Таблица 2. Первая (начальная) симплексная таблица Базис A0 x3 Переменные x1 x2 x3 x4 x5 x6 90 5 15 1 x4 80 10 5 1 x5 25 5 1 x6 21 3 –2 –3 1 F Проверяем критерий оптимальности. В последней строке имеются отрицательные коэффициенты. Выбираем наибольший по модулю (–3), он определит разрешающий столбец. Этот столбец в таблице выделен цветом и отмечен стрелкой. Переменная x 2 перейдет в базисные. Для положительных элементов столбца находим оценочные отношения и выбираем из них минимальное. 17  90 80 25  min ; ;   min 6;16;5  5 .  15 5 5  Третья строка является разрешающей. В таблице эта строка выделена. Переменная x 5 перейдет из базисных переменных в свободные. На пересечении разрешающих строки и столбца стоит разрешающий элемент 5. Построим новую симплексную таблицу по правилам: 1. Базисная переменная (в нашем случае — x 5 ) и свободная переменная (в нашем случае — x 2 ) меняются местами. 2. Элементы строки новой таблицы, соотсетствующей переменной, выведенной из базиса (в нашем случае — третьей), равны соответствующим элементам разрешающей строки «старой» таблицы, деленным на разрешающий элемент. 3. В столбцах, соответствующих базисным переменным, проставляем нули и единицы: 1 — против «своей» базисной переменной, 0 — против «чужой» базисной переменной. 0 — в последней строке для всех основных переменных. 4. Все остальные элементы новой таблицы вычисляем по «правилу прямоугольника». Получим вторую симплексную таблицу (Табл. 3). Таблица 3. Вторая симплексная таблица Базис A0 x3 Переменные x1 x2 x3 x4 x5 x6 15 5 1 -3 x4 55 10 1 -1 x2 5 1 1/5 x6 21 15 3 -2 3/5 1 F Критерий оптимальности вновь не выполнен. Теперь первый столбец является разрешающим. Переменная x1 перейдет в базисные.  15 55 21  min ; ;   min 3;5,5;7   3 .  5 10 3  Первая строка — разрешающая. 5 — разрешающий элемент. Новая симплексная таблица примет вид таблицы 4. Таблица 4. Третья симплексная таблица Переменные x1 x2 x3 x4 x5 x6 Оценочное отношение 3 1 1/5 -3/5 — x4 25 -2 1 5 25/5=5 x2 5 1 1/5 x6 12 -3/5 9/5 1 F 21 2/5 -3/5 Базис A0 x1 5/0,2=25 12/1,8= 6 2 3 И на этот раз критерий оптимальности не выполнен. Пятый столбец и вторая строка являются разрешающими. 5 —разрешающий элемент. Переходим к таблице 5. Таблица 5. Четвертая симплексная таблица 18 Базис A0 x1 Переменные x1 x2 x3 x4 x5 x6 6 1 -1/25 3/25 x5 5 - 2/5 1/5 1 x2 4 1 2/25 - 1/25 x6 3 3/25 - 9/25 1 F 24 4/25 3/25 В последней строке все элементы неотрицательные, критерий оптимальности выполнен. x*  (6; 2; 0; 0; 5; 3) Значит, максимальное значение целевой функции прибыли составит 24 ден. ед., если будет выпущено 6 ед. продукции первого вида и 4 ед. продукции второго вида. Так как x 3  x 4  0 (в последнее симплексной таблице они не вошли в базис), то первый и второй ресурс будут израсходованы полностью. Остаток ресурса Р 3 составит 5 ед. ( x5  5 ), остаток ресурса Р4 составит 3 ед. ( x 6  3 ). При решении задачи на минимум: Признак оптимальности: если все оценки в строке z неположительны, то такой план оптимален. Выбор разрешающего столбца: разрешающим является столбец с наибольшим положительным коэффициентом в строке z . М-метод. Иногда возникает проблема выбора начального допустимого базисного решения, например, когда единичная подматрица в матрице ограничений отсутствует. Тогда можно ввести искусственную переменную в каждое ограничение-равенство и положить ее коэффициент в целевой функции равным достаточно большому отрицательному числу -М. Такой метод получения начального допустимого базиса называется М-методом. Поскольку столбец, соответствующий искусственной переменной, не является единичным в исходной таблице М-метода (коэффициент в строке z равен М), до начала применения симплекс-метода исходную таблицу нужно преобразовать так, чтобы получить нули вместо значений М в строке z. Возможность зацикливания. В некоторых случаях симплекс-метод через несколько итераций может вернуться к ранее определенному базисному решению и далее возвращаться к нему бесконечное число раз. Эта ситуация, например, может возникнуть, когда в вершине многогранника ограничений пересекается более 2 прямых, т.е. когда некоторые ограничения являются несущественными. В этом случае некоторые базисные переменные равняются 0 и базис называется вырожденным. Для того, чтобы избежать зацикливания, при разработке математической модели желательно избегать излишних ограничений. Кроме того, зацикливания не будет, если применять следующее правило: в качестве разрешающего выбирать столбец с отрицательным коэффициентом (необязательно наименьшим!) с наименьшим номером в строке z. в качестве разрешающей выбирать строку с наименьшим неотрицательным значением отношения i с наименьшим номером.  ij 0 19 3.6 Элементы теории двойственности Для каждой задачи ЛП можно сформулировать двойственную ей задачу. Рассмотрим задачу максимизации с ограничениями «  » в матричной форме: f  x   cx  max  Ax  b  x  R T где c  c1; c2 ;...; cn  – вектор-строка, x  x1; x2 ;...; xn  – вектор-столбец, A  aij m n матрица размерности m  n , b  b1; b2 ;...; bm  – вектор-столбец. Введем в рассмотрение двойственную ей задачу: z  y   yb  min T  yA  c  y  0 где y   y1; y2 ;...; ym  – вектор-строка двойственных переменных или потенциалов. Пусть Ai обозначает строку i матрицы A , а A j столбец j этой же матрицы. Соответствие между компонентами прямой и двойственной задач представлено в следующей таблице. Прямая задача maxcx Двойственная задача minyb Ai x  bi , i  I1 yi  0, i  I1 Ai x  bi , i  I 2 yi  R, i  I 2 Ai x  bi , i  I 3 yi  0, i  I 3 x j  0, j  N1 yA j  c j , j  N1 x j  R , j  N2 yA j  c j , j  N 2 x j  0, j  N 3 yA j  c j , j  N 3 Теорема 1. (Теорема двойственности) Справедливо одно из следующих утверждений: а) обе задачи, прямая и двойственная ей, имеют допустимые решения и maxcx  minyb, б) если одна из задач, прямая и двойственная ей, не имеет допустимого решения а другая имеет, то целевая функция другой задачи не ограничена. в) обе задачи не имеют допустимых решений. Теорема 2 (О дополняющей нежесткости) Пусть x и y – допустимые решения прямой и двойственной задач соответственно. Тогда следующие условия а), б) и в) эквивалентны: x и y оптимальные решения прямой и двойственной задач, а) б) cx  yb , в) (условие дополняющей нежесткости) yi  Ai x  bi   0 i  1,..., m и yA j   c j x j  0 j  1,..., n . 20 Если оптимальное решение исходной задачи обращает какое-то i-е i  1,..., m ограничение в строгое равенство, то в оптимальном решении двойственной задачи переменная yi равна нулю. Если какая-то переменная x j  j  1,..., n  оптимального решения исходной задачи положительна, то j-е ограничение двойственной задачи ее оптимальным решением обращается в строгое равенство. Из этой теоремы, например, следует, что если решения прямой и двойственной задач допустимы и выполняется условие в) дополняющей нежесткости, то эти решения оптимальны. Экономический смысл двойственных переменных: Предположим, что некоторая организация может закупить все ресурсы, которыми располагает предприятие. Оценки yi* i  1,..., m  – оптимальные цены (оценки) на ресурсы исходя из естественного условия, что покупающая организация стремится минимизировать общую оценку ресурсов. В прикладных задачах двойственные оценки называют скрытыми или теневыми ценами. Двойственные оценки являются : 1. показателем дефицитности ресурсов и продукции. Величина yi* является * оценкой i-го ресурса. Чем больше значение оценки yi* , тем выше дефицитность ресурса. Для недефицитного ресурса yi*  0 . 2. показателем эффективности производства отдельных видов продукции с позиции критерия оптимальности. В оптимальный план может быть включена лишь та продукция j- го вида, для которой выполняется условие m a i 1 ij yi*  p j . 3. инструментом сопоставления суммарных условных затрат и результатов. Оптимальное решение прямой задачи может быть получено из оптимального решения двойственной задачи. Например, рассмотрим задачу Пример 3.(решение примера 1) Составить модель двойственной задачи для задачи 1. Для составления модели двойственной задачи сначала запишем матрицу исходной задачи  5 15 90    10 5 80   0 5 25     3 0 21  2 3 f  max   В результате транспонирования ее получаем расширенную матрицу двойственной задачи  5 10 0 3 2   15 5 5 0 3     90 80 25 21   min   По полученной матрице легко записать модель задачи, двойственной исходной min  = 90y1+ 80y2+ 25y3+ 21y4 21 5 y1  10 y2  3 y4  2  15 y1  5 y2  5 y3  3 y1  0, y2  0, y3  0, y4  0 Из теорем двойственности следует, что если решена одна из пары двойственных задач, то одновременно найдено решение и другой задачи. Компоненты оптимального плана этой задачи находятся в строке целевой функции последней симплексной таблицы решенной задачи. Преобразуем модель двойственной задачи. Преобразуем ограничения-неравенства в эквивалентные уравнения, вычитая из левых частей дополнительные неотрицательные переменные y5, y6, равные разностям между правыми и левыми частями этих неравенств. Тогда модель двойственной задачи запишется в виде: min  = 90y1+ 80y2+ 25y3+ 21y4 5 y1  10 y2  3 y4  y5  2  15 y1  5 y2  5 y3  y6  3 yj  0 j  1, 6 В этой записи переменные y5, y6 являются базисными, а переменные y1, y2, y3, y4 свободными. В исходной задаче переменные х1, и х2, являются свободными, а переменные х3, х4, х5 и х6 базисными. По правилу соответствия между переменными двойственных задач, получим: БП СП x3 x4 x5 x6 x1 x2 (4) y1 y2 y3 y4 y5 y6 СП БП Воспользуемся соответствием (4) следующим образом. Как видно, переменная у1 связана с переменной х3, а в последней симплексной таблице под х3 в f-строке находится элемент 4/25. Итак y1*=4/25. Далее у2 соответствует переменная х4, а в последней симплексной таблице под х4 в f-строке находится элемент 3/25 , y2*=3/25. Таким образом, оптимальный план задачи будет у*=(4/25; 3/25; 0; 0; 0; 0) Из теорем двойственности следует, что экстремальные значения целевых функций разрешимых двойственных задач совпадают, поэтому  min  f max  24 Оптимальный план х*(6; 4; 0; 0; 5; 3). При этом плане первые два ограничения выполняются как равенства. Именно поэтому в оптимальном плане у*=(4/25; 3/25; 0; 0; 0; 0) оценки y1*; y2* выражаются положительными числами, что свидетельствует о дефицитности этих ресурсов: они использованы полностью и все ограничения выполняются как равенства. Поскольку 4/25>3/25, то ресурс Р1 является наиболее дефицитным. Ресурс Р2является вторым по степени дефицитности. Последние ограничения выполняется как неравенство. Именно поэтому в оптимальном плане у*=(4/25; 3/25; 0; 0; 0; 0) оценки y3*=0 и y4*=0, что свидетельствует о недефицитности этого ресурса: Суммарные стоимостные оценки ресурсов: С1=а11 y1*+ а21 y2*+ а31 y3*+ а41 y4*= 5* 4/25+ 10* 3/25=2 С2=а12 y1*+ а22 y2*+ а32 y3*+ а42 y4*= 15* 4/25+ 5* 3/25=3 Так как стоимость реализации единицы продукции 1-го и 2-го видов составляет 2 и 3 ден.ед. соответственно, то выпуск продукции будет рентабельным. 22 Определим целесообразно ли включать в план изделие 3-го вида, на изготовление которого расходуется по 4 ед. каждого вида ресурсов и ценой 1 ед.? Вычислим стоимость ресурсов, затрачиваемых на производство единицы продукции 4-го вида: С3= а13 y1*+ а23 y2*+ а33 y3*+ а43 y4*= 5* 4/25+ 5* 3/25=35/25=1,4 Так как стоимость ресурсов, затрачиваемых на производство единицы продукции 3го вида составляет 1,4 ден.ед., а прибыль от реализации единицы продукции этого вида составляет 1 ден. ед., то можно сделать вывод, что производство продукции 3-го вида нецелесообразно. Пример 4. z  4 x1  3 x2  6 x3  x4  max  2 x1  x2  5 x3  2 x4  2   3 x1  x2  x3  x4  1  x  0, i  1,2,3,4  i Построим двойственную ей задачу   2 y1  y2  min  2 y1  3 y2  4  y  y  3 2  1 5 y1  y2  6 2 y  y  1 2  1  y1 , y2  0 Решим двойственную задачу графически 0;4 / 3  2;0  2 y1  3 y2  4  y1  y2  3 5 y1  y2  6 2 y1  y2  1 0;3 3;0 0;6  6 / 5;0 0;1  1 / 2;0  y1  y2  3  y  3  y1  y  3  y1  y  3  y1  2  2  2   5 y1  y2  6 5 y1   3  y1   6 5 y1  3  y1  6 4 y1  9 9 21  y  3     2 4 4  y   9  1 4 23 39  9 21  y *    ;   *   . Оптимальное решение определяется пересечением линий, 4  4 4 соответствующих ограничению 2 и 3 двойственной задачи. Эти ограничения выполняются как строгие равенства, а остальные - как нестрогие неравенства. Тогда по условию дополняющей нежесткости должно выполняться x1*  0 , x4*  0 , x2*  0 и x3*  0 МОГУТ быть найдены из равенств 3  x3      x  5 x  2  1  x  5 x  2  1  x  5 x  2 4 x  3  2    3  3 3 3 3 3 4       x2  x3  1  x2  1  x3  x2  1  x3  x2  1  x3 x  1  3  7  2 4 4  7 3  Получаем x*   0; ; ;0  .  4 4  3.7 Транспортная задача (ТЗ) ЛП Имеется m пунктов производства A1 , A2 ,..., Am в которых имеется запас однотипного товара в количестве a1 , a2 ,..., am соответственно. Кроме того, имеется n пунктов потребления B1 , B2 ,..., Bn , в которых имеются заявки на этот товар в количестве b1 , b2 ,..., bn соответственно. Предполагается, что выполнено условие баланса: m n i 1 j 1  ai   b j т.е. все, что произведено, должно быть получено (задача закрытого типа). Известна стоимость cij перевозки единицы товара из пункта отправления Ai в пункт потребления B j . Требуется составить такой план перевозок товара, при котором весь товар из пунктов производства вывезен, все заявки в пунктах потребления удовлетворены и суммарная стоимость перевозок минимальна. Условие баланса может не выполняться. (задача открытого типа). Если m n i 1 j 1  ai   b j (производится больше, чем потребляется), то вводим новый m n i 1 j 1 пункт потребления Bn 1 с заявкой bn 1   ai   b j . Полагаем ci , n 1  0, i  1,..., m . m Если же  a  b i 1 пункт n i j 1 j производства , (потребляется больше, чем производится), то вводим новый Am 1 с предложением n m j 1 i 1 am 1   b j   ai . Полагаем cm 1, j  0, j  1,..., n . В дальнейшем будем считать, что условие баланса выполнено. Математическая модель ТЗ состоит в следующем: xij – количество товара, перевозимого из Ai в B j . Задача ЛП: m n z   cij xij  min i 1 j 1 при ограничениях: на возможности поставщиков – весь продукт из пунктов производства должен быть вывезен: n x j 1 ij  ai ( i  1,..., m ) 24 на спрос потребителей, который должен быть удовлетворен: m x i 1 ij  bj ( j  1,..., n ) при условии неотрицательности переменных, исключающем обратные перевозки: xij  0 ( i  1,..., m j  1,..., n ) Отметим, что ранг системы ограничений ТЗ равен m  n  1 (на 1 меньше m  n за счет связующего условия баланса). Поэтому количество базисных переменных также равно m  n  1 . Исходные данные ТЗ удобно представлять в виде транспортной таблицы (ТТ), см. ниже. Таблица 1 Аi Вj В1 В2 … Вn Запасы ai c11 c12 c1n А1 … a1 х11 х12 х1n … … … … … … cm1 cm2 cmn Аm … am хm1 хm2 хmn Заявки bj b1 b2 … m n i 1 j 1  ai   b j bn Опорным планом ТЗ называется такое распределение объемов перевозок в ТЗ, что  это распределение является допустимым,  число базисных переменных равно m  n  1 , все остальные (свободные) переменные равны нулю. Отметим, что некоторые базисные переменные также могут равняться нулю,  не существует цикла, все вершины которого соответствуют базисным переменным. Циклом в ТЗ называется набор клеток, соединенных замкнутой ломаной линией, которая в точках излома совершает поворот на 90°. Метод потенциалов решения ТЗ. Основные этапы: Этап 1. Отыскание начального опорного плана. Этап 2. Проверка текущего опорного плана на оптимальность. Этап 3. Переход к лучшему опорному плану. Этап 1. Известны 2 основных метода отыскания начального опорного плана: метод северо-западного угла и метод минимальной стоимости. Рассмотрим метод минимального элемента 1. Выбирают клетку табл. ТЗ с минимальным значением cij, в которую записывают min (ai, bj). 2. Из запаса i-го поставщика и потребностей j-го потребителя вычитают эту величину. Из дальнейших рассмотрений исключают поставщика, запасы которого исчерпаны и потребителя, спрос которого полностью удовлетворен. 3. Повторяют шаг 1 до тех пор, пока все запасы продукции не будут исчерпаны. Поясним на примере. Аi В1 В2 Вn Вn Вn Запасы ai Вj А1 А2 10 14 8 6 4 5 22 7 6 12 8 6 9 48 5 30 26 25 8 А3 7 27 7 А4 18 27 7 27 8 20 4 20 8 5 Заявки bj 10 6 42 12 26 125 c =745 В базис ввели 7 < m  n  1 = 8 положительных переменных. Нужно ввести еще одну переменную, равную нулю, так, чтобы не образовался цикл. Например, x42 = 0. (Выбираем клетку с наименьшим тарифом). В методе северо-западного угла каждый раз определяется максимальный объем перевозок, соответствующий северо-западной допустимой клетке таблицы. При этом, если необходимо, полагаем xij  0 . Метод северо-западного угла отличается от метода минимального элемента тем, что клетки заполняют последовательно по строкам, начиная с элемента х11. Аi В1 В2 Вn Вn Вn Запасы ai Вj 10 А1 8 18 27 6 А2 Заявки bj 18 5 30 7 27 8 20 6 4 27 8 12 5 48 10 9 7 А4 6 7 9 8 30 8 6 7 А3 5 3 6 20 42 12 26 125 z  1039 Этап 2. Проверка на оптимальность. В методе потенциалов вводятся в рассмотрение двойственные переменные – потенциалы ui i  1,..., m (дополнительный столбец в матрице ТЗ) и v j j  1,..., n , (дополнительная строка в). Для клеток, соответствующих базисным переменным, должно выполняться ui  v j  cij Вначале один из потенциалов можно выбрать произвольно, например, u1  0 , остальные подсчитать по формуле ui  v j  cij – для клеток, соответствующих базисным переменным. Критерий оптимальности: если  ij  cij  ui  v j   0 для всех клеток ТТ, то построенный опорный план является оптимальным. В левый верхний угол каждой клетки ТТ, соответствующей небазисной переменной, запишем значение  ij . Аi А1 А2 Вj В1 В2 10 14 +2 Вn 22 + 12 8 6 4 +2 Вn 7 5 +7 8 6 +4 Запасы Потенциалы ui ai Вn 6 26 9 48 5 30 -4 26 А3 -3 А4 -2 8 + Заявки bj Потенциалы vj 7 27 - + 7 _+4 10 +1 8 -3 7 27 1 4 +1 6 8 20 -1 5 20 - 18 27 42 12 26 10 6 5 6 9 125 Этап 3. Переход к лучшему опорному плану Если существует  ij  0 , то переходим к лучшему опорному плану следующим образом. Иначе выбираем клетку с минимальным  ij  0 .Начиная с выбранной клетки матрицы перевозок, стоится замкнутый прямоугольный цикл с вершинами в заполненных клетках. Выбранной клетке присваивается знак "+", следующей вершине цикла знак "–", далее "+", "–", и т.д. по циклу. Данная цепочка знаков обязательно заканчивается знаком "–". Среди клеток цикла, отмеченных знаком "–", выбирается клетка с наименьшим значением переменной xij , затем из нагрузки клеток, отмеченных знаком "–", вычитаем это значение, а клетки, отмеченных знаком "+", прибавляем это значение. Получаем новый опорный план, который проверяют на оптимальность. Процесс повторяем до тех пор, пока условие оптимальности не будет выполнено Возможные типы циклов. – + – + – + + – + + – – + + Аi Вj А1 А2 А3 А4 Заявки bj Потенциалы – В1 – В2 +3 10 Вn +2 Вn 8 5 36 6 +2 7 Запасы Потенциалы ui ai Вn 6 +3 9 48 5 30 -1 12 +4 8 +1 6 4 26 8 14 7 _+4 10 +1 8 7 27 1 4 +1 6 +3 8 20 -1 27 1 7 5 14 18 7 6 27 6 42 5 12 6 26 6 125 27 vj Все  ij  0 . Следовательно, построенное решение оптимально. Пример 2. Исходные данные транспортной задачи приведены схематически: внутри прямоугольника заданы удельные транспортные затраты на перевозку единицы груза, слева указаны мощности поставщиков, а сверху – мощности потребителей. Сформулировать экономико-математическую модель исходной транспортной задачи, найти оптимальный план закрепления поставщиков за потребителями. 11 11 11 16 11 15 3 4 5 15 24 15 19 2 22 4 13 15 20 27 1 17 19 Решение. Запишем условие задачи в виде таблицы Аi A1 A2 A3 bj Bj B1 B2 3 х11 х21 х31 19 20 4 2 27 11 B3 х12 х22 х32 11 B4 5 х13 х23 х33 22 1 B5 15 х14 х24 х34 4 17 11 ai 24 х15 х25 х35 13 19 16 11 15 15 15 45 60 3 Суммарное количество произведенной заводами продукции a i 1 i =45 не совпадает 4 с потребностями потребителей b j 1 j =60. Модель задачи – открытая. В нашем случае небаланс составляет 60-45=15 ед. и вызван большей пропускной способностью потребителей, чем имеется у поставщиков. Вводим пятого фиктивного поставщика с наличием продукции 15 ед. и нулевыми тарифами на перевозку. Построим начальный опорный план методом минимального элемента. 60 60 A1=15 A2=15 A3=15 A4=15 3 B1=11 11 4 B2=11 5 B3=11 15 19 2 22 4 20 27 1 17 11 11 B4=16 4 4 4 4 24 B5=11 13 19 11 Наименьшим значением тарифов является число 0. Клетку (4,5) заполним количеством 11 ед., достаточным для удовлетворения потребностей потребителя В5. Клетки (1,5), (2,5) и (3,5) исключаем из рассмотрения. Заполним клетку (3,3) максимальным количеством груза 11 ед. Клетки (1,3), (2,3) и (4,3) исключаем из рассмотрения, так как так как потребитель В 3 полностью обеспечен продукцией. 28 В оставшиеся пустые клетки с наименьшим тарифом 2 можем поместить 11 ед. в клетку (2,2). Клетки (1,2), (3,2) и (4,2) исключаем из рассмотрения, так как потребитель В 2 полностью обеспечен продукцией. В клетку с наименьшим тарифом 3 можем поместить 11 ед. в клетку (1,1). Клетки (1,2), (1,3) и (1,4) исключаем из рассмотрения, так как потребитель В 1 полностью обеспечен продукцией. Клетку (2,4) заполним количеством 4 ед., достаточным для распределения продукции поставщика А2. В клетку (1,4) запишем 4 ед. – это недостающее количество продукции для распределения продукции поставщика А1. В клетку (3,4) запишем 4 ед. – это недостающее количество продукции для распределения продукции поставщика А3. В клетку (4,4) помещаем 4 ед.груза – количество, необходимое для распределения продукции поставщика А4 и удовлетворения потребностей потребителя В4. Загруженных клеток 8, равно числу 4+5-1. Следовательно, составленный план невырожденный и является начальным опорным планом. Транспортные расходы составят z= 3*11+2*11+1*11+15*4+4*4++17*4+0*4+0*11= 210 Выбираем u1  0 Определяем остальные потенциалы u2=-11 u3=2 u4=-15 v1=3 v2=13 v3=-1 v4=15 v5=15 Потенциалы записаны в таблице 60 B1=11 B2=11 B3=11 B4=16 B5=11 ui 60 3 4 5 15 24 A1=15 11 + - 4 19 2 22 4 A2=15 - 11 + 4 13 -11 20 27 1 17 A3=15 11 4 19 2 A4=15 4 0 11 -15 vj 3 13 -1 15 15 Определяем оценки sij свободных клеток: s12=4-(0+13) = -9 s13=5-(0-1) = 6 s15=24-(0+15) = 9 s21=19-(-11+3) =27 s23=22-(-11-1) =34 s25=13-(-11+15) =9 s31=20-(2+3) =15 s32=27-(2+13) = 12 s35=19-(2+15) = 2 s41= 0 -(-15+3) = 12 s42= 0-(-15+13)=2 s43= 0 -(-15-1) = 16 Данный план не оптимален. Выбираем клетку с наименьшей отрицательной оценкой (s12=-9) – переводим в базисную клетку (1,2). Строим для нее замкнутый цикл с вершинами в клетках (1,2), (1,4), (2,4) и (2,2), расставляя в вершинах поочередно «+» и «-», начиная с клетки (1,2). Из загрузок в «отрицательных» клетках выбираем наименьшую величину.  =min (4, 11)=4 Количество продукции в 4 ед. прибавляем в «положительных» клетках (1,2) и (2,4) и вычитаем в «отрицательных» (1,4) и (2,2). В итоге клетка (1,4) становится свободной, а вместо нее в базис водится (1,2). 29 Получаем новый опорный план. 60 B1=11 B2=11 B3=11 B4=16 60 3 4 5 15 A1=15 11 4 19 2 22 4 A2=15 7 8 20 27 1 17 A3=15 11 4 A4=15 4 vj 3 4 -10 6 Транспортные расходы при новом плане составят: z= 3*11+4*4+2*7+1*11+4*8++17*4+0*4+0*11= 174 Выбираем u1  0 Определяем остальные потенциалы u2=-2 u3=11 u4=-6 v1=3 v2=4 v3=-10 v4=6 v5=6 Определяем оценки sij свободных клеток: s13=5-(0-10) = 15 s14=15-(0+6) = 9 s15=24-(0+6) = 18 s21=19-(-2+3) =18 s23=22-(-2-10) =34 s25=13-(-2+6) =9 s31=20-(11+3) =6 s32=27-(11+4) = 12 s35=19-(11+6) = 2 s41= 0 -(-6+3) = 3 s42= 0-(-6+4)=2 s43= 0 -(-6-10) = 4 B5=11 24 13 19 11 ui -2 11 -6 6 Все оценки нового плана неотрицательные. Получен оптимальный план распределения продукции поставщиков по потребителям. Ответ: Продукция поставщика А1 в количестве 11 ед. направляется потребителю В1 и 4 ед. потребителю В2. Продукция поставщика А2 в количестве 7 ед. направляется потребителю В2 и 8 ед. потребителю В4. Продукция поставщика А3 в количестве 11 ед. направляется потребителю В3, 4 ед. направляется потребителю В4. При заданном оптимальном плане потребитель В4 недополучит 4 ед. продукции и потребитель В5 недополучит 11 ед. продукции. При этом транспортные расходы будут минимальными и составят 174 ден.ед. 3.8 Задача о назначениях Имеется n рабочих и m работ и задана стоимость назначения рабочего i на работу j для всех i и j . Каждый рабочий должен быть назначен ровно на одну работу, и каждая работа должна быть выполнена ровно одним рабочим. Требуется найти допустимое назначение, при котором суммарная стоимость F минимальна. Если рабочий не может выполнять какую-то работу, соответствующая стоимость равна бесконечности. Не ограничивая общности, можно считать, что n  m . Иначе можно ввести фиктивных рабочих или фиктивные работы с нулевыми стоимостями. Очевидно, что задача о назначениях является частным случаем транспортной задачи, в котором рабочие и работы могут рассматриваться как пункты производства и 30 потребления, а запас или заявка в каждом пункте равна единице. Для ее решения можно воспользоваться методом решения ТЗ. Однако, существует более эффективный метод ее решения, называемый венгерским. Предварительный этап.  В каждой строке матрицы задачи находим минимальный элемент и вычитаем его из всех элементов строки.  В каждом столбце полученной матрицы находим минимальный элемент и вычитаем его из всех элементов столбца. Задача о назначениях с полученной матрицей стоимостей эквивалентна исходной задаче о назначениях. Для получения стоимости оптимального назначения исходной задачи необходимо к стоимости оптимального назначения новой задачи прибавить сумму вычтенных чисел: F  F   . Последняя полученная матрица называется приведенной. Пример 1 Рассмотрим задачу о назначениях, заданную следующей матрицей стоимостей назначения. 1 4 6 3 9 7 10 9 4 5 11 7 8 7 8 5 Вначале вычтем из каждого элемента строки наименьший элемент этой строки по всем строкам. Получим матрицу 0 3 5 2 2 0 3 2 0 1 7 3 3 2 3 0 Найдем сумму вычтенных чисел   17 . Далее вычтем из каждого элемента столбца наименьший элемент этого столбца по всем столбцам. Получим матрицу 0 3 2 2 2 0 0 2 0 1 4 3 3 2 0 0   17 Общий шаг. 1. Находим строку с одним нулем. Этот нуль называется отмеченным. В столбце, где находится отмеченный нуль, все остальные нули зачеркиваются и в дальнейшем не рассматриваются. Это шаг продолжаем, пока возможно. 2. Находим столбец с одним нулем и этот нуль отмечаем. В строке, где находится отмеченный нуль, все остальные нули зачеркиваются. Этот шаг продолжать, пока возможно. 3. Если после шагов 1 и 2 еще есть неотмеченные нули, то отмечаем любой из них, а в строке и в столбце, где находится этот отмеченный нуль, все остальные нули зачеркиваем. 4. Если каждая строка и каждый столбец матрицы содержат ровно один отмеченный нуль, то получено оптимальное решение. Каждый из отмеченных нулей указывает прикрепление рабочего к работе. В противном случае проводим минимальное число пересекающихся горизонтальных и вертикальных прямых через все отмеченные пули. Среди не зачеркнутых этими прямыми чисел находим минимум. Этот минимум вычитаем из всех незачеркнутых чисел и прибавляем ко всем числам на пересечении прямых. К полученной матрице применяем вышеприведенный алгоритм, начиная с шага 1. 0 3 2 2 31 2 3 0 0 1 4 2 0 2 3 2 3 3 1 2 2 2 3 2 4 В нашем случае минимальное количество линий 3 - это столбец 1 и строки 2 и 4, Среди элементов, не покрытых линиями, находим наименьший (1). Вычитаем его из непокрытых элементов и прибавляем к числам на пересечении прямых. Получаем матрицу 3 4 2 2 1 3 1 2 2 Повторяем общий шаг. 0 2 1 1 3 0 0 2 0 0 3 2 4 2 0 0 Каждая строка и каждый столбец матрицы содержат ровно один отмеченный нуль, получено оптимальное решение. Они нули и определяют оптимальное назначение: рабочий 1 на работу 1, рабочий 2 на работу 3 и т.д. Стоимость назначения равна 21 Неочевидным является вопрос о нахождении минимального числа линий, покрывающих все нули в матрице. При небольшой размерности матрицы это число можно найти при помощи полного перебора. Иначе можно применить следующий алгоритм решения упрощенной задачи о назначениях. В этой задаче лишь нулевые элементы матрицы рассматриваются как допустимые назначения и необходимо выделить максимальное количество нулей таких, что никакие 2 нуля не расположены в одной строке или столбце. Алгоритм решения упрощенной задачи о назначениях Шаг 0. Строим любое допустимое назначение. Например, в каждой строке отмечаем ноль в столбце с наименьшим номером, не содержащем отмеченный ноль. 1 2 3 4 1 0 3 2 2 2 2 0 0 2 3 0 1 4 3 4 3 2 0 0 Шаг 1. Помечаем знаком "-" все строки, не содержащие отмеченных нулей. 1 2 3 4 3 1 2 3 2 3 1 2 3 2 4 4 2 2 3 1 - 32 А) В каждой помеченной («-» или номером) строке, например i , находим неотмеченные нули. Столбцы, соответствующие этим нулям, отмечаем номером строки ( i ). Однажды помеченный столбец далее не помечается. Просматриваем все помеченные строки. Б) В каждом помеченном столбце, например j , отыскиваем отмеченный нуль. Если он найден, помечаем строку, где он расположен, номером столбца ( j ). Просматриваем все помеченные столбцы. Возвращаемся к а), так как появились новые помеченные строки. Шаг 1 завершается, когда помечен столбец, не содержащий отмеченного нуля. В этом случае количество отмеченных нулей может быть увеличено следующим образом, В помеченном столбце, не содержащем отмеченного нуля, отмечаем ноль в строке, указываемой пометкой этого столбца. Затем в этой строке делаем неотмеченным нуль в столбце, указываемым пометкой этой строки. Процесс повторяется до тех пор, пока не отметим нуль в строке, первоначально помеченной знаком "-" (не содержащей отмеченных нулей). Повторяем Шаг 1. Алгоритм завершается, когда невозможно сделать ни одной пометки. Помеченные столбцы и непомеченные строки образуют минимальное количество линий, покрывающий все нули. 33 4 Основы теории графов Граф – это математическое понятие, которое служит для моделирования связей между объектами. 4.1 Основные понятия Графом G называется пара конечных множеств G  V , E  , где V – произвольное множество объектов, называемых вершинами, и E  i, ji, j  V  – множество неупорядоченных пар вершин, где i, j E называется ребром. Ориентированным графом (орграфом,) G называется пара конечных множеств G  V , A , где V – множество вершин, и A  i, j  i, j  V  – множество упорядоченных пар вершин, где i, j   A называется дугой. Примеры: Вершина i называется начальной, а вершина j – конечной вершиной дуги i, j  . При этом i и j – смежные вершины, а дуга i, j  инцидентна, вершинам i и j . Такая же терминология используется для неориентированных графов - смежные вершины и инцидентные ребра. Дуга i, j  выходит из i и входит в j . Если i, j  – дуга, то i называется непосредственным предшественником j , а j непосредственным последователем i . Количество дуг, входящих в вершину i называется степень захода этой вершины, а количество дуг, выходящих из вершины i называется степень исхода этой вершины. В неориентированном графе вершины i и j называются концами ребра i, j  . Количество ребер инцидентных вершине i называется степенью вершины i . Матрицей смежности графа G  V , E  называется матрица A  aij с n n элементами aij  1 , если i, j E , и aij  0 , еели i, j E . Графы могут быть также представлены одним или несколькими списками непосредственных последователей A0 i  и непосредственных предшественников B 0 i  каждой вершины i . Маршрутом (путем) в неориентированном графе G  V , E  называется такая последовательность вершин W  v0 , v1 ,..., vk  , k  0 , что vi 1 , vi  E , i  1,..., k . Граф называется связным, если существует маршрут, связывающий любые его две вершины. Маршрут W называется замкнутым, если k  0 и vk  v0 . 4.2 Построение эйлерова цикла Замкнутый маршрут (цикл), который включает каждое ребро графа ровно один раз, называется эйлеровым маршрутом (циклом), а граф, который содержит такой маршрут, называется эйлеровым графом. 34 Задачу, является ли граф эйлеровым, впервые поставил и решил Эйлер. В 1736 г. он писал: "В городе Кенигсберге есть два острова, которые соединяются между собой и с берегами реки семью мостами (см. Рис. 1). Рис. 1: Граф "Кенигсбергские мосты", a и c – острова, b и d – берега. Можно ли спланировать прогулку так, чтобы, начиная с одного из 4 участков суши a, b, c, d, пройти по каждому из этих мостов один раз и вернуться в начальный пункт? Теорема 3 (Эйлер, 1736 г) Связный (мулъти)граф является эйлеровым тогда и только тогда, когда все его вершины имеют четную степень. Алгоритм построения эйлерова цикла Шаг 0. Если граф несвязен либо существует вершина нечетной степени, то стоп Эйлерова цикла не существует. Шаг 1. Выбираем произвольную вершину v1 и полагаем частичный эйлеров цикл C*  v1. В графе G будем двигаться от некоторой вершины частичного цикла и помечать пройденные ребра. Помеченное ребро будем включать в эйлеров цикл. Полагаем i = 1. Шаг 2. Двигаемся от вершины vi по непомеченным ребрам и помечаем их до тех пор, пока не вернемся в vi . Пусть при этом построен цикл C. Цикл C включаем в C* так, что вначале идут ребра C* до вершины vi ; затем ребра цикла C и затем оставшиеся C*. Если все ребра исходного графа помечены, то эйлеров цикл построен. Если есть непомеченные ребра, то должна существовать вершина v j  C * , которая является концом непомеченного ребра. Пусть v j – последняя из таких вершин, входящая в C*. Шаг 3. Удаляем из графа ребра цикла С. В оставшемся графе вершины будут иметь четную степень. Полагаем i = j и переходим к Шагу 2, т.е. строим новый цикл на непомеченных ребрах, начиная с вершины v j . Алгоритм удобен для реализации на компьютере. При графическом решении задач малой размерности эйлеров цикл находится достаточно просто. 4.3 Остовное дерево (остов) минимального веса Связный граф, не имеющий циклов, называется деревом. Примеры деревьев: генеалогические граф (родословное дерево), совокупность всех файлов на дискете. Пусть n и m – количества вершин и ребер графа соответственно. Теорема (свойства деревьев). Пусть G – неориентированный граф. Тогда следующие условия эквивалентны: 1. G – дерево, 2. G – связный граф и m  n  1 , 3. G – граф без циклов и m  n  1 , 4. между любой парой вершин существует единственный маршрут, 35 5. G не имеет циклов, но при добавлении произвольного ребра в G в нем возникает единственный цикл. Подграф неориентированного графа G  V , E  называется остовным деревом (остовом), и обозначается T , если T – дерево и множество его вершин совпадает с V . Остовное дерево – это дерево вписанное в граф, которому принадлежат все вершины этого графа. Весом ребра называется число, которое ставится в соответствии каждому ребру графа. Весом остовного дерева называется сумма весов wij всех его ребер. Задача поиска в графе остовного дерева минимального веса возникает при проектировании дорог, электрических сетей, трубопроводов и т.п., т.е. в ситуациях, когда необходимо связать заданное множество объектов коммуникационными линиями и суммарная стоимость этих линий минимальна. Пример. Имеется 5 населенных пунктов, для которых нужно построить шоссейную дорогу. Каждому ребру ставим в соответствие число, равное стоимости постройки дороги. (вес ребра). Требуется определить: как необходимо строить дороги, чтобы стоимость строительства (вес остовного дерева) была минимальной. Ниже приводятся алгоритмы, которые для графа G  V , E  строят остовное дерево минимального веса Tn 1 , которое имеет n  1 ребер. Алгоритм Краскала Шаг 1. Полагаем T0  V ,   , V  n . Шаг 2. Для i  1,..., n  1 полагаем Ti 1  Ti  l , где l – ребро G с минимальным весом такое, что оно не является ребром Ti и не образует цикла с ребрами Ti . Последовательность выбираемых ребер: {1, 2}, {3,4}, {4,5}, {4,1}. Вес дерева: 1+1+1+4=7. Алгоритм Прима 36 Шаг 1. Полагаем T1  V1 , E1  , где V1  a, b , E1  a, b , и wab  minwl l  E. То есть выбираем граф, вершинами которого являются вершины графа G и который имеет одно ребро, выбранное из ребер графа G , имеющих минимальный вес. Шаг 2. Для i  1,..., n  1 полагаем Ti 1  Ti  l , где l – ребро G с минимальным весом такое, что оно не является ребром Ti , не образует цикла с ребрами Ti и инцидентно какому либо ребру Ti . Последовательность выбираемых ребер: {1, 2}, {4,1}, {3,4}, {4,5}. Вес дерева: 1+1+1+4=7. 4.4 Кратчайшие пути Рассмотрим орграф со взвешенными дугами и путь из вершины i в вершину j в этом графе. Сумма весов дуг этого пути называется его длиной. Путь минимальной длинны из i в j называется кратчайшим путем из i в j . Пример: Транспортной компании, имеющей базу в городе Минске, надо составить маршруты движения для автомашины в различные города Беларуси. Граф строится следующим образом: вершины – перекрестки дорог, ребра – участки дорог, вес ребра – длина участка (либо стоимость проезда). Требуется построить кратчайший путь от заданной вершины – Минск в остальные города. Дейкстра предложил следующий алгоритм построения кратчайших путей из данной вершины во все остальные вершины орграфа в случае неотрицательных весов дуг. Рассмотрим орграф G  V , A с выделенной вершиной s и весами wij , i, j   A . Алгоритм присваивает вершинам временные и постоянные метки. Постоянная метка вершины равна длине кратчайшего пути из s в эту вершину. Кроме того, формируется массив P , в котором Pv  содержит номер непосредственного предшественника вершины v в кратчайшем пути из s в v . Алгоритм Дейкстры (построения кратчайших путей из вершины s во все остальные вершины орграфа в случае неотрицательных весов дуг) Шаг 1. (Начало). Помечаем вершину s постоянной меткой l s   0 . Все остальные вершины v  s помечаются временными метками l v    . Полагаем номер текущей итерации i  1 и номер текущей вершины с постоянной меткой u  s . Шаг 2. (Рекурсия). Полагаем i  i  1 . Для вершины u найдем всех непосредственных последователей с временной меткой. Для каждого такого последователя v вычисляем новую временную метку l v   minl v , l u   wuv  . Если при этом временная метка изменилась, то полагаем Pv   u . Далее из всех вершин с временными метками выбираем вершину k с наименьшей меткой и делаем ее постоянной. Если i  n  1 , то полагаем u  k и повторяем Шаг 2. Иначе длины кратчайших путей из s в остальные вершины найдены и сами пути могут быть восстановлены по массиву P . Пример: Задан орграф с выделенной вершиной s и весами дуг. Найти кратчайшие пути из вершины s во все остальные вершины орграфа. 37 Решение: Шаг 1. l s   0 l a    l b    l c    l d    l e    Шаг 2. Для вершины s найдем всех непосредственных последователей с временной меткой. Это a, b и с. Вычисляем новые метки для этих вершин: l a   minl a , l s   wsa   min,0  4  4 Pa   s l b   minl b , l s   wsb   min,0  7  7 Pb   s l c   minl c , l s   wsc   min,0  3  3 Pc   s Из всех вершин с временными метками выбираем вершину с наименьшей меткой и делаем ее постоянной. l c   3 . Длины кратчайших путей из s в остальные вершины не найдены. Повторяем процесс. Для вершины c найдем всех непосредственных последователей с временной меткой. Это d . Вычисляем новую метку для этой вершины: l d   minl d , l c   wcd   min,3  3  6 Pd   c Из всех вершин с временными метками выбираем вершину с наименьшей меткой и делаем ее постоянной. l a   4 . 38 Для вершины a все непосредственные последователи с временной меткой – b и d. l b   minl b , l a   wab   min7,4  3  7 Pb   s l d   minl d , l a   wad   min6,4  2  6 Pd   c Из всех вершин с временными метками выбираем вершину с наименьшей меткой и делаем ее постоянной. l d   6 . Для вершины d все непосредственные последователи с временной меткой – e . l e   minl e , l d   wde   min,6  2  8 Pe   d Из всех вершин с временными метками выбираем вершину с наименьшей меткой и делаем ее постоянной. l b   7 . Для вершины b все непосредственные последователи с временной меткой – e . l e   minl e , l b   wbe   min8,7  2  8 Pe   d Из всех вершин с временными метками выбираем вершину с наименьшей меткой и делаем ее постоянной. l e   8 . 39 Замечание. Решение в общем случае не является единственным. Кратчайший путь является единственным только в том случае, если в алгоритме ни разу не возникает неоднозначности в выборе дуг. В данном примере такая неоднозначность возникла и соответствующее альтернативное решение: s, e  s, a , a, d , d , e. 40 5 Сетевое планирование и управление проектами На практике довольно часто встречаются задачи планирования и управления сложными работами или проектами. Примеры: строительство большого объекта, разработка комплекса компьютерных программ, производство самолета, ракеты или другого большого изделия, выпуск нового продукта, передислокация фирмы или производства. Наиболее распространенными методами планирования и управления проектами являются сетевые методы. Сетевая модель включает следующее: 1) определение элементарных работ, 2) представление временных связей между элементарными работами в виде сети, в которой вершины и дуги представляют собой связи между элементарными работами, при этом будет присутствовать начальная, возможно фиктивная, работа, соответствующая началу проекта, и конечная работа, соответствующая его завершению. Решение сетевой задачи включает следующее: 1) определение или оценивание длительности p j выполнения каждой элементарной работы j , 2) определение критического, т.е. наиболее длинного пути между начальной и конечной вершиной сети. Длина критического пути представляет собой наименьшую возможную длительность выполнения проекта. Задержка выполнения любой элементарной работы, принадлежащей критическому пути приводит к задержке завершения выполнения всего проекта. Сетевая модель может использоваться для контроля выполнения проекта. Изменения длительностей выполнения либо задержки выполнения элементарных работ могут вноситься в сетевую модель для пересчета критического пути. Наиболее распространены два типа сетевых моделей, называемые 1) действие-на-вершине 2) действие-на-дуге. В модели 1) вершины представляют собой элементарные работы проекта, а дуги указывают последовательность их выполнения. Вершинам приписаны длительности выполнения соответствующих работ. В модели 2) дуги представляют собой элементарные работы проекта, а вершины соответствуют событиям "начало работы" и "конец работы". Дугам сопоставлены длительности выполнения соответствующих работ. Для отражения отношений предшествования между работами могут вводиться фиктивные дуги нулевой длины. Рассмотрим модель 2) "действие-на-дуге". Алгоритм отыскания критического пути (между вершинами s и t ацикличного орграфа G  V , A с неотрицательными весами дуг tij ) Метка вершины t p v  соответствует длине самого длинного пути из s в v . Шаг 1 (Начало). Помечаем вершину s меткой t p s   0 . Полагаем множество помеченных вершин S  s . Шаг 2 (Рекурсия). Находим непомеченную вершину v , в которую входят дуги только из помеченных вершин (множества Bv0  S ). Помечаем v меткой   t p v   max t p u   tuv u  Bv0 и включаем v в S . Если максимум достигается на вершине u 0  Bv0 , то самый длинный путь в вершину v пришел из вершины u 0 . 41 Если помечена вершина t , то длина критического пути равна T  t p t  и сам путь может быть восстановлен обратным просмотром уравнений рекурсии. Иначе повторяем Шаг 2. Пример. Для реконструкции здания банка необходимо выполнить комплекс работ, который представлен сетевым графиком. Определим критический путь Найдем ранние сроки свершения событий построенного сетевого графика. tp(s)=0 как начального события. tp(1)=0 в событие (1) входит только одна работа . tp(2)= max(tp(1)+t12)= max(0+4)=4 в событие (2) входит только одна работа(1;3). tp(3)= max(tp(1)+t13; tp(2)+t23 )= max(0+2; 4+3)=7 в событие (3) входят две работы (1;3) и (2;3). tp(4)= max(tp(2)+t24)= max(4+6)=10 в событие (4) входит только одна работа. tp(5)= max(tp(2)+t25; tp(3) +t35)= =max(4+4;7+5)= max(8;12)=12 в событие (5) входят две работы (2;5) и (3;5). tp(6)= max(tp(4)+t46; tp(5) +t56)= =max(10+1;12+7)= max(11;19)=19 в событие (6) входят две работы (4;6) и (5;6). tp(t)= max(tp(6)+t6t)= 19 в событие (t) входит одна работа (6;t). Следовательно, критический путь 1-2-3-5-6 С критическим временем tкр=19. Характеристики событий 1. Ранний срок свершения события tp(s)=0, t p v   maxt p u   tuv  характеризует u самый ранний срок завершения всех путей в него входящих. Этот показатель определяется «прямым ходом» по графу модели, начиная с начального события сети. 2. Поздний срок свершения события tn(t)= tp(t), tn u   mintn v   tuv  характеризует v самый поздний срок, после которого остается ровно столько времени, сколько требуется для завершения всех путей следующих за этим событием. Этот показатель определяется “обратным ходом” по графу модели, начиная с завершающего события сети. 42 3. Резерв времени события Rv   t p v   tn v  показывает, на какой максимальный срок можно задержать наступление этого события, не вызывая при этом увеличения срока выполнения всего комплекса работ. Резервы времени для событий на критическом пути равны нулю, R(v)=0. Пример: Так как ранние и поздние сроки свершения критических событий совпадают, то tn(6)=19; tn(5)=12; tn(3)=7; tn(2)=4; tn(1)=0. Остается найти tn(4) tn(4)= min(tn(6)-(4,6))= min(19-1)=18 R(4)= tn(4)- tр(4)=18-10=8 На сетевом графике все рассчитанные параметры отображаются следующим образом: v tр(v) tn(v) R(v) Для каждой работы (i,j) могут быть вычислены наиболее ранний tpн(i,j) и наиболее поздний tпн(i,j) моменты ее начала такие, что начало работы в промежутке [tpн(i,j); tпн(i,j)] не приводит к увеличению длительности всего проекта. Знание указанных моментов позволяет реализовать расписание более гибко, поскольку есть возможность задержки начала выполнения некоторых работ без ущерба для длительности выполнения всего проекта. Характеристики работы (i,j) 1. Ранний срок начала работ tpн(i,j)=tp(i). 2. Ранний срок окончания работы tpo(i,j)= tpн(i,j) + tij =tp(i) + tij 3. Поздний срок начала работы: tпн(i,j)=tп(j) – tij. 4. Поздний срок окончания работы: tпо(i,j) = tп(j). 5. Резервы времени работ:  полный резерв Rп(i,j) = tп(j) - tp(i) - tij. есть максимальный запас времени, на который можно отсрочить начало или увеличить длительность работы без увеличения длительности критического пути. Работы на критическом пути не имеют полного резерва времени, для них Rп(i,j)=0.  частный резерв R1(i,j) = Rп(i,j) - R(i) = tп(j) – tп(i) - tij. есть часть полного резерва, на которую можно увеличить продолжительность работы, не изменив позднего срока ее начального события.  свободный резерв Rс(i,j) = Rп(i,j) - R(j) = tp(j) – tp(i) - tij. есть максимальный запас времени, на который можно задержать начало работы или (если она началась в ранний срок) увеличит ее продолжительность, не изменяя ранних сроков начала последующих работ.  независимый резерв Rн(i,j) = Rп(i,j) - R(i) – R(j) = tp(j) – tп(i) - tij. 43 есть запас времени, при котором все предшествующие работы заканчиваются в поздние сроки, а все последующие – начинаются в ранние сроки. Использование этого резерва не влияет на величину резервов времени других работ. Сделаем ряд замечаний. Работы, лежащие на критическом пути, резервов времени не имеют. Если на критическом пути Lкр лежит начальное событие i работы (i,j), то Rп(i,j) = R1(i,j). Если на Lкр лежит конечное событие j работы (i,j), то Rп(i,j) = Rc(i,j). Если на Lкр лежат и событие i, и событие j работы (i,j), а сама работа не принадлежит критическому пути, то Rп(i,j) = Rс(i,j) = Rн(i,j). Линейный график Ганта Для сетевого графика часто строится линейный график Ганта, на котором обозначаются ранние времена начала и продолжительности всех работ. На графике Гранта каждая работа (i,j) обозначена отрезком, который имеет длину tij и начинается в ранний срок tp(i) начального события (рис. 1). Работы (6,7) (5,7) (5,6) (4,6) (3,5) (2,7) (2,5) (2,3) (1,4) (1,3) (1,2) t tp(2) tkp=16 Рис. 1. Линейный график Гранта. На графике Гранта видны ранние времена начала, окончания и продолжительность каждой работы, параллельно выполняемые работы. По графику легко определить время завершения всего проекта tkp. Пример. Рассмотрим проект, состоящий из ряда взаимосвязанных работ. Необходимо построить сетевую модель проекта, характеристики которого представлены в таблице 1. Выполнить временной и ресурсный анализ. Таблица 1. Исходные данные по проекту. Операция (работа) A B C D E F G H I Последователи Предшественники B, C D E, F, G, H F, G, H I I K J K A A B C C, D C, D C, D E, F Продолжительность (дни) 4 8 6 2 4 8 6 3 4 Рабочая сила (чел.) 5 1 3 6 7 1 8 9 44 J K L M N O K L, M N H G, I, J K K L N O 5 6 8 3 8 2 3 4 2 1 3 Решение: Строим сетевой график. Просматривая структурно-временной проект, видим, что работе А не предшествуют никакие работы. Следовательно, она должна выходить из начального события (1) к другому событию (2). Работам N и O нет последующих, следовательно, они должны входить в завершающее событие из другого события. Работе В предшествует работа А. Следовательно, дуга В должна выходить из события (2), в которое входит работа А и входить в событие(3). Работе С предшествует работа А. Следовательно, дуга С должна выходить из события (2), в которое входит работа А и входить в событие (4) и т.д. 4 E 6 11 10 I С F L 2 1 8 5 А G В 3 O N K J D H 12 9 M 7 45 4 4 6 10 14 4 22 22 6 4 8 4 8 8 26 26 4 5 14 1 4 2 8 2 11 48 48 10 40 40 8 3 12 12 14 6 5 2 3 12 50 50 6 9 32 32 3 7 17 21 4 Найдем ранние сроки свершения событий построенного сетевого графика. tp(i)= max{tp(i)+t(i,j)} tp(1)=0 tp(2)= max(tp(1)+A)= max(0+4)=4 как начального события. в событие (2) входит только одна работа A. tp(3)= max(tp(2)+B)= max(4+8)= 12 в событие (3) входит только одна работа B. tp(4)= max(tp(2)+C)= max(4+6)= 10 в событие (4) входит только одна работа C. tp(5)= max(tp(3)+D; tp(4)+(4, 5))= max(12+2; 10+0)=14 в событие (5) входят две работы D и фиктивная работа (4, 5). tp(6)= max(tp(4)+E; tp(5)+F)= max(8+4; 14+8)= max(12; 22)=22 в событие (6) входят две работы E и F. tp(7)= max(tp(5)+H)= max(14+3)= 17 в событие (7) входит только одна работа H. tp(8)= max(tp(5)+G; tp(6)+ I; tp(7)+ J)= = max(14+6; 22+4; 17+5)=26 в событие (8) входят трт работы G, I и J. tp(9)= max(tp(8)+K)= max(26+6)= 32 в событие (9) входит только одна работа K. tp(10)= max(tp(9)+L)= max(32+8)= 40 в событие (10) входит только одна работа L. tp(11)= max(tp(10)+N)= max(40+8)= 48 в событие (11) входит только одна работа N. tp(12)= max(tp(9)+M; tp(11)+O)= =max(32+3; 48+2)= max(35; 51)=50 в событие (12) входят две работы M и O. Определим критический путь. Из двух работ, входящих в событие (12), tкр=50 определила работа O, так как tp(11)+O=50, поэтому работа O является критической. 46 Момент свершения события (11) определила работа N так как tp(10)+N =48, в связи с чем работа N будет критической. В свою очередь момент свершения события (10) определила работа L, события (9) –работа K, события (8) – работа I, события (6) – работа F, события (5) – работа D, события (3) – работа B и события (2) – работа A. Следовательно, критический путь 1-2-3-5-6-8-9-10-11-12 с критическим временем tкр=50. Найдем поздние сроки свершения событий построенного сетевого графика. tп(i)= min{tп(j)-t(i,j)} Так как ранние и поздние сроки свершения критических событий совпадают, то tп(1)=0; tп(2)=4; tп(3)=12; tп(5)=14; tп(6)=22; tп(8)=26; tп(9)=32; tп(10)=40; tп(11)=48; tп(12)=50. Остается найти tп(4) и tп(7); tп(7)= min(tп(8)- J)= min(26-5)=21 tп(4)= min(tп(6)- E; tп(5)- t(4,5))= min(22-4; 14-0)=14 Определим резервы событий R(i)= tп(i)- tр(i) Резервы критических событий равны 0. R(4)= tп(4)- tр(4)=14-10=4 R(7)= tп(7)- tр(7)=21-17=4 Сведем полученные результаты в таблицу i 1 2 3 4 5 6 7 8 9 10 11 12 tp(i) 4 12 14 14 22 21 26 32 40 48 50 tп(i) 4 12 10 14 22 17 26 32 40 48 50 R(i) 4 4 Произведем оптимизацию графика по ресурсам. Для этого строим линейный график 47 Максимально потребуется 16 чел. трудовых ресурсов на промежутке времени с 14 до 19. Ответ: Критический путь образуют события 1-2-3-5-6-8-9-10-11-12 с критическим временем tкр=50. Резервы критических событий равны 0 и R(4)=4, R(7)=4. Максимально потребуется 16 чел. трудовых ресурсов. 48