Xreferat.com » Рефераты по математике » Транспортная задача линейного программирования

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

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

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

или короче

(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.Диагональный метод, или метод северо-западного угла. При этом методе на каждом шаге построения первого опорного плана заполняется левая верхняя клетка (северо-западный угол) оставшейся части таблицы. При таком методе заполнение таблицы начинается с клетки неизвестного Транспортная задача линейного программирования и заканчивается в клетке неизвестного

Если Вам нужна помощь с академической работой (курсовая, контрольная, диплом, реферат и т.д.), обратитесь к нашим специалистам. Более 90000 специалистов готовы Вам помочь.
Бесплатные корректировки и доработки. Бесплатная оценка стоимости работы.
Подробнее

Поможем написать работу на аналогичную тему

Получить выполненную работу или консультацию специалиста по вашему учебному проекту
Нужна помощь в написании работы?
Мы - биржа профессиональных авторов (преподавателей и доцентов вузов). Пишем статьи РИНЦ, ВАК, Scopus. Помогаем в публикации. Правки вносим бесплатно.

Похожие рефераты: