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

Задача №1

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

Решение

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

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

Z1 = C11 * X11 + C13 * X13 + C15 * X15 + C22 * X22 + C24 * X24 + C32 * X32 + C33 * X33 + C35 * X35 + C41 * X41 + C44 * X44 =

= 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. Получим следующую транспортную таблицу.

Вычислим значение целевой функции на этом опорном решении: Z2=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

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

A1 = 3

A2 = 4

A3 = 10

A4 = 5

B1 = 0

B2 = 2

B3 = -2

B4 = -3

B5 = 1

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

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

Задача №2

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

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

Решение

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

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

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

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

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

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

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

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

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

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

Задача №3

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

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

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

Решение:

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

S0 – работоспособное средство

S1 – не работоспособное средство (ремонтируется)

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

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

или где:

· P0 - вероятность нахождения средства в состоянии S0 ;

· P1 - вероятность нахождения средства в состоянии S1 ;

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

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

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

или

Тогда:

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

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

Задача №4.

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

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

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

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

Решение:

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

· S0 – оба полукомплекта работоспособны;

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

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

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

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

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

λ и µв – интенсивность отказа и восстановления.

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

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

(5)

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

или

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

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

Откуда

.

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

= 2000 / 2000,03332 = 0,999998335027,

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

ч.