Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1


НазваниеУкрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1
страница9/9
Дата публикации06.05.2013
Размер1.03 Mb.
ТипЗакон
userdocs.ru > География > Закон
1   2   3   4   5   6   7   8   9
Таблица 3.34 – Пример моделирования игры двух сторон по алгоритму Брауна

Номер

итерации

Выбранная стратегия

Накопленные результаты стороны А

при стратегиях стороны В

Накопленные результаты стороны В

при стратегиях стороны А

Сторона А

Сторона В

1

2

3

4

1

2

3

1

А2

В1

12

14

11

16

11

12

9

2

А2

В3

24

28

22

32

24

23

21

3

А1

В3

35

43

35

42

37

34

33

4

А1

В1

46

58

48

52

48

46

42

5

А1

В1

57

73

61

62

59

58

51


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


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

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

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

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

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

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

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

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

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

Для получения первоначального базисного решения рассмотрим применение метода минимального элемента. В соответствии с этим методом распределение составляется по следующему алгоритму:

1) формируются дополнительные массивы стоимостей l'ij (l'ij = l ij), объемов ресурса X'Ai (X'Ai=XAi ) и X'Bj (X'Bj =XBj ), ; ;

2) находится минимальная стоимость из всех связей

.

Если lrw =  , то первоначальное базисное решение получено. Иначе на 3);

3) связь rw, соответствующую минимальной стоимости, загружают корреспонденцией Xrw . Объем корреспонденции Xrw , назначаемый для связи rw, определяется как минимум от объемов запаса и потребности с учетом ранее назначенных других поставок:

Xrw = min (X'Ar ,X'Bw),

где X'Ar – количество ресурса r-го поставщика с учетом ранее назначенных корреспонденций другим, кроме w-го, потребителям; X'Bw – количество ресурса, требуемого w-му потребителю с учетом ранее назначенных корреспонденций от других, кроме r-го поставщика;

4) из сравниваемых величин X'Ar и X'Bw вычитается значение Xrw , в результате чего получаются измененные ограничения X'Ar =X'Ar - Xrw и X'Bw =X'Bw - Xrw ;

5) изменяется массив l'ij по следующему правилу:

если X'Bw=0, то l'iw =  (),

иначе (X'Ar=0) l'rj =  ();

6) переход на пункт 2).

Пункт 5 алгоритма обеспечивает исключение из дальнейшего рассмотрения поставщика (если X'Ar =0), либо получателя (если X'Bw=0). Остаток объема ресурса X'Ar или X'Bw к дальнейшему распределению может иметь значение, равное нулю.

Полученное таким образом закрепление потребителей ресурса за поставщиками является одним из возможных базисных распределений.

Для оценки оптимальности текущего решения закрепления потребителей ресурса за поставщиками применяется ряд методов: распределительные методы (метод Хичкока, метод Креко, метод МОДИ), методы с разрешающими элементами (метод разрешающих слагаемых и метод разрешающих множителей) и др.

Наиболее широкое применение получил модифицированный метод (МОДИ). В распределительную таблицу вводят вспомогательные строку и столбец; в них вносят специальные показатели, называемые потенциалами. Распределительные методы основаны на следующем: если к стоимостям любой строки (столбца) распределительной таблицы прибавить (или отнять) одно и то же произвольное число, то оценка оптимальности относительно не изменится. Если, например, от стоимостей каждого i-го поставщика отнять число uAi , а от стоимостей каждого j-го потребителя – uBj, то относительной оценкой любой связи ij может служить оценочный параметр sij (вместо l ij):

sij = lij - uAi- uBj. (3.6)

Принимая для загруженных связей sij = 0 и используя выражение (3.6), определяются потенциалы uAi и uBj по следующему правилу:

потенциал для одного пункта, например первого поставщика принимается равным нулю;

по расстояниям загруженных связей подбираются потенциалы для других поставщиков и потребителей таким образом, чтобы соблюдалось принятое условие lij - uAi- uBj = 0, т.е. стоимость для каждой загруженной связи должна быть равна сумме потенциалов по поставщику и потребителю.

Затем по вычисленным потенциалам uAi , uBj определяется, используя формулу (3.6), значение оценочного параметра sij для каждой незагруженной связи (не входящей в базисный план). Величина параметра sij характеризует общее изменение целевой функции, получаемое при включении в план единичной корреспонденции для связи ij по сравнению с рассматриваемым планом.

Если значение оценочного параметра свободной связи будет меньше нуля (sij <0), то это значит, что перераспределение корреспонденций с загрузкой такой связи, называемой потенциальной, уменьшит значение целевой функции на величину abs(sijXij) , Xij – размер корреспонденции, которой будет загружена связь ij. Отсутствие связей со значением параметра sij <0 означает, что проверяемый план закрепления потребителей за поставщиками является оптимальным. Если для какой-то свободной связи значение sij равно нулю, то это означает, что можно получить другой план с тем же минимальным значением целевой функции.

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

При перераспределении загрузок по связям в распределительной таблице для наиболее потенциальной связи, как для загруженной, строится контур. Введение к m+n-1 загруженным связям еще одной образует ровно один определенный контур, присущий вводимой связи. После чего связи, соответствующие вершинам контура, нумеруются: номер 1 присваивается выбранной потенциальной связи, а дальнейшая нумерация ведется в порядке следования вершин по контуру (могут присваиваться связям контура положительные и отрицательные знаки).

Затем производится перераспределение по контуру корреспонденций следующим образом:

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

2) значение объема ресурса Xм вычитается от значений объемов корреспонденций всех связей с четными номерами вершин. Если среди связей с четными номерами вершин окажутся две (или более) с одинаковой минимальной корреспонденцией, то из плана исключается только одна из них, для связи с большим расстоянием поставки, а вместо остальных оставляют условную корреспонденцию с нулевым значением, чтобы не допустить вырождения;

3) для всех связей с нечетными номерами вершин (включая и потенциальную) к значениям объемов корреспонденций прибавляется величина Xм.

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

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

При решении транспортной задачи линейного программирования на основе существующего базисного решения возможны варианты, когда число загруженных связей в таблице меньше m+n-1 (случай вырождения) или больше m+n-1 (случай наличия циклов). В первом случае нельзя оценить оптимальность решения, так как невозможно определить потенциалы для некоторых поставщиков и (или) потребителей, во втором – потенциалы определяются неоднозначно.

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

В случае наличия циклов для некоторых связей исключают корреспонденции по следующему алгоритму:

1) строится один из возможных контуров;

2) нумеруются углы контура;

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

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

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

Указанные действия повторяются до полного исключения циклов (контуров) в распределительной таблице. При этом нельзя допускать вырождения за счет одновременного исключения загрузок для нескольких связей одного цикла. Исключение контуров в распределительной таблице по вышеописанной методике уменьшает одновременно и значение целевой функции.

При отсутствии дополнительных условий полученное оптимальное решение является окончательным.
1   2   3   4   5   6   7   8   9

Похожие:

Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconКурс «Статистические методы управления качеством» специальность 200503...
Особенности эмпирических данных. Случайные величины. Распределения случайных величин. Статистические гипотезы
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconКоллоквиум 2 тв и мс
Числовые характеристики случайных величин: математическое ожидание (понятие, свойства)
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗакон больших чисел
Корреляционная матрица случайного вектора. Коэффициент корреляции двух случайных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconАвтокорреляция случайного возмущения. Причины. Последствия
Алгоритм теста Голдфелда-Квандта на наличие (отсутствие) гетероскедастичности случайных возмущений
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗакон распределения Пуассона и его характеристики
Локальная предельная теорема Муавра-Лапласа. Теорема Пуассона Понятие случайной величины. Виды случайных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЗачет Казаринова Ирина Николаевна Старовойтова Ольга Рафаэльевна...
Методология, методика, программа, метод, алгоритм исследования, парадигма, научная традиция
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 icon2: Элементы векторной алгебры
Различают понятия величин, которые характеризуются од -ним числом скалярные величины (например: масса, объём, длина, площадь и т...
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconНа рисунке 1 приведен график зависимости скорости движения тела от...
Чему равно отношение силы гравитационного взаимодействия, действующей со стороны Луны на Землю, к силе гравитационного взаимодействия,...
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconЧто такое метрология?
Размерность качественная характеристика физических величин. Правила определения размерности производных величин
Укрупненный алгоритм программы для исследования случайных величин приведен на рисунке 12. 1 iconПрограмма учебного курса «Физическая география России»
В конце программы приведен перечень экзаменационных вопросов за все три семестра: два на 4 курсе и 1 на пятом курсе см!!!
Вы можете разместить ссылку на наш сайт:
Школьные материалы


При копировании материала укажите ссылку © 2020
контакты
userdocs.ru
Главная страница