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

Обновлено: 22.01.2025

Полученное решение сохраняется в файле Word (Пример решения транспортной задачи). Также автоматически генерируется шаблон решения в Excel .

Вместе с этим калькулятором также используют следующие:
Графический метод решения ЗЛП

Решение матричной игры
С помощью сервиса в онлайн режиме можно определить цену матричной игры (нижнюю и верхнюю границы), проверить наличие седловой точки, найти решение смешанной стратегии методами: минимакс, симплекс-метод, графический (геометрический) метод, методом Брауна.

• вычеркивания (метод двойного предпочтения);
• северо-западного угла;
• минимального элемента;
• аппроксимации Фогеля.

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

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

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

Решим транспортную задачу методом потенциалов. Нам известны торговые запасы, потребительские запросы и стоимость доставки за единицу продукции. Сделаем три исходные таблицы.

Построим опорный план транспортной задачи с помощью инструмента «Поиск решений». Рядом составим такие же по объему таблицы с пустыми ячейками. Таблица А – аналог стоимостной, Б – «запасов», В – «спроса».

Элементы таблицы Б – сумма соответствующих строк в таблице А. Элементы таблицы В – сумма соответствующих столбцов в таблице А.

Отдельно составим результирующую таблицу Г. В ней отразятся оптимальные транспортные расходы. Каждый элемент таблицы Г – произведение элемента А и соответствующего элемента стоимостной таблицы.

В отдельном месте листа введем формулу функции: =СУММПРОИЗВ(A1:C3;G1:I3)

Первый массив – стоимостная таблица, второй – диапазон А.

Ставим курсор в ячейку со значением функции. Вызываем инструмент «Поиск решения». Заполняем диалоговое окно:

1. Целевая ячейка – ссылка на ячейку со значением функции.
2. Она должна быть равна «максимальному значению», как наиболее выгодному для перевозчика.
3. Команда изменяет значения ячеек в таблице А. Значения – целые числа.
4. Диапазон таблицы Б = «Запасам».
5. Диапазон В = «Потребительскому спросу».

В открытом диалоговом окне нажимаем кнопку «Параметры» и устанавливаем следующие настройки:

Жмем ОК – «Выполнить». Получаем опорный план транспортной задачи:

Он залит бледно-зеленым цветом. Ячейки со значениями выше нуля называются «базисными», «занятыми». Ячейки со значением 0 – «свободными».

Далее действуем по плану:

Посчитаем число занятых клеток с помощью функции СЧЕТЕСЛИ.

Так как результат равен 5, опорный план является не вырожденным. Проверим оптимальность опорного плана – найдем потенциалы по занятым клеткам.

Нужно составить систему уравнений. Предполагается, что αj = 0, а αi + βj = сij (стоимость доставки единицы груза). Вызываем команду «Поиск решения». Вносим условия системы уравнений в качестве ограничений.

Заполненное диалоговое окно:

Результат работы инструмента «Поиск решения»:

Посчитаем оценки свободных клеток. Формула: сij – (αi + βj). Берем свободную клетку из таблицы А. Смотрим ее значение в стоимостной таблице. Это будет сij. Далее смотрим, какие потенциалы соответствуют данной клетке. Вставляем их значения в формулу.

В программе Excel найдем оценки с помощью математических операторов и ссылок на соответствующие ячейки.

План считается оптимальным, если оценки больше или равны 0. В нашем случае получились отрицательные значения – план не является оптимальным. Поэтому двигаемся дальше.

Находим, какой клетке в таблице А соответствует минимальная оценка. Строим для этой клетки цикл – замкнутую ломаную линию. Условия: обязательно чередование вертикального и горизонтального направления, только по базисным клеткам.

В исходной клетке (с минимальной оценкой) ставим знак «+». Далее чередуем: «-», «+» и т.д.

В таблице стоимости находим минимальное значение со знаком «-».

В нашем примере – это «5», ячейка В1. Эту клетку нужно убрать из базиса. А ячейку с минимальной оценкой сделать базисной.

С учетом изменившихся данных вновь строим опорный план транспортной задачи. Применяем инструмент «Поиск решения». Пересчитанный план перевозок выглядит так:

Обратите внимание: ячейка I1 (где была минимальная оценка) стала базисной, занятой.

Проводим те же расчеты для нового плана (с пункта №1): находим потенциалы, оценки свободных клеток для проверки оптимальности. И так до тех пор, пока оценки свободных клеток не будут больше или равны 0.

На этой странице разберем подробные решения транспортной задачи (алгоритм и примеры разных типов) с использованием пакета электронных таблиц MS Excel (надстройка Поиск решения).

Как решить транспортную задачу в Excel

Ручное решение транспортной задачи занимает очень много времени и сил (скажем, даже для учебной задачи типа 3*5 решение может составлять от 4 до 10 страниц расчетов!). Тогда как решение в Эксель для задачи размерности как 3*3, так и 5*7 потребует буквально 10-15 минут и немного опыта (правда, если уже составлена математическая модель).

Использовать можно любую версию программы - 2003, 2007, 2010 и так далее, главное, включить использование надстройки Поиск решения (интерфейс может немного отличаться в разных версиях).

Алгоритм решения ТЗ в Эксель

• Составить математическую модель транспортной задачи - то есть получить таблицу со стоимостью перевозок, запасами груза у поставщиков и потребностями потребителей (и, возможно, дополнительными ограничениями).
  
  
• Если задача открытая (несбалансированная), то добавить потребителя или поставщика с нулевыми тарифами перевозки.
  
• Внести на лист таблицы Excel данную модель в виде матрицы тарифов (затрат).
  
  
• Создать рядом на листе еще одну таблицу, где будут выводиться искомые перевозки (такой же размерности, что и таблица тарифов). Просуммировать перевозки по строкам и столбцам (чтобы сравнивать с аналогичными ячейками - предельными ограничениями задачи - запасами поставщиков и потребностями потребителей).
  
  
• Ввести в ячейку формулу, подсчитывающую суммарную стоимость перевозок (это число мы должны минимизировать по смыслу транспортной задачи)
  
  В режиме формул таблица будет выглядеть так:
  
  
• Запустить надстройку Поиск решения и указать а) ячейку, которую мы минимизируем, б) все ограничения на запасы поставщиков и потребности потребителей, в) дополнительные ограничения (иногда бывают запреты перевозок или требования по минимальному объему груза между определенными пунктами, как в данном случае).
  
  
• Получить решение транспортной задачи: в целевой ячейке вы увидите минимальную стоимость перевозок (в примере 435), а в таблице перевозок - искомые значения объема перевозимого груза (см. желтые ячейки).
  
  
• Проанализировать решение, если требуется и записать более подробно, например

Минимальные затраты на перевозку составят 435. План перевозок:
Из 1 карьера 10 тонн везем на 1-й участок, 15 тонн на 3-й.
Из 2 карьера 20 тонн везем на 1-й участок.
Из 3 карьера 20 тонн везем на 3-й.
Из 4 карьера 10 тонн везем на 1-й участок, 20 тонн на 2-й, 5 тонн на 3-й.

Транспортные задачи: примеры в Excel

Задача 1. Решить транспортную задачу вручную (методом потенциалов) и в программе Эксель.

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

Задача 3. Имеется 3 нефтеперерабатывающих завода, 4 спиртовых завода, 3 завода по производству синтетического каучука.
Схема кооперационных связей (см. файл).
Далее приведены производственные показатели предприятий.
Также заданы расстояния между предприятиями.
Необходимо найти решение транспортной задачи с ориентацией на спрос СК и минимизацией транспортных суммарных затрат.

Задача 4. Используя метод потенциалов, решить транспортную задачу. Выполнить проверку, используя табличный редактор Microsoft Excel Компания владеет тремя заводами А1, А2, А3. Соответствующие объемы производства равны 600, 300 и 330 единиц продукции. Компания обязалась поставить в города В1, В2, В3 и В4 соответственно 350, 350, 230 и 300 единиц. При заданных в таблице стоимостях перевозок единицы продукции составьте план ее распределения, чтобы общая стоимость перевозок была наименьшей.

Задача 5. Свести задачу к виду ТЗ и решить с помощью надстройки «Поиск решения»
Четыре ремонтные мастерские могут за год отремонтировать соответственно 400, 500, 450 и 550 машин при себестоимости ремонта одной машины в 500, 700, 650 и 600 рублей. Планируется годовая потребность в ремонте пяти автобаз: 550, 350, 300, 375 и 400 машин.
Ремонт машин с 1 автобазы должен осуществляться в 100% случаев силами ремонтных мастерских.
На 4 АБ возможно самостоятельное проведение ремонтных работ (бесплатное) в объеме, не превышающем 8% от планируемой годовой потребности этой мастерской. Платное (на стороне) - совсем не возможно.
Вторая, третья и пятая АБ могут «ремонтироваться» на стороне, стоимость ремонта +трансп.расходы каждой машины в таком случае составит 695 руб.
Дана матрица, характеризующая транспортные расходы на доставку машины с j-й автобазы в i-ю ремонтную мастерскую. Определить минимальную годовую потребность в кредитах на выполнение указанного объема работ по всем автобазам

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

Суть ее заключается в следующем. Есть m поставщиков грузов А₁, А₂, …, А_m и n потребителей B₁, B₂, …, B_n этих грузов. Известны запасы грузов у поставщиков а₁, а₂, …, а_m и потребности в этих грузах b₁, b₂, …, b_n соответственно, а также тарифы перевозок с_ij.

1. Все запасы изъять.
2. Все потребности удовлетворить.
3. Чтобы стоимость доставки грузов была минимальной.

Математическая модель задачи следующая:

Как видим, математическая модель записана в каноническом виде, так как в ней присутствует условие равновесия (2), но это идеальный случай. Чаще всего можно столкнуться со следующим:

1. запасы превышают потребности и тогда приходится вводить фиктивного потребителя с нулевым тарифом;
2. потребности превышают запасы – вводят фиктивного поставщика с нулевым тарифом.

Почему тарифы равны нулю? Вывод очевиден – надо следовать критерию задачи.
Более подробную информацию по теории транспортной задачи можно посмотреть в учебниках по исследованию операций либо математическому программированию.

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

Вывод: метод потенциалов универсален и всегда дает оптимальное решение.

Рассмотрим задачу: имеются три поставщика грузов и три потребителя этих грузов. Запасы грузов составляют 150, 100 и 300 ед., потребности в них равны 100, 250 и 200 ед. соответственно. Тарифы перевозок также известны:

Найти оптимальный план доставки этих грузов.

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

Вначале найдем опорный план с помощью диагонального способа без учета тарифов.

Для решения задачи составляется таблица перевозок:

Правила заполнения таблицы несложные. Заполнение начинают с левой верхней клетки, в которую записывают грузопоставку исходя из наличия груза и потребности в нем. Наличие груза у поставщика А₁ составляет 150 ед. а потребность потребителя В₁ в грузе равна 100 ед. Запишем этот груз полностью, а остаток 50 ед. запишем следующему потребителю, третью ячейку вычеркнем, так как весь груз у первого поставщика изъят:

Подобные действия произведем со вторым и третьим поставщиком. Получим таблицу перевозок:

Как видим, при распределении грузов тарифы не учитывались. Расходы на доставку грузов составляют:
f = 3×100 + 2×50 + 1×100 + 3×100 + 3×200 = 1400 у.е.

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

Грузопоставки начнем вписывать в клетку, которая имеет наименьший тариф. Если таких клеток несколько, то начинать записывать можно в любую из них. Минимальный тариф в таблице равен единице, а так как таких клеток три, то выберем первой например ячейку А₁В₃. Размер грузопоставки определяется исходя из наличия груза у поставщика и потребности потребителя. Наличие груза у первого поставщика равно 150 ед., потребность равна 200 ед. Мы забираем весь груз у А₁ и записываем:

Заполняем следующую клетку с тарифом, равным единице:

Оставшиеся клетки с одинаковым тарифом последовательно заполняем:

Вычислим транспортные расходы:
f = 1×100 + 3×50 + 1×150 + 3×250 = 1150 у.е.
Как видим, опорный план, полученный методом минимального элемента, дает лучший результат, чем диагональный способ.

После того, как получено допустимое решение, его надо проверить на оптимальность с помощью метода потенциалов. Перед проверкой убеждаемся, что число заполненных клеток равно соотношению m+n-1. В нашей таблице их 3+3-1=5.

Признак оптимальности: решение оптимально, если во всех свободных клетках выполняется неравенство: α_i + c_ij ≥ β_j, где α_i и β_j – потенциалы, c_ij – тарифы перевозок. Вычислим α_i и β_j с помощью выше указанного неравенства:

Проверку на оптимальность делают по свободным клеткам с помощью этого же неравенства:
А₁В₃: 0 + 1 ≥ 2 – нет
А₂В₁: 1 + 1 ≥ 3 – нет
А₂В₃: 1 + 4 ≥ 2 – да
А₃В₁: -1 + 2 ≥ 3 – нет

В результате проверки мы выявили три недостаточные клетки. Находим цикл пересчета:

цикл пересчета – это ход ладьи по базовым клеткам с чередованием знаков «+» и «-», начиная с недостаточной клетки и замыкаясь в ней же.

В клетках с минусовыми отметками выбирает минимальное число. В нашем случае это число равно 100. Пересчет делают следующим образом: где стоит знак «-» это число отнимают, а где «+» то прибавляют. Значения, не входящие в цикл пересчета переписывают без изменений. Получает таблицу, в которой соотношение m+n-1 не выполняется, и поэтому выбираем клетку с минимальным тарифом и, проставляя в ней ноль, считаем ее условно базовой:

Вначале транспортные расходы составляли 1400 у.е. Считаем сейчас:
f₂ = 2×100 + 2×150 + 1×100 + 3×200 = 1200 у.е.
Уменьшение этого показателя говорит о том, что мы на верном пути.

Полученное решение снова проверяем на оптимальность:

Проверка выявляет одну недостаточную клетку, для которой находим цикл пересчета:
А₁В₁: 0 + 3 ≥ 0 – да
А₁В₃: 1 + 0 ≥ 1 – да
А₂В₁: 1 + 1 ≥ 0 – да
А₃В₂: -2 + 3 ≥ 2 – нет

В отрицательных клетках из двух значений выбираем число 150, которое отнимаем, где знак «-» и прибавляем где знак «+»:

Транспортные расходы:
f₃ = 2×100 + 3×150 + 1×100 + 1×150 + 3×50 = 1050 у.е.

Проверяем снова на оптимальность и убеждаемся, что найден оптимальный план:
А₁В₁: 0 + 3 ≥ 0 – да
А₁В₂: 0 + 2 ≥ 1 – да
А₂В₁: 0 + 1 ≥ 0 – да
А₂В₃: 0 + 4 ≥ 1 – да

Ответ: f = 1050 у.е.

Успехов! И помните, что Решатель всегда готов Вам помочь с решением транспортной задачи и не только! Заявку можно оставить здесь или заполнив форму наверху страницы.

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

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

Читайте также:

  
• Запрос на обновление данных в эксель
  
• Компьютеру специальной программе можно отследить всю траекторию движения скорость которой
  
• Hp bios update initializing долго загружается
  
• Поиск по двум столбцам excel
  
• Формат готового файла многостраничный tif как сделать