Задачи линейного программирования

ЛИНЕЙНОЕ ПРОГРАММИРОВАНИЕ

Типичные классы задач

Накопленный опыт в решении практических задач исследования операций позволяет выделить по содержательной постановке типичные классы задач[1,2}.

1. Управления запасами

2. Распределения ресурсов

3 Ремонта и замены оборудования

4 Массового обслуживания

5 Упорядочения

6 Сетевого планирования и управления

7 Выбора маршрута

8 Комбинированные

Среди известных разделов математического программирования наиболее развитым и законченным является линейное программирование (ЛП). Несмотря на требования линейности целевой функции и ограничений, в рамки линейного программирования укладываются задачи распределения ресурсов, управления запасами, сетевого и календарного планирования, транспортные задачи, задачи теории расписаний и т.д.

В качестве примера рассмотрим задачу о перевозках. Имеется m cкладов:

С_1, С_2,……., С_m

и n пунктов потребления

П ₁, П _2,……,П _n.

Необходимо составить план перевозок со складов С_1, С_2,……., С_m в пункты П ₁, П _2,……,П _n

некоторого товара. На складах имеются запасы товара в количествах

а_1, а_2,……, а_m

единиц. Пункты потребления подали заявки соответственно на

b_1, b₂,…..b_n

единиц товара. Заявки выполнимы, т.е. сумма всех заявок не превосходит суммы всех имеющихся запасов:

∑b ≤ ∑a,

Склады С_1, С_2,……., С_m связаны с пунктами потребления П ₁, П _2,……,П _n какой-то сетью дорог с определенными тарифами на перевозки. Стоимость перевозки со склада С_i в пункт П_j равна с_ij

(i = 1,2,...,m, j = 1,2,…, n).

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

Обозначим x _{i j} -- количество единиц товара, направляемое со склада С_i в пункт П_j. Решение (план перевозок) состоит из mn чисел:

x _11, x_12,.......,x_1n

x _21, x_22,.......,x_2n

_{......................}

x _m1, x_m2,.......,x_mn

образующих прямоугольную таблицу (матрицу). Сокращенно ее обозначают (x _{i j}). Требуется такие неотрицательные значения переменных x _{i j}, чтобы были выполнены следующие условия:

1.Емкость складов не должна быть превышена, т.е. общее количество товара, взятое с каждого склада, не должно превышать имеющихся в нем запасов:

x _{11 +} x_{12 +......} x_1n ≤ a_1;

x _{21, +} x_{22 +.......} + x_2n ≤ a_2;

_{......................}

x _{m1 +} x_{m2 +.......} + x_mn ≤ a_m,

. 2.Заявки, поданные пунктами потребления, должны быть выполнены:

x _{11 +} x_{12 +....... +} x_1n = b_1;

x _{21, +} x_{22 +.......} + x_2n = b_2;

_{......................}

x _{m1 +} x_{m2 +.......} + x_mn = b_m,

Общая стоимость перевозок L L = c₁₁ x₁₁ + c₁₂ x₁₂ +.... + c_1n x_1n + c₂₁ x₂₁ + c₂₂ x₂₂ +.... + c_2n x_2n +

......+ c_m1 x_m1 + c_m2 x_m2 +.... + c_{m n} x_{m n},

или, гораздо короче,

_{m n}

L = ∑ ∑ c_ij x_ij.

^{i = 1 j = 1}

Требуется так выбрать план перевозок (x _{i j}), чтобы стоимость L этих перевозок обратить в минимум.

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

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

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