Системное програмирование

 

  В новой таблице элементы строк  А₂ и А₃ получены в результате прибавления к соответствующим числам строк А₂ и А₃ (являющихся недостаточными) табл. 5 промежуточной ренты, т. е. 1. В результате в табл. 6 число клеток для заполнения возросло еще на одну и стало равным 6. Определяем указанные клетки и заполняем их. Сначала заполняем клетки А₁В₃, A₂B₁, A₂B₂, А₂В₄, а затем А₃В₅, А₂В₅, А₁В В результате все имеющиеся запасы поставщиков распределяются в соответствии с фактическими потребностями пунктов назначения. Число заполненных клеток равно 7, и все они имеют наименьший показатель с_ij. Следовательно, получен оптимальный план исходной транспортной задачи:

 При этом плане  перевозок общие затраты таковы: S = 4*120 + 5*60+1*110 + 8*90 + 5*80 + 3*70 + 4*20 = 2300.

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

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

 Для определения опорного плана транспортной задачи будем пользоваться одним  из методов, рассмотренных в предыдущем параграфе. Эти методы гарантируют  получение занятых в исходном плане n + m - l клеток, причем в некоторых из них могут стоять нули. Полученный план следует проверить на оптимальность.

  Теорема 1. Если для некоторого опорного плана Х*= (x_ij*) (i = l,m; j = 1,n) транспортной задачи существуют такие числа a₁, a₂, …, a_m , b₁, b₂,…, b_n что

b_j - a_i =c_ij при x_ij > 0   (9)

и

b_j - a_i £  c_ij при x_ij = 0   (10)

для всех i = l,m и j = 1,n, то Х*= (x_ij*) — оптимальный план транспортной задачи.

  Определение 1. Числа a_i , и b_j (i = l,m; j = 1,n) называются потенциалами соответственно пунктов назначения и пунктов потребления.

  Сформулированная  теорема позволяет построить  алгоритм нахождения решения транспортной задачи. Он состоит в следующем. Пусть  одним из рассмотренных выше методов  найден опорный план транспортной задачи. Для каждого из пунктов отправления  и назначения определяют потенциалы a_I , и b_j (i = l,m; j = 1,n). Эти числа находят из системы уравнений

b_j - a_i =c_ij   (11)

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

  Так как число заполненных клеток равно n + m — 1, то система (11) с n + m неизвестными содержит п + т— 1 уравнений: Поскольку число неизвестных превышает на единицу число уравнений, одно из неизвестных можно положить равным произвольному числу, например a₁ = 0, и найти последовательно из уравнений (11) значения остальных неизвестных. После того как все потенциалы найдены, для каждой из свободных клеток определяют числа a_ij = b_j - a_i -c_ij .. 

                                             

                   

рис. 2.

  Если  среди чисел a_ij , нет положительных, то найденный опорный план является оптимальным. Если же для некоторой свободной клетки a_ij > 0, то исходный опорный план не является оптимальным и необходимо перейти к новому опорному плану. Для этого рассматривают все свободные клетки, для которых a_ij > 0, и среди данных чисел выбирают максимальное. Клетку, которой это число соответствует, следует заполнить.

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

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

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

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

  1) каждой из клеток, связанных циклом с данной свободной клеткой, приписывают определенный  знак,  причем  свободной клетке — знак плюс, а всем  остальным  клеткам — поочередно знаки минус и плюс (будем называть эти клетки минусовыми и плюсовыми);

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

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

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

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

  Полученный  новый опорный план транспортной задачи проверяют на оптимальность. Для этого определяют потенциалы пунктов отправления и назначения и находят числа a_ij = b_j - a_i -c_ij , для всех свободных клеток. Если среди этих чисел не окажется положительных, то это свидетельствует о получении оптимального плана. Если же положительные числа имеются, то следует перейти к новому опорному плану. В результате итерационного процесса после конечного числа шагов получают оптимальный план задачи.

  Из  изложенного выше следует, что процесс  нахождения решения транспортной задачи методом потенциалов включает следующие  этапы:

1. Находят опорный план. При этом число заполненных клеток должно быть равным п + т— 1.
2. Находят потенциалы b_j и a_i, соответственно пунктов назначения и отправления.
3. Для каждой свободной клетки определяют число a_ij. Если среди чисел a_ij нет положительных, то получен оптимальный план транспортной задачи; если же они имеются, то переходят к новому опорному плану.

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

    Полученный опорный план проверяют  на оптимальность, т. е. снова  повторят все действия, начиная  с этапа 2.

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

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

таблица 7

  Решение. Сначала, используя метод северо-западного угла, находим опорный план задачи. Этот план записан в табл. 7.

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

b₁ - a₁ = 1,  b₂ - a₁ = 2,  b₂ - a₂ = 3,

b₃- a₂ = 1,  b₄ - a₂ = 5,  b₄ - a₃ = 4,

с семью неизвестными. Полагая a₁ =0, находим b₁ = l, b₂ = 2, a₂=-1, b₃= 0, b₄ = 4, a₃=0.

Для каждой свободной  клетку вычисляем число a_ij = b_j - a_i -c_ij :

a₁₃= -4, a₁₄ = 3, a₂₁ = a₃₂=0, a ₃₁= -2, a₃₃ = -4.

  Заключаем найденные числа в рамки и  записываем их в каждую из свободных клеток табл. 2.8.

Так как  среди чисел a_ij имеются положительные, то построенный план перевозок не является оптимальным и надо перейти к новому опорному плащу. Наибольшим среди положительных чисел a_ij, являются a₁₄ = 3, поэтому для данной свободной клетки строим цикл пересчета (табл. 8) и производим сдвиг по этому циклу. Наименьшее из чисел в минусовых клетках равно 10. Клетка, в которой находится это число, становится свободной в новой табл. 9. Другие числа в табл. 9 получаются так: к