Курсовая работа: Решение задач о планировании перевозок

(2.5)

(2.6)

Коэффициенты a_i,j , b_i , c_j , j = 1, 2, ... , n, i =1, 2, ... , m – любые действительные числа (возможно 0).

Итак, решения, удовлетворяющие системе ограничений (2.4) условий задачи и требованиям неотрицательности (2.5), называются допустимыми , а решения, удовлетворяющие одновременно и требованиям минимизации (максимализации) (2.6) целевой функции, - оптимальными .

Выше описанная задача линейного программирования (ЗЛП) представлена в общей форме, но одна и та же (ЗЛП) может быть сформулирована в различных эквивалентных формах. Наиболее важными формами задачи линейного программирования являются каноническая и стандартная .

В канонической форме задача является задачей на максимум (минимум) некоторой линейной функции F , ее система ограничений состоит только из равенств (уравнений). При этом переменные задачи х₁ , х₂ , ..., х_n являются неотрицательными:

(2.7)

(2.8)

(2.9)

К канонической форме можно преобразовать любую задачу линейного программирования.

Правило приведения ЗЛП к каноническому виду:

1. Если в исходной задаче некоторое ограничение (например, первое) было неравенством, то оно преобразуется в равенство, введением в левую часть некоторой неотрицательной переменной, при чем в неравенства «≤» вводится дополнительная не отрицательная переменная со знаком «+»; в случаи неравенства «≥» - со знаком «-»

(2.10)

Вводим переменную .

Тогда неравенство (2.10) запишется в виде:

(2.11)

В каждое из неравенств вводится своя “уравнивающая ” переменная, после чего система ограничений становится системой уравнений.

2. Если в исходной задаче некоторая переменная не подчинена условию неотрицательности, то ее заменяют (в целевой функции и во всех ограничениях) разностью неотрицательных переменных

, l - свободный индекс

Транспортная задача в матричной постановке и ее свойства

Данная задача сводится к определению такого плана перевозок некоторого продукта из пунктов его производства в пункты потребления (||x_{i , j} ||_mxn ), который минимизирует целевую функцию

на множестве допустимых планов

при соблюдении условия баланса

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

Процесс решения транспортной задачи удобно оформлять в виде последовательности таблиц. Строки транспортной таблицы соответствуют пунктам производства (в последней клетке каждой строки указан объем запаса продукта a_i ), а столбцы — пунктам потребления (последняя клетка каждого столбца содержит значение потребности b_j ). Все клетки таблицы (кроме тех, которые расположены в нижней строке и правом столбце) содержат информацию о перевозке из i -го пункта в j -й : в левом верхнем углу находится цена перевозки единицы продукта, а в правом нижнем — значение объема перевозимого груза для данных пунктов. Клетки, которые содержат нулевые перевозки ( x_{i , j} =0 ), называют свободными, а ненулевые — занятыми ( x_{i , j} >0 ).

C_1,1 C_1,2 …… C_1,n

X_1,1 X_1,2 …… X_1,n A₁

C_2,1 C_2,2 …… C_2,n

X_2,1 X_2,2 …… X_2,n A₂