Решение открытой транспортной задачи

Содержание

     Введение                                                                                                              2 

1. Транспортная задача и методы её решения                                                   4

1.1. Экономико-математическая модель транспортной задачи                       4

1.2.Открытая модель транспортной задачи                                                      7

1.3. Методы составления начального опорного плана                                     9

1.4. Понятие потенциала и цикла                                                                     12

1.5. Критерий оптимальности базисного решения транспортной задачи    15

1.6. Распределительный метод решения транспортной задачи                    16

2. Разработка и описание алгоритма решения задачи                                   18

2.1. Содержательная постановка задачи                                                         18

2.2. Построение математической модели задачи                                           18 

2.3. Решение задачи вручную                                                                          18

2.4. Решение задачи с помощью Excel                                                            23
                                                                                             

Введение

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

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

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

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

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

     1.1. Экономико-математическая модель транспортной задачи

Некоторый однородный продукт, сосредоточенный у m поставщиков A_i  в количестве a_i (i=1,2,3,...,m) единиц соответственно, необходимо доставить n потребителям B_j в количестве b_j (j=1,2,3,...,n) единиц. Известна стоимость  C_ij  перевозки единицы груза от i-го поставщика к j-му потребителю.

Необходимо составить план перевозок, позволяющий вывезти все грузы, полностью удовлетворить C_ij x_ij потребности и имеющий минимальную стоимость.

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

Таблица №1

Составим математическую модель задачи. Так как от i-го поставщика к j-му потребителю запланировано к перевозке x_ij единиц груза, то стоимость перевозки составит C_ijx_ij.

Стоимость всего плана выразится двойной суммой:

Z = .

Систему ограничений получаем из следующих условий задачи:

А) все грузы должны быть вывезены, т.е. 

(i  = 1,2,3,..., m) (эти уравнения получаются из строк таблицы    1);

Б) все потребности должны быть удовлетворены, т.е. 

(j = 1,2,3,...,n)  (уравнения получаются из столбцов таблицы 1).

Таким образом, математическая модель транспортной задачи имеет следующий вид.

Найти наименьшее значение линейной функции:

Z =                                   ( 1)

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

  ,     i = 1, 2, ..., m,              ( 2 )

 ,    j = 1,2,3,...,n ,                 ( 3 )

X_ij ³ 0 ( j = 1,2,3, ..., m;    i = 1,2,3, ..., n).

В рассмотренной модели предполагается, что суммарные запасы равны суммарным потребностям, т.е.

      ( 4 )

Такая модель называется закрытой.
Теорема 1. Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.

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

Доказательство. Пусть   = M > 0.

Тогда   величины  x_ij = a_ib_j /M (i = 1,2,3, ... M ; j = 1,2,3, ..., n)                                являются планом, так как они удовлетворяют системе ограничений

( 2 ) и ( 3 ) .

Действительно, подставляя значения  в  ( 2 ) и ( 3 ) , находим

= a_i ,

 = b_j .

Выберем из значений  C_ij  наибольшее  C¢ = max C_ij и заменим в линейной функции ( 1 ) все коэффициенты  на C¢  тогда, учитывая ( 2 ) , получим

,

Выберем из значений C_ij  наименьшее C¢¢=min C_ij  и заменим в линейной функции все коэффициенты на C¢¢ ; тогда, учитывая ( 2 ) имеем



Т. Е.  Линейная функция ограничена на множестве планов транспортной задачи.
         1.2. Открытая модель транспортной задачи

Транспортная задача,  в  которой  суммарные запасы и потребности совпадают, т. е. выполняется условие , называется закрытой моделью;  в противном случае ¾ открытой. Для открытой модели может быть два случая:

a) суммарные запасы превышают суммарные потребности ;

b) суммарные потребности превышают суммарные запасы .

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

   Найти минимальное значение линейной функции

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

,    i = 1, 2, ..., m,                           (случай  а)

,    j = 1, 2, ..., n;

,    i = 1, 2, ..., m,                           (случай б)

,    j = 1, 2, ..., n,

x_ij ³ 0   (i = 1, 2, ..., m;    j = 1, 2, ..., n).

Открытая модель решается приведением к закрытой модели.

   В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель B_n+1, потребности которого  b_n+1 = . В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик  A_m+1, запасы которого a_m+1 = .

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

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

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

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

Рассмотрим систему ограничений ( 2 ) и ( 3 ) транспортной задачи. Она содержит m´n неизвестных и m+n уравнений,

Связанных соотношением (4). Если сложить почленно уравнения отдельно подсистемы  ( 2 ) и отдельно подсистемы ( 3 ), то получим два одинаковых уравнения . В таблице такое сложение равнозначно соответственно почленному сложению столбцов и почленно сложению строк .

Наличие в системе ограничений двух одинаковых уравнений говорит о ее линейной зависимости. Если одно из этих уравнений отбросить, то в общем случае система ограничений должна содержать m+n-1 линейно независимых уравнений, следовательно, невырожденный опорный план транспортной задачи содержит m+n-1 положительных компонент или перевозок.

Таким образом, если каким-либо способом получен невырожденный опорный план транспортной задачи, то в  матрице

( X_ij ) (i = 1, 2, ..., m;   j = 1, 2,  ... , n) значений его компонент (таблицы 2) положительными являются только

M+n-1, а остальные равны   нулю.

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

Занятые клетки соответствует неизвестным, и для невырожденного опорного плана их количество равно

M+n-1. Если ограничения транспортной задачи записаны в виде ( 2 ) и (3) то, как известно, базисным неизвестным, включенным в опорный план, соответствует система линейно независимых векторов.

Всякий план транспортной задачи, содержащий более

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

Циклом называется набор клеток вида  ( i₁ j₁ )( i₁ j₂ )*( j₂ i₂ )( j₁ i_m ), в котором две и только две соседние клетки расположены в одном столбце или одной строке таблицы, причем последняя клетка находится в той же строке или столбце, что и первая.

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

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

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

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

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

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

Если план  X* = (x*_ij)  транспортной _oзадачи является оптимальным, то ему соответствует набор из m + n чисел U_i*  и  V_j* ,    удовлетворяющих условиям

U_i* + V_j* = C_ij   для   x_ij* > 0

U_i* +  V_j* £ C_ij   для     x_ij* = 0

(i = 1, 2, 3, ..., m ;   j = 1, 2, 3, ..., n) .

Числа  U_i* и V_j*  называются потенциалами соответственно поставщиков и потребителей.

Доказательство.   Транспортную задачу минимизации линейной функции   Z =  при ограничениях

x_i1 + x_i2  + ... + x_in = a_i ,   i = 1, 2, ... , m,

x_1j  + x_2j + ... + x_mj = b_j,   j = 1, 2, ... , n,

x_ij  ? 0  (i = 1, 2, ... , m;   j = 1, 2, ... , n)

можно рассматривать как двойственную некоторой исходной задачи линейного программирования, условия которой получаются по общей схеме, если каждому ограничению вида  x_i1 +  x_i2 + ... +  x_in = a_i  в исходной задаче соответствует переменная U_i (i = 1, 2, ..., m), а каждому ограничению вида  x_1j + x_2j + x_mj  = b_j  - переменная   V_j (j  = 1, 2, ..., n), а именно:  максимизировать линейную функцию f =   при ограничениях  U_i + V_j £ C_ij

(i = 1, 2, ..., m;   j = 1, 2, ..., n).

План  X* является оптимальным планом двойственной задачи, поэтому план  Y* = ( U_i*, V_j* ) является планом исходной задачи и на основании теоремы двойственности

max f = min  Z

или

,

где  x_ij* ³ 0_.

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

U_i* + V_j* = C_ij  для  x_ij* > 0 ,

Ui*  + V_j* £ C_ij  для  x_ij* = 0 .

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

a) для каждой занятой клетки сумма потенциалов должна быть равна стоимости единицы перевозок, стоящей в этой клетке:

U_i + V_j = C_ij   ;     ( 5 )

b) для каждой незанятой клетки сумма потенциалов должна быть меньше или равна стоимости единицы перевозки, стоящей в этой клетке :

U_i + V_j £ C_ij   .  ( 6 )

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

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

Для построения системы потенциалов используем условие

U_i + V_j = C_ij

где  C_ij¾ стоимость перевозки единицы груза занятой клетки в i-ой строке и  j-м столбце .

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

Пусть известен потенциал U_i; тогда из равенства ( 5 ) следует

V_j = C_ij - U_i .

Если известен потенциал V_j ,  то из того же равенства имеем

U_i = C_ij - V_j .

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

Набором называется произвольная совокупность перевозок транспортной таблицы.

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

Циклом называется цепь, крайние элементы которой находятся либо в одной строке, либо в одном столбце.
       1.5.Критерий оптимальности базисного решения транспортной задачи
Базисное распределение поставок оптимально тогда и только тогда когда оценки всех свободных клеток больше нуля. Для свободных клеток строится цикл пересчёта, и в вершинах этого цикла расставляется последовательность чередующихся знаков, начиная со знака плюс в свободной клетке. К коэффициентам затрат таблицы поставок в каждой строке и каждом столбце надо прибавить такие числа (потенциалы) чтобы коэффициент затрат в заполненных клетках стали равными нулю.

Полученные при этом коэффициенты затрат свободных клеток равны оценкам этих клеток.
1.6. Распределительный метод решения транспортной задачи

Один из наиболее простых методов  решения транспортной задачи – распределительный метод.

Пусть для транспортной задачи найдено начальное опорное решение  и вычислено значение целевой функции на этом решении Z(). По теореме для каждой свободной клетки таблицы задачи можно построить единственный цикл, который содержит эту клетку и часть клеток, занятых опорным решением. Означив этот цикл и осуществив сдвиг (перераспределение груза) по циклу на величину =, можно получить новое опорное решение Х₂.

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, k), приращение целевой функции  равно разности двух сумм: =, где  - сумма стоимостей перевозок единиц груза в нечетных клетках цикла, отмеченных знаком  «+»,  - сумма стоимостей перевозок единиц груза в четных клетках цикла, отмеченных знаком

 «-».

В клетках, отмеченных знаком  «+», величины груза прибавляются, что приводит к увеличению значения целевой функции Z(), а в клетках, отмеченных  знаком  «-», величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки (l, k) меньше нуля, т.е. <0, то перераспределение величины  по соответствующему циклу приведет к уменьшению значения Z() на величину , т.е. опорное решение можно улучшить. Если же величины , называемые оценками , для всех свободных клеток таблицы транспортной задачи неотрицательны, то значение целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальностираспределительного метода является условие    =0.           (11)

Для решения транспортной задачи распределительным методом необходимо найти начальное опорное решение. Затем для очередной опорной клетки (l, k) построить цикл и вычислить оценку . Если оценка неотрицательная, переход к следующей свободной клетке. Если же оценка отрицательная, следует осуществить сдвиг по циклу на величину =. В результате получится новое опорное решение.

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

2.Разработка и описание алгоритма решения задачи

2.1. Содержательная постановка задачи
         Составить экономико-математическую модель задачи. Найти оптимальное распределение поставок и минимальные затраты на перевозку. Первоначальное распределение поставок выполнить методом северо-западного угла.

Таблица№2

Поставщики	Потребители			Запасы груза
А1	5	7	6	50
А2	6	6	5	40
А3	8	4	5	20
Потребность в грузе	18	21	33

2.2.Построение математической модели задачи
          Метод Северо-западного угла.

При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка ("северо-западный угол") оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки переменного  и заканчивается в клетке неизвестного , т. е. идет как бы по диагонали таблицы перевозок.

Таблица №3

Поставщики	Потребители				Запасы груза
А1	5    18	7 21	6 11	0	50
А2	6	6	5 22	0 18	40
А3	8	4	5	0 20	20
Потребители В грузе	18	21	33	38

=         

18*5+21*7+11*6+22*5+18*0+20*0=413

2.3.Решение задачи вручную
Находим значение потенциалов:

U_i+V_j=C_i,j(i=1..m, j=1..n),

U₁ + V₁=5

U₁ + V₂=7

U₁  + V₃=6

U₂ + V₃=5

U₂  + V₄=0

U₃ + V₄=0

U₁ =0

U₂=-1

U₃=-1

V₁=5

V₂=7

V₃=6

V₄=1

Определяем значения оценок _ij=C_ij-U_i-V_j для всех свободных клеток:

=


=

=2

==0

3



=0

Строим оценочную матрицу:

=

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

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


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




=

18*5+1*7+31*6+2*5+38*0+20*4=373

В оценочной матрице подчеркиваем элементы соответствующие базисным в новом решении. Строим цепочку выделения. Она строится от особо выделенного элемента (элемент)  по строкам, затем по столбцам. Каждый элемент, попавший в цепочку выделяет и строку, и столбец кроме выделенного элемента.

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

=


=

18*5+1*7+31*0+33*5+7*0+20*4=342
=

=min=1

=

=

Так как в оценочной матрице , нет отрицательных элементов матрица Х_3,  становиться оптимальна.

18*5+32*0+1*6+33*5+6*0+20*4=341




2.4. Решение задач с помощью
Excel

Таблица №4

Поставщики	Потребители			Запасы груза
А1	5	7	6	50
А2	6	6	5	40
А3	8	4	5	20
Потребность в грузе	18	21	33

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

Рассмотрим, как это можно сделать в среде электронных таблиц Microsoft Excel.

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

1. Введите в ячейки диапазона A6:D8 значения спроса

2. Введите в диапазон ячеек A9:D9 матрицу расходов.

3. Введите в ячейки диапазона E6:E8 запасы.

4. В ячейку E9 выводиться оптимальное решение

=СУММПРОИЗВ(A1:D3;A6:D8). Сделать это можно при помощи мастера функций выбрав в разделе. Математические функцию СУММПРОИЗВ и указав необходимый диапазон.


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

В диалоговом окне Параметры поиска решения установить флажок Линейная модель. После нажатия кнопки. Выполнить средство поиска решений находит оптимальный план поставок продукции и соответствующие ему транспортные расходы.





Оптимальное решение транспортной задачи