Первый шаг алгоритма метода потенциалов – первая итерация. Более компактно транспортная модель представляется в виде так называемой транспортной таблицы, имеющей вид матрицы, в которой строки соответствуют исходным пунктам – лесосеки, а столбцы – пунктам потребления – погрузочные пункты. Коэффициенты себестоимости или затрат, руб./м3, располагаются в правом верхнем углу каждой клетки, i, j. На пересечении соответствующих строк и столбцов в клетках показываются объемы транспортировки, не противоречащие поставленным ограничениям.
Базисными переменными в транспортной таблице считаются те, которым присвоено какое-либо значение объема транспортировки. Поставленная транспортная задача имеет т+(n-1) независимых уравнений, и начальное допустимое решение должно иметь т+(n-1) базисных переменных. Сущность начального допустимого решения заключается в том, что необходимо получить такое допустимое распределение объемов транспортировки по маршрутам, при котором удовлетворялись бы поставленные ограничения.Иначе, сумма всех объемов по строкам и столбцам равнялась бы объемам заготовки соответствующих лесосек и объемам потребления (вместимости) соответствующих погрузочных пунктов.
Для нахождения начального базисного допустимого решения используется процедура, основанная на правиле северо-западного угла (известен также метод минимальной стоимости по принципу первоначального распределения объемов по маршрутам, имеющим минимальную себестоимость в порядке ее возрастания). На основе правила северо-западного угла объемы трелевки по маршрутам распределяются так, чтобы они удовлетворяли поставленным ограничениям, т. е. были бы допустимыми. Следуя этому правилу переменной х11, расположенной в северо-западном углу таблицы, приписывается максимальное значение, допустимое ограничением на отгрузку Q1 или потребление V1. После этого вычеркивается соответствующий столбец или строка, для которого дальнейшее заполнение остальных клеток недопустимо по поставленному ограничению. Эта операция фиксирует тот факт, что остальные переменные вычеркнутого столбца равны нулю. Если ограничение выполняется одновременно для столбца и строки, то вычеркивается произвольно либо строка, либо столбец. Оставшийся объем распределяется на следующие клетки не вычеркнутых либо строки, либо столбца и так далее, до тех пор, пока не останется не вычеркнутой одна строка (столбец).
| Рис. 5.20. Начальное допустимое решение |
Процесс получения начального допустимого решения в целом выглядит следующим образом (в последовательности перехода и назначения объемов в 1 м3 по маршрутам от переменной к переменной). Из того, что модель предварительно была сбалансирована, Q=V, то отсюда следует, что одно уравнение является зависимым и транспортная модель содержит m+(n-1) (3+3-1=5) независимых уравнений и начальное базисное допустимое решение должно иметь 5 базисных переменных. Для нахождения начального базисного допустимого решения используем процедуру, основанную на правиле северо-западного угла
Базисные переменные (рис. 5.20) принимают значения x11=200=>х12=50=>x22=100=>х23=50=>х33=50, остальные небазисные переменные равняются нулю. В реальности данный план означает, что необходимо производить трелевку в указанных объемах, соответственно, из первой лесосеки на первый погрузочный пункт, из первой во второй, из второй во второй, из второй в третий, из третьей в третий. Для полученного плана затраты на трелевку составляют 200•2 + 50•1,5 + 100•2 + 50•1 + 50•0=735 руб. в смену.
Оптимален ли этот план? На этот вопрос дает ответ условие оптимальности симплекс-метода (см. разд. 5.3.8, наличие положительных коэффициентов при небазисных переменных транспортной таблицы).
Второй шаг алгоритма – нахождение включаемой в базис переменной на основе метода потенциалов. В методе потенциалов строке i и столбцу j транспортной таблицы ставятся в соответствие числа и vj. Для каждой базисной переменной xij текущего решения потенциалы и vj должны удовлетворять уравнению +vj=cij. Количество таких уравнений, соответствующих базисным переменным, в виде системы т+п-1, и в этой системе (т+п) неизвестных. Если количество уравнений, соответствующих базисным переменным, менее чем т+п-1 (например, т+п-2), то для успешной реализации данного шага алгоритма за базисную принимается любая небазисная переменная, наиболее удобная для последующего построения цикла. Значения потенциалов можно определить из системы, придавая одному их них произвольное значение (обычно полагается j=0). Затем решается система из т+п-1 уравнений относительно т+п-1 остальных потенциалов. Оценки для небазисных переменных хpq определяются после получения решения для базисных переменных в соответствии с соотношением Сpq=ир+vq- (величины Сpq не зависят от выбора значения иi).
В дальнейшем на основе Сpq для включения в базис выбирается небазисная переменная, имеющая наибольшее положительное значение Сpq (сравните с условием оптимальности симплекс-метода при решении задачи на отыскание минимума – в качестве включаемой в базис переменной выбирается та, при которой коэффициент в уравнении функции цели имеет наибольшее положительное значение). Используем рассмотренный метод к условиям поставленной нами задачи (см. рис. 5.21):
x11: u1+v1=c11=2;
x12: u1+v2=c12=1,5;
x22: u2+v2=c22=2;
x23: u2+v3=c23=1;
x33: u3+v3=c33=0.
Полагая иi=0, получим v1=2; v2=1,5; и2=0,5; v3=0,5; u3=-0,5. Оценки потенциалов для небазисных переменных:
x13: C13=u1+v3-c13=0+0,5-4=-3,5
x21: C21=u2+v1-c23=0,5+2-3=-0,5
x31: C13=u3+v1-c31=-0,5+2-0=1,5
x21: C32=u3+v2-c32=-0,5+1,5-0=1
В соответствии с условием оптимальности небазисная переменная х31 (выделена подчеркиванием в тексте и штриховкой на рис. 5.21), имеющая максимальную положительную оценку С31, принимается в качестве включаемой в базис.
Третий шаг алгоритма - нахождение исключаемой из базиса переменной и нового базисного решения. Нахождение переменной, исключаемой из базиса, производится посредством построения цикла. Этот шаг эквивалентен соответствующему шагу симплекс-метода (см. разд. 5.3.8) и выполняется на основе его условия допустимости. Однако здесь есть свои особенности применения условия допустимости, определяемые тем, что все коэффициенты в ограничениях транспортной задачи равны либо нулю, либо единице. Поэтому при проверке условия допустимости отношения будут иметь знаменатель, всегда равный единице. Исходя из изложенного, вместо отношений следует брать значения самих базисных переменных.
Для определения минимального отношения строится замкнутый цикл, соответствующий включаемой в базис переменной х31 на данной итерации для рассматриваемой постановки задачи.
Правила построения цикла следующие: 1) цикл начинается и заканчивается включаемой в базис небазисной переменной; 2) он состоит из последовательности горизонтальных и вертикальных (связанных) отрезков, концами которых должны быть базисные переменные, за исключением тех концов, которые относятся к включаемой в базис переменной; 3) количество всех переменных, охваченных циклом, должно быть четным; 4) при построении цикла не существенно, в каком направлении – против или по часовой стрелке – происходит обход цикла.
| Рис. 5.21. Второй и третий шаги первой итерации |
Рассмотрим иллюстрацию цикла на нашем примере. Последовательность обхода и построения цикла согласно изложенным правилам следующая: x31=>x11=>x12=>x22=>x23=>x33=>x31
Если значение (см. рис. 5.21) вводимой в базис переменной x31 увеличивается на какую-либо величину, то для сохранения допустимости решения значения базисных переменных, стоящих на изломах рассматриваемого цикла, необходимо скорректировать следующим образом: уменьшить х11 на эту величину, увеличить x12 на эту величину, уменьшить x22 на эту величину и т. д. в соответствии со знаками “-“(уменьшить) и "+"(увеличить), расставленными в соответствующих клетках таблицы. При подобном перераспределении объемов трелевки по маршрутам не будут нарушаться ограничения задачи на объемы заготовленной древесины с лесосек и объемы вместимости на погрузочных пунктах.
Переменная, исключаемая из базиса, выбирается из находящихся на изломах цикла переменных, значения которых уменьшаются при увеличении x31. Они располагаются в таблице на местах, отмеченных знаком "-", это – x11, x22, x33. Выводимой из базиса становится та, которая имеет наименьшее значение, поскольку именно она раньше всех достигает нуля, и любое дальнейшее уменьшение делает ее отрицательной (сравните с условием допустимости симплекс-метода, где исключаемая переменная определяется минимальным соотношением, здесь знаменатель равен 1). В нашем случае минимальна х33=50, тогда значение x31=50; х11=150; х12=100; х22=50; х23=100, и транспортная таблица принимает вид, представленный на рис. 5.22.
Суммарные затраты на трелевку (функция цели) для полученного плана равняются у=150•2+100•1,5 +50•2+100•1+50•0=650 руб.
Оптимальность нового решения определяется вычислением новых потенциалов:
x11: u1+v1=2;
x12: u1+v2=1,5;
x22: u2+v2=2;
x23: u2+v3=1;
x31: u3+v1=0.
Полагая u1=0, получим v1=2; v2=1,5; u2=0,5; v3=0,5; u3=-2. Оценки потенциалов для небазисных переменных:
x13: C13=u1+v3-c13=0+0,5-4=-3,5
x21: C21=u2+v1-c21=0,5+2-3=-0,5
x32: C32=u3+v2-c32=-2+1,5-0=-0,5
x33: C33=u3+v3-c33=-2+0,5-0=-1,5
| Рис. 5.22. Оптимальное решение |
В соответствии с условием оптимальности можно сделать вывод о достижении оптимального решения. Полученный план трелевки древесины обеспечит минимальные затраты. При этом сменные маршруты и соответствующие объемы трелевки примут следующий вид (рис. 5.22): 150 м3 – по маршруту с первой лесосеки на первый погрузочный пункт; 100 м3 – по маршруту с первой лесосеки на второй погрузочный пункт; 50 м3 – по маршруту со второй лесосеки на второй погрузочный пункт; 100 м3 – со второй лесосеки на третий погрузочный пункт. И недостающие 50 м3 (фиктивные) – по маршруту с третьей фиктивной лесосеки на первый погрузочный пункт. Суммарные затраты (себестоимость) на трелевку при этом плане составят 650 рублей.