Постановка задачи и планы решения
Пусть [15] в пунктах A1, A2, ... ,Am производят некоторый однородный продукт в объеме ai (i=1, 2, ... , m) единиц. В пунктах B1, B2, ... ,Bn этот продукт потребляется в объеме bj
( j=1, 2, ... , n) единиц. Из каждого пункта производства {Ai} возможна транспортировка в любой пункт потребления Bj. Транспортные издержки} по перевозке из пункта Aiв пункт Bjединицы продукции равны cij (i=1, ... , m; j=1, ... , n).
Необходимо найти такой план перевозок, при котором запросы всех потребителей полностью удовлетворены, весь продукт из пунктов производства вывезен и суммарные транспортные издержки минимальны.
Пусть xij— количество продукта, перевозимого из пункта Aiв пункт Bj. Требуется найти значение переменных (перевозок) xij
 |
(5.1) |
при ограничениях
 |
(5.2) |
при условии неотрицательности
xij
и баланса
 |
(5.4) |
Как известно, условие баланса приводит к линейной зависимости уравнений в системе (5.2), ранг ее матрицы равен m+n-1.
Сформулируем задачу линейного программирования в канонической постановке, исключив из (5.2) одно уравнение. При этом мы считаем, что условие баланса (5.4) оказывает влияние на корректность постановки задачи и учтено при этой постановке. Исключенное уравнение будем использовать также для контроля получаемого решения.
Следуя плану параллельного решения задачи линейного программирования и учитывая, что оптимальное решение находится хотя бы в одной из вершин многогранника допустимых решений, образуемого ограничениями и условиями, сформируем это множество граней. В его состав войдут m+n-1 выделенных уравнений-ограничений и m ? n равенств нулю переменных на основе неотрицательности решения. Выбирая из этой системы по m ? n уравнений с обязательным участием всех выделенных уравнений-ограничений и решая их совместно, мы можем находить вершины многогранника решений.
Так мы можем реализовать метод прямого перебора. Количество вариантов составляет Cm ? nm ? n - (m + n - 1) . Это — количество различных способов приравнивания нулю m ? n-(m+n-1) переменных из их общего числа m ? n.
Мы можем реализовать и аналог симплекс-метода, найдя первоначально некоторую вершину, а затем перемещаясь по ребрам в одну из смежных вершин с большим значением целевой функции, пока это возможно.
Пусть dij — пропускная способность коммуникации (i, j), что порождает ограничение
xij
(5.18)
для всех i, j.
Тогда важная в практическом отношении задача заключается в минимизации (5.1) — целевой функции Z при ограничениях (5.2), (5.3), (5.4) и (5.18). Очевидно, что для разрешимости T -задачи должны выполняться условия
 |
(5.19) |
 |
(5.20) |
Как видим, данную задачу тоже можно решать прямым перебором вершин R с учетом резко увеличившегося числа уравнений его границ: их число, с учетом линейной зависимости, составляет теперь n+m-1+2(m? n). С учетом границ на основе условий неотрицательности решения, общее число испытываемых систем линейных уравнений составит C2(m ? n)m ? n - (m + n - 1).
Однако при этом переборе мы будем исследовать явно несовместимые варианты компоновки систем — а именно, варианты, включающие пары уравнений вида xij=0 и xij=dij. Тогда поступим иначе.
Сначала будем выбирать комбинации переменных, участвующих в формировании указанных систем линейных уравнений. Всех таких комбинаций будет Cm ? nm ? n - (m + n - 1). После выбора очередной комбинации переменных определим комбинацию их значений — 0 или значение пропускной способности. Таких комбинаций для выбранного набора m ? n - (m + n) - 1 переменных будет 2m ? n - (m + n - 1) .
Таким образом, общее число испытываемых систем линейных уравнений составит Cm ? nm ? n - (m + n - 1) ? 2m ? n - (m + n - 1) .
Воспользуемся и здесь параллельным аналогом симплекс-метода, найдя первоначально некоторую вершину многогранника решений, а затем пытаясь "переместиться" в смежную вершину с меньшим значением целевой функции.
Сделаем важное замечание. Будем считать, что если вдоль прямой, отрезком которой является исходящее из вершины L ребро, найдена смежная вершина M, то на этой же прямой, "в другую сторону" от L, нет смежных вершин. Т.е. одна прямая может связывать не более двух вершин многогранника решений. Предположим, что три вершины M, L, N лежат на одной прямой. Т.к. L — вершина, то существует хотя бы еще одно исходящее из нее ребро. Пусть оно соединяет L с вершиной K. Тогда построим плоскость, проходящую через три точки M, N, K, т.е. через точку K и прямую MN, которой принадлежит точка L. Плоскость поглотила как точку L, так и новое ребро, существование которого мы предположили.
Это означает, что если мы нашли смежную вершину "с одной стороны" по прямой, отрезком которой является исходящее ребро, то искать смежную вершину "с другой стороны" по этой же прямой не следует.
Этим предположением мы пользовались в предыдущем разделе, прекращая дальнейший поиск других смежных вершин вдоль прямой в случае, если одна такая вершина оказывается найденной. Здесь же это замечание, в частности, означает, что если мы нашли смежную данной вершину со значением xij = 0 ( xij = dk ), то испытывать значение xij = dk ( xij = 0 ) не следует. Т.е., как и ранее, мы вдоль каждого исходящего ребра будем искать единственную смежную вершину.
