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

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

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

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

(2.4)

 

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

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

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

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

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

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

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

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

Страницы: 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12