Теорема о дополняющей не жестокости

Для того чтобы планы x* и y* пары двойственных задач были оптимальными необходимо и достаточно выполнение следующих условий:

; .

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

Транспортная задача. Постановка транспортной задачи по критерию стоимости в матричной форме. Закрытая и открытая модели транспортной задачи. Построение исходного опорного плана. Метод потенциалов.

Постановка ТЗ по критерию стоимости в матричной форме.

Формулировка ТЗ. В m пунктах отправления A₁, A₂, …, A_m сосредоточен однородный груз в количествах a₁, a₂, a_m. Этот груз необходимо доставить потребителям B₁, B₂, …, B_n, спрос каждого потребителя выражается в единицах b₁, b₂, …, b_n. Известна стоимость c_ij перевозки груза из i-го пункта в j-й.

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

Рассмотрим матрицу: X=[x_ij]_m´n, где x_ij – количество единиц груза, который необходимо доставить из i-го пункта отправления в j-й пункт назначения. Эту матрицу назовем матрицей перевозок, где x_ij³0.

Транспортные издержки запишем в виде матрицы тарифов: C=[c_ij].

Для наглядности ТЗ будем представлять в виде распределительной таблицы.

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

Цель ТЗ. Минимизировать общие затраты на реализацию плана перевозок.

В матричной форме ТЗ запишется:

x_ij³0

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

Теорема о существовании допустимого плана

Для того чтобы ТЗ имела допустимые планы необходимо и достаточно выполнение равенства .

Открытая и закрытая модели ТЗ

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

Открытую модель ТЗ при решении нужно привести к закрытой. Для этого в

первом случае вводят фиктивного потребителя B_n+1, спрос фиктивного потребителя равен

;

во втором случае вводят фиктивного поставщика A_m+1, тогда груз этого поставщика равен

,

и в обоих случаях затраты на перевозку равны нулю.

Теорема о ранге матрицы ТЗ

Ранг матрицы ограничений на единицу меньше числа уравнений.

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

Построение опорного плана будем производить по одним из следующих правил:

1. правило северо-западного угла;

2. правило минимального элемента;

3. метод Фогеля.

Правило 1.

Пользуясь распределительной таблицей, будем распределять груз, начиная с левой верхней клетки (1,1), двигаясь затем от нее по строке вправо или по столбцу вниз. В клетку (1,1) внесем меньшее из чисел b₁ и a₁: x₁ = min(a₁, b₁). Если a₁>b₁, то в клетку внесем b₁, и первый потребитель будет полностью удовлетворен. В дальнейшем первый столбец не рассматривается. Если a₁<b₁, то x₁₁=a₁, т.е. запас первого поставщика исчерпан, и переходим к распределению запасов второго поставщика. В клетку (2,1) вносим наименьшее из чисел a₂ и b₁-a₁ и т.д.

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

Составить план перевозок зерна из 4-х районов, в которых запасы составляют соответственно: 800, 700, 1000, 500 тыс. центнеров зерна, на три элеватора, мощность которых: 1000, 1100, 900 тыс. центнеров. Затраты на перевозку единицы груза определяются по таблице.

r (ранг матрицы) = m + n – 1 = 6, заполненных ячеек также 6, Þ план допустим.

f(x) = 3*800 + 7*200 + 2*500 + 3*600 + 5*400 + 7*500 = 12100.

Правило 2.

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

r = 6; f(x) = 2*700 + 3*1200 + 4*200 + 5*400 + 7*500 = 11300.

Правило 3.

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

f(x) = 3*100 + 4*200 + 2*700 + 4*400 + 5*800 + 7*100 = 8800

Признак оптимальности плана перевозок ТЗ выражается в теореме о потенциалах.

Теорема о потенциалах.

Если план X* = [x_ij]_mxn является оптимальным, то ему соответствует система из m+n чисел u_i* и v_j*, которые удовлетворяют следующим условиям:

Числа u_i и v_j называют потенциалами, соответственно i-го поставщика и j-го потребителя.

Из этой теоремы следуют следующие условия для оптимальности плана перевозок ТЗ:

– каждой занятой клетке распределительной таблицы соответствует сумма потенциалов, равная тарифу этой клетки: u_i+v_j=c_ij.

– каждой свободной клетке соответствует сумма потенциалов, не превышающая тарифа данной клетки: u_i+v_j£c_ij.

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

Из теоремы о потенциалах вытекает новый метод решения ТЗ – метод потенциалов.

Каждому поставщику ставится в соответствие потенциал u_i, каждому потребителю – v_j. Каждой занятой клетке будет соответствовать уравнение u_i+v_j=c_ij. Всех занятых клеток должно быть на единицу меньше числа потенциалов, поэтому система уравнений неопределенная и одному из потенциалов присваивают произвольное числовое значение (обычно 0). Подставляют это значение в систему и находят остальные потенциалы. Для исследования плана на оптимальность, для каждой свободной клетки проверяется условие u_i+v_j£c_ij. Если хотя бы одна клетка не удовлетворяет этому условию, то опорный план не оптимален и его нужно улучшить за счет загрузки этой клетки. Если таких клеток несколько, то наиболее перспективной является та, для которой разность между тарифом этой клетки и суммой потенциалов минимальна. S_ij(разность) = [c_ij – (u_i + v_j)] < 0. S_ij также является оценкой свободных клеток.

Из двух клеток (i,k) и (i,t) с соответствующими оценками S_ik=-5 и S_it=-10 наименьший потенциал имеет (i,t). Величина c_ij показывает, на сколько денежных единиц уменьшатся транспортные издержки от загрузки данной клетки единицей груза. Если для всех свободных клеток оценки S_ij³0, то такой план оптимален, причем, если S_ij>0, то план единственный, а если S_ij=0, то планов бесконечное множество, а функция цели при этих планах имеет одно и то же значение.

Если для опорного плана условие оптимальности не выполняется, то план перевозок улучшается за счет загрузки свободной клетки с отрицательной оценкой. Для наиболее перспективной свободной клетки строится замкнутый цикл с вершинами в занятых клетках. Вершинам этого цикла приписывают условно знаки: свободной клетке – «+»; следующей клетке, по или против часовой стрелке, - «-»; далее – «+» и т.д. Из поставок в клетках цикла с отрицательными знаками выбирается наименьшее количество груза, который перемещается по клеткам этого цикла: прибавляется к поставщикам в положительных вершинах и вычитается из поставок в отрицательных вершинах, поэтому баланс цикла не нарушается. Цикл представляет собой замкнутую ломаную линию, состоящую из звеньев, которые пересекаются под прямым углом. Каждое звено соединяет 2 клетки столбца или строки. Цикл включает в себя одну свободную клетку, остальные должны быть заняты. Цикл строится только для свободной клетки.