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

1.

Тема лекции № 7. Транспортная задача и методы ее решения
Цель
лекции:
Рассмотреть
транспортную
задачу,
построение
математической модели транспортной задачи, методы решения транспортной
задачи.
Конспект лекции: Содержательная постановка задачи.
Имеется m пунктов производства («поставщиков») некоторого однородного
продукта и n пунктов его потребления («потребители»). Для каждого пункта
производства i=1,n и для каждого пункта потребления
величины:
A i −объем производства в пункте производства i;
j=1,m
заданы
B j − объем потребления в пункте потребления j;
Cij −затраты на перевозку единицы продукта от пункта производства i
до пункта потребления j.
{X }
ij
Требуется определить план
перевозок:
А) не выходящий за пределы производительности поставщиков;
Б) полностью обеспечивающий всех потребителей;
В) дающий минимум суммарных затрат на перевозку.
Предполагается, что суммарное производство и суммарное потребление
могут быть и сбалансированы, и не сбалансированы.
Числовые данные в виде матрицы транспортных затрат m=4, n=3 и
объемов производства в пунктах производства и объемов потребления в
пунктах потребления даны в таблице 7.1.
Таблица 7.1
Поставщики
А1
А2
А3
Объемы
потребления
Потребители
В1
3
1
5
150
В2
5
4
8
120
В3
7
6
12
80
В4
11
3
7
50
Объемы
производства
100
130
170
400
Построение математической модели. Так как от i-й производителя к
j-му потребителю запланировано X ij единиц продукта, то затраты от
перевозки составят
двойной суммой
Cij X ij . Затраты от перевозки всего плана выразятся
m
n
z=∑ ∑ cij x ij ,
i=1 j=1
(7.1)
систему ограничений получаем из следующих условий задачи:
а) все грузы должны быть вывезены, т. е.

2.

m
n
∑ ∑ x ij =ai
i =1 j=1
(7.2)
б) все потребности должны быть удовлетворены, т. е.
m
; (i=1,. .., m),
n
∑ ∑ x ij =b j
i =1 j=1
(7.3)
, ( j=1,...,n), ,
x ij≥0
(7.4)
Таким образом, математическая модель транспортной задачи имеет вид
(7.1)−(7.4). В рассмотренной модели предполагается, что суммарные запасы
равны суммарным потребностям т. е.
m
n
∑ ai= ∑ b j
i=1
j=1
.
Такая модель называется закрытой.
Из построенной математической модели видно, что данная задача
относится к задаче линейного программирования транспортного типа.
Методы решения. Так как это задача линейного программирования, то
ее можно решить классическим методом линейного программирования
симплекс-методом. Однако из-за громоздкости симплексных таблиц,
содержащих m, n неизвестных и большего объема вычислительных работ для
оптимального решения транспортных задач используют специальные
методы. Это венгерский метод, метод потенциалов, сетевые методы и др.
Решение транспортной задачи методом потенциалов состоит из 2-х
этапов:
1 Предварительный этап:
А) составляется предварительный план одним из трех методов:
- метод северо-западного угла;
- метод минимальной стоимости;
- приближенный метод Фогеля;
Б) для полученного плана строится система m+n чисел u1 , .. .,u m ;
v 1 , . .. , v n
выбранных
таких, чтобы выполнялись условия
c ij ;
v j−ui=cij
для всех Х-
u1 , ... ,u m ,
v 1 , . .. , v n исследуется на
В) построенная система
потенциальность (т.е. план Х исследуется на оптимальность).
2. Общий шаг (применяется, если план Х, построенный в предыдущем
шаге, не оптимален, т. е. система u1 ,.. . ,u m ; v 1 , . .., v n не потенциальна)
состоит из следующих трех операций:
'
А) улучшение плана, т. е. замены плана Х новым планом X .
Со стоимостью перевозок, не превышающей стоимости перевозок по
плану Х;

3.

'
Б) построения для плана X (путем исправления системы u1 ,... ,u m ;
v 1 , . .. , v n ) новой системы, u'1 , .. . ,u 'm ; v '1 , . .. , v 'n удовлетворяющей условию
v 'j−u'i=cij
(7.5)
для всех Х-выбранных
c ij ;
'
'
В) исследования построенной системы u1 , .. . ,u m ;
потенциальность.
Перейдем к подробному изложению алгоритма.
Предварительный этап.
v '1 , . .. , v 'n
на
X=‖x ‖
ij
1) составление первоначального плана
методом северозападного угла.
Начинаем с определения элемента x 11 (отсюда и название этого
способа построения первоначального плана «правило северо-западного
'
'
x 1 j=0
угла»), полагая x 11 =min {a1 , b1 } . Если v 1 , . .. , v n , то x 11=a1 и
для j=2,3,…,n. Если a1 > b1 , то x 11=b1 и x i1=0 для i = 2,3,…,m. Если
же a1 =b 1 , то x 11=a1 =b1 и все остальные элементы как первой строки,
так и первого столбца равны нулю. Пусть для определенности a1 <b1
.
Тогда запас груза в первом пункте отправления свелся к нулю, а потребность
b1 −a 1 . Эти данные
первого пункта назначения составляет теперь
отмечаем правее таблицы 5 и под ней.
Таблица 7.2
c11
c12
а1n
a1
a1
0
...
0
0
c21
c22
...
c2n
a2
a2
....
....
...
...
...
...
cm1
cm2
...
cmn
am
am
a
b1
b2
...
bn
i
bj
b1-a1
b2
...
bn
Полагаем затем x 21=min { a2 , b1 −a 1 } . Если a2 <b1 −a1 , то x 21=a2 и все
x 2 j=0 для j=2,..., n ; если a2 >b1−a1 , то x 21=b1−a1 и все x i1=0 для
i=3,...,m ; если же a2 =b 1−a1 , то x 21=a2 =b1 −a1 , а все остальные
элементы 1-го столбца и 2-й строки равны нулю.
Пусть имеет место второй случай. Тогда потребность первого пункта
назначения полностью удовлетворена, а остаток запаса во втором пункте
а2 =b 1−a1 . Эти значения записываются также
отправления составляет
правее таблицы 6 и под ней.
Таблица 7.3

4.

c11
a1
c21
b1-a1
....
c12
0
c22
....
cm1
0
b1
cm2
b2
..
c1n
.
0
...
c2n
a1
0
0
a2
a2
a2-b1+a1
...
...
...
....
am
am
am
...
...
cmn
...
bn
ai
bj
b1-a1
0
bn
bn
x 22=min { a2 −b1 + a1 ; b 2 }
Полагаем затем
и т. д., пока не определим все
элементы xij (i =1,.. ,m; j=1,...,n). Заметим, что каждый элемент x ij был
получен из линейных комбинаций ai и b j с коэффициентами 0,1,-1 и
является
либо
остатком
b2
b2
груза
...
...
в
пункте,
либо
соответствующего пункта назначения. Поэтому, если ai
потребностью
и b j были
первоначально неотрицательными целыми числами, то и первоначальный
план перевозок X | xij ||m,n , полученный по описанному правилу, будет
состоять из целых неотрицательных x ij . Число N положительных перевозок
(т. е. элементов xij > 0 ) в этом плане не превышает m+n-1. Действительно,
таблица содержит (снизу и справа) всего m+n чисел
a , ... , a ; b , ..., b . На каждом шаге заполняется положительным x ij одна
1
m
1
n
клетка таблицы, на месте одного или двух из чисел ai, bj ставятся нули, а на
последнем шаге одновременно на месте am и bn ставятся нули. Следовательно,
всего шагов построения плана( когда на местах всех m+n данных чисел будут
нули) потребуется не более чем m+n-1 и план будет содержать не более чем
m+n-1 положительных x ij . Как нетрудно убедится, полученный набор
клеток не содержит циклов. Если N=m+n-1, то переходим к построению
системы u1,...,um; v1,..,vn. Если же N<m+n - 1(тогда задача называется
вырожденной), то вводим в набор дополнительно m+n-1-N новых клеток с
нулевыми перевозками x ij=0 , но так, чтобы весь набор не содержал
циклов. После этого переходим к построению системы u1, ... , um; v1 , ... , vn.
Приближенный метод Фогеля (ПМФ). Этот метод является
эвристическим и обычно приводит к лучшему первоначальному плану.
На самом же деле ПМФ часто дает оптимальное или близкое к
оптимальному начальное решение.
Алгоритм состоит из следующих шагов.
Шаг 1 . Вычислить разность для каждой строки (столбца), вычитая
наименьший элемент этой строки (столбца) из следующего за ним по
величине элемента той же строки (столбца).
Шаг 2 . Отметить строку или столбец с самой большой разностью,

5.

а если таких несколько, выбрать среди них любую строку или любой
столбец. В отмеченной строке или столбце выбрать переменную с самой
минимальной стоимостью и придать ей наибольшее возможное значение.
Скорректировать объем производства и спрос и вычеркнуть строку или
столбец,
соответствующие
выполненному
ограничению.
Если
ограничения по строке и столбцу выполняются одновременно, то
вычеркнуть либо строку, либо столбец, а оставшемуся столбцу (строке)
приписать нулевой спрос (объем производства).Строка (или столбец) с
нулевым объемом производства (или спросом) не используется в
дальнейших вычислениях (на шаге 3).
Шаг 3 . (а) Если невычеркнутой остается в точности одна строка
или один столбец, то закончить вычисления.
(б) Если остается невычеркнутой только одна строка (столбец) с
положительным объемом производства (спросом), находим ненулевые
значения перевозок в этой строке (столбце), используя метод минимальной
стоимости.
(в) Если всем невычеркнутым строкам и столбцам соответствуют
нулевые объемы производства и величины спроса, найти нулевые
значения перевозок , используя метод минимальной стоимости.
(г) В других случаях вычислить новые значения разностей для
невычеркнутых строк и столбцов и перейти к шагу 2. (Следует
отметить, что строки и столбцы с нулевыми значениями объема
производства и спроса не должны использоваться при вычислении этих
разностей.)
Теорема потенциальности. Для того чтобы некоторый допустимый план
X' = || x' ij ||m,n транспортной задачи был оптимальным , необходимо и
достаточно , чтобы ему соответствовала система из m + n чисел u'1, u'2, ... ,
u'm ; v'1 , v'2 , ... , v'n , удовлетворяющая условиям
vj - ui c ij (i = 1 , ... , m ; j = 1 ,..., n)
(7.6)
и
v j - ui = c ij для всех x' ij >0 (x' ij X') .
(7.7)
Числа u'i , v'j называются потенциалами соответственно пунктов
отправления и назначения , вся их система - потенциальной , а условия
(7.6)-(7.7) - условиями потенциальности системы {u'i , v'j } ; каждое в
отдельности неравенство (равенство) называется условием потенциальности
для соответствующей клетки (i , j) .
Если план X, для которого существует потенциальная система {u'i , v'j},
также назвать потенциальным , то теорема коротко формулируется так : для
оптимальности плана транспортной задачи необходимо и достаточно,
чтобы он был потенциальным . Для доказательства заметим сначала , что
транспортную задачу минимизации целевой функции.
Контрольные вопросы:

6.

1. Дайте содержательную постановку транспортной задачи.
2. Постройте математическую модель транспортной задачи
3. Перечислите методы решения транспортной задачи
4. Теорема потенциальности.
Литература:
1. Акулич И.Л. Математическое программирование в примерах и задачах,
Изд. "Высшая школа" 1986.
2. Бурков В.Н., Кулжабаев Н.М. Активные системы и деловые игры–
Алматы:2000.
3. Бурков В.Н. Основы математической теории активных систем. М.: Наука,
1977.
4.Вентцель Е.С. Исследование операций. Задачи, принципы, методология –
Москва: Наука, 1988
5.Зуховицкий С.И. Авдеева Л.И. Линейное и выпуклое программирование,
Изд. "Наука". Москва 1967.
6.Кулжабаев Н.М. Исследование операции. Учебное пособие. –Алматы:РИК
КАО имени И.Алтынсарина,1999.
7.Кулжабаев Н.М. Муханова Г.С. Системный анализ и исследование
операции.