Материал: Роль транспортной задачи в экономике

Роль транспортной задачи в экономике

Введение

Я выбрала эту тему курсовой работы, потому что каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Наши средства и ресурсы всегда ограничены. Жизнь была бы менее интересной, если бы это было не так. Чтобы достичь наибольшего эффекта, имея ограниченные средства, надо составить план, или программу действий. Раньше план в таких случаях составлялся «на глазок» (теперь, впрочем, зачастую тоже). В середине XX века был создан специальный математический аппарат, помогающий это делать «по науке». Соответствующий раздел математики называется математическим программированием. Актуальность выбранной тематики курсовой работы заключается в том, что к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования.

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

Для реализации данной цели в работе необходимо решить следующие задачи:

·              рассмотреть транспортную задачу, общую постановку, цели, задачи;

·              изучить основные типы, виды моделей;

·              охарактеризовать методы решения транспортной задачи;

·              проанализировать метод потенциалов как метод решения транспортной задачи.

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

Предметом исследования является транспортная задача, в частности ее применение в решении экономических задач. Объектом исследования выступает метод потенциалов.

Глава 1. Формулировка транспортной задачи

транспортный задача экономический потенциал

1.1 Математическая модель транспортной задачи

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

Формулировка транспортной задачи.

Однородный груз сосредоточен у m поставщиков в объемах , , …, . Данный груз необходимо доставить n потребителям в объемах , , … , .

Известны

,

где i= 1, 2, …, n

j= 1, 2, …, n

- стоимость перевозки единицы груза от каждого i- того поставщика к каждому j- тому потребителю.

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

Исходные данные транспортной задачи обычно записываются в таблице.

Вектор запасов поставщиков

=(, , …, )

Вектор запасов потребителей:

B=( , , …, )

Матрица стоимостей:

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

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

Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.д.

.2 Необходимое и достаточное условия разрешимости транспортной задачи

Переменными транспортной задачи являются

i= 1, 2, …, m

j= 1, 2, …, n

Эти переменные означают объемы перевозок от каждого i- того поставщика к каждому j- тому потребителю. Переменные записываются в виде матричных перевозок:

т.к. произведение * определяет затраты на перевозку груза от i-того поставщика j-тому потребителю, то S-е затраты на перевозку всех грузов равны:

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

Система ограничений задачи состоит из двух групп уравнений:

Первая группа из m уравнений i описывает тот факт, что запасы всех m- поставщиков вывозятся полностью:

Вторая группа из n уравнений выражает требования полностью удовлетворить запасы всех n-потребителей:

.3 Свойство системы ограничений транспортной задачи

Учитывая условия неотрицательности объемов перевозок, математическую модель задачи можно записать так

В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запасам потребителей, т.е.

такая задача называется задачей с правильным балансом, а ее модель закрытой. Если же условие (6.5) не выполняется, то задача будет называться с неправильным балансом, а ее модель открытой.

Математическая формулировка данной задачи такова:

·        найти переменные задачи  удовлетворяющие системе ограничений (6.2) и (6.3), условиям неотрицательности (6.4)

Математическая транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу А системы уравнений- ограничений задачи (6.2) и (6.3):

Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А соответствует переменный  является вектором- условием задачи и обозначается . Каждый вектор имеет m+n координат и два из них не равны нулю, т.е.=1.

Первая единица вектора  стоит на i-ом месте, а вторая на (m+j)-ом месте, т.е.

Обозначим через  вектор ограничений (правых частей уравнений) (6.2) и (6.3). Представим систему ограничений задачи в векторном виде, тогда математическая модель транспортной задачи записывается следующим образом:

Пример:

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

Введем переменные задачи и запишем матрицу перевозок и матрицу стоимости:

Целевая функция задачи- элемент С*X

Целевая функция

Z(X)=

Z(X) =+

Данная функция определяет все суммарные затраты на все перевозки и должна достигнуть своего минимального значения.

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

Аналогичным способом для потребителей:

Таким образом, математическая модель будет записана следующим образом:

с ограничениями:

Условие не отрицательности

Данная функция определяет все суммарные затраты на все перевозки, которая достигнет своего минимального значения.

Глава 2. Методы и способы решения транспортных задач

.1 Методы построения начального опорного решения

Транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами.

Теорема 1. Для того, чтобы задача линейного программирования имело решение, необходимо и достаточно, чтобы суммарные запасы поставщиков было равно суммарным запасам потребителей:

задача должна быть с правильным балансом.

Теорема 2. Ранг системы векторов- условий транспортной задачи равен:

= m+n-1

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

Определение. Цикл- это такая последовательность клеток таблиц транспортной задачи

(

в которой 2 и только 2 клетки расположены в одной строке или столбце, причем, первая и последние клетки также находятся в одной строке или столбце.

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

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

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

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

Циклом пересчета или короче, циклом в таблице перевозок называется последовательность неизвестных, удовлетворяющая следующим условиям:

) Одно из неизвестных последовательности свободное, а все остальные - базисные.

) Каждые два соседних в последовательности неизвестных лежат либо в одном столбце, либо в одной строке.

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

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

Другое условие означает, что у двух соседних неизвестных в цикле либо первые, либо вторые индексы одинаковы.

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