Составим математическую модель задачи. Обозначим через xij искомый объем перевозки от поставщика I к потребителю j и будем рассматривать переменные xij, задающие план перевозок, как компоненты матрицы перевозок X размеров :

. (13)

Затраты, связанные с некоторой перевозкой xij, составляют величину cijxij, а общая стоимость перевозок z от всех поставщиков ко всем потребителям определится равенством:

. (14)

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

(15)

а общие поставки любому потребителю удовлетворяли его спрос:

(16)

Из физического смысла переменных следуют условия их неотрицательности

(17)

В итоге получаем формулировку транспортной задачи: найти значения переменных xij, удовлетворяющие условиям (15) – (17) и минимизирующие целевую функцию (14). Это каноническая задача линейного программирования. В ней число переменных равно mn, число ограничений-равенств – m+n.

Левые части уравнений (15) образованы строчными , а уравнений (16) – столбцовыми элементами матрицы перевозок (13). В соответствии с условиями (15) и (16) сумма элементов i-й строки матрицы Х должна быть равна ai, а сумма элементов j-го столбца – bj. В дальнейшем будем называть уравнения (15) строчными, (16) – столбцовыми.

Для проверки условий совместности системы (15), (16) проведем суммирование уравнений (15) по индексу I, а (16) – по j. Получаем равенства

; ,

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

(18)

Условие (18) является условием совместимости системы ограничений (15) – (16). Оно выражает требования баланса между суммарными запасами и суммарными потребностями.

Транспортную задачу, для которой выполняется условие баланса (18), называют закрытой задачей. Если же условие нарушено, то задача называется открытой. Здесь возможны два случая:

а) суммарные запасы превышают суммарный спрос;

б) суммарный спрос больше суммарных запасов.

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

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

; (19)

;

;

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

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

Другое по теме:

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

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

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