Транспортная задача

Преимущества применения математических методов в планировании перевозок. Постановка транспортной задачи, отыскание начального решения методом минимального элемента. Проверка опорного плана на невырожденность. Написание программы для автоматизации решения.

Рубрика Программирование, компьютеры и кибернетика
Вид курсовая работа
Язык русский
Дата добавления 19.01.2016
Размер файла 1,5 M

Отправить свою хорошую работу в базу знаний просто. Используйте форму, расположенную ниже

Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.

Размещено на http://www.allbest.ru/

Содержание

Введение

1. Теоретический материал

1.1 Общая постановка транспортных задач

1.2 Методы составления опорного плана транспортной задачи

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

1.4 Метод минимального элемента

2. Постановка задачи

3. Решение задачи аналитическим методом

4. Создание приложения для решения задачи

4.1 Описание алгоритма

4.2 Разработка программы

4.3 Тестирование программы

4.4 Руководство пользователя

Заключение

Список использованных источников

Введение

В нынешнее время компьютер и компьютерные технологии занимают все более и более важную роль в жизни человека. И что бы справляться со многими жизненными задачами, человеку приходится все чаще обращаться к помощи компьютера, а для этого нужно человеку нужно иметь базовую подготовку обращения с компьютером.

Одной из самых распространенных задач во всех областях экономики является транспортировка груза или товара с минимальными материальными и временными затратами. Так как существует множество вариантов перевозок товара, что затрудняет получение самого экономичного плана, то следовательно появилась необходимость разработки специальной теории, для того чтобы быстро решать подобные задачи с помощью программ. Применение математических методов в планировании перевозок дает на многие задачи такого типа. Примером того может служить - "Транспортная задача" объединяющая широкий круг задач с единой математической моделью. Классическая транспортная задача - задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, чаще всего встречаются они в практических приложениях линейного программирования.

Огромное внимание уделяют транспортным задачам, так как они очень нужны и по сегодняшний день. Примером того могут служить ежедневные перевозки товаров, соответствующих предприятий, будь то водным, будь то воздушным, будь то железнодорожным путями. Ведь для любых из вышеперечисленных перевозок товаров требуется сэкономить как можно больше времени и затратить на это как можно меньше средств, и вследствие этого, получить как можно больше прибыли, в принципе на это то и направлена деятельность почти всех предприятий.

1. Теоретический материал

1.1 Общая постановка транспортных задач

Транспортные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение. Для классической транспортной задачи выделяют два типа задач: критерий стоимости (достижение минимума затрат на перевозку) или расстояний и критерий времени (затрачивается минимум времени на перевозку).

Общая постановка транспортной задачи состоит в определении оптимального плана перевозок некоторого однородного груза из m пунктов отправления (производства) a1,a2,…an в n пунктов назначения (потребления) b1,b2,…,bn. При этом в качестве критерия оптимальности обычно берется либо минимальная стоимость перевозок всего груза, либо минимальное время его доставки. Обозначим количество груза, имеющегося на каждой из m баз (запасы), соответственно a1,a2,…an, а общее количество имеющегося в наличии груза a:

;

заказы каждого из потребителей (потребности) обозначим соответственно, а общее количество потребностей:

.

Тогда при условии

мы имеем закрытую модель, а при условии

открытую модель транспортной задачи.

Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены, в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза (a>b), либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены (a<b). Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется "перевалочный пункт", например склад.

План перевозок с указанием запасов и потребностей удобно записывать таблицы (Таблица 1).

Таблица 1 - Общий вид

Пункты отправления

Пункты назначения

Запасы

Потребности

или

Условие a=b или a?b означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменная xij означает количество груза, перевозимого с базы ai потребителю bj, совокупность этих величин образует матрицу (матрицу перевозок).

Очевидно, переменная xij должны удовлетворять условиям:

Система (5) содержит m+n уравнений с m*n неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (5) могут быть разделены на две группы: первая группа из m первых уравнений ("горизонтальные" уравнения) и вторая группа из n остальных уравнений ("вертикальные" уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе (5) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.

Такая структура системы (5) позволяет легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней мере, один из двух их индексов равен единице, а, следовательно, свободные неизвестные определяются условием i?2, j?2. Перепишем систему (5) в виде:

где символы и означают суммирование по соответствующему индексу. Так, например:

При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь i?2, j?2).

В рассматриваемой нами системе только два уравнения, а именно первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные x12,x13,…,x1n с помощью вертикальных уравнений, мы получаем уравнение:

или короче

где символ означает сумму всех свободных неизвестных. Аналогично, исключив из первого вертикального уравнения базисные неизвестные x21,x31,…,xm1 с помощью горизонтальных уравнений, мы получаем уравнение:

Так как для закрытой модели транспортной задачи a=b, то полученные нами уравнения (8) и (9) одинаковы и, исключив из одного из них неизвестное x11, мы получим уравнение-тождество 0=0, которое из системы вычеркивается. Итак, преобразование системы (7) свелось к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (8). Остальные уравнения остаются неизменными. Система приняла вид:

В системе (10) выделен указанный выше базис: базисные неизвестные из первых n уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного x11 (она входит в первое уравнение системы (10)). В системе (10) имеется m+n-1 уравнений, выделенный базис содержит m+n-1 неизвестных, а, следовательно, и ранг системы (7) будет равен m+n-1.

Для решения транспортной задачи необходимо кроме запасов и потребностей знать также и тарифы cij, т. е. стоимость перевозки единицы груза с базы ai потребителю bj. Совокупность тарифов cij также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу (Таблица 2).

Таблица 2 - Совокупность тарифов

Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных xij:

Требуется в области допустимых решений системы уравнений (7) и (6) найти решение, минимизирующее линейную функцию (11). Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы уравнений равен m+n-1, то среди всех m*n неизвестных xij выделяется m+n-1 базисных неизвестных, а остальные (m-1)*(n-1) неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем m+n-1 заполненных и (m-1)*(n-1) пустых клеток. Для контроля надо проверять, равна ли сумма чисел в заполненных клетках каждой строки таблицы перевозок запасу груза на соответствующей базе, а в каждом столбце -- потребности заказчика (этим подтверждается, что данный план является решением системы (5)).

Замечание 1: не исключаются здесь и вырожденные случаи, т. е. возможность обращения в нуль одной или нескольких базисных неизвестных. Но эти нули в отличие от нулей свободных неизвестных вписываются в соответствующую клетку, и эта клетка считается заполненной.

Замечание 2: под величинами cij, очевидно, не обязательно подразумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, xij выражены в тоннах, а cij в километрах, то величина S, определяемая формулой (11), является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.

1.2 Методы составления опорного плана транспортной задачи

Есть множество методов нахождения опорного плана для транспортной задачи такие как: "Метод двойного предпочтения вариантов", "Метод наименьшего значения критерия оптимальности", "Метод прямой прогонки", но самыми главными считаются - "Метод Северо-западного угла"и "Метод минимального элемента".

"Метод Северо-западного угла"используют для нахождения произвольного опорного плана транспортной задачи ,а "метод минимального элемента"позволяет построить начальный опорный план транспортной задачи и является вариантом метода северо-западного угла, учитывающим специфику матрицы С=(Сij)mn. В отличие от метода северо-западного угла данный метод позволяет сразу получить достаточно экономичный план и сокращает общее количество итераций по его оптимизации.

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

Этот первый точный метод решения транспортной задачи предложен в 1949 году Кантаровичем А.В. и Гавуриным М.К. по существу он является детализацией метода последовательного улучшения плана применительно к транспортной задаче. Однако в начале он был изложен вне связи с общими методами линейного программирования. Несколько позднее аналогичный алгоритм был разработан Данциом, который исходил из общей идеи линейного программирования. В американской литературе принято называть модифицированным распределительным методом. Метод потенциалов позволяет определить, отправляясь от некоторого опорного плана перевозок построить решение транспортной задачи за конечное число шагов (итераций).

Общий принцип определения оптимального плана транспортной задачи этим методом аналогичен принципу решения задачи линейного программирования симплексным методом, а именно: сначала находят опорный план транспортной задачи, а затем его последовательно улучшают до получения оптимального плана.

1.4 Метод минимального элемента

Суть метода заключается в том, что из всей таблицы стоимостей выбирают наименьшую и в клетку, которая ей соответствует, помещают меньшее из чисел ai и bj. Затем из рассмотрения исключают либо строку, соответствующую поставщику, запасы которого полностью израсходованы, либо столбец, соответствующий потребителю, потребности которого полностью удовлетворены, либо и строку и столбец, если израсходованы запасы поставщика и удовлетворены потребности потребителя. Из оставшейся части таблицы стоимостей снова выбирают наименьшую стоимость, и процесс распределения запасов продолжают, пока все запасы не будут распределены, а потребности удовлетворены.

2. Постановка задачи

Есть 3 поставщика и 5 потребителей некоторого груза. Стоимость доставки единицы груза от каждого поставщика к каждому потребителю задается матрицей. Найти оптимальный план поставок.

Таблица 3 - Исходные данные

B1

B2

B3

B4

B5

Поставщики

A1

3

2

9

1

7

35

A2

2

4

1

2

1

33

A3

7

4

2

5

8

27

Потребители

21

17

22

15

20

3. Решение задачи аналитическим методом

Шаг 1 (Проверка на сбалансированность).

Общее число запасов на складах 95, общая потребность 95. Следовательно, задача является сбалансированной.

Шаг 2 (Отыскание начального решения методом минимального элемента).

Запишем настоящую задачу в виде транспортной таблицы. В верхней строке перечислим потребности потребителей по порядку номеров. В левом столбце перечислим имеющиеся запасы на складах. На пересечении j-го столбца и i-й строки будем записывать количество продукции, поставляемое с i-го склада j-му потребителю. Пока начальное решение не найдено, оставим эти клетки пустыми. В правом нижнем углу каждой клетки, отобразим соответствующие издержки.

Таблица 4 - Начальная транспортная таблица

Введем вспомогательные строку и столбец, в которых будем отмечать оставшиеся нераспределенные запасы и соответственно потребности (остатки). Изначально их содержимое равно исходным запасам и потребностям, так как еще ничего не распределялось.

Далее выберем клетку, в которую будем распределять продукцию на следующей итерации, это клетка, содержащая минимальное значение издержек (минимальный элемент).

Таблица 5 - Минимальный элемент

Итерация 1.

Заполним клетку a1,b4. Сравним значения остатков для производителя a1 и потребителя b4. Нераспределенных остатков по потребностям для b4 меньше, запишем меньшее число в клетку a1,b4 одновременно вычитая его из обеих клеток остатков. При этом клетка остатков по потребностям обнулится, указывая, что все потребности для b4 удовлетворены. Поэтому исключим столбец b4 из дальнейшего рассмотрения. Ненулевое значение остатка по запасам для a1 показывает, сколько единиц продукции у него осталось не потребленной.

Таблица 6 - Итерационный процесс

Итерация 2.

Заполним клетку a2,b3. Сравним значения остатков для производителя a2 и потребителя b3. Нераспределенных остатков по потребностям для b3 меньше, запишем меньшее число в клетку a2,b3 одновременно вычитая его из обеих клеток остатков. При этом клетка остатков по потребностям обнулится, указывая, что все потребности для b3 удовлетворены. Поэтому исключим столбец b3 из дальнейшего рассмотрения. Ненулевое значение остатка по запасам для a2 показывает, сколько единиц продукции у него осталось не потребленной.

Таблица 7 - Итерационный процесс

Итерация 3.

Таблица 8 - Итерационный процесс

Итерация 4.

Таблица 9 - Итерационный процесс

Итерация 5.

Таблица 10 - Итерационный процесс

Итерация 6.

Таблица 11 - Итерационный процесс

Итерация 7.

Таблица 12 - Итерационный процесс

Получено допустимое начальное решение (опорный план), удовлетворены нужды всех потребителей и использованы все запасы производителей.

Таблица 13 - Готовый опорный план

Шаг 3 (Проверка полученного опорного плана на невырожденность).

Количество заполненных клеток N должно удовлетворять условию N=n+m-1. В нашем случае N=7, n+m-1=5+3-1=7, что удовлетворяет нашему условию.

Шаг 4 (Вычисление общих затрат на перевозку всей продукции).

Для этого запишем транспортную таблицу, в которой совместим найденный опорный план с величинами издержек. В левом верхнем углу каждой клетки будем указывать количество единиц продукции а в правом нижнем затраты на перевозку единицы продукции.

Таблица 14 - Общие затраты

Перемножим числа стоящие в одной клетке (для всех клеток) затем полученные произведения сложим. Получим значение суммарных затрат, для данного начального решения и оно будет равно 289 единиц.

Шаг 5 (Поэтапное улучшение начального решения методом потенциалов).

Итерация 1.

Составим вспомогательную рабочую матрицу затрат. Она строится из исходной матрицы издержек путем переноса только тех ячеек Pij, которые соответствуют заполненным клеткам транспортной таблицы. Остальные ячейки остаются пустыми. Кроме того, введем вспомогательный столбец, в который внесем значения неизвестных U1 ... U3 (3 это m - число складов) и вспомогательную строку, в которую внесем значения неизвестных V1 ... V5 (5 это n - число потребителей). На рисунке они представлены желтым цветом. Эти n+m неизвестных должны для всех (i,j), соответствующих загруженным клеткам, удовлетворять линейной системе уравнений Ui+Vj=Pij.

Эту систему всегда можно решить следующим способом: На первом шаге полагают V5=0. Если на k шаге найдено значение неизвестной, то в системе всегда имеется еще не определенная неизвестная, которая однозначно может быть найдена на (k+1)-м шаге из уравнения Ui+Vj=Pij, так как значение другой неизвестной в этом уравнении уже известно. То какую неизвестную можно найти на (k+1) шаге, определяют методом проб. Переменные Ui и Vj называются симплекс-множителями или потенциалами.

Таблица 15 - Потенциалы

Порядок вычисления потенциалов был следующий:

- пусть V5=0;

- U2=P2,5-V5;

- U3 =P3,5-V5;

- V3=P2,3-U2;

- V1=P3,1- U3;

- U1=P1,1-V1;

- V2=P1,2-U1;

- V4=P1,4-U1.

Теперь для всех свободных клеток рабочей матрицы затрат вычислим оценки Sij, по формуле Sij=Pij-Ui-Vj. Каждая такая оценка показывает на сколько изменятся общие транспортные затраты при загрузке данной клетки единицей груза. Таким образом, если среди оценок имеются отрицательные (затраты уменьшаются) то данный план можно улучшить переместив в соответствующую клетку некоторое количество продукции. Если же среди оценок нет отрицательных - план является оптимальным.

Таблица 16 - Таблица затрат

Из всех отрицательных оценок имеет смысл выбрать наибольшую по модулю, так как ее воздействие на общие затраты является максимальным. В нашем случае такая оценка находится в ячейке а3,b3, в соответствующую ячейку транспортной таблицы мы должны переместить некоторое количество продукции, т.е. загрузить ее. Отметим в транспортной таблице ячейку а3,b3 знаком "+". Кроме нее мы пометим знаками "-"и "+" другие занятые числами ячейки таким образом, что в каждой строке и каждом столбце транспортной таблицы число знаков "+" будет равно числу знаков "-". Это всегда можно сделать единственным образом, причем в каждой строке и каждом столбце содержится по одному "+" и "-".То есть помеченные знаками клетки должны образовывать цикл.

Таблица 17 - Первый цикл

Затем мы определим минимум M из всех элементов, помеченных знаком "-" и выбираем одну ячейку, где этот минимум достигается. В нашем случае таковой является а3,b5 и обозначает загруженную клетку, которая должна стать свободной. Сейчас M=9.

Переход к новой транспортной таблице разбивается на следующие шаги:

- в ячейку а3,b3 новой таблицы записывается число M;

- ячейка а3,b5 остается пустой;

- в остальных ячейках, помеченных знаками "-" или "+", число M соответственно вычитается из стоящего в ячейке числа или складывается с ним, при этом результат вносится в соответствующую ячейку новой таблицы;

- непомеченные числа переносятся в новую таблицу без изменений, а остальные ячейки новой таблицы остаются пустыми.

Таблица 18 - Итерационный процесс

Итерация 2.

Таблица 19 - Пересчитанная таблица затрат

Таблица 20 - Второй цикл

M=13.

Таблица 21 - Итерационный процесс

Итерация 3.

Таблица 22 - Пересчитанная таблица затрат

Таблица 23 - Третий цикл

M=5.

Таблица 24 - Итерационный процесс

Итерация 4.

Таблица 25 - Пересчитанная таблица затрат

В приведенной выше таблице нет отрицательных оценок (план улучшить нельзя), следовательно, достигнуто оптимальное решение.

Таблица 26 - Оптимальное решение

Общие затраты на перевозку всей продукции, для оптимального плана составляют 173 единицы.

4. Создание приложения для решения задачи

4.1 Описание алгоритма

4.2 Разработка программы

Для написания программы был выбран объектно-ориентированный язык программирования Delphi и среда разработки программы BorlandDelphi 10 forMicrosoftWindows. Для ввода исходных значений задачи и вывода уже обработанных результатов был использован компонент StringGrid.

Поиск опорного плана осуществлялся методом минимального элемента, в программе данный метод представлен, как procedure raschet(). Этот метод программно выполняется за несколько итераций, в каждой из которых, сначала находится минимальных элемент в таблице, а потом он вычитается из соответствующего числа поставщика и потребителя, при этом минимальное число среди поставщика и потребителя записывается в клетку минимального элемента, и так пока соответствующие числа поставщика и потребителя не будут равны.

Сразу же после нахождения опорного плана требуется выполнить его оптимизацию, которая в данном случае осуществляется методом потенциалов и представлена в программе, как procedure optimizaciya(). Этот метод тоже программно выполняется за несколько итераций, в каждой из которых, сначала находятся потенциалы (procedure potencial()), а потом уже посредствам множественных расчетов, подробно описанных в аналитическом решении, находится оптимальный план перевозок.

Для оформления программы были использованы такие компоненты, как: MainMenu, Label, Button, Image, Bevel, XPManifest. Для вывода справки по программе былиспользован компонент Form.

4.3 Тестирование программы

Для корректной работы программы на вводимые данные в таблицу наложены ограничения:

- нельзя вводить отрицательные числа;

- нельзя вводить дробные числа;

- сумма запасов продукции на складе не должна превышать сумму потребностей продукции и наоборот.

Для тестирования программы введем в таблицу значения согласно условию задачи (Рисунок 2).

Рисунок 2 - Условия задачи

Далее нажмем на кнопку "Составить опорный план" после чего у нас появится вторая таблица с опорным планом (Рисунок 3).

Рисунок 3 - Опорный план

Далее нажмем на кнопку "Оптимизация" после чего у нас оптимизируется вторая таблица с опорным планом и справа в строке черным подчеркнутым шрифтом у нас выведутся общие затраты на перевозку продукции (Рисунок 4).

Рисунок 4 - Оптимизация

Как видно, решение программно совпадает с аналитическим решением, следовательно, можно сделать вывод о том, что программа работает верно.

4.4 Руководство пользователя

После запуска данного приложения (Программа.exe) откроется окно (Рисунок 5).

Рисунок 5 - Стартовое окно

В правой верхней части окна находятся 4 кнопки, при нажатии на которые будет происходить определенные операции (Рисунок 6).

Рисунок 6 - Кнопки

При нажатии кнопки "Начало" (1) - появится таблица для ввода исходных данных задачи (Рисунок 7).

Рисунок 7 - Начало

Далее требуется правильно ввести исходные данные задачи или же нажать на кнопку "Задача" (2), при нажатии на которую введутся автоматически уже готовые исходные данные (Рисунок 8).

Рисунок 8 - Задача

Далее требуется нажать кнопку "Составить опорный план" (3), после нажатия на которую, появится вторая таблица с найденным опорным планом, а так же справа выйдет краткий список расчетов и общие затраты на перевозку продукции по данному плану (Рисунок 9).

Рисунок 9 - Опорный план

Далее требуется нажать кнопку "Оптимизация" (4), при нажатии на которую, произойдет оптимизация данного опорного плана и справа выйдут общие затраты на перевозку продукции по данному плану.

Так же в программе имеются два меню: "Главная" и "Справка". В свою очередь каждое из них содержит в себе подменю.

Меню "Главная" содержит четыре подменю:

- "Заново (F2)", при выборе этого подменю или нажатии клавиши F2, программа запустится заново, с уже нажатой кнопкой "Начало";

- "Выполнить (Ctrl+Enter)", при выборе этого подменю или нажатии сочетания клавиш Ctrl+Enter, программа выполнит все функции автоматически и выведет конечный результат расчета;

- "Очистить (F3)", при выборе этого подменю или нажатии клавиши F3, программа очистить все действительные расчеты и таблицы;

- "Выход (F4)", при выборе этого подменю или нажатии клавиши F4, программа закончит свою работу и выйдет оболочку операционной системы.

Меню "Справка" содержит одно подменю "О программе… (F1)", при выборе которого или нажатии клавиши F1, программа откроет вспомогательное окно с краткой справкой об этой программе.

Примечание: данная программа решает только сбалансированные задачи с 3-мя поставщиками и 5-ю потребителями. А так же для корректной работы программы кнопки следует нажимать в строгом порядке, приведенном в руководстве пользователя.

Заключение

Наиболее распространенной задачей во всех областях экономики является транспортировка груза или товара с минимальными материальными и временными затратами. Так как существует множество вариантов перевозок товара, что затрудняет получение самого экономичного плана, то следовательно появилась необходимость разработки специальной теории, для того чтобы быстро решать подобные задачи с помощью программ.

Применение математических методов в планировании перевозок дает на многие задачи такого типа. Примером того может служить - "Транспортная задача" объединяющая широкий круг задач с единой математической моделью. Классическая транспортная задача - задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, чаще всего встречаются они в практических приложениях линейного программирования.

Задачей моей курсовой работы было решение транспортной задачи методом минимального элемента и оптимизация данного решения методом потенциалов, составление алгоритма решения и написание программы для автоматизации решения.

Ведь транспортные задачи и по сегодняшний день остаются очень популярными. Ни одна фирма, занимающаяся перевозками товаров любым способом, не обходится без транспортных задач, даже может и не такого типа, но все же. транспортный задача автоматизация математический

С развитием науки и техники интерес к подобного рода задачам будет только возрастать и как следствие понадобится более совершенные алгоритмы для решения подобных задач.

Задачи поиска оптимального плана будет всегда актуальны будут, так как в них находится главное - оптимальное решение, а то есть, кратчайший путь и минимальные затраты, а для любой фирмы, сэкономить средства и время, являются главными критериями наибольшей прибыли. Принципы поиска оптимального плана могут быть использованы не только в транспортных задачах, но и во многих других сферах деятельности.

Мною написанная программа далеко не идеальна в расчетах, но я и не предлагаю ее использовать для решения подобных задач на предприятиях, занимающихся перевозками, моя программа лишь может служить примером решения данных задач, а алгоритм, может понадобиться и для написания полноценной версии подобной программы.

Список использованных источников

Кузнецов А.В., Сакович В.А., Холод Н.И. Высшая математика. Математическое программирование. - Минск: Высшая школа, 2001.

Красс М.С., Чупрынов Б.П. Основы математики и ее приложения в экономическом образовании. - Москва: Дело, 2011.

Банди Б. Основы линейного программирования. - Москва: Радио и связь, 1989.

Партыка Т.Л., Попов И.И. Математические методы. - Москва: Форум, 2007.

Кузнецов Б.Т. Математические методы и модели исследования операций. - Москва: Юнити-Дана 2010.

Размещено на Allbest.ru


Подобные документы

  • Особенности решения транспортной задачи распределительным методом и анализ результатов. Построение математической модели, алгоритма. Создание программы для решения транспортной задачи распределительным методом в программной среде Borland Delphi 7.

    курсовая работа [1000,7 K], добавлен 23.06.2012

  • Условия математической транспортной задачи для ее решения методом потенциалов. Опорный план и проверка целевой функции. Окончательный вариант плана поставок товара предоставленный программой "АОС транспортная задача". Стоимость доставки единицы груза.

    лабораторная работа [1,4 M], добавлен 15.10.2015

  • Создание и реализация алгоритма решения транспортной задачи методом наименьших стоимостей. Схема алгоритма основной программы. Основные шаги алгоритма решения транспортной задачи. Инструкция по эксплуатации программы и обзор результатов ее выполнения.

    курсовая работа [2,0 M], добавлен 12.02.2013

  • Описание алгоритма решения транспортной задачи по планированию перевозки зерна. Ход решения задачи вручную, в программе TORA методом наименьшего элемента, с помощью MS Excel. Разработка программы для решения задачи в общем виде средствами Delphi.

    курсовая работа [2,5 M], добавлен 22.11.2012

  • Составление математической модели решения транспортной задачи. Описание входной и выходной информации. Программно-технические средства, используемые при разработке программы. Общее описание программы, ее назначение, информационная совместимость.

    курсовая работа [49,1 K], добавлен 24.05.2013

  • Критерий эффективности и функции в системе ограничений. Общая постановка задачи линейного программирования. Составление математической модели задачи. Алгоритмы решения задачи симплексным методом. Построение начального опорного решения методом Гаусса.

    курсовая работа [232,4 K], добавлен 01.06.2009

  • Транспортная задача как одна из самых распространенных специальных задач линейного программирования: понятие, основное назначение. Формальное описание метода минимального элемента. Характеристика этапов разработки алгоритма решения поставленной задачи.

    курсовая работа [713,3 K], добавлен 19.10.2012

  • Сущность и назначение основных алгоритмов оптимизации. Линейное программирование. Постановка и аналитический метод решения параметрической транспортной задачи, математическая модель. Метод решения задачи об оптимальных перевозках средствами MS Excel.

    курсовая работа [465,6 K], добавлен 24.04.2009

  • Решение задачи линейного программирования симплекс-методом: постановка задачи, построение экономико-математической модели. Решение транспортной задачи методом потенциалов: построение исходного опорного плана, определение его оптимального значения.

    контрольная работа [118,5 K], добавлен 11.04.2012

  • Создание математической модели, приведение ее к виду задачи линейного программирования. Геометрическая трактовка решения. Определение области допустимых значений. Составление симплекс-таблиц. Разработка опорного плана задачи методом минимального элемента.

    контрольная работа [260,2 K], добавлен 22.12.2013

Работы в архивах красиво оформлены согласно требованиям ВУЗов и содержат рисунки, диаграммы, формулы и т.д.
PPT, PPTX и PDF-файлы представлены только в архивах.
Рекомендуем скачать работу.