Транспортная задача с промежуточными пунктами

Транспортная сеть

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

Рис. 17. Сеть маршрутов перевозок фирмы.

На рис. 17 показана сеть маршрутов перевозок, причём если из пункта 4 в пункт 5 перевозки осуществляются своим транспортом, а в обратном направлении с помощью наёмного транспорта, то стоимость перевозки единицы груза С₄₅ < С₅₄. В представленной сети имеется один “источник”, из которого существует только исходящий поток грузов, и два “стока”, в которые направлены только входящие потоки грузов. В источнике (пункт 1), а также в пункте 2 имеются избытки запасов, соответственно равные 10 и 2 единицам товара. В стоках (пункты 3 и 8), а также в пункте 6 имеется дефицит товара, соответственно равный 3, 8 и 1 единицам.

В задачах такого типа предложение источника соответствует избытку товара в данном пункте (а₁ = 10), а предложение других пунктов a_k = T_k + S, где T_k – избыток (со знаком +) или спрос (со знаком -) в k-ом пункте, S – суммарное предложение для перемещаемых грузов (S = 10+2=12). Спрос стоков равен потребности в грузах в данных пунктах (b₃ = 3, b₈ = 8), а спрос для других пунктов, равен b_k = S. Решение задачи в виде оптимального плана перевозок при минимуме затрат, представлено на рис. 18.

Рис. 18. Исходные данные и оптимальный план перевозок

Задачи с булевыми переменными

Задачи с булевыми переменными (по имени английского математика Джорджа Буля), которые могут принимать значения только δ_i = 0, либо δ_i = 1, - являются частным случаем задач с целочисленными переменными и задач дискретного программирования.

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

Задача. Допустим, рассматриваются четыре проекта, имеющие различные варианта использования ресурсов и различную прибыльность. Имеющиеся в распоряжении фирмы и требуемые для реализации проектов ресурсы (в чел. и ден.ед.), а также ожидаемая прибыль (в ден.ед.) представлены на рис. 19.

Рис.19. Исходные данные задачи выбора проектов

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

,

где δ_j – булева переменная, C_j – прибыль от реализации j-го проекта, a_ij – ресурсы i-го вида, необходимые для реализации j-го проекта, b_i – имеющийся запас ресурсов i-го вида, m - количество видов ресурсов, n – количество рассматриваемых проектов.

Все цифровые данные необходимо ввести в таблицу Excel, выделить свободные ячейки под искомые значения переменных (В9:Е9) и ввести функцию цели {=СУММПРОИЗВ($B$9:$E$9;B11:E11)} в ячейку F11. В ячейки F13 и F14 ввести выражения для левой части ограничений (рис. 20). В меню Сервис вызвать программу Поиск решения, указать адрес ячейки, содержащей целевую функцию, направление поиска экстремума (max), адреса ячеек, предназначенных для значений искомых переменных. Добавить ограничения по ресурсам и указание на двоичный вид переменных (рис. 21).

Рис. 20. Формирование математической модели в Excel

Рис. 21. Ввод условий задачи в программу Поиск решения

Рис. 22. Результаты решения задачи выбора

Левая часть ограничений является ссылкой на адреса ячеек, содержащих математические выражения, а правая часть ограничений – это ссылка на ячейки, содержащие числовые значения наличного запаса ресурсов. Результаты решения задачи (рис. 22) показывают, что следует выбрать третий и четвёртый проекты, которые принесут максимальную прибыль в количестве 300 ден. ед. Финансовые ресурсы при этом будут использованы не полностью вследствие ограниченного количества трудовых ресурсов, которые будут задействованы полностью.

Использование булевых переменных позволяет вводить в задачу логические условия вида “если…, то…”. Например, если необходимо выбрать из пары вариантов только один (δ_i или δ_j), то логическое условие имеет вид: δ_i + δ_j = 1. Если может быть выбран один вариант и другой, оба вместе или не один из них, то логическое условие имеет вид: δ_i + δ_j ≥ 0. Если при выборе i-го варианта следует принять и j-ый, то логическое условие имеет вид: δ_i = δ_j или δ_i - δ_j = 0. Если при выборе k-го варианта следует принять вариант i, либо j, то логическое условие имеет вид: δ_i + δ_j = δ_k или δ_i + δ_j - δ_k = 0. Если необходимо из четырёх проектов выбрать по крайней мере три, то логическое условие имеет вид: δ₁ + δ₂ + δ₃ + δ₄ ≥ 3.

Использование последнего условия показано на рис. 23.

Рис. 23. Результаты решения с логическим ограничением

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