Курсовой проект - Транспортная задача по критериям времени и стоимости. Вариант 3.5
Подождите немного. Документ загружается.
Министерство образования и науки Российской Федерации
Федеральное агентство по образованию
ИРКУТСКИЙ ГОСУДАРСТВЕННЫЙ ТЕХНИЧЕСКИЙ УНИВЕРСИТЕТ
Кафедра Автоматизированных систем
Допускаю к защите
Руководитель_____________________________
_____________________________
И.О. Фамилия
ТРАНСПОРТНАЯ ЗАДАЧА ПО КРИТЕРИЯМ СТОИМОСТИ И ВРЕМЕНИ
наименование темы
ПОЯСНИТЕЛЬНАЯ ЗАПИСКА
к курсовому проекту по дисциплине
Теория Принятия Решений
Вариант 3.5
Курсовой проект защищен
с оценкой ____________
Иркутск 2010 г.
Выполнил студент группы АСУ-06-1
шифр группы подпись И.О. Фамилия
Нормоконтролер
подпись И.О. Фамилия
Содержание
1.Постановка задачи........................................................................................3
2.Обоснование математической модели.......................................................4
3.Краткие сведения о методе решения задачи..............................................5
3.1.Метод северо-западного угла...................................................................5
3.2.Метод потенциалов...................................................................................6
3.3.Вариант метода потенциалов, при дополнительных условиях,
вводимых последовательно в процессе решения задачи.........................................8
4.Проверка достоверности полученных результатов..................................9
5.Алгоритм решения задачи.........................................................................10
6.Листинг фрагмента программы, реализующего алгоритм решения
задачи..........................................................................................................................11
7.Руководство пользователя.........................................................................19
7.1.Системные требования...........................................................................19
7.2.Описание возможностей.........................................................................19
7.3.Основное окно программы.....................................................................20
7.4.Главное меню программы......................................................................20
7.5.Использование.........................................................................................21
7.5.1.Ввод данных и результаты работы.....................................................21
7.5.2.Использование инженерного режима.................................................24
8.Решение задачи курсовой работы на ПЭВМ по исходным данным
индивидуального варианта.......................................................................................25
9.Список использованной литературы........................................................28
2
1. Постановка задачи
Имеется
m
пунктов отправления, в каждом из которых сосредоточено
определенное количество единиц однородного продукта, предназначенного к
отправке: в первом пункте имеется
a
1
единиц этого продукта, во втором -
a
2
единиц, в
i−
м пункте
a
i
единиц, и, наконец, в
m−
м пункте
a
m
единиц
продукта. Этот продукт следует доставить в
n
пунктов назначения
(потребления), причем в первый пункт назначения следует доставить
b
1
единиц
продукта, во второй -
b
2
единиц, в
j−
й пункт
b
j
единиц, и, наконец, в
n−
й
пункт
b
n
единиц продукта.
Каждый пункт отправления соединен с каждым пунктом назначения
некоторым маршрутом (число таких маршрутов
m×n
), причем известна
удельная стоимость
ij
c
перевозки одной единицы продукта из
i−
го пункта
отправления в
j−
й пункт назначения. Общая стоимость перевозки по любому
маршруту пропорциональна количеству перевозимого продукта. Известно
также время
t
ij
перевозки продукта из
i−
го пункта отправления в
j−
й пункт
назначения, причем это время не зависит от количества перевозимого груза.
Удельные стоимости
c
ij
и время перевозок
t
ij
приведены в таблице,
при этом:
1) на пропускные способности коммуникаций ограничения не
накладываются;
2)
a
i
и
b
j
- количество условных единиц продукта;
3) в верхних отделениях клеток таблицы помещены удельные стоимости
c
ij
в рублях, а в нижних - время перевозок
t
ij
в часах.
Таблица 4
B
j
A
i
B
1
B
2
B
3
B
4
B
5
B
6
B
7
B
8
a
i
A
1
9
6
18
9
16
3
2
1
3
7
16
4
11
10
15
3
180
A
2
16
14
5
17
7
16
20
19
21
8
2
11
7
19
14
3
140
A
3
36
22
7
11
10
12
19
23
3
6
9
18
17
11
10
29
50
A
4
2
1
12
10
19
9
16
13
6
10
12
14
20
4
8
3
150
A
5
15
13
16
17
3
10
11
15
6
23
11
5
18
8
20
23
80
A
6
7
33
3
13
12
2
6
6
18
8
5
8
8
20
20
23
80
A
7
21
21
10
9
16
12
21
22
16
3
15
12
11
5
5
24
70
b
j
50 80 10 40 140 110 130 150
Составить план перевозок, при котором весь груз будет доставлен
потребителям в кратчайший срок; определить для этого плана стоимость
перевозок; произвести, если это возможно, дооптимизацию по критерию
стоимости. Первую часть задачи решить, применяя вариант метода
3
потенциалов, при дополнительных условиях, вводимых последовательно в
процесс решения.
Разработанный программный продукт должен обрабатывать числовые
значения из заданного диапазона:
а) количество пунктов отправления может быть или 6, или 7, или 8;
б) количество пунктов отправления может быть или 7, или 8, или 9;
в) количество единиц продукта, предназначенного к отправке может
быть взято из диапазона
50≤а
i
≤190
;
г) количество единиц продукта, которое следует доставить в пункты
назначения может быть взято из диапазона
10≤b
j
≤160
;
д) удельные стоимости могут быть назначены из диапазона
2≤c
ij
≤38
;
е) значения времени перевозок могут быть назначены из диапазона
1≤t
ij
≤35
.
2. Обоснование математической модели
Имеется
m
пунктов производства (
A
1
, A
2
, ... , A
m
) и
n
пунктов
потребления (
B
1
, B
2
,... , B
n
). В пункте
A
i
производится
a
i
единиц
продукта (
i=11m
), а в пункте
B
j
потребляется
b
j
единиц этого же
продукта (
j=11n
).
Пусть
с
ij
- стоимость доставки из
i
-го пункта производства в
j
-ый пункт
потребления (элементы матрицы
C
);
t
ij
- время, которое требуется для перевозки продукта из
i
-го пункта
производства в
j
-ый пункт потребления (элементы матрицы
T
);
x
ij
- количество единиц продукта, которое нужно перевезти из
i
-го
пункта производства в
j
-ый пункт потребления (элементы матрицы
X
).
Необходимо получить такие значения переменных
x
ij
(
i=11 m
,
j=11n
)(то есть составить такой план перевозок), что выполнялись бы
следующие условия:
∑
j=1
n
x
ij
=a
i
, i=11m ;
(1)
∑
i=1
m
x
ij
=b
j
, j=11n
(2)
- и целевая функция
T =max
x
ij
0
t
ij
,i=11m , j=11n
достигала бы минимума.
Условие (1) означает, что из каждого пункта производства должен быть
вывезен весь продукт. Условие (2) означает, что потребности каждого пункта
потребления в этом продукте должны быть удовлетворены.
Целевая функция
T =max
x
ij
0
t
ij
,i=11m , j=11 nmin
указывает на то,
что нам необходимо минимизировать время самой длительной ненулевой
перевозки.
Условия (1) и (2) можно объединить и представить в виде
∑
i=1
m
a
i
=
∑
j=1
n
b
j
.
(3)
4
Условие (3) называется условием баланса и означает, что объем
производства должен быть равен объему потребления. Если данное условие не
выполняется, то транспортная модель в этом случае называется открытой и
транспортная задача не разрешима. Для того, чтобы все-таки решить такую
задачу, её приводят к закрытой модели введением фиктивного пункта
производства
A
m1
с объемом производства
a
m1
=
∑
j=1
n
b
j
−
∑
i=1
m
a
i
(если
∑
i=1
m
a
i
∑
j=1
n
b
j
) или фиктивного пункта потребления
B
n1
с объемом
потребления
b
n1
=
∑
i=1
m
a
i
−
∑
j=1
n
b
j
(если
∑
i=1
m
a
i
∑
j=1
n
b
j
). В первом случае
транспортные издержки и временные затраты
с
m1, j
и
t
m1, j
принимают
равными
M
, где
M ≫c
ij
и M ≫t
ij
,i=11m , j= 1 1n
. Во втором случае
транспортные издержки и временные затраты
с
i , n1
и
t
i , n1
также
принимают равными
M
, где
M ≫c
ij
и M ≫t
ij
,i=11m , j= 11n
. В
найденном оптимальном решении
X
опт
полагают все перевозки из
фиктивного пункта или в него равными нулю, то есть отбрасывают их, и
вычисляют итоговое значение целевой функции используя первоначальные
матрицы
C
и
T
.
Количество единиц товара, перевозимого из пункта производства
A
i
в
пункт потребления
B
j
, не может быть отрицательным, поэтому необходимо
ввести следующее условие:
x
ij
≥0, i=11m , j=11 n.
После того, как будет найдено
X
опт
для целевой функции
T =max
x
ij
0
t
ij
,i=11m , j=11 n
, попытаемся дооптимизировать полученное
решение по критерию стоимости, предварительно заблокировав в матрице
C
те элементы, которым соответствуют элементы матрицы
T
такие, что
t
ij
max
x
ij
0
t
ij
, x
ij
∈
X
опт
. То есть при дооптимизации по критерию стоимости
необходимо избежать увеличения продолжительности самой длительной
перевозки. При этом целевой функцией будет функция
L=
∑
i=1
m
∑
j=1
n
c
ij
⋅x
ij
min
.
3. Краткие сведения о методе решения задачи
3.1. Метод северо-западного угла
Данный метод используется для построения начального опорного плана
транспортной задачи.
Описание алгоритма.
1. Определяют верхний левый элемент матрицы X:
x
11
=min a
1
, b
1
Возможны три случая:
а) если
a
1
b
1
, то
x
11
=a
1
и вся первая строка, начиная со второго
элемента, заполняют нулями;
5
б) если
a
1
b
1
, то
x
11
=b
1
, а все оставшиеся элементы первого столбца
заполняют нулями;
в) если
a
1
=b
1
, то
x
11
=a
1
=b
1
и все оставшиеся элементы первых столбца
и строки заполняют нулями.
На этом один шаг метода заканчивается.
2. Пусть уже проделано k шагов, (k + 1)-й шаг состоит в следующем.
Определяют верхний левый элемент незаполненной части матрицы X.
Пусть это элемент
x
λ
μ
λμ=k 2
,
причем
x
λμ
=min a
λ
k
, b
μ
k
,
где
a
λ
k
=a
λ
−
∑
j=1
μ−1
x
λj
b
μ
k
=b
μ
−
∑
i=1
λ−1
x
iμ
Если
a
λ
k
b
μ
k
то заполняем нулями
λ
-ю строку, начиная с (
μ1
)-го
элемента. В противном случае заполняем нулями оставшуюся часть
μ
-ro
столбца.
3.2. Метод потенциалов
Метод потенциалов позволяет, исходя из некоторого опорного плана,
построить за конечное число итераций решение Т-задачи.
Общая схема метода. В данном начальном опорном плане перевозок
каждому пункту ставят в соответствие некоторое число, называемое его
предварительным потенциалом. Предварительные потенциалы выбирают так,
чтобы их разность для любой пары пунктов
A
i
и
B
j
, связанных основной
коммуникацией, была равна
c
ij
. Если окажется, что разность
предварительных потенциалов для всех других коммуникаций не превосходит
c
ij
, то данный план перевозок – оптимальное решение задачи. В противном
случае указывают способ улучшения текущего плана Т-задачи.
Описание алгоритма метода потенциалов. Алгоритм складывается из
предварительного этапа и конечного числа однотипных итераций.
На предварительном этапе строят начальный опорный план и
составляют матрицу
C
1
=∣∣c
ij
−v
j
0
−u
i
0
∣∣, i=11m , j=11n ,
где
v
j
0
, u
i
0
— предварительные потенциалы пунктов
A
i
i=11m
и
B
j
j=11n
.
Предварительный этап. С помощью известного метода (например
северо-западного угла или минимального элемента) определяют начальный
опорный план
X
0
и вычисляют предварительные потенциалы
v
j
0
j=11n , u
i
0
i=11m
.
Вычисление предварительных потенциалов производят так. По
найденному опорному плану
X
0
строят схему перевозок Т-задачи из
основных коммуникаций плана. Основные коммуникации
P
ij
плана
6
X
0
=∣x
ij
0
∣
- это те, которым отвечают базисные компоненты плана, т.е.
коммуникации для которых
x
ij
0
0
. Далее образуют следующие множества:
J
1
- множество индексов всех пунктов
B
j
, которые связаны с пунктом
A
1
основными коммуникациями;
I
1
- множество индексов тех пунктов
A
i
, которые связаны основными коммуникациями с множеством
J
1
;
J
2
– множество пунктов
B
j
, которые связаны основными коммуникациями с
множеством
I
1
и т.д. Образование таких множеств
I
k
продолжаем до тех
пор, пока не получим пустое множество.
Поскольку на выполнение условий оптимальности оказывают влияние
лишь разности
v
j
−u
i
, то за начало отсчета (нуль) можно принять потенциал
любого из пунктов.
Полагаем для определенности
u
1
0
=0
и вычислим систему
потенциалов относительно
A
1
. Тогда
v
j
0
=c
1j
u
1
0
=c
1j
, где
j∈J
1
. Затем
по значениям
v
j
0
j∈ J
1
определяем потенциалы пунктов
A
i
i ∈I
1
:
u
i
0
=v
j
0
−c
ij
j ∈J
1,
i∈I
1
.
Аналогично вычисляем потенциалы
v
j
0
j∈ J
2
:
v
j
0
=c
ij
u
i
0
(для
i∈I
1
) и т.д. После того как потенциалы всех пунктов найдены, строим
матрицу
C
1
=∣∣c
ij
−v
j
0
−u
i
0
∣∣, i=11m , j=11n.
Очевидно, позиции матрицы
C
1
, отвечающие базисным элементам
плана
X
0
, будут заняты нулями. Если матрица
C
1
не содержит
отрицательных элементов, то
X
0
– оптимальный план. В противном случае
X
0
– неоптимальный план, который может быть улучшен. Тогда переходим
к выполнению однотипных итераций.
(k+1)-я итерация. Каждая итерация, кроме первой, где отсутствует
первый этап, состоит из двух этапов. Предположим, что уже проведено k
итераций (k=1,2,…), в результате которых получен план
X
k
и
вспомогательная матрицу
C
k
. Цель (k+1)-й итерации - построение матрицы
C
k 1
, а также либо установление оптимальности плана
X
k
, либо
нахождение более экономичного плана
X
k 1
.
Первый этап. Вычисляют матрицу
C
k 1
. Преобразвание матрицы
C
k
в матрицу
C
k 1
состоит в следующем. Выбирают наибольший по
модулю отрицательный элемент
C
k
. Пусть это элемент
c
k
=
k
k
0
.
Тогда вычеркивают (или выделяют) строку
, в которой он содержится.
Просматривают эту строку и отыскивают множество существенных его
элементов.
X
k
-существенными элементами называют те элементы
c
ij
k
=0
,
которые отвечают базисным элементам плана
X
k
, т.е. для которых
x
ij
k
0
.
Вычеркивают столбцы, которые содержат эти элементы. Далее просматривают
вычеркнутые столбцы и ищут в них новые существенные элементы, которые
лежат в строках отличных от уже вычеркнутых ранее. Если такие элементы
имеются, то вычеркивают строки, в которых они содержатся. Процесс
выделения продолжают до тех пор, пока очередное множество новых
существенных элементов не окажется пустым. Поскольку каждые строка и
7
столбец не могут быть выделены дважды, то весь процесс заканчивается не
более чем за l =m+ n – 1 шагов. Далее строят матрицу
C
k 1
. Для этого
величину
k
прибавляют ко всем элементам выделенных строк и вычитают
из элементов всех выделенных столбцов матрицы
C
k
. При этом все
существенные элементы матрицы
C
k
остаются равными нулю, а кроме того,
в нуль превращается и элемент
c
.
Если все элементы матрицы
C
k 1
окажутся неотрицательными, то
X
k
– оптимальный план, и на этом процесс заканчивается. В противном
случае переходят ко второму этапу.
Второй этап. Цель этого этапа – построить более экономичный план
X
k 1
. Выбирают наибольший по модулю отрицательный элемент матрицы
C
k 1
. Пусть это элемент
c
i
0
j
0
k 1
=
k 1
0
. Строят цепочку из
положительных элементов плана, которая замыкается на
x
i
0
j
0
. После того,
как цепочка построена, в ней находят минимальный нечетный по порядку
следования элемент:
k1
= min
0≤S
x
i
j
1
k
.
Прибавляют
k1
ко всем четным элементам (по порядку следования)
цепочки и к элементу
x
i
0
j
0
и вычитают
k1
из всех нечетных элементов.
Остальные элементы
X
k
оставляют без изменения.
Новый план
X
k 1
построен. Он является базисным, так как число его
ненулевых элементов не изменилось.
Пусть
L
k
– транспортные издержки, отвечающие плану
X
k
. Тогда
новое значение целевой функции, отвечающее плану
X
k 1
, находят по
соотношению
L
k1
=L
k
k1
⋅
k1
Так как
k1
0 и
k 1
0 , то L
k1
L
k
. Поэтому
X
k 1
–
улучшенный опорный план.
Затем производят аналогично (k+2)-ю итерацию.
3.3. Вариант метода потенциалов, при дополнительных условиях,
вводимых последовательно в процессе решения задачи
Описание алгоритма.
1-й этап.
Шаг 1. Имеется опорный план
X
0
и матрица временных затрат
T
. В
матрице
T =∣∣t
ij
∣∣
отмечаем все элементы, соответствующие
x
ij
0
плана
X
0
,
и находим среди них наибольший, который обозначим
t
'
, т.е.
t
'
=max {t
ij
}
для
всех
x
ij
0
.
Шаг 2. Все элементы матрицы
T
, которым соответствуют
t
ij
≥t
'
блокируем, то есть заменяем реальные значения
t
ij
на произвольно большое
число
M >> max{t
ij
}.
Получим матрицу
T
1
.
Шаг 3. Для матрицы
T
1
ищем, используя метод потенциалов,
оптимальное решение
X
опт
1
, минимизирующее функцию
T =
∑
i=1
m
∑
j=1
n
t
ij
⋅x
ij
.
8
i-й этап (i >1).
Шаг 1. Если в найденном на предыдущем этапе опорном плане
X
опт
i−1
есть ненулевые перевозки, которые соответствуют заблокированным
элементам матрицы
T
1
, то решение найденное на предыдущем, (i-1)-ом,
этапе является оптимальным. Иначе в матрице
T
i−1
=∣∣t
ij
∣∣
отмечаем все
элементы, соответствующие
x
ij
0
плана
X
опт
i−1
, и находим среди них
наибольший, который обозначим
t
'
, т.е.
t
'
=max {t
ij
}
для всех
x
ij
0
.
Шаг 2. Все элементы матрицы
T
i−1
, которым соответствуют
t
ij
≥t
'
блокируем, то есть заменяем реальные значения
t
ij
на произвольно большое
число
M >> max{t
ij
}.
Получим матрицу
T
i
.
Шаг 3. Для матрицы
T
i
ищем, используя метод потенциалов,
оптимальное решение
X
опт
i
, минимизирующее функцию
T =
∑
i=1
m
∑
j=1
n
t
ij
⋅x
ij
.
4. Проверка достоверности полученных результатов.
В общем случае проверка результатов, полученных после выполнения
очередной итерации, осуществляется следующим образом:
1) вычисляются значения
L
k1
1
=L
k
k1
⋅
k1
и
L
k1
2
=
∑
i=1
m
∑
j=1
n
c
ij
⋅x
ij
k1
,
где
L
k1
1
,
L
k1
2
- значения целевой функции на текущей итерации,
вычисленные разными способами;
L
k
- значение целевой функции на предыдущей итерации
итерации;
k1
- количество товара разгружаемой перевозки;
k1
- минимальное отрицательное значение матрицы
C
k 1
;
x
ij
k1
- элементы плана перевозок, полученного на текущей итерации;
с
ij
- элементы матрицы материальных затрат (временных).
2) Если
L
k1
1
=L
k1
2
, то программа приступает к выполнению
следующей итерации. В противном случае программа выдает сообщение об
ошибке.
Также в программе есть «инженерный режим», используя который можно
посмотреть результаты вычислений после каждой итерации.
9
5. Алгоритм решения задачи.
1. Проверка выполнения условия баланса.
2. Если условие баланса не выполняется, то вводим фиктивный пункт
потребления или производства.
3. Построение опорного плана.
4. Устранение вырожденности в полученном опорном плане.
5. Поиск наибольшего времени перевозок среди существующих в
опорном плане.
6. Блокировка элементов матрицы временных затрат, которые больше
максимального времени перевозок, найденного на 4-м или 10-м этапе.
7. Вычисление потенциалов.
8. Вычисление оценочной матрицы.
9. Построение нового плана по полученной оценочной матрице. Во время
построения также осуществляется проверка на вырожденность получаемого
плана.
10. Выполнение следующих итераций метода потенциалов. Получение
оптимального плана.
11. Если в полученном решении существуют перевозки на
заблокированных на 5-м этапе местах, то происходит переход к 11 этапу. Иначе
осуществляется поиск наибольшего времени среди существующих в
полученном плане перевозок и переход к 5-му этапу.
12. Полученный план дооптимизируется по критерию стоимости.
10