27) Экономическая и математическая формулировка транспортной задачи. Необходимое и достаточное условия ее разрешимости.

1. Формулировка транспортной задачи. Однородный груз сосредоточен у m поставщиков в объемах  . Данный груз необходимо доставить n потребителям в объемах  . Известны  , i=1,2,,…,m, j=1,2,…,n- стоимости перевозки единицы груза от каждого I-го поставщика каждому j-му потребителю. Требуется составить такой план перевозок, при котором запасы всех потребителей полностью удовлетворены и суммарные затраты на перевозку всех грузов минимальны. Исходные данные транспортной задачи обычно записываются в таблице (таб1.1).

			…
			…
			…
…	…	…	….	….
			…

Таблица1.1.  И сходные данные задачи могут быть представлены также в виде вектора запасов поставщиков А=( ), вектора запросов потребителей  В= ( ) и матрицы стоимостей   .  В транспортных задачах под поставщиками и потребителями понимаются различные промышленные и сельскохозяйственные предприятия, заводы, фабрики, слады, магазины и т.д. Однородными считаются грузы, которые могут быть перевезены одним видом транспорта. Под стоимостью перевозок понимаются тарифы, расстояния, время, расход топлива и т.п. ^ 2. Математическая модель транспортной задачи. Переменными (неизвестными) транспортной задачи являются   i=1,2,,…,m, j=1,2,…,n – объемы перевозок от каждого i-го поставщика каждому j-му потребителю. Эти переменные можно записать в виде матрицы перевозок  . Так как произведение   определяет затраты на перевозку груза от i-го поставщика j-му потребителю, то суммарные затраты на перевозку всех грузов равны  . По условию задачи требуется обеспечить минимум суммарных затрат. Следовательно, целевая функция имеет вид  . Система ограничений задачи состоит из двух групп уравнений. Первая группа из m уравнений описывает тот факт, что запасы всех m поставщиков вывозятся полностью: , i=1,2,…,m. Вторая группа из n уравнений выражает требование полностью удовлетворить запросы всех n потребителей: , j=1, 2, … , n. Учитывая условие неотрицательности объемов перевозок, математическую модель задачи можно записать так: , (1) , i=1,2,…,m , (2) , j=1, 2, … , n, (3) , i=1,2,,…,m, j=1,2,…,n (4) В рассмотренной модели транспортной задачи предполагается, что суммарные запасы поставщиков равны суммарным запросам потребителей, т.е.  . Такая задача называется задачей с правильным балансом, а ее модель – закрытой. Если же это равенство не выполняется, то задача называется задачей с неправильным балансом, а ее модель – открытой. Математическая формулировка транспортной задачи такова: найти переменные задачи  , i=1,2,,…,m, j=1,2,…,n, удовлетворяющие системе ограничений (2), (3), условиям неотрицательности (4) и обеспечивающие минимум целевой функции (1).  Математическая модель транспортной задачи может быть записана в векторном виде.. Тогда математическая модель транспортной задачи запишется следующим образом: , (7) = , (8) , i=1,2,,…,m, j=1,2,…,n (9)

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