Сделай Сам Свою Работу на 5

Метод двойного предпочтения

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

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

Пример

 
2**
6*
3*
1* 2*
  1. Заполняем клетки с двойным предпочтением :
 
   
   
   
   

2. Заполняем клетки с простым предпочтением, начиная с наименьшей стоимости.

 
 
 

 

3. Заполняем оставшиеся пустыми клетки.

 

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


4.4. Методы проверки опорного плана на оптимальность

4.4.1. Потенциалы. Критерий оптимальности плана

Итак, наша транспортная задача имеет вид:

Распишем нашу задачу в векторной форме. Для этого введем векторы

Тогда ограничения задачи (3) могут быть записаны в виде

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

Рассмотрим теперь двойственную задачу. Так как ограничений всего m + n, то и соответствующие переменные двойственной задачи обозначим так: (переменные, соответствующие первым m ограничениям) и (переменные, соответствующие последним n ограничениям). Тогда, учитывая вид векторов и вид вектора , запишем двойственную задачу в следующем виде:



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

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

можно просто полагать, скажем, .  

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

Это и позволяет проверить оптимальность любого опорного плана.

Сам алгоритм выглядит следующим образом:

  1. Один из потенциалов задается произвольно, скажем, полагается .
  2. Рассматривается система линейных уравнений вида для тех наборов индексов i , j , для которых , и находятся потенциалы и всех складов и всех пунктов потребления.
  3. Для всех остальных наборов индексов i , j (для которых ) проверяется условие

.

Если это условие выполняется для всех наборов индексов i , j , для которых , то рассматриваемый план является оптимальным. Если же, хотя бы

для одной пары , то план не оптимален.

Прежде, чем приводить пример, расскажем о том, как реализуется пункт 2 этого алгоритма, когда находятся потенциалы и . Обычно он реализуется следующим образом:

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

2. Затем рассматриваются уравнения вида для тех j , для которых

. Так как известно, то находятся для некоторого множества индексов

 

3. Для этих индексов рассматриваются уравнения вида:

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

 

4. Далее повторяются пункты 2 (движение по строкам) и 3 (движение по столбцам), пока не определятся все потенциалы.

Проиллюстрируем этот процесс примером, а заодно покажем форму записи результатов при ручном счете.

Пример

Пусть имеется три склада с запасами и четыре пункта потребления с потребностями . Коэффициенты , определяющие стоимость перевозок, заданы матрицей:

Таблица стоимостей перевозок

  Пункты потребления
Ск
ла
ды

Построим исходный опорный план методом северо-западного угла. Он имеет вид

3.1
3.9 4.2
2.8 6.3

План имеет 6=3+4-1 компонент, поэтому он является невырожденным. Заметим, что для него транспортные расходы равны .

Заготовим матрицу размером (в нашем случае размером 3´ 4), в которую впишем те коэффициенты , которые соответствуют ненулевым перевозкам нашего плана (смотрите следующую страницу).

Далее действуем следующим образом:

Полагаем .  
 
   
   
   

 

  1. Идем по строке.
, следовательно ;
, следовательно .
  1. Идем по столбцу.
, следовательно .
  1. Идем по строке.
, следовательно .
  1. Идем по столбцу.
, следовательно .
  1. Идем по строке.
, следовательно .

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

 
7
-3
  2

В ней жирным шрифтом помечены те , которые использовались для нахождения потенциалов.

Сравнивая с матрицей величин, мы видим, что условие оптимальности плана нарушено в двух местах - для и . Следовательно, построенный нами план перевозок не является оптимальным.


Дельта-метод

Рассмотрим алгоритм дельта-метода в общем виде:

 

  1. Рассмотрим таблицы приращений , полученных соответственно в результате выбора каждого столбца наименьшей стоимости и вычитания ее из всех стоимостей столбца, а также таблицу , получающихся в результате выбора в каждой строке приращений и вычитании его из всех приращений строки при условии, что строки с
нулевым приращением не рассматриваются.
  1. Заполнение проводится по столбцам, содержащим одно нулевое приращение, в клетки, содержащие его, записываются потребности, без учета величины запасов на складах. Затем уже с учетом произведенных постановок просматриваем столбцы, содержащие два нулевых и более приращений, и заполняем их, до тех пор, пока все объемы потребностей не будут закреплены за поставщиками.
  2. Подсчитываются для строк разницы между фактическими запасами и полученными для опорного “фиктивного” плана. Критерием оптимальности плана является нулевая разница по всем запасам и “фиктивным” планом. В случае положительной разницы строки называют недостаточными, в случае отрицательной разницы - избыточными, нулевыми строки называют в случае 0-разницы.

 

  1. Отмечаются столбцы, с занятыми клетками в избыточных строках. Для каждой недостаточной и нулевой строки просматриваются приращения , стоящие в отмеченных столбцах, выбирается наименьшее в строке. Эти значения показывают, какое приращение стоимости будет получено на данном шаге, если единицу потребности перезакрепить от одного поставщика к другим (избыточные и недостаточные строки). Сравнивая со значениями нулевой строки, получим два случая:

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

б) минимальное приращение больше приращений нулевой строки;

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

В случае б) составляются цепочки.

Для построения цепочки в нулевой строке в отмеченном столбце находим клетку, для которой разность меньше минимального значение , и отмечаем ее знаком “+”, в этом же столбце находим занятую клетку, стоящую в избыточной строке, и отмечаем ее знаком “-” - начало цепочки. Начиная движение по построенному звену цепочки от “-” к “+”, попадаем в нулевую строку, затем передвигаемся по нулевой строке к занятой клетке и отмечаем ее знаком “-”, далее по столбцу переходим в клетку недостаточной строки и отмечаем ее знаком “+”.

Составляем для каждой цепочки алгебраическую сумму приращения, считая их отрицательными, если они стоят в клетке, отмеченной знаком “-”, и положительными, если клетка отмечена знаком “+”. Если сумма больше минимального , то производится непосредственное распределение, если меньше, то распределение производится по цепочке.

5. Исключаем из рассмотрения отмеченные столбцы. Если занятая клетка избыточной строка стала незанятой или избыточной , то начинаем п.4. В противном случае продолжаем процесс до тех пор, пока все строки не превратятся в нулевые


4.5. Алгоритм улучшения плана

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

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

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

У нас условие выполнено в двух случаях - для и . Вообще

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

Введение в базис вектора означает, что мы должны запланировать какую-то перевозку из третьего склада в первый пункт потребления. Пусть величина этой перевозки равна q . Поставим ее в клетку, соответствующую i =3, j =1. Тогда мы получим следующий план перевозок:

3.1    
  3.9 4.2  
q   2.8 6.3

Но теперь у нас нарушился баланс запасов и потребностей - получилось, что

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

Необходимо восстановить баланс запасов и потребностей. Для этого поступают следующим образом: по ненулевым компонентам плана перевозок(включая и компоненту q ) строят циклвида столбец - строка- столбец- строка- ...- строка (см. рисунок), который начинается и кончается на компоненте q.

Теперь для восстановления баланса запасов и потребностей можно поступить очень просто: при движении по столбцу от имеющихся компонентов плана надо отнимать q, а при движении по строке - наоборот,прибавлять q. В результате получится следующий план перевозок, уже сохраняющий баланс запасов и потребностей:

2-q 3.1+q    
  3.9-q 4.2+q  
q   2.8-q 6.3

С балансом всё в порядке, но теперь у нас стало компонент плана, а должно быть . Поэтому надо выбрать q так, чтобы одна из бывших компонент обратилась в нуль, но все остальные компоненты остались положительными. Легко догадаться, что для этого q надо взять равным минимальному из тех чисел, из которых q вычитается. В нашем случае q вычитается из чисел 2; 3.9; 2.8 . Минимальное из них есть 2 и поэтому надо взять q =2.

В результате получится новый опорный план следующего вида

  5.1    
  1.9 6.2  
  0.8 6.3
в котором снова будет положенные ему компонент.

Вычисляя транспортные расходы для этого плана, мы получим , откуда видно, что по сравнению с исходным планом транспортные расходы уменьшилисьна 2 единицы.

Опишем этот процесс в общем виде.

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

величина разности максимальна.

Исходя из клетки строят цикл по ненулевым компонентам планаперевозок по маршруту столбец - строка - столбец - строка - ... - строка, который начинается и заканчивается в клетке . Мы не будем доказывать следующие два утверждения:

- такой цикл всегда может быть построен;

- такой цикл единственный.

Итак, пусть этот цикл имеет вид

Установим новый планперевозок вида

Все остальные компоненты плана перевозок, не входящие в цикл, остаются неизменными.

Наконец, выберем q таким образом, чтобы одна из новых компонент плана обратилась в нуль, а все остальные остались положительными. Для этого q следует взять в виде ,

где считается .  

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

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

выполнялось условие и поэтому

Для нового плана перевозок мы имеем


В выражении, стоящем в квадратных скобках, большинство слагаемых сокращается и окончательно получаем

так как мы вводим перевозку, для которой .  

Ну, а дальнейшее очевидно: надо повторять все итерации до тех пор, пока не будет получен оптимальный план. В силу конечности числа вершин допустимой области, это может быть сделано за конечное число шагов.J

Закончим наш учебный пример. Одну итерацию мы уже проделали.

Вторая итерация
Этап 1

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

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

 
7
-3 -1
-1

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

Затем оставшиеся клетки заполняются суммами соответствующих

потенциалов, то есть величинами .  

Наконец, производится сравнение получившейся таблицы с таблицей

величин и определяются те клетки, где .

Этап 2

Из тех пар индексов, где , находится та пара, где разность максимальна (в нашем случае это пара i =1, j =3). Строится цикл, определяется q и строится новый опорный план.

В нашем случае эти преобразования имеют следующий вид:

  5.1-q q         5.1  
  1.9+q 6.2-q   Þ   1.1  
  0.8 6.3     0.8 6.3

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

,

то есть на 15.3 единицы.

Следующая итерация дается без пояснений.

Третья итерация
Этап 1

  -1
-1
-1

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

Для этого плана перевозок значение транспортных расходов

.

По сравнению с исходным планом, полученным методом северо-западного угла, транспортные расходы уменьшились на 17.3 единицы, то есть на 21%.

Теперь мы в состоянии доказать одну интересную теорему

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

Доказательство

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

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


Снятие вырожденности

Эпсилон-прием

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

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

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

с некоторым e >0. Можно взять e конкретным, но достаточно малым числом, а можно просто оставить в алгебраическом виде как букву. Затем транспортная задача решается обычным путем, а в ответе просто полагается e =0, (или полученный результат округляется, если e было взято конкретным малым числом).

Проиллюстрируем этот прием на конкретном примере.

Пример

Пусть матрица стоимостей перевозок имеет вид:

Запасы складов равны . Потребности пунктов
потребления равны .

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

Чтобы снять намечающееся вырождение, будем решать задачу с теми же

самыми , но с

Дальнейшее дается с минимальными пояснениями.

Построение исходного опорного плана.

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

2+e    
  4-e 4+2e  
    4-2e 6+3e

Для этого плана значение функции потерь равно

Первая итерация

Этап 1
Определение потенциалов и проверка оптимальности плана.

 
2 3

План не является оптимальным. Отмечены те элементы, для которых

. Для ввода в базис выбран вектор .

 

Этап 2

Строим цикл, находим q и переходим к новому опорному плану.

4-q 2+e +q       2e 6-e    
  4-e -q 4+2e +q     e  
q   4-2e -q 6+3e   4-2e     6+3e

В данном случае . Обратите внимание на то, что если бы было e =0, то построенный план имел бы всего 4 положительных компоненты, то есть он был бы вырожденным.

Вторая итерация

Этап 1

Находим потенциалы и проверяем оптимальность плана.

 
2

Полученный план снова не является оптимальным. Условие нарушается на элементе с i =2, j =4.

Цикл нарисован заранее.

Этап 2

2e -q 6-e +q       e    
  e -q q     e
4-2e +q     6+3e -q   4-e     6+2e

В данном случае . Опять-таки, если бы было e =0, то план был бы вырожденным.

Третья итерация

Этап 1

Нахождение потенциалов и проверка на оптимальность.

Соответствующая таблица приведена ниже.

 

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

Чтобы получить решение исходной задачи, надо положить e =0. Тогда мы получим:

e            
    e      
4-e     6+2e      

Найденный оптимальный план имеет всего 4 компоненты, то есть он является вырожденным. Для него значение транспортных потерь равно

то есть значение транспортных издержек уменьшилось по сравнению с планом, построенным по методу северо-западного угла , на 4 единицы. или на 9.5%


Подстановка

Еще один прием для снятия вырожденности – 0-подстановка.

Рассмотрим задачу

 

План, составленный методом северо-западного угла имеет вид:

     
   
   

 

План является вырожденным.

Рассмотрим таблицу, в которой указаны цены на перевозки, за исключением базисных компонент.

 
   
   
 

 

Удалим из рассмотрения клетки, при постановке в которые некоторых единиц возникает цикл.

 
     
     
 

 

На места, заполненные стоимостями, можно поставить некоторый объем единиц (в нашем случае 0 единиц).

Выберем минимальную стоимость и поставим нулевую перевозку .

Теперь план приобретет вид.

   
   
   

 

Чтобы не путать нулевую базисную компоненту с обычными 0, обычный 0, полученный при вычислениях будем изображать .

План примет вид

 



©2015- 2019 stydopedia.ru Все материалы защищены законодательством РФ.