Студопедия

КАТЕГОРИИ:


Архитектура-(3434)Астрономия-(809)Биология-(7483)Биотехнологии-(1457)Военное дело-(14632)Высокие технологии-(1363)География-(913)Геология-(1438)Государство-(451)Демография-(1065)Дом-(47672)Журналистика и СМИ-(912)Изобретательство-(14524)Иностранные языки-(4268)Информатика-(17799)Искусство-(1338)История-(13644)Компьютеры-(11121)Косметика-(55)Кулинария-(373)Культура-(8427)Лингвистика-(374)Литература-(1642)Маркетинг-(23702)Математика-(16968)Машиностроение-(1700)Медицина-(12668)Менеджмент-(24684)Механика-(15423)Науковедение-(506)Образование-(11852)Охрана труда-(3308)Педагогика-(5571)Полиграфия-(1312)Политика-(7869)Право-(5454)Приборостроение-(1369)Программирование-(2801)Производство-(97182)Промышленность-(8706)Психология-(18388)Религия-(3217)Связь-(10668)Сельское хозяйство-(299)Социология-(6455)Спорт-(42831)Строительство-(4793)Торговля-(5050)Транспорт-(2929)Туризм-(1568)Физика-(3942)Философия-(17015)Финансы-(26596)Химия-(22929)Экология-(12095)Экономика-(9961)Электроника-(8441)Электротехника-(4623)Энергетика-(12629)Юриспруденция-(1492)Ядерная техника-(1748)

Метод потенциалов решения транспортной задачи




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

Задача 4.1. Три предприятия A1, A2, A3 производят однотипную продукцию в количествах соответственно 30, 60, 10 единиц. Спрос на данный вид продукции у потребителей B1, B2, B3, В4 составляет 15, 40, 25, 20 единиц. Заданные удельные издержки транспортировки груза от каждого предприятия каждому потребителю расположены в правых верхних углах клеток таблицы 4.2.

Определить план перевозок, при котором суммарная стоимость доставки грузов будет минимальна.

 

Таблица 4.2 Исходные данные транспортной задачи

Предприятия Потребители
b1 = 15 b2 = 40 b3 = 25 b4 = 20
A1 а1 = 30        
A2 а2 = 60        
A3 а3 = 10        

 

РЕШЕНИЕ.

1 П р о в е р к а у с л о в и я з а м к н у т о с т и.

Задача замкнутая, так как выполняется условие

= 100.

Если в какой-либо задаче условие (4.5) не выполняется (открытая модель транспортной задачи), в транспортную таблицу вводится столбец фиктивного потребителя (при ) или строка фиктивного поставщика (при ). В фиктивной строке или столбце cij назначаются, равными нулю. Спрос фиктивного потребителя равен . Запас продукции у фиктивного поставщика: . Наличие фиктивного поставщика интерпретируется как ввоз недостающего количества продукта извне пределов рассматриваемого района. Фиктивный потребитель – вывоз излишков продукта за пределы данного района.

 

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

Суммарная стоимость перевозок:

.

Балансовые условия:

;

;

;

;

;

;

;

.

3 С о с т а в л е н и е о п о р н о г о п л а н а

Для построения опорного решения можно использовать следующие методы: северо-западного угла, аппроксимации, минимального элемента и др.

Мы рассмотрим один из наиболее простых и эффективных методов – метод минимального элемента.

Суть метода заключается в том, что из таблицы удельных затрат на перевозки выбирают наименьшую стоимость, и в клетку, которая ей соответствует, помещают меньшее из чисел ai или bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо строку и столбец одновременно (если ai = bj). Из оставшейся части таблицы вновь выбирают клетку с наименьшей стоимостью. Процесс заполнения транспортной таблицы (4.2) продолжают до тех пор, пока все запасы продукции на предприятиях не будут распределены и удовлетворен спрос потребителей, т.е. пока не будут выполнены балансовые условия (4.2), (4.3).

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

 

Таблица 4.3 Опорный план транспортной задачи

Предприятия Потребители
b1 = 15 b2 = 40 b3 = 25 b4 = 20
A1 а1 = 30        
A2 а2 = 60        
A3 а3 = 10        

 

4 П р о в е р к а о п о р н о г о п л а н а н а н е в ы р о ж д е н н о с т ь

Опорный план называется невырожденным, если количество занятых клеток в транспортной таблице (таблица 4.3) равно m+n-1.

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

Опорный план, составленный нами в таблице 4.3 – невырожденный, так как число занятых клеток равно

.

 

5 Проверк а оптималности плана методом потенциалов

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

Теорема. Если план транспортной задачи является оптимальным, то ему соответствует система из m+n чисел ui и vj, удовлетворяющих условиям:

ui + vj = сi j для ,

ui + vj сi j для

(i= 1,2,…., m; j = 1,2,…, n).

Числа ui являются потенциалами строк, а vj потенциалами столбцов.

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

а) для каждой занятой клетки сумма потенциалов должна быть равна стоимости перевозки единицы продукта, стоящей в этой клетке:

ui + vj = сi j; (4.6)

б) для каждой незанятой клетки сумма потенциалов должна быть меньше или равна удельной стоимости перевозки, стоящей в этой клетке:

ui + vj сi j. (4.7)

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

Рассчитаем потенциалы для плана перевозок в таблице 4.3. Запишем условия (4.6), справедливые для занятых клеток таблицы:

u 1 + v 2=3

u 2+ v 1 =2

u 2+ v 2 =5 (4.8)

u 2+ v 3= 3

u 2+ v 4 = 9

u 3+ v 4= 3

Получили систему m + n – 1=6 уравнений с m+ n =7 неизвестными. Уравнений на одно меньше, чем неизвестных, поэтому система является неопределённой (имеет бесконечное множество решений). Потенциалы являются абстрактными объектами, т.е. не имеют физического смысла. Для проверки оптимальности плана нам важно знать их соотношения, а не точные значения. Поэтому один из потенциалов определяют произвольно, т.е. равным любому числу. Чаще всего принимают

u 1 =0,

тогда остальные потенциалы легко находятся из системы (4.8).

 

Таблица 4.4 Опорный план с расчетом потенциалов

Предприятия Потребители
b1 = 15 b2 = 40 b3 = 25 b4 = 20
A1 а1 = 30   -3   + 4  
A2 а2 = 60   10 +   - 10  
A3 а3 = 10         -4
         

 

Проверим условие оптимальности для незанятых клеток. Для клетки (1,4) условие (4.7) не выполняется, т.е.

u 1+ v4 = 0+7 >4.

Пометим эту клетку «» и будем называть «плохой».

Таким образом, опорный план не является оптимальным из-за существования «плохой» клетки. В этом случае логично заполнить эту клетку некоторой поставкой, тогда условие оптимальности (4.6) будет выполнено для нее автоматически при расчете потенциалов.

 

6 П е р е р а с п р е д е л е н и е п о с т а в о к

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

А. Строим «маршрут» перераспределения по правилам:

– начальная вершина маршрута находится в «плохой» клетке;

– все остальные вершины лежат в заполненных клетках;

– все углы маршрута – прямые.

По перечисленным правилам можно построить единственный маршрут. Он может иметь конфигурацию, квадрата, прямоугольника, многоугольника (рисунок 4.1).

Б. В вершинах маршрута расставляем знаки: «+» в начальную вершину, «-» в соседнюю, далее знаки чередуются (таблица 4.4).

 

 

В. Выбираем величину перепоставки. Она равна минимуму поставок, расположенных в клетках маршрута со знаком «-»:

.

Теперь можно построить следующий план перевозок: в вершины маршрута со знаком «+» добавляется перепоставка П, а из вершин с «-» она вычитается (таблица 4.5). Далее по известным правилам рассчитываем потенциалы строк и столбцов нового плана и проверяем его на оптимальность.

 

Таблица 4.5 План перевозок (первая итерация)

Предприятия Потребители
b1 = 15 b2 = 40 b3 = 25 b4 = 20
A1 а1 = 30   -3   + 4  
A2 а2 = 60          
A3 а3 = 10   +   - 10 -1
         

 

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

 

Таблица 4.6 План перевозок (вторая итерация)

Предприятия Потребители
b1 = 15 b2 = 40 b3 = 25 b4 = 20
A1 а1 = 30          
A2 а2 = 60          
A3 а3 = 10         -2
         

 

План, представленный в таблице 4.6, удовлетворяет условиям (4.6)-(4.7) и, следовательно, является оптимальным.

 

7 З а п и с ь о п т и м а л ь н о г о п л а н а и вычисление

минимальной стоимости перевозок

Оптимальный план перевозок. От предприятия A1 10 единиц продукцииследует доставить потребителю B2 и 20 единиц – потребителю B4. От предприятия A2 15 единиц продукции нужно перевезти потребителю B1, 20 единиц – потребителю B2, 25 единиц – потребителю B3. От предприятия

A3 груз должен поступить потребителю B2 в количестве 10 единиц.

Минимальная суммарная стоимость перевозок

3·10 + 20·4 +15·2 + 20·5 + 25·3 +10·1 = 325 (денежных единиц).

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

Таблица 4.7 Исходные данные к задаче 4.2

Поставщики Потребители
b1 = 50 b2 = 100 b3 = 150 b4 = 200
A1 а1 = 50        
A2 а2 = 300        
A3 а3 = 100        

 

РЕШЕНИЕ.

1 Проверим условие замкнутости

.

Условие замкнутости не выполняется (открытая транспортная задача), поэтому в таблицу 4.7 вводим строку фиктивного поставщика с запасом продукции

.

В фиктивную строку записываем нулевые удельные стоимости поставок (таблица 4.8).

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

Суммарная стоимость перевозок:

.

Балансовые условия:

;

;

;

;

;

;

;

.

3 Составим опорный план методом минимального элемента (таблица 4.8)

Таблица 4.8 Опорный план по методу минимального элемента в строке

Поставщики Потребители
b1 = 50 b2 = 100 b3 = 150 b4 = 200
A1 а1 = 50        
A2 а2 = 300        
A3 а3 = 100        
AФ аФ = 50        

4 Проверим опорный план на невырожденность..

Опорный план – вырожденный, так как число занятый клеток

.

5 Проверим оптимальность плана методом потенциалов.

Для выполнения условия невырожденности плана не хватает двух заполненных клеток. Поэтому в клетки (3,1) и (4,2) запишем нулевые поставки и будем считать их занятыми. Теперь можно вычислить потенциалы строк и столбцов (таблица 4.9).

Таблица 4.9 Расчет потенциалов опорного плана

Поставщики Потребители
b1 = 50 b2 = 100 b3 = 150 b4 = 200
A1 а1 = 50          
A2 а2 = 300          
A3 а3 = 100 - 0 100 +      
AФ аФ = 50 + 0 -      
  -2 -2 -4  

План неоптимальный, так как для клетки (4,1) не выполняется условие оптимальности, т.е.

u 4+ v1 = 1+2 >0.

 

6 Выполним перераспределение поставок.

Для клетки (4,1) строим маршрут перераспределения; в вершинах маршрута чередуются знаки «+» и «-» (таблица 4.9). Величина перепоставки равна нулю. Перепоставку вычитаем из клеток с «-» и прибавляем к клеткам с «+». Новый план перевозок представлен в таблице 4.10.

 

Таблица 4.10 Оптимальный план перевозок

Поставщики Потребители
b1 = 50 b2 = 100 b3 = 150 b4 = 200
A1 а1 = 50          
A2 а2 = 300          
A3 а3 = 100 - 0        
AФ аФ = 50           -1
  -2   -1  

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

7 Запишем оптимальный план перевозок.

От поставщика A1 50 единиц груза следует направить потребителю B1. От поставщика A2 100 единиц груза нужно перевезти потребителю B3, 200 единиц – потребителю B4. От поставщика A3 груз должен поступить потребителю B2 в количестве 100 единиц. Извне (фиктивный поставщик) 50 единиц груза следует привезти потребителю B3.

Минимальная суммарная стоимость перевозок

1·50 + 8·100 +6·200 +0·4 + 1·100 + 0·0 + 0·50 = 2150.

 




Поделиться с друзьями:


Дата добавления: 2014-11-18; Просмотров: 2262; Нарушение авторских прав?; Мы поможем в написании вашей работы!


Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет



studopedia.su - Студопедия (2013 - 2024) год. Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав! Последнее добавление




Генерация страницы за: 0.011 сек.