Задачи по "Высшей математике"

Задание 2 Решение открытой модели транспортной задачи в матричной форме

                  ∆-методом. 

Исходные данные: А1=65, А2=36, А3=45, А4=60, А5=130, А6=249, А7=115,

                                  А8=116, А9=103, А10=81 (количество порожних вагонов)

                                  В1=190, В2=147, В3=135, В4=93, В5=135, В6=147, В7=253

                                  (план погрузки)

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

Решение: 

    

    Первая  итерация. Решение начинается с приведения открытой модели задачи к закрытому виду путем введения фиктивного получателя, либо отправителя. 

    После разнесения ресурсов каждого из столбцов по клеткам с ∆∆Сij=0 матрицу дополняю 2 столбцами ai и min Cij. Выделяю столбцы, в которых имеются занятые клетки минусовых строк.

Выполняю анализ плюсовых строк:  А3- minC3j=min(0,182,166,8,33,113)=0

                                                А5- minC5j=min(141,119,95,119,137,33)=33

                                               А6- minC6j=min(111,58,258,73,201,60)=58

                                             А9- minC9j=min(235,14,109,0,192,271)=0

                                                          А11- minC11j=min(48,4,78,0,2,56)=0

Вторая  итерация. Поскольку после первой итерации не стало меньше выделенных столбцов, не меняются и значения ai и min Cij. Оценка значений ∆∆Сij в выделенных столбцах не меняется. Наименьшее из значений min ∆∆Cij всех строк также не меняется, но т.к. в строке А3 нет больше ни одной непустой клетки, то нет более ни одного контура перемещения с участием этой строки. Перехожу к следующему по величине значению min ∆∆Cij, это строка А9 (min ∆∆C9j=0). 

      

Третья  итерация.

    

    Поскольку после второй итерации не стало меньше выделенных столбцов, не меняются и значения ai и min Cij. Оценка значений ∆∆Сij в выделенных столбцах не меняется. Наименьшее из значений min ∆∆Cij всех строк также не меняется, но т.к. в строке А3, А8 нет больше ни одной непустой клетки, то нет более ни одного контура перемещения с участием этих строк.

    Четвертая итерация. Поскольку после третьей итерации стало меньше выделенных столбцов, то меняются значения ai и min Cij. Для нулевых строк также определяются min ∆∆Cij.

Выполняю анализ плюсовых строк:  А3- minC3j=min(0,182,166,33,113)=0

                                                              А5- minC5j=min(141,119,95,137,33)=33 

                                                              А6- minC6j=min(111,58,258,201,60)=58

                                                              А9- minC9j=min(235,14,109,192,271)=14

                                                              А11- minC11j=min(48,4,78,2,56)=2

                                                              А8- minC8j=min(238,24,106,233,134)=24  

 
 

    Пятая итерация

Выполняю анализ плюсовых строк:  А3- minC3j=min(0,166,33,113)=0

                                                               А5- minC5j=min(141,95,137,33)=33

                                                               А6- minC6j=min(111,258,201,60)=60

                                                               А9- minC9j=min(235,109,192,271)=109

                                                               А11- minC11j=min(48,78,2,56)=2

                                                               А8- minC8j=min(238,106,233,134)=106

                                                               А10- minC10j=min(58,62,0,341)=0