Закрытая и открытая модели транспортной задачи

Транспортная задача

4.1. Постановка транспортной задачи по критерию
стоимости в матричной форме

В m пунктах отправления A ₁, A ₂, …, A_m, которые в дальнейшем будем называть поставщиками, сосредоточено определенное количество единиц некоторого однородного продукта, которое обозначим a ₁, a ₂,…, a_m. Данный продукт потребляется в n пунктах B ₁, B ₂,…, B_n, которые будем называть потребителями; объем потребления обозначим b ₁, b ₂, …, b_n. Известны расходы (транспортные издержки) на перевозку единицы продукта из пункта A_i (i = 1, 2, …, m) в пункт B_j (j = 1, 2, …, n), которые равны c_ij и приведены в матрице транспортных расходов (издержек) C = (c_ij).

Требуется составить план перевозок, при котором весь продукт вывозится из пунктов A_i в пункты B_j в соответствии с потребностью и общая величина транспортных расходов (издержек) будет минимальной.

Обозначим количество продукта, перевозимого из пункта A_i в пункт B_j, через x_ij. Предполагается, что все x_ij ³ 0. Совокупность всех переменных x_ij для краткости обозначим X.

В математической форме задача линейного программирования имеет следующий вид:

	(15)
	(16)

	(17)

при этом (15) – целевая функция, (16) – ограничения по потребностям и запасам, (17) – условие неотрицательности.

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

Для наглядности условие транспортной задачи (ТЗ) можно представить таблицей, которую будем называть распределительной. Распределительную таблицу называют иногда табличной или матричной моделью ТЗ (матрицей планирования).

Матрицу X = (x_ij) _m _{´ n} будем называть матрицей перевозок,матрицу C = (c_ij) _m_´n – матрицей тарифов, а число c_ij – тарифом клетки (i; j).

Будем называть план перевозок X = (x_ij) _m _{´ n} допустимым, если он удовлетворяет ограничениям (16).

Допустимый план перевозок, доставляющий минимум целевой функции (15), называется оптимальным.

Таблица 13

Потребители, В_j	В ₁	В ₂	…	В_п	Запасы, а_i
Поставщики, А_i
	c ₁₁	c ₁₂		c _{1 n}
A ₁	x ₁₁	x ₁₂	…	x _{1 n}	a ₁
	c ₂₁	c ₂₂		c _{2 n}
A ₂	x ₂₁	x ₂₂	…	x _{2 n}	a ₂

	c_m ₁	c_m ₂		c_mn
A_m	x_m ₁	x_m ₂	…	x_mn	a_m
Потребности, b_j	b ₁	b ₂	…	b_n

Теорема 8 (о существовании допустимого плана). Для того, чтобы ТЗ имела допустимые планы, необходимо и достаточно выполнение равенства

(18)

(сумма запасов продукта равна сумме спроса на него).

Условие (18) является условием баланса.

Закрытая и открытая модели транспортной задачи

Транспортная задача, в которой имеет место равенство (18), называется закрытой.

Если для ТЗ выполняется одно из условий:

(19)

или

(20)

то задачу называют открытой.

Для разрешимости ТЗ с открытой моделью необходимо преобразовать ее в закрытую.

Если суммарный запас продукта превышает общий спрос, т. е. выполняется условие (19), то в рассмотрение вводится фиктивный (n + 1)-й пункт потребления B_n+ ₁ (в матрице задачи предусматривается дополнительный столбец) со спросом, равным небалансу, т. е. , и одинаковыми тарифами, полагаемыми обычно равными нулю. Теперь условие разрешимости выполняется, а величина целевой функции остается прежней, поскольку цены на дополнительные перевозки равны нулю. При этом грузы, которые должны быть перевезены в пункт B_n+ ₁, фактически останутся в пункте отправления.

Если же общий спрос потребителей больше суммарного запаса продукта, т. е. выполняется условие (20), то вводится фиктивный (m + 1)-й пункт отправления A_m+ ₁(в матрице задачи предусматривается дополнительная строка) с запасом продукта .

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

Теорема 9 (о ранге матрицы). Ранг матрицы А (матрица системы ограничений (16)) транспортной задачи на единицу меньше числа уравнений r (A) = m + n – 1.

Построение исходного опорного плана

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

Клетки, в которых стоят отличные от нуля x_ij, называют загруженными,остальные – свободными.

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

Правило “северо-западного угла”. Первой загружается клетка (1; 1), условно называемая северо-западной. Если закрывается строка, то следующей загружается клетка (2; 1); если же закрывается столбец, то следующей загружается клетка (1; 2). Итак, каждый раз загружается клетка, соседняя либо по строке, либо по столбцу (в зависимости от конкретных данных задачи), до тех пор, пока не исчерпаются ресурсы. Последней будет загружена клетка (m; n). В результате загруженные клетки расположатся вдоль диагонали (1; 1)–(m; n), поэтому способ “северо-западного угла” называют еще диагональным способом.

Существенным недостатком способа “северо-западного угла” является игнорирование при загрузке клеток тарифов c_ij, поэтому построенный опорный план обычно оказывается весьма далеким от оптимального.

Правило “минимального элемента” (“минимальной стоимости”). В первую очередь заполняется клетка с минимальным значением тарифа. При этом в клетку записывается максимально возможное значение поставки. Затем из рассмотрения исключают строку, соответствующую поставщику, запасы которого полностью израсходованы, или столбец, соответствующий потребителю, спрос которого полностью удовлетворен. После этого из оставшихся клеток таблицы снова выбирают клетку с наименьшим тарифом. Процесс распределения заканчивается, когда все запасы поставщиков исчерпаны, а спрос потребителей полностью удовлетворен. В результате получаем опорный план, который должен содержать m + n – 1 загруженных клеток. В процессе заполнения таблицы могут быть одновременно исключены строка и столбец. Так бывает, когда полностью исчерпывается запас груза и полностью удовлетворяется спрос. В этом случае и в случае вырожденного плана в свободные клетки надо записать число 0 – “нуль-загрузку” (“базисный” нуль), условно считая такую клетку занятой (обычно клетки, которым соответствует наименьший тариф).

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

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

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

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

Теорема 10 (теорема о потенциалах). Если план ТЗ является оптимальным, то ему соответствует система из m + n чисел , ,удовлетворяющих условиям для и для .

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

На теореме 10 основан метод решения ТЗ, названный методом потенциалов.

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

Сущность этого метода состоит в следующем. После того, как найден первоначальный невырожденный план перевозок, каждому поставщику A_i (каждой строке) ставится в соответствие некоторое число , а каждому потребителю B_j (каждому столбцу) – некоторое число . Числа u_i, v_j – потенциалы A_i и B_j (u_i, v_j произвольного знака).

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

(21)

Так как всех занятых клеток должно быть m + n – 1, а чисел u_i и v_j должно быть m + n, то для нахождения потенциалов u_i, v_j получаем систему из m + n – 1 уравнений (21) с m + n неизвестными. В этой системе уравнений на одно меньше, чем неизвестных, поэтому один потенциал можно задать произвольно, например равным нулю. Тогда остальные потенциалы определяются однозначно.

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

(22)

При этом S_ij – оценка свободной клетки.

Если для всех свободных клеток оценки S_ij ³ 0, то опорный план перевозок является оптимальным.

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

Переход к новому плану

порядок перехода к новому плану следующий:

1. Клетка, для которой значение S_ij минимально, является перспективной и подлежит загрузке. Если таких клеток несколько, то берем любую.

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

Точки самопересечения контура вершинами не являются.

Некоторые примеры циклов приведены на рис. 7.

рис. 7

3. Расставим поочередно знаки “+” и “–” в вершинах цикла. В перспективной клетке ставим знак “+”; затем, двигаясь по вершинам цикла, ставим поочередно знаки “–” и “+”, пока не придем к исходной вершине.

4. В клетках, соответствующих “отрицательным” вершинам, отыскивается наименьший груз (обозначим его q), который “перемещается” по клеткам цикла, т. е. прибавляется к поставкам x_ij в клетках со знаком “+” (включая свободную) и вычитается в клетках со знаком “–”.

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

Процесс продолжается, пока не получится оптимальный план перевозок. В результате остается подсчитать минимальные расходы (z _min).

Примечание. Если все S_ij > 0, то полученный оптимальный план единственный. В случае, если хотя бы одна оценка S_ij = 0, имеем бесчисленное множество оптимальных планов с одним и тем же значением целевой функции.

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

приведем алгоритм метода потенциалов:

1. Условие задачи записывают в форме распределительной таблицы.

2. Сравнивают общий запас продукта с суммарным спросом и в случае нарушения равенства (18) вводят фиктивного поставщика (потребителя).

3. Строят начальный опорный план по одному из правил.

4. Вычисляют потенциалы поставщиков и потребителей u_i и v_j , решив систему уравнений типа (21).

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

6. Загружают выделенную в предыдущем пункте свободную клетку (пункт 4.5), получают новый опорный план и возвращаются к пункту 4 алгоритма.

Пример 8. Решить транспортную задачу методом потенциалов, для которой известно, что a_i – запас груза i -го поставщика, b_j – потребность j -го потребителя, C = (c_ij) – матрица затрат на перевозку одной единицы груза:

a ₁ = 12; a ₂ = 3; a ₃ = 10;

b ₁ = 14; b ₂ = 10; b ₃ = 6;

Решение

Поместим все данные задачи в табл. 14.

Таблица 14

b_j
a_i

Проверим, сколько единиц однородного продукта содержат поставщики (12 + 3 + 10 = 25) и сколько единиц однородного продукта нужно доставить потребителям (14 + 10 + 6 = 30).

Так как 25 < 30, т. е. , то имеем открытую модель транспортной задачи.

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

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

Все тарифы на доставку продукта фиктивным поставщиком равны нулю: .

Имеем ТЗ закрытого типа, которую решаем методом потенциалов (табл. 15).

Построим первоначальный (опорный) план методом “минимального элемента” (табл. 16).

Таблица 15

	b_j
	a_i

Таблица 16

	b_j
	a_i

В результате получаем матрицу перевозок

План X ₁ является невырожденным (m + n – 1 = 4 + 3 – 1 = 6). Общая стоимость перевозки грузов по этому плану составит

z ₁ = 1 × 7 + 0 × 5 + 1 × 3 + 4 × 7 + 5 × 3 + 0 × 5 = 53.

Потенциалы поставщиков и потребителей определены непосредственно на рис. 8.



	7 –	5 +



	7 +		3 –

5		5 –	· +

Рис. 8

Имеют место следующие оценки свободных клеток:

S ₁₃= 2 – (–3 + 5) = 0;	S ₃₂ = 6 – (0 + 3) = 3 > 0;
S ₂₁= 3 – (– 4 + 4) = 3 > 0;	S ₄₁ = 0 – (–3+ 4) = –1 < 0;
S ₂₂ = 4 – (– 4 + 3) = 5 > 0;	S ₄₃ = 0 – (–3 + 5) = –2 < 0.

Так как S ₄₁ < 0 и S ₄₃ < 0, то план является неоптимальным. Наиболее потенциальной и перспективной является клетка (4; 3). Строим для клетки (4; 3) цикл непосредственно на рис. 8. В цикл войдут клетки (4; 3), (3; 3), (3; 1), (1; 1), (1; 2), (4; 2). Проставим знаки “+” и “–” в цикле поочередно, начиная со свободной клетки. Наименьшее количество груза, стоящее в вершинах цикла с отрицательным знаком, – . В результате смещения по циклу получим новый план (рис. 9).

Для этого плана определяем новые потенциалы и оценки свободных клеток:

S ₁₃= 2 – (0 + 0) = 2 > 0;	S ₃₂ = 6 – (3 + 0) = 3 > 0;
S ₂₁ = 3 – (1 + 1) = 1 > 0;	S ₃₃ = 5 – (3 + 0) = 2 > 0;
S ₂₂ = 4 – (1 + 0) = 3 > 0;	S ₄₁ = 0 – (0 + 1) = –1 < 0.



	4 –	8 +		u ₁ = 0

				u ₂ = 1

				u ₃ = 3

5	+ ·	–		u ₄ = 0
	v ₁ = 1	v ₂ = 0	v ₃ = 0

Рис. 9

Так как S ₄₁ < 0, то план является неоптимальным. Строим для клетки (4; 1) цикл непосредственно на рис. 9. В цикл войдут клетки (4; 1), (1; 1), (1; 2), (4; 2). Проставим знаки в цикле. В отрицательных вершинах построенного для клетки (4; 1) цикла наименьшее количество груза – .

После смещения по циклу 2 единиц груза получим новый план перевозок (рис. 10).



			u ₁ = 0

			u ₂ = 0

			u ₃ = 3

			u ₄ = –1
v ₁ = 1	v ₂ = 0	v ₃ = 1

Рис. 10

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

S ₁₃= 2 – (0 + 1) = 1 > 0,	S ₃₂ = 6 – (3 + 0) = 3 > 0,
S ₂₁ = 3 – (0 + 1) = 2 > 0,	S ₃₃ = 5 – (3 + 1) = 1 > 0,
S ₂₂ = 4 – (0 + 0) = 4 > 0,	S ₄₂ = 0 – (–1 + 0) = 1 > 0.

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

значение целевой функции составит

(усл. ед.).

Загрузка x ₄₁ = 2 и x ₄₃ = 3 для фиктивного поставщика указывает на остаток нераспределенного груза в размере 5 ед. у потребителей B ₁ и B ₃.

Ответ: усл. ед.

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

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

Методы линейного программирования являются хорошим инструментом для решения ряда проблем распределения ресурсов. Применение пакетов прикладных программ позволяет значительно упростить решение задачи. Поэтому лицо, принимающее решение, получает возможность уделить большее внимание интерпретации и оценке решения задачи. Однако применение прикладных пакетов предполагает предварительную формализацию модели линейного программирования. В процессе решения большинства проблем эта задача является основной. При построении модели необходимо идентифицировать ее переменные и сформулировать систему ограничений.
При решении некоторых видов проблем распределения ресурсов использование специально созданных для этих целей алгоритмов упрощает процесс построения исходной модели.
Целью является минимизация общей стоимости транспортировки. Пусть, например, некоторой компании принадлежат три завода и пять пунктов распределения продукции, находящиеся в одном регионе. Администрация компании должна организовать перевозку конечной продукции с заводов в пункты распределения с минимальной стоимостью. В этой ситуации наиболее подходящими могли бы стать методы решения транспортной задачи.
Частным случаем транспортной задачи является задача о назначениях. Предполагается, что из каждого пункта производства в каждый пункт потребления перевозится только один товар. Например, в машинном цехе имеется шесть токарных станков различного срока службы и различной конструкции. Каждое утро начальник цеха должен распределить по этим станкам шесть видов работ. Продолжительность выполнения каждой работы на различных станках неодинакова. Начальник цеха намерен распределить по каждому станку работу таким образом, чтобы свести к минимуму общее время выполнения работ. В процессе решения этой и подобных проблем можно использовать алгоритм решения задачи о назначениях.
Транспортная задача связана с распределением товаров между поставщиками (находящимися в пунктах производства) и потребителями (находящимися в пунктах назначения) таким образом, чтобы общая стоимость этого распределения была минимальной. Эта задача может быть решена либо с помощью методов линейного программирования, либо специального алгоритма решения транспортной задачи.

Заключение

В результате выполнения курсовой работы на тему «Решение задач транспортного типа методом потенциалов» была разработана программа, реализующая метод потенциалов для решения транспортной задачи.
20, но может быть увеличена.´Программа позволяет производить решение транспортных задач для любых наборов исходных данных. Размерность задачи ограничена величиной 20
Минимальный, и в то же время достаточно удобный, пользовательский интерфейс программы делает ее доступной пользователю любой квалификации. Минимальные требования к аппаратуре позволяют использовать данную программу на любом компьютере с операционной системой Windows или с ними совместимой.
Применение ручных средств для решения транспортной задачи требует значительных временных затрат и они будут увеличиваться при изменении размерности задачи. При этом также возрастает вероятность ошибки при обработке. Поэтому целесообразно применять для расчетов ЭВМ. Это позволит значительно сократить время счета в сотни раз, повысить надежность результатов и их точность. Кроме того, использование ЭВМ позволит сохранять (при незначительной доработке программы) результаты, что позволит их использовать при решении других задач.

Введение

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

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

Метод потенциалов – первый точный метод решения транспортной задачи – был предложен в 1949 г. Л.В. Канторовичем и М. К. Гавуриным. По существу этот метод является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данцигом, который исходил из общих идей линейного программирования. В американской литературе метод потенциалов принято называть модифицированным распределительным методом. Метод потенциалов позволяет, отправляясь от некоторого опорного плана перевозок, построить решение транспортной задачи за конечное число итераций (шагов).