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

Работа добавлена на сайт samzan.net:

ТРАНСПОРТНАЯ ЗАДАЧА

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

- предложения поставщиков,

- спросы потребителей,

где т - число поставщиков, - число потребителей.

Матрица затрат

- коэффициент затрат - затраты на перевозку единицы груза от i – поставщика к j – потребителю

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

, (1)

(2)

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

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

поставка клетки

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

. (7)

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

Особенности математической модели транспортной задачи:

система ограничений есть система уравнений (т.е. транспортная задача задана в канонической форме);
коэффициенты при переменных системы ограничений равны единице или нулю;
каждая переменная входит в систему ограничений два раза: один раз - в систему (1) и один раз - в систему (2).

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

Табл.1

Постав -щики	Предло-жения поставщиков	Потребители и их спрос
		1	2	3	4
		20	110	40	110
1	60	1	2	5	3
2	120	1	6	5	2
3	100	6	3	7	4

Уравнения балансов для каждой строки таблицы поставок, т. е.

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

Рассмотрим закрытую транспортную задачу.

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

Число базисных переменных ТЗ равно рангу системы линейных уравнений (максимальному числу линейно независимых уравнений в системе ограничений).

Теорема 1. Ранг системы уравнений (1), (2) равен .

Основное следствие теоремы 1 - число базисных (основных) переменных закрытой транспортной задачи равно , где т - число поставщиков, п — число потребителей.

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

Клетки, отвечающие базисным переменным - базисные, «заполненные» клетки;

клетки, соответствующие свободным переменным, — свободные или пустые.

Нахождение начального базисного распределения поставок.

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

Пример 2. Найти начальное допустимое базисное распределение поставок для транспортной задачи 1.

Решение.

Дадим максимально возможную поставку в клетку (1,1) - "северо-западный" угол таблицы поставок (Дадим переменной максимально возможное значение):

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

новый "северо-западный" угол - клетка (1,2) и дадим в нее максимально возможную поставку.

1-й поставщик 60-20=40 единиц груза,

х12 = min {40, 110} = 40.

Из рассмотрения выпадает первая строка таблицы поставок (перечеркиваем сплошной линией клетку (1,2) и пунктирной линией оставшиеся свободные клетки первой строки).

новый "северо-западный угол" и т. д. В результате получаем следующее исходное распределение поставок (табл.2). Число заполненных клеток в полученном распределении оказалось равным =3+4-1=6, т.е. числу основных (базисных) переменных.

Табл. 2

Недостаток метода "северо-западного" угла: опорный план строится без учета коэффициентов затрат ТЗ.

Метод наименьших затрат.

Пример 3. Найти методом наименьших затрат начальное распределение поставок в задаче 1.

Решение. Клеток две - (1,1) и (2,1) с коэффициентами затрат, равными 1.

Для клетки (1,1) ,

Для клетки (2,1) .

Даем поставку, равную 20 единицам, в клетку (2,1).

Табл.3

110

120

100

В оставшейся таблице наименьшим коэффициентом затрат обладают две клетки: с12 = с24= 2.

Для клетки (1,2) x12= min {60, 110} = 60;

Для клетки (2,4) x24 = min {120-20, 110} = 100.

Даем поставку в клетку (2,4), для которой x24 = 100 (табл 4).

Получаем x12 = min{60, 110} = 60, x32 = min{100, 110-60} = 50, x34 = min {100-50, 110-100} = 10, x33 = min {100-60, 40} = 40 (табл. 5).

Табл.4

110

120

100

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

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

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

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

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

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

Теорема 3 приводит к правилу 2 нахождения оценок свободных клеток:

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

Полученные при этом коэффициенты затрат свободных клеток равны относительным оценкам этих клеток

Пример 4. Найти оценки свободных клеток базисного распределения поставок, найденного в примере 3.

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

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

Табл. 11

-2(7)

-1(2)

-3(4)

0(1) 0(6) -4(5) -1(3)

После прибавления этого потенциала к коэффициентам затрат первого столбца коэффициент затрат заполненной клетки (2,1) не изменится; чтобы полученный после сложения коэффициент стал равен нулю, потенциал второй строки табл. 11 должен быть равен -1; для обнуления коэффициента затрат клетки (2,4) потенциал четвертого столбца должен быть равен -1 и т. д.

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

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

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

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

Циклом в матрице будем называть ломаную с вершинами в клетках и звеньями, лежащими вдоль строк и столбцов матрицы, удовлетворяющую условиям:

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

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

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

Решение. Начнем с базисного распределения поставок, полученного в задаче 3. Как было установлено ранее (см. задачу 4), данное распределение не оптимально. Оценки свободных клеток приведены в (9).

Цикл пересчета для клетки (1,3) показан на рис. 3.

Рис. 3

Увеличиваем поставку в клетке (1,3) до тех пор, пока поставка в одной заполненных клеток не станет равной нулю (дальнейшее увеличение приводит в область недопустимых решений). Эта клетка принадлежит, конечно, циклу, построенному на рис. 3 для клетки (1,3).

Найдем ее. Если в клетку (1,3) передать поставку, равную , то поставка в клетках цикла со знаком "+" увеличится на z, а в клетках со знаком "-" - уменьшится на z. Поэтому искомая клетка находится среди клеток цикла, имеющих знак « - » Более того, она имеет минимальную поставку среди таких клеток. Так как min{60,40} = 40 (рис. 3), то в нашем случае - это клетка (3,3), и для обнуления поставки в этой клетке по циклу следует передать 40 единиц груза. Таким образом, поставка, передаваемая по циклу, определяется как минимум среди поставок в клетках цикла со знаком «-». После этого клетка (1,3) считается заполненной, а клетка (3,3) — свободной.

В клетках со знаком "+" цикла поставка увеличивается на передаваемую поставку: поставка клетки (3,2) станет равной 90 единицам, поставка клетки (1,3) - 40 единицам. Аналогично в клетках со знаком " - " поставка уменьшится на передаваемую поставку, например, поставка клетки (1,2) станет равной 20 единицам, что видно из табл. 12. Нетрудно доказать, что вновь полученное распределение поставок - базисное.

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

Найдем оценки свободных клеток (матрицу оценок) распределения поставок. Для этого, как и прежде, подберем потенциалы так, чтобы коэффициенты затрат заполненных клеток стали равными нулю (табл.12). Тогда матрица оценок примет вид (10).

Табл.12

100

-2

-1

-3

0 0 -3 -1

Так как среди свободных клеток есть клетка (1,1) с отрицательной оценкой, то найденное распределение не оптимально и передача поставки в клетку (1,1) ведет к уменьшению суммарных затрат на перевозку. Означенный цикл пересчета для клетки (1,1) приведен на рис. 4. По правилу, сформулированному выше, поставка, передаваемая по циклу = {20, 20, 10}= = 10. Передвигая эту поставку по циклу (рис. 4), приходим к новому распределению поставок (табл. 13).

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

Рис. 4

Табл. 13

110

100

Суммарные затраты на перевозку согласно этого распределения поставок в денежных единицах составляют:

Fmin = 1*10 +2*10 +5*40+1*10 +2*110 + 3*100 = 760.

Замечание 1. Поставка, передаваемая по циклу, не может быть ни меньше, ни больше минимума поставок клеток цикла со знаком " - ". Действительно, в первом случае ни одна из клеток цикла не будет иметь нулевой поставки, а потому общее число заполненных клеток таблицы будет равно и, следовательно, распределение не будет базисным. Во втором случае уходим в область недопустимых решений.

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

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

Для данного базисного распределения поставок подбираем потенциалы строк и столбцов таблицы поставок так, чтобы коэффициенты затрат заполненных клеток стали равны нулю. Составляем матрицу оценок.
Если оценки всех свободных клеток неотрицательны, то найденное распределение оптимально — решение закончено. Если среди оценок свободных клеток есть отрицательные, то выбираем одну из них для передачи в нее поставки (для определенности можно брать, например, одну из клеток с наименьшей оценкой).
Для избранной свободной. клетки строится означенный цикл пересчета. Поставка z, передаваемая по циклу, определяется как минимум среди поставок в клетках со знаком " - ". Найденная поставка передвигается по циклу. При этом поставка в клетках цикла со знаком "+" увеличивается на z, а в клетках со знаком " - " уменьшается на z. Клетка, поставка в которой при этом станет равной нулю, будет считаться свободной (далее рассмотрен случай, когда таких клеток несколько), остальные клетки цикла — заполненными. Таким образом, получено новое базисное распределение поставок.
Переходим к п. 1 алгоритма.

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

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

Пример 8. Завершить решение транспортной задачи из примера 4.

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

Табл. 14

-1 -3 -2

Это приводит к матрице оценок (12). Так как среди свободных клеток таблицы есть клетка (3,2) с отрицательной оценкой, то данное базисное распределение поставок не оптимально. Переведем поставку в клетку (3,2) с отрицательной оценкой. Строя для клетки (3,2) означенный цикл пересчета (рис. 5), находим, что объем передаваемой поставки в данном случае равен х32 =min{0,10}= 0. Передавая по построенному циклу нулевую поставку, приходим к новому базисному распределению (табл. 15).

Рис. 5

Табл. 15

-2

1 -1 -2

Подбирая потенциалы к строкам и столбцам табл. 15, находим матрицу (13) оценок данного распределения. Так как среди свободных клеток таблицы есть клетка (1,3) с отрицательной оценкой, то данное базисное распределение не оптимально. Найдем новое базисное распределение, передавая поставку в клетку (1,3) с отрицательной оценкой. Построим цикл для клетки (1,3), показанный на рис. 6.

Поставка, передаваемая в клетку (1,3): При передаче по циклу (рис. 6) 10 единиц груза станут равными нулю поставки в клетках (1,2) и (3,3). Полагаем, что только одна из них стала свободной, например клетка (3,3), а клетка (1,2) заполнена нулевой поставкой. Таким образом, будет получено базисное распределение поставок, представленное в табл. 16.

Рис. 6

Табл. 16

-1

0 -2 -2

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

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

Открытая транспортная задача решается сведением ее к закрытой транспортной задаче.

Пример 9. Найти оптимальное распределение поставок для транспортной задачи (табл. 17).

Табл. 17 Табл. 18

	45	35	55	65			45	35	55	65
40	4	1	2	5		40	4	1	2	5
60	3	2	3	7		60	3	2	3	7
90	4	4	5	2		90	4	4	5	2
					10	0	0	0	0

Решение. В данном случае суммарный спрос потребителей больше, чем суммарное предложение поставщиков (45+35+55+ +65 = 200 > 40+60+90 = 190). Введем "фиктивного поставщика" и в таблицу поставок добавим дополнительную строку (табл. 18) так, чтобы задача стала закрытой. Для этого мощность фиктивного поставщика следует принять равной 10 = 200—190. Коэффициенты затрат этой добавленной строки определяются издержками ввиду недогрузки мощностей потребителей. Если информация об этих издержках отсутствует, то их принимают равными одному и тому же числу (например, нулю, как в табл. 18). Согласно теореме 3, конкретное значение этого числа не влияет на оптимальное распределение поставок.

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

Табл.19

4	1 35	2 5	5
3 10	2	3 50	7
4 35	4	5	2 55
0	0	0	0 10

-2

-3

-4

-2

0 1 0 2

Установим, оптимально ли это распределение - найдем для него матрицу оценок (15). Так как среди оценок свободных клеток есть отрицательные, то найденное распределение не оптимально. Переведем поставку в одну из клеток с наименьшей отрицательной оценкой, например в клетку (4,3). Цикл для этой клетки изображен на рис 7. Поставка, передаваемая по циклу, равна х43 = min {50, 35, 10} = 10. Передвигая по циклу поставку, равную 10 единицам, приходим к следующему распределению поставок (табл. 20).

Найдем оценки свободных клеток данного распределения (20). Так как оценки всех свободных клеток неотрицательны, то распределение поставок табл. 20 оптимальное.

Рис. 7

Табл. 20

4	1 35	2 5	5
3 20	2	3 40	7
4 25	4	5	2 65
0	0	0 10	0

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

(2,1)

. (9)

7 -

2 -

1 +

5 +

2 -

(1,2)

(3,2)

(1,3)

(3,3)

1 -

(1,1)

(1,2)

(3,2)

2 +

100

(2,4)

3 +

2 -

(3,4)

4 -

. (11)

1 +

. (12)

2 +

3 -

(2,2)

(3,2)

(2,3)

(3,3)

. (13)

(3,3)

(1,3)

(3,2)

(1,2)

3 -

3 +

1 +

2 -

. (14)

0 -

. (15)

2 +

0 +

4 -

3 -

3 +

(2,1)

(2,3)

(3,1)

(4,3)

(3,4)

(4,4)

. (16)

. (10)

1. - порядок действий установить связь между компонентами и результатами этих действий
2. Первые христиане 2
3. і. Основу СОТ становлять угоди узгоджені підписані і ратифіковані більшістю країнучасниць міжнародної тор
4. эксплуататоры и их пособники духовенство люди имеющие нетрудовой доход лица применяющие наёмный труд.html
5. .Научнотеоретические предпосылки возникновения практического радиовещания Античный мир А.
6. Принтери та сканери
7. Анализ привлекательности рынка детской одежды
8. Р Минимальная полезная длина предохранительного тупика для путей общего пользования не менее 50.
9. Цель функционирования предприятия2
10. ТЕМА 4 КРИМІНАЛЬНА ПСИХОЛОГІЯ
11. История Ислама
12. за того что банки приостановили операции по счетам клиентов
13. Дафна Моему отцу Майклу Пикарди Мы никогда туда не вернемся это бесспорно
14. остров сей был жилищем для могущественных прислужников первых богов
15. реферату- Теорія виробництваРозділ- Економіка підприємства Теорія виробництва План Виробництво та виро
16. Каймановы острова
17. Развитие теории и практики управления в России СОДЕРЖАНИЕ Введение
18. Вводные, вставные конструкции и обращения в поэтической речи МЮ Лермонтова
19. Лабораторна робота 12 Елементи управління і користувацька форма у програмах Word і Excel
20. Введение 3 Неформальные молодежные движения и объединения 4 2

Материалы собраны группой SamZan и находятся в свободном доступе