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

Обновлено: 05.07.2024

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

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

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

1. Постановка задачи и ее математическая модель

Транспортная задача является частным типом задачи линейного программирования и формулируется следующим образом. Имеется m пунктов отправления (или пунктов производства) А_i …, А_m , в которых сосредоточены запасы однородных продуктов в количестве a₁ , . а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁ , . В_m , потребность которых в указанных продуктах составляет b₁ , . b_n единиц. Известны также транспортные расходы С_ij , связанные с перевозкой единицы продукта из пункта A_i в пункт В_j , i 1, …, m; j 1, . n. Предположим, что

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

Пусть х_ij - количество единиц продукта, поставляемого из пункта А_i в пункт В_j . Подлежащие минимизации суммарные затраты на перевозку продуктов из всех пунктов производства во все пункты потребления выражаются формулой:

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

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

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

x_ij 0, i 1, . m; j 1, . n (4)

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

Определение 1.

Всякое неотрицательное решение системы линейных уравнений

, j 1, …, n и , i 1, …, m,

определяемое матрицей X=(x_ij )(i 1, …, m; j 1, . n), называется планом транспортной задачи.

Определение 2.

План X*=(x*_ij )(i1, …, m; j1, . n), при котором функция

принимает свое минимальное значение, называется оптимальным планом транспортной задачи.

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

Очевидно, общее наличие груза у поставщиков равно , а общая потребность в грузе в пунктах назначения равна единице. Если общая потребность в грузе в пунктах назначения равна запасу груза в пунктах отправления, т.е.

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

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

Введение этого условия приводит к открытой транспортной модели .

Любая транспортная задача, у которой суммарный объем запасов совпадает с суммарным объемом потребностей, имеет решение.

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

Доказательство. Пусть = M > 0.

Тогда величины x_ij = a_i b_j /M (i = 1,2,3, . m ; j = 1,2,3, . n ) являются планом, так как они удовлетворяют системе ограничений

Действительно, подставляя значения в (2) и (3) , находим

Выберем из значений C_ij наибольшее C¢ = max C_ij и заменим в линейной функции ( 1 ) все коэффициенты на C¢ тогда, учитывая ( 2 ) , получим

Выберем из значений C_ij наименьшее C ¢¢ = min C_ij и заменим в линейной функции все коэффициенты на C ¢¢ ; тогда, учитывая ( 2 ) имеем

Объединяя два последних неравенства в одно двойное , окончательно получаем

C ¢¢ M ? Z ? C ¢ M ,

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

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

a) суммарные запасы превышают суммарные потребности ;

b) суммарные потребности превышают суммарные запасы .

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

Найти минимальное значение линейной функции

,i = 1, 2, . m, (случай а)

, i = 1, 2, . m, (случай б)

x_ij ³ 0 (i = 1, 2, . m; j = 1, 2, . n).

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

В случае (а), когда суммарные запасы превышают суммарные потребности, вводится фиктивный потребитель B_n ₊₁ , потребности которого b_n ₊₁ = . В случае (б), когда суммарные потребности превышают суммарные запасы, вводится фиктивный поставщик A_m ₊₁ , запасы которого a_m ₊₁ = .

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

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

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

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

Число переменных X_ij в транспортной задаче с mпунктами отправления и nпунктами назначения равно nm, а число уравнений в системах (2) и (3) равноn+m. Так как мы предполагаем, что выполняется условие (5), то число линейно независимых уравнений равно n+m-1 отличных от нуля неизвестных.

Если в опорном плане число отличных от нуля компонентов равно в точности n+m-1, то план является не выраженным, а если меньше - то выраженным.

Для определения опорного плана существует несколько методов. Три из них - метод северно-западного угла, метод минимального элемента и метод аппроксимации Фогеля - рассмотрены ниже.

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

Как и для всякой задачи линейного программирования, оптимальный план транспортной задачи является и опорным планом.

Для определения оптимального плана транспортной задачи можно использовать изложенные выше методы. Однако ввиду исключительной практической важности этой задачи и специфики ее ограничений [каждое неизвестное входит лишь в два уравнения системы (2) и (3) и коэффициенты при неизвестных равны единице] для определения оптимального плана транспортной задачи разработаны специальные методы. Два из них - метод потенциалов и Венгерский метод - рассматриваются ниже.

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

Составить первоначальный опорный план методом минимального элемента для транспортной задачи вида:

2	3	4	15
11	6	10	1
8	9	3	3
4	1	2	21
10	20	10

Строим первоначальный опорный план методом минимального элемента.

Выясним минимальную стоимость перевозок. Первая перевозка будет осуществляться с пункта производства в пункт потребления и она составит максимально возможное число единиц продукта :. В этом случае, потребности пункта потребления будут удовлетворены полностью. Значит, стоимости столбца 2 можно больше не рассматривать, так как перевозки .Выясним минимальную стоимость перевозок (без учета столбца № 2).

Вторая и третья перевозки будут осуществляться с пункта производства и в пункт потребления и соответственно и составят максимально возможное число единиц продукта : , ;
Четвертая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца и четвертой строки). .
Пятая перевозка осуществляется с пункта в пункт потребления , т.к. (без учета первого, второго столбца, третьей и четвертой строки). .

6. Шестая перевозка осуществляется с пункта в пункт потребления т.к. (без учета первого, второго столбца, первой, третьей и четвертой строки).

Опорный план имеет вид;

10	5	0
0	1	0
0	3	0
0	11	10

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

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

Найти методом аппроксимации Фогеля первоначальный опорный план транспортной задачи:

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

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

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

Хорошо сказал об этом Галилей:

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

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

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

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

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

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

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

Один из классов математических моделей- задачи линейного программирования. Одной из задач линейного программирования является транспортная задача- задача составления оптимального плана перевозок, позволяющего минимизировать суммарный километраж. Транспортная задача, как и задача линейного программирования была впервые поставлена советским экономистом А.Н.Толстым в 1930 году. Разработка общих методов решения задачи линейного программирования и их математическое исследование связано с именем советского ученого Л.В.Канторовича. В 1939 году методам решения задачи линейного программирования посвящено также большое число работ зарубежных ученых. Основной метод решения задачи линейного программирования –симплекс метод- был опубликован в 1949 году Дандигом. Симплекс метод дает решение любой задачи линейного программирования, но если переменных очень много, то решение весьма затруднительно и для более сложных задач симплекс метод стали модифицировать.

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

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

1.1 МАТЕМАТИЧЕСКАЯ ПОСТАНОВКА ЗАДАЧИ

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

Транспортная задача – это задача линейного программирования, которая ставится как задача отыскания оптимального плана перевозки грузов из М пунктов отправления в N пунктов назначения. При этом тарифы перевозки грузов из i - пункта отправления в j – пункт назначения поставлены и известны.

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

Выполнила
студентка 2 курса экономическогофакультета
Специальность: менеджмент организации.
Яковлева Е. И.
Научный руководитель:
К.т.н., доцент Юров В.М.

Москва 2011
СОДЕРЖАНИЕ

Введение.……………………………………………………………………….…..3
Глава 1. Общая математическая формулировка транспортной задачи и методы ее решения……………………………………………………………………………5
1. Общая математическая формулировка транспортной задачи……. ……. 5
2. Общаяматематическая постановка двойственной транспортной задачи. 8
3. Методы решения транспортной задачи……………………………………13
Глава 2. Разработка открытой транспортной задачи и интерпретация ее результатов…………………………………………………………………………….17
2.1. Разработка конкретной модели открытой транспортной задачи и ее решение методом наименьших затрат…………………………………………….……17
2.2. Решение поставленной задачи с помощью средствExcel………………. 21
2.3 Интерпретация результатов расчетов и выработка управленческого решения………………………………………………………. …………………….…. 27
Заключение………………………………………………………………………31
Список используемой литературы…………………………………………….…..33

В настоящее время методы линейного программирования применяются для решения многих экстремальных задач, с которыми довольно часто приходится иметь дело вэкономике. Решение таких задач сводится к нахождению крайних значений (максимума и минимума) некоторых функций переменных величин. С помощью этого метода в промышленном производстве, например, исчисляется оптимальная общая производительность машин, агрегатов, поточных линий (при заданном ассортименте продукции и иных заданных величинах), решается задача рационального раскроя материалов (с оптимальнымвыходом заготовок). В сельском хозяйстве он используется для определения минимальной стоимости кормовых рационов при заданном количестве кормов (по видам и содержащимся в них питательным веществам). Задача о смесях может найти применение и в литейном производстве (состав металлургической шихты). Этим же методом решаются транспортная задача, задача рационального прикрепления предприятийпотребителей к предприятиям производителям.
Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно большое значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков иработы различных видов транспорта. Кроме того, к задачам транспортного типа сводятся многие другие задачи линейного программирования - задачи о назначениях, сетевые, календарного планирования. Основная цель организации перевозок – минимизация затрат на их выполнение. Моя курсовая работа будет посвящена открытой транспортной задаче.
Цель данной курсовой работы – рассмотрение теоретических основлинейного программирования, разработка экономико-математической модели открытой транспортной задачи и её применение для решения конкретной практической задачи. На основе решения этой задачи разработать оптимальное управленческое решение.
Для реализации данной цели в работе необходимо решить следующие задачи:
- рассмотреть теоретические основы линейного программирования
- правильносоставить вербальную постановку задачи
- правильно составить математическую постановку задачи
- решить вручную поставленную задачу
- решить поставленную задачу с помощью компьютерных программ, в нашем случае, с помощью Microsoft Excel
- грамотно обозначить результаты исследования
Объектом исследуемой.

Читайте также: