Курс лекций по теме Управление в МИСО (1996) (1264200), страница 6

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 6)

13 образуют метод статистического испытания.Стандартный механизм розыгрыша. Замечания об СМР.СМР реализуется 2-мя путями:1. с помощью таблиц случайных чисел, равномерно распределенных на интервале [0, 1], если СМР производится вручную.2. с помощью псевдослучайных чисел, если используется ЭВМ (есть стандартные программы).Алгоритм псевдослучайных чисел:Имеем 2 n-значных двоичных числа.

Из их произведения выбираем nсредних знаков отсюда получаем псевдослучайное число. Если его перемножитьс любым другим двоичным числом и выбрать n знаков в середине, то получимследующее псевдослучайное число и т.д.Пример.Вернемся к задаче 2, поставленной более широко.Требуется при заданных параметрах:• ( mx i, my i ) i = 1…n - расположение точек прицеливания;• x, y - рассеяние ракет по осям OX и OY;Страница 29• координаты точек попадания X и Y независимы ( rxy = 0 - коэффициенткорреляции);• при отсутствии системных ошибок;• закон распределения - нормальный;вычислить характеристики эффективности операций:SM( u) = M[ n ]• МU = М(u) - среднюю долю пораженной площади;Sц• DU = D(u) - дисперсию относительно пораженной площади;• P(v >u) = SП/SЦ - вероятность поражения не менее заданной доли площади;• n0 - среднее число ракет, не причинивших ущерба.Моделирование производится на ЭВМ.

В процессе моделирования каждой i-ой реализации нужно проделать n розыгрышей и рассчитать пораженнуюплощадь S (i)П. На каждой итерации разыгрывается точка попадания j-ой ракеты(Xi, Yi), распределенная по нормальному закону с матожиданием и СКО: mxi,myi, x, y.Используется 6-ти точечная схема: 6x i =  x 2   R k − 3 + m x i k =1 12y i =  y 2   R k − 3 + m xyi k =7Для получения i-ой реализации нужно проделать n12 розыгрышей СМР.Подсчет S (i)п:Для быстродействующей ЭВМ можно предложить следующий алгоритмподсчета: разобьем всю площадь на маленькие dSЦ. Если расстояние , от некоторой (Xi, Yi);  < r, то считаем dSЦ пораженной (радиус поражения r). Остаетсяперебрать все dSЦ для всех точек попадания (Xi, Yi).

Выделяем dSЦ, которыепоражены:  dSЦ = S (i)П, отсюда U(i) = S (i)П/SЦ относительная площадь поражения. Оценка n0 состоит из тех точек попадания, для которых не одна из dSЦ неудовлетворяет неравенству  < r.С каждой реализацией свяжем число Xi = { 1; U(i) > U, 0; U(i) < U }.Далее получим N реализаций:NmU U(i)n =12NxP ( V  U) =N1( U(i) )22−mn (0i )n0 = N2U2i  0.98 N =  U  Ф −1    2  = 0.01Т.е. получили все характеристики случайного процесса.Литература:Моисеев «Современные проблемы исследования операций».

Наука 1980г.См. раздел Имитационное моделирование и операционные игры.Страница 30Методы оптимизации в задачах ИСО.Методы линейного программирования в задачах распределения ресурсов и размещения.Постановка задачи:Вид товара /Вид ресурсаR1R2RiRmСтоимость ед.товараТ1Т2TjТna11a21…am1c1a12a22…am2c2……aij…cja1na2n…amncnОбъем ресурсовруб.b1b2bibmСтоимость ед.ресурсаd1d2didmaij - число ресурсов Ri, необходимое для производства единицы товара Tj;mS j =  a i jd i- себестоимость единицы товара;q j = c j − Sj- доход от реализации единицы товара Tj ,где cj - цена;Xj- число единиц товара Tj (неизвестная величина);i =1nI =  X j q j- показатель эффективности (max);0 < Xj  Kj- ограничения на реализацию;j=1n a i jX j  b i - ограничения на ресурсы.i =1Это простейшая задача распределения ресурсов.Другой физический смысл задачи:Ri - ресурсы комплекса ЭВМ (ОЗУ, периферийная память и т.д.);Tj - набор подзадач, решаемых на ЭВМ;di - время использования ресурса;Sj - временная характеристика подзадач;cj - разрешенное время решения подзадачи.qj - экономия времени для решения подзадачи Tj.Математически, речь идет о максимизации при ограничениях.

Они могутиметь форму равенств или неравенств. Это явно задача линейного программирования (линейный показатель, линейные ограничения).Страница 31Постановка задачи размещения (транспортная).Пусть имеется m источников ресурсов Иi и n пунктов потребления Пj.Необходимо составить рациональный план перемещения по сети пунктов назначения.Потр.П1 ... ПnИст.Cij- стоимость перевозки товара из Иi в Пj;С1Xij- количество товаров, перевозимых из Иi в Пj;...ai- количество ресурсов;Сmbj- заявки на товары;заявкиb1bnn m- общая стоимость I =   C i jX i jj=1 i =1 перевози ресурсов;nm- система ограничений; Xij = ai  Xij = b jj=1i =1nm- уравнение баланса. b j = aij=1i =1Частный случай задачи размещения - задача назначения(распределения людей по работам).ai = bj = 1X i j {0, 1} Xij = 1i Xij = 1jЭто задача «булевого» программирования.

На каждую работу долженбыть поставлен 1 человек.Замечание: Если система ограничений имеет смешанный вид, то введениемдополнительных переменных, переходим к равенствам.n mI =   C i jX i j +  n +1Z i jСтремимсяj=1 i =1ij → 0.Решение линейной задачи распределения ресурсовгеометрическим способом.nI =  C j X j → minj=1Xj  0 a X = b1 j 1j j. . . .

. . . . . . . . . . - система из m линейных ограничений. a mj X j = b m jПриведем ряд известных выводов линейного программирования:1) Допустимое решение существует, если ранг матрицы коэффициентов системыограничений (6) равен рангу расширенной матрицы.Страница 32кол.Рес.а1аm a 11  a 1n  a 11  a 1nR     = R   a m1  a mn a m1  a mnb1  b m , где R - определитель наибольшей размерности  0.2) r - размерность определителя, соответствующая рангу: r  n; r < m;3) r = n = m - решение единственное;4) в общем случае число линейных независимых уравнений k = r, при m < n.Тогда существует бесчисленное множество решений, т.к. связей меньше, чемпеременных: r - базисные переменные; n - r - свободные переменные.Выразив базисные через свободные и задаваясь значением свободных, получаем одно из решений.

Далее будем иметь дело только с подсистемой независимых уравнений и считать m = r, n > m.5) Геометрический способ решения задачи линейного программирования (при n - m < 3).Пусть n - m = 2, выразив базисные переменные через свободные, преобразуем системуограничений(6)такимобразом:x 3 = d 31x1 + d 32 x 2 +  3x = d x + d x + n1 1n2 2n nX2X3 = 0X4 = 0X5 = 0X6 = 0X1Следовательно, задав свободные переменные (X1, X2) можно получать базисные переменные. Пусть n = 6. В системе координат OX1X2 можем построитьобласть допустимых решений.6) Найдем оптимальное решение.I = a + bX1 + cX2 → minНаправление изменения величин X1, X2 определяется знаками величин b и c:b > 0, c > 0 - X1 , X2  - для I → minb < 0, c < 0 - X1 , X2 Пусть b > 0, c > 0 в каком направлении увеличиваются X1 и X2 (от началанаклона до +90 в I-ом квадранте).II, c=Градиент - направление наибольшего возрастания I.X 1X 21Оптимальное решение (bX1 + cX2 = 0)- в одном из углов многоугольника.

В nмерном пространстве многоугольник переходит в симплекс.b=7) Свойства оптимального решения:• Решение задачи лежит на границе ОДР;Страница 33• Решение может быть не единственным (если какая либо из границ ⊥градиенту, то все ее точки будут решениями);• Задача линейного программирования может не иметь решения, еслиОДР не замкнута;• Решение задачи линейного программирования достигается в одной извершин ОДР. Поэтому каждая вершина ОДР - опорная точка, дающаяопорное решение.

Чтобы найти оптимальное решение нужно перебрать опорные решения (в вершинах);• Оптимальное решение достигается в точке, где n - m переменных = 0.Эти конструктивные свойства 17 имеют место для любой разности n-m.Симплекс-метод решения задач распределения ресурсов.Применение табличного алгоритма замены базисных переменных.Опорные и оптимальные решения.Для решения линейной задачи распределения ресурсов (n - m > 3) используется симплекс-метод. При этом используются конструктивные свойства17 задач линейного программирования для (n - m < 3).kX= k +1, i X i +  k +1 k +1i=11kX n =   n , i X i +  ni =1Оптимальное решение достигается в однойиз вершин симплекса ОДР, где k переменныхобращается в 0.X1 = X2 = … =Xk = 0Xi =  i i = k+1…n Если  i > 0, то имеем опорное решение.

Возникают 2 задачи:1. Если полученное решение не опорное (некоторые  i < 0), то как использоватьсистему (1) для нахождения опорного решения.2. Если решение опорное (все  i > 0), то как найти оптимальное.При решении задачи 1 одновременно выясняется вопрос о существованиидопустимого решения.При решении задачи 2 выясняется ограничен ли снизу I.

Если он ограничен, то оптимальное решение находится после конечного числа замен свободныхпеременных на базисные. Аналогично решается и задача 1. Поэтому рассмотримвначале отыскание табличного алгоритма замены базисных переменных.y1 = b1 − ( 11x1 ++1k x k )Систему приведем к виду:2y = b − (  x ++ x )mm1 1mk k mСвязь с предыдущими переменными:kI = c0 −   ixiСтраница 34i =1Табличный алгоритм основан на замене свободных переменных на базисные, поэтому поясним на примере, как производить замену, а затем - какиепеременные надо изменять.Пример.y1 = −1 + x1 − x 2 + x 3y 2 = −3 + 0.5x1 − x 3y = 3x − 2x23 3св.членПусть надо заменитьy2 на x1.I1y1-1x1x21-6-22-1x310-12-16y2I = 1 − x1 + 2x 2 − x 3В сложных случаях для такой заменыможно использовать алгоритм:y3-20-2-3-0.5 016-20-200-3200001) Вводим разрешающий столбец x1 и разрешающую строку y2.2) Разрешающий элемент:21 = - 0.5Вводим  =1/21 = -2 и записываем в правом нижнем углу клетки.3) Все элементы разрешающей строки умножаем на  и записываем в углу.4) Все элементы разрешающего столбца умножаем на -.5) Выделяем исходный элемент разрешающей строки и полученный элементразрешающего столбца.6) Для элементов, не стоящих ни в строке, ни в столбце, записать произведениевыделенных элементов, соответствующих им строки и столбца.7) Заменим таблицу на другую, где вместо x1 примем y2.Полученные угловые элементы заполняют разрешающий столбец и строку, а остальные клетки заполняют суммы исходного и углового числа.x1 = x2 = x3 = 0(-1; -3; 0)св.членy2x2x3I-52-23В исходной системе было недоy15-21-3пустимое решение (-1, -3, 0, 0, 0, 0).

Теx16-20-2перь от недопустимого решения мы пеy300-32решли к опорному (5, 6, 0, 0, 0, 0). Таким образом базисные переменныенужно менять на свободные, чтобы приближаться к границе ОДР. Возьмем одноиз уравнений системы (2) с отрицательным свободным членом.Если все ij строки больше 0, то при любом изменении свободных переменных величина yi этой строки только отрицательная. Это проявление неограниченности ОДР.

Характеристики

Список файлов лекций