Предыдущая страница реферата | 1  2

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

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

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

Sai>Sbj (гдеi=1, ...,m; j=1, ...,n);

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

Sai S bj, (где i=1, m ; j=1, n).

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

Xi,j £ ai (i=1 …, m ).

Xi,j = bi (j=1 …, n ).

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

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

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

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

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

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

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

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

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

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

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

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

Литература:

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

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

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

Скачали данный реферат: Karasevich, Jurkov, Jasakov, Эльмпт, Judashkin, Dmitrij.
Последние просмотренные рефераты на тему: индия реферат, доклад африка, предмет курсовой работы, реферат памятники.





Предыдущая страница реферата | 1  2