IX Международная студенческая научная конференция Студенческий научный форум - 2017

В данной статье рассмотрим метод Фогеля при составлении начального плана перевозки грузов. Как нам всем известно, что транспортная задача - задача о поиске оптимального распределения поставок однородного товара от поставщиков к потребителям при известных затратах на перевозку (тарифах) между пунктами отправления и назначения и она является задачей линейного программирования специального вида.

Решение данных задач начинается с поиска допустимого начального решения (плана перевозок), чтобы все запасы поставщиков были распределены по потребителям. Допустимое начальное решение не обязательно оказывается оптимальным, а метод его нахождения может быть как простейшим (метод северо-западного угла или аналогии) или более сложным и приближенным к оптимальному решению (метод минимальных тарифов, метод Фогеля).

Метод Фогеля (англ. Vogel’s approximation method) один из методов получения начального решения транспортной задачи. В отличие от метода северо-западного угла или метода минимальных тарифов, генерирует наиболее приближенное к оптимальному начальное решение. Это решение, однако, также может потребовать окончательной оптимизации при помощи метода потенциалов.

Последовательность действий при его использовании совершенно иная, чем при заполнении транспортной таблицы методом «Северо-Западного угла» или методом «Минимального элемента». На первый взгляд аппроксимация Фогеля сложнее, но это ложное впечатление. Метод простой и позволяет получить опорный план более приближенный к оптимальному решению, чем в случае применения других методов (за исключением разве что метода «Двойного предпочтения»). Сущность аппроксимации Фогеля в нахождении разности (по модулю) между парой минимальных тарифов в каждой строке и столбце. Затем строка или столбец с наибольшей разностью заполняются в направлении от клетки с минимальным тарифом к клетке с максимальным. Подробнее далее.

Суть метода Фогеля состоит в вычислении для каждой строки транспортной таблицы разницы между двумя наименьшими тарифами. Аналогичное действие выполняют для каждого столбца этой таблицы. Наибольшая разница между двумя минимальными тарифами соответствует наиболее предпочтительной строке или столбцу (если есть несколько строк или столбцов с одинаковой разницей, то выбор между ними произволен). В пределах этой строки или столбца отыскивают ячейку с минимальным тарифом, куда пишут отгрузку. Строки поставщиков или столбцы потребителей, которые полностью исчерпали свои возможности по отгрузке или потребности которых в товаре были удовлетворены, вычеркиваются из таблицы, и вычисление повторяются до полного удовлетворения спроса и исчерпания отгрузок без учета вычеркнутых ячеек.

Разберем алгоритм данного метода при решении транспортной задачи, который состоит из следующих шагов:

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

2. Отметить строку или столбец с самым большим штрафом (если таких несколько, выбрать из них любую строку или любой столбец). В отмеченной строке или столбце выбрать переменную с самой низкой стоимостью и придать ей наибольшее возможное значение. Скорректировать объем производства и спроса и вычеркнуть строку или столбец, соответствующие выполненному ограничению. Если ограничения по строке и столбцу выполняются одновременно, то вычеркнуть либо строку, либо столбец, а оставшемуся столбцу (строке) приписать нулевой спрос (объем производства). Строка (или столбец) с нулевым объемом производства (или спросом) не используется в дальнейших вычислениях (на шаге 3).

3. а) Если невычеркнутой остается только одна строка или один столбец, то закончить вычисления.

б) Если невычеркнутой остается только одна строка (столбец) с положительным объемом производства (спроса), найти базисные переменные в этой строке (столбце), используя метод наименьшей стоимости.

в) Если всем невычеркнутым строкам и столбцам соответствуют нулевые объемы производства и величины спроса, найти нулевые базисные переменные, используя метод наименьшей стоимости.

г) В других случаях вычислить новые значения штрафов для невычеркнутых строк и столбцов и перейти к шагу 2 (строки и столбцы с нулевыми значениями объема производства и спроса не должны использоваться при вычислении этих штрафов).

С помощью рассмотренных методов построения первоначального опорного плана можно получить вырожденный или невырожденный опорный план. Построенный план транспортной задачи, как задачи линейного программирования можно было бы довести до оптимального с помощью симплексного метода. Однако из-за громоздкости симплексных таблиц, содержащих mnнеизвестных, и большого объема вычислительных работ для получения оптимального плана используют более простые методы. Наиболее часто применяются метод потенциалов (модифицированный распределительный метод) и метод дифференциальных рент.

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

Пункты отправления	Пункты назначения				Запасы
	7	8	1	2	160
	4	5	9	8	140
	9	2	3	6	170
Потребности	120	50	190	110	470

Имеем задачу с правильным балансом, так как суммарный объем запасов (470) равен суммарному объему потребностей (470).

Пусть – количество единиц груза, перевозимого из i-го пункта отправления в j-й пункт назначения.

Составим математическую модель задачи:

при условиях

Как правило, применение метода аппроксимации Фогеля позволяет получить либо опорный

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

					Запасы	Столбец-разность
	7 -	8 -	1 50	2 110	160	1		к
	4 120	5 20	9 -	8 -	140	1	1	1	1	1
	9 -	2 30	3 140	6 -	170	1	1	1		к
Потребности	120	50	190	110
Строка- разность	3	3	2
	3	3	2	к
	5	3
	5	3	к
	к	к

План – невырожденный: , в данной задаче он является оптимальным.

В заключении следует отметить, что алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие: оптимальное закрепление за станками операций по обработке деталей; оптимальные назначения, или проблема выбора; задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции; увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега.

Библиографический список:

1. Ермолаева, В.И. Выбор параметра оптимизации при математическом моделировании объекта./ В.И. Ермолаева// Вестник Ульяновской государственной сельскохозяйственной академии, научно-теоретический журнал. - № 2(5) август-ноябрь. - 2007. – С. 41-42.

2. Ермолаева, В.И. Регрессионные математические модели / В.И. Ермолаева, С.И. Банников// Вестник Ульяновской государственной сельскохозяйственной академии, научно-теоретический журнал. - № 2(5) август-ноябрь. - 2007. – С. 39-41.

3. Ермолаева В.И., Банников С.И. Модель адаптивного тестирования нечеткой математики/ В.И. Ермолаева, С.И.Банников// Молодежь и наука XXI века. материалы II-й открытой Всероссийской научно-практической конференции молодых ученых. -Ульяновск: УГСХА , 2007. С. 144-147.

4. Ермолаева В.И., Банников С.И. Временные ряды и прогнозирование/ В.И. Ермолаева, С.И.Банников// Актуальные вопросы аграрной науки и образования. материалы Международной научно-практической конференции, посвященной 65-летию Ульяновской ГСХА. -Ульяновск: УГСХА, 2008. С. 264-266.

5. Ермолаева В.И., Евстигнеева О.Г. Математика/В.И.Ермолаева, О.Г.Евстигнеева//Допущено Министерством сельского хозяйства Российской Федерации в качестве учебного пособия для студентов аграрных вузов обучающихся заочно по инженерным специальностям. -Ульяновск: УГСХА, 2013. - 160 с.

6. Ермолаева В.И. Организация самостоятельной работы студентовавтореферат диссертации на соискание ученой степени кандидата педагогических наук / Ульяновский государственный педагогический университет им. И.Н. Ульянова. Ульяновск, 2004.

7. Ермолаева В.И. Организация самостоятельной работы студентов (на примере преподавания математики). Монография/ –Ульяновск: УГСХА, 2007.

8. Ермолаева В.И. О некоторых путях совершенствования самостоятельной работы студентов/В.И. Ермолаева // Проблемы модернизации высшего профессионального образования. Материалы Международной научно-методической конференции. Федеральное государственное образовательное учреждение высшего профессионального образования " Костромская государственная сельскохозяйственная академия"; Харьковский государственный технический университет сельского хозяйства (Украина); Институт сельскохозяйственного развития в Центральной и Восточной Европе (Германия). 2004. С. 16-18.

9. Хабарова В.В., Ермолаева В.И. Математическое обоснование процесса деформации при измельчении корнеплодов /В.В. Хабарова, В.И. Ермолаева// Аграрная наука и образование на современном этапе развития: опыт, проблемы и пути их решения Материалы VI Международной научно-практической конференции. 2015. С. 118-119.

10. Хабарова В.В., Ермолаева В.И. К вопросу обоснования конструктивных особенностей измельчителя корнеплодов/ В.В. Хабарова, В.И. Ермолаева// Аграрная наука и образование на современном этапе развития: опыт, проблемы и пути их решения Материалы VI Международной научно-практической конференции. 2015. С. 197-199.

Код для цитирования: Скопировать