Главная Случайная страница Контакты | Мы поможем в написании вашей работы! | ||
|
Решение транспортной задачи любым способом производится на макете. Макет для применения метода потенциалов имеет следующий вид.
Основная часть макета выделена двойными линиями. Она l ×содержит k клеток. Каждая клетка в этой части обозначается символом (i, j). Например, клетка, стоящая во второй строке и первом столбце, будет обозначена (2, 1). Макет содержит в себе матрицу тарифов. Назначение строки vj и столбца ui будет выяснено в дальнейшем.
Прежде чем приступить к изложению метода, рассмотрим некоторые предварительные понятия.
Произвольную совокупность клеток в макете называют набором. Цепью называется последовательный набор клеток, в котором каждые две соседние клетки расположены в одном ряду (строке, столбце), причем никакие три клетки в одном ряду не располагаются.
Пример цепи приведен в табл.2.
Прямые, соединяющие взятые клетки, пересеклись, но так как клетку в пересечении мы не берем, правило цепи не нарушается.
Если последняя клетка цепи расположена в одном ряду с первой, то такая замкнутая цепь называется циклом. Некоторые разновидности циклов показаны в табл.3.
Теорема: Пусть в макете (или матрице) из k строк и l столбцов произвольно отмечено k + l клеток, причем kl £ k + l. В этом случае всегда можно построить цикл, вершины которого лежат в отмеченных клетках (может быть не во всех).
Замечание: Числа k и l целые, и для них не всегда будет выполнено неравенство kl £ k+l. Если одно из этих чисел - единица, это неравенство не выполняется. Например, при k =3, l =1 имеем 3 + 1 > 3·1. Однако при k =2 и l =2 будет 2+2 = 2·2, а при k и l, одновременно больших двух, неравенство всегда выполняется.
Условие kl £ k +l исключает случаи матриц с одной строкой или одним столбцом, в которых вообще цикла построить нельзя.
Доказательство: Рассмотрим минимальный возможный случай: k =2, l =2 (табл.4).
В макете надо выбрать k +l = 4, т.е. все 4 клетки. Для этого случая теорема справедлива: выбранные клетки образуют цикл.
Возьмем теперь любые k >2, l >2. Доказательство будем вести методом математической индукции.
Допустим, теорема справедлива для макета, у которого сумма строк и столбцов на единицу меньше взятых нами (k +l). Докажем, что при этом предположении теорема будет справедлива для принятых (k +l).
Первый случай. Среди отмеченных клеток имеется одна клетка, единственная в ряду (строке или столбце) (табл.5).
Откажемся от этой клетки, исключим эту строку из рассмотрения. Тогда придем к таблице, у которой строк на единицу меньше, а число столбцов сохранилось. Число строк в сумме с числом столбцов будет меньше (k +l) на одну единицу, но и число отмеченных клеток уменьшится на одну. Для этого случая можно построить цикл по принятому допущению. Этот цикл возьмем и для нашей таблицы, так как в соответствии с оговоркой вершины цикла могут быть и не вo всex отмеченных клетках.
Второй случай. Нет таких ситуаций, когда клетка одна. В каждой строке (столбце) больше чем одна клетка (или нет ни одной) (табл.6).
Отметим одну клетку знаком плюс, пойдем от нее по строке, попадем в клетку, которая в другом столбце и неединственная в нем; по столбцу перейдем в другую строку, по этой строке в другой столбец и т.д. Это можно было бы продолжать до бесконечности, если бы не было конечным число отмеченных клеток. На каком-то этапе придем в строку (столбец), в которой уже были, чем будет замкнута цепь, т.е. получен цикл.
Выше было показано, что теорема справедлива для k =2, l =2, т.е. для k+l =4. По доказанному она справедлива для случаев: k+l =5, т.е. k+l >4; k+l =6, т.е. k+l >5; k+l >6 и т.д., т.е. для любого макета.
Допустимый план Х (xij) называется ациклическим (нециклическим), если набор клеток с отличными от нуля компонентами плана xij >0 не содержит ни одного цикла.
Пример ациклического плана приведен в табл.7,
где точки обозначают клетки, в которых xij >0 (xij <0 недопустимы по смыслу задачи). Как покажем ниже, среди ациклических планов есть оптимальный.
Если в ациклическом плане Х (xij) число положительных компонентов
N = k + l - 1 (остальные компоненты - нули), то элементы a ij матрицы тарифов из набора клеток, в которых расположены xij >0, будем называть Х -отмеченными.
Если же число положительных компонент плана N < k + l - l, то к клеткам, занятым положительными xij добавляем недостающие до (k+l -1) из нулевых клеток, лишь бы присоединенные клетки вместе с уже взятыми не допускали циклов. Тарифы aij всех взятых клеток, равно как и сами клетки, включаются в число Х -отмеченных.
Больше (k + l - 1) число компонент ациклического плана не может быть: , так как уже при N=k+l по доказанной выше теореме всегда из выбранных клеток можно построить цикл.
Теорема 2 (основная теорема): Если для некоторого плана Х= (xij) l транспортной× k задачи можно подобрать систему из k +l чисел u1, u2,…, ui,…, uk; vl, v2,…, vj,…, vl, удовлетворяющую следующим условиям: vj £ ui-aij для всех i = 1, 2,., k; j = 1, 2,., l, а для xij >0 (xij (- X)) vj - ui = aij, то план Х будет оптимальным.
Числа ui, vj называются потенциалами пунктов отправления и пунктов назначения; условия v= £ ui-aij и vj - ui = aij называют условиями потенциальности плана Х.
К каждой клетке (i, j) относятся два потенциала: i -ro пункта отправления ui и j -ro пункта назначения vj. Условия потенциальности словесно можно сформулировать так: разность потенциалов для всех без исключения клеток должна быть меньше или равна тарифу, а для занятых (Х- отмеченных) клеток она должна быть точно равна тарифу. План, удовлетворяющий этим условиям, называется потенциальным.
С учетом такой терминологии основную теорему можно изложить короче: если некоторый план транспортной задачи потенциален, то он оптимален.
Доказательство: Допустим, что для некоторого плана Х (xij) условия потенциальности выполнены, т.е. существует такая система чисел ui и vj, которая удовлетворяет условиям vj - ui = aij и vj £ ui - aij (табл.8).
Иными словами, пусть план Х потенциален. Докажем, что этот план будет оптимальным. План Х дает значение функционалу
.
Так как мы еще не знаем, оптимален план Х или нет, то возьмем заведомо оптимальный ij ¢ план Х' (x и посмотрим, какое значение он доставляет функционалу):
(транспортные расходы минимальны). Выполняются ли условия потенциальности для плана Х' - неизвестно, но каждой клетке (i, j) макета 8, исходя из потенциальности плана Х, соответствует неравенство vj £ ui- aij или, наоборот, aij ≥ vj - ui. Возьмем из каждой клетки макета соответствующий х'ij, умножим его на левую и правую части последнего неравенства и сложим. Получим неравенство
.
Двойную сумму в правой части обозначим для краткости буквой S:
,
ее можно переписать в виде разности двух двойных сумм:
.
Преобразуем эти суммы следующим образом. Первая из них в развернутом виде дает
или .
Аналогично вторую двойную сумму можно записать так:
.
Тогда равенство запишется в иной форме: .
Но есть сумма компонент плана по j-му столбцу, она равна потребности j -ro пункта назначения .
Аналогично есть сумма компонент плана, взятая по i -й строке, она равна запасам в i -м пункте отправления .
Эти равенства сумм компонент по строке и столбцу соответственно запасам и потребностям будут выполняться для любого допустимого плана, в том числе и для взятого в самом начале плана Х (xij):
Поэтому для любых допустимых планов будем иметь
и в написанном выше равенстве суммы x можно заменить соответствующими суммами xij:
Теперь вернемся к форме записи .
В плане Х (xij) по условию его потенциальности для каждой положительной компоненты xij > 0 выполняется равенство vj - ui = aij.
Остальные компоненты плана равны нулю, и соответствующие слагаемые в сумме обратятся в нули. Поэтому полученная сумма будет равна
.Подставляя в ,приходим к неравенству или zmin ≥ zX. Иными словами, транспортные расходы по плану Х меньше или равны минимальным расходам. Но меньше минимальных они быть не могут, остается только равенство zX = zmin. План Х доставляет минимальные издержки, т.е. он оптимален, что и требовалось доказать.
Таким образом, если план потенциален, то он оптимален. Это и является тем критерием, по которому судят об оптимальности плана.
Справедливо и обратное положение: если план оптимален, то он о6язательно потенциален. Это условие (необходимость) принимается без доказательства.
Дата публикования: 2015-03-26; Прочитано: 234 | Нарушение авторского права страницы | Мы поможем в написании вашей работы!