86073 (Транспортная задача линейного программирования), страница 2

Система (2.1) содержит уравнений с неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (2.1) могут быть разделены на две группы: первая группа из т первых уравне­ний (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом из горизонталь­ных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы пере­возок). Таким образом, каждая неизвестная встречается в системе (2.1) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.

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

(2.1’)

где символы и означают суммирование по соответствующему индексу. Так, например,

При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь , ).

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

или короче

(2.2)

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

(2.2’)

Так как для закрытой модели транспортной задачи , то полученные нами уравнения (2.2) и (2.2’) одинаковы и, исключив из одного из них неизвестное , мы получим уравнение-тождество 0=0, которое из системы вычеркивается.

И так, преобразование системы (2.1) свелось к замене двух урав­нений (первого горизонтального и первого вертикального) уравне­нием (2.2). Остальные уравнения остаются неизменными. Система приняла вид

(2.3)

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

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

Совокупность тарифов также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:

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

(2.4)

Требуется в области допустимых решений системы уравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4).

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

неизвестных являются свободными. В базис­ном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем заполненных и · пустых клеток.

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

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

Замечание 2. Под величинами , очевидно, не обязательно под­разумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, выражены в тоннах, а в километрах, то величина , определяемая формулой (2.4), является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.

3. Методы составления начального опорного плана.

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

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

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

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

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

Различие методов отыскания первого опорного плана состоит в различии способов набора заполняемой клетки.

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

Пример.

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