Проверка оптимальности распределения поставок

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

Постановка задачи

Важным частным случаем ЗЛП является транспортная задача. Задача выглядит следующим образом: имеется m поставщиков и n потребителей, мощности поставщиков, спросы потребителей и затраты на перевозку единицы груза для каждой пары «поставщик-потребитель».

Задача представляется в виде таблицы.

Поставщики Мощность поставщиков Потребители и их спрос
n
N1 N2 Nn
M1 c11   х11 c12   х12 c1n   х1n
M2 c21   х21 c22   х22 c2n   х2n
m Mm cm1   хm1 cv2   хv2 cmn   хmn

В левом верхнем углу клетки стоит коэффициент затрат cij – затраты наперевозку единицы груза от i-го поставщика j-му потребителю.

Задача ставится следующим образом: найти объемы перевозок xij для каждой пары «поставщик-потребитель», так чтобы:

  1. Мощности всех поставщиков были реализованы.
  2. Спросы всех потребителей были удовлетворены.
  3. Суммарные затраты на перевозку должны быть минимальны.

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

Первая система ограничений для поставщиков

Проверка оптимальности распределения поставок - student2.ru х1112+…+х1n=M1

х2122+…+х2n=M2

хm1m2+…+хmn=Mm

Вторая система ограничений для потребителей

Проверка оптимальности распределения поставок - student2.ru х1121+…+хm1=N1

х1222+…+хm2=N2

х1n2n+…+хmn=Nn

Очевидно, что объем перевозимого груза не может быть отрицательным, поэтому следует предположить, что xij³0 (i=1,..,m; j=1,…,n).

Суммарные затраты F на перевозку выражаются через коэффициенты затрат и поставки следующим образом: F=c11x11+c12x12+…+c1nx1n+…+cmnxmn

Математическая постановка задачи

На множестве неотрицательных решений систем ограничений Проверка оптимальности распределения поставок - student2.ru и Проверка оптимальности распределения поставок - student2.ru найти такое решение Х=(х1112,…,хij,…,xmn), при котором линейная функция Проверка оптимальности распределения поставок - student2.ru принимает минимальное значение.

Транспортные задачи делятся на закрытые (сбалансированные) и открытые.

Закрытая модель-это частный случай транспортной задачи, при которой суммарные мощности поставщиков равны суммарным спросам потребителей.

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

Нахождение первоначального базисного распределения поставок

По аналогии с другими задачами линейного программирования решение транспортной задачи начинается с построения допустимого базисного распределения. Первоначальное базисное распределение поставок можно найти:

ü методом северо-западного угла;

ü методом минимального элемента;

ü методом Фогеля и т.д.

Проверка оптимальности распределения поставок

Базисное распределение поставок оптимально тогда и только тогда, когда оценки всех свободных клеток неотрицательны.

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

Наши рекомендации