Маслов А.В., Григорьева А.А. Математическое моделирование в экономике и управлении: Учебное пособие. Гриф УМО
Подождите немного. Документ загружается.
Составим математическую модель задачи. Так как от
i
-го
поставщика к
j
-му потребителю запланировано к перевозке
ij
x
единиц
груза, то стоимость перевозки составит
ijij
xc
. Стоимость всего плана
выразится двойной суммой
m
i
n
j
ijij
xcZ
1 1
.
Систему ограничений получаем из следующих условий задачи:
а) все грузы должны быть вывезены, т.е.
n
j
iij
ax
1
(
mi ,,2,1
)
(уравнения получаются из строк таблицы);
б) все потребности должны быть удовлетворены, т.е.
n
i
jij
bx
1
(
nj ,,2,1
) (уравнения получаются из столбцов таблицы).
Таким образом, математическая модель транспортной задачи имеет
следующий вид:
Найти наименьшее значение линейной функции
m
i
n
j
ijij
xcZ
1 1
при
ограничениях
).,1;,1(,0
,,...,2,1,
,,...,2,1,
1
1
njmix
njbx
miax
ij
m
i
jij
n
j
iij
В рассмотренной модели может быть два случая: когда суммарные
запасы равны суммарным потребностям, т.е.
m
i
n
j
ji
ba
1 1
,
и когда не
равны. В первом случае транспортная модель задачи называется
закрытой, во втором – открытой.
Когда суммарные запасы не равны суммарным потребностям,
может быть два случая:
а) суммарные запасы превышают суммарные потребности
m
i
n
j
ji
ba
1 1
;
б) суммарные потребности превышают суммарные запасы
m
i
n
j
ji
ba
1 1
.
Линейная функция одинакова в обоих случаях, изменяется только
вид системы ограничений.
В случае (а) ограничения имеют вид:
81
1
2
3
5
4
6
).,1;,1(0
;,1,
;,1,
1
1
njmix
njbx
miax
ij
m
i
jij
n
j
iij
В случае (б) ограничения имеют вид:
).,1;,1(,0
;,1,
;,1,
1
1
njmix
njbx
miax
ij
m
i
jij
n
j
iij
Открытая модель приводится к закрытой модели.
В случае (а), когда суммарные запасы превышают суммарные
потребности, вводится фиктивный потребитель
,
1n
B
потребности
которого
m
i
n
j
jin
bab
1 1
1
.
В случае (б), когда суммарные потребности
превышают суммарные запасы, вводится фиктивный поставщик
,
1m
A
запасы которого
n
j
m
i
ijm
aba
1 1
1
.
Стоимость перевозки единицы груза как до фиктивного
потребителя, так и стоимость перевозки единицы груза от фиктивного
поставщика полагают равными 0, т.к. в обоих случаях груз не
перевозится. После преобразований задача принимает вид закрытой
модели. Так что, прежде чем решать какую-нибудь транспортную
задачу, необходимо сначала проверить, к какому виду модели она
принадлежит, только после этого решать.
Существует следующая теорема.
Теорема 6.1. Любая транспортная задача, у которой суммарный
объём запасов совпадает с суммарным объёмом потребностей, имеет
решение.
Особенности транспортной задачи по сравнению с общей задачей
линейного программирования вытекают из её математической модели:
целевая функция имеет несколько другой вид (двойная сумма), вид
коэффициентов
ij
a
специфический (там, где будет перевозка,
коэффициент будет равен 1, в остальных - 0, т.е. в каждом столбце
будет не более двух единиц, остальные элементы - нули). Методы
решения транспортной задачи в силу этих особенностей отличны от
методов решения задачи линейного программирования. Их мы
рассмотрим позже.
Ранее представленная станковая задача полностью попадает под
рассматриваемую модель транспортной задачи, если принять другой
экономический смысл переменных. В самом деле, пусть на предприятии
имеется m видов станков, максимальное время работы которых
соответственно равно a
i
(i=
m,1
) часов. Каждый из станков может
выполнять n видов операций. Суммарное время выполнения каждой
операции соответственно равно b
j
(j=
n,1
) часов. Известна
82
1
2
3
5
4
6
производительность c
ij
i-го станка при выполнении j-й операции.
Определить, сколько времени и на какой операции нужно использовать
каждый из станков, чтобы обработать максимальное количество
деталей.
Для составления математической модели обозначим через x
ij
(i=
m,1
,j=
n,1
) время, которое i-й станок должен работать на j-й
операции. Тогда количество деталей, обработанных на i-м станке, равно
c
ij
x
ij.
. Количество деталей, обработанных на всех станках, можно
выразить функцией
m
i
n
j
ijij
xcZ
1 1
.
Так как максимально возможное время работы i-го станка
ограничено значением a
i
, то получаем
i
n
j
ij
ax
1
, (
mi ,1
), если
максимальное время работы станков используется полностью, или
n
j
iij
miax
1
),1(,
, если это время используется не полностью.
С другой стороны, время, отведённое на j-ю операцию, равно b
j
часов, поэтому
),1(,
1
njbx
n
j
jij
. Из условия следует, что общее время
работы всех станков должно быть равно сумме максимальных времён
работы всех станков, т.е.
m
i
n
j
m
i
iij
ax
1 1 1
, и времени, необходимому на
выполнение всех операций, т.е.
m
i
n
j
m
i
jij
bx
1 1 1
. Отсюда следует, что
m
i
n
j
ji
ba
1 1
.
Таким образом, необходимо найти максимальное значение
линейной функции
m
i
n
j
ijij
xcZ
1 1
при ограничениях
m
i
jij
n
j
iij
njbx
miax
1
1
),,1(,
),,1(,
).,1;,1(,0 njmix
ij
Для того чтобы решить эту задачу методом потенциалов,
достаточно линейную функцию умножить на
1
, т.е. считать в таблице
матрицы планирования все значения c
ij
отрицательными (в
канонической постановке транспортной задачи целевая функция должна
быть на минимум).
Построение первоначального опорного плана
83
1
2
3
5
4
6
Как и для других задач линейного программирования,
итерационный процесс по отысканию оптимального плана
транспортной задачи начинают с нахождения опорного плана.
Рассмотрим систему ограничений транспортной задачи. Она
содержит
nm
неизвестных и
nm
уравнений, связанных
соотношением
m
i
n
j
ji
ba
1 1
,
т.е., если сложить почленно уравнения
отдельно подсистемы
n
j
iij
ax
1
и отдельно подсистемы
m
i
jij
bx
1
, то
получим два одинаковых уравнения. Наличие в системе ограничений
двух одинаковых уравнений говорит об её линейной зависимости. Если
одно из этих уравнений отбросить, то в общем случае система
ограничений должна содержать
1 nm
линейно независимых
уравнений. Следовательно, опорный план транспортной задачи может
иметь не более
1 nm
отличных от 0 неизвестных или перевозок.
Если в опорном плане число отличных от нуля компонент в
точности равно
1 nm
, то план является невырожденным, а если
меньше – то вырожденным. Таким образом, если каким-либо способом
получен невырожденный опорный план транспортной задачи, то в
матрице (
ij
x
) (
njmi ,1;,1
) значений его компонент положительными
являются только
1 nm
, а остальные равны нулю.
Если условия транспортной задачи и её опорный план записаны в
виде таблицы, то клетки, в которых находятся отличные от нуля
перевозки, называются занятыми, остальные – незанятыми. Занятые
клетки соответствуют базисным неизвестным и для невырожденного
опорного плана их количество равно
1 nm
. Если ограничения
транспортной задачи записаны в виде двух подсистем уравнений, то,
как известно, базисным неизвестным, включённым в опорный план,
соответствует система линейно независимых векторов. Опорность плана
при записи условий транспортной задачи в виде таблицы заключается в
его ацикличности, т.е. в таблице нельзя построить замкнутый цикл, все
вершины которого лежат в занятых клетках.
Циклом называется набор клеток, в котором две и только две
соседние клетки расположены в одном столбце или одной строке
таблицы, причём последняя клетка находится в той же строке или
столбце, что и первая. Построение циклов начинают с какой-либо
занятой клетки и переходят по столбцу (строке) к другой занятой
клетке, в которой делают поворот под прямым углом и движутся по
строке (столбцу) к следующей занятой клетке и т.д., пытаясь
возвратиться к первоначальной клетке (рис. 6.1). Если такой возврат
84
1
2
3
5
4
6
возможен, то получен цикл, и план не является опорным. В противном
случае план является опорным. Клетки, в которых происходит поворот
под прямым углом, определяют вершины цикла.
Для определения опорного первоначального плана существует
несколько методов. Рассмотрим два из них: метод северо-западного
угла и с учётом наименьших затрат.
Сущность этих методов, как и других, состоит в том, что опорный
первоначальный план находят последовательно за
1 mn
шагов, на
каждом из которых в таблице условий задачи заполняют одну клетку,
которая становится занятой. Лучше пояснить каждый метод примером.
Рис.6.1. Возможные виды циклов в матрице планирования
транспортной задачи
В методе северо-западного угла при нахождении опорного
первоначального плана транспортной задачи на каждом шаге
рассматривают первый (сверху) из оставшихся пунктов отправления и
первый (слева) из оставшихся пунктов назначения. Заполнение клеток
таблицы условий начинается с левой верхней клетки для неизвестного
x
11
("северо-западный угол") и заканчивается правой нижней клеткой
для неизвестного x
mn
, т.е. идёт как бы по диагонали таблицы.
Таблица 6.2
Начальные условия примера 6.1 транспортной задачи
Пункты Пункты назначения Запасы
отправления B
1
B
2
B
3
B
4
B
5
A
1
2 3 4 2 4 140
A
2
8 4 1 14 1 180
A
3
9 7 3 7 2 160
Потребности 60 70 120 130 100 80
Пример 6.1. Пусть дана транспортная задача, условия которой
заданы матрицей планирования, представленной в табл. 6.2. Здесь число
пунктов отправления m=3, а число пунктов назначения n=5.
3x5 7x7 4x4
85
1
2
3
5
4
6
Следовательно, опорный план задачи определяется числами, стоящими
в 5+3- -1=7 заполненных клетках. Заполнение таблицы начинаем с
клетки для неизвестного x
11
, несмотря на стоимость перевозки, т.е.
попытаемся удовлетворить потребности первого пункта назначения за
счёт запасов первого пункта отправления.
Так как запасы пункта A
1
больше, чем потребности пункта B
1
,
полагаем x
11
=60, записываем это значение в соответствующей клетке
таблицы и временно исключаем из рассмотрения столбец B
1
, считая при
этом запасы пункта A
1
равными 80. Рассмотрим первые из оставшихся
пунктов отправления A
1
и назначения B
2
. Запасы пункта A
1
больше
потребностей пункта B
2
. Положим x
12
=70, запишем это значение в
соответствующей клетке таблицы и временно исключим из
рассмотрения столбец B
2
. В пункте A
1
запасы считаем равными 10
единицам. Снова рассматриваем первые из оставшихся пунктов
отправления A
1
и назначения B
2
. Потребности пункта B
3
больше
оставшихся запасов пункта A
1
. Положим x
13
=10 и исключим из
рассмотрения строку A
1
. Значение x
13
=10 запишем в соответствующую
клетку таблицы и считаем потребности пункта B
3
равными 110
единицам. Теперь перейдём к заполнению клетки для неизвестного x
23
и
т.д. Через шесть шагов остаётся один пункт отправления A
3
с запасом
груза 100 единиц и один пункт назначения B
5
с потребностью 100
единиц. Соответственно имеется одна свободная клетка, которая и
заполняется, полагая x
35
=100.
В результате получаем опорный план
10060000
07011000
00107060
X
.
Таблица 6.3
Последовательность заполнения клеток матрицы планирования
по методу северо-западного угла в примере 6.1
В
1
В
2
В
3
В
4
В
5
А
1
60
2
70 3 10 4
2 4
140
А
2
8 4
1
110
14
70
1
180
А
3
9 7 3
7
60
2
100
160
Потребности 60 70 120 130 100 480
86
1
2
3
5
4
6
Согласно данному плану перевозок, общая стоимость перевозок
составляет
Опорный ли план получен, узнать можно по выполнению условия:
если, начиная движение от занятой клетки x
11
или какой-то другой
занятой, вернуться в неё, двигаясь только по занятым клеткам и делая
повороты под прямым углом, невозможно. В приведённом примере
план является опорным.
При составлении первоначального опорного плана методом северо-
западного угла стоимость перевозки единицы груза не учитывалась,
поэтому построенный план далёк от оптимального. Если при
составлении опорного плана учитывать стоимость перевозки единицы
груза, то, очевидно, план будет значительно ближе к оптимальному.
Метод минимальной стоимости
Суть метода состоит в том, что из всей таблицы стоимостей
выбирают наименьшую и в клетку, которая ей соответствует, помещают
меньшее из чисел a
i
или b
j
. Затем из рассмотрения исключают либо
строку, соответствующую поставщику, запасы которого полностью
израсходованы, либо столбец, соответствующий потребителю,
потребности которого полностью удовлетворены, либо и строку и
столбец, если израсходованы запасы поставщика и удовлетворены
потребности потребителя. Из оставшейся части таблицы стоимостей
снова выбирают наименьшую стоимость, и процесс распределения
запасов продолжают, пока все запасы не будут распределены, а
потребности удовлетворены.
Составим с помощью этого метода опорный план уже
рассмотренной задачи. Выбираем в таблице наименьшую стоимость (эта
стоимость, помещенная в клетке A
2
B
3
). Помещаем туда
120
единиц.
Исключаем из рассмотрения 3-й столбец и распределим дальше, пока
все запасы не будут распределены, а потребности удовлетворены.
Таблица 6.4
Составление опорного плана по методу наименьшей стоимости
В
1
В
2
В
3
В
4
В
5
Запасы
А
1
60
2
70
3 4
10
2 4
140
А
2
8 4
120
1 14
60
1
180
А
3
9 7 3
120
7
40
2
160
Потребности 60 70 120 130 100 480
2080 (ст.ед.)2·100+70144·103·702·60
Z
+1·110
7·60
87
1
2
3
5
4
6
В результате получаем план: X=(x
11
=60, x
12
=70, x
14
=10, x
23
=120,
x
25
=60, x
34
=120, x
35
=40), остальные переменные равны нулю. План не
содержит циклов и состоит из семи положительных перевозок,
следовательно, является невырожденным опорным планом. Определим
его стоимость:
145024071201601120210370260 Z
(ст.ед.).
Общая стоимость уменьшилась. Этот метод даёт более близкий к
оптимальному план, чем метод северо-западного угла. Ещё существуют
такие методы построения первоначального опорного плана, как метод
двойного предпочтения, метод аппроксимации Фогеля.
Опорный первоначальный план имеется. Теперь для получения
оптимального плана используем метод потенциалов
(модифицированный распределительный метод).
Теорема 6.2. Если план
**
ij
xX
транспортной задачи является
оптимальным, то ему соответствует система из
nm
чисел
*
i
u
и
*
j
v
,
удовлетворяющих условиям
ijji
cvu
**
для
0
*
ij
x
и
ijji
cvu
**
для
),1,,1( 0
*
njmix
ij
.
Числа
*
i
u
и
*
j
v
называются потенциалами соответственно
поставщиков и потребителей.
На основании этой теоремы для того, чтобы первоначальный
опорный план был оптимальным, необходимо выполнение следующих
условий:
а) для каждой занятой клетки сумма потенциалов должна быть
равна стоимости единицы перевозки, стоящей в этой клетке:
;
ijji
cvu
б) для каждой незанятой клетки сумма потенциалов должна быть
меньше или равна стоимости единицы перевозки, стоящей в этой клетке:
ijji
cvu
.
Соотношения
ijji
cvu
представляют собой систему
1 nm
линейных уравнений с
nm
неизвестными. Эта система всегда
совместна, причём одно из неизвестных можно положить равным
любому числу (обычно приравнивают к нулю), и тогда все остальные
неизвестные определятся однозначно.
Если хотя бы одна незанятая клетка не удовлетворяет условию
ijji
cvu
, то опорный план является неоптимальным и его можно
улучшить, вводя в базис вектор, соответствующий клетке, для которой
88
1
2
3
5
4
6
нарушается условие оптимальности (т.е. в клетку надо переместить
некоторое количество единиц груза).
Таким образом, для проверки плана на оптимальность необходимо
сначала построить систему потенциалов.
Рассмотрим алгоритм метода потенциалов и одновременно
проиллюстрируем его применение на опорном плане, полученном в
таблице. Для этого к таблице добавим строку и столбец, в которых
записывают значения потенциалов. Алгоритм метода потенциалов
состоит в следующем:
1. Построение опорного плана методом северо-западного угла или
с учётом наименьших затрат. Этот этап уже выполнен.
2. Построение системы потенциалов. Для этого используем
условие
ijji
cvu
для занятых клеток. Систему потенциалов можно
построить только для невырожденного опорного плана. Для него
систему потенциалов строим следующим образом. Когда опорный план
вырожденный, для устранения этого дополняют количество занятых
клеток до
1 nm
, вводя нулевые перевозки. Клетки, в которые
введены нулевые перевозки, называются фиктивно занятыми.
Целесообразно сделать фиктивно занятой клетку, в которой стоит
наименьшая стоимость, но так, чтобы сохранилась ацикличность.
Фиктивно занятую клетку делаем в той строке или столбце, оценки
(потенциалы) которых неизвестны. После того, как построена система
потенциалов (табл. 6.5), переходим к третьему этапу.
3. Проверка выполнения условия оптимальности для незанятых
клеток. Просматриваем строки таблицы и для каждой незанятой клетки
проверяем выполнение условия
ijji
cvu
. Если это условие для всех
незанятых клеток выполним, то план оптимальный. Для каждой клетки,
в которой не выполняется условие оптимальности, находим величину
разности
0))(
ijijji
cvu
и записываем её значения в левый
нижний угол этой же клетки. Таких клеток две: (2,2) и (3,2). Разности
равны 3 и 1 (табл. 6.5).
4. Выбор клетки, в которую необходимо послать перевозку.
Загрузке подлежит в первую очередь клетка, которая соответствует
ijji
cvu )(max
, т.к. в общей задаче линейного программирования в
базис включается тот вектор (если отождествить занятые клетки с
векторами, составляющими базис, а незанятые – с остальными
векторами системы ограничений), которому соответствует max
jj
cz
. У нас
jij
vuz
. Необходимо определить, сколько единиц
груза должно быть перераспределено.
89
1
2
3
5
4
6
Таблица 6.5
Выполнение первого цикла алгоритма метода потенциалов
Матрица
планирования B
1
B
2
B
3
B
4
B
5
За-
Постав-
щики
v
j
u
i
v
1
=2
v
2
=3 v
3
=-3 v
4
=2 v
5
=-3
пас
ы
A
1
u
1
=0 60
2
70 _
3 4
10 +
2 4
140
A
2
u
2
=4
8
+
4
120
1 14
60 –
1
180
A
3
u
3
=5
9
7 3
120 _
7
40 +
2
160
Потребности 60 70 120 130 100 480
5. Построение цикла и определение величины перераспределения
груза. Для определения количества единиц груза, подлежащих
перераспределению, отмечаем знаком ''+'' незанятую клетку, которую
надо загрузить. Это означает, что клетка присоединяется к занятым
клеткам, т.е. включается в базис. В таблице занятых клеток стало
nm
,
поэтому появляется цикл, все вершины которого, за исключением
клетки, отмеченной ''+'', находятся в занятых клетках, причём этот цикл
единственный. Отыскиваем цикл. Его вид может быть разным (рис. 6.1).
Они могут быть самопересекающимися, но точки пересечения – не
вершины.
Начинаем движение от клетки, отмеченной знаком "+", и, двигаясь
по циклу, поочерёдно проставляем знаки "–", "+" в вершинах цикла.
Затем находим
ijо
xmin
, где
ij
x
– величины перевозок, стоящие в
вершинах цикла, отмеченные знаком "–". У нас это
60
. Величина
о
определяет, сколько единиц груза можно перераспределить по
найденному циклу. Значение
о
записываем в незанятую клетку,
отмеченную знаком "+", двигаясь по циклу, вычитаем
о
из объёмов
перевозок, расположенных в клетках, которые отмечены знаком "–", и
прибавляем к объёмам перевозок, находящимся в клетках, отмеченных
знаком "+". Если
о
соответствует несколько минимальных перевозок,
то при вычитании оставляем в соответствующих клетках нулевые
перевозки в таком количестве, чтобы во вновь полученном опорном
плане занятых клеток было
1 nm
. В результате перераспределения
о
получим новый невырожденный опорный план, который снова
подлежит проверке на оптимальность (табл. 6.6).
Таблица 6.6
Выполнение второго цикла алгоритма метода потенциалов
90
1
2
3
5
4
6