Метот минимального элемента

 

 Введение      

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

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

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

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

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

Существует  множество методов для решения  данной задачи. Выбрав один из методов  можно быстро рассчитать оптимальный  план распределения.     

Процесс решения таких задач можно  значительно упростить, применяя различные  программные пакеты.  
  
  
  
  
  
  
  
  
  
  
  
       

1 Постановка транспортной  задачи     

Классическая  постановка транспортной задачи общего вида такова.   
Имеется m пунктов отправления («поставщиков») и n пунктов потребления («потребителей») некоторого одинакового товара. Для каждого пункта определены:   
a_i –объемы производства i -го поставщика, i = 1, …, m;   
в_j – спрос j-го потребителя, j= 1,…,n;   
с_ij – стоимость перевозки одной единицы продукции из пункта A_i– i-го поставщика, в пункт В_j – j-го потребителя.   

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

Таблица 1     

 

Потребители/ Поставщики В1 В2 … В n Запасы А1 С11 C 12   C 1n а1 А2 С21 C 22   C 2n а2 …           Am Cm 1 Cm 2   Cmn аm Потребности в1 в2   вn

 
  
     

Требуется найти план перевозок, при котором  бы полностью удовлетворялся спрос  всех потребителей, при этом хватало  бы запасов поставщиков и суммарные  транспортные расходы были бы минимальными.   
Под планом перевозок понимают объем перевозок, т.е. количество товара, которое необходимо перевезти от i-го поставщика к j-му потребителю. Для построения математической модели задачи необходимо ввести m·n штук переменных х_ij, i= 1,…, n, j= 1, …, m, каждая переменная х_ij обозначает объем перевозок из пункта A_i в пункт В_j. Набор переменных X = {x_ij} и будет планом, который необходимо найти, исходя из постановки задачи.     

Тогда математическая постановка задачи состоит  в определении минимального значения функции:     

,                       (1)      

,   i=1,2,…,m ,                        (2)      

,   j=1, 2, … , n,                        (3)      

,      i=1,2,,…,m,    j=1,2,…,n (4)     

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

2 Математическая модель  транспортной задачи     

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

Переменными (неизвестными)  транспортной задачи являются i=1,2,,…,m, j=1,2,…,n – объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок        

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

(5)       

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

,   i=1,2,…,m (6)       

 Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:      

,   j=1, 2, … , n(7)      

В рассмотренной модели транспортной задачи предполагается, что суммарные  запасы поставщиков равны суммарным  запросам потребителей, т.е.  (8)           

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

Математическая формулировка транспортной задачи такова: найти  переменные задачи ,    i=1,2,,…,m,  j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).           

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

 

 

  
     

.……………………………………………………      

А =    (9)     

……………………………………………………  
       

 Сверху над каждым столбцом  матрицы указана переменная задачи, коэффициентами при которой являются  элементы соответствующего столбца  в уравнениях системы ограничений.  Каждый столбец матрицы А, соответствующий переменной , является вектором-условием задачи и обозначается через . Каждый вектор имеет всего m+n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора стоит на i-м месте, а вторая – на (m+j)-м месте:  
  
  
  
  
  
  
      

Номеркоординаты     

 

=      =         (10)  
       

 Обозначим через  вектор ограничений и представим систему ограничений задачи в векторном виде. Тогда математическая модель транспортной задачи запишется следующим образом:      

(11)      

=,    (12)      

,      i=1,2,,…,m,    j=1,2,…,n   (13)  
  
  
  
  
  
  
  
  
  
  
      

3  Методы нахождение  опорного плана  транспортной задачи      

3.1 Правило "северо-западного  угла"      

При нахождении опорного плана транспортной задачи методом "северо-западного угла" на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение транспортной таблицы начинается с левого верхнего угла (северо-западного), двигаясь далее по строке вправо или  по столбцу вниз (увеличение i, увеличение j). Переменной Х₁₁ приписывают максимальное значение, допускаемое ограничениями на спрос и запасы.     

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

Исходный опорный  план, построенный по правилу "северо-западного  угла", обычно оказывается весьма далеким от оптимального, так как  при его формировании не учитывается  стоимость перевозок (величина с_ij). Более совершенным правилом является правило "минимального элемента".       

3.2  Метод аппроксимации Фогеля        

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

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

3.3 Правило "минимального  элемента"      

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

Правило "минимального элемента" заключается в том, чтобы  перевозить максимально возможные  объемы из пунктов отправления маршрутами минимальной стоимости. Заполнение таблицы начинаем с клетки, которой  соответствует наименьшая стоимость перевозки (элемент c_ij) из всей таблицы. Переменной этой клетки х_ijприсваивается максимально возможное значение с учетом ограничений. Затем остаток по столбцу или строке помещается в клетку того же столбца или строки, которой соответствует следующее по величине значение с_ij и т. д. Иными словами, последовательность заполнения клеток определяется по величине с_ij, а помещаемая в этих клетках величина х_ij такая же, как и в правиле "северо-западного угла".  
  
  
  
  
      

4 Решение транспортной  задачи методом  минимального элемента       

^{Задача:}      

^{У поставщиков A1 , A2 , A3 находится соответственно 115,175,130 единиц однотипной продукции, которая должна быть доставлена потребителям B1 , B2 , B3 , B4, В5 в количествах 70, 220, 40, 30, 60 единиц соответственно.}     

^{Стоимость доставки единицы  продукции от поставщика A1 к указанным потребителям равна 4, 5, 2, 8, 6 ден.ед.}     

^{Стоимость доставки единицы  продукции от поставщика A2 к указанным потребителям равна 3, 1, 9, 7, 3ден.ед.}     

^{Стоимость доставки единицы  продукции от поставщика A3 к указанным потребителям равна 9, 6, 7, 2, 1ден.ед.}     

^{Требуется найти оптимальное  решение доставки продукции от поставщиков  к потребителям с  максимальной прибылью.}     

^{Решение :}       

Математическая  модель транспортной задачи:     

F = ??c_ijx_ij,    (14)     

при условиях:     

?x_ij = a_i,  i = 1,2,…, m,   (15)      

?x_ij = b_j,  j = 1,2,…, n,   (16)      

С целью составления двойственной задачи переменные x_ij в условии (15) заменим на u₁, u₂, u_i,.., u_m, а переменные x_ij в условия (16) на v₁, v₂, v_j,.., v_n.      

Поскольку каждая переменная x_ij входит в условия (15, 16) и целевую функцию (14) по одному разу, то двойственную задачу по отношению к прямой транспортной задаче можно сформулировать следующим образом.     

Требуется найти не отрицательные числа  u_i (при i  = 1,2,…,m) и v_j (при j = 1,2,..,n), обращающие в максимум целевую функцию     

G = ?a_iu_i + ?b_jv_j(17)     

при условии     

u_i + v_j ? c_ij, i = 1,2,..,m; j = 1,2,..,n    (18)     

В систему условий (4) будет mxn неравенств. По теории двойственности для оптимальных планов прямой и двойственной задачи для всех i,j должно быть:     

u_i + v_j ? c_ij, если x_ij = 0,     

u_i + v_j = c_ij, если x_ij ? 0,