Выбор оптимальной схемы доставки грузов

Курсовая работа.

на тему: " Выбор оптимальной схемы доставки грузов" .

Содержание.

• Введение
• Исходные данные транспортной задачи
• 1. Решение транспортной задачи методом Фогеля
• 2. Решение транспортной задачи методом минимального элемента в матрице
• 3. Решение транспортной задачи методом потенциалов
• 4. Распределительная задача
• 5. Метод анализа разностей себестоимости
• 6. Метод эквивалентов
• 7. Решение распределительной задачи методом обобщённых потенциалов
• Заключение
• Список литературы

Имеется три пункта добычи ПГС: i = 1, 2, 3 с объёмами добычи Q = (Q₁, Q₂, Q₃) тыс. тонн. Требуется составить план перевозок добываемой ПГС четырём клиентам: j = 1, 2, 3, 4 c объемами спроса Q = (В₁, В₂, В₃, В₄) тыс. тонн так, чтобы сформировать участки грузовой работы, отвечающие минимальной общей стоимости доставки.

При этом матрица удельной стоимости доставки С:

Матрица расстояний между пунктами L:

Исходные данные транспортной задачи.

Имеется три пункта добычи ПГС: i=1, 2, 3 с объёмами добычи Q=(48, 32, 40) тыс. тонн. Требуется составить план перевозок ПГС четырём клиентам: j=1, 2, 3, 4 c объемами спроса Q=(29, 33, 28, 30) тыс. тонн так, чтобы сформировать участки грузовой работы, отвечающие минимальной общей стоимости доставки.

При этом матрица удельной стоимости доставки С:

Матрица расстояний между пунктами L:

ЭММ транспортной задачи.

1. За критерий эффективности принимаем минимальную общую стоимость доставки.

2. Целевая функция:

;

3. Ограничения:

4. Дополнительные условия: — количество груза, перевозимого от i-го поставщика j-му потребителю.

1. Решение транспортной задачи методом Фогеля.

транспортный расходы груз себестоимость.

Алгоритм:.

1. Формируется матрица из величин а_i, в_j, с_ij.

2. Анализируется значение оценочных величин в каждой строке и каждом столбце.

3. Находится разница между двумя минимальными значениями, если и двумя максимальными, если этих величин по каждой строке и каждому столбцу. Заносится в дополнительный столбец и дополнительную строку.

4. Из всех разностей в дополнительной строке и столбце находится максимальная и рассматривается строка и столбец к которым она принадлежит.

5. В них находится минимальное значение оценочной величины, если и максимальное, если .

6. Клетка соответствующая этому значению загружается первой из условия.

.

7. Из рассмотрения исключается столбец или строка, где ресурсы исчерпаны.

8. Алгоритм повторяется без учёта исключённых столбцов и строк до исчерпания всех ресурсов.

9. Проверяются ограничения задачи и вычисляются значения целевой функции.

Все полученные Х_j подставляются в систему ограничений, тем самым вариант решений проверяется на допустимость. Все выражения системы ограничений должны оказаться верными. Далее рассчитывается значение целевой функции.

Проверка ограничений:

По поставщикам По потребителям.

Целевая функция:

у.е.

2. Решение транспортной задачи методом минимального элемента в матрице.

Алгоритм:.

1. Рассматриваются значения оценочной величины С_ij всей матрицы и выбирается минимум, если, максимум, если .

2. Соответствующий элемент загружается из стандартного условия.

.

3. Из рассмотрения исключается столбец или строк, где ресурсы исчерпаны.

4. Алгоритм повторяется без учёта исключённых столбцов и строк до исчерпания всех ресурсов.

5. Вариант решения проверяется на допустимость т рассчитывается значение целевой функции.

Проверка ограничений:

По поставщикам По потребителям.

Целевая функция:

у.е.

3. Решение транспортной задачи методом потенциалов.

Алгоритм:.

1. Составляется начально допустимый вариант решения (можно любым приближённым методом или любым известным способом, например способ северо-западного угла).

2. Вариант проверяется на не вырожденность. Оптимальный вариант находится среди невырождённых вариантов. Количество базисных клеток должно равняться.

.

Для базисного элемента ;

Для свободных и небазисных ;

Если вариант решения вырожденный, то от вырожденности избавляются (например при помощи заведения значащего нуля).

3. Рассчитывается потенциалы по базисным клеткам.

;

где — потенциал i-ой строки,.

— потенциал j-го столбца.

4. Рассчитываются характеристики для каждой свободной слетки, где Хij=0 по формуле.

;

Характеристика означает величину экономии ресурсов на единицу груза, полученную в результате перераспределения ресурсов в данную свободную клетку, поэтому может выступать в качестве дополнительного критерия оптимальности.

5. Вариант решения проверяется на оптимальность. Для оптимального варианта, если для всех i, j; если для всех i, j.

6. Если вариант не является оптимальным находится максимальный элемент не оптимальности плана.

7. На основании максимального элемента не оптимальности строится контур перераспределения ресурсов.

Правила построения контура.

1. Все углы контура прямые.

2. Одна вершина находится в клетке с максимальным элементом не оптимальности, все другие в базисных клетках.

8. Вершины контура последовательно разделяются на загружаемые и разгружаемые. В клетки с максимальным элементом загружаемая вершина.

9. Находится минимальный элемент контура перераспределения ресурсов кА минимум Х_ij в разгружаемых клетках.

10. Строится матрица следующей итерации Х_ij в которой остаются прежними, если не принадлежали контуру перераспределения.

;

.

11. Алгоритм повторяется до получения оптимального варианта решения.

12. На каждой итерации вариант решения проверяется на допустимость и рассчитывается значение целевой функции. Для двух соседних итераций разница между целевыми функциями равна максимальному элементу не отрицательности умноженному на минимальный элемент контура перераспределения.

Рассмотрим пример варианта решения которого были получены ранее и в качестве начально допустимого варианта выберем план, полученный методом минимального элемента в матрице, так как при имеет наименьшую целевую функцию.

Рассчитываем потенциалы:

клетка 21:

;

клетка 24:

;

клетка 14:

;

клетка 12:

;

клетка 34:

;

клетка 33:

;

Рассчитаем характеристики для свободных клеток:

максимальный элемент неоптимальности плана при.

Данный вариант решения не является оптимальным, т.к. присутствует положительная характеристика при .

На основании максимального элемента не оптимальности строим контур перераспределения ресурсов.

Рассчитываем потенциалы:

клетка 21:

;

клетка 11:

;

клетка 12:

;

клетка 24:

;

клетка 34:

;

клетка 14:

;

у.е.

Данный вариант решения является оптимальным, так как для всех i и j; F=Fopt.

у.е.

Результаты решения транспортной задачи занесём в таблицу.

4. Распределительная задача.

Исходные данные.

По сформированным участкам грузовой работы расставить наличное количество флота трех типов так, чтобы эксплуатационные расходы оказались при этом наименьшими.

Для работы с клиентами порт располагает флотом трёх типов Ф₁, Ф₂, Ф₃ в количестве.

;

.

Имеются матрицы эксплуатационных расходов по одному за расчётный период Э и провозной способности различных типов флота по участкам работы :

Имеются участки грузовой работы с грузооборотом:

А=(60; 240; 21,6; 152,1; 196; 27).

ЭММ распределительной задачи:.

1. Критерий эффективности — минимальные эксплуатационные расходы.

2. Целевая функция:

.

где Х_ij — количество i-го типа флота, работающего на j-м участке.

Система ограничений:

По флоту:

По грузообороту:

Дополнительные условия:

5. Метод анализа разностей себестоимости.

Алгоритм:.

1. В каждой клетке матрицы рассчитывается величина себестоимости перевозок .

2. Достраиваются дополнительные столбцы и строки, в которые заносятся разности между двумя минимальными значениями себестоимости соответственно по строчкам и столбцам.

3. Из всех значений в дополнительных столбце и строке выбирается максимум.

4. В строке или столбце находится минимум значение себестоимости и эта клетка загружается первая.

5. Из рассмотрения исключается столбец или строка, где ресурсы исчерпаны.

6. Алгоритм повторяется до исчерпания ресурсов.

Проверка ограничений:

По флоту:

По грузообороту:

6. Метод эквивалентов.

Алгоритм:.

1. Выбираем базисный тип флота, для которого на всех или большинстве участков работы наименьшая провозная способность, ему присваивается эквивалент .

2. Рассчитываются эквиваленты всех других типов флота на каждом участке работы по формуле.

— эквивалент i-го типа флота, работающего на j-м участке.

3. К матрице достраиваются дополнительные столбцы и строки. В каждом дополнительном столбце находится разница между двумя максимальными эквивалентами, по каждой строке, в каждой дополнительной строчке — между двумя максимальными эквивалентами по столбику.

4. Из значений в каждой дополнительной строке и столбце выбирается максимальной и рассматривается соответствующая строка или столбец.

5. Выбирается клетка с максимальным эквивалентом и загружается первой.

6. Из рассмотрения исключается столбец и строка, где ресурсы исчерпаны.

7. Алгоритм повторяется до исчерпания всех ресурсов.

Проверка ограничений:

По флоту:

По грузообороту:

7. Решение распределительной задачи методом обобщённых потенциалов.

Метод является не универсальным, пригоден только для решения распределительной задачи, точный.

Алгоритм:.

1. Составить начально допустимый вариант решения (можно, например, способ северо-западного угла или любым приближённым методом).

2. План проверяется на не вырожденность. Количество базисных клеток.

3. Рассчитываются потенциалы и по базисным клеткам.

4. Для свободных клеток рассчитываются характеристики.

5. Вариант решения проверяется на не оптимальность подобно транспортной задаче.

6. Находится максимальный элемент не оптимальности плана подобно транспортной задаче.

7. Строится контур перераспределения ресурсов.

8. Минимальный элемент контура находится по более сложной схеме, чем в транспортной задаче. Для этого сначала составляются выражения для перераспределения ресурсов. Выражение соответствующее разгружаемым клеткам приравнивается к нулю. Решаются полученные уравнения и выбирается минимальное значение из всех решений. Если максимальный элемент не оптимальности лежит не в резервном столбце перераспределение начинаем по столбику, если в резервном — по строчке.

9. Строится следующая таблица на основе измененного вариант решения. Для этого минимальный элемент контура подставляется во все решения для перераспределения ресурсов. Базисные клетки, не затронутые контуром, остаются прежними.

10. Алгоритм повторяется до получения оптимального варианта. На каждой итерации необходимо проверять вариант решения на допустимость и рассчитывать значение целевой функции.

КЛ.12:

.

КЛ.32:

.

КЛ.31:

.

КЛ.34:

.

КЛ.35:

.

КЛ.24:

.

КЛ.23:

.

КЛ.26:

.

КЛ.1Р:

.

max элемент неоптимальности плана.

Расчет потенцеалов.

КЛ.12:

.

КЛ.1р:

.

КЛ.2р:

.

КЛ.26:

.

КЛ.24:

.

КЛ.23:

.

КЛ.34:

.

КЛ.35:

.

КЛ.31:

.

Расчет характеристики свободных клеток.

Проверка ограничений:

По флоту:

По грузообороту:

у.е.

Данный вариант решения является оптимальным, так как для всех i и j; F=Fopt.

у.е.

Заключение.

На первом участке необходимо поставить третий тип флота в количестве 6.74 судов.

На втором участке: первый тип флота — 24 судов.

На третьем участке: второй тип флота — 1.52 судов.

На четвертом участке: второй тип флота — 10,37 судов и третий тип флота — 1,3 судов.

На пятом участке: третий тип флота — 14,96 судов.

На шестом участке: второй тип флота — 1,96 судов.

В резерве остались неиспользованными суда первого типа флота Ф 1 в количестве 12,23; суда второго типа флота Ф 2 в количестве 1,15.

При этом эксплуатационные расходы составили 587,766 тыс. руб., а стоимость перевозок — 453,8 тыс. руб.

1. Горшенкова Л. Г. Методические указания по выполнению курсовой работы по дисциплине «Экономико-математические методы и моделирование «Тема: «Выбор оптимальной схемы доставки грузов» .-Новосибирск: НГАВТ, 2011.-26с.