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

Содержание:

Введение………………………………………………………………………….3

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

Пример решения  транспортной задачи………………………………………10

Заключение……………………………………………………………………..15

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

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

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

 

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

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

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

 

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

Экономико-математическая модель задачи имеет вид задачи линейного  программирования. Обозначим  – количество единиц груза, отправляемого из i-го ПО в j-й ПН . Совокупность чисел () будем называть планом перевозок, а сами величины – перевозками.

Необходимо  найти такой план перевозок (), при котором целевая функция (суммарная стоимость перевозок) будет минимальной:

 

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

1) Суммарное количество груза, направляемого  из каждого ПО во все ПН  должно быть равно запасу груза  в данном пункте:

 

2) Суммарное количество груза, доставляемого в каждый ПН из всех ПО, должно быть равно заявке, поданной данным пунктом:

 

3) Условие неотрицательности:

 

 

 

Решение транспортной задачи разбивается на два этапа:

1. определение исходного опорного решения;
2. построение последовательных итераций – приближение к оптимальному решению.

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

 

	ПН					…
ПО						…
						…
						…
…	…	…		…		…	…
						…

 

Определение исходного опорного решения.

Существует  несколько способов, наиболее популярными  являются:

- метод северо-западного угла,

- метод минимального элемента,

- метод аппроксимации Фогеля.

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

В каждом методе на любом шаге в выбранную  ячейку () таблицы помещается максимальная допустимая перевозка – минимальное из того, что есть у соответствующего поставщика (ПО) и требуется соответствующему потребителю (ПН) . При этом каждый раз «закрывается» строка таблицы, если у соответствующего поставщика (ПО) больше нет груза, или «закрывается» столбец, если соответствующему потребителю (ПН) больше не надо груза. Методы отличаются лишь способом построения последовательности заполнения ячеек таблицы.

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

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

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

Последовательность  заполнения таблицы:

 

Стоимость перевозок:

 

 

	ПН
ПО		10		65		25
	30		6		3		2
		10		20
	20		2		1		5
				20
	50		3		4		1
				25		25

 

Пример. Метод минимального элемента

Последовательность  заполнения таблицы:

 

Стоимость перевозок:

 

 

	ПН
ПО		10		65		25
	30		6		3		2
				30
	20		2		1		5
				20
	50		3		4		1
		10		15		25

 

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

Метод потенциалов получения оптимального решения.

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

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

Для каждой свободной клетки вычисляется  числовая характеристика – косвенная стоимость: .

Критерий  оптимальности плана перевозок:

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

1) , если (для заполненных клеток),

2) (для свободных клеток).

Т.е. если все косвенные стоимости  неотрицательные, то решение оптимальное, в противном случае его можно  улучшить.

Перераспределение поставок.

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

	Значение l определяется как максимально возможное, сохраняющее неотрицательность всех перевозок, т.е. по соотношениям вида l. На рис. 1: l. В результате определения l и пересчета перевозок получаем новый опорный план, которые необходимо проверить на оптимальность.
Рис. 1

 

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

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

1) Определить начальный опорный  план, рассчитать стоимость перевозок.

2) Составить систему уравнений  для заполненных клеток. При найти потенциалы всех поставщиков и потребителей .

3) Определить  косвенные стоимости свободных  ячеек по формуле: 

4) Если все косвенные стоимости  неотрицательны, то план перевозок  оптимальный.

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

6) Найти максимальное значение l при условии сохранения неотрицательности всех перевозок, составить новый опорный план, рассчитать стоимость перевозок.

7) Перейти к п.2.

Пример. Провести одно улучшение опорного плана методом потенциалов:

	ПН
ПО		10		65		25
	30	-l	6	+l	3		2
		10		20
	20		2		1		5
				20
	50	l	3	-l	4		1
				25		25