Транспортная задача . виды задач
Автономное учреждение Чувашской Республики
среднего профессионального образования
«Канашский педагогический колледж»
Министерства образования и молодежной политики Чувашской Республики
КУРСОВАЯ РАБОТА
по дисциплине «Математические методы»
Транспортная задача. Виды задач
Выполнил: студент 402 гр.
Марков Д.В.
Руководитель: преподаватель высшей квалификационной категории
Фомина Т.А.
г. Канаш - 2014
Содержание
Введение . . . . . . . . . . . . . . . . . . . . . . . . . . .. . . . . . . . . . . . . . . . . . . . .3
1 Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 5
2 Методы составления начального опорного плана . . . . . . . . . . . . .11
3 Методы решения транспортной задачи
3.1Диагональный метод, или метод северо-западного угла . . . . . . 12
3.2 Метод наименьшей стоимости . . . . . . . . . . . . . . . . . . . . . . . . . . 13
3.3 Метод потенциалов . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .14
4. Транспортная задача с избытком заявок . . . . . . . . . . . . . . . . . . . 22
5. Пример решения транспортной задачи . . . . . . . . . . . . . . . . . . . . .24
Заключение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .31
Список использованных источников . . . . . . . . . . . . . . . . . . . . . . . . .32
Введение
Очень часто мы решаем проблемы: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий @@@.
Все эти ситуации сводится к проблемах используем транспортные задачи .
Под названием транспортная задача объединяет широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
Целью курсовой работы является изучение транспортной задачи. В ходе выполнения работы будет показано для каких целей они используются,рассмотрены различные виды траспортных задач.
Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. @@найти место для этого обза@
- сменить заголовок
- название , виды задач
- всё по разрешению
1 Транспортная задача. Общая постановка, цели, задачи
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с m баз A1,A2,…,Am n потребителям B1,B2,…,Bn.
Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
Обозначим количество груза, имеющегося на каждой из m баз (запасы), соответственно a1,a2,…am, а общее количество имеющегося в наличии груза – a:
;
заказы каждого из потребителей (потребности) обозначим соответственно b1,b2,…,bn, а общее количество потребностей – b:
,
Тогда при условии
мы имеем закрытую модель, а при условии
– открытую модель транспортной задачи.
Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза (a > b), либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены (a < b).
Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.
План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:
Пункты Отправления |
Пункты назначения |
Запасы | |||
… |
|||||
… |
|||||
… |
|||||
… |
… |
… |
… |
… |
… |
… |
|||||
Потребности |
… |
или | |||
Условие a=b или a≠b означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное xij означает количество груза, перевозимого с базы Ai потребителю Bj: совокупность этих величин образует матрицу (матрицу перевозок).
Очевидно, переменные xij должны удовлетворять условиям:
Система (2.1) содержит m+n уравнений с mn неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (2.1) могут быть разделены на две группы: первая группа из т первых уравнений (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе (2.1) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.
Такая структура системы (2.1) позволяет легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней мере, один из двух их индексов равен единице, а, следовательно, свободные неизвестные определяются условием i ≥ 2, j≥ 2.Перепишем систему (2.1) в виде
где символы и означают суммирование по соответствующему индексу. Так, например,
При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь i ≥ 2,j ≥ 2).
В рассматриваемой нами системе только два уравнения, а именно первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные x12,x13,…,x1n с помощью вертикальных уравнений, мы получаем уравнение
или короче
где символ означает сумму всех свободных неизвестных. Аналогично, исключив из первого вертикального уравнения базисные неизвестные x21,x31,…xm1 с помощью горизонтальных уравнений, мы получаем уравнение
Так как для закрытой модели транспортной задачи a=b, то полученные нами уравнения (2.2) и (2.2’) одинаковы и, исключив из одного из них неизвестное x11, мы получим уравнение-тождество 0=0, которое из системы вычеркивается.
Итак, преобразование системы (2.1) свелось к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (2.2). Остальные уравнения остаются неизменными. Система приняла вид
В системе (2.3) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного x11 [она входит в первое уравнение системы (2.3)]. В системе (2.3) имеется m+n-1 уравнений, выделенный базис содержит m+n-1 неизвестных, а, следовательно, и ранг системы (2.1) r=m+n-1.
Для решения транспортной задачи необходимо кроме запасов и потребностей знать также и тарифы cij, т. е. стоимость перевозки единицы груза с базы Ai потребителю Bj.
Совокупность тарифов cij также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:
Пункты Отправления |
Пункты назначения |
Запасы | ||||||||
… |
||||||||||
… |
||||||||||
… |
||||||||||
… |
… |
… |
… |
… |
… | |||||
… |
||||||||||
Потребности |
… |
или | ||||||||
Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных xij:
Требуется в области допустимых решений системы уравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4).
Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен m+n-1 то среди всех mn неизвестных xij выделяется m+n-1 базисных неизвестных, а остальные (m-1)*(n-1) неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем m+n-1 заполненных и (m-1)*(n-1) пустых клеток.
Для контроля надо проверять, равна ли сумма чисел в заполненных клетках каждой строки таблицы перевозок запасу груза на соответствующей базе, а в каждом столбце — потребности заказчика [этим подтверждается, что данный план является решением системы (2.1)].
Замечание 1. Не исключаются здесь и вырожденные случаи, т. е. возможность обращения в нуль одной или нескольких базисных неизвестных. Но эти нули в отличие от нулей свободных неизвестных вписываются в соответствующую клетку, и эта клетка считается заполненной.
Замечание 2. Под величинами cij, очевидно, не обязательно подразумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, xij выражены в тоннах, а cij в километрах, то величина S, определяемая формулой (2.4), является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.
- Методы составления начального опорного плана
Как и в общем случае, решение транспортной задачи начинается с отыскания первого опорного плана (исходного базиса). Мы рассмотрим два наиболее распространенных метода построения такого базиса. Суть обоих этих методов состоит в том, что базисный план составляется последовательно, в несколько шагов (точнее, m+n-1 шагов). На каждом из этих шагов заполняется одна клетка, притом так, что, либо полностью удовлетворяется один из заказчиков (тот, в столбце которого находится заполняемая клетка), либо полностью вывозится весь запас груза с одной из баз (с той, в строке которой находится заполняемая клетка).
В первом случае мы можем исключить столбец, содержащий заполненную на этом шаге клетку, и считать, что задача свелась к заполнению таблицы с числом столбцов, на единицу меньшим, чем было перед этим шагом, но с тем же количеством строк и с соответственно измененным запасом груза на одной из баз (на той базе, которой был удовлетворен заказчик на данном шаге).
Во втором случае исключается строка, содержащая заполняемую клетку, и считается, что таблица сузилась на одну строку при неизменном количестве столбцов и при соответствующем изменении потребности заказчика, в столбце которого находится заполняемая клетка.
Начиная с первоначально данной таблицы и повторив m+n-2 раз описанный шаг, мы придем к “таблице”, состоящей из одной строки и одного столбца (иначе говоря, из одной пустой клетки). Другими словами, мы пришли к задаче с одной базой и с одним потребителем, причем потребности этого единственного заказчика равны запасу груза на этой единственной базе. Заполнив последнюю клетку, мы освобождаем последнюю базу и удовлетворяем потребность последнего заказчика. В результате, совершив m+n-1 шагов, мы и получим искомый опорный план.
Замечание. Может случиться, что уже на некотором (но не на последнем!) шаге потребность очередного заказчика окажется равной запасу груза на очередной базе. Тогда после заполнения очередной клетки объем таблицы как бы одновременно уменьшается на одни столбец и на одну строку. Но и при этом мы должны считать, что уменьшение объема таблицы происходит либо на один столбец, а на базе сохраняется “остаток” равный нулю, либо на одну строку, а у заказчика еще осталась неудовлетворенная “потребность” в количестве нуля единиц груза, которая и удовлетворяется на одном из следующих шагов. Этот нуль (“запас” или “потребностью” – безразлично) надо записать в очередную заполняемую клетку на одном из последующих шагов. Так как при этом оказывается равной нулю одна из базисных неизвестных, то мы имеем дело с вырожденным случаем. Различие методов отыскания первого опорного плана состоит в различии способов набора заполняемой клетки.
4 Транспортная задача с избытком заявок
Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления Am+1 с запасом am+1 равным недостающему запасу, и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равной нулю.
Задача, двойственная к транспортной.
Построим задачу, двойственную к транспортной. С этой целью вспомним, что каждому пункту отправления Ai и назначения Bj отвечает определенное ограничение
В то же время каждому ограничению из (6.1) сопоставляется определенная неизвестная в двойственной задаче. Тем самым устанавливается соответствие между всеми пунктами Ai и Bj и всеми неизвестными двойственной задачи.
Обозначим неизвестную в двойственной задаче, отвечающую пункту отправления Ai, через ui(i=1,..,n), а пункту назначения Bj – через vj(j,…m).
Каждому неизвестному в транспортной задаче соответствует ограничение, связывающее неизвестные в двойственной задаче. Неизвестное xij входит ровно в два ограничения системы (6.1): одно из них отвечает пункту Ai, а другое – пункту Bj. В обоих этих уравнениях коэффициент при xij равен 1. Поэтому соответствующее xij ограничение в двойственной задаче имеет вид
.
Правая часть неравенства (6.2) равна cij, потому что именно с этим коэффициентом неизвестная xij входит в минимизируемую формулу (2.4).
Оптимизируемая форма двойственной задачи имеет вид
Таким образом, задача двойственная к транспортной формулируется следующим образом. При ограничениях (6.2) максимизировать формулу (6.3). Подчеркнем, что знак значений неизвестных ui(i=1,…,n) и vj(j,…,m) может быть произвольным.
Предположим, что нам известно некоторое допустимое базисное решение транспортной задачи, в котором все базисные неизвестные строго положительны. Это решение оптимально лишь в том случае, когда соответствующая ей система оказывается совместной. Эта система возникает из системы (6.2), если в ней все неравенства, отвечающие базисным неизвестным xij заменить точными равенствами.
В итоге приходим к соотношению:
ui + vj ≤ cij (для всех свободных неизвестных xij) (6.4)
Тем самым мы убеждаемся, что признак оптимальности в работе по методу потенциалов совпадает с необходимым и достаточным условием оптимальности.
3 Основные типы, виды моделей
Заключение
В курсовой работе изложены основные подходы и методы решения транспортной задачи, являющейся одной из наиболее распространенных задач линейного программирования. Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и так далее.
Алгоритм и методы решения транспортной задачи могут быть использованы при решении некоторых экономических задач, не имеющих ничего общего с транспортировкой груза. В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие:
оптимальное закрепление за станками операций по обработке деталей. В них cij является таким экономическим показателем, как производительность. Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком;
оптимальные назначения, или проблема выбора. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij. Задача позволяет определить, какой механизм и на какую работу надо назначить, чтобы добиться максимальной производительности;
задача о сокращении производства с учетом суммарных расходов на изготовление и транспортировку продукции;
увеличение производительности автомобильного транспорта за счет минимизации порожнего пробега. Уменьшение порожнего пробега сократит количество автомобилей для перевозок, увеличив их производительность;
решение задач с помощью метода запрещения перевозок. Используется в том случае, если груз от некоторого поставщика по каким-то причинам не может быть отправлен одному из потребителей. Данное ограничение можно учесть, присвоив соответствующей клетке достаточно большое значение стоимости, тем самым в эту клетку не будут производиться перевозки.
Таким образом, важность решения данной задачи для экономики несомненна. Приятно осознавать, что у истоков создания теории линейного программирования и решения, в том числе и транспортной задачи, стоял русский ученый – Леонид Витальевич Канторович.
Список использованных источников
1. Кузнецов А. В., Сакович В. А., Холод Н. И. Высшая математика. Математическое программирование, Минск, Высшая школа, 2001.
2. Красс М. С., Чупрынов Б. П. ”Основы математики и ее приложения в экономическом образовании”, Издательство «Дело», Москва 2001.
3. Ермаков В. И. Общий курс высшей математики для экономистов, Москва, Инфра – М, 2000.
4. Вентцель Е.С. Исследование операций – задачи, принципы, методология. М.:Наука, 1980.
5. Саати Т. Принятие решений. Метод анализа иерархий. М.:Радио и связь, 1993.
6. Беллман Р., Дрейфус С. Прикладные
задачи динамического
7. Ермаков С.М., Михайлов Г.А. Курс статистического моделирования. – М.:Наука, 1976.