Реферат на тему На выбор

Содержание:

Введение 3
1. Транспортная задача и ее применение 6
2. Методы составления базового опорного плана 9
2.1 Минимального элемента 10
2.2 Метод северо-западного угла 10
2.3. Метод Фогеля 11
3. Основные методы решения транспортных задач 13
3.1. Метод потенциалов 13
3.2 Венгерский метод 15
Заключение 16
Список литературы 19
 

Введение:

Введение
Объектом данного реферата является транспортная задача.
Предметом: обзор использования и разрешения данного типа задач.
В задачи данной работы входит:
1. Сформулировать общий вид транспортной задачи как задачи линейного программирования;
2. Дать краткий обзор использования транспортных задач.
3. Продемонстрировать методику решения типовой транспортной задачи;
Чтобы определить актуальность темы, следует, прежде всего ясно определить о чем идет речь, для в первую очередь определим, что транспортная задача – это задача линейного программирования.
Как сказано в [3] линейное программирование – область математики, разрабатывающая теорию и численные методы решения задач нахождения экстремума (максимума или минимума) линейной функции многих переменных при наличии линейных ограничений, т.е. равенств или неравенств, связывающих эти переменные.
Или, говоря проще, линейное программирование означает, что мы хотим получить оптимальное решение в задачах с линейными функциями.
Общий вид задачи линейного программирования состоит из значения линейной целевой функции (например минимума затрат на что-либо или максимума получаемой прибыли):
F(x)=∑_(i=1)^n▒∑_(j=1)^m▒〖c_ij x_ij 〗
и системы линейных же ограничений:
∑_(i=1)^n▒〖c_ij x_ij 〗.
Первый вопрос, с которым мы сталкиваемся, состоит в том, почему, собственно, транспортная задача выделяется в особый класс задач?

Заключение:

Заключение
В реферате был сформулирован общий вид транспортной задачи как задачи линейного программирования. На конкретном примере было рассмотрено составление первоначального опорного плана, как видим для всех трех способов он получился различным:
Метод минимального элемента Метод северо-западного угла Метод Фогеля
1{30} 3 2{5} 4 1{30} 3{5} 2 4 1{15} 3 2{20} 4
2 1{10} 4{15} 3{25} 2 1{5} 4{20} 3{25} 2{15} 1{10} 4 3{25}
3 5 6 1{15} 3 5 6 1{15} 3 5 6 1{15}
а полученное по методу Фогеля решение и вовсе оказалось оптимальным.
В то же время и венгерский метод и метод потенциалов дали совпадающее единственное решение. Обманчивая легкость венгерского метода в сравнении с применяемым в подавляющем большинстве случаев методом потенциалов объясняется простотой сформулированной задачи. Обычно венгерский метод используется для решения задачи о назначениях.
Можно так же заметить, что оптимальное распределение перевозок в сравнении с полученными опорными планами даже в такой простой задаче дает значительный выигрыш в 15 ед. и 35 ед. ресурсов в сравнении с затраченными 185 ед. В более сложных по структуре реальных задачах выигрыш будет еще больше. Метод Фогеля позволил получить оптимальное решение сразу, но и являлся наиболее трудоемким из рассмотренных.
Как видно из вышеприведенного краткого рассмотрения и разнородности представленной литературы, транспортная задача используется в различных областях человеческой жизни: в частности примеры из литературы относятся к сельскохозяйственной

Фрагмент текста работы:

1. Транспортная задача и ее применение
Условием разрешимости транспортной задачи является условие балансировки:
∑_(i=1)^m▒a_i =∑_(j=1)^n▒b_j .
Соответственно с выполнением условия балансировки транспортные задачи разделяются на сбалансированные или закрытого типа, когда величина спроса равна величине предложения (например, на складах именно столько продукции, сколько требуется потребителям) и несбалансированные (открытого типа), когда в конкретный момент времени потребителям требуется больше или меньше продукции, чем есть на самом деле, в этом случае в математической формулировке возникает неравенство (-а) и вводится фиктивная переменная, дополняющая меньшую из сумм до большей.
В общем случае решение транспортной задачи разбивается на следующие этапы(2-4 дается по [7]):
1. Балансировка задачи при необходимости;
2. Нахождение исходного опорного решения;
3. Проверка этого решения на оптимальность;
4. Переход от одного опорного решения к другому;
Частным случаем транспортной задачи является рассматриваемая как отдельная тема задача о назначениях или задача выбора, заключающаяся в наиболее экономном (эффективном) распределении n «работ» между n «исполнителями».
Тогда m=n и a_i=b_j=1 и условия могут быть записаны как: