Автор работы: Пользователь скрыл имя, 29 Ноября 2013 в 16:40, курсовая работа
С помощью методов линейного программирования решается большое количество экстремальных задач, связанных с экономикой. Одной из основных задач, решаемых с помощью линейного программирования, является транспортная задача, которая имеет целью минимизировать грузооборот товаров широкого потребления при их доставке от производителя к потребителю.
Введение…………………………………………………………………………2
Глава 1. Линейное программирование…………………….………………..3
1.1 История зарождения и создания линейного программирования…………3
1.2 Задача линейного программирования. Основные задачи…………………7
Глава 2. Транспортная задача……………………………………..……….11
2.1 Общая постановка, цели, задачи. Основные типы, виды моделей............11
2.2 Математическая модель транспортной задачи……………………………16
Глава 3. Решение транспортной задачи по пути развоза своей продукции компании «Coca-Colа» по г.Бишкек………………………………………..21
3.1 Описание компании «Coca-Cola»………………………………………….21
3.2 Решение транспортной задачи методом программирования.…………….23
Заключение…………………………………………………………………….37
Список использованной литературы………………………………………..39
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
Для каждого нулевого элемента рассчитаем значение , равное сумме наименьшего элемента i строки и наименьшего элемента j столбца.
i j |
1 |
2 |
3 |
4 |
6 |
|
2 |
0(1) |
M |
0(0) |
4 |
9 |
0 |
3 |
1 |
0(4) |
M |
0(0) |
5 |
0 |
4 |
1 |
4 |
0(0) |
M |
0(0) |
0 |
5 |
M |
4 |
1 |
1 |
0(1) |
1 |
7 |
5 |
8 |
5 |
0(5) |
M |
5 |
1 |
4 |
0 |
0 |
0 |
Наибольшая сумма констант приведения равна 5 для ребра (7,4), следовательно, множество разбивается на два подмножества (7,4) и (7*,4*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(7*,4*) = 36 + 5 = 51
Удалим из матрицы строку 7 и столбец 4, в которой присвоим элементу (4,6) значение бесконечности (М), чтобы избежать преждевременного замыкания контура (для исключения образования негамильтонова цикла), так как изначально мы взяли дугу (7,4) как самый кратчайший путь 7-6-4 (между вершинами 7 и 4 не было прямой связи).
В результате получим другую сокращенную матрицу (4 x 4), которая подлежит операции приведения.
ij |
1 |
2 |
3 |
6 |
|
2 |
0 |
M |
0 |
9 |
0 |
3 |
1 |
0 |
M |
5 |
0 |
4 |
1 |
4 |
0 |
M |
0 |
5 |
M |
4 |
1 |
0 |
0 |
0 |
0 |
0 |
0 |
0 |
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0+0 = 0
Нижняя граница подмножества (7,4) равна:
H(7,4) = 46 + 0 = 46
46 < 51
Поскольку нижняя граница этого подмножества (7,4) меньше, чем подмножества (7*,4*), то ребро (7,4) включаем в маршрут.
Шаг №4
Найдем минимальные элементы в каждой строке и в столбце новой матрицы и сразу вычтем их из остальных элементов строки и столбцов.
Получим матрицу представленную ниже.
ij |
1 |
2 |
3 |
6 |
|||||
2 |
0 |
M |
0 |
9 |
|||||
3 |
1 |
0 |
M |
5 |
|||||
4 |
1 |
4 |
0 |
M |
|||||
5 |
M |
4 |
1 |
0 |
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
Для каждого нулевого элемента рассчитаем значение , равное сумме наименьшего элемента i строки и наименьшего элемента j столбца.
ij |
1 |
2 |
3 |
6 |
||||||
2 |
0(1) |
M |
0(0) |
9 |
0 |
|||||
3 |
1 |
0(5) |
M |
5 |
1 |
|||||
4 |
1 |
4 |
0(1) |
M |
1 |
|||||
5 |
M |
4 |
1 |
0(6) |
1 |
|||||
1 |
4 |
0 |
5 |
Наибольшая сумма констант приведения равна 6 для ребра (5,6), следовательно, множество разбивается на два подмножества (5,6) и (5*,6*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(5*,6*) = 46 + 6 = 52
Удалим из матрицы строку 5 и столбец 6. В результате получим другую сокращенную матрицу (3 x 3), которая подлежит операции приведения.
ij |
1 |
2 |
3 |
|||||
2 |
0 |
M |
0 |
0 |
||||
3 |
1 |
0 |
M |
0 |
||||
4 |
1 |
4 |
0 |
0 |
||||
0 |
0 |
0 |
0 |
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0+0 = 0
Нижняя граница подмножества (5,6) равна:
H(5,6) = 46 + 0 = 46
46 < 52
Поскольку нижняя граница этого подмножества (5,6) меньше, чем подмножества (5*,6*), то ребро (5,6) включаем в маршрут.
Шаг №5
Найдем минимальные элементы в каждой строке и в столбце новой матрицы и сразу вычтем их из остальных элементов строки и столбцов.
Получим матрицу представленную ниже.
ij |
1 |
2 |
3 |
||||
2 |
0 |
M |
0 |
||||
3 |
1 |
0 |
M |
||||
4 |
1 |
4 |
0 |
Определяем ребро ветвления и разобьем все множество маршрутов относительно этого ребра на два подмножества (i,j) и (i*,j*).
Для каждого нулевого элемента рассчитаем значение , равное сумме наименьшего элемента i строки и наименьшего элемента j столбца.
ij |
1 |
2 |
3 |
||||||
2 |
0(1) |
M |
0(0) |
0 |
|||||
3 |
1 |
0(5) |
M |
1 |
|||||
4 |
1 |
4 |
0(1) |
1 |
|||||
1 |
4 |
0 |
Наибольшая сумма констант приведения равна 5 для ребра (3,2), следовательно, множество разбивается на два подмножества (3,2) и (3*,2*).
Нижняя граница гамильтоновых циклов этого подмножества:
H(3*,2*) = 46 + 5 = 51
Удалим из матрицы строку 3 и столбец 2. В результате получим другую сокращенную матрицу (2 x 2), которая подлежит операции приведения.
ij |
1 |
3 |
|||||
2 |
0 |
0 |
0 |
||||
4 |
1 |
0 |
0 |
||||
0 |
0 |
0 |
Сумма констант приведения сокращенной матрицы:
∑di + ∑dj = 0+0 = 0
Нижняя граница подмножества (3,2) равна:
H(3,2) = 46 + 0 = 46
46 < 51
Поскольку нижняя граница этого подмножества (3,2) меньше, чем подмножества (3*,2*), то ребро (3,2) включаем в маршрут.
Так как (3,2) включен в маршрут, то заменим элемент (2,3) на бесконечность (М), чтобы избежать преждевременного замыкания контура (для исключения образования негамильтонова цикла).
И поскольку изначально мы представили дугу (4,1) как путь 4-5-1 и в пункте 5 мы уже были (согласно гамильтонову пути в каждом пункте мы должны побывать дин и только один раз, исключением является в данной задаче ребро (6,7), так как уже говорилось у пункта 7 есть прямая связь только с пунктом 6), включив в маршрут ребро (1,5), то заменим ребро (4,1) на бесконечность (М).
В результате получим следующую преобразованную матрицу.
ij |
1 |
3 | ||
2 |
0 |
М | ||
4 |
М |
0 |
Исходя из этой таблицы, в маршрут включаются также ребра (2,1) и (4,3).
Итак, маршрут включает в себя
дуги: (6,7), (1,5), (7,4), (5,6), (3,2), (2,1) и (4,3). Вспомним,
что в ходе разветвления алгоритма у нас
присутствовали и другие варианты дальнейшего
разбиения подмножества, которые также
способны дать и другой вариант оптимального
маршрута, но я не буду их рассматривать,
так как мною уже получен оптимальный
маршрут, расстояние которого все равно
будет равен расстоянию того маршрута,
если бы я рассмотрела другой вариант
дальнейшего разбиения подмножества.
То есть наш оптимальный маршрут таков:
1 – 5 – 6 – 7 – 6 – 4 – 3 – 2 – 1 длиною в 46
км. Если перейти в начало задачи и рассматривать
другой вариант дальнейшего разбиения
подмножества, то мы бы получили такой
оптимальный маршрут: 1 – 2 – 3 – 4 – 6 –
7 – 6 – 5 – 1 такой же длины в 46 км.
Заключение
В курсовой работе изложены основные подходы и методы решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.д.
Алгоритм и методы решения
транспортной задачи могут быть использованы
при решении некоторых
деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;
Список использованной литературы
Информация о работе Методы линейного программирования для решения транспортной задачи