Для реализации данной темы необходимо:
1. изучить теоретический материал,
2. применить теоретические навыки при решении конкретной задачи,
3. рассмотреть решение той же задачи в табличном редакторе Excel.
Это задача о наиболее рациональном плане перевозок однородного продукта из пунктов производства в пункты потребления.
Пусть имеется m пунктов производства некоего однородного продукта А 1 …,Аi …,Am и n пунктов его потребления B1 …,Bj …,Bn . В пункте Аi (i=1,2,3,…,m) производится Аi единиц, а в пункте Bj (j=1,2,3,…,n) потребляется Bj единиц продукта.
Предполагается, что
Транспортные издержки, связанные с перевозкой единицы продукта из пункта A i в пункт Bj равны Cij .
Суть задачи состоит в составлении оптимального плана перевозок, минимизирующего суммарные транспортные издержки, при реализации которого запросы всех пунктов потребления B j j=1,2,3,…,n, были бы удовлетворены за счет производство продукта в пунктах Аi i=1,2,3,…,m.
Пусть x ij — количество продукта, перевозимого из пункта Ai в пункт Bj . Тогда транспортная задача формулируется так: определить значения переменных xij , i=1,2,3,…,m, j=1,2,3,…,n, минимизирующих транспортные издержки.
c ij xij
при условиях,
(1)
(2)
, i=1,2,…,m; j=1,2,…,n.(3)
Множество , i=1,2,…,m; j=1,2,…,n., удовлетворяющее этим условиям, называется планом перевозок, а его элементы — перевозками.
На основе метода математического моделирования в операционных исследованиях решаются также многие важные задачи, требующие специфических методов решения. К их числу относятся:
1. Задача надежности изделий.
2. Задача замены оборудования.
3. Теория расписаний (так называемая теория календарного планирования).
4. Задача распределения ресурсов.
5. Задача ценообразования.
6. Теория сетевого планирования.
В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с m баз A 1 , A2 ,…,Am , n потребителям B1 , B2 ,…,Bn .
Различают два типа транспортных задач: по критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
Особенности организации автомобильных перевозок в туризме
... коммунальные перевозки в населенных пунктах: вывоз бытовых отходов, снега, обслуживание в населения в период ... при централизации перевозок. Эта форма организации перевозок лежит в основе деятельности ... перевозки прямого сообщения, которые осуществляются от пункта отправления до пункта назначения на одном автомобиле; перевозки смешанного (комбинированного) сообщения, которые осуществляются автомобильным ...
Обозначим количество груза, имеющегося на каждой из m баз (запасы), соответственно A 1 , A2 ,…,Am , а общее количество имеющегося в наличии груза-A:
A= A 1 + A2 +…+Am ; (1.1)
заказы каждого из потребителей (потребности) обозначим соответственно B 1 , B2 ,…,Bn , а общее количество потребностей — B:
B= B 1 + B2 +…+Bn ; (1.2)
Тогда при условии
a=b; (1.3)
мы имеем закрытую модель, а при условии
ab; (1.3)
- открытую модель транспортной задачи.
Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза (a>b), либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены (a<b).
Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например — склад.
План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:
|
Пункты отправления |
Пункты назначения |
Запасы |
||||
|
… |
||||||
|
… |
||||||
|
… |
||||||
|
… |
… |
… |
… |
… |
… |
|
|
… |
||||||
|
Потребности |
… |
или |
||||
Условие a=b или ab означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи.
Переменное x ij означает количество груза, перевозимого с базы Аi потребителю Bj : совокупность этих величин образует матрицу (матрицу перевозок).
(2.1)
Система (2.1) содержит m+n уравнений с mn неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (2.1) могут быть разделены на две группы: первая группа из т первых уравнений (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения).
В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок).
Таким образом, каждая неизвестная встречается в системе (2.1) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.
Такая структура системы (2.1) позволяет легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней мере, один из двух их индексов равен единице, а, следовательно, свободные неизвестные определяются условием i2, j2.Перепишем систему (2.1) в виде,
(2.1)
где символы и означают суммирование по соответствующему индексу. Так, например,
При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь i2, j2).
В рассматриваемой нами системе только два уравнения, а именно первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные x 12 ,x13 ,…,x1 n с помощью вертикальных уравнений, мы получаем уравнение
или иначе
(2.2)
где символ означает сумму всех свободных неизвестных. Аналогично, исключив из первого вертикального уравнения базисные неизвестные x 21 ,x31 ,…,xm 1 с помощью горизонтальных уравнений, мы получаем уравнение (2.2′)
Так как для закрытой модели транспортной задачи a=b, то полученные нами уравнения (2.2) и (2.2′) одинаковы и, исключив из одного из них неизвестное x 11 , мы получим уравнение-тождество 0=0, которое из системы вычеркивается.
Итак, преобразование системы (2.1) свелось к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (2.2).
Остальные уравнения остаются неизменными. Система приняла вид (2.3)
В системе (2.3) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного x 11 [она входит в первое уравнение системы (2.3)]. В системе (2.3) имеется m+n-1 уравнений, выделенный базис содержит m+n-1 неизвестных, а, следовательно, и ранг системы (2.1) r=m+n-1.
Для решения транспортной задачи необходимо кроме запасов и потребностей знать также и тарифы C ij , т. е. стоимость перевозки единицы груза с базы Ai потребителю Bj .
Совокупность тарифов C ij также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:
|
Пункты Отправления |
Пункты назначения |
Запасы |
||||||
|
… |
||||||||
|
… |
||||||||
|
… |
||||||||
|
… |
… |
… |
… |
… |
… |
|||
|
… |
||||||||
|
Потребности |
… |
или |
||||||
Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных x ij : (2.4)
Требуется в области допустимых решений системы уравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4).
Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен m+n-1 то среди всех mn неизвестных выделяется m+n-1 базисных неизвестных, а остальные (m-n)*(n-1) неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем m+n-1 заполненных и (m-n)*(n-1) пустых клеток.
Для контроля надо проверять, равна ли сумма чисел в заполненных клетках каждой строки таблицы перевозок запасу груза на соответствующей базе, а в каждом столбце — потребности заказчика [этим подтверждается, что данный план является решением системы (2.1)].
Замечание 1. Не исключаются здесь и вырожденные случаи, т. е. возможность обращения в нуль одной или нескольких базисных неизвестных. Но эти нули в отличие от нулей свободных неизвестных вписываются в соответствующую клетку, и эта клетка считается заполненной.
Замечание 2. Под величинами C ij , очевидно, не обязательно подразумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, xij выражены в тоннах, а Cij в километрах, то величина S, определяемая формулой (2.4), является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.
1.2 Метод потенциалов
Метод потенциалов является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj — числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij — стоимости перевозки единицы продукции между пунктами Аi и Вj: vj[k] — ui[k] Cij, i 1, …, m; j 1, ., п. Если разность предварительных потенциалов для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается способ получения нового допустимого плана, связанного с меньшими транспортными издержками. За конечное число итераций находится оптимальный план задачи..
1.3 Определение оптимального и опорного плана транспортной задачи
Как и при решении задачи линейного программирования, симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана.
Число переменных Xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах равно n+m. Так как мы предполагаем, что выполняется условие
, то число линейно независимых уравнений равно n+m-1 отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонентов равно в точности n+m-1, то план является не выраженным, а если меньше — то выраженным. Для определения опорного плана существует несколько методов. Три из них — метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля.
При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Обычно рассмотренный метод используется при вычислениях с помощью ЭВМ. Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.
Для определения оптимального плана транспортной задачи можно
использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения и коэффициенты при неизвестных равны единице для определения оптимального плана транспортной задачи разработаны специальные методы. Два из них — метод потенциалов и Венгерский метод.
1.4 Понятие потенциала и цикла
Для перехода от одного базиса к другому при решении транспортной задачи используются так называемые циклы.
Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям:
1. Одно из неизвестных последовательности свободное, а все остальные — базисные.
2. Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.
3. Три последовательных неизвестных не могут находиться в одном столбце или в одной строке.
4. Если, начиная с какого-либо неизвестного, мы будем последовательно переходить от одного к следующему за ним неизвестному то, через несколько шагов мы вернемся к исходному неизвестному.
Второе условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.
Если каждые два соседних неизвестных цикла соединить отрезком прямой, то будет получено геометрическое изображение цикла — замкнутая ломаная из чередующихся горизонтальных и вертикальных звеньев, одна из вершин которой находится в свободной клетке, а остальные — в базисных клетках.
Можно доказать, что для любой свободной клетки таблицы перевозок существует один и только один цикл, содержащий свободное неизвестное из этой клетки, и что число вершин в цикле всегда четно.
Замечание. Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак «+», т. е. тот знак, который ей уже приписан при выходе из нее. Это очень существенное обстоятельство, так как иначе мы пришли бы к противоречию. Безразлично также, в каком направлении обходится цикл при «означивании» вершин.
Если минимальное значение среди базисных неизвестных, стоящих в отрицательных вершинах цикла, принимается не в одной отрицательной вершине, то свободной оставляют только одну из них, а в других клетках с тем же минимальным значением пишут нули. В этом случае новое базисное решение будет вырожденным.
Может случиться, что и само минимальное значение среди чисел в отрицательных клетках равно нулю. Тогда преобразование таблицы перевозок сведется к перестановке этого нуля в свободную клетку. Значения всех неизвестных при этом остаются неизменными, но решения считаются различными, так как различны базисы. Оба решения вырождены.
Описанное выше преобразование таблицы перевозок, в результате которого преобразуется базис, называется пересчетом по циклу.
Неизвестные, не входящие в цикл, этим преобразованием не затрагиваются, их значения остаются неизменными и каждое из них остается либо в группе базисных, либо в группе свободных неизвестных, как и до пересчета.
|
Х11 |
Х12 |
Х13 |
Х14 |
X15 |
||||
|
X= |
Х21 |
Х22 |
Х23 |
Х24 |
X25 |
|||
|
Х31 |
Х32 |
Х33 |
Х34 |
X35 |
||||
|
7 |
9 |
15 |
4 |
18 |
||
|
С= |
13 |
25 |
8 |
15 |
5 |
|
|
5 |
11 |
6 |
20 |
12 |
||
|
1 |
2 |
3 |
4 |
5 |
Запасы |
||
|
1 |
7 |
9 |
15 |
4 |
18 |
200 |
|
|
2 |
13 |
25 |
8 |
15 |
5 |
250 |
|
|
3 |
5 |
11 |
6 |
20 |
12 |
250 |
|
|
Потребности |
80 |
260 |
100 |
140 |
120 |
||
Проверим необходимое и достаточное условие разрешимости задачи.
?a = 200 + 250 + 250 = 700
?b = 80 + 260 + 100 + 140 + 120 = 700
Занесем исходные данные в распределительную таблицу.
|
1 |
2 |
3 |
4 |
5 |
Запасы |
||
|
1 |
7 |
9 |
15 |
4 |
18 |
200 |
|
|
2 |
13 |
25 |
8 |
15 |
5 |
250 |
|
|
3 |
5 |
11 |
6 |
20 |
12 |
250 |
|
|
Потребности |
80 |
260 |
100 |
140 |
120 |
||
Этап I. Поиск первого опорного плана, метод наименьшей стоимости
|
1 |
2 |
3 |
4 |
5 |
Запасы |
||
|
1 |
7 |
9[60] |
15 |
4[140] |
18 |
200 |
|
|
2 |
13 |
25[130] |
8 |
15 |
5[120] |
250 |
|
|
3 |
5[80] |
11[70] |
6[100] |
20 |
12 |
250 |
|
|
Потребности |
80 |
260 |
100 |
140 |
120 |
||
В результате получен первый опорный план, который является допустимым, так как все грузы из баз вывезены, потребность магазинов удовлетворена, а план соответствует системе ограничений транспортной задачи.
невырожденным
Значение целевой функции для этого опорного плана равно:
Этап II. Улучшение опорного плана, предварительные потенциалы
|
v 1 =3 |
v 2 =9 |
v 3 =4 |
v 4 =4 |
v 5 =-11 |
||
|
u 1 =0 |
7 |
9[60] |
15 |
4[140] |
18 |
|
|
u 2 =16 |
13 |
25[130] |
8 |
15 |
5[120] |
|
|
u 3 =2 |
5[80] |
11[70] |
6[100] |
20 |
12 |
|
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + vi > cij
Выбираем максимальную оценку свободной клетки (2;3): 8
Для этого в перспективную клетку (2;3) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1 |
2 |
3 |
4 |
5 |
Запасы |
||
|
1 |
7 |
9[60] |
15 |
4[140] |
18 |
200 |
|
|
2 |
13 |
25[130][-] |
8[+] |
15 |
5[120] |
250 |
|
|
3 |
5[80] |
11[70][+] |
6[100][-] |
20 |
12 |
250 |
|
|
Потребности |
80 |
260 |
100 |
140 |
120 |
||
Цикл приведен в таблице (2,3; 2,2; 3,2; 3,3; ).
Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (3, 3) = 100. Прибавляем 100 к объемам грузов, стоящих в плюсовых клетках и вычитаем 100 из Хij , стоящих в минусовых клетках. В результате получим новый опорный план.
|
1 |
2 |
3 |
4 |
5 |
Запасы |
||
|
1 |
7 |
9[60] |
15 |
4[140] |
18 |
200 |
|
|
2 |
13 |
25[30] |
8[100] |
15 |
5[120] |
250 |
|
|
3 |
5[80] |
11[170] |
6 |
20 |
12 |
250 |
|
|
Потребности |
80 |
260 |
100 |
140 |
120 |
||
предварительные потенциалы
|
v 1 =3 |
v 2 =9 |
v 3 =-8 |
v 4 =4 |
v 5 =-11 |
||
|
u 1 =0 |
7 |
9[60] |
15 |
4[140] |
18 |
|
|
u 2 =16 |
13 |
25[30] |
8[100] |
15 |
5[120] |
|
|
u 3 =2 |
5[80] |
11[170] |
6 |
20 |
12 |
|
Опорный план не является оптимальным, так как существуют оценки свободных клеток, для которых u i + vi > cij
Выбираем максимальную оценку свободной клетки (2;1): 13
Для этого в перспективную клетку (2;1) поставим знак «+», а в остальных вершинах многоугольника чередующиеся знаки «-», «+», «-».
|
1 |
2 |
3 |
4 |
5 |
Запасы |
||
|
1 |
7 |
9[60] |
15 |
4[140] |
18 |
200 |
|
|
2 |
13[+] |
25[30][-] |
8[100] |
15 |
5[120] |
250 |
|
|
3 |
5[80][-] |
11[170][+] |
6 |
20 |
12 |
250 |
|
|
Потребности |
80 |
260 |
100 |
140 |
120 |
||
Цикл приведен в таблице (2,1; 2,2; 3,2; 3,1; ).
Из грузов х ij стоящих в минусовых клетках, выбираем наименьшее, т.е. у = min (2, 2) = 30. Прибавляем 30 к объемам грузов, стоящих в плюсовых клетках и вычитаем 30 из Хij , стоящих в минусовых клетках. В результате получим новый опорный план.
|
1 |
2 |
3 |
4 |
5 |
Запасы |
||
|
1 |
7 |
9[60] |
15 |
4[140] |
18 |
200 |
|
|
2 |
13[30] |
25 |
8[100] |
15 |
5[120] |
250 |
|
|
3 |
5[50] |
11[200] |
6 |
20 |
12 |
250 |
|
|
Потребности |
80 |
260 |
100 |
140 |
120 |
||
предварительные потенциалы
|
v 1 =3 |
v 2 =9 |
v 3 =-2 |
v 4 =4 |
v 5 =-5 |
||
|
u 1 =0 |
7 |
9[60] |
15 |
4[140] |
18 |
|
|
u 2 =10 |
13[30] |
25 |
8[100] |
15 |
5[120] |
|
|
u 3 =2 |
5[50] |
11[200] |
6 |
20 |
12 |
|
Опорный план является оптимальным, так все оценки свободных клеток удовлетворяют условию u i + vi <= cij .
Минимальные затраты составят:
F(x) = 9*60 + 4*140 + 13*30 + 8*100 + 5*120 + 5*50 + 11*200 = 5340
2.3 Решение транспортной задачи при помощи табличного редактора Excel, Заключение
Таким образом “транспортная задача” это задача линейного программирования, которая может быть решена при помощи симплекс-метода, однако, из-за своеобразия матриц системы ограничений, решается при помощи методов, разработанных специально для задач данного вида. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Применение данных методов на примере конкретной задачи наглядно продемонстрировало рациональность их использования в данном случае.
Кроме того, задача была решена при помощи табличного редактора Excel, который продемонстрировал способность автоматизировать процесс решения данных задач, что в свою очередь существенно облегчает работу человека.
Список литературы
[Электронный ресурс]//URL: https://jret.ru/kursovaya/transportnyie-zadachi-2/
1 Беклемишев Д.В. Курс аналитической геометрии и линейной алгебры: 9- е изд., перераб. М.: Физматлит,2011. 376 с.
2 Ефимов П.В. Краткий курс аналитической геометрии: Учебник. 13-е изд., стереотип. М.: Физ-матлит,2003.240с.
3 Бермаит А.Ф., Арамаиович И.Г. Краткий курс математического анализа: Учебник. 10-е изд., стереотип. СПб.: «Лань», 2012. 736 с.
4 Пискунов П.С. Дифференциальное и интегральное счисления: Учеб. пособие для втузов. В 2 т. М.: Иитеграл-Пресс, 2004. Т. 1: 416 с; Т. 2:544 с.
5 Щипачев B.C. Основы высшей математики. 4-е изд., стереотип. М.: Высш. шк., 2001.479 с.
6 Демидович Б.П., Кудрявцев В.А. Краткий курс высшей математики: Учеб. пособие для вузов. М.: Астрель,2011.656с.
7 Фихтенгольц Г.М. Основы математического анализа. В 2 т. 7-е изд. М.: Физматлит, 2002. Т. 1: 416 с; Т. 2: 440 с.
8 Матвеев П.М. Методы интегрирования обыкновенных дифференциальных уравнений: Учеб. пособие. 5-е изд., доп. СПб.: «Лань», 2010. 832 с.
