Главная Случайная страница


Полезное:

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


Категории:

АрхитектураАстрономияБиологияГеографияГеологияИнформатикаИскусствоИсторияКулинарияКультураМаркетингМатематикаМедицинаМенеджментОхрана трудаПравоПроизводствоПсихологияРелигияСоциологияСпортТехникаФизикаФилософияХимияЭкологияЭкономикаЭлектроника






Распределительный метод решения транспортной задачи





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

D41 = 6 – 5 + 4 – 3 + 1 – 2 = 1.

Если все Dij неотрицательны (Dij ³ 0), то задача решена, т.е. найден оптимальный план перевозок.

Допустим, есть хотя бы одно отрицательное значение Dij, тогда среди отрицательных Dij выбираем наименьшее и для этой клетки i0, j0 делаем сдвиг по циклу пересчета на величину q0, равную наименьшей из перевозок, стоящих в отрицательных вершинах цикла. Полученный новый опорный план будет лучше предыдущего, при этом целевая функция уменьшится на величину q0 × .

Замечания:

1. Каждая сумма Dij начинается с положительного числа и кончается отрицательным. Количество всех слагаемых четное.

2. Если опорный план вырожденный, то возможен сдвиг по циклу пересчета на величину q = 0. При этом значение целевой функции не изменится, а изменятся базисные клетки.

Найдем решение задачи, первоначальный опорный план которой получен методом северо-западного угла, и введем дополнительное условие: груз из пункта А2 в пункт В3 не может быть доставлен:

 

  В1 В2 В3 В4   Для всех свободных клеток вычислим Dij: D13 = 2 – 1 + 3 – 4 = 0, D14 = 5 – 1 + 2 – 1 + 3 – 4 = 4, D21 = 6 – 5 + 4 – 1 = 4, D23 = М – 1 + 3 – 1 = М + 1, D24 = 3 – 1 + 2 – 1 + 3 – 1 = 5,
А1 - 20 5 + 10 4 2 5  
А2 6 70 1 М 3  
А3 + 2 q - 3 1 40 8  
А4 6 3 30 2 1  
           

D31 = 2 – 3 + 4 – 5 = -2, D34 = 8 – 1 + 2 – 1 = 8,

D41 = 6 – 5 + 4 – 3 + 1 – 2 = 1, D42 = 3 – 3 + 1 – 2 = -1.

Поскольку не все Dij ³ 0, план перевозок неоптимален. Среди Dij < 0 выбираем наименьшее. Это D31 = -2. Делаем сдвиг по циклу пересчета для свободной клетки (3,1) на величину q0. Этот цикл проходит через базисные клетки (1,1), (1,2) и (3,2). В этом цикле две отрицательные клетки (1,1) и (3,2). Им соответствуют перевозки 20 и 10. В качестве q0 выбираем меньшее из этих чисел, т.е. q0 = 10. После сдвига по циклу пересчета на величину q0 переходим к следующему опорному плану:

  В1 В2 В3 В4   Делаем второй шаг распределительного метода. Находим значения Dij для всех свободных клеток D13 = 2 – 5 + 2 – 1 = -2, D14 = 5 – 1 + 2 – 1 + 2 – 5 = 2, D21 = 6 – 5 + 4 – 1 = 4, D23 = М – 1 + 4 – 5 + 2 - 1 = = М – 1 >> 0,
А1 - 10 5 20 4 + q 2 5  
А2 6 70 1 М 3  
А3 + 2 10 3   - 1 40 8  
А4 6 3 30 2 70 1  
           

 

D24 = 3 – 1 + 4 – 5 + 2 – 1 + 2 – 1 = 3,

D32 = 3 – 4 + 5 – 2 = 2,

D34 = 8 – 1 + 2 – 1 = 8,

D41 = 6 – 2 + 1 – 2 = 3,

D42 = 3 – 4 + 5 – 2 + 1 – 2 = 1.

 

f(х) = 10 × 5 + 20 × 4 + 70 × 1 + 10 × 2 + 40 × 1 + 30 × 2 + 70 × 1 = 390.

 

Делаем сдвиг по циклу пересчета для свободной клетки (1,3) на величину q0 = 10. Переходим к новому опорному плану:

 

  В1 В2 В3 В4   Найдем Dij для этой таблицы D11 = 5 – 2 + 1 – 2 = 2, D14 = 5 – 2 + 2 – 1 = 4, D21 = 6 – 1 + 4 – 2 + 1 – 2 = 6, D23 = М – 2 + 4 – 1 = М + 1, D24 = 3 – 1 + 4 – 2 + 2 – 1 = 5, D32 = 3 – 4 + 2 – 1 = 0, D34 = 8 – 1 + 2 – 1 = 8,
А1 5 - 20 4 + 10 2 5  
А2 6 70 1 М 3  
А3 10 2 3 30 1 8  
А4 6 + 3 q - 2 30 1 70  
           

 

D41 = 6 – 2 + 1 – 2 = 3, D42 = 3 – 4 + 2 – 2 = -1.

 

f(х) = 20 × 4 + 10 × 2 + 70 × 1 + 20 × 2 + 30 × 1 + 30 × 2 + 70 × 1 = 370.

 

Делаем сдвиг по циклу пересчета для свободной клетки (4,2) на величину q0 = 20. Переходим к новому опорному плану:

 

  В1 В2 В3 В4   Определим значения Dij D11 = 5 – 2 + 1 – 2 = 2, D12 = 4 – 2 + 2 – 3 = 1, D14 = 5 – 1 + 2 – 2 = 4, D21 = 6 – 1 + 3 – 2 + 1 – 2 = 5, D23 = М – 1 + 3 – 2 = М >> 0, D24 = 3 – 1 + 3 – 1 = 4,
А1 5 4 30 2 5  
А2 6 70 1 М 3  
А3 20 2 3 30 1 8  
А4 6 20 3 10 2 70 1  
           

 

D32 = 3 – 3 + 2 – 1 = 1, D34 = 8 – 1 + 2 – 1 = 8, D41 = 6 – 2 + 1 – 2 = 3.

f(х) = 30 × 2 + 70 × 1 + 20 × 2 + 30 × 1 + 20 × 3 + 10 × 2 + 70 × 1 = 350.

Для этого плана все Dij > 0. Следовательно, этот опорный план оптимальный.

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

Для решения транспортной задачи можно использовать метод потенциалов. Пусть задан опорный план задачи, тогда каждому пункту отправления Аi приписывается некоторое число Ui, а каждому пункту назначения Вj – число Vj. Эти числа называют потенциалами, они подбираются так, чтобы для каждой базисной клетки (i, j) выполнялось равенство Ui + Vj = Cij.

Таким образом, получаем m + n – 1 простых уравнений с m + n неизвестными Ui и Vj. В таком случае, когда система состоит из числа уравнений, меньшего, чем число неизвестных, появляется свободная неизвестная величина, которой мы можем придать любое значение. Все остальные неизвестные можно найти из системы уравнений.

После того, как будут найдены все потенциалы Ui и Vj, для каждой свободной клетки (i, j) определяют числа Dij = Cij -(Ui + Vj). Далее поступаем так же, как и в распределительном методе: находим наибольшее по модулю отрицательное число (т.е. самое малое из отрицательных) и делаем сдвиг по соответствующему циклу пересчета. Таким образом, в методе потенциалов для нахождения чисел Dij не нужно искать циклы пересчета для всех свободных клеток. Надо найти только один цикл пересчета, соответствующий наименьшему отрицательному .

Пример решения задачи методом потенциалов:

 

  V1 = 5 V2 = 4 V3 = 2 V4 = 1   U1 + V1 = 5, U1 + V2 = 4, U2 + V2 = 1, U3 + V2 = 3, U3 + V3 = 1, U4 + V3 = 2, U4 + V4 = 1.
U1 = 0 20 5 10 4 2 5  
U2 = -3 6 70 1 1 3  
U3 = -1 2 10 3 40 1 8  
U4 = 0 6 3 30 2 70 1  
           

 

Положим U1 = 0, тогда

V1 = 5, V2 = 4, U2 = -3, U3 = -1, V3 = 2, U4 = 0, V4 = 1.

Подсчитаем Dij для свободных клеток:

D13 = 2 – (0 + 2) = 0, D23 = 1 – (-3 + 2) = 2, D34 = 8 – (-1 + 1) = 8,

D14 = 5 – (0 + 1) = 4, D24 = 3 – (-3 + 1) = 5, D41 = 6 – (0 + 5) = 1,

D21 = 6 – (5 - 3) = 4, D31 = 2 – (-1 + 5) = -2, D42 = 3 – (0 + 4) = -1.

 

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

Этапы метода потенциалов:

1. Найти первоначальный опорный план. Число заполненных клеток равно m + n – 1.

2. Найти потенциалы Ui и Vj. Составить для базисных клеток m + n – 1 уравнений с m + n неизвестными.

3. Для каждой свободной клетки найти значения Dij = Cij -(Ui + Vj). Если среди значений Dij нет отрицательных, то полученный план транспортной задачи оптимальный. Если же такие имеются, то перейти к новому опорному плану.

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

5. Полученный опорный план проверить на оптимальность. Если он неоптимален, то перейти к п. 2.

 

 

Date: 2015-07-24; view: 653; Нарушение авторских прав; Помощь в написании работы --> СЮДА...



mydocx.ru - 2015-2024 year. (0.006 sec.) Все материалы представленные на сайте исключительно с целью ознакомления читателями и не преследуют коммерческих целей или нарушение авторских прав - Пожаловаться на публикацию