Навигация
Сумма запасов в пунктах, отправлении превышает сумму поданных заявок
12383
знака
1
таблица
0
изображений
1. Сумма запасов в пунктах, отправлении превышает сумму поданных заявок
Sai>Sbj (гдеi=1, ...,m; j=1, ...,n);
2. Сумма поданных заявок превышает наличные запасы
Sai<Sbj (где i=1, ...., m; j=1, ...,n);
Условимся первый случай называть "Транспортной задачей с избытком запасов", а второй — "Транспортной задачей с избытком заявок".
Рассмотрим последовательно эти два случая:
Транспортная задача с избытком запасов.
В пунктах А1 A2, ..., Am имеются запасы груза a1, а2, ..., аm, пункты B1, В2, ..., Вn подали заявки b1, b2, ..., bn, причём
S ai> 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
Похожие работы
... сразу же составлен план перевозок, удовлетворяющий балансовым условиям. Полученное решение является опорным решением транспортной задачи. Составленный нами план перевозок, не является оптимальным по стоимости, так как при его построении мы совсем не учитывали стоимость перевозок Сij . 3. Метод потенциалов. Пусть имеется транспортная таблица, соответствующая начальному решению, хil= для ...
... . Система векторов условий транспортной задачи линейно независима тогда и только тогда, когда из соответствующих им клеток таблицы нельзя образовать ни одного цикла. Следовательно, допустимое решение транспортной задачи , i=1,2,…,m; j=1,2,…,n является опорным только в том случае, когда из занятых им клеток таблицы нельзя образовать ни одного цикла. Метод вычеркивания. Для проверки возможности ...
... . При этом значения cij соответствуют коэффициентам целевой функции исходной замкнутой транспортной задачи (1) и в последующем не изменяются. Элементы xij соответствуют значениям переменных промежуточных решений транспортной задачи линейного программирования и изменяются на каждой итерации алгоритма. Если в некоторой ячейке xij=0, то такая ячейка называется свободной, если же xij>0, то такая ...
... ). Требуется распределить все работы между всеми рабочими так, чтобы время выполнения работ было минимальным, а каждую работу выполнял только один рабочий. §4. Решение транспортной задачи в Excel В качестве примера я рассмотрел транспортную задачу для 2 складов и 5 магазинов. · В ячейки C4:C5 записал объемы продукции, имеющиеся на 2 складах. · В ячейки E5:I5 - заявки на продукцию, ...
0 комментариев