Математические методы

Изм.

Лист

№ Документа

Подпись

Дата

Лист

КР.230105.091.07

Введение

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

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

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

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

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

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

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

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

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

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

 

 

1 Постановка транспортной задачи

Транспортная  задача является частным типом задачи линейного программирования и формулируется  следующим образом.  Имеется m пунктов  отправления (или пунктов производства) А_i ., А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц.

Имеется n пунктов назначения (или пунктов  потребления) В₁, ..., В

_m, потребность которых в указанных продуктах составляет b₁,

..., b_n единиц. Известны также транспортные расходы С_ij, связанные с перевозкой единицы продукта из пункта A_i в пункт В_j, i 1, ., m; j 1, n.

    Найти опорный план  транспортной задачи, исходные данные  которой приведены в таблице  1.

Таблица 1

Пункты отправления	Пункты назначения				Запасы
	B1	B2	B3	B4
A1	7	8	1	2	160
A2	4	5	9	8	140
A3	9	2	3	6	170
Потребности	120	50	190	110	470

 

 

 

 

 

 

 

 

 

 

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

Имеется m пунктов отправления (или пунктов  производства) А_i ., А_m, в которых сосредоточены запасы однородных продуктов в количестве a₁, ..., а_m единиц. Имеется n пунктов назначения (или пунктов потребления) В₁, ..., В_m, потребность которых в указанных продуктах составляет b₁,..., b_n единиц, Известны также транспортные расходы С_ij,

связанные с  перевозкой единицы продукта из пункта A_i в пункт В_j, i 1, ., m; j 1, ..., n. Предположим, что

 (1)

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

Пусть х_ij - количество единиц продукта, поставляемого из пункта А

_i в пункт В_j. Подлежащие минимизации суммарные затраты на

перевозку продуктов  из всех пунктов производства во все  пункты потребления

выражаются  формулой:

 (2)

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

Формально это  означает, что

, i 1, ., m  (3)

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

, j 1, ., n (4)

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

x_ij 0, i 1, ..., m; j 1, ..., n  

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

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

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

, j 1, ., n  (5)

 и       

, i 1, ., m,  (6)

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

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

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

 (7)

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

транспортной  задачи.

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

                                                                                                             

 

 

Таблица 2

Пункты отправления	Пункты назначения			Запасы
	В1	Bj	Bn	А1
A1	C11 X11	C1j X1j	C1n X1n	a1
Ai	Ci1 Xi1	Cij Xij	Cin Xin	ai
Am	Cm1 Xm1	Cmj Xmj	Cmn Xmn	am
Потребности	b1	bj	bn

Очевидно, общее наличие груза у поставщиков  равно 

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

,  (8)

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

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

потребления может быть нарушен:

, i 1, ..., m  (9)

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

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

 

3  Методы нахождение опорного плана  транспортной задачи

3.1 Правило "северо-западного угла"

При нахождении опорного плана транспортной задачи методом "северо-западного угла" на каждом шаге рассматривают первый из оставшихся пунктов отправления и первый из оставшихся пунктов назначения. Заполнение транспортной таблицы начинается с левого верхнего угла (северо-западного), двигаясь далее по строке вправо или по столбцу вниз (увеличение i, увеличение j). Переменной Х₁₁ приписывают максимальное значение, допускаемое ограничениями на спрос и запасы.

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

Исходный опорный план, построенный по правилу "северо-западного угла", обычно оказывается весьма далеким от оптимального, так как при его формировании не учитывается стоимость перевозок (величина с_ij). Более совершенным правилом является правило "минимального элемента".

3.2 Правило "минимального элемента"

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

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