Курсовая работа: Транспортная задача. Венгерский метод

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

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

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

Пункты Отправления	Пункты назначения									Запасы
						…
			…
				…
…	…			…		…	…			…
				…
Потребности						…				или

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

(2.4)

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

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

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

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

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

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