Размещено на http://www.allbest.ru/

ВВЕДЕНИЕ

Под названием «транспортная задача» объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.

Цели и задачи: «Создание оптимального плана перевозок транспортной задачи»



1. ТЕОРЕТИЧЕСКИЙ РАЗДЕЛ

1.1 Общая постановка транспортной задачи

Транспортная задача (Т-задача) является одной из наиболее распространенных специальных задач ЛП. Первая строгая постановка Т-задачи принадлежит Ф. Хичкоку, поэтому в зарубежной литературе ее часто называют проблемой Хичкока.

Первый точный метод решения Т-задачи разработан Л. В. Канторовичем и М. К. Гавуриным.

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

1.2 Решение транспортной задачи

Основные шаги при решении транспортной задачи:

1. Найти начальный допустимый план.

2. Выбрать из небазисных переменных ту, которая будет вводиться в базис. Если все небазисные переменные удовлетворяют условиям оптимальности, то закончить решение, иначе к следующему шагу.

3. Выбрать выводимую из базиса переменную, найти новое базисное решение. Вернуться к шагу 2. Всякое неотрицательное решение систем линейных уравнений и определяемое матрицей, называется планом транспортной задачи. Опорным (базисным) планом Т-задачи называют любое ее допустимое, базисное решение. Обычно исходные данные транспортной задачи записывают в виде таблицы. Матрицу С называют матрицей транспортных затрат, матрицу X, удовлетворяющую условиям Т-задачи называют планом перевозок, а переменные - перевозками. План, при котором целевая функция минимальна, называется оптимальным. Число переменных в транспортной задаче с m пунктами отправления и n пунктами назначения равно m*n. Следовательно опорный план транспортной задачи может иметь не более m+n-1 отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонент равно в точности m+n-1, то план является невырожденным, а если меньше - то вырожденным. Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

1.3 Математическая модель

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

1.4 Понятие открытой и закрытой модели

Модель ТЗ называют закрытой (сбалансированной), если суммарный объем груза, имеющегося у поставщиков, равен суммарному спросу потребителей, т. е. выполняется равенство (1.1):

.

Если для транспортной задачи выполняется одно из условий (1.2):

то модель задачи называют открытой (несбалансированной).

Для разрешимости ТЗ с открытой моделью необходимо преобразовать ее в закрытую модель.

Так, при выполнении условия (1.3) необходимо ввести фиктивный (n+1) пункт назначения , т. е. в матрице задачи добавляется столбец. Спрос фиктивного потребителя полагают равным небалансу, (1.4)



а стоимость перевозок равной нулю, т. е. . Переменные - это количество груза, которое останется в I-ом пункте отправления. Аналогично при выполнении условия (3.4) вводится фиктивный поставщик , т. е. в матрице задачи добавляется строка. Запас груза фиктивного поставщика равен (1.5)

а тарифы (стоимости перевозок) равны нулю, т. е. . Переменные - это количество груза, недостающее J-му пункту назначения.

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

Целевая функция (1.2) и система ограничений (1.1) являются экономико-математической моделью сбалансированной ТЗ.

Алгоритм решения сбалансированной транспортной задачи

1 Строим исходный опорный план.

2 Проверяем его на оптимальность. Если план оптимален, задача решена. Иначе переходим к пункту 3.

Переходим к не худшему опорному плану. Возвращаемся к пункту 2



1.5 Метод северо-западного угла

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

1.6 Метод минимальной стоимости

Метод минимальной стоимости прост и позволяет построить опорное решение, достаточно близкое к оптимальному, так как использует матрицу стоимостей транспортной задачи C=(cij).

Как и метод северо-западного угла, он состоит из ряда однотипных шагов, на каждом из которых заполняется только одна клетка таблицы, соответствующая минимальной стоимости: (1.6)

и исключается из рассмотрения только одна строка (поставщик) или один (1.7)



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

1.7 Метод потенциалов

Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями (1.8) - (1.12)

Стоимость перевозки единицы груза из Ai в Bj равна Cij; таблица стоимостей задана. Требуется найти план перевозок xij, который удовлетворял бы балансовым условиям, и при этом стоимость всех перевозок была минимальна.

Идея метода потенциалов для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправления Ai вносит за перевозку единицы груза (всё равно куда) какую-то сумму ai; в свою очередь каждый из пунктов назначения Bj также вносит за перевозку груза (куда угодно) сумму bj. Эти платежи передаются некоторому третьему лицу (“перевозчику“). Обозначим ai + bj = иij (i=1. m; j=1. n) и будем называть величину иij “псевдостоимостью» перевозки единицы груза из Ai в Bj. Заметим, что платежи ai и bj не обязательно должны быть положительными; не исключено, что “перевозчик» сам платит тому или другому пункту какую-то премию за перевозку.

Также надо отметить, что суммарная псевдостоимость любого допустимого плана перевозок при заданных платежах (ai и bj) одна и та же и от плана к плану не меняется. До сих пор мы никак не связывали платежи (ai и bj) и псевдостоимости иij с истинными стоимостями перевозок C ij. Теперь мы установим между ними связь. Предположим, что план xij невырожденный (число базисных клеток в таблице перевозок ровно m + n - 1). Для всех этих клеток xij >0. Определим платежи (ai и bj) так, чтобы во всех базисных клетках псевдостоимости были ровны стоимостям:

иij = ai + bj = сij, при xij >0.

Что касается свободных клеток (где xij = 0), то в них соотношение между псевдостоимостями и стоимостями может быть, какое угодно. Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана



xij > 0, ai + bj = иij= сij,

а для всех свободных клеток

ij =0, ai + bj = иij? сij,

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

- иij= сij (для всех базисных клеток)

- иij? сij (для всех свободных клеток)

называется потенциальным планом, а соответствующие ему платежи (ai и bj) - потенциалами пунктов Ai и Bj (i=1,.,m; j=1,.,n).

Пользуясь этой терминологией выше упомянутую теорему можно сформулировать так: «всякий потенциальный план является оптимальным».

Итак, для решения транспортной задачи нам нужно одно - построить потенциальный план. Оказывается его можно построить методом последовательных приближений, задаваясь сначала какой-то произвольной системой платежей, удовлетворяющей условию (1.1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план, следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: какова бы ни была система платежей (ai и bj) удовлетворяющая условию (1.1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке: gij = сij - иij.

Таким образом, при пользовании методом потенциалов для решения транспортной задачи отпадает наиболее трудоёмкий элемент распределительного метода: поиски циклов с отрицательной ценой.

Процедура построения потенциального (оптимального) плана состоит в следующем. В качестве первого приближения к оптимальному плану берётся любой допустимый план (например, построенный способом минимальной стоимости по строке). В этом плане m + n - 1 базисных клеток, где m - число строк, n - число столбцов транспортной таблицы. Для этого плана можно определить платежи (ai и bj), так, чтобы в каждой базисной клетке выполнялось условие: ai + bj = сij

Уравнений всего (m+n-1), а число неизвестных равно (m+n), следовательно, одну из этих неизвестных можно задать произвольно (например, равной нулю). После этого из (m + n - 1) уравнений можно найти остальные платежи ai, bj, а по ним вычислить псевдостоимости, иi,j= ai + bj для каждой свободной клетки (таблица 1.1).

Таблица 1.1 - Базисная таблица

ПН / ПО	В1	В2	В3	В4	В5	ai
А1	10 и = 7	8 и = 6	5 42	6 6	9 и = 6	a1= 0
А2	6 4	7 и = 5	8 и = 4	6 и = 5	5 26	a2= - 1
А3	8 и = 8	7 27	10 и = 6	8 и = 7	7 0	a3= 1
А4	7 14	5 и = 6	4 и = 5	6 6	8 и = 6	a4= 0
bj	b1= 7	b2= 6	b3= 5	b4= 6	b5= 6

A4 = 0,

b4 = 6, так как a4 + b4 = С44 = 6,1= 0, так как a1 + b4 = С14 = 6,3 = 5, так как a1 + b3 = С13 = 5,1 = 7, так как a4 + b1 = С41 = 7,2= - 1, так как a2 + b1 = С21 = 6,5 = 6, так как a2 + b5 = С25 = 5,3= 1, так как a3 + b5 = С35 = 7,2 = 6, так как a3 + b2 = С25 = 7.

Если оказалось, что все эти псевдостоимости не превосходят стоимостей иij и сij, и і то план потенциален и, значит, оптимален. Если же хотя бы в одной свободной клетке псевдостоимость больше стоимости (как в нашем примере), то план не является оптимальным и может быть улучшен переносом перевозок по циклу, соответствующему данной свободной клетке. Цена этого цикла ровна разности между стоимостью и псевдостоимостью в этой свободной клетке. Выгоднее всего строить цикл в той клетке, в которой разность иij - сij максимальна. В нашем случае в обоих клетках разность одинакова (таблица 1.2)

Таблица 1.2 - Таблица с потенциальным планом

ПН ПО	В1	В2	В3	В4	В5	ai
А1	10	8	5 42	6 6	9	0
А2	6 + 4	7	8	6	5 - 26	-1
А3	8	7 - 27	10	8	7 + 0	1
А4	7 - 14	5 +	4	6 6	8	0
bj	7	6	5	6	6

Теперь будем перемещать по циклу число 14, так как оно является минимальным из чисел, стоящих в клетках, помеченных знаком «-». При перемещении мы будем вычитать 14 из клеток со знаком - и прибавлять к клеткам со знаком «+». После этого необходимо подсчитать потенциалы ai и bj и цикл расчетов повторяется. Итак, мы приходим к следующему: алгоритму решения транспортной задачи методом потенциалов.

1.8 Построение оптимального плана перевозок

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

Число переменных Xij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах равно (n+m) Так как мы предполагаем, что выполняется условие, то число линейно независимых уравнений равно (n+m-1) отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонентов равно в точности (n+m-1), то план является не выраженным, а если меньше - то выраженным. Для определения опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля.

При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Обычно рассмотренный метод используется при вычислениях с помощью ЭВМ. Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

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



2. ПРАКТИЧЕСКИЙ РАЗДЕЛ

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

Имеется пунктов отправления, в каждом из которых сосредоточено определенное количество единиц однородного продукта, предназначенного к отправке: в первом пункте имеется единиц этого продукта, во втором - единиц, в м пункте единиц, и, наконец, в м пункте единиц продукта. Этот продукт следует доставить в пунктов назначения (потребления), причем в первый пункт назначения следует доставить единиц продукта, во второй - единиц, в й пункт единиц, и, наконец, в й пункт единиц продукта.

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

Удельные стоимости и время перевозок приведены в таблице 2.1, при этом:

1) на пропускные способности коммуникаций ограничения не накладываются;

2) и - количество условных единиц продукта;

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



Таблица 2.1 - Удельные стоимости и время перевозок

Bj Ai	B1	B2	B3	B4	B5	B6	B7	B8	ai
A1									180
A2									140
A3									50
A4									150
A5									80
A6									80
A7									70
bj	50	80	10	40	140	110	130	150

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

Разработанный программный продукт должен обрабатывать числовые значения из заданного диапазона:

а) количество пунктов отправления может быть или 6, или 7, или 8;

б) количество пунктов отправления может быть или 7, или 8, или 9;

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

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

д) удельные стоимости могут быть назначены из диапазона ;

е) значения времени перевозок могут быть назначены из диапазона

2.2 Обоснование математической модели

В пункте производится единиц однородного продукта. В пункте требуется единиц этого продукта. Пусть - количество единиц продукта, перевозимого из пункта в пункт , а затраты на перевозку - материальные, - временные. Необходимо определить множество переменных (; ), удовлетворяющих условиям: (2.1), (2.2)

, ,

, ,

и таких, что целевая функция (2.3) достигает минимума.

,

Так как во всех пунктах производства не должно остаться не вывезенного товара, необходимо условие (2.4).

, ,

Оно гарантирует полный вывоз продукта из всех пунктов производства.

Так как во всех пунктах потребления товара необходимо доставить согласно спросу, необходимо условие (2.5).

, ,

Оно означает полное удовлетворение спроса во всех пунктах потребления.

Количество единиц товара, перевозимого из пункта в пункт , не может быть отрицательным, следовательно, необходимо ввести условие не отрицательности(2.6).

(; ,

Так как нам необходимо минимизировать суммарные материальные транспортные издержки при перевозе всего товара из пунктов производства в пункт потребления, целевая функция (2.7) будет иметь вид:

,

Для дооптимизации по времени необходимо использовать следующую целевую функцию (2.8)

,

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



2.3 Проверка достоверности полученных результатов

В общем случае проверка полученных результатов после очередной итерации вычисления осуществляется следующим образом:

Целевая функция считается 2 способами: (2.9) (2.10)

Пусть минимальным элементом матрицы С(k) оказался элемент с индексами м, к, тогда значение целевой функции на этом шаге будет равно

,

Если значения не совпадают то, на экран выводится ошибка.

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

При выполнении дооптимизации единственным подтверждением правильности результатов может служить уменьшение целевой функции (2.11)

,

2.4 Алгоритм решения задачи

1. Проверка правильности ввода данных.

2. Проверка условия баланса.

3. Построение начального опорного плана Х(0) методом минимального элемента.

4. Проверка плана на вырожденность, если нужно добавляем фиктивные перевозки.

5. Расчет начальных потенциалов и заполнение матрицы С(1).

6. Поиск минимального элемента в матрице С(1).

7. Если этот элемент меньше нуля, то заменяем нулевой элемент, соответствующий минимальному в С(1), в плане Х(0) на фиктивную перевозку, иначе на пункт 12.

8. Производим процедуру вычеркивания.

9. Оставшиеся не вычеркнутыми элементы разделяем на четные и нечетные, учитывая, что добавленный элемент принадлежит к четным.

10. Находим минимальный нечетный элемент и прибавляем его ко всем четным и отнимаем от нечетных элементов. Причем, если минимальных элементов окажется 2 или более, то один из них обнуляем, а остальные делаем фиктивными. В итоге получаем план Х(1).

11. Производим процедуру вычеркивания. Получаем матрицу С(2).

12. Проверяем матрицу С(2) на наличие отрицательных элементов. Если такие элементы присутствуют, то повторяем пункты с 5 по11.

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

14. До оптимизация по времени.

14.1. Ищем отличный от нуля элемент в матрице X(k), которому соответствует наибольший элемент матрицы Т=tmax.

14.2. Ищем в матице С(k) нули соответствующие таким нулям в матрице X(k), что соответствующие им элементы матрицы Т меньше tmax.

14.3. Если в предыдущем пункте нашелся хоть один ноль, то производим процедуры пунктов 7-10.

14.4. Переходим к пункту 14.1.

15. Вывод результатов.



ЗАКЛЮЧЕНИЕ

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

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

Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки. Таким образом, важность решения данной задачи для экономики несомненна. Приятно осознавать, что у истоков создания теории линейного программирования и решения, в том числе и транспортной задачи, стоял русский ученый - Леонид Витальевич Канторович.



СПИСОК ИСПОЛЬЗУЕМЫХ ИСТОЧНИКОВ

1. Бабешко, Л. О. Математическое моделирование финансовой деятельности. Учебное пособие / Л.О. Бабешко. - М.: КноРус, 2016. - 224 c.

2. Белов, П. Г. Управление рисками, системный анализ и моделирование. Учебник и практикум. В 3 частях. Часть 2 / П.Г. Белов. - М.: Юрайт, 2016. - 252 c

3. Королев, А. В. Экономико-математические методы и моделирование : учебник и практикум для вузов А. В. Королев. -- Москва : Юрайт, 2020. -- 280 с

4. Виноградов, Ю.Б. Математическое моделирование в гидрологии / Ю.Б. Виноградов. - М.: Academia, 2017. - 272 c.

5. Горбунов, В.К. Математическое моделирование рыночного спроса: Учебное пособие В.К. Горбунов. - СПб.: Лань, 2018. - 212 c.

6. Бобренева, И.В. Математическое моделирование в технологиях продуктов питания животного происхождения: Учебное пособие И.В. Бобренева, С.В. Николаева. - СПб.: Лань, 2019. - 124 c.

7. Монаков, А.А. Математическое моделирование радиотехнических систем: Учебное пособие / А.А. Монаков. - СПб.: Лань, 2016. - 144 c-

Размещено на Allbest.ru