Letysite.ru

IT Новости с интернет пространства
0 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

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

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

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

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

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

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

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

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

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

Суть ее заключается в следующем. Есть m поставщиков грузов А1, А2, …, Аm и n потребителей B1, B2, …, Bn этих грузов. Известны запасы грузов у поставщиков а1, а2, …, аm и потребности в этих грузах b1, b2, …, bn соответственно, а также тарифы перевозок сij.

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

Принято считать, что α1 всегда равно 0. Если не сделать это допущение, то задача не будет иметь решение. Вычисления остальных значений потенциалов производят по базовым (заполненным) клеткам:
α1 = 0
β1 = 3 + 0 = 3
β2 = 2 + 0 = 2
α2 = 2 — 1 = 1
α3 = 2 — 3 = -1
β3 = -1 + 3 = 2

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

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

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

Читать еще:  Запуск вин 7 в безопасном режиме

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

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

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

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

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

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

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

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

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

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

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

Транспортная задача — решение методом потенциалов

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

Например, у нас есть сеть розничных магазинов, которым требуется определенное количество товаров. Также имеется ряд складов поставщиков, где требуемые товары хранятся. При этом на каждом складе различный объем запасов этих товаров. Кроме этого нам известны тарифы – затраты на перевозку 1 товара от каждого склада к каждому магазину.

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

Теоретический материал по транспортной задаче

Транспортная задача (задача Монжа — Канторовича) — математическая задача линейного программирования специального вида о поиске оптимального распределения однородных объектов из аккумулятора к приемникам с минимизацией затрат на перемещение.

Для простоты понимания рассматривается как задача об оптимальном плане перевозок грузов из пунктов отправления (например, складов) в пункты потребления (например, магазины), с минимальными общими затратами на перевозки.

Математическая модель транспортной задачи имеет следующий вид:

где: Z — затраты на перевозку грузов;
X — объем груза;
C — стоимость (тариф) перевозки единицы груза;
A — запас поставщика;
B — запрос потребителя;
m — число поставщиков;
n — число потребителей.

Общий план решения транспортной задачи методом потенциалов

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

Суть его в следующем: находим некий опорный план и проверяем его на оптимальность (Z → min). Если план оптимален – решение найдено. Если нет – улучшает план столько раз, сколько потребуется, пока не будет найден оптимальный план.

Ниже приведен алгоритм решения транспортной задачи в самом общем виде:

  1. Построение транспортной таблицы.
  2. Проверка задачи на закрытость.
  3. Составление опорного плана.
  4. Проверка опорного плана на вырожденность.
  5. Вычисление потенциалов для плана перевозки.
  6. Проверка опорного плана на оптимальность.
  7. Перераспределение поставок.
  8. Если оптимальное решение найдено, переходим к п. 9, если нет – к п. 5.
  9. Вычисление общих затрат на перевозку груза.
  10. Построение графа перевозок.

Подробная инструкция по решению транспортной задачи

1. Построение транспортной таблицы

Строим таблицу, где указываем запасы материалов, имеющиеся на складах поставщиков (Ai), и потребности заводов (Bj) в этих материалах.

В нижний правый угол ячеек таблицы заносим значение тарифов на перевозку груза (Cij).

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

Обозначим суммарный запас груза у всех поставщиков символом A, а суммарную потребность в грузе у всех потребителей – символом B.

Транспортная задача называется закрытой, если A = B . Если же A ≠ B , то транспортная задача называется открытой. В случае закрытой задачи от поставщиков будут вывезены все запасы груза, и все заявки потребителей будут удовлетворены. В случае открытой задачи для ее решения придется вводить фиктивных поставщиков или потребителей.

Проверим задачу на закрытость:

A = 10 + 20 + 30 = 60

B = 15 + 20 + 25 = 60

A = B, следовательно данная транспортная задача – закрытая.

3. Составление опорного плана

Составляет предварительный (опорный) план перевозок. Он не обязательно должен быть оптимальный. Это просто своеобразный «черновик», «набросок», улучшая который мы постепенно придем к плану оптимальному.

Есть разные методы нахождения опорного плана. Наиболее распространены следующие:

Суть метода проста — ячейки транспортной таблицы последовательно заполняются максимально возможными объемами перевозок, в направлении сверху вниз и слева направо. То есть сперва заполняется самая верхняя левая ячейка («северо-западная» ячейка), потом следующая справа и т.д. Затем переходят на новую строку и вновь заполняют ее слева направо. И так пока таблица не будет заполнена полностью.

Подробное описание метода и пример можно посмотреть здесь.

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

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

4. Проверка опорного плана на вырожденность

Клетки таблицы, в которые записаны отличные от нуля перевозки, называются базисными, а остальные (пустые) — свободными.

План называется вырожденным, если количество базисных клеток в нем меньше, чем m + n -1. Если во время решения задачи получился вырожденный план, то его необходимо пополнить, проставив в недостающем числе клеток нулевую перевозку и превратив, тем самым, эти клетки в базисные (общий баланс и суммарная стоимость перевозок плана при этом не изменятся). Однако проводить пополнение плана, выбирая клетки произвольно, нельзя. План должен быть ациклическим!

План называется ациклическим, если его базисные клетки не содержат циклов. Циклом в транспортной таблице называется несколько клеток, соединенных замкнутой ломаной линией так, чтобы две соседние вершины ломаной были расположены либо в одной строке, либо в одном столбце. Ниже приведен пример цикла:

Ломаная линия может иметь точки самопересечения, но не в клетках цикла.

Кол-во базисных клеток = 5

m + n – 1 = 3 + 3 – 1 = 5

Следовательно, первоначальный план перевозок – невырожденный.

5. Вычисление потенциалов для плана перевозки

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

Читать еще:  Визуальное программирование примеры

Этот метод улучшения плана перевозок называется методом потенциалов. Есть другие методы итерационного улучшения плана перевозок, но здесь мы их рассматривать не будем.

Итак, сопоставим каждому поставщику Ai и каждому потребителю Bj величины Ui и Vj соответственно так, чтобы для всех базисных клеток плана было выполнено соотношение:

Ui + Vj = Cij

Добавим к транспортной таблице дополнительную строку и столбец для Ui и Vj.

Предположим, что U1 = 0.

Тогда мы сможем найти V3 = C13 – U1 = 1 – 0 = 1.

Зная V3, мы теперь можем найти U3:

По аналогии вычисляем все оставшиеся потенциалы:

6. Проверка плана на оптимальность методом потенциалов

Для каждой свободной клетки плана вычислим разности

ΔCij = Cij – (Ui + Vj )

и запишем полученные значения в левых нижних углах соответствующих ячеек.

План является оптимальным, если все разности ΔCij ≥ 0.

7. Перераспределение поставок

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

Отметим ячейку с отрицательной разностью ΔCij знаком «+», следующую знаком «-», и так далее, поочередно.

Затем находим минимальной значение груза в ячейках цикла имеющих знак «-» (здесь это 5) и вписываем его в свободную ячейку со знаком «+». Затем последовательно обходим все ячейки цикла, поочередно вычитая и прибавляя к ним минимальное значение (в соответствии со знаками, которыми эти ячейки помечены: где минус — вычитаем, где плюс — прибавляем).

Получим новый опорный план перевозок:

Так как базисных клеток стало больше, чем m + n – 1, то базисную клетку с нулевым значением делаем свободной:

Снова вычисляем значения потенциалов и разности ΔCij:

На этот раз все разности ΔCij ячеек положительные, следовательно, найдено оптимальное решение.

8. Если оптимальное решение найдено, переходим к п. 9, если нет – к п. 5.

У нас оптимальное решение найдено, поэтому переходим к пункту 9.

9. Вычисление общих затрат на перевозку груза

Вычислим общие затраты на перевозку груза (Z), соответствующие найденному нами оптимальному плану, по формуле:

Zmin = 10 ∙ 1 + 15 ∙ 3 + 5 ∙ 2 + 15 ∙ 1 + 15 ∙ 2 = 110 ден. ед.

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

10. Построение графа перевозок

Найдя оптимальный план перевозок, построим граф. Вершинами графа будут «склады» и «магазины». В вершинах укажем соответствующие объемы запасов и потребностей. Дугам, соединяющим вершины графа, будут соответствовать ненулевые перевозки. Каждую такую дугу подпишем, указав объем перевозимого груза.

В результате получится граф, аналогичный изображенному ниже:

Все, транспортная задача решена. Поздравляю!

Практическое применение транспортной задачи

Транспортная задача применяется во многих случаях. Это оптимизация поставок сырья и материалов на производственные предприятия. Это оптимизация доставок товаров со складов в розничные магазины. Это оптимизация пассажирских перевозок, и много-многое другое.

© Копирование материала допустимо только при указании прямой гиперссылки на источник: Галяутдинов Р.Р.

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

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

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

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

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

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

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

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

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

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

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

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

Допустим, у нас есть 6 продавцов и 7 покупателей. Предложение продавцов составляет 36, 51, 32, 44, 35 и 38 единиц. Спрос покупателей следующий: 33, 48, 30, 36, 33, 24 и 32 единицы. Суммарные количества по спросу и предложению равны, следовательно, это транспортная задача закрытого типа.

Также, мы имеем данные по издержкам перевозок из одного пункта в другой (ячейки с желтым фоном).

Алгоритм решения

Итак, приступи к решению нашей задачи:

  1. Для начала строим таблицу, количество строк и столбцов в которой соответствует числу продавцов и покупателей, соответственно.
  2. Перейдя в любую свободную ячейку щелкаем по кнопке “Вставить функцию” (fx).
  3. В открывшемся окне выбираем категорию “Математические”, в списке операторов отмечаем “СУММПРОИЗВ”, после чего щелкаем OK.
  4. На экране отобразится окно, в котором нужно заполнить аргументы:
    • в поле для ввода значения напротив первого аргумента “Массив1” указываем координаты диапазона ячеек матрицы затрат (с желтым фоном). Сделать это можно, используя клавиши на клавиатуре, или просто выделив нужную область в самой таблице с помощью зажатой левой кнопки мыши.
    • в качестве значения второго аргумента “Массив2” указываем диапазон ячеек новой таблицы (либо вручную, либо выделив нужные элементы на листе).
    • по готовности жмем OK.
  5. Щелкаем по ячейке, расположенной слева от самого верхнего левого элемента новой таблицы, после чего снова жмем кнопку “Вставить функцию”.
  6. На этот раз нам нужна функция “СУММ”, которая также, находится в категории “Математические”.
  7. Теперь нужно заполнить аргументы. В качестве значения аргумента “Число1” указываем верхнюю строку созданной для расчетов таблицы (целиком) – вручную или методом выделения на листе. Жмем кнопку OK, когда все готово.
  8. В ячейке с функцией появится результат, равный нулю. Наводим указатель мыши на ее правый нижний угол, и когда появится Маркер заполнения в виде черного плюсика, зажав левую кнопку мыши тянем его до конца таблицы.
  9. Это позволит скопировать формулу и получить аналогичные результаты для остальных строк.
  10. Выбираем ячейку, которая находится сверху от самого верхнего левого элемента созданной таблицы. Аналогично описанным выше действиям вставляем в нее функцию “СУММ”.
  11. В значении аргумента “Число1” теперь указываем (вручную или с помощью выделения на листе) все ячейки первого столбца, после чего кликаем OK.
  12. С помощью Маркера заполнения выполняем копирование формулы на оставшиеся ячейки строки.
  13. Переключаемся во вкладку “Данные”, где жмем по кнопке функции “Поиск решения” (группа инструментов “Анализ”).
  14. Перед нами появится окно с параметрами функции:
    • в качестве значения параметра “Оптимизировать целевую функцию” указываем координаты ячейки, в которую ранее была вставлена функция “СУММПРОИЗВ”.
    • для параметра “До” выбираем вариант – “Минимум”.
    • в области для ввода значений напротив параметра “Изменяя ячейки переменных” указываем диапазон ячеек новой таблицы (без суммирующей строки и столбца).
    • нажимаем кнопку “Добавить” в блоке “В соответствии с ограничениями”.
  15. Откроется небольшое окошко, в котором мы можем добавить ограничение – сумма значений первых столбцов исходной и созданной таблицы должны быть равны.
    • становимся в поле “Ссылка на ячейки”, после чего указываем нужный диапазон данных в таблице для расчетов.
    • затем выбираем знак “равно”.
    • в качестве значения для параметра “Ограничение” указываем координаты аналогичного столбца в исходной таблице.
    • щелкаем OK по готовности.
  16. Таким же способом добавляем условие по равенству сумм верхних строк таблиц.
  17. Также добавляем следующие условия касательно суммы ячеек в таблице для расчетов (диапазон совпадает с тем, который мы указали для параметра “Изменяя ячейки переменных”):
    • больше или равно нулю;
    • целое число.
  18. В итоге получаем следующий список условий в поле “В соответствии с ограничениями”. Проверяем, чтобы обязательно была поставлена галочка напротив опции “Сделать переменные без ограничений неотрицательными”, а также, чтобы в качестве метода решения стояло значение “Поиск решения нелинейных задач методов ОПГ”. Когда все готово, нажимаем “Найти решение”.
  19. В результате будет выполнен расчет и отобразится окно с результатами поиска решения. Оцениваем их, и в случае, когда они нас устраивают, нажимаем OK.
  20. Все готово, мы получили таблицу с заполненными данными и транспортную задачу можно считать успешно решенной.
Читать еще:  Функции службы безопасности банка

Заключение

Таким образом, с помощью программы Эксель достаточно просто решить транспортную задачу. Самое главное – правильно заполнить начальные данные и четко следовать плану действий, и тогда проблем быть не должно, т.к. программа все расчеты выполнит сама.

Транспортная задача в Microsoft Excel

Транспортная задача представляет собой задачу поиска наиболее оптимального варианта перевозок однотипного товара от поставщика к потребителю. Её основой является модель, широко применяемая в различных сферах математики и экономики. В Microsoft Excel имеются инструменты, которые значительно облегчают решение транспортной задачи. Выясним, как их использовать на практике.

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

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

Если общий объем товара на складах поставщика равен величине спроса, транспортная задача именуется закрытой. Если эти показатели не равны, то такую транспортную задачу называют открытой. Для её решения условия следует привести к закрытому типу. Для этого добавляют фиктивного продавца или фиктивного покупателя с запасами или потребностями равными разнице между спросом и предложением в реальной ситуации. При этом в таблице издержек добавляется дополнительный столбец или строка с нулевыми значениями.

Инструменты для решения транспортной задачи в Эксель

Для решения транспортной задачи в Excel используется функция «Поиск решения». Проблема в том, что по умолчанию она отключена. Для того, чтобы включить данный инструмент, нужно выполнить определенные действия.

    Делаем перемещение во вкладку «Файл».

Кликаем по подразделу «Параметры».

В блоке «Управление», который находится внизу открывшегося окна, в выпадающем списке останавливаем выбор на пункте «Надстройки Excel». Делаем клик по кнопке «Перейти…».

Запускается окно активации надстроек. Устанавливаем флажок возле пункта «Поиск решения». Кликаем по кнопке «OK».

  • Вследствие этих действий во вкладке «Данные» в блоке настроек «Анализ» на ленте появится кнопка «Поиск решения». Она нам и понадобится при поиске решения транспортной задачи.
  • Пример решения транспортной задачи в Excel

    Теперь давайте разберем конкретный пример решения транспортной задачи.

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

    Имеем 5 поставщиков и 6 покупателей. Объёмы производства этих поставщиков составляют 48, 65, 51, 61, 53 единиц. Потребность покупателей: 43, 47, 42, 46, 41, 59 единиц. Таким образом, общий объем предложения равен величине спроса, то есть, мы имеем дело с закрытой транспортной задачей.

    Кроме того, по условию дана матрица затрат перевозок из одного пункта в другой, которая отображена на иллюстрации ниже зеленым цветом.

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

    Перед нами стоит задача при условиях, о которых было сказано выше, свести транспортные расходы к минимуму.

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

    Выделяем любую пустую ячейку на листе. Кликаем по значку «Вставить функцию», размещенному слева от строки формул.

    Открывается «Мастер функций». В списке, который предлагает он, нам следует отыскать функцию СУММПРОИЗВ. Выделяем её и жмем на кнопку «OK».

    Открывается окно ввода аргументов функции СУММПРОИЗВ. В качестве первого аргумента внесем диапазон ячеек матрицы затрат. Для этого достаточно выделить курсором данные ячейки. Вторым аргументом выступит диапазон ячеек таблицы, которая была приготовлена для расчетов. Затем, жмем на кнопку «OK».

    Кликаем по ячейке, которая расположена слева от верхней левой ячейки таблицы для расчетов. Как и в прошлый раз вызываем Мастер функций, открываем в нём аргументы функции СУММ. Кликнув по полю первого аргумента, выделяем весь верхний ряд ячеек таблицы для расчетов. После того, как их координаты занесены в соответствующее поле, кликаем по кнопке «OK».

    Становимся в нижний правый угол ячейки с функцией СУММ. Появляется маркер заполнения. Жмем на левую кнопку мыши и тянем маркер заполнения вниз до конца таблицы для расчета. Таким образом мы скопировали формулу.

    Кликаем по ячейке размещенной сверху от верхней левой ячейки таблицы для расчетов. Как и в предыдущий раз вызываем функцию СУММ, но на этот раз в качестве аргумента используем первый столбец таблицы для расчетов. Жмем на кнопку «OK».

    Копируем маркером заполнения формулу на всю строку.

    Переходим во вкладку «Данные». Там в блоке инструментов «Анализ» кликаем по кнопке «Поиск решения».

    Открываются параметры поиска решения. В поле «Оптимизировать целевую функцию» указываем ячейку, содержащую функцию СУММПРОИЗВ. В блоке «До» устанавливаем значение «Минимум». В поле «Изменяя ячейки переменных» указываем весь диапазон таблицы для расчета. В блоке настроек «В соответствии с ограничениями» жмем на кнопку «Добавить», чтобы добавить несколько важных ограничений.

    Запускается окно добавления ограничения. Прежде всего, нам нужно добавить условие того, что сумма данных в строках таблицы для расчетов должна быть равна сумме данных в строках таблицы с условием. В поле «Ссылка на ячейки» указываем диапазон суммы в строках таблицы расчетов. Затем выставляем знак равно (=). В поле «Ограничение» указываем диапазон сумм в строках таблицы с условием. После этого, жмем на кнопку «OK».

    Аналогичным образом добавляем условие, что столбцы двух таблиц должны быть равны между собой. Добавляем ограничение, что сумма диапазона всех ячеек в таблице для расчета должна быть большей или равной 0, а также условие, что она должна быть целым числом. Общий вид ограничений должен быть таким, как представлен на изображении ниже. Обязательно проследите, чтобы около пункта «Сделать переменные без ограничений неотрицательными» стояла галочка, а методом решения был выбран «Поиск решения нелинейных задач методом ОПГ». После того, как все настройки указаны, жмем на кнопку «Найти решение».

  • После этого происходит расчет. Данные выводятся в ячейки таблицы для расчета. Открывается окно результатов поиска решения. Если результаты вас удовлетворяют, жмите на кнопку «OK».
  • Как видим, решение транспортной задачи в Excel сводится к правильному формированию вводных данных. Сами расчеты выполняет вместо пользователя программа.

    Отблагодарите автора, поделитесь статьей в социальных сетях.

    Ссылка на основную публикацию
    Adblock
    detector