Транспортные задачи - Курсовая работа

«Транспортные задачи»Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку). Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности.Суть задачи состоит в составлении оптимального плана перевозок, минимизирующего суммарные транспортные издержки, при реализации которого запросы всех пунктов потребления Bj j=1,2,3,…,n, были бы удовлетворены за счет производство продукта в пунктах Аі i=1,2,3,…,m. Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза (a>b), либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены (a<b). Кроме того, все уравнения системы (2.1) могут быть разделены на две группы: первая группа из т первых уравнений (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). В системе (2.3) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного x11 [она входит в первое уравнение системы (2.3)].Он позволяет, отправляясь от некоторого допустимого решения, получить оптимальное решение за конечное число итераций. По допустимому решению каждому пункту задачи сопоставляется число, называемое его предварительным потенциалом. Пунктам Аі соответствуют числа ui, пунктам Bj - числа vj.Как и при решении задачи линейного программирования, симплексным методом, определение оптимального плана транспортной задачи начинают с нахождения какого-нибудь ее опорного плана. Если в опорном плане число отличных от нуля компонентов равно в точности n m-1, то план является не выраженным, а если меньше - то выраженным. Для определения опорного плана существует несколько методов. При составлении первоначального опорного плана методом северо-западного угла стоимость перевозки единицы не учитывается, поэтому построенный план далек от оптимального, получение которого связано с большим объемом вычислительных работ.Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям: 1. Если, начиная с какого-либо неизвестного, мы будем последовательно переходить от одного к следующему за ним неизвестному то, через несколько шагов мы вернемся к исходному неизвестному. Если каждые два соседних неизвестных цикла соединить отрезком прямой, то будет получено геометрическое изображение цикла - замкнутая ломаная из чередующихся горизонтальных и вертикальных звеньев, одна из вершин которой находится в свободной клетке, а остальные - в базисных клетках. Можно доказать, что для любой свободной клетки таблицы перевозок существует один и только один цикл, содержащий свободное неизвестное из этой клетки, и что число вершин в цикле всегда четно. Так как число вершин в цикле всегда четно, то, возвращаясь в свободную клетку, мы должны будем приписать ей знак " ", т. е. тот знак, который ей уже приписан при выходе из нее.При изучении теоретического материала по первой главе рассмотрены основные методы решения транспортной задачи. Этот метод позволяет упростить наиболее трудоемкую часть вычислений - нахождение оценок свободных клеток. Цикл - это последовательность клеток таблицы транспортной задачи (i1,j1), (i1,j2), (i2,j2), … , (ik,j1), в которой две и только две соседние клетки расположены в одной клетке или столбце, причем первая и последняя клетки также находятся в одной строке или столбце. Рассмотрен алгоритм решения транспортной задачи методом потенциалов: 1. Строят начальное опорное решение (методом минимальной стоимости или какого либо другим методом) и проверяют правильность его построения, для чего подсчитывают количество занятых клеток (их должно быть m n-1) и убедиться в линейной независимости векторов условий (методом вычеркивания).Составим систему ограничений задачи. Сумма всех перевозок, стоящих в первой строке матрицы X, должна равняться запасам 1-му месторождению, а сумма перевозок во второй строке матрицы X-запасам 2-го месторождения, и сумма перевозок в третьей строке матрицы X-запасам 3-го месторождения: х11 х12 х13 х14 x15=200 х21 х22 х23 х24 x25=250 х31 х32 х33 х34 x35=250 Используя метод наименьшей стоимости, построим первый опорный план транспортной задачи.

Содержание

Введение

Глава 1. Обзор теоретических сведений по теме: «Решение транспортной задачи»

1.1 Транспортная задача. Общая постановка, цели, задачи. Основные типы, виды моделей

1.2 Метод потенциалов

1.3 Определение оптимального и опорного плана транспортной задачи

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

Вывод по главе 1

Глава 2. Решение транспортной задачи

2.1 Построение математической модели

2.2 Решение задачи

2.3 Решение транспортной задачи при помощи табличного редактора Excel

Заключение

Список литературы