На минимум 1 страница

Z < Z_п Да

Нет

8 Нет 9

abs(h)< e h = - a h

Да

10 11 Рисунок 3.7 – Алгоритм поиска

Вывод x_п-h, Z_п Останов экстремума по методу поразрядного

приближения

84-85.Отыскание кратчайших расстояний между пунктами транспортной сети. Алгоритм для реализации на компьютере

Пуск

2

Ввод n, ip n – число вершин транспортной сети

ip – признак одностороннего движения (0 – нет, 1 – да);

3 5

ip=1 Нет Ввод s_ij, s_ij –длина звеньев (вводится

; 1Е20, если звена нет)

Да

4 6

s_ij, s_ji =s_ji,

; , i¹ j ;

s_ij=0, i = j

8 16 s_ij –расстояние между пунктами i и j

Вывод s _{i j}, p _{i j} p_ij – промежуточный пункт на пути

; между i и j

9 17

Останов

10 Да S_jk k

s_{j i} > 1E19 S_ik

j S_ji i

Нет

Да 12 Нет 13

s _{i k} > 1E19 c = s _ji + s _{i k}

15 Да 14

s _{j k} = c c < s _jk

p _{j k} = i

Нет Рисунок 3.21 – Алгоритм метода поиска

кратчайших расстояний между пунктами транспортной сет

и

86.Первоначальное базисное решение по симплекс-методу для задачи линейного программирования

Основные шаги решения задачи (после представления исходной системы в стандартном виде):

31) формируется первоначальное базисное решение;

32) выражается Z через небазисные переменные;

33) проверяется базисное решение на оптимальность. Если оптимально, то на п.10;

34) проверяется задача на наличие решения. Если решения нет, то выход;

35) выбирается из небазисных переменных та, которая способна при введении ее в базис в большей степени улучшить значение целевой функции, и вводится в базис;

36) определяется базисная переменная, которая выводится из базиса;

37) алгебраически выражается вводимая в базис переменная через переменную, выводимую из базиса и другие небазисные переменные;

38) алгебраически выражаются другие базисные переменные через небазисные;

39) переход на п. 2;

40) определяются значения базисных переменных. Они являются решением задачи.

Итерационный процесс (шаги 2–9) повторяются до тех пор, пока не произойдет выход на шаге 3 или 4. Алгоритм реализации отдельных шагов при решении задачи на максимум и ограничениях типа £ следующий:

Шаг 1 состоит в назначении базисных переменных по числу ограничений в задаче. Базисные переменные x_u выражаются через небазисные x_p из равенств, в которые они входят через значимые коэффициенты. При этом небазисные переменные принимаются нулевыми. На первом шаге в качестве базисных принимаются дополнительные переменные, а в качестве небазисных – основные, т.е. и . Тогда первое базисное решение

x_m+1 = b₁;

x_m+2 = b₂;

...

x_M = b_n;

x₁ = 0;

x₂ = 0;

...

x_m = 0.

Шаг 2 – алгебраически выражается целевая функция Z через небазисные переменные

.

Шаг 3 – проверяется все ли с_p≤ 0. Если да, то решение оптимально.

Шаг 4 – оценка наличия решения. Если при х_p, имеющем с_p > 0, во всех уравнениях a_pj< 0 (j =1, 2,..., n), то решение отсутствует (выход из программы с соответствующим сообщением).

Шаг 5 – определяется та небазисная переменная, которую наиболее целесообразно ввести в базис, по максимуму положительного коэффициента в текущем выражении для целевой функции , где s– номер переменной, вводимой в базис.

Шаг 6 – определяется одна из базисных переменных для вывода ее из базиса. Для этого во всех j-х равенствах для х_s вычисляется отношение свободного члена b_j к соответствующему коэффициенту a_sj (a_sj > 0), т.е. b_j/a_sj. Минимальное из отношений указывает на j-е равенство и соответственно на выводимую переменную из базиса.

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

87.Многомерная безусловная оптимизация. Метод координатного спирального спуска

Одним из методов нулевого порядка – метод координатного спирального спуска. Основывается на поочередном приближении к решению с текущим значением шага по всем оптимизируемым переменным. Если с текущим шагом в данном направлении оптимизация вызывает " ухудшение" целевой функции, то шаг уменьшается и направление поиска меняется на противоположное. Коэффициент a_ш рекомендуется принимать равным 0.25 – 0.40. Решение продолжается до тех пор, пока шаг по модулю не станет равным или менее заданной точности решения. Алгоритм метода координатного спирального спуска приведен ниже.

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

Метод вращающихся координат (метод Розенброка) имеет следующий алгоритм (рисунок 3.13):

6) принимается начальное (текущее) приближение к решению – точка X_п1 и начальный (текущий) шаг поиска;

7) находится одним из известных методов при текущем значении шага следующее приближение – точка X_п2;

8) по линии X_п1 - X_п2 принимается новое направление поиска (производят поворот осей);

9) модифицируется шаг поиска и вдоль новых осей Z₁ и Z₂ находится следующее текущее приближение;

10) если результат с заданной точностью получен, то решение закончено или иначе по последнему и предпоследнему приближениям находится новое направление поиска и делается переход на пункт 4.

Для выполнения поворота осей используют ортогонализацию по Граму-Шмидту.

Пуск

2

Ввод m, h, a_ш, e m – число оптимизируемых переменных;

h – начальный шаг поиска; a_ш– коэффициент уменьшения

шага поиска; e – точность поиска

3

x_{п i} – начальные (текущие) приближения к решению

Ввод x_{п i},

4

Z = f(X_п)

5 12

10

Вывод x_пi,

Z, h

6 11 Нет

abs(h) > e

x_пi = x_пi + h

Да

7

Z_п = Z h = –a_ш h

8

Z = f (X) 5 13

Вывод x_пi,

x_{п m} =x_{п m} -h, Z_п, e

на min

Нет 9 Да 14

Z_п > Z Останов

88.Многомерная безусловная оптимизация. Градиентные методы. Методы случайного поиска

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

Для случайного поиска применяются метод с пересчетом, метод с парными пробами, метод по наилучшей пробе и др.

Эффективная оптимизационная процедура должна успешно решать тестовые задачи, которыми могут быть:

функция Розенброка

Х_п = (1; 1);

функция Пауэлла

Х_п = (0; 0; 0; 0);

двумерная экспоненциальная функция:

,

при k = 1 Х_п = (1; 10).

89.Методы многомерной безусловной оптимизации

Многомерная оптимизация заключается в поиске экстремума функции нескольких (n) переменных Z= f(X) = f(x₁, x₂,..., x_n).

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

90.Задача линейного программирования. Общая схема решения симплекс-методом

Для решения задачи в m-мерном пространстве применяется симплекс-метод.

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

x₂

А

7 2-е ограничение

изолиния целевой функции

В В

1-е ограничение

С

1 2 3 4 5 6 7 8 x₁

Рисунок 3.19 – Графическое решение общей задачи линейного программирования

Для применения симплекс-метода исходные данные задачи приводят к каноническому (стандартному) виду путем ввода дополнительных переменных по числу ограничений типа неравенств из общего числа n. Цель – заменить ограничения типа неравенств ограничениями типа равенств. Стандартная форма задачи имеет вид:

целевая функция

c_i = 0 для ;

ограничения

где M = m+n

и

.

Для неравенств типа £ d_ij=1 и для типа ³ d_ij= - 1.

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

20 x₁+ 25 x₂ + 1 x₃+ 0 x₄ = 175

x₁ + x₂ + 0 x₁+ 1 x₂ = 8

Z = 5 x₁+ 6 x₂ + 0 x₃+ 0 x₄ = max.

Основные шаги решения задачи (после представления исходной системы в стандартном виде):

41) формируется первоначальное базисное решение;

42) выражается Z через небазисные переменные;

43) проверяется базисное решение на оптимальность. Если оптимально, то на п.10;

44) проверяется задача на наличие решения. Если решения нет, то выход;

45) выбирается из небазисных переменных та, которая способна при введении ее в базис в большей степени улучшить значение целевой функции, и вводится в базис;

46) определяется базисная переменная, которая выводится из базиса;

47) алгебраически выражается вводимая в базис переменная через переменную, выводимую из базиса и другие небазисные переменные;

48) алгебраически выражаются другие базисные переменные через небазисные;

49) переход на п. 2;

50) определяются значения базисных переменных. Они являются решением задачи.

Итерационный процесс (шаги 2–9) повторяются до тех пор, пока не произойдет выход на шаге 3 или 4. Алгоритм реализации отдельных шагов при решении задачи на максимум и ограничениях типа £ следующий:

Шаг 1 состоит в назначении базисных переменных по числу ограничений в задаче. Базисные переменные x_u выражаются через небазисные x_p из равенств, в которые они входят через значимые коэффициенты. При этом небазисные переменные принимаются нулевыми. На первом шаге в качестве базисных принимаются дополнительные переменные, а в качестве небазисных – основные, т.е. и . Тогда первое базисное решение

x_m+1 = b₁;

x_m+2 = b₂;

...

x_M = b_n;

x₁ = 0;

x₂ = 0;

...

x_m = 0.

Шаг 2 – алгебраически выражается целевая функция Z через небазисные переменные

.

Шаг 3 – проверяется все ли с_p≤ 0. Если да, то решение оптимально.

Шаг 4 – оценка наличия решения. Если при х_p, имеющем с_p > 0, во всех уравнениях a_pj< 0 (j =1, 2,..., n), то решение отсутствует (выход из программы с соответствующим сообщением).

Шаг 5 – определяется та небазисная переменная, которую наиболее целесообразно ввести в базис, по максимуму положительного коэффициента в текущем выражении для целевой функции , где s– номер переменной, вводимой в базис.

Шаг 6 – определяется одна из базисных переменных для вывода ее из базиса. Для этого во всех j-х равенствах для х_s вычисляется отношение свободного члена b_j к соответствующему коэффициенту a_sj (a_sj > 0), т.е. b_j/a_sj. Минимальное из отношений указывает на j-е равенство и соответственно на выводимую переменную из базиса.

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

91.Задача линейного программирования. Приведение задачи к стандартному виду

типа равенств. Стандартная форма задачи имеет вид:

целевая функция

c_i = 0 для ;

ограничения

где M = m+n

и

.

Для неравенств типа £ d_ij=1 и для типа ³ d_ij= - 1.

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

20 x₁+ 25 x₂ + 1 x₃+ 0 x₄ = 175

x₁ + x₂ + 0 x₁+ 1 x₂ = 8

Z = 5 x₁+ 6 x₂ + 0 x₃+ 0 x₄ = max.

92.Задача линейного программирования. Графический метод решения

Алгоритм графического метода следующий:

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

2) строится изолиния целевой функции для произвольного ее значения;

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

Рассмотрим графическое решение на вышеприведенном примере (рисунок 3.19).

Строим линии ограничений и исключаем запрещенные области.

1 ограничение:

x₁ = 0; x₂ = 175/25 = 7;

x₂ = 0; x₁ = 175/20 = 8.75.

2 ограничение:

x₁ = 0; x₂ = 8;

x₂ = 0; x₁ = 8.

Кроме того, ограничениями являются оси координат, так как x₁ ³ 0; x₂ ³ 0.

Полученная незапрещенная область (на рисунке затемненная) – область допустимых решений.

Строим изолинию целевой функции.

Пусть Z = 30, тогда

x₁ = 0; x₂ = 5;

x₂ = 0; x₁ = 6.

Перемещая изолинию параллельно все выше и выше, находим наибольшее значение Z, когда изолиния только касается многоугольника допустимых решений и имеется хотя бы одна общая точка с ним. Точка " В", в которой x₁ = 5 и x₂ = 3 соответствует оптимальному решению поставленной задачи. Если линия уровня целевой функции касалась бы многоугольника допустимых решений не в точке, а по линии – то мы имели бы случай, когда задача имеет множество решений. Если ограничения задачи противоречивы, то задача не имеет решения (например, 1-е ограничение 20 х₁ + 25 х₂≥ 500).

При изменениях коэффициентов целевой функции оптимальное решение может изменяться. Так, например, при целевой функции вида 4 x₁ + 6 x₂ = max решение в точке А, при функции 5x₁ + 6.25 x₂ = max – множество точек отрезка [А, В], при функции 5x₁ + 5 x₂ = max – множество точек отрезка [В, C] и при функции 10x₁ + 6 x₂ = max решение в точке С.

При числе оптимизируемых параметров более двух мы имеем дело с выпуклым многогранником ограничений (при m = 3 ограничения определяются плоскостями, допустимая область – выпуклым многогранником, уровень целевой функции – плоскостью, решение – касание допустимой области плоскостью целевой функции).

Для решения задачи в m-мерном пространстве применяется симплекс-метод.

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

x₂

А

7 2-е ограничение

изолиния целевой функции

В В

1-е ограничение

С

1 2 3 4 5 6 7 8 x₁

Рисунок 3.19 – Графическое решение общей задачи линейного программирования

931.Состязательные задачи (игра двух сторон). Решение задачи при смешанных стратегиях

Состязательные задачи (игры) могут быть:

по вариантности стратегий - с чистой (применяется одна из возможных стратегий) или смешанной (если применяется несколько стратегий);

по числу применяемых стратегий – на конечные и бесконечные;

по количественному результату – с нулевой или ненулевой суммой;

по характеру взаимоотношений игроков – некооперативные (антагонистические) и кооперативные (коалиционные);

по числу сторон – двух или многих игроков;

по характеру протекания – непрерывные и дискретные;

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

Простейшей и наиболее разработанной является теория " матричных" игр двух сторон с нулевой суммой.

Исходные данные задаются в виде матрицы выигрышей c_ij (таблица 3.33).

Таблица 3.33 – Пример матрицы выигрышей

В этом примере сторона А имеет три возможные стратегии А1, А2, А3, а В – четыре (В1, В2, В3, В4). Сторона А не знает, как поступит сторона В, однако действуя наиболее целесообразно, она должна выбирать стратегию А2, которая гарантирует ей наибольший (11) из трех наименьших выигрышей (10, 11, 9).

Принято называть, что сторона руководствуется принципом максиминного выигрыша:

.

Определяемая таким образом величина (а) называется нижней ценой игры, максиминным выигрышем или максимином. Для приведенного примера а=11.

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

.

Величина (b) называется верхней ценой игры, или минимаксом. Для приведенного примера b=12.

Справедливо, что b≥ a.

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

Если а = в, то такая точка называется седловой.

Рациональные правила поведения сторон:

1. Если известна стратегия стороны В, то сторона А должна выбрать A_i, которая дает максимальный выигрыш.

2. Если стратегия В неизвестна, то сторона А должна воспользоваться своей максиминной стратегией.

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

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

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

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

Если считать, что выполнено k итераций и в результате получены оценки смешанных стратегий A_c = (A₁, A₂,..., A_k) игрока А и B_c = (B₁, B₂,..., B_k) игрока В, то на очередной итерации игроком А выбирается такая чистая стратегия, которая обеспечит ему максимум в предположении, что игрок В применит смешанную стратегию B_c. Аналогично В применяет чистую стратегию, которая дает минимум выигрыша А, если последним будет использована смешанная стратегия A_c.

Для парной игры с нулевой суммой обозначим вероятность применения стратегии A_i через p_i, а B_j через q_j (A_i – стратегия стороны А, B_j – стратегия стороны В).

Сумма вероятностей всех стратегий для каждой из сторон равна 1:

Тогда ; .

Средний выигрыш стороны А

,

где m и n – соответственно число различных стратегий сторон А и В.

Для поиска оптимума необходимо взять частные производные и приравнять их к нулю

;

.

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

Решение может быть получено реализацией итерационного процесса путем многократного имитационного моделирования игры. Например, следующей стратегией стороны А для приведенного примера является стратегия А1, дающую максимум при стратегии противоположной стороны В1, а сторона В применит стратегию В3, которая дает минимум выигрыша стороной А при ее предыдущей стратегии А2. При следующей итерации сторона А должна применить стратегию А1, дающую максимум выигрыша (14+14=28) при предыдущих стратегиях (В1, В3) противоположной стороны, а стороне В необходимо применить стратегию В3, которая дает минимум выигрыша стороной А при ее предыдущих стратегиях А2 и А1(11+14=25). Аналогично итерационный процесс моделирования проводят до равенства значений цен игры сторон с заданной точностью. Пример игры для пяти итераций приведен в таблице 3.34. Для рассматриваемого примера на 5-й итерации средняя цена игры стороны А равна 11.4 (57/5) и стороны В – 11.8 (59/5).

Таблица 3.34 – Пример моделирования игры двух сторон по алгоритму Брауна

Для решения задачи на основе итерационного алгоритма Брауна может быть использована его компьютерная реализация. Пример учебной программы приведен в приложении 11.

942.Задача СПУ. Построение схемы сетевого графика.