Расчётно-графическое задание (стр. 3 из 4)

Определяем h²= 0;

Оценка по {4,2}=5464

Определяем пару для ветвления

Q₁₃ = 715+730=1445;

Q₂₁ = 0;

Q₂₄ = 839;

Q₃₁ = 114;

Q₅₆ = 114+961=1075;

Q₆₅ = 345+730=1075

Подходящую оценку имеет маршрут: Q21=0

w

= w(4;2)+ Q21= 6294

Преобразуем матрицу:

Определяем h³= 114+725=839;

Оценка по {2,1}=5464+839=6303

Определяем пару для ветвления

Q₁₃ = 212+730=942;

Q₃₄ = 212;

Q₃₆ = 0;

Q₅₆ = 952;

Q₆₅ = 231+721=952

Подходящую оценку имеет маршрут: Q13=942

w

= w(2;1)+ Q13= 6294+942=7236

Преобразуем матрицу:

Определяем h⁴= 0;

Оценка по {1,3}= 6303

Определяем пару для ветвления

Q₃₄ = 721;

Q₃₆ = 0;

Q₅₆ = 952;

Q₆₅ = 231

Подходящую оценку имеет маршрут: Q36=0

w

= w(1;3)+ Q36= 7236

Преобразуем матрицу:

Матрица приведена

Определяем h⁵=952;

Оценка w{3,6}=6303+721=7024

5464 6303 6303 7024

G₀ 4,2 2,1 1,3 3,6

6294 6294 7236 7236

4,2 2,1 1,3 3,6

Нужный маршрут Казань – Ереван – Донецк – Житомир – Каунас – Калининград.

Т.к. оценка последнего маршрута больше оценки одного из тупиковых ветвей, а именно

, то необходимо доисследовать процесс ветвления этой ветви.

Возвращаемся к исходной матрице расстояний и полагаем в ней

Определяем сумму приводимых элементов

h⁶=5634

Определяем претендентов для ветвления в множестве Y

Претендентами на ветвление могут быть S₁₃, S₂₁, S₂₄, S₃₁, S₄₆, S₅₆,S₆₅

Q₁₃ = 660+9=669;

Q₂₁ = 0;

Q₂₄ = 839;

Q₃₁ = 114;

Q₄₆ =9;

Q₅₆ = 961;

Q₆₅ = 231+730=961

Максимальную оценку имеет маршрут: Q56=961

w

= h⁶+Q56= 5634 + 961 = 6595

Преобразуем матрицу:

Определяем h⁷= 669;

Оценка по {5,6}=5634+669=6303

Определяем пару для ветвления

Q₁₂ = 806;

Q₁₃ = 0;

Q₂₁ = 0;

Q₂₄ = 839;

Q₃₁ = 345;

Q₄₃ = 98;

Q₆₅ = 730+345=1075

Подходящую оценку имеет маршрут: Q24=839

w

= w(5;6)+ Q24= 6595+839=7434

Преобразуем матрицу:

Определяем h⁸= 0;

Оценка по {2,4}=6303

Определяем пару для ветвления

Q₁₂ = 806;

Q₁₃ = 0;

Q₃₁ = 98+345=443;

Q₄₃ = 98;

Q₆₅ = 730+222=952

Подходящую оценку имеет маршрут: Q12=806

w

= w(2;4)+ Q12= 7434+806=8240

Преобразуем матрицу:

Определяем h⁹= 0;

Оценка по {1,2}= 6303

Определяем пару для ветвления

Q₃₁ = 98+345=443;

Q₄₃ = 730+98=828;

Q₆₅ = 730+222=952

Подходящую оценку имеет маршрут: Q43=828

w

= w(4;3)+ Q12= 8240+828=9068

Преобразуем матрицу:

Матрица приведена

Определяем h¹⁰=0;

Оценка w{4,3}=6303

Т.к. получена матрица 2x2 и оценка последнего маршрута не больше всех тупиковых ветвей, то решение оптимально. Маршрутами для завершения могут быть пары (3,1), (6,5).

Составим геометрическую интерпретацию найденного маршрута

5634 5634 6303 6303 6303 6303

G₀ 5,6 2,4 1,2 4,3 3,1

6,5

6595 7434 8240 9068

10744

5,6 2,4 1,2 4,3 3,1 10744

6,5

Нужный маршрут Казань – Ереван – Донецк – Житомир – Каунас – Калининград; x₄₂=1, x₂₁=1, x₁₃=1, x₃₆=1, x₆₅=1, F=5232 км.

Задание №3

На предприятии необходимо выполнить последовательно 12 видов работ (R1÷R12). 12 сотрудников предприятия (S1÷S12) затрачивают на выполнение каждого вида работ различное время в часах. Распределить работников по видам работ так, чтобы общее время на выполнение работ было минимально. Очередность выполнения работ не имеет значения.