Материал: 5442

56

Рисунок 38 – Постановка транспортной задачи в Excel

В окне Поиск решения (рисунок 39) установим следующие параметры:

Целевая ячейка: G18, – минимум

Изменяя ячейки: B12:F15

Ограничения: G4:G7=G12:G15 – выбраны все запасы

B8:F8=B16:F16 – выполнены все заказы

B12:F15 – неотрицательны

Рисунок 39. Работа с окном Поиск решения

При такой организации данных все перевозки окажутся целыми числами (если целыми являются числа в колонках Запасы и Заказы) (рисунок 40).

58

Фиктивный потребитель покажет, сколько не надо отправлять груза от каждого поставщика.

Несбалансированность: дефицит запасов

В случае дефицита запасов, когда сумма запасов меньше, чем сумма заказов, т.е.

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

Запрещённый маршрут

Ещё одно возможное осложнение транспортной задачи – это запрещение определённой перевозки от i-го поставщика к j-му потребителю для составляемого плана перевозок (ремонт дороги, неплатёж и прочее). В этом случае, естественно, можно просто ввести ограничение Хij = 0. Однако это означает невозможность использования эффективных "транспортных" алгоритмов решения.

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

Задача о назначениях

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

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

59

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

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

Мастер должен расставить 4 рабочих для выполнения 4 типовых операций. Из данных хронометрирования известно, сколько минут в среднем тратит каждый из рабочих на выполнение каждой операции. Эти данные представлены в таблице 5.

Таблица 5 – Исходные данные

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

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

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

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

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

60

все остальные – равными нулю. Никаких дополнительных условий целочисленности не требуется.

Рисунок 41 – Постановка задачи о назначениях в Excel

Решение задачи с помощью Excel полностью аналогично транспортной задаче.

Сценарии

Excel предоставляет возможность в процессе моделирования проверить последствия изменения определённых входных данных, сохраняя набор их значений в качестве сценария, который можно реализовать в любой момент. Сценарий – это набор значений, которые Microsoft Excel сохраняет и может автоматически подставлять на листе. Сценарии можно использовать для прогноза результатов моделей и систем расчётов. Существует возможность создать и сохранить на листе различные группы значений, а затем переключаться на любой из этих новых сценариев для просмотра различных результатов.

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

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