Транспортная задача для определения минимальных затрат на перевозку цемента

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

Содержание

Введение

Глава 1. Транспортная задача как частный случай общей распределительной задачи

1.1 Общая характеристика распределительных задач

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

Глава 2. Решение транспортной задачи для определения минимальных затрат на перевозку цемента (ООО База строительных материалов «ЛИДЕР», г. Кунгур Пермский край)

Заключение

Список использованной литературы

Введение

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

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

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

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

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

1. Определение сущности распределительных задач и возможности их эффективного применения в экономике;

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

3. Рассмотрение действенности транспортной задачи при определении минимальных затрат на перевозку грузов на примере одной из оптовых баз строительных материалов г. Кунгура Пермского края.

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

Глава 1. Транспортная задача как частный случай общей распределительной задачи

1.1 Общая характеристика распределительной задачи

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

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

В общем случае цель состоит в определении наиболее эффективного метода такого распределения ресурсов по соответствующим переменным, которое оптимизирует некоторый результат функционирования системы. Очень часто в процессе распределения ресурсов полезным инструментом являются методы моделирования. Математическим программированием называется использование математических моделей и методов для разрешения проблем программирования Эддоус М., Стэнсфилд Р. Методы принятия решений // http://sider.nov.ru. 25.11.2011..

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

Распределительные задачи - класс экономико-математических задач, связанных с распределением ресурсов по работам, которые необходимо выполнить Лопатников Л.И. Экономико-математический словарь: Словарь современной экономической науки. М. 2003..

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

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

Большинство распределительных задач можно представить в виде матриц, пример которых приведен в таблице 1.

Таблица 1. Типичная распределительная задача

Ресурсы	Работы, которые нужно выполнить	Объем имеющихся ресурсов
	J1	J2	…	Jj	…	Jn
R1 R2 … Ri ... Rm	С1,1 С2,1 … Сi,1 … Сm,1	С1,2 С2,2 … Сi,2 … Сm,2	… … … … … …	С1,j С2,j … Сi,j … Сm,j	… … … … … …	С1,n С2,n … Сi,n … Сm,n	b1 b2 … bi … bm
Объем требуемых ресурсов	а1	а2	…	аj	…	an

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

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

Если затраты или доход, определяемые объемом Х_i,j ресурса i, выделенного на выполнение работы J_j, равны Х_i,j*С_i,j, то имеем линейную распределительную задачу.

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

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

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

Основные методы решения распределительных задач линейного программирования, построены на допущении, что объемы имеющихся в наличии ресурсов (b_i), требуемые объемы (a_j) и затраты (С_i,j), - точно известны.

Если общий объем наличных ресурсов ?b_i (i = 1…m) равен общей потребности в них ?a_j (j = 1…n), то имеет место сбалансированная (закрытая) распределительная задача. Если же ?a_j ? ?b_i, то задача называется несбалансированной (открытой).

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

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

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

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

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

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

В связи с высокой частотой возникновения подобных ситуаций, транспортная задача - является одной из наиболее распространенных задач экономико-математического программирования (обычно - линейного) См. Лопатников Л.И. Указ. сочин..

Итак, транспортная задача (задача о размещении) - это распределительная задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отельные работы могут быть выполнены с помощью различных комбинаций ресурсов. Примером типичной транспортной задачи является распределение (транспортировка) продукции, находящейся на складах, по предприятиям-потребителям Алисинская Т.В., Сербин В.Д., Катаев А.В. Учебно-методическое пособие по курсу «Экономико-математические методы и модели. Линейное программирование». Таганрог. 2005. С. 50..

Как уже говорилось, стандартная транспортная задача определяется как задача разработки наиболее экономичного плана перевозки продукции одного вида из нескольких пунктов отправления в пункты назначения. При этом величина транспортных расходов прямо пропорциональна объему перевозимой продукции и задается с помощью тарифов на перевозку единицы продукции Алисинская Т.В. и др. Указ. сочин. С. 50..

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

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

Постановка транспортной задачи (ТЗ)

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

Исходные параметры модели ТЗ:

n - количество пунктов отправления

m - количество пунктов назначения

а_i - запас продукции в пункте отправления А_i (i = 1…n) (ед. тов.)

b_j - спрос на продукцию в пункте назначения B_j (j = 1…m) (ед. тов.)

С_ij - тариф (стоимость) перевозки единицы продукции из пункта отправления А_i в пункт назначения В_j (руб./ед. тов.)

Искомые параметры модели ТЗ:

x_ij - количество продукции, перевозимой из пункта направления A_i в пункт назначения B_j (ед. тов.)

L (X) - транспортные расходы на перевозку всей продукции (руб.)

Итак, имеется m пунктов отправления А₁, А₂, …, А_m, в которых сосредоточены запасы каких-то однородных грузов в количестве соответственно а₁, а₂, …, a_m единиц. Имеется n пунктов назначения В₁, В₂, …, В_n, подавших заявки соответственно на b₁, b₂, …, b_n единиц груза. Известны стоимости С_ij перевозки единицы груза от каждого пункта отправления А_i до каждого пункта назначения В_j.

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

Этапы построения модели

1. Определение переменных

2. Проверка сбалансированности задачи

3. Построение сбалансированной транспортной матрицы

4. Задание целевой функции (ЦФ)

5. Задание ограничений

Транспортная модель

L(X) = > min

при условиях:

, ( i = 1 .. n )

, ( j= 1 .. m )(1.1)

X_ij 0 (i = 1 .. m; j= 1 .. n )

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

Таблица 2. Общий вид транспортной матрицы

Пункты отправления, Ai	Пункты потребления, Bj	Запасы, (ед. прод.)
	B1	B2	…	Bm
A1	c11	c12	…	c1m	a1
A2	c21	c22	…	c2m	a2
…	…	…	…	…	…
An	cn1	cn2	…	cnm	an
Потребность (ед. прод.)	b1	b2	…	bm

Из модели (1.1.) следует, что сумма запасов продукции во всех пунктах отправления должна равняться суммарной потребности во всех пунктах потребления, то есть:

(1.2)

Как уже отмечалось, если (1.2) выполняется, то ТЗ называется сбалансированной, в противном случае - несбалансированной.

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

При этом каждый потребитель получает нужное количество продукта

и каждый поставщик отгружает весь произведенный им продукт

.

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

Поскольку ограничения модели (1.1) могут быть выполнены только при сбалансированной ТЗ, то при построении транспортной модели необходимо проверять условие баланса (1.2).

Несбалансированную ТЗ приводят к виду, показанному выше, искусственно: в модель вводятся фиктивный поставщик или фиктивный потребитель, которые балансируют спрос и потребление.

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

b_ф = > 0(1.3)

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

аф = > 0(1.4)

Введение фиктивного потребителя или отправителя повлечет необходимость формального задания фиктивных (реально не существующих) тарифов (с^ф_ij) для фиктивных перевозок.

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

c^ф_ij › max c_ij (i = 1…n; j = 1…m)

На практике возможны ситуации, когда в определенных направлениях перевозки продукции невозможны, например, по причине ремонта транспортных магистралей. Такие ситуации моделируются с помощью введения так называемых запрещающих тарифов (с^з_ij). Запрещающие тарифы должны сделать невозможными, то есть совершенно невыгодными, перевозки в соответствующих направлениях. Для этого величина запрещающих тарифов должна превышать максимальный из реальных тарифов, используемых в модели:

c^з_ij › max c_ij (i = 1…n; j = 1…m)

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

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

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

Гава 2. Решение транспортной задачи для определения минимальных затрат на перевозку цемента (ООО База строительных материалов «Лидер», г. Кунгур Пермский край)

Необходимо организовать оптимальные по транспортным расходам перевозки цемента с двух складов Базы строительных материалов «Лидер» в три розничных торговых точки, принадлежащих этой же компании (Сеть магазинов строительных материалов «Стройный ряд»).

Ежемесячные запасы цемента на складах равны 79,515 т и 101,925 т, а ежемесячные потребности магазинов составляют 68,0 т, 29,5 т и 117,4 т, - соответственно. Цемент на складах хранится и транспортируется по 45 кг. Транспортные расходы (руб./т) по доставке цемента представлены в таблице 3. Между первым складом и второй розничной торговой точкой заключен договор о гарантированной поставке 4,5 т цемента ежемесячно. В связи с ремонтными работами временно невозможна перевозка из второго склада в третью торговую точку.

Таблица 3. Транспортные расходы по доставке цемента (руб./т)

Склады	Розничные торговые точки
	Т1	Т2	Т3
С1	350,00	190,00	420,00
С2	400,00	100,00	530,00

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

Определение переменных

Обозначим через х_ij (меш.) количество мешков с цементом, которые будут перевезены с i-ого склада в j-ую торговую точку.

Проверка сбалансированности задачи

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

· из запаса первого склада a₁ = 79,515 - 4,5 = 75,015 т/мес.;

· из потребности в цементе второй торговой точки b₂ = 29,5 - 4,5 = 25 т/мес.

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

Тогда:

запас цемента на первом складе равен 75,015 т/мес., или

75,015 т/мес.	= 1667 меш./мес.,
0,045 т/меш.

запас цемента на втором складе равен 101,925 т/мес., или

101,925 т/мес.	= 2265 меш./мес.
0,045 т/меш.

Потребность первой розничной торговой точки составляет 68 т/мес., или

68,000 т/мес.	= 1511,1 ? 1512 меш./мес.,
0,045 т/меш.

потребность второй розничной торговой точки составляет 29,5 т/мес., или

29,500 т/мес.	= 655,6 ? 656 меш./мес.,
0,045 т/меш.

потребность третьей розничной торговой точки составляет 117,4 т/мес., или

117,400 т/мес.	= 2608,9 ? 2609 меш./мес.,
0,045 т/меш.

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

Для данной транспортной задачи имеет место соотношение:

1667 + 2265 ‹ 1512 + 656 + 2609

3932 меш./мес. (склады) ‹ 4777 меш./мес. (розничные торговые точки)

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

4777 - 3932 = 845 мешков цемента, откуда следует вывод: данная транспортная задача несбалансированна.

Построение сбалансированной транспортной матрицы

Сбалансированная транспортная матрица представлена в таблице 4. Стоимость перевозки цемента должна быть отнесена к единице продукции, то есть к 1 мешку цемента.

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

420,00 руб./т * 0,045 т/меш. = 18,90 руб./меш.

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

с^ф_3j = 50,00 руб./меш.

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

с^з₂₃ = 100,00 руб./меш.

Таблица 4. Транспортная матрица задачи

Склады	Розничные торговые точки	Запас, мешки
	Т1	Т2	Т3
С1	15,75	8,55	18,90	1667
С2	18,00	4,50	100,00	2265
Сф	50,00	50,00	50,00	845
Потребность, мешки	1512	656	2609	? = 4777

Задание целевой функции

Формальная целевая функция, то есть суммарные затраты на все возможные перевозки цемента, задается следующим выражением:

L (X) = 15,75x₁₁ + 8,55x₁₂ +18,90x₁₃ +

+ 18,00x₂₁ + 4,50x₂₂ + 100,00x₂₃ +(1.5)

+ 50,00x₃₁ + 50,00x₃₂ + 50,00x₃₃ > min (руб./мес.)

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

Задание ограничений

х₁₁ + х₁₂ + х₁₃ = 1667,

х₂₁ + х₂₂ + х₂₃ = 2265,

х₃₁ + х₃₂ + х₃₃ = 845,

х₁₁ + х₂₁ + х₃₁ = 1512,(меш./мес.)

х₁₂ + х₂₂ + х₃₂ = 656,

х₁₃ + х₂₃ + х₃₃ = 2609,

х_ij ? 0

Выбор опорного плана

Таблица 5. Выбор опорного плана

0	656	1011	1667 (С1)
1512	0	0	2265 (С2)
0	0	0	845 (Сф)
1512 (Т1)	656 (Т2)	2609 (Т3)	В (потреб.) /А (запасы)

m = 3, А = (1667, 2265, 845);

n = 3, В = (1512, 656, 2609).

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

х₃₁ = х₃₂ = х₃₃ = 0, так как сумма поданных заявок превышает наличные запасы и склад фиктивный.

х₂₃ = 0, так как доставка цемента со второго склада в торговую точку 3 невозможна.

Сначала определим х₁₂, так как между складом 1 и торговой точкой 2 заключен договор гарантированной поставки.

х₁₂ = min (1667, 656) = 656.

Тогда х₂₂ = 0.

Затем определяем х₁₃, так как только со склада 1 возможна поставка в торговую точку 3.

х₁₃ = min (1667 - 656, 2609) = 1011

Так как теперь только со склада 2 возможна поставка цемента в торговую точку 1, определяем х₂₁.

х₂₁ = min (2265, 1512) = 1512

Тогда х₁₁ = 0.

Расчет суммарных затрат на все возможные перевозки

L (X) = 15,75 * 0 + 8,55 * 656,00 + 18,90 * 1011,00 +

+ 18,00 * 1512,00 + 4,50 * 0 + 100 * 0 +

+ 50,00 * 0 + 50,00 * 0 + 50,00 * 0

L (X) = 5608,80 + 19107,90 + 27216,00 = 51932,70

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

Заключение

транспортная затрата груз перевозка

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

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

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

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

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

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

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

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

Список использованной литературы

1. Алесинская Т.В., Сербин В.Д., Катаев А.В. Учебно-методическое пособие по курсу «Экономико-математические методы и модели. Линейное программирование». Таганрог. 2010.

2. Баева Н.Б. Моделирование экономических процессов. Учебное пособие. Воронеж. 2003.

3. Лопатников Л.И. Экономико-математический словарь: Словарь современной экономической науки. М. 2003.

4. Орлова И.В. Экономико-математическое моделирование. Практическое пособие по решению задач. М. 2004.

5. Попов А.М., Сотников В.Н. Экономико-математические методы и модели. Учебник для бакалавров. М. 2011.

6. Рэйтман М.И. Транспортная задача // Квант. 1974. № 4.

7. Самаров К.Л. Экономико-математические модели: Учебное пособие для студентов // http://www.resjlventa.ru/metod/student/econmatmodels.htm. 24.11.2011.

8. Тынкевич М.А. Экономико-математические методы. Исследование операций: Учебное пособие. Кемерово. 2000.

9. Федосеев В.В. Экономико-математические методы и прикладные модели: Учебное пособие. М. 1999.

10. Эддоус М., Стэнсфилд Р. Методы принятия решений // http://sider.nov.ru. 24.11.2011.

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