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

Содержание

Введение. . . . . . . . . . . . . . . . . . . . . . . .  . . .. . .  . . . . . . . . . .  . . . . . . . ………3

1.Теоретическая часть.

1.1Постановка Транспортной  задачи (ТЗ) для n переменных. . . . . . . . . . . .4

1.2. Методы составления  начального опорного плана. . . . . . . . . . . . . . . . . .5

1.3. Метод потенциалов. . . . . . . . . . . . . . . . . . . . . . . .  . . .. . .  . . . . . . . . . .  . .6

2 .Практическая часть.

2.1  Условие задачи. . . . . . . . . . . . . . . . . . . . . . . .  . . .. . .  . . . . . . . . . .  . . . . 12

2.2  Решение задачи  методом потенциалов. . . . . . . . . . . . . . . . . . . . . . . . .13

2.3 Решение задачи c помощью Excel

Заключение. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 17

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

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

 

 

 

 

 

 

 

 

 

Теоретическая часть

1.1 Постановка Транспортной задачи (ТЗ) для n переменных

Постановка задачи и ее математическая модель транспортной задачи является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i , А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁, ..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт В_j, i  1, …, m; j  1, ..., n. Предположим, что

          

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

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

             (1)

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

, i  1, …, m                (2)

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

, j  1, …, n                (3)

Объемы  перевозок - неотрицательные числа, так как перевозки из пунктов  потребления в пункты производства исключены:

x_ij  0, i  1, ..., m; j  1, ..., n   (4)

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

Определение 1.

Всякое  неотрицательное решение системы  линейных уравнений

, j  1, …, n       и         , i  1, …, m,

определяемое  матрицей X=(x_ij)(i  1, …, m; j  1, ..., n), называется планом транспортной задачи.  

 

Определение 2.

План X*=(x*_ij)(i  1, …, m; j  1, ..., n), при котором функция

 

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

Обычно  исходные данные записываются в виде таблицы 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

Очевидно, общее наличие груза у поставщиков  равно  , а общая потребность в грузе в пунктах назначения равна единице. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

,          (5)

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

 

 

 

 

1.2. Методы составления  начального опорного плана

Как и  при решении задачи линейного  программирования, симплексным методом, определение оптимального плана  транспортной задачи начинают с нахождения какого-нибудь ее опорного плана. Число  переменных X_ij в транспортной задаче с m пунктами отправления и n пунктами назначения равно nm, а число уравнений в системах (2) и (3) равно n+m. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно n+m-1  отличных от нуля неизвестных. Если в опорном плане число отличных от нуля компонентов равно в точности n+m-1, то план является не выраженным, а если меньше - то выраженным. Для определения опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля - рассмотрены ниже. При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ. Обычно рассмотренный метод используется при вычислениях с помощью ЭВМ. Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом. Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения системы (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы. Два из них - метод потенциалов и Венгерский метод - рассматриваются ниже.

 

 

 

 

 

 

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

Метод потенциалов  является модификацией симплекс-метода решения задачи линейного программирования применительно к транспортной задаче. Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное  решение за конечное число итераций. Общая схема отдельной итерации такова. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аi соответствуют числа ui, пунктам Bj - числа vj. Они выбираются таким образом, чтобы их разность на k-й итерации была равна Сij - стоимости перевозки единицы продукции между пунктами Аi и Вj:

vj[k] –  ui[k]  Cij, i  1, ..., m; j 1, …, п.

Если  разность предварительных потенциалов  для каждой пары пунктов Аi, Вj не превосходит Сij, то полученный план перевозок является решением задачи. В противном случае указывается  способ получения нового допустимого  плана, связанного с меньшими транспортными  издержками. За конечное число итераций находится оптимальный план задачи.

 Пусть имеется транспортная  задача с балансовыми условиями

 

 

Стоимость перевозки единицы  груза из A_i в B_j равна C _ij; таблица стоимостей задана. Требуется найти план перевозок x_ij, который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок была минимальна.

Идея метода потенциалов  для решения транспортной задачи сводиться к следующему. Представим себе что каждый из пунктов отправления A_i вносит за перевозку единицы груза (всё равно куда) какую-то сумму a_i; в свою очередь каждый из пунктов назначения B_jтакже вносит за перевозку груза (куда угодно) сумму b_j. Эти платежи передаются некоторому третьему лицу (“перевозчику“). Обозначим a_i + b_j = č_ij (i=1. m; j=1. n) и будем называть величину č_ij “псевдостоимостью" перевозки единицы груза из A_i в B_j. Заметим, что платежи a_i и b_j не обязательно должны быть положительными; не исключено, что “перевозчик" сам платит тому или другому пункту какую-то премию за перевозку.

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

č_ij = a_i + b_j = с_ij, при x_ij >0.

Что касается свободных клеток (где x_ij = 0), то в них соотношение между псевдостоимостями и стоимостями может быть, какое угодно. Оказывается соотношение между псевдостоимостями и стоимостями в свободных клетках показывает, является ли план оптимальным или же он может быть улучшен. Существует специальная теорема: Если для всех базисных клеток плана x_ij > 0,a_i + b_j = č_ij= с_ij, а для всех свободных клеток x_ij=0,a_i + b_j = č_ij≤ с_ij, то план является оптимальным и никакими способами улучшен быть не может. Нетрудно показать, что это теорема справедлива также для вырожденного плана, и некоторые из базисных переменных равны нулю. План обладающий свойством:

č_ij= с_ij (для всех базисных клеток) (1)

č_ij≤ с_ij (для всех свободных клеток) (2)

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

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

Итак, для решения транспортной задачи нам нужно одно - построить  потенциальный план. Оказывается  его можно построить методом  последовательных приближений, задаваясь  сначала какой-то произвольной системой платежей, удовлетворяющей условию (1). При этом в каждой базисной клетке получиться сумма платежей, равная стоимости перевозок в данной клетке; затем, улучшая план следует одновременно менять систему платежей. Так, что они приближаются к потенциалам. При улучшении плана нам помогает следующее свойство платежей и псевдостоимостей: какова бы ни была система платежей (a_i и b_j) удовлетворяющая условию (1), для каждой свободной клетки цена цикла пересчёта равна разности между стоимостью и псевдостоимостью в данной клетке: g_i,j= с_i,j - č_i,j.

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

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

Уравнений всего m + n - 1, а число неизвестных равно m +n.  Следовательно, одну из этих неизвестных можно задать произвольно (например,  равной нулю). После этого из m +  n - 1 уравнений можно найти остальные платежи a_i, b _j, а по ним вычислить псевдостоимости ,  č_{i ,j}=  a_i + b_j для каждой свободной клетки.  

 

 

 

 

 

 

 

 

 

Таблица №5

ПН / ПО	В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