МЕТОДЫИССЛЕДОВАНИЯ ОПЕРАЦИЙПрограмма
Программа дисциплины«Методы исследования операций» предназначена для студентов специальности«Экономическая кибернетика».
Цель учебной дисциплины«Методы исследования операций» — вооружить студентов фундаментальнымитеоретическими знаниями и помочь сформировать практические навыки в вопросахпостановки и решения оптимизационных экономических задач методами исследованияопераций.
Дисциплина имеетпрактическую направленность относительно решения вопросов оптимальногораспределения ограниченных ресурсов, выбора оптимального варианта (объекта,проекта) из множества альтернативных вариантов и т.д.
Основное содержаниедисциплины раскрывают такие темы:
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. Заполняем начальную симплекс-таблицу.
Базисные
переменные x1 x2 S1 s2 s3 s4
Решение
В Z -3 -2 Z-уравнение s1 1 2 1 6 s1-уравнение s2 2 1 1 8 s2-уравнение s3 -1 1 1 1 s3-уравнение s4 1 1 2 s4-уравнение
Шаг 1. Условие оптимальности или правиловыбора включаемой в базис переменной. Вводимой в базис переменной в задачемаксимизации (минимизации) является небазисная переменная, имеющая в Z-строкенаибольший по модулю отрицательный (положительный) коэффициент. Если такихкоэффициентов несколько, то выбор – произвольный и после этого переходят к шагу2. Если таких коэффициентов нет, то решение оптимально.
Столбец симплекс-таблицы,соответствующий включаемой переменной, будем называть ведущим столбцом. В нашемслучае включаем в базис переменную x1.
Шаг 2. Условие допустимости или правиловыбора исключаемой из базиса переменной (одинаковое в задачах максимизации иминимизации). В качестве исключаемой из базиса переменной выбирается табазисная переменная, для которой отношение постоянной в правой частисоответствующего ограничения к положительному коэффициенту ведущего столбцаминимально. В случае равенства этого отношения для нескольких базисныхпеременных выбор делается произвольно.
Строку симплекс-таблицы,соответствующую исключаемой переменной, будем называть ведущей строкой. В нашемслучае исключаем из базиса переменную s2.
Шаг 3. Вычисляем новое базисное решение ипереходим к шагу 1.
Симплекс-таблица,соответствующая первой итерации:
Базисные
переменные x1 x2 s1 S2 s3 s4
Решение
В Z -½ 3/2 12 Z-уравнение s1 3/2 1 — ½ 2 s1-уравнение x1 1 ½ ½ 4 s2-уравнение s3 3/2 ½ 1 5 s3-уравнение s4 1 1 2 s4-уравнение
Решение не оптимально.Включаем в базис x2 вместо s1.Вторая итерация:
Базисные
переменные x1 x2 s1 s2 s3 s4
Решение
В Z 1/3 4/3 12 2/3 Z-уравнение x2 1 2/3 -1/3 4/3 s1-уравнение x1 1 -1/3 2/3 10/3 s2-уравнение s3 -1 1 1 3 s3-уравнение s4 -2/3 1/3 1 2/3 s4-уравнение
Решение оптимально.
Анализрешения на чувствительность.
Из оптимальнойсимплекс-таблицы либо непосредственно, либо при помощи простых преобразованийможно получить информацию относительно
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).
Исходной задачей дляметодов отсечений, используемых при решении линейных целочисленных задач,является задача с ослабленными ограничениями, которая возникает в результатеисключения требования целочисленности переменных. По мере введения специальныхдополнительных ограничений, учитывающих требования целочисленности,многогранник допустимых решений ослабленной задачи постепенно деформируется дотех пор, пока координаты допустимого решения не станут целочисленными. Название«методы отсечений» связано с тем обстоятельством, что вводимые дополнительныеограничения отсекают (исключают) некоторые области многогранника допустимыхрешений, в которых отсутствуют точки с целочисленными координатами,
В основе комбинаторныхметодов лежит идея перебора всех допустимых целочисленных решений, разумеется,на первый план здесь выдвигается проблема разработки тестовых процедур,позволяющих непосредственно рассматривать лишь относительно небольшую частьуказанных решений, а остальные допустимые решения учитывать некоторым косвеннымобразом. Наиболее известным комбинаторным методом является метод ветвей играниц, который также опирается на процедуру решения задач с ослабленнымиограничениями. При таком подходе из рассматриваемой задачи получаются двеподзадачи путем специального «разбиения» пространства допустимых решений иотбрасывания областей, не содержащих допустимых целочисленных решений.
В случае, когдацелочисленные переменные являются булевыми, применяются комбинированные методы.Булевы свойства переменных существенно упрощают поиск решения.
Алгоритм метода отсеченийдля решения полностью целочисленной задачи.
Необходимым условиемприменения данного алгоритма является целочисленность всех коэффициентов иправых частей ограничений исходной задачи. Любое ограничение с рациональнымикоэффициентами легко приводится к требуемому виду путем умножения ограниченияна наименьший общий знаменатель входящих в него коэффициентов.
Алгоритм состоит вследующем. На первом шаге решается задача с ослабленными ограничениями, несодержащая условий целочисленности переменных. Если полученное оптимальноерешение оказывается целочисленным, то оно является также решением исходнойзадачи. В противном случае следует ввести дополнительные ограничения,порождающие (вместе с некоторыми ограничениями) новую задачу линейногопрограммирования, решение которой оказывается целочисленным и совпадает соптимальным решением исходной целочисленной задачи. Пусть последняясимплекс-таблица задачи с ослабленными ограничениями имеет следующий вид:Базисные переменные x1 … xi … xm w1 … wj … wn Решение Z … … C1 … Cj … Cn b0 x1 1 … … a11 … aj1 … an1 b1 … … … … … … … … … … … … xi … 1 … a1i … aji … ani bi ... … … … … … … … … … … … xm … … 1 a1m … ajm … anm bm
Рассмотрим i-ую строку,которой соответствует нецелое значение базисной переменной xi,и выразим xi черезнебазисные переменные:
/>,bI –нецелое.
Каждую строку симплекс-таблицы, порождающую аналогичное равенство будемназывать производящей строкой. Так как коэффициенты целевой функции можносчитать целыми числами, переменная Z также должна бытьцелочисленной, и верхняя строка таблицы также может быть выбрана в качествепроизводящей. Пусть
bI=[bI]+fi,aji=[aji]+fij,0
В качестве дополнительного ограничения вводим такое
/>,
где Si – неотрицательная дополнительная переменная, котораяпо определению должна принимать целые значения. Такое ограничение равенствоопределяет отсечение Гомори для полностью целочисленной задачи. Добавивпостроенное ограничение в симплекс-таблицу, получим недопустимое, нооптимальное решение. В такой ситуации следует использовать двойственныйсимплекс-метод для получения допустимого и оптимального решения.
Методветвей и границ.
На первом шаге такжерешается задача с ослабленными ограничениями, не содержащая условийцелочисленности переменных. Но в отличие от методов отсечений этот метод можетприменяться как для полностью целочисленной задачи, так и для частичноцелочисленной. Если полученное оптимальное решение оказывается целочисленным,то оно является также решением исходной задачи. Идея метода заключается вследующем. Пусть xr целочисленнаяпеременная, значение которой xr воптимальном решении ослабленной задачи является дробным. Интервал
[xr]
не содержит допустимыхцелочисленных компонент решения. Поэтому допустимое целое значение 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. Запасы ресурсов, количествокаждого ресурса, затрачиваемое на изготовление единицы продукции, прибыль,получаемая от единицы продукции, приведены в таблице. Вид ресурса Запас ресурса Число единиц ресурса, затрачиваемых на изготовление единицы продукции Р1 Р2 Р3 S1 B1 A11 A12 A13 S2 B2 A21 A22 A23 S3 B3 A31 A32 A33 S4 B4 A41 A42 A43 Прибыль, получаемая от единицы продукции C1 C2 C3
Требуется:
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.