Metody_optimizatsii_Shatina_A_V

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

Если суммарные запасы пунктов отправления больше сум-

в) ввести дополнительные переменные xi,n+1 ³ 0, i = 1,...,m . Тогда придем к замкнутой модели транспортной задачи.

Если в задаче имеется дополнительное требование, состоя-

щее в том, что из некоторого пункта Ai груз должен быть полностью вывезен, то стоимость перевозки единицы груза из пункта

Ai в пункт Bn+1 следует положить равной M , где M - достаточ-

но большое положительное число, т.е. ci,n+1 = M .

Если суммарные запасы отправителей меньше суммарных

б) положить cm+1, j = 0, j = 1,...,n ;

в) ввести дополнительные переменные xm+1, j ³ 0, j = 1,...,n . Тогда придем к замкнутой модели транспортной задачи.

Если в задаче имеется дополнительное требование полностью удовлетворить потребности пункта назначения B j , то сле-

дует положить cm+1, j = M , где M - достаточно большое положительное число.

Пример 1. Привести транспортную задачу, заданную платежной матрицей (табл. 7.1), к замкнутой модели.

придем к замкнутой модели транспортной задачи со следующей платежной матрицей:

Таблица 7.2 b1 = 30 b2 = 30 b3 = 20

●

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

Метод «северо-западного угла» нахождения начального плана перевозок.

Назначим максимально возможную перевозку из пункта отправления A1 в пункт назначения B1, т.е. заполняем верхний ле-

точки. При этом либо пункт отправления A1, либо пункт назначения B1, либо оба эти пункта окажутся полностью обслуженными.

Если пункт A1 оказался полностью обслуженным, то выводим из рассмотрения первую строку матрицы X и рассматриваем

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

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

Эту процедуру продолжаем до тех пор, пока все пункты от-

85

правления и пункты назначения не будут обслужены. Последней перевозкой будет перевозка из пункта отправления Am в пункт назначения Bn .

Вкачестве примера найдем первоначальный план перевозок

взадаче представленной платежной матрицей в виде таблицы 7.2. Назначим максимально возможную перевозку из пункта отправ-

ления A1 в пункт назначения B1: x11 = 20. Пункт A1 оказался полностью обслуженным. Первую строку матрицы X выводим из рассмотрения. В оставшейся матрице назначаем максимально

возможную перевозку из пункта A2 в пункт B1: x21 = 10. Тогда

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

возможную перевозку из пункта A2 в пункт B2 : x22 = 30 . Тогда

оба пункта A2 и B2 оказываются полностью обслуженными. Второй столбец матрицы X выводим из рассмотрения. Назначаем

максимально возможную перевозку из пункта A2 в пункт B3 : x23 = 0. В оставшийся элемент матрицы X записываем макси-

мально возможную перевозку из пункта A3 в пункт B3 : x33 = 20. Полученный план перевозок представлен в таблице 7.3.

найденного плана перевозок:

(c, x) = 1× 20 +1×10 + 3× 30 + 3× 0 + 0 × 20 = 120 .

86

Метод «северо-западного угла» не учитывает стоимости перевозок. Поэтому начальный план может оказаться далеко не оптимальным. Следующий метод стоимости перевозок учитывает.

Метод минимума по матрице нахождения начального плана перевозок.

Вплатежной матрице выберем минимальный элемент ci0 j0

иназначим максимально возможную перевозку из пункта Ai0 в

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

пункт отправления Ai0 или пункт назначения B j0 (или оба пункта одновременно) будут обслужены. В платежной матрице соответствующая строка или столбец выводятся из дальнейшего рассмотрения. Если и пункт отправления, и пункт назначения одновременно обслужились, то для определенности будем выводить из рассмотрения столбец матрицы X .

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

Вкачестве минимального элемента возьмем c31 = 0 и назначим максимально возможную перевозку из пункта A3 в пункт B1:

x31 = 20 . Тогда пункт A3 окажется полностью обслуженным, и третью строку матрицы X выводим из рассмотрения. В оставшейся платежной матрице выбираем минимальный элемент

c21 = 1 и назначаем максимально возможную перевозку из пункта

A2 в пункт B1: x21 = 10. Тогда пункт B1 окажется полностью обслуженным. Выводим из рассмотрения первый столбец матрицы

X . В оставшейся платежной матрице выбираем элемент c12 = 2 и

87

назначаем максимально возможную перевозку из пункта A1 в пункт B2 : x12 = 20 . Тогда полностью обслуженным оказывается пункт A1, и первую строку матрицы X выводим из рассмотрения. В оставшейся платежной матрице c22 = c23 = 3. Выбираем c22 = 3 и назначаем максимально возможную перевозку из пунк-

та A2 в пункт B2 : x22 = 10. Тогда пункт B2 оказывается полностью обслуженным, и из рассмотрения выводится второй столбец

матрицы X . В оставшийся элемент x23 матрицы X назначаем максимально возможную перевозку из пункта A2 в пункт B3 :

x23 = 20 . Полученный план перевозок представлен таблицей 7.4. Для найденного плана перевозок

(c, x) = 1×10 + 0 × 20 + 2 × 20 + 3×10 + 3× 20 = 140 . Первоначальный план перевозок. Таблица 7.4

Перейдем непосредственно к методу потенциалов решения транспортной задачи.

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

1)Привести задачу к замкнутой модели.

2)Найти первоначальный план перевозок x (начальную крайнюю точку множества допустимых элементов).

3)Провести исследование плана перевозок x . Для найден-

тенциалами. Они определяются из системы (n + m -1) уравнений ui + v j = cij для базисных индексов (i, j) . Для однозначного опре-

88

деления потенциалов положим один из потенциалов равным за-

данной величине, например, u1 = 0 .

4) Провести исследование матрицы

D = C - C Û Dij = cij - cij (i = 1,..., m, j = 1,..., n) .

Если D ³ 0 , то исследуемый план перевозок x является решением задачи. Если среди элементов матрицы D есть отрицательные, то

ìt, i = i0 , j = j0 ;

tij = ïí± t или 0 для базисных индексов (i, j); ïî0 для всех остальных индексов.

Здесь t > 0 выбирается так, чтобы одна из базисных компонент обратилась в ноль, а остальные были по-прежнему неотрицательны. Тогда вектор матрицы A, соответствующий этой компоненте, выводим из числа базисных, а вектор матрицы A, соответствую-

щий переменной xi0 j0 , вводим в число базисных векторов. Здесь под матрицей A понимается матрица ограничений задачи, задаваемых уравнениями (1), (2).

Далее вновь начинаем исследование полученной крайней

точки x′, т.е. возвращаемся к пункту 3).

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

Пример 2. Решить транспортную задачу, заданную платежной матрицей (табл. 7.1).

Решение:

89

1) В примере 1 задача была приведена к замкнутой модели. Соответствующая платежная матрица представлена таблицей 7.2.

2) в качестве первоначального плана перевозок возьмем план, полученный методом «минимум по матрице» и представленный таблицей 7.4.

В качестве наименьшего отрицательного элемента матрицы

возьмем 32 = −2.

5) Построим новый план перевозок, добавляя в предыдущий

план перевозок на место нулевого небазисного элемента x32 величину t > 0 :