Главная страница | Контакты | Случайная страница Автомобили Астрономия Биология География Дом и сад Другие языки Другое Информатика История Культура Литература Логика Математика Медицина Металлургия Механика Образование Охрана труда Педагогика Политика Право Психология Религия Риторика Социология Спорт Строительство Технология Туризм Физика Философия Финансы Химия Черчение Экология Экономика Электроника

Общая постановка транспортной задачи

Транспортная задача и методы ее решения

Общая постановка транспортной задачи

Транспортные задачи - специальный класс задач линейного программирования. В классической постановке эти модели описывают перемещение (перевозку) какого-либо товара из пункта отправления (например, места производства продукции) в пункт назначения (склад, магазин и т.п.) [1].

Назначение транспортной задачи - определение объемов перевозок из пунктов отправления в пункты назначения с минимальной суммарной стоимостью перевозок. При этом должны быть учтены ограничения, связанные с объемом предложения (производства) и спроса (потребности) [7].

Пусть имеется m поставщиков А_1,А₂,…,А_m, у которых сосредоточены запасы одного и того же груза в количестве a₁,a₂,...,a_m единиц соответственно. Этот груз нужно доставить n потребителям B₁,В₂,...В_m, заказавшим b₁,b₂,…,b_n единиц этого груза, соответственно. Известны так же все тарифы перевозок груза с_ij(стоимость перевозок единицы груза) от поставщика А_i к потребителю В_j (i=1,2,…,m; j=1,2,…,n). Все числа c_ij, образующие прямоугольную таблицу (матрицу), заданы:

С= . (1)

Считается, что стоимость перевозки нескольких единиц груза пропорциональна их числу. Требуется составить такой план перевозок (откуда, куда и сколько единиц везти), чтобы все заявки были выполнены, а общая стоимость всех перевозок была минимальна [5].

Поставим эту задачу, как задачу линейного программирования. Пусть x_ij (x_ij≥0) – количество груза, отправляемого поставщиком A_i потребителю B_j. Неотрицательные переменные х_ij тоже можно записать в виде матрицы:

Х= , (2)

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

Z= (3)

Матрица Х с неотрицательными элементами x_ij называется планом перевозок, X_ij – количество перевозимого груза от i-го к j-ому потребителю. Функция Z называется целевой функцией, которая характеризует суммарные затраты перевозки грузов [8].

Условия транспортной задачи удобно записать в виде следующей транспортной таблицы (таблица 1)[5].

Таблица 1-Транспортная таблица

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

Обозначим суммарный запас груза у всех поставщиков - символом a, а суммарную потребность в грузе у всех потребителей – символом b,тогда:

, (4)

. (5)

Математическая формулировка транспортной задачи заключается в нахождении плана перевозок Х={x_ij}, который удовлетворяет системе ограничений:

. (6)

и доставляет минимум целевой функции z [5].

План перевозок, реализующий минимум целевой функции z, называется оптимальным.

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

С учетом введенных обозначений математическая модель транспортной задачи принимает вид:

(7)

, (8)

где z – целевая функция,

i=1,2…m,
j=1,2…n [8].

Для того чтобы транспортная задача (7) имела допустимые планы необходимо и достаточно выполнение равенства:

. (9)

Это условие называют также условием баланса, если оно выполнено, то транспортную задачу называют сбалансированной.

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

Если выполняется одно из условий:

a) перепроизводство

(10)

b) дефицит

, (11)

то модель транспортной задачи называют открытой (несбалансированной).

Для разрешимости транспортной задачи с открытой моделью необходимо преобразовать ее в закрытую:

1) при выполнении условия a) необходимо ввести (n+1)-й фиктивный пункт потребления, объем спроса которого равен величине дисбаланса.

(12)

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

2) при выполнении условия b) вводится фиктивный пункт производства, A_m+1 объем производства, которого равен величине дисбалансу.

(13)

Стоимости перевозок от этого фиктивного поставщика полагаются равными нулю или, при наличии дополнительной информации, соответствующим значениям штрафов за недопоставку продукции и т.п. Например, чтобы гарантировать удовлетворение спроса некоторого пункта потребления в задаче с условием дефицита можно назначить очень высокую стоимость перевозок (штраф) от фиктивного пункта производства до этого пункта потребления [3].