Математическое программирование

 

     Минимальный тариф, равный 1, находится в клетке для переменной х₁₃. Положим х₁₃=160, запишем это значение в соответствующую клетку таблицы и исключим временно из рассмотрения строку А₁. Потребности пункта назначения В₃ считаем равным 30 ед.

     В оставшейся части таблицы клетка с наименьшим значением тарифа находится  на пересечении строки А₃ и столбца В₂, где с₃₂=2. Положим х₃₂=50 и внесем это значение в соответствующую клетку таблицы.

     Временно  исключим из рассмотрения столбец В₂ и будем считать запасы пункта А₃ равными 120 ед. После этого снова рассмотрим оставшуюся часть таблицы. В ней минимальный тариф находится на пересечении строки А₃ и столбца В₃ и равен 3. Заполним соответствующую клетку таблицы и аналогично заполняем (в определенной последовательности) клетки, находящиеся на пересечении строки А₂ и столбца В₁, строки А₃ и столбца В₄, строки А₂ и столбца В₄. в результате получим опорный план

     

     При данном плане перевозок общая  стоимость перевозок составляет

       

3. Метод потенциалов.

 

     Для определения оптимального плана  транспортной задачи разработано несколько методов, но наиболее часто используется метод потенциалов.

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

     Теорема. Если для некоторого опорного плана транспортной задачи существуют такие числа U1, U2, …, U_m, V₁, V₂, …, V_n, что

        при    

     и

          при  

     для всех i=1,m  и j=1,n   , то - оптимальный план транспортной задачи.

     Определение. Числа Ui и Vj  называются потенциалами соответственно пунктов назначения и пунктов потребления.

     Сформулированная  теорема позволяет построить  алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть одним из рассмотренных выше методов найден опорный план транспортной задачи. Для каждого из пунктов отправления и назначения определяют потенциалы Ui и Vj  . Эти числа находят из системы уравнений , где с_ij – тарифы, стоящие в заполненных клетках таблицы условий транспортной задачи.

     Т.к. число заполненных клеток равно  n+m-1, то система с n+m неизвестными содержит n+m-1 уравнений. Поскольку число неизвестных превышает на единицу число уравнений, одно из неизвестных можно положить равным произвольному числу, например U₁=0, и найти последовательно из системы уравнений значения остальных неизвестных. После того, как все потенциалы найдены, для каждой из свободных клеток определяют числа (оценка свободных клеток). Если среди оценок нет отрицательных, то найденный опорный план является оптимальным. Если среди оценок есть оценки, равные нулю, то найденный опорный план является не единственным оптимальным планом. Если же для некоторой свободной клетки <0, то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых <0, и среди данных чисел выбирают максимальное по абсолютной величине. Клетку, которой это число соответствует, следует заполнить.

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

     Определение. Циклом в таблице условий транспортной задачи называется ломаная линия, вершины которой расположены в занятых клетках таблицы, а звенья вдоль строк и столбцов, причем в каждой вершине цикла встречается ровно два звена, одно из которых находится в строке, а другое – в столбце.

     Если  ломаная линия, образующая цикл, пересекается, то точки самопересечения не являются вершинами.

     

     При правильном построении опорного плана  для любой свободной клетки можно построить лишь один цикл. После того как для выбранной свободной клетки он построен, следует перейти к новому опорному плану. Для этого необходимо переместить грузы в пределах клеток, связанных с данной свободной клеткой. Это перемещение производят по следующим правилам:

1. каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный знак, причем свободной клетке – знак плюс, а всем остальным клеткам – поочередно знаки минус и плюс (будем называть эти клетки минусовыми и плюсовыми);
2. в данную свободную клетку переносят меньшее из чисел x_ij, стоящих в минусовых клетках. Одновременно это число прибавляют к соответствующим числам, стоящим в плюсовых клетках, и вычитают из чисел, стоящих в минусовых клетках. Клетка, которая ранее была свободной, становится занятой, а минусовая клетка, в которой стояло минимальное из чисел x_ij , считается свободной.

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

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

     Следует отметить, что при сдвиге по циклу  пересчета число занятых клеток остается неизменным, а именно равным n+m-1. При этом если в минусовых клетках имеется два (или) более) одинаковых числа, то освобождают лишь одну из таких клеток, а остальные оставляют занятыми (с нулевыми поставками).

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

     Пример. Три комбината строительных материалов выпускают фундаментные блоки, а четыре строительных управления нуждаются в этих фундаментных блоках. Найти оптимальный план перевозки груза от потребителя к заказчику. Данные о запасах, потребностях и тарифах на перевозку грузов приведены в таблице. 

 
 

     Найдем  первый опорный план методом северо-западного  угла. Задача закрытого типа. В результате произведенного распределения весь груз вывезен от поставщиков, а запросы потребителей полностью удовлетворены. Заполнены 6 клеток (m+n-1=6).

     Матрица перевозки грузов имеет вид

     

     Стоимость перевозки при таком распределении  равна

     F=8*35+7*10+6*15+8*30+7*20+9*30=280+70+90+240+140+270=1090 (ден.ед.)

     Проверим  оптимальность данного распределения  методом потенциалов.

     Для определения потенциалов составим систему из 6 уравнений с 7 неизвестными для базисных (занятых) клеток.

             

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

     

     Т.к. среди оценок есть отрицательные (-5; -3; -1), то найденный опорный план не является оптимальным.

     Для улучшения плана перераспределим  грузы, с этой целью для клетки с минимальной отрицательной  оценкой ( ) построим цикл пересчета.

     

     Произошло перераспределение груза в пользу клеток с меньшим тарифом. Запишем матрицу распределения груза:

     

     Стоимость перевозки согласно новому опорному плану равна:

     F=35*8+25*6+20*8+30*7+20*9+10*6=280+150+160+210+180+60=1040

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

 

     Для определения потенциалов составим систему из 6 уравнений с 7 неизвестными для базисных (занятых) клеток.

             

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

     

     Т.к. среди оценок есть отрицательные (-3; -3; -6), то найденный опорный план не является оптимальным.

     Для улучшения плана перераспределим  грузы, с этой целью для клетки с минимальной отрицательной  оценкой ( ) построим цикл пересчета.

     Min( 35;20)

       
 
 
 
 

 Строим новую таблицу