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

Третья строка: с₃₂ = 2 , с₃₁ = 9, с₃₁ – с₃₂ = 9 – 2 = 7 .

Первый столбец: c₂₁ = 4 , с₃₁ =9, с₃₁ – c₂₁ = 9 – 4 = 5.

Второй столбец: с₃₂ = 2, с₂₂ = 5, с₂₂ – с₃₂ = 5 – 2 = 3.

Максимальная разность стоит  в третьей строке. Минимальный  тариф в этой строке с₃₂ = 2, х₃₂ = min(170 -140,50) = 30.

Предложение поставщика исчерпано, и третью строку вычеркиваем.

Осталась одна строка транспортной таблицы. Это вторая строка.  
В этой строке сначала заполняем клетку с наименьшим тарифом c₂₁=4, х₃₁ =min(140,120) = 120 . Оставшееся предложение второго поставщика записываем в единственную свободную клетку х₂₂ = min(140 -120,50 –  
– 30) = 20.

Полученный по методу Фогеля план перевозок имеет вид

Затраты на перевозку по этому плану составляют

S₃ = 50*1 + 110*2+120*4+20*5+30*2+140*3=1430.

S_3< S_2< S₁.

Таким образом, для одной  и той же транспортной задачи получены различные начальные планы перевозок, построенные с использованием разных методов. При этом затраты на перевозки  уставляют соответственно: S₁ =3220, S₂ = 1530, S₃ = 1430. Метод Фогеля наиболее трудоемкий, однако начальный план перевозок, построенный с его использованием, обычно бывает близок к оптимальному плану, а в некоторых случаях является оптимальным планом.

Изложенные методы нахождения начального решения не единственные. В качестве начального решения может  быть взят любой набор чисел, удовлетворяющих  ограничениям (4.9)–(4.12) (например, полученный по методу "юго-восточного" угла). Читатель может придумать свой собственный  метод получения начального решения.

Контрольные вопросы.

1. В чем особенность  метода минимального элемента?

2. В чем особенность  метода северо-западного угла?

3. Какой метод поиска  начального решения дает лучший  результат? 

 

4.4. Оптимальный  план транспортной задачи. Метод  потенциалов

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

Определение 4.3. Если при решении транспортной задачи число заполненных клеток транспортной таблицы равно т+п-1, где т – число производителей, п – число потребителей, то план перевозок невырожденный.

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

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

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

Получение оптимального плана транспортной задачи с использованием метода потенциалов

Шаг 1. Получение начального плана перевозок по методу "северо-западного" угла, минимального элемента, Фогеля или любым другим методом.

Шаг 3. Проверка плана на невырожденность. Если полученный план вырожденный, формально заполняют нулями некоторые из свободных клеток так, чтобы общее число занятых клеток было равно т+п-1. Нули надо расставлять так, чтобы не образовался замкнутый цикл из занятых клеток. (Определение цикла будет дано чуть ниже)

Шаг 3. Проверка плана на оптимальность.

Шаг 3.1. Определение потенциалов производителей и потребителей. Составляют систему уравнений для заполненных клеток транспортной таблицы: U_i + V_j = С_ij , где i,j – номера строк и столбцов на пересечении которых стоят заполненные клетки, U_i – потенциал i-го поставщика,  
V_j – потенциал j-го потребителя, С_ij – тариф на перевозку из пункта i  
в пункт j. Число уравнений в системе равно т+п-1, а число неизвестных U_i – и V_j равно т+п. Для решения данной системы одно из неизвестных выбирают произвольно. Обычно полагают U_i = 0. Решая систему уравнений, находят значения потенциалов U_i и V_j,  ; .

Шаг 3.2. Определение суммы потенциалов (косвенных тарифов) для свободных клеток: C1_qp = U_q + V_p , где q и р – номера строк U столбцов, на пересечении которых стоит свободная клетка, U_q – потенциал q-гo поставщика, V_p – потенциал р-го потребителя, C1_qp – косвенные тарифы.  

Шаг 3.3. Проверка на оптимальность.  

Для каждой свободной клетки транспортной таблицы составляется разность между C1_qp и C_qp (косвенным и реальным тарифами) ∆ _qp =  
= C1_qp – C_qp. Если все ∆ _qp ≤ 0, то полученный план оптимален. Если хотя бы для одной свободной клетки ∆ _qp > 0, то план может быть улучшен. Переход к шагу 4.

Шаг 4. Улучшение плана.

Шаг 4.1. Выбор переменной, вводимой в список базисных переменных.

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

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

Шаг 4.2. Выбор переменной, выводимой из списка базисных переменных.

Заполнение клетки, выбранной  на шаге 4.1, происходит следующим образом. Строят цикл, начинающийся и заканчивающийся  в выбранной свободной клетке, содержащий в качестве вершин заполненные  клетки таблицы и состоящий из горизонтальных и вертикальных отрезков. При этом в каждой клетке таблицы, являющейся вершиной цикла, соединяют  обязательно горизонтальный и вертикальный отрезки. В свободной клетке условно  ставят знак "+", а в остальных  вершинах цикла, чередуясь, ставят "-" и "+". Затем происходит перераспределение  продукции по циклу. Для этого  выбирают клетку со знаком "-" , которой  соответствует наименьшее число  единиц продукции. Это значение прибавляют к значениям, стоящим в клетках  со знаком "+" , и отнимают от значений, стоящих в клетках со знаком "-" . При таком перераспределении  общий баланс не изменяется. Свободная  клетка заполняется. А клетка со знаком "-" , которой соответствует  наименьшее количество продукции, становится свободной; соответствующую ей переменную исключают из списка базисных.

Для нового плана повторяют  все действия, т. е.. переходят к  шагу 3.

Пример 4.5

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

Решение. 

В качестве начального плана  выберем план, найденный по методу минимального элемента (табл. 4.5). 

 

Таблица 4.5

Число заполненных клеток равно 4+3 -1= 6 т. е. данный план невырожденный. Определим потенциалы производителей и потребителей, составив уравнения U_i + V_j = С_ij для заполненных клеток. 

 

Составим разности для  свободных клеток

∆₁₁= (U₁ + V₁)– С₁₁ = (0+0)-7 = -7,

∆₁₂= (U₁ + V₂) – С₁₂ = (0+0)-8 = -8,

∆₁₄= (U₁ + V₄) – С₁₄ =(0+4)-2 = 2,

∆₂₂= (U₂ + V₂) – С₂₂ =(4+0)-5 = -1,

∆₂₃= (U₂ + V₃) – С₂₃ =(4+1)-9 = -4,

∆₃₁= (U₃ + V₁) – С₃₁ =(2+0)-9 = -7.

Получена положительная  разность ∆₁₄ = 3. Заполним клетку первой строки и четвертого столбца. Строим цикл, начинающийся и заканчивающийся в этой клетке. Вершинами цикла являются клетки: (3,4), (3,3), (1,3) (на первом месте стоит номер строки, на втором – столбца). В клетке (1,4) ставим "+", в клетке (3,4) "-", в клетке (3,3) "+", в клетке (1,3) "-". Перераспределяем продукцию по циклу. Минимальное значение для клеток со знакам "-" находится в клетке (3,4) х₃₄ = 90. Отнимаем 90 от значений, стоящих в клетках со знаком "-", и прибавляем к значениям, стоящим в клетках со знаком "+". Получаем новый план перевозок, представленный в следующей транспортной таблице (табл. 4.6): 

 

Таблице 4.6

 

∆₁₁= (U₁ + V₁ )– С₁₁ = -2 – 7= -9,

∆₁₂= (U₁ + V₂) – С₁₂ = 0 – 8 = -8,

∆₂₂= (U₂ + V₂) – С₂₂ = 6 – 5 = 1,

∆₂₃= (U₂ + V₃) – С₂₃ = 7 – 9= -2,

∆₃₁= (U₃ + V₁) – С₃₁ = 0 – 9= -9,

∆₃₄= (U₃ + V₄) – С₃₄ = 4 – 6= -3.

Положительная разность ∆₂₂ = 1. Заполним клетку (2,2). Цикл будет содержать клетки: (2,2), (3,2), (3,3), (1,3), (1,4), (2,4), (2,2).

Минимальное значение х₂₄ = 20 для клеток со знаком "-". Перераспределив продукцию по циклу, получим новый план перевозок, представленный в табл. 4.7.

Таблица 4.7 

 

№	1	2	3	4	Предложение
1	120           7	40        8	50        1	110           2	160
2	120                4	20         5	130     9	20              8	140
3	9	30       2	140      3	90        6	170
Спрос	120	50	190	110

 

 

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

Составляем разности

∆₁₁= (U₁ + V₁ )– С₁₁ = -1 – 7= -8,

∆₁₂= (U₁ + V₂) – С₁₂ = 0 – 8= -8,

∆₂₃= (U₂ + V₃) – С₂₂ = 6 – 9= -3,

∆₂₄= (U₂ + V₄) – С₂₃ = 7 – 8 = -1,

∆₃₁= (U₃ + V₁) – С₃₁ = 1 – 9= -8,

∆₃₄= (U₃ + V₄) – С₃₄ = 4 – 6= -3.

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

 

 

Заметим, что этот план совпадает  с начальным планом, найденным  по методу Фогеля.

Оптимальные затраты:

S* = 50*1+110*2+120*4+20*5+30«*2+140*3=1330.

Контрольные вопросы  

 

1. Что такое косвенный  тариф?

2. Как выбрать «нулевую»  точку»?

3. Почему выбираем максимальную  разность тарифов при выборе  переменной вводимой в базисные?

4. Если план вырожден, как поступать дальше? 

 

4.5. Экономические  задачи, сводящиеся  к транспортным моделям

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

 

4.5.1. Оптимальное  распределение оборудования 

 

Оборудование m-различных видов нужно распределить между        n-рабочими участками. Производительность одной единицы оборудования i-го вида на j-м рабочем участке равна p_ij;  ; . Потребность j -го участка в оборудовании составляет b_j,  . Запас оборудования i -го вида равен а_i,  . Найти распределение оборудования на рабочие участки, при котором суммарная производительность максимальная. 

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

Обозначим через х_ij число единиц оборудования i -го вида, выделенное на j -и рабочий участок,  ; . Математическая модель задачи имеет следующий вид:

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