126,59 Kb.НазваниеПод названием транспортная задача объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача задача о наиболееДата конвертации18.11.2012Размер126,59 Kb.Тип Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями. Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены симплексным методом однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его получить оптимальное решение. 1. Формулировка транспортной задачи.Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны , i=1,2,, ,m, j=1,2, ,n- стоимости перевозки единицы груза от каждого I-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны. Исходные данные транспортной задачи обычно записываются в таблице (таб1.1). . . Таблица1.1. Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А=(), вектора запросов потребителей В=() и матрицы стоимостей . В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, слады, магазины и т.д. Однородными считаются грузы, которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.п.2. Математическая модель транспортной задачи. Переменными (неизвестными) транспортной задачи являются i=1,2,, ,m, j=1,2, ,n объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок . Так как произведение определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид . Система ограничений задачи состоит из двух групп уравнений. Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью: , i=1,2, ,m. Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей: , j=1, 2, , n. Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так: , (1) , i=1,2, ,m , (2), j=1, 2, , n, (3), i=1,2,, ,m, j=1,2, ,n (4) В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е. . Такая задача называется задачей с правильным балансом, а ее модель закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель открытой. Математическая формулировка транспортной задачи такова: найти переменные задачи , i=1,2,, ,m, j=1,2, ,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1). Математическая модель транспортной задачи может быть записана в векторном виде.. Тогда математическая модель транспортной задачи запишется следующим образом: , (7) =, (8) , i=1,2,, ,m, j=1,2, ,n (9)3. Необходимое и достаточное условия разрешимости транспортной задачи. Теорема1. Для того чтобы транспортная задача линейного программирова
Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача задача о наиболее
Под названием транспортная задача объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача задача о наиболее
Комментариев нет:
Отправить комментарий