Решение задач о планировании перевозок — страница 5

  • Просмотров 227
  • Скачиваний 7
  • Размер файла 58
    Кб

некоторая переменная не подчинена условию неотрицательности, то ее заменяют (в целевой функции и во всех ограничениях) разностью неотрицательных переменных , l - свободный индекс Транспортная задача в матричной постановке и ее свойства Данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (||xi,j||mxn), который минимизирует целевую функцию на множестве

допустимых планов при соблюдении условия баланса Если привести условия транспортной задачи к канонической форме задачи линейного программирования, то матрица задачи будет иметь размерность (m+n)mn. Матрицы систем уравнений в ограничениях имеют ранги, равные соответственно m и n. Однако, если, с одной стороны, просуммировать уравнения по m, а с другой — уравнения по n, то получим одно и то же значение. Из этого следует, что одно из

уравнений в системе является линейной комбинацией других. Таким образом, ранг матрицы транспортной задачи равен m+n -1, и ее невырожденный базисный план должен содержать m+n -1 ненулевых компонент. Процесс решения транспортной задачи удобно оформлять в виде последовательности таблиц. Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта ai), а столбцы —

пунктам потребления (последняя клетка каждого столбца содержит значение потребности bj). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i-го пункта в j-й: в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки (xi,j=0), называют

свободными, а ненулевые — занятыми (xi,j>0). C1,1 C1,2 …… C1,n   X1,1 X1,2 …… X1,n A1 C2,1 C2,2 …… C2,n   X2,1 X2,2 …… X2,n A2 …. …. …. …. …. Cm,1 Cm,2 …… Cm,n   Xm,1 Xm,2 …… Xm,n Am B1 B2 …. Bn   Построение исходного допустимого плана в транспортной задаче По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного плана. Наиболее простой способ его нахождения основывается на так

называемом методе северо-западного угла. Суть метода состоит в последовательном распределении всех запасов, имеющихся в первом, втором и т. д. пунктах производства, по первому, второму и т. д. пунктам потребления. Каждый шаг распределения сводится к попытке полного исчерпания запасов в очередном пункте производства или к попытке полного удовлетворения потребностей в очередном пункте потребления. На каждом шаге q величины