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

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

Для изготовления n видов продукции используется m видов ресурсов.

Обозначим через x_j…-число единиц j-го вида продукции (j=1,…,n), запланированной к производству;

b_i- запас i-го ресурса (i=1,…,m)

a_ij…-число единиц ресурса i, затрачиваемого на изготовление единицы продукции j-го вида (a_ij- технологические коэффициенты);

c_j- выручка от реализации единицы продукции j-го вида (или цена продукции j-го вида).

Тогда экономико-математическая модель задачи об использовании ресурсов в общей постановке примет вид:

Найти такой план X=(x_{1, …,} x_n) выпуска продукции, который удовлетворял бы системе ограничений:

и при котором целевая функция достигала бы своего максимального значения

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

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

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

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

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

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

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

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

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

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

Дата добавления: 2017-02-01