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

БОЛЬШАЯ ЛЕНИНГРАДСКАЯ БИБЛИОТЕКА - РЕФЕРАТЫ - Методы исследования операций

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

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

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

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), в модель могут быть введены дополнительные ограничения на планируемый выпуск продукции xjxj0, условия комплектности для сборки xi : хj : xk. = bi : bj : bk для всех i, j, k и т. д.

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

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

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

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

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

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

найти

(1.5)

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

(1.6)

(1.7)

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

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

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

(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 через небазисные переменные:

, I - нецелое.

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

I=[I]+fi, ji=[ji]+fij, 0<fi<1, 0fij<1.

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

,

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

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

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

[xr]< xr<[xr]+1

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

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

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

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

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

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

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

Задание 1

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

Задание 2.

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

Задание 3.

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

Задание 4.

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

Задание 5.

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

Задание 6.

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

Задание 7.

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