Транспортные задачи

Федеральное агентство воздушного транспорта

Федеральное государственное образовательное учреждение высшего профессионального образования

"Московский государственный технический университет гражданской авиации"

Кафедра технической эксплуатации радиоэлектронных систем воздушного транспорта

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

по дисциплине "Исследование операций"

Москва 2010

Задача №1

Исходные данные

Решение

Для сформулированной задачи транспортная таблица имеет вид:

В клетке транспортной таблицы записываются стоимости перевозок из пунктов отправления Аi (i = 1, 2, 3, 4) в пункты назначения Bj (j = 1, 2, 3, 4, 5). Находится начальное опорное решение методом минимальной стоимости. Для этого запасы в Аi пунктов отправления распределяются в соответствии с заявками Bj пунктов назначения и заполняются клетки с минимальными стоимостями перевозок. При этом все запасы должны быть распределены в соответствии с заявками. Вычислим затраты для этого опорного решения.

Z1 = C₁₁ * X₁₁ + C₁₃ * X₁₃ + C₁₅ * X₁₅ + C₂₂ * X₂₂ + C₂₄ * X₂₄ + C₃₂ * X₃₂ + C₃₃ * X₃₃ + C₃₅ * X₃₅ + C₄₁ * X₄₁ + C₄₄ * X₄₄ =

= 349

Для определения сомножителя опорного решения необходимо найти потенциалы заполненных клеток.

Сумма потенциалов равна стоимости перевозок

A1 + B1 =3

A1 + B3 = 1

A1 + B5 = 4

A2 + B2 = 6

A2 + B4 = 1

A3 + B2 = 5

A3 + B3 = 8

A3 + B5 = 2

A4 + B1 = 5

A4 +B4 = 2

Система состоит из 10 уравнений и имеем 9 переменных. Система неопределенная. Поэтому одному из потенциалов задаем произвольное значение. Пусть A1 = 3

Тогда:

B1 = 0

B3 = -2

B5 = 1

A3 = 7

A4 = 5

B4 = -3

A2 = 4

B2 = -2

Значение потенциалов записываем в таблицу рядом с Аi и Bj

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

Начальное опорное решение не является оптимальным, т.к. имеется положительная оценка в A4B5, A3B1, A2B5.

Переходим к новому опорному решению. Необходимо осуществить сдвиг по циклу A4B5 - A2B5. Получим следующую транспортную таблицу.

Вычислим значение целевой функции на этом опорном решении: Z₂=369. Составим уравнения, аналогичные (1)

A1 + B1 =3

A1 + B3 = 1

A1 + B5 = 4

A2 + B2 = 6

A2 + B4 = 1

A3 + B2 = 5

A3 + B3 = 8

A3 + B5 = 3

A4 + B1 = 5

A4 +B4 = 2

Система опять состоит из восьми уравнений и имеет девять переменных. Одному из потенциалов задаем произвольное значение а₄ =0. Тогда,

A1 = 3

A2 = 4

A3 = 10

A4 = 5

B1 = 0

B2 = 2

B3 = -2

B4 = -3

B5 = 1

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

Все оценки не положительны. Следовательно, решение является оптимальным, значение целевой функции: Z₂=369.

Задача №2

Исходные данные:

Таблица возможных перемещений:

Решение

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

Процесс динамического программирования разворачивается от конца (т.В) к началу (т.А), а затем от т.А к т.В. В первый раз находятся условное оптимальное управление и условно минимальные затраты. Во второй раз (от т.А к т.В) определяется безусловное оптимальное управление и безусловно оптимальные затраты.

Любой путь из т.А в т.В состоит из m=4+5 отрезков. Минимальные затраты на всю операцию W складываются из затрат на отдельных участках:

,где l_i затраты на i-м шаге.

Определим условное оптимальное управление.

Условные минимальные затраты:

9 + 5 + 6 + 4 + 7 + 5 + 5 + 9 + 8 = 58

Теперь необходимо построить безусловное оптимальное управление т.е. двигаясь из т.А в т.В.

Условные минимальные затраты:

6 + 5 + 6 + 4 + 6 + 5 + 4 + 6 + 9 = 51

Задача №3

Исходные данные:

- среднее время безотказной работы Т₀=2000 часов;

- среднее время восстановления Т_в=1.5 часа.

Решение:

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

S₀ - работоспособное средство

S₁ - не работоспособное средство (ремонтируется)

Размеченный граф состояний имеет вид:

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

или где:

· P₀ - вероятность нахождения средства в состоянии S_{0 ;}

· P₁ - вероятность нахождения средства в состоянии S_{1 ;}

· л - интенсивность отказов;

· µ_в - интенсивность восстановления.

Нормировочное уравнение:

 или

Тогда:

С учетом исходных данных:

Таким образом все финальные вероятности определены.

Задача №4.

Исходные данные:

· среднее время безотказной работы полукомплекта 2000 часов;

· среднее время восстановления полукомплекта Т_в=2 час;

· среднее время переключения полукомплектов Т_п=60 сек;

Решение:

Резервированные средства имеют следующие состояния:

· S₀ - оба полукомплекта работоспособны;

· S₁ - первый комплект работоспособен, а второй неработоспособен (ремонтируется);

· S₂ - второй комплект работоспособен, а первый неработоспособен (ремонтируется);

· S₃ - оба полукомплекта неработоспособны (ремонтируются).

Размеченный граф состояний имеет вид:

Для рассматриваемого случая линейные алгебраические уравнения Колмогорова имеют вид:

л и µ_в - интенсивность отказа и восстановления.

µ_п - интенсивность переключения

Нормировочное уравнение имеет вид:

(5)

Из уравнений (2) и (3) видно, что . Тогда уравнение (1) запишется в виде:

или

Уравнение (4) имеет вид:

Перепишем уравнение (5) в виде:

Откуда

.

Так как 2Т_пТ₀ >> Т_пТ_в , то получим:

= 2000 / 2000,03332 = 0,999998335027,

Подставив исходные данные (Т_п, Т_0, Т_в) получим количественные данные значения Определим среднее время безотказной работы резервированной системы:

ч.