МЕТОДЫ РЕШЕНИЯ ТРАНСПОРТНОЙ ЗАДАЧИ

Аннотация 2
Введение 3
1 Транспортная задача 6
1.1 Постановка задачи 6
2 Методы решения транспортной задачи 11
2.1 Метод северо-западного угла 12
2.2 Метод минимального элемента 14
2.3 Метод аппроксимации Фогеля 15
2.4 Улучшение опорного плана методом потенциалов 16
3 Пример решения транспортной задачи 22
4 Языки программирования и среда разработки 32
4.1 Языки программирования 32
4.2 Среда разработки 33
5 Логистические информационные системы (ЛИС) 35
5.1 Системы для управления перевозками 36
6 Программная реализация решения транспортной задачи 40
Заключение 48
Список использованных источников и литературы 49
Приложение А 52

Купить

Принятие решений относится к важных частям различного рода управления. Люди всегда сталкивались с проблемой принятия решений в различных ситуациях, причем решений таких, которые приводят к более благоприятному результату, т.е. с использованием рационального способа решения. Такой способ мы будем называть оптимальным. С точки зрения математического описания под принятием решения понимается выбор элемента x из некоторого множества X по некоторому заданному правилу выбора F, что F(y)^x, Vy Е X. Математическая теория принятия решений занимается анализом процесса принятия решений во всех областях жизнедеятельности [10].
Линейное программирование является разделом математического программирования, в котором изучают теорию и методы решения экстремальных задач, связанных с оптимизацией линейных функций при линейной зависимости между переменными. Такие задачи являются первыми хорошо исследованными задачами поиска экстремума целевой функции, т.е. линейной функции, зависящей от переменных х = ( х1,х2, — >хп) при условии, что переменные x удовлетворяют системе ограничений-равенств и неравенств. В 1949 американский математик А. Данциг создал действенный численный метод решения задач линейного программирования, называемый симплекс-методом, который стал основным методом в решении таких задач. После появления вычислительной техники были разработаны различные алгоритмы и методы для решения множества задач, связанных с оптимизацией производства при использовании ограниченных ресурсов. Линейное программирование применяется в различных задачах оптимизации и различных областях экономики, сельского хозяйства, военного дела, транспорта и многих других.
Транспортной задачей называют отдельный класс задач линейного программирования с общей математической моделью, которые могут решаться с помощью симплекс-метода, но для больших объемов данных и специфической математической модели транспортной задачи затруднительно получить решение симплекс-методом. Для решения транспортных задач были созданы специальные численные методы, которые являются простыми в отличие от методов решения общей задачи линейного программирования. Реализация таких методов происходит либо вручную, если задача не очень сложная и входных данных немного, либо используется вычислительная техника и различные языки программирования, поскольку зачастую требуется осуществлять большое количество итераций для нахождения оптимального решения. Как и для любой задачи линейного программирования, сначала находится опорный план, например методом северо-западного угла, методом минимального элемента или методом аппроксимации Фогеля, и затем его оптимизируют. На данный момент существует множество различных методов поиска оптимального решения транспортной задачи, самый распространенный из них метод потенциалов , разработанный советскими учеными Л.В. Канторовичем и М.К. Гавуриным в [11].
Классическая транспортная задача - это задача нахождения некоторого плана перевозок однородного груза (груз, который можно перевозить одним и тем же составом) из пунктов отправления (от поставщиков) в пункты назначения (к потребителям), при котором суммарная стоимость затрат на перевозки минимальна. Такой план является экономически эффективным. При этом учитывают некоторые ограничения, налагаемые на объемы грузов, имеющихся в пунктах отправления, и ограничения, учитывающие потребность грузов в пунктах назначения. Начальные условия принято записывать в виде таблицы [1].
Также математическая модель транспортной задачи позволяет описывать множество других ситуаций, связанных не только с перевозками.
В современном мире, в условиях развития рыночной экономики, любое предприятие хочет уменьшить транспортные издержки. Поэтому использование методов решения транспортных задач на предприятиях, которые хотят минимизировать затраты на транспортировку и хранение товаров, является актуальным.
Целью данной работы является решение транспортной задачи различными методами и их программная реализация. Для этого были сформулированы и решены следующие задачи:
1. изучить математическую модель транспортной задачи;
2. построить опорный план методом северо-западного угла, методом минимального элемента и методом аппроксимации Фогеля;
3. получить оптимальный план перевозок методом потенциалов;
4. выбрать язык программирования и среду разработки приложения;
5. осуществить программную реализацию транспортной задачи в виде оконного приложения;
6. протестировать приложение на задаче с известным решением.

Купить