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

Задача планирования производства.

Каноническая форма ЗЛП.

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

Правила перехода от общей задачи линейного программирования к канонической ЗЛП:

§ ограничения в виде неравенств преобразуются в уравнения за счет добавления фиктивных неотрицательных переменных xi (если в неравенстве стоит знак ≤, то новая переменная прибавляется; если ≥ - вычитается), которые одновременно входят и в целевую функцию с коэффициентом 0, то есть не оказывают влияния на ее значение;

§ переменные, на которые не наложено условие неотрицательности, представляются в виде разности двух новых неотрицательных переменных.

Предприятие располагает m видами ресурсов и может выпускать некоторую однородную продукцию n различными способами. За единицу времени использования j-го технологического способа (j=1,…,n) расходуется a_ij (i=1,…,m) единиц i-го ресурса и выпускается c_i единиц продукции. Требуется спланировать работу предприятия так, чтобы оно выпускало наибольшее количество продукции при условии, что ресурса i-го вида нельзя израсходовать более чем b_i единиц.

Пусть x_j≥0 (j=1,…,n) – время использования предприятием j-го технологического процесса, если при этом функция Z – количество выпущенной продукции, то функция Z (x) будет равна

n

Z(x) = ∑ c_jx_j.

j=1

Работая по этому плану, предприятие израсходует ∑ a_ijxj (j=1,n) единиц i-го ресурса. Тогда задача линейного программирования будет выглядеть так:

n

Z(x) = ∑ c_jx_jàmax

j=1

		n ∑ aijxj ≤ bi j=1 xj ≥ 0

Пример 2. Задача о рационе.

В хозяйстве имеется n видов кормов. Каждый из которых содержит m разновидностей питательных веществ. Известно, что одна единица j-го вида кормов (j=1,…,n) содержит a_ij единиц i-го питательного вещества (i=1,…,m) и имеет стоимость c_j. требуется составить такой рацион, который удовлетворял бы всем потребностям в питательных веществах и имел бы наименьшую стоимость.

Обозначим количество j-го корма в рационе x_j≥0 (j=1,…,n), а Z– стоимость этого рациона, тогда составляем

n

Z(x) = ∑ c_jx_jàmin

j=1

		n ∑ aijxj ≥ bi j=1 xj ≥ 0

Пример 3. Транспортная задача.

Пусть некоторый однородный продукт хранится на m складах и потребляется в n пунктах. Известны следующие параметры:

a_i – запас продукта на i-ом складе, a_i > 0 и (i=1,…,m);

b_i – потребность в продукте в j-ом пункте, (j=1,…,n);

c_ij – стоимость перевозки единичного количества продукта с i-го склада в j-ый пункт, c_ij>0.

При этом суммарные запасы равны суммарным потребностям:

m n

∑ a_i = ∑ b_i

_{j=1 j=1}

Тогда транспортная задача ставится так:

m n

∑ ∑ c_ijx_ijàmin

_{j=1 j=1}

m ∑ x_ij = a_{i j=1}   n ∑ x_ij = b_{j j=1} x_j ≥ 0      

X_ij показывает количество продукта, перевозимого с i-го склада в j-ый пункт.

Требуется организовать перевозки продукта со склада в пункты потребления так, чтобы при полном удовлетворении потребностей минимизировать суммарные транспортные расходы.

Пример 4. Задача о смесях.

Возникла проблема составления таких рабочих смесей на основе исходных материалов, которые обеспечивали бы получение конечного продукта, обладающего определенными свойствами. К этой задаче относится группа задач, например о выборе диеты, составления кормового рациона в животноводстве, горюче-смазочных смесей.

Высокий уровень затрат на исходные материалы и необходимость повышения эффективности производства выдвигают на первый план задачу получения продукции с заданными свойствами при наименьших затратах на исходные сырьевые материалы.

Математическая модель задачи может быть сформулирована как нахождение минимального значения целевой функции со следующими ограничениями:

n

Z(x) = ∑ c_jx_jàmin

j=1

Где j – номер продукта;

a_ij – количество единиц i-го питательного вещества j-го продукта;

c_ij – стоимость единицы продукта j-го вида;

b_i - минимум единиц i-го питательного вещества, необходимого для жизнедеятельности организма.

Одной из часто встречающихся задач хозяйственного управления является задача по разработке рационального плана транспортных перевозок. Основная цель организации перевозок – минимизация затрат на их выполнение.

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

Формулировка транспортной задачи в общем виде осуществляется следующим образом: требуется перевезти определенное количество однородного груза из m пунктов отправления в n пунктов назначения.

Для записи задачи в математической форме вводятся следующие обозначения:

n – число пунктов отправления;

m – число пунктов назначения;

a_i – общее количество груза в i-м пункте отправления;

b_j – общее количество груза, необходимое в j-м пункте назначения;

c_ij – затраты на транспортировку единицы груза из i-го пункта отправления в j-й пункт назначения;

Z – совокупные затраты на транспортировку всего груза;

x_ij – исходно неизвестное количество груза, которое перевозится из пункта i в пункт j.

Непосредственно из условий задачи получаем следующую модель линейного программирования:

m n

∑ ∑ c_ijx_ijàmin (6)

_{j=1 j=1}

m (7)

∑ x_ij = a_i, i=1,2,…,n.

_j=1

n

∑ x_ij = b_j , j=1,2,…,n. (8)

_j=1

x_jj ≥ 0, i=1,2,…,n; j=1,2,…,n. (9)

Целевая функция (6) минимизирует совокупные затраты на транспортировку всех партий грузов из всех пунктов отправления во все пункты назначения. Система ограничений (7) говорит о том, что весь груз из каждого пункта его сосредоточения должен быть вывезен. Система ограничений (8) говорит о том, что потребность в грузе в каждом пункте назначения должна быть удовлетворена. Система ограничений (9) говорит о том, что по любому маршруту либо перевозится некоторое количество груза, либо нет.

Таким образом, транспортная задача является задачей линейного программирования с n+m ограничениями-уравнениями и n+m неизвестными.

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

m n

∑ a_i = ∑ b_i (10)

_{j=1 j=1}

называется закрытой (сбалансированной) транспортной задачей. В случае, если условие (10) не выполняется, то транспортная задача называется открытой. Выполнение условия (10) позволяет исключить одно из ограничений (7), (8) и свести их число к n+m-1. Более того, если выполняется условие (10), то доказывается, что любая транспортная задача имеет оптимальное допустимое решение (план), содержащее не более n+m-1 компонент.

Транспортным задачам присущи следующие особенности:

· распределению подлежат однородные ресурсы;

· условия задачи описываются только уравнениями;

· все переменные выражаются в одинаковых единицах измерения;

· во всех уравнениях коэффициенты при неизвестных равны единице;

Дата добавления: 2014-01-15