Решение транспортной задачи методом потенциалов

ВВЕДЕНИЕ

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

В общем, виде математическая постановка экстремальной задачи состоит в определении наибольшего и наименьшего значения целевой функции f (x1,x2, …,xn) при условиях gi (x1,x2, …,xn) ? bi (i=), где f и gi -заданные функции, а bi - некоторые действительные числа.

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

Прежде всего, задачи математического программирования делятся на задачи линейного и нелинейного программирования. При этом если все функции f и gi линейные, то соответствующая задача является задачей линейного программирования. Если же хотя бы одна из указанных функций нелинейная, то соответствующая задача является задачей нелинейного программирования.

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

Среди задач нелинейного программирования наиболее глубоко изучены задачи выпуклого программирования. Это задачи, в результате решения которых определяется минимум выпуклой (или максимум вогнутой) функции, заданной на выпуклом замкнутом множестве.

1. СПЕЦИАЛЬНАЯ ЧАСТЬ

Математическая постановка задачи состоит в определении минимального значения функции

(1.1)

при условиях

(1.2)

(1.3)

xij0 (i= j=) (1.4)

Поскольку переменные xij (i= j=) удовлетворяют системам линейных уравнений (2) и (3) и условию неотрицательности (1.4), обеспечиваются доставка необходимого количества груза в каждый из пунктов назначения, вывоз имеющегося груза из всех пунктов отправления, а также исключаются обратные перевозки.

Всякое неотрицательное решение систем линейных уравнений (1.2) и (1.3), определяемое матрицей X=(xij) (i= j=), называется планом транспортной задачи.

План X*=(x) (i= j=), при котором функция (1.1) принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

Обычно исходные данные задачи записывают в виде таблицы.

Таблица 1.2 -пример заполнения

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

=, (1.5)

то модель такой транспортной задачи называется закрытой. Если же указанное условие не выполняется, то модель транспортной задачи называется открытой.

Для разрешимости транспортной задачи необходимо и достаточно, чтобы запасы груза в пунктах отправления были равны потребностям в грузе в пунктах назначения, т.е. чтобы выполнялось равенство (1.5).

В случае превышения запаса над потребностью, т.е. > вводится фиктивный (n+1)-й пункт назначения с потребностью bn+1= - и составляющие тарифы считаются равными нулю: cin+1=0 (i=). Полученная задача является транспортной задачей, для которой выполняется равенство (1.5).

Аналогично, при <вводится фиктивный (m+1)-й пункт отправления с запасом груза am+1= - и тарифы полагаются равными нулю: cm+1j=0 (j=). Этим задача сводится к обычной транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. В дальнейшем будем рассматривать закрытую модель транспортной задачи. Если же модель конкретной задачи является открытой, то, исходя из сказанного выше, перепишем таблицу условий задачи так, чтобы выполнялось равенство (1.5).

Число переменных xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (1.2) и (1.3) равно n+m. Так как мы предполагаем, что выполняется условие (1.5), то число линейно независимых уравнений равно n+m-1. Следовательно, опорный план транспортной задачи может иметь не более n+m-1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонент равно в точности n+m-1, то план является невырожденным, а если меньше - то вырожденным.

1.3 Алгоритм метода

Для решения транспортной задачи методом потенциалов необходимо:

1. Построить опорный план по данному из методов.

2. Вычислить потенциалы поставщиков и потребителей, решив систему уравнений вида Ui+Vj=Cij.

3. Вычислить оценки Sij для всех свободных клеток по формуле Sij= Cij-( Ui+Vj). Если все Sij?0, то получим план являющийся оптимальным, при этом если все Sij?0, то полученный оптимальный план единственный. В случае если хотя бы одна оценка Sij=0 имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

Алгоритм метода потенциалов для транспортной задачи:

Vj - Ui=C, если xi,j>0, (1.1)

Vj - Ui ?C, если xi,j=0, (1.2)

Критерий (1.1) - (1.2) положен в основу одного из методов решений транспортной задачи, получившего название метода потенциалов. Впервые он был предложен в 1949 г. Л.В. Канторовичем и М.К. Гавуриным. Позже на базе общих идей линейного программирования аналогичный метод был предложен Дж. Данцигом.

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

Алгоритм начинается с выбора некоторого допустимого базисного плана. Если данный план не вырожденный, то он содержит m+n -1 ненулевых базисных клеток, и по нему можно так определить потенциалы Ui Vj , чтобы для каждой базисной клетки (т.е. для той, в которой xi,j>0) выполнялось условие

Vj - Ui =C, если xi,j>0

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

Рассмотрим процесс определения потенциалов текущего плана транспортной задачи на примере.

Потенциал первого пункта потребления принимаем равным нулю (V1=0). Теперь, зная его, мы можем определить потенциалы для всех пунктов производства, связанных с первым пунктом ненулевыми перевозками. В данном случае их два (это первый и второй пункты), получим:

U1=V1-C1,2=0-14=-14, U2=V1-C2,2=0-10=-10.

 Имея U2 и учитывая, что во второй строке таблицы существуют ещё ненулевые компоненты X2,2 и X2,3 , можно определить V2=U2+C2,2= -10+17=7 и V3=U2+C2,3= -10+15=5, после чего появляется возможность рассчитать U3=V3-C3,3=5-25=-20 и, наконец, V4=U3+C3,4= -20+21=1. В результате получаем полную систему потенциалов, показанную в таблице 1.1.

Таблица 1.1

Для свободных клеток транспортной таблицы вычисляются величины ?i,j=Vj-Ui , называемое разностями потенциалов. В таблице 1.2 они выписаны для всех небазисных клеток под ценами.

Таблица 1.2

Разность потенциалов ?i,j можно трактовать как увеличение цены продукта при его перевозке из пункта i в пункт j. Согласно критерию оптимальности (1.1) - (1.2), если все ?i,j?Ci,j , то план оптимален, в противном случае, если существует хотя бы одна разность потенциалов ?i,j>Ci,j , то он может быть улучшен. Процесс "улучшения" плана состоит в определении вводимой и выводимой клеток, в чем прослеживается содержательная аналогия с соответствующими пунктами симплекс-процедур.

Кандидатом на ввод, очевидно, может быть любая клетка, в которой ?i,j>Ci,j , поскольку после ввода в базис будет обеспечено равенство ?i,j=Ci,j. Для определённости обычно рекомендуется брать ту клетку, в которой оценка ?i,j-Ci,j максимальна. В рассматриваемом нами примере это клетка (3,1).

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

Таблица 1.3

Логика алгоритма построения цепочки достаточно проста: "выйдя" из клетки (3,1) в горизонтальном направлении, мы должны "остановиться" в той же занятой клетке плана, из которой сможем двигаться дальше по вертикали. В данном примере этому требованию удовлетворяют как клетка (3,3), так и клетка (3,4). Однако цепочка от (3,4) не может быть продолжена дальше, в то время как, двигаясь от (3,3) по вертикали к (2,3) и далее к (2,1), мы возвращаемся к исходной клетке (3,1) и образуем замкнутый цикл.

В построенной цепочке, начиная с вводимой клетки (которая считается первой), помечаются вершины знаком "+", а чётные "-". Знаком "+" отмечается те клетки, в которых объемы перевозок должны увеличиться (таковой, в частности, является клетка, вводимая в план, поскольку она должна стать базисной). Знаком "-" - те клетки, в которых перевозки уменьшаются с целью сохранения баланса. Среди множества клеток, помеченных знаком "-", выбирается клетка с наименьшим значением xi,j (обозначим его ?). Она и становится кандидатом на вывод, так как уменьшение объема перевозок на большую величину может привести к отрицательным значениям xi,j в других "минусовых" клетках. Затем производится пересчет плана по цепочке: к объемам перевозок в клетках, помеченных знаком "+", добавляется объем ?, а из объемов клеток, помеченных знаком "-", он вычисляется. В результате ввода одной клетки и вывода другой получается новый базисный план, для которого на следующей итерации описаны выше действия, повторяются.

Страницы: 1, 2, 3