Решение транспортной задачиТеоретические основы В общем виде транспортную задачуможно сформулировать следующим образом: в m пунктах отправления A1, …, Am находится однородный груз, количество которого равно соответственно a1, …, am единиц. Данный груз необходимо доставить потребителям B1, …Bn, спрос которых – b1,…bn. Стоимость перевозки единицы груза из i-го () пункта отправления в j-й () пункт назначения равен сij. Необходимо составить план перевозок, который полностью удовлетворяет спрос потребителей в грузе, и при этом суммарные транспортные издержки минимальны. Математически транспортную задачу можно записать так: Таким образом, даны система ограничений (2) при условии (3) и линейная функция (1). Требуется среди множества решений системы (2) найти такое неотрицательное решение, которое доставляет минимум линейной функции (1). Модель транспортной задачи называют закрытой (сбалансированной), если суммарный объем груза, имеющегося у поставщика, равен спросу потребителей, т.е. выполняется равенство: . Если для транспортной задачи выполняется одно из условий: , то модель задачи называют открытой (несбалансированной). Для разрешимости транспортную задачу с открытой моделью следует преобразовать в закрытую. Если выполняется условие , то необходимо ввести фиктивный (n+1) –й пункт назначения Bn+1,т.е. в матрицу задачи вводится дополнительный столбец. Спрос фиктивного потребителя принимается равным . Стоимость перевозок продукции полагается одинаковой, чаще всего равной нулю (если не задана стоимость складирования продукции), т.е. . Если выполняется условие , то необходимо ввести фиктивного (m+1)-го поставщика Am+1,т.е. в матрицу задачи вводится дополнительная строка. Запас груза данного поставщика принимается равным . Стоимость перевозок продукции полагается одинаковой, чаще всего равной нулю (если не задана стоимость штрафов за недопоставку продукции), т.е. . При преобразовании открытой задачи в закрытую целевая функция не меняется, так как все слагаемые, соответствующие дополнительным перевозкам, равны нулю.
|