Транспортная задача с неправильным балансом.

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

Sa_i=Sb_j (где i=1,.., m; j=1,...,n) (3)

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

Баланс транспортной задачи может нарушаться в 2-ух направлениях:

1. Сумма запасов в пунктах, отправлении превышает сумму поданных заявок

Sa_i>Sb_j (гдеi=1,...,m; j=1,...,n);

2. Сумма поданных заявок превышает наличные запасы

Sa_i<Sb_j (где i=1,...., m; j=1,...,n);

Условимся первый случай называть "Транспортной задачей с избытком запасов", а второй — "Транспортной задачей с избытком заявок".

Рассмотрим последовательно эти два случая:

Транспортная задача с избытком запасов.

В пунктах А₁ A₂,..., A_m имеются запасы груза a₁, а₂,..., а_m, пункты B₁, В₂,..., В_n подали заявки b₁, b₂,..., b_n, причём

S a_i> S b_j, (где i=1, m; j=1, n).

Требуется найти такой план перевозок (X), при котором все заявки будут выполнены, а общая стоимость перевозок минимальна. Очевидно при этой постановке задачи некоторые условия-равенства транспортной задачи превращаются в условия-неравенства, а некоторые — остаются равенствами.

X_i,j £ a_i (i=1 …, m).

X_i,j = b_i (j=1 …, n).

Mы умеем решать задачу линейного программирования, в какой бы форме — равенств или неравенств ни были бы заданы её условия. Поставленная задача может бытъ решена, например, обычным симплекс-методом. Однако, задачу можно решить проще, если искусственным приемом свести её к ранее рассмотренной транспортной задаче с правильным балансом. Для этого, сверх имеющихся n пунктов назначения B₁, В₂,..., В_n, введём ещё один, фиктивный, пункт назначения В_n+1 которому припишем фиктивную заявку, равную избытку запасов над заявками

B_n+1 = S а_i, - S b_j, (где i=1, …, m; j=l,..., n),

а стоимость перевозок из всех пунктов отправления в фиктивный пункт назначения b_n+1 будем считать равным нулю. Введением фиктивного пункта назначения В_n+1 с его заявкой b_n+1 мы сравняли баланс транспортной задачи и теперь его можно решать как обычную транспортную задачу с правильным балансом.

Транспортная задача с избытком заявок.

Эту задачу можно свести к обычной транспортной задаче с правильным балансом, если ввести фиктивный пункт отправления A_m+1 с запасов a_m+1 равным недостающему запасу и стоимость перевозок из фиктивного пункта отправления во все пункты назначения принять равным нулю.

5. Составление опорного плана.

Решение транспортной задача начинается с нахождения опорного плана. Для этого существуют различные способы. Например, способ " северо-западного угла ", способ минимальной стоимости по строке, способ минимальной стоимости по столбцу и способ минимальной стоимости таблицы.

Способ " северо-западного угла ". Будем заполнять таблицу перевозками постепенно начиная с левой верхней ячейки (“ceвеpo-западного” угла таблицы). Будем рассуждать при этом следующим образом. пункт B₁ подал заявку на 18 единиц груза. Удовлетворим эту заявку за счёт запаса 48, имеющегося в пункте A₁, и запишем перевозку 18 в клетке (1,1). После этого заявка пункта B₁ удовлетворена, а в пункте A₁ осталось ещё 30 единиц груза. Удовлетворим засчёт них заявку пункта В₂, (27 единиц), запишем 27 в клетке (1,2);

оставшиеся 3 единицы пункта а₁ назначим пункту В₃. В составе заявки пункта В₃ остались неудовлетворенными 39 единиц. Из них 30 покроем за счет пункта А₂, чем его запас будет исчерпан, и еще 9 возьмём из пункта Аз. Из оставшихся 18 единиц пункта Аз 12 выделим пункту В₄; оставшиеся 6 единиц назначим пункту В₅, что вместе со всеми 20 единицами пункта А₄ покроет его заявку. За этом распределение запасов закончено; каждый пункт назначения получил груз согласно своей заявки. Это выражается в том, что сумма перевозок в каждой строке равна соответствующему запасу, а в столбце — заявке. Таким образом, нами сразу же составлен клан перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи:

Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок С_i,j.

Другой способ — способ минимальной стоимости по строке — основан на том, что мы распределяем продукцию от пункта А_i, не в любой из пунктов В_j, а в тот, к которому стоимость перевозки минимальна. Если в этом пункте заявка полностью удовлетворена, то мы убираем его из расчетов м находим минимальную стоимость перевозки из оставшихся пунктов В_j. Во всем остальном этот метод схож с методом "северо-западного угла". Способ минимальной стоимости по столбцу аналогичен предыдущему способу. Их отличие состоит в том, что во втором способе мы распределяем продукцию от пунктов B_i к пунктам А_j, по минимальной стоимости C_j.i. Опорный план, составленный способами минимальных стоимостей, обычно боже близок к оптимальному решению. Клетки таблицы, в которых стоят ненулевые перевозки, являются базисными. Их число должно равняться m + n - 1. Необходимо отметить также, что встречаются такие ситуации, когда количество базисных клеток меньше чем m + n - 1. В этом случае распределительная задача называется вырожденной. И следует в одной из свободных клеток поставить количество перевозок равное нулю.

Составляя план по способам минимальных стоимостей в отличии от плана по способу "северо-западного угла" мы учитываем стоимости перевозок С_i.j, но все же не можем утверждать, что составленный нами план является оптимальным.

 

Литература:

 

1. Боборыкин В.А. Математические методы решения транспортных задач. Л.: СЗПИ, 1986

2. Геронимус Б.А. Экономико-математические методы в планировании на автомобильном транспорте. М.: Транспорт, 1982

3. Кузнецов Ю.Н., Кузубов В.И., Волощснко А. Б. Математическое программирование. М.: Высшая школа, 1980

12	Поделиться:

Воспользуйтесь поиском по сайту: