Математическая модель решения транспортной задачи Данный курсовой проект содержит программу для решения транспортной задачи методом потенциалов. otherreferats.allbest.ru/emodel/00016660_0.html. 4 семестр. Программа решает транспортные задачи. скачан 162 раза. дата добавления неизвестна. изменен 03.12.2015 21:06. будет удален через 14 дней. Подробнее. Транспортная задача.. ТРАНСПОРТНАЯ ЗАДАЧА. 1. Постановка транспортной задачи. Транспортная таблица. Рассмотрим следующую задачу, называемую транспортной задачей. Чтобы скачать этот файл зарегистрируйтесь и/или войдите на сайт Программа предназначена для решения транспортных задач с. Ельдештейн Ю. М. ЛОГИСТИКАЗначительная часть логистических операций на пути движения материального потока от первичного источника сырья до конечного потребителя осуществляется с применением различных транспортных средств. Затраты на транспортные операции составляют до 5. Транспортная логистика решает проблемы обеспечения технической и технологической сопряженности участников транспортного процесса, согласования их экономических интересов. К задачам транспортной логистики относят. Постановка транспортной задачи и построение ее математической модели. Построение исходного опорного плана. Метод северо- западного угла. Программа находит начальное решение методом северо-западного угла. не известно, какой путь решения транспортной задачи наиболее короткий. Метод наименьшего элемента. Оптимизация опорного решения. Метод оценки циклов. Метод потенциалов. Транспортные задачи с дополнительными ограничениями. Задачи с обязательными поставками. Методы оптимизации транспортная задача численные. формат. Текст DOS. оценка данной работы. Эту статью по программе на Delphi для решения транспортной задачи оценили на 2 из 5 баллов (на основе 1 мнения от 2 посетителей).. Задачи с запретами. Задача с ограниченной пропускной способностью. Транспортная задача с вырожденным решением. Задачи, приводимые к транспортной. Задача о реконструкции. Задача о назначениях. Решение транспортной задачи с использованием Excel. Исходные данные транспортной задачи. Составление кольцевых маршрутов. Задача коммивояжера. Пример решения задачи составления кольцевых маршрутов. Исходные данные задачи оптимизации кольцевого маршрута. Задача оптимизации прокладки дороги. Пример решения задачи оптимизации прокладки дороги. Данные задачи оптимизации прокладки дороги. Определение оптимального срока замены транспортного средства. Пример решения задачи замены транспортного средства. Исходные данные задачи определения момента замены транспортного средства. Постановка транспортной задачи и построение ее математической модели. Пусть имеется n поставщиков однородной продукции (присвоим им имена – ai) и m потребителей этой продукции (bj). Каждый поставщик может поставлять свою продукцию любому из потребителей. Известны затраты Cij на перевозку единицы продукции от каждого поставщика к каждому потребителю. Необходимо так распределить перевозки, чтобы суммарные затраты были минимальными. Элементы решения – Хij количество продукции, перевозимой от каждого поставщика к каждому потребителю. Структурная схема данной задачи в сетевой постановке приведена на рис. Рисунок 2. 5. 1 – Пример структурной схемы транспортной задачи. Обозначим через Ai возможности поставщиков и через Bj потребности потребителей. Составим математическую модель задачи. Ограничения по производственным мощностям поставщиков. Ограничения по производственным мощностям потребителей. Целевая функция – требование минимизации суммарных затрат на перевозки. В краткой форме записи эта модель имеет вид. Закрытой моделью транспортной задачи называется такая задача, в которой суммарные потребности потребителей равны суммарным возможностям поставщиков, т. Построение исходного опорного плана. Опорный план является основой для оптимизации процесса. Существует несколько способов его построения. Здесь описано два из них. Один из них – метод северо- западного угла – наиболее простой, но и наименее эффективен, второй – метод наименьшего элемента несколько сложнее, но значительно ближе к оптимальному. Метод северо- западного угла. Существует несколько методов составления исходного опорного плана. Самый простой из них – метод «северо- западного угла». Исходные данные примера (затраты на перевозку единицы продукции от каждого поставщики к каждому потребителю) приведены в верхних правых углах таблицы 2. Таблица 2. 5. 1. Опорный план решения транспортной задачи, составленный методом «северо- западного угла»Запасы поставщиков. Потребности потребителей. B1=1. 00. B2=2. 00. B3=5. 0B4=2. 52. B5=7. A1=1. 27. 40. 51. A2=1. 52. 70. 35. A3=2. 25. 27. 40. A4=1. 75. 55. 85. Метод наименьшего элемента состоит в заполнении клеток, начиная с тех, в которых стоят наименьшие затраты на перевозку (см. В данном случае минимальную стоимость имеют перевозки по каналу А4- В2 – 8 у. Ставим в эту клетку максимально возможное количество перевозок – 1. А4=1. 75). Следующие по затратам на перевозку каналы А4- В5 и А4- В4. Однако, возможности А4 уже исчерпаны, поэтому далее заполняется клетка, соответствующая каналу А2- В4, в которую ставим 1. А2=1. 52). Далее заполняем клетку А2- В2. Сюда можно поставить только 2. А4. Следующие по затратам перевозки по каналу А2- В4 – 1. В эту клетку можно поставить только 1. А2=1. 52, а он уже поставил 2. В2. Канал А2- В5 и А3- В2 не рассматриваем, т. А2 уже исчерпаны, а потребности В2 полностью удовлетворены. Поэтому затем заполняется клетка, соответствующая каналу А3- В3 (затраты на перевозку – 4. В дальнейшем транспортная таблица заполняется аналогично. Метод наименьшего элемента. Исходные данные примера приведены в верхних правых углах таблицы 2. Таблица 2. 5. 2. Опорный план решения транспортной задачи, составленный методом «наименьшего элемента»Запасы поставщиков. Потребности потребителей. B1=1. 00. B2=2. 00. B3=5. 0B4=2. 52. B5=8. A1=1. 27. 40. 51. A2=1. 52. 70. 35. A3=2. 32. 57. 40. A4=1. 75. 55. 85. Заполнение таблицы начинается с клетки, соответствующей минимальной стоимости перевозок. Такой клеткой в данном случае является канал А4- В2. Поставим сюда 1. 75 единиц, т. А4=1. 75. Следующая по затратам клетка соответствует каналу А2- В2. По этому каналу можно перевезти 1. В2 уже получил от А4 1. Следующая по затратам клетка А2- В4. Здесь можно осуществить поставки в объеме 1. А2 уже поставляет потребителю В2 2. А2- В4. В дальнейшем таблица заполняется аналогично. Оптимизация опорного решения. Метод оценки циклов. Метод состоит в том, что для каждой свободной клетки составляется и оценивается цикл. Цикл, это прямоугольная фигура, в которой все клетки, кроме первой, заняты. Наиболее типичные примеры циклов приведены на рисунке. Рисунок 2. 5. 2 – Примеры циклов транспортных перестановок. В таблице 2. 5. 3 приведены циклы для исходной задачи, представленной в. В пустой клетке ставим минус, а далее по порядку плюс, минус, плюс, минус и т. Таблица 2. 5. 3. Оценки циклов: Перестановки осуществляются по циклу с наибольшей по модулю отрицательной оценкой. В данном случае это цикл, составленный для клетки А2- В4, имеющий оценку минус 4. По циклу переставляется минимальное число, стоящее в отрицательной вершине. Здесь в отрицательных вершинах стоят 1. Переставляем 1. 27, путем вычитания этого числа из отрицательных вершин и прибавления в положительные. В результате получается новый план, приведенный в таблице 2. Таблица 2. 5. 4. План перевозок после первой перестановки. Запасы поставщиков. Потребности потребителей. B1=1. 00. B2=2. 00. B3=5. 0B4=2. 52. B5=7. A1=1. 52. 70. 22. A2=1. 27. 15. 81. A3=2. 25. 27. 16. A4=1. 75. 55. 85. Для этого плана снова составляются и оцениваются все циклы, Процедура повторяется до тех пор, пока есть отрицательные циклы. После каждой итерации вычисляется целевая функция – суммарные затраты на перевозку. В данном случае. F=7. При использовании данного метода для наглядности каждый цикл рекомендуется обозначать своим цветом. Метод потенциалов. Каждому поставщику поставим в соответствие некоторый потенциал αi, а каждому потребителю – потенциал βj (см. Таблица 2. 5. 5. Присвоим любому потенциалу произвольное значение, например α3=0. Остальные потенциалы легко определяются из условия, что для любой занятой клетки. Zij. Для каждой свободной клетки вычислим псевдостоимость. Zij – Pij. Запишем псевдостоимость в левых нижних уголках свободных клеток, а разность в кружках. Сравнивая эти разности с результатами, полученными в предыдущем разделе, убеждаемся, что эти разности характеризуют оценки соответствующих циклов. Для клетки с наибольшей по модулю отрицательной разностью составляется единственный цикл, по которому и производится перестановка. Перестановки могут осуществляться и сразу по нескольким циклам, но только в том случае, если они охватывают разные клетки. По циклам, как и ранее, переставляется минимальное количество грузов, стоящее в отрицательных клетках. Процедура повторяется до тех пор, пока есть отрицательные циклы. Транспортные задачи с дополнительными ограничениями. Задачи с обязательными поставками. В качестве примера решения такой задачи рассмотрим исходные данные, приведенные в таблице 2. Таблица 2. 5. 6. Исходная транспортная таблица задачи с обязательными поставками. Запасы поставщиков. Потребности потребителей. B1=1. 00. B2=2. 00. B3=5. 0B4=2. 50. B5=1. Распределение перевозок. A1=2. 00. 40. 15. A2=1. 50. 72. 55. A3=2. 25. 55. 40. A4=1. 75. 55. 25. Пусть, в силу определенных обстоятельств (например, госзаказ), третий поставщик А3, несмотря на фактические затраты, обязан поставить четвертому потребителю В4 не менее 1. Исключим эту обязательную поставку из транспортной таблицы (см. Таблица 2. 5. 7. Транспортная таблица с исключенными обязательными поставками. Запасы поставщиков. Потребности потребителей. B1=1. 00. B2=2. 00. B3=5. 0B4=1. 50. B5=1. Распределение перевозок. A1=2. 00. 40. 15. A2=1. 50. 72. 55. A3=1. 25. 55. 40. A4=1. 75. 55. 25. Затем решается обычная транспортная задача, но при определении суммарных затрат на перевозки необходимо учесть и затраты на обязательные поставки: 1. Задачи с запретами. В ряде случаев поставки по некоторым каналам оказываются недопустимыми. Это, например, могут быть условия технологии (предприятии, производящее продукцию на экспорт не может потреблять сырье низкого качества), отсутствие у потребителя подходящей взлетно- посадочной полосы для приема воздушных транспортных средств и пр. Исходная транспортная таблица задачи с запретами, составленная методом наименьшего элемента, приведена в таблице 2. Таблица 2. 5. 8. Исходная транспортная таблица задачи с запретами, составленная методом наименьшего элемента. Запасы поставщиков. Потребности потребителей. B1=1. 00. B2=2. 00. B3=5. 0B4=2. 52. B5=1. Распределение перевозок. A1=2. 27. 40. 54. A2=1. 52. 70. 15. A3=2. 25. 50. 40. A4=1. 75. 14. 25. Пусть в силу некоторых обстоятельств поставки по каналу А1- В2 невозможны. Поставим в соответствующую клетку транспортной таблицы вместо реальной стоимости перевозки М (сколь угодно большое число, большее любого наперед заданного числа). Решаем эта задачу методом потенциалов, так как это было показано в разделе 2.
0 Comments
Leave a Reply. |
AuthorWrite something about yourself. No need to be fancy, just an overview. Archives
November 2016
Categories |