Учебное пособие: Методы исследования операций

Учебное пособие: Методы исследования операций

МЕТОДЫ ИССЛЕДОВАНИЯ ОПЕРАЦИЙ

Программа

Программа дисциплины «Методы исследования операций» предназначена для студентов специальности «Экономическая кибернетика».

Цель учебной дисциплины «Методы исследования операций» - вооружить студентов фундаментальными теоретическими знаниями и помочь сформировать практические навыки в вопросах постановки и решения оптимизационных экономических задач методами исследования операций.

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

Основное содержание дисциплины раскрывают такие темы:

I семестр

1.  Методы исследования операций и их использование в организационном управлении.

2.  Общая задача линейного программирования и некоторые методы ее решения.

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

4.  Анализ линейных моделей экономических задач.

5.  Транспортная задача. Постановка, методы решения.

6.  Целочисленные задачи линейного программирования. Некоторые методы их решения и анализа.

II и III семестры

7.  Элементы теории игр.

8.  Блочное программирование.

9.  Параметрическое программирование.

10.  Задачи календарного планирования.

11.  Задачи нелинейного программирования. Некоторые методы их решения.

12.  Динамическое программирование.

13.  Управление запасами.

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

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

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

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

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

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

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

Финансовый отдел, стремясь минимизировать объем капитала, необходимого для функционирования предприятия, пытается уменьшить количество «связанных» оборотных средств. Поэтому он заинтересован в уменьшении запасов до минимума. Как видим, требования к размерам запасов у разных подразделений организации оказываются различными. Возникает вопрос, какая стратегия в отношении запасов будет наиболее благоприятной для всей организации. Это типичная задача организационного управления. Она связана с проблемой оптимизации функционирования системы в целом и затрагивает противоречивые интересы ее подразделений.

Основные особенности исследования операций.

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

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

3. Одной из существенных особенностей исследования операций является стремление найти оптимальное решение поставленной задачи. Однако часто такое решение оказывается недостижимым из-за ограничений, накладываемых имеющимися в наличии ресурсами (денежные средства, машинное время) или уровнем современной науки. Например, для многих комбинаторных задач, в частности задач календарного планирования при числе станков п > 4, оптимальное решение при современном развитии математики оказывается возможным найти лишь простым перебором вариантов. Тогда приходится ограничиваться поиском «достаточно хорошего», или субоптимального решения. Поэтому исследование операций один из его создателей — Т. Саати — определил как «...искусство давать плохие ответы на те практические вопросы, на которые даются еще худшие ответы другими методами».

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

Каждое операционное исследование проходит последовательно следующие основные этапы:

1)  постановка задачи,

2)  построение математической модели,

3)  нахождение решения,

4)  проверка и корректировка модели,

5)  реализация найденного решения на практике.

В самом общем случае математическая модель задачи имеет вид:

найти

max Z=F(x, y) (1.1)

при ограничениях

, (1.2)

где Z=F(x, y) – целевая функция (показатель качества или эффективность) системы; х — вектор управляемых переменных; у — вектор неуправляемых переменных; Gi(x, y)— функция потребления i-го ресурса; bi — величина i-го ресурса (например, плановый фонд машинного времени группы токарных автоматов в станко-часах).

Определение 1. Любое решение системы ограничений задачи называется допустимым решением.

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

Для нахождения оптимального решения задачи (1.1)-(1.2) в зависимости от вида и структуры целевой функции и ограничений используют те или иные методы теории оптимальных решений (методы математического программирования).

1. Линейное программирование, если F(x, y),  — линейны относительно переменных х.

2. Нелинейное программирование, если F(x, y) или  — нелинейны относительно переменных х.

3. Динамическое программирование, если целевая функция F(x, y) имеет специальную структуру, являясь аддитивной или мультипликативной функцией от переменных х.

F(x)=F(x1, x2, …, xn) — аддитивная функция, если F(x1, x2, …, xn)=, и функция F(x1, x2, …, xn) — мультипликативная функция, если F(x1, x2, …, xn)=.

4. Геометрическое программирование, если целевая функция F(x) и ограничения  представляют собой функции вида

Математическая модель задачи в этом случае записывается в виде

при условиях ,

,

где I[0]=(m0, m0+1, …, n0); I[k]= (mk, mk+1, …, nk); mk+1=nk+1; m0=1; n0=n.

5. Стохастическое программирование, когда вектор неуправляемых переменных у случаен.

В этом случае математическая модель задачи (1.1—1.2) будет иметь

maxMyE=My{f(x, y)}

при ограничениях

или вероятностных ограничениях

где My — математическое ожидание по у; Р{gi (х)£ b} — вероятность того, что выполняется условие gi (х)£ b.

6. Дискретное программирование, если на переменные xj наложено условие дискретности (например, целочисленности): xj — целое, j=1,2,…,n1£п.

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

По содержательной постановке выделяют следующие типичные классы задач исследования операций:

1)  управления запасами,

2)  распределения ресурсов,

3)  ремонта и замены оборудования,

4)  массового обслуживания,

5)  упорядочения,

6)  сетевого планирования и управления,

7)  выбора маршрута,

8)  комбинированные.

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

Линейное программирование

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

Определение оптимального ассортимента. Имеется р видов ресурсов в количествах а1, а2, ..., аi, ..., аp и q видов изделий. Задана матрица А=||aik||, где аik характеризует нормы расхода i-го ресурса на единицу k-го изделия (k = 1, 2, ..., q).

Эффективность выпуска единицы k-го изделия характеризуется показателем сi, удовлетворяющим условию линейности.

Определить план выпуска изделий (оптимальный ассортимент), при котором суммарный показатель эффективности принимает наибольшее значение.

Количество единиц k-го изделия, выпускаемых предприятием, обозначим хk. Тогда математическая модель задачи имеет такой вид:

найти

  (1.3)

при ограничениях

 (1.4)

Кроме ограничения по ресурсам (1.3), в модель могут быть введены дополнительные ограничения на планируемый выпуск продукции xj³xj0, условия комплектности для сборки xi : хj : xk. = bi : bj : bk для всех i, j, k и т. д.

Оптимальное распределение взаимозаменяемых ресурсов. Имеются т видов взаимозаменяемых ресурсов а1, а2, ..., аi, ..., аm используемых при выполнении п различных работ в объеме b1, b2, …, bn.

Заданы числа lij, указывающие, сколько единиц j-й работы можно получить из единицы i-го ресурса, а также сij — затраты при изготовлении единицы j-го продукта из i-го ресурса.

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

Данная задача называется общей распределительной задачей.

Количество единиц i-го ресурса, которое выделено для выполнения работ j-то вида, обозначим xij.

Математическая модель задачи такова:

найти

 (1.5)

при ограничениях

 (1.6)

 (1.7)

Ограничение (1.6) означает, что план всех работ должен быть выполнен полностью, а ограничение (1.7) — что ресурсы должны быть израсходованы целиком.

2.  Математическая модель задачи линейного программирования (ЗЛП).

Задачу линейного программирования можно сформулировать так

Найти

 (2.1)

при условиях

 (2.2)

и

 (2.3)

Ограничения (2.3) называют условиями неотрицательности. В данном случае все условия имеют вид неравенств. Иногда они могут быть смешанными, т. е. неравенства и равенства.

Определение 3. Допустимым множеством решений задачи (2.1)—(2.3) называется множество R(х) всех векторов х, удовлетворяющих условиям (2.2) и (2.3).

Очевидно множество R(х) представляет собой выпуклое многогранное множество или выпуклый многогранник.

Отметим, что поскольку minF(х) эквивалентен max[-F(х)], то задачу ЛП всегда можно свести к эквивалентной задаче максимизации.

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

Стандартная форма задачи линейного программирования предполагает, что для всех переменных выполняется условие неотрицательности и все условия-ограничения имеют вид уравнений с неотрицательной правой частью.

Допустимые базисные решения.

Пусть ограничения задачи ЛП заданы в форме уравнений, т.е. задача записана в стандартной форме и содержит m уравнений и n (n³m) переменных. Тогда все допустимые крайние точки множества допустимых решений определяются как все однозначные неотрицательные решения системы m уравнений, в которых n-m переменных равны нулю. Однозначные решения такой системы уравнений, получаемые путем приравнивания к нулю (n-m) переменных, называются базисными решениями. Если базисное решение удовлетворяет требованию неотрицательности, оно называется допустимым базисным решением. Переменные, имеющие нулевое значение называются небазисными или свободными переменными, а остальные базисными.

Основные теоремы линейного программирования

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

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

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

Из теоремы 2.1 следует, что при отыскании оптимального решения достаточно просмотреть только крайние точки допустимого множества решений R.

Теорема 2.2. Каждое допустимое базисное решение соответствует крайней точке R.

Справедлива также следующая теорема, обратная к теореме 2.2. Теорема 2.3. Если  — крайняя точка допустимого множества решений R, то соответствующее решение x0 — является допустимым базисным решением системы ограничений задачи линейного программирования.

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

Симплекс-метод.

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

Алгоритм симплекс-метода состоит из следующих шагов:

Шаг 0. Используя линейную модель стандартной формы, определяют начальное допустимое базисное решение путем приравнивания к нулю n-m (небазисных) переменных. При этом если матрица системы ограничений задачи линейного программирования содержит единичную подматрицу порядка m, то это решение очевидно. Переменные, столбцы которых образуют эту единичную матрицу, являются базисными, остальные – свободными. Если же такой единичной матрицы нет, то для получения начального базисного решения вводятся искусственные переменные. Затем базисные переменные выражаются через небазисные из соответствующих ограничений и полученные выражения подставляются в целевую функцию. Если используются искусственные переменные, то применяются специальные методы (метод больших штрафов, двухэтапный метод).

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

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

Шаг 3. С помощью метода исключения переменных или метода Гаусса-Жордана находится новое базисное решение, соответствующее новым составам базисных и небазисных переменных и осуществляется переход к шагу 1.

Пример. Решить симплекс-методом задачу

Максимизировать z=3x1+2x2

при ограничениях x1+2x2£ 6;

2x1+x2£ 8;

-x1+x2£ 1;

x1£ 2;

x1³ 0, x2³ 0.

Решение.

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

z-3x1-2x2=0

x1+2x2+s1= 6;

2x1+x2+s2= 8;

-x1+x2+s3= 1;

x1+s4= 2,

где s1, s2, s3, s4 – дополнительные неотрицательные переменные, которые вводятся в правые части ограничений имеющих знак «£» и называются остаточными. Если задача линейного программирования является задачей оптимального распределения ограниченных ресурсов, и правые части каждого ограничения представляют запасы ресурсов, то значения остаточных переменных в любом решении показывают остаток этих ресурсов. Матрица системы ограничений содержит единичную матрицу порядка 4. Ее образуют коэффициенты при остаточных переменных, значит переменные s1, s2, s3, s4 будут базисными переменными, а x1, x2 – свободными или нулевыми.

Шаг 0. Заполняем начальную симплекс-таблицу.

Шаг 1. Условие оптимальности или правило выбора включаемой в базис переменной. Вводимой в базис переменной в задаче максимизации (минимизации) является небазисная переменная, имеющая в Z-строке наибольший по модулю отрицательный (положительный) коэффициент. Если таких коэффициентов несколько, то выбор – произвольный и после этого переходят к шагу 2. Если таких коэффициентов нет, то решение оптимально.

Столбец симплекс-таблицы, соответствующий включаемой переменной, будем называть ведущим столбцом. В нашем случае включаем в базис переменную x1.

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

Строку симплекс-таблицы, соответствующую исключаемой переменной, будем называть ведущей строкой. В нашем случае исключаем из базиса переменную s2.

Шаг 3. Вычисляем новое базисное решение и переходим к шагу 1.

Симплекс-таблица, соответствующая первой итерации:

Решение не оптимально. Включаем в базис x2 вместо s1. Вторая итерация:

Решение оптимально.

Анализ решения на чувствительность.

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

1.  Оптимального решения: значения базисных переменных записаны в столбце В оптимальной симплекс-таблицы. Оптимальное значение целевой функции находится на пересечении Z-строки и столбца В оптимальной симплекс таблицы. Для рассмотренного примера: x1=10/3, x2=4/3, s1=s2=0, s3=3, s4=2/3, Zmax=12 2/3.

2.  Статуса ресурсов: ресурс называется дефицитным, если в оптимальном решении он использован полностью. Остаточная переменная, соответствующая дефицитному ресурсу в оптимальном решении равна нулю. Для рассмотренного примера дефицитными будут ресурсы 1 и 2, т.к. s1=s2=0,

3.  Ценности каждого ресурса: характеризуются величиной улучшения оптимального значения целевой функции, приходящегося на единицу прироста объема данного ресурса. Их еще называют теневыми ценами ресурсов или двойственными оценками. Эта информация представлена в Z-строке оптимальной симплекс-таблицы в столбцах, соответствующих остаточным переменным.

4.  Чувствительности оптимального решения к изменениям запасов ресурсов, вариациям коэффициентов целевой функции и интенсивности потребления ресурсов.

Двойственность в линейном программировании.

Любую задачу максимизации с экономической точки зрения можно рассматривать как задачу о распределении ограниченных ресурсов b1, b2,…, bn между различными потребителями, например, между некоторыми технологическими процессами, которые представляются столбцами A1, А2, ..., Аm матрицы ограничений задачи. Любое допустимое решение задачи линейного программирования х1, х2, ..., хm дает конкретное распределение, указывающее ту долю каждого из ресурсов, которая должна быть использована при осуществлении соответствующего технологического процесса.

Рассмотрим пример. Завод производит три вида продукции х1, x2 и x3, каждый из которых требует затрат времени на обработку на токарном, фрезерном и сверлильном станках. Количество машинного времени для каждого из станков ограничено. Пусть с1, c2 и c3 — прибыль от реализации единицы соответствующего вида продукции. Необходимо определить, какое количество каждого вида продукции необходимо производить в течение недели, чтобы получить максимальную прибыль.

Формально эта задача записывается так:

найти

 (1)

при ограничениях

 (2)

где a1j, a2j, a3j — время, необходимое для обработки единицы j-го вида продукции соответственно на токарном, фрезерном и сверлильном станках (j = 1, 2, 3); b1, b2, b3 — недельный ресурс машинного времени соответственно для токарного, фрезерного и сверлильного станков.

Обозначим y1, y2 и y3 — цену единицы времени работы на токарном, фрезерном и сверлильном станках. Тогда a1jy1 + a2jy2+ a3jy3 мож­но трактовать как расходы на изготовление единицы продукции вида j.

Предположим, что цены ресурсов y1, y2 и y3 выбраны так, что выполняются следующие соотношения:

 (3)

Поскольку b1, b2, b3 — использованный ресурс машинного времени для каждого из станков, то b1y1 + b2y2 + b3y3 — суммарные расходы на производство.

Требуется найти такие y1, y2 и y3, удовлетворяющие условиям (3), при которых минимизируются суммарные расходы на производство:

min g(y1, y2, y3)= b1y1 + b2y2 + b3y3, (4)

y1³ 0, y2³ 0, y3³ 0.

Такую задачу называют двойственной задачей по отношению к задаче (1), называемой прямой.

Запишем теперь прямую и двойственную задачи в общем случае. Прямая задача

  (5)

при условиях

 (6)

. (7)

Двойственная задача

 (8)

при условиях

 (9)

. (10)

Сопоставляя формы записи прямой и двойственной задач, можно установить между ними следующие взаимосвязи:

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

2) коэффициенты целевой функции прямой задачи c1, c2, …, cn становятся свободными членами ограничений двойственной задачи;

3) свободные члены ограничений прямой задачи b1, b2, …, bm становятся коэффициентами целевой функции двойственной задачи;

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

5) если знаки всех неравенств в ограничениях прямой «£», то в двойственной задаче все ограничения будут иметь знак «³»;

6) число ограничений прямой задачи равно числу переменных двойственной задачи, а число ограничений двойственной задачи равно числу переменных прямой задачи.

Переменные y1, y2,…, ym двойственной задачи иногда называют «теневыми ценами».

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

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

Теорема. Если x0 и у0 — допустимые решения прямой и двойственной задач, т. е. если Ах0 £ b и АTy0 ³ с, то

cTx0£ bTy0,

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

Теорема(основная теорема двойственности). Если x0 и у0 — допустимые решения прямой и двойственной задач и если cTx0=bTy0, то x0 и у0 — оптимальные решения пары двойственных задач.

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

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

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

Экономическая интерпретация этой теоремы: поскольку величины yj представляют собой цены соответствующих ресурсов, то  — это затраты на i-й технологический процесс, величина сi — прибыль от реализации на единицу изделия. Поэтому с экономической точки зрения теорема означает следующее: если i-й технологический процесс оказывается строго невыгодным с точки зрения оптимальных цен ресурсов уопт, то в оптимальном решении прямой задачи интенсивность использования данного технологического процесса хi должна быть равна 0.

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

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

Теорема (теорема двойственности). Допустимый вектор x0 оптимален тогда и только тогда, когда в двойственной задаче имеется такое допустимое решение уо, что

.

Методы решения целочисленных ЗЛП.

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

Методы решения задач целочисленного программирования можно классифицировать как методы отсечений (1) и комбинаторные методы (2).

Исходной задачей для методов отсечений, используемых при решении линейных целочисленных задач, является задача с ослабленными ограничениями, которая возникает в результате исключения требования целочисленности переменных. По мере введения специальных дополнительных ограничений, учитывающих требования целочисленности, многогранник допустимых решений ослабленной задачи постепенно деформируется до тех пор, пока координаты допустимого решения не станут целочисленными. Название «методы отсечений» связано с тем обстоятельством, что вводимые дополнительные ограничения отсекают (исключают) некоторые области многогранника допустимых решений, в которых отсутствуют точки с целочисленными координатами,

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

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

Алгоритм метода отсечений для решения полностью целочисленной задачи.

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

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

Рассмотрим i-ую строку, которой соответствует нецелое значение базисной переменной xi, и выразим xi через небазисные переменные:

, bI – нецелое.

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

bI=[bI]+fi, aji=[aji]+fij, 0<fi<1, 0£fij<1.

В качестве дополнительного ограничения вводим такое

,

где Si – неотрицательная дополнительная переменная, которая по определению должна принимать целые значения. Такое ограничение равенство определяет отсечение Гомори для полностью целочисленной задачи. Добавив построенное ограничение в симплекс-таблицу, получим недопустимое, но оптимальное решение. В такой ситуации следует использовать двойственный симплекс-метод для получения допустимого и оптимального решения.

Метод ветвей и границ.

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

[xr]< xr<[xr]+1

не содержит допустимых целочисленных компонент решения. Поэтому допустимое целое значение xr должно удовлетворять одному из неравенств [xr]³ xr или xr³ [xr]+1. Введение этих условий в задачу с ослабленными ограничениями порождает две не связанные между собой задачи. В таком случае говорят, что исходная задача разветвляется на две подзадачи. Осуществляемый в процессе ветвления учет необходимых условий целочисленности позволяет исключить части многогранника допустимых решений, не содержащие точек с целыми координатами.

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

Задача линейного программирования транспортного типа.

Постановка задачи. Пусть в m пунктах производят некоторый однородный продукт, причем объем производства в пункте i составляет Ai единиц. Допустим, что данный продукт потребляется в n пунктах потребления, а объем потребления в пункте j составляет единиц Bj. Предположим, что из каждого пункта производства i возможна транспортировка продукта в любой пункт потребления j с затратами cij. Задача состоит в определении такого плана перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт вывезен из пунктов производства и суммарные транспортные издержки минимальны.

Математическая модель. Пусть xij – количество продукта, перевозимого из пункта i в пункт j. Найти множество переменных удовлетворяющих условиям

,

.

и таких, что целевая функция

достигает минимума.

Метод решения транспортной задачи [6, 7, 10].

Сети

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

Задача минимизации сети.

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

Задача о кратчайшем пути

Задача о кратчайшем пути состоит в нахождении связанных между собой дорог на транспортной сети, которые имеют минимальную длину от исходного пункта до пункта назначения. Для решения этой задачи можно применить следующий алгоритм. Каждому узлу сети будем приписывать временные пометки равные расстоянию от начального узла до данного узла. Если оказывается, что узел принадлежит кратчайшему маршруту, то временную пометку объявляем постоянной. На первой итерации начальному узлу приписывается постоянная пометка равная нулю, а остальным узлам – временные пометки, равные длине дуги из начального узла в рассматриваемый узел, если такая дуга существует и «¥», если нет такой дуги. Затем, до тех пор пока конечный узел не получит постоянную пометку выполняются следующие две процедуры: 1) среди временных пометок выбирается минимальная и объявляется постоянной; 2) для всех временно помеченных узлов вычисляются новые временные пометки, меньшей из двух величин – старой временной пометки рассматриваемого узла и суммы постоянной пометки последнего постоянно помеченного узла и длины дуги, соединяющей последний постоянно помеченный узел с рассматриваемым узлом. Если при этом постоянную пометку получает конечный узел, то кратчайший маршрут найден. Дуги входящие в этот маршрут определяются следующим образом: если разность между постоянными пометками начального и конечного узлов данной дуги равна длине дуги, то эта дуга принадлежит кратчайшему маршрут.

Задача о максимальном потоке

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

Пропускные способности cij сети можно представить в матричной форме. Для определения максимального потока из источника s в сток t используется следующий алгоритм.

Шаг 1. Найти цепь, соединяющую s с t, по которой поток принимает положительное значение в направлении s®t. Если такой цепи не существует, перейти к шагу 3. В противном случае перейти к шагу 2.

Шаг 2. Пусть cij- (cij+) – пропускные способности дуг цепи (s, t) в направлении s®t (t®s) и q = min{cij-}>0. Матрицу пропускных способностей (cij) изменить следующим образом:

(а) вычесть q из всех cij- ;

(б) прибавить q ко всем cij+ .

Заменить текущую cij-матрицу на вновь полученную и перейти к шагу 1.

Операция (а) дает возможность использовать остатки пропускных способностей дуг выбранной цепи в направлении s®t. Операция (б) восстанавливает исходные пропускные способности сети, поскольку уменьшение пропускной способности дуги в одном направлении можно рассматривать как увеличение ее пропускной способности в противоположном направлении.

Шаг 3. Найти максимальный поток в сети. Пусть C = ççcijçç - исходная матрица пропускных способностей, и пусть C* = ççcijçç - последняя матрица, получившаяся в результате модификации исходной матрицы (шаги 1 и 2). Оптимальный поток X = ççxijçç в дугах задается как

Максимальный поток из s в t равен

При этом z есть сумма всех положительных q, определенных на шаге 2. Таким образом, можно объяснить, почему используются положительные элементы матрицы C – C* для определения результирующего потока в направлении s® t.

Литература

1.  Протосеня А.Г., Кулиш С.А., Азбель Е.И. и др. Математические методы планировании и управлении горным производством. Учебное пособие для вузов. - М.: Наука, 1985.

2.  Филлипс Д., Гарсиа-Диас А. Методы анализа сетей. -М.: Мир,1984.

3.  Пападимитриу Х., Стайглиц К. Комбинаторная оптимизация. Алгоритмы и сложность. - М.: Мир, 1985.

4.  Грешилов А.А. Как принять наилучшее решение в реальных условиях. - М.: Радио и связь, 1991.

5.  Попов Ю.Д. Линейное и нелинейное программирование. Учебное пособие. - Киев, 1988.

6.  Зайченко Ю.П. Исследование операций. Учебное пособие для студентов вузов. - Киев: Вища школа. Головное издательство, 1979

7.  Таха Х.. Введение в исследование операций: в 2-х книгах. - М.: Мир, 1985.

8.  Акоф Р., Сасиени М. Основы исследования операций. - М.: Мир, 1997.

9.  Акулич И.Л. Математическое программирование в примерах и задачах. - М.: Высшая школа, 1986.

10.   Данко. Высшая математика в примерах и задачах.

Контрольная работа.

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

Задание 1

Для изготовления трех видов продукции Р1, Р2 и Р3 используют четыре вида ресурсов S1, S2, S3 и S4. Запасы ресурсов, количество каждого ресурса, затрачиваемое на изготовление единицы продукции, прибыль, получаемая от единицы продукции, приведены в таблице.

Требуется:

a)  составить такой план производства продукции, при котором прибыль от ее реализации будет максимальной;

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

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

2)  Привести задачу к стандартному виду.

3)  Определить начальный допустимый план.

4)  Заполнить начальную симплекс-таблицу.

5)  Найти оптимальный план производства симплекс-методом. (Допускается использование ПЭВМ). Решение оформить в виде симплекс-таблиц.

6)  По оптимальной симплекс-таблице определить: ограничено ли пространство допустимых решений; единственно ли оптимальное решение задачи; есть ли у задачи вырожденные решения. Все ответы объяснить и обосновать.

7)  Определить, какие из ресурсов являются дефицитными. Почему?

8)  Определить на сколько можно увеличить запас дефицитных ресурсов, для улучшения полученного оптимального значения целевой функции.

9)  Определить, на сколько можно снизить запас некоторого ресурса при сохранении полученного оптимального значения целевой функции.

10)  Определить увеличение запаса какого из ресурсов наиболее выгодно.

11)  Определить, в каких пределах допустимо изменение коэффициентов целевой функции.

Задание 2.

Для задачи, полученной в первом задании построить двойственную. Дать экономическую интерпретацию двойственной задачи. Решить двойственную задачу. Используя соотношения двойственности, получить оптимальное решение прямой задачи.

Задание 3.

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

Задание 4.

Решить транспортную задачу.

Задание 5.

Для каждой дуги (i, j) неориентированной сети указана ее длина. Построить минимальное дерево-остов.

Задание 6.

Для каждой дуги (i, j) неориентированной сети указана ее длина. Найти кратчайший маршрут из узла 1 в узел 13.

Задание 7.

Для каждой дуги (i, j) сети указана ее пропускная способность. Найти максимальный поток из источника s в сток t.