Приднестровский государственный университет им. Т. Г. Шевченко
Рыбницкий филиал
Кафедра физики математики и информатики
Курсовая работа
По дисциплине «Исследование операций»
Тема:«Транспортная задача. Венгерский метод»
Выполнил:
Студент IV курса,
специальности «ПОВТиАС»
Козлов Е.В.
Проверила:
преподаватель
Глазова Н.С.
г. Рыбница
2010 г.
ОГЛАВЛЕНИЕ
ВВЕДЕНИЕ
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Классическая транспортная задача – задача о наиболее экономном плане перевозок однородного продукта или взаимозаменяемых продуктов из пунктов производства в пункты потребления, встречается чаще всего в практических приложениях линейного программирования. Линейное программирование является одним из разделов математического программирования – области математики, разрабатывающей теорию и численные методы решения многомерных экстремальных задач с ограничениями.
Огромное количество возможных вариантов перевозок затрудняет получение достаточно экономного плана эмпирическим или экспертным путем. Применение математических методов и вычислительных в планировании перевозок дает большой экономический эффект. Транспортные задачи могут быть решены симплексным методом однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его получить оптимальное решение.
В зависимости от способа представления условий транспортной задачи она может быть представлена в сетевой (схематичной) или матричной (табличной) форме. Транспортная задача может также решаться с ограничениями и без ограничений.
В данной курсовой работе будут рассматриваться математическая постановка транспортной задачи линейного программирования - венгерский метод.
ТРАНСПОРТНАЯ ЗАДАЧА.
ОБЩАЯ ПОСТАНОВКА, ЦЕЛИ, ЗАДАЧИ. ОСНОВНЫЕ ТИПЫ, ВИДЫ МОДЕЛЕЙ.
Под названием “транспортная задача” объединяется широкий круг задач с единой математической моделью. Данные задачи относятся к задачам линейного программирования и могут быть решены симплексным методом. Однако матрица системы ограничений транспортной задачи настолько своеобразна, что для ее решения разработаны специальные методы. Эти методы, как и симплексный метод, позволяют найти начальное опорное решение, а затем, улучшая его, получить оптимальное решение.
В общей постановке транспортная задача состоит в отыскании оптимального плана перевозок некоторого однородного груза с баз потребителям .
Различают два типа транспортных задач: но критерию стоимости (план перевозок оптимален, если достигнут минимум затрат на его реализацию) и по критерию времени (план оптимален, если на его реализацию затрачивается минимум времени).
Обозначим количество груза, имеющегося на каждой из баз(запасы), соответственно ,а общее количество имеющегося в наличии груза–:
(1.1)
;
з
(1.2)
аказы каждого из потребителей (потребности) обозначим соответственно
, а общее количество потребностей –
:
,
Тогда при условии
(1.3)
мы имеем закрытую модель, а при условии
(1.4)
– открытую модель транспортной задачи.
Очевидно, в случае закрытой модели весь имеющийся в наличии груз развозится полностью, и все потребности заказчиков полностью удовлетворены; в случае же открытой модели либо все заказчики удовлетворены и при этом на некоторых базах остаются излишки груза , либо весь груз оказывается израсходованным, хотя потребности полностью не удовлетворены .
Так же существуют одноэтапные модели задач, где перевозка осуществляется напрямую от, например, базы или завода изготовителя к потребителю, и двухэтапные, где между ними имеется “перевалочный пункт”, например – склад.
План перевозок с указанием запасов и потребностей удобно записывать в виде следующей таблицы, называемой таблицей перевозок:
Пункты Отправления | Пункты назначения | Запасы |
| | … | |
| | | … | | |
| | | … | | |
… | … | … | … | … | … |
| | | … | | |
Потребности | | | … | | или |
Условие или означает, с какой задачей мы имеем дело, с закрытой моделью или открытой моделью транспортной задачи. Переменное означает количество груза, перевозимого с базы потребителю : совокупность этих величин образует матрицу (матрицу перевозок).
Очевидно, переменные должны удовлетворять условиям:
(2.1)
(2.1.1)
Система (2.1) содержит уравнений с неизвестными. Её особенность состоит в том, что коэффициенты при неизвестных всюду равны единице. Кроме того, все уравнения системы (2.1) могут быть разделены на две группы: первая группа из т первых уравнений (“горизонтальные” уравнения) и вторая группа из п остальных уравнений (“вертикальные” уравнения). В каждом из горизонтальных уравнений содержатся неизвестные с одним и тем же первым индексом (они образуют одну строку матрицы перевозок), в каждом из вертикальных уравнений содержатся неизвестные с одним и тем же вторым индексом (они образуют один столбец матрицы перевозок). Таким образом, каждая неизвестная встречается в системе (2.1) дважды: в одном и только одном горизонтальном и в одном и только одном вертикальном уравнениях.
Такая структура системы (2.1) позволяет легко установить ее ранг. Действительно, покажем, что совокупность неизвестных, образующих первую строку и первый столбец матрицы перевозок, можно принять в качестве базиса. При таком выборе базиса, по крайней мере, один из двух их индексов равен единице, а, следовательно, свободные неизвестные определяются условием , .Перепишем систему (2.1) в виде
(2.1’)
где символы и означают суммирование по соответствующему индексу. Так, например,
При этом легко заметить, что под символами такого суммирования объединяются только свободные неизвестные (здесь , ).
В рассматриваемой нами системе только два уравнения, а именно первое горизонтальное и первое вертикальное, содержат более одного неизвестного из числа выбранных нами для построения базиса. Исключив из первого горизонтального уравнения базисные неизвестные с помощью вертикальных уравнений, мы получаем уравнение
и
(2.2)
ли короче
где символ означает сумму всех свободных неизвестных. Аналогично, исключив из первого вертикального уравнения базисные неизвестные с помощью горизонтальных уравнений, мы получаем уравнение
(2.2’)
Так как для закрытой модели транспортной задачи , то полученные нами уравнения (2.2) и (2.2’) одинаковы и, исключив из одного из них неизвестное , мы получим уравнение-тождество 0=0, которое из системы вычеркивается.
Итак, преобразование системы (2.1) свелось к замене двух уравнений (первого горизонтального и первого вертикального) уравнением (2.2). Остальные уравнения остаются неизменными. Система приняла вид
(2.3)
В системе (2.3) выделен указанный выше базис: базисные неизвестные из первых т уравнений образуют первый столбец матрицы перевозок, а базисные неизвестные остальных уравнений образуют первую строку матрицы перевозок без первого неизвестного [она входит в первое уравнение системы (2.3)]. В системе (2.3) имеется уравнений, выделенный базис содержит неизвестных, а, следовательно, и ранг системы (2.1) .
Для решения транспортной задачи необходимо кроме запасов и потребностей знать также и тарифы , т. е. стоимость перевозки единицы груза с базы потребителю .
Совокупность тарифов также образует матрицу, которую можно объединить с матрицей перевозок и данными о запасах и потребностях в одну таблицу:
Пункты Отправления | Пункты назначения | Запасы |
| | … | |
|
| |
| | … |
| | |
| | |
|
| |
| | … |
| | |
| | |
… | … | … | … | … | … |
|
| |
| | … |
| | |
| | |
Потребности | | | … | | или |
Сумма всех затрат, т. е. стоимость реализации данного плана перевозок, является линейной функцией переменных :
(2.4)
Требуется в области допустимых решений системы уравнений (2.1) и (2.1.1) найти решение, минимизирующее линейную функцию (2.4).
Таким образом, мы видим, что транспортная задача является задачей линейного программирования. Для ее решения применяют также симплекс-метод, но в силу специфики задачи здесь можно обойтись без симплекс-таблиц. Решение можно получить путем некоторых преобразований таблицы перевозок. Эти преобразования соответствуют переходу от одного плана перевозок к другому. Но, как и в общем случае, оптимальное решение ищется среди базисных решений. Следовательно, мы будем иметь дело только с базисными (или опорными) планами. Так как в данном случае ранг системы ограничений-уравнений равен то среди всех неизвестных выделяется базисных неизвестных, а остальные ·
неизвестных являются свободными. В базисном решении свободные неизвестные равны нулю. Обычно эти нули в таблицу не вписывают, оставляя соответствующие клетки пустыми. Таким образом, в таблице перевозок, представляющей опорный план, мы имеем заполненных и · пустых клеток.
Для контроля надо проверять, равна ли сумма чисел в заполненных клетках каждой строки таблицы перевозок запасу груза на соответствующей базе, а в каждом столбце — потребности заказчика [этим подтверждается, что данный план является решением системы (2.1)].
Замечание 1. Не исключаются здесь и вырожденные случаи, т. е. возможность обращения в нуль одной или нескольких базисных неизвестных. Но эти нули в отличие от нулей свободных неизвестных вписываются в соответствующую клетку, и эта клетка считается заполненной.
Замечание 2. Под величинами , очевидно, не обязательно подразумевать только тарифы. Можно также считать их величинами, пропорциональными тарифам, например, расстояниями от баз до потребителей. Если, например, выражены в тоннах, а в километрах, то величина , определяемая формулой (2.4), является количеством тонно-километров, составляющих объем данного плана перевозок. Очевидно, что затраты на перевозки пропорциональны количеству тонно-километров и, следовательно, будут минимальными при минимуме S. В этом случае вместо матрицы тарифов мы имеем матрицу расстояний.
Другие работы по теме:
Математическая постановка транспортной задачи линейного программирования
Содержание Введение Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Транспортная задача
Юридический техникум Рассмотрено и одобрено ПЦК г. Кропоткин программирования Председатель ПЦК Покалицына О.В. План чтения лекции по учебной дисциплине
Венгерский метод в логистике
Содержание Введение 3 1 Задача о назначениях. Венгерский метод 4 1.1 Задача о назначениях 4 1.2 Венгерский метод решения задачи о назначениях 7 2 Решение задачи о назначениях с помощью венгерского метода 15
Мате Залка
Введение 1 Биография 2 Память 3 Библиография Список литературы Введение Ма́те За́лка (венг. Zalka Mбtй; настоящее имя Бела Франкль, венг. Frankl Bйla; 23 апреля 1896, Матольч, Венгрия — 11 июня 1937, Уэска, Испания) — венгерский писатель и революционер, активный участник гражданских войн в России 1918—1921 и Испании 1936—1939.
Витез, Янош
Янош Витез (венг. Jбnos Vitйz; ок. 1408-1471) — венгерский епископ, канцлер Венгерского королевства, воспитатель Матьяша Хуньяди. Учился в Падуанском университете. Вернувшись в Венгрию, этот сын мелкопоместного хорватского дворянина сделал головокружительную карьеру: от загребского каноника до варадского епископа, а затем эстергомского архиепископа-примаса и канцлера Венгерского королевства.
Клапка, Дьёрдь
Введение 1 Биография 1.1 Участие в революции 1.2 Эмиграция 1.3 Возвращение на родину Введение Дьёрдь Клапка (венг. Klapka Gyцrgy, 7 апреля 1820 — 17 мая 1892) — венгерский военачальник, участник Венгерской революции 1848 года.
Турзо, Дьёрдь
Введение 1 Биография 2 Участие в «деле графини Батори» 3 В искусстве 3.1 Кинематограф Введение Дьёрдь (Юрай) Турзо (1557, замок Льетавский Град у Жилины — 1616, Битча) — венгерский аристократ и государственный деятель. Граф. Палатин Венгрии в 1609—1616 гг.
Европейский пикник
— демонстрация мира на австрийско-венгерской границе вблизи города Шопрон 19 августа 1989 года. С согласием обеих стран открыли пограничные ворота на старой Братиславской дороге между Санкт-Маргаретен (Бургенланд) и Шопронкёхида (Sopronkőhidal) символически на три часа. На этом же месте австрийский министр иностранных дел Алоиз Мок и его венгерский коллега Дьюла Хорн 27 июня 1989 совместно разрезали пограничный забор, чтобы подчеркнуть начатую Венгрией 2 мая 1989 года ликвидацию наблюдательных сооружений.
Северная Трансильвания
Введение 1 История 1.1 После I Мировой войны 1.2 Венгерская аннексия 1.3 Окончание II Мировой войны 3 Источники Список литературы Введение Северная Трансильвания (рум. Transilvania de Nord, венг. Йszaki Erdйly) — историко-культурный венгерский регион в составе горной области Трансильвания, составляющей географический запад современной республики Румыния.
Гавро, Лайош
Введение 1 До 1917 года 2 Гражданская война 3 После Гражданской 4 Арест и смерть 5 Факты Список литературы Введение Ла́йош Га́вро (в СССР также Гавро, Людовик Матвеевич) (28 декабря 1894, Брашов — 23 мая 1938) — венгерский интернационалист, активный участник Гражданской войны в России.
О Коннелл-стрит
Монумент О’Коннелла, именем которого названа улица. О’Коннелл-стрит (ирл. Srбid Uн Chonaill, англ. O'Connell Street) — важнейшая транспортная артерия Дублина. Одна из самых широких улиц в Европе. Ее ширина в южной части — 49 метров, в северной — 46 метров; длина — около 500 метров. Первоначально она называлась Дроэда-стрит, затем — Сэквилл-стрит, а после 1924 года ей было дано имя Дэниэла О’Коннелла, национального лидера Ирландии в начале XIX века.
Лигети, Карой
Введение 1 Биография 2 Память Список литературы Введение Ка́рой Ша́ндор Ли́гети (венг. Ligeti Kбroly Sбndor, 8 декабря 1890, Кишкёрёш, Австро-Венгрия — 2 июня 1919, Омск, Советская Россия) — венгерский революционер-интернационалист, поэт, руководитель венгерской парторганизации при Федерации иностранных групп РСДРП(б) и редактор её газеты, командир венгерского интернационального отряда.
Сабо, Эрвин
Введение 1 Биография 2 Память 3 Работы Список литературы Введение Эрвин Сабо (венг. Szabу Ervin, 23 августа 1877, Сланица — 29 сентября 1918, Будапешт) — венгерский коммунист (изначально левый социал-демократ, затем эволюционировавший в сторону анархо-синдикализма), теоретик марксизма, деятель рабочего движения, историк и социолог.
Иштван I Святой
Король Иштван I Святой Иштван Великий ) (венг. (Szent) I. Istvбn, в латинизированном варианте Стефан I ) (ок. 970/975 — 15 августа 1038) — нитранский князь (995—997), венгерский надьфейеделем (с 997) и первый король Венгерского королевства (с 1000/1001) из династии Арпадов.
Констанция Арагонская
Введение 1 Королева Венгрии 2 Жена императора Фридриха II 3 Браки и дети Введение Констанция Арагонская (1179 — 23 июня 1222 года, Катания) — принцесса из Арагонского королевского дома (Барселонская династия). В первом браке — королева Венгрии, во втором — императрица Священной Римской империи, королева Германии и Сицилии.
Мадьяр, Людвиг Игнатьевич
План Введение 1 Биография 2 Научная деятельность 3 Книги Введение Лайош Мадьяр Людвиг Игнатьевич Мадьяр или Лайош Мадьяр (венг. Ludwig (Lajos) Magyar, настоящее имя — Мильхофер или Мильгорф Лайош, 25 ноября 1891, Иштванди, комитат Шомодь — 2 ноября 1937, СССР) — венгерский историк-китаевед, политолог и экономист.
Битва на реке Шайо
План Введение 1 Предпосылки 2 Соотношение сил 3 Ход битвы 4 Последствия Битва на реке Шайо Введение Битва на реке Шайо (на реке Сайо, Солёной; в долине Мохи) — сражение 11 апреля 1241 года между войсками венгерского короля Белы IV и его брата, хорватского герцога Коломана, с одной стороны, и монгольскими войсками во главе с Батыем, Шибаном, Каданом и Субэдэем, действовавших в рамках Западного похода монголов 1236—1242 годов и, в частности, похода на Юго-Западную Русь и в Центральную Европу 1240—1242 годов.
Оттон III герцог Баварии
План Введение 1 Биография 2 Семья и дети Введение Оттон III (нем. Otto I von Niederbayern, венг. Ottу; 11 февраля 1261(12610211), Бургхаузен — 9 сентября 1312, Ландсхут) — в 1290—1312 годах герцог Нижней Баварии из династии Виттельсбахов, являвшийся с 1305 по 1307 годы венгерским королём под именем Бела V.
Венгерская автономная область
Жёлтый цвет — территории, входившие в область всё время её существования; красный цвет — отделённые в 1960, зелёный — добавленные в 1960 Венгерская автономная область
Королевство Венгрия
План Введение 1 История 1.1 Древневенгерский период 1.2 Первый австрийский период 1.3 Османский период 2 Австро-Венгрия Королевство Венгрия Введение
Погань, Йожеф
План Введение 1 Биография 2 Сочинения 2.1 На английском языке Введение Джон Пеппер Йожеф Погань (венг. Pogбny Jуszef, урожённый Йожеф Шварц, американский псевдоним — Джон Пеппер (англ. John Pepper); 8 ноября 1886, Будапешт — 1938, СССР) — венгерский писатель, журналист, литературный критик, деятель Венгерской советской республики (ВСР), работник Госплана СССР и Коминтерна.
Дудаш, Йожеф
Йожеф Дудаш , венг. Jуzsef Dudбs (22 сентября 1912, Марошвашархей, Венгерское королевство (ныне в составе Румынии) — 19 января 1957, Будапешт) — венгерский и румынский радикальный политический деятель, возглавивший во время Венгерской революции 1956 г. группы боевиков, виновные в массовых погромах и убийствах сотрудников госбезопасности[1].
Альпари, Дьюла
Дьюла Альпари (венг. Alpбri Gyula; 19 января 1882, Дунафёльдвар — 17 июля 1944, концлагерь Заксенхаузен) — венгерский политический деятель и журналист.
Чеснеки де Милвань, Дьюла
Граф Дью́ла Че́снеки де Ми́лвань (28 июня 1914, Чорваш, Королевство Венгрия, Австро-Венгрия — после 1970, Бразилия) — венгерский поэт, переводчик, политик, в годы 2-й мировой войны — формальный правитель марионеточного Пиндско-Мегленского княжества.
Миндсенти, Йожеф
Миндсенти, Йожеф Его Высокопреосвященство кардинал Йо́жеф Ми́ндсенти (венг. Mindszenty Jуzsef, настоящее имя Йожеф Пехм , венг. Jуzsef Pehm; 29 марта 1892 — 6 мая 1975) — венгерский кардинал. Архиепископ Эстергома и примас Венгрии. Кардинал-священник с титулом церкви Санто-Стефано-Ротондо с 18 февраля 1946.
Баттяни, Лайош
Лайош Баттяни де Неметуйвар (венг. Lajos Batthyбny de Nйmetъjvбr, 10 февраля 1807(18070210), Прессбург — 6 октября 1849, Пешт) — венгерский политик, глава правительства Венгрии во время Венгерского восстания 1848—1849 годов.
Фогараши, Бела
Бела Фогараши (венг. Fogarasi Bйla, 25 июля 1891 — 28 апреля 1959) — венгерский философ-марксист. Биография Участник радикального политического движения в Венгрии до Первой мировой войны, видный работник культурного фронта в Венгерской советской республике, соратник Дьёрдя Лукача, участник его «Воскресного кружка», в котором состояли такие деятели венгерской культуры, как Бела Балаш, Фредерик Антал, Арнольд Хаузер и другие.
Балаш, Бела
Бела Балаш (правильнее Балаж , венг. Balбzs Bйla; наст. имя и фамилия Герберт Бауэр , венг. Bauer Herbert, 4 августа 1884, Сегед, — 17 мая 1949, Будапешт) — венгерский писатель, поэт, драматург, сценарист, теоретик кино.
Эффективное распределение ресурсов, транспортная задача
Доклад на тему «Эффективное распределение ресурсов. Транспортная задача.» В настоящее время большое прикладное значение имеет задача распределения ресурсов по работам. Значение этой проблемы определяется, во-первых, ограниченностью ресурсов и, во-вторых, тем, что эффективность ресурсов в разных направлениях может быть различна.
Транспортная задача 5
Содержание Введение Транспортная задача линейного программирования получила в настоящее время широкое распространение в теоретических обработках и практическом применении на транспорте и в промышленности. Особенно важное значение она имеет в деле рационализации постановок важнейших видов промышленной и сельскохозяйственной продукции, а также оптимального планирования грузопотоков и работы различных видов транспорта.
Печ
Венгерский город Печ родился на месте римского поселения. Печ развивался неспешно, в те далекие времена никому и в голову не могло прийти, что именно здесь в будущем расположится епископат, а спустя века вырастет первый венгерский университет.
Секешфехервар
Секешфехервар называли городом королей. Он лежит у истоков венгерской государственности. Это один из древнейших городов страны. Здесь короновали и хоронили королей, хранили корону и коронационные принадлежности.
Кровеносная система Строение и состав крови
Text Graphics Пиноцитоз – поглощение клеткой капелек жидкости. Пиноцитоз – поглощение клеткой капелек жидкости. Фагоцитоз – поглощение клеткой твердых частиц ( возможно и роли частиц выступление бактерий и вирусов) Graphics
Бела Барток (Bartok)
Венгерский композитор, пианист и музыковед-фольклорист. Родился в семье директора сельскохозяйственного училища, музыканта-любителя (играл в местном оркестре) и учительницы. Учился в Будапештской музыкальной академии им. Листа (1899—1903).