![](/user_photo/_userpic.png)
5463
.pdfМинистерство образования и науки Российской Федерации Федеральное агентство по образованию
Государственное образовательное учреждение высшего профессионального образования
«Хабаровская государственная академия экономики и права»
В.Н. Захарова
Оптимизация транспортно-экономических связей
Рекомендовано Дальневосточным региональным учебно-методическим центром (ДВ РУМЦ) в качестве учебного пособия
для студентов экономических специальностей вузов региона
Хабаровск 2005
2
ББК В З-38
Захарова В.Н. Оптимизация транспортно-экономических связей: учеб. пособ. – Хабаровск: РИЦ ХГАЭП, 2005. – 104 с.
Рецензенты: канд.физ.-мат.наук, доцент кафедры прикладной математики ДВГУПС Е.Н. Ломакина; канд.физ.-мат.наук, старший научный сотрудник института экономических исследований ДВО РАН С.А. Ланец.
В учебном пособии рассмотрены различные проблемы оптимизации транспортно-экономических связей, постановки задач, их математические модели, алгоритмы решения. Даны решения типовых задач и задания для самостоятельного решения.
©В.Н. Захарова, 2005
©Хабаровская государственная академия экономики и права, 2005
3
Оглавление
Введение Глава 1. Классическая транспортная задача по критерию минимума издержек
Глава 2. Обобщенная транспортная задача (λ – задача) Глава 3. Транспортная задача с запретами Глава 4. Транспортная задача по критерию времени
Глава 5. Транспортные задачи с учетом времени и издержек Глава 6. Транспортные задачи по перевозке неоднородного взаимозаменяемого груза Глава 7. Транспортные задачи с ограничениями по пропускной способности
Глава 8. Двухэтапные производственно-транспортные задачи Глава 9. Задача оптимального размещения производства Глава 10. Транспортная задача в сетевой постановке Глава 11. Задача коммивояжера
Глава 12. Решение транспортной задачи на персональном компьютере с использованием ППП QM for Windows (Transportation)
4
Введение
Транспортные расходы при производстве и доставке продукции до потребителя являются значительной составляющей цены на продукцию, поэтому их снижение является одной из важнейших задач производства и реализации продукции.
Задача минимизации суммарных транспортных затрат по доставке продукции от поставщиков до потребителей решается по алгоритму метода потенциалов для классической транспортной задачи. В этой задаче предполагается, что перевозится однородная продукция, одним видом транспорта, по любому маршруту.
На практике условия задач значительно усложняются. Перевозимая продукция редко бывает однородной, перевозится различными видами транспорта, многие маршруты могут быть закрыты. В некоторых случаях доставка продукции осуществляется не непосредственно потребителю, а поэтапно – через переработку, склады, посредника и пр. Таким образом, возникают задачи по перевозке неоднородного груза, с запретами, многоэтапные.
Во многих задачах критерием оптимальности является минимальное время реализации доставки груза. Реализация решений задач по критерию минимума времени требует больших затрат, поэтому возникает задача минимизации затрат при минимальном времени реализации, то есть задача
сучетом времени и издержек.
Вданном учебном пособии рассмотрены математические постановки и алгоритмы решения:
-классической транспортной задачи;
-обобщенной транспортной задачи (λ – задачи);
-задачи с запретами;
-задачи по перевозке неоднородного взаимозаменяемого груза;
-двухэтапной производственно-транспортной задачи;
-задачи с ограничениями по пропускной способности;
-задачи оптимального размещения производства;
-транспортной задачи в сетевой постановке;
-транспортной задачи по критерию времени;
-транспортной задачи с учетом времени и издержек;
-задачи коммивояжера.
Вкаждой главе предложены вопросы для самопроверки и задачи для самостоятельного решения.
Вданном пособии рассматривается решение классической транспортной и некоторых других задач на компьютере с применением
ППП QM for Windows.
![](/html/65386/291/html_4eBfXnPzhI.XcGP/htmlconvd-aOKVW65x1.jpg)
5
Глава 1. Классическая транспортная задача по критерию минимума издержек
Постановка задачи. На m станциях отправления A1 , A2 ,..., Ai, ..., Am имеется
a1 , a2 ,..., ai ,..., am |
единиц однородного груза. Этот груз необходимо |
||||||||||
перевезти в n пунктов потребления |
B1 , B2 ,..., B j ,..., Bn |
в количествах, |
|||||||||
соответственно |
равных b1 , b2 ,..., b j ,..., Bn . Известны |
величины |
Сij , |
||||||||
характеризующие затраты по перевозке единицы груза из пункта |
Ai в |
||||||||||
пункт B j . Требуется определить оптимальный план |
перевозок, |
при |
|||||||||
котором минимизируются общие суммарные затраты на перевозки. |
|
||||||||||
Математическая модель задачи |
|
|
|
|
|
|
|
|
|
||
Пусть xij – искомый объем перевозки груза из пункта |
Ai в пункт B j , |
||||||||||
тогда |
|
|
|
|
|
|
|
|
|
|
|
|
n |
|
|
|
|
|
|
|
|
|
(1.1) |
|
xij |
ai , |
i |
1, m |
|
||||||
|
j |
1 |
|
|
|
|
|
|
|
|
|
|
m |
|
|
|
|
|
|
|
(1.2) |
||
|
xij |
bi , |
j |
1, n |
|
||||||
|
i 1 |
|
|
|
|
|
|
|
|
|
|
|
|
|
xij |
0 |
|
|
|
|
|
|
|
|
z |
|
Cij |
xij |
|
|
min |
|
(1.3) |
||
|
|
i |
j |
|
|
|
|
|
|
|
|
Система ограничений (1.1) характеризует ограничения по ресурсам, (1.2) – ограничения по потребностям. Задача решается в таблице
|
Потребители |
В1 |
|
B2 |
|
Bj |
|
Bn |
Постав- |
|
10 |
b2 |
... |
bj |
... |
bn |
|
щики |
|
|
|
|
||||
A1 |
|
|
C11 |
C12 |
|
C1j |
|
C1n |
|
a1 |
x11 |
|
x12 |
|
xij |
|
x1n |
A2 |
|
|
C21 |
C22 |
|
C2j |
|
C2n |
|
a2 |
x21 |
|
x22 |
|
x2j |
|
x2n |
Ai |
ai |
xi1 |
Ci1 |
Ci2 |
|
Cij |
|
C2n |
|
|
xi2 |
|
x2j |
|
x2n |
||
Am |
am |
xm1 |
Cm1 |
Cm2 |
|
Cmj |
|
Cmn |
|
|
xm2 |
|
xmj |
|
xmn |
||
|
|
|
|
|
|
|
|
|
![](/html/65386/291/html_4eBfXnPzhI.XcGP/htmlconvd-aOKVW66x1.jpg)
6
Если для задачи (1.1) – (1.3) выполнено условие баланса
ai |
b j , |
(1.4) |
i |
j |
|
то транспортная задача называется закрытой.
Если условие баланса не выполняется, то задача называется открытой и приводится к закрытой введением фиктивного поставщика с мощностью
am 1 |
b j |
ai (если |
|
ai |
b j ) |
или |
фиктивного потребителя со |
j |
|
i |
|
i |
j |
|
|
спросом |
bn 1 |
ai |
|
b j |
(если |
ai |
b j ). |
|
|
i |
j |
|
i |
|
j |
Для фиктивного поставщика или потребителя Сij = 0.
Приведем необходимые для решения формулировки основных теорем транспортной задачи.
Теорема 1. (О разрешимости транспортной задачи). Транспортная задача при условии выполнения баланса всегда имеет оптимальное решение.
Система ограничений математической модели (1.1) – (1.2) имеет (m + n) уравнений и m · n неизвестных.
Доказано, что одно из уравнений является линейной комбинацией остальных, то есть является линейно зависимой и число базисных переменных системы равно (m + n -1).
Теорема 2. (О числе базисных переменных). Система ограничений транспортной задачи (1.1) – (1.3) содержит (m +n -1) линейно независимых уравнений.
Из этой теоремы следует, что невырожденный план транспортной задачи (все базисные переменные xij отличны от нуля) содержит (m + n –
1) базисных переменных, которым соответствуют занятые клетки в таблице решения.
Как и в симплексном методе при решении транспортной задачи необходимо найти первоначальный опорный план задачи. Рассмотрим на условном примере один из распространенных методов построения первоначального опорного решения (плана), учитывающих затраты на перевозки.
Метод наименьшего элемента матрицы С
Строительный песок добывается в четырех карьерах и доставляется на пять строительных площадок. Производительность карьеров за день составляет А1 – 100, А2 – 120, А3 – 80, А4 – 120 т песка. Потребность строительных площадок в песке В1 – 60, В2 – 100, В3 – 95, В4 – 125, В5 – 40 т. Затраты на добычу и доставку песка из карьеров до строительных площадок представлены матрицей
![](/html/65386/291/html_4eBfXnPzhI.XcGP/htmlconvd-aOKVW67x1.jpg)
7
70 50 30 20 10
С
30 40 80 40 50
20 20 50 60 90
10 30 60 50 80
Найти оптимальную схему прикрепления строительных площадок к карьерам, при которой суммарные затраты на добычу и доставку сырья будут минимальными.
Решение. Карьеры представим поставщиками, строительные площадки
– потребителями. Проверим условие баланса
аi |
100 120 |
80 120 |
420, |
b j |
60 100 95 |
125 40 |
420. |
Условие баланса выполняется, следовательно, задача закрытого типа. Данные задачи представим в таблице
60 |
100 |
95 |
125 |
40 |
|
|
70 |
50 |
30 |
20 |
10 |
100 |
|
|
|
|
|
|
30 |
40 |
80 |
40 |
50 |
120 |
|
|
|
|
|
|
|
|
|
|
|
|
20 |
20 |
50 |
60 |
90 |
80 |
|
|
|
|
|
|
|
|
|
|
|
|
10 |
30 |
60 |
50 |
80 |
120 |
|
|
|
|
|
|
|
|
|
|
|
Первой в таблице заполняется клетка (i,j) с наименьшим Сij по правилу xij min ai , b j . Затем заполняются клетки в порядке возрастания Сij с
учетом предыдущих поставок. В нашем случае наименьший тариф имеют клетки (1,5) и (4,1). Выбираем любую, например (4,1), и ставим в неё
поставку |
x41 |
min 120,60 |
60. |
Следующей заполняем клетку (1,5) |
поставкой x15 |
min 100,40 |
40. Затем выбираем любую клетку с Сij = 20 |
||
и заносим в нее соответствующую поставку. |
||||
Например, |
x32 |
min 80,100 |
80, |
|
|
x14 |
min 100 40,125 |
60 . |
Следующими заполняются клетки в порядке возрастания Сij с учетом предыдущих поставок:
![](/html/65386/291/html_4eBfXnPzhI.XcGP/htmlconvd-aOKVW68x1.jpg)
|
|
|
|
|
8 |
|
|
|
|
|
|
|
x42 |
min 120 |
60,100 |
80 20; |
|
||||
|
|
x24 |
min 120,125 |
60 |
65; |
|
||||
|
|
x43 |
min 120 |
60 |
20,95 |
40; |
|
|||
|
|
x23 |
min 120 |
65,95 |
40 |
50. |
|
|||
Получим первоначальный опорный план Х1 задачи (табл. 1). |
||||||||||
План Х1 |
|
|
|
|
|
|
|
|
|
Таблица 1 |
|
60 |
100 |
95 |
|
125 |
|
40 |
ui |
||
|
70 |
50 |
|
30 |
|
|
|
20 |
10 |
|
100 |
|
|
+ |
|
- |
60 |
|
40 |
u1=0 |
|
|
60 |
20 |
-30 |
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|
|||
120 |
30 |
40 |
- |
80 |
|
+ |
40 |
50 |
|
|
0 |
-10 |
55 |
|
65 |
|
20 |
u2=20 |
|||
|
|
|
||||||||
|
|
|
|
|
|
|
|
|||
80 |
20 |
20 |
|
50 |
|
|
60 |
90 |
u3=-10 |
|
|
80 |
|
|
|
|
|
|
|
||
|
20 |
0 |
|
50 |
|
|
90 |
|
||
|
|
|
|
|
|
|||||
120 |
10 |
30 |
|
60 |
|
|
50 |
80 |
u4=0 |
|
60 |
20 |
40 |
|
|
|
|
|
|
||
|
|
30 |
|
|
70 |
|
||||
|
|
|
|
|
|
|
|
|||
Vj |
V1=10 |
V2=30 |
V3=60 |
|
V4=20 |
V5=10 |
|
|
Для этого плана значение целевой функции |
|
|
|
|
||||||
z1 |
20 60 |
10 |
40 |
80 50 |
40 65 |
20 80 |
30 |
20 |
60 |
40 |
12800 |
Число базисных переменных задачи равно |
m |
n |
1 |
4 |
5 8. Из этого |
следует, что число заполненных клеток в таблице равно 8. Для решения задачи используем один из распространенных методов решения метод
потенциалов. |
|
Этот метод основывается на следующей теореме. |
|
Теорема 3. (О потенциалах). Если план Х * (x |
* ) является |
ij |
оптимальным планом транспортной задачи (1.1) – (1.3), то ему соответствует система из (m + n) чисел ui* и v*j , удовлетворяющим условиям
1) |
ui* |
v*j |
Cij , если |
xij* |
0 ; |
(1.5) |
2) |
ui* |
v*j |
Cij , если |
xij* |
0 . |
(1.6) |
![](/html/65386/291/html_4eBfXnPzhI.XcGP/htmlconvd-aOKVW69x1.jpg)
9
Из условия (1.6) следует, что в оптимальном плане для свободных клеток величины Еij Cij ui* v*j 0 . Числа Еij называются характеристиками свободных клеток i, j .
Экономический смысл Еij : величина характеристики свободной клетки i, jпоказывает, на сколько изменится значение целевой функции Z при перемещении в клетку i, j
одной единицы груза.
Если в оптимальной плане для свободных клеток Еij = 0, то
оптимальный план не единственный. Рассмотрим алгоритм метода потенциалов.
1.Проверяем условие баланса для задачи. Если оно не выполняется, приводим задачу закрытой.
2.Находим первоначальный опорный план Х1 задачи по методу минимального элемента матрицы С, вычисляем для него Z и число
занятых |
клеток в таблице, которых должно быть (m + n – 1). |
|||
В случае, если занятых клеток окажется меньше, чем (m + n – 1), то |
||||
необходимо в свободные клетки записать нужное число поставок, но |
||||
так, чтобы не замкнуть контур. |
|
|||
3. Для |
занятых |
клеток составляем систему |
уравнений из условия |
|
ui |
v j |
Cij . |
Система содержит (m + n – |
1) линейно независимых |
уравнений и (m + n) неизвестных, поэтому она имеет множество
решений. Одну из неизвестных задаем произвольно, например u1 |
0. |
|||
Остальные ui и v j |
находим, решая систему уравнений. |
|
||
4. Для |
свободных |
клеток |
вычисляем характеристики по формуле |
|
Eij |
Cij ui v j |
. Если |
все характеристики неотрицательны, |
то |
полученный план оптимальный. Если имеется хотя бы одна отрицательная характеристика, то переходим к лучшему опорному решению. Для этого выбираем свободную клетку с наименьшей отрицательной характеристикой и строим для нее контур.
Для контура характерно следующее:
а) контур – это замкнутая ломаная линия, звенья которой взаимно перпендикулярны;
б) все вершины контура лежат в занятых клетках кроме одной, для которой он строится;
в) число вершин в контуре четное; г) контур для каждой свободной клетки единственный;
д) контур может пересекать занятые клетки.
Помечаем знаком |
плюс свободную клетку в контуре, а далее знаки по |
|
вершинам контура |
чередуем. Определяем величину поставки, |
|
перемещаемой по контуру, из условия |
min xij (минимальная поставка в |
|
|
|
" " |
вершинах со знаком минус).
![](/html/65386/291/html_4eBfXnPzhI.XcGP/htmlconvd-aOKVW610x1.jpg)
10
Затем величину θ прибавляем к поставкам в вершинах со знаком плюс и отнимаем от поставок со знаком минус. Получаем новый опорный план
Х2. |
Для |
него изменение |
целевой функции |
составит |
z1 |
Eij |
, а |
||||
z2 |
z1 |
Eij . |
|
|
|
|
|
|
|
|
|
|
Процесс решения задачи продолжается до выполнения условия |
||||||||||
оптимальности (все Eij |
0 для свободных клеток). |
|
|
|
|
||||||
|
Решим задачи по методу потенциалов, взяв за первоначальный |
||||||||||
опорный план Х1 из табл. 1 |
|
|
|
|
|
|
|
|
|||
|
В табл. 1 число занятых клеток должно быть m n |
1 |
4 5 |
1 |
8 . |
||||||
Определим потенциалы |
поставщиков |
v j . Для |
этого |
составим |
систему |
||||||
уравнений из условия ui |
v j |
Cij |
для занятых клеток. |
|
|
|
|
||||
|
|
|
|
u1 |
v4 |
20 |
|
|
|
|
|
|
|
|
|
u1 |
v5 |
10 |
|
|
|
|
|
|
|
|
|
u2 |
v3 |
80 |
|
|
|
|
|
|
|
|
|
u2 |
v4 |
40 |
|
|
|
|
|
|
|
|
|
u3 |
v2 |
80 |
|
|
|
|
|
|
|
|
|
u4 |
v1 |
10 |
|
|
|
|
|
|
|
|
|
u4 |
v2 |
30 |
|
|
|
|
|
|
|
|
|
u4 |
v3 |
60 |
|
|
|
|
|
Система уравнений содержит 8 линейно независимых уравнений и 9 неизвестных, поэтому одно из неизвестных задаем произвольно, остальные рассчитываем из системы уравнений.
Полагаем u4 0 (по наибольшему числу занятых клеток в четвертой
строке). Получаем |
|
|
||
u1 |
0, |
v1 |
10, |
|
v2 |
30, |
|||
u2 |
20, |
|||
v3 |
60, |
|||
u3 |
10, |
|||
v4 |
20, |
|||
u4 |
0. |
|||
v5 |
10. |
|||
|
|
Для свободных клеток вычисляем характеристики Еij Cij (ui v j ) и записываем их в левых нижних углах.