Иследование транспортнои задачи по критериям стоимости и времени

     Первый  этап.

Если  все ненулевые элементы матрицы окажутся в выделенных столбцах, то переходят к третьему этапу. В противном случае пусть некоторый невыделенный нуль находится в i-й  строке и в j-м столбце. Тогда вычисляют значения невязки i-й строки .

Возможен  один из двух случаев: 1) , 2) . В первом случае i-ю строку Сk отмечают знаком '+' справа  от нее, а сам невыделенный нуль отмечают штрихом. Далее просматривают элементы i-й строки, которые лежат в выделенных столбцах и ищут среди

них существенные нули.

       Если таким существенным нулем  оказался элемент  ,  а сам столбец m - выделен, то знак выделения '+' над столбцом m уничтожают, а сам этот нуль отмечают звездочкой.  Затем просматривают m-й столбец и отыскивают в нем нуль (нули), расположенные в отличных от i-й строках. Если такой нуль имеется, то отмечают его штрихом и анализируют невязку его строки. Далее процесс поиска нулей и выделение их (штрихами или звездочками) продолжается аналогично, и за несколько шагов он заканчивается одним из следующих исходов:

1. найдем очередной невыделенный нуль матрицы Сk, для которого невязкая в строке .  Тогда отметив его штрихом, переходим ко второму этапу;
2. все нули матрицы Сk оказались выделенными, причем для каждого из нулей, выделяемых штрихом, невязка . Тогда переходим к третьему этапу.

Во втором случае, отметив этот нуль штрихом, сразу переходим к третьему этапу.

         Второй этап.

Состоит в построении цепочки из нулей  матрицы Сk, отмеченных штрихами и звездочками, и в последующем переходе к новой матрице . Пусть для некоторого нуля со штрихом матрицы Сk, расположенного, например, в позиции , невязка строки .Начиная с этого элемента , строят цепочку из отмеченных нулей матрицы Сk: двигаясь по столбцу , выбирают нуль со звездочкой , далее двигаясь от него по строке , находят нуль со штрихом . Потом движутся от него по столбцу к следующему нулю со звездочкой и т.д.. Такой последовательный переход от 0' к 0* по столбцу и от 0* к 0' по строке осуществляют до тех пор, пока это возможно. После этого осуществляют переход к матрице от матрицы по формулам

     

     

     Таким образом, -минимальный элемент среди совокупности четных элементов цепочки, невязки строки, где начинается цепочка, и столбца, где она заканчивается.Вычисляем невязку . На этом (k+1)-я итерация заканчивается.

     Третий  этап.

     Пусть , где минимум выбирают из всех невыделенных элементов матрицы Сk. Тогда из всех элементов невыделенных строк матрицы Сk вычитают h, а ко всем элементам выделенных столбцов прибавляют h. В результате получают матрицу С'k(С'k ~ Ck), в которой все существенные нули матрицы Сk остаются нулями, и кроме того, появляются новые невыделенные нули. 
 

    

      
 

     3.3 Метод запрещенных  клеток

     

Задача на дооптимизацию по времени перевозки при заданных минимальных затратах 

          

     При ограничениях

     

         

         

      

     Алгоритм  решения базируется на идеях венгерского  метода для классической транспортной задачи и элементарном здравом смысле. Предварительно выбирается минимальное  значение и запрещаются к рассмотрению все клетки, время которых превышает выбранное ( < ). Тогда пытаются найти план, минимизирующий затраты на перевозку при разрешенных клетках. Если такой план найти не удается или же затраты не равны , то увеличиваем , расширяя таким образом множество клеток доступных для рассмотрения. Наличие запрещенных клеток не повлияет на алгоритм второго этапа венгерского метода, потому он останется без изменений. Остальные же должны учитывать ограничение по . 
 
 

Предварительный этап.

     В каждом из столбцов матрицы транспортных издержек отыскивают минимальный элемент в клетках с , который вычитают из всех элементов этого столбца для которых . Получают матрицу С'. Далее в каждой строке матрицы С' выбирают минимальный элемент в клетках с и вычитают его из всех элементов рассматриваемой строки для которых .  Приходят к матрице С0 (С0 ~ C), все элементы которой неотрицательны. Строят матрицу Х0 так, чтобы ее ненулевые элементы были расположены в позициях нулей матрицы С0. Пусть - номер строки, в которой расположен k-й нуль j-го столбца матрицы С0. Тогда элементы первого столбца матрицы Х0 определяют по рекуррентной формуле

     Если  , то - оптимальный план Т-задачи. Иначе переходим к первой итерации.

     (k+1)-я  итерация.

     Перед началом итерации выделяют знаком '+' те столбцы матрицы  , для которых невязки по столбцам равны нулю.

     Первый  этап.

Если  все ненулевые элементы матрицы  окажутся в выделенных столбцах или в запрещенных клетках, то переходят к третьему этапу. В противном случае пусть некоторый невыделенный нуль находится в i-й  строке и в j-м столбце. Тогда вычисляют значения невязки i-й строки .

Возможен  один из двух случаев: 1) , 2) . В первом случае i-ю строку Сk отмечают знаком '+' справа  от нее, а сам невыделенный нуль отмечают штрихом. Далее просматривают элементы i-й строки, которые лежат в выделенных столбцах и не в запрещенных клетках, и ищут среди них существенные нули.

       Если таким существенным нулем  оказался элемент  ,  а сам столбец m - выделен, то знак выделения '+' над столбцом m уничтожают, а сам этот нуль отмечают звездочкой.  Затем просматривают m-й столбец и отыскивают в нем нуль (нули), расположенные в отличных от i-й строках и не в запрещенных клетках. Если такой нуль имеется, то отмечают его штрихом и анализируют невязку его строки. Далее процесс поиска нулей и выделение их (штрихами или звездочками) продолжается аналогично, и за несколько шагов он заканчивается одним из следующих исходов:

3. найдем очередной невыделенный нуль матрицы Сk, для которого невязкая в строке .  Тогда отметив его штрихом, переходим ко второму этапу;
4. все нули матрицы Сk оказались выделенными, причем для каждого из нулей, выделяемых штрихом, невязка . Тогда переходим к третьему этапу.

Во втором случае, отметив этот нуль штрихом, сразу переходим к третьему этапу.

Второй  этап.

Состоит в построении цепочки из нулей  матрицы Сk, отмеченных штрихами и звездочками, и в последующем переходе к новой матрице . Пусть для некоторого нуля со штрихом матрицы Сk, расположенного, например, в позиции , невязка строки .Начиная с этого элемента , строят цепочку из отмеченных нулей матрицы Сk: двигаясь по столбцу , выбирают нуль со звездочкой , далее двигаясь от него по строке , находят нуль со штрихом . Потом движутся от него по столбцу к следующему нулю со звездочкой и т.д.. Такой последовательный переход от 0' к 0* по столбцу и от 0* к 0' по строке осуществляют до тех пор, пока это возможно. После этого осуществляют переход к матрице от матрицы по формулам 

 

     

     

     Таким образом, -минимальный элемент среди совокупности четных элементов цепочки, невязки строки, где начинается цепочка, и столбца, где она заканчивается.Вычисляем невязку . На этом (k+1)-я итерация заканчивается.

     Третий  этап.

     Пусть ,  где минимум выбирают из всех невыделенных элементов матрицы Сk и которые не находятся в запрещенных клетках. Если такой элемент нельзя найти (все не запрещенные клетки выделены), то увеличиваем время , сбрасываем счетчик итераций и идем на предварительный этап. Тогда из всех элементов невыделенных строк матрицы Сk, для которых , вычитают h, а ко всем элементам выделенных столбцов, для которых , прибавляют h. В результате получают матрицу С'k(С'k ~ Ck), в которой все существенные нули матрицы Сk остаются нулями, и кроме того, появляются новые невыделенные нули. 

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

4. Описание программы

     4.1 Основные функции 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

4.2 Листинг программы 

4.3 Руководство пользователя 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 
 

5. Анализ результатов

Параметры: 

Матрица затрат на перевозку

Таб.1