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

Пусть имеется несколько пунктов отправления, в которых сосредоточены запасы какого-либо однородного товара в определенных количествах, несколько пунктов назначения, которые хотят получить этот товар в определенных количествах. Известно, что сумма заявок на получение груза из всех пунктов назначения равна сумме запасов товара, находящегося во всех пунктах отправления. Известна стоимость перевозки единицы товара от каждого пункта отправления до каждого пункта назначения. Требуется составить такой план перевозок, чтобы:

Все грузы из всех пунктов отправления были вывезены;

Заявки всех пунктов назначения были бы удовлетворены;

Суммарные затраты на перевозку были бы минимальны.

Математическая формулировка транспортной задачи

Обозначим через x_ijколичество товара, который перевозится из пункта отправления A_i.. в пункт назначения B_j…(i=1,…,m; j=1,…,n); ai- количество товара, сосредоточенного в пункте отправления Ai; bj- количество товара, заявленного в пункте назначения B_j.

Первое содержательное ограничение: сумма товара, содержащегося во всех пунктах отправления, должна равняться сумме заявок на доставку данного товара, которые подали все пункты назначения. Математически это означает, что должно выполняться уравнение:

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

а линейная функция

В этой задаче необходимо найти такой вектор X=(x₁₁, …, x_nm), который удовлетворял бы построенной системе ограничений и доставлял бы минимум целевой функции. Важная особенность данной задачи – соблюдение баланса между количеством товара, которое хотят приобрести по заявкам все пункты назначения, и количеством груза, имеющегося во всех пунктах отправления. Такие транспортные задачи наз. закрытыми (при несоблюдении баланса - открытыми).

Каноническая задача линейного программирования заключается в минимизации (максимизации) линейной целевой функции

F(x) = c_lx₁+c₂x₂+... + c_nx_n при ограничениях (2.3)

a₁₁х₁ +а₁₂х₂ +...+а₁_nх_n=b₁

а²¹х₁ +а₂₂х₂ +...+а₂_nх_n=b₂…

…

а_m1х₁ +а_m2х₂ +...+а_mпх_n=b_m

x_t,x₂,...,x_n>0.

где с₁,с₂,...,с_n - коэффициенты целевой функции, a_tJ, i = 1, 2,...,n, j = 1, 2,...,m -коэффициенты системы ограничений, а b₁,b₂,...,b_m- свободные члены, которые считаются неотрицательными.

Вектор X = (x₁, х₂,..., x_n, удовлетворяющий ограничениям задачи ЛП, называется допустимым решением или планом. Допустимый план X* =(x*₁,x*₂,...,x*_n), при котором целевая функция задачи ЛП принимает максимальное (минимальное) значение, называется оптимальным планом.

Иными словами, каноническая задача линейного программирования (ЛП) состоит в нахождении среди всех решений выписанной выше системы линейных уравнений такого ее неотрицательного решения, на котором достигает своего минимального (максимального) значения линейная целевая функция F(x) от n переменных.

В задаче линейного программирования общего вида вместо некоторых (всех) равенств в ограничениях записаны нестрогие неравенства в ту или другую сторону; при этом условие не отрицательности переменных может отсутствовать для части или же для всех переменных. Известно, что решение любой задачи линейного программирования может быть сведено к решению канонической задачи, представляемой в форме (2.1, 2.2) или (2.3).

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