Реферат: Решение транспортной задачи

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