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


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

Маршрутизации перевозок ресурсов помашинными отправками на основе гарантированного эффекта.



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

,

где lгi – длина (стоимость) i –й производительной ездки;

lхj – длина (стоимость) j –й непроизводительной ездки;

m – число производительных ездок;

n – число непроизводительных ездок;

Kг – коэффициент гарантированного эффекта.

Большие значения Kг принимаются при местных перевозках (порядка 1,15) и меньшие при магистральных перевозках (порядка 1,05).

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

где Qi – объем ресурса при i-й перевозке (с учетом ранее окончательно принятых маршрутов);

Qmi – объем ресурса i-й перевозки, включенный в данный маршрут;

γсi – коэффициент использования вместимости транспортных средств при i-й перевозке.

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

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

Из схемы следует, что возможен маршрут А-В-С-Д-А с Z= (11+10) – 1.15 (6.0+5.0) = 4.9 >0(при Kг =1.15) .

Если принять, что дополнительных ограничений нет, то этот маршрут вводится в окончательное решение с объемом перевозок , т.е. при 1-й ездке назначается объем 100 и при 2-й ездке 100*0.8=80.

Объем 2-й перевозки ресурса в объеме 20 ед. (остаток от осваиваемого на принятом маршруте) назначается на маятниковый маршрут с обратным непроизводительным пробегом.
А 11 км Q1=100 γс1 =1.0


В

8км

6км
Д C

10 км Q2=100 γс2 =0.8

Рисунок 3.25 – Пример схемы транспортной сети и корреспонденций ресурса

Маршрутизации перевозок ресурсов помашинными отправками на основе расчета выигрышей.

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

Выигрыш от объединения определяется как разница между производительным и непроизводительным пробегом на маршруте . Например, при рассмотрении объединения по две перевозки выигрыши рассчитываются по формуле (см. рисунок 3.26): .
i
j


n

k

Рисунок 3.26 – Схема транспортной сети и корреспонденций ресурса (перевозок)

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

максимум коэффициента использования пробега

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



или минимум отношения непроизводительных пробегов к общим (коэффициент непроизводительных пробегов)

или минимум отношения непроизводительных пробегов к производительным

.

Рекомендуется принимать рациональные маршруты со значениями коэффициента использования пробега β не ниже 0.55-0.60 (меньшие допускаемые значения соответствуют магистральным и большие местным перевозкам) и минимальными значениями zно порядка 0.40-0.45 (большие допускаемые значения соответствуют магистральным и меньшие местным перевозкам).

Порядок окончательного формирования системы маршрутов для освоения перемещения ресурсов соответствует ранее приведенному для метода гарантированного эффекта.

Вычисление частот и частостей случайной величины

5) подсчитать число попаданий случайной величины в каждый j-й интервал (частоты Мj), для чего пересмотреть все числа xi () относительно границ интервалов

Мj = М j + 1 , если X j-1  xi < X j при ;

Мj = М j + 1 , если X j-1  xi  X j при j = N;

6) определить частости (эмпирические вероятности) pэj попадания значений случайной величины в каждый из интервалов путем деления соответствующих частот на объем выборки n, т.е. pэj = Мj / n. Сумма всех частот равна объему выборки

,

а сумма частостей pэj соответственно равна единице.


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

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

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

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

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



ci = 0 для ;

ограничения



где M = m+n

и

.

Для неравенств типа  dij=1 и для типа  dij= - 1.

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

20 x1+ 25 x2 + 1 x3+ 0 x4 = 175

x1 + x2 + 0 x1+ 1 x2 = 8

Z = 5 x1+ 6 x2 + 0 x3+ 0 x4 = max.
Основные шаги решения задачи (после представления исходной системы в стандартном виде):

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

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

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

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

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

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

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

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

  9. переход на п. 2;

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

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

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

xm+1 = b1;

xm+2 = b2;

. . .

xM = bn;

x1 = 0;

x2 = 0;

. . .

xm = 0.

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

.

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

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

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

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

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

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

Решение задачи при ограничениях одновременно типа  , = и  отличается от приведенного алгоритма введением искусственных переменных /4/.

Задача СПУ. Расчет критического времени и нахождение критического пути.

Задача СПУ. Расчет параметров сетевого графика (поздние сроки свершения событий).

Задача СПУ. Расчет параметров сетевого графика (полный резерв работ).

Задача СПУ. Расчет параметров сетевого графика (свободный резерв работ).

Задачи упорядочения – это задачи определения оптимальной последовательности событий, а задачи согласования рассматривают сетевое планирование и управление.

Основа решения первых – теория расписаний, вторых – теория графов.

Предметом сетевого планирования и управления (СПУ) является разработка и оптимизация сетевых графиков.

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

Работа – это процесс, сопровождающийся затратами времени и ресурсов. Если имеются затраты только времени – это так называемые фиктивные работы (естественная сушка и т.п.).

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

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

Длина пути определяется суммой продолжительности образующих его работ.

Рассмотрим сетевой график с одним исходным и одним завершающим событием, известными продолжительностями tij работ ij, где i – событие, соответствующее началу работы и j – соответственно окончанию. Общее число событий m, число работ n.

Ниже приведен пример сетевого графика (рисунок 3.30) и длительности работ (таблица 3.30).

Расчет сетевого графика включает отыскание следующих основных параметров:

ранний и поздний сроки начала работ tр.нij и tп.нij;

ранний и поздний сроки окончания работ Tр.оij и Tп.оij;

ранний и поздний сроки наступления событий Tрi и Tпi;

4



3

1 6


  1. 5

Рисунок 3.30 – Пример схемы сетевого графика
Таблица 3.30 – Дительность работ

i

j

tij

1

2

6

1

3

5

1

4

7

2

3

3

2

5

5

3

4

4

3

6

10

4

6

11

5

6

5

полный и свободный резервы времени каждой работы Rпij и Rсij;

резерв времени событий Ri;

критическое время графика tкр и перечень работ, образующих критический путь;

полный резерв Rl времени путей l, альтернативных критическому.

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

Для расчета необходимо произвести правильную нумерацию событий, т.е. для любой работы ij номер предшествующего события i должен быть меньше номера последующего события j.

Алгоритм вычислений следующий:

1) Присваивается исходному событию начальный, например, нулевой момент времени раннего срока свершения Tрi=1=0;

2) Последовательно для каждого рассчитываются

;



где ^ Bj – множество событий i, соединенных работами с j- м событием.

В результате находятся Трi , .

3) Критическое время сетевого графика tкр = Tрm .

4) Поздний срок свершения завершающего события принимается равным критическому tкр или заданному директивному времени tдир (tдир tкр ):

Tпm = tкр или Tпm = tдир.

5) Последовательно для каждого пункта рассчитываются

;

,

где ^ Ai – множество событий j, соединенных работами с i-м событием.

6) Рассчитываются резервы времени событий

Ri = Tпj - Tрi.

7) Рассчитываются полные резервы времени работ – максимальное время на которое можно отсрочить или увеличить продолжительность работы ij, не изменяя установленного позднего срока наступления завершающего события

Rпij = Tпj - Tр.оij= Tпj - Tрi - tjj.

8) Рассчитываются свободные резервы времени работ – максимальное время на которое можно отсрочить или увеличить продолжительность работы ij, при условии, что все события будут выполнены в свои ранние сроки

Rсij = Tрj - Tр.оij = Tрj - Tрi – tij.

Величина свободного резерва меньше или равна величине полного резерва.

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

10) Полный резерв времени интересующих альтернативных путей определяется как разность между длиной критического пути и длиной любого другого полного пути tl

Rl = tкр - tl .

Звено транспортной сети и его параметры.
Транспортная сеть района (региона) представляет собой систему путей сообщения, предназначенную для передвижения транспортных средств. Модель транспортной сети – это описание местонахождения ее вершин (пунктов), а также длин и других параметров (характеристик) соединяющих вершины звеньев. Может быть задана в графическом или табличном виде. Звеном транспортной сети является ее часть, соединяющая две смежные вершины. Длина звеньев может быть выражена в единицах длины, приведенных единицах длины, единицах времени и стоимостном выражении (в дальнейшем длина). В качестве других параметров звеньев может быть задана техническая категория пути сообщения и др. Вершины (пункты) транспортной сети соответствуют местонахождению ресурсообразующих и ресурсопоглащающих точек, терминалов, пересечений путей.

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


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

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

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

^ Аналитический метод основывается на 1-х и 2-х частных производных по оптимизируемым параметрам:

 Z/ xi = 0 }, .

Решение системы уравнений  Z/ xi = 0 }, дает оптимальное решение Xп , если оно существует.

Вид экстремума определяется значением определителя  матрицы Гессе

, , .

Если решение существует в точке Xп и в этой точке  > 0, то оптимизируемая функция имеет минимум, а иначе максимум.

^ Среди численных методов различают методы нулевого порядка и градиентные (1-го и 2-го порядка). Первые основаны только на вычислениях значений оптимизируемой функции. Вторые используют частные производные соответствующего порядка. Эффективность процедуры поиска оптимума – возможность отыскания решения и сходимость к решению по скорости зависят от применяемого метода и вида функции.

Наиболее известны следующие методы нулевого порядка:

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

спирального координатного спуска;

вращающихся координат (метод Розенброка);

конфигураций;

Хука-Дживса с поиском по образцу;

параллельных касательных (метод Пауэлла);

Нелдера-Мида – поиска по деформируемому многограннику за счет его отражения, растяжения и сжатия и др.

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

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

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

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



Хп = (1;1);
функция Пауэлла



Хп = (0;0;0;0);
двумерная экспоненциальная функция :

,

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

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

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

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

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

  4. модифицируется шаг поиска и вдоль новых осей Z1 и Z2 находится следующее текущее приближение;

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

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

^ Метод Пауэлла основан на определении направлений поиска путем проведения касательных к изолиниям (изоповерхностям), параллельных друг другу. Линия, соединяющая точки касания определяет текущее направление поиска Z1. Графическое представление метода приведено на рисунке 3.14.

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
Главная страница