Транспортная задача

Двухиндексные ЗЛП – это задачи оптимизации, в которых искомые переменные представляют собой матрицу

Примером может служить транспортная задача по критерию стоимости, которая формулируется следующим образом.

Задача.В четырёх районах А₁, А₂ ,А₃ ,А₄ (поставщики) имеется зерно, которое требуется доставить на три элеватора В₁, В₂, В₃ (потребители) согласно их мощностям. Запасы зерна в районах (мощность поставщика а_i), мощности элеваторов (мощность потребителя b_j) и затраты на перевозку 1т зерна из каждого района на каждый элеватор (c_ij) приведены в таблице (матрице затрат).

Составить план перевозок грузов так, чтобы затраты на эти перевозки были минимальны.

Решение.

1. Введём управляющие переменные:

x_ij – количество зерна, перевозимого из района А_i на элеватор В_j.

Следовательно, искомая матрица перевозок

2. Построим функцию цели.Стоимость перевозки зерна из пункта А_i в пункт В_j составит c_ij x_ij. Тогда целевая функция – наименьшие суммарные затраты на все перевозки – запишется выражением

или в общем виде:

3. Для составления ограничений проверим баланс задачи.

Всего зерна в районах (мощности поставщиков)

Элеваторы могут принять (мощности потребителей)

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

4. Запишем систему ограничений.

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

или

По потребителю: условие полной загрузки элеваторов:

или .

По смыслу все

<20 21 222324 25 26 >

Дата добавления: 2016-10-17; просмотров: 1587;