Как сделать транспортную задачу в excel?

Маршрутизация перевозок (решение транспортной задачи в EXCEL)

Страницы работы

Содержание работы

Для решения транспортной задачи в EXCEL нам потребуется инструмент Поиск решения из меню Сервис. С помощью его можно искать решение систем уравнений, которые к тому же могут содержать ограничения. Если этого инструмента в меню нет, то его надо установить. Для этого в CD-привод ставим установочный диск Microsoft Office, затем в меню Сервис нажимаем на инструмент Надстройки… , в поле Доступные надстройки ставим галочку напротив инструмента Поиск решения (рисунок 1), далее нажимаем ОК . Далее выскочит окно нажимаем кнопку Да , и компьютер начнет устанавливать этот инструмент.

Рисунок 1 – Установка инструмента Поиск решения

Рисунок 2 – Расстояния до поставщиков, оптимальный и заданный план перевозок

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

2.Составление алгоритма решения первого маршрута

2.1. Составление совмещенной матрицы (матрица №3)

Накладываем данные одной матрицы на другую, как показано на рисунке 3 . Причем слева в ячейке ставим ссылку на матрицу №2 – план перевозок, а справа в ячейке на матрицу №1 – оптимальный план возврата порожних автомобилей. Например клетка матрицы №3 А1Б1:

– Слева в ячейке С4 листа 2 ставим знак «=», переходим на Лист 1, нажимаем мышкой на ячейку С38, нажимаем Enter, получаем запись в ячейке С4 листа 2:

Это означает что значение в ячейке С4 листа 2 равно значению ячейки С38 листа 1, и если мы поменяем значение в этой ячейке, то автоматически поменяется значение в С4 листа 2.

– Справа в ячейке D4 листа 2 ставим знак «=», переходим на Лист 1, нажимаем мышкой на ячейку С18, нажимаем Enter, получаем запись в ячейке D4 листа 2:

Рисунок 3 – Совмещённая матрица

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

2.2. Расчет маятниковых маршрутов

Для расчета маятниковых маршрутов составляем матрицу №4 (рисунок 4). Что бы выделить маятниковые маршруты нужно вывести минимальное число из каждой клетки совмещенной матрицы. Для этого нам потребуется функция МИН(число1;число2;…), она возвращает минимальное значений из списка аргументов. Для этого в ячейке С17 ставим знак «=», верхнем правом углу ищем значок fx , нажимаем его, откроется окно Мастер функций, в поле Категория выбираем Полный арифметический перечень, ищем функцию МИН, нажимаем ОК, откроется окно Аргументы функции, в строке Число1 нажимаем на значок , мышкой выделяем ячейку С4, нажимаем Enter, в строке Число2 нажимаем на значок , мышкой выделяем ячейки D4, нажимаем Enter, затем ОК, таким образом, мы записываем формулу в ячейке С17:

в ячейке D17 записываем формулу:

в ячейке E17 записываем формулу:

в ячейке F17 записываем формулу:

Так заполняем все ячейки первой стоки. Остальные ячейки заполняем, перенося формулы, как это было показано выше, получаем матрицу №4.

Рисунок 4 – Маятниковые маршруты

Таким образом, матрица №4 отображает количество груза, перевозимое в маятниковых маршрутах. Далее исключаем маятниковые маршруты из совмещенной матрицы. Для этого вычитаем из матрицы №3 матрицу №4 по каждой ячейке (рисунок 5). В ячейке С30 ставим знак «=», мышкой нажимаем на ячейку С4, ставим знак «-», мышкой нажимаем на ячейку С17, получаем запись

Переносим эту формулу сначала на всю строку, затем на всю матрицу. Таким образом, получаем матрицу №5.

Рисунок 5 – Совмещенная матрица без маятниковых маршрутов

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

Составляем вспомогательную матрицу (рисунок 6). В ячейке С44 записываем формулу

в ячейке D44 записываем формулу

Читать еще:  Как в excel сделать копирование ячейки?

Так заполняем первую строку, на остальные строки переносим формулы. Таким образом, получаем матрицу №6.

Находить маршрут будем в двоичной системе, то есть «1» означает вершину контура маршрута в клетке матрицы, «0» означает, что вершины контура в клетке нет. Для того чтобы все цифры вспомогательной матрицы перевести в двоичную систему нам потребуется функция ЗНАК(число). Она возвращает знак числа: 1 – если число положительное, 0 – если оно равно нулю и -1 – если число отрицательное.

Для этого в ячейке N44 записываем формулу:

Переносим формулу сначала на всю строку, а затем на всё матрицу. Таким образом, получаем матрицу №7

Для заданного плана из совмещенной матрицы без маятниковых маршрутов (рисунок 5) берём цифры слева клетки, то есть в ячейке С58 записываем формулу:

в ячейке D58 записываем формулу:

И так, заполняем все ячейки первой строки, затем формулы из первой строки переносим на всю матрицу, получаем матрицу №8.

А для оптимального плана из совмещенной матрицы берём цифры справа клетки, то есть в ячейке N58 записываем формулу:

в ячейке O58 записываем формулу:

Так, заполняем все ячейки первой строки, затем формулы из первой строки переносим на всю матрицу, получаем матрицу №9.

Рисунок 6 – Вспомогательная матрица, заданный план и оптимальный план возврата в двоичной системе

Матрицы №8 и №9 будут являться ограничениями для инструмента Поиск решения.

Составим поле изменяемых ячеек (рисунок 7).

В этом поле программа вычертит контур маршрута, то есть будет ставить в каждой клетке либо «1» либо «0». Чтобы обеспечить чередование цифр из оптимального плана возврата и заданного плана в контуре, поле изменяемых ячеек разбиваем на две половины. Верхняя (ячейки C71;L80) будет отображать вершины контура маршрута из заданного плана, а нижняя (ячейки C81;L90) из оптимального плана возврата.

Раскрываем меню Сервис, открываем инструмент Поиск решения:

Как сделать транспортную задачу в excel?

Задача. Пусть производство продукции осуществляется на 4-х предприятиях А1, А2, А3, А4 а затем развозится в 5 пунктов потребления этой продукции B1, B2, B3, B4, B5. На предприятиях Ai (i = 1, 2, 3, 4) продукция находится соответственно в количествах ai (условных единиц). В пункты Bj (j = 1, 2, 3, 4,5) требуется доставить bj единиц продукции. Стоимость перевозки единицы груза (с учетом расстояний) из Ai в Bj определена матрицей .
Предприятия могут выпускать в день 235, 175, 185 и 175 единиц продукции. Пункты потребления готовы принимать ежедневно 125, 160, 60, 250 и 175 единиц продукции. Стоимость перевозки единицы продукции (в у. е.) с предприятий в пункты потребления приведена в таблице.


Требуется минимизировать суммарные транспортные расходы по перевозке продукции.

Решение.
Необходимо выполнить следующее:
1. Установить, является ли модель транспортной задачи, заданная таблицей, сбалансированной.
2. Разработать математическую модель задачи.
3. Найти минимальную стоимость перевозок, используя надстройку «Поиск решения» в среде MS Excel.

Решение.

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

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

2. Приступим к построению математической модели поставленной задачи. Неизвестными будем считать объемы перевозок.
Пусть хij – объем перевозок с i-го пункта поставки в j-й пункт потребления. Суммарные транспортные расходы – это функция , где сij – стоимость перевозки единицы продукции с i-го предприятия в j-й пункт потребления .

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

Итак, имеем следующую задачу ЛП:
найти минимум функции:
при ограничениях:


, ,

3. Приступаем к решению задачи на компьютере.
3.1. Откроем новый рабочий лист Excel.
3.2. В ячейки B3:F6 стоимость перевозок единицы груза.
3.3. В ячейках B16:F16 укажем формулы для расчета суммарной потребности продукции для j-го пункта, в ячейках G12:G15 – формулы суммарного объема производства i-го предприятия.

3.4. В ячейки B18:F18 заносим значения потребности продукции соответствующего пункта потребления, в ячейки H12:H15 заносим значения объема производства соответствующего предприятия.
3.5. В ячейку B20 занесем формулу целевой функции.
3.6. Выполним команду Сервис → Поиск решения. Откроется диалоговое окно Поиск решения. Если такой команды во вкладке Сервис нет, то следует подключить эту надстройку перейдя по Сервис → Надстройки, и поставив галочку напротив нужной, т.е. Поиск решения.
3.7. В поле Установить целевую ячейку указываем ячейку, содержащую оптимизируемое значение. Установим переключатель Равный в положение минимальному значению.
3.8. В поле Изменяя ячейки мышью зададим диапазон подбираемых параметров $B$12:$F$15.
3.9. В поле Ограничения введем необходимые ограничения и нажмем на кнопку Добавить, затем Выполнить.

Читать еще:  Как сделать наложение графиков в excel?

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

Оптимальность решения можно проверить, экспериментируя со значениями ячеек $B$12:$F$15.

Как сделать транспортную задачу в excel?

Пример решения транспортной задачи с помощью MS Excel

Транспортная задача является классической задачей исследования операций. Множество задач распределения ресурсов сводится именно к этой задаче.

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

Имеются следующие исходные данные.

Наличие минеральных удобрений на складах.

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

Расстояния между складами и пунктами доставки.

На пересечении столбца конкретного пункта доставки со строкой склада находится информация о расстояниях между этими пунктом доставки и складом. Например, расстояние между 3 пунктом и складом №3 равно 10 километрам.

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

Рис.1 Изменяемые ячейки.

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

Например, значение ячейки B4=СУММ(C4:F4)

Значения ячеек по 9 строке по столбцам от С до F определяются суммированием данных ячеек соответствующих столбцов с 4 по 8 строки.

Например, значение ячейки С9=СУММ(C4:C8)

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

Теперь, используя исходные данные, введем на этом же листе требуемые объемы поставок и расстояния между складами и пунктами доставки.


Рис.2 Исходная информация.

В строке 16 по столбцам C-F определим грузооборот по каждому пункту доставки. К примеру для 1 пункта (ячейка С16) это рассчитывается с помощью формулы

С16=С4*С1 1 +С5*С1 2 +С6*С1 3 +С7*С14+С8*С15

либо можно использовать функцию СУММПРОИЗВ

В ячейке С4 находится количество минеральных удобрений, перевозимых со склада №1 в 1 пункт доставки, а в ячейке С11 — расстояние от склада №1 до 1 пункта доставки. Соответственно первое слагаемое в формуле означает полный грузооборот по данному маршруту. Вся же формула вычисляет полный грузооборот перевозок минеральных удобрений в 1 пункт доставки.

В ячейке В16 по формуле =СУММ(С16: F 16 ) будет вычисляться общий объем грузооборота минеральных удобрений.

Таким образом, информация на рабочем листе примет следующий вид (рис. 3 )

Рис. 3 . Рабочий лист, подготовленный для решения транспортной задачи

Для решения транспортной задачи воспользуемся процедурой Поиск решения, которая находится в меню Сервис.

После выбора данной команды появится диалоговое окно (рис. 4 ).

Рис. 4 . Диалоговое окно Поиск решения

Поскольку в качестве критерия оптимизации нами выбрана минимизация грузооборота, в поле Установить целевую ячейку введите ссылку на ячейку, содержащую формулу расчета о бщего объема грузооборота минеральных удобрений . В нашем случае это ячейка $ B $1 6 . Чтобы минимизировать значение конечной ячейки путем изменения значений влияющих ячеек (влияющими, в данном случае это и изменяемые ячейки, являются ячейки, которые предназначены для хранения значений искомых неизвестных), переключатель установите в положение минимальному значению;

В поле Изменяя ячейки введите ссылки на изменяемые ячейки, разделяя их запятыми; либо, если ячейки находятся рядом, указывая первую и последнюю ячейку, разделяя их двоеточием ($ С $4:$ F $8 ). Это означает, что для достижения минимального грузооборота перевозок будут меняться значения в ячейках с С4 по F8 , то есть будут изменяться количество груза, перевезенного по конкретному маршруту.

Если сейчас запустить процесс подбора параметров, то будет найден вариант, где все переменные равны нулю. И это правильно — если не перевозить ничего, то это самый дешевый вариант. Но нам необходимо перевезти минеральные удобрения, поэтому надо наложить некоторые ограничения для поиска решения.

В группе полей Ограничения нажмите кнопку Добавить. Появится диалог Добавление ограничения (рис. 5 )

Рис. 5 . Диалоговое окно Добавление ограничения

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

Рис. 6 . Диалоговое окно Поиск решения с заполненными полями

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

Читать еще:  Как сделать последовательность чисел в excel?

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

Первое условие $B$4:$B$8 =0. Оно означает, что объем перевозок не может быть отрицательным, то есть, если на складе не хватает минеральных удобрений, их не везут с пункта доставки, на который эти минеральные удобрения были завезены ранее. Грузопоток имеет только одно направление — от складов к пунктам доставки удобрений.

И. наконец, третье, и последнее условие $С$9:$F$9>=$C$10:$F$10. Оно означает, что значения в ячейках девятой строки должны быть больше или равны значениям в ячейках десятой строки,, то есть запросы пунктов доставки минеральных удобрений должны быть выполнены полностью. Перевыполнение объема поставок допустимо, а недовыполнение — нет.

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

После нахождения решения появляется диалог Результаты поиска решения (рис. 7 )

Рис. 7 . Диалоговое окно Результаты поиска решения

Нажав кнопку ОК, вы занесете вариант решения на рабочий лист (рис. 7).

Рис. 7. Решенная транспортная задача

Минимальный грузооборот перевозок при соблюдении всех условий равен 3540 т.-км.

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

Решение транспортной задачи в Excel — условное название для методов нахождения решения транспортной задачи с применением электронных таблиц Microsoft Excel.

Надстройка «Поиск решения» в Microsoft Excel позволяет напрямую находить оптимальное решение транспортной задачи. В MS Excel также можно организовать поиск начального допустимого плана и пошаговое решение транспортной задачи симплеккс-методом.

Содержание

[править] Рабочий лист

При решении в качестве начального этапа можно подготовить рабочий лист как показано на рисунке:

Можно, в частности, взять готовый пример здесь: [1]

[править] Формулы в таблице

Ячейки рядом с серыми (на изображении — строка 12 и столбец F) содержат формулы суммирования по строке и столбцу.

В отмеченной красным цветом итоговой ячейке использована формула =СУММПРОИЗВ(B4:E6;B9:E11), которая вычисляет сумму произведений цены на объем для каждого из путей перевозки груза. Другие ячейки на этом рабочем листе формул не содержат.

[править] Изменение числа поставщиков и потребителей

Если число строк и столбцов (поставщиков и потребителей) не совпадает с примером, их добавляют, «не задевая» первую и последнюю колонку из диапазона, чтобы не испортились настройки. Например, чтобы добавить еще одну колонку, добавляйте ее после столбца B, а нового поставщика — после строки Поставщик 1 в двух местах), после чего нужно «размножить» соответствующие формулы и оформление из имеющихся ячеек на вновь вставленные.

[править] Ввод исходных данных

В отмеченные зеленым цветом клетки затем надо ввести цены, в отмеченные серым — объем спроса и предложения. Желтые ячейки (объемы перевозки) при вызове надстройки «Поиск решения» программа посчитает сама.

[править] Сбалансированность задачи

Сумма спроса и сумма запасов (в этом примере = 90) должны совпадать, в противном случае требуется ввести фиктивного отправителя или поставщика с нулевыми ценами доставки (см. Транспортная задача#Балансировка задачи).

[править] Установка надстройки

Чтобы начать расчет, нужно убедиться, что в меню Сервис есть пункт меню «Поиск решения»:

Если его там нет, то нужно зайти в пункт «Надстройки» и установить соответствующую надстройку:

[править] Выполнение вычислений

Затем необходимо вызвать пункт меню «Сервис — Поиск решения»:

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

Для начала поиска решения нужно нажать кнопку «Выполнить», затем в появившемся окне — «Сохранить найденное решение».

[править] Округление

В итоговом решении могут оказаться числа наподобие 19.99999 или 1E-6 — для их форматирования до чисел с нужной разрядностью следует использовать кнопку «Формат с разделителями» на панели инструментов.

[править] Настройки для предотвращения зацикливания

По нажатию кнопки Параметры доступно окно с параметрами поиска решения:

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

[править] Итоговое решение

Общая стоимость транспортировки содержится в отмеченной красным цветом ячейке «Целевая функция». Чем меньше это значение, тем меньше будет затрачено денег на перевозку всего груза.

[править] Ограничение на величину таблиц

Excel 2003 выдает ошибку на таблицах определенной величины (из 2-3 десятков потребителей и поставщиков).

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