Транспортная задача. Метод потенциалов и метод минимального элемента. Пример решения транспортной задачи линейного программирования

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

Опорное решение транспортной задачи

Опорным решением транспортной задачи называется любое допустимое решение, для которого векторы условий, соответствующие положительным координатам, линейно независимы. Для проверки линейной независимости векторов условий, соответствующих координатам допустимого решения, используют циклы.
Циклом называется такая последовательность клеток таблицы транспортной задачи, в которой две и только соседние клетки расположены в одной строке или столбце, причем первая и последняя также находятся в одной строке или столбце. Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи , i=1,2,…,m; j=1,2,…,n является опорным только в том случае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла.

Приближенные методы решения транспортной задачи.
Метод вычеркивания (метод двойного предпочтения). Если в строке или столбце таблицы одна занятая клетка, то она не может входить в какой-либо цикл, так как цикл имеет две и только две клетки в каждом столбце. Следовательно, можно вычеркнуть все строки таблицы, содержащие по одной занятой клетке, затем вычеркнуть все столбцы, содержащие по одной занятой клетке, далее вернуться к строкам и продолжить вычеркивание строк и столбцов. Если в результате вычеркивания все строки и столбцы будут вычеркнуты, значит, из занятых клеток таблицы нельзя выделить часть, образующую цикл, и система соответствующих векторов условий является линейно независимой, а решение опорным. Если же после вычеркиваний останется часть клеток, то эти клетки образуют цикл, система соответствующих векторов условий линейно зависима, а решение не является опорным.
Метод «северо-западного угла» состоит в последовательном переборе строк и столбцов транспортной таблицы, начиная с левого столбца и верхней строки, и выписывании максимально возможных отгрузок в соответствующие ячейки таблицы так, чтобы не были превышены заявленные в задаче возможности поставщика или потребности потребителя. На цены доставки в этом методе не обращают внимание, поскольку предполагается дальнейшая оптимизация отгрузок.
Метод «минимального элемента». Отличаясь простотой данный метод все же эффективнее чем, к примеру, метод Северо-западного угла. Кроме того, метод минимального элемента понятен и логичен. Его суть в том, что в транспортной таблице сначала заполняются ячейки с наименьшими тарифами, а потом уже ячейки с большими тарифами. То есть мы выбираем перевозки с минимальной стоимостью доставки груза. Это очевидный и логичный ход. Правда он не всегда приводит к оптимальному плану.
Метод «аппроксимации Фогеля». При методе аппроксимации Фогеля на каждой итерации по всем столбцам и по всем строкам находят разность между двумя записанными в них минимальными тарифами. Эти разности записывают в специально отведенных для этого строке и столбце в таблице условий задачи. Среди указанных разностей выбирают минимальную. В строке (или в столбце), которой данная разность соответствует, определяют минимальный тариф. Клетку, в которой он записан, заполняют на данной итерации.

Пример №1. Матрица тарифов (здесь количество поставщиков равно 4, количество магазинов равно 6):

1 2 3 4 5 6 Запасы
1 3 20 8 13 4 100 80
2 4 4 18 14 3 0 60
3 10 4 18 8 6 0 30
4 7 19 17 10 1 100 60
Потребности 10 30 40 50 70 30

Решение. Предварительный этап решения транспортной задачи сводится к определению ее типа, открытой она является или закрытой. Проверим необходимое и достаточное условие разрешимости задачи.
∑a = 80 + 60 + 30 + 60 = 230
∑b = 10 + 30 + 40 + 50 + 70 + 30 = 230
Условие баланса соблюдается. Запасы равны потребностям. Итак, модель транспортной задачи является закрытой. Если бы модель получилась открытой, то потребовалось бы вводить дополнительных поставщиков или потребителей.
На втором этапе осуществляется поиск опорного плана методами, приведенными выше (наиболее распространенным является метод наименьшей стоимости).
Для демонстрации алгоритма приведем лишь несколько итераций.
Итерация №1. Минимальный элемент матрицы равен нулю. Для этого элемента запасы равны 60, потребности 30. Выбираем из них минимальное число 30 и вычитаем его (см. в таблице). При этом из таблицы вычеркиваем шестой столбец (потребности у него равны 0).

3 20 8 13 4 x 80
4 4 18 14 3 0 60 – 30 = 30
10 4 18 8 6 x 30
7 19 17 0 1 x 60
10 30 40 50 70 30 – 30 = 0 0

Итерация №2. Снова ищем минимум (0). Из пары (60;50) выбираем минимальное число 50. Вычеркиваем пятый столбец.

3 20 8 x 4 x 80
4 4 18 x 3 0 30
10 4 18 x 6 x 30
7 19 17 0 1 x 60 – 50 = 10
10 30 40 50 – 50 = 0 70 0 0

Итерация №3. Процесс продолжаем до тех пор, пока не выберем все потребности и запасы.
Итерация №N. Искомый элемент равен 8. Для этого элемента запасы равны потребностям (40).

3 x 8 x 4 x 40 – 40 = 0
x x x x 3 0 0
x 4 x x x x 0
x x x 0 1 x 0
0 0 40 – 40 = 0 0 0 0 0

1 2 3 4 5 6 Запасы
1 3[10] 20 8[40] 13 4[30] 100 80
2 4 4 18 14 3[30] 0[30] 60
3 10 4[30] 18 8 6 0 30
4 7 19 17 0[50] 1[10] 100 60
Потребности 10 30 40 50 70 30

Подсчитаем число занятых клеток таблицы, их 8, а должно быть m + n – 1 = 9. Следовательно, опорный план является вырожденным. Строим новый план. Иногда приходится строить несколько опорных планов, прежде чем найти не вырожденный.

1 2 3 4 5 6 Запасы
1 3[10] 20 8[40] 13[30] 4 100 80
2 4 4[20] 18 14 3[10] 0[30] 60
3 10 4[10] 18 8[20] 6 0 30
4 7 19 17 0 1[60] 100 60
Потребности 10 30 40 50 70 30

В результате получен первый опорный план, который является допустимым, так как число занятых клеток таблицы равно 9 и соответствует формуле m + n – 1 = 6 + 4 – 1 = 9, т.е. опорный план является невырожденным.
Третий этап заключается в улучшении найденного опорного плана. Здесь используют метод потенциалов или распределительный метод. На этом этапе правильность решения можно контролировать через функцию стоимости F(x). Если она уменьшается (при условии минимизации затрат), то ход решения верный.

Пример №2. Используя метод минимального тарифа, представить первоначальный план для решения транспортной задачи. Проверить на оптимальность, используя метод потенциалов.

30 50 70 10 30 10
40 2 4 6 1 1 2
80 3 4 5 9 9 6
60 4 3 2 7 8 7
20 5 1 3 5 7 9

Пример №3. Четыре кондитерские фабрики могут производить три вида кондитерских изделий. Затраты на производство одного центнера (ц) кондитерских изделий каждой фабрикой, производственные мощности фабрик (ц в месяц) и суточные потребности в кондитерских изделиях (ц в месяц) указаны в таблице. Составить план производства кондитерских изделий, минимизирующий суммарные затраты на производство.

Кондитерская фабрика Стоимость производства одного центнера кондитерских изделий Месячная производительность кондитерских изделий
1 2 3
1 3 4 3 30
2 2 3 5 20
3 1 2 3 10
4 4 5 8 30
Месячная потребность в кондитерских изделиях 30 20 30

Примечание. Здесь предварительно можно транспонировать таблицу затрат, поскольку для классической постановки транспортной задачи сначала следуют мощности (производство), а потом потребители.

Кондитерская фабрика Стоимость производства одного центнера кондитерских изделий Месячная потребность в кондитерских изделиях
1 2 3 4
1 3 2 1 4 30
2 4 3 2 5 20
3 3 5 3 8 30
Месячная производительность кондитерских изделий 30 20 10 30

Пример №4. На строительство объектов кирпич поступает с трех (I, II, III) заводов. Заводы имеют на складах соответственно 50, 100 и 50 тыс. шт. кирпича. Объекты требуют соответственно 50, 70, 40 и 40 тыс. шт. кирпича. Тарифы (ден. ед./тыс.шт.) приведены в таблице. Составьте план перевозок, минимизирующий суммарные транспортные расходы.

Завод Тариф, ден. ед./тыс.шт. Запасы
1 2 3 4
I 2 6 2 3 50
II 5 2 1 7 100
III 4 5 7 8 50
Потребности 50 70 40 40

Пример №5. Транспортная задача, заданная таблицей

будет закрытой если:
А) a=40, b=45
Б) a=45, b=40
В) a=11, b=12
Условие закрытой транспортной задачи: ∑a = ∑b
Находим, ∑a = 35+20+b = 55+b; ∑b = 60+a
Получаем: 55+b = 60+a
Равенство будет соблюдаться только при a=40, b=45

Примеры решения транспортной задачи онлайн

Задача 1. Из трех холодильников Ai, i=1..3, вмещающих мороженную рыбу в количествах ai т, необходимо последнюю доставить в пять магазинов Bj, j=1..5 в количествах bj т. Стоимости перевозки 1т рыбы из холодильника Ai в магазин Bj заданы в виде матрицы Cij, 3×5.
Написать математическую модель задачи и спланировать перевозки так, чтобы их общая стоимость была минимальной.

Задача 2. Построить закрытую модель транспортной задачи.

Задача 3. В таблице приведены исходные данные транспортной задачи: заданы удельные транспортные расходы на перевозку единицы груза, слева указаны возможности поставщиков, а сверху – спрос потребителей.Сформулируйте экономико-математическую модель транспортной задачи, распределительным методом найдите оптимальный план перевозок.
(таблица в файле)

Задача 4. Решить транспортную задачу
1) методом потенциалов (опорный план построить всеми известными способами);
2) методом дифференциальных рент;
3) любым методом при ограничениях: x24≥4, x35≤5, x12=3.
(таблица в файле)

Задача 5. Выполнить решение в программе QM for Windows
Числа в скобках – коэффициенты транспортных расходов, столбец чисел справа от матрицы – запасы груза у поставщиков, строка снизу – потребности потребителей.
1. Решить и проанализировать ТЗ без ограничений.
2. Решить ТЗ с запретом перевозки по самому выгодному пути (с наименьшими затратами).
3. Решить двухэтапную ТЗ с числом поставщиков – 3, складов – 2 и потребителей – 4, взяв за c_ik первых два столбца коэффициентов исходной матрицы, а за c_kj – последние две строки этой матрицы. Мощности складов одинаковы и равны половине суммарных запасов поставщиков, округлённых до целых десятков в большую сторону.

Задача 6. Составить математическую модель транспортной задачи и решить её методом потенциалов. Завод имеет 3 цеха А, В, С и 4 склада №1,2,3,4. Цех А производит 30 тыс.штук изделий, цех В – 40 тыс. штук изделий, С – 20 тыс. штук изделий. Пропускная способность склада №1 – 20 тыс. штук изделий, №2 – 30 тыс. штук изделий, №3 – 30 тыс.штук, №4 – 10 тыс. штук. Стоимость перевозки из цеха А соответственно в склады №1,2,3,4 1 тыс. штук изделий составляет 20, 30, 3, 4 р., из цеха В 1 тыс. – соответственно 3, 20, 5, 1 р., а из цеха С – соответственно 4, 30, 2, 6 р.
Составить такой план перевозок изделий, при котором расходы на перевозку 90 тыс. изделий были бы наименьшими.

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

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

Транспортные задачи бывают двух типов:

  • Закрытая – совокупное предложение продавца равняется общему спросу.
  • Открытая – спрос и предложение не равны. Чтобы решить такую задачу, нужно сначала привести ее к закрытому типу. В этом случае добавляется условный покупатель или продавец с недостающим количеством спроса или предложения. Также в таблицу издержек следует внести соответствующую запись (с нулевыми значениями).

Заказать решение транспортной задачи

Прямо здесь и сейчас в онлайн режиме каждый студент может заказать решение самой сложной задачи или выполнение любой другой работы (курсовой, дипломной, контрольной и т. д.). От пользователя требуется только заполнить специальную форму. Все преимущества сотрудничества с онлайн помощником «Все Сдал!»:

  • Все работы выполняются в минимально короткие сроки
  • Устранение недочетов и дополнения не требуют дополнительной оплаты
  • В отличие от конкурирующих сервисов, здесь самые доступные цены
  • Решение задач оформляется с учетом требований ВУЗа
  • Все работы проверяются на уникальность

И, пожалуй, самое главное, – сотрудничая напрямую с онлайн помощником «Все Сдал!», студенты избегают встречи с недобросовестными исполнителями в лице мелких рефератных компаний, предоставляющих свои услуги по бросовой цене. Попав в руки мошенников велика вероятность того, что заказчик получит неправильно выполненную работу, поэтому деньги, пусть и не совсем большие, будут выброшены на ветер. Чтобы такого не случилось, предлагаем решение транспортной задачи методом потенциалов онлайн заказывать на проверенном и надежном сервисе, каким мы и являемся.

Решение задач на заказ

К нам можно обратиться за решением задач по данной дисциплине. Наши специалисты подробно распишут решение в короткие сроки.
Узнать цену работы можно на странице заказа.

Условие задачи

Поставщики товара – оптовые коммерческиепредприятия mathminsk.com имеют запасы товаров соответственно вколичестве mathminsk.com и розничные торговые предприятия mathminsk.com -подали заявки на закупку товаров в объемахсоответственно: mathminsk.com. Тарифы перевозок единицыгруза с каждого из пунктов поставки в соответствующие пункты потребления заданыв виде матрицы mathminsk.com. Найти такой планперевозки груза от поставщиков к потребителям, чтобы совокупные затраты наперевозку были минимальными.

mathminsk.com

mathminsk.com

mathminsk.com

Виды транспортных задач

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

Условия транспортной задачи можно представить двумя способами:

  • в виде схемы;
  • в виде матрицы.

В процессе решения могут быть ограничения (либо задача решается без них).

По характеру условий различают следующие типы транспортных задач:

  • открытые открытые транспортные задачи (запас товара у поставщика не совпадает с потребностью в товаре у потребителя);
  • закрытые (суммарные запасы продукции у поставщиков и потребителей совпадают).

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



Подготовительный этап: включение функции “Поиск решения”

Чтобы решить транспортную задачу в Эксель, нужно воспользоваться функцией “Поиск решения”, которую нужно предварительно активировать, т.к. изначально она не включена. Алгоритм действий следующий:

  1. Открываем меню “Файл”.Переход в меню Файл в Эксель
  2. В перечне слева выбираем пункт “Параметры”.Переход к параметрам Эксель
  3. В параметрах кликаем по подразделу “Надстройки”. Затем в правой части окна в самом низу, выбрав значение “Надстройки Excel” для параметра “Управление”, щелкаем по кнопке “Перейти”.Переход к надстройкам Excel
  4. В открывшемся окне ставим галочку напротив надстройки “Поиск решения” и жмем OK.Включение надстройки Поиск решения в Эксель
  5. В результате, если мы перейдем во вкладу “Данные”, то увидим здесь кнопку “Поиск решения” в группе инструментов “Анализ”.Поиск решения во вкладке Данные в Excel

Примеры решения сетевой транспортной задачи

Задача 7. Имеется сеть железных дорог, на которой расположены 3 пункта отправления однородного груза и 9 станций его приема. Известны затраты на перевозку грузов от i-ой до j-ой станции. Заданы объемы ресурсов в каждом пункте отправления и объемы прибытия в каждый пункт назначения. Требуется составить оптимальный план перевозок, предусматривающий минимальные суммарные затраты.
1. Пункты 1, 2, 3 – пункты отправления с объемом запаса, соответственно 200, 150 и 150.Потребности пунктов назначения таковы: 4 – 40, 5 – 70, 6 – 40, 7 – 50, 8 – 45,9 – 60,10 – 70,11 – 75,12 – 50.Затраты между соответствующими вершинами заданы: 1-5 – 65, 1-7 – 75, 1-9 – 25, 2-5 – 60, 2-6 – 115, 2-9 – 25, 2-12 – 90, 3-4 – 95, 3-8 – 30, 3-10 – 45, 3-11 – 40, 4-8- 15, 4-12 – 40, 5-7 – 95, 5-9 – 35, 6-8 – 65, 6-9 – 15, 6-11 – 55,6-12 – 80,7-10 – 15,8-11 – 45,9-11 – 35,10-11-110.
2. Пункты 1, 2, 3 – пункты отправления с объемом запаса, соответственно 200,150 и 150.Потребности пунктов назначения таковы: 4 – 40, 5 – 70, 6 – 40, 7 – 50, 8-45,9-60,10-70,11 -75,12-50.Затраты между соответствующими вершинами заданы: 1-5 – 65, 1-7 – 75, 1-9 – 25, 2-5 – 60, 2-6 – 115, 2-9 – 25, 2-12 – 90, 3-4 – 95, 3-8 – 30, 3-10 – 45, 3-11 – 40, 4-8 – 15, 4-12 – 40, 5-7 – 95, 5-9 – 35, 6-8 – 65, 6-9 – 15, 6-11 – 55,6-12 – 80,7-10 – 15,8-11 – 45, 9-11 – 35,10-11 -110.
Для следующих звеньев существуют ограничения на пропускные способности. 1-7 – 40, 1-11 – 10, 2-9 – 15, 3-10 – 30.

Задача 8. Пункты производства и потребления связаны между собой транспортной сетью. В пунктах производства сосредоточено некоторое количество однородного груза, которое необходимо вывезти в пункты потребления. Стоимость перевозки единицы груза на каждом участке (равная Сs) задана. Предполагается, что на каждом участке перевозка грузов осуществляется в одном направлении. Требуется составить такой план перевозки, при котором транспортные расходы будут минимальными.

Решаем транспортные задачи на заказ

Пример задачи и ее решение

Чтобы лучше понять, как решать транспортные задачи в Excel, давайте рассмотрим конкретный практический пример.

Решение задачи

Экономико-математическая модель задачи

Обозначим через mathminsk.com количествогруза, перевозимого от mathminsk.com поставщика mathminsk.com потребителю.Тогда общая стоимость перевозок равна:

mathminsk.com

mathminsk.com

Ограничениядля поставщиков:

mathminsk.com

Ограничения для потребителей:

mathminsk.com

Объем суммарных поставок любогопоставщика к потребителю не может быть отрицательным числом, поэтомусправедливы ограничения:    mathminsk.com

Проверка транспортной задачи на закрытость

Стандартная транспортная задачаразрешима только в том случае, когда выполняется условие баланса:

mathminsk.com

В нашем случае:

mathminsk.com

Модельтранспортной задачи открытая. Вводим фиктивного потребителя, которомутребуется  85 единиц груза.

Правило минимального элемента

Заполняем таблицу по правилуминимального элемента.

Просматривая таблицу замечаем, чтонаименьшие затраты соответствуют маршруту mathminsk.com, поэтому в клетку помещаем mathminsk.com. В этом случае 5-й столбец в расчет не принимается.Просматриваем оставшиеся таблицы клетки. Наименьшие тарифы имеют клетки mathminsk.com и mathminsk.com

mathminsk.com

mathminsk.com

Далее действуя по аналогичной схеме:

mathminsk.com

mathminsk.com

mathminsk.com

mathminsk.com

mathminsk.com

Число занятых клеток должно быть mathminsk.com.

Решение транспортной задачи методом потенциалов

Решать задачу будем методомпотенциалов. Потенциал 1-й строки принимаем равным нулю. После этого мы можемвычислить остальные потенциалы (если известны потенциал и тариф занятой клетки,то из соотношения mathminsk.com легкоопределить неизвестный потенциал).

mathminsk.com

Найдем оценки свободных клеток:

S ( 1, 1)= 7-( 0+ 10)= -3 S ( 1, 2)= 20-( 0+ 21)= -1
S ( 2, 3)= 10-(-7+ 3)=  14 S ( 2, 4)= 20-(-7+ 15)=  12
S ( 2, 5)= 0-(-7+ 0)=  7 S ( 3, 1)= 15-( 4+ 10)=  1
S ( 3, 3)= 11-( 4+ 3)=  4 S ( 3, 5)= 0-( 4+ 0)= -4
S ( 4, 1)= 11-(-9+ 10)=  10 S ( 4, 2)= 12-(-9+ 21)=  0
S ( 4, 3)= 18-(-9+ 3)=  24 S ( 4, 5)= 0-(-9+ 0)=  9

Дляклетки ( 3, 5) строим цикл.

mathminsk.com

Найдем оценки свободных клеток:

S ( 1, 1)= 7-( 0+ 10)= -3 S ( 1, 2)= 20-( 0+ 21)= -1
S ( 1, 5)= 0-( 0-4)=  4 S ( 2, 3)= 10-(-7+ 3)=  14
S ( 2, 4)= 20-(-7+ 15)=  12 S ( 2, 5)= 0-(-7-4)=  11
S ( 3, 1)= 15-( 4+ 10)=  1 S ( 3, 3)= 11-( 4+ 3)=  4
S ( 4, 1)= 11-(-9+ 10)=  10 S ( 4, 2)= 12-(-9+ 21)=  0
S ( 4, 3)= 18-(-9+ 3)=  24 S ( 4, 5)= 0-(-9-4)=  13

Дляклетки ( 1, 1) строим цикл.

mathminsk.com

Найдем оценки свободных клеток:

S ( 1, 2)= 20-( 0+ 18)=  2 S ( 1, 5)= 0-( 0-4)=  4
S ( 2, 3)= 10-(-4+ 3)=  11 S ( 2, 4)= 20-(-4+ 15)=  9
S ( 2, 5)= 0-(-4-4)=  8 S ( 3, 1)= 15-( 4+ 7)=  4
S ( 3, 2)= 25-( 4+ 18)=  3 S ( 3, 3)= 11-( 4+ 3)=  4
S ( 4, 1)= 11-(-9+ 7)=  13 S ( 4, 2)= 12-(-9+ 18)=  3
S ( 4, 3)= 18-(-9+ 3)=  24 S ( 4, 5)= 0-(-9-4)=  13

Оценкисвободных клеток не отрицательны, следовательно, полученный план являетсяоптимальным:

mathminsk.com

Минимальныетранспортные издержки оптимального плана:

mathminsk.com

Приреализации оптимального плана у поставщика mathminsk.com останется нереализованный товар в размере 85ед.

На сайте mathminsk.com имеется возможность получить платную помощь с учебой. Для этого необходимо оформить заявку, отправив сообщение Вконтакте или на электронную почту. Услугу онлайн-помощи на экзаменах/зачетах (срок решения 1,5 часа и меньше) необходимо заказывать заранее, указав точную дату и время.

Рейтинг
( 1 оценка, среднее 5 из 5 )
Загрузка ...