Задача транспорта

Содержание

Введение

1. Транспортная задача
2. Математическая модель
3. Постановка классической транспортной задачи
4. Способы составления первого допустимого плана перевозок
5. Способ северо-западного угла
6. Способ наименьшего элемента в матрице
7. Способ двойного предпочтения
8. Способ аппроксимации Фогеля
9. Решение транспортных задач, имеющих некоторые дополнительные условия
1. Задача с распределением резерва (спрос не равен предложению)
2. Запрещение корреспонденции
3. Обязательная (директивная) корреспонденция
4. Открытая модель распределительного метода
5. Признаки наличия альтернативных решений в различных способах распределительного метода
10. Закрепление потребителей за поставщиками неоднородного взаимозаменяемого продукта
11. Усложнённая задача перевозки разнородной продукции
12. Транспортная задача по критерию времени

Заключение

Использованная литература

Введение

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

Задания:

1. Рассмотреть понятие транспортной задачи, ее типы.
2. Рассмотреть различные методы решения транспортной задачи.
3. Построить первый опорный план данной транспортной задачи двумя различными методами.
4. Найти оптимальный план перевозок данной задачи методом потенциалов.
5. Решить данную задачу с использованием MS Excel (привести описание решения).
6. Составьте компьютерную программу по решению задач данного типа (привести описание программы, приложить программу в электронном виде).

Каждый  человек ежедневно, не всегда осознавая  это, решает проблему: как получить наибольший эффект, обладая ограниченными  средствами. Наши средства и ресурсы  всегда ограничены. Жизнь была бы менее  интересной, если бы это было не так. Не трудно выиграть сражение, имея армию  в 10 раз большую, чем у противника. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить  план, или программу действий. Раньше план в таких случаях составлялся  “на глазок”. В середине XX века был  создан специальный математический аппарат, помогающий это делать “по  науке”. Соответствующий раздел математики называется математическим программированием. Слово “программирование" здесь  и в аналогичных терминах (“линейное  программирование, динамическое программирование”  и т.п.) обязано отчасти историческому  недоразумению, отчасти неточному  переводу с английского. По-русски лучше  было бы употребить слово “планирование”. С программированием для ЭВМ  математическое программирование имеет  лишь то общее, что большинство возникающих  на практике задач математического  программирования слишком громоздки  для ручного счета, решить их можно  только с помощью ЭВМ, предварительно составив программу. Временем рождения линейного программирования принято считать 1939 г, когда была напечатана брошюра Леонида Витальевича Канторовича “Математические методы организации и планирования производства”.

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

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

Цель  транспортной деятельности считается  достигнутой при выполнении шести  условий:

1. нужный товар;
2. необходимого качества;
3. в необходимом количестве доставлен;
4. в нужное время;
5. в нужное место;
6. с минимальными затратами.

1. Транспортная задача

Линейные  транспортные задачи составляют особый класс задач линейного программирования. Задача заключается в отыскании  такого плана перевозок продукции  с m складов в пункт назначения n который, потребовал бы минимальных затрат. Если потребитель j получает единицу продукции (по прямой дороге) со склада i, то возникают издержки С_ij. Предполагается, что транспортные расходы пропорциональны перевозимому количеству продукции, т.е. перевозка k единиц продукции вызывает расходы k С _{i j}.

Далее,

где a_i есть количество продукции, находящееся на складе i , и b_j - потребность потребителя j.

Замечание.

1. Если сумма запасов в пунктах  отправления превышает сумму  поданных заявок  то количество продукции, равное остается на складах. В этом случае мы введем "фиктивного" потребителя n+1 с потребностью и положим транспортные расходы p_{i,n +1} равными 0 для всех i.

2. Если сумма поданных заявок  превышает наличные запасы то потребность не может быть покрыта. Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления m + 1 с запасом и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.

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

где x_ij количество продукции, поставляемое со склада i потребителю j, а С _{i j} издержки (стоимость перевозок со склада i потребителю j).

3. Постановка классической транспортной задачи

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

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

Потребителям В₁, В₂, ..., В_j, ..., В_n требуется однородный продукт (груз) в количествах соответственно b₁, b₂, ..., b_j ,…, b_n тонн, который производится (или хранится) у поставщиков А₁, А₂, ..., А_i, ....А_m в количествах а₁, а₂, ...,а_i, ..., а_m тонн. Так как все поставщики производят одну и ту же продукцию, каждый из них может удовлетворять запросы любого потребителя. Расстояния между отправителями и получателями груза известны и составляют 1ц километров. Требуется составить такой план перевозок грузов, который обеспечит удовлетворение запросов всех потребителей при минимальной транспортной работе (минимальной сумме тонно-километров). Очевидно, что для решения рассматриваемой задачи необходимо равенство общей потребности получателей наличию груза у отправителей.

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

Таблица 1

Обозначим через х_ij количество тонн груза, предназначенного к отправке из пункта А_i в пункт В_j. Тогда количество груза, планируемое к доставке в пункт В_j из всех пунктов отправления, составит

х_1j + х_2j +…+ x_mj = Х_ij .                                                       (1)

Так как  потребность пункта назначения В_j составляет b_j, то при планировании перевозок должно соблюдаться равенство

X_ij = b_j .

Сказанное справедливо для любого пункта В_j. Поэтому получаем n уравнений

                                                 (2)

С другой стороны, общее количество груза, отправляемого  из пункта А_i во все пункты назначения В_j составит

 х_i1+х_i2+...+x_in= Х _ij.  (3)

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

Х _ij=a_i .

Так как  приведённое рассуждение относится  к любому пункту отправления, имеем m уравнений

(4)

Более компактно уравнения (1) - (4) можно записать следующим образом:

Х _ij= b_j, j = 1, 2, …, n;                                                        (5)

Х _ij= a_i, i = 1, 2, …, m;                                                       (6)

P = 1₁₁x₁₁ +1₁₂ x₁₂+…+1_ij x_ij +…+1_mn x_mn = l_ij X _ij.                        (7)

Очевидно, что объем каждой поставки не может быть отрицательным числом, т.е.

                                               x_ij >0, i=1,2, ..., m; j=1,2,..., n.                                      (8)

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

 l_ij X _ij, j = 1, 2, …, n, i = 1, 2, …, m  (9)

при условиях

X _ij= b_j, j = 1, 2, …, n;                                      (10)

X_ij= a_i, i = 1, 2, …, m;                                       (11)

                                                  x_ij>0, i =1, 2, ..., m; j=1, 2,..., n.                            (12)

Соблюдение  равенства (10) обеспечивает полное удовлетворение запросов всех потребителей. Уравнения (11) гарантируют полный вывоз из пунктов отправления, а уравнения (9) - неотрицательность переменных. Для совместности системы уравнений (9 - 12) необходимо, чтобы

                                                   a_i = b_j .                                                        (13)

Равенство (13) является не только необходимым, но и достаточным условием для совместности системы уравнений (9 – 12).

Поскольку уравнения (10 - 12) содержат неизвестные только в первой степени, а показатель L_ij в формуле (9) не зависит от x_ij, сформулированная задача является задачей линейного программирования. Формулировка задачи, в которой спрос и предложение равны, получила название закрытой модели.

Модель  транспортной задачи имеет следующие  особенности:

1. Модель выражается неопределённой системой линейных уравнений и, следовательно, имеет бесчисленное множество возможных решений.

2. Модель  совместна, т.е. имеет решение.

3. Элементами  матрицы системы являются единицы  и нули.

4. Система  является линейно-зависимой, так  как любое её уравнение можно  представить в виде линейной  комбинации остальных уравнений.

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

6. Целевая  функция выражается линейной  формой. Матрица целевой функции  — это матрица-строка, элементами  которой могут быть расстояния, время или стоимость перевозки.

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

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

Разновидности распределительного метода отличаются в основном способом выявления оптимального решения.

8. Способы составления первого допустимого плана перевозок

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

Таблица 2

Первоначальное распределение  перевозок может быть получено несколькими  способами. Рассмотрим на конкретном примере  сущность и эффективность некоторых  из них. От четырех кирпичных заводов  кирпич автомобильным транспортом  доставляется на пять строительных площадок. Необходимо определить план перевозок  кирпича, при котором объем транспортной работы будет минимальной. Исходные данные задачи приведены в табл. 2.

9. Способ северо-западного угла

Построение допустимого плана  этим способом начинается с верхней  левой клетки и заканчивается  в нижней правой клетке матрицы. В  клетки заносят максимально возможную  поставку, учитывая соотношение ресурсов поставщика и спрос потребителя. Груз первого поставщика распределяется так, что вначале удовлетворяются потребности первого потребителя, затем второго и так до полного распределения всего объема грузов данного поставщика. Затем переходят к распределению грузов второго поставщика и так до полного распределения объема грузов всех поставщиков. Если спрос какого-либо потребителя превышает количество груза у поставщика, то недостающий спрос удовлетворяется за счет следующего поставщика, т.е. расчет в этом случае ведется по столбцу. Допустимый план перевозки кирпича на строительные площадки, составленный способом северо-западного угла, приведен в табл. 3. В плане полностью соблюдается условие по ввозу и вывозу кирпича, количество заполненных клеток соответствует m + n - 1. Суммарная транспортная работа по плану распределения, составленному способом северо-западного угла, будет

L( x ) = 15 • 25 +12 • 75 +22 • 75 +22 • 100+14 • 125+ 6 • 50 + 10 • 25+ 18• 125 = 9675т• км.

Таблица 3