Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Операцией называется всякое мероприятие, объединенное единым замыслом и направленное к достижению какой-то цели.
Операция есть всегда управление мероприятием, т.е. имеется возможность распорядиться способом выбора некоторых параметров, характеризующих ее организацию. Эти параметры называют управляемыми параметрами.
Всякий определенный выбор таких переменных называют решением. Решения могут быть удачными и неудачными, разумными и неразумными.
Оптимальным называется такие решения, которые по некоторым критериям оптимальные других.
Цель исследования операций - предварительное количественное обоснование оптимальных решений, которых может быть более одного.
2. Общая постановка задачи исследования операций
Важно усвоить методологию построения моделей задач исследования операций. Все факторы, входящие в описание операции, можно разделить на две группы:
• постоянные факторы (условия проведения операции), на которые мы влиять не можем. Обозначим их через α1, α2, ...;
• зависимые факторы (элементы решения) x
1, х2, ...; которые в известных пределах мы можем выбирать по своему усмотрению.
Критерий эффективности, выражаемый некоторой функцией, называемой целевой, зависит от факторов обеих групп, поэтому целевую функцию Z можно записать в виде
Z = f(x1, х2, ..., α1, α2,...)
Все модели исследования операций могут быть классифицированы в зависимости от природы и свойств операции, характера решаемых задач, особенностей применяемых математических методов.
3.Экономико – математическое моделирования. Основные понятия и определения.
Под моделью понимается либо некий образ объекта, интересующего нас, либо прообраз некоторого объекта или системы объектов. Под моделированием понимается конструирование модели и работа с ней, состоящие из ряда последовательных и взаимосвязанных стадий: постановка задачи, построение модели, ее исследование, проверка и оценка полученного на основе модели решения, реализация результатов решения. Экономическая модель - аналог совокупности производственных отношений, определенной общественно - экономической формаций, свойства которых и отношения между которыми описаны математическим методом. Модели можно классифицировать по разным признакам:
-по характеру моделируемых объектов; -по сферам приложения; -по средствам моделирования
Макроэкономические модели описывают экономику как единое целое со связями между агрегированными материальными и финансовыми показателями (ВВП, потребление, инвестиции, занятость, денежная масса, государственный долг, инфляция и др.).Равновесные модели описывают такие состояния экономики, когда результирующая всей воздействий на нее равна нулю. Как правило, равновесные модели являются описательными.
Линейное программирование – это направление математического программирования, изучающее методы решения экстремальных задач, которые характеризуются линейной зависимостью между переменными и линейным критерием. Задачами нелинейного программирования называются задачи математического программирования, в которых нелинейны и (или) целевая функция, и (или) ограничения в виде неравенств или равенств. Задачи нелинейного программирования на практике возникают довольно часто, когда, например, затраты растут не пропорционально количеству закупленных или произведённых товаров.
Динамическое программирование — это вычислительный метод для решения задач определенной структуры. В упрощенной формулировке динамическое программирование представляет собой направленный последовательный перебор вариантов, который обязательно приводит к глобальному максимуму Теория графов. Граф это множество точек или вершин и множество линий или ребер, соединяющих между собой все или часть этих точек.
· Вершины, прилегающие к одному и тому же ребру, называются смежными.
· Если ребра ориентированы, что обычно показывают стрелками, то они называются дугами, и граф с такими ребрами называется ориентированным графом.
· Если ребра не имеют ориентации, граф называется неориентированным.
5. Постановка задачи линейного программирования.
Общая постановка задачи Линейное программирование — наука о методах исследования и отыскания экстремальных (наибольших и наименьших) значений линейной функции, на неизвестные которой наложены линейные ограничения.Эта линейная функция называется целевой, а ограничения, которые математически записываются в виде уравнений или неравенств, называются системой ограничений.
Математическое выражение целевой функции и ее ограничений называется математической моделью экономической задачи.
В общем виде математическая модель задачи линейного программирования (ЛП) записывается как
Z(x)=C1X1+C2X2 + . . . +СJXJ+. . . +СnXn_ max (min)
1) Запись ЗЛП с помощью линейных неравенств и уравнений, каждые используются при составлении конкретных моделей задач.
2) Матричная форма записи, каждая используется как краткая форма записи для задач, представленных в симметричном виде. max z=CX, AX=B, X≥0, где X – столбик всех x, С – строка коэффициентов при x в целевой функции, А – все коэффициенты при x в ограничениях, В – столбик правых частей в ограничениях, 0 – столбик нулей
3) Векторная форма записи: вводят векторы-столбцы при каждой переменной в системе уравнений и вектор-столбец из правых частей уравнения, а также вектор-строчку из коэффициентов при переменных целевой функции. max z=cx, px1+px2+…+pxn=b, x≥0, где p – столбики коэффициентов перед соответствующей переменной в ограничениях, х – строчка из всех х, остальное – как в матрицах
7.Двойственная задача линейного программирования
Каждая задача линейного программирования, называемая прямой или исходной, тесно связана с другой задачей, ее называют двойственной.
Математические модели этих задач имеют следующий вид.
|
прямая задача: |
двойственная задача: |
Прямая задача: сколько и какой продукции хi(i-1, 2, … , n) надо произвести, чтобы при заданных стоимостях единицы продукции Сi, объемом имеющихся ресурсов bj (j=1,2,…, m) и нормах расхода ресурсов аij максимизировать выпуск продукции в стоимостном виде.
Двойственная задача: какова должна быть оценка единицы каждого ресурса yj (j=1, 2,…, m), чтобы при заданных bj, ci и аijминимизировать общую оценку затрат на все ресурсы.
8. Первая и вторая теоремы двойственности
Основная теорема двойственности даёт правило нахождения оптимального решения двойственной задачи о оптимальному решению исходной задачи. Для нахождения оптимального решения двойственной задачи необходимо найти оптимальное решение исходной задачи симплекс-методом. Оптимальное значение двойственной переменной равно соответствующей оценке последней симплекс-таблицы плюс коэффициент целевой функции исходной задачи.
Вторая теорема двойственности (О равновесии). Теорема верна для симметричных двойственных задач. Для остальных задач можно применять только для ограничений в виде неравенств и для неотрицательных переменных. Рассмотрим стандартную ЗЛП.
9. Третья теорема двойственности:
Двойственные оценки показывают приращение функции цели, вызванное малым изменением свободного члена соответствующего ограничения задачи линейного программирования, т.е.
В последнем выражении дифференциалы заменим приращениями. Тогда получим выражение:, если , тогда , Экономическое содержание третьей теоремы двойственности: двойственная оценка численно равна изменению целевой функции при изменении соответствующего ресурса на единицу. Двойственные оценки yjчасто называются скрытыми теневыми или маргинальными оценками ресурсов.
В линейном программировании используется графический метод, с помощью которого определяют выпуклые множества (многогранник решений). Если основная задача линейного программирования имеет оптимальный план, то целевая функция принимает значение в одной из вершин многогранника решений Решение задачи линейного программирования графическим методом включает следующие этапы:
11. Симплекс-метод решения задач линейного программирования
Симплексный метод – метод последовательного улучшения плана.
Метод является универсальным, так как позволяет решить практически любую задачу линейного программирования. Математическая модель задачи приводится к каноническому (стандартному) виду. Заполняется опорная симплекс – таблица с использованием коэффициентов целевой функции и системы ограничений. Решается задача по алгоритму.
Идея симплексного метода заключается в том, что начиная с некоторого исходного опорного решения, осуществляется последовательно направленное перемещение по допустимым решениям к оптимальному. Значение целевой функции для задач на максимум не убывает. Так как число допустимых решений, конечно, то через конечное число шагов получим оптимальное решение.
общая схема решения задач симплекс-методом: 1) привести ЗЛП к стандартному виду; 2) привести ЗЛП к каноническому виду, если это возможно, что позволяет найти одно из опорных решений – первоначальное (одна из вершин многогранника). Если задача имеет решение, то 3) проверяем полученный опорный план на оптимальность. Если оптимальный, то задача решена, если нет, то 4) строим новый опорный план. Опорный план является оптимальным, если все коэффициенты при свободных переменных в целевой ф-ции в каноническом виде являются неположительными..
Для решения ЗЛП или линейных моделей используются специальные таблицы, которые называются симплексными и которые являются расширением таблиц Жордана-Гаусса для решения системных линейных уравнений.
Расчеты так же, как в обычном симплекс-методе, но Z строчку можно рассчитать так: Zj-Cj.
Если в симплекс-таблице, содержащей некоторый опорный план, все элементы f-строки (не считая свободного члена) неотрицательны, то этот опорный план является оптимальным.. Пусть в f-строке табл. 2.b0j> (i=1, ..., n — m). В опорном плане х0, содержащемся в этой таблице, значения всех свободных переменных xm+j равны нулю и f(х0) =b00. Если же увеличивать какую-либо из свободных переменных xm+j, то, как видно из равенства (2.5), в силу неотрицательности b0j значение f(х) начнет уменьшаться. Следовательно, при xо функция f(х) достигает наибольшей величины, а значит, х0действительно является оптимальным опорным планом.
14. Транспортная задача. Постановка задачи
Однородный груз сосредоточен у m поставщиков в объемах а1, а2, …, аm.
Данный груз необходимо доставить n потребителям в объемах, b1, b2, … , bn.
Известен Сij (i= 1, 2, … , m; j=1, 2 ,…, n) – стоимости перевозки единицы груза от каждого i-го поставщика каждому j-му потребителю.
Требуется составить такой план перевозок, при котором запасы всех поставщиков вывозятся полностью, запросы всех потребителей удовлетворяются полностью и суммарные затраты на перевозку всех грузов минимальны. Исходные данные транспортной задачи записываются в таблице вида:
Переменными (неизвестным) транспортной задачи являются xij(i=1,2,…,m; j=1,2,…,n) – объемы перевозок от каждого i-го поставщика j-му потребителю. Эти переменные могут быть записаны в виде матрицы перевозок.
15. Транспортная задача. Математическая модель транспортной задачи.
Математическая модель транспортной задачи в общем виде имеет вид:
Целевая функция задачи Z(X) выражает требование обеспечить минимум суммарных затрат на перевозку всех грузов. Вторая группа из уравнений ограничений, записанных в общем виде, выражает требование, что запасы всех m, поставщиков вывозятся полностью, а также полностью должны удовлетворятся запросы всех n потребителей. Последнее неравенство является условием не отрицательности всех переменных.
16. Транспортная задача открытого и закрытого типа. Математическая модель двойственной задачи.
В математической модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.такая задача называется сбалансированной, а её модель закрытой. Если же это равенство не выполняется, то задача называется несбалансированной, а её модель – открытой.Для того чтобы транспортная задача линейного программирования имела решение, необходимо, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей, т.е. задача должна быть сбалансированной.
Математическая модель двойственной задачи:
если целевая функция Z’ стремится к минимуму, то в системе ограничении меняется знак: .
17. Определения транспортной задачи.
Определения:
Если задача открыта, то необходимо добавить фиктивного поставщика или потребителя с недостающим объемом поставки и нулевой стоимостью перевозки. Распределение поставки фиктивному потребителю, идет в последнюю очередь.
Клетка в плане перевозок называется базисной, если в нее ставится перевозка.
Количество базисных клеток определяется соотношением r=m+n-1. опорное решение не может иметь базисных клеток больше, чем r.
План называется вырожденным, если количество базисных клеток меньше r. В этом случае необходимо добавить нулевую перевозку.
Если в задаче указана не только стоимость перевозки, но и стоимость производства товара, тогда необходимо сложить эти стоимости с учетом перевозки товара от i-гопоставщика j-мупотребителю. Кроме того, математическая модель составляется с учетом этой суммарной стоимости.
18. Алгоритм решения транспортных задач. Метод наименьшего элемента
Алгоритм решения транспортных задач.
Метод наименьшего элемента.
19. Метод потенциалов.
Метод потенциалов.
Если в математической модели целевая функция на максимум (Zmax), то задача решается методом максимального элемента. В методе потенциалов проверяется выполнение неравенства .
20. Целочисленное программирования. Постановка задачи целочисленного программирования.
В ряде экономических задач, относящихся к задачам линейного программирования, элементы решения должны выражаться в целых числах. В этих задачах переменные означают количество единиц неделимой продукции. Задача целочисленного программирования формулируется следующим образом:
Найти такое решение план Х=(х1, х2,…, хn), при котором линейная функция принимает максимальное или минимальное значение при ограничениях
задача решается методами линейного программирования. В случае если переменные оптимального решения оказываются нецелочисленными, то, применяя методы отсечения или метод перебора целочисленных решений.
21.Метод ветвей и границ.
Метод ветвей и границ заключается в упорядоченном переборе вариантов и рассмотрении лишь тех из них, которые оказываются по определенным признакам перспективными, и отбрасывании бесперспективных вариантов.
Метод ветвей и границ состоит в следующем: множество допустимых решений некоторым способом разбивается на подмножества, каждое из которых этим же способом снова разбивается на подмножества. Процесс продолжается до тех пор. Пока не получено оптимальное целочисленное решение исходной задачи.
Название метода ветвей и границ исходит из того, что в процессе решения задача последовательно «ветвится», заменяясь более простыми. Процесс решения можно продолжать в виде дерева, цифры в узлах которого обозначают план решения задачи.
22. Графический метод решения задачи целочисленного программирования. Алгоритм.
При наличии в задаче линейного программирования двух переменных, а в системе ограничения – неравенств, она может быть решена графическим методом без требований целочисленных переменных.
Если оптимальное решение этой задачи является целочисленным, то оно и является оптимальным для исходной задачи.
Если же полученное оптимальное решение не целочисленное, то строится дополнительное линейное ограничение. Оно обладает следующими свойствами:
Алгоритм графического решения задачи целочисленного программирования.
23. Задача коммивояжера.
Имеется необходимость посетить n городов в ходе деловой поездки. Спланировать поездку нужно так, чтобы, переезжая из города в город, побывать в каждом не более одного раза и вернуться в исходный город. Определить оптимальный маршрут посещения городов и его минимальное расстояние.
Задана матрица расстояний между городами cij.
Сформулированная задача - задача целочисленная. Пусть хij = 1 , если путешественник переезжает из i -ого города в j-ый и хij = 0, если это не так.
Формально введем (n+1) город, расположенный там же, где и первый город, т.е. расстояния от (n+1) города до любого другого, отличного от первого, равны расстояниям от первого города. При этом, если из первого города можно лишь выйти, то в (n+1) город можно лишь придти.
Введем дополнительные целые переменные, равные номеру посещения этого города на пути. u1 = 0, un+1 = n . Для того, чтобы избежать замкнутых путей, выйти из первого города и вернуться в (n+1) введем дополнительные ограничения, связывающие переменные xij и переменные ui.( ui целые неотрицательные числа).
Математическая модель
24.Динамическое программирование. Постановка задачи.
Динамическое программирование – раздел оптимального программирования (оптимального управления), в котором процесс принятия решения и управления, может быть разбит на отдельные этапы (шаги).
Динамическое программирование позволяет свести одну сложную задачу со многими переменными ко многим задачам с малым числом переменных.
Управление – совокупность решений, принимаемых на каждом этапе для влияния на ход развития процесса.
Операция – управляемый процесс, т.е. мы можем выбирать какие-то параметры, влияющие на ход процесса и управлять шагами операции, обеспечивать выигрыши на каждом шаге и в целом за операцию.
Решение на каждом шаге называется «шаговым управлением».
Совокупность всех шаговых управлений представляет собой управление операцией в целом.
При распределении средств между предприятиями шагами целесообразно считать номер очередного предприятия; при распределении на несколько лет ресурсов деятельности предприятия – временной период. В других задачах разделение на шаги вводится искусственно.
Требуется найти такое управление (х), при котором выигрыш обращался бы в максимум:
F(x)=
В общем случае шаговые управления (х1, х2, … хm) могут стать числами, векторами, функциями.
То управление (х*), при котором достигается максимум, называется оптимальным управлением. Оптимальность управления состоит из совокупности оптимальных шаговых управлений х* = х*1, х*2, … х*m
F* = max {F*(х*)} – максимальный выигрыш, который достигается при оптимальном управлении х*.
Исходя из условий, каждой конкретной задачи длину шага выбирают таким образом, чтобы на каждом шаге получить простую задачу оптимизации и обеспечить требуемую точность вычислений.
25. Принцип оптимальности Беллмана.
Основным методом динамического программирования является метод рекуррентных соотношений; который основывается на использовании принципа оптимальности, разработанного американским математиком Р. Беллманом.
Суть принципа:
Каковы бы ни были начальное состояние на любом шаге и управление, выбранное на этом шаге, последующие управления должны выбираться оптимальными относительно состояния, к которому придет система в конце каждого шага.
Использование данного принципа гарантирует, что управление, выбранное на любом шаге, не локально лучше, а лучше с точки зрения процесса в целом.
Условная оптимизация
Безусловная оптимизация
Задача динамического программирования начинает решаться с конца, т.е. с последнего шага. Решается задача в 2 этапа:
1 этап (от конца к началу по шагам): Проводится условная оптимизация, в результате чего находится условные оптимальные управления и условные оптимальные выигрыши по всем шагам процесса.
2 этап (от начала к концу по шагам): Выбираются уже готовые рекомендации от 1-го шага до последнего и находится безусловное оптимальное управление х*, равный х*1, х*2, …, х*m.
26.Формулировка задачи и характеристики СМО
Ожидание является следствием вероятностного характера возникновения потребностей в обслуживании и разброса показателей обслуживающих систем, которые называют системами массового обслуживания (СМО).
Цель изучения СМО состоит в том, чтобы взять под контроль некоторые характеристики системы, установить зависимость между числом обслуживаемых единиц и качеством обслуживания. Качество обслуживания тем выше, чем больше число обслуживаемых единиц. Но экономически невыгодно иметь лишние обслуживающие единицы.
В промышленности СМО применяются при поступлении сырья, материалов, комплектующих изделий на склад и выдаче их со склада; обработке широкой номенклатуры деталей на одном и том же оборудовании; организации наладки и ремонта оборудования; определении оптимальной численности обслуживающих отделов и служб предприятий и т.д.
Основными элементами СМО являются источники заявок; их входящий поток; каналы обслуживания и выходящий поток.
В зависимости от характера формирования очереди СМО различают:
системы с отказами, в которых при занятости всех каналов обслуживания заявка не встает в очередь и покидает систему необслуженной;
системы с неограниченными ожиданиями, в которых заявка встает в очередь, если в момент ее поступления все каналы были заняты.
системы смешанного типа с ожиданием и ограниченной длиной очереди: заявка получает отказ, если приходит в момент, когда все места в очереди заняты. Заявка, попавшая в очередь, обслуживается обязательно.
По числу каналов обслуживания СМО делятся наодноканальные и многоканальные.
В зависимости от расположения источника требований, системы могут быть разомкнутыми и замкнутыми.
27.СМО с отказами.
Основные понятия
Заявка, поступившая в систему с отказами и нашедшая все каналы занятыми, получает отказ и покидает систему необслуженной. Показателем качества обслуживания выступает вероятность получения отказа. Предполагается, что все каналы доступны в равной степени всем заявкам, входящий поток является простейшим, длительность обслуживания одной заявки (tобс) распределена по показательному закону.
Формулы для расчета установившегося режима
1. Вероятность простая каналов обслуживания, когда нет заявок (k=0):
N P0=1/(Σρk / k!)
k=0
2. Вероятность отказа в обслуживании, когда поступившая на обслуживание заявка найдет все каналы занятыми (k=n):
Pотк= Pn =P0ρn / n
3. Вероятность обслуживания: Робс= 1- Pотк_
4. Среднее число занятых обслуживанием каналов: _ n3=ρ Робс
5. Доля каналов, занятых обслуживанием: k3= n3/n
6. Абсолютная пропускная способность СМО: A=λ Робс
28.СМО с неограниченным ожиданием
Основные понятия
Заявка, поступившая в систему с неограниченным ожиданием и нашедшая все каналы занятыми, становится в очередь, ожидая освобождения одного из каналов.
Основной характеристикой качества обслуживания является время ожидания. Для таких систем характерно отсутствие отказа в обслуживании, т.е.Pотк=0 и Робс=1.
Для систем с ожиданием существует дисциплина очереди:
обслуживание в порядке очереди по принципу «первым пришел – первым обслужен»;
случайное неорганизованное обслуживание по принципу «последний пришел - первым обслужен»;
обслуживание с приоритетами по принципу «генералы и полковники вне очереди».
Формулы для расчета установившегося режима
1. Вероятность простоя каналов, когда нет заявок (k=0):
n P0=1/Σ(ρк/к!)+ρn+1/n!(n-ρ) k=0
Предполагается, что ρ/n<1, т.е. интенсивность нагрузки меньше числа каналов.
2. Вероятность занятости обслуживанием k заявок: Pk= ρкP0/k!, 1≤ k≤ n
3. Вероятность занятости обслуживанием всех каналов: Pn =P0ρn / n!
4. Вероятность того, что заявка ожидается в очереди: Роч= ρn+1/n!(n-ρ)* P0
5. Среднее число заявок в очереди: Lоч= ρn+1/(n+λ)!(n-ρ)2* P0
6. Среднее время ожидания заявки в очереди: tоч= Lоч/λ
7. Среднее время ожидания заявки в СМО: tсмо= tоч+ tобс
8. Среднее число занятых обслуживанием каналов: n3=ρ
9. Среднее число свободных каналов: nсв= n- n3
10. Коэффициент занятости каналов обслуживания: k3= n3/ n
11. Среднее число заявок в СМО: z= Lоч+ n3
29.СМО с ожиданием и с ограниченной длиной очереди
Основные понятия
Заявка, поступившая в систему с ожиданием с ограниченной длиной очереди и нашедшая все каналы и ограниченную очередь занятыми, покидает систему необслуженной.
Основной характеристикой качества системы является отказ заявке в обслуживании.
Ограничения на длину очереди могут быть из-за:
Формулы для установившегося режима
1. Вероятность простоя каналов, когда нет заявок (k=0): P0=1 : {Σρк/к!+ρn+1/n!(n-ρ)[1-(ρ/n)m]}
2. Вероятность отказа в обслуживании: Pотк= ρn+m/n!nm*P0
3. Вероятность обслуживания: Робс= 1- Pотк
4. Абсолютная пропускная способность: A=λ Робс
5. Среднее число занятых каналов: n3=A/μ= λ Робс/μ=ρРобс, где ρ=λ/ μ
6. Среднее число заявок в очереди: Lоч= ρn+1/n*n! * 1-(ρ/n)m(m+1-mρ/n) / (1-ρ/n)2 * P0
7. Среднее время ожидания обслуживания: tоч= Lоч/λ
8. Среднее число заявок в системе: z= Lоч+ n3
9.Среднее время пребывания в системе: tсмо= z/λ
30.Сетевое планирование. Основные понятия метода сетевого планирования
При сетевом планировании определяются оценки продолжительности операций, и строится сетевая модель – сетевой график.
Сетевой график (сетевая модель) – графическое изображение плана выполнения комплекса работ, состоящего из нитей и узлов, которые отражают логическую взаимосвязь всех операций.
В основе сетевого планирования лежит изображение планируемого комплекса работ в виде графа.
Граф – схема состоящая из заданных точек, соединенных системой линий.
Ориентированным называется такой граф, на котором стрелкой указаны направления всех его ребер, что позволяет определить какая из двух его граничных вершин является начальной, а какая конечной.
Сетевой график – это ориентированный граф без контуров.
Основными элементами сетевых графиков являются: работа, события, путь.
РАБОТА – это активный процесс, требующий затрат ресурсов, либо пассивный, приводящий к достижению намеченного результата. ФИКТИВНАЯ РАБОТА – это связь между результатами работ, не требующая затрат времени и ресурсов, т.е. имеющая нулевую продолжительность.
СОБЫТИЕ – это результат выполнения одной или нескольких предшествующих работ. ПУТЬ – любая непрерывная последовательность работ и событий. КРИТИЧЕСКИЙ ПУТЬ – это путь не имеющий резервов работы комплекса.Работы, расположенные на критическом пути, называют критическими.
Все остальные работы являются некритическими (ненапряженными) и обладают резервами времени, которые позволяют передвигать сроки их выполнения, не влияя на общую продолжительность выполнения всего комплекса работ. ОЖИДАНИЕ – процесс, требующий затрат времени, но не требующий затрат ресурсов. Понятие СОБЫТИЕ отличается от понятия РАБОТЫ тем, что не является процессом и не связано с затратами времени и ресурсов (разработка сметы закончена, ресурс принят, сборка узла машины завершена).
31.Расчет сетевых графиков
Алгоритм расчета сетевого графика.
Для начального события 1 назначается tp1=0.
Достигаемая от начального события графика к конечному.
Последовательно просматриваются события в порядке возрастания их кодов и вычисляются ранние сроки свершения событий по формуле tpj=max(tpi+tpj). Если в событие j входит несколько дуг, то по каждой их них вычисляется величина tpi+tij и в качестве tpjпринимается большая из рассчитанных величин.
Для конечного события графика (код его обозначим k) назначается tnk=tpk – поздний срок свершения конечного события равен раннему сроку свершения этого события.
Двигаемся от конечного события графика к начальному. Просматриваются события в порядке убывания их кодов и вычисляются поздние сроки свершения событий по формуле: tni=min(tnj-tij). Если из события i выходит несколько дуг. То по каждой их них вычисляется величина tnj-tij и в качестве tnjпринимается меньшая. Если расчет произведен без ошибок, то для начального события графика должно оказаться tn1=0.
Формулы для вычислений по работам:
tpnij=tpi; tnoij=tnj;
tpoij=tpi+ tij; Rnij= tnj- tpi- tij;
tnнij=tnj- tij; Rчij= tpj- tpi- tij.
Можно ограничится расчетом на графике. Иногда результаты расчета показывают в таблице.
|
i |
j |
tij |
tpnij |
tpoij |
tnнij |
tnoij |
Rnij |
Rчij |
32.Нелинейное программирование.
Основные понятия.
Во многих оптимизационных задачах целевая функция, или функции, задающие ограничения, не являются линейными. Такие задачи называются задачами нелинейного программирования.
Пример простой нелинейной задачи:
Предприятие для производства какого-то продукта расходует два средства в количестве х и y соответственно. Это факторы производства, например, машины и труд, два различных вида сырья и т.п., а х и y – затраты факторов производства.
Факторы производства считаются взаимозаменяемыми. Если это «труд» и «машины», то можно применять такие методы производства, при которых величина затрат в сопоставлении с величиной затрат труда оказывается больше или меньше (производство более или менее трудоемкое).
Объем производства, выраженный в натуральных или стоимостных единицах, является функцией затрат производства
Z = f (х, y). Эта зависимость называется производственной функцией.
Совокупные издержки выражаются формулой с1х1 + с2y2 = в.
Требуется при данных совокупных издержках определить количество факторов производства, которое максимизирует объем продукции Z.
Математическая модель задачи:
Определить такие переменные х и у, удовлетворяющие условиям
с1х1+с2у=в, х≥0, у≥0,
при которых функция z=f(х, у) достигнет максимума.
Ограничения могут отсутствовать. В этом случае производится безусловная оптимизация задачи. Как правило, функция z может иметь произвольный нелинейный вид. В теории нелинейной оптимизации выделяют понятие локального экстремума (локального минимума, локального максимума), глобального экстремума, условного экстремума.
Понятие условного экстремума вводится для случая, когда число переменных n не меньше 2 (n≥2).
Задачи нелинейного программирования делятся на два класса: имеющие безусловный экстремум и имеющие условный экстремум в зависимости от того есть ли дополнительные условия или нет.
33. Условий и безусловий экстремум
Безусловный экстремум
Рассмотрим задачу безусловного экстремума.
Найти экстремум функции z=х²+ху+у²-2х-3у.
Найдем частные производные.
Первая производная по х: z׳х=2х+у-2
Первая производная поу: z׳у=х+2у-3
Решим систему уравнений. 2х+у=2
х+2у=3 Получаем критическую точку (1/3; 4/3).
Найдем вторые частные производные.
Вторая производная по х: z׳׳хх=2
Вторая производная по у: z׳׳уу=2
Смешанные производные z׳׳ху=z׳׳ух=1
Составим определитель 2 1
1 2 = 4-1=3
Следовательно, экстремум есть. Так как z=2>0, то в точке (1/3; 4/3) точка минимума.
Условный экстремум
Задача на минимум. Определить матрицы L и все ее главные миноры порядка больше чем m+1 должны иметь знак (-1)m, где m – число ограничений задачи.
Задача на максимум. Определить матрицы L должен иметь знак (-1)n, где n – число переменных в задаче. Главный минор порядка m+n-1 должен иметь противоположный знак. Последующие миноры должны иметь чередующие знаки.
34.Теория игр.Основные понятия.
Теория игр - это математическая теория, исследующая конфликтные ситуации, в которых принятие решений зависит от нескольких участников.
Математическая модель конфликтной ситуации называется игрой. Стороны, участвующие в конфликте - игроки, а исход конфликта - выигрыш (проигрыш). Выигрыш или проигрыш может быть задан количественно.
Игра называется антагонистической или игрой с нулевой суммой, если выигрыш одного из игроков равен проигрышу другого, поэтому для полного «задания» игры достаточно указать величину выигрыша первого игрока.
Стратегией игрока называется совокупность принципов, определяющих выбор его действий при каждом личном ходе в зависимости от сложившейся ситуации.
Для того чтобы найти решение игры, следует для каждого игрока выбрать стратегию, которая удовлетворяет условию оптимальности, т.е. один из игроков должен получать максимальный выигрыш, когда второй игрок придерживается своей стратегии. В тоже время второй игрок должен иметь минимальный проигрыш, если первый придерживается своей стратегии.
Такие стратегии называются оптимальными.
35.Антагонистические игры.
Прежде всего, надо уметь находить верхнюю и нижнюю цены игры, т.к. достаточно много игр решается в чистых стратегиях.
Общее значение нижней и верхней цены игры α = β = ν называется чистой ценой игру. Седловой точке соответствует пара минимаксных стратегий, эти стратегии называются оптимальными, а их совокупность - решением игры.
Если седловой точки нет, то можно применить графический способ или составить модель и решить симплекс-методом.
Геометрический способ решения игр с нулевой суммой применяется к играм, где хотя бы у одного игрока только две стратегии. Иногда возможно упростить игры, применяя следующие принципы:
1. Игрок А стремится увеличить свой выигрыш, поэтому он не будет использовать стратегии, которые заведомо дают ему меньшие суммы;
2. Игрок Встремится уменьшить свой проигрыш, поэтому он не будет использовать стратегии, которые заведомо отнимают большие суммы.
36. Игры с « природой». Критерий Вальда.
Для того чтобы можно сделать вывод о том какую именно стратегию выбирать игроку, необходимо использовать критерии Вальда, Гурвица, Сэвиджа, Лапласа, Байеса.
1. Критерий Вальда. Рекомендуется применять максиминную стратегию. Она достигается из условия maxminαijи совпадает с нижней ценой игры.ij
Критерий является пессимистическим, считается, что природа будет действовать наихудшим для человека образом, агрессивно, делать все, чтобы помешать нам достигнуть успеха.
37. Игры с природой. Критерий Гурвица. Критерий. Сэвиджа.
Для того чтобы можно сделать вывод о том какую именно стратегию выбирать игроку, необходимо использовать критерии Вальда, Гурвица, Сэвиджа, Лапласа, Байеса.
Критерий Гурвица (оптимизма - пессимизма). Критерий рекомендует при выборе решения не руководствоваться ни крайним пессимизмом (всегда рассчитывай на худшее), ни крайним легкомысленным оптимизмом (авось кривая выведет). Критерий рекомендует стратегию, определяемую по формуле
H = Max {γminaij + (1- γ)maxaij}ijj
где γ - степень оптимизма - изменяется в диапазоне [0, 1].
Критерий придерживается некоторой промежуточной позиции, учитывающей возможность как наихудшего, так и наилучшего поведения природы. При γ = 1 критерий превращается в критерий Вальда, при γ = 0 - в критерий максимума. На γ оказывает влияние степень ответственности лица, принимающего решение по выбору стратегии. Чем хуже последствия ошибочных решений, больше желания застраховаться, тем γ ближе к единице.
Критерий Сэвиджа. Суть критерия состоит в выборе такой стратегии, чтобы не допустить чрезмерно высоких потерь, к которым она может привести. Находится матрица рисков, элементы которой показывают, какой убыток понесет человек (фирма), если для каждого состояния природы он не выберет наилучшей стратегии.
Элементы матрицы рисков находится по формуле (rij):
rij= maxaij- aij
где maxaij- максимальный элемент в столбце исходной матрицы.
38. Игры с природой. Критерий Лапласа. Критерий Байеса.
Для того чтобы можно сделать вывод о том какую именно стратегию выбирать игроку, необходимо использовать критерии Вальда, Гурвица, Сэвиджа, Лапласа, Байеса.
Критерий Лапласа. Этот критерий основывается на принципе недостаточного обоснования. Поскольку вероятности состояния не известны, необходимая информация для вывода, что эти вероятности различны, отсутствует. Поэтому можно предположить, что они равны. Выбор стратегии осуществляется по формуле
H = Max {1/n·∑ aij} где 1/n вероятность реализации одного из состояний р = 1/n.
Критерий Байеса. Принятие решения в условиях риска.
Если в рассмотренных выше критериях, необходимая информация о вероятностях какого-либо состояния отсутствовала, то критерий Байеса действует в условиях не полной информации, т.е. в условиях риска (имеется информация о вероятностях применения стратегий второй стороной). Эти вероятности называются априорными вероятностями.
Выбор стратегии осуществляется по формуле H = Max {∑piaij}
В условиях полной неопределенности теория не дает однозначных принципов выбора того или иного критерия.
Оптимальные стратегии, выбранные по различным критериям, различны.
Таким образом, окончательный вывод зависит от предпочтений человека, который принимает решение.