Реферат: Определение оптимального плана перевозок
👉🏻👉🏻👉🏻 ВСЯ ИНФОРМАЦИЯ ДОСТУПНА ЗДЕСЬ ЖМИТЕ 👈🏻👈🏻👈🏻
ОПРЕДЕЛЕНИЕ ОПТИМАЛЬНОГО ПЛАНА ПЕРЕВОЗОК
1. Познакомиться с общей постановкой транспортной задачи.
2. Решить задачу методом северо-западного угла
3. Решить задачу методом потенциалов
4. Дать анализ результатов расчетов
Пусть в пунктах А 1
, А 2
,…, А
m
производится некоторая однородная продукция. Таким образом, имеется m
поставщиков А
i
,
где =
. Объем производства в пункте А
i
составляет a i
единиц. Величину a i
называют мощностью поставщика, а - суммарной мощностью всех поставщиков. Допустим, что выпускаемая продукция потребляется в пунктах В 1
, В 2
, …, В
n
, причем в пункте В
j
, составляет b j
единиц продукции. Величина b j
называется емкостью (спросом) потребителя В
j
, где . Общий объем потребления (суммарная емкость) составляет .
В практике встречаются два типа транспортных задач.
1. Объем производства совпадает с объемом потребления, то есть
Такой тип задач называется закрытыми транспортными задачами.
2. Объем производства не совпадает с объемом потребления, то есть
Такой тип задач называется закрытыми транспортными задачами.
Рассмотрим принцип решения закрытой транспортной задачи (1 тип).
- от каждого поставщика возможна перевозка к любому потребителю;
- стоимость перевозки единицы продукции от поставщика А
i
к потребителю В
j
известна и составляет C ij
денежных единиц. ( В некоторых случаях вместо стоимости перевозки может быть указано расстояние от А
i
до В
j
.)
Условия задачи могут быть записаны в виде таблицы 1.
В задаче требуется разработать план перевозок, обеспечивающий с наименьшими транспортными затратами запросы всех потребителей при условии, что предложения и спрос будут сбалансированы.
Пусть объем перевозок из пункта А
i
в пункт В j
( от i
– го поставщика к j
– му потребителю) будет равен Х
ij
. Тогда целевая функция будет равна
В то же время должны выполняться условия (ограничения):
В равенствах (2) и (3) имеется m+n уравнений с mn неизвестными, причем одно из них есть следствие других в силу того, что . Следовательно, в равенствах (2) и (3) будет m+n-1 линейно независимых уравнений и каждая программа (план0 перевозок должна содержать не более чем m+n-1 положительных перевозок.
Принимаем условие, что клетки табл. 1. в которых объем перевозок Х
ij
не равен нулю, называть базисными
, а в которых Х
ij
=0 – свободными
. Элементы таблицы перевозок C ij
называть показателями критерия оптимальности
, а совокупность C ij
Х
ij
– планом перевозок
.
Транспортная задача относится к задачам линейного программирования, ее решение может быть осуществлено различными методами, наиболее распространенными из них являются: метод «северо-западного угла», распределенный метод и метод потенциалов.
Решение транспортной задачи методом потенциалов
Метод потенциалов решения транспортной задачи основан на выборе некоторого исходного варианта прикрепления поставщиков к потребителям и последовательном его преобразовании вплоть до получения оптимального варианта.
Рассмотрим применение метода потенциалов на конкретном производственном примере составления оптимального плана перевозок. Пусть имеется три оптовых базы, которые поставляют сырье для пяти производственных предприятий. Условия задачи представлены в табл.2. Себестоимость перевозки сырья представлена в условных единицах.
Требуется найти такой план перевозок, чтобы общая стоимость транспортных затрат была минимальной.
Руководствуясь здравым смыслом, прикрепим поставщиков к потребителям следующим образом.
В клетках, в которых записаны поставки (базисные клетки), показатели критерия оптимальности обведены кружком, чтобы облегчить ориентацию в таблице. Получившийся план перевозок отвечает одному из условий – вся мощность поставщиков (оптовых баз) полностью распределена, весь спрос потребителей (предприятий) полностью удовлетворен.
Z=22 4+38 1+7 3+20 2+8 2+10 4+30 4=363 у.е.
Этот план является допустимым, однако является ли он оптимальным, насколько оправдал себя здравый смысл, утверждать трудно.
При перераспределении поставок составляются цепи, для которых характерны следующие особенности:
1. цепь является замкнутым многоугольником;
2. вершинами цепи являются клетки таблицы, причем одна из вершин –свободная, а все остальные базисные;
3. все углы цепи являются прямыми, каждый отрезок цепи, ограниченный двумя вершинами, принадлежит к одному столбцу или к одной строке таблицы;
4. цепь всегда имеет четное число вершин;
5. отрезки цепи могут проходить через базисные клетки, не являющимися вершинами данной цепи, при этом объемы перевозок в таких клетках не изменяются.
Вершины, в которых поставка при распределении увеличиваются, отмечают плюсом и называют положительными вершинами, а если поставка уменьшается, отмечают минусом и считают отрицательными.
На рисунке 1 представлен пример составления элементарной цепи, где три базисные клетки обозначены кружками, а одна свободная – квадратом. При перераспределении поставок по данной цепи получается следующий результат.
Пусть А 2
будет поставлять 1 т сырья в пункт В 1
, тогда необходимо уменьшить поставки на 1 т из А 1
в В 1
и из А 2
в В 2
и увеличить из А 1
в В 2
, чтобы выполнялось условие равенства запаса сырья в базах и спроса предприятий. Уменьшая или увеличивая поставки, тем самым уменьшаем или увеличиваем значение целевой функции Z
. Цепь дает возможность установить, насколько изменится стоимость транспортировки при записи поставки в 1 т , в ту клетку цепи, которая была свободной.
Рисунок 1. Пример построения цепи к свободной клетке А 2
- В 1
Алгебраическую сумму показателей C ij
в вершинах цепи называем характеристикой цепи.
Следовательно, в представленном примере
Следовательно, изменение поставок по данной цепи на 1 т уменьшает значение Z
на 4 у.е.
Суть метода потенциалов заключается в том, что проверки допустимого плана на оптимальность особым образом определяются числа, называемые «потенциалами», при помощи которых достаточно просто вычисляются характеристики цепей к свободным клеткам. Единственное требование к потенциалам – каждый показатель критерия оптимальности базисной клетки должен быть равен алгебраической сумме потенциалов строки и столбца.
Потенциалы строк и столбцов определяются следующим образом. В табл. 3 произвольно принимается потенциал строки А 1
равным 3 (может быть принято и любое другое число). В строке А 1
находятся две базисные клетки, показатели C ij
, которых равны 4 и 1. Тогда потенциал столбца В 1
равен 4-3=1, а В 2
1 – 3 = – 2. В столбце В 2
находится еще одна базисная клетка, в которой C ij
=3, следовательно, потенциал строки А 2
равен 3 – (–2) =5, тогда потенциалы столбцов В 3
и В 4
равны соответственно 2 – 5 = – 3, строки А 3
= 7 и столбца В 5
= – 3 .
Обозначив потенциалы строк через u i
, потенциалы столбцов v j
, а показатели оптимальности в базисных клетках через C ij
, можно записать
C ij
= u i
+ v j
; u i
= C ij
- v j
; v j
= C ij
- u i
(6)
Характеристики цепей к свободным клеткам обозначим Е
ij
. Зная потенциалы их строк и столбцов,
Е
ij
= C ij
– ( u i
+ v j
) . (7)
Если показатель C ij
меньше алгебраической суммы потенциалов строки и столбца, то характеристика Е
ij
будет отрицательной. Перераспределение поставок по цепи к этой клетке уменьшает целевую функцию на величину характеристики (в расчете на единицу перераспределяемой продукции). Наоборот, если показатель C ij
больше алгебраической суммы потенциалов строки и столбца, то характеристика Е
ij
будет положительной и перераспределение по цепи к этой клетке увеличит значение целевой функции.
Если же характеристик Е
ij
будет равна нулю, то перераспределение поставок по данной цепи не изменит значения целевой функции. Для базисных клеток характеристики равны нулю.
Продолжая решение задачи, условие которой представлено в табл.3, определим характеристики свободных клеток:
Е 13
= 3; Е 14
= 4; Е 15
= 4; Е 21
= – 4; Е 25
= 3 –(5+( – 3)) =1;
Е 31
= – 5; Е 32
= 0; Е 33
= – 2.
Видно, что отрицательных характеристик три: А 2
- В 1
, А 3
- В 1
и А 3
– В 3
. Наибольшая по абсолютной величине отрицательная характеристика в А 3
- В 1
, которая составляет – 5. перераспределим поставки по цепи к этой клетке. Для этого составим цепь с вершинами: А 1
- В 1
,
А 1
– В 2
,
А 2
– В 2
,
А 2
– В 4
,
,
А 3
– В 4
,
А 3
- В 1
.
Положительными вершинами в этой цепи будут А 3
– В 1
,
,
А 1
– В 2
,
,
А 2
– В 4
(так как увеличение поставок в этих клетках приводит к уменьшению значения целевой функции), а остальные отрицательными.
Наименьшая по величине поставка в отрицательных вершинах цнпи равна 7 (в А 2
– В 2
). Прибавляем по 7 к объемам поставки в положительных вершинах и вычитаем из поставок в отрицательных также по 7. Получившийся план перевозок записываем в таблицу 4 и определяем новые потенциалы, произвольно приняв потенциал строки А 1
равным 1. Значение целевой функции при новом плане поставок будет на 7 5=35 у.е. меньше, т.е.:
Характеристики свободных клеток для вновь созданного плана будут следующими:
Е 13
= -2; Е 14
= -1; Е 15
= -1; Е 21
= 1; Е 22
=5; Е 25
=1;
В таблице 4 отрицательных характеристик свободных клеток четыре: А 1
– В 3
,
А 1
– В 4
,
А 1
– В 5
,
А 3
– В 3
. Перераспределим поставки по цепи к любой из этих клеток, допустим к А 1
– В 5
, по цепи: А 1
– В 5
, А 3
– В 5
, А 3
– В 1
, А 1
– В 1
. Положительные вершины цепи А 1
– В 5
и А 3
– В 1
, а отрицательные А 3
– В 5
и А 1
– В 1
, минимальная поставка равна 15 от поставщика А 1
к потребителю В 1
, т.е. А 1
– В 1
(таблица 4/1).
Прибавляем по 15 к поставкам в положительных вершинах и отнимаем по 15 в отрицательных вершинах цепи. Получившийся план перевозок представлен в таблице 5.
Значение целевой функции при новом плане:
Аналогично определяем потенциалы строк и столбцов и рассчитываем характеристики цепей к свободным клеткам:
Е 11
= 1; Е 14
= 0; Е 13
= -1; Е 21
= 1; Е 22
=4; Е 23
=1;
Принимаем перераспределение поставок по цепи к А 3
– В 3
, т.к. характеристика данной клетки отрицательная и наибольшая по абсолютному значению. Составляем цепь перераспределения: А 3
– В 3
, А 2
– В 3
, А 3
– В 4
, А 3
– В 4
(таблица 5/1).
Минимальная поставка в отрицательных вершинах ( А 3
– В 4
) равна 3. Получившийся план перевозок представлен в таблице 6.
Значение целевой функции при новом плане:
Аналогично определяем потенциалы строк и столбцов и рассчитываем характеристики цепей к свободным клеткам:
Е 11
= 1; Е 14
= 2; Е 13
= 1; Е 21
= -1; Е 22
=2; Е 25
= -1;
Отрицательными характеристиками обладают две клетки: А 2
– В 1
и А 2
– В 5
. Произведем поставку 17 т из А 2
в В 1
(таблица 7).
При таком плане перевозок значение целевой функции:
Характеристики цепей к свободным клеткам:
Е 11
= 1; Е 14
= 2; Е 13
= 1; Е 22
= 3; Е 23
=2; Е 25
= 0;
Таким образом, в данном плане перевозок нет ни одной отрицательной характеристики. Нулевая оценка клетки А 2
– В 5
указывает на то, что данную программу можно изменить так, что эта клетка станет базисной, но при этом получится равноценный план с той же величиной затрат.
Отсутствие отрицательных характеристик свидетельствует о том, что нельзя построить цепей, перемещение поставок по которым уменьшит значение целевой функции. Значит, распределение является оптимальным. Задача решена.
Оптимальный план перевозок даст снижение стоимости перевозок по сравнению с исходным:
ИСХОДНЫЕ ДАННЫЕ К ЛАБОРАТОРНОЙ РАБОТЕ №2
Название: Определение оптимального плана перевозок
Раздел: Рефераты по логике
Тип: реферат
Добавлен 21:35:43 18 июня 2011 Похожие работы
Просмотров: 352
Комментариев: 14
Оценило: 3 человек
Средний балл: 4
Оценка: неизвестно Скачать
Срочная помощь учащимся в написании различных работ. Бесплатные корректировки! Круглосуточная поддержка! Узнай стоимость твоей работы на сайте 64362.ru
Привет студентам) если возникают трудности с любой работой (от реферата и контрольных до диплома), можете обратиться на FAST-REFERAT.RU , я там обычно заказываю, все качественно и в срок) в любом случае попробуйте, за спрос денег не берут)
Да, но только в случае крайней необходимости.
Реферат: Определение оптимального плана перевозок
Курсовая Работа На Тему Государственный Долг, Проблемы Управления Им
Реферат по теме Человек и мир человека в творчестве Ф.М.Достоевского
Сочинения Простакова Недоросль Цитаты
Сочинение по теме Человек в истекающем кровью мире
Курсовая Работа На Тему Злочини Проти Статевої Свободи Та Статевої Недоторканості Особи
Реферат по теме Житлове право України
Рассказы Шукшина Сочинение
Курсовая работа по теме Совершенствование организационной системы муниципального бюджетного образовательного учреждения
Реферат: Формирование духовности младших школьников
Реферат: Проблема аборта. Скачать бесплатно и без регистрации
Реферат по теме Образование и его проблемы на современном этапе
Курсовая работа: Разработка структуры управления, распределение полномочий
Как Заполнить Дневник По Учебной Практике
Реферат: Статистика уровня образования населения и развития системы обучения
Дипломная работа по теме Формирование спроса и стимулирование сбыта продукции на предприятии
Дипломная работа по теме Тренинг эмоциональной саморегуляции, как способ снижения уровня эмоционального выгорания у учителей
Составить План Сочинения На Тему Однажды Зимой
Полное Собрание Сочинений А П Чехова
Диета 0 Реферат
Диссертации Баумана
Курсовая работа: Проблемы государственного регулирования отечественной экономики
Реферат: Тэорыя інстытутаў М. Орыу
Реферат: Використання народного мистецтва в естетичному вихованні