Выполнил:

Студент IV курса,

специальности «ПОВТиАС»

Козлов Е.В.

Проверила:

преподаватель

Глазова Н.С.

г. Рыбница

2010 г.

ОГЛАВЛЕНИЕ

ВВЕДЕНИЕ

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

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

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

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

ТРАНСПОРТНАЯ ЗАДАЧА.

ОБЩАЯ ПОСТАНОВКА, ЦЕЛИ, ЗАДАЧИ. ОСНОВНЫЕ ТИПЫ, ВИДЫ МОДЕЛЕЙ.

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

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

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

Обозначим количество груза, имеющегося на каждой из баз(запасы), соответственно ,а общее количество имею­щегося в наличии груза–:

(1.1)

;

(1.2)

?????? ??????? ?? ???????????? (???????????) ????????? ???????????????, ? ????? ?????????? ???????????? ? :

,

Тогда при условии

(1.3)

мы имеем закрытую модель , а при условии

(1.4)

– открытую модель транспортной задачи.

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

Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.

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

Пункты Отправления	Пункты назначения				Запасы
			…
			…
			…
…	…	…	…	…	…
			…
Потребности			…		или

Условие или означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Перемен­ное означает количество груза, перевозимого с базы потреби­телю : совокупность этих величин образует матрицу (матрицу перевозок).

Очевидно, переменные должны удовлетворять условиям:

(2.1)

(2.1.1)

Система (2.1) содержит уравнений с неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (2.1) могут быть разделены на две группы: первая группа из т первых уравне­ний (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом из горизонталь­ных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы пере­возок). Таким образом, каждая неизвестная встречается в системе (2.1) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.

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

(2.1’)

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

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

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

(2.2)

??? ??????

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

(2.2’)

Так как для закрытой модели транспортной задачи , то полученные нами уравнения (2.2) и (2.2’) одинаковы и, исключив из одного из них неизвестное , мы получим уравнение-тождество 0=0 , которое из системы вычеркивается.

--> ЧИТАТЬ ПОЛНОСТЬЮ <--