Студопедия
Случайная страница | ТОМ-1 | ТОМ-2 | ТОМ-3
АвтомобилиАстрономияБиологияГеографияДом и садДругие языкиДругоеИнформатика
ИсторияКультураЛитератураЛогикаМатематикаМедицинаМеталлургияМеханика
ОбразованиеОхрана трудаПедагогикаПолитикаПравоПсихологияРелигияРиторика
СоциологияСпортСтроительствоТехнологияТуризмФизикаФилософияФинансы
ХимияЧерчениеЭкологияЭкономикаЭлектроника

Транспортная задача ЛП

Читайте также:
  1. C V 4 (транспортная служба управленческой группы).
  2. Адреса терминалов самообслуживания ОАО Тюменская транспортная система
  3. Билет № 26 задача № 20
  4. Билет № 26 задача № 20
  5. Билет № 37 задача № 1
  6. Билет № 37 задача № 1
  7. Важнейшая задача оптовой торговли

 

Транспортная задача (ТЗ) ЛП может быть сформулирована следующим образом. Имеет- ся m пунктов отправления (производства) A 1 ,..., Am, в которых имеется товар в количе- стве a 1 ,..., am соответственно. Кроме того, имеется n пунктов назначения (потребления) B 1 ,..., Bn, в которых имеются заявки на этот товар в количестве b 1 ,..., bn соответственно. Предполагается, что


m

 

 

i =1


 

ai =


n

 

 

j =1


 

bj,


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

Известна стоимость cij перевозки единицы товара из пункта отправления Ai в пункт по- требления Bj. Требуется составить такой план перевозок товара, при котором весь товар из пунктов производства вывезен, все заявки в пунктах потребления удовлетворены и общая стоимость перевозок минимальна.

Математическая модель ТЗ состоит в следующем. Обозначим через xij количество товара, перевозимого из Ai в Bj. Составим задачу ЛП:

 

m n

cij xij → min,

i =1 j =1

 


n

 

 

j =1

m i =1


 

xij = ai, i = 1 ,..., m,

 

xij = bj, j = 1 ,..., n, xij≥ 0, ∀i, j.


 

На практике условие баланса может не выполняться. Что делать? Если


 

m

 

 

i =1


 

 

ai>


 

n

 

 

j =1


 

 

bj, (производится больше, чем потребляется),


 

то вводим новый пункт потребления Bn +1 с запросом


 

Полагаем


 

 

bn +1 =


 

m i =1


 

ai−


 

n j =1


 

 

bj.


 

 

Если же


 

 

m i =1


 

 

ai<


 

 

n j =1


ci,n +1= 0, i = 1 ,..., m.

 

bj, (потребляется больше, чем производится),


то вводим новый пункт производства Am +1 с предложением


 

 

am +1 =


 

n j =1


 

bj−


 

m i =1


 

 

ai.


Полагаем


 

 

cm +1 ,j = 0, j = 1 ,..., n.


 

В дальнейшем будем считать, что условие баланса выполнено.

Отметим, что ранг системы ограничений ТЗ равен m + n − 1 (на 1 меньше m + n за счет

связующего условия баланса). Поэтому количество базисных переменных также равно

m + n − 1.

Исходные данные ТЗ удобно представлять в виде транспортной таблицы (ТТ), см. ниже.

 

Ai/Bj B 1 B 2 ... Bn Запасы ai
A 1 c 11 c 12 ... c 1 n a 1
A 2 c 21 c 22 ... c 2 n a 2
... ... ... ... ... ...
Am cm 1 cm 2 ... cmn am
Заявки bj b 1 b 2 ... bn ai = bj

Опорным планом ТЗ называется такое распределение объемов перевозок в ТЗ, что

– это распределение является допустимым,

– число базисных переменных (xij> 0) равно m + n− 1,все остальные (свободные) перемен-

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

нулю,

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

Метод потенциалов решения ТЗ. Основные этапы:

Этап 1. Отыскание начального опорного плана.

Этап 2. Проверка текущего опорного плана на оптимальность.

Этап 3. Переход к лучшему опорному плану.

Этап 1. Известны 2 основных метода отыскания начального опорного плана: метод северо-западного угла и метод минимальной стоимости.

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

мо, полагаем xij = 0. Поясним на примере.

 

Ai/Bj B 1 B 2 B 3 B 4 B 5 Запасы ai
A 1            
A 2            
A 3            
A 4            
Заявки bj           = 125

 

c = 1039

 

В методе минимальной стоимости каждый раз определяется максимальный объем перево- зок, соответствующий допустимой клетке таблицы с наименьшей стоимостью cij. Поясним на примере.


 

Ai/Bj B 1 B 2 B 3 B 4 B 5 Запасы ai
A 1            
A 2            
A 3            
A 4            
Заявки bj           = 125

 

c = 745

В базис ввели 7 < m + n − 1 = 8 положительных переменных. Нужно ввести еще одну переменную, равную нулю, так, чтобы не образовался цикл. Например, x 42 = 0.

Этап 2. Проверка на оптимальность В методе потенциалов вводятся в рассмотрение двойственные переменные – потенциалы ui, i = 1 ,..., m, (дополнительный столбец в матрице ТЗ) и vj, j = 1 ,..., n, (дополнительная строка в ТТ).

Для клеток, соответствующих базисным переменным, должно выполняться

 

ui + vj = cij.

 

Вначале один из потенциалов можно выбрать произвольно, например, u 1 = 0, остальные подсчитать по формуле ui + vj = cij для клеток, соответствующих базисным переменным.

 

Ai/Bj B 1 B 2 B 3 B 4 B 5 Запасы ai Потенциалы ui
A 1 + 10 148 + 225   + 9    
A 2   + 7 + 8 + 6     -3
A 3     + 10 + 8 + 7   -1
A 4 + 7 2 + 5 204 + 6 + 8   -1
Заявки bj           = 125  
Потенциалы vj              

Критерий оптимальности: если

ij = cij− (ui + vj) 0 для всех клеток ТТ,

 

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

Этап 3. Переход к лучшему опорному плану Если существует ∆ ij < 0, то переходим

к лучшему опорному плану следующим образом.

Определяем переменную, которая будет введена в базис, и переменную, которая будет из него выведена. В базис введем переменную xi 0 j 0 такую, что

i 0 j 0 = min {ij|∀i,j}.

 

Ai/Bj B 1 B 2 B 3 B 4 B 5 Запасы ai Потенциалы ui
A 1 + 10       + 9    
A 2   + 7 + 8 + 6     -1
A 3     + 10 + 8 + 7    
A 4 + 7     + 6 + 8   -1
Заявки bj           = 125  
Потенциалы vj              

c = 721 (8 + 4 5 5) · 14 = 693

 

Обозначим клетку (i 0, j 0) знаком “+”. Рассмотрим цикл, образованный этой клеткой и клетками, соответствующими базисным переменным. Припишем клеткам цикла знаки “+” и “-” так, что они чередуются при каком-либо обходе этого цикла. Вычислим

 

xi∗j∗ = Q = min {xij| клетка (i, j) отмечена “-” }.

 

Переменную xi∗j∗ выводим из базиса.

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

Пересчитываем новые объемы перевозок для элементов цикла:

xij = xij + Q, если клетка (i, j) помечена ”+”, и

xij = xij − Q, если клетка (i, j) помечена ”-”.

Для нового опорного плана определяем новые потенциалы и проверяем его на оптималь-

ность. Процесс повторяем до тех пор, пока условие оптимальности не будет выполнено.

В нашем примере меняется лишь v 2 = 6. Все ∆ ij ≥ 0. Следовательно, построенное решение

оптимально.

 

 


Дата добавления: 2015-07-08; просмотров: 227 | Нарушение авторских прав


Читайте в этой же книге: Классификация задач | Многокритериальные задачи | Графический метод решения задач ЛП | Эквивалентные постановки задач ЛП | Основы теории графов | Кратчайшие пути | Задача коммивояжера и метод ветвей и границ | Монте-Карло | Основы теории сложности вычислений | Динамическое программирование |
<== предыдущая страница | следующая страница ==>
Симплекс-метод.| Задача о назначениях

mybiblioteka.su - 2015-2024 год. (0.015 сек.)