Математическое моделирование транспортной задачи
Математическое моделирование транспортной задачиСкачать файл - Математическое моделирование транспортной задачи
Математическая модель транспортной задачи. Необходимое и достаточное условия разрешимости транспортной задачи. Свойство системы ограничений транспортной задачи. Опорное решение транспортной задачи. Методы построения начального опорного решения. Переход от одного опорного решения к другому. Особенности решения транспортных задач с неправильным балансом. Алгоритм решения транспортной задачи методом потенциалов. Транспортная задача с ограничениями на пропускную способность. Транспортная задача по критерию времени. Применение транспортной задачи для решения экономических задач. Методы линейного программирования применяются для решения многих экстремальных задач, с которыми довольно часто приходится иметь дело в экономике. Решение таких задач сводится к нахождению крайних значений максимума и минимума некоторых функций переменных величин. Линейное программирование основано на решении системы линейных уравнений с преобразованием в уравнения и неравенства , когда зависимость между изучаемыми явлениями строго функциональна. Для него характерны математическое выражение переменных величин, определенный порядок, последовательность расчетов алгоритм , логический анализ. Применять его можно только в тех случаях, когда изучаемые переменные величины и факторы имеют математическую определенность и количественную ограниченность, когда в результате известной последовательности расчетов происходит взаимозаменяемость факторов, когда логика в расчетах, математическая логика совмещаются с логически обоснованным пониманием сущности изучаемого явления. С помощью этого метода в промышленном производстве, например, исчисляется оптимальная общая производительность машин, агрегатов, поточных линий при заданном ассортименте продукции и иных заданных величинах , решается задача рационального раскроя материалов с оптимальным выходом заготовок. В сельском хозяйстве он используется для определения минимальной стоимости кормовых рационов при заданном количестве кормов по видам и содержащимся в них питательным веществам. Задача о смесях может найти применение и в литейном производстве состав металлургической шихты. Этим же методом решаются транспортная задача, задача рационального прикрепления предприятий-потребителей к предприятиям-производителям. Все экономические задачи, решаемые с применением линейного программирования, отличаются альтернативностью решения и определенными ограничивающими условиями. Решить такую задачу - значит выбрать из всех допустимо возможных альтернативных вариантов лучший, оптимальный. Важность и ценность использования в экономике метода линейного программирования состоят в том, что оптимальный вариант выбирается из весьма значительного количества альтернативных вариантов. При помощи других способов решать такие задачи практически невозможно. Весьма типичной задачей, решаемой с помощью линейного программирования, является транспортная задача. Транспортная задача transportation problem - одна из наиболее распространенных задач математического программирования обычно - линейного. В общем виде ее можно представить так: Следовательно, дело сводится к наиболее рациональному прикреплению производителей к потребителям и наоборот. В простейшем виде, когда распределяется один вид продукта и потребителям все равно, от кого из поставщиков его получать, задача формулируется следующим образом. Обозначим через x ij планируемое количество единиц груза для перевозки из i -ro пункта в j -й. Заметим, что условие является естественным условием разрешимости замкнутой транспортной задачи. Более общей транспортной задачей является так называемая открытая несбалансированная транспортная модель:. Ясно, что в этой задаче не предполагается, что весь груз, накопленный в i -м пункте, должен быть вывезен. Простейшими транспортными задачами являются задачи о перевозках некоторого однородного груза из пунктов отправления от поставщиков в пункты назначения к потребителям при обеспечении минимальных затрат на перевозки. Обычно начальные условия таких задач записывают в таблицу. Например, для k поставщиков и l потребителей такая задача имеет следующий вид:. Обозначим через x ij поставку количество груза , которая планируется к перевозке от i -того поставщика к j -тому потребителю. Математически задача сводится к нахождению минимума целевой функции, выражающей суммарные затраты на перевозку груза, то есть функции. Система ограничений 1 сразу имеет вид уравнений, поэтому отпадает необходимость вводить добавочные переменные. Заметим, что число k равно числу строк исходной таблицы, а число l - числу столбцов. Число переменных x ij , входящих в целевую функцию и в систему уравнений 1 , равно произведению kl, то есть числу клеток таблицы. Любое решение транспортной задачи x 11 , x 12 ,…, x kl называется распределением поставок. Так как поставки не могут быть отрицательными, то речь идет только о допустимых решениях. Оптимальному решению транспортной задачи соответствует оптимальное распределение поставок, при котором целевая функция достигает своего минимума. В ходе решения задачи и нужно получить это оптимальное распределение поставок, которому соответствует какое-то допустимое базисное решение системы ограничений 1. Эти условия образуют систему ограничений. Любой план, компоненты которого удовлетворяют этой системе, будет допустимым. Установим условия, при которых эта система будет совместной, то есть будет иметь решения. Сложим элементы x ij матрицы перевозок по строкам, каждая строка в сумме дает M i, и в итоге получим. Сложим те же элементы по столбцам, каждый столбец дает N j, и в сумме получим. Но от перестановки слагаемых сумма не меняется, поэтому для любого допустимого плана обязательно будет выполняться условие. Равенство является необходимым условием совместности ограничений задачи. Докажем и достаточность этого условия: Убедимся, что эти числа образуют допустимый план. Для этого достаточно проверить, что они удовлетворяют всем ограничениям задачи. Но величины N j, от индекса i не зависят и их можно вынести за знак суммы. Вынося постоянные M i и за знак суммы и имея в виду, что , получаем. Как видим, наши числа удовлетворяют группе уравнений 1. Эти числа неотрицательны, то есть система ограничений полностью удовлетворяется. Таким образом, допустимый план существует, что и требовалось доказать. Равенство запасов потребностям есть необходимое и достаточное условие совместности и, следовательно, разрешимости транспортной задачи. Согласно теореме о структуре координат опорного плана задачи линейного программирования, в невырожденном опорном плане должно содержаться r отличных от нуля координат, где r - ранг системы ограничений. Главная Опубликовать работу О сайте. Методы линейного программирования для решения транспортной задачи. Сохрани ссылку на реферат в одной из сетей:
Решение транспортных задач с применением программирования в системе MathCAD
Математическая модель транспортной задачи
Решение транспортных задач
Масяня желтая пресса прохождение
Правила русского языка орфоэпия
Использование закона сохранения импульса
Бар казанская божья матерь где