Пример 1. осущ. с помощью болтов , сварки, заклепок

осущ. с помощью болтов, сварки, заклепок

усил. св. элем закд увелич их расч длинны и наплавкой катета шва

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

Пример 1.

Ограничение (*) означает, что мы находимся в I квадрате. (рис.3)

рис.3

Рассмотрим (1): если , то ;если , то .

Рассмотрим (2): если , то ;если , то .

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

Пример 2. Поменяем вид целевой функции (рис 4):

рис 4. В этом случае бесконечное число решений находится на отрезке .

Пример 3. (рис 5) Рассмотрим (1): если , то ;если , то .Рассмотрим (2): если , то ;если , то .

рис 5. В этом случае имеем бесконечно возрастающее решение.

Пример 4. (рис 6)

рис 6. Задача не имеет решений, так как область допустимых значений распадается на две подобласти.

2)Задача о выборе кратчайшего пути.Этап I. Имеется сеть, которая состоит из 8 городов. (рис 8)

рис 8. Города связаны друг с другом. Известна стоимость проезда по дороге, связывающей -й город с -м, т.е. . В некоторых случаях можно рассматривать вместо стоимости длину или время проезда . На некоторых участках возможны циклы, которые обозначают допустимость возможных проездов в двух направлениях. На этой сети выделим 2 города: исток - №1, из которого начинается движение, и сток - №8, в который нужно добраться. Необходимо выбрать либо самый дешевый маршрут, либо самый кратчайший путь от №1 до №8. При этом в распоряжение исследователя предоставляется граф соединения городов сетью. Указана стоимость проезда.

Этап II. Уместна матричная формулировка. Обозначим через для узлов, когда -й и узел -й не связаны. Введем переменные , если узел соединен с узлом , и в противном случае. Составим матрицу . Составим матрицу по рис.8.

Этап III. Перевод матричной форму в каноническую. Целевая функция будет иметь вид: Систему ограничений будем формировать по одному уравнению для каждого узла, и использовать по одной переменной для каждой дуги.Условие выезда из источника: .Для каждого промежуточного узла сумма входов равна сумме выходов, т.е. нет накопления в узлах. Поэтому надо приравнять суммы входов (положительные по строке) и разности выходов (отрицательные по столбцам). Для узла 7: Для узла 6: Для узла 5: Для узла 4: Для узла 3: Для узла 2: Для узла 1: (условие прибытия на конечный пункт).Ограничения: .Решение указанной системы уравнений, обеспечивающих минимум – есть решение задачи выбора кратчайшего пути.

3) Расчет параметров сетевого графика при фиксированных временах выполнения работ.

Вычисленные значения вектора характеристик, значения событий и работ заносятся на сетевой график. Расчет проводится в несколько этапов.

I. Рассчитываются наиболее ранние сроки свершения работ . Расчет производится в направлении от исходного события к завершающему. Для любого события равно длине максимального пути от исходного события в данному. Каждое -ое событие считается свершившимся лишь в том случае, когда выполнены все работы, входящие в это событие i. Если к событию входит несколько работ с известными , то . Практически при расчете свершения событий на сетевом графике последовательно переходят от исходного события (находящегося слева) к более отдаленным от него событиям, пока не придут к завершающему событию. Исходное событие равно нулю. Вычисленные значения записываются в левый сектор круга. (рис 30)

рис 30

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

рис 31

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

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

IV. Находят значение компонентов вектора по формулам , , , . (рис 32)

рис 32. Заметим, что события имеют времена с одним индексом и три характеристики (, , ), а работы – два индекса и четыре характеристики . Когда все характеристики оценок свершения событий и оценок времен выполнения работ вычислены и нанесены на сетевой график, приступают к следующему этапу.

V. Анализ параметров сетевого графика.

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

2 шаг. Определяют полный и частный резервы сетевого графика. Полным резервом называется время, в течение которого можно увеличить продолжительность работы , не изменяя при этом критический путь (и при этом «отобрать» у работы резервы, перекинув их на работу, лежащую на критическом пути). Резерв вычисляется по формуле: . Заметим, что если полный резерв времени расходуется на каком-либо пути, то все следующие работы будут иметь нулевой резерв и становятся критическими. Частный (независимый) резерв определяется временем, в течение которого можно увеличить длительности работ , не изменяя при этом раннего срока начала последующих работ. Он вычисляется по формуле: . Частный резерв образуется у работ, непосредственно предшествующих событию . В этих событиях пересекаются пути разной длины. Этот резерв показывает, какая часть полного резерва может быть использована для продолжительности этой работы и предшествующих ей работ. При этом изъятие не вызовет сокращения ни у одной из работ, которые следуют за событием .

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

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

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

Пример. (рис 33)

рис 33

4)Задача о наборе высоты и скорости самолета.Имеется транспортное средство (самолет). Он находится в состоянии . Необходимо переметить самолет в состояние при условии, что расход горючего при этом будет минимальный.Разобьем на этапы, =4, =6. В данной модели имеется одно ограничение: можно набирать либо высоту (↑), либо скорость (→).

; .Необходимо составить программу для бортового оборудования, по которой будет формироваться последовательность управляющих воздействий на это оборудование, чтобы обеспечить минимальный расход горючего для достижения самолетом состояния . Есть 2 типа управляющих воздействий: → -увеличение скорости; ↑ - увеличение высоты. (рис 34)

рис 34

В кружках записывается минимальный расход горючего, который необходим для того, чтобы добраться из исходной точки в конечную. От кружка идут стрелки: либо ↑, либо →, которые означают увеличение высоты и скорости соответственно. Начинаем с точки .

1-я итерация: видим, что имеется 2 варианта движения. Выбираем тот, где минимум расхода горючего.

2-я итерация:

…

10-я итерация:

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

5)Принцип минимакса.Пусть у игрока имеется стратегий: , у игрока имеется стратегий: . Игра представлена матрицей-игрой , , . Такая матрица имеет нормальную форму, т.к. , и называется платежной (игровой) матрицей. Она указывает «платежи» , т.е. выигрыш и проигрыш игроков и соответственно.

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

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

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

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

Смешанная стратегия для игрока : , причем .

Смешанная стратегия для игрока : , причем .

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

6) Для примера упрощения расчетов рассмотрим геометрическую интерпретацию игровых моделей.

Рассмотрим игру .

Игрок имеет стратегии . Необходимо найти оптимальную стратегию , , т.е. определить вероятности и . Составим уравнение для цены игры: Решая эту систему, получаем: ;

Решению игры можно придать простую геометрическую интерпретацию. Поскольку , то рассмотрим единичный график. (рис 36)

рис 36

На этом рисунке показаны значения выигрыша из платежной матрицы . В результате для игрока левая сторона соответствует стратегии , правая – . На этих сторонах отложим значения выигрышей соответственно по первой и второй строках. Соединим линиями точки, находящиеся на левой и правой стороне квадрата и получим стратегии и . В данном примере видим, что платежная матрица имеет седловую точку . Точка - есть нижняя цена игры, или максимин. Точка - есть верхняя цена игры, или минимакс. Седловая точка получилась на пересечении стратегий игрока . Чистая цена игры определена ординатой точки . В ней совпадает нижняя цена игры и верхняя цена игры . Отклонение игрока от своей оптимальной стратегии всегда приводит к потере выигрыша. Мы рассмотрели случай, когда седловая точка находится в центре рисунка.Рассмотрим другие примеры.(рис 37)

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

рис 38

Для игрока стратегия заведомо выгоднее, чем стратегия .

Геометрическая интерпретация показывает, имеет ли смысл применять смешанную стратегию.

Геометрическая интерпретация для игры .

Рассмотрим случай, когда .(рис 39)

рис 39

, ,

, .

Для игрока стратегии и окажутся бесполезными, т.е. заведомо проигрышными. Полезными являются стратегии и .

Геометрическая интерпретация применяется для двух целей:

1. определить ожидаемый эффект для игроков и и в соответствии с этим определить для них выбор их стратегий;

2. для применения симплекс-метода зачастую с помощью геометрического способа отбраковывают те переменные, которые являются небазовыми.

7)Задача «Полицейские и воры». Имеется универсальный магазин, в котором имеется 2 секции: и . За секциями наблюдают 2 телевизионные камеры, которые передают сигнал в телевизионную будку (), из которой можно наблюдать за ситуацией в магазине (рис 40). В секции товар дешевый, толпа густая. В секции товар дорогой, толпа редкая. Магазин обслуживают 2 полицейских. Они могут находиться:

· оба в секции с вероятностью ;

· в разных секциях с вероятностью ;

· один в секции , другой в телевизионной будке с вероятностью ;

· один в секции , другой в телевизионной будке с вероятностью ;

· оба в секции с вероятностью ;

· оба в телевизионной будке с вероятностью .

рис 40

; .

Стратегии вора:

· красть в секции : ;

· красть в секции : ; .

Очевидно, что в основе должна быть положена матрица-игра , . Путем многолетних наблюдений была положена матрица-игра.

Ставится задача: найти векторы и , которые удовлетворяют полицейских таким образом, чтобы вероятность поймать вора была не менее величины , т.е. . Вероятность вора попасться в руки полиции должна быть менее величины , т.е. . Устойчивость игры будет тогда, когда , .

Будем считать, что вероятности представляют собой вероятности поимки вора. Тогда по формуле полной вероятности независимых событий имеем 2 уравнения на две стратегии вора:

если вор крадет в секции , то ;

если вор крадет в секции , то .

Вор должен составить 6 уравнений на каждую стратегию полицейских:

Рассмотрим единичный случай.

Ответ: