Юридический техникум Рассмотрено и одобрено ПЦК
г. Кропоткин программирования
Председатель ПЦК
Покалицына О.В.
План чтения лекции по учебной дисциплине
«Математические методы»
Раздел № 2.Линейное программирование.
Тема № 2.5. Транспортная задача.
Место проведения: аудитория.
Литература:
1. Венцель Е.С. Исследование операций. Задач, принципы, методология. – М.: Наука, 1980.
2. Шелобаев С.И. Математические методы и модели в экономике, финансах, бизнесе. – М.:ЮНИТИДАНА, 2001
Учебные вопросы и расчет времени
№п/п |
Учебные вопросы |
Время, мин |
Методические указания |
1.
2.
3.
|
Постановка транспортной задачи.
Математическая модель транспортной задачи.
Методы решения транспортной задачи.
|
1. Вводная часть. Организационный момент. План занятия. Основные требования.
2. Основная часть.
1. Постановка транспортной задачи.
Важным частным случаем задачи линейного программирования является транспортная задача.
Постановка задачи: Пусть имеется
m
поставщиков и
n
потребителей. Мощность поставщиков и спросы потребителей, а так же затраты на перевозку груза для каждой пары «поставщик – потребитель» заданы таблицей.
поставщики
|
потребители
|
В1
|
В2
|
…
|
В
j
|
…
|
Bn
|
Мощность поставщиков
|
A1
|
С11
|
С1
2
|
С1
j
|
С1
n
|
a1
|
A2
|
С21
|
С2
2
|
С2
j
|
С2
n
|
a2
|
…
|
…
|
…
|
…
|
…
|
Ai
|
С
ij
|
С
ij
|
С
ij
|
С
in
|
ai
|
…
|
…
|
…
|
…
|
…
|
Am
|
Cm1
|
Cm2
|
Cmj
|
Cmn
|
am
|
Спрос потребителей
|
b1
|
b2
|
bj
|
bn
|
Найти объемы перевозок каждой пары
«поставщик – потребитель» так, чтобы: мощности всех поставщиков были реализованы; спросы всех потребителей были удовлетворены; суммарные затраты на перевозку были бы максимальны.
Особенности математической модели транспортной задачи:
-система ограничений есть система уравнений, то есть задача ЛП в каноническом виде;
-коэффициенты при неизвестных системы ограничений равны единицы или нулю;
-каждая переменная входит в систему ограничений два раза: один раз в систему ограничений поставок, второй раз – в систему ограничений спроса.
2. Математическая модель транспортной задачи.
Пусть хij – количество груза, перевозимого с i-го в j-й пункт.
Целевая функция: 
Система ограничений:

Для решения задачи составляется таблица. В клетки таблицы записывается стоимость соответствующих перевозок сij и в них же заносятся значения перевозок xij, удовлетворяющих поставленным ограничениям. Клетки с не нулевыми перевозками называются базисными, а с нулевыми – свободными. В зависимости от соотношения между запасами и заявками транспортная задача называется сбалансированной или несбалансированной.
Сбалансированная ТЗ:
Несбалансированная ТЗ: 
Для сбалансированной ТЗ ограничения принимают вид равенств, то есть получаем m+n ограничений, в которых все переменные линейно зависимы. В результате допустимое решение сбалансированной ТЗ может быть получено, если заполнять клетки транспортной таблицы таким образом, чтобы сумма перевозок в каждой строке
должна быть равна запасам ai, а сумма перевозок в каждом столбце
равна соответствующей заявке вj. Вариантов заполнения транспортной таблицы множество, поэтому искомым решением является то из допустимых решений, для которых общая стоимость перевозок будет минимальной.
3.
Методы решения транспортной задачи.
Транспортная задача может быть решена симплекс методом. Однако специфическая форма системы ограничений позволяет упростить симплекс метод.
МЕТОД СЕВЕРО-ЗАПАДНОГО УГЛА. Заполнение клеток происходит последовательно по следующему алгоритму: сначала вывозится груз из пункта А1 и завозится в пункт В1, и этой перевозке х11 присваивается максимально возможное значение. Если заявка пункта В1 выполнена, а в пункте А1 еще остается груз, то он вывозится в пункт В2 и т.д. Если в пункте А1 недостаточно было груза для В1, то недостающий груз берется из А2 и т.д.
После того как спрос потребителя А1 удовлетворен, он выпадает из рассмотрения и т.д.
В1 |
В2 |
В3 |
В4 |
Запасы
|
А1 |
15
5 |
5
7 |
6 |
8 |
20
|
А2 |
6 |
25
7 |
8 |
5 |
25
|
А3 |
5 |
5
4 |
25
6 |
7 |
30
|
А4 |
6 |
5 |
10
7 |
5
4 |
15
|
А5 |
5 |
6 |
6 |
10
6 |
10
|
Заявки
|
15
|
35
|
35
|
15
|
100
|
Стоимость перевозки: W=5*15+5*7+25*7+5*4+25*6+10*7+5*4+10*6=605
Существенным недостатком метода северо-западного угла является то, что он построен без учета стоимости перевозок.
МЕТОД МИНИМАЛЬНОГО ЭЛЕМЕНТА. Заполнение клеток транспортной таблицы начинается с той клетки, в которой значение минимально. В нее записывается максимально возможное значение перевозки хij, которое может быть равно либо запасу аi, либо заявке вj. Если заявка вj выполнена полностью, то j-й столбец больше не рассматривается. Если не вывезенный груз еще остался, то он вывозится в пункт с наименьшим тарифом.
В1 |
В2 |
В3 |
В4 |
Запасы
|
А1 |
15
5 |
7 |
5
6 |
8 |
20
|
А2 |
6 |
7 |
25
8 |
5 |
25
|
А3 |
5 |
30
4 |
6 |
7 |
30
|
А4 |
6 |
5 |
7 |
15
4 |
15
|
А5 |
5 |
5
6 |
5
6 |
6 |
10
|
Заявки
|
15
|
35
|
35
|
15
|
100
|
Стоимость перевозки: W = 30*4+5*6+15*4+15*5+5*6+25*8+5*6 = 545.
РАСПЕРЕДЕЛЕННЫЙ МЕТОД УЛУЧШЕНИЯ ПЛАНА ПЕРЕВОЗОК. Для улучшения плана используют цикл транспортной таблицы. Цикл – это несколько клеток, соединенных замкнутой ломанной с прямыми углами.
Изобразим два цикла: А1В1, А1В2, А2В2, А2В1; А1В3,А1В4, А2В4, А2В6, А1В5, А4В5, А4В3.
поставщики
|
потребители
|
В1
|
В2
|
В3
|
В4
|
В5
|
B
6
|
Мощность поставщиков
|
A1
|
С11
|
С1
2
|
С13
|
С14
|
С15
|
С16
|
a1
|
A2
|
С21
|
С2
2
|
С23
|
С24
|
С25
|
С26
|
a2
|
A
3
|
С31
|
С32
|
С33
|
С34
|
С35
|
С36
|
a
3
|
А4
|
С41
|
С42
|
С43
|
С44
|
С45
|
С46
|
а4
|
A
5
|
С51
|
С52
|
С53
|
С54
|
С55
|
С56
|
a
5
|
Спрос потребителей
|
b1
|
b2
|
в3
|
b
4
|
в5
|
b
6
|
Каждый цикл имеет четное число вершин и ребер, то есть в таблице в каждой строке или столбце может находтся только четное число клеток, содержащих вершины. Поэтому в клетках-вершинах можно менять значения петевозки так, что в сумма по строкам и столбцам не изменяется. Вершины цикла, в которых увеличиваем перевозки «+», а в которых уменьшаем перевозки «-». Величину изменения обозначим ∆, ее будем перемещать по циклу. Максимальное значение ∆, на которое можно уменьшить перевозку, определяется условием неотрицательности перевозок.
Цена цикла q– это изменение стоимости перевозок при перемещении ∆ по циклу, которая равна разности между суммой стоимостей перевозок, соответствующих «+»-ым вершинам и суммой стоимостей «-» -ых вершин.
Q1= (с11+с22)-(с12+с21)
Q2 = (с13+с24+с16+с45)-(с14+с26+с15+с43)
При переносе по циклу к единиц груза, стоимость цикла и стоимость плана перевозок измениться на к единиц. Для улучшения плана перевозок нужно найти «-» цикл и переместить по нему максимально возможное количество груза, до тех пор пока таких циклов не останется. Количество груза, которое можно переместить определяется минимальным значением перевозок в «-» вершинах цикла.
Другие работы по теме:
Методы и модели в экономике
МИНИСТЕРСТВО ОБРАЗОВАНИЯ И НАУКИ РОССИЙСКОЙ ФЕДЕРАЦИИ ГОУ ВПО Омский государственный технический университет Кафедра «Экономика и организация труда»
Транспортная задача
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение Высшего профессионального образования "Волгоградский государственный технический университет"
Улучшение системы выпуска товаров
Решение оптимизационной транспортной задачи: расстановка связей пунктов отправления и назначения, обеспечив вывоз всех грузов из пункта отправления, ввоз во все пункты назначения требуемых объемов грузов и достижения минимального суммарного грузооборота.
Методы решения транспортных задач
Составление системы ограничений и целевой функции по заданным параметрам. Построение геометрической интерпретации задачи, ее графическое представление. Решение транспортной задачи распределительным методом и методом потенциалов, сравнение результатов.
Методы и модели в экономике
Математическая модель задачи (транспортная матрица с опорным планом северо-западного угла) и её решение вычислением потенциалов, графическим, фиктивного пункта методами. Проверка решений на оптимальность, нахождение новых схем пунктов перевозок.
Экономика предприятия
Планирование производства. Суммарная суточная прибыль от производства. Математическая модель задачи. Транспортная задача. Планирование перевозок, чтобы минимизировать суммарные транспортные расходы. Назначение на работы. Планирование портфеля заказов.
Транспортная задача
Составление плана перевозок зерна с учетом данных о потребности в нем и его запасах. Минимизация затрат на реализацию плана перевозок. Методы "северо-западного угла" и "минимального элемента". Новый улучшенный опорный план по методу потенциалов.
Транспорт и связь: мировая транспортная система
Все пути сообщения и транспортные средства в совокупности образуют мировую транспортную систему. Она сформировалась в XX в. В ней можно выделить транспортные системы экономически развитых и развивающихся стран, а также региональные транспортные системы.
Социально-экономическая статистика
Определение численности случайной повторной выборки. Расчет коэффициентов роста и среднегодового прироста объемов реализациии услуг коммунальных предприятий. Исчисление индекса физического объема продукции, производительности и численности рабочих.
Нормативно-правовая документация, регламентирующая деятельность транспорта
1.5. , взаимоотношения видов транспорта между собой и с потребителями. Транспортное законодательство является наиболее стабильным законодательством, и основные его положения, регулирующие отношения, связанные с заключением договора перевозки, с подачей транспортных средств, ответственностью за их неиспользование, утрату, повреждение грузов, предъявлением претензий и т.д., продолжают оставаться неизменными уже многие годы.
Транспортная иммобилизация
Сущность и физиологическое обоснование иммобилизации, ее разновидности и отличительные признаки. Основные принципы транспортной иммобилизации, используемые при этом средства и оборудование, особенности проведения при повреждениях различных частей тела.
Моделирование транспортных процессов
Содержание Введение………………………………………………………………………. 3 Транспортная задача как разновидность методов и моделей в управлении экономическими системами
Анализ экономических задач оптимизации
ФЕДЕРАЛЬНОЕ АГЕНСТВО ПО ОБРАЗОВАНИЮ Государственное образовательное учреждение высшего профессионального образования РОССИЙСКИЙ ГОСУДАРСТВЕННЫЙ ТОГОВО-ЭКОНОМИЧЕСКИЙ УНИВЕРСИТЕТ
Свойства операций над множествами
Содержание Свойства операций над множествами Смежность и инцидентность. Степени вершины графа Определение транспортной сети 1.Свойства операций над множествами
Экономика предприятия 26
СОДЕРЖАНИЕ 1. Задача №1 «Планирование производства» 2. Задача №3 «Транспортная задача» 3. Задача №4 «Назначение на работы» 4. Задача №2 «Планирование портфеля заказов»
по Математическому анализу
Задача 1. Вычислить предел последовательности. Ответ: Задача 2. Вычислить предел последовательности. Ответ: 0 Задача 3. Вычислить предел последовательности.
Решение транспортной задачи
Типичная распределительная задача. Основные методы решения распределительных задач. Транспортная задача как частный случай общей распределительной задачи.
Упаковка и маркировка товара
Упаковка – это разработка и производство вместилища или оболочки для товара. Упаковка включает три слоя: внутренняя упаковка, внешняя и транспортная.
Транспортная задача. Венгерский метод
Приднестровский государственный университет им. Т. Г. Шевченко Рыбницкий филиал Кафедра физики математики и информатики Курсовая работа По дисциплине «Исследование операций»
О Коннелл-стрит
Монумент О’Коннелла, именем которого названа улица. О’Коннелл-стрит (ирл. Srбid Uн Chonaill, англ. O'Connell Street) — важнейшая транспортная артерия Дублина. Одна из самых широких улиц в Европе. Ее ширина в южной части — 49 метров, в северной — 46 метров; длина — около 500 метров. Первоначально она называлась Дроэда-стрит, затем — Сэквилл-стрит, а после 1924 года ей было дано имя Дэниэла О’Коннелла, национального лидера Ирландии в начале XIX века.
Алтус авиабаза
Алтус (авиабаза) Авиабаза ВВС США, расположенная в пределах города Алтус, Оклахома, США. Это в 6 км к востоку от центрального делового района Altus, город в округе Джексон.
Транспортные модели
Оптимальное решение задач транспортного типа, математические модели; определение потребностей в грузах и суммарного объема поставок по пунктам назначения; сведение к минимуму общей суммы затрат на перевозку. Ситуации, ограничивающие транспортную задачу.
Решение транспортной задачи
Определение оптимального плана перевозок однородного груза из k-пунктов отправления в m-пункты назначения. Описание алгоритма нахождения потока минимальной стоимости. Решение транспортной задачи вручную и в среде MathCad, сравнение полученных результатов.
Эффективное распределение ресурсов, транспортная задача
Доклад на тему «Эффективное распределение ресурсов. Транспортная задача.» В настоящее время большое прикладное значение имеет задача распределения ресурсов по работам. Значение этой проблемы определяется, во-первых, ограниченностью ресурсов и, во-вторых, тем, что эффективность ресурсов в разных направлениях может быть различна.
Транспортная задача 2
Лабораторная работа 2 Теоретическая часть Задача о размещении(транспортная задача) – это распределительная задача, в которой работы и ресурсы измеряются в одних и тех же единицах. В таких задачах ресурсы могут быть разделены между работами, и отдельные работы могут быть выполнены с помощью различных комбинаций ресурсов.
Белки
Это линейные биополимеры состоящие из периодических мономеров (альфа аминокислот). Все 10 000 белков образованы 20 аминокислотами.
Кровеносная система Строение и состав крови
Text Graphics Пиноцитоз – поглощение клеткой капелек жидкости. Пиноцитоз – поглощение клеткой капелек жидкости. Фагоцитоз – поглощение клеткой твердых частиц ( возможно и роли частиц выступление бактерий и вирусов) Graphics
ДНК и РНК
Принцип комплементарности оснований. Информационная РНК. Рибосомная РНК. Транспортная РНК.