Размещено на http://www.allbest.ru/

2

Размещено на http://www.allbest.ru/

Министерство образования и науки Российской Федерации

Федеральное агентство по образованию

Санкт-Петербургский государственный политехнический университет

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

Выполнила студентка:

группы: «З3072/24»

Ермакова А.А.

Подпись___________

Проверил:

Артеменко Е.С.

Дата_______________

Оценка____________

Санкт-Петербург

2012

• Содержание

1 Транспортная задача линейного программирования 1.1 Математическая модель транспортной задачи (ТЗ) 1.2 Свойства транспортной задачи 1.3 Методы нахождения начального плана перевозок 1.3.1 Метод северо-западного угла 1.3.2 Метод минимального элемента 1.4 Метод потенциалов 1.4.1 Циклы матрицы перевозок 1.4.2 Метод потенциалов, его алгоритм 2 Решение транспортной задачи. Метод северо-западного угла	3 3 5 6 7 9 11 11 12 19

транспортная задача решение методы

1 Транспортная задача линейного программирования

1.1 Математическая модель транспортной задачи (ТЗ)

Пусть имеются m пунктов отправления A₁, A₂, …, A_m, в которых находится однородный груз в количествах а₁, а₂, …, а_m cоответственно, и n пунктов назначения B₁, B₂, …, B_n , потребности которых в данном грузе равны b₁, b₂, …, b_n. Известны c_ij расходы на перевозку единицы груза из i-го пункта отправления в j-й пункт потребления. Требуется составить план перевозок так, чтобы запасы каждого поставщика были бы вывезены, спрос каждого потребителя удовлетворен, и общая стоимость всех перевозок была минимальной.

Исходные данные транспортной задачи запишем в виде матрицы перевозок (табл. 1.1).

Таблица 1.1

Bj Ai	B1	B2	…	Bn	Запасы ai
A1	С11	C12		C1n	a1
A2	С21	C22		C2n	a2
…	…	…	…	…	…
An	Сm1	Cm2		Cmn	am
Потребности bj	b	b	…	bn	-

Обозначим через количество единиц груза, которое нужно перевезти из пункта A_i в пункт B_j .

Так как нужно перевезти весь груз из каждого пункта отправления A_i , то должны выполняться равенства:

транспортная задача решение методы

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

Стоимость всех запланированных перевозок должна быть минимальной:

.

Математическая модель транспортной задачи (ТЗ) в общем случае имеет вид:

, (1)

, (2)

(3)

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

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

(4)

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

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

Всякое неотрицательное решение системы линейных уравнений (2), определяемое матрицей называется планом ТЗ. План, при котором целевая функция (1) принимает свое минимальное значение, называется оптимальным планом ТЗ. Матрица называется матрицей тарифов (издержек или транспортных расходов).

1.2 Свойства транспортной задачи

1. Ранг матрицы из коэффициентов при неизвестных системы ограничений ТЗ равен m+n-1, где m и n - количество поставщиков и потребителей соответственно.

2. ТЗ всегда имеет оптимальный план.

3. В ТЗ всегда существуют допустимые планы, содержащие не более m+n-1 положительных элементов.

4. Если в ТЗ все числа a_i, b_j целые, то она имеет оптимальный целочисленный план.

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

Решение ТЗ разобьем на три этапа:

· определение первоначального допустимого решения;

· проверка найденного решения на оптимальность (оценка плана по критерию стоимости). Если оно оптимальное, то ТЗ решена;

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

1.3 Методы нахождения начального плана перевозок

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

В матрице есть m+n-1 базисных клеток. Их число совпадает с числом независимых уравнений - ограничений.

Значение в матрице перевозок находится по формуле:

(5)

Значение в свободной клетке не пишется явно, а вместо этого в ней ставится точка.

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

Вычисление проводим по формуле (5), начиная с элемента x₁₁, стоящего в северо-западном углу матрицы перевозок.

Пример 1. Найти начальный план перевозок в ТЗ методом северо-западного угла.

Запишем матрицу перевозок (табл. 1.2).

Таблица 1.2

Bj Ai	B1	B2	В3	B4	Запасы ai
A1	10 5	0 10	20 *	11	15
A2	12 *	7 5	9 15	20 5	25
A3	0	14 *	16 *	18 5	5
Потребности bj	5	15	15	10	45 45

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

.

Тогда в пункте B₁ потребности удовлетворены, и, следовательно, (в табл. 3.2 ставится точка (*)). Первый столбец выбывает из рассмотрения.

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

.

Запасы в пункте А₁ исчерпаны и (в табл. 3.2 ставится точка). Первая строка таблицы выбывает из рассмотрения.

Продолжаем с северо-западного угла:

.

Потребности в пункте В₂ удовлетворены, второй столбец выбывает из рассмотрения.

Продолжаем с северо-западного угла:

и .

Третий столбец выбывает из рассмотрения.

.

Запасы в пункте А₂ исчерпаны.

.

Получен начальный план перевозок:

с суммарной стоимостью

.

Число базисных клеток

m+n-1=3+4-1=6.

Примечание. При нахождении начального плана перевозок возможен случай вырождения, когда в результате вычислений значения x_ij получается, что потребности в пункте B_j удовлетворены, а запасы в пункте A_i исчерпаны. Тогда одновременно из рассмотрения выбывают строка и столбец. Рекомендуется в одну из клеток выбывающих строки и столбца (лучше в клетку с наименьшей стоимостью) ставить так называемый базисный нуль. Эта клетка считается базисной (в ней пишется 0), а общее число базисных клеток остается равным m+n-1.

1.3.2 Метод минимального элемента

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

В этом методе по формуле (11) последовательно заполняются клетки с наименьшей стоимостью перевозок. Если есть несколько клеток с наименьшей стоимостью, то из них выбирается любая.

Пример 2. Найти начальный план перевозок в ТЗ методом минимального элемента.

Запишем матрицу перевозок (табл. 1.3).

Таблица 1.3

Bj Ai	B1	B2	В3	B4	Запасы ai
A1	10 0	0 15	20 *	11	15
A2	12	7 0	9 15	20 10	25
A3	0 5	14 *	16 *	18	5
Потребности bj	5	15	15	10	45 45

Заполняем клетку с наименьшей стоимостью:

.

Потребности в пункте В₂ удовлетворены, запасы в пункте А₁ исчерпаны - случай вырождения. В клетке с наименьшей стоимостью среди выбывающих клеток ставим базисный нуль .

Среди оставшихся клеток ищем клетку с наименьшей стоимостью:

- случай вырождения, базисный нуль .

Из оставшихся клеток заполняем клетку с наименьшей стоимостью:

.

Потребности в пункте В₃ удовлетворены, выбывает третий столбец.

.

Получен начальный план перевозок:

с суммарной стоимостью

,

которая меньше стоимости, полученной методом северо-западного угла. Число базисных клеток m+n-1=3+4-1=6.

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

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

1.4.1 Циклы матрицы перевозок

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

a б в

Рис. 1. Простейшие циклы

На рис. 1 звездочкой отмечены клетки матрицы, включенные в состав цикла. На рис. 3в кружком отмечена точка самопересечения.

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

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

1.4.2 Метод потенциалов, его алгоритм

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

для ,

для , .

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

АЛГОРИТМ.

1. Для ТЗ с правильным балансом находим начальный план перевозок методом северо-западного угла или методом минимального элемента.

2. Для каждой базисной клетки составляем уравнение . Так как число базисных клеток m+n-1, то система m+n-1 уравнений с m+n неизвестными имеет бесконечное множество решений. Для определенности положим u₁=0. Тогда все остальные потенциалы находятся однозначно. Вносим их в матрицу перевозок.

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

4. Для всех свободных клеток проверяем выполнение условия оптимальности:

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

· если для одной или нескольких свободных клеток, то переходим к п. 5.

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

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

Клетки матрицы, не входящие в цикл, остаются без изменения.

Строим новую матрицу перевозок.

7. Переход к шагу 2.

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

Пример 3. Составить математическую модель ТЗ, решить ТЗ:

Запишем матрицу перевозок (табл. 1.4).

Таблица 1.4

Bj Ai	B1	B2	В3	B4	Запасы ai
A1	10	0	20	11	15
A2	12	7	9	20	25
A3	0	14	16	18	5
Потребности bj	5	15	15	10	45 45

1. Пусть - количество единиц груза, которое нужно перевезти из пункта А_i в пункт B_j .

2. Ограничения:

а) по запасам

б) по потребностям

3. Целевая функция:

.

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

4. Данная ТЗ с правильным балансом: 15+25+5=5+15+10; 45=45.

5. Начальный план перевозок найден в п. 1.3.2 методом минимального элемента (табл. 1.3). Выпишем найденную матрицу перевозок.

6. Находим потенциалы базисных клеток:

Матрица перевозок

	Bj Ai	B1	B2	В3	B4	Запасы ai
u1=0	A1	10 0	0 15	20 2	11 13	15
u2=7	A2	12 17	7 0	9 15	20 10	25
u3= -10	A3	0 5	14 -10	16 -8	18 3	5
	Потребности bj	5	15	15	10	45 45

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

8. Для свободных клеток проверяем выполнение условия оптимальности: для . Для клеток (1,4) и (2,1) условие не выполнено.

9. , Для свободных клеток строим обозначенный цикл.

10. Производим сдвиг по циклу на Клетка (2,1) становится базисной , а клетка (1,1) - свободной.

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

12. Строим новую матрицу перевозок.

u1=0 10 5 0 15 20 2 11 13 u2=7 12 0 7 0 9 15 20 10 u3= -5 0 5 14 -5 16 -3 18 8 Матрица перевозок.

Для свободной клетки (1,4) условие оптимальности не выполнено. Строим для нее обозначенный цикл, осуществляем сдвиг по циклу на Клетка (1,4) становится базисной , клетка (2,4) - свободной. Строим новую матрицу перевозок.

u1=0 10 5 0 5 20 2 11 10 u2=7 12 0 7 10 9 15 20 18 u3=-5 0 5 14 -5 16 -3 18 6 Матрица перевозок

13. Переходим к шагу 2 метода потенциалов:

Для всех свободных клеток

.

Полученный план является оптимальным:

.

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

.

транспортная задача решение методы

2 Решение транспортной задачи. Метод северо-западного угла

Имеется 3 поставщика молочной продукции - компания «ВИММ-БИЛЛЬ-ДАНН», ОАО «Петмол» и ООО «ПИСКАРЕВСКИЙ» - и четыре потребителя однородной продукции: ОАО «ЛЕНСТРОЙКЕРАМИКА» для работников предприятия за тяжелый, вредный труд, ООО «АГРОТОРГ» для дальнейшей перепродажи населению, ЗАО «ТАНДЕР» и ОАО «ДИКСИ Групп» также для дальнейшей перепродажи населению.

Запасы поставщика «ВИММ-БИЛЛЬ-ДАНН» составляют 170 единиц продукции; ОАО «Петмол» - 120 единиц; ООО «ПИСКАРЕВСКИЙ» - 150 единиц продукции, которая должна быть доставлена потребителям.

Потребность потребителя «ЛЕНСТРОЙКЕРАМИКА» составляет 90 единиц продукции; «АГРОТОРГ» - 130 единиц; ЗАО «ТАНДЕР» - 120 единиц продукции; «ДИКСИ Групп» - 100 единиц продукции.

Стоимость доставки единицы продукции от поставщика «ВИММ-БИЛЛЬ-ДАНН» к указанным потребителям равна 4, 3, 5, 2 ден. ед.

Стоимость доставки единицы продукции от поставщика ОАО "Петмол" к указанным потребителям равна 7, 1, 2, 3 ден. ед.

Стоимость доставки единицы продукции от поставщика ООО «ПИСКАРЕВСКИЙ» к указанным потребителям равна 9, 2, 4, 5 ден. ед.

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

Таблица 2.1.

	90	130	120	100
170	904	803	5 -	2 -
120	7 -	501	702	3 -
150	9 -	2 -	504	1005

3+4-1=6 - ранг системы ограничений.

Мы израсходовали все запасы поставщиков и удовлетворили все потребности потребителей.

S₀=4*90+3*80+1*50+2*70+4*50+5*100=1490 ден. ед.

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

	90	130	120	100
170	904	803	5 -	2 -	-4
120	7 -	501	702	3 -	-2
150	9 -	2 -	504	1005	-4
	0	1	0	-1

7 потенциалов при сложении дают 0.

Матрица оценок:

0 0 -1 -3

5 0 0 0

5 -1 0 0

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

Размещено на http://www.allbest.ru/

...