В качестве критерия оптимальности транспортных перевозок берется. Целевые функции

Расчетная работа № 4: ТРАНСПОРТНАЯ ЗАДАЧА

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

производства	Пункты потребления				производства
потребителя

Составим математическую модель задачи.

(1)

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

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

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

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

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

В случае вводится фиктивный- й пункт назначения с потребностью ; аналогично, при вводится фиктивный-й пункт отправления с запасом груза и соответствующие тарифы считаются равными нулю:. Этим задача сводится к обычной транспортной задаче. В дальнейшем будем рассматривать закрытую модель транспортной задачи.

Число переменных в транспортной задаче с пунктами отправления и пунктами назначения равно , а число уравнений в системе (2)-(4) - . Так как мы предполагаем выполнение условия (5), то число линейно независимых уравнений равно . Следовательно, опорный план может иметь не более отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонент равно в точности , то план называется невырожденным , а если меньше - то вырожденным .

Построение первоначального опорного плана

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

Кратко рассмотрим каждый из них.

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

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

3. Метод двойного предпочтения . Суть метода заключается в следующем. В каждом столбце отмечают знаком «√» клетку с наименьшей стоимостью. Затем то же проделывают в каждой строке. В результате некоторые клетки имеют отметку «√√». В них находится минимальная стоимость, как по столбцу, так и по строке. В эти клетки помещают максимально возможные объемы перевозок, каждый раз исключая из рассмотрения соответствующие столбцы или строки. Затем распределяют перевозки по клеткам, отмеченным знаком «√». В оставшейся части таблицы перевозки распределяют по наименьшей стоимости.

4. Метод аппроксимации Фогеля . При определении опорного плана данным методом на каждой итерации по всем столбцам и всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности заносят в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают максимальную. В строке (или столбце), который данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

Определение критерия оптимальности

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

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

Метод потенциалов позволяет определить отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).

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

Составим двойственную задачу

1. , - любые

3.

Пусть есть план

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

Если. (7)

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

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

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

Процесс улучшения плана продолжается до тех пор, пока не будут выполнены условия если (7).

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

Задача. На четыре базы A 1 , A 2 , A 3 , A 4 поступил однородный груз в следующем количестве: а 1 тонн - на базу А 1 , а 2 тонн - на базу А 2 , а 3 тонн - на базу А 3 , а 4 тонн - на базу А 4 . Полученный груз требуется перевезти в пять пунктов: b 1 тонн - на базу B 1 , b 2 тонн - на базу B 2 , b 3 тонн - на базу B 3 , b 4 тонн - на базу B 4 , b 5 тонн - на базу B 5 . Расстояния между пунктами назначений указаны в матрице расстояний.

пункты отправления	пункты назначения
потребности

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

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

, .

1. Решим задачу диагональным методом или методом северо-западного угла.

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

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

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (поставщики) A1, A2, . . ., Am в n пунктов потребления (потребители) B1, B2, . . . Bn так, чтобы:

Вывезти все грузы от поставщиков;

Удовлетворить спрос каждого потребителя;

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

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

Обозначим:

ai - наличие груза в i -ом пункте отправления https://pandia.ru/text/78/103/images/image205_0.gif" width="81" height="27 src=">;

сij - стоимость перевозки единицы груза из i -ого пункта отправления в j -ый пункт потребления (тариф перевозки);

xij - количество груза, перевозимого из i -ого пункта отправления в j -ый пункт назначения, назначения, xij ≥ 0.

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

Запишем математическую модель транспортной задачи.

Требуется определить матрицу ) , которая удовлетворяет следующим условиям:

Https://pandia.ru/text/78/103/images/image210_0.gif" width="74" height="45">.gif" width="47" height="21">.gif" width="63" height="20"> (5.3)

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

L () = https://pandia.ru/text/78/103/images/image215_0.gif" width="36" height="24"> удовлетворяют системе линейных уравнений (5.1), (5.2) и условию неотрицательности, то обеспечивается доставка необходимого груза каждому потребителю, вывоз имеющегося груза от всех поставщиков, а также исключаются обратные перевозки.

Определение 1. Всякое неотрицательное решение систем линейных уравнений (5.1) и (5.2), определенное матрицей ) называется допустимым планом транспортной задачи .

Определение 2. План ) https://pandia.ru/text/78/103/images/image218_0.gif" width="23" height="24"> , называется базисным или опорным.

Определение 4. Если в опорном плане число отличных от нуля значений переменных https://pandia.ru/text/78/103/images/image219_0.gif" width="55" height="22">.gif" width="55" height="22"> > , вводится фиктивный (n+ 1) –ый пункт назначения с потребностью bn +1 = − https://pandia.ru/text/78/103/images/image221_0.gif" width="83 height=22" height="22">

Если < https://pandia.ru/text/78/103/images/image220_0.gif" width="56 height=25" height="25">.gif" width="79" height="22 src=">

Рассмотрим один из методов построения первого опорного плана транспортной задачи – метод минимальной стоимости или наилучшего элемента матрицы удельных затрат.

Определение 6. Наилучшим элементом матрицы удельных затрат (тарифов) будем называть наименьший тариф, если задача поставлена на минимум целевой функции, наибольший тариф – если задача поставлена на максимум.

Алгоритм построения первого опорного плана.

1. Среди матрицы удельных затрат находим наилучший тариф.

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

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

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

Дальнейшее улучшение первого опорного плана транспортной задачи и получение оптимального плана производим методом потенциалов.

Теорема 3 . План ) транспортной задачи является оптимальным, если существует система (m + n) чисел ui и vj (называемых потенциалами), удовлетворяющая условиям:

(5.6)

(5.7)

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

Обозначим: ) оценка свободной (незанятой) клетки таблицы.

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

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

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

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

Потенциалы могут быть рассчитаны только для невырожденного плана. Если число занятых клеток в опорном плане (число базисных переменных) меньше, чем (m+n−1), то вносим нуль в одну из свободных клеток таблицы так, чтобы общее число занятых клеток стало равным (m+n−1). Нуль вводят в клетку с наилучшим тарифом, которая принадлежит строке или столбцу. Одновременно вычеркиваемых при составлении первого опорного плана. При этом фиктивно занятая нулем клетка таблицы не должна образовывать замкнутого прямоугольного контура с другими занятыми клетками таблицы.

3. Расчет значения функции цели (5.4) путем суммирования произведений тарифов (удельных затрат) на объемы перевозимого груза по всем занятым клеткам таблицы.

4. Проверка оптимальности плана.

Определяем потенциалы . Для каждой занятой клетки записываем уравнение , в результате получаем систему (m + n−1) уравнений с (m + n) переменными.

Так как число переменных больше числа уравнений, то полученная система не определена и имеет бесчисленное множество решений..gif" width="70" height="22">, тогда остальные потенциалы определяются однозначно, а их значения заносятся в дополнительные строку и столбец распределительной таблицы.

Для каждой свободной клетки определяем оценки https://pandia.ru/text/78/103/images/image233.gif" width="72 height=24" height="24">(задача решается на минимум целевой функции), то оптимальный план найден. Если хотя бы одна оценка свободной клетки не удовлетворяет условию оптимальности, то необходимо план улучшить, осуществив перераспределение груза.

5.

Из всех положительных оценок свободных клеток выбираем наибольшую (задача поставлена на минимум); из всех отрицательных – наибольшую по абсолютной величине (задача поставлена на максимум). Клетку, которой соответствует наибольшая оценка, следует заполнить, т. е. направить в нее груз. Заполняя выбранную клетку, необходимо изменить объем поставок, записанных в ряде других занятых клеток и связанных с заполняемой так называемым циклом.

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

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

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

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

Замечания.

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

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

3. Значение целевой функции на каждой итерации можно рассчитать следующим образом:

(задача поставлена на минимум),

(задача поставлена на максимум),

где - величина перемещаемого по контуру объема груза;

Оценка свободной клетки, в которую направляется груз при переходе к новому опорному плану;

− значение функции цели на k-ой итерации;

− значение функции цели на предыдущей итерации.

Пример.

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

Составить план перевозок однородного груза с минимальными транспортными затратами (числа условные).

Решение.

1. Проверим необходимое и достаточное условие разрешимости задачи:

40+80+80 = 200,

70+20+60+60 = 210.

Как видно, суммарная потребность груза превышает его запасы на складах оптовой базы. Следовательно, модель транспортной задачи является открытой и в исходном виде решения не имеет. Для получения закрытой модели введем дополнительный (фиктивный) склад А4 с запасом груза, равным а 4 = 210 – 200 = 10 ед. тарифы перевозки единицы груза из склада А4 во все магазины полагаем равными нулю.

Все исходные данные заносим в таблицу 7.

						Запасы
	A 1
	A 2		3
	A 3
	A 4
Потребности					210 210

2. Построение первого опорного плана методом минимальной стоимости.

Среди тарифов минимальным или наилучшим является С14 =1. В клетку А1В4 направляем максимально возможный груз, равный min{60,40} = 40. Тогда x 14 = 40. Из склада А1 весь груз вывезен, но потребность четвертого магазина неудовлетворенна на 20 ед. строка А1 выходит из рассмотрения.

Среди оставшихся тарифов минимальный элемент - С23 = 2. В клетку А2В3 направляем груз min{60,80} = 60. При этом столбец В3 выходит из рассмотрения, а из склада А2 не вывезено 20 ед.

Из оставшихся элементов минимальный С22 = 3. В клетку А2В2 направляем груз в количестве min{20,20} = 20. При этом столбец одновременно вычеркиваются строка А2 и столбец В2.

Выбираем минимальный элемент С31 = 4. В клетку А3В1 направляем груз, равный min{70,80} = 70. При этом столбец В1 выходит из рассмотрения, а из склада А3 не вывезено 10 ед. Оставшийся груз с третьего склада направляем в летку А3В4, x 34 = 10. Потребность четвертого магазина не удовлетворена на 10 ед. направим от фиктивного поставщика – склад А4 10 ед. груза в клетку А4В4, x 44 = 10.

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

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

Число занятых клеток или базисных переменных в первом опорном плане равно шести. план транспортной задачи является вырожденным, так как число базисных переменных в невырожденном плане равно m + n – 1 = 4 + 4 – 1 = 7. Для продолжения решения задачи опорный план необходимо дополнить введением фиктивной перевозки, т. е. занять нулем одну из свободных клеток.

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

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

Значение целевой функции первого опорного плана определяем путем суммирования произведений тарифов на объемы перевозимого груза по всем занятым клеткам таблицы.

L(Х1) = 4∙70 + 3∙20 + 2∙60 + 1∙40 + 3∙0 + 6∙10 + 0∙10 = 560 (тыс. руб.).

5. Проверка условия оптимальности.

Рассчитаем потенциалы по занятым клеткам таблицы из условия: https://pandia.ru/text/78/103/images/image260_0.gif" width="139" height="22">Так как число неизвестных потенциалов больше числа уравнений (m + n > m + n – 1), то один из потенциалов принимаем равным нулю..gif" width="115 height=154" height="154">

Полагая , получим https://pandia.ru/text/78/103/images/image265_0.gif" width="82" height="22">, ,https://pandia.ru/text/78/103/images/image268_0.gif" width="193" height="22">

Рассчитанные потенциалы заносим в таблицу 7. Подсчитаем оценки свободных клеток.

https://pandia.ru/text/78/103/images/image270_0.gif" width="167" height="22 src=">,

https://pandia.ru/text/78/103/images/image272_0.gif" width="210" height="22 src=">,

https://pandia.ru/text/78/103/images/image274_0.gif" width="183" height="22 src=">,

https://pandia.ru/text/78/103/images/image276_0.gif" width="153" height="22 src=">,

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

6. Построение нового опорного плана.

Для клетки А3В2 построим прямоугольный замкнутый контур 0таблица 7) и проведем перераспределение груза контуру. Вершинам контура, начиная от вершины, находящейся в свободной клетке А3В2,присваиваем поочередно знаки «+» и «−» .

Из объемов груза, стоящих в минусовых клетках, выбираем наименьшее, т. е. θ = min(20,10) = 10. Прибавляем значение θ = 10 к объемам груза, стоящих в плюсовых клетках, вычитаем из объемов груза, стоящих в минусовых клетках замкнутого контура. В результате получим новый опорный план, приведенный в таблице 8.

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

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

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

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

В зависимости от методов подсчета алгебраических сумм тари­фов для свободных клеток различают два метода отыскания опти­мальногорешения транспортной задачи:

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

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

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

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

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

Выше рассматривалась закрытая модель транспортной задачи, с правильным балансом, когда выполняется условие (1.3). В случае выполнения (1.4) (открытая модель) баланс транспортной задачи может нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах отправления превышает сумму поданных заявок (транспортная задача с избытком запасов):

а i > b j (где i=1,...,m ; j=1,...,n);

2. Сумма поданных заявок превышает наличные запасы (транспортная задача с избытком заявок):

а i < b j (где i=1,...,m ; j=1,...,n);

Рассмотрим последовательно эти два случая:

Транспортная задача с избытком запасов.

Сведем её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов назначения В 1 , B 2 , ... , B n , введём ещё один, фиктивный, пункт назначения B n +1 , которому припишем фиктивную заявку, равную избытку запасов над заявками

b n+1 = а i - b j (где i=1,...,m ; j=1,...,n) ,

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения b n +1 будем считать равной нулю. Введением фиктивного пункта назначения B n +1 с его заявкой b n +1 мы сравняли баланс транспортной задачи, и теперь ее можно решать, как обычную транспортную задачу с правильным балансом.

Транспортная задача с избытком заявок.

Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления A m +1 с запасом a m +1 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю.

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

1) Объем работы транспорта (критерий - расстояние в т/км). Минимум пробега удобен для оценки планов перевозок, поскольку расстояние перевозки определяется легко и точно для любого направления. Поэтому критерию нельзя решать транспортные задачи с участием многих видов транспорта. С успехом применяется при решении транспортных задач для автомобильного транспорта. При разработке оптимальных схем перевозки однородных грузов автомобилями.

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

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

4) Сроки доставки грузов (критерий - затраты времени).

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

6) Приведенные затраты (с учетом полных эксплуатационных расходов капиталовложений на строительство объектов в подвижной состав).

,

где - эксплутационные издержки,

Расчетный коэффициент эффективности капиталовложения,

Капитальные вложения, приходящие на 1 т груза на протяжении участка,

Т - время следования,

Ц - цена одной тоны груза.

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

Рассмотрим транспортную задачу, в качестве критерия оптимальности которой взята минимальная стоимость перевозок всего груза. Обозначим через тарифы перевозки единицы груза из i-го пункта отправления в j-й пункт назначения, через – запасы груза в i-м пункте отправления, через – потребности в грузе в j–м пункте назначения, а через – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения. Тогда математическая постановка задачи состоит в определении минимального значения функции

при условиях

(2)

(3)

(4)

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

Таким образом, Т-задача представляет собой задачу ЛП с m*n числом переменных, и m + n числом ограничений - равенств.

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

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

Существует ряд практических задач, в которых условие баланса не выполняется. Такие модели называются открытыми . Возможные два случая:

В первом случае полное удовлетворение спроса невозможно .

Такую задачу можно привести к обычной транспортной задаче следующим образом. В случае превышения потребности над запасом, т. е. вводится фиктивный (m +1)–й пункт отправления с запасом груза и тарифы полагаются равными нулю:

Тогда требуется минимизировать

при условиях

Рассмотрим теперь второй случай .

Аналогично, при вводится фиктивный (n +1)–й пункт назначения с потребностью и соответствующие тарифы считаются равными нулю:

Тогда соответствующая Т-задача запишется так:

Минимизировать

при условиях:

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

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

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

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

· из запаса соответствующего пункта отправки;

· из потребности соответствующего пункта назначения.

Пример.

Четыре предприятия данного экономического района для производства продукции используют три вида сырья. Потребности в сырье каждого из предприятий соответственно равны 120, 50, 190 и 110 ед. Сырье сосредоточено в трех местах его получения, а запасы соответственно равны 160, 140, 170 ед. На каждое из предприятий сырье может завозиться из любого пункта его получения. Тарифы перевозок являются известными величинами и задаются матрицей

Составить такой план перевозок, при котором общая стоимость перевозок является минимальной.

Решение. Обозначим через количество единиц сырья, перевозимого из i–го пункта его получения на j–е предприятие. Тогда условия доставки и вывоза необходимого и имеющегося сырья обеспечиваются за счет выполнения следующих равенств:

(6)

При данном плане перевозок общая стоимость перевозок составит

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

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

Основные шаги при решении транспортной задачи:

1. Найти начальный допустимый план.

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

3. Выбрать выводимую из базиса переменную, найти новое базисное решение. Вернуться к шагу 2.

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

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

Матрицу С называют матрицей транспортных затрат, матрицу X, удовлетворяющую условиям Т-задачи (2) и (3) называют планом перевозок, а переменные - перевозками. План , при котором целевая функция минимальна, называется оптимальным.

Число переменных в транспортной задаче с m пунктами отправления и n пунктами назначения равно m*n , а число уравнений в системах (2) и (3) равно m+n . Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно m+n–1 . Следовательно, опорный план транспортной задачи может иметь не более m+n–1 отличных от нуля неизвестных.

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

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

Построение допустимого (опорного) плана в транспортной задаче

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

Наиболее простой способ его нахождения основывается на так называемом мето­де северо-западного угла. Суть метода состоит в последова­тельном распределении всех запасов, имеющихся в первом, вто­ром и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте про­изводства или к попытке полного удовлетворения потребно­стей в очередном пункте потребления. На каждом шаге q вели­чины текущих нераспределенных запасов обозначаются а i (q ), а текущих неудовлетворенных потребностей - b j (q ) . Построение допустимого начального плана, согласно методу северо-запад­ного угла, начинается с левого верхнего угла транспортной таб­лицы, при этом полагаем а i (0) = а i , b j (0) = b j . Для очередной клетки, расположенной в строке i и столбце j , рассматриваются зна­чения нераспределенного запаса в i -ом пункте производства и неудовлетворенной потребности j -ом пункте потребления, из них выбирается минимальное и назначается в качестве объема перевозки между данными пунктами: х i, j =min{а i (q) , b j (q) } . После этого значения нераспределенного запаса и неудовлетворенной потребности в соответствующих пунктах уменьшаются на дан­ную величину:

а i (q+1) = а i (q) - x i , j , b j (q+1) = b j (q) - x i , j

Очевидно, что на каждом шаге выполняется хотя бы одно из равенств: а i (q+1) = 0 или b j (q+1) = 0 . Если справедливо первое, то это означает, что весь запас i-го пункта производства исчерпан и необходимо перейти к распределению запаса в пункте произ­водства i+1 , т. е. переместиться к следующей клетке вниз по столбцу. Если же b j (q+1) = 0, то значит, полностью удовлетворе­на потребность для j -го пункта, после чего следует переход на клетку, расположенную справа по строке. Вновь выбранная клетка становится текущей, и для нее повторяются все пере­численные операции.

Основываясь на условии баланса запасов и потребностей, нетрудно доказать, что за конечное число шагов мы полу­чим допустимый план. В силу того же условия число шагов ал­горитма не может быть больше, чем m+n-1 , поэтому всегда останутся свободными (нулевыми) mn-(m+n-1) клеток. Следовательно, полученный план является базисным. Не ис­ключено, что на некотором промежуточном шаге текущий не­распределенный запас оказывается равным текущей неудовлет­воренной потребности (а i (q) =b j (q)) . В этом случае переход к следующей клетке происходит в диагональном направлении (одновременно меняются текущие пункты производства и по­требления), а это означает «потерю» одной ненулевой компо­ненты в плане или, другими словами, вырожденность построен­ного плана.

Особенностью допустимого плана, построенного методом северо-западного угла, является то, что целевая функция на нем принимает значение, как правило, далекое от оптимально­го. Это происходит потому, что при его построении никак не учитываются значения c i , j . В связи с этим на практике для по­лучения исходного плана используется другой способ - ме­тод минимального элемента , в котором при распределении объемов перевозок в первую очередь занимаются клетки с наи­меньшими ценами.

Пример нахождения опорного плана

F=14 x 11 + 28 x 12 + 21 x 13 + 28 x 14 + 10 x 21 + 17 x 22 + 15 x 23 + 24 x 24 + 14 x 31 + 30 x 32 +25 x 33 + 21 x 34

Первоначальный план получен по методу северо-западного угла. Задача сбалансированная (закрытая).

Таблица 1

Стоимость перевозок по данному плану составляет: 1681:

F=14 *27 + 28* 0 + 21*0 + 28*0 + 10 *6 + 17 *13 + 15*1 + 24 *0 + 14 *0 + 30 *0 +25*26 + 21 *17 =1681

План перевозок

является оптимальным планом тогда и только тогда, когда найдется система платежей

для которой выполняются условия:

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

удовлетворяют ограничениям прямой задачи, а

удовлетворяют ограничениям двойственной задачи, то для оптимальности плана

необходимо и достаточно выполнение условий

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

Условие b) можно расписать как следствие о дополняющей нежесткости, а именно

Итак, для базисных переменных

имеем равенство

а для небазисных переменных

достаточно выполнения допустимости двойственных переменных

Таким образом имеем условия 1) и 2) критерия.

Критерий доказан.

9.5 Построение опорного плана транспортной задачи

Методы решения транспортной задачи сводятся к простым операциям с транспортной таблицей, которая имеет вид:

Базисными клетками транспортной таблицы являются клетки с от-

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

1) сумма перевозок в каждой строке равна запасу в данной

2) сумма перевозок в каждом столбце равна соответствующему

столбцу спросу

Опорный план транспортной задачи содержит не более n+m-1

отличных от нуля перевозок

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

меньше и n+m-1, опорный план - невырожден , если число

ненулевых перевозок равно n+m-1.

Рассмотрим способы построения опорного плана в невырожденном и вырожденном случаях.

Метод севево-западного угла

Рассмотрим "северо-западный угол" незаполненной таблицы, то

есть клетку, соответствующую первому поставщику и первому потребителю.

Возможны три случая.

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

запас равен нулю, поэтому

При этом неудовлетворенный спрос в первом пункте потребления равен

то есть спрос первого потребителя полностью удовлетворен и поэтому

а остаток продукта в первом пункте производства равен

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

поэтому условно считается, что выбывает только поставщик,

а спрос потребителя остается неудовлетворенным и равным нулю.

После этого рассматриваем северо-западный угол оставшейся не-

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

через n+m-1 шагов получим опорный план.

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

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

Открытая и закрытая транспортные задачи. Выделяют два типа ТЗ: открытая ТЗ и закрытая ТЗ.

Транспортная задача называется закрытой, если выполняется условие баланса : суммарный объем производства равен суммарному объему потребления:

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

Открытая ТЗ имеет место в двух случаях.

Первый случай. Суммарный объем производства меньше суммарного объема потребления:

Известно, что для существования допустимого решения транспортной задачи необходимо и достаточно, чтобы задача была закрытой. Поэтому транспортную задачу открытого типа предварительно необходимо свести к закрытой, для чего вводится фиктивный пункт производства с номером m+1 с объемом производства:

, (3.3)

при этом полагают .

Второй случай. Суммарный объем производства больше суммарного объема потребления:

Для сведения ТЗ к закрытому типу вводят фиктивный пункт потребления с номером n+1 с объемом потребления:

, (3.5)

при этом полагают .

Методы решения.

· Как задача линейного программирования ТЗ может быть решена симплекс методом .

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

11. Построение начального (опорного) плана перевозок по методу северо–западного угла и по методу наименьшей стоимости.

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

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