Содержание

Решение транспортной задачи в Excel (задача с обязательными поставками)

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

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

Для отображения формул необходимо на вкладке «Формулы» в группе «Зависимости формул» выбрать «Показать формулы» либо горячее сочетание клавиш «Ctrl+` (тильда)».

Дальше выбираем команду «Поиск решения» на вкладке «Данные» (Файл – Параметры – Надстройки – Управление – Поиск решений).

Решение транспортной задачи в MS Excel (фиктивный поставщик или потребитель)

Есть запасы однотипной продукции у поставщиков A1, A2, A3, A4.

Стоимость доставки единицы продукции от поставщиков к потребителям представлена в таблице.

Необходимо составить такой план перевозок, который бы удовлетворил все потребности и имел минимальную стоимость.

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

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

Сбалансировав саму задачи решаем ее стандартным способом. Для начал составим две таблицы: одна с данными, вторая – без.

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

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

Дальше выбираем команду «Поиск решения» на вкладке «Данные».

Как видно из решения все фиктивные поставки пришлись на потребителя В1, именно у него будет недопоставка в 40 единиц товара.

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

Решение транспортной задачи в Excel (задача с обязательными поставками)

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

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

Есть запасы однотипной продукции у поставщиков A1, A2, A3, A4.

Стоимость доставки единицы продукции от поставщиков к потребителям представлена в таблице.

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

Допустим, у первого поставщика есть обязательство перед потребителем B3 в обязательной поставке 200 единиц товара, а у второго – перед потребителем B2, в обязательной поставке 80 единиц товара.

Записанное условие в таблицах MS Excel выглядит следующим образом:

Как видим, минимальная стоимость перевозки несколько больше предыдущей задачи (1690 против 1280), поскольку контракты на обязательную поставку снизили общую эффективность перевозки.

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

Модели организации как закрытой, открытой, частично открытой системы: Закрытая система имеет жесткие фиксированные границы, ее действия относительно независимы.

[expert_bq id=»1570″]Задача поиска кратчайшего пути на графе может быть определена для неориентированного , ориентированного или смешанного графа. Если же вы хотите что-то уточнить, обращайтесь ко мне![/expert_bq] Когда я писала эту статью, мне очень хотелось придумать задачу на Поиск решения, которая была бы полезна в реальной практике. Я опросила множество экономистов, никто из моих знакомых Поиск решения в своей работе не применял.

Как Решить Задачу о Кратчайшем Пути в Excel • Наивное решение

Вычислительные машины и труднорешаемые задачи Задача о кратчайшем пути | Геннадий Степанов | Яндекс Дзен

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

Алгоритм Дейкстры нахождения кратчайшего пути

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

Для решения указанной задачи можно использовать алгоритм Дейкстры — алгоритм на графах, изобретённый нидерландским ученым Э. Дейкстрой в 1959 году. Находит кратчайшее расстояние от одной из вершин графа до всех остальных. Работает только для графов без рёбер отрицательного веса.

Пусть требуется найти кратчайшие расстояния от 1-й вершины до всех остальных.

Кружками обозначены вершины, линиями – пути между ними (ребра графа). В кружках обозначены номера вершин, над ребрами обозначен их вес – длина пути. Рядом с каждой вершиной красным обозначена метка – длина кратчайшего пути в эту вершину из вершины 1.

Инициализация

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

Первый шаг

Минимальную метку имеет вершина 1. Её соседями являются вершины 2, 3 и 6. Обходим соседей вершины по очереди.

Все соседи вершины 1 проверены. Текущее минимальное расстояние до вершины 1 считается окончательным и пересмотру не подлежит. Вершина 1 отмечается как посещенная.

Второй шаг

Шаг 1 алгоритма повторяется. Снова находим «ближайшую» из непосещенных вершин. Это вершина 2 с меткой 7.

Снова пытаемся уменьшить метки соседей выбранной вершины, пытаясь пройти в них через 2-ю вершину. Соседями вершины 2 являются вершины 1, 3 и 4.

Все соседи вершины 2 просмотрены, помечаем её как посещенную.

Третий шаг

Повторяем шаг алгоритма, выбрав вершину 3. После её «обработки» получим следующие результаты.

Четвертый шаг

Пятый шаг

Шестой шаг

Таким образом, кратчайшим путем из вершины 1 в вершину 5 будет путь через вершины 1 — 3 — 6 — 5, поскольку таким путем мы набираем минимальный вес, равный 20.

Реализация алгоритма Дейкстры

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

// Восстановление пути
int ver[SIZE]; // массив посещенных вершин
int end = 4; // индекс конечной вершины = 5 — 1
ver[0] = end + 1; // начальный элемент — конечная вершина
int k = 1; // индекс предыдущей вершины
int weight = d[end]; // вес конечной вершины

Результат выполнения

[expert_bq id=»1570″]Важно учитывать, что если переменные должны быть выражены неотрицательным или целым числом — это тоже ограничения , которые необходимо задать. Если же вы хотите что-то уточнить, обращайтесь ко мне![/expert_bq] Метка самой вершины 1 полагается равной 0, метки остальных вершин – недостижимо большое число (в идеале — бесконечность). Это отражает то, что расстояния от вершины 1 до других вершин пока неизвестны. Все вершины графа помечаются как непосещенные.

Алгоритм Дейкстры нахождения кратчайшего пути

Таким образом, требуется
составить план перевозок продукции от поставщиков к потребителям так, чтобы
потребности потребителей были бы удовлетворены за счет вывоза запаса от
поставщиков. Цель – минимизация суммарной стоимости всех перевозок.

Дополнительные данные → Похожие темы → Все про Exel → Как вставить значения → Как объединить ячейки → Как вставить форматы → Дополнительные данные → Вставить формулы→ Аргументы функции