Методичка
 

5

4

6

7

6

5

1

6

7

8

9

7

5

3

2

1

4

5

7

4

6

10

4

7

3

8

6

6

10

12

5

4

4

3

10

8

5

3

2

12

7

8

7

4

8

9

3

8

12

6

3

6

12

4

8

9

6

7

4

3

5

9

4

7

8

9

1

Ответы:

1) L(x*)= 16. 2) L(x*)= 24. 3) L(x*)= 25. 4) L(x*)= 38. 5) L(x*)= 24.

6) L(x*)= 25. 7) L(x*)= 81. 8) L(x*)= 73. 9) L(x*)= 60. 10) L(x*)= 68.

Лабораторная работа 15.

ЗАДАЧА О НАЗНАЧЕНИИ. МЕТОД МАКА

Постановка задачи такая же самая, как и в предыдущем разделе (14.114.4).

Алгоритм метода Мака.

1. Помечаем минимальный элемент строки отметкой *. Если минимальных элементов несколько, помечаем любой из них.

2. Действия п. 1 повторяем для всех строк матрицы расходов.

3. Если строка имеет еще один минимальный элемент, просматриваем столбец, к которому этот элемент принадлежит. Возможные случаи:

i) Столбец не имеет обозначенных элементов;

ii) Столбец имеет по крайней мере один обозначенный элемент.

4. В случае i) помечаем минимальный элемент строки отметкой *. Все другие отметки в этой строке снимаются. В случае ii) помечаем минимальный элемент строки отметкой ^, если элемент этой строки с отметкой * не является единственным обозначенным элементом в своем столбце.

5. Действия п.п. 3 и 4 повторяем последовательно для всех строк, которые имеют больше одного минимального элемента.

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

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

8. Просматриваем последовательно строки матрицы расходов, начиная с первого, и находим строку, в которой элемент с отметкой * принадлежит множеству В.

9. Находим для строки минимальную разницу между элементами множества. Но и элементом с отметкой *.

10. Действия п.п. 8 и 9 повторяем последовательно для всех строк, которые имеют свойства, которые указаны в п. 8.

11. Выбираем наименьшую из минимальных разниц.

12. Добавляем это число к каждому элементу множества В.

13. Возвращаемся к п. 3.

Замечания те же самые, как в предыдущем разделе.

Программное обеспечение.

Обучающий модуль, с помощью которого задача об оптимальных назначениях Решается в диалоге с пользователем за выложенным алгоритмом, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПЗМО.

Задание.

Решить методом Мака задачи об оптимальных назначениях, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1—№9), а также задачи, матрице расходов C которых заданы в предыдущем разделе.

Лабораторная работа 16.

МАТРИЧНЫЕ ИГРЫ. СВЯЗЬ С ЗАДАЧЕЙ ЛИНЕЙНОГО ПРОГРАММИРОВАНИЯ. МЕТОД БРАУНА-РОБIНСОН

Постановка матричной игры двух лиц с нулевой суммой.

Найти цену игры и оптимальные смешанные стратегии игроков для матричной игры двух лиц с нулевой суммой и заданной платежной матрицей C=||cij||, i=1...,m, j=1...,n (игрока I1 игроку I2).

Основные определения и теоремы.

Смешанные стратегии игроков I1 и I2 — это векторы x=(x1...,xm) и y=(y1...,yn)', компоненты которых удовлетворяют условия:

xi ³ 0, i=1...,m, x1 +...+ xm = 1

yj ³ 0, j=1...,n, y1 +...+ yn = 1.

Можно считать, что числа xi (i=1...,m) и yj (j=1...,n) есть не что другое, как вероятности выбора і-ї и j-ї стратегий, соответственно, игроками I1 и I2 (і-го строки матрицы C первым игроком та j-го столбца этой же матрицы вторым игроком).

Функция F(x,y)=xCy' называется математической ожиданием платежа игрока I1 игроку I2 (средним выигрышем игрока I2).

Точка (x*,y*) (x*ÎX, y*ÎY) называется седловой точкой функции f(x,y), xÎX, вÎВ, если для произвольных xÎX, вÎВ имеет место неравенство

f(x*,y) £ f(x*,y*) £ f(x,y*).

Теорема. Пусть заданная действительная функция f(x,y), xÎX, вÎВ, для которой существуют

min max f(x,y) max min f(x,y).

xÎX вÎВ вÎВ xÎX

Для того, чтобы выполнялось соотношение

min max f(x,y)= max min f(x,y).

xÎX вÎВ вÎВ xÎX

необходимо и достаточно, чтобы функция f(x,y) имела седловую точку.

Теорема. Функция F(x,y) (средний выигрыш игрока I2) всегда имеет седловую точку.

Компоненты x*, y* точки (x*,y*) седла функции F(x,y) определяют оптимальные смешанные стратегии игроков I1 и I2, соответственно, а цена игры v определяется соотношением:

v = min max F(x,y)= max min F(x,y)= F(x*,y*)

 xÎX вÎВ вÎВ xÎX

X = { x = (x1...,xm) : xi ³ 0, i=1...,m,  x1 +...+ xm = 1}

В = { в = (y1...,yn)' : yj ³ 0, j=1...,n, y1 +...+ yn = 1}.


Теорема. Задача определения оптимальных смешанных стратегий x* и y* игроков I1 и I2 эквивалентная пару двойственных задач линейного программирования:

v ® min

c1j x1 +...+ cmj xm £ v, j=1...,n

x1 +...+ xm = 1, xi ³ 0, i=1...,m;

v ® max

ci1 y1 +...+ сіn yn ³ v, i=1...,m

y1 +...+ yn = 1, yj ³ 0, j=1...,n.

Метод Брауна-Робинсона.

Метод Брауна-Робинсона представляет собой итеративный метод решения матричной игры, с каждым шагом которого связывается некоторая фиктивная игра, что разыгрывается в чистых стратегиях.

Пусть на s-у шаге полученные векторы

M(s)= (m1(s),...,mm(s)),  N(s)= (n1(s),...,nn(s))

компоненты которых mi(s) и nj(s) соответственно уровни количествам выбора і-ї и j-ї чистых стратегий первым и вторым игроками на предыдущих шагах. Указанные векторы определяют очевидно частоты выбора соответствующих чистых стратегий игроков. Рассматриваются также векторы относительных частот

x(s)= (x1(s),...,xm(s))  но в(s)= (y1(s),...,yn(s))'

где xi(s)= mi(s)/s, i=1...,m, yj(s)= nj(s)/s, j=1...,n.

На s-у шаге величина

ci1 y1(s) +...+ сіn yn(s), i=1...,m

определяет средний платеж первого игрока второму при условии, что первый игрок выбирает и строку, величина

c1j x1(s) +...+ cmj xm(s), j=1...,n — средний выигрыш второго игрока при условии, что второй игрок выбирает j-й столбец.

На каждом шагу первый игрок выбирает строку, которой отвечает минимальное значение указанного среднего платежа; второй игрок выбирает столбец, который отвечает максимальному значению указанного среднего выигрыша.

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

Теорема Брауна-Робинсон.

При неограниченном росте s величины x(s) и в(s) следуют к оптимальным смешанным стратегиям x* и y* первого и второго игроков соответственно.

Программное обеспечение.

Обучающий модуль, с помощью которого матричная игра Решается в диалоге с пользователем за алгоритмом Брауна-Робинсона, вызывается из раздела «ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ» главного меню пакета ПОМО.


Задание.

Решить методом Брауна-Робинсона матричные игры, условия которых задаются модулем с помощью команды «Данные» главного меню (задачи №1—№9).

Путем сведения двойственных задач линейного программирования и методом Брауна-Робинсона найти оптимальные смешанные стратегии и цену игры матричных игр с такими платежными матрицами:

1)

-8

 2

2)

 2

-5

3)

-1

 5

4)

 5

-6

5)

-3

 1

 1

-8

,

-4

 3

,

6

-4

,

-3

 0

,

 2

-1

,

6)

-3

 3

 3

7)

 0

 1

 6

8)

 1

 0

-1

9)

 1

 0

-1

-5

 5

-3

 7

 1

 3

 0

 2

 1

-1

 2

 3

 3

-9

 2

,

 1

 2

 0

,

 1

-1

 3

,

-2

-3

 3

.


Лабораторная работа 17.

МЕТОДЫ ОДНОМЕРНОЙ ОПТИМIЗАЦИИ

Метод золотого сечения.

Метод золотого сечения (МЗС) применяется для поиска минимума унимодальной функции одной переменной y=F(x), что задана на промежутке [A,B]. Алгоритм метода реализуется в виде последовательности шагов, на каждом из которых осуществляется сужение интервала, что содержит точку минимума.

В начале вычислений возлагают А{0}= А, B{0}= B.

На s-у шаге определяют величины

L{s}= B{s} G(B{s} А{s})

R{s}= А{s}+ G(B{s} А{s})

где константа G = (Ö51)/2 » 0.618. Подставим

А{s+1}= А{s},  B{s+1}= R{s}, если  F(L{s}) £ F(R{s})

А{s+1}= L{s},  B{s+1}= B{s}, если  F(L{s})> F(R{s}).

Итерации продолжают до тех пор, пока не будет выполняться неравенство

B{s} А{s} £ e,

где e > 0 — заданное число, которое определяет погрешность решения задачи.

На каждом шагу МЗП, начиная с 1-го, вычисляется лишь одно значение функции F(x), потому что одна из точек золотого перерезу на предыдущем шаге осуществляет золотой перерез промежутка на следующем шаге.

За приближенное решение задачи принимают

x* = (А{s}+ B{s})/2, y* = F(x*).

При решении задачи максимизации функции F(x) необходимо заменить ее на функцию — F(x).

Метод случайного поиска.

Метод случайного поиска применяется для нахождения минимума (максимума) произвольной функции y=F(x), что задана в любой допустимой области D.

В программе рассматривается реализация данного метода для функции одной переменной.

Произвольная функция F(x) задана на промежутке [A,B]. С помощью датчика случайных чисел, равномерно распределенных на промежутке [0,1], строится последовательность случайных чисел x{k}, k=1...,N, равномерно распределенных на промежутке [A,B]. Вычисляются и сравниваются между собой значения функции F(x) в точках x{k}. Минимальное из них принимается за оценку минимума функции F(x) на промежутке [A,B].

Если N стремится к бесконечности, полученная оценка за вероятностью совпадает к глобальному минимуму функции, что рассматривается.