Теория двойственности в анализе оптимальных решений экономических задач

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

2. Назовите основные причины экономических кризисов?

3. Каковы фазы циклов и как они проявляются?

4. Виды экономических кризисов, в чем их различия?

5. Современные тенденции динамики экономических кризисов?

Теория двойственности в анализе оптимальных решений экономических задач

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

f( )= max ,	(2.18)
,	(2.19)
, j = .	(2.20)

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

Переменные двойственной задачи y_i, называют объек­тивно обусловленными оценками или двойственными оцен­ками. Модель двойственной задачи имеет вид:

g( )= min ,	(2.21)
,	(2.22)
, i = .	(2.23)

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

Двойственная задача по отношению к исходной состав­ляется согласно следующим правилам:

1) целевая функция исходной задачи (2.18)-(2.20) формули­руется на максимум, а целевая функция двойственной задачи (2.21)-(2.23 ) - на минимум, при этом в задаче на максимум все неравенства в функциональных ограниче­ниях имеют вид , а в задаче на минимум – вид ;

2) матрица А= ,

составленная из коэффициентов при неизвестных в сис­теме ограничений (2.19) исходной задачи, и аналогич­ная матрица

=

в двойственной задаче получаются друг из друга транс­понированием;

3) число переменных в двойственной задаче равно числу функциональных ограничений (2.19) исходной задачи, а число ограничений в системе (2.22) двойственной задачи - числу переменных в исходной задаче;

4) коэффициентами при неизвестных в целевой функции (2.21) двойственной задачи являются свободные члены в системе (2.19) ограничений исходной задачи, а правыми частями в ограничениях (2.22) двойственной задачи - коэффициенты при неизвестных в целевой функции (2.18) исходной задачи;

5) каждому ограничению одной задачи соответствует пере­менная другой задачи: номер переменной совпадает с номером ограничения; при этом ограничению, записан­ному в виде неравенства , соответствует переменная, связанная условием неотрицательности. Если функцио­нальное ограничение исходной задачи является равенст­вом, то соответствующая переменная двойственной зада­чи может принимать как положительные, так и отрица­тельные значения.

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

Основные утверждения о взаимодвойствен­ных задачах содержатся в двух следующих теоремах.

Первая теорема двойственности. Для взаимодвойствен­ных ЗЛП имеет место один из взаимоисключающих случаев:

1. В прямой и двойственной задачах имеются оптимальные решения, при этом значения целевых функций на оп­тимальных решениях совпадают: max f( )= min g( ).

2. В прямой задаче допустимое множество не пусто, а це­левая функция на этом множестве не ограничена сверху. При этом у двойственной задачи будет пустое допусти­мое множество.

3. В двойственной задаче допустимое множество не пусто, а целевая функция на этом множестве не ограничена снизу. При этом у прямой задачи допустимое множест­во оказывается пустым.

4. Обе из рассматриваемых задач имеют пустые допусти­мые множества.

Вторая теорема двойственности (теорема о дополняющей нежесткости). Пусть = (х₁, х₂, ..., x_п) - допустимое реше­ние прямой задачи (2.18)-(2.20), a = (y₁, y₂, ..., y_m) - допус­тимое решение двойственной задачи (2.21)-(2.23). Для того чтобы они были оптимальными решениями соответствую­щих взаимодвойственных задач, не­обходимо и достаточно, чтобы выполнялись следующие соот­ношения:

	(2.24)
j = .	(2.25)

Условия (2.24) и (2.25) позволяют, зная оптимальное решение одной из взаимодвойственных задач, найти оптимальное ре­шение другой задачи.

Рассмотрим еще одну теорему, выводы которой будут использованы в дальнейшем.

Теорема об оценках. Значения переменных y_i в опти­мальном решении двойственной задачи представляют собой оценки влияния свободных членов b_i системы ограничений-неравенств прямой задачи на величину :

.

(2.26)

Решая ЗЛП симплексным методом, мы одновременно ре­шаем двойственную ЗЛП.

Рассмотрим экономическую интерпретацию двойствен­ной задачи на следующем примере.

▼

Пример 1. (Задача оптимального использования ресур­сов). Пусть для выпуска четырех видов продукции P₁, Р₂, P₃, Р₄ на предприятии используют три вида сырья S₁, S₂ и S₃. Объемы выделенного сырья, нормы расхода сырья и прибыль на единицу продукции при изготовлении каждого вида продукции приведены в табл. 6. Требуется опреде­лить план выпуска продукции, обеспечивающий наиболь­шую прибыль.

Составим экономико-математическую модель задачи оп­тимального использования ресурсов на максимум прибыли. В качестве неизвестных примем объем выпуска продукции j-го вида х_j (j = 1,2,3,4).

Таблица 6

Модель задачи: f( )= 14х₁ + 10х₂ + 14х₃ + 11х₄ max

4х₁+2х₂+2х₃+3х₄ 35

x₁+x₂+2х₃+3х₄ 30

3х₁+x₂+2х₃+x₄ 40

x_j 0, j= 1,2,3,4.

Теперь сформулируем двойственную задачу. Пусть некая организация решила закупить все ресурсы рассматриваемо­го предприятия. При этом необходимо установить опти­мальную цену на приобретаемые ресурсы y₁, y₂, y₃ исходя из следующих объективных условий:

1) покупающая организация старается минимизировать об­щую стоимость ресурсов;

2) за каждый вид ресурсов надо уплатить не менее той суммы, которую хозяйство может выручить при перера­ботке сырья в готовую продукцию. Согласно первому условию общая стоимость сырья выра­зится величиной g( )= 35y₁ + 30y₂ + 40y₃ min. Согласно второму требованию вводятся ограничения: на единицу пер­вого вида продукции расходуются четыре единицы первого ресурса ценой y₁, одна единица второго ресурса ценой y₂ и три единицы третьего ресурса ценой y₃. Стоимость всех ре­сурсов, расходуемых на производство единицы первого вида продукции, равна 4y₁ + y₂ + 3y₃ и должна составлять не ме­нее 14, т. е. 4y₁ + y₂ + 3y₃ 14.

В результате аналогичных рассуждений относительно про­изводства второго, третьего и четвертого видов продукции получаем систему неравенств:

4y₁ + y₂ + 3y₃ 14,

2y₁ + y₂ + y₃ 10,

2y₁ + 2y₂ + 2y₃ 14,

3y₁ + 3y₂ + y₃ 11.

По экономическому смыслу цены неотрицательные: , , .

Получили симметричную пару взаимодвойственных задач. В результате решения данной задачи симплексным методом получен оптимальный план =(0;5;12,5;0); =(3;4;0).

▲

Экономический смысл первой теоремы двойственности следующий. План производства Х и набор оценок ресурсов Y оказываются оптимальными тогда и только тогда, когда прибыль от реализации продукции, определенная при из­вестных заранее ценах продукции
c₁, с₂, ..., с_n, равна затра­там на ресурсы по «внутренним» (определяемым только из решения задачи) ценам ресурсов y₁, y₂,…, y_т. Для всех же других планов и обеих задач прибыль от продукции всегда меньше (или равна) стоимости затраченных ресурсов: f( ) g( ), т. е. ценность всей выпущенной продукции не превосходит суммарной оценки имеющихся ресурсов. Зна­чит величина g(Y) - f(X) характеризует производственные потери в зависимости от рассматриваемой производственной программы и выбранных оценок ресурсов.

Из первой теоремы двойственности следует, что при оп­тимальных производственной программе и векторе оценок ресурсов производственные потери равны нулю.

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

Из второй теоремы двойственности в данном случае сле­дуют такие требования на оптимальную производственную программу = (х₁, х₂, ..., x_п) и оптимальный вектор оценок = (y₁, y₂, ..., y_m):

если yi > 0, то ; если то yi=0, i = .	(2.27)
если xj > 0, то j = ; если то xj = 0, j = .	(2.28)

Условия (2.27) можно интерпретировать так: если оценка y_i, единицы ресурса i-го вида положительна, то при опти­мальной производственной программе этот ресурс использу­ется полностью; если же ресурс используется не полностью, то его оценка равна нулю.

Из условия (2.28) следует, что если j-й вид продукции вошел в оптимальный план, то он в оптимальных оценках не убыточен; если же j-й вид продукции убыточен, то он не войдет в план, не будет выпускаться.

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

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

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

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

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

Свойство 1. Оценки как мера дефицитности ресурсов и продукции.

Свойство 2. Оценки как мера влияния ограничений на функционал.

Свойство 3. Оценки как инструмент определения эффек­тивности отдельных вариантов.

Свойство 4. Оценки как инструмент балансирования сум­марных затрат и результатов.

▼

Пример 2. (Задача о планировании выпуска тканей). Пусть некоторая фабрика выпускает три вида тканей, при­чем суточное плановое задание составляет не менее 90 м тканей первого вида, 70 м — второго и 60 м— третьего. Суточные ресурсы следующие: 780 единиц производственного оборудования, 850 единиц сырья и 790 единиц электроэнергии, расход которых на один метр ткани представлен в табл. 7.

Цена за один метр ткани вида I равна 80 денежным единицам, II — 70 денежным единицам, III — 60 денеж­ным единицам.

Таблица 7

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

Составим модель задачи. Введем следующие обозначе­ния. Неизвестными в задаче являются объемы выпуска тка­ни каждого вида:

х_i — количество метров ткани вида I;

х₂ — количество метров ткани вида II;

х_з — количество метров ткани вида III.

f( )= max ,

,

, j = , .

С учетом имеющихся данных модель примет вид:

f( )=80х₁ + 70х₂ + 60х₃ max

2х₁+3х₂+4х₃ 780

x₁+4x₂+5х₃ 850 Ограничения по ресурсам

3х₁+4x₂+2х₃ 790

х₁ 90

x₂ 70 Плановое задание

х₃ 60

В результате решения задачи симплексным методом получен следующий оптимальный план: максимум общей стоимости продукции f( )=19075 при

х₁ = 112,5м — оптимальный план выпуска ткани вида I;

x₂ = 70 м — оптимальный план выпуска ткани вида II;

х₃ = 86,25 м — оптимальный план выпуска ткани вида Ш.

Решение двойственной задачи получим с использованием теорем двойственности. Введем обозначения:

y₁ — двойственная оценка ресурса «оборудование»;

y₂ — двойственная оценка ресурса «сырье»;

y₃— двойственная оценка ресурса «электроэнергия»;

y₄— двойственная оценка ткани вида I;

y₅— двойственная оценка ткани вида II;

y₆— двойственная оценка ткани вида III.

Модель двойственной задачи имеет вид:

g( )= 780y₁ + 850y₂ + 790y₃+90 y₄+70 y₅+60 y₆ min

2y₁ + y₂ +3 y₃+ y₄ 80,

3y₁ + 4y₂ + 4y₃+ y₅ 70,

4y₁ + 5y₂ +2 y₃+ y₆ 60.

, .

Из соотношений второй теоремы двойственности выте­кают следующие условия:

для каждого ресурса:

если то y_i=0,

если y_i > 0, то

для задания по выпуску продукции:

Для нашего примера в этих соотношениях m=3 (количе­ство типов ресурсов).

Подставим значения х₁ = 112,5, х₂ = 70 и x₃ = 86,25 в ограничения прямой задачи:

2*112,5+3*70 +4*86,25 = 780,

112,5 +4*70 + 5*86,25 = 823,75 < 850,

3*112,5+4*70 +2*86,25 = 790,

112,5 > 90,

70 = 70,

86,25 > 60.

Суточные ресурсы по оборудованию и электроэнергии ис­пользованы полностью. Сырье используется не полностью, имеется остаток в размере 850 - 823,75 = 26,25 (кг). План выпуска по тканям вида I и III перевыполнен.

Из второй теоремы двойственности вытекает, что y₂, y₄ и y₆ равны нулю. Остается найти значения y₁, y₃ и y₅. Так как х₁, х₂ и х₃ — больше нуля, то все три ограничения двойст­венной задачи выполняются как равенства:

2y₁ + y₂ +3 y₃+ y₄ = 80,

3y₁ + 4y₂ + 4y₃+ y₅ =70,

4y₁ + 5y₂ +2 y₃+ y₆=60.

Учитывая, что y₂= у₄ = у₆=0 имеем:

2y₁ +3y₃ = 80,

3y₁ + 4y₃+ y₅ =70,

4y₁ +2 y₃ =60,

откуда y₁= 2,5; уз= 25; y_{5 =} -37,5.

Подставив значения неизвестных в целевую функцию двойственной задачи, проверим, выполняется ли условие f( )=g( ) для оптимального плана:
f( )=780*2,5+850*0+790*25+90*0-70*37,5+60*0 = 19075.

Условие первой теоремы двойственности выполняется, сле­довательно, рассмотренный план выпуска тканей и соответст­вующая ему система оценок ресурсов и продукции оптимальны.

Экономическое истолкование оценок есть интерпретация их общих экономико-математических свойств применитель­но к конкретному содержанию задачи. По условию (2.27) не использованный полностью в оптимальном плане ресурс по­лучает нулевую оценку. Нулевая оценка ресурса свидетель­ствует о его недефицитности. Ресурс недефицитен не из-за его неограниченных запасов (они ограничены величиной b_i), а из-за невозможности его полного использования в опти­мальном плане. Так как суммарный расход недефицитного ресурса меньше его общего количества, то план производст­ва им не лимитируется. Данный ресурс не препятствует и дальше максимизировать целевую функцию f( ).

Ограничивают целевую функцию дефицитные ресурсы, в данном примере — оборудование и электроэнергия. Они пол­ностью использованы в оптимальном плане. По условию (2.27) оценка таких ресурсов положительна (y₁= 2,5; уз= 25).

Рассмотрим теперь понятие дефицитности продукции. По условию (2.29) нулевую оценку (у₄ = 0, у₆= 0) получает продукция, задания по выпуску которой в оптимальном плане перевыполняются. Очевидно, перевыполнение плана целесообразно по выгодной продукции (ткани I и III видов), т. е. такой, производство которой способствует достижению максимума критерия оптимальности. Размеры производства такой выгодной продукции определяются не величиной за­дания на выпуск (T_j) (в оптимальном плане они перекрыты), а ограниченностью дефицитных ресурсов. Эту продукцию выпускают как можно больше, пока хватит ресурсов.

Выпуск выгодной продукции лимитируется не только фактом ограниченности дефицитных ресурсов, но и тем, что часть дефицитных ресурсов требуется выделить на обеспече­ние выпуска невыгодной продукции в соответствии с плано­выми заданиями. По условию (2.29) отрицательную оценку (y_{5 =} -37,5) получает продукция, задания по выпуску которой не перевыполняются. Так как по условию задачи ( ) плановые задания должны быть обязательно выполнены, то продукция делится на выгодную (виды I и III ткани) и не­выгодную (вид II ткани). Если в ограничение двойственной задачи, относящееся к виду II ткани:

3y₁ + 4y₂ + 4y₃+ y₅ 70,

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

3*2,5+4*0 +4*25- 37,5 = 70,

107,5 - 37,5 = 70,

т. е. стоимость ресурсов, затраченных на один метр ткани вида II, составляет 107,5 денежных единиц и это на 37,5 де­нежных единиц больше цены одного метра ткани этого вида. Таким образом, вид II ткани убыточен для фабрики: на каждом выпущенном метре ткани этого вида фабрика теряет 37,5 денежных единиц.

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

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

Влияние ограничений по выпуску продукции на критерий оптимальности противоположно влиянию ограничений по ре­сурсам. Если продукция невыгодна (вид II ткани,
y₅₌ -37,5), то увеличение плановых заданий по ее выпуску ведет к уменьшению выпуска выгодной продукции и ухудшает план. Наоборот, уменьшение плановых заданий по невыгод­ной продукции позволяет снизить ее выпуск, перебросить сэкономленные ресурсы на дополнительный сверхплановый выпуск выгодных видов продукции, что увеличивает значение целевой функции. Изменение плановых заданий по выгодной продукции не изменяет значения целевой функции.

▲

2.1.6. Транспортная задача

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

В т пунктах отправления А₁, А_{2, …,}, А_m , которые в даль­нейшем будем называть поставщиками, сосредоточено опре­деленное количество единиц некоторого однородного про­дукта, которое обозначим a_i (i = 1, 2, ..., т). Данный про­дукт потребляется в п пунктах
B₁, B_{2, …,}, B_n, которые будем называть потребителями; объем потребления обозначим b_j
(j = 1, 2, ..., n). Известны расходы на перевозку единицы продукта из пункта A_i в пункт B_j, которые равны c_ij и при­ведены в матрице транспортных расходов С = (c_ij).

Требуется составить такой план прикрепления потреби­телей к поставщикам, т.е. план перевозок, при котором весь продукт вывозится из пунктов А_i, в пункты B_j в соответ­ствии с потребностью и общая величина транспортных из­держек будет минимальной.

Обозначим количество продукта, перевозимого из пункта A_j в пункт B_j, через х_ij. Совокупность всех переменных х_ij для краткости обозначим , тогда целевая функция задачи будет иметь вид

f( )= min ,

(2.30)

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

,	(2.31)
,	(2.32)
.

Условия (2.31) означают полное удовлетворение спроса во всех пунктах потребления; условия (2.32) определяют полный вывоз продукции от всех поставщиков.

Необходимым и достаточным условием разрешимости задачи (2.30) — (2.32) является условие баланса:

(2.33)

Транспортная задача, в которой имеет место равенство (2.33), называется закрытой и может быть решена, как за­дача линейного программирования с помощью симплексного метода. Однако благодаря особенностям переменных задачи и системы ограничений разработаны специальные, менее громоздкие методы ее решения. Наиболее применяемым ме­тодом является метод потенциалов, при котором каждой i-й строке (i-му поставщику) устанавливается потенциал u_i, который можно интерпретировать как цену продукта в пункте поставщика, а каждому столбцу j (j-му потребителю) устанавливается потенциал v_j, который можно принять ус­ловно за цену продукта в пункте потребителя. В простей­шем случае цена продукта в пункте потребителя равна его цене в пункте поставщика плюс транспортные расходы на его доставку, т.е.

Алгоритм метода потенциалов для закрытой транспортной задачи детально описан в ряде учебных пособий. Первым этапом этого алгоритма является состав­ление начального распределения (начального плана перевозок); для реализации этого начального этапа имеется в свою очередь ряд методов: северо-западного угла, наименьших стоимостей, аппроксимаций Фогеля и др. Вторым этапом служат построение системы потенциалов на основе равенства (2.34) и проверка начального плана на оптимальность; в случае его неоптимальности переходят к третьему этапу, содер­жание которого заключается в реализации так называемых циклов перераспределения (корректировка плана прикреп­ления потребителей к поставщикам), после чего переходят опять ко второму этапу. Совокупность процедур третьего и второго этапов образует одну итерацию; эти итерации повторяются, пока план перевозок не окажется оптимальным по критерию (2.30).

Если баланс (2.33) не выполняется, то ограничения (2.31) или (2.32) имеют вид неравенств типа «меньше или равно»; транспортная задача в таком случае называется открытой. Для решения открытой транспортной задачи методом по­тенциалов ее сводят к закрытой задаче путем ввода или фиктивного потребителя, если в неравенства превращаются условия (2.32), или фиктивного поставщика — в случае пре­вращения в неравенства ограничений (2.31).

Рассмотрим этапы реализации метода потенциалов для закрытой транспортной задачи более подробно. Прежде всего следует отметить, что при условии баланса (2.33) ранг сис­темы линейных уравнений (2.31), (2.32) равен т + п - 1; таким образом из общего числа т п неизвестных базисных неизвестных будет т + п - 1. Вследствие этого при любом допустимом базисном распределении в матрице перевозок (таблице поставок), представленной в общем виде в табл. 8, будет занято ровно т + п - 1 клеток, которые будем назы­вать базисными в отличие от остальных свободных клеток; занятые клетки будем отмечать диагональной чертой.

Этап 1.Первоначальное закрепление потребителей за поставщиками. Рассмотрим два метода получения начального распределения (начального опорного плана): метод северо-западного угла и метод наименьших стоимостей. При каждом из этих методов при заполнении некоторой клетки, кроме последней, вычеркивается или только строка матрицы перевозок, или только столбец; лишь при заполнении последней клетки вычеркиваются и строка, и столбец. Такой подход будет гарантировать, что базисных клеток будет ровно
т + п -1. Если при заполнении некоторой (не последней) клетки одновременно удовлетворяются мощности и постав­щика, и потребителя, то вычеркивается, например, только строка, а в соответствующем столбце заполняется незанятая клетка так называемой «нулевой поставкой», после чего вычеркивается и столбец. Для идентификации клетки обыч­но в скобках указываются номера ее строки и столбца.

В методе северо-западного угла всегда в первую очередь за­полняется клетка (из числа невычеркнутых), стоящая в верхнем левом (северо-западном) углу матрицы перевозок. Пример составления начального распределения данным мето­дом показан в табл. 9: заполняется клетка (1;1) и вычерки­вается первый столбец, заполняется клетка (1;2) и вычер­кивается первая строка; заполняется клетка (2;2) и вычерки­вается второй столбец; заполняется клетка (2;3) и вычерки­вается вторая строка; заполняется клетка (3;3) и вычеркива­ется третий столбец; наконец, заполняется клетка (3:4) и вычер­киваются последние строка и столбец. Число занятых клеток равно т+п -1=3+4-1=6. Суммарные затраты на реали­зацию данного плана перевозок составят

f( )=4*30 + 5*30 +3*70 +6*30 + 7*10 +4*110 = 1170.

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

В различных модификациях метода наименьших стоимо­стей заполнение клеток матрицы перевозок проводится с учетом значений величин c_ij. Так, в модификации «двойно­го предпочтения» отмечают клетки с наименьшими стоимо­стями перевозок сначала по каждой строке, а затем по каж­дому столбцу. Клетки, имеющие две отметки, заполняют в первую очередь, затем заполняют клетки с одной отметкой, а данные о нераспределенном грузе записывают в неотме­ченные клетки с наименьшими стоимостями. При этом из двух клеток с одинаковой стоимостью перевозок предпочтение отдается клетке, через которую осуществляется больший объем перевозок. Вычеркивание строк и столбцов при заполнении клеток проводится по описанным выше прави­лам. Пример начального распределения методом наимень­ших стоимостей для тех же исходных данных, что и ранее, представлен в табл. 10.

Порядок заполнения клеток: (2;1), (3;2), (1;3), (2;4), (1;4), (3;4). Суммарные затраты на перевозки, представленные в табл. 10, составляют

f( )= 1*30+2*100+ 2*40 +2*70 + 3*20 +4*20 = 590.

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

Этап 2.Проверка оптимальности полученного плана перевозок. Введем специальные показатели u_i для каждой строки матрицы перевозок (каждого поставщика), где , и показатели v_j для каждого столбца (каждого по­требителя), где . Эти показатели называются потен­циалами поставщиков и потребителей, их удобно интерпре­тировать как цены продукта в соответствующих пунктах по­ставщиков и потребителей. Потенциалы подбираются таким образом, чтобы для заполненной клетки (i;j) выполнялось равенство (2.34). Совокупность уравнений вида (2.34), со­ставленных для всех заполненных клеток (всех базисных неизвестных), образует систему т + п - 1 линейных урав­нений с т+п неизвестными u_i и v_j. Эта система всегда со­вместна, причем значение одного из неизвестных можно задавать произвольно (например, и₁= 0), тогда значения остальных неизвестных находятся из системы однозначно.

Рассмотрим процесс нахождения потенциалов для базис­ного начального распределения по методу северо-западного угла, представленного в табл. 9. Задав и₁ = 0 и используя формулу (2.34) для заполненных клеток (1;1) и (1;2), нахо­дим v₁ = 4 и v₂ = 5. Зная v₂, по заполненной клетке (2;2) находим и₂ = 2, а зная и₂, по заполненной клетке (2;3) на­ходим v₃= 8. Зная v₃, по заполненной клетке (3;3) находим u₃ = 1, а затем по заполненной клетке (3;4) находим v₄ = 5. Результаты представлены в табл. 11, где потенциалы по­ставщиков приведены в последнем столбце, а потенциалы потребителей — в последней строке.

Таблица 11

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

Аналогичные результаты для начального распределения по методу наименьших стоимостей, приведенного в табл. 10, представлены в табл. 12.

Таблица 12

Чтобы оценить оптимальность распределения, для всех клеток (i;j) матрицы перевозок определяются их оценки, ко­торые обозначим через d_ij, по формуле:

Используя ранее принятую интерпретацию, выражение (u_i+c_ij) можно трактовать как сумму цены продукта у по­ставщика и стоимости перевозки; эта сумма путем вычита­ния сравнивается с ценой продукта у соответствующего потребителя v_j. Очевидно, оценки заполненных клеток рав­ны нулю (цена потребителя покрывает цену поставщика и стоимость перевозок). Таким образом, об оптимальности распределения можно судить по величинам оценок свобод­ных клеток. Если оценка некоторой свободной клетки от­рицательна, это можно интерпретировать так: цена, предла­гаемая соответствующим потребителем, больше суммы цены поставщика и стоимости перевозки, т.е. если бы эта клетка была занята, то можно было бы получить дополнительный экономический эффект. Следовательно, условием оптималь­ности распределения служит условие неотрицательности оценок свободных клеток матрицы перевозок.

Оценки клеток по формуле (2.35) удобно представить в виде матрицы оценок. Для ранее рассматриваемого рас­пределения, полученного методом северо-западного угла (см. табл. 11), матрица оценок клеток имеет вид

(dij)= .

(2.36)

Наличие большего числа отрицательных оценок свобод­ных клеток свидетельствует о том, что данный план перевозок далек от оптимального (напомним, что суммарные затраты на перевозку по этому плану равны 1170).

Для распределения, полученного методом наименьших стоимостей (табл. 12), матрица оценок клеток имеет вид:

(dij)= .

Так как все оценки неотрицательны, то не имеется возможности улучшить данный план перевозок, т.е. он оп­тимален (суммарные затраты на перевозку по этому плану равны 590). Кроме того, следует отметить, что в данном слу­чае оценки всех свободных клеток строго больше нуля, т.е. любой другой план, предусматривающий занятие хотя бы одной из этих клеток, будет менее оптимален. Это говорит о том, что найденный оптимальный план является единст­венным. Наличие нулевых оценок свободных клеток в опти­мальном плане перевозок, наоборот, свидетельствует о неединственности оптимального плана.

Этап 3.Улучшение неоптимального плана перевозок (циклы перераспределения). Чтобы улучшить неоптимальный план перевозок, выбирается клетка матрицы перевозок с от­рицательной оценкой; если таких клеток несколько, то обычно (но необязательно) выбирается клетка с наибольшей по абсо­лютной величине отрицательной оценкой. Например, для рас­пределения, представленного в табл. 11, такой клеткой может служить клетка (1;3) (см. матрицу оценок (2.36)).

Для выбранной клетки строится замкнутая линия (контур), начальная вершина которой лежит в выбранной клетке, а все остальные вершины находятся в занятых клетках; при этом направления отдельных отрезков контура могут быть толь­ко горизонтальными и вертикальными. Вершиной контура, кроме первой, является занятая клетка, где отрезки контура образуют один прямой угол (нельзя рассматривать как вер­шины клетки, где горизонтальные и вертикальные отрезки контура пересекаются). Очевидно, число отрезков контура, как и его вершин, будет четным. В вершинах контура рас­ставляются поочередно знаки «+» и «-», начиная со знака «+» в выбранной свободной клетке. Пример простого контура показан пунктиром в табл. 11, хотя вид контура может быть самым разнообразным (см., например, контур в табл. 14).

Величина перераспределяемой поставки определяется как наименьшая из величин поставок в вершинах контура со зна­ком «-», и на эту величину увеличиваются поставки в верши­нах со знаком «+» и уменьшаются поставки в вершинах со зна­ком «-». Это правило гарантирует, что в вершинах контура не появится отрицательных поставок, начальная выбранная клетка окажется занятой, в то время как одна из занятых клеток при этом обязательно освободится. Если величина перераспределяе­мой поставки равна поставкам не в одной, а в нескольких вер­шинах контура со знаком «-» (это как раз имеет место в контуре перераспределения в табл. 11), то освобождается только одна клетка, обычно с наибольшей стоимостью перевозки, а все другие такие клетки остаются занятыми с нулевой поставкой.

Таблица 13

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

f( )= 4*30 +5*0 +2*30 +3*100 +7*10 +4*110 = 990, что значительно меньше предыдущей суммы затрат 1170, хотя план перевозок в табл. 13 еще не является оптимальным. Об этом свидетельствует наличие отрицательных значений в матрице оценок клеток этого плана (соответствующие по­тенциалы u_i и v_j, найдены способом, изложенным при описа­нии этапа 2):

(dij)=

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

▼

Пример 4. Решим методом потенциалов закрытую транс­портную задачу, заданную в табл. 14, в которую уже внесе­но некоторое допустимое базисное распределение. Суммарные транспортные расходы составляют при этом плане перево­зок
f( )= 3*5+2*25+1*20+2*25+1*15+4*20=230. Потенциалы по формуле (2.34) находим следующим образом: задавая и₁= 0, находим по клетке (1;1) v₁ = 3, по клетке (1;2) v₂ = 2, а по клетке (1:4) v₄ = 1; затем по клетке (2;1) находим и₂ = 1 и по клетке (2;3) v₃ = 2; наконец, по клетке (3;3) находим и₃ = -2.

Матрица оценок клеток для этого плана рассчитывается по формуле (2.35):

(dij)=

Наличие отрицательных оценок свидетельствует о том, что план неоптимален. Построим контур перераспределения, например, для клетки (3;2); в табл. 14 он показан пункти­ром и его вершинам присвоены соответствующие знаки.

Наименьшая поставка в вершине контура со знаком «-» равна 20, поэтому проведем перераспределение поставок, уменьшив поставки в клетках со знаком «-» на 20 и увеличив поставки в клетках со знаком «+» также на 20; при этом клетка (3;2) заполняется, а клетка (3;3) освобождается. Новый план представлен в табл. 15; соответствующие значения потенциалов показаны в последних столбце и строке.

Матрица оценок клеток этого распределения не содержит отрицательных значений:

(dij)=

следовательно, данный план перевозок является оптималь­ным. Стоимость перевозок по этому плану равна

f( )= 3*25+2*5+1*20 +2*5+1*35+2*20 = 180.

Наличие нулевой оценки незанятой клетки (3;1) гово­рит о том, что оптимальный план не является единствен­ным. Можно отметить также, что применяя для начального распределения в этой транспортной задаче модификацию двойного предпочтения метода наименьших стоимостей, мы сразу же получили бы оптимальное распределение, пред­ставленное
в табл. 15.

▲