Графическая иллюстрация полученного решения

Методические указания к заданию 6

Транспортные задачи являются частным случаем задач линейного программирования и формулируются следующим образом.

Имеется m предприятий-производителей (заводы, фабрики) с запасом произведенных товаров (продуктов, материалов, топлива). Кроме того, имеется n предприятий-потребителей (магазины, рынки, бензозаправочные станции), у которых есть спрос на эти товары.

Обозначим предприятия-производители символом A_i, а предприятия-потребители символом Bj.

Наличие товаров (запасов) на i-том предприятии-производителе описывается вектором:

.

Потребность товаров (спрос) на j-том предприятии-потребителе описывается вектором:

.

 

Стоимость перевозок товаров между i-тым предприятием-производителем и j-тым предприятием-потребителем описывается матрицей:

 

.

 

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

 

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

 

Рассмотрим порядок решения конкретной транспортной задачи с помощью математической системы Mathcad.

Пусть дана матрица стоимости перевозок (тарифы) между предприятиями А и В:

.

Другими словами, пусть задана целевая функция:

 

Z(x)=7х₁₁+8х₁₂+х₁₃+2х₁₄+4х₂₁+5х₂₂+9х₂₃+8х₂₄+9х₃₁+2х₃₂+3х₃₃+6х_34.

 

Известен вектор предложений (запасов):

Кроме того, задан вектор потребностей (спроса):

Другими словами, имеются ограничения предложения (6.1) и спроса (6.2):

х₁₁+х₁₂+х₁₃+х₁₄=160

х₂₁+х₂₂+х₂₃+х₂₄=140                   (6.1)

х₃₁+х₃₂+х₃₃+х₃₄=170

 

х₁₁+х₂₁+х₃₁=120

х₁₂+х₂₂+х₃₂=50                            (6.2)

х₁₃+х₂₃+х₃₃=190

х₁₄+х₂₄+х₃₄=110

 

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

Таблица 6.1.

Предприятия	B1	B2	B3	B4	Запасы
A1	7	8	1	2	160
A2	4	5	9	8	140
A3	9	2	3	6	170
Потребности	120	50	190	110	Сумма 470

 

Таблицу следует трактовать следующим образом.

Стоимость перевозок между предприятием A₂ и предприятием B₃ равна 9 единицам. На предприятии A₂ имеется 140 единиц продукции. Потребность предприятия B₃ составляет 190 единиц продукции.

Итак, в рассматриваемой транспортной задаче задана ЦФ, известны ограничения. Требуется найти минимум ЦФ:

Приведем текст программы для расчета (математическая система Mathcad). Комментарии выделены полужирным шрифтом.

ORIGIN: =1

Задан отсчет индексов, начиная с 1

m: =3

Указано число предприятий-производителей (складов)

n: =4

Определено число предприятий-потребителей (магазинов)

j: =1..n             i: =1..m

Организованы циклы

t_j: = 1     l_i: = 1

 

Введена матрица стоимости перевозок

Введен вектор запасов

 

Введен вектор спроса

 

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

x_{m, n}: =0

Given

x ≥ 0

x: =Minimize(Z, x)

 

Получена матрица оптимальных перевозок

Z(x) =1330

Определена стоимость оптимальных перевозок

 

Методические указания к заданию 7

Рассмотрим порядок решения задачи ЛПР с помощью математической системы MATLAB 6.5

Пусть требуется максимизировать ЦФ:

Z=1, 1х₁+1, 2х₂

при имеющихся ограничениях:

2х₁+х₂≤ 8

0, 75х₁+ х₂≤ 6

х₁≥ 0, х₂≥ 0

Так как MATLAB ищет минимум функции, то перед коэффициентами максимизируемой ЦФ необходимо сменить знаки на противоположные.

 

Решение.

Z=[-1.1; -1.2];

A=[2 1; 0.75 1];

b=[8; 6];

[x, Zval]=linprog(Z, A, b)

Optimization terminated successfully.

x =

     1.6000

     4.8000

Zval =

-7.5200

 

Таким образом, оптимальные значения х₁= 1.6, х₂=4.8. Максимальное значение целевой функции f = 7, 52. При записи ответа знак целевой функции изменен на противоположный.

В данной программе символом Z обозначена ЦФ, символом А – матрица условий, символом b – вектор ограничений. Поиск оптимального плана осуществляется с помощью функции linprog.

Контрольная работа №2

1–10. Среднее число вызовов, поступающих на станцию скорой помощи за один час, равно . Поток вызовов простейший. Найти:

а) математическое ожидание, дисперсию, среднее квадратическое отклонение непрерывной случайной величины T – интервала времени между двумя последовательными вызовами в потоке;

б) вероятность того, что за t минут поступит: mвызовов; менееm   вызовов; не менее m вызовов.

1.  = 60,      t = 6,       m = 3.

2.  = 40,      t = 6,       m = 4.

3.  = 30,      t = 10,              m = 2.

4.  = 15,      t = 12,              m = 4.

5.  = 30,      t = 4,            m = 3.

6.  = 20,      t = 9,       m = 3.

7.  = 35,      t = 12,              m = 4.

8.  = 25,      t = 12,              m = 3.

9.  = 10,      t = 24,              m = 2.

10.  = 50,              t = 6,       m = 4.

 

11–20. Электронное устройство работает в ждущем режиме и переключается очередным импульсом. Поток импульсов является потоком Эрланга k – го порядка с интенсивностью  импульсов в час. В случайный момент времени устройство включается в сеть и ждет первого очередного импульса. Найти плотность распределения вероятностей времени ожидания очередного импульса и построить ее график. Вычислить вероятность того, что устройство останется в ждущем режиме не более t минут. Ответ дать с тремя десятичными знаками.

Указание: плотность распределения времени ожидания первого очередного события для потока Эрланга k – го порядка имеет вид

f ( x )= ,

где  – интенсивность простейшего потока, из которого получен поток Эрланга k – го порядка.

 

11.  k = 3, = 2,    t = 10.

12. k = 2, = 3,    t = 5.                           

13. k = 3, = 1,    t = 6.                           

14. k = 2, = 2,    t = 12.                         

15. k = 3, = 3,    t = 15.                         

16. k = 2, = 0, 5, t = 10.                         

17. k = 3, = 1, 5, t = 5.                           

18. k = 2, = 2, 5, t = 20.                         

19. k = 3, = 0, 5, t = 12.                         

20. k = 2, = 1, 5, t = 15.

21–30. Задана матрица P вероятностей перехода дискретной цепи Маркова за один шаг. Распределение вероятностей по состояниям в начальный момент определяется вектором . Построить размеченный граф состояний. Найти:

1) матрицу P ₂ переходов цепи за два шага;

2) распределение вероятностей по состояниям в конце второго шага;

3) вероятность пребывания цепи в третьем состоянии в конце первого шага;

4) стационарное распределение вероятностей.

 

21. P =   , .

22. P =   , .

23. P =   , .

24. P =  , .

25. P =  , .

26. P = , .

27. P =  , .

28. P =  , .

29. P = , .

30. P =  , .

31 – 40. Задана матрица  интенсивностей переходов непрерывной цепи Маркова. Построить размеченный граф состояний. Провести классификацию состояний системы. Найти стационарное распределение вероятностей, если оно существует.

 

31.  =  .

32.  =  .

33.  =  .

34.  =  .

35.  =  .

36.  =  .

37.  =  .

38.  =  .

39.  =  .

40.  =  .

41–50. В компьютерном зале l персональных ком-пьютеров. Зал эксплуатируется 12 часов в сутки. Интенсивность потока отказов одного компьютера равна  компьютеров в сутки. Время восстановления одного компьютера одним мастером в среднем составляет T часов. Все потоки простейшие. Определить оптимальное число обслуживающих зал мастеров по ремонту, если производительность зала оценивается по формуле

П_зала= ,

где l - число персональных компьютеров,  - среднее число неисправных компьютеров.

Указание: экономически оправдан прием на работу еще одного мастера, если он обеспечивает прирост производительности зала не менее чем на 10% от номинальной.

 

41. l = 6,    = 0, 2,    T = 36.   

42. l = 5,    = 0, 2,    T = 30.   

43. l = 4,    = 0, 2,    T = 24.   

44. l = 6,    = 0, 15, T = 48.        

45. l = 5,    = 0, 3,    T = 20.   

46. l = 4,    = 0, 1,    T = 48.   

47. l = 6,    = 0, 3,    T = 24.   

48. l = 5,    = 0, 15, T = 40.        

49. l = 4,    = 0, 16, T = 30.        

50. l = 6,    = 0, 24, T = 30.

51–60. В отделе k телефонных аппаратов. Среднее число поступающих в отдел вызовов равно    вызовов в час. Входной поток простейший. Время переговоров распределено по показательному закону и в среднем составляет T минут. Определить: 1) вероятность отказа в переговорах; 2) абсолютную пропускную способность системы; 3) относительную пропускную способность; 4) среднее число занятых аппаратов; 5) коэффициент загрузки оборудования
 .

Как изменятся эти показатели работы системы, если в отделе добавить еще один аппарат? Сколько аппаратов необходимо добавить, чтобы отказ получали не более 10 % вызовов?

 

51. k = 3,  = 20, T = 10.

52. k = 2,  = 15, T = 12.

53. k = 2,  = 8,    T = 15.

54. k = 3,  = 10, T = 18.

55. k = 2,  = 5,    T = 24.

56. k = 4,  = 24, T = 10.

57. k = 3,  = 15, T = 12.

58. k = 4,  = 30, T = 12.

59. k = 2,  = 10, T = 18.

60. k = 3,  = 25, T = 6.

61–70. Разработчик СМО располагает двумя каналами обслуживания. Интенсивность обслуживания одним каналом m заявок в час. Время обслуживания распределено по показательному закону. Входящий поток заявок простейший с интенсивностью l заявок в час. Возможны два варианта проекта: вариант 1 – две независимо работающих одноканальных безотказных СМО( 1; ¥ ; l/2; m ); вариант 2 – одна двухканальная безотказная СМО( 2; ¥ ; l; m ). Провести сравнительный анализ вариантов по следующим показателям эффективности: среднее число занятых каналов; средняя длина очереди; среднее время пребывания заявки в системе.

Провести аналогичный сравнительных анализ в том случае, если при тех же условиях разработчик располагает средствами для организации m мест в очереди для ожидания обслуживания. Рассмотреть два варианта: вариант 1 – две независимо работающих одноканальных СМО( 1; m/2; l/2; m ); вариант 2 – одна двухканальная СМО( 2; m ; l; m ).

Указание: всюду вектор ( а₁; а₂; а₃; а₄) имеет компоненты: а₁ – число каналов обслуживания; а₂ – число мест в очереди; а₃ – интенсивность входного потока; а₄ – интенсивность потока обслуживания.

 

61. l = 8, m = 5,      m = 6.

62. l = 6, m = 5,         m = 4.

63. l = 6, m = 4,      m = 6.

64. l = 8, m = 7,         m = 4.

65. l = 10, m = 6,         m = 6.

66. l = 10, m = 7,      m = 4.

67. l = 8, m = 6,      m = 4.

68. l = 12, m = 7,      m = 6.

69. l = 4, m = 3,      m = 4.

70. l = 10, m = 8,      m = 4.

71–80. В двухканальную систему массового обслуживания (СМО) с отказами поступает стационарный пуассоновский поток заявок с интенсивностью  заявок в минуту. Длительность обслуживания каждой заявки равна (0, 5 + ) минут, где  – непрерывная случайная величина, закон распределения которой неизвестен. Статистическое распределение выборки { } объема n = 100 имеет вид

, мин	[0; 0, 1)	[0, 1; 0, 2)	[0, 2; 0, 3)	[0, 3; 0, 4)	[0, 4; 0, 5)
ni	10	25	35	15	15

 

Вновь прибывшая заявка занимает свободный канал с меньшим номером. При занятости всех каналов заявка покидает СМО необслуженной. Требуется: 1) построить эмпирическую функцию распределения случайной величины ; 2) методом обратных функций смоделировать входящий поток и поток обслуживания; 3) смоделировать работу СМО методом Монте-Карло; 4) по результатам трех испытаний найти среднее число обслуженных заявок за время T; 5) к одному из испытаний (любому) построить временные диаграммы работы СМО.

Указание: воспользоваться таблицей случайных чисел, приведенной на стр. 24 – 25. В числовых данных задачи: i – номер строки, j – номер столбца для первого случайного числа r_{i j}. Выбор случайных чисел проводить по строкам, начиная с числа r_{i j}, без пропусков и вставок.

 

71.   = 2,   T = 5, i = 1, j = 2.

72.   = 3,   T = 4, i = 2, j = 4.

73.   = 4,   T = 3, i = 3, j = 6.

74.   = 5,   T = 3, i = 4, j = 8.

75.   = 2,   T = 6, i = 5, j = 10.

76.   = 3,   T = 5, i = 6, j = 12.

77.   = 4,   T = 4, i = 7, j = 14.

78.   = 5,   T = 4, i = 8, j = 16.

79.   = 2,   T = 4, i = 9, j = 18.

80.   = 3,   T = 3, i = 10, j = 20.

 

 

Вопросы для выполнения контрольной работы

1. В чем состоят особенности динамических задач оптимизации?

2. Приведите примеры динамической задачи оптимизации.

3.Что такое управление и переменная состояния в динамических моделях?

2. В чем состоит метод динамического программирования в многошаговых задачах оптимизации?

3. Сформулируйте принцип оптимальности Беллмана

4. Как формулируется задача по подбору эмпирических формул.

5. Геометрическая интерпретация задачи построения эмпирической формулы.

6. Функции, используемые для построения эмпирических формул.

7. Метод наименьших квадратов.

8. Выбор наилучшей функции.

9. Орграфы. Основные определения. Матрицы орграфов. Орцепи и орциклы.

10. Неориентированные графы. Основные определения. Полный граф Kn. Матрицы графов. Циклы, цепи. Достижимость. Связность.

11. Эйлеровы и гамильтоновы графы. Задача Эйлера.

12. Деревья, лес. Остовное дерево графа. Цикломатическое и хроматическое числа графа.

13. Что понимается под системами массового обслуживания (СМО) и для чего они предназначены?

14. В чем стоит цель, предмет задачи теории СМО?

15. Какие блоки включает схема СМО?

16.  Что понимается под характеристикой эффективности работы СМО?

17.  Случайный процесс (СП) какого типа протекает в СМО?

18.  Какой процесс называется случайным? Приведите примеры.

19.  Какой СП называется Марковским?

20.  Что представляет собой граф состояний системы?

21.  Какие СП называются дискретными?

22. Какие СП называются непрерывными?

23. Дайте определение состояния без выхода, без входа.

24. Какая система называется эргодической?

25. Дайте определение СП с дискретным и непрерывным временем.

26. Что называется Марковской цепью?

27. Что собой представляют вероятности состояний?

28. Какая Марковская цепь называется однородной (неоднородной)?

29. Дайте определение вероятностей состояний системы, в которой протекает Марковский случайный процесс с непрерывным временем.

30. Что называется плотностью вероятности перехода системы из состояния в состояние?

31. Дайте определение однородного и неоднородного Марковского дискретного процесса с непрерывным временем.

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

33. Какова физическая интерпретация предельных вероятностей состояний дискретной Марковской системы с непрерывным временем?

34. Как составляется система линейных алгебраических уравнений с неизвестными предельными вероятностями по размеченному графу состояний системы?

35. Как составляется система линейных алгебраических уравнений с неизвестными предельными вероятностями по матрице плотностей вероятностей перехода?

36. На какие классы делятся СМО в зависимости от характера потоков?

37. На какие классы делятся СМО в зависимости от числа каналов?

38. На какие классы делятся СМО в зависимости от дисциплины обслуживания?

39. На какие классы делятся СМО в зависимости от ограничения потока заявок?

40. На какие классы делятся СМО в зависимости от количества этапов обслуживания?

41. Кто впервые занимался исследованием многоканальных СМО с отказами?

42. Как называется модель случайного процесса, протекающего в многоканальной СМО с отказами?

43. Что понимается под «потоком обслуживаний» заявок?

44. Как выглядит размеченный граф для многоканальной СМО с отказами?

45. Какие вероятности состояний СМО называются предельными и какой режим функционирования они характеризуют?

46. Что представляет собой приведенная интенсивности входящего потока и какова единица измерения этого показателя?

47. Перечислите основные предельные характеристики эффективности функционирования n-канальной СМО с отказами.

48. Генерирование случайных чисел. Генерирование случайных чисел, распределенных по экспоненциальному закону распределения.

49. Генерирование случайных чисел. Генерирование случайных чисел, распределенных по нормальному закону распределения.

50. Генерирование случайных чисел. Псевдослучайные числа. Генерирование последовательности равномерно распределенных случайных чисел.

51. Дайте определение вероятностей состояний системы, в которой протекает Марковский случайный процесс с непрерывным временем.

52. Дайте определение однородного и неоднородного Марковского дискретного процесса с непрерывным временем.

53. Замкнутая многоканальная СМО.

54. Как имитируется расстояние между двумя случайными событиями пуассоновского потока? Как на практике определить интенсивность порождающего потока случайных событий?

55. Как обеспечить требуемый выходной параметр статической модели, управляя входными воздействиями на нее? Напишите алгоритм, нарисуйте схему реализации.

56. Как определить необходимое число итераций в статистическом эксперименте для достижения заданной точности?

57. Как рассчитать рейтинг проекта в экспертизе методом Кемени? Как рассчитать объективность эксперта?

58. Как составляется система линейных алгебраических уравнений с неизвестными предельными вероятностями по размеченному графу состояний системы?

⇐ Предыдущая123

Поделиться: