Недавно просмотренные:





Главная -> Скачать курсовые -> Транспорт -> Понятие о транспортной задаче

Понятие о транспортной задаче

Содержание

Введение

1. Понятие о транспортной задаче

1.1. Транспортная задача: понятие, история появления

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

1.3. Решение транспортной задачи методом потенциалов

2.Задача о назначениях как частный вид транспортной задачи. Понятие Венгерского метода

2.1. Задача о назначениях

2.2. Венгерский метод решения задачи о назначениях

3. Практическое решение задачи о назначении

Заключение

Список литературы

Выдержки из текста

Введение

Тема представленного проекта – задача транспортного типа о назначениях.

Задача о назначениях [assignment problem] — вид задачи линейного программирования, с помощью которой решаются вопросы типа: как распределить рабочих по станкам, чтобы общая выработка была наибольшей или затраты на заработную плату наименьшими (поскольку для каждой комбинации “рабочий — станок” характерна своя производительность труда), как наилучшим образом распределить экипажи самолетов, как назначить людей на различные должности (отсюда и название задачи) и т. д.

Математически такие задачи — частный случай распределительных задач с той особенностью, что в них объемы наличных и требующихся для выполнения каждой работы ресурсов равны единице, т. е. aj = bj = 1, и все xij=1, если работник i назначен на работу j, или нулю в остальных случаях (обозначения см. в ст. “Распределительные задачи”). Иначе говоря, для выполнения каждой работы расходуется только один вид ресурса, а каждый ресурс может быть использован на одной работе: ресурсы неделимы между работами, а работы — между ресурсами. Исходные данные группируются в таблице, которая называется матрицей оценок, результаты — в матрице назначений.

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

Заключение

В заключении можно сделать вывод о проделанной работе:

Задача о назначениях - частный случай транспортной задачи, в которой количество пунктов производства и потребления равны, т.е транспортная таблица имеет форму квадрата, а объем потребления и производства=1.

Данная задача решается с помощью алгоритма, носящего название "Венгерского метода", состоящего из 3 этапов.

Суть венгерского метода состоит в следующем: Путем прибавления определенным образом найденных чисел к некоторым столбцам и вычитания из них некоторых чисел находят систему так называемых независимых нулей. Набор нулей называется системой независимых нулей, если никакие два (или больше) нуля не лежат на одной линии (в строке или столбце). Если число независимых нулей равно n, то, приняв соответствующие им переменные xij равными 1, а все остальные – равными 0, согласно утверждению 2, получим оптимальный план назначения.

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

Оптимальный план назначения определится положением независимых нулей на последней итерации.

Литература

1. Волков И. К., Загоруйко Е. А.: Математика в техническом университете. Выпуск XX. Исследование операций-М.: МГТУ им. Н. Э. Баумана, 2004. - 436с.

2. Красс М.С., Чупрынов, Б.П.: Основы математики и ее приложения в экономическом образовании- М.: Дело, 2008. - 464с.

3. Невежин В.П., КружиловС.И.: Сборник задач по курсу "Экономико-математическое моделирование": Учебное пособие для вузов-М: Городец, 2005. - 320 с.

4. Фролькис В.С. Введение в теорию и методы оптимизации для экономистов. 2-е изд. - СПб: Питер, 2002. - 320 с.

5. Хазанова Л.Э. Математическое программирование в экономике: Учебное пособие. – М.: Издательство БЕК, 2008. – 141с.

О работе

Автор: . Показать все работы автора

15663

Цена: 450 рублей.

Дисциплина: «Транспорт»

Тема: «Понятие о транспортной задаче»

Тип: «Курсовая работа»

Объем: 26* страниц

Год: 2012

Скачать курсовую

Пароль на скачивание файла (получить пароль):

Укажите результаты вычисления:
8 + 10 =

Продажи полностью автоматические. Пароль выдается сразу после завершения процедуры покупки. Для получения пароля на курсовую «Понятие о транспортной задаче» произведите оплату.
Внимание!!! Работы могут не соответствовать требованиям к оформлению какого-либо конкретного учебного заведения.
Для получения полноценной курсовой или реферата с вашими требованиями сделайте заказ новой работы.

По всем вопросам обращайтесь по почте procom@mail.ru.

Выберите удобный для Вас способ оплаты

Похожие работы:

 

Комментарии:

Текст сообщения:

Ваше имя:

Ваш e-mail:

Укажите результаты вычисления:

6 + 6 =

Понятие о транспортной задаче - Курсовая работа
Number of Queries: 18, Parse Time: 0.086395978927612, 2016-09-22 16:21:55
www.webmoney.ru