Logo GenDocs.ru

Поиск по сайту:  

Загрузка...

Ответы на экзаменационные вопросы - компьютерное моделирование - файл 1.doc


Ответы на экзаменационные вопросы - компьютерное моделирование
скачать (644 kb.)

Доступные файлы (1):

1.doc644kb.22.11.2011 23:00скачать

содержание
Загрузка...

1.doc

1   2   3
Реклама MarketGid:
Загрузка...

^ 17. Геометрическая интерпретация оптимизационной задачи линейного программирования.

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

Данные о запасе и нормах расхода ресурсов (табл) Оптимизационная модель задачи запишется следующим образом: а) целевая функция:

б) ограничения: по ресурсу А,

по ресурсу B, по ресурсу C; в) условие неотрицательности переменных:

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

Преобразуем нашу систему ограничений, найдя в каждом из уравнений x2 , и отложим их на графике. Любая точка на данном графике с координатами x1 и x2 представляет вариант искомого плана. Однако ограничение по ресурсу А сужает область допустимых решений. Ими могут быть все точки, ограниченные осями координат и прямой АА , так как не может быть израсходовано ресурса А больше, чем его на предприятии имеется. Если точки находятся на самой прямой, то ресурс используется полностью. Аналогичные рассуждения можно привести и для ресурсов В и С . В результате условиям задачи будет удовлетворять любая точка, лежащая в пределах заштрихованного многоугольника. Данный многоугольник называется областью допустимых решений. Однако нам необходимо найти такую точку, в которой достигался бы максимум целевой функции. Для этого построим произвольную прямую 4x1+5x2=20, как x2  =4 -4/5x1 (число 20 произвольное). Обозначим эту линию РР. В каждой точке этой линии прибыль одинакова. Перемещая эту линию параллельно ее исходному положению, найдем точку, которая удалена от начала координат в наибольшей мере, однако не выходит за пределы области допустимых решений. Это точка М, которая лежит на вершине многоугольника. Координаты этой точки (x'1=3,03 и x' 2=7,4) и будут искомым оптимальным планом.
^ 18. Симплексный метод решения оптимизационной задачи линейного программирования.

Симплексный метод  это вычислительная процедура, основанная на принципе последовательного улучшения решений при переходе от одной базисной точки к другой. При этом значение целевой функции улучшается. Базисным решением является одно из допустимых решений, находящихся в вершинах области допустимых значений. Проверяя на оптимальность вершину за вершиной, приходят к искомому оптимуму. На этом принципе основан симплекс -метод. Симплекс  это выпуклый многогранник в n -мерном пространстве с n+1 вершинами, не лежащими в одной гиперплоскости. Доказано, что если оптимальное решение существует, то оно обязательно будет найдено через конечное число шагов, кроме случаев зацикливания. Алгоритм симплексного метода состоит из ряда этапов. Первый. Строится исходная оптимиз модель. Далее исходная матрица условий преобразуется в приведенную каноническую форму. если после добавления дополнительных переменных матрица условий не содержит полную единичную подматрицу, то вводятся искусственные переменные, которые не имеют никакого экономического смысла. Они вводятся исключительно для того, чтобы получить единичную подматрицу и начать процесс решения задачи при помощи симплексного метода. Второй. Строится исходная симплекс-таблица и отыскивается некоторое начальное базисное решение. Множество переменных, образующих единичную подматрицу, принимается за начальное базисное решение. Третий. Проверка базисного решения на оптимальность осуществляется при помощи специальных оценок коэффициентов целевой функции. Если все оценки коэффициентов целевой функции отрицательны или равны нулю, то имеющееся базисное решение  оптимальное. Четвертый этап . Переход к новому базисному решению. Очевидно, что в оптимальный план должна быть введена такая переменная, которая в наибольшей степени увеличивает целевую функцию. При решении задач на максимум прибыли в оптимальный план вводится продукция, производство которой наиболее выгодно. Это определяется по максимальному положительному значению оценки коэффициента целевой функции. Столбец симплексной таблицы с этим номером на данной итерации называется генеральным столбцом. Далее, если хотя бы один элемент генерального столбца а ij 0 строго положителен, то отыскивается генеральная строка. Для отыскания генеральной строки все свободные члены делятся на соответствующие элементы генерального столбца. Из полученных результатов выбирается наименьший. Соответствующая ему строка на данной итерации называется генеральной. Она соответствует ресурсу, который лимитирует производство на данной итерации. Элемент симплексной таблицы, находящийся на пересечении генеральных столбца и строки, называется генеральным элементом. Затем все элементы генеральной строки делятся на генеральный элемент. В результате этой операции генеральный элемент становится равным единице. Далее необходимо, чтобы все другие элементы генерального столбца стали бы равны нулю, т.е. генеральный столбец должен стать единичным. Все строки преобразуются следующим образом. Полученные элементы новой строки умножаются на соответствующий элемент генерального столбца и полученное произведение вычитается из элементов старой строки. Значения новых базисных переменных получим в соответствующих ячейках столбца свободных членов.

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

Пусть необходимо найти оптимальный план производства двух видов продукции х1 и х2 Табл– Исходные данные примера

Вид продукции

Норма расхода ресурса на единицу прибыли

Прибыль на единицу изделия




А

В




1

5

8

7

2

2

4

3

Объем ресурса

20

36




1. Построим ОМ ограничение по ресурсу А;   ограничение по ресурсу В. 2. Преобразуем задачу в приведенную каноническую форму. Для этого достаточно ввести дополнительные переменные x3 и x4 . В результате неравенства преобразуются в строгие равенства: Построим исходную симплексную таблицу и найдем начальное базисное решение. Им будет пара значений дополнительных переменных, которым соответствует единичная подматрица х3=20 и х4=36.

Базисные
переменные

Свободные
члены (план)

x 1

x 2

x 3

x 4

x 3

20

5

2

1

0

x 4

36

8

4

0

1

F j - C j




7

3

0

0

1-я итерация . Находим генеральный столбец и генеральную строку:

Генеральный элемент равняется 5.

Базисные переменные

Свободные члены (план)

x 1

x 2

x 3

x 4

x 1

4

1

0,4

0,2

0

x 4

4

0

0,8

- 1,6

1

F j – C j

28

0

0,2

- 1,4

0

2-я итерация . Найденное базисное решение не является оптимальным, так как строка оценок ( F j  -   C j  ) содержит один положительный элемент. Находим генеральный столбец и генеральную строку: max(0,0,3,-1,4,0)=0,2

Базисные
переменные

Свободные члены (план)

x 1

x 2

x 3

x 4

x 1

2

1

0

1

- 0,5 0

x 2

5

0

1

- 2

1,25

F j - C j

29

0

0

- 1

- 0,25

Найденное решение оптимально, так как все специальные оценки целевой функции (Fj - Cj) равны нулю или отрицательны. F (x) =29; x1=2; x2 =5.
^ 20. Двойственная задача линейного програмирования

Двойственная задача ЛП может быть сформулирована следующим образом: найти переменные yi(i =1,2, ...,m), при которых целевая функция была бы минимальной

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

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

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






(1)






(2)

Следствие 1 . Пусть оптимальное значение некоторой переменной двойственной задачи строго положительно

Тогда из условия (1) получим

или Экономический смысл данных выражений можно интерпретировать в следующей редакции. Если объективно обусловленная оценка некоторого ресурса больше нуля (строго положительна), то этот ресурс полностью (без остатка) расходуется в процессе выполнения оптимального плана. Следствие 2 . Пусть для оптимального значения некоторой переменной x i прямой задачи выполняется условие строгого неравенства Тогда, основываясь на том же первом условии (1), можно заключить, что y i  = 0.

Экономически это означает, что если в оптимальном плане какой-то ресурс используется не полностью, то его объективно обусловленная оценка обязательно равна нулю.
^ 21. Решение двойственной задачи линейного программирования

Ранее (6) мы рассматривали прямую задачу ЛП:

В системе неравенств должны быть однотипные знаки меньше или равно. Поэтому неравенство x 1  Ё  80 умножим на - 1 и поменяем знак неравенства на противоположный.



Ограничение на целочисленность переменных здесь не требуется. Решение прямой задачи дало следующие результаты:

В результате решения двойственной задачи получим

Объективно обусловленная оценка y 1  = 0 указывает на то, что у нас избыток древесины: y 2  = 33,3, т.е. больше нуля. Значит этот ресурс (труд) полностью используется в оптимальном плане. Значение целевой функции Z  ( y  ) равно F  ( x  ) = 42400. Это свидетельствует о том, что найденное решение оптимально.
^ 22. Св-а объективно обусловленых оценок и их анализ

Анализ задачи с использованием объективно обусловленных оценок показывает, что первый ресурс расходуется не полностью. Можно убедиться, что для найденного оптимального плана достаточно 96 куб. м древесины, а 104 куб. м избыточны. Изменение ограничения по древесине с 200 до 96 куб. м не повлияет на оптимальный план. Следовательно, объективно обусловленные оценки являются устойчивыми в некоторых пределах изменения исходных условий задачи. Объективно обусловленные оценки выступают как мера дефицитности ресурсов. Древесина, объективно обусловленная оценка которой у нас равна нулю, не дефицитна, а трудовые ресурсы с объективно обусловленной оценкой, равной в нашей задаче 33,3, дефицитны и используются полностью. Объективно обусловленные оценки выступают как мера влияния ограничений на целевую функцию при приращении данного ресурса на единицу. Так, например, уменьшение задания по производству столов с 80 до 79 увеличивает целевую функцию на 220 руб., а увеличение трудовых ресурсов с 1800 до 1801 чел.-ч увеличивает целевую функцию на 33,3 руб. Объективно обусловленные оценки выступают как меры взаимозаменяемости ограничений. Так, например, если увеличить задание по производству столов на единицу, то для того чтобы целевая функция осталась прежней, нужно добавить 6,6 чел.-ч (220/33,3). В этом случае х1 будет равен 81, х2=1391, а значение целевой функции составит 42400. Следует иметь в виду, что при существенном изменении исходных условий задачи обычно получается уже другая система оценок. Следовательно, объективно обусловленные оценки обладают свойством конкретности, так как определяются совокупностью условий данной задачи. Для другой задачи и других условий их значения будут совершенно иными.

^ 23. Понятие систем массового обслуживания.

Системы массового обслуживания — это такие системы, в кото­рые в случайные моменты времени поступают заявки на обслужи­вание, при этом поступившие заявки обслуживаются с помощью имеющихся в распоряжении системы каналов обслуживания. Поступив в обслуживаю­щую систему, требование присоединяется к очереди других требований. Канал обслуживания выбирает требова­ние из находящихся в очереди, с тем, чтобы приступить к его об­служиванию. После завершения процедуры обслуживания очеред­ного требования канал обслуживания приступает к обслуживанию следующего требования. Примеры систем массового обслуживания: посты ремонта автомобилей; персональные компьютеры, обслуживающие поступающие заявки или требования на решение тех или иных задач; телефонные станции и т. д. Основными компонентами системы массового обслуживания лю­бого вида являются: Входной поток требований. Для описания входного потока тре­буется задать вероятностный закон, определяющий последователь­ность моментов поступления требований на обслуживание и ука­зать количество таких требований в каждом очередном поступле­нии. Дисциплина очереди — это важный компонент системы массово­го обслуживания, он определяет принцип, в соответствии с кото­рым поступающие на вход обслуживающей системы требования подключаются из очереди к процедуре обслуживания. Механизм обслуживания определяется характеристиками самой процедуры обслуживания и структурой обслуживающей системы. Система обслуживания может иметь не один канал обслуживания, а не­сколько; система такого рода способна обслуживать одновременно несколько требований. Функциональные возможности любой систе­мы массового обслуживания определяются: вероятностным распределением моментов поступлений заявок на обслуживание; вероятностным распределением времени продолжительности об­служивания; конфигурацией обслуживающей системы; количеством и производительностью обслуживающих каналов; дисциплиной очереди; мощностью источника требований. Предметом теории массового обслуживания является установле­ние зависимости между факторами, определяющими функциональ­ные возможности системы массового обслуживания, и эффектив­ностью ее функционирования. Независимо от характера процесса, протекающего в системе мас­сового обслуживания, различают два основных вида: системы с отказами, в которых заявка, поступившая в систему в момент, когда все каналы заняты, получает отказ и сразу же по­кидает очередь; системы с ожиданием, в которых заявка, поступив­шая в момент, когда все каналы обслуживания заняты, стано­вится в очередь и ждет, пока не освободится один из каналов.Все системы массового обслуживания различают по числу каналов обслуживания: одноканальные; многоканальные системы.
^ 24. Одноканальная модель смо с пуассоновским входным потоком и экспоненц распределением длительности обслуживания с отказами.

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

где λ. — интенсивность поступления заявок в систему. Плотность распределения длительностей обслуживания: где μ - интенсивность обслуживания. Потоки заявок и обслуживании простейшие. Пусть система работает с отказами. Необходимо определить абсолютную и относительную пропускную способность системы. Представим данную систему массового обслуживания в виде графа (р), у которого имеются два состояния: S0 — канал свободен (ожидание); S1— канал занят. Рис – Граф состояний одноканальной СМО с отказами Обозначим вероятности состояний: P0(t) — вероятность состояния «канал свободен»; P1(t) — вероятность состояния «канал занят».По размеченному графу состояний (р) составим систему дифференциальных уравнений Колмогорова для вероятностей стояний:

Система линейных дифференциальных уравнений имеет решение с учетом нормировочного условия P0(t) + P1(t)=1. Реше­ние данной системы называется неустановившимся, поскольку оно непосредственно зависит от t и выглядит следующим образом:

Нетрудно убедиться, что для одноканальной СМО с отказами вероятность P0(t) есть не что иное, как относительная пропускная способность системы q. Действительно, P0 — вероятность того, что в момент t канал сво­боден и заявка, пришедшая к моменту t, будет обслужена, а следо­вательно, для данного момента времени t среднее отношение числа обслуженных заявок к числу поступивших также равно P0(t), т. е. По истечении большого интервала времени (при t → ∞) дости­гается стационарный режим:Зная относительную пропускную способность, легко найти аб­солютную. Абсолютная пропускная способность (А) — среднее чис­ло заявок, которое может обслужить система массового обслужива­ния в единицу времени:

Вероятность отказа в обслуживании заявки будет равна вероят­ности состояния «канал занят»: Данная величина Pотк может быть интерпретирована как сред­няя доля не обслуженных заявок среди поданных.


^ 25. Одноканальная модель смо с пуассоновским входным потоком и экспоненциальным распределением длительности обслуживания с ожиданием и ограничением на длину очереди

Система массового обслуживания имеет один канал. Входящий поток заявок на обслуживание — простейший поток с интенсивно­стью λ,. Интенсивность потока обслуживания равна μ. Длительность обслуживания — случайная величина, подчи­ненная показательному закону распределения. Поток обслужива­нии является простейшим пуассоновским потоком событий. Заявка, поступившая в момент, когда канал занят, становится в очередь и ожидает обслуживания. Данная система не может вместить более N -требований. Граф состояний СМО в этом случае имеет вид, показанный на р.

Состояния СМО имеют следующую интерпретацию:S0 — «канал свободен»;

S1 — «канал занят» (очереди нет);S2 — «канал занят» (одна заявка стоит в очереди);Sn — «канал занят» (п — 1 заявок стоит в очереди);SN — «канал занят» (N — 1 заявок стоит в очереди).

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

п — номер состояния.

Решение приведенной выше системы уравнений для на­шей модели СМО имеет вид

Тогда

Следует отметить, что выполнение условия стационарности для данной СМО не обязательно, поскольку число допускаемых в обслуживающую систему заявок контролируется путем введения ограничения на длину очереди, а не соотношением между интенсивностями входного потока, т. е. не отношением λ/μ=ρ Определим характеристики одноканальной СМО с ожиданием и ограниченной длиной очереди, равной (N — 1): вероятность отказа в обслуживании заявки:

относительная пропускная способность системы

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

среднее время пребывания заявки в системе:

средняя продолжительность пребывания клиента в очереди: среднее число заявок в очереди:
^ 26. Одноканальная модель смо с пуассоновским входным потоком и экспоненц распределением длительности обслуживания с ожиданием без ограничения длины очереди

Стационарный режим функционирования данной СМО суще­ствует при t →∞ оо для любого n = 0, 1, 2, ... и когда λ < μ. Система алгебраических уравнений, описывающих работу СМО при t →∞ для любого n = 0, 1, 2, ... , имеет вид

Решение данной системы уравнений имеет вид

Характеристики одноканальной СМО с ожиданием, без огра­ничения на длину очереди, следующие: среднее число находящихся в системе клиентов на обслуживание: ; средняя продолжительность пребывания клиента в системе: ; среднее число клиентов в очереди на обслуживании: ; средняя продолжительность пребывания клиента в очереди:
^ 27. Многоканальная модель смо с пуассоновским входным потоком и экспоненц распределением длительности обслуживания с отказами.

В подавляющем большинстве случаев на практике системы мас­сового обслуживания являются многоканальными. Процесс массового обслуживания, описываемый данной моде­лью, характеризуется интенсивностью входного потока λ, при этом параллельно может обслуживаться не более n клиентов. Средняя продолжительность обслуживания одной заявки равняет­ся l/μ. Входной и выходной потоки являются пуассоновскими. Ре­жим функционирования того или иного обслуживающего канала не влияет на режим функционирования других обслуживающих ка­налов системы. Граф состояний многоканальной системы массового обслужи­вания с отказами имеет вид, показанный на рис. 4.3.



Состояния данной СМО имеют следующую интерпретацию:

S0 - все каналы свободны; S1 - занят один канал, остальные свободны; Sk - заняты ровно k каналов, остальные свободны; Sn - заняты все n каналов, заявка получает отказ в обслужива­нии.

Уравнения Колмогорова для вероятностей состояний системы Р0, …, Pk,…, Рn будут иметь следующий вид:



Начальные условия решения системы таковы:

P0(0)=1, P1(0)=P2(0)=…=Pk(0)=…=Pn(0)=0. Стационарное решение системы имеет вид:

где .Формулы для вычисления вероятностей Pk называются форму­лами Эрланга.
^ 28. Многоканальная модель смо с пуассоновским входным потоком и экспоненц распределением длительности обслуживания с ожиданием.

Процесс массового обслуживания при этом характери­зуется следующим: входной и выходной потоки являются пуассоновскими с интенсивностями λ и μ соответственно; параллельно обслуживаться могут не более С клиентов. Система имеет С кана­лов обслуживания. Средняя продолжительность обслуживания одного клиента равна

В установившемся режиме функционирование многоканальной СМО с ожиданием и неограниченной очередью может быть описа­но с помощью системы алгебраических уравнений: Решение системы уравнений имеет вид где Решение будет действительным, если выполняется следующее условие:
1   2   3



Скачать файл (644 kb.)

Поиск по сайту:  

© gendocs.ru
При копировании укажите ссылку.
обратиться к администрации