Задача о перевозках реферат

22.09.2019 Савватий DEFAULT 3 comments

Первая база с запасом может полностью удовлетворить потребность второго заказчика. Построение исходного допустимого плана. Цели работы: изучить методы решения транспортной задачи и их реализацию при решении практической задачи. Оглавление Задание Введение Транспортная задача Математическая модель Опорный план Распределительный метод оптимального плана Решение транспортной задачи методом потенциалов Всякий потенциальный план является оптимальным Заключение Список используемой литературы Введение Каждый человек ежедневно, не всегда осознавая это, решает проблему: как получить наибольший эффект, обладая ограниченными средствами. Проверка решений на оптимальность, нахождение новых схем пунктов перевозок. Однако идеи Л.

Особенности постановки классической транспортной задачи и трех способов ее решения. Аспекты вырождения в задачах линейного программирования. Примеры составления первого допустимого плана перевозок. Решение задач с дополнительными условиями, их критерии. Задача о более задача о перевозках реферат плане перевозок однородной или взаимозаменяемой продукции. Выполнение заявок и их стоимость. Методы получения опорного плана Т-задачи.

Определение значений векторов. Вычисление псевдочастот. Значение суммарной стоимости перевозок. Другой способ - способ минимальной стоимости по строке - основан на том, что мы распределяем продукцию от пункта Ai не в любой из пунктов Bj, а в тот, к которому стоимость перевозки минимальна.

Решение задач с дополнительными условиями, их критерии. От этой трудоёмкой работы нас избавляет специальный метод решения транспортной задачи, который называется методом потенциалов. Если каждые два соседних неизвестных цикла соединить отрезком прямой, то будет получено геометрическое изображение цикла — замкнутая ломаная из чередующихся горизонтальных и вертикальных звеньев, одна из вершин которой находится в свободной клетке, а остальные - в базисных клетках. В обоих этих уравнениях коэффициент при равен 1. В то же время каждому ограничению из 6.

Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов и находим минимальную стоимость перевозки из оставшихся пунктов Bj. Во всем остальном этот метод схож задача о перевозках реферат методом северо-западного угла. При этом методе может получиться, что стоимости перевозок Cij и Cik от пункта Ai к пунктам Bj.

В этом случае, с экономической точки зрения, выгоднее распределить продукцию в тот пункт, в котором заявка. Способ минимальной стоимости по столбцу аналогичен предыдущему способу. Их отличие состоит в том, что во втором способе мы распределяем продукцию от пунктов Bi к пунктам Aj по минимальной стоимости Cji.

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

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

Сколько стоит написать твою работу?

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

Перенесем, например, 18 единиц из клетки 1,1 в клетку 2,1 и чтобы не нарушить баланса перенесём те же 18 единиц из клетки 2,3 в клетку 1,3. Получим новый план. Подсчитав стоимость опорного плана она ровняется и стоимость нового плана она ровняется нетрудно убедиться, что стоимость нового плана на единиц меньше. Таким образом, за счёт циклической перестановки 18 единиц груза из одних клеток в другие нам удалось понизить стоимость плана:.

На этом способе уменьшения стоимости в дальнейшем и будет основан алгоритм оптимизации плана перевозок.

Транспортная задача (закрытая, с циклом). Метод потенциалов - подробно и понятно

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

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

Стоимость же плана при этом может меняться: увеличиваться или уменьшатся. Назовём ценой цикла увеличение стоимости перевозок при перемещении одной единицы груза по означенному циклу. Обозначим цену цикла через g.

Курсовая работа: Транспортная задача линейного программирования

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

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

2762248

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

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

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

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

Транспортная задача

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

Этот метод позволяет автоматически выделять циклы с отрицательной ценой и определять их цены. Пусть имеется транспортная задача с балансовыми условиями. Стоимость перевозки единицы груза из Ai в Bj равна C ij; таблица стоимостей задана.

2811435

Требуется найти план перевозок xij, который удовлетворял бы балансовым условиям и при этом стоимость всех перевозок была минимальна. В обоих этих уравнениях коэффициент при равен 1. Правая часть неравенства 6.

Рассмотреть различные методы решения транспортной задачи. Промокод можно применить один раз при первом заказе. План составлен. Удовлетворим эту заявку за счёт запаса 48, имеющегося в пункте А1, и запишем перевозку 18 в клетке 1,1. Геометрическая интерпретация и графический метод решения ЗЛП.

При ограничениях 6. Это решение оптимально лишь в том случае, когда соответствующая ей система оказывается совместной. Эта система возникает из системы 6. В городе N имеется 4 склада Аi, на которых хранится ткань в рулонах и 5 магазинов Bj, занимающихся продажей ткани.

Ниже, в таблице, приведены данные по количеству рулонов на каждом складе, запросы магазинов и стоимость перевозки одного рулона из Аi в Bj. Необходимо составить такой план перевозок, при котором запросы магазинов будут удовлетворены при минимальной суммарной стоимости перевозок. Имеем таблицу:. Составим таблицу. Здесь и далее в нижнем правом углу записываем значение перевозки.

Будем улучшать этот план методом потенциалов: ui- потенциал Аi ,vj- задача о перевозках реферат Bj. Составим таблицу:.

  • Минимизация затрат на реализацию плана перевозок.
  • Рабочая программа по криминалистике для студентов определяет общий объем криминалистических знаний, умений и навыков, которыми должен обладать выпускн
  • Линейное программирование Экономико-математическая модель транспортной задачи.
  • Определение оптимального плана методом потенциалов.
  • Определить для этого плана платежи ai и bj исходя из условия, чтобы в любой базисной клетке псевдостоимости были равны стоимостям.

Получим новую таблицу. Чтобы 4-ый план был невырожденным, оставим в клетке А4В5 нулевую перевозку. Содержательный ответ: Оптимально перевозить так:. В курсовой работе изложены основные подходы и методы задача о перевозках реферат транспортной задачи, являющейся задача о перевозках реферат из наиболее распространенных задач линейного программирования.

Решение данной задачи позволяет разработать наиболее рациональные пути и способы транспортирования товаров, устранить чрезмерно дальние, встречные, повторные перевозки. Все это сокращает время продвижения товаров, уменьшает затраты предприятий и фирм, связанные с осуществлением процессов снабжения сырьем, материалами, топливом, оборудованием и т.

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

В этом случае величины тарифов cij имеют различный смысл в зависимости от конкретной экономической задачи. К таким задачам относятся следующие:. В них cij является таким экономическим показателем, как производительность.

Задача позволяет определить, сколько времени и на какой операции нужно использовать каждый из станков, чтобы обработать максимальное количество деталей. Так как транспортная задача требует нахождения минимума, то значения cij берутся с отрицательным знаком. Имеется m механизмов, которые могут выполнять m различных работ с производительностью cij.

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

Таким образом, важность решения данной задачи для экономики несомненна. Приятно осознавать, что у истоков создания теории линейного программирования и решения, курсовая работа технология с семьей том числе и транспортной задачи, стоял русский ученый — Леонид Витальевич Канторович.

Кузнецов А. Красс М. Плохо Средне Хорошо Отлично. Банк рефератов содержит более тысяч рефератовкурсовых и дипломных работ, шпаргалок и докладов по различным дисциплинам: истории, психологии, экономике, менеджменту, философии, праву, экологии. А также изложения, сочинения по литературе, отчеты по практике, топики по английскому.

Реферат профилактика варикозной болезниДоклад на тему свадьба во францииКак научиться делать доклад
Организация поведения персонала рефератДоклад на тему профилактика сердечно сосудистых заболеванийБрак и сожительство эссе

Всего работ: Курсовая работа: Транспортная задача линейного программирования Название: Транспортная задача линейного программирования Раздел: Рефераты по математике Тип: курсовая работа Добавлен 30 ноября Похожие работы Просмотров: Комментариев: 16 Оценило: 12 человек Средний балл: 4. Курсовая работа по дисциплине экономико—математические методы.

Задача о перевозках реферат 1061

Магазины Склад. RUя там обычно заказываю, все качественно и в срок в любом случае попробуйте, за спрос денег не берут. Главная Рефераты Благодарности.

Лекция 3: Транспортная задача

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

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

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

Если же имеется хотя бы одна клетка с положительной задача о перевозках реферат, то опорное решение не является оптимальным. Переходят к новому опорному решению, на котором значение целевой функции будет меньше. Строят цикл, включающий в свой состав данную клетку и часть клеток, занятых опорным решением. Далее возвращаемся к пункту 3 алгоритма. Строим 1-ое опорное решение методом наименьших стоимостей. Проверяем 1-ое опорное решение на оптимальность методом потенциалов.

Вывод: 1-ый план не является оптимальным. Переходим к новому опорному решению, на котором значение целевой функции будет меньше.

Строим цикл. Проверяем 2-ое опорное решение на оптимальность методом потенциалов. Вывод: 2-ий план не является оптимальным. Проверяем 3-ье опорное решение на оптимальность методом потенциалов. Цена за единицу потока у этих рёбер тоже равна 0. Дальше решается задача нахождения максимального потока минимальной стоимости mincost maxflow.

Только вместо кратчайшего задача о перевозках реферат потока ищется самый дешёвый. Соответственно, в этой подзадаче используется не поиск в ширинуа алгоритм Беллмана — Форда. При возврате потока стоимость считается отрицательной. Но в этом случае процесс решения будет несколько более долгим. При решении несбалансированной транспортной задачи применяют приём, позволяющий сделать её сбалансированной. Для этого вводят фиктивные пункты назначения или отправления.

Задача о перевозках реферат 9868

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