транспортная задача пример
Это интересно!!!
транспортная задача алгоритм сборки

транспортная задача алгоритм

Транспортная задача (Венгерский алгоритм). 21 апреля 2011 года в 14:43 Просмотров: 3512.

транспортная, Банк Рефератов …………… Институт ………..
Транспортная задача Выполнил студент ………………………
Москва
2006 Содержание
Введение
Многие задачи, с которыми приходится иметь дело в повседневной практике, являются многовариантными. Среди множества возможных вариантов в условиях рыночных отношений приходится отыскивать наилучшие в некотором смысле при ограничениях, налагаемых на природные, экономические и технологические возможности. В связи с этим возникла необходимость применять для анализа экономических ситуаций и систем математические методы и современную вычислительную технику. Такие методы объединяются под общим названием - математическое программирование. Математическое программирование - область математики, разрабатывающая теорию и численные методы решения многомерных экстремальных задач с ограничениями, т. е. задач на экстремум функции многих переменных с ограничениями на область изменения этих переменных. Функцию, экстремальное значение которой нужно найти в условиях экономических возможностей, называют целевой, показателем эффективности или критерием оптимальности. Экономические возможности формализуются в виде системы ограничений. Все это составляет математическую модель. Математическая модель задачи — это отражение оригинала в виде функций, уравнений, неравенств, цифр и т. д. Модель задачи математического программирования включает: совокупность неизвестных величин, действуя на которые, систему можно совершенствовать. Их называют планом задачи (вектором управления, решением, управлением, стратегией, поведением и др.);
целевую функцию (функцию цели, показатель эффективности, критерий оптимальности, функционал задачи и др.). Целевая функция позволяет выбирать наилучший вариант из множества возможных. Наилучший вариант доставляет целевой функции экстремальное значение. Это может быть прибыль, объем выпуска или реализации, затраты производства, издержки обращения, уровень обслуживания или дефицитности, число комплектов, отходы и т. д.; Эти условия следуют из ограниченности ресурсов, которыми располагает общество в любой момент времени, из необходимости удовлетворения насущных потребностей, из условий производственных и технологических процессов. Ограниченными являются не только материальные, финансовые и трудовые ресурсы. Таковыми могут быть возможности технического, технологического и вообще научного потенциала. Нередко потребности превышают возможности их удовлетворения. Математически ограничения выражаются в виде уравнений и неравенств. Их совокупность образует область допустимых решений (область экономических возможностей). План, удовлетворяющий системе ограничений задачи, называется допустимым. Допустимый план, доставляющий функции цели экстремальное значение, называется оптимальным. Оптимальное решение, вообще говоря, не обязательно единственно, возможны случаи, когда оно не существует, имеется конечное или бесчисленное множество оптимальных решений.

установками генератора случайных чисел. Испытания проводились при М = 50, Т = 20, РС= 1.00 и РМ = 0.10. ЗАКЛЮЧЕНИЕ В этой статье мы исследовали применение нашего генетического алгоритма к задаче канальной трассировки в классической

Один из разделов математического программирования - линейным программированием. Методы и модели линейного программирования широко применяются при оптимизации процессов во всех отраслях народного хозяйства: при разработке производственной программы предприятия, распределении ее по исполнителям, при размещении заказов между исполнителями и по временным интервалам, при определении наилучшего ассортимента выпускаемой продукции, в задачах перспективного, текущего и оперативного планирования и управления; при планировании грузопотоков, определении плана товарооборота и его распределении; в задачах развития и размещения производительных сил, баз и складов систем обращения материальных ресурсов и т. д. Особенно широкое применение методы и модели линейного программирования получили при решении задач экономии ресурсов (выбор ресурсосберегающих технологий, составление смесей, раскрой материалов), производственно-транспортных и других задач.
Начало линейному программированию было положено в 1939 г. советским математиком-экономистом Л. В. Канторовичем в работе «Математические методы организации и планирования производства». Появление этой работы открыло новый этап в применении математики в экономике. Спустя десять лет американский математик Дж. Данциг разработал эффективный метод решения данного класса задач — симплекс-метод. Общая идея симплексного метода (метода последовательного улучшения плана) для решения ЗЛП состоит в следующем: умение находить начальный опорный план; наличие признака оптимальности опорного плана; умение переходить к нехудшему опорному плану. Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача – задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены симплексным методом однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его получить оптимальное решение. В зависимости от способа представления условий транспортной задачи она может быть представлена в сетевой (схематичной) или матричной (табличной) форме. Транспортная задача может также решаться с ограничениями и без ограничений. В работе рассмотрены метод северо-западного угла, метод минимальной стоимости, распределительный метод и метод потенциалов. Алгоритмы решения транспортной задачи Формулировка транспортной задачи

google.ru вводим "транспортная задача" алгоритм и переходим по второй ссылке (конечно место может поменяться).

Однородный груз сосредоточен у m поставщиков в объемах . Данный груз необходимо доставить n потребителям в объемах . Известны , i=1,2,,…,m, j=1,2,…,n- стоимости перевозки единицы груза от каждого I-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны ([3]. Стр 52).
Исходные данные транспортной задачи обычно записываются в таблице 1.
… … … … … … …. …. …
Таблица 1.
Исходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А=( ), вектора запросов потребителей
В=( ) и матрицы стоимостей .
В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, слады, магазины и т.д. Однородными считаются грузы, которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.п. Математическая модель транспортной задачи
Переменными (неизвестными) транспортной задачи являются i=1,2,,…,m, j=1,2,…,n – объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок
.
Так как произведение определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид .
Система ограничений задачи состоит из двух групп уравнений. Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью:
, i=1,2,…,m.
Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей:
, j=1, 2, … , n.
Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так:
, (1)
, i=1,2,…,m , (2)
, j=1, 2, … , n, (3)
, i=1,2,,…,m, j=1,2,…,n (4)
В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е. .
Такая задача называется задачей с правильным балансом , а ее модель – закрытой . Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель – открытой ([5]. Стр 84) .
Математическая формулировка транспортной задачи такова: найти переменные задачи , i=1,2,,…,m, j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).
Математическая модель транспортной задачи может быть записана в векторном виде. Для этого рассмотрим матрицу А системы уравнений-ограничений задачи (2), (3):
.……………………………………………………
А = (6).
……………………………………………………
Сверху над каждым столбцом матрицы указана переменная задачи, коэффициентами при которой являются элементы соответствующего столбца в уравнениях системы ограничений. Каждый столбец матрицы А, соответствующий переменной , является вектором-условием задачи и обозначается через . Каждый вектор имеет всего m+n координат, и только две из них, отличные от нуля, равны единице. Первая единица вектора стоит на i-м месте, а вторая – на (m+j)-м месте, т.е.
Номер
корди-
наты
= ; = .
Обозначим через вектор ограничений (правых частей уравнений (2), (3)) и представим систему ограничений задачи в векторном виде. Тогда математическая модель транспортной задачи запишется следующим образом:
, (7)
= , (8)
, i=1,2,,…,m, j=1,2,…,n (9) Необходимое и достаточное условия разрешимости транспортной задачи
Теорема 1. ([18]. Стр 134) Для того чтобы транспортная задача линейного программирования имела решение, необходимо и достаточно, чтобы суммарные запасы поставщиков равнялись суммарным запросам потребителей:
, т.е. задача должна быть с правильным балансом.
Доказательство. Необходимость. Пусть задача имеет допустимое решение , i=1,2,,…,m, j=1,2,…,n . Докажем, что . Подставим в уравнения системы ограничен

Integer (алгоритм Брезенхема, 1965 г.) IV Методы решения систем уравнений.  5.6. Транспортная задача с ограничениями.Значительное количество экономических


Примеры решения транспортной задачи онлайн. Задача 1. Из трех холодильников Ai, i=13, вмещающих мороженную рыбу в количествах ai т

Артём Михайлович 1 Метод потенциалов предназначен для решения транспортной задачи в матричной  Aлгоритм Шаг 0 Замкнуть задачу, если она не замкнута.


Задание:Реализовать решение транспортной задачи.13 декабря 2008


16. Алгоритм решения транспортной задачи. 1. Построение исходного опорного плана. 2. Оценка полученного плана.

Задача коммивояжера. алгоритм Литтла. Статистика.  Решение транспортной задачи симплекс методом.


Решение транспортной задачи - OnLine. Транспортная задача будет решена методом потенциалов, прямо на сайте


Классификация и особенности категории "Алгоритм решения транспортной задачи на основе метода потенциалов".

6.1. Транспортная задача в матричной постановке и ее свойства 6.2.  Алгоритм начинается с выбора некоторого допустимого базисного плана (первоначальный план


1.3 Алгоритм метода. Для решения транспортной задачи методом потенциалов необходимо: 1. Построить опорный план по данному из методов.


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

30. Введение. Транспортная задача линейного программирования получила в  Несколько позднее аналогичный алгоритм был разработан Данцигом, который


Рекомендуем

rd-ok.ru Телефон: +7 (382) 089-44-12 Адрес: Краснодарский край, Армавир, Посёлок РТС, дом 43