Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
ТРАНСПОРТНАЯ ЗАДАЧА
Математическая модель транспортной задачи. Важным частным случаем задачи линейного программирова ния является транспортная задача.
- предложения поставщиков,
- спросы потребителей,
где т - число поставщиков, - число потребителей.
Матрица затрат
- коэффициент затрат - затраты на перевозку единицы груза от i – поставщика к j – потребителю
Тогда система ограничений примет вид
, (1)
(2)
Математическая формулировка транспортной задачи в общей постановке будет следующей: на множестве неотрицательных (допустимых) решений системы ограничений (1), (2) найти такое решение , при котором значение целевой функции минимально
Произвольное допустимое решение - распределение поставок
поставка клетки
Транспортная задача, приведенная в примере, обладает важной особенностью: предложения поставщиков равны спросу потребителей, т.е.
. (7)
Такие транспортные задачи называются закрытыми. В противном случае транспортная задача называется открытой
Особенности математической модели транспортной задачи:
Пример 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.
Решение.
.
Заполнен ные клетки перечеркиваем сплошной линией (табл. 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
|
20 |
110 |
40 |
110 |
|
|
60 |
1 |
2 |
5 |
3 |
|
120 |
1 20 |
6 |
5 |
2 |
|
100 |
6 |
3 |
7 |
4 |
В оставшейся таблице наименьшим коэффициентом затрат об ладают две клетки: с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
|
20 |
110 |
40 |
110 |
|
|
60 |
1 |
2 60 |
5 |
3 |
|
120 |
1 20 |
6 |
5 |
2 100 |
|
100 |
6 |
3 50 |
7 40 |
4 10 |
Теорема 2. Пусть на каждом шаге заполнения таблицы поста вок возникает одна заполненная клетка, причем из рассмотрения на каждом (кроме последнего) шаге выпадает либо одна строка, либо один столбец. Тогда переменные, соответствующие заполненным клеткам, можно принять за базисные.
Критерий оптимальности базисного распределения поставок. В задаче ЛП на максимум допустимое базисное решение считается оптимальным, когда все относительные оценки свободных переменных неположительные. Транспортная задача - задача на минимум, поэтому оптимум достигается тогда и только тогда, когда все относительные оценки свободных переменных неотрицательные.
Оценка при свободной переменной называется оценкой свободной клетки .
Тогда критерий опти мальности формулируется следующим образом: базисное распреде ление поставок оптимально тогда и только тогда, когда оценки всех свободных клеток неотрицательны.
.
Метод потенциалов
Теорема 3. (о потенциалах). Оценка свободной клетки не изме нится, если к коэффициентам затрат некоторой строки (столбца) таблицы поставок прибавить некоторое число. Это число, прибав ляемое к коэффициентам затрат выделенной строки (столбца), будем называть потенциалом данной строки (столбца).
Теорема 3 приводит к правилу 2 нахождения оценок свободных клеток:
к коэф фициентам затрат таблицы поставок в каждой строке и столбце надо прибавить такие числа (потенциалы), чтобы коэффициенты затрат в заполненных клетках стали равными нулю.
Полученные при этом коэффициенты затрат свободных клеток равны относительным оценкам этих клеток
Пример 4. Найти оценки свободных клеток базисного распределе ния поставок, найденного в примере 3.
Решение. Найдем оценки свободных клеток, следуя из ложенной выше последовательности действий. Изменение коэффициентов затрат можно начинать с любого столбца (строки). Потенциал столбца (строки), избранного для нача ла, может быть произвольным, но можно доказать, что после его фиксации потенциалы остальных столбцов и строк будут определены однозначно.
Начнем с первого столбца. Пусть потенциал этого столбца ра вен нулю (табл. 11). Рядом с потенциалом в скобках записываем номер шага (поставки опускаем).
Табл. 11
|
1 |
2
|
5
|
3 |
|
1
|
6 |
5 |
2
|
|
6 |
3
|
7
|
4
|
-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
|
1 |
2 20 |
5 40 |
3 |
|
1 20 |
6 |
5 |
2 100 |
|
6 |
3 90 |
7
|
4 10 |
-2
-1
-3
0 0 -3 -1
Так как среди свободных клеток есть клетка (1,1) с отрица тельной оценкой, то найденное распределение не оптимально и передача поставки в клетку (1,1) ведет к уменьшению суммарных затрат на перевозку. Означенный цикл пересчета для клетки (1,1) приведен на рис. 4. По правилу, сформулированному выше, поставка, передаваемая по циклу = {20, 20, 10}= = 10. Передви гая эту поставку по циклу (рис. 4), приходим к новому рас пределению поставок (табл. 13).
Найдя матрицу (11) оценок этого распределения, заключаем, что оно оптимально, так как среди оценок свободных клеток нет отрицательных.
Рис. 4
Табл. 13
|
1 10 |
2 10 |
5 40 |
3 |
|
1 10 |
6 |
5 |
2
110 |
|
6 |
3 100 |
7
|
4
|
Суммарные затраты на перевозку согласно этого распределения поста вок в денежных единицах составляют:
Fmin = 1*10 +2*10 +5*40+1*10 +2*110 + 3*100 = 760.
Замечание 1. Поставка, передаваемая по циклу, не может быть ни меньше, ни больше минимума поставок клеток цикла со знаком " - ". Действительно, в первом случае ни одна из клеток цикла не будет иметь нулевой поставки, а потому общее число заполненных клеток таблицы будет равно и, следователь но, распределение не будет базисным. Во втором случае ухо дим в область недопустимых решений.
Замечание 2. Оптимальное распределение поставок, найден ное в задаче 7 (табл.13), не единственное, так как среди оценок свободных клеток есть нулевые, например клетка (2,3) в матрице (11).
.
Последовательность действий по решению произвольной за крытой транспортной задачи теперь может быть изложена в виде следующего алгоритма.
Рассмотрим особые случаи, которые могут возникнуть при ре шении транспортной задачи.
Пример 8. Завершить решение транспортной задачи из примера 4.
Решение. Установим сначала, оптимально ли распределение поставок, полученное в указанном примере методом "северо-западного" угла (табл. 8). Подберем потенциалы строк и столбцов этой таблицы поставок так, чтобы коэффициенты затрат заполненных клеток стали равны нулю (табл. 14).
Табл. 14
|
1 20 |
3 10 |
3 |
|
3 |
3 0 |
2 30 |
|
4 |
1 |
2 10 |
0
0
0
-1 -3 -2
Это приводит к матрице оценок (12). Так как среди свободных клеток таблицы есть клетка (3,2) с отрицательной оценкой, то дан ное базисное распределение поставок не оптимально. Переведем поставку в клетку (3,2) с отрицательной оценкой. Строя для клетки (3,2) означенный цикл пересчета (рис. 5), находим, что объем передаваемой поставки в данном случае равен х32 =min{0,10}= 0. Передавая по построенному циклу нулевую поставку, приходим к новому базисному распределению (табл. 15).
Рис. 5
Табл. 15
|
1 20 |
3 10 |
3 |
|
3 |
3 0 |
2 30 |
|
4 |
1 0 |
2 10 |
-2
0
0
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 20 |
3 0 |
3 10 |
|
3 |
3 0 |
2 30 |
|
4 |
1 10 |
2 0 |
-1
0
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 -
40
2 -
20
+
50
1 +
5 +
2 -
60
(1,2)
(3,2)
(1,3)
(3,3)
1 -
20
(1,1)
(1,2)
(3,2)
2 +
100
(2,4)
3 +
90
2 -
10
(3,4)
4 -
10
. (11)
1 +
. (12)
2 +
30
3 -
0
(2,2)
(3,2)
(2,3)
(3,3)
. (13)
(3,3)
(1,3)
(3,2)
(1,2)
3 -
10
3 +
1 +
0
2 -
10
. (14)
0 -
10
. (15)
2 +
55
0 +
4 -
35
3 -
50
3 +
10
(2,1)
(2,3)
(3,1)
(4,3)
(3,4)
(4,4)
. (16)
. (10)