Расчётно-графическое задание

Оценка  по {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) затрачивают на выполнение каждого вида работ различное время в часах. Распределить работников по видам работ так, чтобы общее время на выполнение работ было минимально. Очередность выполнения работ не имеет значения.

     Составить экономико-математическую модель задачи и решить задачу с помощью венгерского  алгоритма.

 

     Составляем  экономико-математическую модель задачи

     F = 10x₁₁ + 2x₁₂ + 3x₁₃ + 7x₁₄ + 7x₁₅ + 9x₁₆ + 10x₁₇ + 10x₁₈ + 10,5x₁₉ + 12x₁₁₀ + 14,5x₁₁₁ + 7x₁₁₂ + 12x₂₁ + x₂₂ + 5x₂₃ + 6,5x₂₄ + 8x₂₅ + 10,5x₂₆ + 8x₂₇ + 9x₂₈ + 12x₂₉ + 11x₂₁₀ + 15x₂₁₁ + 7,5x₂₁₂ + 11x₃₁ + x₃₂ + 3,5x₃₃ + 6,5x₃₄ + 8x_3,5 + 10,5x₃₆ + 8x₃₇ + 9x₃₈ + 12x₃₉ + 11x₃₁₀ + 15x₃₁₁ +17,5x₃₁₂ + 11x₄₁ + 2x₄₂ + 4x₄₃ + 6,5x₄₄ + 8x₄₅ + 11x₄₆ + 8x₄₇ + 9,5x₄₈ + 12x₄₉ + 12x₄₁₀ + 15,5x₄₁₁ + 7,5x₄₁₂ + 10x₅₁ + 2,5x₅₂ + 4x₅₃ + 5x₅₄ + 8x₅₅ + 11,5x₅₆ + 8,5x₅₇ + 8x₅₈ + 11x₅₉ + 12x₅₁₀ + 15,5x₅₁₁ + 6x₅₁₂ + 10x₆₁ + 2,5x₆₂ + 4,5x₆₃ + 5x₆₄ + 7,5x₆₅ + 10,5x₆₆ + 8,5x₆₇ + 8x₆₈ + 11x₆₉ + 12x₆₁₀ + 15x₆₁₁ + 6x₆₁₂ + 9,5x₇₁ + x₇₂ + 4x₇₃ + 5,5x₇₄ + 7,5x₇₅ + 10,5x₇₆ +8,5x₇₇ + 9x₇₈ + 11x₇₉ + 12x₇₁₀ + 15,5x₇₁₁ + 6x₇₁₂ + 9,5x₈₁ + 1x₈₂ + 3,5x₈₃ + 6,5x₈₄ + 7x₈₅ + 10,5x₈₆ + 10x₈₇ + 10,5x₈₈ + 12x₈₉ + 10x₈₁₀ + 15,5x₈₁₁ + 6x₈₁₂ + 9,5x₉₁ + 3x₉₂ + 3x₉₃ + 3,5x₉₄ + 6,5x₉₅ + 7x₉₆ + 11x₉₇ + 10,5x₉₈ + 10x₉₉ +12x₉₁₀ +15x₉₁₁ + 7x₉₁₂ + 8x₁₀₁ + 3x₁₀₂ + 3x₁₀₃ + 6,5x₁₀₄ + 7x₁₀₅ + 11x₁₀₆ + 10,5x₁₀₇ + 10x₁₀₈ + 9,5x₁₀₉ + 12x₁₀₁₀ + 15,5x₁₀₁₁ + 6,5x₁₀₁₂ + 8x₁₁₁ + 3x₁₁₂ + 3x₁₁₃ + 6,5x₁₁₄ + 7,5x₁₁₅ + 10x₁₁₆ + 11x₁₁₇ + 10,5x₁₁₈ + 9,5x₁₁₉ + 12x₁₁₁₀ + 15,5x₁₁₁₁ + 6,5x₁₁₁₂ + 8x₁₂₁ + 3x₁₂₂ + 3x₁₂₃ + 6,5x₁₂₄ + 7,5x₁₂₅ + 9x₁₂₆ + 11x₁₂₇ + 10,5x₁₂₈ + 9,5x₁₂₉ + 12x₁₂₁₀ + 15x₁₂₁₁ + 6,5x₁₂₁₂ min

 

 
 
 
 
 
 
 
 
 

     По  исходным данным составляем таблицу

 

 Преобразуем  составляемую таблицу

     1     2     3       4     5    6      7      8      9     10     11     12

       
 
 
 
 
 
 
 
 
 
 
 

       1    2   3      4      5     6     7     8      9     10    11   12

     Произведем  назначение каждого сотрудника на один из видов работ:

     S₁→R₂; S₂→?; S₃→?; S₄→R₇; S₅→R₄; S₆→R₈; S₇→?; S₈→?; S₉→R₅; S₁₀→R₁; S₁₁→R₃; S₁₂→R₉

       Решение не оптимально; не можем назначить  всех сотрудников на выполнение работ.

     Делаем  дальнейшее преобразование таблицы.

     Минимальное число, через которое не проходит ни одна линия: 0,5

             1       2      3       4      5      6     7    8      9     10    11    12

     

Произведем назначение каждого сотрудника на один из видов  работ:

     S₁→R₁₁; S₂→R₂; S₃→?; S₄→R₇; S₅→R₄; S₆→R₈; S₇→?; S₈→?; S₉→R₅; S₁₀→R₁; S₁₁→R₃; S₁₂→R₉

          Решение не оптимально; не можем назначить  всех сотрудников на выполнение работ.

     Делаем  дальнейшее преобразование таблицы.

     Минимальное число, через которое не проходит ни одна линия: 0,5 

       
 

      1       2      3      4      5     6     7     8      9    10    11   12

 

Произведем назначение каждого сотрудника на один из видов  работ:

     S₁→R₁₁; S₂→R₂; S₃→?; S₄→R₇; S₅→R₄; S₆→R₈; S₇→?; S₈→?; S₉→R₅; S₁₀→R₁; S₁₁→R₃; S₁₂→R₉

          Решение не оптимально; не можем назначить  всех сотрудников на выполнение работ.