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

Пример 4.2

Читайте также:
  1. I) Эффективность военных преобразований 1860-1870-х годов на примере Русско-японской войны.
  2. I. Примерный перечень вопросов рубежного контроля.
  3. II. Примерный перечень вопросов к зачету (экзамену) по всему курсу.
  4. III. РАЗЛИЧНЫЕ СХЕМЫ УПРАВЛЕНИЯ ГОСУДАРСТВЕННОЙ СОБСТВЕННОСТЬЮ: ПРИМЕРЫ ИЗ ИСТОРИЧЕСКОГО ОПЫТА И ЗАРУБЕЖНОЙ ПРАКТИКИ
  5. Look at the family tree and complete the sentences as in the example (Посмотри на семейное древо и заполни пропуски как в примере).
  6. Lt;question>Выберите правильный пример аннотации.
  7. XVI. Переведите на калмыцкий язык, заменяя подчеркнутые слова предложенными примерами.

Вопросы к экзамену

по дисциплине «Методы оптимальных решений»

25-26 Меркулиньо

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

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

Сущность метода состоит в том, что для каждой строки и каждого столбца таблицы (матрицы) определяются потенциалы (числа), с помощью которых устанавливается необходимость заполнения свободных клеток. Потенциалы определяются по заполненным клеткам. Элемент таблицы (расстояние между поставщиками и потребителями) равен сумме потенциалов строки и столбца, на пересечении которых эта клетка находится: Сij = Ui + Vj, (2.4)

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

потенциал строки Ui = Cij - Vj, (2.5)

столбца Vj = Cij - Ui. (2.6)

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

Рассмотрим исходный план, полученный способом наименьшего элемента по строке, представленный в табл. 2.5. Для строки П1 принимаем потенциал, равный 0. Затем для двух заполненных клеток определяем потенциалы столбцов: М1 V1 = C11 – U1 = 6 – 0 = 6,

М2 V2 = C12 – U1 = 5 – 0 = 5.

Таблица 2.5

Поставщик и его запас Потребитель и его потребность Потенциал строки Ui
М1 М2 М3 М4 М5
         
П1   (1) (3) Сijaij 8      
П2   (2)   (2) (3)   -2
П3       (1)   (3) -1
Потенциал столбца Vj              

По потенциалу столбца М1 рассчитываем потенциал строки П2, т.к. в ней находится заполненная клетка, имеющая потенциал в своем столбце: U2 = С21 – V1 = 4 – 6 = -2.

 

Потенциал строки П2 позволяет по двум заполненным клеткам определить потенциалы столбцов М3 V3 = C23 – U2 = 6 – (-2) = 8,

М4 V4 = C24 – U2 = 5 – (-2) = 7.

Потенциал для строки П3 рассчитывается по заполненной клетке в столбце М3

U3 = С33 – V3 = 7 – 8 = -1, по которому определяется потенциал столбца М5

V5 = C35 – U3 = 10 – (-1) = 11.

Объем транспортной работы при этом распределении составит:

F = 1*6 + 3*5 + 2*4 +2*6 + 3*5 + 1*7 + 3*10 = 93 т-км.

Для определения оптимальности плана или необходимости его улучшения определяем сумму потенциалов строк и столбцов в свободных клетках и проставляем их в левом нижнем углу табл. 2.5.

При решении задач на минимум целевой функции F не заполняются свободные клетки, в которых сумма потенциалов Сij меньше элемента аij. (на максимум – больше элемента), т.е. Сij – (Ui + Vj) – положительна (отрицательна).

В плане (табл. 3.5) четыре клетки имеют суммы потенциалов меньше величины элементов, в двух (П1М3 и П1М4) - равны элементам и в двух (П1М5 и П2М5) больше.

Поскольку задача решается на минимум транспортной работы, то должны заполняться клетки, в которых сумма потенциалов больше элемента, при этом объем работы уменьшится на величину равную произведению характеристики клетки П1М5: C15 – (U1 + V5) = 6 – 11 = -5 на записываемую в нее величину. Для этой клетки строится цепь перераспределения (рис. 2.6)

- П1М1 + П1М5

 
 

 

(2)

 

- П2М3 - П1М2 + П1М5

       
     
     
       

 

(3)

 

 

(2)

 

 

 

 

 

(1)

 

+ П2М1

 

       
     
     
       

 

 

+ П3М3 - П3М5 + П3М2 -- П3М5

Рис. 2.6. Рис. 2.7.

Наименьшая величина из отрицательных величин, которую можно записать в свободную клетку, равна 1, при этом целевая функция уменьшится на D = 5*1 = 5 т-км. Изменение произойдет в 5 клетках. Приняв потенциал для строки П1 = 0, вычислим остальные потенциалы и суммы потенциалов (табл. 2.6), которые в трех клетках (П2М2, П2М5, П3М2) выше величины элемента.

Таблица 2.6

Поставщик и его запас Потребитель и его потребность Потенциал строки Ui
М1 М2 М3 М3 М4
         
П1     (3)     (1)  
П2   (3)   (2) (3)    
П3       (1)   (2)  
Потенциал столбца Vj              

Наибольшую отрицательную характеристику имеет клетка П3М2: Н32 = 6 - 9 = -3, которую нужно заполнить в первую очередь по цепи (рис. 2.7).

Таблица 2.7

Поставщик и его запас Потребитель и его потребность Потенциал строки Ui
М1 М2 М3 М3 М4
         
П1     (1)     (3)  
П2   (3)   (1) (3)    
П3     (2) (2)      
Потенциал столбца Vj              

В свободную клетку записывается 2, при этом объем работы уменьшится на D = 2*3 = 6 т-км. Перераспределение приведено в табл. 2.7.

После перераспределения F = 1*5 + 3*6 + 3*4 +1*6 + 3*5 + 2*6 + 2*7 = 82 т-км.

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

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

Таким образом, алгоритм метода состоит из следующих этапов:

1. Cоставляется исходный допустимый план с m+n-1 заполненными клетками.

2. По элементам заполненных клеток определяют потенциалы строк Ui = Cij - Vj и столбцов Vj = Cij - Ui.

Первый потенциал строки или столбца принимается равным 0, остальные определяют путем вычитания из элемента заполненной клетки Cij потенциала строки Ui или столбца Vj.

3. Для свободных клеток определяется сумма потенциалов строк и столбцов Cij = Ui + Vj.

4. Путем сравнения суммы потенциалов с величиной элемента клетки выявляют клетку, заполнение которой приведет к улучшению плана на наибольшую величину, т.е. для которой величина Сij - (Ui + Vj) равняется наименьшему отрицательному числу, и строят для нее цепь.

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

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

Кроме рассмотренных методов решения транспортной задачи существуют методы:

- расчета планов перевозок в сетевой форме,

- условно-оптимального распределения,

- аппроксимации.

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

1) суммарные запасы поставщиков превышают суммарные потребности потребителей

,

2) суммарные потребности потребителей превышают суммарные запасы поставщиков

.

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

В первом случае для сохранения баланса в матрицу вводится фиктивный потребитель, т.е. столбец, в котором отражается избыток запасов (табл. 2.8): bn+1 = = 16 – 15 = 1.

Показатели Cij (расстояния) обычно принимаются равными нулю. При решении преобразованной задачи изложенными матричными методами клетки фиктивного потребителя заполняются не в начале (хотя Ci j в них минимальные), а в конце распределения. В табл. 2.8 показан оптимальный план распределения, в котором избыток запасов имеет поставщик П3, запасы остальных поставщиков распределены полностью.

Таблица 2.8

Поставщик И его запас Потребитель и его потребность
М1 М2 М3 М3 М4 Ф(bn+1)
           
П1     (1)     (3)  
П2   (3)   (2) (3)    
П3     (2) (1)     (1)

Во втором случае в матрицу вводится фиктивный поставщик, т.е. дополнительная строка, в которой отражается часть потребностей не обеспечиваемая наличными запасами с нулевыми Cij (табл. 2.9): аm+1 = = 15 – 14 = 1.

Заполнение клеток в этой строке производится после распределения имеющихся запасов между реальными потребителями. В табл. 2.9 показан оптимальный план распределения, в котором не удовлетворены потребности потребителя М3 на 1 т.

Таблица 2.9

Поставщик И его запас Потребитель и его потребность
М1 М2 М3 М3 М4
         
П1     (1)     (3)
П2   (3)   (1) (3)  
П3     (2) (1)    
Ф(аm+1)       (1)    

 

2) Методы нахождения начального решения транспортной задачи.

Шаг 2.Транспортную таблицу начинают заполнять с левого верхнего (северо-западного) угла. При заполнении двигаются по строке вправо и по столбцу вниз. В клетку, находящуюся на пересечении первой строки и первого столбца, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос: Если а1 < b2, то х11 = a1 и предложение первого поставщика полностью исчерпано. Первая строка вычеркивается, и двигаются по столбцу вниз. В клетку, находящуюся на пересечении первого столбца и второй строки, помещается максимально возможное число единиц продукции, разрешенное ограничениями на предложение и спрос: х21 =
= min(a 2 ,b1-a1). Если b 1 -a 1 <a 2то х 21 = b 1 -a 1. Спрос первого потребителя удовлетворен. Первый столбец вычеркивают и двигаются по второй строке вправо. Заполнив клетку, стоящую на пересечении второй строки и второго столбца, переходят к заполнению следующей третьей клетки второй строки, либо второго столбца. Процесс продолжают до тех пор, пока не исчерпается предложение и не удовлетворится спрос. Последняя заполненная клетка находится в последнем n -м столбце и последней m -й строке.

Пример 4.2

Определить начальное решение по методу "северо-западного" угла для транспортной задачи из примера 4.1.

Решение.

Транспортная таблица имеет следующий вид (табл. 4.2):

Таблица 4.2

        Предложение
  120 7 40 8 1 2  
  4 10 5 130 9 8  
  9 2 60 3 110 6  
Спрос          

 

В первую клетку помещают: х11 = min(160,120) = 120. Спрос первого потребителя полностью удовлетворен, первый столбец вычеркивают. Остаток сырья в первом пункте составляет: 160 – 120=40 усл. ед. Двигаемся по первой строке вправо х 21 =min(160 -120,50) = 40. Предложение поставщика исчерпано, первая строка вычеркивается. Второму потребителю не хватает 50-40=10 усл. ед. Двигаемся по второму столбцу вниз х 22 = min(140,50 – 40) = 10; Второй столбец вычеркивается. Двигаемся по второй строке вправо х 23 = min(140 -10,90) = 130. Вторая строка вычеркивается. Двигаемся по третьему столбцу вниз x33 = min(170,190 -130) = 60. Спрос третьего потребителя удовлетворен. Двигаемся по третьей строке вправо х34 = min(170 -160, 10) = 110. Таблица заполнена. Число ненулевых значений xij, , равно 6. Число базисных переменных задачи 3+4 -1=6. Остальные 3*4-6=6 переменных являются свободными, их значения равны нулю.

Начальный план перевозок имеет вид

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

S1 = 120*7+40*8+10*5+130*9+60*3+110*6=3220.

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


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


<== предыдущая страница | следующая страница ==>
РОЗДІЛ XLV| Пример 4.3

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