XREFF.RU


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



Если Вам понравился сайт нажмите на кнопку выше

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

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

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

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

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

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

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

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

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

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

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

F(x) = clx1+c2x2+... + cnxn при ограничениях (2.3)

a11х1 +а12х2 +...+а1nхn=b1

а21х1 +а22х2 +...+а2nхn=b2…

аm1х1 +аm2х2 +...+аmпхn=bm

xt,x2,...,xn>0.

где с1,с2,...,сn - коэффициенты целевой функции, atJ, i = 1, 2,...,n, j = 1, 2,...,m -коэффициенты системы ограничений, а b1,b2,...,bm - свободные члены, которые считаются неотрицательными.

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

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

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

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

uib.deutsch-service.ru
  • Карта сайта