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

Содержание

 

Введение

§1. Постановка Транспортной задачи (ТЗ) для n переменных

§2. Пример решения Транспортной задачи

§3. Транспортные задачи по различным критериям

§4. Решение транспортной задачи в Excel

Список литературы

 

 

Введение

 

Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача – задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.

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

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

 

 

§1. Постановка Транспортной задачи (ТЗ) для n переменных

 

Пусть имеется несколько  поставщиков однородной продукции (каждый с определенным запасом) и  несколько потребителей этой продукции (с известными потребностями у каждого). Задана также сеть коммуникаций (дорог, рек, воздушных линий и т.д.) связывающая каждого поставщика с каждым потребителем. На каждой коммуникации задана цена перевозки – стоимость перевозки единицы продукции. Если какая – либо коммуникация отсутствует, то считаем, что она есть, но цену перевозки на ней устанавливаем равной бесконечности (+∞). Это соглашение сделает невыгодным перевозку по ней и автоматически исключит данную коммуникацию из плана перевозок.

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

Транспортные задачи бывают:

1) открытые m ≠ n (суммарный запас продукции, имеющейся у поставщиков, не совпадает с суммарной потребностью в продукции у потребителей.)

2) закрытые m = n (суммарный запас продукции, имеющейся у поставщиков, совпадает с суммарной потребностью в продукции у потребителей.)

Метод потенциалов «работает» только для закрытых ТЗ, причем, закрытая ТЗ всегда разрешима.

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

Закрытая транспортная задача формулируется как Задача Линейного Программирования (ЗЛП) следующего вида:

 

 

 

 

 

, где

 

- запас i – го поставщика

- потребность j – го потребителя

- цена перевозки единицы продукции по коммуникациям (i,j)

(от i – го поставщика к j – му потребителю)

- объем перевозки продукции  (неизвестный) по коммуникациям  (i,j).

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

Структура матрицы ограничений транспортной задачи такова, что столбец, соответствующей переменной содержит ровно два ненулевых элемента: единицу в строке с номером i и единицу в строке m + i.

Вектор двойственных переменных Y = ( ,…, , ,…, ) имеет m + n компонент (по числе ограничений ТЗ), которые называются потенциалами: переменные , ,…, - потенциалы поставщиков; переменные , …, - потенциалы потребителей.

Используя схему для  построения двойственной задачи к ЗЛП  в стандартной форме, имеем:

 

 

В полученной двойственной задаче n·m ограничений, соответствующих каждой переменной ТЗ. Вспоминая, что невязка между левой и правой частью в ограничений двойственной задачи есть оценка для соответствующей переменной исходной задачи , запишем условия оптимальности текущего плана перевозок в ТЗ:

 

.

 

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

 

 

 

для заполненных клеток (i,j) таблицы ТЗ.

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

 

§2. Пример решения Транспортной задачи

 

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

ШАГ 1. Построение начального плана перевозок.

ШАГ 2. Проверка текущего плана на оптимальность.

Если план оптимален, то алгоритм завершен.

ШАГ 3. Улучшение  плана перевозок. Переход к шагу 1.

Опишем алгоритм по шагам, иллюстрируя каждый шаг

ШАГ 1. Построение начального плана перевозок.

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

 

 

Клетка ( i , j ) таблицы соответствует коммуникации, связывающей i-го поставщика сj-м потребителем.

Построить начальный  план перевозок означает - назначить  объемы перевозок в клетки таблицы  таким образом, чтобы:

а)число заполненных  клеток было (m+n-1). (Тогда план перевозок будет отвечать базисному решению ЗЛП);

б)сумма перевозок  в любой строке должна быть равна  запасу соответствующего поставщика, а сумма перевозок в каждом столбце равна потребности потребителя. (Условие выполнения ограничений ТЗ). Существует несколько способов нахождения начального решения, которые отличаются только выбором клетки, в которую назначается очередная перевозка. Так, в способе северо-западного угла (СЗУ) для очередного назначения перевозки выбирается левая верхняя клетка таблицы (при этом никак не учитываются цены перевозок). Наоборот, в способе минимальной стоимости (МС) для заполнения выбирается клетка текущей таблицы с минимальной ценой перевозки, что в большинстве случаев (но не всегда) приводит к более дешевому (а значит и более близкому к оптимальному) начальному плану перевозок.

Мы будем пользоваться способом минимальной стоимости (МС).

Изложим теперь алгоритм нахождения начального решения.

ШАГ 1. Определенным способом выбираем клетку в текущей таблице. Пусть она имеет индексы (i, j) (i -номер поставщика, j - номер потребителя).

ШАГ 2. В качестве перевозок в эту клетку назначаем наименьшую из a_i и потребности bj.

 

x_ij = min{ a_i, bj }

 

ШАГ З. Уменьшим запас a_i и потребность bj на величину перевозки x_ij, т.е.

 

a_i = a_i - x_ij,

bj =bj -x_ij

 

ШАГ 4. При исчерпании запаса (a_i = 0) запрещаем к перевозке оставшиеся свободные клетки i-ой строки, а при исчерпании потребности

(bj =0) запрещаем такие же клетки вj-ом столбце.

В случае одновременного исчерпания запасов потребностей (ai =bj = 0) запрещаем перевозки или в строке (тогда считаем, что у потребителя осталась потребность в количестве равном нулю, которую необходимо удовлетворить), или в столбце (в этом случае считаем, что у поставщика остается запас равный нулю, который необходимо вывезти). Это делается для того, чтобы при одновременном запрещении перевозок в строке и столбце количество заполненных клеток таблицы не стало меньшим, чем m+n-1.

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

 

Способ минимальной стоимости.

 

1.Клетки с минимальной ценой  (3,1), (3,2) и (3,3). Выбираем, например, (3,2). (Далее все шаги, как в предыдущем  способе).

2 . x₃₂ = min{50,60} = 50

3. a ^'₃ =50-50=0, b ^'₂ = 100-50=50

4.Запрещаем строку 3.

 

 

1. Клетка с min ценой ~ (2,3)
2. x₂₃ = min{70,80} = 70
3. a₂=70-70=0, b'₃ = 80-70=10
4. Запрещаем строку 2.

 

	1	2	3
60	5 60	10	12
Χ	8 -	6 -	4 70
Χ	0	0 50	0 -
		50	10

 

1. Клетка с min ценой ~ (1,1)
2. x ₁₁=min{120,60} = 60
3. a _1' =120-60 = 60, b_1' = 0

4.В первом столбце  запрещать уже нечего. Текущая  таблица содержит две клетки (1,2) и (1,3).

 

 

1.Выбираем клетку (1,2)

_2.x ₁₂ =min{110,100} = 100

3.a ₁ =110-100 = 10, b^'₁ = 0

4.Текущая таблица содержит одну клетку (1,3).

 

 

1. Выбираем последнюю клетку(1,3)

2. x₁₃=min{10,10} = 10

3.a₁^' = b₃ = 0

4.Таблица исчерпана.  Конец.

Переходим к описанию следующего шага метода потенциалов.

ШАГ 2. Проверка текущего плана на оптимальность.

Признаком того, что текущий план перевозок является оптимальным, служит условие

 

(1)u_i +vj -c_ij ≤0

 

которое выполняется  для всех клеток таблицы. Неизвестные здесь величины u_i и vj (называемые потенциалами) определяются из условий

 

(2)u_i + v_j = c_ij

 

Условие (1) означает невозможность  появления "спекулятивной" цены. Само же название "потенциалы" заимствовано из физического закона о том, что работа по перемещению заряда в электростатическом поле равна разности потенциалов в данных точках поля (У нас: "...цена перевозки единицы продукции по коммуникации равна разности цен в конце и в начале пути")

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

Заполненные клетки Уравнения

 

(1,1) u₁ + v₁ =5

(1,2) u₁ + v₂ =10

(1,3) u₁ + v₃ =12

(2,3) u₂ +v₃ =4

(3,2) u₃ +v₂ =0

 

Положим, например, неизвестное u ₁ равным 0 (через него можно из первых трех уравнений найти v₁, v₂ и v₃). Последовательно из них находим u _{2 ,} u _3.

Этот метод можно сформулировать в виде единого правила:

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

Применим это правило для  определения u и v в нашем примере и получим:

 

u₁ =0, u₂ =-8, u₃ =-6

v₁ =5, v₂ =10, v₃ =12

 

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