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

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

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

 

Содержание

 

Введение

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

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

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

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

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

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

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

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

Заключение

Список литературы

 

Введение

 

Имеется три пункта добычи ПГС: 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. Ограничения:

 

 

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

 

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

Алгоритм:

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

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

 

.

 

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

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

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

 

 

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

По поставщикам

По потребителям

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

у.е.

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

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

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

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

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

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

 

;

.

 

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

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

 

 

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

 

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

 клетка 21:

;

клетка 24:

;

клетка 14:

;

клетка 12:

;

клетка 34:

;

клетка 33:

;

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

-

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

 

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

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

 

 

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

 клетка 21:

;

клетка 11:

;

клетка 12:

;

клетка 24:

;

клетка 34:

;

клетка 14:

;

 у.е.

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

у.е.

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

 

Пункт добычи	Клиент	Количество перевозок, тыс. т	Расстояние перевозок, км *10-2	Грузооборот, млн. ткм	Стоимость перевозок, у.е.
Д 1	В 1	12	50	60	51,6
Д 1	В 2	40	60	240	144
Д 2	В 1	9	24	21,6	28,8
Д 2	В 4	39	39	152,1	117
Д 3	В 3	28	70	196	89,6
Д 3	В 4	6	45	27	22,8
				Итого:	453,8

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

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

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

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

 

;

.

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

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

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

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

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

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

 

,

 

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

 

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

По флоту:

 

 

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

 

 

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

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

Алгоритм:

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

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

 

 

 

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

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

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

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

 

 

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

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

 

 

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

По флоту:

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

 

Заключение

 

На первом участке необходимо поставить третий тип флота в количестве 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с.

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

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

 

Содержание

 

Введение

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

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

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

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

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

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

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

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

Заключение

Список литературы

 

Введение

 

Имеется три пункта добычи ПГС: 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. Ограничения:

 

 

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

 

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

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

Алгоритм:

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

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

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

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

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

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

 

.

 

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

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

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

 

 

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

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

По поставщикам

По потребителям

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

 у.е.