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

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

Введение

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

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

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

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

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

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

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

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

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



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

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

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

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

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

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

Известны

,

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

j= 1, 2, …, n

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

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

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



			…
			…
			…
…	…	…	…	…
			…

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

A=(, , …, )

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

B=( , , …, )

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

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

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

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

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

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

i= 1, 2, …, m

j= 1, 2, …, n

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

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

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

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

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

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

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

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

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

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

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

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

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



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

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

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

Пример:

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

	20	30	40
40	3	5	7
50	4	6	10

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

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

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

Z(X)=

Z(X) =+

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

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

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

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

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

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

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



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

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

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

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

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

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

N= m+n-1

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

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



(

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

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

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

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

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

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

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

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

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

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

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

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

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

Алгоритм решения задачи методом потенциалов:

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

2) Строят начальное опорное решение (методом наименьших стоимостей). Количество занятых клеток должно равняться m+n-1. Если количество клеток не совпадает с числом N, то задача называется вырожденной. Чтобы избавиться от вырожденности, необходимо заполнить клетки до совпадения с числом N нулями так, чтобы они не образовывали цикл с уже имеющимися заполненными клетками. В противном случае задача называется невырожденной и можно переходить к следующему этапу алгоритма.

3) Строят систему потенциалов. Для этого решают систему уравнений.

4) Проверяют, выполняются ли условия оптимальности для свободных клеток таблицы.

?ij=

?ij?0

Если ?ij?0, то решение не оптимальна. Таким образом, его нужно улучшить.

5) Переходят к новому опорному решению. Для этого находят клетку таблицы задачи, которой соответствует наименьшая отрицательная оценка min. Затем строят цикл, включающий в свой состав данную клетку и часть клеток занятых опорным решением. Осуществляется сдвиг и возвращаемся обратно к пункту 3 алгоритма решения. Красс М. С., Чупрынов Б.П. «Основы математики и ее приложения в экономическом образовании», Минс, 2001 г. издания

1) Решим конкретный пример с помощью методом потенциалов транспортную задачу:

400 400	150	120	80	50
100	3 20	- 5 80	+ 7 _	11 _
130	1 130	4 _	6 _	3 _
170	5 _	+ 8 40	- 12 80	7 50

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

2) Находим опорное решение методом наименьшей стоимости:

N= m+n-1=3+4-1=6 (невырожденная).

3) F(

3)

Для заполнения клеток вычислим значения потенциалов:



(1; 1)

(1; 2)

(2; 1)

(3; 2)

(3; 3)

(3; 4)

Вычислим оценки для пустых клеток:

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

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

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

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

min

E= min

400 400	150	120	80	50
100	- 3 20	+ 5 0	7 80	11 _
130	1 _	4 _	6 _	3 _
170	+ . 5 _	- 8 120	12 _	7 50

3) F= (

Для заполненных клеток вычислим значения потенциалов:

(1; 1)

(1; 2)

(1; 3)

(2; 1)

(3; 2)

(3; 4)

Оценки

3) F= (

400 400	150	120	80	50
100	- 3 _	5 20	7 80	11 _
130	1 130	4 _	6 _	3 _
170	+ 5 20	- 8 100	12 _	7 50

(1; 2)

(1; 3)

(2; 1)

(3; 1)

(3; 2)

(3; 4)

F (

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

Замечание 2. Можно показать, что если сумму всех затрат по данному плану перевозок выразить через свободные неизвестные [для этого надо исключить базисные неизвестные из выражения для S, см. формулу (2.4)], то коэффициент при каждом из таких неизвестных будет равен алгебраической сумме тарифов по циклу, соответствующему ей в таблице перевозок. Это еще раз подтверждает, что пересчет по циклам является специфической формой применения симплекс-метода к решению транспортной задачи.

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

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

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

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

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

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

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

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

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

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

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



2.3 Распределительный метод

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

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

Определим, как изменится целевая функция при переходе к новому опорному решению. При сдвиге на единицу груза по циклу, соответствующему клетке (l, m), приращение целевой функции равно разности двух сумм:

В клетках, отмеченных знаком “+”, величины груза прибавляются, что приводит к увеличению значения целевой функции F(X), а в клетках, отмеченных знаком “-”, величины груза уменьшаются, что приводит к уменьшению значения целевой функции.

Если разность сумм для свободной клетки ( l, m ) меньше нуля, т.е. ? lm< 0, то перераспределение величины ? по соответствующему циклу приведет к уменьшению значения F(X) на величину ?*?lm, т.е. опорное решение можно улучшить. Если же величины ?lm, называемые оценками, для всех свободных клеток таблицы транспортной задачи неотрицательны, то значениие целевой функции нельзя уменьшить и опорное решение оптимально. Следовательно, признаком оптимальности распределительного метода является условие

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

В результате получится новое опорное решение.

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

Пример. Решить распределительным методом транспортную задачу, исходные данные которой приведены в таблице: b1 b2 b3

		20	40	40
a1	20	1	3	2
a2	30	4	5	7
a3	50	6	8	15

Решение . Строим начальное опорное решение методом минимальной стоимости :

Затем вычисляем значение целевой функции да нем:

F(X1) = 20•1 + 30•5 + 10•8 + 40•15 = 850

Таблица

		b1	b2	b3
		20	40	40
a1	20	20	1		3	0	2
		-				+
a2	30		4	30	5
		+		-			7
a3	50		6	10	8	40	15
				+		-

Находим цикл для свободной клетки (1, 2) таблицы, он включает клетки (1, 2), (1, 3), (3, 3), (3, 2). Вычисляем оценку ?12 = (3 + 15) -- (2 + 8) = 8. Так как ?12 = 8 > 0, переходим к следующей свободной клетке (2, 1). Для нее цикл таков: (2, 1), (1, 1), (1,3), (3, 3), (3, 2), (2, 2) (см. табл.). Оценка ?21 = (4 + 2 + 8) - (1 + 15 + 5) =14 - 21 = -7. Так как ?21| =- -7 < 0, определяем величину груза, перераспределяемого по циклу,

Приращение целевой функции ?F=-7•20=-140. Получим новое опорное решение X2. Значение целевой функции на нем F(X2)=20•2+20•4+10•5+30•8+20•15=710.

		b1	b2	b3
		20	40	40
a1	20		1		3	0	2
a2	30	20	4	10	5	+	7
				-
a3	50		6	30	8	20	15
				+		-

Вычисляем ?11 = (1 + 15 + 5) - (2 + 8 + 4) =7>0 , ? 12 = (3 + 15) - (2 + 8) =8>0, ? 23 = (7 + 8) - (5 + 15)=-5<0, ?31= (6 + 5) - (8 + 4) =-1<0. Оценки можно вычислять до первой отрицательной. Так как?23 =-5<0, осуществляем сдвиг по циклу (2,3), (3,3), (3,2), (2,2) на величину. Приращение целевой функции ?F=-5•10=-50. Получаем третье опорное решение X3. Значение целевой функции на нем F(X3)=20•2+20•4+10•7+40•8+10•15=660.

		b1	b2	b3
		20	40	40
a1	20		1		3	20	2
a2	30	20	4		5	10	7
		-				+
a3	50		6	40	8	10	15
		+		+		-

Вычисляем оценки для свободных клеток ?11 = (1 + 7) - (2 + 4) =2>0 , ?12 = (3 + 15) - (2 + 8) =8>0, ?22 =(5 + 15) - (7 + 8) =5>0, ?31 = (6 + 7) - (4 + 15) =-6<0. Так как ?31 =-6<0, осуществляем сдвиг по циклу (3,1), (2,1), (2,3), (3,3), на величину. Приращение целевой функции ?Fm=-6•10=-60. Получаем четвертое опорное решение X4 Значение целевой функции на нем F(X4)=20 •2+10•4+20•7+10•6+40•8=600.

		b1	b2	b3
		20	40	40
a1	20		1		3	20	2
a2	30	10	4		5	20	7
		-		+
a3	50	10	6	40	8		15
		+		-

Вычисляем оценки для свободных клеток ?11 = (1 + 7) - (2 + 4) =2>0 , ?12 = (3 + 7+ 6) - (2 +4+ 8) =2>0, ?22 =(5 + 6) - (4 + 8) =-1<0. Так как ?22 =-1<0, осуществляем сдвиг по циклу (2,2), (3,2), (3,1), (2,1), на величину. Приращение целевой функции ?F=-1•10=-10. Получаем пятое опорное решение X5.

		b1	b2	b3
		20	40	40
a1	20		1		3	20	2
a2	30	0	4	10	5	20	7
a3	50	20	6	30	8		15

Значение целевой функции на нем F(X5)=20 •2+10•5+20•7+20•6+30•8=590. Вычисляем оценки для свободных клеток ?11 = (1 + 7) - (2 + 4) =2>0 , ?12 = (3 + 7) - (2 +5) =3>0, ?33 =(15 + 5) - (7 + 8) =5>0. Все оценки для свободных клеток положительные, следовательно, последнее опорное решение оптимально.

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

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

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

в рассмотрение вводится фиктивный потребитель с потребностью

и тарифами на перевозку ci ( k +1) =0. Если же

то вводится фиктивный поставщик, запасы которого равны

с тарифами на перевозку c ( n +1)j=0. Этим приемом задача сводится к закрытой транспортной задаче, из оптимального плана которой получается оптимальный план исходной задачи. Заметим, что при составлении начального опорного решения для ускорения вычислений в последнюю очередь следует (хотя и не обязательно) распределять запасы фиктивного поставщика и удовлетворять запросы фиктивного потребителя, несмотря на то, что им соответствуют наименьшие тарифы на перевозку (равные 0). Кузнецов А.В., Сакович В.А. “ Математическое программирование” Минск 2001 г.

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

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

Возможны ограничения двух типов



I ) xlm > а ; 2) xlm<b ,

где а и b - постоянные величины.

1. Если xlm > a , то необходимо прежде, чем решать задачу, сократить (уменьшить) запасы l-го поставщика и запросы m-го потребителя на величину а (зарезервировать перевозку xlm =а). После решения задачи в оптимальном решении следует увеличить объем перевозки xlm на величину а.

2. Если xlm <b , то необходимо вместо m -го потребителя с запросами bm ввести двух других потребителей. Один из них с номером m должен иметь запросы b 'm=b, а другой с номером п + 1- запросы bп+1= bm - b. Стоимости перевозок для этих потребителей остаются прежними, за исключением стоимости cl(n+1) которая принимается равной сколь угодно большому числу М (М >> 1). После получения оптимального решения величины грузов, перевозимых к (n + 1)-му потребителю, прибавляются к величинам перевозок l-го потребителя. Так как cl(n+1)) = М- самая большая стоимость перевозки, то в оптимальном решении клетка с номером (l, n+ 1) останется пустой, xl{n+1) = 0 и объем перевозки хlm не превзойдет b.

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



Глава 3. Применение транспортной задачи для решения экономических задач

3.1 Рассмотрение применения транспортных задач на конкретном примере

Пример:

400 400	150	120	80	50
100	3 20	- 5 80	+ 7 _	11 _
130	1 130	4 _	6 _	3 _
170	5 _	+ 8 40	- 12 80	7 50

N= m+n-1=3+4-1=6 (невырожденная).

3) F(

3)

Для заполнения клеток вычислим значения потенциалов:

(1; 1)

(1; 2)

(2; 1)

(3; 2)

(3; 3)

(3; 4)

Вычислим оценки для пустых клеток:

min

E= min

400 400	150	120	80	50
100	- 3 20	+ 5 0	7 80	11 _
130	1 _	4 _	6 _	3 _
170	+ . 5 _	- 8 120	12 _	7 50

3) F= (

Для заполненных клеток вычислим значения потенциалов:

(1; 1)

(1; 2)

(1; 3)

(2; 1)

(3; 2)

(3; 4)

Оценки

3) F= (

400 400	150	120	80	50
100	- 3 _	5 20	7 80	11 _
130	1 130	4 _	6 _	3 _
170	+ 5 20	- 8 100	12 _	7 50

(1; 2)

(1; 3)

(2; 1)

(3; 1)

(3; 2)

(3; 4)

F (

3.2 Анализ применения транспортных задач в экономике

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

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



Заключение

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

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

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

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

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

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



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

1. Красс М. С., Чупрынов Б.П. «Основы математики и ее приложения в экономическом образовании», Минс, 2001 г. Издания

2. Математическое моделирование в задачах. Белолипецкий В.М., Шокин Ю.И.

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

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