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

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

задача линейного программирования" width="25" height="25" align="BOTTOM" border="0" />


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

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


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

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


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


Потребности

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

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

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

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

или

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


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

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

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

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

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

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

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

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


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


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


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

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


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

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

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


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


Пример.


Пункты

Отправления

Пункты назначения Запасы

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

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

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

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

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


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


70
50
15
80
70 300

170 110 20


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


80
90
40
60
85 150



80 70

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


50
10
90
11
25 250




50 200
Потребности 170 110 100 120 200 700

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

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

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

Общий объем перевозок в тонно-километрах для этого плана составит


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


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


Пример.


Пункты

Отправления

Пункты назначения Запасы

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

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

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

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

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


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


70
50
15
80
70 300

20
100
180

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


80
90
40
60
85 150

150




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


50
10
90
11
25 250


110
120 20
Потребности 170 110 100 120 200 700

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


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


На пятом шаге клеток с наименьшими значениями Транспортная задача линейного программирования оказалось две Транспортная задача линейного программирования. Мы заполнили клетку для Транспортная задача линейного программирования, положив Транспортная задача линейного программирования. Можно было выбрать для заполнения другую клетку, положив Транспортная задача линейного программирования, что приведет в результате к другому опорному плану. Общий объем перевозок в тонно-километрах для этого плана составит


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


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

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


4.Понятие потенциала и цикла.


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

Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям:

Одно из неизвестных последовательности свободное, а все остальные – базисные.

Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.

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

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

Второе условие

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

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

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

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